The Worst-Case Capacity of Wireless Sensor Networks

The key application scenario of wireless sensor networks is data gathering: sensor nodes transmit data, possibly in a multi-hop fashion, to an information sink. The performance of sensor networks is thus characterized by the rate at which information can be aggregated to the sink. In this paper, we derive the first scaling laws describing the achievable rate in worst-case, i.e. arbitrarily deployed, sensor networks. We show that in the physical model of wireless communication and for a large number of practically important functions, a sustainable rate of Theta(1/log² n) can be achieved in every network, even when nodes are positioned in a worst-case manner. In contrast, we show that the best possible rate in the protocol model is Theta(1/n), which establishes an exponential gap between these two standard models of wireless communication. Furthermore, our worst-case capacity result almost matches the rate of Theta(1/log n) that can be achieved in randomly deployed networks. The high rate is made possible by employing non-linear power assignment at nodes and by exploiting SINR-effects. Finally, our algorithm also improves the best known bounds on the scheduling complexity in wireless networks.