Polynomial time algorithm for solving k-coverage problem in wireless sensor networks - Qi WANG; Zheng’an XIAO; Huaixing WANG (Dianxin kexue)
How to solve the k-coverage problem,which was divided into worst-case and best-case,inside the two-dimensional target area in wireless sensor networks was explored,and a polynomial time algorithm for solving this problem was put forward.In this algorithm,a series of definitions and theorems were proposed based on the geometric graph of growing disks,and the k-coverage problem was transformed into one of finding a series of adjacent borders.The simulation results show that the algorithm could compute the optimal k-breach path and k-support path in polynomial time,so as to avoid or select the network coverage reasonably.