Open access peer-reviewed chapter

Autonomous Traffic Balancing Routing in Wireless Mesh Networks

By Sangsu Jung

Submitted: December 4th 2011Reviewed: April 28th 2012Published: August 14th 2012

DOI: 10.5772/48540

1. Introduction

Wireless mesh networks (WMNs) are attractively deployed as a backhaul for public Internet access with the advantages of network performance and cost efficiency. With the cooperation of multiple mesh nodes, a packet is transmitted through multi-hops to reach a destination. Wireless medium experiences relatively an unstable environment due to interferences of wireless signals. As traffic increases, a communication environment becomes worse. Similarly, as more mesh nodes join a WMN, a network performance is also degraded due to increasing interferences. Therefore, challenges of a WMN are how to accommodate a dynamic nature of wireless medium and achieve the scalability.

A typical WMN serves hub-and-spoke type accesses, where a mesh gateway (hub) connects to the Internet for mesh clients as shown in Fig. 1. In other words, a mesh node is required to communicate with just one-of-many mesh gateways similar to anycast communications [1], [2]. For anycasting, conventional routing schemes [3], [4], [5] are developed with modifications of existing unicast routing protocols. That is, the schemes usually select the closest destination among multiple service gateways. Thus, they are inefficient in taking benefits of having multiple gateways. Even though some protocols [6], [7], [8] utilize multiple gateways for load balancing, they convey flooding overheads to collect traffic load information for re-routing and require associations among the gateways.

Classically, back-pressure routing [9] and geographic routing [10] are considered as alternatives for traditional hop-count-based routing. Back-pressure routing is well-known to achieve throughput-optimal by adaptively selecting paths depending on queuing-dynamics. However, it unnecessarily chooses long paths and degrades network performance by keeping old data packets. This problem manifests critically in lightly- or moderately-loaded cases [11]. On the other hand, conventional geographic routing is scalable with no flooding overhead, but it is vulnerable to avoiding congested hot spots due to its simple geographical routing metric. Even though some enhancements of geographic routing for congestion mitigation, it entails similar overheads such as perimeter routing or other face routing.

To overcome the limitations of conventional approaches, we suggest a novel routing scheme inspired by electrostatic potential theory [12], [13], [14], [15]. The main motivation comes from the fact that packet movements can be corresponding to electric charge behaviors governed by electrostatic potential. By constructing a virtual potential field for routing, our scheme forwards a packet following the steepest gradient direction towards any mesh gateway (a destination inside a WMN) as presented in Fig. 2. Interestingly, our scheme based on nature characteristics resembles a hybrid behavior of back-pressure and geographic routing schemes. With the help of numerical analysis techniques, our scheme operates in a distributed manner. Furthermore, our formula is equipped with a Gaussian function to adjust a routing reflecting ratio of back-pressure and geographic routing schemes for dynamic traffic environments.

Our work is relevant to recent approaches [16], [17], [18] motivated by physical systems of which system models have been studied for several centuries.

This chapter introduces a practical solution to develop large-scalable WMNs. The organization of this chapter is as follows. In section 2, we review relevant works and address distinguished features of our scheme. Section 3 provides a background of our work and designs a traffic-adaptive autonomous routing scheme for WMNs. In addition, we evaluate our scheme through simulations. (Section 4) Finally, we conclude this chapter in Section 5.

2. Related works

Our scheme is a family of gradient-based routing [19], [20], [21], [22]. In gradient-based routing, scalar values are assigned to each node to form a field gradient, so packets traverse followed by the lowest gradient. Several proposed works differ by the target network, communication pattern, and parameters to determine scalar values for a field.

A. Basu et al. have introduced potential-based routing (PB routing) [20] for unicast Internet traffic. Their idea is to set potentials with queue lengths on the top of the standard shortest path (hop count) routing. Here, the steepest gradient routing enables routers to be less congested. Even though the aim of this work is quite similar to ours, it is for fixed wired networks and unicast with flooding overheads. Regarding an anycast, V. Lenders et al. propose a density-based strategy [21] for wireless ad hoc networks in the framework of gradient-based routing. Under the scheme, a field is constructed based on node density and routing is towards a dense group destination, which increases the success probability of packet transmission. However, the routing scheme cannot react to traffic congestion; hence, even a worse scenario could occur where traffic is densely populated. For an anycast in a WMN, R. Baumann et al. develop HEAT routing [22] where a temperature field is used for routing. In this work, two metrics are considered to influence a temperature value: one is the distance from a node to a gateway, and the other is the robustness of a path towards a gateway. Because this model is based on Laplace's equation, which is a special form of Poisson's equation, it cannot deal with traffic dynamics so that congested hot spots degrade the routing performance.

On the other hand, our scheme utilizes the numerical analysis techniques of a finite element method (FEM) [23], [24] and a local equilibrium method (LEM) [25], to achieve a distributed algorithm [12], [13], [14], [15]. Similarly, a finite difference method routing (FDMR) is suggested in [26] reflecting link-diversity. It is also a gradient routing scheme based on Laplace's equation. However, it is known that an FDM is restricted to a grid topology [23], [24]; hence, another algorithm is desired for arbitrarily-shape topologies.

Furthermore, we adopt a Gaussian function to tune our scheme for dynamic networking environments. Conventionally, Gaussian functions have been applied in the Gaussian filter [27] in signal processing, the Gaussian beam [28] in microwave systems, self-similar network traffic generation [29] in WAN (wide area network) and LAN (local area network), and other modeling researches [30]. Even though a Gaussian function has been variously applied in many areas such as statistics and engineering, there has been little approach to use a Gaussian function for routing modeling.

In conclusion, the novelties of our scheme are characterized by anycast capability in WMNs, load balancing, distributed algorithm, scalability with constant control overheads, self-adaptation, and random topology accommodation.

3.1. A hybrid routing inspired by electrostatics

Our aim is to combine geographic routing and back-pressure routing represented as:

$\Pi =aD+\left(1-a\right)T,$uid4

or

${\Pi }^{\text{'}}=D+\frac{1-a}{a}T,$uid5

where routing metric $\Pi$(or $\Pi$`) is a linear combination of geometric distance Dand traffic component Tadjusted by ratio a. Interestingly, a distributed form of Poisson's equation [12] can be matching to (2), which describes the movement behaviors of electrostatic charges [12], [13]:

$\begin{array}{cc}\hfill \phi \left(v\right)& =\left\{{\Sigma }_{k=1}^{n}\frac{\left(\phi \left({p}_{v},k+1\right){\stackrel{\to }{r}}_{v},k-\phi \left({p}_{v},k\right){\stackrel{\to }{r}}_{v},k+1\right)·\left({\stackrel{\to }{r}}_{v},k-{\stackrel{\to }{r}}_{v},k+1\right)}{{A}_{k}}+\alpha q\left(v\right)\right\}/{\Sigma }_{k=1}^{n}\frac{\parallel {\stackrel{\to }{r}}_{v},k-{\stackrel{\to }{r}}_{v}{,k+1\parallel }^{2}}{{A}_{k}}\hfill \end{array}$uid7

where routing metric potential of node v, $\phi$(v), is obtained by consideration of neighbor nodes' potential $\phi \left({p}_{v},k\right)$, distance component ${\stackrel{\to }{r}}_{v},k$, and queue length q(v)as shown in Fig. 3. In [12] and [13], we describe how to derive (3) by using an FEM. On the other hand, every node operates (3) in an iterative manner to get converged potential which is used as a routing metric under boundary conditions:

$\pi \left(G\right)=Min,$uid8
$\pi \left(B\right)=Max,$uid9

where Gis the set of mesh gateways and Bis the set of boundary nodes which are located at the outer boundary of a WMN. As a result of an LEM (refer to Fig. 4), a potential field is formed inclined from mesh nodes to mesh gateways in a range of [Min, Max]. According to a routing policy, a packet traverses following the steepest gradient field towards a mesh gateway which has the lowest potential. (See Algorithm 1) The steps for our routing scheme (ALFA-Advanced, ALFA-A) are as follows:

1. Step 1. In an initial network deployment stage, boundary conditions are defined as (4) and (5).

2. Step 2. Every mesh node v, which is non-mesh gateways and -boundary nodes assigns zero as its potential value.

3. Step 3. Every mesh node v exchanges its potential with its neighbor nodes nvia a hello message.

4. Step 4. Every mesh node v calculates its potential with (3).

5. Step 5. A forwarding node is determined by:

$arg\underset{{n}_{v},k\in {N}_{v}}{max}\frac{\phi \left({n}_{v},k\right)-\phi \left(v\right)}{\parallel {\stackrel{\to }{r}}_{n},k-{\stackrel{\to }{r}}_{v}\parallel },$uid16

In cases of one-way traffic such as for IPTV, the downlink FIB may not be updated often enough because of the absence of uplink traffic, and, thus, dynamic load balancing cannot be achieved. This problem can be mitigated by each mesh node sending association refresh messages periodically to a gateway for a downlink path.

The principal ability of our scheme is autonomous load balancing among multiple mesh gateways as well as among mesh nodes. For example, when a congested hot spot forms due to an extensive local traffic area, it causes a potential increase of nodes around the hot spot due to the increase of the queue lengths. This potential increase prevents packets from ingressing the region; packets are forwarded away from the congested high-potential area as shown in Fig. 5 and 6.

3.2. Tuning for traffic dynamics

The characteristics of (3) are affected by tunable parameter $\alpha$, which determines the reflecting ratios of geographic routing and back-pressure routing. That is:

1. When $\alpha$of (3) is large, the sensitivity to traffic congestion increases and the behavior of our scheme resembles that of back-pressure routing.

2. When $\alpha$of (3) is small, the sensitivity to traffic congestion decreases and the behavior of our scheme is close to that of geographic routing.

In a previous work, ALFA [12], the constant value of $\alpha$is assumed so that the reflection degrees of both routing schemes are fixed. In other words, ALFA is only optimized for a specific network environment with no dynamic traffic consideration. In our scheme, we develop a new form of Î± adopting a Gaussian function. The reasoning behind this setting is come from:

1. If traffic load level is low under network capacity, a routing decision is not necessary to consider a traffic component (queue length) because the network resources are sufficient.

2. If traffic load level is high more than network capacity, a routing decision is not necessary to consider a geographic factor because the short path marginally contributes to minimizing delay.

Interestingly, the shape of a Gaussian function can exhibit low reflection of the routing metric and high reflection of that via queue length as shown in Fig. 7. Therefore, we set $\alpha$as:

$\alpha =C{e}^{-R{\left(q\left(v\right)-Q\right)}^{2}}$uid25

where Cis a constant, Ris a sensitivity for queue length, and Qis a bounded value from which queue length cannot affect the value of $\alpha$. Because we can adjust C and R with respect to a network characteristic, our scheme flexibly adopts to a dynamic network scenario. Previously, we apply a Gaussian function to an FDM-based routing scheme [15]. As an extension, we introduce a Gaussian function applied to an FEM and evaluate our proposed scheme in the next section.

4. Performance evaluations

In this section, we evaluate our scheme (ALFA-Advanced, AFLA-A) compared with conventional ALFA, geographic routing (GR), and back-pressure routing (BPR) using NS2 [31]. Incorporating the PHY/MAC models of IEEE 802.11, we conduct simulations with randomly deployed 100 mesh nodes and two mesh gateways in 1000m$×$1000m areas. The average distance between two mesh nodes is set to 200m. The transmission and interference ranges are set to 250m and 550m, respectively. We assume the two-ray ground model as a radio propagation model. We select 15 mesh nodes located almost equally far away from two mesh gateways as traffic source nodes (which generate traffic loads from 20-40Mbit/s) and 20 mesh nodes as back-ground traffic (10Mbit/s) generation nodes. The total mesh gateway capacity is 2Mbit/s channel bandwidth. The size of each data packet (UDP) is 2000 bytes long. The maximum queue size is set to 2000. Every mesh node utilizes RTS/CTS and hello-message-jittering. For boundary conditions, we assign -1 for the potential of mesh gateways and 0 for the boundary nodes. On the other hand, we modify GR and BPR to accommodate anycast communications, in such a way that a mesh node first checks which mesh gateway is the closest to itself. Removing the data of a transient period, we collect the data of the mid 1000s of out of 1600s simulations run period. In the simulations, we set $\alpha$as 0.005 for conventional ALFA considering previous empirical results. For our scheme, we set 2 and 0.5 for C and R, respectively.

First, we observe the load balancing behaviors of the schemes with the aggregate throughput. Because our purpose is to increase the aggregate throughput in an entire network by efficiently sharing the loads, instead of just even distribution of the loads, which is unnecessary when there are sufficient network resources. Similar to BPR, ALFA utilizes multiple paths for mitigating traffic congestion but avoids unnecessary explorations of a large number of paths observed in BPR at some point. However, ALFA-A maintains stable performance regardless of traffic loads.

Second, we show the hop counts of utilized paths per source. Due to the genetic nature of ALFA and ALFA-A, the hop counts of those two tend to maintain small hop counts comparable with GR. Still, the strength of ALFA remains only for a specific environment.

Finally, we conduct simulations to investigate the robustness of our scheme to node failures. With the constant control overheads, ALFA and ALFA-A maintain the performance of a network under node failures.

In Fig. 8, we present aggregate throughput for each scheme. ALFA-A, ALFA, and BPR diversify paths so that they show relatively higher performance compared with GR. The difference between those three schemes comes from the number of unnecessary paths. ALFA is only optimized for a limited case and BPR is known to utilize tremendous number of paths which increases path-lengths. In case of ALFA-A, it dynamically adjust the level of traffic reflection in its routing metric considering the traffic load level, and thus, it shows the highest performance among four schemes.

4.2. Hop counts

We illustrate the hop count distribution for each packet in Fig. 9. ALFA-A and ALFA behave as GR under lightly-loaded cases, whereas BPR traverses relatively long paths, as reported in [11]. Because BPR exploits unnecessarily long paths due to large hop counts, including frequent route loops, it is very harmful to delay-sensitive applications. BPR shows inferior performance compared with ALFA-A, ALFA, and GR. The result of high hop counts can be understood with long queueing delays at every hop. The long queueing delay of BPR is caused by the large queue lengths. As a queue increases, the queueing delay also increases. We observe that ALFA-A shows the shortest hop counts compared with those of others because ALFA-A tends to take short paths and to avoid nodes with large queue lengths. In GR, which maintains short path lengths, packet paths tend to be concentrated on a specific region and form a congested hot spot. Such a hot spot causes large queueing delays. In the case of BPR, it has a large number of hops and large queue sizes at the same time; hence, the delay performance is undesirable. This behavior is also originated from the number route looping in routing as shown in Fig. 10. Because GR does not consider detouring, it shows zero route-looping. Similarly, ALFA-A adapts its routing behavior appropriately to a network state, it also shows zero route-looping. Differently, ALFA and BPR generate frequent route-looping due to overestimate congestion degree in a network.

4.3. Robustness to node failures

Intrinsically, ALFA-A and ALFA adaptively utilize multiple paths in search of less congested areas toward a mesh gateway in a hop-by-hop fashion. This property also enables packet routing to be robust to node failures. Because ALFA-A and ALFA always maintain a field gradient toward mesh gateways, if one node disappears, they automatically select an alternative forwarding node with no additional route re-establishment. This feature corresponds to the stateless property similarly to geographic routing.

We present the robustness of ALFA-A as the same as ALFA against node failures in Fig. 11. As a performance metric, we consider a packet delivery ratio that is defined as the percentage of packets that have successfully arrived at destinations out of the total packets sent by sources. From the figure, we see that ALFA-A and ALFA can maintain approximately a 95% or higher packet delivery ratio when the ratio of broken links over the entire network varies from 0% to 30% of the total links. In contrast, the delivery ratio of GR drops from 86% to 52% when the ratio of broken links reaches 30% because GR experiences voids or dead-ends when nodes disappear. In the case of voids or dead-ends, GR conducts face routing to track an available alternative forwarding node, but it incurs longer delays due to a larger number of hops [32]. On the other hand, BPR experiences relatively low degradation (from 72% to 68%) due to its adaptive routing mechanism.

All routing schemes evaluated in this chapter, ALFA-A, ALFA, GR, and BPR, significantly reduce the control overheads as they require no state-vector flooding mechanism, which is used in traditional reactive routing protocols such as AODV [33]. Like the other two, ALFA requires just one-hop neighbor information for route decisions. That is, it only uses a 'hello' message with the interval of 1s, which is commonly used for all routing protocols to find one-hop neighbors. The 'hello' message delivers information for route decisions such as potential and location. This simple local behavior achieves scale-free routing, and simultaneously achieves network-wide load balancing routing in response to congestion. This merit is an advantage in the cases of congestion and node failures different from flooding-based schemes that consume large network resources with route re-establishment processes.

An underlying understanding of constant control overheads is that a local behavior is important and sufficient to make a routing decision, and we can avoid requiring an accurate solution for the global potential field. In fact, the computation cost of every update might be O(|S|)within a small subset of nodes S, meaning that the impact of a local change is quickly seized by the neighbor nodes. A global impact is slowly gained through an LEM property and affects the routing as packets traverse a network with multiple hops. In other words, a dynamic queue length change at a far node affects little in choosing the next hop.

Compared to the routing cost of the traditional shortest-path routing, O(|S${}^{\text{3}}$|), such as in the Floyd Warshall's ”all pairs shortest path” algorithm [34], ALFA-A is obviously a superior solution for scalable WMNs. In addition, the memory space requirement for routing is greatly reduced because every node stores only its location and potential and those of one-hop neighbors. The total storage required in an entire network is O(|S|+|S|).

5. Conclusions

In this chapter, we deal with a potential-based anycast routing scheme for WMNs, which achieves autonomous traffic balancing and path-length reduction. By analogy with an electrostatic potential theory governed by Poisson's equation, we derive a routing metric that shows the hybrid behaviors of back-pressure routing and geographic routing. The beauty of our routing scheme is adopting the strengths of the two aforementioned routing schemes while overcoming the limitations of the two. We adopt an FEM and an LEM to design a distributed potential assignment as the routing metric; only one-hop neighbor information is required for scale-free global routing. The stateless property of our scheme contributes to maintaining robustness to node failures and eliminating requirement of flooding overheads for re-routing. Furthermore, our scheme utilizes a Gaussian function to dynamically adapt to rapidly changing environments. Using simulations, we investigate how our scheme behaves with respect to a tuning parameter, which characterizes a routing behavior similarly to back-pressure routing or geographic routing. In addition, we demonstrate the superior performance of our scheme compared with conventional schemes in the aspects of throughput, load balancing, and path lengths. Considering the implementation issues of a protocol in practical applications, our scheme is the appropriate solution combining the properties of back-pressure routing and geographic routing.

As a future work, applications of our scheme can be extended to other mesh networking areas based on sensor networks, machine-to-machine communications, and LTE-Advanced, with practical network service models.

More

© 2012 The Author(s). Licensee IntechOpen. This chapter is distributed under the terms of the Creative Commons Attribution 3.0 License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.

How to cite and reference

Cite this chapter Copy to clipboard

Sangsu Jung (August 14th 2012). Autonomous Traffic Balancing Routing in Wireless Mesh Networks, Wireless Mesh Networks - Efficient Link Scheduling, Channel Assignment and Network Planning Strategies, Andrey V. Krendzel, IntechOpen, DOI: 10.5772/48540. Available from:

Related Content

Next chapter

Achievable Capacity Limit of High Performance Nodes for Wireless Mesh Networks

By Thomas Olwal, Moshe Masonta, Fisseha Mekuria and Kobus Roux

First chapter

Optical Fiber Sensors

By Marcelo M. Werneck and Regina Célia S. B. Allil

We are IntechOpen, the world's leading publisher of Open Access books. Built by scientists, for scientists. Our readership spans scientists, professors, researchers, librarians, and students, as well as business professionals. We share our knowledge and peer-reveiwed research papers with libraries, scientific and engineering societies, and also work with corporate R&D departments and government entities.