Interference-aware fair rate control in wireless sensor networks

ABSTRACT

In a wireless sensor network of N nodes transmitting data to a single base station, possibly over multiple hops, what distributed mechanisms should be implemented in order to dynamically allocate fair and efficient transmission rates to each node? Our interferenceaware fair rate control (IFRC) detects incipient congestion at a node by monitoring the average queue length, communicates congestion state to exactly the set of potential interferers using a novel low-overhead congestion sharing mechanism, and converges to a fair and efficient rate using an AIMD control law. We evaluate IFRC extensively on a 40-node wireless sensor network testbed. IFRC achieves a fair and efficient rate allocation that is within 20-40% of the optimal fair rate allocation on some network topologies. Its rate adaptation mechanism is highly effective: we did not observe a single instance of queue overflow in our many experiments. Finally, IFRC can be extended easily to support situations where only a subset of the nodes transmit, where the network has multiple base stations, or where nodes are assigned different transmission weights.

REFERENCES

• 1: Hari Balakrishnan , Hariharan S. Rahul , Srinivasan Seshan, An integrated congestion management architecture for Internet hosts, Proceedings of the conference on Applications, technologies, architectures, and protocols for computer communication, p.175-187, August 30-September 03, 1999, Cambridge, Massachusetts, United States
• 2: Pierpaolo Bergamo , Shadnaz Asgari , Hanbiao Wang , Daniela Maniezzo , Len Yip , Ralph E. Hudson , Kung Yao , Deborah Estrin, Collaborative Sensor Networking Towards Real-Time Acoustical Beamforming in Free-Space and Limited Reverberance, IEEE Transactions on Mobile Computing, v.3 n.3, p.211-224, July 2004 [doi>10.1109/TMC.2004.17]
• 3: Vaduvur Bharghavan , Alan Demers , Scott Shenker , Lixia Zhang, MACAW: a media access protocol for wireless LAN's, Proceedings of the conference on Communications architectures, protocols and applications, p.212-225, August 31-September 02, 1994, London, United Kingdom
• 4: Cheng Tien Ee and Ruzena Bajcsy. Congestion Control and Fairness for Many-to-One Routing in Sensor Networks. In SenSys '04.
• 5: A. Demers , S. Keshav , S. Shenker, Analysis and simulation of a fair queueing algorithm, Symposium proceedings on Communications architectures & protocols, p.1-12, September 25-27, 1989, Austin, Texas, United States
• 6: Sally Floyd , Van Jacobson, Random early detection gateways for congestion avoidance, IEEE/ACM Transactions on Networking (TON), v.1 n.4, p.397-413, Aug. 1993 [doi>10.1109/90.251892]
• 7: R. Govindan, E. Kohler, D. Estrin, F. Bian, K. Chintalapudi, O. Gnawali, S. Rangwala, R. Gummadi, and T. Stathopoulos. Tenet: An Architecture for Tiered Embedded Networks. CENS Technical Report 56, 2005.
• 8: B. Greenstein, A. Pesterev, C. Mar, E. Kohler, J. Judy, S. Farschi, and D. Estrin. Collecting High-Rate Data Over low-rate Sensor Network Radios. CENS Technical Report 55, 2005.
• 9: G. Holland and N. Vaidya. Impact of Routing and Link Layers on TCP Performance in Mobile Ad-Hoc Networks. In IEEE WCNC '99.
• 10: Jonathan W. Hui , David Culler, The dynamic behavior of a data dissemination protocol for network programming at scale, Proceedings of the 2nd international conference on Embedded networked sensor systems, November 03-05, 2004, Baltimore, MD, USA [doi>10.1145/1031495.1031506]
• 11: 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]
• 12: 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]
• 13: V. Jacobson, Congestion avoidance and control, ACM SIGCOMM Computer Communication Review, v.18 n.4, p.314-329, August 1988
• 14: Kamal Jain , Jitendra Padhye , Venkata N. Padmanabhan , Lili Qiu, Impact of interference on multi-hop wireless network performance, Proceedings of the 9th annual international conference on Mobile computing and networking, September 14-19, 2003, San Diego, CA, USA [doi>10.1145/938985.938993]
• 15: Jinyang Li , Charles Blake , Douglas S.J. De Couto , Hu Imm Lee , Robert Morris, Capacity of Ad Hoc wireless networks, Proceedings of the 7th annual international conference on Mobile computing and networking, p.61-69, July 2001, Rome, Italy [doi>10.1145/381677.381684]
• 16: D. Kim, C.-K. Toh, and Y. Choi. TCP-BuS: Improving TCP Performance in Wireless Ad-Hoc Networks. In ICC '00.
• 17: V. Kottapalli, A. Kiremidjian, J. P. Lynch, E. Carryer, T. Kenny, K. Law, and Y. Lei. A Two-Tier Wireless Sensor Network Architecture for Structural Health Monitoring. In Proc. of SPIE's 2003.
• 18: Srisankar Kunniyur , R. Srikant, Analysis and design of an adaptive virtual queue (AVQ) algorithm for active queue management, Proceedings of the 2001 conference on Applications, technologies, architectures, and protocols for computer communications, p.123-134, August 2001, San Diego, California, United States
• 19: P. Levis, N. Patel, D. Culler, and S. Shenker. Trickle: A Self-Regulating Algo-rithm for Code Propagation and Maintenance in Wireless Sensor Networks In NSDI '04.
• 20: P. E. McKenney. Stochastic Fairness Queuing. In INFOCOMM '90.
• 21: K. Mechitov, W. Y. Kim, G. Agha, and T. Nagayama. High-Frequency Dis-tributed Sensing for Structure Monitoring. In INSS '04.
• 22: J. Paek, K. Chintalapudi, J. Cafferey, R. Govindan, and S. Masri. A Wireless Sensor Network for Structural Health Monitoring: Performance and experi-ence. In EmNetS '05.
• 23: Mohammad Rahimi , Rick Baer , Obimdinachi I. Iroezi , Juan C. Garcia , Jay Warrior , Deborah Estrin , Mani Srivastava, Cyclops: in situ image sensing and interpretation in wireless sensor networks, Proceedings of the 3rd international conference on Embedded networked sensor systems, November 02-04, 2005, San Diego, California, USA [doi>10.1145/1098918.1098939]
• 24: 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]
• 25: Prasun Sinha , Narayanan Venkitaraman , Raghupathy Sivakumar , Vaduvur Bharghavan, WTCP: a reliable transport protocol for wireless wide-area networks, Proceedings of the 5th annual ACM/IEEE international conference on Mobile computing and networking, p.231-241, August 15-19, 1999, Seattle, Washington, United States [doi>10.1145/313451.313541]
• 26: A. Sridharan and B. Krishnamachari. Max-Min Fair Collision-Free Scheduling for Wireless Sensor Networks. In Workshop on Multihop Wireless Networks (MWN'04), IPCCC.
• 27: F. Stann and J. Heidemann. Rmst: Reliable Data Transport in Sensor Networks. In SNPA '03.
• 28: Robert Szewczyk , Alan Mainwaring , Joseph Polastre , John Anderson , David Culler, An analysis of a large scale habitat monitoring application, Proceedings of the 2nd international conference on Embedded networked sensor systems, November 03-05, 2004, Baltimore, MD, USA [doi>10.1145/1031495.1031521]
• 29: Chieh-Yih Wan , Andrew T. Campbell , Lakshman Krishnamurthy, PSFQ: a reliable transport protocol for wireless 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.570740]
• 30: 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]
• 31: 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]
• 32: 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]
• 33: Kaixin Xu , Mario Gerla , Lantao Qi , Yantai Shu, Enhancing TCP fairness in ad hoc wireless networks using neighborhood RED, Proceedings of the 9th annual international conference on Mobile computing and networking, September 14-19, 2003, San Diego, CA, USA [doi>10.1145/938985.938988]
• 34: W. Ye, J. Heidemann, and D. Estrin. An Energy-Efficient MAC Protocol for Wireless Sensor Networks, In Infocom '02.
• 35: Hongwei Zhang , Anish Arora , Young-ri Choi , Mohamed G. Gouda, Reliable bursty convergecast in wireless sensor networks, Proceedings of the 6th ACM international symposium on Mobile ad hoc networking and computing, May 25-27, 2005, Urbana-Champaign, IL, USA [doi>10.1145/1062689.1062724]

INDEX TERMS

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

Additional Classification:
  C. Computer Systems Organization
  C.3 SPECIAL-PURPOSE AND APPLICATION-BASED SYSTEMS
      Subjects: Real-time and embedded systems

General Terms:
Algorithms, Design

Keywords:
ControlRate control, IFRC, congestion, fairness, sensor network, wireless