Passive Location Resource Scheduling Based on an Improved Genetic Algorithm

Abstract

With the development of science and technology, modern communication scenarios have put forward higher requirements for passive location technology. However, current location systems still use manual scheduling methods and cannot meet the current mission-intensive and widely-distributed scenarios, resulting in inefficient task completion. To address this issue, this paper proposes a method called multi-objective, multi-constraint and improved genetic algorithm-based scheduling (MMIGAS), contributing a centralized combinatorial optimization model with multiple objectives and multiple constraints and conceiving an improved genetic algorithm. First, we establish a basic mathematical framework based on the structure of a passive location system. Furthermore, to balance performance with respect to multiple measures and avoid low efficiency, we propose a multi-objective optimal function including location accuracy, completion rate and resource utilization. Moreover, to enhance its practicability, we formulate multiple constraints for frequency, resource capability and task cooperation. For model solving, we propose an improved genetic algorithm with better convergence speed and global optimization ability, by introducing constraint-proof initialization, a penalty function and a modified genetic operator. Simulations indicate the good astringency, steady time complexity and satisfactory location accuracy of MMIGAS. Moreover, compared with manual scheduling, MMIGAS can improve the efficiency while maintaining high location precision.

1. Introduction

Passive location plays a significant role in modern communication scenarios for its satisfactory concealment based on the passive reception pattern. In addition, with the characteristics of long distance measurement and high robustness [1], passive location techniques are of significance in both civil and military areas. The major passive location technique is angle-of-arrival (AOA) [2], which obtains the target location by combining the measured angles of each station and whose performance is highly affected by scheduling plans [3,4]. Resource scheduling is implemented to establish an optimized task-to-resource dispatch with the purpose of maximizing the total performance (such as location accuracy and task completion rate) and avoiding the conflicts effectively. However, despite its importance, little attention is paid to the scheduling mechanism. In recent years, studies in passive location have mainly focused on location algorithms [5,6], accuracy analysis [7], filters and tracking [8,9]. There is little information available in the literature about passive location resource scheduling. The scheduling method mostly used today, which we call traditional manual scheduling, is unable to handle the increasing number of tasks and overloaded resources, thus leading to the following serious problems.

• Low efficiency. Because manually allocated broadcast resources cannot achieve parallel processing very well, when task conflicts occur, some signals may be lost, reducing efficiency.
• Unstable location accuracy. Because location accuracy is highly relevant to the stations-to-tasks schedule plans, it is possible to encounter low location accuracy due to mistakes caused by human subjectivity.

To address these problems and achieve high efficiency and location accuracy, new intelligent automated scheduling methods urgently need to be studied. Xiu et al. [10] analyzed constellations in bearing-only location systems and proposed an optimal geometric relationship to improve location precision and minimize circular probable error, providing an important reference for station scheduling. Prasan et al. [11] proposed the pre-scheduling-based k-coverage group scheduling and self-organized k-coverage scheduling algorithms to address problems in existing sleep-scheduling algorithms.

Hu et al. [12] established a centralized framework for sensor scheduling in wireless sensor networks and modeled the problem using integer linear programming. In [13], the proposed algorithms, which deal directly with minimizing the mean squared error, are based on the convex relaxation approach to address the binary optimization scheduling problems that are formulated in sensor network scenarios. Xu et al. [3] analyzed the Cramer-Rao lower bound of AOA and discussed the measurement of location accuracy based on the information matrix. Wei et al. [9] proposed a modified binary particle swarm optimization (BPSO) algorithm motivated by the information matrix in the wireless sensor network nodes scheduling problem for tracking. Sun et al. [14] were inspired by Xu et al. and Wei et al. and proposed a BPSO algorithm motivated by geometric dilution of precision deduced from the information matrix for station scheduling. However, Sun et al. did not solve the problem thoroughly because they neglected to consider complex constraints and efficiency. Furthermore, previous studies seldom discuss scheduling strategies for scenes with multiple concurrent tasks. Therefore, to solve passive location station scheduling more specifically, the scheduling method must satisfy these conditions. (1) The optimal objective must involve not only accuracy but also other important factors, especially efficiency. (2) Complex constraints are formulated. (3) The method can support multiple concurrent task scenarios.

Inspired by the factors mentioned above, we propose a new method called multi-object, multi-constraint and improved genetic algorithm-based Scheduling (MMIGAS), enhancing the efficiency and practicability for passive location resource scheduling. Our first contribution is to construct a mathematical primary centralized optimization model of passive location resource scheduling according to a practical system framework. Second, we introduce position dilution of precision (PDOP) to measure the location accuracy and define other objective values, such as completion rate, resource utilization and task priority. These values are combined into a multi-objective function to ensure that our schedule can balance performance with respect to multiple aspects, specially efficiency. Third, based on several important assumptions, we formulate complex constraints in three categories: frequency, station capability and task cooperation requirement, thus improving practicability. Moreover, since the model is an NP-hard problem, we conceive an improved genetic algorithm (IGA) by introducing constraint-proof initialization (CI), penalty function (PF) and modified genetic operator (MGO), which can achieve a better convergence rate and global optimization ability. Simulations show that MMIGAS has a satisfactory astringency and stability of time complexity. Additionally, the method is appropriate for multiple concurrent targets. Compared with manual scheduling, MMIGAS can clearly improve the efficiency while maintaining high location accuracy.

The remainder of this paper is organized as follows. Section 2 introduces the primary framework of the location system, clarifies some critical assumptions and establishes a basic mathematical optimization model. In Section 3, we demonstrate our design for multiple objectives and multiple constraints. In Section 4, we illustrate the three steps of the IGA: CI, PF and MGO. Section 5 presents the experimental results and analyses the performance of proposed method. Section 6 concludes the paper.

2. Problem Formulation

The passive location channel is heavily crowded due to the narrowband and dense signals. The time-varying fading and silence zones also cause many problems, making the passive location problem a difficult task and topic of interest [15,16,17,18,19,20]. To increase the location accuracy and flexibility, a location system generally uses a cooperative location approach [21], which consists of the steps of task arrival, command downloading, data uploading and position output, as shown in Figure 1.

Moreover, the system has a centralized architecture consisting of the command center and direction-finding stations, as shown in Figure 2. Therefore, the essence of station scheduling is a centralized tasks-to-resources allocation, which guides us to establish a combination optimization model.

2.1. Assumptions and Scenario Declaration

Because the passive location scenario is extremely complicated due to complex channels [22], we make some critical assumptions to simplify this problem.

• We ignore the silence zone. This assumption is made to reduce the space constraint and make the model more concise. According to related studies, potential silence zones can be fully avoided if appropriate locations for building stations are chosen [10].
• Signals from all directions have the same gain in the receiving antennas. This assumption is made to ensure the strength of the signal directly reflects the distance between the station and the target, which simplifies the discussion about geographical relationships. This can be achieved by using an omnidirectional antenna.
• Targets are static or moving slowly enough that their locations do not noticeably change over a short time. This assumption avoids a heavy time delay or even invalidation of the scheduling due to drastic changes in geographical relationships.
• Prior knowledge about targets is available. This assumption ensures that the approximate potential area of the target is known, which is an essential condition of using the proposed scheduling method.
• In addition, the scenario discussed in this paper is specified by the following declarations.
• We only discuss the scheduling activity in one slot. We define one slot as the duration of a scheduling and location process. It is the minimum interval needed to implement one complete activity in the passive location system. Therefore, any length of time can be considered to be a sum of several slots.
• We only discuss narrow-band stations because wide-band stations can be considered the sum of several different narrow-band stations.

2.2. Notation

Stations and signals are considered to be resources and tasks, respectively. And to demonstrate their allocation relationship, we structure a scheduling matrix as follows.

1.

Task: We denote tasks as $T=\left\{t_1,t_2,\mathrm{\dots },t_i,\mathrm{\dots }{t}_{N_m}\right\}$, where $N_m$ is the total number of tasks. We use four attributions to describe a task: frequency, location, collaboration and priority, $\forall t_i\in T,t_i=\left\{{\widehat{Z}}_i,{\widehat{\lambda }}_i,{\widehat{B}}_i,{\widehat{H}}_i\right\}$, where $i$ denotes the task sequence number.

• ${\widehat{Z}}_i=\left[{\widehat{f}}_{\min }\left(i\right),{\widehat{f}}_{\max }\left(i\right)\right]$ gives the frequency range of the task signal, where ${\widehat{f}}_{\min }\left(i\right)\in R,{\widehat{f}}_{\max }\left(i\right)\in R$ and ${\widehat{f}}_{\min }\left(i\right)\le {\widehat{f}}_{\max }\left(i\right)$.
• ${\widehat{\lambda }}_i=\left({\widehat{x}}_i,{\widehat{y}}_i\right)$ denotes the two-dimensional coordinates of task $i$, where ${\widehat{x}}_i\in R,{\widehat{y}}_i\in R$.
• ${\widehat{B}}_i$ gives the cooperative station number requirement for task location, where ${\widehat{B}}_i\in Z^{+}$.
• ${\widehat{H}}_i\in \left\{1,\dots ,6\right\}$. We define the priority of tasks as an integer ranging from 1 to 6. The task is more important if its ${\widehat{H}}_i$ is higher.

2.

Resources: We denote $N_s$ direction-finding stations as $K=\left\{k_1,k_2,\dots ,k_j,\dots ,k_{N_s}\right\}$. We use three attributions to describe one station (resource): frequency, location and capability, $\forall k_j\in K,k_j=\left\{Z_j,{\lambda }_j,C_j\right\}$. Here, $j$ denotes the station sequence number.

• $Z_j=\left[f_{\min }\left(j\right),f_{\max }\left(j\right)\right]$ is the frequency range at which the station implements direction-finding, where $f_{\min }\left(j\right)\in R,f_{\max }\left(j\right)\in R$ and $f_{\min }\left(j\right)\le f_{\max }\left(j\right)$.
• ${\lambda }_j=\left(x_j,y_j\right)$ denotes the two-dimensional coordinates of station $j$, $x_j\in R,y_j\in R$.
• $C_j$ is the maximum number of tasks the station can process synchronously, implying its working capacity, where $C_j\in Z^{+}$.

3.

Scheduling matrix: We design a binary solution matrix with $N_s$ columns and $N_m$ rows as $\mathrm{A}={\left[a_{ij}\right]}_{N_m\times N_s}$, where $a_{ij}$ indicates the relation between station $j$ and task $i$. Here $a_{ij}=1$ means that station $j$ is assigned to process task $i$, while $a_{ij}=0$ means $j$ is not assigned to process $i$.

2.3. Optimization Model

Based on the analysis mentioned above, we formulate the passive location resource scheduling problem as a combination optimization problem. Denote $F$ as the objective function, $h_i$ as the equality constraints and $g_i$ as the inequality constraints. Then, the mathematical model is:

$$\{\begin{array}{ll}& \max \left\{F\left\{\mathrm{A}\right\}\right\}\\ s.t.& h_i\left\{\mathrm{A}\right\}=0,i=1,2,3\dots \\ & {\mathrm{g}}_i\left\{\mathrm{A}\right\}\ge 0,\mathrm{j}=1,2,3\dots \end{array}$$

(1)

3. Multi-Objective and Multi-Constraint Properties

3.1. Objective Function

To balance different aspects of the performance and obtain a comprehensive solution, we design a multi-objective function using a linear weighting as follows:

$$F={\displaystyle \sum _q{\phi }_q{\omega }_q}$$

(2)

Here ${\phi }_q$ is the objective and ${\omega }_q$ is the weight. The definition and calculation of objectives and weights is illustrated in the following part of this section.

3.1.1. Location Accuracy

Because the fundamental requirement of passive location resource scheduling is to obtain a scheduling plan with a satisfactory location accuracy, the objective function must involve the location accuracy. We introduce PDOP as the measure of location accuracy. PDOP quantifies the geographical relationships between receivers and targets, which can directly impact the performance of the location activity. Smaller PDOP means better performance and on the contrary, larger PDOP means worse performance. Based on [14,23], PDOP is calculated as follows:

$$p_i=\frac{{\left\{{\displaystyle \sum _{j-1}^{M_1}\frac{1}{r_j{}^2}\frac{1}{{\left({\sigma }_{\varphi }^{}\left(j\right)\right)}^2}}\right\}}^{\frac{1}{2}}}{\det {\left(L_i\right)}^{\frac{1}{2}}}$$

(3)

$$\det \left(L_i\right)={\displaystyle \sum _{\left\{u,v\right\}\in M_2}\frac{1}{{\left({\sigma }_{\varphi }^{}\left(u\right)\right)}^2{\left({\sigma }_{\varphi }^{}\left(v\right)\right)}^2}}\frac{{\sin }^2\left({\varphi }_u-{\varphi }_v\right)}{r_u{}^2{r}_v{}^2}$$

(4)

Here, $p_i$ is the PDOP value of task $i$, $L_i$ is the Fisher information matrix, $r_j$ is the distance from station $j$ to the target, ${\varphi }_j$ is the direction angle, ${\sigma }_{\varphi }^{}\left(j\right)$ is the measurement error of ${\varphi }_j$, $M_1$ denotes the number of stations that participate in the task and $M_2$ denotes the set of every match of two stations in $M_1$. For example, when $M_1=\left\{1,2,3\right\}$, then $M_2=\left\{\left\{1,2\right\},\left\{2,3\right\},\left\{1,3\right\}\right\}$. To make the objective factor positive with respect to location accuracy, we formulate ${\phi }_p$ as the reciprocal of the sum of PDOP as:

$${\phi }_p=\frac{1}{{\displaystyle \sum _i{p}_i}}$$

(5)

Additionally, we set ${\omega }_p=1$ and the objective function is:

$$F={\phi }_p+{\displaystyle \sum _q{\phi }_q{\omega }_q}$$

(6)

3.1.2. Completion Rate

To avoid the task missing problem and low efficiency, we define an objective factor named completion rate ${\phi }_1$ which is equal to the ratio of completed tasks $n$ to the total number of tasks $N_m$.

$${\phi }_1=\frac{n}{N_m}$$

(7)

Weight ${\omega }_q$ is calculated as the product of scaling factor ${\eta }_q$ and concern level $c_q$.

$${\omega }_q={\eta }_q{c}_q$$

(8)

Here, ${\eta }_q$ transforms objective factor ${\omega }_q$ to the same order of magnitude of ${\phi }_p$, which avoid poor performance of $F$ caused by the wrong size of ${\phi }_p$. It helps $F$ to reflect various factors evenly. Objective factor ${\eta }_i$ is calculated as follows:

$${\eta }_i={10}^{{\log }_{10}\lfloor \frac{{\phi }_p}{{\phi }_i}\rfloor }$$

(9)

Here $\lfloor x\rfloor$ means the maximum integer value less than $x$ and $c_q$ indicates a user’s concern about the objective factor, which is shown as Equation (10).

$$\{s.t.\begin{array}{c}{c}_q\in \left[0,1\right]\\ {\displaystyle \sum _q{c}_q}=1\end{array}$$

(10)

3.1.3. Resource Utilization

To prevent resource waste, we introduce the resource utilization in Equation (11), which is the ratio of occupied resources $m$ to the total number of resources $N_s$.

$${\phi }_2=\frac{m}{N_s}$$

(11)

Analogously, weight ${\omega }_2$ is calculated by (8)–(10).

3.1.4. Task Priority

Inspired by priority scheduling [24], we design objective factor ${\phi }_3$ based on task priority, which makes the model prefer the task with the highest priority, shown in Equation (12).

$${\phi }_3={\displaystyle \sum _i{\widehat{H}}_i}$$

(12)

Here, ${\phi }_3$ equals the sum of priorities of completed tasks. As above, weight ${\omega }_3$ is analogously calculated by (8)–(10).

In conclusion, the formulation of multi-objective function $F$ is as follows:

$$F={\phi }_p+{\displaystyle \sum _{q-1}^3{\phi }_q{\omega }_q}={\phi }_p+{\displaystyle \sum _{q-1}^3{\phi }_q{\eta }_q}{c}_q$$

(13)

3.2. Constraints

Due to the complexity of wireless communication channels [25], the resource scheduling problem, involving many constraints on time, space, frequency and other factors, need to be analyzed and formulated to ensure our mathematical model is reasonable. Based on our assumptions, we ignore the constraints in the time and space domains and simplify the complex conditions into three categories: frequency, station capability and task cooperation requirements.

3.2.1. Frequency

The direction-finding activity cannot be implemented when the frequency of the task is beyond the station’s range. We formulate such a constraint as follows:

$$\forall t_i\in T,\forall k_j\in K,\{\begin{array}{c}{a}_{ij}\left({\widehat{f}}_{\min }\left(i\right)-f_{\min }\left(j\right)\right)\ge 0\\ a_{ij}\left(f_{\max }\left(j\right)-{\widehat{f}}_{\max }\left(i\right)\right)\ge 0\end{array}$$

(14)

3.2.2. Station Capability

For narrow-band stations, receivers are highly restricted, leading to the limitation of the number of tasks that can be implemented by one station synchronously.

$$\forall j\in \left[1,N_s\right],{\displaystyle \sum _{i-1}^{N_S}{a}_{ij}\le C_j}$$

(15)

3.2.3. Task Cooperation Requirement

Because different tasks may have different cooperation requirements, a sufficient number of stations should be allocated to the task.

$$\forall i\in \left[1,N_t\right],{\displaystyle \sum _{j-1}^{N_s}{a}_{ij}}\ge {\widehat{B}}_i$$

(16)

4. IGA

Due to the strong relevant effects among tasks and resources, the proposed model becomes an NP-hard problem [26], for which a genetic algorithm (GA) is suitable for searching for a solution because of its adaptive global optimization ability. Originally, a GA was conceived based on the simulation of heredity and evolution in the natural environment [27].

In the algorithm initialization, various initial feasible solutions are randomly generated as the original genetic group. During the iterations, genetic operators construct the offspring based on the parental genetic group, where the genes with highest environmental fitness can survive and multiply, thus conveying the dominated characteristics into the final generation. Eventually, the algorithm obtains an optimal solution. Compared with other algorithms, GA has low complexity and high practicability [28], thus being appropriate for the passive location resource scheduling problem. However, the normal GA has the disadvantages of a low convergence rate and local optimization dilemma. To make it more suitable for our application scenario, we make several improvements by implementing CI, PF and MGO, helping the algorithm to obtain a satisfying solution quickly. The objective function is utilized as the fitness function, while the decision matrix is used for gene construction. The process of the algorithm is shown in Figure 3 and details in Algorithm 1.

Algorithm 1. IGA.

1. Parameters setting and constraint-proof initialization.

2. Terminate? Yes→Step 6, No→Step3.

3. Calculate the fitness with the PF and select next generation.

4. Use MGO to get next generation.

5. Constrain satisfaction? Yes→step 2, No→Step 4.

6. Get the solution.

4.1. CI

Traditional GA is very sensitive to the initial values [29]. When the initial values do not meet the constraints, the algorithm is unable to calculate the fitness and thus the evolution direction is unclear, which substantially reduces the convergence rate and even leads to the non-convergence. Therefore, in order to provide a specific evolution direction at the beginning and improve the astringency, we implement the CI by building a taboo-table which marks out the element unable to satisfy the frequency constrain and coding the scheduling matrix stepwise. The process is shown in Figure 4.

Step ①: Generate the original matrix according to the number of tasks and stations. Build up a taboo-table by using Equations (14)–(16). And take away the taboo-table from the original matrix to obtain the frequency-satisfying matrix.

Step ②: Select one column of the matrix as a vector, which indicates the task scheduling table of one station. Value it randomly within the capability of the resource and then use it as a task allocation vector.

Step ③: Repeat Step ② for every column in the frequency-satisfying matrix to obtain the task allocation vectors of all stations.

Step ④: Combine the task allocation vectors as a decision matrix.

4.2. PF

To enhance the algorithm performance, the original genetic group must satisfy all constraints in our model. CI guarantees the original genetic group will meet the constraints on frequency and resource capability. For the task cooperation constraint, we introduce the PF method based on Section 2.2 and Equation (1).

Denote $\Omega$ as the penalty factor. Set $\Omega >1,\Omega \in Z^{+}$. Define $X_i={\displaystyle \sum _{j-1}^{N_s}{a}_{ij}}$ as the number of stations scheduled for task $i$. The PF is denoted as $P$:

$$P={\displaystyle \sum _{i-1}^{N_m}{\Omega }^{\left(B_i-X_i\right)}}$$

(17)

Therefore, the fitness function becomes:

$$Fitness=F-P$$

(18)

According to (17) and (18), if one solution does not meet the task cooperation requirement, its $P$ will increase exponentially, rapidly reducing its fitness and causing it to be eliminated during the iteration. Therefore, solutions eventually that survive must satisfy the task cooperation constraint.

4.3. MGO

The preceding section introduces the generation of the initial solution and the penalty function. Then, we will introduce the modified genetic operation of the solution which contains roulette wheel, elitism selection, crossover and mutation.

4.3.1. Roulette Wheel and Elitism Selection

We introduce a combined roulette-wheel and elitism selection strategy, which can keep the randomness of offspring and prevent the loss of the best individual in the group. First, the individuals with the highest fitness are directly saved to the next generation. Second, parents are selected according to probability $p_g$, of individual $l$, which is calculated as follows:

$$p_g^{}\left(l\right)=\frac{Fitness\left(l\right)}{{\displaystyle \sum _{j-1}^{N_p}Fitness\left(j\right)}}$$

(19)

where $N_p$ is the population of genetic group in this algorithm and $Fitness\left(l\right)$ is the fitness of individual $l$.

4.3.2. Crossover

1. Crossover between chromosomes

There is a probability $p_{cc}$ that chromosome crossover will happen for each individual. In the case, two chromosomes will be randomly selected and exchange their gene in the same location. Parameters $p_{cc}$ is set according to human experience, normally ranging from 0.3 to 0.7. Figure 5 shows the crossover process.

2. Crossover between individuals

In the same way, we need to consider the concurrent processing of multiple tasks. So, there is a probability $p_{ci}$ for individual crossover among the entire group, which is the operation that one individual exchanges part of its genes with another. The location at which the gene exchange happens is selected randomly. Probability $p_{ci}$ is set by experience as well, normally ranging from 0.3 to 0.7. Figure 6 shows the process of two concurrent tasks.

3. Mutation

In every individual, there is a probability $p_m$ of mutation, which is when one or more genes inside this individual change themselves randomly. Parameter $p_m$ usually ranges from 0.01 to 0.1. An example of mutation is shown in Figure 7.

5. Experiment Results and Discussion

5.1. Simulation Setting

We simulate a passive location scenario based on AOA. The exact location, frequency and capability of stations are all known. Moreover, the approximate area, communication frequency, priority and cooperation requirement of tasks are known as well. Note that we only discuss the one-slot and narrow-band condition. Scenario and algorithm parameters are shown in

Table 1. Parameter settings for the algorithm.

Chromosome Crossover Probability	Individual Crossover Probability	Mutation Probability	Population	Iteration	Penalty Factor	Objective Function Weights	Probability Distribution
0.8	0.8	0.1	10	1000	$\Omega =5$	$c_1=1$ $c_2=c_3=0$	Gaussian $N\left(0,1\right)$

,

Table 2. Parameter settings for the station scenario.

Location Area (km × km)	Beginning Frequency (HZ)	Band (HZ)	Capacity	Probability Distribution
50 × 50	1000~5000	2000~3000	1~2	Uniform Distribution

and

Table 3. Parameter settings for the task scenario.

Location Area (km × km)	Beginning Frequency (HZ)	Band (HZ)	Cooperation Requirement	Probability Distribution
50 × 50	1000~5000	2000~3000	2~3	Uniform Distribution

. First, we mainly consider the location accuracy and completion rate, so in this experiment objective function weights are set as $c_1=1$ and $c_2=c_3=0$. In addition, chromosome crossover probability, individual crossover probability and mutation probability are set according to Section 4.3. The direction angle error associated with the positioning accuracy is generated according to $N\left(0,1\right)$ Gaussian distribution and the penalty factor is $\Omega =5$. Moreover, the population number of chromosomes is 10 and the max iteration of genetic algorithm is 2000.

The stations and task signals were randomly distributed in a 50 km × 50 km area. The frequency range of stations and tasks were decided by their beginning frequencies and bands. The capabilities are randomly varied between 1 and 2, while the cooperation requirements are randomly varied between 2 and 3. And the locations of stations and task signals are randomly generated according to uniform distribution.

5.2. Experiment Results

We built up a scenario with 15 stations and six tasks. The solution given by the proposed algorithm is shown in Figure 8 and

Table 4. Scheduling results of 15 stations and six tasks.

Task	1	2	3	4	5	6
Station	1, 3, 14	2, 3, 9	5, 6, 10	8, 12, 13	2, 4, 11	6, 7, 9

Notes: the numbers of task and station are shown in Figure 8.

. The result indicates that the method can work out an appropriate solution and handle the NP-hard problem effectively.

Furthermore, we ran a Monte-Carlo experiment by repeating this simulation 300 times to examine the astringency. To better show the effect of the algorithm, the 300 experiments were divided into five groups (No. 1~No. 5), where each group including 60 experiment results and each curve representing the average value of each group. In each experiment, the location of the targets and the location of the stations are randomly generated. The convergence curves are shown in Figure 9, illustrating that the convergence values are very close to one another. This method can enlarge the search space and help the algorithm jump out of local minima. Moreover, all the curves reached their convergence in less than 100 iterations, showing the rapid convergence which means that the algorithm can finish calculation in a short time. Such a characteristic is very important for the passive location problem.

5.3. Results and Discussion

The experimental results show that the proposed algorithm can solve the multi-objective and multi-constraint scheduling problems. To further verify the performance of the IGA and analyze the experimental results, we analyze the performance and indicators, including the performance of the IGA and some experiment indicators, such as time complexity and location accuracy.

5.3.1. Performance of the IGA

CI has an advantage with respect to astringency because it can provide a specific evolution direction at the beginning of the iterations. Random initialization means the random generation of initial solutions which directly participate in the next operation of the genetic algorithm without checking constraints. In this experiment, in order to compare the difference between CI initialization and random initialization, the parameters are set the same as Table 1 except for the initialization step. And the experiment results are shown in Figure 10.

As shown in Figure 10, the random initialization method fails to find the direction of astringency because it is difficult for random initialization to find an initial value satisfying the constraints and it is also difficult to achieve a continuous reduction of the optimization goals. The CI can accumulate enough solutions to satisfy the constraints in the initialization so that the algorithm can quickly find the appropriate updating direction in the feasible solution space, thus maintaining a considerable descent speed for the optimization target. The results prove that CI can effectively improve the convergence rate of the algorithm.

In order to better prove the advantage of IGA algorithm, we conduct a contrast experiment between IGA, particle swarm optimization (PSO) and ant colony optimization (ACO). A simulation with 6 tasks and 25 stations was set up and the parameter settings of PSO and ACO are shown in

Table 5. Parameter settings for PSO and ACO.

Algorithm	Maximum Iterations	Population	Search Parameters	Other Parameters
PSO	1000	10	${\gamma }_1=2$, ${\gamma }_2=2$	$V_{\max }=10$
ACO	1000	10	$\alpha =2$, $\beta =3$	$\eta =0.3$, $cons=10$

Notes: In PSO, ${\gamma }_1$ and ${\gamma }_2$ represent the global optimal factor and local optimal factor of particle velocity update in iteration and $V_{\max }$ denotes the maximum velocity of a particle. In ACO, $\alpha$ and $\beta$ respectively represent pheromone factor and elicitation factor, $\eta$ denotes pheromone volatilization factor and $cons$ denotes the total amount of pheromone released by an ant at one iteration.

. In the scenario, the station frequency of all sites could match the communication frequency of the task, the maximum working capacity of the site was one and the cooperative number was two. The three algorithms were recorded over 1000 iterations to optimize the change of targets. As shown in Figure 11, IGA has a stronger global search ability than ACO and PSO and it can resist the problem of falling into locally optimal points to a certain extent.

5.3.2. Time Complexity

Our requirements for time complexity are relatively high, because location tasks require very strict real-time performance, which means low time delay for processing tasks.

1. Effect of population.

To investigate the influence of population on time complexity, we built a scenario with 15 stations and six tasks and vary the population from 2 to 40. We examined the time spent for calculation and the fitness of the final solution. From the results of the experiment shown in Figure 12, we can draw the following conclusions. (a) The time of calculation increase approximately linearly according to the population. (b) The fitness can be obviously enhanced by a bigger population at the beginning but when the population is larger than 10, the fitness is no longer sensitive. From this, we can make a final deduction: the population should not increase or decrease without limit and it should be appropriately chosen to balance low time complexity with good global search capability according to real application scenarios.

2. Effect of coding length.

To study the effect of coding length, also regarded as the number of stations, on time complexity, we conducted an experiment to observe the time spent on calculation in different scenarios with different coding lengths. However, the results were not significant because the delay caused by retrogression can enormously impact the final output and obscure the impact of the coding length. Hence, to avoid the retrogression and emphasize the influence of coding length, we fixed the values of the population, maximum number of iteration, frequency, task cooperation requirement and station capabilities. In addition, we varied the coding length from 10 to 19. The relationship between time complexity and coding length becomes more observable, as shown in Figure 13 (two experiments with five and six tasks were conducted).

Clearly, the time of calculation has an approximately linear relationship with the coding length. Moreover, because the coding length may change because of station network adjustments such as added or removed nodes, this experiment demonstrates that the algorithm can maintain a stable time complexity even in rapidly transforming scenarios such as war and this will not lead to a saltation. In conclusion, the algorithm has good time complexity stability in practice.

5.3.3. Location Accuracy

This section discusses the variation tendency of location accuracy during the iterations, which is very important in location tasks. We calculate the PDOP by Equations (3) and (4) and the measurement error $\Delta$ is calculated as follows:

$$\Delta ={\displaystyle \sum _{i-1}^{N_t}\sqrt{{\left({\widehat{x}}_i-x_i\right)}^2+{\left({\widehat{y}}_i-y_i\right)}^2}}$$

(20)

Here, ${\widehat{x}}_i$ and ${\widehat{y}}_i$ are the measured coordinates of the targets while $x_i$ and $y_i$ are the real values, respectively.

The behaviors of $\Delta$ and PDOP during the iterations are shown in Figure 14. Generally, as the fitness increases during the iterations, the PDOP value and real measurement error of the solution decrease, indicating that the location accuracy increases. As shown in Figure 14, as the number of iterations increases, the algorithm can improve the location accuracy under the condition of satisfying multiple constraints and completing multiple tasks.

5.4. Comparison with the Manual Method

We compare the proposed method and traditional manual scheduling. Here, to simulate the manual method, all stations select the same randomly allocated task for one slot; that is, the task itself is randomly allocated but all stations perform the same one. We used two metrics to examine their performance, PDOP and task completion rate, to indicate the location accuracy and efficiency, respectively. The results, shown in Figure 15 and Figure 16, illustrate two preliminary conclusions. First, MMIGAS has the same location accuracy as the manual scheduling in a scenario with sufficient resources. When the station number is small, the PDOP of manual scheduling is lower than that of MMIGAS because the manual scheduling only finishes one task every slot. However, the gap between them gets smaller and finally goes to zero as the number of stations increases. The proposed method and manual scheduling reach the same accuracy when the number of stations is equal to or more than 60. Second, MMIGAS has a higher completion rate than manual scheduling, which indicates better efficiency. This result also shows that the competition rate grows when the number of stations increases. Eventually, we draw our final conclusion: when the number of stations is high enough, MMIGAS can effectively enhance the efficiency with just a little or even no loss of location accuracy.

For further discussion, we define two values: $Q_1$ and $Q_2$, which are respectively calculated using (21) and (22).

$$Q_1=\frac{p_1-p_2}{\max \left(p\right)}$$

(21)

Here, $p_1$ and $p_2$ are the PDOP values of MMIGAS and manual scheduling respectively. The physical meaning of $Q_1$ is the relative loss of accuracy.

$$Q_2=R_1-R_2$$

(22)

Here $R_1$ and $R_2$ are the completion rates of MMIGAS and manual scheduling respectively. The physical meaning of $Q_2$ is the improvement in completion rate.

For five tasks, the curve of $Q_1$ and $Q_2$ are shown in Figure 17. Clearly, as the number of stations increase, $Q_1$ decreases nearly to zero and $Q_2$ increases nearly to one, showing that the loss of location accuracy is cut down while the efficiency is significantly improved. Hence, the following can be concluded: when the number of stations is high enough, this method can substantially enhance efficiency at a little cost of location accuracy.

5.5. Multi-Objective Function Weights

According to Equation (13), $c_1$, $c_2$ and $c_3$ respectively represent the weights of completion rate, resource utilization and task priority. In Section 5.1, we mainly considered the location accuracy and task completion rate, which mainly aims at accomplishing as many tasks as possible while ensuring accuracy, so the weights are set as $c_1=1$, $c_2=c_3=0$. Then, we will set different values for $c_1$, $c_2$ and $c_3$ to verify the effectiveness of the proposed algorithm for multi-objective situations.

5.5.1. Analysis of Multi-Objective Weights

First, we set the parameters as: $c_1=c_2=0.1$, $c_3=0.8$. This setting is primarily about task priority and the simulation scenario is to prioritize important tasks when the stations are insufficient. We built up a scenario with eight stations and six tasks. The parameters settings for the algorithm are shown in

Table 6. Parameter settings for the algorithm.

Chromosome Crossover Probability	Individual Crossover Probability	Mutation Probability	Population	Iteration	Penalty Factor	Objective Function Weights	Probability Distribution
0.8	0.8	0.1	10	1000	$\Omega =5$	$c_1=c_2=0.1$ $c_3=0.8$	Gaussian $N\left(0,1\right)$

, the station scenario parameters are set as shown in Table 2 and the task scenario parameters are set as shown in Table 3. The experiment results are shown in

Table 7. Scheduling results of eight stations and six tasks.

Task	1	2	3	4	5	6
Priority	6	5	4	3	2	1
Station	1, 5, 6	7, 8	4, 8	2, 6	2, 6	——

and Figure 18.

As can be known from Table 7 and Figure 18, when the number of sites is insufficient, No.6 task is abandoned due to the lowest priority and No.1 task has the most stations and best location accuracy due to the highest priority.

To analyze the performance of the IGA and verify the experiment conclusions, we adopt the performance and indicators in Section 5.3. And the analysis of experiment results is shown in Figure 19. In Figure 19a, IGA algorithm can still ensure the fitness curve converges to the optimal value. From Figure 19b, we can find out that the PDOP curve is oscillatory due to the influence of priority. And Figure 19c shows that the completion rate did not reach 100% due to insufficient sites and considering the priority, the completion rate curve also oscillated in the early stage. It can be concluded from Figure 19d that because stations are not sufficient, the resource utilization is always at 100%.

Through the experiment analysis, it can be concluded that when the stations are insufficient, MMIGAS can give the optimal solution to different requirements.

5.5.2. Reliability in Different Scenarios

Then, we will combine location accuracy, completion rate, resource utilization and task priority to test the proposed algorithm in different scenarios. Therefore, the task priority is set as Table 7, the parameters are set as $c_1=c_2=c_3=\frac{1}{3}$ and the parameters settings for the algorithm are shown in

Table 8. Parameter settings for the algorithm.

Chromosome Crossover Probability	Individual Crossover Probability	Mutation Probability	Population	Iteration	Penalty Factor	Objective Function Weights	Probability Distribution
0.8	0.8	0.1	10	1000	$\Omega =5$	$c_1=c_2=c_3=\frac{1}{3}$	Gaussian $N\left(0,1\right)$

. The station and task scenario parameters are also set in Table 2 and Table 3. The experiment results in accordance with the above experimental settings are as follows.

From Figure 20, it can be found out that as the number of stations increases, the location accuracy gradually increases. But the station redundancy will occur later. The results show that excessive stations will not bring a noticeable increase in location accuracy when the station number is enough.

In Figure 21, as the number of stations increases, the task completion rate gradually increases until 100%. Similarly, as the number of tasks increases, so does the number of stations needed to complete all tasks.

Figure 22 shows that the utilization rate is 100% in the early stage due to the lack of sites. However, with the increase in the number of stations, station redundancy appears and the resource utilization has gradually declined in all scenarios.

From the above experiment results, we can draw the following two conclusions. First, the algorithm proposed in this paper can well solve the multi-objective and multi-constraint resource scheduling problem of passive location. Secondly, the proposed algorithm has high reliability in different scenarios.

6. Conclusions

In this paper, we studied the scheduling problem for passive location resources and proposed a new solution method named MMIGAS. A multi-objective function was conceived to balance various aspects of the performance such as location accuracy, efficiency and resource utilization. And multi-constraint (i.e., frequency, cooperation requirement and capability) was formulated for the practicability of the approach. CI, PF and MGO were implemented to improve the GA, by enhancing the convergence rate and global optimal ability. We evaluated the performance of MMIGAS by computer simulations. In various scenarios, this method can reach its convergence bound within 100 iterations, showing a remarkable astringency. Moreover, its steady time complexity was illustrated because the calculation time was shown to have an approximately linear relationship with population and coding length. Furthermore, we compared traditional manual scheduling and MMIGAS. The results showed that the efficiency is clearly improved by MMIGAS and the location accuracy is still maintained at a high level in a scenario of more than 50 resources at the same time. At last, we also conducted a multi-objective parameter adjustment experiment to verify that the algorithm is suitable for different target requirements and reliable in different scenarios. In conclusion, the proposed algorithm can solve the problem of scheduling of station resources in passive location while maintaining high efficiency and stable location accuracy.