Optimal hierarchical energy efficient design for MANETs

Due to the growing interest in mobile wireless Ad-Hoc networks' (MANETs) applications, researchers have proposed many routing protocols that differ in their objective. Energy efficiency and scalability are two of the most important objectives. In our previous work, we proposed a fuzzy based hierarchical energy efficient routing protocol (FEER) for large scale MANETs that aims to maximize the network's lifetime and increase its scalability. The problem has two parts: the clustering part and the routing part. In the first part, we cluster the network into two levels of hierarchy (cluster heads and normal nodes), connect the cluster heads (backbone) with each other, and connect the normal nodes to the cluster heads while maximizing the network lifetime. In the second part, we design energy efficient routing that uses the hierarchical structure. We call the first part, the energy efficient clustering problem (EEC). In this paper, we formulate three variations of EEC as integer linear programming (ILP) problems. We first consider a network with a fully connected backbone (EEC-FCB). Then, we relax the fully connected constraint and consider a network with a connected backbone (EEC-CB), not necessarily fully connected. Finally, we consider a more reliable network (EEC-R) by electing a backup cluster head for each cluster.