Optimal stochastic routing in low duty-cycled wireless sensor networks

ABSTRACT

We study a routing problem in wireless sensor networks where sensors are duty-cycled. When sensors alternate between on and off modes, delay encountered in packet delivery due to loss in connectivity can become a critical problem, and how to achieve delay-optimality is non-trivial. For instance, when sensors' sleep schedules are uncoordinated, it is not immediately clear whether a sensor with data to transmit should wait for a particular neighbor (who may be on a short route) to become available/active before transmission, or simply transmit to an available/active neighbor to avoid waiting. To obtain some insight into this problem, in this paper we formulate the above problem as an optimal stochastic routing problem, where the randomness in the system comes from random duty cycling, as well as the uncertainty in packet transmission due to channel variations. Similar framework has been used in prior work which results in optimal routing algorithms that are sample-path dependent, also referred to as opportunistic in some cases. We show such algorithms are no longer optimal when duty cycling is introduced. We first develop and analyze an optimal centralized stochastic routing algorithm for randomly duty-cycled wireless sensor network, and then simplify the algorithm when local sleep/wake states of neighbors are available. We further develop a distributed algorithm utilizing local sleep/wake states of neighbors which performs better than some existing distributed algorithms such as ExOR.

REFERENCES

• 1: S. Biswas and R. Morris. Opportunistic routing in multi-hop wireless networks. In Workshop on Hot Topics in Networks (HotNets-II), Nov. 2003.
• 2: Sanjit Biswas , Robert Morris, ExOR: opportunistic multi-hop routing for wireless networks, Proceedings of the 2005 conference on Applications, technologies, architectures, and protocols for computer communications, August 22-26, 2005, Philadelphia, Pennsylvania, USA
• 3: D. Ferrara, L. Galluccio, A. Leonardi, G. Morabito, and S. Palazzo. Macro: An integrated mac/routing protocol for geographic forwarding in wireless sensor networks. In Joint Conference of the IEEE Computer and Communications Societies (INFOCOM), Mar. 2005.
• 4: D. Ganesan, B. Krishnamachari, A. Woo, D. Culler, D. Estrin, and S. Wicker. Complex behavior at scale: An experimental study of low-power wireless sensor networks. Technical report ucla/csd-tr 02--0013, Feb. 2002.
• 5: Chalermek Intanagonwiwat , Ramesh Govindan , Deborah Estrin , John Heidemann , Fabio Silva, Directed diffusion for wireless sensor networking, IEEE/ACM Transactions on Networking (TON), v.11 n.1, p.2-16, February 2003 [doi>10.1109/TNET.2002.808417]
• 6: D. B. Johnson and D. A. Maltz. Dynamic source routing in ad hoc wireless networks. Mobile computing, Kluwer Academic Publishers, 1996.
• 7: D. Kim. Low Duty-Cycled Wireless Sensor Networks: Connectivity and Opportunistic Routing. PhD thesis, Univ. of Michigan, 2008.
• 8: C. Lott and D. Teneketzis. Stochastic routing in ad-hoc networks. IEEE Transactions on Automatic Control, 51(1), 2006.
• 9: T. Melodia, D. Pompili, and I. F. Akyildiz. Optimal local topology knowledge for energy efficient geographical routing in sensor networks. In Joint Conference of the IEEE Computer and Communications Societies (INFOCOM), Mar. 2004.
• 10: Shree Murthy , J. J. Garcia-Luna-Aceves, An efficient routing protocol for wireless networks, Mobile Networks and Applications, v.1 n.2, p.183-197, Oct. 1996 [doi>10.1007/BF01193336]
• 11: Charles E. Perkins , Pravin Bhagwat, Highly dynamic Destination-Sequenced Distance-Vector routing (DSDV) for mobile computers, Proceedings of the conference on Communications architectures, protocols and applications, p.234-244, August 31-September 02, 1994, London, United Kingdom
• 12: Karim Seada , Marco Zuniga , Ahmed Helmy , Bhaskar Krishnamachari, Energy-efficient forwarding strategies for geographic routing in lossy wireless sensor networks, Proceedings of the 2nd international conference on Embedded networked sensor systems, November 03-05, 2004, Baltimore, MD, USA [doi>10.1145/1031495.1031509]
• 13: Z. Zhong and S. Nelakuditi. On the efficacy of opportunistic routing. In IEEE Communications Society Conference on Sensor, Mesh and Ad Hoc Communications and Networks (SECON), June 2007.
• 14: Nianjun Zhou , Huaming Wu , Alhussein A. Abouzeid, Reactive routing overhead in networks with unreliable nodes, Proceedings of the 9th annual international conference on Mobile computing and networking, September 14-19, 2003, San Diego, CA, USA [doi>10.1145/938985.939001]

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Wireless communication

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.2 Network Protocols
          Subjects: Routing protocols

  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.6 Optimization
  G.3 PROBABILITY AND STATISTICS
      Subjects: Markov processes; Stochastic processes