Article

Beacon vector routing: scalable point-to-point routing in wireless sensornets

Authors:

Rodrigo Fonseca,

Sylvia Ratnasamy,

Ion StoicaAuthors Info & Claims

NSDI'05: Proceedings of the 2nd conference on Symposium on Networked Systems Design & Implementation - Volume 2

Pages 329 - 342

Published: 02 May 2005 Publication History

Publisher Site Get Access

Abstract

We propose a practical and scalable technique for point-to-point routing in wireless sensornets. This method, called Beacon Vector Routing (BVR), assigns coordinates to nodes based on the vector of hop count distances to a small set of beacons, and then defines a distance metric on these coordinates. BVR routes packets greedily, forwarding to the next hop that is the closest (according to this beacon vector distance metric) to the destination. We evaluate this approach through a combination of high-level simulation to investigate scaling and design tradeoffs, and a prototype implementation over real testbeds as a necessary reality check.

References

[1]

{1} BOSE, P., MORIN, P., STOJMENOVIC, I., AND URRUTIA, J. Routing with guaranteed delivery in ad hoc wireless networks. Wireless Networks 7, 6 (2001), 609-616.]]

Digital Library

[2]

{2} CAO, Q., AND ABDELZAHER, T. A scalable logical coordinates framework for routing in wireless sensor networks. In IEEE Real-time Systems Symposium (December 2004).]]

Digital Library

[3]

{3} COUTO, D. D., AGUAYO, D., CHAMBERS, B., AND MORRIS, R. Performance of multihop wireless networks: Shortest path is not enough. In Proceedings of HotNets (Oct. 2002).]]

[4]

{4} DEMIRBAS, M., ARORA, A., AND GOUDA, M. A pursuerevader game for sensor networks. In Proceedings of the Sixth Symposium on Self-Stabilizing Systems (2003), pp. 1-16.]]

[5]

{5} FLOYD, S., JACOBSON, V., MCCANNE, S., LIU, C., AND ZHANG, L. A reliable multicast framework for light-weight sessions and application level framing. In Proceedings of SIGCOMM (1995), ACM Press, pp. 342-356.]]

Digital Library

[6]

{6} GANESAN, D., ESTRIN, D., AND HEIDEMANN, J. DIMENSIONS: Why do we need a new data handling architecture for sensor networks? In Proceedings of the ACM HotNets (October 2002), ACM, pp. 143-148.]]

[7]

{7} GIROD, L., STATHOPOULOS, T., RAMANATHAN, N., ELSON, J., ESTRIN, D., OSTERWEIL, E., AND SCHOELLHAMMER, T. EmStar: An environment for developing wireless embedded systems software. In Proceedings of the Second SenSys (Nov. 2004), ACM Press.]]

[8]

{8} GREENSTEIN, B., ESTRIN, D., GOVINDAN, R., RATNASAMY, S., AND SHENKER, S. DIFS: A distributed index for features in sensor networks. In Proceedings of First IEEE WSNA (May 2003).]]

[9]

{9} HAMILTON, M., ALLEN, M., ESTRIN, D., ROTTENBERRY, J., RUNDEL, P., SRIVASTAVA, M., AND SOATTO, S. Extensible sensing system: An advanced network design for microclimate sensing, June 2003.]]

[10]

{10} HILL, J., AND CULLER, D. Mica: a wireless platform for deeply embedded networks. IEEE Micro 22, 6 (November 2002), 12-24.]]

Digital Library

[11]

{11} HILL, J., SZEWCZYK, R., WOO, A., HOLLAR, S., CULLER, D., AND PISTER, K. System architecture directions for networked sensors. In Proceedings of the ASPLOS (2000), ACM Press, pp. 93-104.]]

Digital Library

[12]

{12} INTANAGONWIWAT, C., GOVINDAN, R., AND ESTRIN, D. Directed Diffusion: a scalable and robust communication paradigm for sensor networks. In Proceedings of the 6th Annual MOBICOM (2000), ACM Press, pp. 56-67.]]

Digital Library

[13]

{13} JOHNSON, D. B., AND MALTZ, D. A. Dynamic source routing in ad hoc wireless networks. In Mobile Computing, Imielinski and Korth, Eds., vol. 353. Kluwer Academic Publishers, 1996.]]

[14]

{14} KARGER, D. R., LEHMAN, E., LEIGHTON, T., LEVINE, M., LEWIN, D., AND PANIGRAHY, R. Consistent hashing and random trees: Distributed caching protocols for relieving hot spots on the world wide web. In Proc. 29th ACM STOC (May 1997), pp. 654-663.]]

Digital Library

[15]

{15} KARP, B., AND KUNG, H. T. GPSR: Greedy perimeter stateless routing for wireless networks. In Proceedings of the 6th annual MOBICOM (2000), ACM Press, pp. 243-254.]]

Digital Library

[16]

{16} KUHN, F., WATTENHOFER, R., ZHANG, Y., AND ZOLLINGER, A. Geometric ad-hoc routing: Of theory and practice. In 22nd ACM PODC (2003).]]

Digital Library

[17]

{17} KUMAR, S., ALAETTINGLU, C., AND ESTRIN, D. Scalable object-tracking through unattended techniques (scout). In Proceedings of the 2000 International Conference on Network Protocols (2000), IEEE Computer Society, p. 253.]]

Digital Library

[18]

{18} LEVIS, P., LEE, N., WELSH, M., AND CULLER, D. Tossim: accurate and scalable simulation of entire TinyOS applications. In Proceedings of the First SenSys (2003), ACM Press, pp. 126-137.]]

Digital Library

[19]

{19} LEVIS, P., MADDEN, S., GAY, D., POLASTRE, J., SZEWCZYK, R., WOO, A., BREWER, E., AND CULLER, D. The emergence of networking abstractions and techniques in tinyos. In Proceedings of the First USENIX/ACM NSDI (March 2004).]]

Digital Library

[20]

{20} LI, X., KIM, Y. J., GOVINDAN, R., AND HONG, W. Multi-dimensional range queries in sensor networks. In Proceedings of the First SenSys (2003), ACM Press, pp. 63-75.]]

Digital Library

[21]

{21} MADDEN, S. The design and evaluation of a query processing architecture for sensor networks. PhD thesis, UC Berkeley, 2003.]]

Digital Library

[22]

{22} MADDEN, S., FRANKLIN, M., HELLERSTEIN, J., AND HONG, W. TAG: a tiny aggregation service for ad hoc sensor networks. In OSDI (2002).]]

Digital Library

[23]

{23} MAINWARING, A., POLASTRE, J., SZEWCZYK, R., CULLER, D., AND ANDERSON, J. Wireless sensor networks for habitat monitoring. In Proceedings of ACM WSNA (Sept. 2002).]]

Digital Library

[24]

{24} NEWSOME, J., AND SONG, D. Gem: Graph embedding for routing and data-centric storage in sensor networks without geographic information. In Proceedings of the First SenSys (2003), ACM Press, pp. 76-88.]]

Digital Library

[25]

{25} RAO, A., RATNASAMY, S., PAPADIMITRIOU, C., SHENKER, S., AND STOICA, I. Geographic routing without location information. In Proceedings of the 9th Annual MOBICOM (2003), ACM Press, pp. 96-108.]]

Digital Library

[26]

{26} ROYER, E. M., AND TOH, C.-K. A review of current routing protocols for ad-hoc mobile wireless networks. IEEE Personal Communications 6 (April 1999), 46-55.]]

[27]

{27} SAVVIDES, A., HAN, C.-C., AND SRIVASTAVA, M. B. Dynamic fine-grained localization in ad-hoc networks of sensors. In Mobile Computing and Networking (2001), pp. 166-179.]]

Digital Library

[28]

{28} SEADA, K., ZUNIGA, M., HELMY, A., AND KRISHNAMACHARI, B. Energy-efficient forwarding strategies for geographic routing in lossy wireless sensor networks. In Proceedings of the 2nd SenSys (2004), ACM Press, pp. 108-121.]]

Digital Library

[29]

{29} SHENKER, S., RATNASAMY, S., KARP, B., GOVINDAN, R., AND ESTRIN, D. Data-centric storage in sensornets. SIGCOMM Comput. Commun. Rev. 33, 1 (2003), 137-142.]]

Digital Library

[30]

{30} SZEWCZYK, R., POLASTRE, J., MAINWARING, A., ANDERSON, J., AND CULLER, D. An analysis of a large scale habitat monitoring application. In Proceedings of the Second SenSys (2004), ACM Press.]]

Digital Library

[31]

{31} TSUCHIYA, P. F. The Landmark Hierarchy: a new hierarchy for routing in very large networks. In ACM SIGCOMM (1988), ACM Press, pp. 35-42.]]

Digital Library

[32]

{32} WOO, A., TONG, T., AND CULLER, D. Taming the underlying challenges of reliable multihop routing in sensor networks. In Proceedings of the First SenSys (2003), ACM Press, pp. 14-27.]]

Digital Library

[33]

{33} ZHAO, J., AND GOVINDAN, R. Understanding packet delivery performance in dense wireless sensor networks. In Proceedings of the First SenSys (2003), ACM Press, pp. 1-13.]]

Digital Library

[34]

{34} ZHAO, J., GOVINDAN, R., AND ESTRIN, D. Computing aggregates for monitoring wireless sensor networks. In Proceedings of the IEEE SNPA (May 2003).]]

Cited By

Sahhaf SDixit ATavernier WColle DPickavet MDemeester P(2018)All-optical tree-based greedy router using optical logic gates and optical flip-flopsPhotonic Network Communications10.1007/s11107-017-0723-y35:1(109-121)Online publication date: 1-Feb-2018
https://dl.acm.org/doi/10.1007/s11107-017-0723-y
Aksa K(2017)BilliardoWireless Personal Communications: An International Journal10.1007/s11277-016-3675-094:3(1147-1164)Online publication date: 1-Jun-2017
https://dl.acm.org/doi/10.1007/s11277-016-3675-0
Hoffmann SWanke EXing G(2016)Generic route repairProceedings of the 15th International Conference on Information Processing in Sensor Networks10.5555/2959355.2959367(1-10)Online publication date: 11-Apr-2016
https://dl.acm.org/doi/10.5555/2959355.2959367
Show More Cited By

Index Terms

Beacon vector routing: scalable point-to-point routing in wireless sensornets
1. Hardware
  1. Communication hardware, interfaces and storage
    1. Signal processing systems
2. Networks
  1. Network protocols
    1. Network layer protocols
      1. Routing protocols
  2. Network types
    1. Mobile networks
    2. Wireless access networks

Recommendations

Performance analysis of fault-tolerant beacon vector routing for wireless sensor networks
MSWiM '05: Proceedings of the 8th ACM international symposium on Modeling, analysis and simulation of wireless and mobile systems

This paper presents a performance analysis for an improved Beacon Vector Routing (BVR) protocol. BVR algorithms are useful for point-to-point routing in wireless sensor networks. The original BVR algorithm is compared through performance analysis to ...
Fault-Tolerant Beacon Vector Routing for Mobile Ad Hoc Networks
IPDPS '05: Proceedings of the 19th IEEE International Parallel and Distributed Processing Symposium (IPDPS'05) - Workshop 16 - Volume 17

This paper presents a new and robust Fault-Tolerant Beacon Vector Routing (BVR) approach with multiple novel improvements. The fault tolerance algorithm NetRec was extended to apply to BVR. The new technique, ManRec, provides fault tolerance in the ...
Beacon location service: a location service for point-to-point routing in wireless sensor networks
IPSN '07: Proceedings of the 6th international conference on Information processing in sensor networks

In this paper we present Beacon Location Service (BLS): a location service for beacon-based routing algorithms like Beacon Vector Routing (BVR) [8] and S4 [19] . The role of a location service is to map node names to topologically meaningful addresses ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

NSDI'05: Proceedings of the 2nd conference on Symposium on Networked Systems Design & Implementation - Volume 2

May 2005

356 pages

Sponsors

Publisher

USENIX Association

United States

Publication History

Published: 02 May 2005

Check for updates

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

69
Total Citations
View Citations
389
Total Downloads

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

Reflects downloads up to 20 Sep 2024

Other Metrics

View Author Metrics

Citations

Cited By

Sahhaf SDixit ATavernier WColle DPickavet MDemeester P(2018)All-optical tree-based greedy router using optical logic gates and optical flip-flopsPhotonic Network Communications10.1007/s11107-017-0723-y35:1(109-121)Online publication date: 1-Feb-2018
https://dl.acm.org/doi/10.1007/s11107-017-0723-y
Aksa K(2017)BilliardoWireless Personal Communications: An International Journal10.1007/s11277-016-3675-094:3(1147-1164)Online publication date: 1-Jun-2017
https://dl.acm.org/doi/10.1007/s11277-016-3675-0
Hoffmann SWanke EXing G(2016)Generic route repairProceedings of the 15th International Conference on Information Processing in Sensor Networks10.5555/2959355.2959367(1-10)Online publication date: 11-Apr-2016
https://dl.acm.org/doi/10.5555/2959355.2959367
Qian CLam SChen Qian Lam S(2016)Greedy Routing by Network Distance EmbeddingIEEE/ACM Transactions on Networking10.1109/TNET.2015.244976224:4(2100-2113)Online publication date: 1-Aug-2016
https://dl.acm.org/doi/10.1109/TNET.2015.2449762
Tan GYin ZJiang H(2016)Trap arrayIEEE/ACM Transactions on Networking10.1109/TNET.2014.236294324:1(328-341)Online publication date: 1-Feb-2016
https://dl.acm.org/doi/10.1109/TNET.2014.2362943
Qian CLam S(2016)A scalable and resilient layer-2 network with ethernet compatibilityIEEE/ACM Transactions on Networking10.1109/TNET.2014.236177324:1(231-244)Online publication date: 1-Feb-2016
https://dl.acm.org/doi/10.1109/TNET.2014.2361773
Tschopp DDiggavi SGrossglauser M(2015)Hierarchical routing over dynamic wireless networksRandom Structures & Algorithms10.1002/rsa.2058947:4(669-709)Online publication date: 1-Dec-2015
https://dl.acm.org/doi/10.1002/rsa.20589
Tan GJiang HLiu JKermarrec A(2014)Convex Partitioning of Large-Scale Sensor Networks in Complex FieldsACM Transactions on Sensor Networks10.1145/259477210:3(1-23)Online publication date: 6-May-2014
https://dl.acm.org/doi/10.1145/2594772
Gnawali OFonseca RJamieson KKazandjieva MMoss DLevis P(2013)CTPACM Transactions on Sensor Networks10.1145/252998810:1(1-49)Online publication date: 6-Dec-2013
https://dl.acm.org/doi/10.1145/2529988
Tan GJiang HZhang SYin ZKermarrec A(2013)Connectivity-based and anchor-free localization in large-scale 2D/3D sensor networksACM Transactions on Sensor Networks10.1145/252997610:1(1-21)Online publication date: 6-Dec-2013
https://dl.acm.org/doi/10.1145/2529976
Show More Cited By

View Options

Get Access

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

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents