Alec Woo
ABSTRACT
The dynamic and lossy nature of wireless communication poses major challenges to reliable, self-organizing multihop networks. These non-ideal characteristics are more problematic with the primitive, low-power radio transceivers found in sensor networks, and raise new issues that routing protocols must address. Link connectivity statistics should be captured dynamically through an efficient yet adaptive link estimator and routing decisions should exploit such connectivity statistics to achieve reliability. Link status and routing information must be maintained in a neighborhood table with constant space regardless of cell density. We study and evaluate link estimator, neighborhood table management, and reliable routing protocol techniques. We focus on a many-to-one, periodic data collection workload. We narrow the design space through evaluations on large-scale, high-level simulations to 50-node, in-depth empirical experiments. The most effective solution uses a simple time averaged EWMA estimator, frequency based table management, and cost-based routing.
- B. Albrightson, J. Garcia-Luna-Aceves, and J. Boyle. EIGRP-a fast routing protocol based on distance vectors. In Proceedings of NetworldInterop, May 1994.]]Google Scholar
- B. Chen, K. Jamieson, H. Balakrishnan, and R. Morris. Span: An energy-efficient coordination algorithm for topology maintenance in ad hoc wireless networks. In International Conference on Mobile Computing and Networking (MobiCom 2001), pages 85--96, Rome, Italy, July 2001.]] Google ScholarDigital Library
- Y. Choi, M. G. Gouda, M. C. Kim, and A. Arora. The mote connectivity protocol. Technical Report TR-03-08, Department of Computer Sciences, The University of Texas at Austin, 2003.]]Google ScholarCross Ref
- D. D. Couto, D. Aguayo, B. Chambers, and R. Morris. Performance of multihop wireless. First Workshop on Hot Topics in Networks (HotNets-I), October 2002.]]Google Scholar
- M. Datar, A. Gionis, P. Indyk, and R. Motwani. Maintaining stream statistics over sliding windows. In 13th Annual ACM-SIAM Symposium on Discrete Algorithms, 2002.]] Google ScholarDigital Library
- E. D. Demaine, A. Lopez-Ortiz, and J. I. Munro. Frequency estimation of internet packet streams with limited space. In Proceedings of the 10th Annual European Symposium on Algorithms ESA 2002, pages 348--360, September 2002.]] Google ScholarDigital Library
- C. Estan and G. Varghese. New directions in traffic measurement and accounting. In ACM SIGCOMM Internet Measurement Workshop, 2001.]] Google ScholarDigital Library
- D. Ganesan, B. Krishnamachari, A. Woo, D. Culler, D. Estrin, and S. Wicker. Complex behavior at scale: An experimental study of low-power wireless sensor networks. In Technical Report UCLACSD-TR 02-0013, February 2002.]]Google Scholar
- P. G. Gibbons and Y. Matias. New sampling- based summary statistics for improving approximate query answers. In Proceedings of ACM SIGMOD International Conference on Management of Data, pages 311--342, June 1998.]] Google ScholarDigital Library
- G. Manku and R. Motwani. Approximate frequency counts over data streams. In Proceedings of the 28th International Conference on Very Large Data Bases, August 2002.]]Google ScholarDigital Library
- C. Hedrick. Routing information protocol. In RFC 1058, June 1988.]] Google ScholarDigital Library
- C. Hedrick. An introduction to IGRP. In Rutgers - The State University of New Jersey Technical Publication, Laboratory for Computer Science, August 1991.]]Google Scholar
- J. Hill and D. Culler. Mica: a wireless platform for deeply embedded networks. IEEE Micro, 22(6):12--24, novdec 2002.]] Google ScholarDigital Library
- J. Hill and D. Culler. A wireless-embedded architecture for system level optimization. In UC Berkeley Technical Report, 2002.]]Google Scholar
- J. Hill, R. Szewczyk, A. Woo, S. Hollar, D. Culler, and K. Pister. System architecture directions for networked sensors. In the Ninth international Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS 2000), pages 93--104, November 2000.]] Google ScholarDigital Library
- C. Intanagonwiwat, R. Govindan, and D. Estrin. Directed diffusion: a scalable and robust communication paradigm for sensor networks. In Proceedings of the International Conference on Mobile Computing and Networking Mobicom, pages 56--67, August 2000.]] Google ScholarDigital Library
- D. Johnson and D. Maltz. Dynamic source routing in ad hoc wireless networks. In Mobile Computing, pages 153--181. Kluwer Academic Publishers, 1996.]]Google ScholarCross Ref
- C. E. Perkins and P. Bhagwat. Highly dynamic destination-sequenced distance-vector routing (dsdv) for mobile computers. In Proceedings of the ACM SIGCOMM, pages 234--244, August 1994.]] Google ScholarDigital Library
- C. E. Perkins and E. M. Royer. Ad hoc on-demand distance-vector (aodv) routing. In Proceedings of the 2nd IEEE Workshop on Mobile Computing Systems and Applications, 1999.]] Google ScholarDigital Library
- R. Ramanathan and R. Rosales-Hain. Topology control of multihop wireless networks using transmit power adjustment. In IEEE Infocom, March 2000.]]Google ScholarCross Ref
- E. Shih, P. Bahl, and M. J. Sinclair. Wake on wireless:: an event driven energy saving strategy for battery operated devices. In Proceedings of the eighth annual international conference on Mobile computing and networking, pages 160--171. ACM Press, 2002.]] Google ScholarDigital Library
- A. Woo and D. Culler. A transmission control scheme for media access in sensor networks. In International Conference on Mobile Computing and Networking (MobiCom 2001), page 221, Rome, Italy, July 2001.]] Google ScholarDigital Library
- A. Woo and D. Culler. Evaluation of efficient link reliability estimators for low-power wireless networks. Technical Report UCBCSD-03-1270, U.C. Berkeley Computer Science Division, September 2003.]]Google Scholar
- M. D. Yarvis, W. S. Conner, L. Krishnamurthy, A. Mainwaring, J. Chhabra, and B. Elliott. Real-world experiences with an interactive ad hoc sensor network. In International Conference on Parallel Processing Workshops, August 2002.]] Google ScholarDigital Library
Index Terms
- Taming the underlying challenges of reliable multihop routing in sensor networks
Recommendations
Reliable data transmission in mobile ad hoc sensor networks
In this paper, we introduce a new routing scheme for mobile ad hoc sensor networks, which effectively transports the information from source to sink by curbing the energy requirements, both at node and system level. The proposed approach, termed as ...
Routing efficiency in wireless sensor-actor networks considering semi-automated architecture
Wireless networks have become increasingly popular and advances in wireless communications and electronics have enabled the development of different kind of networks such as Mobile Ad-hoc Networks (MANETs), Wireless Sensor Networks (WSNs) and Wireless ...
Towards more reliable and secure source routing in mobile ad hoc and sensor networks
Routing protocols in mobile ad hoc and sensor networks discover a multi-hop route between source and destination nodes. A highly reliable path is an important component for enhancing the security of communication. This paper presents RAS: a Reliable ...
Comments