Document Type: Research Paper
Authors
Electrical & Electronic Engineering Department, Shahed University, Tehran, IRAN
Abstract
Keywords
Wireless Sensor Network (WSN) belongs to the Low Range Wireless Personal Area Network (LRWPAN) [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, selfconfiguring and can withstand in any harsh environment. This makes the sensor nodes to be applied in various realtime 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 multiplehop. After certain time period (round time) reclustering 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 quasistationary nodes with realvalued weights [10].
The hierarchal clustering scheme uses spanning treebased 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 noncluster 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 Multihop LEACH was proposed in [13]. PLEACH 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.PLEACH 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 natureinspired 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 secondorder models with an integral component and variable parameters [17], solving the NPhard 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 nonlinear 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.
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]:
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 M_{1 }and M_{2} 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 M_{1} and M_{2}.
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 ndimensional 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. (56) 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 rand_{j} 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 23
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 reexecuted, 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. 1214). 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].
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, a_{1} and a_{2 }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)
In our simulation, we have used MATLAB programming and compare energy consumption of proposed method with LEACH algorithm, BPSO algorithm [23], Kmeans 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 160node 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 KMEANS algorithm [2425] 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 m^{2} 
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.3e1.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.
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.