Opportunistic forwarding in wireless networks with duty cycling

ABSTRACT

Opportunistic forwarding, by which data is randomly relayed to a neighbor based on local network information, is a fault-tolerant distributed algorithm particularly useful for challenged ad hoc and sensor networks where it is difficult to obtain global topology information because of frequent disruptions. Also, duty cycling is a common technique that constrains the RF operations of wireless devices for saving the battery energy and thus extending the longevity of the network. The combination of opportunistic forwarding and duty cycling is a useful approach for wireless ad hoc and sensor networks that are plagued with energy constraints and poor connectivity. However, such a design is hampered by the difficulty of analyzing and controlling its performance, particularly, the end-to-end latency. This paper presents analytical results that shed light on the latency of opportunistic forwarding in wireless networks with duty cycling. In particular, we give approximation formulas and bounds for the expected latency of opportunistic forwarding in presence of duty cycling for general finite network topologies, and an exact formula for a specific regular network topology that captures some common sensor network deployment scenarios. Moreover, our results concern finite-sized networks, and hence, are practically more useful than other asymptotic analyses in the literature.

REFERENCES

• 1: D. Aldous and J. A. Fill. Reversible Markov chains and random walks on graphs. http://www.stat.berkeley.edu/ aldous/RWG/book.html, 1999. Lecture notes.
• 2: Chen Avin , Gunes Ercal, On the cover time and mixing time of random geometric graphs, Theoretical Computer Science, v.380 n.1-2, p.2-22, June, 2007 [doi>10.1016/j.tcs.2007.02.065]
• 3: S. Boyd, A. Ghosh, B. Prabhakar, and D. Shah. Randomized gossip algorithms. IEEE Trans. Information Theory, 52(6), June 2006.
• 4: Fan Chung , S.-T. Yau, Discrete Green's functions, Journal of Combinatorial Theory Series A, v.91 n.1-2, p.191-214, July-Aug. 2000 [doi>10.1006/jcta.2000.3094]
• 5: L. Dai, P. Basu, and J. Redi. An energy efficient and accurate slot synchronization scheme for wireless sensor networks. Broadband Communications, Networks and Systems, 2006. BROADNETS 2006. 3rd International Conference on, pages 1--8, 1-5 Oct. 2006.
• 6: Julius Degesys , Prithwish Basu , Jason Redi, Synchronization of strongly pulse-coupled oscillators with refractory periods and random medium access, Proceedings of the 2008 ACM symposium on Applied computing, March 16-20, 2008, Fortaleza, Ceara, Brazil [doi>10.1145/1363686.1364164]
• 7: R. B. Ellis. Discrete green's functions for products of regular graphs, 2003. arXiv:math/0309080v2.
• 8: D. Geller, I. Kra, S. Popescu, and S. Simanca. On circulant matrices. http://www.math.sunysb.edu/ sorin/. Lecture notes.
• 9: D. A. Levin, Y. Peres, and E. L. Wilmer. Markov chains and mixing times. http://www.oberlin.edu/markov/, 2006. Lecture notes.
• 10: L. Lovasz. Random walk on graphs: A survey. Combinatorics, Paul Erdos is Eighty, 2:1---46, 1993.
• 11: C. Park, K. Lahiri, and A. Raghunathan. Battery discharge characteristics of wireless sensor nodes: An experimental analysis. In IEEE SECON 2005, September 2007.
• 12: J. Redi, S. Kolek, K. Manning, C. Partridge, R. Rosales-Hain, R. Ramanathan, and I. Castineyra. Javelen: An ultra-low energy ad hoc wireless network. Ad Hoc Networks Journal, 5(8), 2008.

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:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Network problems

General Terms:
Design, Performance, Theory

Keywords:
duty cycling, opportunistic forwarding, random walk on graphs, wireless ad hoc and sensor networks