Load balanced connected dominating set for mobile ad hoc networks

A connected Dominating Set (CDS) can be used as a backbone in a mobile ad hoc network (MANET) where a fixed communication infrastructure does not exist. Creating a virtual backbone within a MANET can reduce routing overhead and enhance scalability. Most CDS algorithms that exist today use a heuristic approach to try and find a Minimum CDS (MCDS). These approaches generally assign nodes with a large number of connections to be backbone nodes. Due to the high number of connections, the backbone nodes process a high volume of traffic, increasing energy consumption. This paper expands on an existing load balancing CDS algorithm, where the communication load is more evenly distributed between the backbone nodes.