Distributed resource management in Wireless Ad Hoc networks

: from the perspective of cross-layer design and interaction

Abstract

In recent years, resource management in wireless ad hoc networks has drawn in- creasing attention. However, due to the interference-limited characteristic of wire- less channels and the distributed operation mode of ad hoc networks, before an e®ective and e±cient solution is obtained, several challenges need to be addressed. Generally speaking, the motivation of resource management is to allocate fair share of bandwidth and support quality of service for di®erent users in the network. Re- liable routing protocols could increase the packet delivery ratio and reduce the number of rerouting operations, and thus provide the ¯rst step of e®ectively man- aging the scarce wireless resource. According to a speci¯c allocation objective, the rate allocation schemes in the network layer calculate the entitled rate for each °ow. Then the MAC protocols support these rate allocation schemes by coordinating the packet transmissions and guarantee the calculated rates are achieved in the MAC layer. As we will discuss in detail later, a well designed reliable routing protocol is an important part of resource management in wireless ad hoc networks, especially when nodes are changing their positions, which essentially leads to mobile ad hoc networks (MANETs). There has been very active research on routing in MANETs and many routing metrics and protocols were proposed in the past few years, for both unicast and multicast transmissions. However, the reliability of transmission remains a problem. In the ¯rst part of this thesis, a Robust Link Availability Routing (RLAR) protocol is proposed to address the problem of reliable routing. RLAR combines pro-active routing with on-demand routing. The two modules of RLAR are responsible for pro-active estimation of link reliability and on-demand optimal routing, respectively. The ¯rst module relies on the information collected from the physical layer to estimate the normalized link availability (NLA). The second module then takes charge of route discovery and maintenance based on NLA. The optimal routing tree is ¯rst constructed and then additional protective links are also added to the tree backbone to form the ultimate mesh structure so to further enhance reliability. Through simulations, RLAR is proved to successfully reduce the number of rerouting and improve the average communication time before a rerouting procedure is triggered. The packet delivery ratio is also remarkably increased. The study of rate allocation schemes can be divided into several steps. Firstly, a speci¯c fairness criterion needs to be de¯ned. Then an appropriate interference model is built up to investigate the interference among di®erent °ows and their sub°ows. In the second part of this thesis, a price-based rate allocation scheme is proposed. Max-min fairness is adopted as the fairness criterion to ensure that no user is penalized excessively, and a certain minimum quality of service is guar- anteed to all users. To accurately re°ect the contention in wireless environment, the °ow contention graph is converted from the network topology graph. Based on the °ow contention graph, the clique constraint is modeled to generate the clique- based prices, which act as the congestion signal to control the end-to-end rates of multi-hop °ows. Through analysis and simulation, the proposed scheme is shown to be able to e®ectively distribute the bandwidth, according to max-min fairness criterion, to multi-hop °ows from the end-to-end perspective. The proposed scheme has many strengths, such as distributed operation, low computational complexity, applicability to both static and dynamic °ows, and short convergence time. In or- der to further accelerate the convergence speed of the algorithm, we propose a fast converging approach which signi¯cantly reduces the convergence time. With little modi¯cation, we also extend our scheme to support weighted max-min fairness. In the third part of this thesis, we move to the design of MAC protocol for band- width allocation. After the target rates are calculated in the network layer by the rate allocation schemes, a MAC protocol is needed to support these schemes by allowing each °ow to obtain its entitled bandwidth through medium access control. Unfortunately, the current MAC protocols, such as IEEE 802.11 DCF and other variants, are usually based on random access or intuitional fairness, and thus cannot satisfy this requirement. Therefore, we propose a novel cross-layer MAC protocol. This protocol has a time-slotted framework. Every N time slots are de¯ned as a transmission frame to estimate the share of the bandwidth within the correspond- ing maximal clique. All the nodes maintain a clique occupancy table (COT) for each maximal clique to which they are related. Based on this framework, two dif- ferent MAC algorithms are implemented in this protocol. The ¯rst one, Greedy Self-Contention (GSC) algorithm, is a contention-based algorithm. With this al- gorithm, every node contend for the shared medium at the beginning of each free time slot. It could support arbitrary rate allocation schemes. In order to acceler- ate the convergence speed, the second algorithm, Cooperative Token Forwarding (CTF) algorithm, is speci¯cally designed for the category of quasi-synchronous rate allocation schemes. It makes use of the quasi-synchronously shared °ow contention information within each maximal clique to eliminate the medium access contention, and thus its convergence performance is much better.

Date of Award	2 Oct 2007
Original language	English
Awarding Institution	City University of Hong Kong
Supervisor	Chi Hung Sammy CHAN (Supervisor)