DOI: 10.3724/SP.J.1004.2008.01157

Acta Automatica Sinica (自动化学报) 2008/34:9 PP.1157-1162

Efficient Cover Set Selection in Wireless Sensor Networks

The effectiveness of a cluster-based distributed sensor network, to a large extent, depends on the coverage provided by the sensor nodes. To activate only the necessary number of sensor nodes at any particular moment is an efficient way to save the overall energy. However, this is an NP-complete problem because of the high-density deployment of wireless sensor networks.In this paper, a novel searching algorithm based on improved NSGA-II (elitist nondominated sorting genetic algorithm) is proposed to select an optimal cover set. In contrast to the binary detection model used in the previous work, a probabilistic detection model is adopted in combination with the detection error range and coverage threshold.With the full network coverage being guaranteed, a number of nodes are made into dormancy mode to save energy.The circulated combination and delete operators are proposed to enhance the search capability. Extensive simulation results are presented to demonstrate the effectiveness of our approach.

Key words:Wireless sensor networks (WSN), cover set, detection model, improved NSGA-II

ReleaseDate:2014-07-21 14:27:30

Funds:Supported by National Natural Science Foundation of China (60602061)and National High Technology Research and Development Program ofChina (863 Program) (2006AA01Z413)

1 Akyildiz I F, Su W L, Sankarasubramaniam Y, Cayirci E. A survey on sensor networks.IEEE Communications Magazine,2002,40(8):102-114

2 Wang L, Xiao Y. A survey of energy-efficient scheduling mechanisms in sensor networks.Mobile Networks and Applications,2006,11(5):723-740

3 Meguerdichian S, Koushanfar F, Potkonjak M, Srivastava M B. Coverage problems in wireless Ad-Hoc sensor network. In: Proceedings of the 20th International Annual Joint Conference of the IEEE Computer and Communications Societies. Anchorage, USA: IEEE, 2001. 1380-1387

4 Slijepcevic S, Potkonjak M. Power efficient organization of wireless sensor networks. In: Proceedings of the IEEE Conference on Communications. Helsinki, Finland: IEEE, 2001. 472-476

5 Tian D, Georganas N D. A coverage-preserving node scheduling scheme for large wireless sensor networks. In: Proceedings of the 1st ACM International Workshop on Wireless Sensor Networks and Applications. Atlanta, USA: ACM, 2002. 32-41

6 Zhang H H, Hou J C. Maintaining sensing coverage and connectivity in large sensor networks.Ad-Hoc and Sensor Wireless Networks,2005,1(1-2):89-124

7 Keshavarzian A, Lee H, Venkatraman L. Wakeup scheduling in wireless sensor networks. In: Proceedings of the 7th ACM International Symposium on Mobile Ad Hoc Networking and Computing. Florence, Italy: ACM, 2006. 322-333

8 Wang B, Chua K C, Srinivasan V, Wang W. Information coverage in randomly deployed wireless sensor networks.IEEE Transactions on Wireless Communications, 2007,6(8): 2994-3004

9 Chakrabarty K, Iyengar S S, Qi H R, Cho E. Grid coverage for surveillance and target location in distributed sensor networks.IEEE Transactions on Computers,2002,51(12):1448-1453

10 Ye F, Zhong G, Lu S W, Zhang L X. PEAS: a robust energy conserving protocol for long-lived sensor networks. In: Proceedings of the 23rd International Conference on Distributed Computing Systems. Providence, USA: IEEE, 2003. 28-37

11 Younis O, Fahmy S. Heed: a hybrid, energy-efficient, distributed clustering approach for Ad-Hoc sensor networks.IEEE Transactions on Mobile Computing,2004,3(4):366-379

12 Heinzelman W R, Chandrakasan A, Balakrishnan H. Energy-efficient communication protocol for wireless microsensor networks. In: Proceedings of the 33rd Annual Hawaii International Conference on System Sciences. Hawaii, USA: IEEE, 2000. 3005-3014

13 Lindsey S, Raghavendra C S. PEGASIS: power-efficient gathering in sensor information systems. In: Proceedings of the IEEE Aerospace Conference. Montana, USA: IEEE, 2002. 1125-1130

14 Zou Y, Chakrabarty K. Sensor deployment and target localization based on virtual forces. In: Proceedings of the 22nd International Annual Joint Conference of the IEEE Computer and Communications Societies. San Francisco, USA: IEEE, 2003. 1293-1303

15 Deb K, Pratap A, Agarwal S, Meyarivan T. A fast and elitist multiobjective genetic algorithm: NSGA-II.IEEE Transactions on Evolutionary Computation,2002,6(2):182-197

16 Srinivas N, Deb K. Multiobjective optimization using nondominated sorting in genetic algorithms.Evolutionary Computation,1994,2(3):221-248