AVERAGE INTERFERENCE MINIMIZATION UNDER THE PROTOCOL MODEL IN WIRELESS SENSOR NETWORKS*

摘要

Reducing interference is one of the main challenges in wireless communication. How to minimize interference through network topology control in wireless sensor networks is a well-known open algorithmic problem. In this paper, we answer the question of how to minimize the average interference when a node is receiving a message. We adopt the protocol interference model, which defines the interference range of a node to be a constant times larger than its transmission range. We study the problem for nodes arbitrarily deployed in one-dimensional (1D) and two-dimensional (2D) regions respectively. For 1D networks, we propose a fast polynomial-time exact algorithm that can compute the minimum average interference. For 2D networks, we give a proof that the maximum interference can be bounded while minimizing the average interference. The bound is only related to the distances between nodes but not the network size. Based on the bound, we propose the first exact algorithm to compute the minimum average interference in 2D networks. Optimal topologies with the minimum average interference can be constructed through traceback in both 1D and 2D networks.