NCG: Partitioning Working Sensors Based on Node Coverage in Wireless Sensor Networks

Abstract

How to prolong sensor network lifetime while maintaining a sufficient sensing area has been one of the most important research issues in wireless sensor networks. In general, sensors in the connectivity group are within sensing range of each other, and data collected by sensors in a connectivity group are assumed to be similar. In this paper, we present a novel approach to partition sensors based on connectivity in wireless sensor networks, called Node Coverage Grouping (NCG), which is proved to be a NP-hard problem. We also propose a heuristic algorithm of NCG with the time complexity of O(n^3). In addition, we present two approaches of the avoidance of blind period for NCG, called periodic probing (P-NCG) and nextturn probing (NT-NCG).The experimental results showed that NCG outperforms the Lightweight Deployment-Aware Scheduling (LDAS) and the Probing Environment and Adaptive Sleeping (PEAS) methods in terms of the number of living nodes, the number of working nodes, and the coverage with the proceeding of system lifetime. In addition, by applying probing mechanisms on NCG to avoid blind period, P-NCG and NT-NCG would have higher average coverage than LDAS and PEAS. In conclusion, NT-NCG works the best among these five approaches in terms of coverage and system lifetime on WSN when unexpected node failure is concerned.