Abstract

Ad hoc wireless networks are characterized by lack of fixed infrastructure and central administration, dynamic topology, and strict resource limitations. These features put special challenges in routing protocol design. Existing routing protocols employ flooding for route detection or topology update. But flooding is very unreliable, which means not all hosts receive the broadcasted packet. Flooding also suffers from "broadcast storm problem", which causes excessive redundancy, contention and collision in the network. One solution to overcoming this problem is to compute a virtual backbone based on the physical topology, and run existing routing protocols over the virtual backbone. The most attractive benefit of the introduction of virtual backbone is the substantial reduction on protocol overhead. This virtual structure also facilitates QoS routing and cost-aware routing in ad hoc wireless networks. In my study, the virtual backbone is approximated by a "minimum connected dominating set (MCDS)" in unit-disk graphs. Since MCDS is a NP-Hard problem, heuristics have to be sought. Two distributed time/message efficient algorithms are proposed to compute connected dominating sets. Both of them have good performance compared with existing algorithms in the literature. One of my future work is to turn these algorithms into virtual backbone-based routing protocols that take resource limitation into consideration .