Please use this identifier to cite or link to this item:

A Graph Theory Based Opportunistic Link Scheduling for Wireless Ad Hoc Networks

Authors Chen, Qing
Zhang, Qian
Niu, Zhisheng
Issue Date 2009
Source IEEE transactions on wireless communications , v. 8, (10), 2009, OCT, p. 5075-5085
Summary Taking advantage of the independent fading channel conditions among multiple wireless users, opportunistic transmissions schedule the user with the instantaneously best condition and thus increase the spectrum utilization efficiency of wireless networks. So far, most proposed opportunistic scheduling policies for ad hoc networks exploit local multiuser diversity, i.e., each transmitter selects its best receiver independently. However, due to co-channel interference, the decisions of neighboring transmitters are highly correlated. Furthermore, the neighboring links without a common sender also experience independent channel fading. Taking the contention relationship and the channel diversity among links into account, we extend the concept of multi-user diversity to a more generalized one, by which a set of senders cooperatively schedule the instantaneously and globally best out-going links, thus the spatial diversity of the channel variation can be further exploited. In this paper, we formulate the opportunistic scheduling problem with fairness requirements into an optimization problem and present its optimal solution, i.e., the optimal scheduling policy. We also propose GOS, a distributed Graph theory based and Opportunistic Scheduling algorithm, which modifies IEEE 802.11 protocol to implement the optimal scheduling policy. Theoretical analysis and simulation results both verify that our implementation achieves higher network throughput and provides better fairness support than the existing algorithms.
ISSN 1536-1276
Rights © 2009 IEEE. Personal use of this material is permitted. However, permission to reprint/republish this material for advertising or promotional purposes or for creating new collective works for resale or redistribution to servers or lists, or to reuse any copyrighted component of this work in other works must be obtained from the IEEE. This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. In most cases, these works may not be reposted without the explicit permission of the copyright holder.
Language English
Format Article
Access View full-text via DOI
View full-text via Web of Science
View full-text via Scopus
Files in this item:
File Description Size Format
graphtheory.pdf 465127 B Adobe PDF