Integer Programs for Contention Aware Connected Dominating Sets in Wireless Multi-Hop Networks

Efficient propagation of data across mobile nodes is essential in wireless networks. A minimum connected dominating set (MCDS) of nodes is typically used to reduce redundant transmission in broadcasts. If a group of nodes wants to transmit over a shared channel simultaneously, then contention occurs. Contending nodes then defer transmissions for a random time. A contention aware connected dominating set (CACDS) that minimizes transmission conflict is therefore essential. We study integer programming formulations computationally for MCDS and CACDS. We use Benders decomposition to solve them and propose a new method to compute Bender’s feasibility cut based on the number of connected components.We evaluate the state-of-art approach computationally for MCDS and CACDS based on the shortest paths with our approach. The detailed experiments show that the new method takes less time and minimizes contention better in large networks.