A New Method for Clustering Wireless Sensor Networks to Improve the Energy Consumption

Document Type: Research Paper

Authors

Electrical & Electronic Engineering Department, Shahed University, Tehran, IRAN

Abstract

Clustering is an effective approach for managing nodes in Wireless Sensor Network (WSN). A new method of clustering mechanism with using Binary Gravitational Search Algorithm (BGSA) in WSN, is proposed in this paper to improve the energy consumption of the sensor nodes. Reducing the energy consumption of sensors in WSNs is the objective of this paper that is through selecting the sub optimum sensors as Cluster Heads (CHs) to eliminate the number of transmissions and subsequently to attain more network lifetime. Clustering mechanism consist of two phases: CH selection and cluster formation. One of the major problems affecting energy consumption in WSN is cluster head selection. The proposed method is used for selecting suboptimum cluster head nodes. However, selecting CHs is not an easy subject. In this paper this issue will be discussed based on the residual energy or distance from Base Station (BS) or both of them with considering BS coordinate by BGSA algorithm. Simulation results show that if the BS is not very far from the network area, considering distance and residual energy for selecting CHs by proposed method can be efficient for reducing energy consumption and prolonging lifetime.

Keywords


Wireless Sensor Network (WSN) belongs to the Low Range Wireless Personal Area Network (LR-WPAN) [1]. It consists of hundred to thousand sensor nodes in the sensing region. These sensors are capable of sensing, computing and communication. WSN gets its popularity, because of various attractive characteristics of sensor nodes. The characteristics of sensor nodes are: robustness, reliability, flexibility, adaptability, tiny, low cost, less weight, self-configuring and can withstand in any harsh environment. This makes the sensor nodes to be applied in various real-time applications including health monitoring of patients in hospitals, habit monitoring, environmental monitoring, structural monitoring, military applications etc [2]. An arrangement of sensor nodes into different virtual groups is known as clustering. Each cluster comprises of CH and its members. A CH generally serves like a leader for its cluster, performing intra cluster transmission arrangement, data sensing, and so on. The cluster heads can summarize the data and send it to the data center or Base Station (BS) [3]. Clustering of nodes is an energy efficient approach for WSN. In clustering, nodes are grouped to form clusters. Each cluster has at least one cluster head. Instead of sending data directly to BS, nodes send data to their corresponding CH via single or multiple hop communication. CH receives data of all nodes in clusters and aggregates it. CH sends aggregated data to BS again via single or multiple-hop. After certain time period (round time) re-clustering of nodes is performed [4]. Clustering of nodes avoid long distance communication of nodes to BS. Only few nodes i.e. CHs are sending data over long distance. Avoidance of long distance communication is preserving energy of sensor nodes [5].Clustering is performed by assigning each sensor nodes to a specific CH. All communication to (form) each sensor nodes is carried out through its corresponding CH node. Obviously one would like to have each sensor to communicate with the closest CH node to conserve its energy, however CH nodes can usually handle a specific number of communication channels. Therefore, there is a maximum number of sensors that each CH node can handle [6]. Several clustering methods such as weighted clustering [7], hierarchal clustering [8] and dynamic clustering algorithms [9] have been proposed to organized nodes as a cluster. Most algorithms elect CHs based on certain weights or iteratively optimize a cost function or use heuristic to generate minimum number of clusters. The Distributed Clustering Algorithm (DCA) assumes quasi-stationary nodes with real-valued weights [10].   
    The hierarchal clustering scheme uses spanning tree-based approach to produce cluster with certain properties. However, energy efficiency is not addressed in this work. In [11], the authors have proposed an emergent algorithm that iteratively tries to achieve high packing efficiency, however negotiation among nodes to be CH and join cluster based on degree and proximity leads to high amount of communication overhead, thus wastage energy. Research related to WSNs is not new and several related problems have been exposed and addressed within the last few years. This research effort has been categorized into three main areas: clustering algorithms, data dissemination techniques and routing protocols [12]. In [13] a hierarchal clustering algorithm for sensor networks, the Low Energy Adaptive Clustering Hierarchy (LEACH) was introduced. The idea is to form clusters out of sensor nodes based on the received wireless signal strength. The purpose of this approach is to maintain the energy of the node when there is gathered data which is transmittable to the sink, which this could only be done by cluster heads rather than by all sensor nodes. Accordingly, less energy would be consumed in comparison with transmitting one data at a time. LEACH randomly selects a number of sensor nodes as cluster heads and then rotates this role to uniformly distribute the energy load among the sensor in the network. Each elected cluster head broadcasts an advertisement message to the rest of the nodes in network informing them of their new role as cluster heads. All the non-cluster head nodes, after receiving this advertisement, choose the cluster to which they intend to belong to. This decision is based on signal strength of the received advertised message. In addition, it is not obvious how the number of the predetermined CHs is going to be uniformly distributed through the network. Therefore, there is a possibility that the elected CHs will be more concerned in one part of the network over other parts. As a consequence of this, some nodes will not have any CHs in their neighborhood and will not be covered. In order to mitigate some of these problems Multi-hop LEACH was proposed in [13]. P-LEACH was proposed in [14] as an improvement on LEACH. It partitiones the network into certain regions and according to the number of sensors in each regions, partitions are change after that in each regions CHs are selected and clusters formed.P-LEACH minimizing the cluster and CHs unevenly in number of cluster head and nodes. Clustering problem can be viewed as a search problem through a typically NP- hard solution space. In this sense, some researches have adopted nature-inspired approaches for WSNs. The Gravitational Search Algorithm is the latest nature inspired algorithm proposed by E.Rashedi to solve the optimization problems based on the Law of gravity. Many researchers have applied the gravitational search algorithm on large number of problems because it requires only two parameters and having ability to find near global optimum solution and provides better results as comprise to other nature inspired algorithms. Esmat Rashedi has developed the binary version of the orginal GSA for binary optimization problems in which updating position means to which between 0 and 1 rather than contiguous. The proposed algorithm is used pareto optimality function with standard GSA to solve the multi objective problems [15]. In [16] multi objective version of GSA algorithm is used for solving the relay node placement problem in wireless sensor networks and finding the relay node place in network. Furthermore the GSA algorithm has different application in various field such as: using GSA for the optimal tuning of fuzzy controlled servo systems characterized by second-order models with an integral component and variable parameters [17], solving the NP-hard problem that is related to clustering problem and proposing mimetic GSA (MGSA) algorithm [18], using gravity method to optimize the parameters of sensor monitoring selection for each round in a point coverage network [19], solving non-linear optimization problem in WSN by using GSA algorithm [20] and also the GSA algorithm was used in WSN problems by utilizing the BGSA algorithm in WSN and clustering the network elaborated on this research.

    The remainder of this paper is organized as follows: Section II discusses clustering in wireless sensor networks, Section III presents the proposed method for clustering in WSN. Section IV presents the simulation results. Finally, section V presents the conclusion.

I.     clustering in wireless sensor network

A.     Clustering

An arrangement of sensor nodes into different virtual groups is known as clustering. Each cluster comprises of CH and its members. A CH generally serves like a leader for its cluster, performing intra cluster transmission arrangement, data sending, and so on. The cluster heads can summarize the data and send it to the data center or BS as a single packet, thus reducing the overhead from packet headers. The CHs rotate randomly in each epoch within the network for load balancing. In each round of the cluster formation phase, the network needsto select cluster heads and transfers the aggregated data to BS. For electing a cluster head, the following questions are to be considered [3]:

  • Who will initialize the cluster head selection?
  • What are the parameters necessary for deciding the role of a sensor node?
  • Which sensor nodes will be nominated as cluster heads?
  • Clustering is very much essential for WSNs for the following reasons.
  • Reduces energy consumption by improving bandwidth utilization.
  • Load balancing for even distribution of sensors.
  • “Re-clustering”when fault tolerance occure.CH transmits only aggregated data to the data sink node.
  • Reducing number of nodes taking part in transmission to BS by electing CH.
  • Scalability for large number of nodes.

B.     Binary Gravitational Search Algorithm (BGSA)

Inspired from the law of gravitation and the law of motion, E. Rashedi et al. developed a stochastic optimization algorithmcalled GSA. By Newton’s universal law of gravitation objects, “objects in the universe attract each other with a force F which is directly proportional to the product of their masses M1 and M2 and inversely proportional to the square of distance between them” as follows:

                                                                                                                      (1)

Where G denotes the gravitational constant and R denotes the Euclidean distance between M1 and M2.

The law of motion gives a relationship between an object’s mass M, its acceleration a, and the force F applied on it’s as follows:

                                                                                                                                      (2)

GSA combines both these laws and considers every object as an agent having a position, velocity, acceleration, and mass. Eventually, all agents will get attracted towards the heaviest agent. The performance of an agent is measured by its mass. Heavy mass represents an optimal solution for the given problem. The BGSA algorithm can be explained in 4 steps.  

Step 1: Population Initialization          
Initialize N agents in an n-dimensional search space with random positions and velocities. The position and velocity X and V respectively of agent at time t are define as follows:

 

                                                                                                         (3)

                                                                                                            (4)

 

Step 2: Fitness Evaluation

Evaluate the fitness function at each agent location. For a maximization problem, the worst fitness value will be the least among the fitness values of all agents and best value will be the highest one.

                                                                                                                (5)

                                                                                                      (6)

Step 3: Updating and Calculations

Since universe is continuously, the reduced force of attraction between all objects will cause G to reduce over time. Hence, G is calculated as a decrementing function of time (t) and its initial value

() [19].

   G (t) = G (,t)                                                                                                                                 (7)

The fitness values obtained from Eq. (5-6) are used to calculate mass of every agents and is normalized as given:

                                                                                         (8)

                                                                                                                 (9)

Where the force applied on agent i by agent j using Eq. (10), and d denotes the dimension.

                                                                  (10)

Where  is the Euclidean distance between agent iand agent j and.Calculate the force applied by all agents on agent ias follows:

 

                                                                                                         (11)

 Where randj is random number and using the mass of agent iand the force, its acceleration is calculated as follows:

                                                                                                                (12)

Velocity of an agent is updated using its acceleration and using this velocity, the agent position can also be updated.

                                                                                            (13(

                                                                                                 (14(

Step 4: Repeat Steps 2-3

If the algorithm has reached a termination condition, such as maximum number of iteration or an error threshold, then the position of the heaviest agent is returned as the optimal solution. Else, step 2 and 3 are re-executed, and the process is repeated. The workflow of this algorithm is shown in Fig. 1 [21], [22].

    In this explanations we present a binary version of GSA. To do this, some basic concepts of GSA will be modified. In discrete binary environment, every dimension can take only 0 or 1. Moving through a dimension means that the corresponding variable value changes from 0 to 1 or vice versa. In order to introduce a binary mode for the gravitational algorithm, the updating procedure of the force, acceleration and velocity may be considered similar to the continuous algorithm (Eqs. 12-14). Themain difference between continuous and binary GSA is that in the binary algorithm, the position updating means a switching between “0” and “1” values. This switching need to be done according to the mass velocity. Our idea is to update the position in a manner that the current bit value is changed

with a probability that is calculated according to the mass velocity. In other words, BGSA updates the velocity based on Eq. 13 and considers the new position to be either 1 or 0 with the given probability [22].

II.     Proposed method for clustering in WSN

 

For clustering sensors in WSN at first we need to select CHs. BGSA is the optimization algorithm that selects sub optimum CH set.For selecting CHs we need algorithm that at first based on fitness

 

 

 

Fig. 1. Binary Gravitational Search Algorithm Workflow

function and second can search fast and good between possible answers. BGSA algorithm is the algorithm that selects CHs based on fitness function that can defined based on different parameter(s).Also the struction of algorithm caused to achievethe response (CHs) with minimum iteration of algorithm. In the current paper, BGSA with considering average of residual energy in each partition was used because the CH sets that are selectedhave the residual energy more than averag. It is worth bearing in mind that the calculation space of BGSA algorithm is different from network space, more specifically in BGSA algorithm we have agents that are distributed in space for calculating the values such as mass, velocity, acceleration etc. And finally selects better agent as a solution thusmentioned value are defined for agents not sensors. At the end of computation we have a binary vector that1 valuepointed to the sensors that select as CHs. In BGSA algorithm for selecting CHs The fitness function should be defined. With defining the fitness function as equation 15 the vector of agents(sensors) with more energy have heavier finess function than other and have more probability to select as CH. The fitness function is defined as follow:           

Fitness function =                                                                                           (15)

dim is vector size and the members are the sensors that have residual energy more than average and also L is binary vector so that if vector value is 1 it means that the corresponding sensor selected as

 

 

 
   

 

 

 

 

 

 

 

 

 

 

 

 

 

Fig. 2. The Block Diagram of Proposed Method

 

CH and if 0 it was not.The flow diagram of proposed method is as Fig.1. It is important to be noted that the base station has information regarding the energy and coordination of all sensors. The clustering of sensors, by use of this method, contains five steps that is shown in Fig. 2.

 

Step 1: Partitioning network space.

In this method, the base station divides the network area into severalsubspace. The figure of partitioned network is shown in Fig. 3.

Step 2: Calculating average residual energy of sensors in each partition.

Base station calculates average of residual energy for each partition’s sensorsto can determine the candidate set.

Step 3: Determine the candidate set for cluster head in each partition.

After step two, candidate set is determined in such way that each sensor that has residual energy higher than average can be CH candidate in that partition.

Step 4:  Selection by use of BGSA in each partition.

BGSA algorithm selects cluster heads not among all sensors but only among the candidate set in each partition. In Fig. 4 CHs are shown as black points.

Step 5: Cluster formation.       
In the BGSA algorithm in evaluation step,the fitness function at each agent location is evaluating. This evaluation in our problem can be based on different parameters such as residual energy or

 

 

Fig. 3. Partitioned Network Area (m*m)

 

Fig. 4. CHs in Network Area clustered by proposed method (m*m)

 

distance from BS or other parameters. In Eq. 13 just considered residual energy as parameter for fitness function definition which is shown in Eq. 14. In this paper we consider residual energy and distance from BS simultaneously.The fitness function in Eq. 16 was considered both two parameters. In eq. 15 because just we  have one parameter  it is not  necessary to normalized  but ineq. 16

because we have two parameters with diffrent units of measurments the  and the should be normalized.

Fitness function = *                                                        (16)

Where  is residual energy sensor i in time t, dim is the dimension which is equal to the candidate set size. Candidate set is consist of sensors that are volunteer for selecting as CHs. E  is  sensor  initial

 

energy for normalize residual energy parameter, is sensor distance to BS, a1 and a2 are the best factors for achieving minimum energy consumption thatwith try and error both of them are 1, and  are network size and D is the maximum distance of sensor from BS that is calculated in Eq. 17.

 

D =                                                                                                   (17)

 

 

III.     Simulation and results

 

In our simulation, we have used MATLAB programming and compare energy consumption of proposed method with LEACH algorithm, BPSO algorithm [23], K-means algorithm [24] and BGSA algorithm.Clusteringshould be repeated for each round because if the network is clustered just one time the network energy will be finished very soon especially if CHsdo not chang in each round CHs node turning off very soon.We have used random 160-node networks for our simulations with similar parameters and the base station is located at (500, 50000)meter. The initial network parameters considered for simulation is given in Table.1. The number of the selected cluster heads in all three algorithms is fix and is equal to (n*p) numbers where n is the number of alive nodes in each round.According to Fig. 5, the residual energy of the network that is clustered by our proposed method is more than that of BGSA algorithm and other algorithms. This algorithms are utilized for CH selection and the cluster formation phase are similar in all methods. In  Fig. 6 Fuzzy K-MEANS algorithm [24-25] is compared with BGSA algorithm and intense to show that the BGSA algorithm has better performance than some of the recent clustering algorithm. In Fig. 5 we compre network residual energy of proposed method with BGSA algorithm that is just considered residual energy for CH selection and the fitness function is given in Eq. 1. X coordinate shows number round and y coordinate shows residual enegy that calculated based on residual energy summation of all nodes for each round. Distance effect on energy consumption in wireless sensor network is also studied according to Eq. 16. So we consider different location for BS and investigate the network residual energy when clustering with proposed method and realize that has relationship with BS coordination.Simulation result of this comparision is given in Fig. 7. According to the results adding distance parameter with residual energy due to Eq. 16 can be effective for networks that the BS is not very far away as shown in Fig. 8 but the BS that shown in Fig. 9 is far from network.

    Based on Fig. 7 the proposed method is efficient for the networks that their BS is not very far away. One of the reason is that if the BS is far from the network, the distance between sensors is very very less than the distance between sensors to BS, so distance can not be suitable criterion for CH

 

Fig. 5. Residual Energy of Network

 

Table 1. Network Parameters

 

Parameter

value

Simulator area

1000*1000 m2

Initial Energy

0.5J and 0.1J

Transmitted Power

50nJ

Receiving Power

50nJ

Data Aggregation Energy

5e – 0.9*(10 ^-9) J

Transmit Amplifier types

=10e – 1.2*(10 ^-9) J

=1.3e-1.5*(10 ^-9)  J

 

CH Probability

P =0.1

 

 

 

Fig. 6. Residual Energy of Network

 

 

Fig. 7. Residual energy of network

 

 

Fig. 8. Network Area (m*m), BS: (500, 2000)

 

selection. It means that distance from BS is approximatelyequal for all sensors,while residual energy of sensors are verydifferent with each other so with appending distance parameter in this network the effect of energy parameter is lessened due to Eq. 16 therefore network performance will get worse than before. But in status that BS is not very far (approximately 10 times or less) away from network similar to Fig. 8, affixing distance effect in CH selection procedure is efficacious and can diminish energy consumption. The reason is that if the CHs are closer to BS pursuant to the consumed energy formoula that is proportional to distance, residual energy is increase and this technique can be useful.

IV.     conclusion

 

The present study seeks to improve energy consumption of the network with the proposed method.In wireless sensor network it is better to have more residual energy or less consumption energy because

 

 

Fig. 9. Network Area(m*m), BS: (500, 50000)

 

in this situation the network is off later. At first we selected the CHs based on residual energy. Secondly based on distance from BS and we understanded that residual energy is more important than distance from BS in CH selection because base station is located very far from the network and the residual energy plays an important role in the cluster head selection, accordingly better nodes were selected as cluster heads than before. In this paper, the clustering conducted through BGSA algorithm improves WSNs performance and as shownin Fig 5, in our proposed method, the energy consumption of the network is much lower than other methods. And also distance from BS can play an important rule in CH selection in the networks that BS coordinate is not very far from sensors. For future research, we suggest the consideration of other possible affective criteria for selecting CHs.

[1]     S. Ramakrishnan and T. Thyagarajan, “Energy Efficient Medium Access Control for Wireless Sensor Networks,” International Journal of Computer Science and Network Security (IJCSNS), vol.9, No.6, pp. 273-279, June 2009.

[2]     J. Parvin and C. Vasanthanayaki, “Gravitational Search Algorithm Based Mobile Aggregator Sink Nodes for Energy Efficient Wireless Sensor Networks,” International conference on circuits, power and computing technologies (ICCPCT), pp. 1052-1058, 2013.

[3]     S. Nithyakalyani and S. Kumar, “Data Aggregation in Wireless Sensor Network using Nodes Clustering Algorithm–A Comparative Study,” IEEE Int. Conference on Information & Communication Technologies (ICT), pp. 508–513, April 2013.

[4]     D. Wei and H. Chan, “Clustering ad hoc networks: Schemes and classifications,” in proc. 3rd Annual IEEE Communications Society on sensor and Ad Hoc Communications and Networks, pp. 920-926, 2006.

[5]     V. Pal, G. Singh, R. Yadav, and P. Pal, “Energy Efficient Clustering Scheme for Wireless Sensor Networks: A Survey,” Journal of Wireless Networking and Communication, pp.168-174, 2012.

[6]     P. Chan, R. Sheriff, Y. Conforto and C. Tocci, “Data gathering algorithms in sensor networks using energy metrics,” IEEE Transaction on Parallel and distributed Systems, vol.13, no. 9, pp. 924-935, 2002.

[7]     M. Chtterjee, S. Karaki, and D. Turgut, “WCA: A Weighted clustering algorithm for mobile and ad hoc networks,” Journal of cluster Computing, vol. 5, no. 2, pp. 193-204, 2002.

[8]     S. Banerjee and S. Khuller, “A Clusteriavung Scheme for Hierarchical Control in Multi-hop Wireless Networks,” Twentieth Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM), vol. 2, pp. 1028-1037, 2001.

[9]     W. Chen, J. How, and L. Sha “Dynamic Clustering for Acoustic Target Tracking in Wireless Sensor Networks,” IEEE Trans. on mobile Computing, vol. 3, no. 3, pp. 258-271, 2004.

[10]  S. Basagni, “Disributed Clustering for ad-hoc Networks,” International Symposium of parallel Architectures, Algorithm and Networks) I-SPAN’99), pp. 310-315, 1999.

[11]  H. Chan and A. Perrig, “An Emergent Algorithm for Highly Uniform Cluster Formation,” Proc. of European Workshop on Wireless Sensor Networks (EWSN), pp.154-171, 2004.

[12]  R. Marjan, B. Dezfouli, K. Bakar, and M. Lee, “Multiple routing in Wireless Sensor networks survey and research challenge,” Sensors, vol. 12, pp. 650-685, 2012.

[13]  W. Heinzelman, A. Chandrakasan and H. Balakrishnan, “Energy-Efficient Communication Protocol for Wireless Microsensor Networks,” Proceedings of the 33rd Annual Hawaii International Conference on  System Sciences, 2000.

[14]  M. Rafsanjani and H. Imani, “Clustering Algorithm for Wireless Sensor Networks”, Journal of New Theory, vol. 3, pp. 20-29, 2015.

[15]  Y. Kumar and G. Sahoo, “A Review on Gravitational Search Algorithm and its Applications to Data Clustering and Classification,” International Journal of Intelligent Systems and Applications, Published Online in MECS, pp. 79-93, 2014.

[16]  J. Gutierrez and J. Pulido, “A gravitational search algorithm for solving the relay node placement in wireless sensor networks,” International Journal of communication Systems, Wiley online library, 2015.

[17]  R. Precup, R. David, S. Preitl, and M. Radac, “Novel Adaptive Gravitational Search Algorithm for Fuzzy Controlled Servo Systems,” IEEE Transactions on Industrial Informatics, vol. 8, issue. 4, pp. 791–800, 2012.

[18]  J. Chen, C. Yang, C. Tsai, and K. Huang, “A Memetic Gravitation Search Algorithm for Solving Clustering Problems,” IEEE Congress on Evolutionary Computation (CEC), pp. 751-757, 2015.

[19]  A. Rostami, H. Bernety, and A. Hosseinabadi, “A Novel and Optimization Algorithm to Select Monitoring Sensors by GSA,” 2nd International Conference on Control, Instrumentation and Automation (ICCIA), PP. 829 – 834, 2011.

[20]  R. Krishnaprabna and A. Gopakmar, “Performance of Gravitational search Algorithm in Wireless Sensor Network Localization,” National Conference on Communication, Signal Processing and Networking (NCCSN), pp. 1-6, 2014.

[21]  P. Garg, R. Rani, and G. Singh, “Achieving Energy Efficient in WSN using GSA”, International Journal of Advanced Research in computer Science and Software Engineering, vol. 4, April 2014.

[22]  E. Rashedi, H. Nezamabadi-pour, and S. Saryazdi, “BGSA: Binary Gravitational Search Algorithm,” Information Sciences, vol. 179, pp. 2232-2248, 2009.

[23]  P. Namin and M. Tinati, “Node Localization Using Particle Swarm Optimization,” Seventh International Conference on Intelligent Sensors, Sensor Networks and Information Processing (ISSNIP), pp. 288-293, 2011.

[24]  D. Hoang, R. Kumar, and S. Panda, “Realization of a Cluster-Based Protocol Using Fuzzy C-means Algorithm for Wireless Sensor Network,” IET Wireless Sensor Systems, vol. 3, Issue 3, pp. 163-171, 2013.

[25]  M. Bajelan, H. Bakhshi, “An Adaptive LEACH-based Clustering Algorithm for Wireless Sensor Networks”, Journal of Communication Engineering (JCE), vol. 2, pp. 351-365, 2013.