Algorithms on Calculating the Minimum Dominating Connected Set for Efficient Routing in Ad hoc Wireless Network

Author Name : Vikas Singh Thakur, Hiral Raja

ABSTRACT

In This paper presents a new approach to compute the MCDS (Minimum Connected Dominating Set) for Mobile Ad hoc Network (MANET). The problem of finding a MCDS is NP-hard. This approach is based on linear programming theory. In first step, we formulate the problem to find the minimum dominatingset as an integer linear programming problem. Next, we add constraints to the original problem to force the minimum dominating set to be a connected set. The effectiveness of the approach is confirmed through simulation study and comparison with other approaches.

Keywords: Ad hoc network, Minimum Connected dominating Set, Integer programming.