Abstract：A new coverage optimization problem named disjoint set k-cover for fusion-based coverage of WSN is investigated in this paper where sensor nodes are assumed using a fusion-based collective probabilistic sensor model.First,the problem is formulated as a fusion-based coverage game and then the game is proved as a potential game.So that the optimal solution is a pure Nash equilibrium.Second,we present the conditions that determine the independence of coverage utility among sensor nodes.Furthermore,two distributed algorithms only based on local information are proposed and proven to be convergent to pure Nash equlibria.Finally,experimental results show that Nash equilibria can provide a near-optimal and well-balanced solution to the problem.
李劲, 岳昆, 刘惟一. 基于融合的无线传感器网络k-集覆盖的分布式算法[J]. 电子学报, 2013, 41(4): 659-665.
LI Jin, YUE Kun, LIU Wei-yi. Distributed Set k-Cover Algorithms for Fusion-Based Coverage in Wireless Sensor Networks. Chinese Journal of Electronics, 2013, 41(4): 659-665.
[1] Bang Wang.Coverage Control in Sensor Networks[M].London:Springer-Verlag,2010. [2] 凡高娟,王汝传,黄海平,等.基于容忍覆盖区域的无线传感器网络节点调度算法[J].电子学 报,2011,39(1):89-94. FAN Gao-juan,WANG Ru-chuan,HUANG Hai-ping,et al.Tolerable coverage area based node scheduling algorithm in wireless sensor networks[J].Acta Electronica Sin ica,2011,39(1):89-94.(in Chinese) [3] 任丰原,黄海宁,林闯.无线传感器网络[J].软件学报,2003,14(7):1282-1290. REN Feng-yuan,HUANG Hai-ning,LIN Chuang..Wireless sensor networks[J].Journal of Software,2003,14(7):1282-1290.(in Chinese) [4] S Slijepcevic,M Potkonjak.Power efficient organization of wireless sensor networ ks[A].Proceedings of the IEEE International Conference on Communications [C] .Helsinki:IEEE Computer Society Press,2001.472-476. [5] ZoëAbrams,Ashish Goel,Serge A Plotkin.Set k-cover algorithms for energy effic ient monitoring in wireless sensor networks[A].Proceedings of the Third Intern ational Symposium on Information Processing in Sensor Networks[C].California:A CM Press,2004.424-432. [6] Amol Deshpande,Samir Khuller,Azarakhsh Malekian,Mohammed Toossi.Energy efficient monitoring in sensor networks[J].Algorithmica,2011,59(1):94-114. [7] Xin Ai,Vikram Srinivasan,Chen-Khong Tham.Optimality and complexity of pure Nash equilibria in the coverage game[J].IEEE Journal on Selected Areas in Communic ations ,2008,26(7):1170-1182. [8] Nadeem Ahmed,Salil S Kanhere,Sanjay Jha.Probabilistic coverage in wireless senso r networks[A].Proceedings of 30th Annual IEEE Conference on Local Computer Net works[C].Sydney:IEEE Computer Society Press,2005.672-681. [9] Mohamed Hefeeda,Hossein Ahmadi.A probabilistic coverage protocol for wireless se nsor networks[A].Proceedings of the IEEE International Conference on Network P rotocols[C].Beijing:IEEE Computer Society Press,2007.41-50. [10] 何欣,桂小林.基于概率感知覆盖的无线传感器网络节点优化部署方案[J].通信学报,2010, (9A):1-8. HE Xin,GUI Xiao-lin.Probabilistic disc model based optimal node deployment sche me to target coverage in wireless sensor networks[J].Journal on Communications ,2010,(9A):1-8.(in Chinese) [11] 孟凡治,王换招,何晖.基于联合感知模型的无线传感器网络连通性覆盖协议[J].电子学报, 2011,39 (4):772-779. MENG Fan-zhi,WANG Huan-zhao,HE Hui.Connected coverage protocol using cooperati ve sensing model for wireless sensor networks[J].Acta Electronica Sinica,2011, 39(4):772-779.(in Chinese) [12] Wei Wang,Vikram Srinivasan,Kee Chaing Chua,Bang Wang.Energy-efficient coverage for target detection in wireless sensor networks[A].Proceedings of the 6th Int ernational Conference on Information Processing in Sensor Networks [C].Massach usetts ,USA:ACM Press 2007.313-322. [13] Guoliang Xing,Rui Tan,Benyuan Liu,Jianping Wang,Xiaohua Jia,Chih-Wei Yi.Data fu sion improves the coverage of wireless sensor networks[A].Proceedings of the 1 5th Annual International Conference on Mobile Computing and Networking [C].Bei jing:ACM Press,2009.157-168. [14] Satoru Fujishige.Submodular Functions and Optimization (Second Edition)[M].Ams terdam:Elsevier,2005. [15] Fudenberg D,J Tirole.Game Theory[M].Cambridge,MA:MIT Press,1991. [16] D Monderer,L Shapley.Potential games[J].Games and Economic Behavior,1996,14:12 4-143. [17] Renita Machado,Sirin Tekinay.A survey of game-theoretic approaches in wireless sensor networks[J].Computer Networks,2008,52(16):3047-3061. [18] Jason R Marden,Gürdal Arslan,Jeff S Shamma.Cooperative control and potential ga mes[J].IEEE Transactions on Systems,Man and Cybernetics,2009,39(6):1393-1407. [19] Ozan Candogan,Ishai Menache,Asuman E Ozdaglar,Pablo A Parrilo.Near-optimal powe r control in wireless networks:A potential game approach[A].Proceedings of the 29th IEEE International Conference on Computer Communications (INFOCOM)[C].Sa n Diego,CA,USA:IEEE Computer Society Press,2010.1954-1962. [20] Alex Fabrikant,Christos H Papadimitriou,Kunal Talwar.The complexity of pure Nash equilibria[A].Proceedings of the 36th Annual ACM Symposium on Theory of Compu ting[C].Chicago,USA:ACM Press,2004.604-612. [21] Christos H Papadimitriou.How easy is local search[J].Journal of Computer and S ystem Sciences,1988,37(2):79-100.
2013, Vol. 41 
