A Balanced Power Consumption Algorithm Based on Enhanced Parallel Cat Swarm Optimization for Wireless Sensor Network

Abstract

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 composed of a few to hundreds or even thousands of sensor node 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 WSN is paralyzed because the packages cannot be forwarded 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 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; our proposed sensor node deployment strategy is presented in Section 3; our proposed 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 ( $C_p$ ) and network coverage intensity ( $C_n$ ) as follows:

$$\begin{array}{cc}& C_p=\frac{T_c}{T_a},\end{array}$$

(1)

where $C_p$ is the coverage intensity for a given point p in an environment, $T_a$ stands for any given long time period, and $T_c$ is the total time during $T_a$ when point p 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 $C_p$ is equal and could be used to evaluate the coverage quality of the whole network. Thus, the definition of the network coverage intensity $C_n$ is equal to the expectation of $C_p$ [9] and is given as follows:

$$\begin{array}{cc}& C_n=E\left|C_p\right|=\mathrm{1}-{\left(\mathrm{1}-\frac{q}{k}\right)}^n,\hspace{1em}\text{where}\mathrm{\hspace{0.17em}\hspace{0.17em}}q=\frac{r}{a},\end{array}$$

(2)

where q is the probability that each sensor node covers a given point and k denotes the number of subset. The minimum-number-node theory is a corollary from $C_n$ . For $C_n$ , if we predefine the subset number k and network coverage intensity t, which means the network coverage intensity $C_n$ is no less than the threshold value t, we get the lower bound on the number of sensor nodes n satisfied to the application:

$$\begin{array}{cc}& C_n\gg t,\\ \mathrm{1}-{\left(\mathrm{1}-\frac{q}{k}\right)}^n\gg t,\\ \text{easily}\mathrm{\hspace{0.17em}\hspace{0.17em}}\text{get},\hspace{0.17em}\hspace{0.17em}\mathrm{1}-t\gg {\left(\mathrm{1}-\frac{q}{k}\right)}^n,\\ \ln \left(\mathrm{1}-t\right)\ll n\ln \left(\mathrm{1}-\frac{q}{k}\right),\\ n\gg \frac{\ln \left(\mathrm{1}-t\right)}{\ln \left(\mathrm{1}-\left(q/k\right)\right)}.\end{array}$$

(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 behaviors of cats in 2006. In 2008, Tsai et al. propose a 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.

Figure 1

The flowchart of EPCSO algorithm.

A brief review of EPCSO algorithm is given as follows.

Step 1.

Create N cats, randomly classify the cats into the M-dimensional solution space within the limited ranges of the initial value, and randomly split them into G 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 $\text{MR}\in [\mathrm{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.

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 fitness value calculated so far.

Step 3.

Move the cats by the seeking mode process or the tracing mode process. If the cat is assigned into seeking mode, it takes (4) and (5). Otherwise, it takes (6)–(9) according to the statues of the motion flag.

Step 4.

Reset the motion flag for all cats. Repick and separate $\left[N\times \left(1-\text{MR}\right)\right]$ 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 dimension (SRD), the counts of dimension to change (CDC), and the self-position considering (SPC). These parameters affect the searching ability, directly, because they are related 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.

For each copy cat, according to CDC, randomly plus or minus SRD percent values and replace the old ones:

$$\begin{array}{cc}& x_j=\left(\mathrm{1}+\text{rand}\times \text{SRD}\right)\times x_j,\hspace{1em}\text{where}\mathrm{\hspace{0.17em}\hspace{0.17em}}\forall j.\end{array}$$

(4)

Here rand is a random variable in the range $[0\text{-}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 $P_i$ of each candidate by (5);

$$\begin{array}{cc}& P_i=\left\{\begin{array}{cc}\mathrm{1},\hfill & \text{if}\mathrm{\hspace{0.17em}\hspace{0.17em}}{\text{FS}}_{\max }={\text{FS}}_{\min }\hfill \\ \frac{\left|{\text{FS}}_i-{\text{FS}}_b\right|}{{\text{FS}}_{\max }-{\text{FS}}_{\min }},\hfill & \begin{array}{c}\text{where}\mathrm{\hspace{0.17em}\hspace{0.17em}}\mathrm{0}<i<j,\hspace{0.17em}\hspace{0.17em}\text{otherwise}.\end{array}\hfill \end{array}\right.\end{array}$$

(5)

If the goal of the optimization process is to find the minimum solution of the fitness function, let ${\text{FS}}_b={\text{FS}}_{\max }$ , otherwise let ${\text{FS}}_b={\text{FS}}_{\min }$ .

Step 5.

Pick the coordinate from the candidate points to move 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_{k,d}(t)$ by (6) for the ${\text{cat}}_k$ at the current iteration, marked as ${CV}_{1,d}\left(t\right)$ and ${CV}_{2,d}\left(t\right)$ , respectively:

$$\begin{array}{ll}& {CV}_{\mathrm{1},d}\left(t\right)=V_{k,d}\left(t-\mathrm{1}\right)+r\times c\\ \times \left[x_{g_{\text{best}},d}\left(t-\mathrm{1}\right)-x_{k,d}\left(t-\mathrm{1}\right)\right],\\ \hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\text{where}\mathrm{\hspace{0.17em}\hspace{0.17em}}d=\mathrm{1,2},\dots ,M,\\ {CV}_{\mathrm{2},d}\left(t\right)=V_{k,d}\left(t-\mathrm{1}\right)+r\times c\\ \times \left[x_{l_{\text{best}},d}\left(t-\mathrm{1}\right)-x_{k,d}\left(t-\mathrm{1}\right)\right],\\ \hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\text{where}\mathrm{\hspace{0.17em}\hspace{0.17em}}d=\mathrm{1,2},\dots ,M,\end{array}$$

(6)

where M denotes the dimension of the solution space, $x_{g_{\text{best}}}$ denotes the global near-the-best solution found so far, $x_{l_{\text{best}}}$ is the local near-the-best solution of the group. l represents the group that $x_k$ belongs to, r is a random value in the range of $[$ 0-1 $]$ , and c is a constant. Use the candidate velocities and the Taguchi orthogonal array to create a series of velocity sets, shown as follows:

$$\begin{array}{cc}& v_{{\text{set}}_{s,d}}\left(t\right)=\left\{\begin{array}{cc}{cv}_{\mathrm{1},d}\left(t\right),\hfill & \text{if}\mathrm{\hspace{0.17em}\hspace{0.17em}}\text{the}\mathrm{\hspace{0.17em}\hspace{0.17em}}\text{element}\mathrm{\hspace{0.17em}\hspace{0.17em}}\text{in}\hfill \\ \hfill & \text{the}\mathrm{\hspace{0.17em}\hspace{0.17em}}\text{orthogonal}\mathrm{\hspace{0.17em}\hspace{0.17em}}\text{array}\mathrm{\hspace{0.17em}\hspace{0.17em}}\text{is}\mathrm{\hspace{0.17em}\hspace{0.17em}}\text{“}\mathrm{0}\text{”},\hfill \\ {cv}_{\mathrm{2},d}\left(t\right),\hfill & \text{otherwise},\hfill \end{array}\right.\end{array}$$

(7)

where s is the index of the velocity set.

Step 2.

Take one velocity set to update the original velocity $v_{k,d}\left(t\right)$ , shown as follows:

$$\begin{array}{cc}& v_{k,d}\left(t\right)=\left\{\begin{array}{cc}{v}_{\max },\hfill & \text{if}\mathrm{\hspace{0.17em}\hspace{0.17em}}{v}_{k,d}\left(t-\mathrm{1}\right)+v_{{\text{set}}_{s,d}}\left(t\right)\hfill \\ \hfill & \text{exceeds}\mathrm{\hspace{0.17em}\hspace{0.17em}}\text{the}\hfill \\ \hfill & \text{maximum}\mathrm{\hspace{0.17em}\hspace{0.17em}}\text{velocity},\hfill \\ v_{k,d}\left(t-\mathrm{1}\right)+v_{{\text{set}}_{s,d}}\left(t\right),\hfill & \text{otherwise}.\hfill \end{array}\right.\end{array}$$

(8)

Then update the position $x_{k,d}\left(t\right)$ of the present ${\text{cat}}_k$ as follows:

$$\begin{array}{cc}& x_{k,d}\left(t\right)=x_{k,d}\left(t-\mathrm{1}\right)+v_{k,d}\left(t\right).\end{array}$$

(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 ${\text{cat}}_k$ 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 sort these cats according to their FS values.

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\hspace{0.17em}\hspace{0.17em}G$ times (there are only G 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 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.

Figure 2

A quarter of network structure.

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, the payload of WSN in the inner layer sectors can be shared 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, $k=1$ . The network coverage intensity is t:

$$\begin{array}{cc}& \mathrm{1}-{\left(\mathrm{1}-\frac{a}{k}\right)}^s\ge t,\end{array}$$

(10)

where a is the area of circle with radius 350, which covers the whole region, and r 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 $P_{\text{area}}=\left((\mathrm{1}-\left(\left(\pi \times {\mathrm{300}}^{\mathrm{2}}\right)/\left(\pi \times {\mathrm{350}}^{\mathrm{2}}\right)\right))/\mathrm{8}\right)=\mathrm{13}/\mathrm{392}$ and $S=\mathrm{48}/(\mathrm{13}/\mathrm{392})\approx \mathrm{1}\text{,}\mathrm{448}$ is the number of sensor nodes for the circle with radius 350.

(c)

In (10), given q, we get $q=r/a=\pi {50}^2/\pi {350}^2=1/49$ .

(d)

Finally, taking q, k, S into (10), we get

$$\begin{array}{cc}& \mathrm{1}-{\left(1-\frac{1/49}{1}\right)}^{1448}\ge t,\hspace{1em}t\le \mathrm{0.9999999999995}.\end{array}$$

(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. Based on the criteria mentioned above, the overview of the WSN based on our proposed deployment scheme is shown in Figure 3.

Figure 3

Network node deployment result.

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 the number of relay nodes for each concentric circle node. However, the EPCSO originally is not a method used in finding paths for the WSN. Its first application is designed for the aircraft schedule recovering. Thus, we have to partially modify EPCSO before employing it to solve the routing problem in WSN. The modifications we made for EPCSO in 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 package to the sink node. We use node tar as an example to explain how to use EPCSO to solve the routing problem. The modified EPCSO and the whole processes are explained as 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

$$\begin{array}{cc}& {\text{cat}}_i=\left\{\left(x_{\mathrm{11}},x_{\mathrm{12}},x_{\mathrm{13}}\right),\left(y_{\mathrm{21}},y_{\mathrm{22}},y_{\mathrm{23}}\right),\dots ,\left(n_{l\mathrm{1}},n_{l\mathrm{2}},n_{l\mathrm{3}}\right)\right\},\end{array}$$

(12)

where i is the identity index of the cat and l is the identifier of the concentric circle (the layer). In this application, the population size is set to 16. There are three backup sensor nodes located in the same layer in every cat. As shown in Figure 4, sensor node tar in the given example is located on the 5th layer.

Figure 4

One of the initialized cats for node tar.

In this case, one of the initialization results of node tar can be described by

$$\begin{array}{cc}& {\text{cat}}_{\mathrm{1}}=\left\{\left(a,b,c\right),\left(d,e,f\right),\left(i,g,h\right),\left(m,j,k\right)\right\}.\end{array}$$

(13)

As given in (13), ${\text{cat}}_{\mathrm{1}}$ consists of nodes in 4 layers, where sensor nodes a and b belong to the first layer and sensor nodes d, e, and f are located in the second layer and so on. There is only one integrated routing path in ${\text{cat}}_{\mathrm{1}}$ ; routing path $\left\{k,h,e,b\right\}$ 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

$$\begin{array}{cc}& V_{\text{cat}}=\left\{\left(v_{11},v_{12},v_{13}\right),\left(v_{21},v_{22},v_{23}\right),\dots ,\left(v_{l1},v_{l2},v_{l3}\right)\right\}.\end{array}$$

(14)

The velocity is corresponding to the composition of cat. For example, $v_{11}$ plays the role of the velocity for the sensor node a. The velocities are constrained within a predefined maximum velocity for every dimension. The maximum velocity set is defined by

$$\begin{array}{cc}& V_{\max }=\left\{v_{\mathrm{1}},v_{\mathrm{2}},v_{\mathrm{3}}{,\dots ,v}_l\right\},\end{array}$$

(15)

where l stands for the numerical value of concentric circles and $v_1<v_2<v_3<\cdots <v_l$ . 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 $]$ . In every cluster, we can find at least one cat, which presents the best fitness value in its own cluster. This cat will be marked as the local best solution in the cluster and is denoted by $C_{{\text{best}}_i}$ , where I 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

$$\begin{array}{cc}& F_x={\alpha }_{\mathrm{1}}\frac{x_{\mathrm{1}}}{{\mathrm{3}}^l}+{\alpha }_{\mathrm{2}}\frac{x_{\mathrm{2}}}{x_{\mathrm{1}}}+{\alpha }_{\mathrm{3}}\frac{\mathrm{1}-x_{\mathrm{3}}}{{\mathrm{3}}^{l-\mathrm{1}}}+{\alpha }_{\mathrm{4}}\frac{x_{\mathrm{4}}}{\mathrm{3}·l},\end{array}$$

(16)

where $x_1$ denotes the sum of all collected paths which go through the current node in the cat, $x_2$ stands for the average power consumption of all connected paths collected in the cat, $x_3$ is the relay counter for calculating the number of forwarding packages for other nodes, $x_4$ is used for counting the number of usage node existing in the cat, and ${\alpha }_1$ , ${\alpha }_2$ , ${\alpha }_3$ , and ${\alpha }_4$ are the weights and ${\sum }_{i=1}^4{\alpha }_i=1$ . The parameters in the fitness function are described in detail as follows.

• (a)

  Path Number ( $x_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 ( $x_2$ ). This parameter accumulates all power consumption caused by paths carried by this cat.

• (c)

  Relay Number ( $x_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 ( $x_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); it stands for the ratio of the found path numbers to the ideal path in the cat:

  $$\begin{array}{cc}& {\text{Path}}_{\text{ratio}}=\frac{x_{\mathrm{1}}}{{\mathrm{3}}^l},\end{array}$$

  (17)

•  

  where Path_ratio represents the path ratio, l is the position circles minus one, and the ideal path number is known as $3^l$ .

• (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:

  $$\begin{array}{cc}& {\text{Ave}}_{\text{power}}=\frac{x_{\mathrm{2}}}{x_{\mathrm{1}}}.\end{array}$$

  (18)

• (c)

  Relay Ratio. The relay ratio is defined by (19). It is known that, in the ideal case, the total relay number is $3^{l-1}$ . Hence, the relay ratio is equal to 1 in the ideal case:

  $$\begin{array}{cc}& R=\frac{x_{\mathrm{3}}}{{\mathrm{3}}^{l-\mathrm{1}}}\text{.}\end{array}$$

  (19)

• (d)

  Usage Rate. The usage rate is defined by (20). It stands for the ratio of the usable nodes to all nodes collected by the cat. In the ideal case, all nodes carried by a cat should be useable; that is, the usage rate is equal to 1:

  $$\begin{array}{cc}& U=\frac{x_{\mathrm{4}}}{\mathrm{3}·l}.\end{array}$$

  (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 $G_{\text{best}}$ ) and the local near-the-best solution (denoted by $G_{{\text{best}}_i}$ ) for the ith cluster.

4.3. An Example Is Given as Follows

Assume the target node tar is located in the 5th layer as shown in Figure 4; the parameter l is 4. For cat₁, we have $x_1=1$ , and Ave_power is the average power consumption of path $\{k,h,e,b\}$ . $R=7$ because the relay ratio is the set of $\{(j,g),(k,h),(e,h),(b,e),(b,f),(d,i),(a,d)\}$ , and $U=4$ because nodes $\{k,h,e,b\}$ are usable.

4.4. Seeking Mode Process

Suppose cat₁ is assigned to move by the seeking mode process; j copies of ${\text{cat}}_{\mathrm{1}}$ are made in the beginning. If the SPC is set to “true” by the user, the copies should remain one set identical to ${\text{cat}}_{\mathrm{1}}$ . Based on the value or CDC and SRD, the rest of the copies are slightly modified. An example is given as follows. Suppose we have cat₁ in the process and ${\text{cat}}_{\mathrm{1}}$ is given in

$$\begin{array}{cc}& {\text{cat}}_{\mathrm{1}}=\left\{\left(a,b,c\right),\left(d,e,f\right),\left(i,g,h\right),\left(m,j,k\right)\right\}.\end{array}$$

(21)

Assume $\text{CDC}=2$ ; nodes m and i are chosen to be the mutative nodes as shown in Figure 5. The node index is modified by $\text{SRD}$ percents. After the process, it is possible that node m is changed to node n; and node i is changed to node p as shown in Figure 6. Calculate and sort the fitness values of all copies by (16) and keep the best cat in the memory.

Figure 5

An example of ${\text{cat}}_{\mathrm{1}}$ in the tracing mode process.

Figure 6

The result of ${\text{cat}}_{\mathrm{1}}$ after the tracing mode process.

4.5. Tracing Mode Process

In the tracing mode process, the cat's velocity should be updated, and the cat will be moved based on its velocity produced by the Taguchi method. The velocity is produced based on $G_{\text{best}}$ and $G_{{\text{best}}_i}$ . We take the same example listed in Figure 5. Let ${\text{cat}}_{\mathrm{1}}$ be initialized for node tar; we get ${CV}_{1,d}\left(t\right)$ and ${CV}_{2,d}\left(t\right)$ two 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 $L_{\mathrm{13}}\left({\mathrm{2}}^{\mathrm{12}}\right)$ orthogonal array is given in Table 1. The values “−1” and “1” in the elements of the orthogonal array indicate the value from ${CV}_{\mathrm{1},d}\left(t\right)$ or ${CV}_{\mathrm{2},d}\left(t\right)$ should be used in the corresponding dimension.

Table 1

The $$L_{\mathrm{13}}({\mathrm{2}}^{\mathrm{12}})$$ orthogonal array.

Experiment number	Considered factors
	A	B	C	D	E	F	G	H	I	J	K	L
1	−1	−1	1	−1	1	1	−1	−1	1	1	−1	1
2	1	−1	−1	−1	−1	1	1	−1	−1	1	1	1
3	−1	1	−1	−1	1	−1	1	−1	1	−1	1	1
4	1	1	1	−1	−1	−1	−1	−1	−1	−1	−1	1
5	−1	−1	1	1	−1	−1	1	−1	1	1	−1	−1
6	1	−1	−1	1	1	−1	−1	−1	−1	1	1	−1
7	−1	1	−1	1	−1	1	−1	−1	1	−1	1	−1
8	1	1	1	1	1	1	1	−1	−1	−1	−1	−1
9	−1	−1	1	−1	1	1	−1	1	−1	−1	1	−1
10	1	−1	−1	−1	−1	1	1	1	1	−1	−1	−1
11	−1	1	−1	−1	1	−1	1	1	−1	1	−1	−1
12	1	1	1	−1	−1	−1	−1	1	1	1	1	−1
13	−1	−1	1	1	−1	−1	1	1	−1	−1	1	1
14	1	−1	−1	1	1	−1	−1	1	1	−1	−1	1
15	−1	1	−1	1	−1	1	−1	1	−1	1	−1	1
16	1	1	1	1	1	1	1	1	1	1	1	1

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 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 LD_ACO [10], AODV [6], and LD_CSO [7] in Table 2. In our 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 $\mathrm{3.5417}\times {10}^6$ for LD_ACO algorithm, and the average power consumption for one node is $\mathrm{1.317}\times {10}^3$ , the maximum consumption is $\mathrm{1.310}\times {10}^4$ , and the minimum is $\mathrm{6.7}\times {10}^1$ . 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.

Table 2

The results of four algorithms.

Nodes	Methods	All	Average	Max	Min
All	LDACO (Ho et al. 2012) [10]	$$\mathrm{3.5417}\times {\mathit{10}}^{\mathit{6}}$$	$$\mathrm{1.317}\times {\mathit{10}}^{\mathit{3}}$$	$$\mathrm{3.10}\times {\mathit{10}}^{\mathit{4}}$$	$$\mathrm{6.7}\times {\mathit{10}}^{\mathit{1}}$$
	AODV (Perkins and Royer, 1999) [6]	$$\mathrm{3.5772}\times {\mathit{10}}^{\mathit{6}}$$	$$\mathrm{1.330}\times {\mathit{10}}^{\mathit{3}}$$	$$\mathrm{8.82}\times {\mathit{10}}^{\mathit{4}}$$	$$\mathrm{6.7}\times {\mathit{10}}^{\mathit{1}}$$
	LDCSO (Kong et al., 2014) [7]	$$\mathrm{3.5881}\times {\mathit{10}}^{\mathit{6}}$$	$$\mathrm{1.334}\times {\mathit{10}}^{\mathit{3}}$$	$$\mathrm{5.15}\times {\mathit{10}}^{\mathit{4}}$$	$$\mathrm{6.7}\times {\mathit{10}}^{\mathit{1}}$$
	Our proposed method	$$\mathrm{2.2984}\times {\mathit{10}}^{\mathit{6}}$$	$$\mathrm{0.855}\times {\mathit{10}}^{\mathit{3}}$$	$$\mathrm{1.41}\times {\mathit{10}}^{\mathit{4}}$$	$$\mathrm{6.7}\times {\mathit{10}}^{\mathit{1}}$$
One	LDACO (Ho et al. 2012) [10]	$$\mathrm{6.7614}\times {\mathit{10}}^{\mathit{5}}$$	$$\mathrm{1.760}\times {\mathit{10}}^{\mathit{3}}$$	$$\mathrm{3.10}\times {\mathit{10}}^{\mathit{4}}$$	$$\mathrm{6.7}\times {\mathit{10}}^{\mathit{1}}$$
	AODV (Perkins and Royer, 1999) [6]	$$\mathrm{7.0002}\times {\mathit{10}}^{\mathit{5}}$$	$$\mathrm{1.822}\times {\mathit{10}}^{\mathit{3}}$$	$$\mathrm{8.82}\times {\mathit{10}}^{\mathit{4}}$$	$$\mathrm{6.7}\times {\mathit{10}}^{\mathit{1}}$$
	LDCSO (Kong et al., 2014) [7]	$$\mathrm{6.9459}\times {\mathit{10}}^{\mathit{5}}$$	$$\mathrm{1.808}\times {\mathit{10}}^{\mathit{3}}$$	$$\mathrm{5.15}\times {\mathit{10}}^{\mathit{4}}$$	$$\mathrm{6.7}\times {\mathit{10}}^{\mathit{1}}$$
	Our proposed method	$$\mathrm{2.9920}\times {\mathit{10}}^{\mathit{5}}$$	$$\mathrm{7.99}\times {\mathit{10}}^{\mathit{2}}$$	$$\mathrm{1.41}\times {\mathit{10}}^{\mathit{4}}$$	$$\mathrm{6.7}\times {\mathit{10}}^{\mathit{1}}$$
Two	LDACO (Ho et al. 2012) [10]	$$\mathrm{5.7792}\times {\mathit{10}}^{\mathit{5}}$$	$$\mathrm{1.505}\times {\mathit{10}}^{\mathit{3}}$$	$$\mathrm{1.95}\times {\mathit{10}}^{\mathit{4}}$$	$$\mathrm{6.7}\times {\mathit{10}}^{\mathit{1}}$$
	AODV (Perkins and Royer, 1999) [6]	$$\mathrm{5.8802}\times {\mathit{10}}^{\mathit{5}}$$	$$\mathrm{1.531}\times {\mathit{10}}^{\mathit{3}}$$	$$\mathrm{3.71}\times {\mathit{10}}^{\mathit{4}}$$	$$\mathrm{6.7}\times {\mathit{10}}^{\mathit{1}}$$
	LDCSO (Kong et al., 2014) [7]	$$\mathrm{5.9846}\times {\mathit{10}}^{\mathit{5}}$$	$$\mathrm{1.558}\times {\mathit{10}}^{\mathit{3}}$$	$$\mathrm{4.12}\times {\mathit{10}}^{\mathit{4}}$$	$$\mathrm{3.5}\times {\mathit{10}}^{\mathit{1}}$$
	Our proposed method	$$\mathrm{2.3038}\times {\mathit{10}}^{\mathit{5}}$$	$$\mathrm{6.01}\times {\mathit{10}}^{\mathit{2}}$$	$$\mathrm{7.14}\times {\mathit{10}}^{\mathit{3}}$$	$$\mathrm{9.0}\times {\mathit{10}}^{\mathit{1}}$$
Six	LDACO (Ho et al. 2012) [10]	$$\mathrm{1.8860}\times {\mathit{10}}^{\mathit{5}}$$	$$\mathrm{4.91}\times {\mathit{10}}^{\mathit{2}}$$	$$\mathrm{2.81}\times {\mathit{10}}^{\mathit{3}}$$	$$\mathrm{5.7}\times {\mathit{10}}^{\mathit{1}}$$
	AODV (Perkins and Royer, 1999) [6]	$$\mathrm{1.7568}\times {\mathit{10}}^{\mathit{5}}$$	$$\mathrm{4.57}\times {\mathit{10}}^{\mathit{2}}$$	$$\mathrm{9.44}\times {\mathit{10}}^{\mathit{3}}$$	$$\mathrm{1.2}\times {\mathit{10}}^{\mathit{1}}$$
	LDCSO (Kong et al., 2014) [7]	$$\mathrm{1.7617}\times {\mathit{10}}^{\mathit{5}}$$	$$\mathrm{4.58}\times {\mathit{10}}^{\mathit{2}}$$	$$\mathrm{8.02}\times {\mathit{10}}^{\mathit{3}}$$	$$\mathrm{1.2}\times {\mathit{10}}^{\mathit{1}}$$
	Our proposed method	$$\mathrm{4.7954}\times {\mathit{10}}^{\mathit{5}}$$	$$\mathrm{1.248}\times {\mathit{10}}^{\mathit{3}}$$	$$\mathrm{3.29}\times {\mathit{10}}^{\mathit{3}}$$	$$\mathrm{2.5}\times {\mathit{10}}^{\mathit{2}}$$
Seven	LDACO (Ho et al. 2012) [10]	$$\mathrm{7.4627}\times {\mathit{10}}^{\mathit{4}}$$	$$\mathrm{1.94}\times {\mathit{10}}^{\mathit{2}}$$	$$\mathrm{7.09}\times {\mathit{10}}^{\mathit{2}}$$	$$\mathrm{5.8}\times {\mathit{10}}^{\mathit{1}}$$
	AODV (Perkins and Royer, 1999) [6]	$$\mathrm{8.4859}\times {\mathit{10}}^{\mathit{4}}$$	$$\mathrm{2.20}\times {\mathit{10}}^{\mathit{2}}$$	$$\mathrm{3.23}\times {\mathit{10}}^{\mathit{3}}$$	$$\mathrm{1.5}\times {\mathit{10}}^{\mathit{1}}$$
	LDCSO (Kong et al., 2014) [7]	$$\mathrm{8.8532}\times {\mathit{10}}^{\mathit{4}}$$	$$\mathrm{2.26}\times {\mathit{10}}^{\mathit{2}}$$	$$\mathrm{1.91}\times {\mathit{10}}^{\mathit{3}}$$	$$\mathrm{3.1}\times {\mathit{10}}^{\mathit{1}}$$
	Our proposed method	$$\mathrm{3.0722}\times {\mathit{10}}^{\mathit{5}}$$	$$\mathrm{8.00}\times {\mathit{10}}^{\mathit{2}}$$	$$\mathrm{3.87}\times {\mathit{10}}^{\mathit{3}}$$	$$\mathrm{2.3}\times {\mathit{10}}^{\mathit{2}}$$

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 of which the inner layer nodes usually are out of battery is 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.