Delay analysis of randomised algorithms for link scheduling in wireless networks. (22nd May 2013)

• Record Type: Journal Article
• Authors: Ghiasian, Ali; Saidi, Hossein; Behdadfar, Mohammad
• Is Part Of: International journal of ad hoc and ubiquitous computing. Volume 13:Number 1(2013)
• Page Start: 59
• Page End: 72
• Publication Date: 2013-05-22
• Subjects: 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; Ubiquitous computing -- Periodicals; Embedded computer systems -- Periodicals; Electronic data processing -- Distributed processing -- Periodicals; Wireless communication systems -- Periodicals; Computer architecture -- Periodicals; 004.2
• Languages: English
• ISSNs: 1743-8225

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.