Power balanced coverage-time optimization for clustered wireless sensor networks

ABSTRACT

We consider a wireless sensor network in which sensors are grouped into clusters, each with its own cluster head (CH). Each CH collects data from sensors in its cluster and relays them to a sink node directly or through other CHs. The coverage time of the network is defined as the time until one of the CHs runs out of battery, resulting in an incomplete coverage of the sensing region. We study the maximization of coverage time by balancing the power consumption of different CHs. Using a Rayleigh fading channel model for inter-cluster communications, we provide optimal power allocation strategies that guarantee (in a probabilistic sense) an upper bound on the end-to-end (inter-CH) path reliability. Our allocation strategies account for the interaction between routing and clustering by considering the impacts of intra- and inter-cluster traffic at each CH. Two mechanisms are proposed for achieving balanced power consumption: the routing-aware optimal cluster planning and the clustering-aware optimal random relay. For both mechanisms, the problem is formulated as a signomial optimization, which can be efficiently solved using generalized geometric programming. Numerical examples and simulations are used to validate our analysis and study the performance of the proposed schemes.

REFERENCES

• 1: I. F. Akyildiz, W. Su, Y. Sankarasubramaniam, and E. Cayirci, "A survey on sensor networks," IEEE Communications Magazine, pp. 102--114, Aug. 2002.
• 2: J. M. Kahn , R. H. Katz , K. S. J. Pister, Next century challenges: mobile networking for “Smart Dust”, Proceedings of the 5th annual ACM/IEEE international conference on Mobile computing and networking, p.271-278, August 15-19, 1999, Seattle, Washington, United States [doi>10.1145/313451.313558]
• 3: D. J. Baker and A. Ephremides, "The architectural organization of a mobile radio network via a distributed algorithm," IEEE Transactions on Communications, vol. 29, no. 11, pp. 1694--1701, Nov. 1981.
• 4: A. Ephremides, J. E. Wieselthier, and D. J. Baker, "A design concept for reliable mobile radio networks with frequency hopping signaling," Proceedings of the IEEE, vol. 75, no. 1, pp. 56--73, 1987.
• 5: C. R. Lin and M. Gerla, "Adaptive clustering for mobile wireless networks," IEEE Journal on Selected Areas in Communications, vol. 15, pp. 1265--1275, Sep. 1997.
• 6: Mario Gerla , Jack Tzu-Chieh Tsai, Multicluster, mobile, multimedia radio network, Wireless Networks, v.1 n.3, p.255-265, 1995 [doi>10.1007/BF01200845]
• 7: Jie Wu , Hailan Li, On calculating connected dominating set for efficient routing in ad hoc wireless networks, Proceedings of the 3rd international workshop on Discrete algorithms and methods for mobile computing and communications, p.7-14, August 20-20, 1999, Seattle, Washington, United States [doi>10.1145/313239.313261]
• 8: Fabian Kuhn , Thomas Moscibroda , Roger Wattenhofer, Initializing newly deployed ad hoc and sensor 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.1023746]
• 9: P. J. Wan, K. M. Alzoubi, and O. Frieder, "Distributed construction of connected dominating set in wireless ad hoc networks," Proc. IEEE INFOCOM Conference, New York, June 23-27, 2002.
• 10: W. B. Heinzelman, A. P. Chandrakasan, and H. Balakrishnan, "An application-specific protocol architecture for wireless microsensor networks," IEEE Transactions on Wireless Communications, vol. 1, no. 4, pp. 660--670, Oct. 2002.
• 11: G. Gupta and M. Younis, "Load-balanced clustering of wireless sensor networks," in Proc. IEEE International Conference on Communications (ICC'03), vol. 3, pp. 1848--1852, May 2003.
• 12: Alan D. Amis , Ravi Prakash, Load-Balancing Clusters in Wireless Ad Hoc Networks, Proceedings of the 3rd IEEE Symposium on Application-Specific Systems and Software Engineering Technology (ASSET'00), p.25, March 24-25, 2000
• 13: A. D. Amis, R. Prakash, T. H. P. Vuong, and D. T. Huynh, "Max-min d-cluster formation in wireless ad hoc networks," in Proc. IEEE INFOCOM 2000 Conf., vol. 1, pp. 32--41, Mar. 2000.
• 14: Carla-Fabiana Chiasserini , Imrich Chlamtac , Paolo Monti , Antonio Nucci, An energy-efficient method for nodes assignment in cluster-based Ad Hoc networks, Wireless Networks, v.10 n.3, p.223-231, May 2004 [doi>10.1023/B:WINE.0000023857.83211.3c]
• 15: S. Bandyopadhyay, E. J. Coyle, "An energy efficient hierarchical clustering algorithm for wireless sensor networks," in Proc. IEEE INFOCOM 2003 Conference, vol. 3, pp. 1713--1723, Mar. 2003.
• 16: 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]
• 17: Thomas Moscibroda , Roger Wattenhofer, Maximizing the Lifetime of Dominating Sets, Proceedings of the 19th IEEE International Parallel and Distributed Processing Symposium (IPDPS'05) - Workshop 12, p.242.2, April 04-08, 2005 [doi>10.1109/IPDPS.2005.276]
• 18: Jianping Pan , Y. Thomas Hou , Lin Cai , Yi Shi , Sherman X. Shen, Topology control for wireless sensor networks, Proceedings of the 9th annual international conference on Mobile computing and networking, September 14-19, 2003, San Diego, CA, USA [doi>10.1145/938985.939015]
• 19: Seung-Jong Park , Ramanuja Vedantham , Raghupathy Sivakumar , Ian F. Akyildiz, A scalable approach for reliable downstream data delivery in wireless sensor networks, Proceedings of the 5th ACM international symposium on Mobile ad hoc networking and computing, May 24-26, 2004, Roppongi Hills, Tokyo, Japan [doi>10.1145/989459.989470]
• 20: C. F. Chiasserini and M. Garetto, "Modeling the performance of wireless sensor networks," in Proc. IEEE INFOCOM 2004 Conf., Mar. 2004.
• 21: Bevan Das , Raghupathy Sivakumar , Vaduvur Bharghavan, Routing in Ad Hoc Networks Using a Spine, Proceedings of the 6th International Conference on Computer Communications and Networks, p.34, September 22-25, 1997
• 22: J. G. Ecker, "Geometric programming: methods, computations and applications," Society of Industrial and Applied Mathematics, SIAM Review, vol. 22, no. 3, pp. 338--362, July 1980.
• 23: E. L. Peterson, "Geometric programming," Society of Industrial and Applied Mathematics, SIAM Review, vol. 18, no. 1, pp. 1--51, Jan. 1976.
• 24: Stephen Boyd , Lieven Vandenberghe, Convex Optimization, Cambridge University Press, New York, NY, 2004

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

Keywords:
clustering, coverage time, generalized geometric programming, sensor networks, signomial optimization, topology control