5th International Workshop on Spatial Stochastic Models for Wireless Networks

Research Article

A delay-minimizing routing strategy for wireless multi-hop networks

  • @INPROCEEDINGS{10.1109/WIOPT.2009.5291567,
        author={Kostas Stamatiou and Francesco Rossetto and Martin Haenggi and Tara Javidi and James Zeidler and Michele Zorzi},
        title={A delay-minimizing routing strategy for wireless multi-hop networks},
        proceedings={5th International Workshop on Spatial Stochastic Models for Wireless Networks},
        keywords={Delay multi-hop Poisson point process interference},
  • Kostas Stamatiou
    Francesco Rossetto
    Martin Haenggi
    Tara Javidi
    James Zeidler
    Michele Zorzi
    Year: 2009
    A delay-minimizing routing strategy for wireless multi-hop networks
    DOI: 10.1109/WIOPT.2009.5291567
Kostas Stamatiou1,*, Francesco Rossetto2,*, Martin Haenggi3,*, Tara Javidi1,*, James Zeidler1,*, Michele Zorzi4,*
  • 1: University of California San Diego, La Jolla, CA 92037
  • 2: DLR, Institute of Communications and Navigation, 82234 Weßling, Munich, Germany
  • 3: University of Notre Dame, Notre Dame, IN 46556
  • 4: DEI - University of Padova, Via G. Gradenigo, 6/B, Padova, 35131, Italy
*Contact email: kostas@ucsd.edu, franzross@gmail.com, mhaenggi@nd.edu, tjavidi@ucsd.edu, zeidler@ece.ucsd.edu, zorzi@ing.unife.it


We consider a network where each route comprises a backlogged source, a number of relays and a destination at a finite distance. The locations of the sources and the relays are realizations of independent Poisson point processes. Given that the nodes observe a TDMA/ALOHA MAC protocol, our objective is to determine the number of relays and their placement such that the mean end-to-end delay in a typical route of the network is minimized. We first study an idealistic network model where all routes have the same number of hops, the same distance per hop and their own dedicated relays. Combining tools from queueing theory and stochastic geometry, we provide a precise characterization of the mean end-to-end delay. We find that the delay is minimized if the first hop is much longer than the remaining hops and that the optimal number of hops scales sublinearly with the source-destination distance. Simulating the original network scenario reveals that the analytical results are accurate, provided that the density of the relay process is sufficiently large. We conclude that, given the considered MAC protocol, our analysis provides a delay-minimizing routing strategy for random, multi-hop networks involving a small number of hops.