An Exact Algorithm for Minimum CDS With Shortest Path Constraint in Wireless Networks

In wireless networks, it is very difficult to realize routing on-demand or table-driven routing, since the topology is changing from time to time and the energy of each node is very limited. Motivated by the physical backbone in wired networks, a Connected Dominating Set (CDS) is imposed as a virtual backbone on wireless networks, which can make routing in wireless networks more efficient and practical. The authors can shrink the searching space for routing problem from the whole network to a CDS to reduce routing time and routing table size. Besides routing protocols, CDS can also be used in coverage problem, broadcasting and many other network applications..