Loop-free hybrid single-path/flooding routing algorithms with guaranteed delivery for wireless networks
Top Cited Papers
- 1 October 2001
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Parallel and Distributed Systems
- Vol. 12 (10), 1023-1032
- https://doi.org/10.1109/71.963415
Abstract
In a localized routing algorithm, each node makes forwarding decisions solely based on the position of itself, its neighbors, and its destination. In distance, progress, and direction-based approaches'(reported in the literature), when node A wants to send or forward message m to destination node D, it forwards m to its neighbor C which is closest to D (has best progress toward D, whose direction is closest to the direction of D, respectively) among all neighbors of A. The same procedure is repeated until D, if possible, is eventually reached. The algorithms are referred to as GEDIR, MFR, and DIR when a common failure criterion is introduced: The algorithm stops if the best choice for the current node is the node from which the message came. We propose 2-hop GEDIR, DIR, and MFR methods in which node A selects the best candidate node C among its 1-hop and 2-hop neighbors according to the corresponding criterion and forwards m to its best 1-hop neighbor among joint neighbors of A and C. We then propose flooding GEDIR and MFR and hybrid single-path/flooding GEDIR and MFR methods which are the first localized algorithms (other than full flooding) to guarantee the message delivery (in a collision-free environment). We show that the directional routing methods are not loop-free, while the GEDIR and MFR-based methods are inherently loop free. The simulation experiments, with static random graphs, show that GEDIR and MFR have similar success rates, which is low for low degree graphs and high for high degree ones. When successful, their hop counts are near the performance of the shortest path algorithm. Hybrid single-path/flooding GEDIR and MFR methods have low communication overheads. The results are also confirmed by experiments with moving nodes and MAC layer.Keywords
This publication has 27 references indexed in Scilit:
- Dynamic Source Routing in Ad Hoc Wireless NetworksPublished by Springer Nature ,2007
- Power-aware localized routing in wireless networksPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- On the reduction of broadcast redundancy in mobile ad hoc networksPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Power Optimization in Routing Protocols for Wireless and Mobile NetworksPublished by Wiley ,2002
- Location Updates for Efficient Routing in Ad Hoc NetworksPublished by Wiley ,2002
- GPSRPublished by Association for Computing Machinery (ACM) ,2000
- A review of current routing protocols for ad hoc mobile wireless networksIEEE Wireless Communications, 1999
- Mobile ad hoc networking and the IETFACM SIGMOBILE Mobile Computing and Communications Review, 1998
- A survey of routing techniques for mobile communications networksMobile Networks and Applications, 1996
- The Spatial Capacity of a Slotted ALOHA Multihop Packet Radio Network with CaptureIEEE Transactions on Communications, 1984