Maximum connectivity and maximum lifetime energy-aware routing for wireless sensor networks

In this paper, we consider the energy-aware routing algorithm that explicitly takes into account the connectivity of the sensor networks. In typical sensor network deployment, some nodes may be more important than other nodes because the death of these nodes cause the network disintegration. The network disintegration causes early termination of information delivery. To overcome this problem, we propose a routing algorithm called keep connect algorithm that explicitly considers the connectivity of the network while making the routing decision. The algorithm can be used along with the existing routing algorithms. When doing the routing decision, the keep connect algorithm embeds the importance of the nodes in the routing cost. The importance of a node is quantified by how severe the remaining network becomes disconnected/disintegrated when that particular node dies. In particular, the importance of a node is characterized by the algebraic connectivity of the remaining graph. Compared to the existing routing algorithms, the proposed method achieves up to two times improvement in terms of the network lifetime and the number of successfully delivered packets in the special grid network. In random network, the proposed algorithm achieves 20% improvement of network lifetime, 30% less energy per packet, and 33% more successfully delivered packets.