minimizing interference in ad hoc and sensor networks
Reducing interference is one of the main challenges in wireless communication, and particularly in ad hoc networks. The amount of interference experienced by a node v corresponds to the number of other nodes whose transmission range covers v . At the cost of communication links being dropped, interference can be reduced by decreasing the node's transmission power. In this paper, we study the problem of minimizing the average interference while still maintaining desired network properties, such as connectivity, point-to-point connections, or multicast trees. In particular, we present a greedy algorithm that computes an O(log n) approximation to the interference problem with connectivity requirement, where n is the number of nodes in the network. We then show the algorithm to be asymptotically optimal by proving a corresponding ?(log n) lower bound that holds even in a more restricted interference model. Finally, we show how the algorithm can be generalized towards solving the interference problem for network properties that can be formulated as a 0-1 proper function.
interference sensor networks network challenge wireless communication communication ad hoc networks cost links power paper connection multicast trees greedy algorithm algorithm log approximation requirements optimality lower bound model general functional point primal-dual algorithms ad-hoc