Polynomial time algorithm for solving k-coverage problem in wireless sensor networks

Abstract

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.

Keywords

• wireless sensor network
• k-coverage problem
• growing disk
• adjacent border
• polynomial time algo-rithm