article

Virtual surrounding face geocasting in wireless ad hoc and sensor networks

Authors:

Kshirasagar Naik,

Lei ChenAuthors Info & Claims

IEEE/ACM Transactions on Networking (TON), Volume 17, Issue 1

Pages 200 - 211

https://doi.org/10.1109/TNET.2008.927251

Published: 01 February 2009 Publication History

Abstract

Geocasting in wireless sensor and ad hoc networks means delivering a message from a source node to all the nodes in a given geographical region. The objectives of a geocasting protocol are two-fold: guaranteed message delivery and low transmission cost. Most of the existing protocols do not guarantee message de-livery, and those that do, incur high transmission costs.

In this study, we propose the concept of Virtual Surrounding Face (VSF), and design a VSF-based geocasting protocol (VSFG). We also design a SKIP method and a local dominating set (DS) based restricted flooding technique to further reduce the cost of VSFG. Through mathematical analysis and comprehensive sim-ulations, we show that VSFG, together with SKIP and local DS based restricted flooding, guarantees message delivery and has a much lower transmission cost than the previous approaches. The reduction of cost can be up to 65% compared with the most effi-cient existing approach.

References

[1]

G. G. Finn, "Routing and addressing problems in large metropolitan internetworks," ISI Research Report ISU/RR-87-180, 1987.

[2]

E. Kranakis, H. Singh, and J. Urrutia, "Compass routing on geometric networks," in Proc. Canadian Conf. Computational Geometry, 1999, pp. 51-54.

[3]

P. Bose, P. Morin, I. Stojmenovic, and J. Urrutia, "Routing with guar-anteed delivery in ad hoc wireless networks," in Proc. ACM Workshop on Discrete Algorithms and Methods for Mobile Computing and Com-munications, 1999, pp. 48-55.

Digital Library

[4]

P. Bose, P. Morin, I. Stojmenovic, and J. Urrutia, "Routing with guar-anteed delivery in ad hoc wireless networks," Wireless Networks, vol. 7, no. 6, pp. 609-616, 2001.

Digital Library

[5]

H. Gupta, Z. Zhou, S. R. Das, and Q. Gu, "Connected sensor cover: Self-organization of sensor networks for efficient query execution," IEEE/ACM Trans. Networking, vol. 14, no. 1, pp. 55-67, Feb. 2006.

Digital Library

[6]

F. Kuhn, R. Wattenhofer, and A. Zollinger, "Asymptotically optimal geometric mobile ad hoc routing," in Proc. ACM Workshop on Discrete Algorithms and Methods for Mobile Computing and Communications, 2002, pp. 24-33.

Digital Library

[7]

F. Kuhn, R. Wattenhofer, Y. Zhang, and A. Zollinger, "Geometric ad hoc routing: Of theory and practice," in Proc. PODC, 2003, pp. 63-72.

Digital Library

[8]

A. Qayyum, L. Viennot, and A. Laouiti, "Multipoint relaying for flooding broadcast messages in mobile wireless networks," in Proc. Hawaii Int. Conf. System Sciences, 2002, pp. 3898-3907.

Digital Library

[9]

Y. B. Ko and N. H. Vaidya, "Geocasting in mobile ad hoc networks: Location-based multicast algorithms," in Proc. Workshop on Mobile Computer System and Applications, 1999, pp. 101-110.

Digital Library

[10]

S. Basagni, I. Chlamtac, and V. R. Syrotiuk, "Geographic messaging in wireless ad hoc networks," in Proc. VTC, 1999, pp. 1957-1961.

[11]

H. Takagi and L. Kleinrock, "Optimal transmission ranges for ran-domly distributed packet radio terminals," IEEE Trans. Commun., vol. 32, no. 3, pp. 246-257, Mar. 1984.

[12]

I. Stojmenovic, A. P. Ruhil, and D. K. Lobiyal, "Voronoi diagram and convex hull based geocasting and routing in wireless networks," in Proc. IEEE Symp. Computers and Communication (ISCC'03), 2003, vol. 1, pp. 51-56.

Digital Library

[13]

Y. B. Ko and N. H. Vaidya, "Flooding-based geocasting protocols for mobile ad hoc networks," Mobile Networks and Applications, vol. 7, no. 6, pp. 471-480, 2002.

Digital Library

[14]

C. Schwingenschlogl and T. Kosch, "Geocast enhancements of AODV for vehicular networks," ACM Mobile Computing and Communication, vol. 6, no. 3, pp. 96-97, 2002.

Digital Library

[15]

B. An and S. Papavassiliou, "Geomulticasting: Architectures and pro-tocols for mobile ad hoc networks," J. Parallel Distrib. Comput., vol. 63, pp. 182-195, 2003.

Digital Library

[16]

T. Camp and Y. Liu, "An adaptive mesh-based protocol for geocast routing," J. Parallel Distrib. Comput., vol. 62, no. 2, pp. 196-213, 2003.

Digital Library

[17]

K. Seada and A. Helmy, "Efficient geocasting with perfect delivery in wireless networks," in Proc. IEEE Wireless Communications and Networking Conf. (WCNC 2004), Mar. 2004, vol. 4, pp. 2551-2556.

[18]

I. Stojmenovic, "Geocasting with guaranteed delivery in sensor net-works," IEEE Wireless Commun., vol. 11, no. 6, pp. 29-37, Dec. 2004.

Digital Library

[19]

S. Ni, Y. Tseng, Y. Chen, and J. Sheu, "The broadcast storm problem in mobile ad hoc network," in Proc. ACM MOBICOM, 1999, pp. 152-162.

Digital Library

[20]

J. Wu and H. Li, "A dominating-set-based routing scheme in ad hoc wireless networks," Telecommun. Syst. J., vol. 3, Special Issue on Wire-less Networks, pp. 63-84, 2001.

[21]

I. Stojmenovic, M. Seddigh, and J. Zunic, "Dominating sets and neighbor elimination based broadcasting algorithms in wireless net-works," IEEE Trans. Parallel Distrib. Syst., vol. 13, no. 1, pp. 14-25, Jan. 2002.

Digital Library

[22]

J. Wu and F. Dai, "Mobility management and its applications in ef-ficient broadcasting in mobile ad hoc networks," in Proc. IEEE IN-FOCOM, 2004, pp. 339-350.

[23]

J. Lian, S. Naik, Y. Liu, and L. Chen, "Virtual surrounding face based geocasting with guaranteed message delivery for ad hoc and sensor net-works," in Proc. IEEE Int. Conf. Network Protocols (ICNP'06), Nov. 2006, pp. 198-207.

Digital Library

[24]

Y. Liu and M. Li, "Iso-Map: Energy-efficient contour mapping in wire-less sensor networks," in Proc. IEEE ICDCS, Jun. 2007, p. 36.

Digital Library

[25]

A. Muqattash and M. Krunz, "A distributed transmission power control protocol for mobile ad hoc networks," IEEE Trans. Mobile Comput., vol. 3, no. 2, pp. 113-128, Apr./Jun. 2004.

Digital Library

[26]

W. H. Liao et al., "Geogrid: A geocasting protocol for mobile ad hoc networks based on grid," J. Internet Technol., vol. 1, no. 2, pp. 23-32, 2000.

[27]

M. Garetto, J. Shi, and E. Knightly, "Modeling media access in em-bedded two-flow topologies of multi-hop wireless networks," in Proc. ACM MOBICOM, Aug. 2005, pp. 200-214.

Digital Library

[28]

R. Purtoosi, H. Taheri, A. Mohammadi, and F. Foroozan, "A high performance cluster-based flooding algorithm for wireless ad hoc networks," in Proc. IEEE Int. Conf. Computer and Information Tech-nology, 2005, pp. 417-423.

Digital Library

[29]

F. Foroozan and K. Tepe, "A high performance cluster-based broad-casting algorithm for wireless ad hoc networks based on a novel gateway selection approach," in Proc. ACM Int. Workshop on Per-formance Evaluation of Wireless Ad Hoc, Sensor, and Ubiquitous Networks, 2005, pp. 65-70.

Digital Library

[30]

H. Frey and I. Stojmenovic, "On delivery guarantees of face and com-bined greedy-face routing algorithms in ad hoc and sensor networks," in Proc. ACM MOBICOM, 2006, pp. 390-401.

Digital Library

[31]

A. Qayyum, L. Viennot, and A. Laouiti, "Multipoint relaying: An ef-ficient technique for flooding in mobile wireless networks," in Proc. 35th Annu. Hawaii Int. Conf. System Sciences (HICSS-35), 2002, pp. 298-307.

Digital Library

[32]

Y.-J. Kim, R. Govindan, B. Karp, and S. Shenker, "Geographic routing made practical," presented at the 2nd USENIX/ACM Symp. Networked System Design and Implementation (NSDI'05), Boston, MA, May 2005.

Digital Library

Cited By

Zhang GXu YWang XGuizani M(2018)Capacity of hybrid wireless networks with directional antenna and delay constraintIEEE Transactions on Communications10.1109/TCOMM.2010.07.09033058:7(2097-2106)Online publication date: 13-Dec-2018
https://dl.acm.org/doi/10.1109/TCOMM.2010.07.090330
Slavik MMahgoub I(2010)Stochastic broadcast for VANETProceedings of the 7th IEEE conference on Consumer communications and networking conference10.5555/1834217.1834258(205-209)Online publication date: 9-Jan-2010
https://dl.acm.org/doi/10.5555/1834217.1834258
Chen BPompili DFreitag LMidkiff SSchurgers CZhou S(2010)Reliable geocasting for underwater acoustic sensor networksProceedings of the 5th International Workshop on Underwater Networks10.1145/1868812.1868830(1-2)Online publication date: 30-Sep-2010
https://dl.acm.org/doi/10.1145/1868812.1868830
Show More Cited By

Index Terms

Virtual surrounding face geocasting in wireless ad hoc and sensor networks
1. Computing methodologies
  1. Modeling and simulation
    1. Model development and analysis
      1. Model verification and validation
      2. Modeling methodologies
2. Networks

Recommendations

Multi-geocast Algorithms for Wireless Sparse or Dense Ad Hoc Sensor Networks
ICNS '08: Proceedings of the Fourth International Conference on Networking and Services

Multi-Geocasting in wireless sensor network and Ad Hoc network is the delivery of packets from a source (or sink) to all the nodes located in several geographic areas. The objectives of a multi-geocasting protocol are guaranteed message delivery and low ...
Efficient and robust geocasting protocols for sensor networks

Geocasting is the delivery of packets to nodes within a certain geographic area. For many applications in wireless ad hoc and sensor networks, geocasting is an important and frequent communication service. The challenging problem in geocasting is ...
Flooding-based geocasting protocols for mobile ad hoc networks

Geocasting is a variation on the notion of multicasting. A geographical area is associated with each geocast, and the geocast is delivered to the nodes within the specified geographical area. Thus, geocasting may be used for sending a message that is ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image IEEE/ACM Transactions on Networking

IEEE/ACM Transactions on Networking Volume 17, Issue 1

February 2009

346 pages

ISSN:1063-6692

Issue’s Table of Contents

Publisher

IEEE Press

Publication History

Published: 01 February 2009

Revised: 27 August 2007

Received: 30 December 2006

Published in TON Volume 17, Issue 1

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

4
Total Citations
View Citations
315
Total Downloads

Downloads (Last 12 months)1
Downloads (Last 6 weeks)0

Reflects downloads up to 20 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Zhang GXu YWang XGuizani M(2018)Capacity of hybrid wireless networks with directional antenna and delay constraintIEEE Transactions on Communications10.1109/TCOMM.2010.07.09033058:7(2097-2106)Online publication date: 13-Dec-2018
https://dl.acm.org/doi/10.1109/TCOMM.2010.07.090330
Slavik MMahgoub I(2010)Stochastic broadcast for VANETProceedings of the 7th IEEE conference on Consumer communications and networking conference10.5555/1834217.1834258(205-209)Online publication date: 9-Jan-2010
https://dl.acm.org/doi/10.5555/1834217.1834258
Chen BPompili DFreitag LMidkiff SSchurgers CZhou S(2010)Reliable geocasting for underwater acoustic sensor networksProceedings of the 5th International Workshop on Underwater Networks10.1145/1868812.1868830(1-2)Online publication date: 30-Sep-2010
https://dl.acm.org/doi/10.1145/1868812.1868830
Li MLiu Y(2010)Rendered pathIEEE/ACM Transactions on Networking (TON)10.1109/TNET.2009.202494018:1(320-332)Online publication date: 1-Feb-2010
https://dl.acm.org/doi/10.1109/TNET.2009.2024940

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Issue’s Table of Contents