Topology control and channel assignment in lossy wireless sensor networks

In wireless sensor networks (WSNs), a significant amount of packets are lost when transmitted over wireless links, leading to unnecessary energy expenditure. This lossy property of a link can be described by the packet reception ratio (PRR) over it. In the literature, it was shown that the PRR of a link is a non-decreasing function of its signal to interference-plus-noise ratio (SINR), which indicates that the PRR can be improved by either enhancing the received power or reducing the interference-plus-noise level. On the other hand, a number of topology control algorithms and channel assignment algorithms have been presented for WSNs to reduce interference. However, most of them simply use the number of interfering nodes to describe the level of interference, which is inaccurate thus cannot guarantee high PRR. In this paper, we propose a joint design of topology control and channel assignment for lossy WSNs, aiming at improving the PRR of each link in the network. We first construct a maximum PRR spanning tree, then adjust the transmitting power and channel of sensor nodes to further improve the PRR of links on the tree. This way, packet retransmission due to lossy links is minimized, which leads to performance improvement in terms of network throughput, energy efficiency and end-to-end packet delay. We formulate the joint design into an optimization problem and prove its NP-hardness. We then present heuristic algorithms to give practical solutions for the problem. We have carried out extensive simulations and the results show that network performance can be significantly improved by using the topology generated by our algorithms compared to the topologies generated by other schemes under the same traffic demand.