Opportunity-Based Topology Control in Wireless Sensor Networks

Abstract

Topology control is an effective method to improve the energy efficiency of wireless sensor networks (WSNs). Traditional approaches are based on the assumption that a pair of nodes is either "connected" or "disconnected." These approaches are called connectivity-based topology control. In real environments, however, there are many intermittently connected wireless links called lossy links. Taking a succeeded lossy link as an advantage, we are able to construct more energy-efficient topologies. Toward this end, we propose a novel opportunity-based topology control. We show that opportunity-based topology control is a problem of NP-hard. To address this problem in a practical way, we design a fully distributed algorithm called CONREAP based on reliability theory. We prove that CONREAP has a guaranteed performance. The worst running time is O(\vert E\vert ), where E is the link set of the original topology, and the space requirement for individual nodes is O(d), where d is the node degree. To evaluate the performance of CONREAP, we design and implement a prototype system consisting of 50 Berkeley Mica2 motes. We also conducted comprehensive simulations. Experimental results show that compared with the connectivity-based topology control algorithms, CONREAP can improve the energy efficiency of a network up to six times.