AIRCC PUBLISHING CORPORATION
A NOVEL ENERGY AWARE NODE CLUSTERINGALGORITHM FOR WIRELESS SENSOR NETWORKS USINGA MODIFIED ARTIFICIAL FISH SWARM ALGORITHM
Reza Azizi1, Hasan Sedghi2, Hamid Shoja3, Alireza Sepas-Moghaddam4
1Young Researchers and Elite Club, Bojnourd Branch, Islamic Azad University Bojnourd, Iran
2Department of Information Technology Engineering, PNU, Assaluye, Iran
3Department of Computer Engineering and Information Technology, PNU, Tehran, Iran
4Young Researchers and Elite Club, Science and Research Branch, Islamic AzadUniversity, Tehran, Iran
Clustering problems are considered amongst the prominent challenges in statistics and computationalscience. Clustering of nodes in wireless sensor networks which is used to prolong the life-time of networksis one of the difficult tasks of clustering procedure. In order to perform nodes’ clustering, a number ofnodes are determined as cluster heads and other ones are joined to one of these heads, based on differentcriteria e.g. Euclidean distance. So far, different approaches have been proposed for this process, whereswarm and evolutionary algorithms contribute in this regard. In this study, a novel algorithm is proposedbased on Artificial Fish Swarm Algorithm (AFSA) for clustering procedure. In the proposed method, theperformance of the standard AFSA is improved by increasing balance between local and global searches.Furthermore, a new mechanism has been added to the base algorithm for improving convergence speed inclustering problems. Performance of the proposed technique is compared to a number of state-of-the-art
Wireless Sensor Networks, Artificial Fish Swarm Algorithm, Node Clustering, Energy
Optimization technique is used in order to minimize or maximize the outcome of a function byadjusting its factors. All proper values for this problem are called possible solutions and the bestone is optimal solution. Up to now, different approaches were proposed to perform optimizationprocess e.g. swarm intelligence methods . Swarm intelligence techniques are based on relationsbetween animals and insects swarms which tries to detect the solutions that are close to optimalone. Particle Swarm Optimization (PSO) , Ant Colony Optimization (ACO) , Shuffled FrogLeaping Algorithm (SFLA)  and Artificial Fish Swarm Algorithm (AFSA)  are someexamples of swarm intelligence algorithms. All swarm intelligence algorithms are based onpopulation, where their iterative procedure leads to improve the position of individual inpopulation and subsequently, their movement toward the better positions.International Journal of Computer Networks & Communications (IJCNC) Vol.7, No.3, May 201592As mentioned above, Artificial Fish Swarm Algorithm (AFSA) is one of the swarm intelligencetechniques . The procedure of AFSA has been inspired from social behaviors of fish in nature,based on random search, population and behaviorism. This algorithm involves somecharacteristics i.e. high convergence speed, insensitivity to the initial values of artificial fish,flexibility, and fault tolerant which make it useful for solving optimization problems. Fish canfind the zones involving more foods in underwater world by individual or swarm searches.According to this property, AFSA model was proposed by Free-Movement, Food-Search,Swarm-Movement and Follow Behaviors in order to search the problem space. This algorithm isused in different applications  such as neural networks [7, 8], color quantization , dynamicoptimization problems , physics , global optimization [12-15], and data clustering .In recent years, Wireless Sensor Network (WSN) has been significantly considered byresearchers. Each sensor network includes a number of nodes, where each node involvesprocessing resources and a limited amount of energy. Sensor nodes can sense, measure andcollect information by some local decision and transmit it to the main station . Intelligentsensor node consist of one or several sensors, one processor, a memory unit, a type of energysupply with low energy utilization, transmitter, receiver, and a stimulator. Battery is the primarysource in a sensor node which is not commonly rechargeable, so the node will be dead byfinishing batteries’ energy. Network lifetime is determined by two criteria: 1) the time in whichthe first node dies (FND) and 2) the time in which the last node dies (LND). Utilizing different
mechanisms to increase the lifetime of the network is considered amongst most challengeablesubjects in this domain.Many researches aim at enhancing the network lifetime by proposingduty cycling schemes , coverage targeted protocols  or novel routing protocols .One of the efficient solutions to increase the network’s lifetime is clustering of the nodes .
Clustering is especially important for sensor networks which contain a substantial number ofwireless sensors. Each network can be divided into smaller clusters and contain a cluster head(CH). Sensor nodes in every cluster transfer their informationto the relevant CH and CH collectsinformation and sends them to a primary station. In this way, cluster nodes can conserve moreenergy by reducing the range and length of the communication. Swarm and evolutionaryalgorithms can be used in the primary station to determine the members of each cluster along withthe cluster heads.In this research, a novel algorithm for clustering of nodes in wireless sensor networks has beenproposed, based on AFSA. The proposed algorithm along with Leach algorithm  and severalother ones have been used for the clustering process. The results of the simulations showed thatthe network’s lifetime has been increased by using the proposed method, compared to other ones.The rest of the paper is organized as follow: in the second section Artificial Fish SwarmAlgorithm is reviewed. The third section describes the proposed method and the forth one showsthe experiments and the results. The fifth sectionconcludes the paper.
2. ARTIFICIAL FISH SWARM ALGORITHM (AFSA)
AFSA is one of the swarm intelligence methods and evolutionary optimization techniques .The framework of this algorithm is based on functions that are modelled from social interactions of fish groups in the nature.In this algorithm, there are four functions modelled from fish behaviors in fish swarms. The firstfunction is free-move behavior: as in nature, fishes move freely in the swarm when they do notprey. The second function is prey behavior: certainly, every fish searches for its prey individuallyby means of its senses. These senses are sense of vision, smell and available sensors on theirbodies. In AFSA, the area where an artificial fish can sense a prey is modeled as a neighborhoodwith a visual-sized radius. The next function is follow behavior: when a fish finds food, otherswarm members also follow it to reach the food. The last function is swarm behavior: in nature,fish always try to be in the swarm and not to leave it in order to be protected from hunters.In the underwater world, a fish can discover areas that have more food, which is done byindividual or swarm search by the fish. According to this characteristic, an artificial fish (AF)model is expressed by four aforementioned behaviors. AFs search the problem space by thesebehaviors. The environment, where an AF lives, is basically the solution space and other AFsdomain. Food consistency degree in the water area is AFSA objective function. Finally, AFsreach to a point where its food consistency degree is maxima (global optimum).As it is observed in Fig. 1, AF perceives external concepts with a sense of sight. The currentposition of an AF is shown by vector X=(x1, x2, …,xn). The visual is equal to sight field of the AFand Xv is a position in visual where the AF wants to go. Then if Xv has better food consistencythan the current position of AF, it goes one step toward Xv which causes change in the AFposition from X to Xnext, but if the current position of AF is better than Xv, it continues searchingin its visual area. Food consistency in position X is fitness value of this position and is shownwith f(X). The step is equal to the maximum length of the movement. The distance between twoAFs which are in Xi and Xj positions is shown by Disi,j=|| Xi-Xj|| (Euclidean distance) that iscomputed by Eq (1)
AF model consists of two parts of variables and functions. Variables include X (current AFposition), step (maximum length step), visual (sight field), try-number (the maximum testinteractions and tries), bulletin and crowd factor (0<<1). Also functions consist of preybehavior, free-move behavior, swarm behavior and follow behavior.In each step of the optimization process, AF attempts to find locations with better fitness values inthe problem search space by performing these four behaviors based on the algorithm procedure.In the following, the behaviors of AFSA will be discussed.
Free-move behavior: In AFSA, when an AF can’t move toward a place with more food, itmoves a arbitrary step in the problem space by Eq (2):
Xi,d is component d of AF i’s position in the D-dimensional space and 1 d D. Rand functiongenerates a random number with a uniform distribution in [-1, 1].Prey behavior: If Xi is the current position of AF i, we choose position Xj in the visual of AF irandomly. f(X) is the food consistency in position X or its fitness value. Position Xj is given by
Then food density in Xi is compared with the that of the current position, if f(Xi) f(Xj), AF imoves forward a step from its current position to Xj, which is done by Eq (4):
Xi is a D-dimensional vector and Disi,j is the Euclidean distance between vectors Xi and Xj. Xj –Xi generates a transfer vector from Xi to Xj and when divided by Disi,j, a vector with unit length iscreated from Xi toward Xj. Here, Rand function generates a random number which causes AF i tomove as much as a random percent of Step toward position Xj. Nevertheless, if f(Xi) < f(Xj), wechoose another position Xi by Eq (3) and evaluate its food density to understand whether forwardcondition is satisfied or not. If after try_number times AF does not succeed in satisfying forwardcondition, the concerned AF performs free-move behavior and moves a step in the problem spacerandomly.Swarm behavior: In AFSA, in order to keep swarm generality, in each of the iterations, AFs tryto move toward a central position. A central position of swarm is given by Eq (5):
As it is seen in Eq (5), component d of Xcenter vector is the arithmetic average of component d ofall swarm AFs. Let N be the population size, and nc be the number of AF in Visual field aroundXcenter. If f(Xcenter) f(Xi) and >(nc/N), that is the central position has a better food consistencythan the current position and population density in its neighborhood is not much, so AF i movestoward the central position by Eq (6):
If nc = 0 or the condition of moving toward the central position is not satisfied, prey behavior isperformed for AF i.Follow behavior: If Xi is the current position of AF i, it checks neighbor Xn, if nn is the numberof AFs in the Visual of AF n, if f(Xn) f(Xi) and >(nn/N), i.e. position Xn has a better foodconsistency than the current position of AF i and population density in its neighborhood is notmuch, therefore AF i moves one step toward AF by Eq (7):
If AF i has no neighbors or none of its neighbors satisfy following condition, prey behavior wouldbe performed for AF i.
AFSA performs the optimization process iteratively by means of functions described as itsbehaviors, and the algorithm factors or AFs try to get closer to our objectives by executing thesefunctions.For AFs, prey and free-move behaviors are the individual ones and follow and swarm behaviorsare group behaviors. Prey behavior would be performed if an AF can’t move to a better locationby executing follow behavior and/or swarm behavior, and free-move behavior is performed if an
AF is not successful in finding a better location by performing prey behavior. Certainly, prey andfree-move behaviors are not performed individually by AFs and are only performed when an AFcouldn’t move to a better location by follow and swarm behaviors. In AFSA, in each step of theoptimization process, all AFs pass the same procedure in parallel.Let the position of AF i at time t be Xi(t). AF i performs follow behavior at position Xi(t) once,which leads to obtain position Xi,Follow. After executing the follow behavior, AF i performs swarmbehavior from that position Xi(t) and it leads to obtain position Xi,Swarm. After performing bothfollow and swarm behaviors that were done with respect to Xi(t), the next position of AF i
(Xi(t+1)) is obtained by Eq (8):
In AFSA, a bulletin is used for recording the best position that has been found so far by all swarmmembers. In each of the iterations, after performing AFSA’s behaviors by all AFs and movingthem to new locations, the fitness value of the best AF is compared with the recorded location onthe bulletin. If fitness value of the best AF is better than the recorded location on the bulletin, thelocation of the best AF is recorded as the best found location so far. Standard AFSA pseudo codeis shown in Figure 2.
In this pseudo code, prey and free-move behaviors were considered as a part of swarm and followbehaviors. That is, if an AF could not perform successfully a swarm or follow behavior, it wouldperform prey behavior and if could not reach a better position by executing this behavior, it wouldperform free move behavior.
3. THE PROPOSED METHOD
In this section, the proposed clustering algorithm is described. In this algorithm, there exists apopulation of fish, where each fish includes n positions of clusters’ center. If the clusteringsamples observe d-dimensional space, each artificial fish includes a position vector with n*ddimensions.In the proposed method, in order to establish a balance between exploration and exploitation,some modifications have been applied to the structure of visual and step parameters. For thisreason, Euclidean distance between all artificial fish and the best position, which is stored inbulletin, is calculated. Subsequently, the value of visual parameter for each fish is equal to v% ofits distance to the best found position and the amount of step parameter for each fish is equal tos% of visual value. Based on the structure of swarm intelligent methods regarding convergence tothe goal and reduction in swarm diversity by approaching the goal, Step and Visual parametersare reduced by approaching the goal. This issue leads to a balance between local and globalsearches, and consequently increases the efficiency of the algorithm.Concerning the calculation process of visual and step parameters in the proposed method, eachfish can use its visual and step parameters by equations 2, 3, 4, 6 and 7. It is worth to mention thatregarding the difference between values of visual parameter for different fish, crowed factor andother related conditions are eliminated from follow and swarm behaviors of standard AFSA. Byeliminating this parameter, convergence speed is increased in the proposed method which leads topremature convergence problem. To master this weakness, a novel mechanism is added to thealgorithm.In the new mechanism, each artificial fish moves with probability of p1%, based on the storedposition in bulletin by eq. 9.
X (t +1) = X (t )+((X − X (t ))× Rand(−1,1))
where, Xbulletin is equal to the best found position by the algorithm and Rand function generates arandom number in range of [-1,1] with uniform distribution. According to Eq. 9, in case ofgeneration the random number in range of [-1,0), the new position of the artificial fish is awayfrom bulletin position, which leads to explorer the distant regions by the artificial fish and escapefrom local minima. On the other hand, in case of generation the random number in range of (0,1],the positions of the fish approaches the bulletin which leads to increase convergence speed. So,using Eq. 9, a balance between density and diversity is obvious, which leads to establish a balancebetween exploration and exploitation.In addition, another mechanism has been considered in the proposed method in order to increaseconvergence speed in clusters. As it was mentioned before, each artificial fish included n × ddimensionalcluster centers. Since the nodes’ clustering performs based on their position, andeach node consists two components (X and Y geographical coordinates), the problem space for
AFSA algorithm is a 2×n dimensional space. Position vector for each artificial fish is shown inFigure 3. Here Zi,j represents the dimension j from cluster head i.International Journal of Computer Networks & Communications (IJCNC) Vol.7, No.3, May 2015
Figure 3. Structure of position vector for solving node clustering problem in wireless sensor networks.Fitness function that has been used for each artificial fish in the proposed method is the total ofintra-cluster distances which is equal to the whole Euclidean distances between nodes and thenearest cluster head.In the third mechanism, one cluster head changes its position with the probability of P2% in eachiteration. This cluster head is arbitrarily chosen form entire set of cluster heads. To change theposition of the selected cluster, first, all nodes that their distance to the selected head is lower thanthat to other ones are determined. Then, the new position of this head is equal to the centerposition of the determined nodes. In other word, the center is equal to the average position of the determined nodes.