Distributed Scheduling in Multihop Ad Hoc Networks

This dissertation, "Distributed Scheduling in Multihop Ad Hoc Networks" by Yijiang, Sun, 孫一江, was obtained from The University of Hong Kong (Pokfulam, Hong Kong) and is being sold pursuant to Creative Commons: Attribution 3.0 Hong Kong License. The content of this dissertation has not been altered in any way. We have altered the formatting in order to facilitate the ease of printing and reading of the dissertation. All rights not granted by the above license are retained by the author. Abstract: Abstract of thesis entitled "Distributed Scheduling in Multihop Ad Hoc Networks" Submitted by Sun Yijiang for the degree of Master of Philosophy at The University of Hong Kong in February 2008 A multihop ad hoc network is a network formed by multiple nodes with- out the aid of any centralized administration, and data traffic is typically forwarded by multiple intermediate nodes before reaching its destination. In this thesis, we focus on improving QoS of end-to-end traffic flows in multihop ad hoc networks through packet transmission scheduling. Our approach was to design a framework in which existing schedul- ingalgorithmsoriginallydesigned forinfrastructure-basedwirelessnetworks could be adapted to multihop ad hoc networks. While infrastructure-based wireless scheduling has been studied extensively and most of the proposed algorithms handle the characteristics of wireless medium in an effective and fairway, ourapproach aimstogeneralizetheadaptationofthese algorithms to ad hoc networks and thus to make maximum use of the existing resource of wireless scheduling. iThe framework consists of two sets of mechanisms. The first one is an end-to-end service compensation mechanism. Each multihop flow is asso- ciated with some QoS requirement, which is requested and granted in the form of the desired service rate. The achieved rate is estimated at the des- tination and fed back to the source periodically. Both the desired rate and achieved rate of a multihop flow are propagated from the source node to all its downstream relaying nodes. With this information, a compensation- capable scheduling algorithm originally designed for infrastructure-based wireless networks can be adapted to each ad hoc node for error compensa- tion. The second part of the framework is a set of mechanisms for distributed opportunistic scheduling in multihop wireless ad hoc networks. The frame- work includes a wireless link state estimation mechanism, a requirement on medium access control protocol and two mechanisms to limit the access of the wireless medium. The link state estimation mechanism provides the necessary status of each wireless link and thus enables the adaptation of various opportunistic scheduling algorithms. The performance ofthe proposed framework was evaluated by computer simulations. Theresultsshowed thattheframeworkcaneffectivelycompen- sate flows that suffer sporadic burst channel errors in an end-to-end fashion and provides robust outcome fairness in the presence of channel errors. (Total number of words: 357) Signed Sun Yijiang ii DOI: 10.5353/th_b3955828 Subjects: Ad hoc networks (Computer networks) Computer algorithms