Omprakash Gnawali
Kyle Jamieson
ABSTRACT
This paper presents and evaluates two principles for wireless routing protocols. The first is datapath validation: data traffic quickly discovers and fixes routing inconsistencies. The second is adaptive beaconing: extending the Trickle algorithm to routing control traffic reduces route repair latency and sends fewer beacons.
We evaluate datapath validation and adaptive beaconing in CTP Noe, a sensor network tree collection protocol. We use 12 different testbeds ranging in size from 20--310 nodes, comprising seven platforms, and six different link layers, on both interference-free and interference-prone channels. In all cases, CTP Noe delivers > 90% of packets. Many experiments achieve 99.9%. Compared to standard beaconing, CTP Noe sends 73% fewer beacons while reducing topology repair latency by 99.8%. Finally, when using low-power link layers, CTP Noe has duty cycles of 3% while supporting aggregate loads of 30 packets/minute.
- Texas Instruments, CC1100 Data Sheet. http://focus.ti.com/lit/ds/symlink/cc1100.pdf, 2003.Google Scholar
- The MultiHopLQI protocol. http://www.tinyos.net/tinyos-2.x/tos/lib/net/lqi, 2009.Google Scholar
- G.-S. Ahn, E. Miluzzo, A. Campbell, S. Hong, and F. Cuomo. Funneling MAC: A Localized, Sink-Oriented MAC for Boosting Fidelity in Sensor Networks. In Proc. of the ACM SenSys Conf., pages 293--306, Boulder, CO, Nov. 2006. Google ScholarDigital Library
- M. Bathula, M. Ramezanali, I. Pradhan, N. Patel, J. Gotschall, and N. Sridhar. A sensor network system for measuring traffic in short-term construction work zones. In Proc. of DCOSS '09, pages 216--230, Berlin, Heidelberg, 2009. Springer-Verlag. Google ScholarDigital Library
- N. Burri, P. von Rickenbach, and R. Wattenhofer. Dozer: ultra-low power data gathering in sensor networks. In Proc. of the IPSN Conf., pages 450--459, New York, NY, 2007. Google ScholarDigital Library
- D. S. J. D. Couto, D. Aguayo, J. Bicket, and R. Morris. A High-Throughput Path Metric for Multi-Hop Wireless Routing. In Proc. of the ACM MobiCom Conf., San Diego, CA, Sept. 2003. Google ScholarDigital Library
- A. Dhananjay, H. Zhang, J. Li, and L. Subramanian. Practical, Distributed Channel Assignment and Routing in Dual-radio Mesh Networks. In Proc. of the ACM SIGCOMM Conf., Aug. 2009. Google ScholarDigital Library
- R. Draves, J. Padhye, and B. Zill. Comparison of routing metrics for static multi-hop wireless networks. In Proc. of the ACM SIGCOMM Conf., pages 133--144, Portland, OR, Aug. 2004. Google ScholarDigital Library
- C. T. Ee and R. Bajcsy. Congestion control and fairness for many-to-one routing in sensor networks. In Proc. of the ACM SenSys Conf., pages 148--161, Baltimore, MD, Nov. 2004. Google ScholarDigital Library
- R. Fonseca, O. Gnawali, K. Jamieson, S. Kim, P. Levis, and A. Woo. TEP 123: The Collection Tree Protocol, Aug. 2006.Google Scholar
- R. Fonseca, O. Gnawali, K. Jamieson, and P. Levis. Four Bit Wireless Link Estimation. In Hotnets-VI, Atlanta, GA, Nov. 2007.Google Scholar
- J. W. Hui and D. E. Culler. IP is dead, long live IP for wireless sensor networks. In Proc. of the SenSys Conf., pages 15--28, New York, NY, 2008. Google ScholarDigital Library
- B. Hull, K. Jamieson, and H. Balakrishnan. Mitigating congestion in wireless sensor networks. In Proc. of the ACM SenSys Conf., pages 134--147, Baltimore, MD, Nov. 2004. Google ScholarDigital Library
- S. Kim, R. Fonseca, P. Dutta, A. Tavakoli, D. Culler, P. Levis, S. Shenker, and I. Stoica. Flush: a reliable bulk transport protocol for multihop wireless networks. In Proc. of the ACM SenSys Conf., pages 351--365. ACM, 2007. Google ScholarDigital Library
- J. Ko, T. Gao, and A. Terzis. Empirical Study of a Medical Sensor Application in an Urban Emergency Department. In BodyNets '09: 4th Intl Conference on Body Area Networks. Google ScholarDigital Library
- K. Langendoen, A. Baggio, and O. Visser. Murphy loves potatoes: Experiences from a pilot sensor network deployment in precision agriculture. In 14th Int. Workshop on Parallel and Distributed Real-Time Systems (WPDRTS), pages 1--8, apr 2006.Google ScholarCross Ref
- P. Levis, N. Lee, M. Welsh, and D. Culler. TOSSIM: Simulating large wireless sensor networks of tinyos motes. pages 126--137, Los Angeles, CA, Nov. 2003.Google Scholar
- P. Levis, N. Patel, D. Culler, and S. Shenker. Trickle: A self-regulating algorithm for code maintenance and propagation in wireless sensor networks. In Proc. of the USENIX NSDI Conf., San Francisco, CA, Mar. 2004. Google ScholarDigital Library
- J. Li, C. Blake, D. S. D. Couto, H. I. Lee, and R. Morris. Capacity of Ad Hoc wireless networks. In Proc. of MobiCom, pages 61--69. ACM, 2001. Google ScholarDigital Library
- C. Lu, B. M. Blum, T. F. Abdelzaher, J. A. Stankovic, and T. He. RAP: A Real-Time Communication Architecture for Large-Scale Wireless Sensor Networks. In Proc. of the IEEE RTAS Symposium, San Jose, CA, September 2002. Google ScholarDigital Library
- A. Mainwaring, J. Polastre, R. Szewczyk, D. Culler, and J. Anderson. Wireless Sensor Networks for Habitat Monitoring. In Proceedings of the ACM International Workshop on Wireless Sensor Networks and Applications, Sept. 2002. Google ScholarDigital Library
- R. Musaloiu-E., C.-J. Liang, and A. Terzis. Koala: Ultra-low power data retrieval in wireless sensor networks. In Proc. of the International Conference on Information Processing in Sensor Networks (IPSN 2008), 2008. Google ScholarDigital Library
- D. Pei, X. Zhao, D. Massey, and L. Zhang. A study of bgp path vector route looping behavior. In ICDCS '04: Proceedings of the 24th International Conference on Distributed Computing Systems (ICDCS'04), pages 720--729, Washington, DC, USA, 2004. IEEE Computer Society. Google ScholarDigital Library
- C. Perkins and P. Bhagwat. Highly Dynamic Destination-Sequenced Distance-Vector Routing (DSDV) for Mobile Computers. Computer Comm. Review, October 1994. Google ScholarDigital Library
- J. Polastre, J. Hill, and D. Culler. Versatile low power media access for wireless sensor networks. In Proc. of the ACM SenSys Conf., pages 95--107, Baltimore, MD, Nov. 2004. Google ScholarDigital Library
- S. Rangwala, R. Gummadi, R. Govindan, and K. Psounis. Interference-aware fair rate control in wireless sensor networks. In Proc. of the ACM SIGCOMM Conf., pages 63--74, Pisa, Italy, Aug. 2006. Google ScholarDigital Library
- Y. Sankarasubramaniam, Özgür Akan, and I. Akyildiz. ESRT: Event-to-Sink Reliable Transport in Wireless Sensor Networks. In Proc. of the ACM Mobihoc Conf., pages 177--189, Annapolis, MD, June 2003. Google ScholarDigital Library
- T. Schoellhammer, B. Greenstein, and D. Estrin. Hyper: A routing protocol to support mobile users of sensor networks. Technical Report 2013, CENS, 2006.Google Scholar
- K. Srinivasan, M. Kazandjieva, S. Agarwal, and P. Levis. The beta-factor: Measuring wireless link burstiness. In Proceedings of the 6th ACM Conference on Embedded Networked Sensor Systems (SenSys), 2008. Google ScholarDigital Library
- F. Stann and J. Heidemann. RMST: Reliable Data Transport in Sensor Networks. In Proc. of the IEEE SNPA Workshop, pages 102--112, Anchorage, AK, May 2003.Google ScholarCross Ref
- G. Tolle, J. Polastre, R. Szewczyk, D. E. Culler, N. Turner, K. Tu, S. Burgess, T. Dawson, P. Buonadonna, D. Gay, and W. Hong. A macroscope in the redwoods. In Proc. of the ACM SenSys Conf., pages 51--63, San Diego, CA, Nov. 2005. Google ScholarDigital Library
- C.-Y. Wan, A. Campbell, and L. Krishnamurthy. PSFQ: a Reliable Transport Protocol for Wireless Sensor Networks. In Proc. of the ACM WSNA Workshop, pages 1--11, Atlanta, GA, 2002. Google ScholarDigital Library
- C.-Y. Wan, S. Eisenman, and A. Campbell. CODA: Congestion Detection and Avoidance in Sensor Networks. In Proc. ACM SenSys, pages 266--279, Nov. 2003. Google ScholarDigital Library
- C. Y. Wan, S. Eisenman, A. Campbell, and J. Crowcroft. Siphon: Overload Traffic Management using Multi-Radio Virtual Sinks. In Proc. of the ACM SenSys Conf., pages 116--129, San Diego, CA, Nov. 2005. Google ScholarDigital Library
- G. Werner-Allen, S. Dawson-Haggerty, and M. Welsh. Lance: Optimizing High-Resolution Data Collection in Wireless Sensor Networks. In Proc. of the ACM SenSys Conf., Nov. 2008. Google ScholarDigital Library
- G. Werner-Allen, K. Lorincz, J. Johnson, J. Lees, and M. Welsh. Fidelity and Yield in a Volcano Monitoring Sensor Network. In USENIX Symposium on Operating Systems Design and Implementation, Seattle, WA, Nov. 2006. Google ScholarDigital Library
- A. Woo and D. E. Culler. A transmission control scheme for media access in sensor networks. In Proceedings of the seventh annual international conference on Mobile computing and networking, Rome, Italy, July 2001. Google ScholarDigital Library
- A. Woo, T. Tong, and D. Culler. Taming the underlying challenges of reliable multihop routing in sensor networks. In Proc. ACM SenSys, pages 14--27, Los Angeles, CA, Nov. 2003. Google ScholarDigital Library
- H. Zhang, A. Arora, Y. R. Choi, and M. Gouda. Reliable bursty convergecast in wireless sensor networks. Computer Communications, 30(13):2560--2576, Dec. 2007. Google ScholarDigital Library
- H. Zhang, A. Arora, and P. Sinha. Learn on the fly: Data-driven link estimation and routing in sensor network backbones. In Proc. IEEE INFOCOM, Barcelona, Spain, Apr. 2006.Google ScholarCross Ref
Index Terms
- Collection tree protocol
Recommendations
Fixed node assisted collection tree protocol for mobile wireless sensor networks
The collection tree protocol (CTP) is widely used in static wireless sensor network applications. With the increasing deployment of mobile WSNs, the performance of this scheme in mobile scenarios becomes extremely important. The motivation in using ...
EZRP: an enhanced zone-based routing protocol for ad-hoc networks: Research Articles
Performance Analysis and Enhancements of Wireless NetworksIn mobile ad-hoc networks (MANETs), the nodes intercommunicate through single-hop and multi-hop paths in a peer-to-peer fashion. Intermediate nodes between two pairs of communication nodes act as routers. Thus, the nodes operate both as hosts and ...
On-demand multicast routing protocol in multihop wireless mobile networks
An ad hoc network is a dynamically reconfigurable wireless network with no fixed infrastructure or central administration. Each host is mobile and must act as a router. Routing and multicasting protocols in ad hoc networks are faced with the challenge ...
Comments