A case for hybrid sensor networks

ABSTRACT

In this paper, we investigate the use of limited infrastructure, in the form of wires, for improving the energy efficiency of a wireless sensor network. We call such a sensor network--a wireless sensor network with a limited infrastructural support--a hybrid sensor network. The wires act as short cuts to bring down the average hop count of the network, resulting in a reduced energy dissipation per node. Our results indicate that adding a few wires to a wireless sensor network can not only reduce the average energy expenditure per sensor node, but also the nonuniformity in the energy expenditure across the sensor nodes.

REFERENCES

• 1: Alan Mainwaring , David Culler , Joseph Polastre , Robert Szewczyk , John Anderson, Wireless sensor networks for habitat monitoring, Proceedings of the 1st ACM international workshop on Wireless sensor networks and applications, September 28-28, 2002, Atlanta, Georgia, USA [doi>10.1145/570738.570751]
• 2: Alberto Cerpa , Jeremy Elson , Michael Hamilton , Jerry Zhao , Deborah Estrin , Lewis Girod, Habitat monitoring: application driver for wireless communications technology, Workshop on Data communication in Latin America and the Caribbean, p.20-41, April 2001, San Jose, Costa Rica [doi>10.1145/371626.371720]
• 3: A. Kansal et al., "Sensing uncertainty reduction using low complexity actuation," Center for Embedded Networked Sensing (CENS), Univ. California, Los Angeles, Feb. 2004, Tech. Rep..
• 4: M. Rahimi et al., "Adaptive sampling for environmental robotics," Center for Embedded Networked Sensing (CENS), Univ. California, Los Angeles, Nov. 2003, Tech. Rep.
• 5: Gaurav Sharma , Ravi Mazumdar, Hybrid sensor networks: a small world, 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.1062736]
• 6: P. Gupta and P. R. Kumar, "The capacity of wireless networks," IEEE Trans. Inf. Theory, vol. IT-46, no. 2, pp. 388-404, Mar. 2000.
• 7: D. J. Watts and S. H. Strogatz, "Collective dynamics of small-world networks," Nature, pp. 440-442, 1998.
• 8: A. Helmy, "Small Worlds in Wireless Networks," IEEE Commun. Lett., vol. 7, no. 10, pp. 490-492, Oct. 2003.
• 9: Jon Kleinberg, The small-world phenomenon: an algorithm perspective, Proceedings of the thirty-second annual ACM symposium on Theory of computing, p.163-170, May 21-23, 2000, Portland, Oregon, United States [doi>10.1145/335305.335325]
• 10: Rohan Chitradurga , Ahmed Helmy, Analysis of Wired Short Cuts in Wireless Sensor Networks, Proceedings of the The IEEE/ACS International Conference on Pervasive Services, p.167-176, July 19-23, 2004 [doi>10.1109/ICPS.2004.10]
• 11: Wendi Rabiner Heinzelman , Anantha Chandrakasan , Hari Balakrishnan, Energy-Efficient Communication Protocol for Wireless Microsensor Networks, Proceedings of the 33rd Hawaii International Conference on System Sciences-Volume 8, p.8020, January 04-07, 2000
• 12: Wendi Rabiner Heinzelman , Joanna Kulik , Hari Balakrishnan, Adaptive protocols for information dissemination in wireless sensor networks, Proceedings of the 5th annual ACM/IEEE international conference on Mobile computing and networking, p.174-185, August 15-19, 1999, Seattle, Washington, United States [doi>10.1145/313451.313529]
• 13: 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]
• 14: Seema Bandyopadhyay , Edward J. Coyle, Minimizing communication costs in hierarchically-clustered networks of wireless sensors, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.44 n.1, p.1-16, 15 January 2004 [doi>10.1016/S1389-1286(03)00320-7]
• 15: Vivek P. Mhatre , Catherine Rosenberg , Daniel Kofman , Ravi Mazumdar , Ness Shroff, A Minimum Cost Heterogeneous Sensor Network with a Lifetime Constraint, IEEE Transactions on Mobile Computing, v.4 n.1, p.4-15, January 2005 [doi>10.1109/TMC.2005.2]
• 16: V. Mhatre and C. Rosenberg, "Design guidelines for wireless sensor networks: Communication, clustering, and aggregation," Ad Hoc Networks J., vol. 2, pp. 45-63, 2004.
• 17: B. Liu, Z. Liu, and D. Towsley, "On the capacity of hybrid wireless networks," in IEEE INFOCOM, 2003.
• 18: S. R. Kulkarni and P. Viswanath, "Throughput scaling in heterogeneous networks," in IEEE ISIT, 2003.
• 19: M. Yarvis et al., "Exploiting heterogeneity in sensor networks," in IEEE INFOCOM, Mar. 2005.
• 20: Prosenjit Bose , Pat Morin , Ivan Stojmenović , Jorge Urrutia, Routing with guaranteed delivery in ad hoc wireless networks, Proceedings of the 3rd international workshop on Discrete algorithms and methods for mobile computing and communications, p.48-55, August 20-20, 1999, Seattle, Washington, United States [doi>10.1145/313239.313282]
• 21: Brad Karp , H. T. Kung, GPSR: greedy perimeter stateless routing for wireless networks, Proceedings of the 6th annual international conference on Mobile computing and networking, p.243-254, August 06-11, 2000, Boston, Massachusetts, United States [doi>10.1145/345910.345953]
• 22: Ananth Rao , Sylvia Ratnasamy , Christos Papadimitriou , Scott Shenker , Ion Stoica, Geographic routing without location information, Proceedings of the 9th annual international conference on Mobile computing and networking, September 14-19, 2003, San Diego, CA, USA [doi>10.1145/938985.938996]
• 23: Jyh-Han Lin , Jeffrey Scott Vitter, e-approximations with minimum packing constraint violation (extended abstract), Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, p.771-782, May 04-06, 1992, Victoria, British Columbia, Canada [doi>10.1145/129712.129787]
• 24: Sanjeev Arora , Prabhakar Raghavan , Satish Rao, Approximation schemes for Euclidean k-medians and related problems, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.106-113, May 24-26, 1998, Dallas, Texas, United States [doi>10.1145/276698.276718]
• 25: M. Franceschetti and R. Meester, "Navigation in small world networks, a scale-free continuum model," Preprint, Dept. ECE, Univ. California, San Diego, 2004.

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.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.2 Network Protocols
      C.2.3 Network Operations
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Performance attributes; Design studies

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory

General Terms:
Algorithms, Design, Management, Performance

Keywords:
energy dissipation, graph theory, lifetime, routing, sensor networks, small world networks, system design, trade-offs