NSF Research Grant
(June 2000  May 2002)
A DominatingSetBased Routing Scheme in Ad Hoc Wireless
Networks
Recent advances in technology have provided portable computers with wireless
interfaces that allow networked communication among mobile users. The
resulting computing environment, which is often referred to as mobile
computing, no longer requires users to maintain a fixed and universally
known position in the network, and enables almost unrestricted mobility.
An ad hoc wireless network is a special type of wireless mobile network
in which a collection of mobile hosts with wireless network interfaces
may form a temporary network, without the aid of any established infrastructure
or centralized administration. Efficient routing among a set of mobile
hosts (also called nodes) is one of the most important functions in ad
hoc wireless networks. Routing based on a connected dominating set is
a promising approach, where the search space for a route is reduced to
the nodes in the set. A set is dominating if all the nodes in the system
are either in the set or are neighbors of nodes in the set. In this proposal,
we study a simple and efficient distributed algorithm for calculating
a connected dominating set in an ad hoc wireless network, where connections
of nodes are determined by their geographical distances and the corresponding
graph is called a unit graph. A reduced graph is then induced from the
connected dominating set and the routing process is restricted to this
reduced graph. Our preliminary results on random unit graphs are very
promising in generating a small reduced graph in a way faster than existing
methods. The goals of the proposed research are: (1) Enhance the process
(also called the marking process) of determining a connected dominating
set of a unit graph. (2) Complete the update/recalculation algorithm
for the connected dominating set when the topology of the ad hoc wireless
network changes dynamically. (3) Extend the proposed approach to a hierarchical
structure, where the marking process is applied on the reduced graph to
generate a reduced graph of the reduced graph. The hierarchical structure
is obtained by applying the marking process iteratively. (4) Select an
appropriate routing protocol for the reduced graph. This scheme could
be a proactive routing (such as various extended link state and distance
vector routing protocols), a reactive routing (also called on demand),
or a combination of both. (5) Explore the possibility of combining dominating
set information and location information provided by a Global Positioning
System (GPS) to derive a better routing scheme. (6) Integrate different
components and fine tune the system through an empirical study based on
a set of welldefined quantitative performance metrics.
Since July 2003
