Open Access Open Access  Restricted Access Subscription or Fee Access

Analysis of Delay Performance Techniques on Multi-Hop Wireless Networks

R. Vediyappan, S. Prabhu, M. Gowthaman, C.S. Dhanabalan, Senthil Murugan


We analyze the delay performance of a multi-hop wireless network in which the routes between source-destination pairs are fixed. We develop a new queue grouping technique to handle the complex correlations of the service process resulting from the multi-hop nature of the flows and their mutual sharing of the wireless medium. A general set based interference model is assumed that imposes constraints on links that can be served simultaneously at any given time. These interference constraints are used to obtain a fundamental lower bound on the delay performance of any scheduling policy for the system. We present a systematic methodology to derive such lower bounds. For a special wireless system, namely the clique, we design a policy that is sample path delay optimal. For the tandem queue network, where the delay optimal policy is known, the expected delay of the optimal policy numerically coincides with the lower bound. The lower bound analysis provides useful insights into the design and analysis of optimal or nearly optimal scheduling policies.


Wireless Networks,voice over IP, singlehop and multihop.

Full Text:



H. Balakrishnan, C. Barrett, V. Kumar, M. Marathe, and S. Thite.The distance-2 matching problem and its relationship to the maclayercapacity of ad hoc networks. IEEE Journal on Selected Area inCommunications, 22, 2004.

L. Bui, R. Srikant, and A. L. Stolyar. Novel architectures and algorithmsfor delay reduction in back-pressure scheduling and routing. INFOCOMMini-Conference, 2009.

P. Chaporkar, K. Kar, and S. Sarkar. Throughput guarantees throughmaximal scheduling in wireless networks. In 43rd Annual AllertonConference on Communication, Control, and Computing, 2005.

J. G. Dai and W. Lin. Maximum pressure policies in stochasticprocessing networks. Operations Research, 53:197–218, 2005.

J. G. Dai and W. Lin. Asymptotic optimality of maximum pressurepolicies in stochastic processing networks. Preprint, October 2007.


  • There are currently no refbacks.

Creative Commons License
This work is licensed under a Creative Commons Attribution 3.0 License.