Siphon: overload traffic management using multi-radio virtual sinks in sensor networks

ABSTRACT

There is a critical need for new thinking regarding overload traffic management in sensor networks. It has now become clear that experimental sensor networks (e.g., mote networks) and their applications commonly experience periods of persistent congestion and high packet loss, and in some cases even congestion collapse. This significantly impacts application fidelity measured at the physical sinks, even under light to moderate traffic loads, and is a direct product of the funneling effect; that is, the many-to-one multi-hop traffic pattern that characterizes sensor network communications. Existing congestion control schemes are effective at mitigating congestion through rate control and packet drop mechanisms, but do so at the cost of significantly reducing application fidelity measured at the sinks. To address this problem we propose to exploit the availability of a small number of all wireless, multi-radio virtual sinks that can be randomly distributed or selectively placed across the sensor field. Virtual sinks are capable of siphoning off data events from regions of the sensor field that are beginning to show signs of high traffic load. In this paper, we present the design, implementation, and evaluation of Siphon, a set of fully distributed algorithms that support virtual sink discovery and selection, congestion detection, and traffic redirection in sensor networks. Siphon is based on a Stargate implementation of virtual sinks that uses a separate longer-range radio network (based on IEEE 802.11) to siphon events to one or more physical sinks, and a short-range mote radio to interact with the sensor field at siphon points. Results from analysis, simulation and an experimental 48 Mica2 mote testbed show that virtual sinks can scale mote networks by effectively managing growing traffic demands while minimizing the impact on application fidelity.

REFERENCES

• 1: Chalermek Intanagonwiwat , Ramesh Govindan , Deborah Estrin, Directed diffusion: a scalable and robust communication paradigm for sensor networks, Proceedings of the 6th annual international conference on Mobile computing and networking, p.56-67, August 06-11, 2000, Boston, Massachusetts, United States [doi>10.1145/345910.345920]
• 2: Chieh-Yih Wan , Shane B. Eisenman , Andrew T. Campbell, CODA: congestion detection and avoidance in sensor networks, Proceedings of the 1st international conference on Embedded networked sensor systems, November 05-07, 2003, Los Angeles, California, USA [doi>10.1145/958491.958523]
• 3: Chieh-Yih Wan , Andrew T. Campbell , Jon Crowcroft, A case for all-wireless, dual-radio virtual sinks, Proceedings of the 2nd international conference on Embedded networked sensor systems, November 03-05, 2004, Baltimore, MD, USA [doi>10.1145/1031495.1031529]
• 4: Anish Arora , Rajiv Ramnath , Emre Ertin , Prasun Sinha , Sandip Bapat , Vinayak Naik , Vinod Kulathumani , Hongwei Zhang , Hui Cao , Mukundan Sridharan , Santosh Kumar , Nick Seddon , Chris Anderson , Ted Herman , Nishank Trivedi , Chen Zhang , Mikhail Nesterenko , Romil Shah , Sandeep Kulkarni , Mahesh Aramugam , Limin Wang , Mohamed Gouda , Young-ri Choi , David Culler , Prabal Dutta , Cory Sharp , Gilman Tolle , Mike Grimmer , Bill Ferriera , Ken Parker, ExScal: Elements of an Extreme Scale Wireless Sensor Network, Proceedings of the 11th IEEE International Conference on Embedded and Real-Time Computing Systems and Applications (RTCSA'05), p.102-108, August 17-19, 2005 [doi>10.1109/RTCSA.2005.47]
• 5: Jerry Zhao , Ramesh Govindan, Understanding packet delivery performance in dense wireless sensor networks, Proceedings of the 1st international conference on Embedded networked sensor systems, November 05-07, 2003, Los Angeles, California, USA [doi>10.1145/958491.958493]
• 6: Yogesh Sankarasubramaniam , Özgür B. Akan , Ian F. Akyildiz, ESRT: event-to-sink reliable transport in wireless sensor networks, Proceedings of the 4th ACM international symposium on Mobile ad hoc networking & computing, June 01-03, 2003, Annapolis, Maryland, USA [doi>10.1145/778415.778437]
• 7: Bret Hull , Kyle Jamieson , Hari Balakrishnan, Mitigating congestion in wireless sensor networks, Proceedings of the 2nd international conference on Embedded networked sensor systems, November 03-05, 2004, Baltimore, MD, USA [doi>10.1145/1031495.1031512]
• 8: Sameer Tilak , Nael B. Abu-Ghazaleh , Wendi Heinzelman, Infrastructure tradeoffs for sensor networks, Proceedings of the 1st ACM international workshop on Wireless sensor networks and applications, September 28-28, 2002, Atlanta, Georgia, USA [doi>10.1145/570738.570746]
• 9: Alec Woo , David E. Culler, A transmission control scheme for media access in sensor networks, Proceedings of the 7th annual international conference on Mobile computing and networking, p.221-235, July 2001, Rome, Italy [doi>10.1145/381677.381699]
• 10: Eugene Shih , Paramvir Bahl , Michael J. Sinclair, Wake on wireless:: an event driven energy saving strategy for battery operated devices, Proceedings of the 8th annual international conference on Mobile computing and networking, September 23-28, 2002, Atlanta, Georgia, USA [doi>10.1145/570645.570666]
• 11: M. Yarvis, N. Kushalnagar, H. Singh, A. Rangarajan, Y. Liu, and S. Singh. Exploiting Heterogeneity in Sensor Networks. In Proc. of IEEE INFOCOM. Miami, FL, Mar 2005.
• 12: Feng Xue , P. R. Kumar, The number of neighbors needed for connectivity of wireless networks, Wireless Networks, v.10 n.2, p.169-181, March 2004 [doi>10.1023/B:WINE.0000013081.09837.c0]
• 13: Stargate datasheet. http://www.xbow.com.
• 14: Jason Hill , Robert Szewczyk , Alec Woo , Seth Hollar , David Culler , Kristofer Pister, System architecture directions for networked sensors, Proceedings of the ninth international conference on Architectural support for programming languages and operating systems, p.93-104, November 2000, Cambridge, Massachusetts, United States
• 15: Alec Woo , Terence Tong , David Culler, Taming the underlying challenges of reliable multihop routing in sensor networks, Proceedings of the 1st international conference on Embedded networked sensor systems, November 05-07, 2003, Los Angeles, California, USA [doi>10.1145/958491.958494]
• 16: Chipcon. http://www.chipcon.com.
• 17: Benjie Chen , Kyle Jamieson , Hari Balakrishnan , Robert Morris, Span: an energy-efficient coordination algorithm for topology maintenance in ad hoc wireless networks, Wireless Networks, v.8 n.5, p.481-494, September 2002 [doi>10.1023/A:1016542229220]
• 18: Tinyos homepage. http://webs.cs.berkeley.edu/tos/.
• 19: Tian He , Brian M. Blum , John A. Stankovic , Tarek Abdelzaher, AIDA: Adaptive application-independent data aggregation in wireless sensor networks, ACM Transactions on Embedded Computing Systems (TECS), v.3 n.2, p.426-457, May 2004 [doi>10.1145/993396.993406]
• 20: R. Murty, E. H. Qi, and M. Hazra. An Adaptive Approach to Wireless Network Performance Optimization. In Wireless World Research Forum (WWRF11 Meeting). Oslo, Norway, Jun 10-11 2004.
• 21: Anindya Basu , Brian Boshes , Sayandev Mukherjee , Sharad Ramanathan, Network deformation: traffic-aware algorithms for dynamically reducing end-to-end delay in multi-hop wireless networks, Proceedings of the 10th annual international conference on Mobile computing and networking, September 26-October 01, 2004, Philadelphia, PA, USA [doi>10.1145/1023720.1023731]
• 22: B. Liu, Z. Liu and D. Towsley. On the Capacity of Hybrid Wireless Networks In Proc. of IEEE INFOCOM. San Francisco, CA, Mar 30 - Apr 3, 2003.
• 23: Armstrong Project http://comet.columbia.edu/armstrong.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Wireless communication

General Terms:
Algorithms, Design, Experimentation

Keywords:
simulations, system design, testbeds