skip to main content
article

Message-efficient beaconless georouting with guaranteed delivery in wireless sensor, ad hoc, and actuator networks

Published: 01 February 2010 Publication History

Abstract

Beaconless georouting algorithms are fully reactive and work without prior knowledge of their neighbors. However, existing approaches can either not guarantee delivery or they require the exchange of complete neighborhood information. We describe two general methods for completely reactive face routing with guaranteed delivery. The Beaconless Forwarder Planarization (BFP) scheme determines correct edges of a local planar subgraph without hearing from all neighbors. Face routing then continues properly. Angular Relaying determines directly the next hop of a face traversal. Both schemes are based on the Select-and-Protest principle. Neighbors respond according to a delay function, but only if they do not violate a planar subgraph condition. Protest messages are used to remove falsely selected neighbors that are not in the planar subgraph. We show that a correct beaconless planar subgraph construction is not possible without protests. We also show the impact of the chosen planar subgraph on the message complexity. With the new Circlunar Neighborhood Graph (CNG) we can bound the worst case message complexity of BFP, which is not possible when using the Gabriel graph (GG) for planarization. Simulation results show similar message complexities in the average case when using CNG and GG. Angular Relaying uses a delay function that is based on the angular distance to the previous hop. We develop a theoretical framework for delay functions and show both theoretically and in simulations that with a function of angle and distance we can reduce the number of protests by a factor of 2 compared to a simple angle-based delay function.

References

[1]
B. Blum, T. He, S. Son, and J. Stankovic, "IGF: A state-free robust communication protocol for wireless sensor networks," Univ. Virginia, Tech. Rep. CS-2003-11, 2003.
[2]
P. Bose, L. Devroye, W. Evans, and D. Kirkpatrick, "On the spanning ratio of Gabriel graphs and beta-skeletons," SIAM J. Discrete Math., vol. 20, no. 2, pp. 412-427, 2006.
[3]
J. Gudmundsson and P. Morin, "Ordered theta graphs," Comput. Geometry, vol. 28, no. 1, pp. 11-18, May 2004.
[4]
P. Bose, P. Morin, I. Stojmenovic, and J. Urrutia, "Routing with guaranteed delivery in ad hoc wireless networks," in Proc. 3rd Int. Workshop on Discrete Algor. and Methods for Mobile Comput. Commun. (DIAL-M '99), 1999, pp. 48-55.
[5]
M. Chawla, N. Goel, K. Kalaichelvan, A. Nayak, and I. Stojmenovic, "Beaconless position based routing with guaranteed delivery for wireless ad-hoc and sensor networks," in Proc. 1st IFIP Int. Conf. Ad-Hoc Netw., Aug. 2006, pp. 61-70.
[6]
M. Chawla, N. Goel, K. Kalaichelvan, A. Nayak, and I. Stojmenovic, "Beaconless position-based routing with guaranteed delivery for wireless ad hoc and sensor networks," ACTA AUTOMATICA SINICA, vol. 32, no. 6, pp. 846-855, Nov. 2006.
[7]
D. Chen and P. K. Varshney, "A survey of void handling techniques for geographic routing in wireless networks," IEEE Commun. Surveys Tutorials, vol. 9, no. 1, pp. 50-67, 2007.
[8]
D. Chen, J. Deng, and P. K. Varshney, "Selection of a forwarding area for contention-based geographic forwarding in wireless multi-hop networks," IEEE Trans. Veh. Technol., vol. 56, no. 5, pt. 2, pp. 3111-3122, Sep. 2007.
[9]
R. J. Cimikowski, "Properties of some euclidean proximity graphs," Pattern Recogn. Lett., vol. 13, no. 6, pp. 417-423, 1992.
[10]
L. Devroye, "The expected size of some graphs in computational geometry," Comput. Math. Appl., vol. 15, no. 1, pp. 53-64, 1988.
[11]
G. G. Finn, "Routing and addressing problems in large metropolitan-scale Internetworks," Univ. Southern California, Tech. Rep. ISI/RR-87-180, 1987.
[12]
H. Frey and I. Stojmenovic, "On delivery guarantees of face and combined greedy-face routing in ad hoc and sensor networks," in Proc. 12th MobiCom, 2006, pp. 390-401.
[13]
H. Füßler, J. Widmer, M. Mauve, and H. Hartenstein, "A novel forwarding paradigm for position-based routing (with implicit addressing)," in Proc. IEEE 18th Annu. CCW, Oct. 2003, pp. 194-200.
[14]
K. R. Gabriel and R. R. Sokal, "A new statistical approach to geographic variation analysis," Syst. Zool., vol. 18, no. 3, pp. 259-278, 1969.
[15]
J. Gao, L. J. Guibas, J. E. Hershberger, L. Zhang, and A. Zhu, "Geometric spanner for routing in mobile networks," in Proc. 2nd ACM Symp. Mobile Ad Hoc Netw. Comput., Oct. 2001, pp. 45-55.
[16]
T. Braun, "A novel position-based and beacon-less routing algorithm for mobile ad-hoc networks," in Proc. 3rd IEEE Workshop on Appl. Services in Wireless Netw., 2003, pp. 197-209.
[17]
M. Heissenbüttel, T. Braun, T. Bernoulli, and M. Wälchli, "BLR: Beacon-less routing algorithm for mobile ad-hoc networks," Comput. Commun., vol. 27, no. 11, pp. 1076-1086, Jul. 2004.
[18]
J. W. Jaromczyk and G. T. Toussaint, "Relative neighborhood graphs and their relatives," Proc. IEEE, vol. 80, no. 9, pp. 1502-1517, 1992.
[19]
H. Kalosha, A. Nayak, S. Rührup, and I. Stojmenovic, "Select-and-protest-based beaconless georouting with guaranteed delivery in wireless sensor networks," in Proc. 27th Annu. IEEE INFOCOM, Apr. 2008, pp. 346-350.
[20]
H. T. Kung, "Gpsr: greedy perimeter stateless routing for wireless networks," in Proc. 6th Annu. ACM/IEEE MobiCom, 2000, pp. 243-254.
[21]
Y.-J. Kim, R. Govindan, B. Karp, and S. Shenker, "Geographic routing made practical," in Proc. 2nd USENIX/ACM Symp. NSDI'05, May 2005, pp. 217-230.
[22]
Y.-J. Kim, R. Govindan, B. Karp, and S. Shenker, "Lazy cross-link removal for geographic routing," in Proc. 4th Int. Conf. Embedded Netw. Sens. Syst. (SenSys'06), 2006, pp. 112-124.
[23]
F. Kuhn, R. Wattenhofer, and A. Zollinger, "Ad-hoc networks beyond unit disk graphs," in Proc. 2003 Joint Workshop on Found. Mobile Comput. (DIALM-POMC), 2003, pp. 69-78.
[24]
F. Kuhn, R. Wattenhofer, and A. Zollinger, "Worst-case optimal and average-case efficient geometric ad-hoc routing," in Proc. 4th ACM Int. Symp. on Mobile Ad Hoc Netw. Comput., 2003, pp. 267-278.
[25]
J. Kuruvila, A. Nayak, and I. Stojmenovic, "Hop count optimal position-based packet routing algorithms for ad hoc wireless networks with a realistic physical layer," IEEE J. Sel. Areas Commun., vol. 23, no. 6, pp. 1267-1275, Jun. 2005.
[26]
B. Leong, B. Liskov, and R. Morris, "Geographic routing without planarization," in Proc. 3rd USENIX/ACM Symp. NSDI, 2006, pp. 339-352.
[27]
B. Leong, S. Mitra, and B. Liskov, "Path vector face routing: Geographic routing with local face information," in Proc. 13th IEEE ICNP, 2005, pp. 147-158.
[28]
Li X.-Y, G. Calinescu, and P.-J. Wan, "Distributed construction of planar spanner and routing for ad hoc wireless networks," in Proc. 21st Annu. IEEE INFOCOM, 2002, pp. 1268-1277.
[29]
Li X.-Y, "Approximate MST for UDG locally," in Proc. 9th Ann. Int. Conf. Comput. Combinator., 2003, pp. 364-373.
[30]
Li X.-Y, I. Stojmenovic, and Y. Wang, "Partial Delaunay triangulation and degree limited localized Bluetooth scatternet formation," IEEE Trans. Parallel Distrib. Syst., vol. 15, no. 4, pp. 350-361, 2004.
[31]
K. M. Lillis, S. V. Pemmaraju, and I. A. Pirwani, "Topology control and geographic routing in realistic wireless networks," Ad Hoc Sens. Wireless Netw., vol. 6, pp. 265-297, 2008.
[32]
M. Narasawa, M. Ono, and H. Higaki, "Nb-face: No-beacon face ad-hoc routing protocol for reduction of location acquisition overhead," in Proc. 7th Int. Conf. MDM, 2006, pp. 102-102.
[33]
H. Takagi and L. Kleinrock, "Optimal transmission ranges for randomly distributed packet radio terminals," IEEE Trans. Commun., vol. COM-32, no. 3, pp. 246-257, Mar. 1984.
[34]
M. Witt and V. Turau, "BGR: Blind geographic routing for sensor networks," in Proc. 3rd WISES, 2005, pp. 51-61.
[35]
Y. Xu, W.-C. Lee, J. Xu, and G. Mitchell, "PSGR: Priority-based stateless geo-routing in wireless sensor networks," in Proc. 2nd IEEE Int. Conf. MASS, 2005, pp. 673-680.
[36]
M. Zorzi, "A new contention-based MAC protocol for geographic forwarding in ad hoc and sensor networks," in Proc. IEEE ICC, 2004, pp. 3481-3485.

Cited By

View all
  • (2020)Weighted link quality and forward progress coupled with modified RTS/CTS for beaconless packet forwarding protocol (B-PFP) in VANETsTelecommunications Systems10.1007/s11235-016-0207-x75:2(145-160)Online publication date: 1-Oct-2020
  • (2018)Alternative forwarding strategies for geographic routing in wireless networksInternational Journal of Ad Hoc and Ubiquitous Computing10.1504/IJAHUC.2018.09060027:4(295-307)Online publication date: 1-Jan-2018
  • (2017)Coordinate-Assisted Routing Approach to Bypass Routing Holes in Wireless Sensor NetworksIEEE Communications Magazine10.1109/MCOM.2017.160034855:7(180-185)Online publication date: 1-Jan-2017
  • Show More Cited By

Index Terms

  1. Message-efficient beaconless georouting with guaranteed delivery in wireless sensor, ad hoc, and actuator networks

        Recommendations

        Comments

        Information & Contributors

        Information

        Published In

        cover image IEEE/ACM Transactions on Networking
        IEEE/ACM Transactions on Networking  Volume 18, Issue 1
        February 2010
        332 pages

        Publisher

        IEEE Press

        Publication History

        Published: 01 February 2010
        Revised: 31 August 2008
        Received: 21 April 2008
        Published in TON Volume 18, Issue 1

        Author Tags

        1. ad hoc networks
        2. beaconless routing
        3. contention-based forwarding
        4. geographic routing
        5. wireless sensor networks

        Qualifiers

        • Article

        Contributors

        Other Metrics

        Bibliometrics & Citations

        Bibliometrics

        Article Metrics

        • Downloads (Last 12 months)2
        • Downloads (Last 6 weeks)0
        Reflects downloads up to 19 Feb 2025

        Other Metrics

        Citations

        Cited By

        View all
        • (2020)Weighted link quality and forward progress coupled with modified RTS/CTS for beaconless packet forwarding protocol (B-PFP) in VANETsTelecommunications Systems10.1007/s11235-016-0207-x75:2(145-160)Online publication date: 1-Oct-2020
        • (2018)Alternative forwarding strategies for geographic routing in wireless networksInternational Journal of Ad Hoc and Ubiquitous Computing10.1504/IJAHUC.2018.09060027:4(295-307)Online publication date: 1-Jan-2018
        • (2017)Coordinate-Assisted Routing Approach to Bypass Routing Holes in Wireless Sensor NetworksIEEE Communications Magazine10.1109/MCOM.2017.160034855:7(180-185)Online publication date: 1-Jan-2017
        • (2017)EMGRComputer Networks: The International Journal of Computer and Telecommunications Networking10.1016/j.comnet.2017.08.011129:P1(51-63)Online publication date: 24-Dec-2017
        • (2016)Evaluation of MAC contention techniques for efficient geo-routing in vehicular networksAd Hoc Networks10.1016/j.adhoc.2015.09.00837:P1(44-62)Online publication date: 1-Feb-2016
        • (2016)Security of electrostatic field persistent routingAd Hoc Networks10.1016/j.adhoc.2015.07.01636:P1(270-295)Online publication date: 1-Jan-2016
        • (2015)Face Routing on a Non-Planar GraphProceedings of the 16th ACM International Symposium on Mobile Ad Hoc Networking and Computing10.1145/2746285.2746314(97-106)Online publication date: 22-Jun-2015
        • (2013)Intelligent beaconless geographical forwarding for urban vehicular environmentsWireless Networks10.1007/s11276-012-0470-z19:3(345-362)Online publication date: 1-Apr-2013
        • (2013)Spectrum-aware Beaconless Geographical Routing Protocol for Cognitive Radio Enabled Vehicular NetworksMobile Networks and Applications10.1007/s11036-013-0476-518:6(854-866)Online publication date: 1-Dec-2013

        View Options

        Login options

        Full Access

        View options

        PDF

        View or Download as a PDF file.

        PDF

        eReader

        View online with eReader.

        eReader

        Figures

        Tables

        Media

        Share

        Share

        Share this Publication link

        Share on social media