Title: Delay analysis of randomised algorithms for link scheduling in wireless networks

Authors: Ali Ghiasian; Hossein Saidi; Mohammad Behdadfar

Addresses: Department of Electrical and Computer Engineering, Isfahan University of Technology, Isfahan, Iran ' Department of Electrical and Computer Engineering, Isfahan University of Technology, Isfahan, Iran ' IRIB University, Tehran, Iran

Abstract: To design a link scheduling algorithm that can maximise the throughput region yet meet the average delay constraint is a challenging issue in wireless networks. In this paper we aim to analyse and improve the delay performance of the well-studied randomised link scheduling algorithms. To this end, we first introduce a novel concept, the average hitting time, and analyse its impact on the upper bound of the average delay. We analytically show that for two given randomised algorithms achieving the same throughput region, the one with a smaller average hitting time has less average delay bound. We also show that by assigning traffic priorities in some specific applications, the achievable throughput region delivered by the randomised algorithm remains intact. This result is much valuable in the design of algorithms for some real-time applications by prioritising the traffic to reduce the average delay of those applications. The simulation results are consistent with our theoretical analysis.

Keywords: wireless sensor networks; WSNs; wireless networks; ad hoc networks; link scheduling; maximum weight matching; randomised algorithm; delay performance; throughput region; Lyapunov drift; simulation; QoS; quality of service.

DOI: 10.1504/IJAHUC.2013.054017

International Journal of Ad Hoc and Ubiquitous Computing, 2013 Vol.13 No.1, pp.59 - 72

Received: 23 Mar 2012
Accepted: 31 Jul 2012
Published online: 15 May 2013 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article