Optimal placement and routing strategies for resilient two-tiered sensor networks

摘要

In hierarchical sensor networks using relay nodes, sensor nodes are arranged in clusters and higher powered relay nodes can be used as cluster heads. The lifetime of such a network is determined primarily by the lifetime of the relay nodes. In this paper, we propose two new integer linear programs (ILPs) formulations for optimal data gathering, which maximize the lifetime of the upper tier relay node network. Unlike most previous approaches considered in the literature, our formulations can generate optimal solutions under the non-flow-splitting model. Experimental results demonstrate that our approach can significantly extend network lifetime, compared to traditional routing schemes, for the non-flow-splitting model. The lifetime can be further enhanced by periodic updates of the routing strategy based on the residual energy at each relay node. The proposed rescheduling scheme can be used to handle single or multiple relay node failures. We have also presented a very simple and straightforward algorithm for the placement of relay nodes. The placement algorithm guarantees that all the sensor nodes can communicate with at least one relay node and that the relay node network is at least 2-connected. This means that failure of a single relay node will not disconnect the network, and data may be routed around the failed node. The worst case performance of the placement algorithm is bounded by a constant with respect to any optimum placement algorithm.