The worst-case capacity of wireless sensor networks

ABSTRACT

The key application scenario of wireless sensor networks is data gathering sensor nodes transmit data, possibly in a multi-hop fashion, to an information sink. The performance of sensor networks is thus characterized by the rate at which information can be aggregated to the sink. In this paper, we derive the first scaling laws describing the achievable rate in worst-case i.e.arbitrarily deployed,sensor networks. We show that in the physical model of wireless communication and for a large number of practically important functions, a sustainable rate of Ω(1 / log² n) can be achieved in every network even when nodes are positioned in a worst-case manner. In contrast, we show that the best possible rate in the protocol model is Θ(1 /n), which establishes an exponential gap between these two standard models of wireless communication. Furthermore, our worst-case capacity result almost matches the rate of Θ(1 / log n) that can be achieved in randomly deployed networks. The high rate is made possible by employing non-linear power assignment at nodes and by exploiting SINR-effects. Finally,our algorithm also improves the best known bounds on the scheduling complexity in wireless networks.

REFERENCES

• 1: R.J. Barton and R. Zheng. Order-Optimal Data Aggregation in Wireless Sensor Networks Using Cooperative Time-Reversal Communication. In Proceedings of the 40th Conference on Information Sciences and Systems (CISS)pages 1050--1055, 2006.
• 2: Arnab Chakrabarti , Ashutosh Sabharwal , Behnaam Aazhang, Multi-hop communication is order-optimal for homogeneous sensor networks, Proceedings of the third international symposium on Information processing in sensor networks, April 26-27, 2004, Berkeley, California, USA [doi>10.1145/984622.984649]
• 3: R. Cristescu, B. Beferull-Lozano, and M. Vetterli. On Network Correlated Data Gathering. In Proceedings of the 23th Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM) 2004.
• 4: Enrique J. Duarte-Melo , Mingyan Liu, Data-gathering wireless sensor networks: organization and capacity, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.43 n.4, p.519-537, 15 November 2003 [doi>10.1016/S1389-1286(03)00357-8]
• 5: T. ElBatt and A. Ephremides. Joint Scheduling and Power Control for Wireless Ad-hoc Networks. In Proceedings of the 21th Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM) 2002.
• 6: M. Fussen, R. Wattenhofer, and A. Zollinger. Interference Arises at the Receiver. In Proc.of theInternational Conference on Wireless Networks, Communications, and Mobile Computing (WirelessCom) June 2005.
• 7: Jie Gao , Leonidas J. Guibas , John Hershberger , Li Zhang, Fractionally cascaded information in a sensor network, Proceedings of the third international symposium on Information processing in sensor networks, April 26-27, 2004, Berkeley, California, USA [doi>10.1145/984622.984668]
• 8: A. Giridhar and P.R. Kumar. Computing and Communicating Functions over Sensor Networks. IEEE Journal on Selected Areas in Communications 23(4):755--764, 2005.
• 9: A. Giridhar and P.R. Kumar. Towards a Theory of In-Network Computation in Wireless Sensor Networks. IEEE Communications Magazine 44(4), 2006.
• 10: Ashish Goel , Deborah Estrin, Simultaneous optimization for concave costs: single sink aggregation or single source buy-at-bulk, Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, January 12-14, 2003, Baltimore, Maryland
• 11: P.K. Gopala and H.E. Gamal. On the Scaling Laws of Modal Wireless Sensor Networks. In Proceedings of the 23rd Annual Joint Conference of the IEEE Computer Communications Societies (INFOCOM) 2004.
• 12: P. Gupta and P.R. Kumar. The Capacity of Wireless Networks.IEEE Trans. Information Theory 46(2):388--404, 2000.
• 13: Martin Haenggi, Routing in Ad Hoc Networks-A Wireless Perspective, Proceedings of the First International Conference on Broadband Networks (BROADNETS'04), p.652-660, October 25-29, 2004 [doi>10.1109/BROADNETS.2004.75]
• 14: Qiang-Sheng Hua , Francis C. M. Lau, The scheduling and energy complexity of strong connectivity in ultra-wideband networks, Proceedings of the 9th ACM international symposium on Modeling analysis and simulation of wireless and mobile systems, October 02-06, 2006, Terromolinos, Spain [doi>10.1145/1164717.1164767]
• 15: Lujun Jia , Guolong Lin , Guevara Noubir , Rajmohan Rajaraman , Ravi Sundaram, Universal approximations for TSP, Steiner tree, and set cover, Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, May 22-24, 2005, Baltimore, MD, USA [doi>10.1145/1060590.1060649]
• 16: Sachin Katti , Hariharan Rahul , Wenjun Hu , Dina Katabi , Muriel Médard , Jon Crowcroft, XORs in the air: practical wireless network coding, Proceedings of the 2006 conference on Applications, technologies, architectures, and protocols for computer communications, September 11-15, 2006, Pisa, Italy
• 17: Murali Kodialam , Thyaga Nandagopal, Characterizing achievable rates in multi-hop wireless networks: the joint routing and scheduling problem, Proceedings of the 9th annual international conference on Mobile computing and networking, September 14-19, 2003, San Diego, CA, USA [doi>10.1145/938985.938991]
• 18: V. S. Anil Kumar , Madhav V. Marathe , Srinivasan Parthasarathy , Aravind Srinivasan, Algorithmic aspects of capacity in wireless networks, Proceedings of the 2005 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, June 06-10, 2005, Banff, Alberta, Canada
• 19: D. Marco, E.J. Duarte-Melo, M. Liu, and D.L. Neuhoff. On the Many-to-One Transport Capacity of a Dense Wireless Sensor Network and the Compressibility of its Data. In Proc. of the 2nd International Workshop on Information Processing in Sensor Networks (IPSN) 2003.
• 20: Urbashi Mitra , Ashutosh Sabharwal, Complexity constrained sensor networks: achievable rates for two relay networks and generalizations, Proceedings of the third international symposium on Information processing in sensor networks, April 26-27, 2004, Berkeley, California, USA [doi>10.1145/984622.984667]
• 21: T. Moscibroda and R. Wattenhofer. The Complexity of Connectivity in Wireless Networks. In Proc. of the 25th IEEE INFOCOM 2006.
• 22: T. Moscibroda, R. Wattenhofer, and Y. Weber. Protocol Design Beyond Graph-based Models. In Proceedings of the 5th ACM SIGCOMM Workshop on Hot Topics in Networks (HotNets) 2006.
• 23: Thomas Moscibroda , Roger Wattenhofer , Aaron Zollinger, Topology control meets SINR: the scheduling complexity of arbitrary topologies, Proceedings of the 7th ACM international symposium on Mobile ad hoc networking and computing, May 22-25, 2006, Florence, Italy [doi>10.1145/1132905.1132939]
• 24: Pascal von Rickenbach , Roger Wattenhofer, Gathering correlated data in sensor networks, Proceedings of the 2004 joint workshop on Foundations of mobile computing, October 01-01, 2004, Philadelphia, PA, USA [doi>10.1145/1022630.1022640]
• 25: L. Ying,R. Srikant, and G.E. Dullerud. Distributed Symmetric Function Computation in Noisy Wireless Sensor Networks with Binary Data. In Proc. of the 4th Symposium on Modeling and Optimization in Mobile, Ad Hoc and Wireless Networks (WiOPT)2006.

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, Theory

Keywords:
capacity, data gathering, scheduling complexity