Construction of Virtual Backbone with Multiple Factors Constraints in Wireless Ad-hoc Network
Ning Zhang, Incheol Shin, Feng Zou,Weili Wu and My T. Thai
Connected Dominating Set (CDS) has been a well known approach for constructing a virtual backbone to alleviate the broadcasting storm in wireless ad-hoc networks. Current research has focused on minimizing the CDS size, since computing a minimum size CDS is NP-hard. However, little work on CDS with multiple factors constraints has been found in literature. In this work, we investigate the trade-offs among multiple factors in CDS construction, such as fault tolerance, size, diameter and running time. To our best knowledge, no existing research has considered these important factors together in a single model, so that we introduce the multi-factors model studying a joint optimization problem in which the objective is to optimize the CDS size, network latency or running time while keeping the fault tolerance. Building on this model, we provide the approximation algorithms with constant ratios. In addition, we present improvement techniques, inspired by the computational geometry and probability, that systematically reduce running time or size of CDS. Simulation results show that our algorithms can gain good trade-offs among these factors, which coincide with theoretical analysis.
Keywords: Virtual backbone, connected dominating set, wireless ad hoc network.