A balanced power consumption algorithm based on enhanced parallel cat swarm optimization for wireless sensor network

Research Article A Balanced Power Consumption Algorithm Based on Enhanced Parallel Cat Swarm Optimization for Wireless Sensor Network Lingping Kong,1Jeng-Shyang Pan,2Pei-Wei Tsai,2Snasel Vaclav,3and Jiun-Huei Ho4 1Innovative Information Industry Research Center, Shenzhen Graduate School, Harbin Institute of Technology, Shenzhen 518055, China 2College of Information Science and Engineering, Fujian University of Technology, Fuzhou 350118, China 3Department of Computer Science, VSB Technical University of Ostrava, 70833 Ostrava, Czech Republic 4Department of Computer Science and Information Engineering, Cheng Shiu University, Kaohsiung 83347, Taiwan Correspondence should be addressed to Jeng-Shyang Pan; [email protected] Received 24 October 2014; Revised 26 January 2015; Accepted 5 February 2015 Academic Editor: Qiangfu Zhao Copyright © 2015 Lingping Kong et al. This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited. The wireless sensor network (WSN) is composed of a set of sensor nodes. It is deemed suitable for deploying with large-scale in the environment for variety of applications. Recent advances in WSN have led to many new protocols specifically for reducing the power consumption of sensor nodes. A new scheme for predetermining the optimized routing path is proposed based on the enhanced parallel cat swarm optimization (EPCSO) in this paper. This is the first leading precedent that the EPCSO is employed to provide the routing scheme for the WSN. The experimental result indicates that the EPCSO is capable of generating a set of the predetermined paths and of smelting the balanced path for every sensor node to forward the interested packages. In addition, a scheme for deploying the sensor nodes based on their payload and the distance to the sink node is presented to extend the life cycle of the WSN. A simulation is given and the results obtained by the EPCSO are compared with the AODV, the LD method based on ACO, and the LD method based on CSO. The simulation results indicate that our proposed method reduces more than 35% power consumption on average. 1. Introduction The wireless sensor network (WSN) is a popular research field in computer science and telecommunications. It is extensively used in a variety of applications such as the environmental observation [1], the air pollution monitoring, the natural disaster prevention, and the healthcare. The WSN is composedofafewtohundredsoreventhousandsofsensornode modules; sensor nodes are capable of cooperating with others by passing packages through the network to the sink node, which is regarded as the data collection and control center. The price of a sensor node should be inexpensive. It implies that the battery, which supplies the power for the sensor node, is with a limited capacity. In many real-world applications, the sensor nodes are stochastic deployed by airplanes, vehicles, or other transportations. The distance and the density between sensor nodes are not identical. Without properly designing the deployment density, some of the sensor nodes would take higher payload of forwarding packages. This kind of situation is very common to be observed on the inner layer nodes located near to the sink node. Since the inner layer nodes have higher payload than the outer layer nodes, the life cycle of the inner layer nodes is shorter than those deployed in the outer layer. Once the inner layer nodes are out of battery, the whole WSNisparalyzedbecausethepackagescannotbeforwarded to the sink node. Therefore, a scheme for extending the life cycle of the whole WSN is employed at phase of the sensor node deployment. In addition, the connectivity and the coverage of the sensor nodes also affect the performance of the whole WSN, directly. For example, when using the WSN to monitor the environment in an area with natural disasters, the lack of full coverage is not tolerable. An effective WSN must provide the best coverage to meet the need of the user’s requirement. For deploying structural network, each node plays the same role with the fixed and equalized sensing and transmitting range. These sensor nodes work Hindawi Publishing Corporation International Journal of Distributed Sensor Networks Volume 2015, Article ID 729680, 10 pages http://dx.doi.org/10.1155/2015/729680 2 International Journal of Distributed Sensor Networks collaboratively for both sensing and broadcasting packages and transmit the interested packages to the relay nodes. The relay nodes will further forward the package to the sink node. Each sensor node can be treated as the relay node to its neighborhoods. Moreover, the sensor nodes are usually small and inexpensive. Considering the deployment method and the environment of using the WSN, the battery module on the sensor node is generally neither changeable nor rechargeable. The life cycle of the whole WSN can be extended by properly designing the deployment of the sensor nodes and employing the suitable routing algorithm. Hence, how to design an efficient data forwarding path and to maximally extend the life cycle of the WSN become the principal issues. Answering to these needs, enhanced parallel cat swarm optimization (EPCSO) [2–5] is modified partially and is employed to produce the balanced paths for the whole WSN. This is the first application that utilizes EPCSO in the routing design for WSN. In this paper, we propose a strategy for deploying the sensor nodes by considering the coverage of WSN base on the minimum-number-node theory. Furthermore, we utilize EPCSO to design a routing algorithm for providing the balanced routing paths. Our design balances the power consumption between the forwarding distance and the energy saving for all nodes in the whole WSN. The rest of the paper is composed as follows: the related works on the minimum-number-node theory and EPCSO algorithm are briefly reviewed in Section 2;ourproposedsensornode deployment strategy is presented in Section 3;ourproposed method by using EPCSO to produce the balanced routing paths for the WSN is explained in detail in Section 4;the simulation result is given and is compared with the AODV method, the LD methods with both ACO and CSO in Section 5; finally, the conclusion is given in Section 6. 2. Related Works 2.1. Minimum-Number-Node Theory. In general, a WSN in the real-world application contains hundreds or even thousands of sensor nodes scattered in the network field. Keeping the WSN in a high connectivity status with full sensing coverage in a certain region is a difficult problem. The full sensing coverage can be secured by deploying massive sensor nodes into the field. However, deploying too many redundant sensor nodes into the field is very wasteful. Thus, the issue on the minimum requirement of the sensor node number has been discussed in many exiting literatures [8,9]. In 2006, Liu et al. present the definition of coverage intensity [9]for a specific point (𝐶𝑝) and network coverage intensity (𝐶𝑛)as follows: 𝐶𝑝=𝑇𝑐 𝑇𝑎,(1) where 𝐶𝑝is the coverage intensity for a given point 𝑝in an environment, 𝑇𝑎stands for any given long time period, and 𝑇𝑐is the total time during 𝑇𝑎when point 𝑝is covered by at least one active sensor. At the same time, sensors are independently and uniformly deployed in the environment. Hence, the expectation of 𝐶𝑝isequalandcouldbeusedto evaluate the coverage quality of the whole network. Thus, the definition of the network coverage intensity 𝐶𝑛is equal to the expectation of 𝐶𝑝[9] and is given as follows: 𝐶𝑛=𝐸󵄨󵄨󵄨󵄨󵄨𝐶𝑝󵄨󵄨󵄨󵄨󵄨=1−(1−𝑞 𝑘)𝑛,where 𝑞=𝑟 𝑎,(2) where 𝑞is the probability that each sensor node covers a given point and 𝑘denotes the number of subset. The minimumnumber-nodetheoryisacorollaryfrom𝐶𝑛.For𝐶𝑛,if we predefine the subset number 𝑘and network coverage intensity 𝑡, which means the network coverage intensity 𝐶𝑛 is no less than the threshold value 𝑡, we get the lower bound on the number of sensor nodes 𝑛satisfied to the application: 𝐶𝑛≫𝑡, 1−(1−𝑞 𝑘)𝑛≫𝑡, easily get,1−𝑡≫(1−𝑞 𝑘)𝑛, ln (1−𝑡)≪𝑛ln (1− 𝑞 𝑘), 𝑛≫ ln (1−𝑡) ln (1−(𝑞/𝑘)). (3) 2.2. Enhanced Parallel Cat Swarm Optimization (EPCSO). In the field of swarm intelligence (AI), many optimization algorithms were being proposed in recent years. Chu et al. first present the cat swarm optimization algorithm [2]for solving optimization problems by model upon the natural behaviorsofcatsin2006.In2008,Tsaietal.proposea parallel cat swarm optimization (PCSO) algorithm based on the frame structure of parallelizing the CSO method, which has the ability to find the near best solution under more strict conditions. However, the operation in PCSO becomes more complex and requires more computational time to complete the whole process. Therefore, Tsai et al. propose a new algorithm called enhanced parallel cat swarm optimization in 2013 by adopting the orthogonal array of the Taguchi method into the tracing mode process of CSO. EPCSO algorithm has two modes called the seeking mode and the tracing mode for retaining the behaviors of cats to move the individuals in the solution space. The flowchart of EPCSO algorithm is given in Figure 1. A brief review of EPCSO algorithm is given as follows. Step 1. Create 𝑁cats, randomly classify the cats into the 𝑀-dimensional solution space within the limited ranges of theinitialvalue,andrandomlysplittheminto𝐺groups. Generate the velocities for each dimension of each cat and set the motion flags that define which mode the cat belongs to be according to the user predefined value of MR, where MR ∈ [0,1] (here, MR stands for the ratio of individuals moved by the seeking process and the tracing process, and MR also affects the ratio of artificial agents to work on the exploitation and exploration). The Seeking mode presents exploitative capacity. Tracing mode presents exploration capacity. International Journal of Distributed Sensor Networks 3 Yes Start Initialize the position, velocities,t and the flag of every cat Evaluate the cats according to the fitness function and keep the seeking mode? Yes No Seeking mode process End Yes No No Enhanced parallel tracing mode Exchange information? Repick a number of cats and set them into the tracing mode Reach the terminating condition? Information exchanging kis in thecat according to value of MR, and set the others into the seeking mode position xbest of the cat which has the best fitness value Create Ncats and separate them into Ggroups Figure 1: The flowchart of EPCSO algorithm. Step 2. By taking the cats’ coordinates into fitness function to evaluate the fitness values, respectively, record the best coordinate and the fitness value of the cat which has the better fitnessvaluecalculatedsofar. Step 3. Movethecatsbytheseekingmodeprocessorthe tracingmodeprocess.Ifthecatisassignedintoseekingmode, it takes (4) and (5).Otherwise,ittakes(6)–(9) according to the statues of the motion flag. Step 4. Reset the motion flag for all cats. Repick and separate [𝑁×(1−MR)]cats into the tracing mode and the rest into the seeking mode. Step 5. Check whether the number of iterations reaches a predefined iteration number or not. If it is satisfied, run the information exchanging process. Step 6. Check whether the termination criteria are satisfied. If the answer is positive, output the coordinate, which represents the best solution found in the whole process and terminate the program. Otherwise, go back to Step 2 and repeat the process. 2.2.1. The Seeking Mode Process. Tsai et al. define 4 essential parameters in the seeking mode process, that is, the seeking memory pool (SMP), the seeking range of the selected 4 International Journal of Distributed Sensor Networks dimension (SRD), the counts of dimension to change (CDC), and the self-position considering (SPC). These parameters affectthesearchingability,directly,becausetheyarerelated to the quantity of the changes caused to the cats. The seeking mode process is briefly reviewed as follows. Step 1. Generate SMP copies of the present position of cat. If SPC value is true, then store the present position as one of the candidates. Step 2. Foreachcopycat,accordingtoCDC,randomlyplus or minus SRD percent values and replace the old ones: 𝑥𝑗=(1+rand ×SRD)×𝑥𝑗,where ∀𝑗. (4) Here rand is a random variable in the range [0-1]. Step 3. Calculate the fitness values (FS) of all candidate points, respectively. Step 4. If all FS are not exactly equal, calculate the selecting probability 𝑃𝑖of each candidate by (5); 𝑃𝑖={ { { { { 1, if FSmax =FSmin 󵄨󵄨󵄨󵄨FS𝑖−FS𝑏󵄨󵄨󵄨󵄨 FSmax −FSmin ,where 0<𝑖<𝑗,otherwise.(5) If the goal of the optimization process is to find the minimum solution of the fitness function, let FS𝑏=FSmax, otherwise let FS𝑏=FSmin. Step 5. Pickthecoordinatefromthecandidatepointstomove to base on the probability. 2.2.2. The Parallel Tracing Mode Process. Once a cat runs into tracing mode, it migrates according to its’ own velocities corresponding to every dimension. The parallel tracing mode process can be depicted as follows. Step 1. Generate two sets of the velocities for every dimension V𝑘,𝑑(𝑡)by (6) for the cat𝑘at the current iteration, marked as 𝐶𝑉1,𝑑(𝑡)and 𝐶𝑉2,𝑑(𝑡),respectively: 𝐶𝑉1,𝑑 (𝑡)=𝑉 𝑘,𝑑 (𝑡−1)+𝑟×𝑐 ×[𝑥𝑔best,𝑑 (𝑡−1)−𝑥𝑘,𝑑 (𝑡−1)], where 𝑑=1,2,...,𝑀, 𝐶𝑉2,𝑑 (𝑡)=𝑉 𝑘,𝑑 (𝑡−1)+𝑟×𝑐 ×[𝑥𝑙best,𝑑 (𝑡−1)−𝑥𝑘,𝑑 (𝑡−1)], where 𝑑=1,2,...,𝑀, (6) where 𝑀denotes the dimension of the solution space, 𝑥𝑔best denotes the global near-the-best solution found so far, 𝑥𝑙best is the local near-the-best solution of the group. 𝑙represents the group that 𝑥𝑘belongs to, 𝑟is a random value in the range of [0-1],and𝑐is a constant. Use the candidate velocities and the Taguchi orthogonal array to create a series of velocity sets, shown as follows: Vset𝑠,𝑑 (𝑡)={ { { { { { { { { 𝑐V1,𝑑 (𝑡),if the element in the orthogonal array is “0”, 𝑐V2,𝑑 (𝑡),otherwise, (7) where 𝑠is the index of the velocity set. Step 2. Take one velocity set to update the original velocity V𝑘,𝑑(𝑡), shown as follows: V𝑘,𝑑 (𝑡)= { { { { { { { { { { { { { { { Vmax,if V𝑘,𝑑 (𝑡−1)+Vset𝑠,𝑑 (𝑡) exceeds the maximum velocity, V𝑘,𝑑 (𝑡−1)+Vset𝑠,𝑑 (𝑡),otherwise.(8) Then update the position 𝑥𝑘,𝑑(𝑡)of the present cat𝑘as follows: 𝑥𝑘,𝑑 (𝑡)=𝑥𝑘,𝑑 (𝑡−1)+V𝑘,𝑑 (𝑡).(9) Calculate its fitness value for later use. Accumulate the FS values contributed by the column factors and take the most adaptive factors to compose the latest velocity. Step 3. Move the present cat𝑘with the latest velocity by (9) to update its position. 2.2.3. The Information Exchanging Process. This process aims at exchanging subpopulation information and forming the cooperation structure between different groups. There is a factor ECH to monitor the condition of each subpopulation. After ECH number iterations, these subpopulations exchange information once. Four steps of the exchanging process are showed as follows. Step 1. Pick up a group of subpopulations sequentially and sortthesecatsaccordingtotheirFSvalues. Step 2. Randomly select a local best solution from an unrepeatable group. Step 3. Replace the position of the worst of cat whose FS value is the worst with the local best solution cat position. Step 4. Repeatedly perform Step 1 to 3𝐺times (there are only 𝐺groups) to let each group receive a local best solution from the others. 3. Network Model Deployment In this paper, we consider two-dimensional static flat environment and assume each node equipped with the same fixed transmission range. The network region is a circle with radius 350. It would be much easier and cheaper than International Journal of Distributed Sensor Networks 5 1 29 0 350 250 150 50 50 150 250 350 49 41 33 25 17 10 Figure 2: A quarter of network structure. predefined position deployment. However, for the sake of diminishing the critical nodes workload and then prolonging the whole network lifetime, we propose a scheme for the sensor deployment. The closer to the sink node results in the more power consumption is a definite fact in deploying sensor nodes. The reason is that the nodes closer to the sink node are much frequently treated as the delay nodes. To overcome the power consumption problem, it is necessary to increase the number of nodes in the regions near to the sink node. Answering to the problem mentioned above, we propose a scheme to deploy the sensor nodes by calculating the required density of the sensor nodes. To deploy sensor nodes in a two-dimensional field, we divide the field into 7 concentric circles, 8 sectors, and 56 subboxes as shown in Figure 2. There are 2,688 sensor nodes deployed in this field. The outer layer is defined as sectors on the 7th concentric circle; and the inner layer is defined as sectors numbered as 1 to 6 on the 1st concentric circle. For the outer layer concentric circles, each sector is assigned 48 sensor nodes scattered randomly to the field. Based on this condition, the same amount of sensor nodes is assigned to all sectors. This result in the coverage intensity is increased in the inner layer sectors. Therefore, thepayloadofWSNintheinnerlayersectorscanbeshared with more optional paths. The power consumption is now with larger chance to be balanced automatically by deploying sensor nodes with higher density in the inner layer sectors. Furthermore, the possibility of network paralyzing caused by disabled internal nodes is reduced. In addition, the lifetime of the WSN is also extended. For a fixed amount of sensor nodes, the larger the measure of area is, the lower the coverage intensity is. To ensure the WSN is functional, the network coverage intensity must be above a certain threshold. Hence, in our deployment strategy, the minimum amount of sensor deployed in a sector is calculated based on the sector located on the outer layer. This deployment strategy is easy to operate. And the result is capable of achieving high coverage intensity. The proof of high coverage intensity is given as follows. Proof. For the reason that the shape of each sector is not a circle, we cannot directly apply the minimum number of nodes theory to the sector area. Thus, we use the derivation method to verify the high coverage intensity. First, we calculate the coverage intensity value of an area covered by 48 sensor nodes. According to reverse deduction, the whole network minimum coverage intensity can be found. (a) Only one subset exists in the WSN, 𝑘=1.The network coverage intensity is 𝑡: 1−(1−𝑎 𝑘)𝑠≥𝑡, (10) where 𝑎is the area of circle with radius 350, which covers the whole region, and 𝑟denotes the size of sensing area of one node. (b) It is known that the outer layer sector such as number 49, which is covered by 48 sensor nodes, satisfies the minimum full coverage condition. The same coverage intensity can be treated as the criterion for defining the number of sensor nodes used in other sectors to achieve the same coverage condition. The number of sensor nodes can be figured out by the equivalent proportional relationship. The area ratio of sector 49 to the whole field is 𝑃area = ((1−((𝜋×3002)/(𝜋× 3502)))/8) = 13/392and 𝑆 = 48/(13/392) ≈ 1,448is the number of sensor nodes for the circle with radius 350. (c) In (10),given𝑞,weget𝑞=𝑟/𝑎=𝜋502/𝜋3502=1/49. (d) Finally, taking 𝑞,𝑘,𝑆into (10),weget 1−(1−1/49 1)1448 ≥𝑡, 𝑡≤0.9999999999995. (11) The area of a sector located in the outer layer such as sector 49 is larger than any sectors in the other layers. Hence, the coverage intensity of the most outer layer concentric is definitely smaller than the inner layer concentric sectors. In order to ensure a good data forwarding quality, the whole network coverage intensity is designed to be greater than 0.99. Basedonthecriteriamentionedabove,theoverviewofthe WSN based on our proposed deployment scheme is shown in Figure 3. 4. Using EPCSO Method to Solve the Routing Problem in WSN In the wireless sensor network, we need to build routing path for every sensor node. The routing path is different in thenumberofrelaynodesforeachconcentriccirclenode. However, the EPCSO originally is not a method used in finding paths for the WSN. Its first application is designed for theaircraftschedulerecovering.Thus,wehavetopartially modify EPCSO before employing it to solve the routing 6 International Journal of Distributed Sensor Networks 0 100 200 300 400 500 600 700 0 100 200 300 400 500 600 700 Figure 3: Network node deployment result. probleminWSN.ThemodificationswemadeforEPCSOin this paper are listed as follows: (1) The representation of the artificial agent is modified from the coordinate to a set. (2) A newly defined cluster flag is added into the basic component of the artificial agent. (3) The newly designed fitness function is custom-made for the WSN routing problem. Assume that the transmission range of a single sensor node is 50. Thus, the nodes located in the sectors in the 5th concentric circles need four relay nodes to transmit their packagetothesinknode.Weusenodetar as an example to explainhowtouseEPCSOtosolvetheroutingproblem.The modifiedEPCSOandthewholeprocessesareexplainedas follows. 4.1. Initialization. In the initialization process, some parameters and constants are required to be defined before the whole process starts. In the original EPCSO, the artificial agent (the cat) is composed of the coordinate representing its position in the solution space. In our design, the artificial agent is composed by a set of sensor nodes. The sensor nodes in one set are from different layers and should be capable of forming at least one complete path from the most outer layer back to the sink node. For each cat, the set is defined by cat𝑖={(𝑥11,𝑥12,𝑥13),(𝑦21,𝑦22,𝑦23),...,(𝑛𝑙1,𝑛𝑙2,𝑛𝑙3)}, (12) where 𝑖is the identity index of the cat and 𝑙is the identifier of the concentric circle (the layer). In this application, the population size is set to 16. There are three backup sensor nodeslocatedinthesamelayerineverycat.Asshownin Figure 4,sensornodetar in the given example is located on the 5th layer. In this case, one of the initialization results of node tar canbedescribedby cat1={(𝑎,𝑏,𝑐),(𝑑,𝑒,𝑓),(𝑖,𝑔,ℎ),(𝑚,𝑗,𝑘)}. (13) As given in (13),cat 1consists of nodes in 4 layers, where sensor nodes 𝑎and 𝑏belong to the first layer and sensor e ab c d f g h i j k mTar Sink Sink node Node tar Sensor node Data transfer route Concentric circle cat1transfer route Figure 4: One of the initialized cats for node tar. nodes 𝑑,𝑒,and𝑓arelocatedinthesecondlayerandsoon. There is only one integrated routing path in cat1;routingpath {𝑘,ℎ,𝑒,𝑏}is composed of four sensor nodes. Each node is collected from different layers, and the order of path is exactly the relay node order for node tar to transmit package to the sink node. In addition, all sensor nodes employed in one cat should be gathered from the same quadrant. This criterion is capable of avoiding the incomplete path caused by a sudden jump, which exceeds the sensing range of the sensor node. Besides the set of sensor nodes, a cat should also carry the corresponding velocities to all components. The velocity of a cat is described by 𝑉cat ={(V11,V12,V13),(V21,V22,V23),...,(V𝑙1,V𝑙2,V𝑙3)}.(14) The velocity is corresponding to the composition of cat. For example, V11 plays the role of the velocity for the sensor node 𝑎. The velocities are constrained within a predefined maximum velocity for every dimension. The maximum velocity set is defined by 𝑉max ={V1,V2,V3,...,V𝑙}, (15) where 𝑙stands for the numerical value of concentric circles and V1<V2<V3<⋅⋅⋅<V𝑙. The velocity increases gradually because the area of a sector increases in the outer layers. The last step in the initialization process is to set the motion flag and the cluster flag for every cat. The cluster flag is defined to indicate the cluster number which the cat belongs to. Based on our design, the 2D space is divided into 8 sectors in every layer. Hence, the cluster flag is an integer in the range of [1, 8]. International Journal of Distributed Sensor Networks 7 In every cluster, we can find at least one cat, which presents thebestfitnessvalueinitsowncluster.Thiscatwillbemarked asthelocalbestsolutionintheclusterandisdenotedby𝐶best𝑖, where 𝐼stands for the cluster label. 4.2. Custom-Made Fitness Function. The fitness function (also called the object function or the evaluation function) plays the principal role in the whole process. A well-designed fitness function should be capable of representing the input solution’s behavior in the solution space. To utilize the modified EPCSO in finding the balanced path for the WSN, a fitness function is designed specifically for this goal. Our proposed fitness function can be described by 𝐹𝑥=𝛼1𝑥1 3𝑙+𝛼2𝑥2 𝑥1+𝛼31−𝑥3 3𝑙−1 +𝛼4𝑥4 3⋅𝑙,(16) where 𝑥1denotes the sum of all collected paths which go through the current node in the cat, 𝑥2stands for the average power consumption of all connected paths collected in the cat, 𝑥3is the relay counter for calculating the number of forwarding packages for other nodes, 𝑥4is used for counting the number of usage node existing in the cat, and 𝛼1,𝛼2,𝛼3, and 𝛼4are the weights and ∑4 𝑖=1 𝛼𝑖=1. The parameters in the fitness function are described in detail as follows. (a) Path Number (𝑥1). This parameter is the accumulation of collected paths which go through the current node. However, the sensor nodes are not allowed to transmit packages to their neighborhood nodes located in the same layer. The transmission path between nodes in the same layer should be eliminated. (b) Total Power Consumption (𝑥2). This parameter accumulates all power consumption caused by paths carried by this cat. (c) Relay Number (𝑥3). This parameter indicates the count of legal transmission between neighborhood nodes. As mentioned above, the transmission between nodes located in the same layer is forbidden. (d) Usage Number (𝑥4). This parameter counts the number of nodes in the cat involved in building the integrated routing path from the current node to the sink node. These nodes are called the useful nodes. The fitness function can be decomposed into 4 parts, that is, the path ratio, the average power consumption, the relay ratio, and the usage rate. The detailed description is listed as follows. (a) Path Ratio. The path ratio is defined by (17);itstands fortheratioofthefoundpathnumberstotheideal path in the cat: Pathratio =𝑥1 3𝑙,(17) where Pathratio represents the path ratio, 𝑙is the position circles minus one, and the ideal path number is known as 3𝑙. (b) Average Power. The average power is defined by (18).Ave power calculates the power consumption on average over all paths carried by the cat: Avepower =𝑥2 𝑥1.(18) (c) Relay Ratio. The relay ratio is defined by (19).Itis known that, in the ideal case, the total relay number is 3𝑙−1. Hence, the relay ratio is equal to 1 in the ideal case: 𝑅= 𝑥3 3𝑙−1 .(19) (d) Usage Rate. The usage rate is defined by (20).Itstands for the ratio of the usable nodes to all nodes collected bythecat.Intheidealcase,allnodescarriedbyacat should be useable; that is, the usage rate is equal to 1: 𝑈= 𝑥4 3⋅𝑙.(20) The fitness function is employed in the EPCSO process to evaluate the fitness of the cats and is the gauge to find the global near-the-best solution (denoted by 𝐺best)andthelocal near-the-best solution (denoted by 𝐺best𝑖)forthe𝑖th cluster. 4.3.AnExampleIsGivenasFollows. Assume the target node tar islocatedinthe5thlayerasshowninFigure 4;the parameter 𝑙is 4. For cat1,wehave𝑥1=1,andAve power is the average power consumption of path {𝑘,ℎ,𝑒,𝑏}.𝑅= 7because the relay ratio is the set of {(𝑗,𝑔),(𝑘,ℎ),(𝑒,ℎ), (𝑏,𝑒),(𝑏,𝑓),(𝑑,𝑖),(𝑎,𝑑)},and𝑈=4because nodes {𝑘,ℎ,𝑒,𝑏} are usable. 4.4. Seeking Mode Process. Suppose cat1is assigned to move by the seeking mode process; 𝑗copies of cat1aremadeinthe beginning.IftheSPCissetto“true”bytheuser,thecopies should remain one set identical to cat1.Basedonthevalue or CDC and SRD, the rest of the copies are slightly modified. An example is given as follows. Suppose we have cat1in the process and cat1is given in cat1={(𝑎,𝑏,𝑐),(𝑑,𝑒,𝑓),(𝑖,𝑔,ℎ),(𝑚,𝑗,𝑘)}.(21) Assume CDC =2; nodes 𝑚and 𝑖arechosentobethe mutative nodes as shown in Figure 5.Thenodeindexis modified by SRD percents. After the process, it is possible that node 𝑚is changed to node 𝑛; and node 𝑖is changed to node 𝑝as shown in Figure 6.Calculateandsortthefitnessvalues of all copies by (16) andkeepthebestcatinthememory. 4.5. Tracing Mode Process. In the tracing mode process, thecat’svelocityshouldbeupdated,andthecatwillbe moved based on its velocity produced by the Taguchi method. The velocity is produced based on 𝐺best and 𝐺best𝑖. We take the same example listed in Figure 5.Letcat 1be initialized for node tar;weget𝐶𝑉1,𝑑(𝑡) and 𝐶𝑉2,𝑑(𝑡) two 8 International Journal of Distributed Sensor Networks Table 1: The 𝐿13(212)orthogonal array. Experiment number Considered factors 𝐴𝐵𝐶𝐷𝐸𝐹𝐺𝐻𝐼𝐽𝐾𝐿 1−1−11−11 1−1−11 1−11 21−1−1−1−11 1−1−11 1 1 3−11−1−11−11−11−11 1 4 111−1−1−1−1−1−1−1−11 5−1−11 1−1−11−11 1−1−1 61−1−11 1−1−1−1−11 1−1 7−11−11−11−1−11−11−1 8 1111111−1−1−1−1−1 9−1−11−11 1−11−1−11−1 10 1 −1−1−1−11 1 1 1−1−1−1 11 −11−1−11−11 1−11−1−1 12 111−1−1−1−11 1 1 1−1 13 −1−11 1−1−11 1−1−11 1 14 1 −1−11 1−1−11 1−1−11 15 −11−11−11−11−11−11 16 111111111111 e ab c d f g h i j k mTa r Sink Sink node Node tar Mutative node Data transfer route Concentric circle Sensor node cat1transfer route Figure 5: An example of cat1in the tracing mode process. twelve-dimensional velocities sets. To find the optimal combination of the velocity, EPCSO uses Taguchi method to solve this problem. Twelve dimensional velocities mean twelve column factors. The 𝐿13(212)orthogonal array is given in Table 1.Thevalues“−1” and “1” in the elements of the orthogonal array indicate the value from 𝐶𝑉1,𝑑(𝑡)or 𝐶𝑉2,𝑑(𝑡) should be used in the corresponding dimension. e ab c d f g h i j k mTa r Sink n p Mutated node Sink node Node tar Mutative node Data transfer route Concentric circle Sensor node cat1transfer route Figure 6: The result of cat1after the tracing mode process. 5. Experiment and Experimental Result The experimental result is produced by our proposed routing method based on the minimum-number-node theory and the modified EPCSO. As mentioned above, 2,688 nodes are deployed in a 2D field within a 350-radius circle. The International Journal of Distributed Sensor Networks 9 Table 2: The results of four algorithms. Nodes Methods All Average Max Min All LDACO (Ho et al. 2012) [10]3.5417×1061.317×1033.10×1046.7×101 AODV (Perkins and Royer, 1999) [6]3.5772×1061.330×1038.82×1046.7×101 LDCSO (Kong et al., 2014) [7]3.5881×1061.334×1035.15×1046.7×101 Our proposed method 2.2984×1060.855×1031.41×1046.7×101 One LDACO (Ho et al. 2012) [10]6.7614×1051.760×1033.10×1046.7×101 AODV (Perkins and Royer, 1999) [6]7.0002×1051.822×1038.82×1046.7×101 LDCSO (Kong et al., 2014) [7]6.9459×1051.808×1035.15×1046.7×101 Our proposed method 2.9920×1057.99×1021.41×1046.7×101 Two LDACO (Ho et al. 2012) [10]5.7792×1051.505×1031.95×1046.7×101 AODV (Perkins and Royer, 1999) [6]5.8802×1051.531×1033.71×1046.7×101 LDCSO (Kong et al., 2014) [7]5.9846×1051.558×1034.12×1043.5×101 Our proposed method 2.3038×1056.01×1027.14×1039.0×101 Six LDACO (Ho et al. 2012) [10]1.8860×1054.91×1022.81×1035.7×101 AODV (Perkins and Royer, 1999) [6]1.7568×1054.57×1029.44×1031.2×101 LDCSO (Kong et al., 2014) [7]1.7617×1054.58×1028.02×1031.2×101 Our proposed method 4.7954×1051.248×1033.29×1032.5×102 Seven LDACO (Ho et al. 2012) [10]7.4627×1041.94×1027.09×1025.8×101 AODV (Perkins and Royer, 1999) [6]8.4859×1042.20×1023.23×1031.5×101 LDCSO (Kong et al., 2014) [7]8.8532×1042.26×1021.91×1033.1×101 Our proposed method 3.0722×1058.00×1023.87×1032.3×102 circle is divided into 7 concentric circles and each of the concentric circles contains the same number of sensor nodes, that is, 384 nodes. The experimental result of the total power consumption produced by our proposed method is compared with LDACO [10], AODV [6], and LDCSO [7]inTable 2.Inour simulation, we only count the routing power consumption. The routing path is from one node that senses an event to the sink. In the first column, “all” stands for the power consumption caused by all sensor nodes deployed in the environment, “one” means the power consumption caused by all sensor nodes located in the most inner layer, “two”is the power consumption caused by the sensor nodes located in the 2nd layer, and “seven” is the power consumption caused by the sensor nodes located in the most outer layer. The experimental result indicates that the whole power consumption is 3.5417×106for LDACO algorithm, and the average power consumption for one node is 1.317×103,the maximum consumption is 1.310 × 104, and the minimum is 6.7 × 101. The above power consumption is for all the nodes. The rest of rows results are for each of the concentric circles sensor nodes, respectively. The proposed method gets better performance due to low total power consumption and balance of consumption for the in-layer nodes and outer layer nodes. This could partially solve the problem for prolonging the lifetime of sensor network. 6. Conclusion In this paper, we propose a strategy for deploying the sensor nodes by considering the coverage of WSN based on the minimum-number-node theory. Furthermore, we utilize EPCSO to design a routing algorithm for providing the balanced routing paths. Three modifications are made for the EPCSO algorithm to make it suitable for finding routing paths for WSN. Our design balances the power consumption between the forwarding distance and the energy saving for all nodes in the whole WSN. Our deployment strategy is easy to use in different WSN applications. Furthermore, the problem ofwhichtheinnerlayernodesusuallyareoutofbatteryis solved because our deployment method with EPCSO finding transmission paths keeps the sensor nodes in the inner layer alive and the nodes in the most outer layer are firstly out of battery. The experimental result indicates that our proposed method could partially balance the power consumption between the inner layer and the outer layer. The total power consumption of our proposed method is the lowest among other algorithms. The simulation results indicate that our proposed method reduces more than 35% power consumption on average. Conflict of Interests The authors declare that there is no conflict of interests regarding the publication of this paper. References [1] M. Prauzek, P. Musilek, A. G. Watts, and M. Michalikova, “Powering environmental monitoring systems in arctic regions: a simulation study,” Elektronika ir Elektrotechnika,vol.20,no.7, pp. 34–37, 2014. [2] S. C. Chu, P. W. Tsai, and J. S. Pan, “Cat swarm optimization,” in PRICAI 2006: Trends in Artificial Intelligence: roceedings of