Power conservation for strongly connected topology control in wireless sensor network

ABSTRACT

Topology control is one of the most elementary topics in wireless sensor networks. Typically, most of the research only considered the bidirectional communication and symmetric weighted communication model, while the real wireless world contains not only bidirectional but also unidirectional communication links and asymmetric weighted communication model. In this paper, we present two heuristics for the minimum power topology control problem on general model, i.e., given a set of sensors in the Euclidean plane and a transmission power threshold for each directed pair of sensors, to find a power assignment for each sensor to achieve a strong connectivity with minimum total transmission power. Extensive results in simulation evaluate the efficiency of the proposed algorithms.

REFERENCES

• 1: Xiuzhen Cheng , Bhagirath Narahari , Rahul Simha , Maggie Xiaoyan Cheng , Dan Liu, Strong Minimum Energy Topology in Wireless Sensor Networks: NP-Completeness and Heuristics, IEEE Transactions on Mobile Computing, v.2 n.3, p.248-256, July-September 2003 [doi>10.1109/TMC.2003.1233530]
• 2: Jian Ma , Min Gao , Qian Zhang , Lionel M. Ni, Energy-Efficient Localized Topology Control Algorithms in IEEE 802.15.4-Based Sensor Networks, IEEE Transactions on Parallel and Distributed Systems, v.18 n.5, p.711-720, May 2007 [doi>10.1109/TPDS.2007.1025]
• 3: Xiaowen Liu , Martin Haenggi, Toward Quasiregular Sensor Networks: Topology Control Algorithms for Improved Energy Efficiency, IEEE Transactions on Parallel and Distributed Systems, v.17 n.9, p.975-986, September 2006 [doi>10.1109/TPDS.2006.130]
• 4: Tommaso Melodia, Dario Pompili, and Ian F. Akyildiz. 2005. On the Interdependence of the Distributed Topology Control and Geographical Routing in Ad Hoc and Sensor Networks. IEEE Journal on Selected Areas in Communications. 23, 3 (March 2005), 520--532. DOI= http://dx.doi.org/10.1109/JSAC.2004.842557
• 5: Errol L. Lloyd , Rui Liu , Madhav V. Marathe , Ram Ramanathan , S. S. Ravi, Algorithmic aspects of topology control problems for ad hoc networks, Proceedings of the 3rd ACM international symposium on Mobile ad hoc networking & computing, June 09-11, 2002, Lausanne, Switzerland [doi>10.1145/513800.513816]
• 6: Andrea E. F. Clementi , Paolo Penna , Riccardo Silvestri, Hardness Results for the Power Range Assignmet Problem in Packet Radio Networks, Proceedings of the Third International Workshop on Approximation Algorithms for Combinatorial Optimization Problems: Randomization, Approximation, and Combinatorial Algorithms and Techniques, p.197-208, August 08-11, 1999
• 7: W. T. Chen, and N. F. Huang. 1989. The Strongly Connecting Problem on Multihop Packet Radio Networks. IEEE Trans. Comm. 37, 3(March 1989), 293--295.
• 8: Xiuzhen Cheng , Min Ding , David Hongwei Du , Xiaohua Jia, Virtual backbone construction in multihop ad hoc wireless networks: Research Articles, Wireless Communications & Mobile Computing, v.6 n.2, p.183-190, March 2006 [doi>10.1002/wcm.v6:2]
• 9: Deying Li , Xiaohua Jia , Hongwei Du, QoS topology control for nonhomogenous ad hoc wireless networks, EURASIP Journal on Wireless Communications and Networking, v.2006 n.2, p.43-43, April 2006 [doi>10.1155/WCN/2006/82417]
• 10: Xiaohua Jia, Deying Li, and D. Du. 2004. QoS Topology Control in Ad Hoc Wireless Networks. Twenty-third Annual Joint Conference of the IEEE Computer and Communications Societies (Hong Kong, March 7-11, 2004). INFOCOM'04. 2, 1264--1272.
• 11: Maggie X. Cheng , Mihaela Cardei , Jianhua Sun , Xiaochun Cheng , Lusheng Wang , Yinfeng Xu , Ding-Zhu Du, Topology Control of Ad Hoc Wireless Networks for Energy Efficiency, IEEE Transactions on Computers, v.53 n.12, p.1629-1635, December 2004 [doi>10.1109/TC.2004.121]
• 12: R. Ramanathan, and R. Rosales-Hain. 2000. Topology Control of Multihop Wireless Networks Using Transmit Power Adjustment. Nineteenth Annual Joint Conference of the IEEE Computer and Communications Societies (Israel, March 26-30, 2000). INFOCOM'00. 2, 404--413. DOI= http://dx.doi.org/10.1109/INFCOM.2000.832213
• 13: V. Rodoplu, and T. Meng. 1999. Minimum Energy Mobile Wireless Networks. IEEE J. Selected Areas in Comm. 17, 8 (August 1999), 1333--1344.
• 14: L. Hu. 1993. Topology Control for multihop packet radio Networks. IEEE Trans. on Communications. 41, 10 (Oct. 1993), 1474--1481. DOI= http://dx.doi.org/10.1109/26.237882

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

Keywords:
greedy algorithm, minimum power topology control, power assignment, power threshold, wireless sensor networks