Qing Cao
Tarek Abdelzaher
Skip Abstract Section
Abstract
In this article, we present logical coordinates based routing (LCR), a novel framework for scalable and location-independent routing in wireless sensor networks. LCR assigns each node a logical coordinate vector, and routes packets following these vectors. We demonstrate that LCR (i) guarantees packet delivery with a high probability, (ii) finds good paths, and (iii) exhibits robust performance in the presence of network voids and node failures. We systematically evaluate the performance of LCR through simulations and compare it with other state-of-the-art protocols. We also propose two extensions of LCR, one for three-dimensional node deployments and the other for unreliable wireless links.
- ARGO. http://www.argo.ucsd.edu/. Project argo website.Google Scholar
- Bose, P., Morin, P., Stojmenovic, I., and Urrutia, J. 2001. Routing with guaranteed delivery in ad hoc wireless networks. Wireless Netw. 7, 6, 609--616. Google Scholar
- Broch, J., Maltz, D. A., Johnson, D. B., Hu, Y., and Jetcheva, J. 1998. A performance comparison of multi-hop wireless ad hoc network routing protocols. In Proceedings of the 4th ACM/IEEE International Conference on Mobile Computing and Networking. ACM Press, 85--97. Google Scholar
- Bulusu, N., Heidemann, J., and Estrin, D. 2000. Gps-less low cost outdoor localization for very small devices. IEEE Pers. Comm. Mag. 7, 5 (Oct.), 28--34.Google Scholar
- Cao, Q. and Abdelzaher, T. 2004. A scalable logical coordinates framework for routing in wireless sensor networks. In Proceedings of the 25th Internetional Real-Time Systems Symposium (RTSS 04). vol. 00. ACM Press, 349--358. Google Scholar
- Carzaniga, A., Rosenblum, D., and Wolf, A. 2000. Content-based addressing and routing: A general model and its application. Tech. Rep. CU-CS-902-00, Dept. of Computer Science, Univ. of Colorado, Sept.Google Scholar
- Finn, G. March 1987. Routing and addressing problems in large metropolitan-scale internetworks. In Tech. Rep. Vol. ISI/RR-87-180. USC/ISI.Google Scholar
- Fonseca, R., Ratnasamy, S., Zhao, J., Ee, C., Culler, D., Shenker, S., and Stoica, I. 2005. Beacon vector routing: Scalable point-to-point routing in wireless sensornets. In the 2nd Symposium on Networked Systems Design and Implementation. ACM Press. Google Scholar
- GloMoSim. http://pcl.cs.ucla.edu/projects/glomosim/. Glomosim website.Google Scholar
- He, T., Huang, C., Blum, B., Stankovic, J., and Abdelzaher, T. 2003. Range-free localization schemes in large scale sensor networks. In Proceedings of the 9th Annual ACM/IEEE International Conference on Mobile Computing and Networking. ACM Press. Google Scholar
- Johnson, D. and Maltz, D. 1996. Dynamic source routing in ad hoc wireless networks. In Mobile Computing, Imielinski and Korth, Eds. vol. 353. Kluwer Academic Publishers.Google Scholar
- Karp, B. and Kung, H. T. 2000. Gpsr: greedy perimeter stateless routing for wireless networks. In Proceedings of the 6th Annual ACM/IEEE International Conference on Mobile Computing and Networking. ACM Press, 243--254. Google Scholar
- Kim, Y., Govindan, R., Karp, B., and Shenker, S. 2005. Geographic routing made practical. In Proceedings of the 2nd Symposium on Networked Systems Design and Implementation. Google Scholar
- Kuhn, F., Wattenhofer, R., and Zollinger, A. 2003. Worst-case optimal and average-case efficient geometric ad hoc routing. In Proceedings of the 4th ACM International Symposium on Mobile ad hoc Networking and Computing (MobiHoc). Google Scholar
- Nagpal, R. 1999. Organizing a global coordinate system from local information on an amorphous computer. In A.I. Memo 1666, MIT A.I. Laboratory.Google Scholar
- Newsome, J. and Song, D. 2003. Gem: Graph embedding for routing and datacentric storage in sensor networks without geographic information. In Proceedings of the 1st ACM Conference on Embedded Networked Sensor Systems. ACM Press. Google Scholar
- Niculescu, D. and Nath, B. 2003a. Dv based positioning in ad hoc networks. In J. Telecomm. Syst. 22, 1--4 (Jan.), 267--280.Google Scholar
- Niculescu, D. and Nath, B. 2003b. Trajectory based forwarding and its applications. In Proceedings of the 9th Annual International Conference on Mobile Computing and Networking. ACM Press, 260--272. Google Scholar
- Perkins, C. and Royer, E. M. 1999. Ad hoc on demand distance vector routing. In Proceedings of the 2nd IEEE Workshop on Mobile Computing Systems and Applications. Google Scholar
- Rao, A., Papadimitriou, C., Shenker, S., and Stoica, I. 2003. Geographic routing without location information. In Proceedings of the 9th Annual International Conference on Mobile Computing and Networking. ACM Press, 96--108. Google Scholar
- Seada, K., Helmy, A., and Govindan, R. 2004. On the effect of localization errors on geographic face routing in sensor networks. In Proceedings of the 3rd International Symposium on Information Processing in Sensor Networks. ACM Press, 71--80. Google Scholar
- Seada, K., Zuniga, M., Helmy, A., and Krishnamachari, B. 2004. Energy efficient forwarding strategies for geographic routing in lossy wireless sensor networks. In the 2nd ACM Conference on Embedded Networked Sensor Systems. Google Scholar
- Shang, Y., Ruml, W., Zhang, Y., and Fromherz, M. 2003. Localization from mere connectivity. In Proceedings of the 4th ACM International Symposium on Mobile Ad Hoc Networking and Computing (MobiHoc). ACM Press, 201--212. Google Scholar
- Tolle, G., Polastre, J., Szewczyk, R., Turner, N., Tu, K., Burgess, S., Gay, D., Buonadonna, P., Hong, W., Dawson, T., and Culler, D. 2005. A macroscope in the redwoods. In the 3rd ACM Conference on Embedded Networked Sensor Systems. ACM Press. Google Scholar
- Woo, A., Tong, T., and Culler, D. 2003. Taming the underlying challenges of reliable multihop routing in sensor networks. In the 1st ACM Conference on Embedded Networked Sensor Systems. Google Scholar
- Zhao, J. and Govindan, R. 2003. Understanding packet delivery performance in dense wireless sensor networks. In Proceedings of the 1st ACM Conference on Embedded Networked Sensor Systems. Google Scholar
- Zhou, H. and Singh, S. 2000. Content based multicast (cbm) in ad hoc networks. In Proceedings of the 1st ACM International Symposium on Mobile Ad Hoc Networking and Computing (MobiHoc). 51--60. Google Scholar
- Zuniga, M. and Krishnamachari, B. 2004. Analyzing the transitional region in low power wireless links. In Proceedings of the 1st IEEE Conference on Sensor and Ad Hoc Communications and Networks (SECON).Google Scholar
Index Terms
- Scalable logical coordinates framework for routing in wireless sensor networks
Recommendations
Mitigating attacks against virtual coordinate based routing in wireless sensor networks
WiSec '08: Proceedings of the first ACM conference on Wireless network securityVirtual coordinate system (VCS) based routing provides a practical, efficient and scalable means for point-to-point routing in wireless sensor networks. Several VCS-based routing protocols have been proposed in the last few years, all assuming that ...
Secure and robust virtual coordinate system in wireless sensor networks
Virtual Coordinate System (VCS)-based routing provides a practical, efficient, and scalable means for point-to-point routing in wireless sensor networks. Several VCS-based routing protocols have been proposed in the last few years, all assuming that ...
Localized routing with guaranteed delivery and a realistic physical layer in wireless sensor networks
Routing is the problem of sending a packet from a source node to a destination node in the network. Existing solutions for sensor networks assume a unit disk graph model, where messages between nodes are received correctly if and only if the distance ...
Comments