A hybrid ant colony optimization approach (hACO) for constructing load-balanced clusters

Nodes in an ad hoc network are usually organized into clusters, with each cluster being coordinated by a node acting as the cluster head (CH). Cluster members are one hop away from their CH. The collection of CHs give rise to a graph structure known as a dominating set. This paper proposes a hybrid ACO (hACO) approach that, when given a graph representing a network, selects a set of CHs in such a way that enables the remaining nodes to be distributed as evenly as possible to these CHs while ensuring that the maximum load a CH can take is maintained. Artificial ants are used to select the CHs. After a CH is selected, a heuristic is used to determine cluster member assignment. Solution quality is measured using a metric called the load balancing factor (LBF). We benchmark the performance of the hACO against a recently proposed genetic algorithm (GA) that addresses the same problem. Empirical results point to the fact that hACO consistently produced good solutions across the 41 problem instances. Even though GA gave the best solutions for several instances, its performance deteriorated for graphs with relatively higher density. We explain this behavior by examining the clusters produced by both methods.