Low Information Redundancy Based Node Partition Protocols for Wireless Sensor Networks

Coverage is one of the fundamental measurements of quality in wireless sensor networks. In order to prolong the network lifetime while maintaining coverage, many node partition algorithms have been developed. In this article, we model coverage problem by a set coverage problem. Based on the density of information, the optimal node partitions are investigated by solving an ILP problem. An intersection point method (IPM) is introduced to reduce the number of variables in ILP to O(km) where m is the number of deployed sensors; k is the number of neighbors. Even though the ILP model can give an approximately optimal solution for generating a minimum cover set. It cannot be used in a distributed scenario. Based on the Voronoi Diagram we present a distributed partition algorithm that constructs minimum node partitions by merging voronoi cells. The simulation results show that the IPM based ILP coverage model can deal with extremely large areas and improve the ILP performance by reducing the number of variables and constraints. The voronoi based distributed partition algorithm can give approximate optimal results as given by the IPM based ILP solution. Both the flexibility and accuracy of our algorithms show the potential to be used in scheduling and duty circle algorithms.