Analysis of total average queue length in multi-hop wireless networks

In upcoming communication environments, multi-hop networking is expected to be pervasive in wireless access and backbone networks because it promises large coverage and increased capacity. Many studies have been devoted to the throughput of multi-hop wireless networks, but the delay performance is not clearly investigated yet. In this Letter, we analyze a multi-hop wireless network to obtain a lower bound of the total average queue length since it is closely related to the delay. We first consider a network with single hop sessions only, and its total average queue length is characterized as a solution of a linear program. Then we present a novel idea of translating a network with multi-hop sessions into a network with single hop sessions only, thereby the linear programming approach can be applied again. Simulation results show that the lower bound is very close to the achievable value of our reference link scheduler. Hence, our bound is tight.

► We derive a lower bound of the total average queue length in multi-hop wireless networks.
► The lower bound is characterized as a solution of a linear program.
► The critical constraint of the linear program is obtained from our G/D/1 approximation for the conflicting queues.
► The bound is very close to the achievable value of the reference scheduling scheme such that it is very tight.