Backbone formation in wireless ad hoc networks using connected dominating set

Abstract

This thesis investigates the virtual backbone construction in wireless ad hoc networks using Connected Dominating Set (CDS) and analyzes the performance of centralized scheduling in IEEE 802.16 based wireless mesh networks. In the absence of infrastructure and facing the dynamic topology change, efficient protocol for backbone formation is one of the most important issues in wireless ad hoc networks. Connected dominating set formation is a promising approach for constructing virtual backbones. However, finding the minimum CDS in an arbitrary graph is a NP-Complete problem. We propose a novel zone-based distributed algorithm for CDS formation in ad hoc networks. In this Zone algorithm, we combine the zone and level concepts to sparsify the CDS constructed by previous approaches. Thus, this proposed algorithm can significantly reduce the CDS size, especially for large-scale dense networks. For IEEE 802.16 based Wireless Mesh Networks (WMN), we propose a collision-free centralized scheduling algorithm to provide high qualified wireless multimedia services. We design a relay strategy for the mesh nodes in a transmission tree, taking special considerations on fairness, channel utilization and transmission delay. We evaluate the proposed algorithm with four selection criteria through extensive simulations and the experimental results are instrumental for improving the performance of IEEE 802.16 based WMNs in terms of link scheduling.

Date of Award	3 Oct 2006
Original language	English
Awarding Institution	City University of Hong Kong
Supervisor	Wei Jia JIA (Supervisor)