Multi-Static Radar System Deployment Within a Non-Connected Region Utilising Particle Swarm Optimization

Abstract

This paper is mainly devoted to studying the deployment problem of a multi-static radar system (MSRS) within a non-connected deployment region using multi-objective particle swarm optimization (MOPSO). By modeling and reformulating the problem, it can be represented as a multi-objective mixed integer programming (MOMIP), which eliminates the need for additional constraints. To enhance the algorithm performance, integer variables and continuous ones are treated separately employing multiple velocity formulas. The velocity formulas for integer variables are modified using the sigmoid function and genetic operation, leading to the proposal of two MSRS deployment algorithms, namely MOPSO-Sigmoid and MOPSO-Gene. To evaluate the performance of the proposed algorithms, they are compared with two existing MOPSO-based algorithms. The first algorithm is the MSRS deployment algorithm for the non-connected deployment region that addresses the additional constraint problem model. The second algorithm is based on an existing conventional MOPSO algorithm and addresses the equivalent MOMIP problem model. A numerical study demonstrates that MOPSO-Sigmoid and MOPSO-Gene exhibit promising efficiency and effectiveness.

1. Introduction

In recent years, there has been a growing interest among researchers in the field of multi-static radar system (MSRS) [1,2,3]. In comparison to conventional mono-static radar, MSRS has the potential to enhance performance, yet it also introduces a multitude of new challenges. Among these, the issue of node deployment has attracted the attention of many researchers [4,5,6]. The computational burden associated with the optimal node deployment criteria for MSRS is escalating, due to the introduction of new applications, such as advanced waveform design [7], novel tracking technology [8], advanced intelligent electronic countermeasure [9], and remote sensing [10,11]. In order to address the computational challenge, heuristic algorithms like particle swarm optimization (PSO) have been employed in many studies on radar or sensor deployment [12,13,14,15,16,17]. On the other hand, in practical applications, it is often necessary to consider multiple conflicting performance indicators simultaneously. Consequently, some researchers have constructed unconstrained multi-objective optimization problem models for the MSRS deployment problem and solved them with multi-objective particle swarm optimization (MOPSO) and its variants [18,19]. Nevertheless, the aforementioned works are predicated on the assumption that the MSRS deployment region is connected.

Due to geographical constraints, meteorological conditions, special requirements, or other reasons, it is not uncommon for the deployment region of MSRS to be complex and scattered. It can be said that the deployment region of MSRS is often divided into several non-connected subregions by the regions that are unsuitable for deployment in practice, such as rivers, steep hills, and so on. The non-connected deployment region of MSRS could be treated as a constrained multi-objective problem (MOP) and often solved using constraint handling mechanisms [20,21].

However, the introduction of constraint handling mechanism may result in an increase in algorithm complexity and a concomitant rise in computing cost when attempting to solve the MSRS deployment problem, particularly when MOPSO is employed. To the authors’ best knowledge, at present, this problem has not been paid enough attention by researchers. Consequently, further research is required to investigate MSRS deployment within non-connected deployment region. This is indeed the main topic of this paper.

1.1. Overview

The following literature overview contains three main areas of research: (1) the MSRS deployment, (2) the constraint handling mechanism with PSO, and (3) the solving of mixed-integer programming (MIP) solution with PSO.

1.1.1. MSRS Deployment

The deployment of nodes in MSRS has been demonstrated to enhance its performance. The optimal location for each node is determined through traversal while adhering to strict criteria [4,5]. A algorithm for MSRS deployment is proposed, utilizing a sequential exhaustive enumeration approach. However, this method is susceptible to significant computational constraints [6]. The computational challenge has been addressed in numerous studies by employing PSO, which has demonstrated excellent performance in solving continuous variable problems [12,13,14,16]. Based on the aforementioned works, an MSRS deployment problem with multiple conflicting performance indicators is investigated [18,19]. Another work is devoted to the iteration convergence criterion [20]. Nevertheless, these works are all based on the assumption that the MSRS deployment region is connected. There is a paucity of relatively systematic studies on the case of non-connected deployment regions.

1.1.2. Constraint Handling Mechanisms with PSO

Many studies have focused on the constraints handling mechanism, which can be broadly classified into three categories. (1) Modifying the ordering of solutions [22], which changes the ordering rule of candidate solutions so that feasible solutions are identified. Although intuitive, this approach may reduce the efficiency of the algorithm when solving complex problems. (2) Modifying the constraints [23], which regards constraints as additional objectives. This mechanism could be inconvenient when the number of constraints considered is large. (3) Modifying the objective function, which is also known as the penalty function mechanism. Among these mechanisms, the penalty function is the most direct and commonly used, due to the universality of PSO towards optimization problems.

The fundamental principle underlying the penalty function mechanism is punishing the infeasible solutions during the calculation of objective functions. The penalty function mechanism can be subclassified into two categories, static [24] and adaptive [25,26]. The former approach is relatively simpler, which introduces a fixed penalty value to all infeasible solutions when calculating the objective functions. In contrast, the latter approach modifies the penalty function continuously throughout the iteration, based on the information gathered from the search process. Although the modified criteria vary, the most commonly used one is to determine the penalty function according to the constraint violation of each infeasible solution. Nevertheless, the aforementioned methodologies inevitably result in increased algorithm complexity when compared to unconstrained versions.

1.1.3. MIP Solution with PSO

To date, only a limited number of studies have focused on the application of multi-objective mixed integer programming (MOMIP) with PSO. A real-world application of MOMIP, multi-objective portfolio optimization is studied in [27], which is further transformed into a standard MOP by assuming dependence among integer variables and continuous ones on their investment problem. This method is ingenious, but it is not appropriate for general MOMIP like MSRS deployment.

Meanwhile, many methods have been proposed for single-objective mixed-integer programming (SOMIP). Considering that some methods for SOMIP could offer valuable insights for the solving MOMIP, we also investigated the heuristic algorithms based on the SOMIP solving methodologies, as follows. The most enlightening and most commonly used methodology for solving SOMIP is to treat the integer variables as continuous during the iterations, and to obtain the true value of each integer variable by rounding operation [28,29]. While these methods are capable of addressing the SOMIP, their algorithm performance is constrained due to the inability to fully leverage the characteristics of integer variables inherent in the problem. On the other hand, some researchers have attempted to integrate some specific mechanisms, such as the branch-and-bound method, into PSO to develop an SOMIP customized algorithm [30]. However, it results in the optimization objective being recalculated multiple times within each iteration, which is a challenging solution for MOMIP, particularly in cases where the computational objective functions are complex, such as the MSRS deployment problem. Therefore, the methods employed for SOMIP cannot be directly employed to the domain of MOMIP.

In summary, according to the available literature, the problem of solving MOMIP with PSO remains unresolved.

1.2. Motivation

The motivation of this paper mainly stems from engineering practice. In practical application, the MSRS deployment region is often divided into several non-connected subregions due to geographical limitations, meteorological conditions, or other reasons. For further details, please refer to Figure 1 and the context provided in Section 2.1. These deployment problems, which we refer to as MSRS deployment within a non-connected deployment region, can be properly abstracted and modeled as a typical multi-objective segmented decision variable problem (MOSDVP). As mentioned in our previous work [19,20], given the complexity of the problem at hand, we model the non-connected deployment region as additional constraints and attempt to address it, employing MOPSO with a constraint-handling mechanism to address it. However, MOPSO is demonstrably less efficient and effective than when solving the MSRS deployment problem with a connected deployment region. This phenomenon promptly attracted our attention.

To eliminate the additional constraints associated with the non-connected deployment region, we reformulate this problem into an MOMIP and employ the rounding operation for integer variables to solve this MOMIP. The results indicate that this method remains less efficient than conventional methods. To address this, we modify the velocity formula for integer variables while maintaining those for continuous variables. Finally, we solve the deployment problem in an efficient and effective manner.

1.3. Original Contributions

The original contributions of this paper are as follows.

(1) In order to address the MSRS deploying problem within a non-connected deployment region, we conducted further investigation and extended the problem model. Rather than introducing additional constraints, we reformulated the problem into an MOMIP by dividing the deployment region and introducing integer variables. This allows the full potential of the matching algorithm to be realized.

(2) Furthermore, in order to effectively address the attached integer variables, we propose two MSRS deployment algorithms for the non-connected deployment region. These algorithms employ two altering velocity formulas for integer variables based on the sigmoid function and genetic operation. The results of the comparative experiment results demonstrate that the proposed algorithms exhibit a statistically significant superiority over traditional algorithms. Moreover, these proposed algorithms can also be applied in general MOMIP.

1.4. Organization

The rest of this paper is organized as follows. Section 2 presents the problem formulation of MSRS deployment within a non-connected deployment region. This formulation includes two variations: one with additional constraints and another with additional integer variables. In Section 3, the customized algorithms for MSRS deployment within a non-connected region problem are presented. Section 4 presents the results of the proposed algorithms on a benchmark test set and on MSRS deployment within a non-connected deployment region. Section 5 presents a conclusion.

2. Problem Formulation

The following section outlines the methodology employed to establish and extend the mathematical model of an MSRS deployment problem within a non-connected region, to align with the mathematical solving tool adopted.

To fully consider this problem and to avoid overcomplicating it, we focus on the radar detection mission in our study. For the sake of convenience in expression, this problem will be studied in two-dimensional space. It is also worth noting that the model and methodology proposed in this paper are readily extended to other radar application areas by replacing the optimization objectives.

2.1. Mathematical Modeling

In light of the fact that MSRS is designed to monitor a surveillance region with potential targets, we divide the surveillance region A into L resolution cells. The optimal deployment scheme can then be defined as the scheme with the overall best detection probability $P_d$ performance of MSRS among all resolution cells.

The non-connected deployment region B can be defined as a combination of non-connected deployable subregions, i.e., $\mathbf{B}=\bigcup {\mathbf{B}}_m$, where J widely separated nodes are deployed within.

Moreover, the effective coverage region C is defined as the region where the detection probability of the lth resolution cell $P_d\left(l\right)$ is greater than the detection probability threshold of the MSRS $P_{dt}$. The sketch of this optimization problem is shown as Figure 1.

In light of the aforementioned considerations, the overall optimal $P_d$ performance scheme for the MSRS should simultaneously satisfy both of the following criteria: (1) the first objective is to ensure the most reliable monitoring of all resolution cells, which means maximizing the area of the effective coverage region, C; (2) the second objective is to ensure the most even distribution of $P_d$ among all resolution cells.

In practice, the optimal performance objective can be represented by effective cover rate (ECR), which is the coverage ratio of the area of effective coverage region to the surveillance region. The computational formulas for ECR can be expressed as:

$$\mathrm{ECR}\left(\mathrm{\Theta }\right)={\displaystyle \frac{area\left(\mathbf{C}\left(\mathrm{\Theta }\right)\bigcap \mathbf{A}\right)}{area\left(\mathbf{A}\right)}},$$

(1)

where $area\left(•\right)$ represents the area of this region and $\mathrm{\Theta }$ represents the deployment scheme.

To ascertain the specific mathematical expressions of the evenly distributed performance objective, it was necessary to conduct a study of the arbitrary resolution cell and the value of $P_d$. By using a monopulse square rate detector, the detection probability of the lth resolution cell $P_d\left(l\right)$ can be expressed as [31,32]:

$$P_d\left(l\right)=Q_{J\times J}\left(\sqrt{2{\mathrm{SNR}}_l},\sqrt{2{\gamma }_T}\right),$$

(2)

where $Q_u\left(\alpha ,t\right)$ represents the Marcum Q function (see [33] for detail definition), ${\mathrm{SNR}}_l$ represents the ratio of total signal energy to noise power (SNR) of the lth resolution cell, and ${\gamma }_T$ represents the detection threshold of MSRS.

Given that the threshold ${\gamma }_T$ is set according to a predetermined false alarm probability, $P_d\left(l\right)$ is solely dependent on ${\mathrm{SNR}}_l$, which is to say, the objective is to identify the scheme that results the most evenly distributed ${\mathrm{SNR}}_l$. To facilitate the calculation, a uniform distribution can be translated into a focus on the minimum. Hence, the objective of distributing performance evenly can be proposed as a minimum SNR (minSNR). The computational formula can be given as:

$$\mathrm{minSNR}\left(\mathrm{\Theta }\right)=\underset{0<l<L}{min}\left\{{\mathrm{SNR}}_l\left(\mathrm{\Theta }\right)\right\}.$$

(3)

It is evident that, whilst the total energy remains constant, an increase in the minSNR results in a more uniform energy distribution. Therefore, the uniform distribution of energy can be converted to maximize the minSNR.

Furthermore, by assuming that the transceiver channels of each node of MSRS are orthogonal, ${\mathrm{SNR}}_l$ can be expressed as the sum of the signal energy divided by the noise power of each transceiver channel. By jointly processing the received signals from all $J\times J$ transceiver channels, ${\mathrm{SNR}}_l$ can be expressed as:

$${\mathrm{SNR}}_l=\sum _{i=1}^J\sum _{j=1}^J{\mathrm{SNR}}_l\left(i,j\right),$$

(4)

where J is the number of nodes of MSRS. By assuming that all J nodes of MSRS have the same parameters, for a typical targets whose radar cross section is $\sigma$, the SNR of the transceiver channel for transmitting from ith node and receiving at jth node ${\mathrm{SNR}}_l\left(i,j\right)$ can be expressed as [19,34]:

$${\mathrm{SNR}}_l\left(i,j\right)=D_0{\displaystyle \frac{{\sigma }^{ij}{R}_{max}^4}{\sigma {\left(R_{i,l}{R}_{j,l}\right)}^2}},$$

(5)

where $D_0$ is the detectability factor, $R_{max}$ is the maximum detection range when radar node works independently, ${\sigma }^{ij}$ is the bistatic radar cross section of transceiver channel for transmitting from ith node and receiving at jth node, and $R_{i,l}$ is the distance between the ith node and the lth resolution cell.

Given that $D_0$ is defined in accordance with the typical characteristics of the target and that $R_{max}$ can be regarded as a constant in the MSRS deployment problem, the performance of MSRS is determined by σ^ij/σ, R_i,l and R_j,l. In other words, the optimal solution to this problem depends on the position of each node of MSRS.

Consequently, the decision vector $\mathrm{\Theta }$ of this problem is defined by the location of each node, represented by the coordinates $\left(x,y\right)$. Meanwhile, it is evident that the objective of MSRS deployment is to identify the MSRS deployment scheme that maximizes the aforementioned objectives. Hence, the form of MSRS deployment within a non-connected deployment region problem is shown as:

$$\begin{gathered} \begin{array}{cc}\hfill & \begin{array}{cc}\hfill \mathrm{maximize}\mathbf{F}\left(\mathrm{\Theta }\right)& =\left\{f_1\left(\mathrm{\Theta }\right),f_2\left(\mathrm{\Theta }\right)\right\},\hfill \\ \hfill & =\left\{\mathrm{ECR}\left(\mathrm{\Theta }\right),\mathrm{minSNR}\left(\mathrm{\Theta }\right)\right\},\hfill \end{array}\hfill \end{array} \\ \begin{array}{cc}\hfill & \mathrm{\Theta }={\left(x_1,y_1,\dots ,x_J,y_J\right)}^T\hfill \\ \hfill & s.t.\left(x_j,y_j\right)\in \mathrm{B}=\bigcup {\mathrm{B}}_m,j=1,\cdots ,J.\hfill \end{array} \end{gathered}$$

(6)

where ${\left(•\right)}^T$ is the transpose operation.

Problem (6) is evidently a constrained multi-objective optimization problem, comprising a constraint and two conflicting optimization objective functions. It is therefore impossible to identify a single solution that can simultaneously optimize all of the objective functions.

Our previous work have demonstrated that the computational complexity of the optimization objectives for this problem exceeds that of traditional exact solution algorithms [19,20]. Therefore, we adopt the MOPSO, a well-tested heuristic algorithm architecture, to address this deployment problem.

However, our previous works did not study the case with a non-connected deployment region in sufficient depth, merely offering an initial conceptual solution. The numerical simulations have demonstrated that the problem (6) constrains the performance of MOPSO, resulting in challenges in calculation accuracy and computational cost. Therefore, it is necessary to abstract the problem into a mathematical model and extend it into a more appropriate form.

2.2. Model Extending

It is evident that the defining characteristic of problem (6) lies in its non-connected solution space, i.e., the deployment region B is non-connected. Furthermore, it can be considered a problem with several additional constraints compared to a deployment problem within a connected deployment region. So we abbreviate this model as the additional constraint problem model (AC model).

AC model can be abstracted as:

$$\begin{array}{cc}\hfill & \mathrm{maximize}\mathbf{F}\left(\mathrm{\Theta }\right)={\left[f_1\left(\mathrm{\Theta }\right),f_2\left(\mathrm{\Theta }\right)\right]}^T\hfill \\ \hfill & \mathrm{subject}\mathrm{to}:\mathrm{\Theta }\in \mathrm{\Omega },\hfill \end{array}$$

(7)

where $\mathrm{\Theta }$ represents the N-dimensional decision vector, where N is the number of decision variables (in our case $N=2\times J$). $\mathrm{\Omega }\subset R^N$ is non-empty and non-connected, and it represents the solution space, i.e., deployment region. In mathematics, a problem with a non-connected solution space $\mathrm{\Omega }$, can be collectively referred to as MOSDVP, where some or all of the decision variables exhibit a segmented value range.

Accordingly, the decision variables of MOSDVP can be further divided into two categories according to whether value range is segmented or connected. This can be expressed as $\mathrm{\Theta }={\left[{\mathrm{\Theta }}_{\mathrm{S}};{\mathrm{\Theta }}_{\mathrm{C}}\right]}^T$, where ${\mathrm{\Theta }}_{\mathrm{S}}$ is the vector of segmented variables and ${\mathrm{\Theta }}_{\mathrm{C}}$ is the vector of connected variables. They represent non-connected dimensions and connected dimensions, respectively, in the deployment region.

For the sake of brevity, the subsequent content is all based on the unconstrained MOSDVPs, i.e., problems discussed below contain no constraints other than those caused by the segmented variables. The conclusions are also applicable to constrained MOSDVPs by introducing a proper constraint handling mechanism.

It can be argued that an unconstrained MOSDVP can be treated as a generic constrained MOP, which contains only linear inequality constraints. This implies that an MOSDVP can be refined to

$$\begin{array}{c}\hfill \begin{array}{c}\mathrm{maximize}\mathbf{F}\left({\mathbf{\Theta }}_{\mathit{S}},{\mathbf{\Theta }}_{\mathit{C}}\right)\hfill \\ s.t.\left\{\begin{array}{c}\begin{array}{c}\mathbf{\Theta }\in \left[l{b}_1,u{b}_1\right]\times \cdots \times \left[l{b}_N,u{b}_N\right]\subseteq R^N\hfill \\ {\theta }_s\in \left[l{b}_s^1,u{b}_s^1\right]\cup \cdots \cup \left[l{b}_s^{K_s},u{b}_s^{K_s}\right],\forall {\theta }_s\in {\mathbf{\Theta }}_{\mathit{S}}\hfill \end{array}\hfill \end{array}\right.\hfill \end{array}\end{array}$$

(8)

where for any segmented variable ${\theta }_s\in {\mathbf{\Theta }}_{\mathit{S}}$, its value range is divided into $K_s$ subintervals, and $lb$ is the interval lower bound and $ub$ is the interval upper bound.

To circumvent these additional constraints, we propose an alternative approach to determine each segmented variable ${\theta }_s$ by employing a combination of a connected variable ${\widehat{\theta }}_s$ and an additional integer variable $z_s$. This approach can be expressed as:

$$\begin{array}{c}\hfill \begin{array}{c}{\theta }_s=l{b}_{z_s}+{\widehat{\theta }}_s\times {∥u{b}_{z_s}-l{b}_{z_s}∥}_2\hfill \\ \left\{\begin{array}{c}{\widehat{\theta }}_s\in \left[0,1\right]\hfill \\ z_s\in \left\{1,\cdots ,K_s\right\}\hfill \end{array}\right.\hfill \end{array}\end{array}$$

(9)

where ${∥•∥}_2$ represents the the length of the corresponding interval. This approach can be interpreted as first determining which segment ${\theta }_s$ is within, using $z_s$, and then determining the specific value in this segment using ${\widehat{\theta }}_s$.

Further, substituting (9) into problem (8), we can obtain the equivalent model for MOSDVP as:

$$\begin{array}{c}\hfill \begin{array}{c}\mathrm{maximize}\mathbf{F}\left({\widehat{\mathrm{\Theta }}}_{\mathrm{S}},{\mathrm{\Theta }}_{\mathrm{C}},\mathrm{Z}\right)\hfill \\ s.t.\left\{\begin{array}{c}\begin{array}{c}{\mathrm{\Theta }}_{\mathrm{C}}\in \left[l{b}_1,u{b}_1\right]\times \cdots \times \left[l{b}_{N_C},u{b}_{N_C}\right]\subseteq R^{N_C}\hfill \\ {\widehat{\mathrm{\Theta }}}_{\mathrm{S}}\in \left[0,1\right]\times \cdots \times \left[0,1\right]\subseteq R^{N_S}\hfill \\ {\mathrm{Z}}_{\mathrm{S}}\in \left\{1,\cdots ,K_1\right\}\times \cdots \times \left\{1,\cdots ,K_{N_S}\right\}\subseteq Z^{N_S}\hfill \end{array}\hfill \end{array}\right.\hfill \end{array}\end{array}$$

(10)

where ${\widehat{\mathrm{\Theta }}}_{\mathrm{S}}$ is the vector that consists of ${\theta }_s$s, ${\mathrm{Z}}_{\mathrm{S}}$ is the vector that consists of $z_s$s, while $N_C$ and $N_S$ represent the number of continuous variables and segmented variables, respectively. Obviously, this problem model (10) contains only connected variables (i.e., $\theta \in {\left[{\widehat{\mathrm{\Theta }}}_{\mathrm{S}};{\mathrm{\Theta }}_C\right]}^T$) and integer variables (i.e., $z\in \mathrm{Z}$), which is an MOMIP. Hence, we abbreviate this extended model as the MOMIP model.

3. MOPSO-Based Deployment Algorithm

This section mainly concerns the customized algorithm for MSRS deployment within a non-connected region problem. Without loss of generality, we utilize the crowding distance based MOPSO (MOPSO-CD) [35], a well-established and widely utilized MOPSO variant, as the fundamental algorithm framework for the subsequent customized algorithms. To the authors’ best knowledge, the methodologies proposed in this paper can also be applied to any MOPSO-based algorithms.

Firstly, the basic concepts related to the MOPSO-CD algorithm are defined as follows:

MOPSO adopts the Pareto optimality criterion, as outlined in [36], which involves identifying a set of optimal trade-off solutions rather than a single optimal solution. The set of all Pareto optimal tradeoff solutions is designated as the Pareto set $PS$. The set of optimization objective function vectors obtained by all the solutions from $PS$ is referred to as the Pareto front $PF$.

MOPSO, as a quintessential population-based heuristic algorithm, explores the solution space by changing the position of candidate solutions (also known as particles) through iterations. In particular, P particles are randomly distributed throughout the solution space as the initial solution. Subsequently, the location of each particle is gradually adjusted by combining its current position (inertia component), its own experience (cognitive component), and the optimal solution found by other particles (social component). For original continuous variables, the velocity formula for particle p at iteration t is as:

$$\begin{array}{cc}\hfill v_n^p\left(t+1\right)& =w\times v_n^p\left(t\right)+c_1\times r_1\times \left(p{b}_n^p\left(t\right)-{\theta }_n^p\left(t\right)\right)\hfill \\ \hfill & +c_2\times r_2\times \left(g{b}_n\left(t\right)-{\theta }_n^p\left(t\right)\right),\hfill \end{array}$$

(11)

$${\theta }_n^p\left(t+1\right)={\theta }_n^p\left(t\right)+v_n^p\left(t+1\right),$$

(12)

where $x_n^p\left(t\right)$ represents the value of the nth decision variable of the particle p at the iteration t. w is the inertia weight and c is the acceleration constant. The random real value r is uniformly distributed in the interval $[0,1]$. $p{b}^p$ is the individual best solution of the particle p (also termed as personal best or personal leader), and $gb$ is the best solution found by the entire swarm (also known as global best or global leader).

At each iteration, the trajectory of each particle is recorded, and the superior solutions found up to that point are used to create and update the $archive$. In other words, the superior solutions identified by the entire swarm are stored in the $archive$. Hence, upon the fulfillment of the termination condition, the optimal trade-off solutions discovered by the algorithm are preserved within the $archive$.

The definition of superior solutions, the selection rules for $gb$ and $pb$, and the release method for inferior solutions vary across different MOPSO variants. In general, the fundamental difference lies in the definition of the superior solution and the ranking of candidate solutions. In this paper, the standard for evaluating the quality of solutions is the combination of Pareto dominance and crowding distance(CD).

Which is to say the solutions are sorted into two steps.

First, the non-dominated solutions that outperform all remaining solutions in at least one optimization objective are identified and ranked above other solutions. Second, among these non-dominated solutions, they are arranged in descending order of CD.

This mechanism has the potential to reduce the clustering density of solutions, thereby reducing the probability of falling into the local $PS$.

The overall algorithm is presented in Algorithm 1. The two major components, namely (1) the problem transformation for MSRS deployment within a non-connected region and (2) the modification of velocity formulas for integer variables, are described in Section 3.1 and Section 3.2, respectively. Subsequently, the extant MSRS deployment algorithms for comparing are described in Section 3.3.

Algorithm 1: MSRS Deployment algorithm within non-connected region.
w is the inertia weight  c is the acceleration constant  $T_{max}$ is the total iteration number  $N_P$ is the number of particles  $N_{\mathrm{C}}$ is the number of continuous variables  $N_{\mathrm{S}}$ is the number of segmented variables  $N_{\mathrm{bin}}$ is the number of binary variables  ${\mathrm{\Theta }}^p\left(t\right)$ is the position of the pth particle at iteration t  ${\mathrm{\Theta }}_S$ is the vector of segmented variables  ${\mathrm{\Theta }}_C$ is the vector of connected variables
Step 0: Problem transformation
for	$s=1,2,\dots ,N_S$ do
	Map segmented variable ${\theta }_s$ to a combination of integer variable $z_s$ and a connected variable ${\widehat{\theta }}_s\in \left[0,1\right]$ using (9); Encode $z_s$ into a linear combination of binary variables $z_{\mathrm{bin}}$ by means of binary encoding;
end
Step 1: Initialization
for  $p=1,2,\dots ,N_P$ do
	for	$n=1,2,\dots ,N_{\mathrm{C}}+N_{\mathrm{S}}+N_{\mathrm{bin}}$ do
		Randomly initialize particle position ${\mathrm{\Theta }}^p\left(0\right)$ and the individual best solution $p{b}^p={\mathrm{\Theta }}^p\left(0\right)$; Initialize $v_n^p\left(0\right)=0$
	end Calculate optimization objectives $\mathbf{F}\left({\mathrm{\Theta }}^p\left(0\right)\right)$; Initialize $archive$ as the non-dominated solutions in initialized solutions and global best solution $gb$ as randomly selected from $archive$;
end
for	$t=1,2,\dots ,T_{max}$ do
	Step 2: Sort the non-dominated solutions in $archive$ in descending CD; Step 3: Particle position update with modified velocity formula For MOPSO-Sigmoid, follow the Algorithm 2 and for MOPSO-Gene, follow the Algorithm 3; Step 4: Perform mutation operator proposed in [37]; Step 5: Boundaries check for each dimension;
	for	$p=1,2,\dots ,N_P$ do
		$\phantom{(}$$\phantom{(}$Step 6: Calculate $\mathit{F}\left({\mathrm{\Theta }}^p\left(t\right)\right)$; Step 7: Replace $p{b}^p$ with the non-dominated solutions of $\left(p{b}^p\bigcup {\mathrm{\Theta }}^p\left(t\right)\right)$; Step 8: Replace $archive$ with the non-dominated solutions of $\left(archive\bigcup {\mathrm{\Theta }}^p\left(t\right)\right)$;
	end
	$\phantom{(}$Step 9: Sort the solutions in $archive$ in descending CD and randomly select the $gb$ for each particle from a specified top portion of the sorted $archive$;
end
Step 10: Solution output;
For each solution in $archive$, calculate ${\theta }_s$ according to $z_{\mathrm{bin}}$ and ${\widehat{\theta }}_s$ using (9);
Step 11: Output the final solutions $\mathrm{\Theta }={\left[{\mathrm{\Theta }}_{\mathrm{S}};{\mathrm{\Theta }}_{\mathrm{C}}\right]}^T$ in $archive$;

3.1. Problem Transformation for MOMIP Model

As mentioned in Section 2, the deployment of MSRS within a non-connected region can be transformed into an MOMIP like (10). In this context, the integer variables distinguish this problem from a standard MOP. Hence, the most critical issue to be addressed is the handling of integer variables.

To handle integer variables, each integer variable z is encoded into a linear combination of binary variables z_bins by means of binary encoding and concatenated together by order. For further information, please refer to the following citations: [38,39,40,41]. Hence, the problem model (10) is transformed into a multi-objective mixed binary programming model (MOMBP model) as:

$$\begin{array}{c}\hfill \begin{array}{c}\mathrm{maximize}\mathbf{F}\left({\widehat{\mathrm{\Theta }}}_{\mathrm{S}},{\mathrm{\Theta }}_{\mathrm{C}},{\mathrm{Z}}_{\mathrm{bin}}\right)\hfill \\ s.t.\left\{\begin{array}{c}\begin{array}{c}{\mathrm{\Theta }}_{\mathrm{C}}\in \left[l{b}_1,u{b}_1\right]\times \cdots \times \left[l{b}_{N_C},u{b}_{N_C}\right]\subseteq R^{N_C}\hfill \\ {\widehat{\mathrm{\Theta }}}_{\mathrm{S}}\in \left[0,1\right]\times \cdots \times \left[0,1\right]\subseteq R^{N_S}\hfill \\ {\mathrm{Z}}_{\mathrm{bin}}\in \left\{0,1\right\}\times \cdots \times \left\{0,1\right\}\subseteq Z^{N_{\mathrm{bin}}}\hfill \end{array}\hfill \end{array}\right.\hfill \end{array}\end{array}$$

(13)

where $z_{\mathrm{bin}}$ represents a binary-encoded integer variable, which is henceforth referred to as binary variable. Meanwhile, ${\mathrm{Z}}_{\mathrm{bin}}$ is the vector of $z_{\mathrm{bin}}$, $N_{\mathrm{bin}}=\sum _s⌈{log}_2\left(K_s\right)⌉$ is the number of binary variables and $⌈•⌉$ represents the round up operator.

In comparison to the standard MOP, the MOMBP model exhibits a significant distinction in its binary variables. Given the inability of generic MOPSO to solve binary variables, we proceeded to modify the algorithm.

3.2. Velocity Formulas for Integer Variables

The primary challenge in solving the MOMBP model is that the generic velocity formulas for particle motion, i.e., (11) and (12), are designed for continuous variables and therefore not directly applicable to discrete variables.

However, for MOPSO, it was observed that the motion of each variable is independent, which implies that the projections of particle trajectories in different dimensions are independent of one another. In other words, the velocity formulas for binary variables can be modified to enhance variable adaptation, while the velocity formulas for continuous variables adhere to the generic formulas. This methodology can be designated as the multiple velocity formulas. The following two multiple velocity formula-based MSRS deployment algorithms are proposed.

3.2.1. MSRS Deployment Algorithm Based on Sigmoid Function (MOPSO-Sigmoid)

The natural number operations utilized in the generic position iteration formula (12) are unsuitable for binary variables. However, the Boolean operations are specifically designed for binary variables. Consequently, the inversion operator of a Boolean operation is employed to calculate the position iteration of the binary variable $z_{\mathrm{bin}}$ in the MOMBP model (13). While the velocity v in (11) is normalized and taken as a probability, it is used to control whether the value of the binary variable $z_{\mathrm{bin}}$ changes. The detailed methodology is as follows:

Firstly, in order to maintain the group behavior methodology of PSO, the velocity iteration formula of $z_{\mathrm{bin}}$ essentially remains the same as that given in (11), with the addition of an additional normalization operator. Among the existing velocity normalization methods in PSO, the sigmoid function is the most widely used because it does not require the introduction of additional parameters. Hence, this function is employed in this paper. The specific method is to normalize the velocity with the sigmoid function, which can be defined as:

$$\overline{v}=Sigmoid\left(v\right)={\displaystyle \frac{1}{1+e^{-v}}},$$

(14)

where $\overline{v}$ is the normalized velocity. Obviously, the normalized velocity $\overline{v}\in \left(0,1\right)$.

Further, the position iteration Formula (12) of binary variable motion can be replaced by:

$$z_n^p\left(t+1\right)=\left\{\begin{array}{c}\begin{array}{c}{\overline{z}}_n^p\left(t\right),ifrand<{\overline{v}}_n^p\left(t+1\right)\hfill \\ z_n^p\left(t\right),else\hfill \end{array}\hfill \end{array}\right.$$

(15)

where $\overline{z}$ is the inversion operator and $rand$ is a random real number uniformly distributed in $(0,1)$. The detail modified velocity formula is presented in Algorithm 2.

Algorithm 2: The modified dynamics based on the sigmoid function.

In summary, this customized algorithm is based on the sigmoid function and normalized velocity, hence it can be named MOPSO-Sigmoid.

3.2.2. MSRS Deployment Algorithm Based on Genetic Operation (MOPSO-Gene)

Given the promising results achieved by genetic algorithms in optimizing binary variables [37], we propose a novel approach combining the genetic operation (including mutation and crossover) with the group behavior methodology of PSO (i.e., (11) and (12)). This integration leads to the development of a modified velocity formula for binary variables motion. The specific details of the mutation operator and crossover operator are provided below.

The mutation operator is primarily implemented through the use of binary mutation, which entails the execution of an inversion operator within a Boolean operation, with the mutation probability designated as $p_{mutate}$. In this paper, the mutation probability $p_{mutate}$ is proportional to the inertia weight w in (11). This proportionality reflects the inertia component observed in swarm behavior. The mutation operator can be expressed as:

$$\begin{array}{c}{z}_n^p\left(t+1\right)={\overline{z}}_n^p\left(t\right),ifrand<p_{mutate}\\ p_{mutate}={\displaystyle \frac{1}{N_P}}\times w\end{array}$$

(16)

where $N_P$ represents the number of particles, while $rand$ is a random real number uniformly distributed in the interval $(0,1)$.

The crossover operator is to modify the value of $z_n^p$, which represents the nth binary variable of particle p, to that of the personal leader $p{b}_n^p$ or the global leader $g{b}_n$ as specified in (11). The specific crossover object between $pb$ and $gb$ is determined by the ratio of the two acceleration factors $c_1$ and $c_2$ in (11). This ratio corresponds to the relative emphasis on individual experience or group experience in swarm behavior. The crossover probability $p_{cross}$, is set to a relatively large constant. The crossover operator can be expressed as:

$$\begin{array}{c}{z}_n^p=\left\{\begin{array}{c}\begin{array}{c}{z}_n^p,ifran{d}_1\ge p_{cross}\hfill \\ p{b}_n^p,ifran{d}_1<p_{cross},ran{d}_2<{\displaystyle \frac{c_1}{c_1+c_2}}\hfill \\ g{b}_n,ifran{d}_1<p_{cross},ran{d}_2\ge {\displaystyle \frac{c_1}{c_1+c_2}}\hfill \end{array}\hfill \end{array}\right.\hfill \end{array}$$

(17)

where $ran{d}_1$ and $ran{d}_2$ are random real numbers uniformly distributed in the interval $(0,1)$.

Similar to MOPSO-Sigmoid, this algorithm based on the aforementioned genetic operation is named MOPSO-Gene. The detail modified velocity formula of MOPSO-Gene is shown in Algorithm 3.

Algorithm 3: The modified dynamics based on genetic operation.

3.3. Comparing Algorithms for MOSDVP

In order to demonstrate the efficacy of the proposed algorithms, two existing MOPSO-CD-based comparing algorithms for the MSRS deployment problem are introduced.

3.3.1. MSRS Deployment Algorithm for AC Model (MOPSO-Penalty)

The first comparing algorithm is to solve the MSRS deployment problem as an AC model (i.e., problem model (8)) directly. The primary challenge lies in the effective handling of the constraint that arises from the segmented decision variables. We utilize a additive adaptive penalty factor [42], which is comprised of two components. (1) A constant penalty factor ${\tilde{r}}_C$ is applied to any infeasible solution. (2) An additional adaptive penalty factor ${\tilde{r}}_S$ is applied according to the distance between the solution and the nearest feasible subregion boundary under the Euclidean norm. Consequently, the modified optimization problem can be expressed as:

$$\begin{array}{c}\hfill \begin{array}{c}\mathrm{maximize}\widehat{\mathbf{F}}\left({\mathbf{\Theta }}_{\mathit{S}},{\mathbf{\Theta }}_{\mathit{C}}\right)=\mathbf{F}\left({\mathbf{\Theta }}_{\mathit{S}},{\mathbf{\Theta }}_{\mathit{C}}\right)+\tilde{r}\hfill \\ \tilde{r}=\left\{\begin{array}{c}\begin{array}{cc}{\tilde{r}}_C+{\tilde{r}}_S,\hfill & \mathbf{X}\notin \mathrm{\Omega }\\ 0,\hfill & \mathbf{X}\in \mathrm{\Omega }\end{array}\hfill \end{array}\right.\hfill \\ s.t.\mathbf{\Theta }\in \left[l{b}_1,u{b}_1\right]\times \cdots \times \left[l{b}_N,u{b}_N\right]\subseteq R^N\hfill \end{array}\end{array}$$

(18)

where $\widehat{\mathbf{F}}$ represents the modified optimization objectives and $\tilde{r}$ represents the penalty factor. The expressions of constant penalty factor ${\tilde{r}}_C$ and adaptive penalty factor ${\tilde{r}}_S$ can be given as:

$${\tilde{r}}_C=A$$

(19)

$${\tilde{r}}_S=A\times \sum _{s=1}^{N_S}{r}_s$$

(20)

where A represents the magnitude of the penalty factor chosen according to every particular problem and $r_s$ represents the degree to which ${\theta }_s$ (i.e., the sth element within ${\mathbf{\Theta }}_{\mathit{S}}$) violates the constraint measured by Euclidean distance. We call this comparing algorithm MOPSO-Penalty for short.

3.3.2. MSRS Deployment Algorithm for MOMIP Model (MOPSO-Round)

Another comparing algorithm is to solve the MSRS deployment problem as an MOMIP model. In contrast to the algorithms proposed in this paper, this algorithm addresses integer variables by employing a rounding operation, as described in [28,43]. This operation substitutes continuous variables for discrete ones, thereby enabling the algorithm to handle integer variables.

In this way, all decision variables can be treated uniformly throughout the iterations, resulting in the conversion of the MOMIP to a standard MOP. When solving a problem (10), the problem model is further reformulated as:

$$\begin{array}{c}\hfill \begin{array}{c}\mathrm{maximize}\mathbf{F}\left({\widehat{\mathrm{\Theta }}}_{\mathrm{S}},{\mathrm{\Theta }}_{\mathrm{C}},\left[\widehat{\mathrm{Z}}\right]\right)\hfill \\ s.t.\left\{\begin{array}{c}\begin{array}{c}{\mathrm{\Theta }}_{\mathrm{C}}\in \left[l{b}_1,u{b}_1\right]\times \cdots \times \left[l{b}_{N_C},u{b}_{N_C}\right]\subseteq R^{N_C}\hfill \\ {\widehat{\mathrm{\Theta }}}_{\mathrm{S}}\in \left[0,1\right]\times \cdots \times \left[0,1\right]\subseteq R^{N_S}\hfill \\ \widehat{\mathrm{Z}}\in \left[1,K_1\right]\times \cdots \times \left[1,K_{N_S}\right]\subseteq R^{N_S}\hfill \end{array}\hfill \end{array}\right.\hfill \end{array}\end{array}$$

(21)

where $\widehat{\mathrm{Z}}$ is the vector for substituting continuous variables for discrete ones (i.e., $\mathrm{Z}$) and $\left[•\right]$ is the rounding operation. Therefore, the core modification of this algorithm is to round substitution variables when calculating the optimization objectives. For this reason, we name it MOPSO-Round for short.

4. Numerical Study

This section presents a comparative analysis of the performance of the proposed customized algorithms for MSRS deployment within a non-connected region. For the sake of clarity, we first present a summary of the four customized algorithms proposed in the previous section, along with a brief overview of their corresponding problem models in

Table 1. Summary of four customized algorithms and main features of their corresponding problem models.

Algorithm Name	Problem Model	Decision Variables (Variable Number)
MOPSO -Penalty [42]	AC model (18)	XS ∪ XC (NC + NS)
MOPSO -Round [28]	MOMIP model (21)	${\widehat{\mathrm{X}}}_{\mathrm{S}}\cup {\mathrm{X}}_{\mathrm{C}}\cup \widehat{\mathrm{Z}}$ $\left(N_C+2\times N_S\right)$
MOPSO -Sigmoid	MOMBP model (13)	${\widehat{\mathrm{X}}}_{\mathrm{S}}\cup {\mathrm{X}}_{\mathrm{C}}\cup {\mathrm{Z}}_{\mathrm{int}}$ $\left(N_C+N_S+{\displaystyle \sum _s}⌈{log}_2\left(K_s\right)⌉\right)$
MOPSO -Gene

. It is worth reiterating that all three problem models are, in fact, equivalent models, despite their respective scales of variables and complexities of objective functions differing to some extent.

The algorithms proposed in Section 3 are applied to both benchmark test functions and the MSRS deployment problem. A quantitative comparison is conducted among these algorithms.

4.1. Numerical Study on Benchmark Testing Set

Due to the pursuit of problem-independence by PSO, many benchmark test sets are formed to measure the performance of the algorithm. Each benchmark test set comprises a number of test problems exhibiting varying characteristics. The performance of an algorithm is gauged through statistical analysis of the outcomes observed across the test problems within the benchmark test set.

Specific to our work, since the benchmark test set specially designed for MOSDVP is not seen yet, we employ ZDT [44], a widely used benchmark test set, cut off the value range of part of decision variables for each test problem, and obtain the modified ZDT (MZDT) test set.

For convenience, for MZDT1, MZDT2, and MZDT3, the value range of the last 10 decision variables are cut into 2 segments (i.e., $x_j\in \left[0,0.3\right]\cup \left[0.7,1\right],j=21,\cdots ,30$) and other components remain the same as shown in [38], (Equations (7)–(9)). For MZDT4 and MZDT6, to maintain a consistent number of binary variables, 10, we cut the last 5 variables into 3 segments (i.e., for MZDT4, $x_j\in \left[-5,-3\right]\cup \left[-2,2\right]\cup \left[3,5\right],j=6,\cdots ,10$, and for MZDT6, $x_j\in \left[0,0.2\right]\cup \left[0.3,0.7\right]\cup \left[0.8,1\right],j=6,\cdots ,10$), and other components remain the same as shown in [38], (Equations (10) and (12)).

It is evident that the $PS$ and $PF$ of MZDT test problems remain unaltered in comparison to those of the ZDT test set.

4.1.1. Performance Metrics

In order to quantitatively assess the performance of these algorithms in different testing problems quantitatively, two performance metrics have been implemented in our research: the Hypervolume (HV) [45] and the Additive Unary Epsilon Indicator $\left(I_{ϵ}^{+}\right)$ [46]. These performance metrics indicate the performance of an algorithm by evaluating the quality of the final output approximation Pareto front $P^t$. The following paragraphs provide further details on these performance metrics.

The quality of the approximation Pareto front $P^t$ is determined by the size of the space that dominates the reference point r while being dominated by $P^t$. It can be defined as:

$$HV\stackrel{\Delta }{=}\mathrm{vol}\left[\left(\bigcup _{\forall u\in P^t}D\left(u\right)\right)\cap D^{\left(-1\right)}\left(r\right)\right]$$

(22)

where $D\left(a\right)$ represents the space that a dominates, $D^{\left(-1\right)}\left(a\right)$ represents the space that dominates a, and $\mathrm{vol}\left(•\right)$ represents the Lebesgue measure. A larger HV indicates a better approximation Pareto front.

$I_{ϵ}^{+}$ can be defined as:

$$I_{\epsilon }^{+}\stackrel{\Delta }{=}\underset{\epsilon }{min}\left\{\exists u\in P^t\left|u{\le }_{\epsilon +}r\right.\right\},$$

(23)

where $v{\le }_{\epsilon +}r$ means $f_i\left(v\right)\le \epsilon +f_i\left(r\right),i=1,\dots ,M$. A smaller $I_{\epsilon }^{+}$ indicates a better convergent $P^t$. Therefore, $I_{\epsilon }^{+}$ can only measures the convergence of the results.

To be fair, only feasible solutions obtained by MOPSO-Penalty are included in the calculation of performance metrics while infeasible ones are not included.

4.1.2. Parameter Settings

The common parameters of the four algorithms are all set to be the same. Parameters in the basic PSO velocity formula, acceleration constants $c_1=c_2=2$, and inertia weight w decrease linearly from 0.8 to 0.4 with the number of iterations and all four algorithms select the global best $gb$ from the top 10% sorted $archive$, as suggested in [35]. The magnitude of penalty factor in MOPSO-Penalty $A=10$ and for MOPSO-Gene, the Crossover probability $p_{cross}$ is set to 0.9, as suggested in [37].

In terms of computational cost, the number of particles is $N_P=50$ while the maximum number of iterations is $T_{max}=1000$. In terms of parameters of performance metrics, while the reference points of HV and $I_{ϵ}^{+}$ are (11,11) and (0,0), respectively.

4.1.3. Experimental Results and Comparative Analysis

Considering the random exploration nature of heuristic algorithms, each algorithm was executed 100 times independently for each test problem and all the performance metrics were subsequently measured and recorded statistically. In statistical language, hypothesis testing is a method of statistical inference used to determine whether differences between samples (i.e., the results obtained by each algorithm) are due to sampling error (i.e., accidentalia) or to substantive differences. To ascertain the relative superiority of the four algorithms, hypothesis testing was employed. Unfortunately, some of the samples do not conform to the normality assumption. Hence, the Wilcoxon signed ranks test is employed to assess the performance of the algorithms, as proposed in Section 3 of [47].

The four algorithms are compared in pairs. The null hypothesis, $H_0$, is set as the performance metrics obtained by one algorithm were not better than those obtained by another based on overall results. The alternative assumption, $H_1$, is that the performance metrics obtained by one algorithm were better than those obtained. At the significance level of $\alpha =5\%$, statistical conclusions are drawn in

Table 2. The results of Wilcoxon Signed Ranks Test on MZDTs.

Null Hypothesis	p-Value		Statistical Conclusion
MOPSO-Gene	HV	2.863 × 10−14	Reject
No better than
MOPSO-Sigmoid	Iϵ+	6.247 × 10−26
MOPSO-Gene	HV	<1 × 10−50	Reject
No better than
MOPSO-Round	Iϵ+	<1 × 10−50
MOPSO-Gene	HV	<1 × 10−50	Reject
No better than
MOPSO-Penalty	Iϵ+	<1 × 10−50
MOPSO-Sigmoid	HV	1.295 × 10−29	Reject
No better than
MOPSO-Penalty	Iϵ+	2.480 × 10−14
MOPSO-Sigmoid	HV	5.483 × 10−19	Reject
No better than
MOPSO-Round	Iϵ+	<1 × 10−50
MOPSO-Round	HV	4.779 × 10−3	Reject
No better than
MOPSO-Penalty	Iϵ+	4.616 × 10−5

.

In statistics, a small p-value means that the probability of observation under the null hypothesis $H_0$ is small. That is to say, a smaller p-value indicates a stronger evidence against $H_0$, and it is statistically obvious to draw such a conclusion. Therefore, the p-values of the Wilcoxon signed ranks test are shown in Table 2. The order of superiority of the four algorithms is as follows: MOPSO-Gene, MOPSO-Sigmoid, MOPSO-Round, and MOPSO-Penalty. This indicates that two velocity formula modification methodologies for integer variables are more effective than the others.

4.2. Numerical Study on MSRS Deployment Problem

In order to further substantiate the efficacy of the proposed algorithm in addressing the actual MSRS deploying problem within the non-connected deployment region, a series of simulation experiments was conducted, the results of which are presented below.

4.2.1. Simulation Model

For simplicity, we assume that the nodes of MSRS are deployed within a non-connected deployment region in this simulation. This region B is composed of two non-connected rectangular subregions each of size 100 km × 100 km. The treatment of deployment region in a special shape other than rectangular can be found in our previous work [20].

As shown in Figure 2, the surveillance region A is also defined as a rectangular area with size of 300 km × 300 km. In order to reduce the computational burden, the surveillance region A was divided into 900 square resolution cells of 10 km × 10 km resolution. The deployment region is comprised of two unconnected square deployable subregions. Hence, the specific MSRS deployment problem of this simulation can be expressed as:

$$\begin{array}{cc}\hfill & \begin{array}{cc}\hfill \mathrm{maximize}\mathbf{F}\left(\mathrm{\Theta }\right)& =\left\{f_1\left(\mathrm{\Theta }\right),f_2\left(\mathrm{\Theta }\right)\right\},\hfill \\ \hfill & =\left\{\mathrm{ECR}\left(\mathrm{\Theta }\right),\mathrm{minSNR}\left(\mathrm{\Theta }\right)\right\},\hfill \end{array}\hfill \\ \hfill & \mathrm{\Theta }={\left({\theta }_1,...,{\theta }_J\right)}^T\hfill \\ \hfill & ={\left(x_1,y_1,\dots ,x_J,y_J\right)}^T\hfill \\ \hfill & s.t.\left\{\begin{array}{c}{x}_j\in \left[0,100\right]\cup \left[200,300\right]\hfill \\ y_j\in \left[50,150\right]\hfill \end{array}\right.,j=1,\cdots ,J.\hfill \end{array}$$

(24)

4.2.2. Parameter Settings

Firstly, the parameters of the MSRS deployment problem are set in accordance with the actual designed performance as follows.

The detection probability threshold value of MSRS is set at $P_{dt}=0.8$ for each resolution cell, the detectability factor $D_0=12.5$ dB, and the constant false alarm rate $P_{fa}={10}^{-6}$.

For the typical target of MSRS with a radar cross section (RCS) of 2 m², the power range of each single node is set to $R_{max}=30$ km. To assess the resilience of the proposed algorithm to changes in problem size, four test cases were conducted, with the number of nodes, J, set to 4, 6, 8, and 10, respectively.

In regard to the parameters of the algorithms, the magnitude of the penalty factor in the MOPSO-Penalty is set to $A=-100$, which is sufficient to accommodate the maximization problem. The maximum number of iterations is set to $T_{max}=500$, which is limited by the calculation requirements of the practical application. The remaining parameters of algorithms are consistent with the settings given in Section 4.1 and are not separately stated.

In terms of parameters of performance metrics, the reference points of HV and $I_{ϵ}^{+}$ are (0,0) and (10,10), respectively.

4.2.3. Result Analysis

Similar to the experiment on MZDTs, each algorithm was run 100 times independently for each case. For the sake of brevity, MOPSO-Gene is abbreviated as “Gen.”, MOPSO-Sigmoid is abbreviated as “Sig.”, MOPSO-Round is abbreviated as “Rou.”, and MOPSO-Penalty is abbreviated as “Pen.”.

Firstly, we present the solutions obtained by the four algorithms. Due to the large number of solutions, we only plot the best and worst solutions obtained by each algorithm as shown in Figure 3. In the figure, the best solutions obtained by MOPSO-Gene are abbreviated as “Gen.-Bes.”, and the worst solutions obtained by it are abbreviated as “Gen.-Wor.”. The same abbreviation was applied to the other three groups. From this figure, the following phenomena can be observed:

(1) There is a trade-off between the ECR and the minSNR, which means that no solution can have the best of both performances.

(2) In the majority of cases, with the exception of the MSRS with four nodes, the red and blue curves are situated further to the upper left. Given that this is a maximization problem, the closer the curve is to the top left, the better the set of solutions. This evidence indicates that MOPSO-Gene and MOPSO-Sigmoid yield superior outcomes.

(3) As the MSRS scale increases, the performance of the solutions obtained by each algorithm also improves, although the improvement amplitude varies. In cases of a larger scale, it is evident that the black curve is at a disadvantage, as it is situated in the lower right of the figure. This evidence indicates that MOPSO-Penalty, as a classical algorithm, is deficient in its ability to address complex cases.

(4) In each case, the distance between the two black curves (i.e., Pen.-Bes. and Pen.-Wor.) is significantly larger than the other three. This demonstrates that the disparity in the quality of solutions yielded by MOPSO-Penalty is greater than that of the other three. Consequently, MOPSO-Penalty is deemed to be unreliable.

In terms of computational cost, the box plots of the computational time of the four algorithms for solving the MSRS deployment problem are shown in Figure 4. All computations are performed in an AMD Ryzen 9 3950X operating at 3.5 GHz and 32 GB of RAM operating at 3600 MHz. The figure shows that MOPSO-Penalty takes longer time to converge, while the other three, although slightly different, have roughly the same computational cost.

The observations presented in this paper allow for the preliminary qualitative conclusion that the two algorithms proposed have advantages. However, to provide a more comprehensive quantitative conclusion, we introduce performance metrics in multi-objective optimization and statistical methods. The corresponding performance metrics statistics for each case are presented below. In order to provide a comprehensive evaluation of the performance of each algorithm, the relationship between the average values of HV and $I_{ϵ}^{+}$ on each case and the number of iterations is presented in Figure 5. The performance metrics of the final solutions obtained by the four algorithms are presented in

Table 3. Performance metrics statistics of the final approximations on the MSRS deployment problem.

			MOPSO -Penalty	MOPSO -Round	MOPSO -Sigmoid	MOPSO -Gene
4 nodes	HV	Bes.	50.54	50.37	50.24	50.72
		Ave.	48.23	47.91	48.60	49.48
		Wor.	7.595	42.11	45.28	44.78
		Var.	59.19	4.869	1.147	0.7427
	Iϵ+	Bes.	6.053	6.068	6.004	5.966
		Ave.	6.306	6.259	6.167	6.080
		Wor.	10.29	6.853	6.495	6.546
		Var.	0.5777	4.733 × 10−2	1.123 × 10−2	7.333 × 10−3
6 nodes	HV	Bes.	84.64	84.85	84.97	85.15
		Ave.	78.49	82.49	83.01	83.69
		Wor.	57.64	76.86	81.28	81.92
		Var.	57.16	2.905	0.4514	0.3894
	Iϵ+	Bes.	2.694	2.670	2.665	2.650
		Ave.	3.296	2.906	2.856	2.792
		Wor.	5.351	3.462	3.027	2.968
		Var.	57.16	2.905	0.4514	0.3894
		Var.	0.5526	2.813 × 10−2	4.408 × 10−3	3.848 × 10−3
8 nodes	HV	Bes.	95.99	96.39	96.87	96.87
		Ave.	90.15	94.42	95.29	96.08
		Wor.	78.67	92.71	93.76	94.80
		Var.	18.23	0.4259	0.3010	0.1557
	Iϵ+	Bes.	1.640	1.593	1.554	1.545
		Ave.	2.201	1.793	1.703	1.634
		Wor.	3.326	1.961	1.852	1.759
		Var.	0.1748	4.001 × 10−2	2.957 × 10−2	1.557 × 10−2
10 nodes	HV	Bes.	100.8	102.0	102.6	103.0
		Ave.	95.75	101.0	101.6	102.4
		Wor.	91.41	100.1	100.6	101.2
		Var.	6.234	0.2132	0.1455	9.571 × 10−2
	Iϵ+	Bes.	1.105	1.030	1.021	1.013
		Ave.	1.698	1.202	1.131	1.093
		Wor.	2.116	1.296	1.231	1.197
		Var.	5.944 × 10−2	2.002 × 10−3	1.390 ×10−3	9.483 × 10−4

. The best values of each statistical indicator are marked in highlight, the second values are in bold and the worst values are in red. The statistic analysis results of the Wilcoxon signed ranks test of HV and $I_{ϵ}^{+}$ statistics on four cases are presented in

Table 4. The Results of Wilcoxon Signed Ranks Test on the MSRS deployment problem.

Null Hypothesis	p-Value		Statistical Conclusion
MOPSO-Gene	HV	0.2785	Accept
No better than
MOPSO-Sigmoid	Iϵ+	0.1576
MOPSO-Gene	HV	6.557 × 10−5	Reject
No better than
MOPSO-Round	Iϵ+	6.787 × 10−6
MOPSO-Gene	HV	7.431 × 10−5	Reject
No better than
MOPSO-Penalty	Iϵ+	3.922 × 10−6
MOPSO-Sigmoid	HV	1.419 × 10−2	Reject
No better than
MOPSO-Round	Iϵ+	1.803 × 10−2
MOPSO-Sigmoid	HV	9.575 × 10−3	Reject
No better than
MOPSO-Penalty	Iϵ+	9.649 × 10−3
MOPSO-Round	HV	3.922 × 10−2	Reject
No better than
MOPSO-Penalty	Iϵ+	1.712 × 10−3

.

In light of the aforementioned evidence, the following phenomena are observed:

(1) The comparative results on two performance metrics are essentially consistent, indicating that each algorithm exhibits consistent performance in terms of the two performance metrics across all test problems. Combined with the definition of these performance metrics, this phenomenon implies that each algorithm proposed in this paper is consistent in terms of convergence and uniformity.

(2) With regard to the efficiency of MSRS deployment, it can be observed that MOPSO-Penalty requires a greater number of iterations to converge than the other three algorithms. Meanwhile, there is no significant difference among other three algorithms. As shown in Figure 5, the black line, which represents MOPSO-Penalty, requires the greatest number of iterations to achieve convergence.

This phenomenon demonstrates that MOPSO-Penalty exhibits inferior convergence rates in comparison to the other three algorithms. Moreover, it can be concluded that MOPSO-Penalty, as a typical constraint-handling method, necessitates a greater computational complexity when attempting to resolve the MSRS deployment problem.

(3) In regard to the efficacy of the MSRS deployment, the relevant statistical indicators of the ultimate outcomes are delineated in Table 3. Table 3 has 32 rows, each of which represents a statistical indicator, and it has four columns, each representing an algorithm. For the MOPSO-Gene column, 30 are highlighted. This means that MOPSO-Gene obtains the best results of 93.75% (30 out of 32) statistical indicators on four cases. For MOPSO-Sigmoid, 22 of which are in bold or in highlight. This indicates that MOPSO-Sigmoid is a top-two algorithm in 96.875% (31 out of 32) of statistical indicators, outperforming other algorithms, besides MOPSO-Gene.

And as indicated in Table 4, the superiority of MOPSO-Gene over MOPSO-Sigmoid is not statistically significant at the 5% level. This suggests that there is no significant difference between the two modifications in terms of their effectiveness in solving the MSRS deployment problem.

With regard to MOPSO-Round and MOPSO-Penalty, MOPSO-Round exhibited smaller variances in HV and $I_{ϵ}^{+}$ and the average level is better than those data obtained by MOPSO-Penalty in Table 3. The results demonstrate that MOPSO-Round outperforms MOPSO-Penalty in addressing the MSRS deployment problem. And according to Table 4, this superiority is statistically significant under the significance level at 5%. This phenomenon indicates that the constraint handling method (i.e., MOPSO-Penalty) is inadequate in comparison to other algorithms when addressing the MSRS deployment problem.

(4) In the terms of robustness, MOPSO-Penalty exhibits a lack of performance, as evidenced by a decline in efficiency and effectiveness as the system scale increases. In the larger scale case (MSRS with 8 or 10 nodes), MOPSO-Penalty is unable to complete convergence within the given computational cost.

In conclusion, the algorithms based on the multiply velocity formula method, (i.e., MOPSO-Gene and MOPSO-Sigmoid) have been demonstrated to have a statistically significant advantage in terms of efficiency and effectiveness.

In contrast, the algorithm based on the constraint handling method (MOPSO-Penalty) has been found to be unsatisfactory when solving the MSRS deployment problem, particularly when the scale of MSRS is large.

5. Conclusions

We devoted this paper to deploying MSRS within a non-connected deployment region utilising MOPSO. To eliminate the necessity for additional constraints, this MSRS deployment problem was reformulated into a MOMIP by dividing the solution space and introducing integer variables. Moreover, two MSRS deployment algorithms, MOPSO-Sigmoid and MOPSO-Gene, are proposed, respectively, based on two altering velocity formulas for integer variables. These formulas are based on the sigmoid function and the genetic operation. A numerical study has demonstrated that the proposed MSRS deployment algorithms exhibit a statistically significant advantage in effectiveness with the same computational cost.