skip to main content
10.1145/1400863.1400875acmconferencesArticle/Chapter ViewAbstractPublication PagesdialmConference Proceedingsconference-collections
research-article

Latency of opportunistic forwarding in finite regular wireless networks

Published: 18 August 2008 Publication History

Abstract

In opportunistic forwarding, a node randomly relays packets to one of its neighbors based on local information, without the knowledge of global topology. Each intermediate node continues this process until the packet arrives at its destination. This is particularly attractive in certain types of wireless ad hoc and sensor networks where obtaining accurate knowledge of global topology may be infeasible. However, opportunistic forwarding is hampered by the difficulty to control its performance, particularly, the end-to-end latency. This paper presents new analytical results that shed light on the latency of "random walk", the simplest type of opportunistic forwarding, for several useful regular network topologies, such as r-nearest cycle that can model variable wireless transmission distance in one dimensional scenario, and a 2D regular torus-type graph that can approximate grid-like deployments. We give new exact and approximation formulas for the maximum expected hitting time of random walk on such topologies.

References

[1]
S. Boyd, A. Ghosh, B. Prabhakar, and D. Shah, "Randomized gossip algorithms," IEEE Trans. Information Theory, vol. 52, no. 6, June 2006.
[2]
R. B. Ellis, "Discrete green's functions for products of regular graphs," 2003, arXiv:math/0309080v2.
[3]
F. Chung and S.-Y. Yau, "Discrete green's functions," Journal of Combinatorial Theory, Series A, vol. 91, pp. 191--214, 2000.
[4]
D. A. Levin, Y. Peres, and E. L. Wilmer, "Markov chains and mixing times," http://www.oberlin.edu/markov/, 2006, lecture notes.
[5]
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.
[6]
L. Lovasz, "Random walk on graphs: A survey," Combinatorics, Paul Erdos is Eighty, vol. 2, pp. 1--46, 1993.
[7]
D. Geller, I. Kra, S. Popescu, and S. Simanca, "On circulant matrices," http://www.math.sunysb.edu/sorin/, lecture notes.

Cited By

View all
  • (2015)Convergence Analysis for Regular Wireless Consensus NetworksIEEE Sensors Journal10.1109/JSEN.2015.242095215:8(4522-4531)Online publication date: Aug-2015
  • (2011)Analysis of latency of stateless opportunistic forwarding in intermittently connected networksIEEE/ACM Transactions on Networking10.1109/TNET.2010.210332119:4(1111-1124)Online publication date: 1-Aug-2011
  • (2009)Exact Analysis of Latency of Stateless Opportunistic ForwardingIEEE INFOCOM 200910.1109/INFCOM.2009.5061992(828-836)Online publication date: Apr-2009

Index Terms

  1. Latency of opportunistic forwarding in finite regular wireless networks

        Recommendations

        Comments

        Information & Contributors

        Information

        Published In

        cover image ACM Conferences
        DIALM-POMC '08: Proceedings of the fifth international workshop on Foundations of mobile computing
        August 2008
        100 pages
        ISBN:9781605582443
        DOI:10.1145/1400863
        Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

        Sponsors

        Publisher

        Association for Computing Machinery

        New York, NY, United States

        Publication History

        Published: 18 August 2008

        Permissions

        Request permissions for this article.

        Check for updates

        Author Tags

        1. opportunistic forwarding
        2. random walk on finite graphs
        3. wireless ad hoc and sensor networks

        Qualifiers

        • Research-article

        Conference

        PODC '08

        Acceptance Rates

        DIALM-POMC '08 Paper Acceptance Rate 10 of 35 submissions, 29%;
        Overall Acceptance Rate 21 of 68 submissions, 31%

        Contributors

        Other Metrics

        Bibliometrics & Citations

        Bibliometrics

        Article Metrics

        • Downloads (Last 12 months)3
        • Downloads (Last 6 weeks)0
        Reflects downloads up to 19 Feb 2025

        Other Metrics

        Citations

        Cited By

        View all
        • (2015)Convergence Analysis for Regular Wireless Consensus NetworksIEEE Sensors Journal10.1109/JSEN.2015.242095215:8(4522-4531)Online publication date: Aug-2015
        • (2011)Analysis of latency of stateless opportunistic forwarding in intermittently connected networksIEEE/ACM Transactions on Networking10.1109/TNET.2010.210332119:4(1111-1124)Online publication date: 1-Aug-2011
        • (2009)Exact Analysis of Latency of Stateless Opportunistic ForwardingIEEE INFOCOM 200910.1109/INFCOM.2009.5061992(828-836)Online publication date: Apr-2009

        View Options

        Login options

        View options

        PDF

        View or Download as a PDF file.

        PDF

        eReader

        View online with eReader.

        eReader

        Figures

        Tables

        Media

        Share

        Share

        Share this Publication link

        Share on social media