Order-optimal data collection in wireless sensor networks: Delay and capacity

Data collection is one of the most important functions provided by wireless sensor networks. In this paper, we study theoretical limitations of data collection and data aggregation in terms of delay and capacity for a wireless sensor network where n sensors are randomly deployed. We consider different communication scenarios (single sink or multiple sinks, regularly-deployed or randomly-deployed sinks, with or without aggregation) under protocol interference model. For each scenario, we first propose a new collection/aggregation method and analyze its performance in terms of delay and capacity, then theoretically prove that our method can achieve the optimal order (i.e., its performance is within a constant factor of the optimal). Particularly, with a single sink, the capacity of data collection is in order of Theta(W) where W is the fixed data-rate on individual links. With k sinks, the capacity of data collection is increased to Theta(kW) when k=O(n/log n) or Theta(n/log n) when k=Omega(n/log n). If each sensor can aggregate its receiving packets into a single packet to send, the capacity of data collection with a single sink is also increased to Theta(n/log nW).