The Hong Kong University of Science and Technology
Department of Computer Science


PhD Thesis Defence


"BANDWIDTH ALLOCATION IN WIRELESS AD HOC NETWORKS"

By


Mr. Zuyuan Fang

Abstract

The emergence of nomadic applications has raised intensive research
interest in providing Quality of Service (QoS) in Mobile Ad hoc Networks
(MANETs). In the networking protocol stack, a QoS capable medium access
control (MAC) protocol plays an important role. However, currently, the
widely deployed MAC protocol IEEE 802.11 Distributed Coordination Function
(DCF) does not provide any QoS guarantee and suffers from a problem of
fairness. In this thesis, we formulate the design of MAC protocols as the
problem of bandwidth allocation to individual links. The concept of
conflict graph is adopted to model the contention relations between link
flows in ad hoc networks, and based on this modelling, different
algorithms are proposed to address the problem in such a way that the
obtained MAC protocols for MANETs satisfy QoS objectives such as fairness
or a minimal bandwidth guarantee.

Firstly, a distributed max-min fair allocation algorithm is proposed to
enable each node in the ad hoc network to calculate the max-min fair share
of its links based on the two-hop away link flow information. Once each
link flow is assigned its fair share and those of its neighbors, a
measurement based backoff algorithm presented in the thesis can be invoked
to achieve weighted fairness. Secondly, in order to reduce the
communication overheads and meet different fairness objectives, the fair
bandwidth allocation problem is also modelled as a general utility based
constrained maximization problem. By invoking the Lagrange relaxation and
duality, both a non-cooperative and a cooperative game formulation of the
problem are proposed. The algorithm derived from the non-cooperative game
framework does not depend on any local flow information or contentions.
The algorithm derived from the cooperative game framework depends only on
one-hop link flow information. The fairness objective of these algorithms
is controlled by the adopted utility function. Simulations and numerical
results have shown that all these solutions not only provide better
fairness than the IEEE 802.11 DCF but also have the capability of
quantifying the bandwidth, which is crucial to other processes such as
admission control. As an alternative to this class of algorithms that are
all based on random access technique, a series of collision-free
scheduling algorithms are proposed to guarantee a minimal bandwidth. In
these algorithms, with the help of one-hop local flow information, each
node determines a local collision-free transmission schedule for all its
link flows.


Date:			Friday, 20 August 2004

Time:			11:00a.m.-1:00p.m.

Venue:			Room 3311
			Lifts 17-18

Chairman:		Prof. Susheng Wang (ECON)

Committee Members:	Prof. Brahim Bensaou (Supervisor)
			Prof. Gary Chan
			Prof. Jogesh Muppala
			Prof. Danny Tsang (ELEC)
			Prof. K.C. Chua (Elec. & Comp. Engg.,
					 National Univ. of Singapore)


**** ALL are Welcome ****