The clustering algorithm for efficient energy management in mobile ad-hoc networks

Abstract

MANET (Mobile Ad-hoc Network) consumes much energy due to their dynamic capabilities, complexities, constraints of design such as lack of a specified communication infrastructure, and their change over time. One strategy to reduce energy consumption is to optimize routing in these networks, which is, in turn, one of the most important challenges in these networks. In addition, optimal routing will increase the network lifetime and lead to its stability. Considering the high efficiency of clustering methods among the routing algorithms we present a new clustering method and considering good performance of Evolutionary Algorithms (EAs) in finding proper head clusters, we present a specific EA-based method named ICA (Imperialist Competitive Algorithm) via numerical coding. By thinking of specific conditions of a MANET and estimating the mobility direction of nodes, we prevent from additional reclusterings leading to reducing the overload. We have evaluated our proposed method for: 1) accuracy (including the reproducibility, convergence and stability criteria) through three case studies with different numbers of nodes and ranges and 2) efficiency (by comparing to other methods). Moreover, we applied our proposed method to a case study (multi-robot system) with low velocity.

Introduction

A network is a number of computers and devices connected together for the purpose of transferring information and sharing resources through communication channels (Fig. 1).

Ad hoc networks are an autonomous set of distributed nodes that can communicate and exchange data with each other without the need for a centralized management system and a clear and fixed infrastructure. In addition to sending and receiving its packets, each node on a network can act as a host or router and can be involved in the routing and carry the data by sending the data to other nodes (Fig. 2).

Ad hoc networks are divided into wireless sensor networks and MANETs. They are called MANETs because of the mobility and autonomy of their nodes [1]. Each node has a routing table that contains information about the network and its routes. An increase in the number of nodes in the network will lead to increase in the size of the routing table which exists in the limited memory of the nodes [2].

Motivation: Considering widespread use of MANET in routine life, the consumption energy problem is a matter of concern. MANETs consume much energy due to their dynamic capabilities and lack of a specified communication infrastructure, which change over time. This concern motivates us to present an efficient solution for the consumption energy. However, this concern is directly dependent on the routing problem in MANETs. The optimal routing protocol, in turn, one of the most important challenges in MANETs. Moreover, an optimal routing protocol leads to the increase of the network lifetime and its stability. In designing a routing protocol, network resources, network diversity, load balancing paths and efficient routing should be considered as important factors. Hierarchy routing is the method considerably think these factors.

Hierarchy routing is one of MANET's algorithms for overcoming the hindrances that traditional algorithms suffer from in finding the specific route. Hence, we concentrate our work on the hierarchical routing which divides the network into clusters.

Having adopted clustering algorithm for a solution in optimal routing problem, we face the challenge of the optimal count of clusters and selecting cluster heads. Since these issues depends on several conflicting attributes, such as battery power, range, node degree and the velocity, a multi-attribute decision-making (MADM) algorithm should be thought. Evolutionary Algorithms (EAs) are known as MADM to select optimal solution in context of conflicting attributes. This fact motivates us to use an EA.

Moreover, clustering in MANETs and selection of head clusters is an NP-Hard problem, which motivates us to use EA. Imperialist Competitive Algorithm (ICA) is known as an effective EA to solve NP-Hard problems and has widely been used for similar NP-Hard problems such as combinatorial optimization, machine learning, signal processing [3], [4]. For travelling salesman problem (TSP), which is one of the most important discrete problems, ICA has benefited more efficiency than other EAs. This fact has been shown through 14 TSP samples consisting of 50 to 199 nodes (cities) [5]. Such evidences motivate us to present an ICA-based method to solve the routing problem in MANET. In addition, assimilation and evolution policies and elimination process of weak empires in ICA lead to reach to selection of optimal cluster head rapidly. The results we obtained show this fact (see Section VI). Due to very large and complex operational environments in MANETs, there are many routings among which optimal ones should be selected.

In a clustering algorithm, network nodes are divided into groups and clusters and one of the nodes which is responsible for cluster management, resource allocation, routing, and packet transport in the cluster is selected as the cluster head. In these clusters, nodes that have a direct two-way connection with the cluster head are called cluster member nodes or normal nodes, while nodes that have a direct two-way connection with more than one cluster head are called gateway nodes, which are used in inter-cluster communication. These clusters and gateways are considered the network infrastructure. Initially, the source node sends its packet to its cluster in each connection, then, the cluster head will direct to a specific destination through the network infrastructure after packet routing [6], [7].

In this paper, an optimal clustering model is presented for MANETs through numerical coding and specific operators. A reclustering is taken place when the topological structure of the network changes by the mobility of the node(s). Since, reclustering has an overload of control messages, this paper presents a new algorithm that prevents reclustering in certain conditions and estimates the direction of nodes mobility. These options reduce the overload leading to reduce energy consumption.

We evaluate the proposed algorithm in three sections for accuracy, reliability, and efficiency. The accuracy is evaluated using criteria of reproducibility, convergence and stability for different samples with different nodes and ranges. The reliability is evaluated in terms of the count of clusters, the count of changes of the cluster heads and the count of connections for different samples. The efficiency of the proposed algorithm is evaluated in comparison to other algorithms in terms of the count of clusters, the count of changes in cluster heads, the value of the fitness function, the count of live nodes, the count of connections, the end-to-end delay, and the count of reclusterings.

Our Contribution: To select the optimal cluster heads, there are various algorithms for clustering MANETs. However, some of them consider one attribute/objective in the cluster formation phase and ignore other attributes, while there are usually several conflicting attributes should be considered. In contrast with these algorithms, our proposed algorithm considers several conflicting attributes. The contributions of our proposed method are:

• 1. Compared to EAs and non-EAs, an effective routing is presented by which the count of hops and the count of cluster are decreased when there is a prior knowledge of link estimation,

• 2. Compared to other algorithms, the network durability and stability is increased using a proper fitness function and coverage simultaneously,

• 3. Compared to WCA, FWCA and MOC, an increase in longevity of cluster heads is created due to using node ranking and identifying node performance and ignoring weak nodes,

• 4. Compared to GA and PSO algorithms, an increase in stability of clusters is created due to decrease of count of node mobilities and directions,

• 5. Comparison to EA-based algorithms (CLPSO, IPSO, and BIOPSO) and Non-EAs algorithms (WCA, FWCA and MOC), there is an increase in the count of reclusterings using providing specific conditions and estimation of node mobility,

• 6. Compared to other algorithms (WCA, FWCA, EWCA, MOC, GACA and ZBMRP), there is a decrease of the end-to-end delay due to using the selection of the appropriate nodes as the gateway.