Asymptotically Optimal Data Dissemination in Multichannel Wireless Sensor Networks: Single Radios Suffice

We analyze the performance limits of data dissemination with multichannel, single radio sensors under random packet loss. 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 Dijkstra´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 multihop cluster chains. For these topologies, we derive the structure of policies that achieve an asymptotically optimal average delay, in networks with large number of nodes. Our analysis reveals that a single radio in each node suffices to achieve performance gain directly proportional to the total number of channels available. Through simulation, we show that the derived policies perform close to optimal even for networks with small and moderate numbers of nodes and can be implemented with limited overhead.