Source-linked AI summary
ZD-AOMDV: A New Routing Algorithm for Mobile Ad-Hoc Networks
Nastooh Taheri Javan, Reza Kiaeifar, Bahram Hakhamaneshi, Mehdi Dehghan
TL;DR
Parallel node-disjoint routes can still contend for channel access, so their transmissions are not fully independent. The paper modifies AODV to select zone-disjoint paths using active-neighbor counts, and reports lower delay and higher packet delivery than AOMDV.
Problem
CSMA/CA channel competition can make transmissions on parallel node-disjoint paths interdependent and increase end-to-end delay.
Source: §I · p. 1Method
ZD-AOMDV modifies AODV to select zone-disjoint paths by counting active neighbors and choosing paths with the lowest total count.
Source: §III · p. 2Results
Compared with AOMDV, ZD-AOMDV achieves lower average end-to-end delay and higher packet delivery rate.
Source: 3) Average end to end delay · p. 5, 1) Packet Delivery Ratio · p. 5Takeaways & Limitations
Selecting zone-disjoint paths decreases MAC-layer collisions, and the reported packet delivery rate is higher than AOMDV's as node maximum speed increases.
Source: 1) Packet Delivery Ratio · p. 5
Abstract
from arXiv · showhide
A common characteristic of all popular multi-path routing algorithms in mobile ad-hoc networks, such as AOMDV, is that the end to end delay is reduced by utilization of parallel paths. The competition between the neighboring nodes for obtaining a common channel in those parallel paths is the reason for end to end delay increment. In fact, due to medium access mechanism in wireless networks, such as CSMA/CA, data transmissions even through two node-disjoint paths are not completely independent and each path will affect the other one. In this paper we have modified the AODV protocol which results in selection of zone-disjoint paths, to the extent feasible, and as a result we achieve less end to end delay. The efficiency of the proposed protocol has been evaluated on different scenarios and there has been a noticeable improvement in the packet delivery ratio and also in the reduction of end-to-end delay comparing to AOMDV.
I. INTRODUCTION
Multi-path routing can reduce delay and improve fault tolerance, but parallel node-disjoint routes still contend for wireless channel access. The paper proposes an AODV-based multi-path algorithm using common omni-directional antennas.
I. INTRODUCTION
- Multi-path routing discovers several routes, reducing the need for new route discovery after a link breaks and increasing fault tolerance.Some algorithms use stored alternatives only after a break, while others transfer data over all discovered paths concurrently.Source: §I · p. 1
- Node-disjoint paths have no common nodes and can limit the effect of a broken node to one path, but wireless channel contention can still increase delay.CSMA/CA uses RTS/CTS messages that can make nodes wait for channel access.Source: §I · p. 1
- CSMA/CA control messages can make transmissions on two node-disjoint paths interdependent, delaying one path when a node receives a CTS from the other.The example describes two S–D routes and attributes this interaction to RTS/CTS exchanges.Source: §I · p. 1
- The proposed on-demand multi-path algorithm is based on AODV and uses common omni-directional antennas, unlike solutions requiring unidirectional antennas.Source: §I · p. 2
II. RELATED WORKS
The related work describes AOMDV's link-disjoint route discovery and a directional-antenna approach to selecting zone-disjoint paths. The latter uses stored neighbor signal information but requires directional antennas.
II. RELATED WORKS
- Multi-path algorithms send more routing requests than single-path algorithms, increasing their complexity.Source: §II · p. 2
- AOMDV seeks link-disjoint paths by broadcasting route requests, which intermediate nodes reconstruct and rebroadcast.Source: §II · p. 2
- Intermediate nodes may accept a repeated request when it comes from a new neighbor or path founder, or has fewer hops; the destination responds to received requests.Source: §II · p. 2
- A directional-antenna method uses stored neighbor signal power and angle information to select zone-disjoint paths, but requires directional antennas.Source: §II · p. 2
III. PROPOSED ALGORITHM
ZD-AOMDV is an AODV-based on-demand multi-path protocol that aims to find zone-disjoint routes. It counts active neighbors and selects paths with the lowest total count.
III. PROPOSED ALGORITHM
- ZD-AOMDV is an on-demand multi-path routing protocol based on AODV that seeks zone-disjoint paths to the feasible extent.Source: §III · p. 2
- An active neighbor is a neighbor that has received and replied to an RREQ and may also lie on another path between the same source and destination.Such neighbors may affect simultaneous data transfer even when the routes are node-disjoint.Source: §III · p. 2
- The algorithm counts active neighbors along each source-to-destination path and chooses paths with the lowest total count.Source: §III · p. 2
A. AODV Modifications
ZD-AOMDV changes route discovery and message fields to track requests and active neighbors. It also adds query messages to the discovery process.
A. AODV Modifications
- ZD-AOMDV does not require intermediate-node Route Cache tables, allowing the destination to receive path-request messages from different paths.Source: A. AODV Modifications · p. 2
- Each node stores received RREQ messages in an RREQ_Seen table and adds an After_Active_Neighbor_Count field to count active neighbors identified after sending an RREQ.Source: A. AODV Modifications · p. 2
- An ActiveNeighborCount field is added to RREQ and RREP headers to pass the total active-neighbor count along a path.Source: A. AODV Modifications · p. 2
- Route discovery also adds RREQ_Query and RREQ_Query_Reply messages.Source: A. AODV Modifications · p. 2
B. Proposed algorithm procedure
ZD-AOMDV queries neighbors to estimate how much candidate paths overlap, then uses those counts to select paths. Unlike AOMDV, it waits for multiple RREP packets before beginning data transfer.
B. Proposed algorithm procedure
- Route discovery begins when a node lacks a valid route; ZD-AOMDV is Zone-Disjoint Ad-hoc On-demand Multi-path Distance Vector, based on AODV.The source broadcasts an RREQ to start discovery.Source: B. Proposed algorithm procedure · p. 2
- Path founders query their neighbors about previously seen RREQs and add positive responses to the RREQ's ActiveNeighborCount.Neighbors check the RREQ_Seen table and reply with RREQ_Query_Reply messages.Source: B. Proposed algorithm procedure · p. 3
- A repeated RREQ query receives a reply only from a new neighbor; After_A_N_C tracks new neighbors found after the RREQ was broadcast.The node increments After_A_N_C when a new neighbor queries an RREQ it has already broadcast.Source: B. Proposed algorithm procedure · p. 3
- Intermediate nodes add After_A_N_C to the ActiveNeighborCount carried in the RREP so the source can determine each path's active-neighbor count.The destination's RREP carries the count from its RREQ.Source: B. Proposed algorithm procedure · p. 3
- The source waits for multiple RREP packets, then chooses paths with fewer active neighbors for load-balanced data transfer.AOMDV begins transferring data after the first RREP, using the path with the fewest hops.Source: B. Proposed algorithm procedure · p. 3
C. Pseudo code of ZD-AOMDV
The pseudocode covers source, destination, and intermediate nodes. A worked example traces how active-neighbor counts are accumulated and used to choose paths.
C. Pseudo code of ZD-AOMDV
- The source starts discovery by broadcasting an RREQ when it has no route; A, B, and C become path founders and query neighbors.Figures 2, 3, and 4 present pseudocode for the source, destination, and intermediate nodes, respectively.Source: C. Pseudo code of ZD-AOMDV · pp. 3–4, Figure 2 · p. 3, Figure 3 · p. 3
- In the example, A and C each count B as one active neighbor, while B counts both A and C, giving the first S-B-D route a count of two.E and F also identify B as an active neighbor; B records their later queries in After_A_N_C.Source: C. Pseudo code of ZD-AOMDV · p. 4
- All RREQs arriving at the destination in the example have ActiveNeighborCount equal to two; B's After_A_N_C value is also two.The example labels the count before and after each node broadcasts an RREQ.Source: C. Pseudo code of ZD-AOMDV · p. 4
- The destination returns an RREP for each received RREQ, and intermediate nodes add their After_A_N_C values to its ActiveNeighborCount.In the example, only B changes the RREP count, increasing it by two.Source: C. Pseudo code of ZD-AOMDV · p. 4
- After waiting for other RREPs, the source chooses lower-count paths; in the example, it selects S-A-E-D and S-C-F-D.The source waits for a set time after receiving the first RREP.Source: C. Pseudo code of ZD-AOMDV · p. 4
IV. PERFORMANCE EVALUATION
The evaluation compares ZD-AOMDV with AOMDV across several performance metrics. The section also includes an example of the proposed routing algorithm.
IV. PERFORMANCE EVALUATION
- The evaluation compares ZD-AOMDV's performance with AOMDV across several metrics.The supplied Figure 5 caption identifies an example of the proposed routing algorithm, rather than reporting an evaluation result.Source: §IV · p. 4
- Figure 5 presents an example of the proposed routing algorithm.Source: Figure 5 · p. 4
A. Simulation Environment
The simulation compares the algorithms in a 100-node mobile network using CBR traffic and IEEE 802.11 MAC. Results average 25 runs of 300 seconds each.
A. Simulation Environment
- The scenario uses 100 nodes in a 1000×1000-meter area, with a 250-meter movement range and CBR traffic.Nodes use IEEE 802.11 at the MAC layer and the RADIO-ACCNOISE model for sending or receiving data.Source: A. Simulation Environment · p. 5
- Nodes move toward arbitrary destinations, pause for one second upon arrival, and the simulations run for 300 seconds.The node movement model specifies random-direction travel.Source: A. Simulation Environment · p. 5
- Both algorithms use three paths for load-balanced data transfer, and results are averaged over 25 simulation runs.Source: A. Simulation Environment · p. 5
B. Performance Metrics
ZD-AOMDV is reported to achieve lower average end-to-end delay and higher packet delivery ratio than AOMDV. The section also reports routing-overhead behavior and defines the three simulation metrics.
B. Performance Metrics
- The simulation evaluates average end-to-end delay, packet delivery ratio, and control overhead ratio.Average delay includes buffering during route discovery, interface queuing, MAC retransmissions, propagation, and transfer delays; control overhead counts routing control packets over simulation time.Source: B. Performance Metrics · p. 5
- As node speed increases, packet delivery rate decreases for both algorithms, but ZD-AOMDV achieves a higher rate than AOMDV.The paper attributes this to fewer MAC-layer collisions from selecting zone-disjoint paths.Source: Figure 6 · p. 5, 1) Packet Delivery Ratio · p. 5
- At a maximum node speed of 25 meters per second, ZD-AOMDV routing overhead increases rapidly as the number of nodes grows.The paper attributes the increase to more query and query-reply packets during route discovery.Source: Figure 7 · p. 5, 2) Routing overhead · p. 5
- ZD-AOMDV achieves lower average end-to-end delay than AOMDV, despite taking longer in route discovery.It overtakes AOMDV during data transfer; the paper attributes the lower delay to zone-disjoint path selection.Source: Figure 8 · p. 5, 3) Average end to end delay · p. 5
V. CONCLUSION
The paper argues that node-disjoint parallel paths can still interfere under CSMA/CA, motivating zone-disjoint routing. Its AODV-based protocol uses omni-directional antennas and reports lower delay and higher packet delivery ratio than AOMDV.
V. CONCLUSION
- CSMA/CA channel access means nodes on separate node-disjoint paths can still affect one another during simultaneous data transfer.The paper notes that this can increase end-to-end delay.Source: §V · p. 6
- The proposed AODV-based protocol uses common omni-directional antennas and transfers data simultaneously over multiple zone-disjoint paths.The number of active neighbors in each path is used during route discovery to select paths.Source: §V · p. 6
- Compared with AOMDV, the proposed protocol achieves lower end-to-end delay and higher packet delivery ratio.Source: §V · p. 6