Differentiated Service Based Interference-Aware Routing for Multigateway Multiradio Multichannel Wireless Mesh Networks

Abstract

Routing metric helps select optimal path from source node to destination node. It is the key for the whole network performance and needs to be designed carefully. Existing routing metrics have at least one of the limitations listed below. (1) Internet-oriented traffic is considered only, and client-oriented traffic is omitted, or vice versa. (2) Route selection is done in mesh network with a single gateway, so route selection is only related to selecting a route path without selecting gateway node. (3) The isotonic requirement cannot be satisfied. In order to conquer the limitations aforementioned and guide route selection, an isotonic differentiated service based interference-aware routing metric is proposed for mesh networks with multiple gateways. Traffic pattern, node load, gateway load, and intraflow and interflow interference are all taken into consideration to guide the selection of best path and best gateway. Simulations reveal that the proposed metric outperforms state-of-art metrics in terms of the average network throughput and average end-to-end delay.

1. Introduction

Due to the characteristics such as high bandwidth, fast deployment, easy installation, and low cost investment, wireless mesh networks (WMNs) are considered to be potential technologies for constructing next generation wireless communication systems [1]. Capacity reduction caused by interference is a major problem faced by WMNs [2]; one efficient way to solve this problem is to use multiple channels and equip each node with multiple radio interface cards, which is termed as multiradio multichannel (MRMC) technology [3]. Recently research on WMNs mainly focuses on MRMC WMNs, especially routing metrics.

Routing metric is composed of a series of mathematical integrated measurements on link quality. For given source and destination, one or several paths will be selected according to the results from metric calculation. So the quality of routing metric design directly affects the end-to-end network performance. From the first routing metric specifically designed for WMNs, expected transmission count (ETX) [4], many routing metrics have been proposed by academic community, but they have at least one of the limitations listed below. (1) Internet-oriented traffic (traffic between mesh clients and the Internet) is considered only, and client-oriented traffic (traffic between clients) is omitted, or vice versa. At present, people want to access the Internet and get service from it, so the Internet-oriented traffic is dominant. As newly emerging applications get popular, there may be substantial random and unpredictable traffic caused by client-oriented traffic [5]. As a result, Internet-oriented traffic and client-oriented traffic will coexist in WMNs. (2) Gateway discovery process is not taken into consideration. Gateway nodes inform mesh routers about their existence and relevant information through gateway discovery process, which is very important for clients who want to access the Internet. Considering networks with multiple gateways, routing selection is related to not only selecting a proper route path but also selecting a proper gateway node. Gateway nodes are easy to become capacity bottleneck; thus proper gateway selection is especially crucial for the whole network performance. (3) The isotonic requirement cannot be satisfied. Isotonicity is a necessary and sufficient condition for Bellman-Ford and Dijkstra's algorithm to find optimum weight path and loop-free forwarding [6]. Nonisotonic routing may introduce more overhead into the network in order to select path among multiple possible paths between a given pair of source and destination.

In order to conquer limitations of current routing metrics, a differentiated service based interference-aware routing metric (DSIA) is proposed for WMNs with multiple gateways in this paper, which comprehensively takes traffic pattern, node load, gateway load, and intraflow and interflow interference into consideration and provides powerful assistance for routing selection in MRMC WMNs. Extensive simulations show that the proposed metric is efficient in various scenarios; it can dramatically improve network throughput, end-to-end delay, and average packet loss ratio.

This paper is organized as follows. In Section 2, we review the previous works on routing metrics for WMNs and highlight their limitations. Section 3 provides our DSIA routing metric, which has the service differentiated capability. The performance evaluation of the proposed routing metric using network simulator 2 (NS-2) is given in Section 4. Our conclusions and future work are presented in Section 5.

2. Related Works

In this section, we overview some well-known routing metrics proposed for WMNs and we also provide a detailed analysis of their drawbacks.

ETX and expected transmission time (ETT) [7] are basic components for several other routing metrics. They both use probing packets to acquire packet delivery ratio, which introduces overhead to the networks. Also ETX and ETT deal with interference indirectly. Metric of interference and channel switching (MIC) [8] and interferer neighbors count (INX) [9] routing metrics both consider intraflow interference and interflow interference. They are proposed based on the protocol interference model, which uses the transmission range and interference range concept, but the fact that physical signal power can also affect the successful reception of a packet is not considered. Interference-aware routing metric (iAWARE) [10] is a physical interference model based metric. The problem is that the component used to describe intraflow interference makes iAWARE nonisotonic. Weighted end-to-end delay (WEED) metric in [11] also considers the impact of physical signal power on transmission and its drawback is the same as iAWARE.

All aforementioned routing metrics omit gateway node; they are used in WMNs with client-oriented traffic only or Internet-oriented traffic only, where gateway selection problem does not exist. In practice, WMNs with more than one gateway node are commonly used; therefore the gateway selection problem should be solved.

The works in [12] are closest to this paper, the authors proposed the best path to best gateway (BP2BG) routing metric for WMNs with multiple gateways. During route selection, not only the best path to gateway, but also the best gateway should be selected, which contributes to load balance among gateway nodes. The BP2BG metric for path p is defined as

$$\begin{array}{cc}& \text{BP}\mathrm{2}\text{B}{\text{G}}_{\left(g,p\right)}=\frac{\alpha \left(\mathrm{1}-\text{DACI}\right)+\left(\mathrm{1}-\alpha \right)\text{PQ}}{\mathrm{2}},\end{array}$$

(1)

where DACI is the distribution available capacity indicator of gateway node g and α is a parameter satisfying $0<\alpha <1$ . PQ is the path quality, which is shown in

$$\begin{array}{cc}& \text{P}{\text{Q}}_{s\to g}=\frac{\text{Ma}{\text{x}}_{k\in p}\left(\text{LQ}{\text{M}}_k\right)+{{\displaystyle \prod }}_{k\in p}\text{LQ}{\text{M}}_k}{\mathrm{2}},\end{array}$$

(2)

where ${\text{LQM}}_k$ is the quality metric of link k, which is made up of expected link quality ELQ and interference ratio IR, as shown in (4) and (5), respectively:

$$\begin{array}{cc}& \text{LQ}{\text{M}}_k=\frac{\beta \times \text{IR}+\left(\mathrm{1}-\beta \right)\times \text{ELQ}}{\mathrm{2}},\end{array}$$

(3)

$$\begin{array}{cc}& \text{ELQ}=\frac{\mathrm{1}}{d_f},\end{array}$$

(4)

$$\begin{array}{cc}& \text{IR}=\frac{{\sum }_{l\in v^{\prime }}{P}_R\left(l\right)}{P_{\max }},\end{array}$$

(5)

where $d_f$ is forward packet delivery ratio, $P_{\max }$ is the maximum tolerable interference at the receiver, $P_R(l)$ is interference power from an interfering node l, β is a parameter satisfying $0\le \beta \le 1$ , and $v^{\prime }$ is the set of nodes in the interference range R.

BP2BG has three limitations. The first limitation, which is common for all of the existing routing metrics, is that it only considers that Internet-oriented traffic and client-oriented traffic are omitted, but actually Internet-oriented traffic and client-oriented traffic coexist in WMNs. The second limitation is that forward packet delivery ratio and physical interference are used to describe path quality, without considering the impact of logical interference on route selection. The third limitation is that BP2BG is not isotonic. As demonstrated in literature [6], isotonicity is a sufficient and necessary condition for Bellman-Ford and Dijkstra's algorithm to find minimum weight paths, so routing protocols based on Bellman-Ford and Dijkstra's algorithm may not find minimum weight path between a pair of nodes when using BP2BG as routing metric. The resulting suboptimal paths may degrade network performance [8].

First, the definition of isotonicity is given below [6].

Definition 1.

Assuming, for any path a, its metric is defined by a metric function $W(a)$ and the concatenation of two paths a and b is denoted by $a+b$ , the metric function $W(·)$ is isotonic if $W(a)\le W(b)$ implies both $W(a+c)\le W(b+c)$ and $W(c^{\prime }+a)\le W(c^{\prime }+b)$ , for all a, b, c, $c^{\prime }$ . See Figure 1 for details.

Figure 1

Example of isotonicity.

We can see from the figure that, for paths a and b, if $W(a)\le W(b)$ , even if we add any path before or after them, the relationship between the whole paths will not change; that is, from $W(a)\le W(b)$ we can get $W(a+c)\le W(b+c)$ and $W(c^{\prime }+a)\le W(c^{\prime }+b)$ . Then we say metric $W(·)$ is isotonic.

Next we use a simple topology in Figure 2 to show that BP2BG is not isotonic. For simplicity, we just omit the DACI part in (1) and use PQ as routing metric, as BP2BG is nonisotonic because of the path quality component PQ. Assuming β in BP2BG is set to 0.5, in Figure 2, one number is associated with each link—the LQM of the link. When looking for path from S to T using distance vector routing protocol based on PQ, according to (2), the network will calculate the PQ values for these paths:

•  

path $S\to A\to C$ : $(0.5\times 0.5+0.5)/2=0.375$ ,

 

path $S\to B\to C$ : $(0.7\times 0.1+0.7)/2=0.385$ ,

 

path $S\to A\to C\to T$ : $(0.5\times 0.5\times 0.7+0.7)/2=0.4375$ ,

 

path $S\to B\to C\to T$ : $(0.7\times 0.1\times 0.7+0.7)/2=0.3745$ .

Figure 2

Nonisotonicity of BP2BG.

From the above calculation, we can find out that metric of path $S\to A\to C$ is smaller than that of path $S\to B\to C$ , but we cannot draw conclusions that metric of path $S\to A\to C+C\to T$ ( $S\to A\to C\to T$ ) is smaller than that of path $S\to B\to C+C\to T$ ( $S\to B\to C\to T$ ). According to the definition, metric PQ does not satisfy the isotonic condition and we can say PQ is not isotonic; thus BP2BG is not isotonic. In this case, the minimum metric path from S to C is $S\to A\to C$ ; node C only tells its neighbors about the metric of this path. Hence, node S does not have a chance to check the metric of $S\to B\to C\to T$ , which is the correct minimum metric path. Therefore, node S incorrectly sets its path to T as $S\to A\to C\to T$ and forwards any packets for T to node A.

We use one example to show why nonisotonic routing causes more overhead. For example, when selecting path for flow from node S to node D, if distance vector routing protocol based on isotonic routing metric is used, for any intermediate node A, it receives routing requests (RREQs) from its neighbors and selects the minimum metric subpath from S to A as the best subpath, as isotonicity ensures that the best path from S to D includes this best subpath; then node A broadcasts one routing request (RREQ) including this best subpath to its one-hop neighbors. If distance vector routing protocol based on nonisotonic routing metric like BP2BG is used, for any intermediate node A, it selects the best subpath from S to A as the best subpath, but nonisotonicity cannot ensure that the best path from S to D includes this best subpath. Thus in order to select the correct minimum metric path, intermediate node A has to reserve several subpaths; for any subpath, node A broadcasts one RREQ including this subpath to its one-hop neighbors. If the number of reserved subpaths is N, then node A should broadcast N RREQs; if the path length from S to D is M hops, the RREQ overhead of routing protocol based on nonisotonic routing metric is $M·N$ times that of routing protocol based on isotonic routing metric. These RREQs cause more overhead for WMNs.

From the analysis above, we conclude that an isotonic metric which can take traffic pattern, node load, gateway load, and intraflow and interflow interference into consideration comprehensively is still in need. In the following section, we present our DSIA routing metric which can conquer all the limitations aforementioned.

3. Proposed Differentiated Service Based Interference-Aware Routing Metric

3.1. Gateway Discovery Process

Clients who want to access the Internet to get service must firstly acquire the existence of gateway nodes and related information, such as gateway identification. Such information can be informed through gateway discovery process, which can roughly be classified into three categories: active gateway discovery, passive gateway discovery, and hybrid gateway discovery [12]. Active gateway discovery [13] is employed in this paper to obtain the relative position of nodes from the gateway, which can be simply denoted by hop count distance from the gateway. In active gateway discovery process, message including the state of the gateway is broadcasted out periodically by the gateway itself; mesh routers that receive the message will update accordingly and then broadcast out the message again. Flood of this kind of message can affect the network performance, but, thanks to the static characteristics of WMNs, long broadcast period can be adopted, so the effect of flood message can be neglected. The concrete format of gateway discovery message is given in Table 1, where message identification is the only indicator for the message; gateway identification, say, host ID, is the indicator of gateway that yields the message; the position field keeps records of the relative position of other mesh nodes from gateway node, that is, hop count distance from gateway node. The value of the position field is initialized to zero and it is gradually increased as the message propagates; that is, it is increased by one each time the message passes through a node.

Table 1

Format of gateway discovery message.

Message identification

Gateway identification

Position

Upon receipt of gateway discovery message, a node first finds out whether it has received the same message before according to the message identification and gateway identification field of the message. If it has not received the same message before, it keeps records of corresponding information, updates the position field, and rebroadcasts the updated message; else it compares the value of the position field with recorded one; if the value of the position field in the message is smaller than that of the recorded one, the related information will be updated and the message will be rebroadcasted; otherwise the message will be simply discarded. The value of position field will be used later in DSIA routing metric, but how to use it depends on traffic pattern and we will show it below.

As the performance of the WMNs is mainly decided by its backbone network, clients are usually ignored and the corresponding access routers are considered instead. We use node and mesh router interchangeably in this paper. We define traffic-related factor as ${\delta }_l$ , which exhibits the service differentiated characteristics of DSIA routing metric. For a link l on which client-oriented traffic is routed, ${\delta }_l=\text{Position}/M$ , where Position is the value of the position field of above gateway discovery message for the endpoint of link l, that is, hop count distance from the gateway node, and M is the maximum hop count distance from nodes in the network to the gateway node, which is determined by network topology. When the network topology is given, M is a constant. For client-oriented traffic, links far away from gateway node are preferable; in this way, links adjacent to gateway node can be reserved for future Internet-oriented traffic, as links adjacent to the gateway node are the only routes for Internet-oriented traffic and it is easy for them to become capacity bottlenecks. For a link k on which Internet-oriented traffic is routed, ${\delta }_k=0$ .

3.2. Interference Model

The signal to interference plus noise ratio (SINR) of receiver is used to judge whether a transmission is successful or not; that is, a transmission from node j to node i is successful if the SINR value at the receiver i is above a predetermined threshold $\text{th}$ which is determined by propagation characteristics, such as channel and data rate:

$$\begin{array}{cc}& \text{SIN}{\text{R}}_i=\frac{P_i\left(j\right)}{N+{\sum }_{k\in v^{\prime }}{P}_i\left(k\right)}\ge \text{th},\end{array}$$

(6)

where N is the background noise, $v^{\prime }$ is the set of nodes carrying on parallel transmissions, and $P_i(j)$ is the received power of node i from node j. Physical interference model is not so strict compared to protocol interference model; it can capture the dynamic variance of interference inside the network. The interference ratio IR, which is defined as the ratio between SINR and signal-to-noise ratio (SNR), is used in this paper. The IR value for node i is shown below:

$$\begin{array}{cc}& \text{I}{\text{R}}_i=\frac{\text{SIN}{\text{R}}_i}{\text{SN}{\text{R}}_i},\\ \text{SN}{\text{R}}_i=\frac{P_i\left(j\right)}{N}.\end{array}$$

(7)

For a link $l=(i,j)$ , its IR is set to the smaller one of $\text{I}{\text{R}}_i$ and $\text{I}{\text{R}}_j$ ; that is,

$$\begin{array}{cc}& \text{I}{\text{R}}_l=\min \left(\text{I}{\text{R}}_i,\text{I}{\text{R}}_j\right).\end{array}$$

(8)

SINR and SNR used to calculate IR value are gained through passive monitoring technology from interface cards, so overhead introduced by active probing can be eliminated.

3.3. Channel Busy Time

Carrier sense multiple access/collision avoidance (CSMA/CA) is used by the IEEE 802.11 medium access control (MAC) layer. Before a node sends out a packet, it needs to monitor the channel; if the channel is idle for at least a short interframe space (SIFS) interval, the node will begin to transmit data; otherwise the node has to launch a counter, which is set to a random chosen integer value between 0 and current contention window. The node perceives the channel status at the beginning of each time slot; if the channel is idle, the counter is decreased by one and otherwise the counter is frozen. The node will not begin to transmit packet until the counter is decreased to zero. The receiver will send back acknowledgement of a distributed coordinated function interframe space (DIFS) interval after packet reception. Successful reception of the acknowledgement means successful transmission. For unsuccessful transmission, current contention window will be doubled, the counter will be reset, and the node has to wait for the counter to decrease to zero and begin to retransmit. Channel busy time (CBT) is time fraction when data keeps the channel busy. A channel is busy in two cases: one is that the node is transmitting data on this channel and the other is that the channel is occupied by adjacent transmission. CBT is defined as

$$\begin{array}{cc}& \text{CBT}=\frac{\text{TotalTime}-\text{IdleTime}}{\text{TotalTime}},\end{array}$$

(9)

where TotalTime is the entire monitoring time and IdleTime is the time when no data keeps the channel busy. CBT is proved to be the most precise means of measuring the utilization of channels in wireless networks and it can measure logical interflow interference more accurately than other measurements [14].

3.4. DSIA Routing Metric

DSIA routing metric is composed of three components: channel contention and position relevant load CC_PBLoad, which describes position relevant load, physical interference, and logical interflow interference; channel switching cost CSC, which describes intraflow interference; residual capacity fraction Capr, which exhibits gateway relevant information. These three components are defined below.

(1) CC_PBLoad. Consider

$$\begin{array}{cc}& {\text{CC}\_\text{PBLoad}}_l=\left(\mathrm{1}-{\delta }_l\right)·\text{Loa}{\text{d}}_l·\left(\mathrm{1}-\text{I}{\text{R}}_l\right)·\text{CBT},\\ \text{Loa}{\text{d}}_l=\frac{Q_{\text{wait}}}{Q_{\max }},\end{array}$$

(10)

where $Q_{\text{wait}}$ denotes the number of packets waiting in the buffer queue of the link receiver and $Q_{\max }$ is the maximum buffer queue length.

(2) CSC. CSC measures intraflow interference by considering channels used by two consecutive links; if they operate on the same channel, CSC will be set to a large value $w_{\mathrm{2}}$ and otherwise CSC will be set to a small value $w_{\mathrm{1}}$ . CSC is shown in the following:

$$\begin{array}{l}\text{CS}{\text{C}}_i=\{\begin{array}{ll}{w}_{\mathrm{1}}\hfill & \text{CH}\left(i\right)\ne \text{CH}\left(\text{prev}\left(i\right)\right)\hfill \\ w_{\mathrm{2}}\hfill & \text{CH}\left(i\right)=\text{CH}\left(\text{prev}\left(i\right)\right),\hfill \end{array}\\ \hspace{1em}\hspace{1em}\phantom{\text{aaaaaaaaaaaaiaaaaaa}}\mathrm{0}\le w_{\mathrm{1}}<w_{\mathrm{2}}.\end{array}$$

(11)

(3) Capr. Capr is residual capacity fraction, which can be obtained from the ratio between residual capacity and total capacity of the gateway node. For gateway node g, its Capr is

$$\begin{array}{cc}& \text{Cap}{\text{r}}_g=\frac{\text{ResCa}{\text{p}}_g}{\text{TotalCa}{\text{p}}_g},\end{array}$$

(12)

where $\text{ResCa}{\text{p}}_g$ is the residual capacity of node g and $\text{TotalCa}{\text{p}}_g$ is its total capacity.

So DSIA metric for path p can be expressed as follows:

$$\begin{array}{l}\text{DSIA}\left(p\right)={\displaystyle \sum }_{\text{link}\hspace{0.17em}l\in p}^n\text{CC}\_\text{PBLoa}{\text{d}}_l\\ \hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}+\gamma ·{\displaystyle \sum }_{\text{node}\hspace{0.17em}i\in p}^m\text{CS}{\text{C}}_i+\theta ·\left(\mathrm{1}-\text{Cap}{\text{r}}_g\right),\end{array}$$

(13)

where γ ( $0\le \gamma \le 1$ ) and θ ( $0\le \theta \le 1$ ) are adjustable parameters used to balance these three components. Larger θ means that gateway has larger impact on route selection. Larger γ means that intraflow interference has larger impact on route selection.

3.5. Isotonicity Demonstration

DSIA is an isotonic metric which takes traffic pattern, node load, gateway load, and interference into consideration and it can detect heavy load and heavy interference areas in the network and guide packets to bypass these areas. DSIA employs a virtual network to deal with the CSC component to achieve isotonicity, so the isotonicity demonstration for DSIA is the same as that in [8]. By introducing several virtual nodes to represent these possible channel assignments for the precedent links, DSIA can be translated into isotonic metric assignments to the virtual links. Since the DSIA of a real path is the same as the aggregated link metric of the corresponding virtual links and the metric assignment of virtual links are isotonic, efficient algorithms can find minimum DSIA metric paths. See [8] for details.

4. Performance Evaluation

In order to evaluate the decisions made by proposed DSIA routing metric, we designed extensive simulations to compare it with other metrics. Our experiments are carried out using NS-2.35. We also modify NS to support multichannel multiradio technology. The followings are our performance metrics, simulation parameters, and results.

4.1. Performance Metrics

• (i)

Average end-to-end delay: the end-to-end delay is defined as the time it takes a packet to reach the destination after it leaves the source. The average taken over all received packets is then computed, which is the average end-to-end delay.

(ii)

Average network throughput: the throughput is defined as the total amount of data bits actually received by a receiver divided by the time between receiving the first packet and the last packet. The average taken over all the receivers is the average network throughput.

(iii)

Average packet loss rate: the packet loss rate is defined as the ratio between the number of data packets received unsuccessfully and the number of packets supposed to be received. The average taken over all the receivers is the average packet loss rate.

4.2. Simulation Parameters

The simulations are based on IEEE 802.11b/g standard and the data transmission rate at the physical layer is 2 Mbps. Grid topology of $7\times 7$ squared grids is used; that is, each vertex is deployed with a mesh router and each edge denotes a wireless link. Mesh routers are equipped with radios of similar capability and configuration, which means that the communication and interference ranges are uniformly set to 250 m and 550 m, respectively, for all radios. The grid step is set to 250 m, which is the distance between adjacent nodes. This means that a node can communicate with its neighbors except the diagonal nodes. Traffic is generated by the constant bit rate (CBR) source and the packet size is set to 512 bytes. The parameters for all experiments are summarized in Table 2.

Table 2

Simulation parameter settings.

Simulation parameters	Values
Simulation time	100 s
Network area	1500 m × 1500 m
Network size	7 × 7
PHY/MAC technology	802.11 b/g
Data rate	2 Mbps
Traffic pattern	CBR (UDP)
Packet size	512 bytes
Transmission range	250 m
Interference range	550 m
Propagation model	Two-ray ground
Antenna	Omnidirectional

4.3. Superiority of DSIA

In order to demonstrate the effectiveness of our DSIA routing metric in distinguishing service and selecting gateway, respectively, the experiments are conducted in two scenarios. In the first scenario, DSIA routing metric is compared with MIC and INX in single-gateway WMNs with both kinds of traffic, that is, Internet-oriented traffic and client-oriented traffic. For single-gateway WMNs, there is no gateway selection problem, so we use DSIA in (13) without Capr component in performance simulations to demonstrate its service differentiated capability. In the second scenario, DSIA routing metric is compared with the nearest gateway selection algorithm, load-based gateway selection algorithm, and BP2BG in multigateway WMNs where Internet-oriented traffic is dominant and there is also client-oriented traffic which is used for creating interference and load. Here, we fix the number of gateways as two and the adjustable parameters γ and θ are both set to 1, which means that the three components in the routing metric are of equivalent importance.

4.3.1. Performance Comparisons in Single-Gateway WMNs

In single-gateway WMNs, our DSIA is compared with MIC and INX based on the metrics listed in Section 4.1. We fix the number of client-oriented traffic flows as 6 and vary the number of concurrent Internet-oriented traffic flows to observe the impact of number of flows on the network performances. Simulation results are given in Figures 3 and 4.

Figure 3

Performance comparisons versus network load in single-gateway WMNs.

Figure 4

Average packet loss rate with 1 Internet-oriented traffic flow.

From these figures, we can draw conclusions that MIC and INX have comparable performance; they both use active probing technology to acquire packet delivery ratio and available bandwidth and the probing packets used may collide with data packets and result in packet loss. Without service differentiated capability, the average network throughput using these two metrics almost linearly decreases as number of Internet-oriented traffic flows increases and the average end-to-end delay is stable. Our DSIA routing metric outperforms MIC and INX, as it comprehensively takes traffic pattern, node load, and intraflow and interflow interference into consideration and provides powerful assistance for routing selection. Thanks to the service differentiated capability of DSIA, during the route selection process for client-oriented traffic, links adjacent to the gateway node can be reserved for future Internet-oriented traffic. When Internet-oriented traffic is injected into the network, it has larger probability to find paths with low interference and traffic load, so more packets can be routed to destinations with low delay; thus the average network throughput may not decrease but increase and average end-to-end delay is lower than the other two metrics. Figure 4 gives the average packet loss rate with 1 Internet-oriented traffic flow.

As shown in Figure 4, DSIA has the lowest packet loss rate among the three metrics, which is due to the comprehensive consideration of factors affecting packet loss, so that packets will be guided to route through paths with low loss rate. Together with Figure 3, we can also draw conclusions that packet loss rate is complementary to the average network throughput. In view of their relationship, performance results about average packet loss rate are omitted in the following simulations.

4.3.2. Performance Comparisons in Multigateway WMNs

In multigateway WMNs, our DSIA is compared with the nearest gateway selection algorithm, load-based gateway selection algorithm, and BP2BG based on the metrics listed in Section 4.1. If the nearest gateway selection is used, the gateway with minimum hop count distance from the source will be selected. If load-based gateway selection is used, the gateway with minimum load will be selected. For simplicity, we call them nearest and load for short, respectively. We fix the number of Internet-oriented traffic flows as 4 and gradually vary the number of concurrent client-oriented traffic flows to observe the impact of gateway selection on the network performances. Here increasing flow number means adding more interference and load into the network. Simulation results are given in Figure 5.

Figure 5

Performance comparisons versus network load in multigateway WMNs.

These figures show that DSIA has better performance than the other three metrics and the reason is that DSIA considers various factors such as intraflow and interflow interference, node load, and gateway capability to select both the best gateway and the best route path. Heavy load and heavy interference areas can be avoided and more packets can be routed to destinations with lower delay, so the average network throughput is improved and the average end-to-end delay is reduced. The load-based gateway selection has better performance than BP2BG and the nearest gateway selection with respect to the average network throughput, as it can achieve load balance between gateway nodes and avoid capacity bottleneck occurring at the gateway. However, without considering interference, load-based gateway selection may select paths with high interference to lightly loaded gateway. For BP2BG, due to its nonisotonic characteristic, overhead is introduced into the network when selecting routes which offsets the benefit from the low-load gateway selection capability. Without considering interference and gateway load, nearest gateway selection may select paths with high interference to overloaded gateway, which may result in more packet loss. However, the nearest gateway selection and BP2BG both perform better than load-based gateway selection with respect to average end-to-end delay, because the nearest gateway selection selects paths with minimum hop count distance from the gateway and the effect of hop count distance is also considered in BP2BG. Shorter path can help reduce the end-to-end delay to some extent.

From the analysis above, DSIA can identify heavy interference and heavy load areas in the network; packets are routed to lightly loaded gateway through low interference and lightly loaded path, which can lead to less packet loss, shorter end-to-end delay; that is, more packets can reach destinations more quickly and more accurately and thus the network performance is improved.

5. Conclusion

In this paper, we research the problem of routing metric for multigateway WMNs. On the analysis of limitations of current routing metrics, a differentiated service based interference-aware routing metric DSIA is proposed, and the innovativeness of DSIA includes the following: (1) Internet-oriented and client-oriented traffic are both considered while designing DSIA metric, as they will coexist in WMNs in the future; (2) isotonic requirement is satisfied, so optimal paths can be found by using efficient algorithms such as Bellman-Ford or Dijkstra's algorithm; (3) best gateway and best path to best gateway are selected simultaneously, so traffic can be routed through low interference and low load paths and reach destinations more quickly and more accurately. NS-2 simulations in single-gateway and multigateway scenarios demonstrate its service differentiated and gateway selection capability, and network performance including network throughput, end-to-end delay, and packet loss rate is dramatically improved.

Our future works include (1) evaluating the performance of our routing metric in real testbed; (2) extending our routing metric to hybrid WMNs which is the combination of multihop wireless local area networks (WLAN) consisting of backbone of access points and decentralized mobile ad hoc networks (MANET) at lower end [15]; (3) due to the limited number of orthogonal channels used by current IEEE 802.11b/g standard, interference cannot be totally eliminated. Partially overlapped channels (POCs) [16–18] based design has been identified recently as an emerging technology to further eliminate interference and improve network capacity, so research on routing metrics for WMNs using POCs is another possible future direction.