# Quantum Clone Elite Genetic Algorithm-Based Evaluation Mechanism for Maximizing Network Efficiency in Soil Moisture Wireless Sensor Networks

Authors: Jing Xiao; Yang Liu; Jie Zhou
Journal: Journal of Sensors
 (2021)

---

## Abstract

In agriculture, soil moisture wireless sensor networks (SMWSNs) are used to monitor the growth of crops for obtaining higher yields. The purpose of this paper is to improve the network efficiency of SMWSNs. Therefore, we propose a novel network efficiency evaluation mechanism which is suitable for soil moisture sensors and design a sensor target allocation model (STAM) for the actual agricultural situation. After that, a quantum clone elite genetic algorithm (QCEGA) is proposed; then, QCEGA is applied to optimize the STAM for obtaining optimal results. QCEGA uses the parallel mechanism of quantum computing to encode individuals, integrates the quantum revolving gate in quantum computing and the concept of cloning in biology to avoid the algorithm from falling into local optimum, and applies the elite strategy to speed up the convergence of the algorithm. Subsequently, the proposed algorithm is compared with simulated annealing (SA) and particle swarm optimization (PSO). Under the novel network efficiency evaluation mechanism, the simulation results demonstrate that the network efficiency based on QCEGA is higher than that of SA and PSO; what is more, QCEGA has better convergence performance. In comparison with traditional wireless sensor network efficiency evaluation approaches, our methods are more in line with the development of modern agriculture and can effectively improve the efficiency of SMWSNs, thus ensuring that crops can have a better growth condition.


---

## Body

## 1. Introduction

Although the current crop yields have increased, the irrigation management of crops has not been satisfactory [1]. At present, the number of people engaged in agricultural activities is on a downward trend, resulting in increasing labor costs. The Internet of things technology develops quickly, and soil moisture sensor networks (SMWSNs) are already used in the actual production process. Moreover, the development of artificial intelligence, cloud computing, and big data has also greatly improved SMWSN efficiency [2–4]. However, due to the particularity of soil moisture sensors, the original evaluation mechanism for wireless sensor networks is not well applicable to SMWSNs, so it is urgent to propose a novel network efficiency evaluation mechanism [5].In previous works, it proposes to use sensor nodes to dynamically monitor the land that needs to be irrigated [6–8], which can effectively save human resource. Nonetheless, the network efficiency optimization problem is too complex to be solved by traditional mathematical methods [9, 10]. Yu et al. [11] use PSO to increase the network efficiency, whose effect is better than before, but it has a problem of falling into local optimum. Tang et al. [12] use SA to improve the soil moisture monitoring ability, which has low algorithm complexity. However, it has the disadvantages of local optimum and slow convergence ability.In this paper, a novel network efficiency evaluation mechanism, a sensor node target allocation model of SMWSNs, and a novel algorithm are proposed. The purpose of the evaluation mechanism and the model is to maximize the network efficiency of the SMWSNs. In addition, to verify the model’s effectiveness, the mathematical model of target allocation is firstly shown. Subsequently, the quantum operator, clonal operator, and elite operator are applied into the traditional genetic algorithm (GA). The simulation results show that the proposed algorithm effectively improves the network efficiency.The main contributions can be listed as follows:(1)
A novel evaluation mechanism for SMWSNs is proposed(2)
We have designed a novel sensor target allocation model suitable for SMWSNs, which comprehensively considers different sensor positions and soil depth values(3)
A quantum clone elite genetic algorithm (QCEGA) that combines the concepts of quantum computing and cloning is proposed. This algorithm can obtain the optimal target allocation method and has good convergence performance(4)
The target allocation method based on QCEGA is compared with SA and PSO in terms of network efficiency, convergence performance, and computational complexityThe structure of the paper can be shown as follows. Related works are given in Section2. Section 3 shows the network efficiency evaluation mechanism and the target allocation model. In Section 4, to obtain the optimal solution, QCEGA is introduced. Section 5 presents the effectiveness of QCEGA through simulation experiments and makes discussion. In Section 5, the conclusion part is given.


## 2. Related Work

Recently, there are relatively few researches on soil moisture wireless sensor networks. However, many scholars have proposed ways to improve the efficiency of wireless sensor networks (WSNs).In [13], with the purpose of enhancing the allocation efficiency of WSNs, the authors improve the wireless sensor network coverage model by analyzing the structural characteristics of the wireless sensor network. However, because it introduces the optimization links into the PSO, it has increased the computational complexity. On the other hand, to increase the energy management efficiency of WRSNs, Gong et al. [14] propose a two-phase scheme for obtaining the best energy allocation method by dealing with the model’s game equilibrium. Although the two-phase scheme improves coverage efficiency and energy supply efficiency, it has poor convergence performance. In addition, a method of node optimization coverage for passive monitoring system of 3D-WSN based on a link model is proposed in [15]. The method constructs a three-dimensional WSN link coverage model based on a wireless link-aware area and uses a network coverage based on a cube to describe the network’s service quality. Cao et al. [16] mention the concept of edge computing, and a localization method for WSNs is proposed in this paper. A dynamic deployment technology which bases an improved genetic algorithm (IDDT-GA) is proposed to minimize the number of nodes and reduce the overlap area between adjacent nodes [17]. However, the algorithm has long running time. Zanaj et al. [18] propose a customizable heuristic method for WSN topology design based on a genetic algorithm. This method enables users to construct network topologies which are selected by optimizing different potential configurations, such as coverage, energy efficiency, system node degrees in the environment, and network lifetime, but the setting of related weight coefficients is a problem worthy of careful consideration.In addition, in terms of optimizing the network efficiency of WSNs, Kumar et al. [19] consider the impact of multiple parameters on the energy consumption of WSNs and propose a lifetime maximization technology based on an ant colony algorithm and Huffman coding. After that, the authors verify the validity of four performance indicators: energy consumption, average remaining energy, number of live sensors, and standard deviation of energy. On the other hand, to reduce the cost of WSN resource sharing, a nondominated sorting genetic algorithm is proposed to maximize the fault tolerance of the network and minimize the delay [20].In recent years, quantum optimization algorithms have been increasingly used to improve the network efficiency of WSNs. Wu et al. [21] propose a positioning algorithm based on quantum particle swarm optimization, which uses the parallelism of quantum computing to improve the accuracy of positioning. Similarly, Kanchan and Pushparaj [22] also propose a quantum heuristic PSO, but their purpose is to extend the lifetime of the network by clustering the nodes in WSNs. In addition, Prasad and Panigrahi [23] merge the quantum concept into PSO to optimize the maximum likelihood (ML) parameters for enhancing the positioning accuracy of WSNs. An algorithm that combines quantum computing and artificial bee colony is proposed to optimize the search of bees to improve food source substitution strategies, thereby optimizing data collection and distribution in WSNs [24]. Chu et al. [25] use quantum computing to ameliorate the performance of the symbiosis organism search, which improves the algorithm’s running speed and convergence ability. However, the simple use of quantum optimization algorithms cannot effectively improve the quality of the solution, and some other techniques need to be combined to further optimize the search capabilities of the algorithm.In this paper, a novel genetic algorithm combining quantum optimization, cloning operator, and elite operator is proposed. The algorithm has good performance in terms of solution quality and convergence speed in enhancing network efficiency in SMWSNs.


## 3. Evaluation Mechanism and System Model

### 3.1. Problem Description

In the SMWSNs, moisture sensors should be placed in the land to monitor the moisture status of crops. Different from other wireless sensors, multiple moisture sensors need to be placed at the same target point to work together, and these sensors are located at different depth values. We need to place limited soil moisture sensors in suitable locations to obtain the best network efficiency and then grasp the moisture information of crops in time to irrigate them. In addition, Table1 is an explanation of the symbols that appear in this part.Table 1
List of symbols.
NotationDescriptionmNumber of soil moisture sensor nodesnNumber of target pointsxNumber of sensors that need to be placed at each target pointyNumber of depth valuesDSensor placement advantage matrixD∗Actual sensor placement advantage matrixVSensor monitoring effect matrixYSolution in decimal formY∗Solution in binary formLFitness matrixlFitness value of each sensor placementfitFitness function


### 3.2. Evaluation Mechanism

To better describe the network efficiency of SMWSNs, we should consider not only the difficulty of placing sensors but also the monitoring effects of soil moisture sensors at different depths. Therefore, we establish two evaluation matrices: one is the sensor placement advantage matrix and the other is the sensor monitoring effect matrix. In view of the limitations of the actual site, we use a random method to generate these two matrices. If it is applied to an actual project, we only need to replace the values in the matrix with real values, which will not affect the problem to be solved. The so-called network efficiency refers to the sum of the monitoring effects of all soil moisture sensors located at different depths. The monitoring effect of each sensor is affected by both the placement advantage matrix and the monitoring effect matrix. In detail, different soil depth values can be expressed as shown in Figure1.Figure 1
Schematic diagram of different soil depths.


### 3.3. Sensor Target Allocation Model

To maximize the network efficiency of SMWSNs, a mathematical model is shown with reference to some restrictions of calculating abilities and constrained monitoring range. In [26], it uses a model based on first-in first-out logic to optimize the task allocation problem in SMWSNs. Paper [27] studies the problem of complex application allocation and proposes a model that considers multifactor and sensor heterogeneity. The model can assign complex applications to appropriate sensor nodes, thereby maximizing the network efficiency of WSNs.A SMWSN-based sensor allocation model is proposed in this paper. The model can be described concisely as supposing that there arem soil moisture sensor nodes and n target points in SMWSNs. Each target point is evenly distributed in a certain area and has y depth values to choose. x sensor nodes should be put into every target point for monitoring the moisture of the soil (x<y). Sensor nodes located at different depths will get different monitoring advantage values. The goal of the paper is to obtain the highest network efficiency value by assigning sensor nodes at different depths.It is assumed that the monitoring effect of each depth has been evaluated before sensor allocation, and the advantages of sensor placement have been evaluated in advance. The advantage of thejth sensor allocated to the bth target point can be expressed as Dj,b. The advantage matrix of the sensors being assigned to the target points can be shown as
(1)D=d1,1d1,2⋯d1,B−1d1,Bd2,1d2,2⋯d2,B−1d2,B⋮dj,b⋮dJ−1,1dJ−1,2⋯dJ−1,B−1dJ−1,BdJ,1dJ,2⋯dJ,B−1dJ,BJ∈1,2,⋯,m,B∈1,2,⋯,n,where m is the number of soil moisture sensors and n is the number of targets. Each depth has the value of advantage which is shown in
(2)V=v1,1v1,2⋯v1,K−1v1,Kv2,1v2,2⋯v2,K−1v2,K⋮vb,k⋮vB−1,1vB−1,2⋯vB−1,K−1vB−1,KvB,1vB,2⋯vB,K−1vB,KB∈1,2,⋯,n,K∈1,2,⋯,y,where y is the number of depth values.Specifically, if an individual has 4 depth values, 10 soil moisture sensor nodes, and 5 target points, 2 sensor nodes need to be placed in each target point. A solution is generated randomly by the individual in (3).
(3)Y=2123144342.To facilitate the execution of the next operation, the decimal code is ought to be converted to a binary code, and the target allocation matrix in binary form can be expressed as(4)Y∗=01001101010011011010.In (4), Y∗j,b=1 stands for the sensor at the jth depth being placed to the bth target point. Otherwise, the sensor at thejthdepth is not placed to thebthtarget point.According to equations (1) and (4), D∗ is calculated in (5). It represents the actual sensor placement advantage value.
(5)D∗=D⋅Y∗,where Y∗ is the target allocation matrix in binary form and D is the sensor placement advantage matrix. The value in D is the advantage value of the sensor at the jth depth being placed to the bth target point. In the previous example, D∗ can be expressed as
(6)D∗=0d1,200d5,1d2,10d2,30d5,200d3,3d3,40d4,1d1,40d4,40.Since the advantage values of sensor nodes at different soil depths are placed inD∗, with the aim of obtaining the overall SMWSN advantage value, it is necessary to multiply D∗ with the sensor monitoring effect matrix V for obtaining the fitness matrix L, which is shown in
(7)L=V⋅D∗.According to the example cited above,L can be specifically expressed as
(8)L=0l1,200l5,1l2,10l2,30l5,200l3,3l3,40l4,1l1,40l4,40.After the fitness matrixL is obtained, the fitness function in the target allocation problem in SMWSNs can be expressed as
(9)fit=∑j=1y∑b=1nLj,b,where y is the number of soil depth values and n is the number of target points.In SMWSNs, not only should the allocation of the soil moisture sensor nodes meet the actual needs but also it needs to increase the overall network efficiency. The network efficiency of SMWSNs represents the total network benefit monitored by soil moisture sensor nodes. Due to the fact that the soil moisture sensor nodes in SMWSNs are homogeneous, the monitoring efficiency of every sensor node is roughly the same. For SMWSNs, the allocation of soil moisture sensor nodes can usually achieve better service quality and higher overall network efficiency. Therefore, it is necessary to allocate sensor nodes according to the soil moisture monitoring capabilities of sensor nodes, and the sensors locate at different soil depths of different target points.


## 3.1. Problem Description

In the SMWSNs, moisture sensors should be placed in the land to monitor the moisture status of crops. Different from other wireless sensors, multiple moisture sensors need to be placed at the same target point to work together, and these sensors are located at different depth values. We need to place limited soil moisture sensors in suitable locations to obtain the best network efficiency and then grasp the moisture information of crops in time to irrigate them. In addition, Table1 is an explanation of the symbols that appear in this part.Table 1
List of symbols.
NotationDescriptionmNumber of soil moisture sensor nodesnNumber of target pointsxNumber of sensors that need to be placed at each target pointyNumber of depth valuesDSensor placement advantage matrixD∗Actual sensor placement advantage matrixVSensor monitoring effect matrixYSolution in decimal formY∗Solution in binary formLFitness matrixlFitness value of each sensor placementfitFitness function


## 3.2. Evaluation Mechanism

To better describe the network efficiency of SMWSNs, we should consider not only the difficulty of placing sensors but also the monitoring effects of soil moisture sensors at different depths. Therefore, we establish two evaluation matrices: one is the sensor placement advantage matrix and the other is the sensor monitoring effect matrix. In view of the limitations of the actual site, we use a random method to generate these two matrices. If it is applied to an actual project, we only need to replace the values in the matrix with real values, which will not affect the problem to be solved. The so-called network efficiency refers to the sum of the monitoring effects of all soil moisture sensors located at different depths. The monitoring effect of each sensor is affected by both the placement advantage matrix and the monitoring effect matrix. In detail, different soil depth values can be expressed as shown in Figure1.Figure 1
Schematic diagram of different soil depths.


## 3.3. Sensor Target Allocation Model

To maximize the network efficiency of SMWSNs, a mathematical model is shown with reference to some restrictions of calculating abilities and constrained monitoring range. In [26], it uses a model based on first-in first-out logic to optimize the task allocation problem in SMWSNs. Paper [27] studies the problem of complex application allocation and proposes a model that considers multifactor and sensor heterogeneity. The model can assign complex applications to appropriate sensor nodes, thereby maximizing the network efficiency of WSNs.A SMWSN-based sensor allocation model is proposed in this paper. The model can be described concisely as supposing that there arem soil moisture sensor nodes and n target points in SMWSNs. Each target point is evenly distributed in a certain area and has y depth values to choose. x sensor nodes should be put into every target point for monitoring the moisture of the soil (x<y). Sensor nodes located at different depths will get different monitoring advantage values. The goal of the paper is to obtain the highest network efficiency value by assigning sensor nodes at different depths.It is assumed that the monitoring effect of each depth has been evaluated before sensor allocation, and the advantages of sensor placement have been evaluated in advance. The advantage of thejth sensor allocated to the bth target point can be expressed as Dj,b. The advantage matrix of the sensors being assigned to the target points can be shown as
(1)D=d1,1d1,2⋯d1,B−1d1,Bd2,1d2,2⋯d2,B−1d2,B⋮dj,b⋮dJ−1,1dJ−1,2⋯dJ−1,B−1dJ−1,BdJ,1dJ,2⋯dJ,B−1dJ,BJ∈1,2,⋯,m,B∈1,2,⋯,n,where m is the number of soil moisture sensors and n is the number of targets. Each depth has the value of advantage which is shown in
(2)V=v1,1v1,2⋯v1,K−1v1,Kv2,1v2,2⋯v2,K−1v2,K⋮vb,k⋮vB−1,1vB−1,2⋯vB−1,K−1vB−1,KvB,1vB,2⋯vB,K−1vB,KB∈1,2,⋯,n,K∈1,2,⋯,y,where y is the number of depth values.Specifically, if an individual has 4 depth values, 10 soil moisture sensor nodes, and 5 target points, 2 sensor nodes need to be placed in each target point. A solution is generated randomly by the individual in (3).
(3)Y=2123144342.To facilitate the execution of the next operation, the decimal code is ought to be converted to a binary code, and the target allocation matrix in binary form can be expressed as(4)Y∗=01001101010011011010.In (4), Y∗j,b=1 stands for the sensor at the jth depth being placed to the bth target point. Otherwise, the sensor at thejthdepth is not placed to thebthtarget point.According to equations (1) and (4), D∗ is calculated in (5). It represents the actual sensor placement advantage value.
(5)D∗=D⋅Y∗,where Y∗ is the target allocation matrix in binary form and D is the sensor placement advantage matrix. The value in D is the advantage value of the sensor at the jth depth being placed to the bth target point. In the previous example, D∗ can be expressed as
(6)D∗=0d1,200d5,1d2,10d2,30d5,200d3,3d3,40d4,1d1,40d4,40.Since the advantage values of sensor nodes at different soil depths are placed inD∗, with the aim of obtaining the overall SMWSN advantage value, it is necessary to multiply D∗ with the sensor monitoring effect matrix V for obtaining the fitness matrix L, which is shown in
(7)L=V⋅D∗.According to the example cited above,L can be specifically expressed as
(8)L=0l1,200l5,1l2,10l2,30l5,200l3,3l3,40l4,1l1,40l4,40.After the fitness matrixL is obtained, the fitness function in the target allocation problem in SMWSNs can be expressed as
(9)fit=∑j=1y∑b=1nLj,b,where y is the number of soil depth values and n is the number of target points.In SMWSNs, not only should the allocation of the soil moisture sensor nodes meet the actual needs but also it needs to increase the overall network efficiency. The network efficiency of SMWSNs represents the total network benefit monitored by soil moisture sensor nodes. Due to the fact that the soil moisture sensor nodes in SMWSNs are homogeneous, the monitoring efficiency of every sensor node is roughly the same. For SMWSNs, the allocation of soil moisture sensor nodes can usually achieve better service quality and higher overall network efficiency. Therefore, it is necessary to allocate sensor nodes according to the soil moisture monitoring capabilities of sensor nodes, and the sensors locate at different soil depths of different target points.


## 4. QCEGA-Based Target Allocation in SMWSNs to Maximize Network Efficiency

To obtain a better performance of the target allocation in SMWSNs, a QCEGA-based allocation method is proposed. The method is inspired by the traditional genetic algorithm, and it effectively avoids falling into local optimum. The strategy allows QCEGA to handle the distribution of soil moisture sensors and get the best solution. In the method of QCEGA, the significant improvement is the addition of quantum operator, clone operator, and elite operator to the traditional GA.Compared with traditional optimization algorithms, GA has the advantages of wide range of use, strong robustness, less restricted conditions, and simple use. GA basically has no restrictions on the problem to be solved and does not require complex mathematical algorithm support. With the development of modern computer technology, its superiority is more obvious when studying some complex problems with multiple factors. With the continuous furthering of research, GA is constantly improving, and its application range is getting wider and wider. However, classic GA is prone to fall into being premature and has poor performance.The procedures of QCEGA can be described as population encoding, initializing the population, calculating fitness, selection, crossover, mutation, quantum operator, clonal operator, elite operator, and termination condition.


### 4.1. Population Encoding

The above-mentioned sensor node target allocation is the problem of placing the soil moisture sensor at an appropriate depth. Since the moisture sensors used in this problem have the same structure and the sensors at different target points do not affect each other, binary coding can be used [28, 29]. The idea of coding is to treat the allocation sequence of all sensors as the various genes in the chromosome. The sequence of the genes represents the order of the depth value of the soil. An individual carries a complete allocation schema. For example, there are 6 different target points, each target point has 6 different soil depth values, and 3 soil moisture sensors need to be placed in each target point. Then, the corresponding coding matrix can be expressed as
(10)010100101110110010001011110101001001.In (10), the first column indicates that there are 6 depth values at the first target point, and this column selects the second, third, and fifth depth values to place the soil moisture sensor. The analysis of the remaining columns is the same as that of the first column.


### 4.2. Initializing the Population

Since the problem of sensor target allocation is to place multiple soil moisture sensors in one target point, the population should be three-dimensional. Due to the particularity of the problem, it is necessary to ensure that a specified number of sensors are placed on a target point to better complete the task of soil moisture monitoring [30]. Therefore, the coding of the population needs to be restricted. Assuming that the quantity of individuals is P, then the population and restriction can be shown as
(11)pop=h1,1h1,2⋯h1,M−1h1,Mh2,1h2,2⋯h2,M−1h2,M⋮hn,m⋮hN−1,1hN−1,2⋯hN−1,M−1hN−1,MhN,1hN,2⋯hN,m−1hN,Mhn,m∈0,1,(12)∑n=1Nhn,m=xm∈1,2,⋯,M,where N represents the quantity of target points, M is the quantity of soil depth values, and x is the quantity of sensors that should be placed at each target point.


### 4.3. Calculating Fitness

With the purpose of solving the problem of target allocation in SMWSNs, individual fitness calculation is an important tool. A high fitness of an individual indicates that a target allocation plan based on its genetic sequence can obtain a better performance. On the contrary, an individual with a lower fitness suggests that its plan is not optimal. QCEGA excludes individuals with low fitness through selection operation and retains individuals with high adaptability. Fitness is the criterion for judging the pros and cons of individuals, and it is calculated according to equation (9).


### 4.4. Selection

In the genetic algorithm, the selection operation is to make the genes of high-fitness individuals have a greater probability of being inherited to the next generation. In solving the problem of sensor target allocation, the goal is to maximize the network efficiency, so the probability of selection operation is proportional to the fitness of the individual. Assuming that there areG individuals in the population, the probability of the gth individual being determined can be presented as
(13)WselectGg=FGg∑i=1GFGi,where Wselect represents the selection probability of an individual, Gg is the gth individual in the population, and FGg represents the fitness value of Gg.


### 4.5. Crossover

To better solve the problem of sensor target allocation in SMWSNs, the traditional two-point crossover operator needs to be improved [31]. Since the individuals in the population are three-dimensional, the crossover operation can be transformed into the crossover of the two-dimensional matrix. Supposing there are m target points, the specific crossover operation is to select a cross point q1<q<m and then keep the genes in front of q unchanged and exchange the genes behind q. To better understand the crossover process, we can give an example. Before crossover, two individuals can be shown as equations (15) and (16).
(14)individual1before=a11a12a13a14a21a22a23a24a31a32a33a34,(15)individual2before=b11b12b13b14b21b22b23b24b31b32b33b34.The crosspointq can be 1 to 3; if we take q=2, then the two individuals after crossover can be expressed as equations (17) and (18).
(16)individual1after=a11a12b13b13a21a22b23b24a31a32b33b34,(17)individual2after=b11b12a13a14b21b22a23a24b31b32a33a34.


### 4.6. Mutation

The mutation operation is to break the original gene combination of the individual and enable the population to evolve in more diverse directions. Through the mutation of genes, the local search ability of the algorithm can be improved. Due to the fact that binary coding is used in QCEGA, the mutation operation is to reverse the selected mutation bit on the premise of mutation probabilityP. For example, if the position before mutation is 1, then the position after mutation is 0. The mutation process is shown in Figure 2.Figure 2
Mutation operation.


### 4.7. Quantum Operator

The quantum operator is a probabilistic search method based on quantum computing. Compared with the classical swarm intelligent algorithm, quantum operators can effectively improve the algorithm’s global search capability and convergence speed [32]. QCEGA is a novel algorithm that combines quantum operator. It mainly uses concepts of qubits and quantum superposition states in quantum computing to improve the global search and optimization ability [33]. In QCEGA, each individual in the population is represented by a set of binary numbers and a set of qubit probability amplitudes. Therefore, each individual has the ability to search the solution space in parallel, which effectively improves the search efficiency. In QCEGA, each individual can update the optimal solution through the quantum revolving gate during the evolution process, thus realizing the quantum search mechanism in the iterative process.In QCEGA, the quantum probability amplitude is used to accelerate the convergence speed and improve the global search capability of the algorithm. The quantum probability amplitude is shown in equation (18).
(18)Q=q1,1q1,2⋯q1,J−1q1,Jq2,1q2,2⋯q2,J−1q2,J⋮qi,j⋮qI−1,1qI−1,2⋯qI−1,J−1qI−1,JqI,1qI,2⋯qI,J−1qI,Jqi,j∈0,1,where Q is the quantum probability amplitude matrix, I is the number of target points, and J is the number of soil depths.After all individuals in the population are updated, the quantum probability amplitude will be updated according to the optimal individual in the last iteration with the quantum revolving gate. The quantum revolving gate is shown in Algorithm1.Algorithm 1. Quantum revolving gate.
Input: The quantum probability amplitude matrix Q, the number of target points n, the number of soil depths y, quantum probability amplitude increment ∆Output: The updated quantum probability amplitude matrix Q1.for i from 1 to n do2.for j from 1 to y do3.ifQ (i, j) ==1 andQ (i, j) <1 then4.Q (i, j) = Q (i, j) + ∆5.else ifQ (i, j) ==0 andQ (i, j) >0 then6.Q (i, j) = Q (i, j) - ∆7.   end if8.end for9.end for10. ReturnQIn addition, the quantum NOT gate is used to increase the diversity of solutions in the target allocation problem in SMWSNs. The quantum NOT gate is shown in Algorithm2.Algorithm 2. Quantum NOT gate.
Input: The quantum probability amplitude matrix Q, the number of target points n, the number of soil depths y, probability R, random number r between 0 and 1Output: The updated quantum probability amplitude matrix Q1.for i from 1 to n do2.for j from 1 to y do3.ifr < R then4.Q (i, j) =1 - Q (i, j)5.    end if6.end for7.end for8. ReturnQ


### 4.8. Clone Operator

To enhance the speed of convergence, QCEGA uses a clone operator to make clonal expansion of the outstanding individuals in the iterative process [34]. The probability of an individual being selected for cloning is determined by its advantage value. In each cloning process, a certain proportion of fitness individuals are selected for cloning. For example, assuming that there are R individuals in the population, clonal expansion is performed by selecting S individuals with the highest advantage as the mother during each iteration (S<R). After the cloning process, to increase the diversity of the population, it is necessary to perform mutation operations on the generated individuals. The mutation operation here includes quantum revolving gate operation and quantum NOT operation.


### 4.9. Elite Operator

The elite operator of QCEGA is the establishment of the elite population. The specific operation is to establish a population from the most adaptive individuals of the previous generation and then use the elite population to replace the least adaptive individuals in the next generation [35]. Due to the fact that the optimal individual may be destroyed by mutation and crossover operations, the elite operator can retain the optimal one to ensure the performance of the algorithm.


### 4.10. Steps of the Algorithm

The following steps can be used to describe the execution of QCEGA.Step 1. Set the initial parameters in QCEGA, generate a matrix of the advantage of placing sensors according to equation (1), generate a matrix of sensor monitoring effects using equation (2), and generate a quantum probability amplitude matrix according to equation (18).Step 2. Obtain the fitness value of the initial population using equation (9), and record the optimal network efficiency of the individual.Step 3. Execute the selection operation according to equation (13).Step 4. Execute the crossover operation.Step 5. Execute the mutation operation.Step 6. Calculate the fitness of the new population with equation (9).Step 7. Execute the clone operator.Step 8. Do high-probability mutation of the cloned population and make calculation of the new population’s fitness according to equation (9).Step 9. Execute the elite operator.Step 10. Assign the obtained clonal population to the next-generation population.Step 11. Update the quantum probability amplitude according to Algorithms1 and 2.Step 12. If the maximum iteration is not reached, return to step 3; otherwise, the algorithm terminates execution and outputs the optimal solution.The algorithm flowchart is shown in Figure3.Figure 3
Flowchart of QCEGA.


## 4.1. Population Encoding

The above-mentioned sensor node target allocation is the problem of placing the soil moisture sensor at an appropriate depth. Since the moisture sensors used in this problem have the same structure and the sensors at different target points do not affect each other, binary coding can be used [28, 29]. The idea of coding is to treat the allocation sequence of all sensors as the various genes in the chromosome. The sequence of the genes represents the order of the depth value of the soil. An individual carries a complete allocation schema. For example, there are 6 different target points, each target point has 6 different soil depth values, and 3 soil moisture sensors need to be placed in each target point. Then, the corresponding coding matrix can be expressed as
(10)010100101110110010001011110101001001.In (10), the first column indicates that there are 6 depth values at the first target point, and this column selects the second, third, and fifth depth values to place the soil moisture sensor. The analysis of the remaining columns is the same as that of the first column.


## 4.2. Initializing the Population

Since the problem of sensor target allocation is to place multiple soil moisture sensors in one target point, the population should be three-dimensional. Due to the particularity of the problem, it is necessary to ensure that a specified number of sensors are placed on a target point to better complete the task of soil moisture monitoring [30]. Therefore, the coding of the population needs to be restricted. Assuming that the quantity of individuals is P, then the population and restriction can be shown as
(11)pop=h1,1h1,2⋯h1,M−1h1,Mh2,1h2,2⋯h2,M−1h2,M⋮hn,m⋮hN−1,1hN−1,2⋯hN−1,M−1hN−1,MhN,1hN,2⋯hN,m−1hN,Mhn,m∈0,1,(12)∑n=1Nhn,m=xm∈1,2,⋯,M,where N represents the quantity of target points, M is the quantity of soil depth values, and x is the quantity of sensors that should be placed at each target point.


## 4.3. Calculating Fitness

With the purpose of solving the problem of target allocation in SMWSNs, individual fitness calculation is an important tool. A high fitness of an individual indicates that a target allocation plan based on its genetic sequence can obtain a better performance. On the contrary, an individual with a lower fitness suggests that its plan is not optimal. QCEGA excludes individuals with low fitness through selection operation and retains individuals with high adaptability. Fitness is the criterion for judging the pros and cons of individuals, and it is calculated according to equation (9).


## 4.4. Selection

In the genetic algorithm, the selection operation is to make the genes of high-fitness individuals have a greater probability of being inherited to the next generation. In solving the problem of sensor target allocation, the goal is to maximize the network efficiency, so the probability of selection operation is proportional to the fitness of the individual. Assuming that there areG individuals in the population, the probability of the gth individual being determined can be presented as
(13)WselectGg=FGg∑i=1GFGi,where Wselect represents the selection probability of an individual, Gg is the gth individual in the population, and FGg represents the fitness value of Gg.


## 4.5. Crossover

To better solve the problem of sensor target allocation in SMWSNs, the traditional two-point crossover operator needs to be improved [31]. Since the individuals in the population are three-dimensional, the crossover operation can be transformed into the crossover of the two-dimensional matrix. Supposing there are m target points, the specific crossover operation is to select a cross point q1<q<m and then keep the genes in front of q unchanged and exchange the genes behind q. To better understand the crossover process, we can give an example. Before crossover, two individuals can be shown as equations (15) and (16).
(14)individual1before=a11a12a13a14a21a22a23a24a31a32a33a34,(15)individual2before=b11b12b13b14b21b22b23b24b31b32b33b34.The crosspointq can be 1 to 3; if we take q=2, then the two individuals after crossover can be expressed as equations (17) and (18).
(16)individual1after=a11a12b13b13a21a22b23b24a31a32b33b34,(17)individual2after=b11b12a13a14b21b22a23a24b31b32a33a34.


## 4.6. Mutation

The mutation operation is to break the original gene combination of the individual and enable the population to evolve in more diverse directions. Through the mutation of genes, the local search ability of the algorithm can be improved. Due to the fact that binary coding is used in QCEGA, the mutation operation is to reverse the selected mutation bit on the premise of mutation probabilityP. For example, if the position before mutation is 1, then the position after mutation is 0. The mutation process is shown in Figure 2.Figure 2
Mutation operation.


## 4.7. Quantum Operator

The quantum operator is a probabilistic search method based on quantum computing. Compared with the classical swarm intelligent algorithm, quantum operators can effectively improve the algorithm’s global search capability and convergence speed [32]. QCEGA is a novel algorithm that combines quantum operator. It mainly uses concepts of qubits and quantum superposition states in quantum computing to improve the global search and optimization ability [33]. In QCEGA, each individual in the population is represented by a set of binary numbers and a set of qubit probability amplitudes. Therefore, each individual has the ability to search the solution space in parallel, which effectively improves the search efficiency. In QCEGA, each individual can update the optimal solution through the quantum revolving gate during the evolution process, thus realizing the quantum search mechanism in the iterative process.In QCEGA, the quantum probability amplitude is used to accelerate the convergence speed and improve the global search capability of the algorithm. The quantum probability amplitude is shown in equation (18).
(18)Q=q1,1q1,2⋯q1,J−1q1,Jq2,1q2,2⋯q2,J−1q2,J⋮qi,j⋮qI−1,1qI−1,2⋯qI−1,J−1qI−1,JqI,1qI,2⋯qI,J−1qI,Jqi,j∈0,1,where Q is the quantum probability amplitude matrix, I is the number of target points, and J is the number of soil depths.After all individuals in the population are updated, the quantum probability amplitude will be updated according to the optimal individual in the last iteration with the quantum revolving gate. The quantum revolving gate is shown in Algorithm1.Algorithm 1. Quantum revolving gate.
Input: The quantum probability amplitude matrix Q, the number of target points n, the number of soil depths y, quantum probability amplitude increment ∆Output: The updated quantum probability amplitude matrix Q1.for i from 1 to n do2.for j from 1 to y do3.ifQ (i, j) ==1 andQ (i, j) <1 then4.Q (i, j) = Q (i, j) + ∆5.else ifQ (i, j) ==0 andQ (i, j) >0 then6.Q (i, j) = Q (i, j) - ∆7.   end if8.end for9.end for10. ReturnQIn addition, the quantum NOT gate is used to increase the diversity of solutions in the target allocation problem in SMWSNs. The quantum NOT gate is shown in Algorithm2.Algorithm 2. Quantum NOT gate.
Input: The quantum probability amplitude matrix Q, the number of target points n, the number of soil depths y, probability R, random number r between 0 and 1Output: The updated quantum probability amplitude matrix Q1.for i from 1 to n do2.for j from 1 to y do3.ifr < R then4.Q (i, j) =1 - Q (i, j)5.    end if6.end for7.end for8. ReturnQ


## 4.8. Clone Operator

To enhance the speed of convergence, QCEGA uses a clone operator to make clonal expansion of the outstanding individuals in the iterative process [34]. The probability of an individual being selected for cloning is determined by its advantage value. In each cloning process, a certain proportion of fitness individuals are selected for cloning. For example, assuming that there are R individuals in the population, clonal expansion is performed by selecting S individuals with the highest advantage as the mother during each iteration (S<R). After the cloning process, to increase the diversity of the population, it is necessary to perform mutation operations on the generated individuals. The mutation operation here includes quantum revolving gate operation and quantum NOT operation.


## 4.9. Elite Operator

The elite operator of QCEGA is the establishment of the elite population. The specific operation is to establish a population from the most adaptive individuals of the previous generation and then use the elite population to replace the least adaptive individuals in the next generation [35]. Due to the fact that the optimal individual may be destroyed by mutation and crossover operations, the elite operator can retain the optimal one to ensure the performance of the algorithm.


## 4.10. Steps of the Algorithm

The following steps can be used to describe the execution of QCEGA.Step 1. Set the initial parameters in QCEGA, generate a matrix of the advantage of placing sensors according to equation (1), generate a matrix of sensor monitoring effects using equation (2), and generate a quantum probability amplitude matrix according to equation (18).Step 2. Obtain the fitness value of the initial population using equation (9), and record the optimal network efficiency of the individual.Step 3. Execute the selection operation according to equation (13).Step 4. Execute the crossover operation.Step 5. Execute the mutation operation.Step 6. Calculate the fitness of the new population with equation (9).Step 7. Execute the clone operator.Step 8. Do high-probability mutation of the cloned population and make calculation of the new population’s fitness according to equation (9).Step 9. Execute the elite operator.Step 10. Assign the obtained clonal population to the next-generation population.Step 11. Update the quantum probability amplitude according to Algorithms1 and 2.Step 12. If the maximum iteration is not reached, return to step 3; otherwise, the algorithm terminates execution and outputs the optimal solution.The algorithm flowchart is shown in Figure3.Figure 3
Flowchart of QCEGA.


## 5. Results and Discussion

The definition of network efficiency of SMWSNs is the advantage value that can be obtained under a given soil moisture sensor target allocation scheme. The advantage value consists of two parts. One part is the advantage value of the sensor placement position determined by the distance between the sprinkler device and the target points. The closer the sprinkler device is, the higher the advantage value is. Another part of the advantage value comes from the depth of the soil. The lower the moisture value, the higher the advantage of the depth position. In SMWSNs, the target allocation of soil moisture sensors involves consideration of different target nodes and different soil depths. If the sensor nodes are placed at different target nodes and soil depths, their monitoring effects on the growth environment of crops are dissimilar. What is more, the calculation formula of the advantage is carried out according to equation (9).The network efficiency of the proposed QCEGA method in target allocation is tested, and QCEGA makes a comparison with the SA and PSO algorithms in SMWSNs for target allocation. Then, the performance of QCEGA is in comparison with different quantities of target points and soil moisture sensors. The whole testing cases are executed on a computer equipped with Pentium 2.1 GHz CPU.The algorithm efficiency of QCEGA needs to be compared with that of SA and PSO. To make the execution conditions of the algorithm as the same as possible, we set the number of iterations of QCEGA, SA, and PSO to 100 generations, and the size of the population is 40. In QCEGA, the crossover probability and the mutation probability are 0.8 and 0.05, respectively, and the value of the quantum probability amplitude matrix is initialized to 0.5. In SA, the initial temperature is 200, the annealing rate is exponentially decreased, and the decrease factor is 0.96. In PSO, the value of the individual learning factor is 2, the social learning factor is 2, and the speed boundary value is 5.According to Figures4(a)–4(d), the convergence of QCEGA, SA, and PSO is shown. Figure 4(a) suggests that QCEGA performs better than SA and PSO under the condition of 15 target points, 6 soil depth values, and 3 soil moisture sensors placed in each target point. Specifically, Figure 4(a) suggests that the network efficiency of SA is lower than that of PSO and the network efficiency of PSO is lower than that of QCEGA. In the first 50 iterations, the network efficiency value of QCEGA varies hugely, and as the times of iterations increase, its convergence speed is accelerated. From the iteration process 50 to 100, the network efficiency value of QCEGA is 18.16; however, the performance of PSO is worse than that of QCEGA, and its network efficiency value is 17.39. The network efficiency value of SA is 15.66. With roughly 50 generations of accumulation, QCEGA’s network efficiency advantages are better than those of PSO and SA; QCEGA’s performance has been enhanced with its quantum operator, clone operator, and elite operator. In a total of 100 iterations, the network efficiency of SA is lower than that of PSO, the convergence speed of QCEGA is greater, and it generates an optimal solution. In Figures 4(b)–4(d), the network efficiency of QCEGA is higher than that of SA and PSO under the situation that the target points are 20, 25, and 50 and the number of soil depths is 8, 10, and 12. The average network efficiency of QCEGA does not converge prematurely, which is a common phenomenon of SA and PSO. In general, QCEGA has a faster convergence rate than SA and PSO under the same number of iterations.Figure 4
The comparison of the network efficiency of the three algorithms: (a) 15 target points, 6 soil depths, and 3 sensors per target point; (b) 20 target points, 8 soil depths, and 4 sensors per target point; (c) 25 target points, 10 soil depths, and 5 sensors per target point; (d) 50 target points, 12 soil depths, and 6 sensors per target point.
(a)(b)(c)(d)Figure5 shows the number of iterations required for the three algorithms to achieve convergence under different simulation conditions. The standard of convergence is the range fluctuation percentage judgment method. The fluctuation range defined in this experiment is 1% to 2%; that is to say, if the increase percentage of the network efficiency obtained by the algorithm is between 1% and 2%, it can be considered convergent. In Figure 5 a, we can find that the convergence iterations required by QCEGA only require 18 generations, while SA requires the most convergence iterations, which are 32 generations. In Figure 5 a–c, the convergence performance of PSO is between SA and QCEGA, but in Figure 5 d, the number of iterations for SA to reach convergence is 26 generations, which is lower than 28 iterations of PSO. But at this time SA fell into premature convergence. In Figure 5 a–d, the number of iterations required for QCEGA to reach convergence is few, which can indicate that it has good convergence performance.Figure 5
Iterations required for the algorithms to converge: a—15 target points, 6 soil depths, and 3 sensors per target point; b—20 target points, 8 soil depths, and 4 sensors per target point; c—25 target points, 10 soil depths, and 5 sensors per target point; and d—50 target points, 12 soil depths, and 6 sensors per target point.Table2 shows the percentage increase of the solutions obtained by the three algorithms compared to the unoptimized scheme. In 5 different situations, QCEGA’s improvement percentage is the highest among the three algorithms, which are 22.72%, 23.30%, 29.97%, 31.29%, and 31.67%, respectively, compared to before optimization. The worst performance among the three algorithms is in SA. This is because it falls into the local optimum early and has a weak ability to jump out of it. PSO also has the weakness of falling into local convergence. Neither PSO nor SA can obtain the optimal solution to the SMWSN target assignment problem. Therefore, it can be seen that QCEGA can effectively improve the sensor target allocation scheme in SMWSNs.Table 2
The percentage increase of the results.
QCEGAPSOSA18 target points7 soil depths3 sensors per target point22.72%10.23%8.27%24 target points8 soil depths4 sensors per target point23.30%9.87%7.84%30 target points10 soil depths4 sensors per target point29.97%10.36%8.17%36 target points12 soil depths5 sensors per target point31.29%11.13%7.12%40 target points15 soil depths6 sensors per target point31.67%7.48%6.56%In the line chart of Figure6, the performance of QCEGA, SA, and PSO is compared in the form of one point every 10 generations. In Figure 6(a), when the conditions are 30 target points, 6 soil depths, and 3 sensors per target point, QCEGA obtains higher network efficiency than SA and PSO at the first point. Since then, the network efficiency value obtained based on QCEGA has been higher than that of PSO and SA. In addition, the network efficiency value of SA is lower than that of PSO, but both PSO and SA fall into the local optimum. In Figures 6(b)–6(d), similar conclusions can be drawn. In general, in solving the problem of SMWSN target allocation, QCEGA can jump out of the local optimum for obtaining the optimal target allocation scheme.Figure 6
The line chart of the three algorithms compared every ten generations: (a) 30 target points, 6 soil depths, and 3 sensors per target point; (b) 40 target points, 8 soil depths, and 4 sensors per target point; (c) 50 target points, 10 soil depths, and 5 sensors per target point; (d) 100 target points, 12 soil depths, and 6 sensors per target point.
(a)(b)(c)(d)Two sensors, 3 sensors, 4 sensors, and 5 sensors are placed at each target point in Figure7. The fitness function used to calculate the network efficiency can be obtained from formula (9). In Figure 7(a), the network efficiency value is improved after placing 2 sensors at each target point and 100 iterations. The result suggests that the effect of QCEGA is better than that of PSO and the effect of PSO is better than that of SA. In Figures 7(b)–7(d), when 3, 4, and 5 sensors are placed at each target point, comparable results are given. QCEGA always has a better performance than SA and PSO under the condition of placing a different number of sensors at each target point.Figure 7
Comparison of the solution quality of three algorithms: (a) 20 target points, 5 soil depths, and 2 sensors per target point; (b) 25 target points, 7 soil depths, and 3 sensors per target point; (c) 30 target points, 10 soil depths, and 4 sensors per target point; (d) 35 target points, 12 soil depths, and 5 sensors per target point.
(a)(b)(c)(d)It can be seen from Table3 that in the specific implementation process, the algorithm complexity of QCEGA and SA is all Om∗n2 and the algorithm complexity of PSO is Om∗n2+n, where m is the number of outer cycles and n is the number of individuals in the population. However, because PSO needs to continuously update the velocity and position of particles, SA, which is not efficient in solving the problem, has been continuously looping within the group. As a result, the actual complexity of PSO and SA in solving the SMWSN target allocation problem is higher than that of QCEGA. Although QCEGA requires quantum probability amplitude update and cloning, these operations are simple double loops. In addition, it can be seen from Figures 5 and 7 that the convergence performance and solution quality of QCEGA are better than those of PSO and SA. To further compare the complexity of the three algorithms, the running time of the algorithms is given in Table 4.Table 3
The computational complexity of the three algorithms.
AlgorithmQCEGAPSOSAComplexityOm∗n2Om∗n2+nOm∗n2Table 4
Comparison of algorithm running time (s).
QCEGAPSOSA18 target points7 soil depths3 sensors per target point3.347.004.3724 target points8 soil depths4 sensors per target point4.1410.516.0930 target points10 soil depths4 sensors per target point5.1312.307.1736 target points12 soil depths5 sensors per target point6.3416.729.3140 target points15 soil depths6 sensors per target point7.7921.1711.51According to the running time of the three algorithms in Table4, it can be further proven that the complexity of QCEGA is lower than that of PSO and SA. When the simulation conditions are 18 target points, 7 soil depths, and 3 sensors per target point, the running time of QCEGA only takes 3.34 s, the running time of SA takes 4.37 s, and the running time of PSO is the longest, reaching 7.00 s. As the scale of the problem continues to expand, the running time of PSO and SA has increased more than that of QCEGA. With the simulation conditions of 40 target points, 15 soil depths, and 6 sensors per target point, the running time of QCEGA is 63.20% lower than that of PSO and 32.31% lower than that of SA. Therefore, QCEGA has excellent running performance.


## 6. Conclusions

In conclusion, this paper puts forward an evaluation mechanism and a quantum clone elite genetic algorithm (QCEGA) for the allocation of sensors in SMWSNs. From the perspective of soil irrigation, this paper makes a mathematical model for the agricultural scenario and then uses the proposed algorithm to solve the mathematical model. The results show that it is effective in solving the problem of target allocation. By introducing QCEGA into the sensor target allocation problem, the results prove the effectiveness of the QCEGA-based target allocation in optimizing network efficiency of the SMWSNs. By applying QCEGA, a more efficient irrigation scheme can be obtained when land irrigation is carried out. Not only does the scheme obtain the maximum monitoring effect of the soil moisture sensor but also it saves water, which is especially useful in some places where water resources are relatively scarce. Through the suitable deployment of sensors, limited resources can be used as much as possible.Future research should carefully consider other methods that can further improve the network efficiency of SMWSNs, such as combining routing optimization algorithms, clustering SMWSNs, and machine learning techniques.



---

*Source: 5590472-2021-05-17.xml*