WU Gaofeng,WAN Kaifang,GAO Xiaoguang, and FU Xiaowei

School of Electronics and Information,Northwestern Polytechnical University,Xi’an 710129,China

Abstract: The network performance and the unmanned aerial vehicle (UAV) number are important objectives when UAVs are placed as communication relays to enhance the multi-agent information exchange. The problem is a non-deterministic polynomial hard (NP-hard) multi-objective optimization problem, instead of generating a Pareto solution, this work focuses on considering both objectives at the same level so as to achieve a balanced solution between them. Based on the property that agents connected to the same UAV are a cluster, two clustering-based algorithms,M-K-means (MKM) and modified fast search and find density of peaks (MFSFDP) methods, are first proposed. Since the former algorithm requires too much computational time and the latter one requires too many relays, an algorithm for the balanced network performance and relay number (BPN) is proposed by discretizing the area to avoid missing the optimal relay positions and defining a new local density function to reflect the network performance metric. Simulation results demonstrate that the proposed algorithms are feasible and effective. Comparisons between these algorithms show that the BPN algorithm uses fewer relay UAVs than the MFSFDP and classic set-covering based algorithm, and its computational time is far less than the MKM algorithm.

Keywords:unmanned aerial vehicle(UAV),relay,communication,clustering,relay node placement,wireless network.

1.Introduction

Cooperation of multiple agents is popularly applied in both civilization and military missions, which turns to be the multi-agent system (MAS), and has significant meaning.These applications are extremely varied and include missions such as search and rescue [1], environment sensing and monitoring [2], surveillance and reconnaissance[3,4],wildland firefighting[5],“l(fā)ast tactical mile”connection to and among mobile forces [6], and other scientific research. In the MAS, cooperation is realized through the information exchange and further affects mission efficiency of the system.Wireless communications is one of the two most widely chosen choices, and especially suitable for on-demand requirements. However, in the radio frequency(RF)environment,the channel quality decreases quickly because of increasing distance[7,8],and obstructions caused by building and terrains.

Addressing these,using extral nodes as communication relays gains more and more attention and is applied to retransmit signals among the agents.As the network performance is co-related to the positions of the relays and agentrelay associations, the relay node placement(RNP) problem should be studied.

Objectives in researches of the RNP problem can be classified into two different classes: minimize the relay number and optimize the network performance. The former intends to match the network connectivity [9–11],fault-tolerant[12],lifetime [13,14],delay[15–18], capacity[19,20],network coverage[21,22],and quality of service(QoS)[17,23,24]with the minimum relay UAV,while the latter concentrates on improving the aforementioned metrics with the limited[25,26]or un-limited[27,28]number of relays.

In realistic applications,both of them are important because the network performance is relevant to the mission efficiency and the resource of UAV is usually precious and scarce, which means both two metrics should be better considered at the same level and giving out the balanced solution for this problem is quite important. However, it is quite difficult because the two metrics are coupled and non-comparable[29].

Perez et al. [30] tried to find an appropriate solution by adding one or several relay nodes to the Pareto solution with the minimum number of relays so that the energy consumption of the network would be greatly reduced.Apparently,the two metrics are still not at the same level, and the proposed algorithm could only be applied to the single-tiered network. Gu′erin [31] studied to give out optimal routing paths between the given source node and any destination node by using any desired number of relays, whose computational complexity was reduced by Burdakov[29,32]by using the limited relay number.However, the network in both works only includes two nodes,which shows to be RNP for the end-to-end communication.To our best knowledge,no study has simultaneously managed the network performance and relay number metrics at the same level for multi-agent systems(more than two agents). Such an RNP problem naturally turns to be the multi-objective RNP(MORNP)problem.

This work attempts to use unmanned aerial vehicles(UAVs) as communication relays to solve the MORNP problem. (i) The UAV is an airborne platform, and the ground-to-air and air-to-air channels are easier to provide the line of sight communication than the ground-toground channel, further improving the quality of wireless channels, such as better signal strength, capacity and reliability [33,34]. (ii) The UAV can be deployed easier than ground platforms and human vehicles, especially in dirty scenarios,and obtain higher survivability and adaptability [34,35]. The placement is two-tiered because it is more reliable and scalable than the single-tiered placement[18,36].

The main concentrations and contributions of this work are listed as follows. (i) Build up the mathematic model of the MORNP problem in the MAS.(ii)It is more meaningful to generate solutions with the balanced network performance and relay UAV number instead of systematically proving Pareto solutions for the MORNP problems. (iii)Two clustering based methods modified from the data mining region are proposed firstly,and then an approach ameliorated from the former is proposed, where a discretization progress is executed to avoid missing the optimal relay position, a state-of-art defined function is given for showing the influence of network performance metric on the local density function,and an iteration progress could eventually give out the required MORNP solution. Since the RNP problem concentrates on studying the relay node placement strategy for the enhanced communication in the system,the achievement of the MORNP problem can also be extended to other types of system matching such scenario.

The remainder of this paper is organized as follows.Section 2 reviews the related works. Section 3 gives out the system models and formulates the MORNP problem as an optimization problem.Section 4 discusses the problem and gives preliminaries for solving it. Section 5 discusses the proposed clustering based algorithms for solving the MORNP problem, and their performance and computational complexity difficulties are discussed. Section 6 tests the proposed algorithm,as well as their performance comparisions and analizations. Section 7 summarizes this paper with conclusions.

2.Related works

In this section, we review the related works. Throughout,most methods use graph-theory based methods. Cheng et al. [37] formulated the optimization problem as a Steiner minimum tree with the minimum number of Steiner points(SMT-MSP),and proposed a two-phase algorithm, where a minimum-cost spanning tree was formed in the first phase, and the transmission power of each node was reduced on the second phase. In [37–39], the problem of deploying a minimum number of relay nodes in wireless sensor networks(WSN)was formulated as the SMT-MSP and bounded edge length problem(SMT-MSPBEL),which proved that it was non-deterministic polynomial hard(NP-hard) and a simple minimum spanning tree (MST) based five-approximation algorithm was presented. Ma et al.[15] proposed a polynomial time subtree-and-mergencebased algorithm to solve the delay constrained relay node placement (DCRNP) problem, which was also studied in[16,17], and presented a shortest path tree based iterative relay pruning (SPTiRP) algorithm. The set theory based method is also widely used.Ma et al.[18]proposed a twophase set-covering-based algorithm (TSCA) to approximately solve the DCRNP problem. Tang et al. [36] used the idea of covering each sensor node by multiple relay nodes to solve the connected/2-connected relay node single/double cover problem by using the minimum number of relays.Some other researches jointly take advantage of methods from the graph-theory and the set theory to solve the RNP problems[40,41].Channel models in these works are usually oversimplified which linearly depends on the distance between the transmitter and the receiver,and the approximation algorithms may use several times of the optimal relay number.These methods may be efficient in the WSN area,but can be hardly applied to the UAV-relay mission,because(i)the UAV is much more valuable and rarer than wireless sensors, using the minimum number of relay UAV as possible is quite important in RNP missions;(ii)realistic channel performance metric models should be used since the operational distance is much farther than wireless sensors.

Misra et al.[14]formulated the constrained RNP problem as a mixed integer nonlinear programming(MINLP)problem to generate the low bound of the optimal solution.Burdakov et al. [29] did the similar formulation in relay placement for end-to-end communication,and an all-hopoptimal-placement was proposed to generate all optimal Pareto solutions for any restricted number of relays.Nigam and Agarwal[42]formulated the DCPNP problem as a linear programming problem, and proposed a branch-andcut algorithm. Azharuddin et al. [43] also formulated the RNP problem as a liner programming problem and proposed an algorithm based on the genetic algorithm. Hou et al. [44] proposed a two-phase procedure to solve the MINLP problem, where a heuristic was proposed for the optimized placement of relay nodes in the first phase,and the energy budget was allocated to the combined aggregation and forward node(AFN) and relay node(RN) in the second phase.However,these methods only consider one objective,while in this work,the RNP with multi-objective of relay UAV number and network performance are synthetically considered.

This work formulates placing UAV as relay supporting MAS communication as a multi-objective MINLP(MOMINLP) optimization problem, and clustering based methods are proposed to solve the problem and their performance is evaluated.

3.System model and problem formulation

3.1 Network model

Consider there areNagentsui ∈U={u1,...,uN}executing missions in the MAS, and the operation region isD.The communication performance of each agent is limited. A set ofM(N) UAVsri ∈R={r1,...,rM}with higher communication performance are available to be deployed to build a backbone relay network so that the communication performance of the MAS can be improved.The operation altitudes of the agents and relays arehuandhr, respectively. The two-tiered network is shown in Fig.1,where each agent only connects to the UAV.

Fig.1 Two-tiered network model

The primary goal of the RNP is to give out the location of relays and relay-agent assocations so as to optimize the network performance. It should figure out that the placement results can only affect the channels between agents and their associated relays, while channels with only agents cannot be affected.Thus during the placement work, only the performance of channels including the relay UAV needs to be considered,that is, the channel from the agent to its relay,named uplink channel,ui →rj;the channel from the relay to its agents,named downlink channel,rj →uk;the channel from one relay UAV to another relay UAV,rj1→rj2.Based on this property,the network performance metric can be built as follows.

3.2 Network performance metric

Received signal strength (RSS) at the receiver is one of the primary aspects that affect the performance of wireless channels,such as connectivity and capacity,in RF environment[7,8].As aforementioned,the transmit power of the agent is usually smaller than the transmit power of the realy UAV, then the qualities of wireless links are normally limited by the uplink channels. Then this work makes an assumption that qualities of both channel,rj1→rj2andrj →ukare both non-bottleneck in application,and only use the uplink RSS of channelsui →rjas the metric of network performancef[45]:

whereSiis the RSS from agentuiat the receiver antenna of its connected relay, which could be estimated by using the following simplified model[46]:

wherediis the Euclidean distance between the transmitting agentuiand its relay,didF(dFis the Fraunhofer distance[47]),γiis a constant gain reflecting the comprehensive property of the transmit power, the channel gain and other fading effects,αis a path-loss exponent,which normally varies between 2 and 6.

Letdenote the three dimensional Cartesian coordinates of agentui. Letdenote the three dimensional Cartesian coordinates of relay UAVrj. Letrirepresent the connected relay UAV of agentuiwith positionpr(i)=(xr(i),yr(i),hr(i)).Thendican be calculated as

3.3 MORNP problem

Given the set ofUat positionsand the set of availableR,the primary work of solving the RNP problem is giving out the desired relay setR,which can be denoted astheir placement positionand the agent-relay association matrixX= [xij]N×m, wherexijrepresents the connection state between each agent and relay UAV and is defined as follows:

The goal of this work is finding an RNP solution where both the relay UAV number and the network performance are considered at the same level. Let the former be denoted as f1(g) and the latter be denoted as f2(g), and letthen

Then this work formulates the MORNP problem as follows:

subject to

These constrints urge that each agent should be only allocated to one relay UAV and each UAV should be allocated with at least one agent so that no UAV is idle.

4.Problem analysis and preliminaries

The MORNP problem given in (7)–(10) could be commonly applied to both two-way and one-way communication modes,since normally both of them are bottlenecked by the uplink channel and the RSS metric is independent to the communication mode.The problem is multi-objective.Traditionally,the motivation of solving such problems is to find out the Pareto set,which contains solutions that cannot be optimized of one objective without negatively affecting the other objectives.After getting the Pareto set, decision makers still should choose one solution from the set so as to achieve a tradeoff between the objectives[30].

However,a Pareto solution for the problem in(7)–(10)may not worth much or even cannot meet application requirements. Before giving out the reasons, the following properties in Lemma 1 and Proportion 1 should be given first.

This lemma demonstrates that the network performance could be easily improved by using more relays,only if the relay number is no more than the agent number.

This proportion demonstrates that Pareto is the optimal solution with the given relay UAVs number and the correlated placement position and association.

Lemma 1 and Proportion 1 show that the MORNP problem includes N Pareto solution,thus the solution may contain too many relay UAVs or turn out too low network performance.As a result, it is more meaningful to find a tradeoff solution where both the relay UAV number and the network performance metrices are balanced.

Another important fact is that the complexity for solving this problem is NP-hard as it is a MOMINLP optimization problem, where MINLP is proved NP-hard [48]. In time sensitive applications,generating an acceptable solution for the decision makers is quite important.Thus,low computational complexity should be looked for.

In a word, this work attempts to find a tradeoff solution,which occupies the balanced relay UAV number and network performance,with acceptable computational complexity so as to meet on-demand requirements.

The two-tiered network is a cluster-based network in essence,where each relay acts as cluster head in the corresponding cluster[49].Agents belonging to the same relay act as a “cluster”,whereas the “head/center”of the cluster is the optimal placement position of the relays.This work concentrates on solving the MORNP problem by clustering the agents into several clusters and finds centers for each cluster as the operation position for the relay UAVs.

5.Clustering based algorithms

Before discussing the clustering based algorithms,preliminaries should be prepared.Solutions for RNP problems in-clude two aspects,optimal relay positions and channel associations,where optimizing channel association with the known relay position could be solved with Lemma 2,similarly, seeking the optimal relay positions with the known channel association could be solved with Lemma 3.

Proof According to(1)and(2),if all Si,i=1,...,m,are maximized,then f2(g)is definitely minimized or optimized in other words.

where u(j)represents agents connected to the same relay rj,|u(j)|is its size,and uk(j)is its kth agent.

Proof Let(1)be as follows first:

5.1 K-means strategy based MORNP algorithm

K-means clustering[50,51]is a classic algorithm to group a set of data(agents in this work)into K clusters according to their proximity[34],and it is distance-based.The algorithm starts from generating an initial set of cluster centers, which could be randomly chosen from the data set or purposely chosen with methods such as roulette. Then an iteration progress, which consists of two procedures,is carried out until no changes happen to the cluster centers and channel association matrix,meaning the algorithm converges: cluster center update using existed channel association matrix, re-association of agent to clusters using obtained cluster centers.

However, this classical K-means clustering algorithm can only deal with the specified number of cluster centers,which is embarrassedly set according to experience.In this work, the available UAV number is M, which means the cluster center numbers vary from 1 to M.In many realistic applications with UAVs as communication relays, it is hardly to know the appropriate cluster center number because of the complicated and different environments,agent number, and operation altitude. As a result, the classical K-means algorithm is iterated for M times so that M solutions for the MORNP problem can be generated for the decision maker to choose,which turns to be the M-K-means(MKM)algorithm.

Algorithm 1 gives out the pseudo-code of the MKM algorithm,where a roulette method based on selection possibility is applied to produce initial clusters centers to avoid the local optimal.

Algorithm 1 Pseudo-code of MKM algorithm

Step 1 Input:PU,M

Step 2 Output:G={g(1),...,g(M)}

Step 3 For m=1,...,M

Step 4 For i=1,...,m

Step 6 Calculate the minimum distancesk =1,...,N between

Step 7 Calculate the selection possibility(drop U here)as the cluster center;

Step 8 According to bj,select one cluster center from PUPr,0using the roulette method;

Step 9 End for

Step 10 Calculate matrix X using(11);

Step 11 Update the optimal cluster centers by solving(12);

Step 12 Repeat Step 10 and Step 11 until X andconverge(no change).

Step 14 End for

Step 12 is an iteration progress of Step 10 and Step 11,which is the same as the classic K-means algorithm,whose convergence is proved [52]. When the output of Algorithm 1 is obtained,the decision-maker should choose one from the M results.

Lemma 4 The computational complexity of Algorithm 1 is O(N2M2).

Proof The complexity from Step 4 to Step 9 is O(N2×m). The complexity of Step 10 is O(2N × m). Step 11 includes m times center update, each update procedure solves an non-linear programming(NLP)problem,whose complexity with the approximate algorithms, such as simultaneous perturbation stochastic approximation(SPSA)algorithm[53],is O(K1×N2×m),where K1represents the iteration of SPSA.Let Algorithm 1 include I1times iteration of Step 10 and Step 11.The total complexity of Al-gorithm 2 isO(I1K1N2M2),whereI1is the iteration times of Step 10 and Step 11. Generally,I1andK1are constant, thus the computational complexity of Algorithm 1 isO(N2m2).

5.2 Fast search and find density of peaks(FSFDP)strategy based MORNP algorithm

In the former section, the MKM algorithm is centroidbased. In this section, a non-centroid based clustering algorithm is discussed, among which clustering by FSFDP[54] is widely used. The algorithm is proposed based on the concept that the local density of cluster centers is normally higher than their surrounded neighbors and the distance between cluster centers and those with higher density should be large enough.Apparently,the two mentioned parameter,namely local density and distance should be given first.

Letρidenote the local density of each point

whereχ(x) = 1,ifx <0 andχ(x) = 0,otherwise,dijis the distance betweenuianduj,anddcis a cut off distance,which can be chosen according to the experienced threshold of the communication distance in this application.

Letδirepresent the distance between each pair of agent positions,then it can be measured by computing the minimum distance betweenand other positions within higher local density.

In this work, letηbe a heuristic function and estimate the potential advantange of the position of each agent as a cluster center

Then based on the identified cluster centers,the left noncenteral agents are assigned.The method is tabbing each of them as the same cluster as its nearest neighbor with higher local density.

Algorithm 2 gives out the pseudo-code of the FSFDP strategy based algorithm, namely MFSFDP, wherebidenotes the neighbor ofuithat has higher local density and the nearest distance.

Algorithm 2 Pseudo-code of MFSFDP algorithm

Step 1 Input:PU,M,dc

Step 3 Calculate the distancedij;

Step 4 Calculateρi;

Step 5 Descend sortρi,and letqiremember their subscript;

Step 6δq1=max(dij),and let

Step 7 Fori=2,3,...,N

Step 8δqi=δq1

Step 9 Forj=1,2,...,i ?1

Step 11

Step 12bqi=qj;

Step 13 End if

Step 14 End for

Step 15 End for

Step 16 Choosem(mM)cluster centers,namelyaccording toηi=ρi×δiand add them togi ∈G,

Step 17 Fori=1,2,...,N

Step 19 Add it to the same cluster as

Step 20 End if

Step 21 End for

Lemma 5 The computational complexity of Algorithm 2 isO(N2).

Proof Step 3 includesN2/2 times computation,thus its computational complexity isO(N2/2). Step 4 checks all distances with complexityO(N2/2). Step 5 is a sorting operation with complexityO(NlogN). Step 6 is a maximum operation with complexity +O(N). Steps 7–16 include two loops, the computational complexity isO(N2), similarly the computational complexity of Steps 17–21 isO(N). Therefore, the computation complexity of Algorithm 2 isO(N2).

According to Lemma 5, this clustering algorithm requires only one-off process, and the computational complexity of Algorithm 2 is much lower than that of Algorithm 1(O(N2M2)).

5.3 Balanced network performance and relay number algorithm

In the MKM algorithm,iterations of the relay number from 1 toMis progressed, which costs too much time. The MFSFDP algorithm solves this problem and it only requires one step search. However, the MFSFDP algorithm assigns the agents to the same cluster center as its closest neighbor with high local density, which is actually based on the position similarity of agents,the same as the motivation of data mining.Instead,the ultimate target of RNP in realistic applications is to find cluster centers as relay positions so that the network performance is optimized.As a result, these methods could be improved to meet the specified requirement of the MORNP problem,thus an algorithm with the balanced network performance and relay number(BPN)is discussed in this section.

This work intends to find a tradeoff solution for the MORNP problem with the balanced network performance and relay UAV number in limited computational time.Considering the superiorities of the MKM and MFSFDP algorithms,the former could find a better channel association,the latter could give cluster center numbers in one step so that the iteration of relay number from 1 toMis not required.The overall thinking of the BPN algorithm is using the concept of local density to find the appropriate cluster center number,and taking advantage of the K-means cluster center update progress to optimize the former achieved cluster center positions and channel association matrix.

(i)Relay number and initial position generation

Clustering based on similarity may cost extra relays because agents connected to one relay may be assigned to several clusters.As Fig.2 shows,the dot points are agents,which could be well served by the relay locating at the redtriangle position, while according to the classical clustering concept, they will be allocated to three clusters. This is because the MFSFDP algorithm only checks the local density of agent positions, while the red-triangle position is dismissed.Thus,the first improvement of the BPN is applying a spatial discretization progress,so that positions as the red-triangle position are considered.Let the discretized points be denoted asV={v1,...,vQ}with positions

Fig.2 RNP using extra relays by clustering based on similarity

Another improvement is motivated by the fact that the local density function defined in (15) simply counts the agents within distancedc, which cannot reflect the relationship that RSS exponentially decreases with linearly increasing the transmitter and receiver distance. Thus this work proposes a brand new local density function by taking this property into consideration,and gives it as follows:wheredcis the threshold distance between agents and the relay located atvithat can be well served, it is normally obtained according to experience.

The proposed local density function shows two benefits:firstly, the local density does not increase as the distance increases,and is affected by the path loss exponentsαand channel gainγ;secondly,agents that can be well served by a relay, namely their distance is less thandc, are equally counted with 1.Otherwise,it will decrease as the distance increases,since in realistic application,agents may not be well-served, but can still be served by the relay with the degraded performance.

(ii)Relay position and channel association update

The MFSFDP algorithm assigns data to clusters based on their similarity,Fig.3 shows a case where these points are clustered to three clusters, and each shows as a curve[54]. This is correct in most cases in data mining. However, realistic relay missions are different from data mining, where the RSS decreases exponentially with increasing the distance linearly. As a result, clustering in RNP must be distance based and centroid.Then the spheroidal distribution points in Fig.3 should be clustered as different colors show in the RNP problem.Thus this work updates the initial obtained cluster centers and the agent-relay association matrix is similar to the K-means algorithm.Since the initial cluster centers in the BPN ensure that they are much farther and own higher local density than the other potential placement positions,they are usually closer to the optimal placement position,and then the iteration times in the BPN decrease.

Fig.3 Difference between clustering based on similarity and realistic RNP problem

Algorithm 3 gives the pseudo-code of the BPN algorithm.

Algorithm 3 Pseudo-code of the BPN algorithm

Step 1 Input:PU,M,dc,dT

Step 3 Area discretization and calculateV;

Step 4 Calculate the distancedijbetweenviandvj;

Step 5 Calculateρi(i=1,...,Q)at

Step 6 Descend sortρi,and letqiremember their subscript;

Step 7δq1=max(dij);

Step 8 Fori=2,3,...,Q

Step 9δqi=δq1;

Step 10 Forj=1,2,...,i ?1

Step 12

Step 13 End if

Step 14 End for

Step 15 End for

Step 16 Choosempositions as cluster centers{r1,...,rm}according toηi=ρi ×δiand add them togi ∈G,

Step 17 Repeat the following two steps untilXconverges:

Step 18xij= 1?rj= arg minj=r(i)=1,...,m d(vi,rj),i=1,...,Q;

Step 19 Update

Step 20

Lemma 6 The computational complexity of Algorithm 3 isO(Q2+QN+I2(2mN+mK2N2)).

Proof Step 4 includesQ2/2 times computation, thus its computational complexity isO(Q2/2).Step 5 requires to check each distance, thus the computational complexity is alsoO(QN/2). Step 6 is a sorting operation with complexityO(QlogQ). Step 7 is a maximum operation with complexityO(Q2/2).Steps 8–15 include two loops,the computational complexity isO(Q2). Step 16 includes a sorting operation,its complexity isO(QlogQ).Similar to Algorithm 1,the computational complexity of Steps 17–19 isO(I2(2Nm+mK2N2)).Therefore,the computation complexity of Algorithm 3 isO(Q2+QN+I2(2mN+mK2N2)).

Compared to the computation complexity of Algorithm 1, ifQ < NM, then the computation complexity of Algorithm 3 is lower. Otherwise, the computational complexity of Algorithm 4 is higher.As a result,in realistic applications, the discretization size should be appropriately chosen to make the computational time of the BPN meet application requirement.

6.Experiments and results

In this section, the proposed clustering based algorithms and their performance comparisons are tested and demonstrated.The operation area of the agents is a set square with 10 km×10 km in length and width.The positions of the agents are assumed prior known to the decision makers.The loitering altitude of the relay UAVs is 500 m. Channel parameters are set as follows:α= 1,γ= 2.5, anddF=50.

6.1 Effectiveness and feasibility validation

Fifty agents are randomly deployed in the operation area in this simulation.Firstly,the MFSFDP algorithm is applied,whose result is shown in Fig.4.The square points denote the desired relay UAV placement positons,the circle points with the same color as the square points mean they belong to the same cluster.Apparently,three relays are placed and the network performance is 3.458 5×1010.

Fig.4 Placement result using MFSFDP algorithm

For comparison with the MFSFDP algorithm, three relays are limited in the MKM algorithm as shown in Fig. 5. The obtained network performance is 1.522 1×1010. According to the position of relay UAVs and distribution of clusters, the result is more reasonable, which is also indicated by the network performance matrix.

Fig.5 Placement result using MKM algorithm

As aforementioned,the MKM algorithm needs to estimate the objective function by varying the number of relay UAVs from 1 toM,so that the balanced relay number and network performance could be achieved.LetM=10,and the result in Fig. 6 validates Lemma 1, that is using more relay UAVs could form a network with a better performance.

Fig.6 Network performance using MKM algorithm

The effectiveness and feasibility of the BPN algorithm are also tested, wheredc= 500 m and the result is shown in Fig.7,where the achieved network performance is 1.797 9×1010, similar to the MKM algorithm. This proves the effectiveness and feasibility of the BPN algorithm,while the BPN algorithm only needs two iterations,compared to the four iterations required by the MKM algorithm.

Fig.7 Placement result using BPN algorithm

To test the idea that the BPN algorithm can avoid using more relays where multiple agents could be well served by one relay,40 agents are deployed in the operation area,whose positions are shown in Fig.8(a).Assume that if the agent is no further than 2 000 m to its associated relay,then the RSS at the relay is well enough.As a result,dcin the BPN algorithm is set as 2 000 m.Figs.8(b)–(d)show the placement result by using the proposed three algorithms,where the square points denote the correlated optimal relay position, the circle points with the same color mean they belong to the same cluster.Apparently,the result of using the BPN algorithm uses fewer relay UAVs than MKM and MFSFDP algorithms,which reduces the platform cost and validates the feasibility of the BPN algorithm.

Fig.8 Required relay number using different BPN algorithms

6.2 Performance comparison and analysis

In this part,Monte-Carlo simulation is executed to the detail test and compare the performance of the proposed algorithms, where 10 UAVs are available to be deployed as communication relays, the agent number varies from 20 to 100. The cutoff distance of MFSFDP and BPN are 2 000 m. The length of the discretizational square grid edges in the BPN algorithm is 500 m.

Fig. 9 shows the comparison of the network performance of using different algorithms. It should be figured out that a lower value iny-axis means a better network performance because of(1).

Fig.9 Comparions of network performance

According to Fig. 9, it is easy to figure out that using three to four relays achieves the appropriate balance between the network performance and the relay UAV number. The network performance improves little with more relay UAVs,while it is over degraded with only one to two relay UAVs.

Although both MFSFDP and BPN algorithms generate the similar network performance as shown in Fig. 9,Fig.10 shows that the MFSFDP algorithm uses much more relay UAVs.

Fig. 10 Comparison of deployed relay UAV numbers using MFSFDP and BPN algorithms

Fig.11 shows the computational time by using the proposed algorithms.Fig.11 indicates that the MFSFDP algorithm costs extremely low computational time, the MKM algorithm costs the highest computational time, the BPN algorithm costs a little more computational time than the former and much less computational time than the latter.It is because the MFSFDP algorithm requires no iteration, the MKM algorithm requires iterations in both two phases, while the BPN algorithm only requires the iteration in realy-UAV association phase and it converges faster than the MKM algorithm.

Fig.11 Comparison of average computational time

From Fig. 9 to Fig. 11, we can conclude that the BPN algorithm deployes much fewer relay UAVs than the MFSFDP algorithm, together with much less computational time than MKM. The compuatational time of the BPN is near optimal and acceptable, while it requires no prior set of cluster number.

Since the set-covering based algorithm (SCA) [39] is classic in solving two-tiered relay node problems,another simulation is carried out to make a comparison between the BPN and the SCA.In this simulation,the communication distance with the SCA is limited to 1 000 m,2 000 m,and 3 000 m, respectively.Simulation results are showed in Fig.12.

Fig.12 Comparison of deployed relay UAV numbers using BPN and SCA algorithm

Fig.12 shows that when the communication distance between the UAV and agents increases, the number of the used relay UAVs is reduced when using the SCA algorithm. However, it still uses much more relays than the BPN algorithm, it is because the approximation ratio of the SCA algorithm is proved more than 1. As aforementioned, the UAV resource is usually precision in realistic applications.

7.Conclusions

This paper studies the multi-objective relay UAV placement problem by jointly considering the achieved network performance and the deployed relay UAV number. Clustering based algorithms are used since agents connected to the same relay UAV can be treated as a cluster.Simulation results show that the proposed clustering based algorithm could efficiently solve the MORNP problems. The proposed BPN algorithm generates the best balance between these two metrics compared to the MKM and MFSFDP algorithms, where the BPN costs much less computational time than the former,and fewer UAVs than the latter.The network performance and the relay UAV number of the BPN algorithm are both near optimal, and the computational time is acceptable. Comparion between the classic SCA algorithm also demonstrates that the BPN algorithm uses fewer relay UAVs.

The clustering based algorithms are proposed to solve the MORNP problem and discussed in detail in this work,there are still aspects that can be improved, such as the find clustering based algorithm for solving the MRONP problem with obstacles, non-placement zones, which is a constrained multi-objective relay UAV placement problem(CMORUP),and future work is required.