Keywords
|
| AODV, RAODV, ERAODV, RREQ, RREP, NS2, Power consumption, Power Constrains. |
INTRODUCTION
|
| A mobile ad hoc network is a dynamically self-organizing network without any central administrator or infrastructure. If two nodes are not within the transmission limit of each other, then other nodes are needed to serve as intermediate routers to establish the communication between the two nodes [4]. Moreover, mobile devices wander autonomously without any predefined manner and communicate via dynamically changing network topology. Thus, frequent change of network topology leads to many challenging issues, such as power life, routing procedure and performance degradation [5-15]. Routing protocols for different types of wireless networks have been proposed by a number of researchers. Researchers traditionally classify these protocols in to three categories as proactive protocols, Reactive protocols, or hybrid of the two, based on the way they find new routes or update existing ones. Proactive routing protocols keep routes continuously updated, while reactive routing protocols react when there is a demand for routing [1]. Proactive routing protocols require nodes to exchange routing information periodically and compute routes continuously between any nodes in the network, regardless of using the routes or not. This is also known as Table Driven Protocol. This means a lot of network resources such as power and bandwidth may be wasted, which is not desirable in MANETs where the power and resources are constrained [4-6]. On the other hand, on-demand routing protocols do not exchange routing information periodically. Instead, they discover a route only when it is needed for the communication between two nodes [4, 9, 10]. This reactive protocol is also called source initiated protocol. Due to dynamic change of network on adhoc networks, links between nodes are not permanent. In occasions, a node cannot send packets to the intended next hop node and as a result packets may be lost. Loss of packets may affect on route performance in different ways. Among these packet losses, loss of route reply brings much more problems, because source node needs to re-initiate route discovery procedure. A drawback of existing Adhoc On demand Distance Vector routing protocol is that their main route discovery mechanisms are not well concerned about a route reply message loss. More specifically, most of today’s on-demand routing is based on single route reply message. The lost of route reply message may cause a significant waste of power and performance. Here we propose a modified AODV termed as Reverse AODV (RAODV) which has a many good aspect compared to other source initiated routing protocols on mobile Adhoc networks. In RAODV, the Route Reply message is not unicast, rather, the destination node uses reverse RREQ to find source node. It reduces path fail correction messages and can improve the robustness of performance. Therefore, success rate of route discovery may be increased even though high node mobility situation. The NS2 simulation results show our proposed algorithm improves performance of AODV in most metrics, including power consumption, packet delivery ratio and average end to end communication delay. |
NEED FOR AODV MODIFICATION
|
| In mobile ad hoc networks nodes may move from one location to another on variety of node speed. As the result, the network topology changes continuously and unpredictably. Only within a short period of time neighbouring nodes can loose communication link, especially when the mobility is high. In on-demand routing protocols, loosing a communication link between nodes brings route breaks and packet losses which eats up the battery power of wireless mobile nodes. Especially, loosing the RREP of AODV protocol produces a large impairment on the AODV protocol. In fact, a RREP message of AODV is obtained by the cost of flooding the entire network or a partial area [4-8]. RREP loss leads to source node reinitiate route discovery process which causes degrade of the routing performance, like high power consumption, long end-to-end delay and inevitably low packet delivery ratio. Therefore, we are considering how simply to decrease the loss of RREP messages. We can see a situation in Figure 1, where S is a source node, D is a destination node and others are intermediate nodes. In traditional AODV, when RREQ is broadcasted by node S and each node on a path builds reverse path to the previous node, finally the reverse path D to 3 to 2 to 1 to S has built. This reverse path is used to deliver RREP message to the source node S. If node 1 moves towards the arrow direction and goes out of transmission range of node 2, RREP missing will occur and the route discovery process will be useless. This RREP missing enable the source to send multiple RREQ signals in order to get the RREP. Hence the mobile nodes are wasting enormous power in sending and receiving RREQ and RREP signals respectively. As mentioned in [6], when the number of nodes is 100 and the number of flows is 50, 14% of total RREP messages are lost. Hence we need some modification in AODV approach to avoid the above drawback. |
| Here we introduce a Reverse Route Request signal to call the Route Reply signal which evolved from the destination, which is Reverse Route Request (RRREQ). RAODV protocol can reply from destination to source if there is at least one path to source node. In this manner, RAODV prevents a large number of retransmissions of route request messages, and hence diminishes the power loss, congestion in the network. Moreover, RAODV will improve the routing performance such as packet delivery ratio and end-to-end communication delay. |
| A. Drawbacks of AODV |
| Routes in AODV protocol are established based on minimum hop count. This consideration might have a bad effect when the number of communications increases. So it is more likely to include other parameters that have a significant effect on, network connectivity and lifetime. Furthermore, power is a very important constraint in wireless network. If a node that participates in a route establishment has very low energy, this later will break very soon. Moreover, this has also a bad effect on the network lifetime: there are some nodes that will dead very faster than other ones. To deal with these problems, the power should be taken into account in the route establishment algorithm. At this end, we propose a mechanism that considers the residual energy of mobile nodes when making routing decisions. |
MODIFIED AODV ALGORITHM
|
| Taking into account the various problems and power constraints described above, we propose a reactive routing protocol Energy Reverse AODV (ERAODV) which aims to maximize the lifetime of the network and improve the performance obtained by the basic AODV routing protocol. Thus, the goal is to reduce the cost of control packets used to maintain the network by incorporating the mechanism called "Reverse AODV", and routing around nodes that we expect that they have more residual energy than other by integrating mechanism "Energy Reverse AODV" into our algorithm.AODV is modified and a new proposed algorithm is called Reverse AODV (RAODV). Analysing previous protocols, we can say that most of on-demand routing protocols, except multipath routing, uses single route reply along the first reverse path to establish routing path. As we mentioned before, in high mobility, pre-decided reverse path can be disconnected and route reply message from destination to source can be missed. In this case, source node needs to retransmit route request message. Purpose of our study is to increase possibility of establishing routing path with less RREQ messages than other protocols have on topology change by nodes mobility. Specifically, the proposed RAODV protocol discovers routes on-demand using a reverse route discovery procedure. During route discovery procedure source node and destination node plays same role from the point of sending control messages. Thus, after receiving RREQ message, destination node floods reverse request (RRREQ), to find source node. When source node receives an RRREQ message, data packet transmission is started immediately. |
| Since RAODV is reactive routing protocol, no permanent routes are stored in nodes. The source node initiates route discovery procedure by broadcasting. The RREQ message contains following information (Figure 2): message type, source address, destination address, broadcast ID, hop count, source sequence number, destination sequence number, request time (timestamp). |
| Whenever the source node issues a new RREQ, the broadcast ID is incremented by one. Thus, the source and destination addresses, together with the broadcast ID, uniquely identify this RREQ packet [4, 12]. The source node broadcasts the RREQ to all nodes within its transmission range. These neighbouring nodes will then pass on the RREQ to other nodes in the same manner. As the RREQ is broadcasted in the whole network, some nodes may receive several copies of the same RREQ. When an intermediate node receives a RREQ, the node checks if already received a RREQ with the same broadcast id and source address. The node cashes broadcast id and source address for first time and drops redundant RREQ messages. The procedure is the same with the RREQ of AODV. When the destination node receives first route request message, it generates so called reverse request (RRREQ) message and broadcasts it to neighbour nodes within transmission range like the RREQ of source node does. RRREQ message (Figure 3) contains following information: reply source id, reply destination id, reply broadcast id, hop count, destination sequence number, reply time (timestamp). When broadcasted RRREQ message arrives to intermediate node, it will check for redundancy. If it already received the same message, the message is dropped, otherwise forwards to next nodes. |
| Furthermore, node stores or updates following information of routing table: |
| ? Destination Node Address |
| ? Source Node Address |
| ? Hops up to destination |
| ? Destination Sequence Number |
| ? Route expiration time and next hop to destination node. |
| And whenever the original source node receives first RRREQ message it starts packet transmission, and late arrived RRREQs are saved for future use. The alternative paths can be used when the primary path fails communications. Let’s see the same case of AODV, we have mentioned above, in figure 4. In RAODV, destination does not unicast reply along pre-decided shortest reverse path D to 3 to 2 to 1 to S. Rather, it floods RRREQ to find source node S. And forwarding path to destination is built through this RRREQ. Following paths might be built: S to 4 to 5 to 6 to D, S to 11 to 10 to 9 to 8 to 7 to D, and etc. Node S can choose best one of these paths and start forwarding data packet. So RREP delivery fail problem on AODV does not occur in this case, even though node 1 moves from transmission range. |
| When control packets are received, the source node chooses the best path to update, i.e. first the node compares sequence numbers, and higher sequence numbers mean recent routes. If sequence numbers are same, then compares number of hops up to destination, routing path with fewer hops is selected. Since the wireless channel quality is time varying, the best path varies over time. The feedback from the MAC layer can be used to detect the connectivity of the link. When a node notifies that its downstream node is out of its transmission range, the node generates a route error (RERR) to its upstream node. If fail occurs closer to destination node, RRER received nodes can try local-repair, otherwise the nodes forward RRER until it reaches the source node [4,5]. The source node can select alternative route or trigger a new route discovery procedure. |
ENERGY AODV
|
| This mechanism proposes a new adaptive approach which seeks to incorporate the metric "residual energy of nodes" instead of the number of hops in the process route selection. Indeed, we define the rate of energy consumption for each node to estimate its lifetime. Then, we define a cost that fits this lifetime and the energy level. This information is then used to calculate routes cost. |
| A. Control Packet |
| RREQ Message: A field called « min_bat» has been added to RREQ packets. It takes as value the minimum of residual energies of nodes traversed by the RREQ packet. Routing Table: This structure is used to store every candidate route in destination nodes, indexed by source node identifier. Every entry in the routes table contains the following fields: |
| • Src: maintains the identifier of source node who initiated the route discovery procedure. |
| • Seq: maintains the RREQ sequence number. |
| • Route: contains the nodes sequence traversed by RREQ packet. |
| • Min_bat: keeps the minimal residual energy of nodes traversed by RREQ packet. |
| • Arrival_time: keeps the arrival time of RREQ packet at the destination node. |
| Content of the first four fields is directly extracted from arriving RREQ packets. |
| B. Computing the expected residual lifetime |
| In our mechanism, we do not only consider the current energy level value of a node, we observe also the speed of energy consumption at each constant period (Tupdate) [3]. For each node, we follow the following formula to compute energy speed consumption: |
 |
| Where Energiecour (j) is the current energy value of the node, and ETx is the value of the power that will be consumed to transmit the Npkts remaining packets in the buffer. Then, we can estimate the expected residual life time Tlifetime (j) in each node considering the energy speed consumption Energieconsom (j) and the estimated residual energy Energierest (J) values computed at each time interval j as follow: |
 |
| C. Computing the route establishment cost |
| Using the Tlifetime (j) value, each node computes a cost at each route request demand. This cost is defined as follows: |
 |
| Where Wk is a multiplication factor in the interval [0,1] defined for each energy interval k . Hence, k go from 1 to 4 referring four energy intervals: the first one is from 50% to 100% of initial energy value (Wk =1), the second one is from 30% to 50% (Wk =0.75), the third one is from 10% to 30% (Wk =0.5) and the last one is from 0% to 10% (Wk =0.25). |
| Thus the route establishment cost from source to destination is calculated as follows: |
 |
| Where nbr node is the intermediate nodes number |
| D. Control Packet Overhead |
| Intuitively, we can say that RAODV causes a lot of control packet overhead. However, we can prove that route discovery procedure based on single reply message may cause even more packet overhead for some cases. We define the followings: |
| ? An ad hoc network has N number of nodes |
| ? Required number of control messages to discover routing path for AODV is AODV(N) |
| ? Required number of control messages to discover routing path for RAODV is RAODV(N). |
| Let’s say m nodes participate to discover a routing path. Then AODV obtains a routing path using control message(1). |
 |
| where t is the number of nodes relied on route reply message. If source node fails in first try, because route reply message could not arrive, the node re-initiates path discovery, the number of control messages increase by the number of tries. Expressed in (2) as, |
 |
| where c is the number of tries for route discovery. When we assume that RAODV has at least one stable path by a RREQ, then the number of control messages for RAODV will require only 2m-2 messages for route discovery.Given in (3) |
 |
| when c>1, then AODV causes more packet overhead than the case of c=1 on RAODV routing. Hence we conclude that for any case the control packet overhead is reduced much in RAODV than AODV which in turn reduces the power constrains and increases the performance of mobile network. |
SIMULATION RESULTS
|
| We first describe the simulation environment used in our research and then discuss the results in detail. Our simulations are implemented in Network Simulator (NS-2) [19]. At this level, we discuss only the results of our first mechanism Reverse AODV. Simulation parameters are as follows: |
| • Number of nodes: 10, 20, 30, 40, 50, respectively. |
| • Testing area: 1000m x 1000m. |
| • Mobility model: random way point model (when the node reaches its destination, it pauses for several seconds, e.g, 1s, then randomly chooses another destination point). |
| • Traffic load: UDP, CBR traffic generator. Each simulation is run for 100 seconds and repeated for 10 times. To evaluate performance of RAODV, we compare our proposed RAODV with AODV, using the following metrics: |
| • Delivery Rate: the ratio of packets reaching the destination node to the total packets generated at the source node. |
| • Average End-to-End Delay: the interval time between sending by the source node and receiving by the destination node, which includes the processing time and queuing time. |
| • Average Energy Remained: mean value of energy remained in each node. |
| Figure 5 shows packet deliver ratio of AODV and RAODV, by increasing number of nodes brings apparent difference between the two protocols, more exact result is shown on Figure 6. Packet delivery ratio difference in figure 6 calculated as below: |
 |
| Figure 7 shows the average energy remained of each protocol. We have to mention that it is a mean value of energy remained each node at the end of simulation. Remained energy in RAODV is higher than AODV; even it has sent more data packets to destination as shown on figure 5 and 6. |
| Figure 8 shows the average end-to-end delay of each protocol. It should be noted that the delay is considered for the packets that actually arrive at the destinations. We can see that RAODV has lower delay than AODV. The reason is that AODV chooses route earlier, RAODV chooses recent route according to reverse request. Figure 9 shows the control packet overhead required by the transportation of the routing packets. AODV has more control packet overhead. The reason is that AODV sends many route request to get a reply message which is not received even though the route reply message in AODV is unicast along reverse path. But the control packet overhead in RAODV is medium because it also floods many route reply messages to find the source. So we can say that, half of these messages are RRREQ. Figure 10 shows the average end-to-end delay of each protocol. It should be noted that the delay is considered for the packets that actually arrive at the destinations. |
| We can see that RAODV has almost same delay ratio with AODV. It is very clear to differentiate the delay in Figure 11 which shows average end to end delay is very less for RAODV than AODV when the nodes are moving with maximum varying speed. The reason is that AODV chooses route earlier, but RAODV chooses recent route according to reverse request. As fast node mobility causes high topology changes, recently selected path may have better consistency. Figure 12 shows remained average energy. Where RAODV has more remained energy than AODV, which will be helpful for nodes to survive in network because the sent and received ratio is equal in RAODV than AODV. |
CONCLUSION
|
| Successful delivery of RREP messages are important in On demand routing algorithm for adhoc networks. Because Sudden change of topology causes that the Route Reply could not arrive to the source node, i.e. after a source node sends several route request messages; the node obtains a reply message which leads to loss of battery energy. This increases the power consumption and communication delay and decreases the packet delivery ratio. Also the loss of RREPs causes serious impairment on the routing performance. This is because the cost of a RREP is very high. If the RREP is lost, a large amount of route discovery effort will be wasted in terms of sending number of control packets, and in terms of energy loss. We proposed the idea of reverse AODV, which tries multiple route replies. RAODV route discovery succeeds in fewer tries than AODV. The results show that RAODV improves the performance of AODV in most metrics, as the packet delivery ratio, end to end delay, and energy consumption. We used “Min_bat” in control packet which keeps track of the minimal residual energy of the nodes to avoid route breakage, if the route breaks then excess power loss. The power consumption and other problems can be eliminated through a modified AODV technique. Next we plan to focus our research work on implementing the Energy AODV mechanism in order to conserve more power. |
Figures at a glance
|
 |
 |
 |
 |
 |
| Figure 1 |
Figure 2 |
Figure 3 |
Figure 4 |
Figure 5 |
 |
 |
 |
 |
 |
| Figure 6 |
Figure 7 |
Figure 8 |
Figure 9 |
Figure 10 |
 |
 |
| Figure 11 |
Figure 12 |
|
References
|
- Boukerche, “Performance comparison and analysis of ad hoc routing algorithms,” in Proc. of IEEE International Conference onPerformance, Computing, and communications pp. 171-178, 2001.
- NS, The UCB/LBNL/VINT Network Simulator (NS), http://www.isi.edu/nsnam/ns/, 2004.
- Lamia Romdhani and Christian Bonnet “Energy Consumption Speed-Based Routing for Mobile Ad Hoc Networks“.DistributedComputing Systems Workshops, 2004. Proceedings. 24th International Conference
- E. Perkins and E. M. Royer, “Ad hoc on-demand distance vector routing,” in Proc. WMCSA, New Orleans, LA, Feb. 1999, pp. 90-100.
- Zhi Li and Yu-Kwong Kwok, “A New Multipath Routing Approach to Enhancing TCP Security in Ad Hoc Wireless Networks” in Proc. ICPPW 2005.
- RendongBai and MukeshSinghal, “Salvaging Route Reply for On-Demand Routing Protocols in Mobile Ad-Hoc Networks” in MSWIM 205, Montreal, Quebec, Canada. Oct 2005
- K.-L. Lee, X.-H. Lin, and Y.-K. Kwok, “A Multipath Ad Hoc Routing Approach to Combat Wireless Link Insecurity”. Proc. ICC2003, vol. 1, pp. 448–452, May 2003.
- S.-J. Lee and M. Gerla, “Split Multipath Routing with Maximally Disjoint Paths in AdHoc Networks,” Proc. ICC 2001, vol. 10, pp.3201–3205, June 2001.
- M. K. Marina and S. R. Das “On-Demand Multi Path Distance Vector Routing in Ad Hoc Networks,” Proc. ICNP 2001, pp. 14– 23,Nov. 2001.
- A.Nasipuri and S. R. Das, “On-Demand Multipath Routing for Mobile Ad Hoc Networks,” Proc. ICCN 1999, pp. 64–70, Oct. 1999.
- A.Perkins, E. Belding-Royer “Ad hoc on-Demand Distance Vector (AODV) Routing”, RFC 3561, July 2003
- Stojmenovic, M. Seddigh, J. Zunic, ”Dominating sets and neighbor elimination-based broadcasting algorithms in wireless networks”,IEEE Transactions on Parallel and Distributed Systems, 2002, pp. 14-25
- J.Wu, and H. Li, ”On Calculating Power-Aware Connected Dominating Sets for Efficient Routing in Ad HocWireless Networks”, in Proc.of the 3rd Int’l Workshop on Discrete Algorithm and Methods for Mobile Computing and Commun., 1999, pp. 7-14.
- Jae-Ho Bae, Dong-Min Kim, Tae-Hyoun Kim, Jaiyong Lee. An AODV-based Efficient Route Re-Acquisition Scheme in Ad HocNetworks.
- Y.Kim, J.Jung, S.Lee and C.Kim, “A Belt-Zone Method for Decreasing Control Messages in Ad Hoc Netowkrs” ICCSA 2006, LNCS3982, pp 64-72, 2006.
- L. M. Feeney and M. Nilsson. Investigating the energy consumption of a wireless network interface in an ad hoc networking environment.In IEEE INFOCOM, 2001.
- Y. Xu, J. Heidemann and D. Estrin, “Adaptive energyconserving routing for multihop ad hoc networks,” Technical Report TR-2000-527,2000.
- Ramanathan and Rosales-Hain, “Topology control of multihop wireless networks using transmit power adjustment,” IEEE Infocom2000,2000.
- NS, The UCB/LBNL/VINT Network Simulator (NS),http://www.isi.edu/nsnam/ns/, 2004. World Academy of Science, Engineering andTechnology 44 2010 1512
- B. Chen, K. Jamieson, H. Balakrishnan, et R. Morris, "Span: An Energy-Efficient Coordination Algorithm for Topology Maintenance inAd Hoc Wireless Networks," ACM/IEEE International Conference on Mobile Computing and Networking (MobiCom 2001), Rome, Italy,juillet 16-21, 2001.
- L. M. Feeney. “An energy consumption model for performance analysis of routing protocols for mobile ad hoc networks”. MobileNetworks and Applications, 6(3):239–249, Juin 2001.
- Perkins, Ad hoc on demand distance vector (AODV) routing, Internet-Draft, draft-ietf-manet-aodv-04.txt, pages 3-12, October 1999,Work in progress.
- YaXu, John Heidemann, and Deborah Estrin, Adaptive Energy- Conserving Routing for Multihop Ad Hoc Networks, ResearchReport527, USC/Information Sciences Institute, October, 200
|
Menu