A Link Quality Based Dispersity Routing Algorithm for Mobile Ad Hoc Networks

Published Online August 2012 in MECS

Mobile Ad Hoc networks (MANET) play an important role in providing ubiqutous services and are envisioned to support future generation networks . Research in this area is becoming popular due to wide ranging applications supported. MANET’s are characterized by fast changing topology , limited battery power and constrained resources. MANET’s enable easy deployment as they do not need any infrastructure like base stations.

As MANET’s are expected to support real time multimedia services, network capacity provisioning and

Quality of Service(QoS) guarantees are some of the key issues to be addressed . Multipath routing schemes are often seen as a better alternative in not only providing parallel fail safe paths but also seen as a good choice for facilitating network provisioning and realizing QoS guarantees. Its effectiveness in providing bandwidth aggregation and load balancing is already proved in the wired networks and is now currently gaining relevance in the context of Mobile Ad Hoc Networks and Mesh networks. In this work, a design for load balancing the network load which can tackle congestion and at the same time extend network life time is proposed. Multipath load balancing overcomes the capacity limitation of single path routing by distributing data traffic on to multiple paths and reducing congestion by routing traffic through lightly loaded paths.

However, the advantages of multipath routing comes at a price as concurrent data transmission along multiple paths interfere with each other. Further ,when network traffic starts increasing, there will be increased level of contention among nodes coupled with higher collision level consequently leading to packet drops and network level congestion. So a routing metric needs to be judiciously selected while constructing multiple paths that avoids high interference areas and high contention areas. To ease out the network wide congestion ,we adopt congestion aware metric for route selection combined with a good traffic distribution strategy that distributes the load according to quality of a path .

As all nodes transmit on the same channel ,neighbouring nodes compete with each other for channel bandwidth resulting in inter-flow interference[1] . The inter-flow interference level experienced is directly proportional to the amount of load generated by the neighbouring nodes. It also has adverse effect on quality of the received signals significantly and can cause collisions ,packet loss leading to more energy consumption. We adopt MAC layer contention window size and interface buffer size of a node and its neighbouring nodes to capture inter-flow interference and load .To ensure network longevity only the intermediate nodes which have enough energy are allowed to participate in the routing process. The rest of the paper is organized as follows.

In section 2, we review related prior work. In section

• 3,    design of the proposed protocol is described. Section 4 introduces the working of Link Quality based Dispersity Routing Protocol .Performance evaluation and simulation results are presented in section 5 ,while conclusions are offered in section 6.

• II.    Related works

Quality of Service enhancements to routing protocols has become a necessary feature to meet the performance requirements of applications. Towards this, load balancing solutions are seen as an important way to alleviate congestion and for satisfying Quality of Service demands. Load balancing refers to distribution of network traffic among all portions of the network uniformly to improve resource utilization and fairness among nodes effciently. Shortest path routing does not consider traffic or load status of the intermediate nodes during route construction. This leads to increased concentration of traffic along the links which are part of the shortest path resulting in packet loss and faster energy drain rate. Load aware or delay based routing circumvents congested routes and select routes with lesser traffic or delay. Load or delay aware routing metrics [2],[3],[4],[5],[6] have been adopted by single path routing protocols to avoid congested routes.

Multipath routing is a natural choice for distributing the load evenly across the network. One important component of load balancing is that of traffic distribution. There are two strategies for distibuting traffic using multiple paths[7]. In one load balancing strategy ,multipath routing protocol may decide to forward the traffic over only one lightly loaded path and keep others as backup paths[8],[9] and in other case, traffic may be distributed over multiple paths concurrently[10],[11]. Load balancing protocols adopt metrics that characterize existing load or traffic on the paths and try to avoid such congested areas. Hence , routing paths discovered by load balancing protocols are always longer than shortest hop metric based routing protocols. One of the earliest works, MSR[10] introduces load balancing which distributes traffic using weighted round robin scheduling strategy. The criterion used to distribute the load is based on round trip time or RTT which is not an effective method of load evaluation. [11] distributes load such that total number of congested packets on each path is equal and does load splitting at packet level granularity. AMOR[12] chooses ETX (Expected Transmission Count) as the metric to optimize upon load distribution instead of shortest hop metric. [13] proposes a solution for load balancing , where every intermediate node records the number of primary paths passing through it. During route discovery, RREQ packets are dropped if the number of primary paths passing through that node has reached a maximum limit.

• [14]    considers number of valid routes of the intermediate nodes to represent load state and the source distributes the load based on the capacity of each path. In order to predict the occurrence of congestion in future ,count of RREP packets is used in[15]. Then a combined cost metric using current and future congestion status is used to evaluate the load and accordingly balance the load. [16] uses number of retransmission attempts for a successful data transmission and it is taken as a function of energy expended for transmission and reception . It addresses the issue of energy balancing but not balancing of the load.

But the above load balancing mechanisms does not consider the effect of interpath interference arising due to concurrent data transmissions. Intereference is a limiting factor in ad hoc networks that greatly influences the network’s performance due to the shared nature of the medium. The impact of interference has been studied [17] by presenting a multi-commodity flow problem with interference related constraints using a conflict graph to model the constraints imposed by interference. It is shown that adopting interference reduction measures can bring in improvement in the throughput. [18] presents a stochastic framework for analysis of interference and develops a mathematical model to assess network capacity for multipath routing using non linear programming. But these methods proves to be inefficient even for small networks due its complexity .[19] tries to reduce the transmission range of the nodes using power control to minimize unnecessary interferences experienced by the neighbouring nodes .[20] uses topology control to reduce the effect of interference . [21] proposes an interference aware metric Network Allocation Vector Count (NAVC) based upon which delay and available bandwidth is predicted .

As there are different approaches used to consider interference, proposed work adopts a simple traffic based approach to measure interference. This paper adopts a load balancing solution with interference awareness. The solution proposed here ,estimates the load as well as interference based on channel condition indicators like contention window and MAC Layer buffer size.

• III.    Protocol Design

In this section, we deal with the design of proposed work Link Quality based Dispersity routing algorithm for load balancing(LQLB) .

• A.    Problem Formulation

The goal of this design is to find lightly loaded node disjoint paths with less interference and which balances the traffic over multiple paths adaptively according to the link conditions and at the same time extend the network life time. Key issue to be addressed while splitting traffic over multiple paths is ,how to apportion the traffic according to the quality of each path. Next, is the choice of an appropriate metric that reflects quality of a path.

Before we introduce our design ,we will putforth the working principle behind it. Consider a sample network shown in figure 1. Node A wants to communicate with node H. Nodes B,C,D,E,F,G are intermediate nodes. Filled circles are neighbor nodes . Adjacent rectangles beside the neighbor nodes show the size of MAC layer buffer. Shaded portion of the rectangle indicate unutilized portion of the queue. Node disjoint multipath routing algorithm would select three paths ABCH, ADEH, AFGH based on shortest hop metric without considering the quality of the links. But selecting path ABCH would lead to congested links and severe throughput degradation due to more number of neighbours actively transmitting resulting in more amount of contentions . Bigger queue size of a node would mean higher load and intense traffic activity. Comparatively, path AFGH would experience lesser level of contention as it has only one neighbour with less load. Our protocol will not select path ABCH as we consider contentions caused due to neighbouring node activity. Our route selection procedure not only finds node disjoint paths but also integrates contention window size and queue size calculation to capture interflow interference. It also balances load across paths by traffic splitting .

In the following section ,we describe how this proposed metric link-Quality accounts for interference caused due to neighboring node traffic and also measures the current load of a link.

Figure 1 : Sample Network depicting interfering neighbours and their queue stataus.

• B.    Metric for Interflow Interference and Load

One of the important factors that cause interference is traffic generated by the nodes . Traffic produced per node and the traffic relayed by the node determines the amount of interference created [22] . In addition ,number of neighbour nodes within the transmission range and interference range are potential sources of interference. Level of interference experienced by a node also depends on distance of its neighbour nodes. Active neighbours busy transmitting is another factor influencing interference. Ad hoc networks uses DCF[23] as the medium access mechanism supported by IEEE 802.11 MAC layer protocol. When one or more nodes try to access the channel simultaneously collision is experienced following which contention window is set to CWmin. .The size of the contention window determines how long a node would backoff before attempting to gain access to the channel. In other words CW[5] indicates the busyness of the medium and can be considered as a useful metric for contention and traffic interference. A large CW would mean more amount of traffic interference. As nodes transmit using the same channel , they have to contend with each other for sharing bandwidth causing traffic interference [1] . The level of interference depends on the amount of load generated by the interfering nodes.

In order to capture the effects of neighboring node transmissions we use average size of contention window and the queue size of the current node and its neighboring nodes. Traffic conditions of the neighboring nodes is propagated using Hello packets periodically. Each node maintains a neighbor table shown below to store traffic information of its neighboring nodes.

• IV.    Link Quality based Dispersity Routing Protocol

This section describes a solution for load splitting derived by integrating path quality metric into AODVM[24] routing protocol.

• A.    The Load Splitting algorithm

During initialization phase every node collects information about the size of its CW, its buffer occupancy level, and remaining battery level . In order to contain transient bursts the size of contention window found is averaged out using exponential weighted moving average method. Similarly average size of the interface buffer and energy values are calculated. Each node then constructs a neighbour table which stores the list of its neighbouring nodes along with their respective traffic load which is again expressed by its contention window size. AODV’s Hello messages are modified to convey information about neighbour node’s contention window size ,queue size and battery level. Using the information from the Hello messages each node constructs a neighbour table. Format of a neighbour table is shown below.

Table 1. Neighbor Table contents

TimeStamp

Avg-CW size

Avg-Queue size

Rem Energy Level Node-Id

Using the information from the neighbour table ,each intermediate node stores the cost found using the equation 1 where i refers to an intermediate node ,n refers to number of neighbor nodes of i .

n

Cost_i = CW_i*Q-Size_i*1/Rem-Energy +∑( CW j *Q-Size j )  (1)

j=0

CW indicates average size of the contention window , Q-Size represents the average size of the MAC Buffer. Quality of a path is taken as the cumulative cost of intermediate nodes that form a path. We enhance AODVM’s route discovery procedure to support link quality based load splitting. Route Request packets are overloaded to note the size of contention window, remaining energy level and queue size information by the intermediate nodes. Let cost A be the cost of path A, cost B the cost of path B and N be the total amount of data to be forwarded from a source to a particular destination . Let the total cost of two paths A and B be Total-cost , then the number of data packets( N A) forwarded along the first path A would be

N_A = ( cost_A / Total-cost) *N                 (2)

• B.    Route Discovery

Route Discovery procedure is initiated by the source when it does not have a route in its cache to a destination by broadcasting a RREQ packet. When an intermediate node receives a RREQ packet it forwards the packet only if the node has energy beyond a threshold value. While a RREQ is forwarded ,each intermediate node inserts its cost which is computed as in (1) . Similarly every internediate node checks if it has enough energy and subsequently appends its cost in to the RREQ packet . When the RREQ reaches the destination it will have the cumulative cost of the path. When additional RREQ’s arrive destination selects four least cost paths. Destination then generates RREP for the four selected best paths. Source, after receiving the best paths starts with data transmission by distributing the packets proportional to the quality of each path found as in (2) . Only two paths with best cost is selected for data transmission.

• C.    Route Maintenance

Route Maintenance is initiated when a link break is detected by a node by transmitting a RERR packet . Data transmission is continued along the next prediscovered path stored by the source. Number of packets forwarded along this new path is proportional to its cost . If all prediscovered paths fail a new route discovery procedure is initiated by the source.

• V.    Performance Evaluation

In this section, we bring out a comparative study of two load balancing strategies. First one being LQLB-1path, a load balancing strategy that distributes the load along one best path computed by the proposed link quality metric. Source switches to next best path when currently active path fails due to link failure. Second load balancing strategy LQLB-2path distributes the traffic along two best paths concurrently .

• A.    Simulation Environment

  Evaluation of the proposed protocol is carried out using OMNET++ , a discrete event simulator which supports complete physical, data link and MAC layer models for simulating wireless ad hoc networks. We simulated a network of 50 mobile nodes placed randomly in an area of 1500 x 600 square meters. Each node is assumed to use IEEE 802.11b radio interface. A source and a destination is selected randomly. Free space propagation model is assumed as the channel model. Each node is assumed to have a constant transmission range of 250 meters and a channel capacity of 2Mbps. Source destination pairs are spread randomly over the network. Mobility pattern of the mobile nodes is generated using Random waypoint model . Speed of a mobile node is assigned as 5 meters/sec. Energy level of all nodes is initialized as 100mJ. Amount of energy expended while transmitting and receiving is assumed to be 0.0003mJ and 0.0001mJ respectively.

We evaluate the performance of the proposed work using following parameters.

• 1.    Packet Delivery Ratio(PDR): This is defined as ratio of number of packets that have successfully reached the destination to the total number of packets sent by the source. This metric is expressed in percentage .

• 2.    Throughput : Throughput refers to the total number of packets successfully reaching the destination per second. This metric is an indicator of the quality of a routing path and the effectiveness of the load balancing mechanism.

• 3.    Average contention window size: The size of the contention window reflects the level of contention suffered by a node. A large contention window indicates larger level of traffic interference. It is measured in terms of number of slot times.

• 4.    Route Life Time: Route Life Time indicates how stable a path is and it shows how long can it sustain data transmission. It is measured by the time elapsed between the generation of a RREP packet and the generation of a RERR packet .

• 5.    MAC Buffer overflow: This occurs when a node cannot enqueue a packet as it’s queue is full due to congestion. In other words, low buffer overflow level indicates how well traffic is distributed over the entire network.

• 6.    Average Energy Consumed per Bit: Remaining energy of the network is sum of the remaining energy of all nodes in the network . Similarly initial energy of the network is found by summing up initial energy levels of the nodes. Energy consumed then is the difference between the remaining energy and the initial energy of the network . Ratio of the energy consumed to total number of bits transferred gives the average energy consumed per bit.

• 7.    Network lifetime :A mobile node with its remaining energy level less than a threshold equal to 20% of the initial energy is considered dead. Network lifetime is

equal to the difference in time when network is initialized to the time when the first node is dead.

• B.    Simulation results

Performance of two load balancing strategies LQLB-2Paths , LQLB-1Path is compared. Figure 2 shows the packet delivery ratio achieved for both strategies. LQLB-2Paths performs better than LQLB-1Path .This shows the advantage of performing load balancing using traffic distribution along two paths. Initially there is not much difference between two schemes ,but as network load increases beyond 100 Kbps there is marked difference in their performance asserting the fact that load distribution is advantageous when network traffic is high.

Figure 2: Packet Delivery Ratio under varying Network Load.

Increase in the PDR achieved initially is around 20% but when network load increases ,up to 55% improvement is achieved . On an average ,improvement in the PDR achieved is 27%. Another parameter of interest studied is throughput.

Figure 3:Throughput against varying Network Load.

As this proposed work avoids high contention areas and selects routes with less interference ,packet loss and retransmissions will be reduced. This accounts for the increase in throughput which can be observed from the Fig. 3. The size of the contention window indicates backoff interval of a node on the occurrence of collision. Lesser size would mean lesser level of contention and hence less traffic interference.

Figure 4: Contentention Window Size against varying Network Load.

Average growth of contention window is lesser in case of LQLB-2Paths . This can be attributed to the fact that our protocol avoids routes which will have less neighboring node contention. In other words LQLB-2Paths avoids nodes with lesser level of traffic activity at the neighboring nodes. Fig. 4 shows this.

Figure 5: MAC Buffer overflow under varying Network Load.

To further demonstrate the advantage of our protocol we compare the level of buffer overflow .Buffer overflow occurs when nodes gets congested. Amount of buffer overflow in LQLB-2Paths is very less compared to LQLB-1Path method that does not split the load which is shown in Fig. 5. Queue size monotonously increases as the node is depreived of channel due to contention by neighboring node traffic. As this proposed protocol can distribute the load evenly lesser amount of buffer overflow occurs at the nodes in LQLB-2Paths case .

Data packets are simultaneously routed along two paths because of which latency tends to decrease .

Figure 6: Latency against varying network load

Figure 7: Average Energy Consumed against varying network load

But this method has the disadvantage that it gives rise to additional overhead at the transport layer in the form of packet reordering. Fig. 6 shows the improvement in the latency achieved . Other than reducing end to end delay, load balancing mechanisms positively influence the energy consumption also. Adopting proper load balancing solutions can reduce creation of hot spots which are highly congested regions.

Figure 8: Network Life Time against different Network Load

Nodes in congested regions tend to loose energy at a rapid rate due to increased number of retransmissions resulting out of packet losses. Energy expenditure incurred by adopting load balancing is shown in Fig. 7. Energy expended is less in case of load balancing with traffic spliiting as LQLB-2Paths have lesser degree of control overhead thereby saving upon the transmission/retransmission cost . As energy expended by the nodes gets reduced due to traffic splitting ,network lifetime is extended. Fig 8 and 9 show the enhancement achieved.

Figure 9: RouteLife Time against varying Network Load

Further set of simulations were conducted to evaluate the performance against mobility .

Figure10 : Packet Delivery Ratio for different pause Times.

For this pause time is varied keeping the node speed 5m/s. Though initially both the methods of load balancing show similar performance ,as data transfer progresses load splitting mechanism outperforms which is shown in Fig. 10.

Figure 11: Network Throughput against different pause Times.

Throughput is also compared for both load balancing mechansims. Load splitting aimed at balancing the load brings improvement in throughput. Fig. 11 shows the increase in throughput experienced which increases when node mobility decreases as there will be fewer route changes.

Figure 12: Contention Window variation for different pause Times.

Contention window size does not show much difference for both schemes as network load is not varied Fig. 12 shows the contention level experienced by the nodes which is affected only when traffic level varies.

Figure 13: Latency for different pause Times.

Latency also shows improvement when the degree of mobility is varied. Load splitting based on path quality has reduced latency under reduced level of mobilty. For increased level of mobility latency invariably increases . When mobility level is very low or when network topology is almost static there is no difference in latency for both schemes. Fig. 13 depicts the latency experienced by both the schemes. Under increased level of mobility energy consumed in LQLB-2Paths is lesser than LQLB-1Path load balancing strategy. Energy expended by the nodes is reduced as LQLB-2Paths selects routing paths based on path quality and hence will not route through congested areas and high interference regions. Fig. 14 shows this.

Figure 14: Energy consumption against pause Time.

A network sustains for a longer period of time if the rate at which energy is consumed for data transmision and reception activities is less. As LQLB-2Paths will have lesser amount of packet losses and retransmissions ,Network lifetime is better. Fig. 15 shows Network Life Time achieved for both schemes .

Figure15: Network life Time against pause Times.

Link breaks leading to generation of RERR packets are used to asses route lifetime . Path quality based routing enhances route life time . Link breaks are caused due to congestion or mobility.

Figure 16: Life Time of a route for different pause Times.

Fig.16 shows improvement in route life time for LQLB-2Paths when compared to LQLB-1Path due to the reduced amount of control overhead .

• VI.    Conclusions

A fundamental issue that adversely impacts the performance of multipath routing protocol is that of interference. Another deterrent factor is that of link level congestion . Hence an efficient load balancing solution is necessary that addresses both the above mentioned issues. This paper presents an algorithm that leverages link quality information for load balancing by distributing the load . A metric that effectively captures interflow interference and that also accounts for the traffic load is proposed. Link quality is evaluated by considering contention, load and energy metrics. Interfering traffic load due to neighbouring nodes is also considered. Performance evaluation of the proposed traffic splitting strategy is carried out under varying network load conditions and mobility levels show improvement over the load balancing strategy without traffic splitting.