article

G-STAR: Geometric STAteless Routing for 3-D wireless sensor networks

Authors:

Benjamin R. Hamilton,

Xiaoli MaAuthors Info & Claims

Ad Hoc Networks, Volume 9, Issue 3

Pages 341 - 354

https://doi.org/10.1016/j.adhoc.2010.07.013

Published: 01 May 2011 Publication History

Abstract

3-D aerial and underwater sensor networks have found various applications in natural habitat monitoring, weather/earthquake forecast, terrorist intrusion detection, and homeland security. The resource-constrained and dynamic nature of such networks has made the stateless routing protocol with only local information a preferable choice. However, most of the existing routing protocols require sensor nodes to either proactively maintain the state information or flood the network from time to time. The existing stateless geometric routing protocols either fail to work in 3-D environments or have tendency to produce lengthy paths. In this paper, we propose a novel routing protocol, namely Geometric STAteless Routing (G-STAR) for 3-D networks. The main idea of G-STAR is to distributively build a location-based tree and find a path dynamically. G-STAR not only generalizes the notion of geographic routing from two modes to one mode, but also guarantees packet delivery even when the location information of some nodes is either inaccurate or simply unavailable regardless of the uses of virtual coordinates. In addition, we develop a light-weight path pruning algorithm, namely Branch Pruning (BP), that can be combined with G-STAR to enhance the routing performance with very little overhead. The extensive simulation results by ns-2 have shown that the proposed routing protocols perform significantly better than the existing 3-D geometric routing protocols in terms of delivery rate with competitive hop stretch. We conclude that the proposed protocols serve as a strong candidate for future high-dimensional sensor networks.

References

[1]

Sozer, E.M., Stojanovic, M. and Proakis, J.G., Underwater acoustic networks. IEEE Journal of Oceanic Engineering. v25 i1. 72-83.

[2]

V.R. Syrotiuk, C.J. Colbourn, Routing in mobile aerial networks, in: Proceedings of WiOpt, 2003, pp. 293-301.

[3]

Akyildiz, I.F., Su, W., Sankarasubramaniam, Y. and Cayirci, E., Wireless sensor networks: a survey. Computer Networks. v38. 393-422.

[4]

C.E. Perkins, P. Bhagwat, Highly dynamic destination-sequenced distance-vector routing (DSDV) for mobile computers, in: Proceedings of the ACM International Conference on Communications Architectures, Protocols and Appliations (SIGCOMM), 1994, pp. 234-244.

[5]

D.B. Johnson, Routing in ad hoc networks of mobile hosts, in: Proceedings of IEEE Internatinal Workshop on Mobile Computing Systems and Applications, 1994, pp. 158-163.

Digital Library

[6]

P. Bose, P. Morin, I. Stojmenovic, J. Urrutia, Routing with guaranteed delivery in ad hoc wireless networks, in: Proceedings of the 3rd International Workshop on Discrete Algorithms and Methods for Mobile Computing and Communications (DIAL-M), 1999, pp. 48-55.

Digital Library

[7]

B. Karp, H.T. Kung, GPSR: greedy perimeter stateless routing for wireless networks, in: Proceedings of the ACM International Conference on Mobile Computing and Networking (MOBICOM), 2000, pp. 243-254.

Digital Library

[8]

F. Kuhn, R. Wattenhofer, Y. Zhang, A. Zollinger, Geometric ad-hoc routing: of theory and practice, in: Proceedings of the 22nd Annual Symposium on Principles of Distributed Computing (PODC), 2003.

[9]

B. Leong, B. Liskov, R. Morris, Geographic routing without planarization, in: Proceedings of the 3rd Conference on Networked Systems Design and Implementation (NSDI), 2006, pp. 25-25.

Digital Library

[10]

Y.-J. Kim, R. Govindan, B. Karp, S. Shenker, Geographic routing made practical, in: Proceedings of the USENIX Symposium on Networked Systems Design and Implementation (NSDI), 2005, pp. 217-230.

[11]

R. Kleinberg, Geographic routing using hyperbolic space, in: Proceedings of the IEEE International Conference on Computer Communications (INFOCOM), 2007, pp. 1902-1909.

Digital Library

[12]

R. Flury, R. Wattenhofer, Randomized 3D geographic routing, in: Proceedings of the IEEE International Conference on Computer Communications (INFOCOM), 2008, pp. 834-842.

[13]

C. Liu, J. Wu, Efficient geometric routing in three dimensional ad hoc networks, in: Proceedings of the IEEE International Conference on Computer Communications (INFOCOM), Mini Conference, 2009.

[14]

A. Rao, S. Ratnasamy, C. Papadimitriou, S. Shenker, I. Stoica, Geographic routing without location information, in: Proceedings of the 9th Annual International Conference on Mobile Computing and Networking (MOBICOM), 2003, pp. 96-108.

Digital Library

[15]

Watteyne, T., Augé-Blum, I., Dohler, M., Ubéda, S. and Barthel, D., Centroid virtual coordinates - a novel near-shortest path routing paradigm. Computer Network. v53 i10. 1697-1711.

[16]

T. Watteyne, D. Simplot-Ryl, I. Auge-Blum, M. Dohler, On using virtual coordinates for routing in the context of wireless sensor networks, in: Proceeding of the International Symposium on Personal, Indoor and Mobile Radio Communications (PIMRC), 2007.

[17]

T. Watteyne, I. Auge-Blum, M. Dohler, D. Barthel, Geographic forwarding in wireless sensor networks with loose position-awareness, in: Proceeding of the International Symposium on Personal, Indoor and Mobile Radio Communications (PIMRC), 2007.

[18]

M. Caesar, M. Castro, E.B. Nightingale, Virtual ring routing: network routing inspired by DHTs, in: Proceedings of the ACM International Conference on Communications Architectures, Protocols and Applications (SIGCOMM), 2006, pp. 351-362.

[19]

A. Awad, C. Sommer, R. German, F. Dressler, Virtual cord protocol (vcp): a flexible dht-like routing service for sensor networks, in: Proceedings of the IEEE International Conference on Mobile Ad-hoc and Sensor Systems (MASS 2008), 2008, pp. 133-142.

[20]

I. Stojmenovic, M. Russell, B. Vukojevic, Depth first search and location based localized routing and QoS routing in wireless networks, in: Proceedings of the International Conference on Parallel Processing (ICPP), 2000, p. 173.

[21]

I. Stojmenovic, M. Russell, B. Vukojevic, Depth first search and location based localized routing and QoS routing in wireless networks in: Proceedings of the International Conference on Parallel Processing (ICPP), 2002, pp. 149-165.

[22]

F. Kuhn, R. Wattenhofer, A. Zollinger, Asymptotically optimal geometric mobile ad-hoc routing, in: Proceedings of the 6th International Workshop on Discrete Algorithms and Methods for Mobile Computing and Communications (DIALM), 2002.

Digital Library

[23]

F. Kuhn, R. Wattenhofer, A. Zollinger, Worst-case optimal and average-case efficient geometric ad-hoc routing, in: Proceedings of the ACM International Symposium on Mobile Ad Hoc Networking and Computing (MobiHoc), 2003, pp. 267-278.

Digital Library

[24]

Garbriel, K. and Sokal, R., A new statistical approach to geographic variation analysis. Systematic Zoology. v18. 259-278.

[25]

Toussaint, G., The relative neighborhood graph of a finite planarset. Pattern Recognition. v12 i4. 261-268.

[26]

Li, X.-Y., Calinescu, G., Wan, P.-J. and Wang, Y., Localized delaunay triangulation with application in ad hoc wireless networks. IEEE Transactions on Parallel Distributed Systems. v14 i10. 1035-1047.

[27]

H. Yan, Z.J. Shi, J.-H. Cui, DBR: depth-based routing for underwater sensor networks, in: Proceedings of the IFIP Networking, 2008, pp. 1-13.

[28]

D. Pompili, T. Melodia, I.F. Akyildiz, Routing algorithms for delay-insensitive and delay-sensitive applications in underwater sensor networks, in: Proceedings of the ACM/IEEE International Conference on Mobile Computing and Networking (MOBICOM), 2006.

Digital Library

[29]

N. Nicolaou, A. See, P. Xie, J.-H. Cui, D. Maggiorini, Improving the robustness of location-based routing for underwater sensor networks in: Proceedings of the IEEE OCEANS, 2007, pp. 18-21.

[30]

Kurose, J.F. and Ross, K.W., Computer Networking: A Top-Down Approach. 2009. fifth ed. Addison-Wesley Publishing Company.

[31]

R. Ramanathan, R. Hain, Topology control of multihop wireless networks using transmit power adjustment, in: Proceedings of the IEEE 23rd International Conference on Computer Communication (INFOCOM), 2000, pp. 404-413.

[32]

Bahramgiri, M., Hajiaghayi, M. and Mirrokni, V.S., Fault-tolerant and 3-dimensional distributed topology control algorithms in wireless multi-hop networks. Wireless Networks. v12 i2. 179-188.

[33]

A. Ghosh, Y. Wang, B. Krishnamachari, M. Hsieh, Efficient distributed topology control in 3-dimensional wireless networks, in: Proceedings of the IEEE 4th International Conference on Sensor, Mesh and Ad Hoc Communications and Networks (SECON), vol. 12, 2007, pp. 91-100.

[34]

Cormen, T.H., Leiserson, C.E., Rivest, R.L. and Stein, C., Introduction to Algorithms. 2001. second ed. The MIT Press.

[35]

Even, S., Graph Algorithms. 1979. Computer Science Press.

[36]

Bollobas, B., Random Graphs. 1985. Academic Press.

[37]

Ma, X., Sun, M.-T., Liu, X. and Zhao, G., An efficient path pruning algorithm for geographical routing in wireless networks. IEEE Transactions on Vehicular Technology. v57 i4. 2474-2488.

[38]

Rappaport, T.S., Wireless Communications: Principles and Practice. 2001. second ed. Princeton-Hall.

[39]

K. Seada, M. Zuniga, A. Helmy, B. Krishnamachari, Energy-efficient forwarding strategies for geographic routing in lossy wireless sensor networks, in: Proceedings of the 2nd International Conference on Embedded Networked Sensor Systems (SenSys), 2004, pp. 108-121.

Digital Library

[40]

B.R. Hamilton, X. Ma, Noncooperative routing with cooperative diversity, in: Proceedings of the IEEE International Conference on Communications (ICC), 2007, pp. 4237-4242.

[41]

The Network Simulator (ns-2), <http://www.isi.edu/nsnam/ns/>.

[42]

IEEE 802.11b Standard, <http://standards.ieee.org/getieee802/download/802.11b-1999.pdf>.

Cited By

(2018)Clustering-based energy-efficient routing approach for underwater wireless sensor networksInternational Journal of Sensor Networks10.1504/IJSNET.2018.09211427:1(26-36)Online publication date: 1-Jan-2018
https://dl.acm.org/doi/10.1504/IJSNET.2018.092114
Ammari H(2016)3D-kCov-ComForACM Transactions on Sensor Networks10.1145/282289412:4(1-32)Online publication date: 15-Nov-2016
https://dl.acm.org/doi/10.1145/2822894
Gao CZhao GLu JPan S(2015)A grid-based cooperative QoS routing protocol with fading memory optimization for navigation carrier ad hoc networksComputer Networks: The International Journal of Computer and Telecommunications Networking10.1016/j.comnet.2014.11.01776:C(294-316)Online publication date: 15-Jan-2015
https://dl.acm.org/doi/10.1016/j.comnet.2014.11.017

G-STAR: Geometric STAteless Routing for 3-D wireless sensor networks
1. Networks
  1. Network protocols
    1. Network layer protocols
  2. Network types

Recommendations

Aligned virtual coordinates for greedy geometric routing in WSNs

The performance of geographic routing protocols is impacted by physical voids and localisation errors. Traversing voids is carried out by a complimentary algorithm, which requires high overhead and results in lower quality paths. Furthermore, ...
On greedy geographic routing algorithms in sensing-covered networks
MobiHoc '04: Proceedings of the 5th ACM international symposium on Mobile ad hoc networking and computing

Greedy geographic routing is attractive in wireless sensor networks due to its efficiency and scalability. However, greedy geographic routing may incur long routing paths or even fail due to routing voids on random network topologies. We study greedy ...
Experimental validation of resilient tree-based greedy geometric routing

Geometric routing is an alternative for IP routing based on longest prefix matching. Using this routing paradigm, every node in the network is assigned a coordinate and packets are forwarded towards their intended destination following a distance-...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Ad Hoc Networks

Ad Hoc Networks Volume 9, Issue 3

May, 2011

266 pages

ISSN:1570-8705

Issue’s Table of Contents

Copyright © Elsevier B.V. © 2010.

Publisher

Elsevier Science Publishers B. V.

Netherlands

Publication History

Published: 01 May 2011

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

3
Total Citations
View Citations
0
Total Downloads

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

Reflects downloads up to 20 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

(2018)Clustering-based energy-efficient routing approach for underwater wireless sensor networksInternational Journal of Sensor Networks10.1504/IJSNET.2018.09211427:1(26-36)Online publication date: 1-Jan-2018
https://dl.acm.org/doi/10.1504/IJSNET.2018.092114
Ammari H(2016)3D-kCov-ComForACM Transactions on Sensor Networks10.1145/282289412:4(1-32)Online publication date: 15-Nov-2016
https://dl.acm.org/doi/10.1145/2822894
Gao CZhao GLu JPan S(2015)A grid-based cooperative QoS routing protocol with fading memory optimization for navigation carrier ad hoc networksComputer Networks: The International Journal of Computer and Telecommunications Networking10.1016/j.comnet.2014.11.01776:C(294-316)Online publication date: 15-Jan-2015
https://dl.acm.org/doi/10.1016/j.comnet.2014.11.017

View Options

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 Publication

Media

Figures

Other

Tables

View Issue’s Table of Contents