Applied Soft Computing 12 (2012) 1913–1928
Contents lists available at ScienceDirect
Applied Soft Computing journal homepage: www.elsevier.com/locate/asoc
Energy-efficient clustering in mobile ad-hoc networks using multi-objective particle swarm optimization Hamid Ali, Waseem Shahzad, Farrukh Aslam Khan ∗ Department of Computer Science, National University of Computer and Emerging Sciences, A.K. Brohi Road, H-11/4, Islamabad 44000, Pakistan
a r t i c l e
i n f o
Article history: Received 2 October 2010 Received in revised form 29 April 2011 Accepted 12 May 2011 Available online 20 May 2011 Keywords: Mobile ad hoc network (MANET) Multi-objective particle swarm optimization (MOPSO) Clustering Cluster-head (CH) Energy-efficient networks Load balance factor
a b s t r a c t A mobile ad hoc network (MANET) is dynamic in nature and is composed of wirelessly connected nodes that perform hop-by-hop routing without the help of any fixed infrastructure. One of the important requirements of a MANET is the efficiency of energy, which increases the lifetime of the network. Several techniques have been proposed by researchers to achieve this goal and one of them is clustering in MANETs that can help in providing an energy-efficient solution. Clustering involves the selection of cluster-heads (CHs) for each cluster and fewer CHs result in greater energy efficiency as these nodes drain more power than noncluster-heads. In the literature, several techniques are available for clustering by using optimization and evolutionary techniques that provide a single solution at a time. In this paper, we propose a multi-objective solution by using multi-objective particle swarm optimization (MOPSO) algorithm to optimize the number of clusters in an ad hoc network as well as energy dissipation in nodes in order to provide an energy-efficient solution and reduce the network traffic. In the proposed solution, inter-cluster and intra-cluster traffic is managed by the cluster-heads. The proposed algorithm takes into consideration the degree of nodes, transmission power, and battery power consumption of the mobile nodes. The main advantage of this method is that it provides a set of solutions at a time. These solutions are achieved through optimal Pareto front. We compare the results of the proposed approach with two other well-known clustering techniques; WCA and CLPSO-based clustering by using different performance metrics. We perform extensive simulations to show that the proposed approach is an effective approach for clustering in mobile ad hoc networks environment and performs better than the other two approaches. © 2011 Elsevier B.V. All rights reserved.
1. Introduction A mobile ad hoc network (MANET) is a dynamic and selfadapting network in which no centralized control exists. It has a set of dynamic nodes that can move freely. These nodes have limited processing speed, battery, storage, and communication capabilities. These features of MANETs with non-existence of central base station bring many new problems and challenges for the researchers. Clustering is a method of organizing objects into meaningful groups with respect to their similarities. The objective of clustering in MANETs is to identify the groups of nodes in such a way that the identified groups are exclusive and any instance in the network belongs to a single group. The special nodes known as cluster-heads (CHs) are responsible for the formation of clusters, maintenance of the network topology, and the resource allocation to all nodes belonging to their clusters. Since the configuration of the cluster-
∗ Corresponding author. Tel.: +92 321 8551974; fax: +92 51 8314119. E-mail addresses:
[email protected] (H. Ali),
[email protected] (W. Shahzad),
[email protected] (F.A. Khan). 1568-4946/$ – see front matter © 2011 Elsevier B.V. All rights reserved. doi:10.1016/j.asoc.2011.05.036
heads is constantly changing due to the dynamic nature of mobile nodes, minimizing the number of cluster-heads becomes essential. An optimal selection of the cluster-heads is an NP-hard problem. The neighbourhood of a CH is the set of nodes that lie within its transmission range. Since energy efficiency is an important requirement of a MANET, which increases its lifetime, clustering can provide an energy-efficient solution as only few nodes are involved in doing the main operations in the network such as routing, management, data aggregation, etc. A wireless sensor network (WSN), which is a special type of ad hoc network consists of autonomous tiny devices that cooperatively monitor physical or environmental conditions, such as temperature, vibration, pressure, motion, etc. These tiny devices or sensors have more limited battery power, memory and processing capabilities. Therefore, clustering can also help achieve an energy-efficient solution for WSNs. Optimization refers to finding one or more solutions of a problem, which correspond to extreme values of one or more objectives. It has been an active area of research as many real world optimization problems have become increasingly complex. Therefore better optimization algorithms are always needed. Most of the real world problems consist of several objectives that need to be optimized
1914
H. Ali et al. / Applied Soft Computing 12 (2012) 1913–1928
Fig. 1. Optimal Pareto front.
simultaneously. These problems arise in many applications. When solving multi-objective problems (MOPs) with traditional mathematical programming techniques, they generate a single solution from the set of solutions in one run. Therefore these techniques are not suitable to solve multi-objective optimization problems. Evolu-
tionary algorithms paradigm is very suitable to solve MOPs because they are population based and can generate a set of solutions in one run [1]. Optimization problems have great importance in scientific, engineering design and decision-making applications. When an optimization problem has only one objective then the task of finding optimal solution is called single-objective problem. Normally in a single-objective problem we are interested in finding only a single solution except multimodal functions. When an optimization problem has more than one objective functions then the optimization problem is known as multi-objective optimization problem. In multi-objective problems multiple criteria are considered. Since there is no single solution that can be termed as optimal solution, i.e., having multiple conflicting objectives, therefore, we are interested in finding a number of optimal solutions [2]. In this paper, we present a multi-objective particle swarm optimization (MOPSO) based clustering algorithm for mobile ad hoc networks. MOPSO efficiently manages the resources of the network by finding optimal numbers of clusters in multi-objective fashion. Optimal number of clusters can make the MANET energy-efficient by efficiently managing the resources of the network so that the cluster-heads can do the job of routing network packets within the cluster or to the nodes of other clusters. The proposed clustering algorithm takes into consideration the transmission power, ideal degree, mobility of nodes, and battery power consumption
Fig. 2. Flowchart of MOPSO.
H. Ali et al. / Applied Soft Computing 12 (2012) 1913–1928
1915
Fig. 3. Degree difference vs. energy consumption in case MOPSO in 100 m × 100 m area by fixing nodes (a) 15 nodes (b) 20 nodes (c) 25 nodes (d) 30 nodes.
of the mobile nodes for selecting the cluster-heads. MOPSO uses the evolutionary capability to optimize the number of clusters. Instead of assigning a weight to each of the parameters mentioned above, we deal directly with the multi-objective problem in order to find out the Pareto-optimal solutions. The algorithm first finds the cluster-head and then neighbours of the cluster-head. The neighbourhood of a cluster-head is the set of nodes that lie within its transmission range. There are some requirements of clustering in MANETs. The clustering algorithm must be distributed, since every node in the network has only local knowledge and communicates outside its group only through its cluster-head as in the case of cluster-based routing. The algorithm should be robust as the network size increases or decreases and it should be able to adapt to all the changes. The clusters should be reasonably efficient, i.e., the selected cluster-heads should cover large number of nodes as much as possible. We compare the results of the MOPSO-based clustering technique with two other well-known clustering algorithms; comprehensive learning particle swarm optimization (CLPSO) based clustering [3] and weighted clustering algorithm (WCA) [4]. The experimental results show that the proposed approach covers the whole network with minimum number of clusters that can reduce the routing cost of the network and consumes less energy. This will help minimize the number of hops and delays of packets transferred in a cluster-based routing environment. The numbers of clusters are large when the transmission ranges of nodes are small. It also has advantage of finding multiple solutions instead of a single solu-
tion. This diversity of solutions provides more flexibility for the domain experts so that they can choose a solution according to their requirements. The results show that the proposed clustering approach is effective and flexible as compared to the other approaches and performs better than the other two algorithms in a mobile ad hoc network environment. The algorithm has the ability to optimize the parameters of mobile nodes for finding the multi-objective solution. The rest of the paper is organized as follows: In Section 2 we give an overview of the previous clustering algorithms for mobile ad hoc networks. Section 3 describes multi-objective clustering approach while Section 4 provides an overview of multiobjective particle swarm optimization. Section 5 describes our proposed MOPSO-based clustering algorithm. The experimental results are presented in Section 6 while Section 7 concludes the paper. 2. Related work Baker and Ephremides [5] proposed the lowest-ID, known as identifier-based clustering algorithm. It assigns a unique ID to each node and chooses the node with the lowest ID as a cluster-head. It means that whenever a new node with a lowest ID appears, it will become the cluster-head. Gerla and Tsai [6] proposed the highest connectivity algorithm for clustering. It is multi-cluster, multi-hop packet radio network architecture for wireless adaptive mobile information systems. In this technique the degree of nodes
1916
H. Ali et al. / Applied Soft Computing 12 (2012) 1913–1928
Fig. 4. Number of clusters vs. transmission range in case of WCA, CLPSO, and MOPSO in 100 m × 100 m area by fixing nodes from 30 to 60.
is calculated, which describes the number of neighbours of a given node. Each node broadcasts its identifier for the election procedure. After computing its degree, the node having the maximum degree becomes the cluster-head. A genetic algorithm based clustering algorithm was proposed in Ref. [7]. Genetic algorithm was used to optimize the number of clusters in an ad hoc network. It is a weight-based clustering algorithm, which assigns a weight to each objective of the problem and is set by the user. Chatterjee et al. [4] proposed the weighted clustering algorithm. It elects cluster heads according to their weights. The weights are computed by combining a set of parameters such as battery power, mobility and transmission range. This was the first weighted clustering algorithm proposed for MANETs. The time required to identify the cluster-heads depends on the diameter of the underlying network. The non-periodic procedure for the selection of cluster heads is invoked on-demand and is aimed to reduce the computation and communication costs. Another clustering algorithm based on d-hops has been proposed in Ref. [8]. It forms variable diameter clusters based on mobility pattern of the nodes in MANETs. A new metric is used to find the variation of distance between nodes over time in order to estimate the relative mobility of two nodes. The authors also estimate the stability of clusters based on relative mobility of cluster members. The diameter of clusters is not restricted to two hops as other clustering algorithms do. The diameter of clusters is flexible
and determined by the stability of clusters. Nodes are grouped into one cluster, which have similar moving pattern. Shahzad et al. [3] proposed a comprehensive learning particle swarm optimization based clustering algorithm for mobile ad hoc networks. It finds the optimal or near-optimal number of clusters to efficiently manage the resources of the network. The cluster-heads are used for routing network packets within the cluster or to the nodes of other clusters. It takes into consideration the transmission power, ideal degree, mobility of the nodes and battery power consumption of the mobile nodes. It is also a weighted clustering algorithm that assigns a weight to each of these parameters of the network. Each particle contains information about the cluster-heads and the members of each cluster. The basic problem with all these heuristic-based algorithms is that none of them include all the basic parameters of MANETs. WCA was the first algorithm that includes maximum number of parameters but it does not find optimal number of clusters in the network. It assigns weight to each objective function and makes the multi-objective problem single-objective and finds only a single final solution. Whereas, the proposed MOPSO based clustering algorithm finds multiple solutions. Since our problem is continuous in nature, therefore, we used PSO as it has been successfully applied to solve continuous optimization problems and our problem can easily be encoded in PSO.
H. Ali et al. / Applied Soft Computing 12 (2012) 1913–1928
1917
Fig. 5. Number of clusters vs. transmission range in case of WCA, CLPSO, and MOPSO in 200 m × 200 m area by fixing nodes from 30 to 60.
3. Multi-objective clustering Multi-objective problems have a number of objectives that are minimized or maximized simultaneously. These problems have a number of constraints, which a solution must satisfy. In multiobjective optimization we have a multi-dimensional search space. There are n objective functions: f(s) = (f1 (s), f2 (s),. . ., fn (s)) in which each objective function can be either minimized or maximized. s* is Pareto optimal solution if there exists no feasible vector of decision variables s ∈ F which would decrease some objective value without causing a simultaneous increase in at least one other objective value. This concept almost always gives not a single solution, but rather a set of solutions called the Pareto optimal set or Pareto optimal solutions. The vector corresponding to the solutions included in the Pareto optimal set is called non-dominated vector. The plot of the objective functions whose non-dominated solutions are in the Pareto optimal set is called the Pareto front [9]. In multi-objective optimization we are interested to find the set of Pareto-optimal solutions that are close to true Pareto-optimal front. Those solutions, which are not close to the true Pareto-front are not desirable solutions. The set of optimal solutions should be diverse. Multi-objective problems have two spaces, one is decision variables space and another is objective space. Diversity can be defined in both of these spaces. Multiple Pareto-optimal solutions can exist if and only if the objectives are conflicting to each other
in a problem. If the objectives are not conflicting to each other then Pareto-optimal set is just one. In single-objective solution, there is only one search space, i.e., the decision variable space. But the difficulty with multi-objective problems is that it involves two search spaces instead of one. A solution s1 is said to dominate the other solution s2 if and only if following two conditions are true which are given below: • The solution s1 is no worse than s2 in all objectives. • The solution s1 is strictly better than s2 in at least one objective. If any of the above mentioned condition is false, the solution s1 does not dominate the solution s2 . If solution s1 dominates the solution s2 then solution s1 is better than solution s2 . When two solutions are compared with respect to all objective functions and if none of them is better than the other or in other words none of these dominate the other then the two solutions are called non-dominated solutions. If all objectives are equally important then we cannot say which of these solutions is better than the other. For a given set of solutions, we can perform all possible pairwise comparisons and find which solution dominates the other and which solutions are non-dominated with respect to each other. At the end we have a set of solutions, which do not dominate each other and these solutions are called Pareto-optimal solutions. These all non-dominated solutions are joined with a curve and all solu-
1918
H. Ali et al. / Applied Soft Computing 12 (2012) 1913–1928
Table 1 Proposed MOPSO algorithm. (1) Randomly initialize the positions of all the nodes. (2) Initialize the velocity of each node. (3) Initialize the general parameters of MOPSO (4) FOR each particle X DO (a) WHILE whole network is not covered DO i. Randomly select a cluster head Xi ii. Find the neighbours of the cluster head (b) Remove the cluster head ‘i’ and its neighbours for next cluster head selection process (c) END WHILE (5) END FOR (6) Evaluate each of the particles in POP (7) Store the best cluster heads vectors (8) Find the Pareto front with non-dominated sorting, (9) Store cluster heads vectors that represent non-dominated vectors in the repository REP (10) Find the global cluster heads vector from the repository (11) WHILE maximum number of cycles not reached DO (a) Compute the velocity (VEL) of each cluster heads vector (b) Compute the new cluster heads vectors of the solutions adding the velocity produced from the previous step (c) Evaluate each of the particles in POP (d) Update the contents of REP (e) When the current combination of cluster heads of the solution is better than the combination of cluster heads contained in its memory, the particle’s position is updated (f) Increment the loop counter (12) END WHILE
tions lying on this curve are called Pareto-optimal solutions. The curve formed by these solutions is known as Pareto-optimal front [10]. This can be seen from Fig. 1 in which we have two objective functions that are conflicting with each other. As our problem is multi-objective clustering in which we group the mobile nodes according to multiple objectives, we used four objective functions from mobile ad-hoc networks environment. Usually we do not have only a single best solution for this kind of problem. Hence, we are interested in finding a set of optimal clusters. 4. Multi-objective particle swarm optimization Evolutionary algorithms have been widely used for finding multiple solutions in multi-objective optimization problems. These algorithms are capable of finding multiple solutions at a time instead of a single solution. A number of evolutionary algorithms have been developed that use different mechanisms to evolve the solutions, for example, genetic algorithm [12], artificial immune system, differential evolution and swarm intelligence [1,3,10,13–17], etc. Swarm intelligence is an evolutionary technique inspired by the natural world. It has been used to solve various difficult optimization problems. There are two main approaches under the umbrella of swarm intelligence, one is particle swarm optimization and other is ant colony optimization. We speak of swarming behaviour with regard to social insects, ants, bees, termites and wasps. An insect nest contains hundreds, thousands, or millions of individual insects. The individual insect is not a very intelligent creature, but the social organism makes a collective intelligence, i.e., the ants efficiently gather food, the bees in the hive help regulate temperature, etc. Each individual insect is a reactive agent responding to local stimuli in a very simple way without reasoning. Kennedy and Eberhart [11] proposed an algorithm in 1995 inspired by the choreography of a bird flock, known as particle swarm optimization (PSO). In this algorithm best personal and best global behaviour guide each individual
in the flock. These behaviours quickly converge each individual to near-optimal geographical positions. In PSO, a complete single solution of the problem is called a particle. The group of all these particles becomes a swarm, which searches for an optimum solution. A group of swarms is used in multi-objective problems instead of a single swarm. A particle i . The dimension of the vector is defined by its position vector X i is equal to the number of attributes in a problem. The position of its personal best solution and its velocity found so far are Pi and V i , respectively. All the particles know their best solution found so far. Initially, particle positions and velocities are generated randomly and then proceed iteratively. The velocities and positions are calculated as follows:
vid = wvid + c1r1(pid − xid ) + c2r2(pgd − xid )
(1)
xid = xid + vid
(2)
where d = 1,2,..,D; i = 1,2,..,N, N is the size of the population, w is the inertia weight, c1 and c2 are two positive constants, r1 and r2 are two random values in the range [0.1]. The new velocity of the ith particle is calculated using Eq. (1) by taking into consideration three terms; the particle’s previous velocity, the best personal position and the global best position. Eq. (2) is used for new position of a particle. The inertia weight is employed to control the impact of the previous history of velocities on the current velocity. If we do not want to include the previous history then we simply exclude the inertia weight. Particle swarm optimization is initialized with a group of random particles (solutions) and then it searches for optima by updating these particles generation by generation. In every generation, each particle updates the personal best value achieved and the global best position obtained so far by any particle in the population. When a particle takes part of the population as its topological neighbours, the best value is a local best and is called lbest [13]. PSO has attracted a high level of interest during the past few years. It is very popular due to simplicity in its implementation. It requires only a few parameters to be tuned. It is computationally cheap in the updating of individual, as it requires only two simple equations as compared to mutation and crossover operators in genetic algorithms. Many researchers have worked on improving its performance in different ways, which derives several interesting variants. One of the variants [18] introduces a parameter called inertia weight w into the original PSO algorithm, which is used to balance the global and local search capabilities. There are numerous variants for the PSO algorithm but solving multidimensional problems is still the main deficiency of the standard PSO. Many problems handled by PSOs are often having a single global optimum in single objective problems. In the initial PSO proposed by Ref. [11], each particle in a swarm population adjusts its position in the search space based on the best position it has found so far, and the position of the known best-fit particle in the entire population (or neighbourhood) [14]. PSO has recently been extended to deal with multi-objective optimization problems. During the past few years, researchers focused on how to modify PSO to handle multiple objective optimization problems and have proposed multi-objective particle swarm optimization [2,9] algorithm to solve such problems. Many real world problems are dynamic, i.e., they change over time. In such cases, the optimization algorithm has to track a moving optimum [5,6,19]. 5. Proposed technique PSO can handle both continuous as well as discrete variable problems. The implementation of PSO is very easy and few lines of code are required for implementation. It is also computationally inexpensive in terms of memory as well as speed and is suitable
H. Ali et al. / Applied Soft Computing 12 (2012) 1913–1928
1919
Fig. 6. Number of clusters vs. transmission range in case of WCA, CLPSO, and MOPSO in 300 m × 300 m area by fixing nodes from 30 to 60.
for multi-objective optimization. These features suggest that PSO is a potential algorithm for optimizing clustering in a mobile ad hoc network. In this work, we use a multi-objective particle swarm optimization algorithm to solve the problem of clustering in a mobile ad hoc network. Each particle in MOPSO represents coordinates of N number of cluster-heads. The proposed MOPSO algorithm is composed of the following steps as shown in Table 1. MOPSO starts with population P0 of N randomly generated cluster-heads vector T, which has a unique ID in the network. Each vector T covers the whole network for communication. It is important to note that each of these particles has the following characteristics: (1) completeness, and (2) uniqueness. It means that each particle covers the whole network as well as has the unique cluster-heads. For each solution the objectives are calculated using the respective equations. First of all we find the neighbours of the cluster-head, which is at first position in the cluster-heads vectors T and calculate the energy consumption of that cluster-head, mobility, and transmission range. In the same way we calculate all objectives for all cluster-heads. The degree difference is calculated for each cluster-head by the equation = |d − ı| where is degree difference, d is the total number of clusterhead neighbours and ı is a predefined threshold. In the same way we calculate the objectives for all cluster-heads in a single solution in the population. After that we sum up all the values of each objec-
tive of cluster-heads. These summations are the overall objective values of a single solution in a population. In the same manner we calculate the objectives of all the population. After finding the objective values, the comparison of current objective values and old objective values is taken place to find the personal best cluster-heads vector. Non-domination sorting is used for optimal Pareto front, which is used for global best cluster-heads vector. Velocity of each individual is calculated with the help of current positions, personal best positions of the cluster-heads of the current individual and the positions of global best cluster-heads vector positions. The current positions and the velocity of each clusterhead in the current vector are used for new cluster-heads vector. After comparison an individual is selected from new cluster-heads vector or the current cluster-heads vector. This process is pictorially shown in Fig. 2.
6. Experimentation and evaluation In this section, we describe the experimental setup and the results of our experiments performed for comparison of the proposed technique with other techniques for clustering in mobile ad hoc networks.
1920
H. Ali et al. / Applied Soft Computing 12 (2012) 1913–1928
Fig. 7. Number of clusters vs. transmission range in case of WCA, CLPSO, and MOPSO in 400 m × 400 m area by fixing nodes from 30 to 60.
6.1. Experimental setup We have implemented the proposed algorithm in MATLAB 7.8.0. We conducted the experiments using a machine with 1.75 GHz dual processors and 512 MB of RAM. We performed experiments of M different nodes on an initial 100 m × 100 m grid. All the nodes can move in all possible directions with displacement varying uniformly between 0 and maximum value (max disp). The transmission range of each node varies from 10 to 60. In our experiments, M is varied between 20 and 60. The threshold for degree difference is set to 10. This restriction will ensure load balancing for an ad hoc network. The parameters of MOPSO and CLPSO are initialized as follows: • • • •
The population size is set to 100; The maximum generations are set to 150; The inertia weight w is set to 0.694; The learning factors c1 and c2 are set to 2.
We compare the MOPSO-based clustering with two other wellknown algorithms for wireless networks clustering, i.e., weighted clustering algorithm and comprehensive learning particle swarm optimization based clustering. The same values of all different parameters are used for the three algorithms. The results are
obtained after performing ten simulations of each algorithm and then taking their averages.
6.2. Experimental results The multi-objective evolutionary algorithms are very useful in case of conflicting objectives. In this problem the degree difference and energy consumption are conflicting objects, which are shown in Fig. 3. We compare the performance of the proposed approach with other two clustering algorithms by using three performance metrics: (i) the number of cluster-heads, (ii) energy consumed in a network, and (iii) load balance factor (LBF). The experimental results have been produced by varying the transmission range, number of nodes in the network, grid size, and the displacement. The dominant set in a network defines the number of clusterheads in the network. The energy consumed in a network is calculated by adding the energy consumed within a cluster and from cluster-head to the receiver. Load balance factor is a ratio between the actual number of neighbours of the cluster-head and the number of neighbours achieved by the algorithm. These parameters are studied by varying the transmission range, number of nodes in the network, grid size, and the maximum displacement.
H. Ali et al. / Applied Soft Computing 12 (2012) 1913–1928
1921
Fig. 8. Number of clusters vs. network nodes in case of WCA, CLPSO, and MOPSO in 100 m × 100 m area with transmission range fixing from 10 to 40.
6.2.1. Number of clusters vs. transmission range We conduct the experiments to find the number of clusters against the transmission range varying from 10 m to 60 m by fixing the number of nodes. We obtain four different solutions by fixing the number of nodes to 30, 40, 50, and 60, using the grid size as 100 m × 100 m. Results are also produced by varying the grid size from 100 m × 100 m to 400 m × 400 m. We use average number of clusters as the performance metric. As can be seen in Fig. 4, our proposed algorithm based on MOPSO finds a range of solutions against each transmission range to cover the whole network as compared to WCA and CLPSO in the same environment, i.e., 100 m × 100 m. The numbers of clusters are less than WCA and CLPSO. We conduct the experiments by varying the nodes from 30 to 60. In most of the cases, MOPSO finds minimum number of clusters as compared to WCA. The MOPSO also gives a diversity of solutions at each point, which gives a choice to select the solution that performs best according to the situation of the network. Now we change the network area from 100 m × 100 m to 200 m × 200 m. The results are shown in Fig. 5; we can see that the CLPSO and WCA provide almost same number of solutions in all cases. It is to be noted that when the transmission range is very small the numbers of solutions are same and in many cases only one solution is available. The reason behind this scenario is that with minimum transmission range all the nodes are almost isolated from each other, so every node is a cluster-head in that case.
As the transmission range increases the numbers of solutions increase in case of MOPSO. In this case MOPSO also performs better than the other two algorithms in all cases with a variety of solutions. Now we change the network area to 300 m × 300 m. If we see Fig. 6(a) and (b), the number of clusters are almost same up to transmission range 25. It is because the network area is very large and the number of nodes is relatively small. So we can say that a direct relation is available between the network area and the number of solutions when we fix the transmission range. It is also found that the number of solutions increases as transmission range increases. MOPSO still performs better than other two algorithms when the network area increases to 300 m × 300 m. Now we change the network area to 400 m × 400 m. In Fig. 7(a) the number of clusters are almost same up to the transmission range 50. Whereas, in Fig. 7(b–d), the MOPSO algorithm performs better because we increase the number of nodes, so there are many cluster-heads that have their neighbours in the network.
6.2.2. Number of clusters vs. network nodes We conduct the experiments to find the number of clusters against the number of nodes in a network varying from 20 to 60, by fixing the transmission range. We obtain four different solutions by fixing the transmission range as 10, 20, 30, and 40.
1922
H. Ali et al. / Applied Soft Computing 12 (2012) 1913–1928
Fig. 9. Number of clusters vs. network nodes in case of WCA, CLPSO, and MOPSO in 200 m × 200 m area with transmission range fixing from 10 to 40.
Results are produced by varying the grid size from 100 m × 100 m to 400 m × 400 m. We evaluate the performance of the three algorithms by keeping the transmission range constant and increasing the number of nodes. Fig. 8 shows that the proposed algorithm works better than the other two algorithms in terms of producing number of solutions and the average number of clusters. This shows the flexibility and robustness of the algorithm in terms of the parameters setting. The results in Fig. 8 are produced by fixing the transmission range as 10, 20, 30, and 40 and the grid size as 100 m × 100 m. Figure also shows that as the transmission range increases the MOPSO performance also increases. So, we can say that the MOPSO performs much better in case of dense networks. Fig. 9 shows the results of number of clusters against network nodes when the grid size increases to 200 m × 200 m, and fixing the transmission range to 10, 20, 30, and 40. If we compare Figs. 8 and 9, we observe that as the grid size increases, the number of clusters also increases, which shows the direct relation of the network size with the number of clusters. Fig. 10 shows the relation of number of clusters against the network nodes. These results are obtained by fixing the grid size to 300 m × 300 m and transmission range to 10, 20, 30 and 40. As we limit the degree of cluster-heads, the number of clusters increases
as the number of nodes increases. In some cases the numbers of clusters are less when we increase the transmission range, which is due to increase in the degree of the cluster-head. If we see Fig. 10(a) and (b), we find that all algorithms produce almost equal number of clusters because at transmission ranges 10 and 20 different nodes made isolated groups. As the transmission range increases, MOPSO performs better than the other algorithms. If we observe the number of clusters when the transmission range is 40 and nodes in the network are 60, we find that MOPSO produces ((26 − 20)/26) × 100 = 23% less number of clusters than the other algorithms. MOPSO also performs better in all cases. Fig. 11 shows the results in case of grid size 400 m × 400 m and taking the value of transmission range as 10, 20, 30 and 40. There is a direct relation between the distances of the nodes from each other and the grid size. As the grid size increases, the distance between the nodes also increases which leads to the isolation of nodes from each other. If all the nodes are isolated from each other then all the algorithms must produce the same number of clusters. If we see Fig. 11, almost all the algorithms are producing the same number of clusters because with grid size 400 m × 400 m and transmission ranges up to 60 all the nodes are isolated. The network of Fig. 11(d) is more dense than Fig. 11(a–c), so the MOPSO algorithm performs better than other algorithms. We can easily claim
H. Ali et al. / Applied Soft Computing 12 (2012) 1913–1928
1923
Fig. 10. Number of clusters vs. network nodes in case of WCA, CLPSO, and MOPSO in 300 m × 300 m area with transmission range fixing from 10 to 40.
that MOPSO is better than the other algorithms for our clustering problem.
posed MOPSO algorithm provides multiple solutions in each case that shows its significance.
6.2.3. Number of clusters vs. grid size Fig. 12 shows the relation between the number of clusters and the grid size by fixing the network nodes and transmission range. As we can see the number of clusters increases as the grid size increases due to increase of distance between nodes, which isolate the nodes from each other. Fig. 12(a–d) shows that increase in transmission range decreases the number of clusters at each grid size. The MOPSO decreases the number of clusters up to 30%, which leads to efficient clustering. Fig. 12 also shows that the MOPSO performs better in the case of dense environment.
6.2.5. Energy consumption In our experiments, we use the radio model as discussed in Ref. [20], which is the first order radio model. To run the transmitter and receiver circuitry, this model uses Eelec = 50 nJ/bit and for amplifier it uses Eamp = 100 pJ/bit/m2 . These power levels are suitable for Eb /No . The energy loss of the node is proportional to r2 (where r is distance between the transmitter and receiver nodes). Thus, to transmit a n-bit message the total energy consumed is calculated as follows: The energy required at receiver node = energy consumed in circuitry + energy consumed to transmit a n-bit message from transmitter to receiver
6.2.4. Number of clusters vs. displacement Fig. 13 shows the different variations of network nodes and maximum displacement. The transmission range is kept constant as 30. Fig. 13 shows that the number of cluster-heads is almost the same for different values of displacement particularly for larger values of numbers of nodes. This is because, mobility of nodes just changes the configuration of clusters but the cluster size remains the same. Moreover, the pro-
ET (n, d) = ETx (n, d) + ERx (n, d)
(3)
where ETx (n, d) = Eelec × n + Eamp × n × d2
(4)
and ERx (n, d) = Eelec × n
(5)
1924
H. Ali et al. / Applied Soft Computing 12 (2012) 1913–1928
Fig. 11. Number of clusters vs network nodes in case of WCA, CLPSO, and MOPSO in 400 m × 400 m area with transmission range varying from 10 to 40.
If we see Eqs. (4) and (5), the total energy consumption depends upon the distance between the transmitter and the receiver nodes as well as the number of operations required to transmit and receive the massage. To evaluate the performance, we vary the nodes from 30 to 60 in a play field of size 100 m × 100 m. The receiver is located at position (50, 110). We assume the program stops running when the number of iterations is 150. Fig. 14 shows the energy consumed in case of WCA, CLPSO, and MOPSO when grid size is 100 m × 100 m and the transmission range varies from 10 to 60 while fixing the number of nodes to 30, 40, 50 and 60. The results show that as the transmission range increases, energy consumption also increases because the number of clusters decreases. The maximum energy consumed is when the numbers of clusters are equal to the numbers of nodes or there is only one cluster. So we must find the optimum number of clusters, which consume less energy to perform their functions. The energy consumed by the different algorithms is shown in the following tables. Tables 2 and 3 show the total energy saving of the best algorithm from the 2nd best algorithm in percentage (%). Table 2 shows that MOPSO consumed less energy 10 out of 11 times and energy saving is up to 13%. Table 3 shows that when the number of nodes are 40 the MOPSO performs better 8 out of 11 times and the energy saving
is up to 27%. So, we can easily say that MOPSO performs better than the other single-objective algorithms for clustering in an ad hoc network. 6.2.6. Load balance factor Load balance factor is used to quantify how well a cluster-head is balanced. In an ideal case every cluster-head must handle equal number of nodes, but it is very difficult to maintain a perfectly load-balanced system at all times. The main reason is the frequent detachment and attachment of neighbours from the cluster-heads. The cardinality of the cluster size represents the load of a clusterhead. In Ref. [4], the LBF is defined as the inverse of the variance of the cardinality of the clusters. Thus, LBF =
i
nc (xi − )2
(6)
where nc is the number of cluster-heads, xi is the cardinality of cluster i, and = N − nc /nc is the average number of neighbours of a cluster-head (being the total number of nodes in the system). In this equation it is clear that a higher value of LBF signifies a better load distribution and it tends to infinity for a perfectly balanced system.
H. Ali et al. / Applied Soft Computing 12 (2012) 1913–1928
1925
Fig. 12. Number of clusters vs. Grid size in case of WCA, CLPSO, and MOPSO when node = 40 and transmission range varying from 30 to 60.
Fig. 13. Number of clusters vs. displacement in case of WCA, CLPSO, and MOPSO in 100 m × 100 m area when nodes are 40 and 60 while transmission range is 30.
1926
H. Ali et al. / Applied Soft Computing 12 (2012) 1913–1928
Fig. 14. Energy consumed in case of WCA, CLPSO, and MOPSO in case of 100 m × 100 m area and transmission range varying from 10 to 60 and number of nodes from 30 to 60. Table 2 Energy consumed by different algorithms when nodes = 30. Energy consumed by the network in (J)*
Transmission Range
10 15 20 25 30 35 40 45 50 55 60 *
Saving in energy consumption (%)
MOPSO
CLPSO
WCA
((high value − low value)/high value) × 100
0.0374 0.0365 0.0375 0.0394 0.0403 0.0390 0.0403 0.0365 0.0413 0.0405 0.0401
0.0379 0.0373 0.0385 0.0407 0.0408 0.0421 0.0445 0.0447 0.0435 0.0445 0.0471
0.0373 0.0365 0.0396 0.0434 0.0407 0.0397 0.0428 0.0393 0.0456 0.0410 0.0466
((0.0374 − 0.0373)/0.0374) × 100 = 0.27 ((0.0365 − 0.0365)/0.0365) × 100 = 0.00 ((0.0385 − 0.0375)/0.0385) × 100 = 2.60 ((0.0407 − 0.0394)/0.0407) × 100 = 3.20 ((0.0407 − 0.0403)/0.0407) × 100 = 0.98 ((0.0397 − 0.0390)/0.0397) × 100 = 1.76 ((0.0428 − 0.0403)/0.0428) × 100 = 5.84 ((0.0393 − 0.0365)/0.0393) × 100 = 7.12 ((0.0435 − 0.0413)/0.0435) × 100 = 5.06 ((0.0410 − 0.0405)/0.0410) × 100 = 1.22 ((0.0466 − 0.0401)/0.0466) × 100 = 13.95
The unit of energy is Joule (J).
Eq. (6) is only suitable when we consider just the load balance factor. But it fails when we want to optimize not only the LBF but also the number of clusters at the same time. We illustrate this with an example. Case 1: Algorithms/objectives
Algorithm 1
Algorithm 2
No. of clusters 2 (xi − )
5 2
5 3
i
Case 2: Algorithms/objectives
Algorithm 1
Algorithm 2
No. of clusters 2
5 3
8 3
i
(xi − )
In case 1, LBF1 = 5/2 = 2.5 and LBF2 = 5/3 = 1.67 So, in this case the algorithm 1 is better than the algorithm 2. This solution fulfils our requirement because algorithm 1 is more balanced than algorithm 2 although it has the same number of solutions.
H. Ali et al. / Applied Soft Computing 12 (2012) 1913–1928
1927
Table 3 Energy consumed by different algorithms when nodes = 40. Transmission Range
10 15 20 25 30 35 40 45 50 55 60 *
Energy consumed by the network in (J)*
Saving in energy consumption (%)
MOPSO
CLPSO
WCA
((high value − low value)/high value) × 100
0.0560 0.0560 0.0590 0.0595 0.0556 0.0553 0.0581 0.0648 0.0571 0.0750 0.0537
0.0573 0.0590 0.0614 0.0630 0.0625 0.0608 0.0629 0.0668 0.0709 0.0777 0.0779
0.0564 0.0568 0.0576 0.0606 0.0632 0.0569 0.0569 0.0663 0.0743 0.0742 0.0741
((0.0564 − 0.0560)/0.0564) × 100 = 0.71 ((0.0568 − 0.0560)/0.0568) × 100 = 1.41 ((0.0590 − 0.0576)/0.0590) × 100 = 2.37 ((0.0606 − 0.0595)/0.0606) × 100 = 1.81 ((0.0625 − 0.0556)/0.0625) × 100 = 11.04 ((0.0569 − 0.0553)/0.0569) × 100 = 2.81 ((0.0581 − 0.0569)/0.0581) × 100 = 2.06 ((0.0663 − 0.0648)/0.0663) × 100 = 2.26 ((0.0709 − 0.0571)/0.0709) × 100 = 19.46 ((0.0750 − 0.0742)/0.0750) × 100 = 1.06 ((0.0741 − 0.0537)/0.0741) × 100 = 27.53
The unit of energy is Joule (J).
Fig. 15. Load Balance Factor in case of WCA, CLPSO, and MOPSO when grid size is 100 m × 100 m and transmission range varying from 10 to 60 and number of nodes are 30–40.
In case 2, LBF1 = 5/3 = 1.67 and LBF2 = 8/3 = 2.67 This shows that the algorithm 2 is better than the algorithm 1. But actually the algorithm 1 is better than the algorithm 2, because it has less number of clusters. So algorithm 1 is more optimized than algorithm 2. The above discussion clearly shows that Eq. (3) is not suitable when we want to optimize both the number of clusters and the load balance factor. To overcome this problem we modify Eq. (6) of LBF as: LBF =
nc ×
1
i
(xi − )2
(7)
Now we calculate the LBF of above cases according to Eq. (7). In case 1, LBF1 = 1/(5 × 2) = 0.01 and LBF2 = 1/(5 × 3) = 0.067 So, in this case the algorithm 1 is better than the algorithm 2. This solution fulfils our requirement because algorithm 1 is more balanced than algorithm 2 although it has the same number of solutions. In case 2, LBF1 = 1/(5 × 3) = 0.067 and LBF2 = 1/(8 × 3) = 0.042 This now shows that the algorithm 1 is better than the algorithm 2, which confirms the desired results. It is clear from the above results that Eq. (7) is more suitable than Eq. (6) in case of multi-objective criteria optimization. Load balance factor is shown in Fig. 15 in case of WCA, CLPSO, and MOPSO. The LBF is calculated when the grid size is 100 m × 100 m, transmission range varying from 10 to 60, and number of nodes are 30 and 40. The MOPSO gives more balanced clusters
than the WCA and CLPSO as we increase the transmission range as well as it gives a variety of solutions. Both graphs show that MOPSO is more effective as the number of neighbours reaches the threshold value and performs better than WCA and CLPSO in terms of balancing the load in the network. 7. Conclusion and future work In this paper, we have presented a multi-objective particle swarm optimization algorithm for energy-efficient clustering in mobile ad hoc networks (MANETs). One of the main constraints of these networks is the limited battery power. The major challenge for the researchers is to make these networks energy-efficient as much as possible. In the proposed approach we have used clustering for providing the energy-efficient solution. Moreover, the proposed approach has the ability to find out multiple optimal solutions, which provides the flexibility of the solutions. The users can choose a solution according to their needs. By minimizing the number of clusters we can reduce the routing cost of a packet. It also makes the routing energy-efficient because less number of nodes are involved for routing a packet. The evolutionary capability of the algorithm allows it to search large search space. It also has the advantage of dynamically adjusting objective function values instead of specifying by the user. The simulation results show that it is an effective and flexible approach. We compared the results with two other well-known clustering algorithms, i.e., WCA and CLPSO-based clustering. The proposed MOPSO-based approach outperforms these two algorithms in finding optimal number of clusters as well as providing multiple options for the user.
1928
H. Ali et al. / Applied Soft Computing 12 (2012) 1913–1928
In future we will try to optimize the different parameters used in the algorithm. Further, more objectives can be added in the algorithm. We can also change our environment by making the number of nodes dynamic. Another future direction is to use other multi-objective evolutionary techniques and make a comprehensive comparison among them. Acknowledgements The authors thank the Higher Education Commission (HEC) Pakistan for supporting this work through the Indigenous PhD Fellowship Program. The authors are also thankful to the anonymous reviewers for their valuable suggestions and feedback. References [1] J.J. Liang, A.K. Qin, P.N. Suganthan, S. Baskar, Comprehensive learning particle swarm optimizer for global optimization of multimodal functions, IEEE Transactions on Evolutionary Computation 10 (June (3)) (2006) 281–295. [2] J.E. Alvarez-Benitez, R.M. Everson, J.E. Fieldsend, A MOPSO algorithm based exclusively on Pareto dominance concepts, in evolutionary multi-criterion optimization, vol. 3410, Springer, Berlin/Heidelberg, 2005, pp. 459–473. [3] W. Shahzad, F.A. Khan, A.B. Siddiqui, Clustering in mobile ad hoc networks using ´ ezak, ˛ comprehensive learning particle swarm optimization (CLPSO), in: D. Sl et al. (Eds.), Communication and Networking, vol. 56, Springer, Berlin Heidelberg, 2009, pp. 342–349. [4] M. Chatterjee, S.K. Das, D. Turgut, WCA: a weighted clustering algorithm for mobile ad hoc networks, Cluster Computing 5 (April (2)) (2002) 193–204. [5] D.J. Baker, A. Ephremides, The architectural organization of a mobile radio network via a distributed algorithm, IEEE Transactions on Communications 29 (January (11)) (2003) 1694–1701. [6] M. Gerla, J.T.C. Tsai, Multi-cluster, mobile, multimedia radio network, Wireless Networks 1 (September (3)) (1995) 255–265. [7] S.K. Das, R. Elmasri, B. Turgut, D. Turgut, Optimizing clustering algorithm in mobile ad hoc networks using genetic algorithmic approach, in: Proceedings of GLOBECOM’02, vol. 1, Taipei, Taiwan, 2002, pp. 62–66.
[8] I.I. Er, W.K.G. Seah, Mobility-based D-hop clustering algorithm for mobile ad hoc networks, in: IEEE Wireless Communications and Networking Conference, vol. 4, Atlanta, USA, 2004, pp. 2359–2364. [9] C.A. Coello Coello, G.T. Pulido, M.S. Lechuga, Handling multiple objectives with particle swarm optimization, IEEE Transaction on Evolutionary Computation 8 (3) (2004) 256–279. [10] K. Deb, A. Pratap, S. Agarwal, T. Meyarivan, A fast and elitist multiobjective genetic algorithm: NSGA-II, IEEE Transaction and Evolutionary Computation 6 (2002) 182–197. [11] J. Kennedy, R.C. Eberhart, Particle swarm optimization, in: Proceeding Of IEEE International conference on Neural Networks, vol. IV, IEEE Service Center, Piscataway, 1995, pp. 1942–1948. [12] R. Dewri, N. Poolsappasit, I. Ray, D. Whitley, Optimal security hardening using multi-objective optimization on attack tree models of networks, in: Proceedings of the 14th ACM conference on Computer and Communications Security (CCS’07), Alexandria, Virginia, 2007. [13] Y. Valle, G.K. Venayagamoorthy, S. Mohagheghi, J.-C. Hernandez, R.G. Harley, Particle swarm optimization: basic concepts, variants and applications in power systems, IEEE Transactions on Evolutionary Computation 12 (2008) 11–195. [14] J. Kennedy, The particle swarm: social adaptation of knowledge, in: Proceedings of IEEE International Conference on Evolutionary Computation IEEE Service Center, Piscataway NJ, Indianapolis, Indiana, 1997, pp. 303–308. [15] J. Kennedy, The behavior of particles, in: Proceedings of 7th Annual Conference on Evolutionary Programming, vol. 1447, San Diego, USA, 1998, pp. 581–589. [16] W. Leong, G.G. Yen, Dynamic population size in pso-based multi-objective optimization, in: IEEE Congress on Evolutionary Computation, Canada, 2006, pp. 1718–1725. [17] S. Mostaghim, J. Teich, Covering pareto-optimal fronts by subswarms in multi-objective particle swarm optimization, in: Congress on Evolutionary Computation, vol. 2, 2004, pp. 1404–1411. [18] D. Parrott, X. Li, Locating and tracking multiple dynamic optima by a particle swarm model using speciation, IEEE Transactions on Evolutionary Computation 10 (2006) 440–458. [19] M.R. AlRashidi, M.E. El-Hawary, A survey of particle swarm optimization applications in electric power systems, IEEE Transactions on Evolutionary Computation 13 (4) (2009) 913–918. [20] W.R. Heinzelman, A. Balakrishnan, H. Chandrakasan, Energy-efficient communication protocol for wireless microsensor networks, in: Proceedings of the 33rd Hawaii International Conference on System Sciences, vol. 8, 2000, p. 8020.
