Interference arises at the receiver

Energy consumption in general and interference in particular being among the most critical issues in wireless networks, this paper introduces an explicit definition of interference, based on the number of other nodes by which a given network node can be disturbed. With this definition we show that there exist instances of sensor networks in which no topology control algorithm - aiming at interference reduction by having nodes restrict their transmission power levels - can construct a valid data gathering network with interference less than logarithmic in the number of network nodes n. In a second part of the paper we introduce the nearest component connector (NCC) algorithm, which asymptotically matches this lower bound, guaranteeing to build a valid topology with interference in O(log n) in any given sensor network. Finally the paper compares NCC to other previously proposed data gathering structures in average-case networks.