NSF Research Grant 

(June 2000 - May 2002)

A Dominating-Set-Based 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/re-calculation 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 well-defined quantitative performance metrics.

Contador    Since July 2003