Near-Optimal Data Dissemination Policies for Multi-Channel, Single Radio Wireless Sensor Networks - 02/02/2007

Weiyao Xiao

We analyze the performance limits of data dissemination with multi-channel, single radio sensors. We formulate the problem of minimizing the average delay of data dissemination as a stochastic shortest path problem and show that, for an arbitrary topology network, an optimal control policy can be found in a finite number of steps, using value iteration or Dijsktra's algorithm. However, the computational complexity of this solution is generally prohibitive. We thus focus on two special classes of network topologies of practical interest, namely single-hop clusters and multi-hop cluster trees. For these topologies, we derive the structure of policies that achieve an average delay within a factor $1+\epsilon$ of the optimal average delay, in networks with large number of nodes. Through simulation, we show that these policies perform close to optimal even for networks with small and moderate numbers of nodes. Our analysis and simulations reveal that multi-channel data dissemination policies lead to a drastic reduction in the average delay, up to a factor as large as the total number of channels available, even though each node can communicate over only one channel at any point of time. Finally, we present the foundations of a methodology, based on extreme value theory, allowing the implementation of our near-optimal dissemination policies with minimal overhead.