Advanced
End-to-end Reliable Message Transmission Considering Load Balancing in Wireless Networks
End-to-end Reliable Message Transmission Considering Load Balancing in Wireless Networks
KSII Transactions on Internet and Information Systems (TIIS). 2014. Sep, 8(9): 3094-3109
Copyright © 2014, Korean Society For Internet Information
  • Received : June 25, 2013
  • Accepted : August 08, 2014
  • Published : September 28, 2014
Download
PDF
e-PUB
PubReader
PPT
Export by style
Share
Article
Author
Metrics
Cited by
TagCloud
About the Authors
Anh Tai Tran
Myung Kyun Kim

Abstract
This paper proposes a load balanced reliable routing protocol called LBR (Load Balanced Reliable routing) in wireless networks. The LBR protocol transmits messages through a reliable path considering the balancing of the traffic load. Recently, the authors have proposed a multipath-based reliable routing protocol called MRFR, which is an appealing protocol for fault tolerant reliable data transmission. However, However, MRFR has no concern with the problem of load balancing, which results in increasing congestion and consuming high energy at some network nodes. As a result, the problem affects negatively the performance of the network. Taking account of load balancing as a route selection criteria can avoid routing through the congested nodes and allows to find better routes. In this paper, we extend MRFR by considering load balancing in the route discovery process of reliable communication. The simulation results showed that the proposed protocol outperforms AODV in terms of end-to-end delay, packet delivery radio, and average jitter. Compared to MRFR, the LBR protocol has the same packet delivery ratio, and obtains a better efficiency of load balancing.
Keywords
1. Introduction
R outing in ad hoc wireless networks has been an active research area for many years. Recently, many interesting commercial applications intended for wireless networks in which most of the nodes being either stationary or minimally mobile have been developed [1 , 2] . The aim of routing protocols in such networks tends to improve the data transmission reliability.
The most common link metric being used in ad hoc routing protocols is minimum hop-count [3 , 4 , 5] . This metric selects a path minimizing hop-count between the source and destination without considering the lossy ratio of wireless links. In static ad hoc wireless networks, several studies have shown the poor performance of minimum hop-count [6 , 7] . Several estimators in terms of link quality have been proposed such as ETX [6] , RTT (Per-hop Round Trip Time) [8] and BW (Bandwidth) [9 , 10] . Among them, the ETX estimator is shown to be the best metric in static wireless networks [7] . To deal with the problem of reliable data transmission, our routing protocol uses ETX as a link metric to select high quality routes.
The problem of balancing load in wireless networks is one of the interesting topics being studied recently [11 , 12 , 13] . Routing protocols using shortest path can make the center of the network become “crowded”, because of having more paths to transmit data through the center than through the periphery of the network. This issue causes the increase of congestion and energy consumption for nodes near the center. Our routing protocol aims to increase the lifetime of network and has a good load distribution among nodes.
The rest of the paper is organized as follows. Section 2 describes related work. Section 3 gives a detailed description of LBR protocol for both reliable communication and load balancing. Section 4 presents the performance evaluation of the proposed protocol and Section 5 concludes the paper.
2. Related Work
Much work has been done for real-time and reliable data communication [14 , 15 , 16] . Many routing protocols use the shortest routing path to transmit data packets. Using the shortest path for data transmission may be a good choice for fast delivery, but cannot be a good choice for reliability due to the frequent link failures [6 , 17] . Physical layer parameters have been used as a link quality metric for routing in wireless networks. The authors of [18] presented the design and demonstration of a set of routing protocol mechanisms that significantly improves the transmission of real-time multimedia streams in a mobile ad hoc network. Their routing protocol extends DSR protocol [5] by using SNR (Signal-to-Noise Ratio) in route discovery to limit unreliable links. In that protocol, a node that receives a RREQ packet with the SNR of the packet below a threshold will not forward the packet. Some LQI (Link Quality Indicator)-based routing protocols have been proposed [16 , 19 , 20] . The authors of [21] showed that LQI-based routing could have negative effects on the network performance. Due to the short temporal dynamics of wireless channels, it is difficult to achieve good correlation between physical layer information and real link quality over different links. The ETX was widely adopted as a good link quality estimator for reliable communication in wireless networks [6 , 22] . Authors of [7] compared the performance of routing metrics including ETX, RTT, per-hop packet pair, and minimum hop-count. The authors showed that ETX is the best metric in static wireless networks. Authors of [22] used ETX as a link metric to find high quality paths for collecting data from sensor nodes to sinks. The authors showed that the performance of routing based on ETX outperforms MultihopLQI [19] . The authors of [23] showed that PRR based metrics such as ETX is more suitable in cost-sensitive routing scenarios and proposed an effective method for designing ETX-based multi-hop routing protocols. Recently, the authors of [24] have proposed a reliable routing protocol with fault tolerance capability called MRFR, which uses ETX as a link quality estimator.
Authors of [25] showed that using multiple paths for balancing load will not achieve a good results unless a large number of paths is used. The authors in [26] proposed a load balancing scheme in MANETs for handling congestion and uneven energy consumption of nodes. Depending on the self-traffic load of nodes, the nodes may intentionally give up packet forwarding to save energy. The authors of [27] proposed a grouping algorithm based on AODV [4] such that the routing load is balanced by evenly distributing source nodes into a number of groups. A routing protocol with congestion-aware path selection was proposed in [28] . The authors proposed a solution to the problem of congestion in MANETs by moving the traffic away from the shortest paths, which is usually the most congested area, to a less congested path. By removing congestion, we can minimize the number of data packets drops during transmission and reduce unnecessary delay due to path recovery. The authors of [29] presented a protocol which aims to balance the energy consumption among nodes to ensure the network connectivity and maximize the network life time. This protocol chooses the node with the highest energy level among potential nodes as the next hop for transmitting data.
3. LBR – A Load Balanced Reliable Routing Protocol
- 3.1 Expected transmission count (ETX)
The ETX of a link is the expected number of data transmissions requiring to send a data packet over that link, including retransmissions. The ETX of a route is the sum of the ETX of links over that route. Each node measures the probability that a data packet is successfully delivered to the receiver, known as the forward delivery ratio and denoted as df . The probability that an ACK is successfully received by the sender, which is called the reverse delivery ratio, is denoted as dr . The ETX value of the link is given by
PPT Slide
Lager Image
. Each node broadcasts probe packets of a fixed size to measure the delivery ratios dr and df [6] .
- 3.2 Definitions
The LBR protocol considers both the end-to-end reliability of routes and the load of each node when selecting a path between a source and a destination. The LBR uses ETX as a link quality estimator to measure the packet transmission reliability on the link. The end-to-end ETX of a path from node S to node D, e2eETX(x,y) , is defined as the sum of link ETX values in the path. We define the load of node n , load(n) , as the number of data packets that the node transmits and receives in a unit time during the previous window w from the current time. The load factor of node n, lf(n), is defined as the ratio between load(n) and the max_load(n) . The max_load(n) of node n denotes the maximum number of data packets that node n can transmit and receive in a unit time, which is calculated as follows.
PPT Slide
Lager Image
The max_transmission_rate(n) denotes the maximum number of bits that node n can receive or transmit in a unit time and the data_packet_size denotes the average size of data packets including all protocol headers. Thus, max_load(n) indicates the maximum number of data packets that node n can receive or transmit back-to-back in a unit time. The remaining load factor of node n, rlf(n) , is then defined as follows.
PPT Slide
Lager Image
The higher remaining load factor of node n means that it has smaller congestion. The LBR protocol uses rlf(n) and link-ETX values to find a path which has the smallest end-to-end ETX value and the minimum remaining load factor of the nodes in the path is the highest. Node n keeps its rlf( n ) by calculating the number of data packets being received and transmitted during the previous window. Node n also calculates ETX( n , m ) by exchanging and measuring beacon packets between its neighbor m and keeps ETX( n , m ) in its neighbor table.
- 3.3 Route Discovery
The LBR protocol uses ETX as a link quality estimator and considers the remaining load factor of a node as a criterion for balancing load when selecting a path from a source to a destination. Route discovery process is performed by exchanging RREQ (Route REQuest) and RREP (Route REPly) control packets between the source and the destination. Each node maintains a routing table for routing data packets. The routing table consists of a reverse route entry, RE[ id , p Hop, src ETX, src MRF], and a forward route entry, RE[ id , n Hop]. The id denotes the identifier of the path and p Hop and n Hop the previous and the next node of the path. The src ETX denotes e2e_ETX(S, x ) of the path from the source of the path id to the node x and src MRF denotes the minimum remaining load factor of nodes in the path id that we call the minimum remaining load factor of path id .
When a source node S wants to transmit data to a destination node D, it tries to set up a path by broadcasting RREQ packet. The RREQ packet carries RREQ[ id , etx , mrf ] where id denotes the ID of the path, etx denotes the sum of the ETX values of links over which the RREQ packet has traversed, and mrf indicates the minimum remaining load factor of nodes in the path through which the RREQ has been traveled. Initially, node S broadcasts RREQ[ id , etx =0, mrf = rlf (S)] packet. When a node Y with the remaining load factor rlf (Y) receives RREQ[ id , etx , mrf ] from its neighbor X, it performs as described in Fig. 1 .
PPT Slide
Lager Image
The process of LBR Route Request.
When node Y receives RREQ[ id , etx , mrf ] packet from X for a new path id, it creates a reverse routing entry for the path id as RE[ id , p Hop = X, src ETX = etx +ETX(X,Y), src MRF = mrf ]. After that, if node Y receives another RREQ[ id , etx , mrf ] packet from Z, it compares the routing information in the new RREQ packet with that of the path id in the routing table. If the routing information in the new RREQ packet is better than that of the path id in the routing table, it updates the reverse routing entry for the path id . We determine the better path in terms of two factors. The first one is the load balancing factor ( Condition 1 ). That is, if the minimum remaining load factor of the new RREQ packet ( mrf ) is greater than the existing minimum remaining load factor in the routing table ( src MRF) by more than H2 threshold, the path of the new RREQ packet is better than the existing path in the routing table. The second factor is the e2e_ETX values of the paths ( Condition 2 ). If Condition 1 is not true, LBR compares the e2e_ETX value of the new RREQ packet with the e2e_ETX value in the routing table and select the better (smaller) one. In the case of Condition 2 , however, we accept the new path in the RREQ packet only when it has smaller e2e_ETX value and the minimum remaining load factor in the RREQ packet is not lower than the existing one by more than H1 threshold.
Fig. 2 shows the two route selection conditions of the LBR protocol. The values of the two H1 and H2 thresholds may affect the performance of LBR protocol. H2 is defined as the load balancing factor. In which, routing table is updated if the minimum remaining load factor in RREQ packet is larger than the minimum remaining load factor in routing table entry by more than H2 threshold. H1 is defined as the end-to-end reliability factor. The routing table is updated if the RREQ packet has smaller e2eETX and the minimum remaining load in the RREQ is not smaller than the minimum remaining load in routing table by more than H1 threshold. Given H1, if H2 is small, the load balancing factor affects more than the end-to-end reliability factor in choosing route. Given H2, if H1 is small, the end-to-end reliability factor affects more than the load balancing factor in choosing route. We need to choose the optimal vaues of H1 and H2 parameters, which will depend on the application. We performed a simulation to see the impact of H1 and H2 threshold values to the performance of LBR protocol.
PPT Slide
Lager Image
Route selection conditions of LBR protocol.
If the path of the new RREQ packet is better than the existing one in the routing table in terms of Condition 1 or Condition 2 , node Y updates its routing table. After that, it has to rebroadcast the new RREQ packet to its neighbors to notify the better route. However, if node Y rebroadcasts the new RREQ packet immediately, the number of RREQ broadcast packets can be large. Thus, we use ΔdelayRREQ timer to reduce the number of RREQ broadcast packets. After broadcasting the first RREQ packet, node Y sets ΔdelayRREQ timer and, it collects all the RREQ packets arriving during that time, and selects the best route and rebroadcasts it when ΔdelayRREQ timer expires. The value of ΔdelayRREQ timer can affect the performance of the LBR protocol. If it is set to small value, each node cannot receive enough number of RREQ packets during that time, so the number of RREQ packets can increase. If it is given a large value, each node can select the best route by collecting enough number of RREQ packets, but the route establishment delay can increase. We evaluated the impact of ΔdelayRREQ timer to the performance of the LBR protocol in the performance evaluation section.
On receiving the first RREQ packet, the destination sets ΔdelayDEST timer, and collects all the RREQ packets arriving during that time, and selects the best route and transmits a RREP packet through the reverse of the selected path when ΔdelayDEST timer expires.
- 3.4 Route discovery example of LBR
As an example, a network with ETX value in each link and the remaining load factor in each node is given as shown in Fig. 3 , and the parameters H1 and H2 are chosen to be 0.1 and 0.2, respectively. The source S transmits RREQ[ id , etx =0, mrf =0.9] packet by broadcasting to find a route to the destination D.
PPT Slide
Lager Image
Route discovery example.
When receiving RREQ[ id , 0, 0.9] from S, node A and B will create the reverse routing entries for the path id , RE[ id , S, 1, 0.9] and RE[ id , S, 3, 0.9], respectively. After that, node A and B will update and rebroadcast the RREQ packet immediately, RREQ[ id , 1, 0.8] and RREQ[ id , 3, 0.5] respectively. Afterwards, when receiveing RREQ[ id , 3, 0.5] from B, node A will check Condition 1 and Condition 2 to compare the quality of the two paths, the path of the new RREQ packet and the existing path in the routing table. Because both Condition 1 and Condition 2 are not true, node A drops the new RREQ packet. On the other hand, when node B receives RREQ[ id , 1, 0.8] from A, it checks Condition 1 and Condition 2 to compare the quality of the two paths. Even though the Condition 1 is not true ( mrf src MRF = 0.8 – 0.9 < H2), the Condition 2 is true ( etx + ETX(A,B) = 2 < src ETX) and ( src MRF - mrf = 0.9 – 0.8 ≤ H1). Thus, node B updates its routing entry as RE[ id , A, 2, 0.8] as shown in Fig. 3 -(b). Likewise, when node E receives first RREQ[ id , 3, 0.5] from B and RREQ[ id , 1, 0.8] from A next time, it first creates its routing entry for path id as RE[ id , B, 5, 0.5], and updates it as RE[ id , A, 5, 0.7] because the Condition 2 is satisfied ( mrf src MRF = 0.8 – 0.5 ≥ H2).
If RREQ packets are forwarded like this, the destination node D receives multiple RREQ packets from its neighbors. After receiving the first RREQ packet for path id , the destination D sets ΔdelayDEST timer, and collects all the RREQ packets arriving during that time. In the example of Fig. 4 , node D receives RREQ[ id , 5, 0.7] and RREQ[ id , 3, 0.5] from E and C, respectively. Node D chooses RREQ[ id , 5, 0.7] as the better path because it is better in terms of load balance (0.7 – 0.5 ≥ H2), and when ΔdelayDEST timer expires, it sends a RREP packet through the reverse path set up while the RREQ[ id , 5, 0.7] was broadcasted. Thus, the established path from S to D is S-A-E-D with e2e_ETX = 6, mrf = 0.7.
PPT Slide
Lager Image
Route selection at the destination.
4. Performance Evaluation
In this section, we used the Qualnet simulator [30] to evaluate the performance of our protocol and compared with the AODV [4] and MRFR [24] protocols. AODV protocol uses the shortest path to transmit data, meanwhile, MRFR protocol is a reliable routing protocol, which uses ETX as a link quality metric. MRFR discovers routes that have the smallest end-to-end route-ETX value. Our simulations were implemented on a static 125-node network of 1500m*1500m. In all simulations, we set up five simultaneous flows with sources and destinations chosen randomly. The network traffic scenario is illustrated in Fig. 5 . Note that, because of space limitation, we only labeled some nodes used in our simulations. The results of almost all simulations were calculated as the average of the five flows. The data rate of each node is 5.5 Mbps. The data packet size is 512 bytes. The MAC layer model is 802.11 and the physical layer model is 802.11b. In most of the simulations, we use the transmission power of 15dBm (32mW) for all of the nodes. At the application layer, the constant bit rate (CBR) traffic is used. Source nodes of each flow send data packets from 1 CBR (1 packet per second) to 14 CBR (14 packets per second), depending on the simulation. During the first 30 seconds, the nodes just broadcast probes to measure link metrics and establish network stability. At the time of 30 seconds, the LBR protocol uses ETX to discover routes for the five flows. After routes have been established, the five flows start to transmit data. During the running time, in the event that a route failure occurs at any flow, the source of the corresponding flow broadcasts a RREQ packet to find a new route. In most of the simulations, the total running time is 240 seconds. The performance of LBR protocol depends on the two thresholds H1 and H2 for considering load balance. We performed a simulation to show the impact of H1 and H2 thresholds to the network performance.
PPT Slide
Lager Image
The network traffic scenario with 125 nodes and 1500m*1500m range.
- 4.1 Impact of H1 and H2 thresholds
The H1 and H2 threshold values can affect to the performance of the LBR protocol. To find the proper values of H1 and H2 thresholds, we conducted the following simulations. At first, we measured the end-to-end packet delivery ratio in terms of H2 threshold values after fixing H1 threshold value. Fig. 6 -(a) shows the result when H1= 0.1, H1= 0.2, and H1= 0.3. For all of the three cases, the end-to-end packet delivery ratio is small if the H2 threshold value is small. This shows that if the H2 threshold value is small, the load balance factor ( Condition 1 ) affects more than the end-to-end reliability factor ( Condition 2 ) when selecting paths, thus, it becomes difficult to find more reliable path. When the H2 threshold value increases, the end-to-end packet delivery ratio also increases as shown in Fig. 6 -(a). However, from the point of 0.2, even though we increase the H2 threshold value, there is no difference in the end-to-end packet delivery ratio. If we use a large H2 threshold value, it becomes difficult to find the better path in terms of load balance factor ( Condition 1 ), thus, we can see that the proper value of the H2 threshold is 0.2 in Fig. 6 -(a).
PPT Slide
Lager Image
Packet delivery ratio in terms of H1 and H2 threshold values.
As the next step, we measured the end-to-end packet delivery ratio in terms of H1 threshold values after fixing the H2 threshold to 0.2. As shown in Fig. 6 -(b), we can see that the proper value of the H1 threshold is 0.1. When we increase the H1 threshold value more after 0.1, the end-to-end packet delivery ratio has been decreased. The reason can be explained that as the H1 threshold value becomes larger, from 0.2 to 0.9, the end-to-end reliability factor ( Condition 2 ) becomes easier to be satisfied. However, if the new RREQ packet with low mrf value is accepted, the srcMRF value of the reverse routing entry for the path will be replaced with the mrf value. Afterwards, the path becomes easier to be replaced by the upcoming RREQ packets only by considering the Condition 1 , thus, it becomes easily replaced by the next path with high e2e_ETX value.
Fig. 7 shows the impact of H2 threshold on balancing load after fixing the H1 threshold to 0.1. In Fig. 7 , the horizontal axis denotes node ID and the vertical axis is the total number of data packets that each node forwards by the end of the simulation. As we can see in Fig. 7 , the load distribution is more even and better when H2 is 0.2 than when H2 is 0.4. This result shows that when we use a large H2 threshold value, the LBR protocol cannot find the better path in terms of the load balance factor because it becomes difficult to satisfy Condition 1 .
PPT Slide
Lager Image
The impact of large H2 threshold value to the load distribution.
- 4.2 End-to-end packet delivery ratio
Fig. 8 compare the packet delivery ratio of the routing protocols. The simulation result was calculated as the average of five flows. We measured the delivery ratio at different data loads, varying from 2 CBR to 14 CBR. The parameters H1 and H2 of the LBR protocol were chosen as 0.1 and 0.2, respectively.
PPT Slide
Lager Image
The end-to-end packet delivery ratio in terms of the packet traffic load.
The results show that our protocol and MRFR have almost the same delivery ratios at different loads and both two protocols obtain high delivery ratios (almost above 98%). Because both MRFR and LBR use ETX as a link metric for finding high quality paths, routes discovered by the two protocols are reliable. While our protocol and MRFR maintain the same performance at the different cases of load, the AODV protocol has a low delivery ratio when the data load is increased. For example, at a load of 14 CBR, MRFR and LBR have approximately delivery ratios of a 0.97, while delivery ratio using AODV is 0.83. This presents an performance improvement of 14%. AODV uses shortest paths for routing; however, it does not consider link loss ratios. Therfore, AODV can use routes with a high probability of route failure. In constrast to AODV, MRFR and LBR take into account the link loss ratios. This is why they find high quality routes and obtain a good performance.
- 4.3 Average end-to-end packet delay and jitter
We compared the average end-to-end packet delay and delay jitter of the three protocols. Fig. 9 shows the simulation result. As the data traffic is increased, the average end-to-end packet delay of the three protocols is increased. Although AODV protocol uses the shortest path routing, the average end-to-end packet delay is shown to be the highest in most cases. This is because, in the case of AODV, the route fault happens more frequently, which incurs the large average end-to-end packet delay. Besides using the e2e_ETX, our protocol uses the load balancing factor when selecting paths. As a result, congestion avoidance is better than that of MRFR. Therefore, as shown in Fig. 9 , our protocol has a little smaller average end-to-end delay and delay jitter than that of MRFR.
PPT Slide
Lager Image
Average end-to-end packet delay and delay jitter.
- 4.4 Load balancing efficiency
Our protocol uses an end-to-end reliable path while considering load balance to transmit data packets. To compare the load balancing efficiency of LBR and MRFR, we measured the number of data packets being forwarded during the simulation by each node. In our simulation, five flows transmit data simultaneously. Source nodes send data at rate of 10 CBR. Fig. 10 shows the distribution of the number of data packets forwarded at each node.
PPT Slide
Lager Image
Comparison of load distribution of LBR and MRFR.
As shown in Fig. 10 , the load distribution of our protocol is more even than that of MRFR. This result indicates that our protocol takes paths that avoid congested nodes near the network center while providing reliable data transmission.
Table 1 shows the comparison between our protocol and MRFR in term of the minimum, the maximum, the average value, and the variance of the number of forwarded data packets, respectively. The LBR and MRFR have the same minimum and average values. However, the maximum and the variance of MRFR are larger than those of our protocol, which shows that our protocol has more even load distribution compared to MRFR.
Comparison of load distributions of MRFR and LBR.
PPT Slide
Lager Image
Comparison of load distributions of MRFR and LBR.
Fig. 11 compares the average mrf (minimum remaining load factor) of routes using LBR and MRFR. The mrf of a route is minimum of remaining load factors of nodes in the route. A route with high mrf value means that it has a low probability of congestion and nodes of high remaning energy. Note that MRFR only uses route-ETX values to choose the best route. In constrast, LBR uses both mrf of route and route-ETX in the its route discovery process. To calculate the average mrf of routes for each protocol, we performed as follows. For each flow, we measured the mrf of routes used for that flow. Note that, due to route failure, each flow can use many different routes in the running time. The average mrf of routes for each protocol was then calculated as the average of mrf of routes used for all flows (see the network scenario in Fig. 5 ). As shown and compared to MRFR in Fig. 11 , LBR creates routes with larger average mrf at different loads. For example, at a load of 8 CBR, the average mrf of routes using LBR is 0.925, while the mrf using MRFR is 0.631. This means the probability of congestion on routes using LBR is lower than that using MRFR.
PPT Slide
Lager Image
Comparison of the minimum remaining load factor of route using LBR and MRFR.
- 4.5 Route failure and average inter-route failure time
Fig. 12 -(a) compares the average inter-route failure time using MRFR and LBR. The results present for the five flows (see the scenarior in Fig. 5 ). In which, the average inter-route failure time of each flow was calculated as the following. For each flow, during the data transmission, in the case that a route used for the flow is broken, the source of the flow will broadcast RREQ packets to discover a new route. The average inter-route failure time of each flow is then the average of durations of active route, in which a duration of active route is time during two successive route discoveries. Note that a route failure occurs in two following events. First, a link in that route is broken. Second, a node on the route is out of energy. When the average inter-route failure time of a protocol is large, it implies that the protocol uses reliable and stable routes. As shown in Fig. 12 -(a), the average inter-route failure time using LBR is larger than that using MRFR at different flows. For instance, the inter-route failure time at flow 5 (22-100) for LBR and MRFR are 46.9 sec and 20.08 sec, respectively.
PPT Slide
Lager Image
Comparison of the inter-route failure times (a) and the number of route failures (b).
Fig. 12 -(b) shows the comparison of the number of route failures due to out of node energy. In our simulation, every node was given an equal initial energy. During the data transmission, in the case that a node is out of energy, it stops working. Thus, a route of any flow containing that node will be broken. The results in Fig. 12 -(b) present the number of route failures in each flow, in which a route failure is caused by out of energy of any node on that route. Because our protocol obtain a better load balancing than MRFR, LBR voids nodes of heavy load better than MRFR. As we can see in Fig. 12 -(b), the number of route failures at each flow using LBR is smaller than that using MRFR.
- 4.6 Impact of ΔdelayRREQ and ΔdelayDEST parameters
In the following simulations, we conducted the impact of ΔdelayRREQ and ΔdelayDEST timers to the performance of the LBR protocol. For that purpose, we measured the path establishment delay and controlling the number of RREQ control packets broadcasted while increasing ΔdelayRREQ and Δ delayDEST timer values from 0. In this simulation, the value of ΔdelayDEST is fixed to 25ms and the value of ΔdelayRREQ is changed from 0 to 25ms. In the process of route discovery, we set ΔdelayRREQ timer at each intermediate node for collecting multiple RREQ packets and finding better routes while limiting the number of RREQ packets rebroadcasted. During the ΔdelayRREQ time, the LBR protocol just updates and stores the RREQ packet with smaller e2e_ETX without rebroadcasting. After that, it rebroadcasts this RREQ packet when ΔdelayRREQ is expired. If this parameter is large, we can reduce the number of RREQ control packets generated, however, the route establishment delay can be increased. Therefore, it is necessary to find a proper ΔdelayRREQ value. In Fig. 13 , the left vertical axis represents the RREQ rebroadcasting ratio that is calculated as the ratio between the number of RREQ packets rebroadcasted and the total number of RREQ packets received, and the right vertical axis depicts the route establishment delay. As show in in Fig. 13 -(a), when we set ΔdelayRREQ to value 0, the RREQ rebroadcasting ratio is equal to 1. When we increase ΔdelayRREQ, the RREQ rebroadcasting ratio is decreased, however, the route establishment delay increased.
PPT Slide
Lager Image
The impact of ΔdelayRREQ and ΔdelayDEST timers.
Fig. 13 -(b) shows the impact of ΔdelayDEST parameter to the e2e_ETX of the selected path and the route establishment delay. In this simulation, we set ΔdelayRREQ to 5ms and alter ΔdelayDEST from 0 to 30ms. In our protocol, when the destination node receives the first RREQ, it sets the ΔdelayDEST timer to collect RREQ packets arriving during that time and select the path with the smallest e2e_ETX value. When the ΔdelayDEST timer expired, it replies with a RREP packet through the reverse of the chosen path. A shown in Fig. 13 -(b), when we vary the ΔdelayDEST timer from 0 to 30ms, the e2e_ETX value of the selected path decreases greatly while the route establishment delay varies from 0.13 sec to 0.21 sec. However, if the ΔdelayDEST is higher than 15ms, the e2e_ETX value remains almost the same. This result shows that at high ΔdelayDEST values, our protocol could not find better routes anymore, therefore, the quality of the paths remain the same after 15ms.
5. Conclusions
We have proposed an effective reliable routing protocol while considering balancing load. For load balanced reliable communication, our protocol selects a path that has the small e2e_ETX value and the minimum remaining load of the nodes in the path is large. We have evaluated the performance of our protocol using Qualnet and compared with AODV and MRFR protocols. The simulation results shows that our protocol has better performance than the comparing protocols in terms of the packet delivery ratio, the average end-to-end packet delay and delay jitter, and the load balancing efficiency.
BIO
Anh Tai Tran is a master student in the School of Electrical Engineering, University of Ulsan, Korea. He works on routing protocols in wireless networks. He received the B.Sc. degree from Hanoi University of Science and Technology, Vietnam.
Myung Kyun Kim, Ph.D., is currently a professor in School of Electrical Engineering, University of Ulsan, Korea. His main research area is real-time communications in wireless networks and industrial communication networks. He received the B.Sc. degree from Seoul National University of Korea and the M.Sc. and Ph.D. degrees from KAIST, Korea.
References
Seattle wireless. http://www.seattlewireless.net
Karrer R. , Sabharwal A. , Knightly E. 2004 “Enabling Large-scale Wireless Broadband: The Case for TAPs” SIGCOMM Comput. Commun. Rev. Article (CrossRef Link). 34 (1) 27 - 32    DOI : 10.1145/972374.972380
Perkins C. E. , Bhagwat P. 1994 “Highly dynamic destination-sequenced distance vector routing (dsdv) for mobile computeres” in Proc. of Int. Conf. on Communications Architectures, Protocols and Applications Article (CrossRef Link). 234 - 244
Perkins C. E. , Royer E. M. 1999 “Ad-hoc on-demand distance vector routing” in Proc. of 2nd Int. Workshop on Mobile Computing Systems and Applications February 25-26 Article (CrossRef Link). 90 - 100
Johnson D. B. , Maltz D. A. 1996 “Dynamic source routing in ad-hoc wireless networks” in Proc. Of Conf. on Mobile Computing Article (CrossRef Link). 153 - 181
Couto D. , Aguayo D. , Bicket J. , Morris R. 2005 “A high-throughput path metric for multi-hop wireless routing” Wireless Networks Article (CrossRef Link). 11 (4) 419 - 434    DOI : 10.1007/s11276-005-1766-z
Draves R. , Padhye J. , Zill B. 2004 “Comparison of routing metrics for static multi-hop wireless networks” in Proc. of Int. Conf. on Applications, Technologies, Architectures, and Protocols for Computer Communications Article (CrossRef Link). 133 - 144
Adya A. , Bahl P. , Padhye J. , Wolman A. , Zhou L. 2004 “A multi-radio unification protocol for IEEE 802.11 wireless networks” in Proc of 1st Int. Conf. on Broadband Networks October 25-29 Article (CrossRef Link). 344 - 354
Keshav S. 1991 “A control-theoretic approach to flow control” in Proc. of Int. Conf. on Communications architecture and protocols Article (CrossRef Link). 3 - 15
Das S. M. , Pucha H. , Papagiannaki K. , Hu Y. C. 2007 “Studying wireless routing link metric dynamics” in Proc. of 7th ACM Conf. on Internet Measurement Article (CrossRef Link). 327 - 332
Sankar A. , Liu Z. 2004 "Maximum lifetime routing in wireless ad-hoc networks" in Proc. of 23rd IEEE Conf. on Computer and Communications Societies March 7-11 Article (CrossRef Link). 1089 - 1097
Popa L. , Rostamizadeh A. , Karp R. , Papadimitriou C. , Stoica I. 2007 “Balancing traffic load in wireless networks with curveball routing” in Proc. of 8th ACM Int. symposium on Mobile ad hoc networking and computing Article (CrossRef Link). 170 - 179
Luo J. , He Y. 2011 “GeoQuorum: Load Balancing and Energy Efficient Data Access in Wireless Sensor Networks” in Proc. of IEEE Conf. on Computer and Communications Societies Article (CrossRef Link). 616 - 620
Li X. , Cuthbert L. 2009 “Stable Node-Disjoint Multipath Routing with LowOverhead in Mobile Ad hoc Network” in Proc. of IEEE Int. Symposium on Modeling, Analysis & Simulation of Computer and Telecommunication Systems October 04-08 Article (CrossRef Link). 184 - 191
Al-Rabayah M. , Malaney R. 2010 “A New Hybrid Location-Based Ad Hoc Routing Protocol” in Proc. of IEEE Conf. on Global Telecommunications December 6-10 Article (CrossRef Link). 1 - 6
Mainaud B. , Zekri M. , Afifi H. 2008 “Improving Routing Reliability on Wireless Sensors Network with Emergency Paths” in Proc. of 28th IEEE Conf. on Distributed Computing Systems Workshops June 17-20 Article (CrossRef Link). 545 - 550
Pham P. P. , Perreau S. 2003 “Performance analysis of reactive shortest path and multipath routing mechanism with load balance” in Proc. of 22nd IEEE Conf. on Computer Communications March 30-April 3 Article (CrossRef Link). 251 - 259
Hu Y.-C. , Johnson D. B. 2002 “Design and demonstration of live audio and video over multi-hop wireless networks” in Proc. of Int. Conf. on Military Communications October 7-10 Article (CrossRef Link). 1211 - 1216
The MultiHopLQI protocol http://www.tinyos.net/tinyos-2.x/tos/lib/net/lqi/
Tolle G. , Culler D. 2005 “Design of an application-cooperative management system for wireless sensor networks” in Proc. of 2nd Workshop on Wireless Sensor Networks January 31-February 2 Article (CrossRef Link). 121 - 132
Gupta A. , Diallo C. , Marot M. , Becker M. 2010 “Understanding topology challenges in the implementation of wireless sensor network for cold chain” in Proc. of IEEE Symposium on Radio and Wireless January 10-14 Article (CrossRef Link). 376 - 379
Gnawali O. , Fonseca R. , Jamieson K. , Moss D. , Levis P. 2009 “Collection tree protocol” in Proc. of 7th ACM Conf. on Embedded Networked Sensor Systems Article (CrossRef Link). 1 - 14
Woo A. , Tong T. , Culler D. 2003 “Taming the underlying challenges of reliable multihop routing in sensor networ ks” in Proc. of 1st ACM Conf. on Embedded Networked Sensor Systems Article (CrossRef Link). 14 - 27
Hoai P. N. , Kim M. K. 2012 “MRFR - Multipath-based routing protocol with fast-recovery of failures on MANETs” KSII Transactions on Internet and Information Systems Article (CrossRef Link). 6 (12) 271 - 287
Ganjali Y. , Keshavarzian A. 2004 “Load balancing in ad hoc networks: single-path routing vs. multi-path routing” in Proc. of 21st IEEE Conf. on Computer and Communications Societies March 7-11 Article (CrossRef Link). 1120 - 1125
Yoo Y. , Ahn S. 2004 “A simple load-balancing approach in cheat-proof ad hoc networks” in Proc. of IEEE Conf. on Global Telecommunications November 29-December 3 Article (CrossRef Link). 3573 - 3577
Kim B. C. , Lee J. Y. , Lee H. S. , Ma J. S. 2003 “An ad-hoc routing protocol with minimum contention time and load balancing” in Proc. of IEEE Conf. on Global Telecommunications December 1-5 Article (CrossRef Link). 81 - 85
Obaidat M. S. , Dhurandher S. K. , Diwakar K. 2011 “CASPER: Congestion Aware Selection of Path with Efficient Routing in Multimedia Networks” Information Processing System Article (CrossRef Link). 7 (2) 241 - 260    DOI : 10.3745/JIPS.2011.7.2.241
Azim M. M. 2010 “MAP: A Balanced Energy Consumption Routing Protocol for Wireless Sensor Networks” Information Processing Systems Article (CrossRef Link). 6 (3) 295 - 306    DOI : 10.3745/JIPS.2010.6.3.295
Qualnet simulator http://web.scalable-networks.com/content/qualnet