#  SCIENCE CHINA Information Sciences, Volume 64 , Issue 4 : 140306(2021) https://doi.org/10.1007/s11432-020-3013-1

## A large-scale clustering and 3D trajectory optimization approach for UAV swarms • AcceptedJul 27, 2020
• PublishedMar 5, 2021
Share
Rating

### Abstract ### Acknowledgment

This work was supported in part by National Natural Science Foundation of China (Grant No. 61871211), Natural Science Foundation of Jiangsu Province Youth Project (Grant No. BK20180329), Innovation and Entrepreneurship of Jiangsu Province High-level Talent Program, Summit of the Six Top Talents Program of Jiangsu Province.

### Supplement

Appendix

Proof of Lemma 4.2

The proof of Lemma 1 is quite similar to that of Proposition 1 in . Let $f(z)=\log_2(1+\frac{c}{z})$ with $c=\frac{P_i\gamma_0}{\alpha_i[n]}>0$. It is not difficult to verify that $f(z)$ is a convex function with $z\geq~0$. Then, $f(z)$ can be globally lower-bounded by its first-order Tayler expansion at any point $z_0$ 1). That is, we have \begin{equation}f(z)\geq f(z_0)+f'(z_0)(z-z_0), \forall z, \tag{31}\end{equation} where $$f'(z_0)=\frac{-c\log_2e} {z_0(z_0+c)}.$$ Consequently, letting $z=\max(\|{\boldsymbol~q}[n]-{\boldsymbol~s}_i\|^2,d_{\min}^2)$ and $z_0=\max(\|{\boldsymbol~q}^l[n]-{\boldsymbol~s}_i\|^2,d_{\min}^2)$, it completes the proof.

Boyd S, Vandenberghe L. Convex Optimization. Cambridge: Cambridge University Press, 2004.

Proof of Lemma 4.3

Recalling the expression of $\hat{R}_i[n]$ in 23, only the term $-\phi^l_i[n]z_i[n]$ involves ${\boldsymbol~q}[n]$. We can easily obtain the convexity of $z_i[n]=\max(\|{\boldsymbol~q}[n]-{\boldsymbol~s}_i\|^2,d_{\min}^2)$ as the maximum of convex function $\|{\boldsymbol~q}[n]-{\boldsymbol~s}_i\|^2$ and a constant $d_{\min}^2$. Combined with $-\phi^l_i[n]<0$, it immediately yields the concavity of $-\phi^l_i[n]z_i[n]$ as well as $\hat{R}_i[n]$.

### References

 Boccardi F, Heath R W, Lozano A. Five disruptive technology directions for 5G. IEEE Commun Mag, 2014, 52: 74-80 CrossRef Google Scholar

 Zhou H, Wu Y, Hu Y. A novel stable selection and reliable transmission protocol for clustered heterogeneous wireless sensor networks. Comput Commun, 2010, 33: 1843-1849 CrossRef Google Scholar

 Ma T, Qian B, Niu D. A Gradient-Based Method for Robust Sensor Selection in Hypothesis Testing. Sensors, 2020, 20: 697 CrossRef Google Scholar

 Shi W, Zhou H, Li J. Drone Assisted Vehicular Networks: Architecture, Challenges and Opportunities. IEEE Network, 2018, 32: 130-137 CrossRef Google Scholar

 Cheng N, Xu W, Shi W. Air-Ground Integrated Mobile Edge Networks: Architecture, Challenges, and Opportunities. IEEE Commun Mag, 2018, 56: 26-32 CrossRef Google Scholar

 Shi W, Li J, Xu W. Multiple Drone-Cell Deployment Analyses and Optimization in Drone Assisted Radio Access Networks. IEEE Access, 2018, 6: 12518-12529 CrossRef Google Scholar

 Zhang S, Zhang H, Di B. Cellular UAV-to-X Communications: Design and Optimization for Multi-UAV Networks. IEEE Trans Wireless Commun, 2019, 18: 1346-1359 CrossRef Google Scholar

 Tuna G, Nefzi B, Conte G. Unmanned aerial vehicle-aided communications system for disaster recovery. J Network Comput Appl, 2014, 41: 27-36 CrossRef Google Scholar

 Zeng Y, Wu Q, Zhang R. Accessing From the Sky: A Tutorial on UAV Communications for 5G and Beyond. Proc IEEE, 2019, 107: 2327-2375 CrossRef Google Scholar

 Matolak D W, Ruoyu Sun D W. Unmanned Aircraft Systems: Air-Ground Channel Characterization for Future Applications. IEEE Veh Technol Mag, 2015, 10: 79-85 CrossRef Google Scholar

 Khawaja W, Guvenc I, Matolak D W. A Survey of Air-to-Ground Propagation Channel Modeling for Unmanned Aerial Vehicles. IEEE Commun Surv Tutorials, 2019, 21: 2361-2391 CrossRef Google Scholar

 Shi W, Li J, Cheng N. Multi-Drone 3-D Trajectory Planning and Scheduling in Drone-Assisted Radio Access Networks. IEEE Trans Veh Technol, 2019, 68: 8145-8158 CrossRef Google Scholar

 Zhao N, Lu W, Sheng M. UAV-Assisted Emergency Networks in Disasters. IEEE Wireless Commun, 2019, 26: 45-51 CrossRef Google Scholar

 Hayat S, Yanmaz E, Muzaffar R. Survey on Unmanned Aerial Vehicle Networks for Civil Applications: A Communications Viewpoint. IEEE Commun Surv Tutorials, 2016, 18: 2624-2661 CrossRef Google Scholar

 Bujari A, Palazzi C E, Ronzani D. FANET application scenarios and mobility models. In: Proceedings of the 3rd Workshop on Micro Aerial Vehicle Networks, Systems, and Applications, NewYork, 2017. 43--46. Google Scholar

 Park J H, Choi S-C, Hussen H R, et al. Analysis of dynamic cluster head selection for mission-oriented flying ad hoc network. In: Proceedings of the 9th International Conference on Ubiquitous and Future Networks (ICUFN), Milan, 2017. 21--23. Google Scholar

 Du J M, You Q D, Zhang Q, et al. A weighted clustering algorithm based on node stability for Ad Hoc networks. In: Proceedings of the 16th International Conference on Optical Communications and Networks (ICOCN), Wuzhen, 2017. Google Scholar

 Fahad M, Aadil F, Rehman Z. Grey wolf optimization based clustering algorithm for vehicular ad-hoc networks. Comput Electrical Eng, 2018, 70: 853-870 CrossRef Google Scholar

 Khan A, Aftab F, Zhang Z. BICSF: Bio-Inspired Clustering Scheme for FANETs. IEEE Access, 2019, 7: 31446-31456 CrossRef Google Scholar

 Aadil F, Raza A, Khan M. Energy Aware Cluster-Based Routing in Flying Ad-Hoc Networks. Sensors, 2018, 18: 1413 CrossRef Google Scholar

 Ali H, Shahzad W, Khan F A. Energy-efficient clustering in mobile ad-hoc networks using multi-objective particle swarm optimization. Appl Soft Computing, 2012, 12: 1913-1928 CrossRef Google Scholar

 Zhu X, Bian C, Chen Y. A Low Latency Clustering Method for Large-Scale Drone Swarms. IEEE Access, 2019, 7: 186260 CrossRef Google Scholar

 Zeng Y, Zhang R, Lim T J. Throughput Maximization for UAV-Enabled Mobile Relaying Systems. IEEE Trans Commun, 2016, 64: 4983-4996 CrossRef Google Scholar

 Wu Q, Zhang R. Common Throughput Maximization in UAV-Enabled OFDMA Systems With Delay Consideration. IEEE Trans Commun, 2018, 66: 6614-6627 CrossRef Google Scholar

 Zhang G, Wu Q, Cui M. Securing UAV Communications via Joint Trajectory and Power Control. IEEE Trans Wireless Commun, 2019, 18: 1376-1389 CrossRef Google Scholar

 Jeong S, Simeone O, Kang J. Mobile Edge Computing via a UAV-Mounted Cloudlet: Optimization of Bit Allocation and Path Planning. IEEE Trans Veh Technol, 2018, 67: 2049-2063 CrossRef Google Scholar

 Wu Q, Zeng Y, Zhang R. Joint Trajectory and Communication Design for Multi-UAV Enabled Wireless Networks. IEEE Trans Wireless Commun, 2018, 17: 2109-2121 CrossRef Google Scholar

 Zhang G C, Wu Q Q, Cui M, et al. Securing UAV communications via trajectory optimization. In: Proceedings of IEEE Global Communications Conference, Singapore, 2017. Google Scholar

 Zhang J, Zeng Y, Zhang R. UAV-Enabled Radio Access Network: Multi-Mode Communication and Trajectory Design. IEEE Trans Signal Process, 2018, 66: 5269-5284 CrossRef ADS arXiv Google Scholar

 Zhang J, Zhou L, Zhou F. Computation-Efficient Offloading and Trajectory Scheduling for Multi-UAV Assisted Mobile Edge Computing. IEEE Trans Veh Technol, 2020, 69: 2114-2125 CrossRef Google Scholar

 Mahajan M, Nimbhorkar P, Kasturi R. The planar k-means problem is NP-hard. Theoretical Computer Science, 2009, 442: 274-285, doi: 10.1016/j.tcs.2010.05.034. Google Scholar

 Matolak D W, Sun R. Air-Ground Channel Characterization for Unmanned Aircraft Systems-Part I: Methods, Measurements, and Models for Over-Water Settings. IEEE Trans Veh Technol, 2017, 66: 26-44 CrossRef Google Scholar

 Grant M, Boyd S, Ye Y. CVX Toolbox. Redwood City: Stanford University Press, 2009. Google Scholar

 Qian B, Zhou H, Lyu F. Toward Collision-Free and Efficient Coordination for Automated Vehicles at Unsignalized Intersection. IEEE Internet Things J, 2019, 6: 10408-10420 CrossRef Google Scholar

 Laporte G. The traveling salesman problem: An overview of exact and approximate algorithms. Eur J Operational Res, 1992, 59: 231-247 CrossRef Google Scholar

• Figure 1

(Color online) Hierarchical framework for large-scale UAV clustering and 3D trajectory design in UAV swarms.

• Figure 4

(Color online) Transmission delay with different numbers of CHs in area 6.

• Figure 5

(Color online) Ferry UAV trajectories with throughput requirement $C~=~300$ Mbits. (a) Optimal 2D trajectory with fixed altitude; (b) optimal 3D trajectory.

• Figure 6

(Color online) Ferry UAV trajectories with throughput requirement $C~=~1500$ Mbits. (a) Optimal 2D trajectory with fixed altitude; (b) optimal 3D trajectory.

• Figure 7

(Color online) Completion time with different throughputs.

•

Algorithm 1 Modified k-means algorithm for each area

Input: UAV swarms $\mathcal{D}=\{{\boldsymbol~x}_1,~{\boldsymbol~x}_2,\ldots,~{\boldsymbol~x}_M\}$, clusters number $S$ from 5.

Output: locations of Super-CHs.

Randomly select $S$ UAVs from $\mathcal{D}$ as the initial mean vectors $\{{\boldsymbol\mu}_1,~{\boldsymbol\mu}_2,~\ldots,{\boldsymbol\mu}_S\}$.

Initialize $\mathcal{C}_i=\emptyset,~i=1,\ldots,S$.

for $j=1,2,\ldots,M$

Calculate the distance between each UAV ${\boldsymbol~x}_j$ and each mean vector ${\boldsymbol\mu}_i~(1\leq~i\leq~S)$: $d_{ji}=\|{\boldsymbol~x}_j-{\boldsymbol\mu}_i\|$;

Determine the cluster label of ${\boldsymbol~x}_j$ based on the nearest mean vector: $\lambda_j=\arg\min\nolimits_{i\in\{1,2,\ldots,S\}}d_{ji}$;

Divide ${\boldsymbol~x}_j$ into the corresponding cluster: $\mathcal{C}_{\lambda_j}=\mathcal{C}_{\lambda_j}\cup~\{{\boldsymbol~x}_j\}$.

end for

for $i=1,2,\ldots,S$

Calculate the new mean vector: ${\boldsymbol\mu}&apos;_i=\frac{1}{|\mathcal{C}_i|}\sum_{{\boldsymbol~x}_i\in~\mathcal{C}_i}{\boldsymbol~x}$;

if ${\boldsymbol\mu}&apos;_i\neq{\boldsymbol\mu}_i$ then

Update the current mean vector${\boldsymbol\mu}_i$ to ${\boldsymbol\mu}&apos;_i$;

else

Keep the current mean vector ${\boldsymbol\mu}_i$ unchanged;

end if

end for

Stop the Loop (Step 5–17) until all mean vectors are not updated.

Select UAVs closest to the mean vector as the CHs.

Choose the CH closest to all other CHs as the Super-CH.

• Table 1

Table 1Main notations

 Notation Meaning Notation Meaning $K$ Total number of Super-CH UAVs (i.e., the number of areas) $\alpha_i(t)$ Fraction of total bandwidth allocated for Super-CH $i$ $M_k$ Total number of UAVs in area $k$ $B$ Total available bandwidth $m$ Packet size $P_i$ Transmit power of Super-CH $i$ $\mu$ Transmission rate of each UAV $R_i(t)$ Instantaneous normalized achievable rate $T_t$ Total transmission delay of each UAV $\gamma_0$ Reference signal-to-noise ratio (SNR) at the reference distance of $d_0~=~1$ m $T_m$ CM delay $C_i$ Throughput requirement for Super-CH $i$ $T_h$ CH delay $N$ Time slot number ${\boldsymbol~x}_i$, ${\boldsymbol~s}_i$ Locations of UAVs and the Super-CH, respectively $\delta$ Length of time step $\mathcal{C}_i$ Cluster $i$ composed of CMs and one CH $T_{\rm~tr}$ Ferry UAV' traveling time $\mathcal{U}$ Set of Super-CH UAVs $\hat{\pi}$ Visiting order under TSP ${\boldsymbol~q}(t)$ Ferry UAV's trajectory $T_{\rm~tsp}$ Minimum traveling time under TSP $V_{\max}$ Maximum Ferry UAV speed $\bar{T}_i$ Time for Ferry UAV to satisfy the throughput requirement of Super-CH $i$ $d_{\min}$ Minimum safe distance between the Ferry UAVand Super-CH UAVs $\tilde{T}_i$ Residence time of Ferry UAV at Super-CH $i$ $d_i(t)$ Distance between Ferry UAV and Super-CH $i$ $r$ Radius of the sphere centered at Super-CH $h_i(t)$ Channel power gains ${\boldsymbol~g}_i$ Waypoint inside the sphere for Super-CH $i$
•

Algorithm 2 BCD based algorithm for (P1.3)

Require:A given $T$, initial trajectory of the Ferry UAV $\mathcal{Q}^0$,

prescribed thresholds $\epsilon_1>0$, $\epsilon_2>0$, $l=0$.

Output:$\mathcal{Q}^l$, $\mathcal{A}^l$, $\eta^l$.

while $\frac{\eta^{l+1}-\eta^l}{\eta^l}\geq~\epsilon_2$ do

For given $\mathcal{Q}^l$,obtain $\mathcal{A}^{l+1}$by solving problem (P1.4);

Initialize the inner iterative index $r=0$and the inner initial trajectory$\mathcal{Q}^{l,0}=\mathcal{Q}^{l}$;

while $\frac{\eta^{r+1}-\eta^r}{\eta^r}\geq~\epsilon_1$ do

For given $\mathcal{A}^{l+1}$ and $\mathcal{Q}^{l,r}$, obtain $\mathcal{Q}^{l,r+1}$ and $\eta^{r+1}$ by solving problem (P1.6);

$r=r+1$;

end while

$\mathcal{Q}^{l+1}=\mathcal{Q}^{l,r}$,$\eta^{l+1}=\eta^{r}$;

$l=l+1$;

end while

• Table 2

Table 2Main simulation parameters

 Parameter Value Parameter Value Total bandwidth: $B$ 10 MHz Minimum safe distance between the Ferry UAV and Super-CH UAVs: $d_{\min}$ $50$ m Noise power spectrum density: $N_0$ $-169$ dBm/Hz Time step length: $\delta$ 4 s Channel power gain at the reference distance of $d_0=1$ m: $\lambda_0$ $-50$ dB Thresholds in Algorithm 2: $\epsilon_1$,$\epsilon_2$ $10^{-2}$ Transmit power of each Super-CH: $P_i$ 10 dB Threshold in Algorithm initr: $\epsilon$ $10^{-3}$ Maximum speed of the Ferry UAV: $V_{\max}$ $50$ m/s
•

Algorithm 3 Initial trajectory design for given $T$

Require:A given $T$, locations of Super-CHs $\{{\boldsymbol~s}_i\}$.

Output:$r$, the initial trajectory.

Solve TSP to obtain minimum traveling time$T_{\rm~tsp}$ and optimal visiting order $\hat{\pi}$based on $\{{\boldsymbol~s}_i\}$;

if $T\geq~T_{\rm~tsp}$ then

else

Let $r_l=0$, $r_u$ be sufficiently large andtolerance $\epsilon>0$;

while $|T_{\rm~tr}~-T|\leq~\epsilon$ do

$r=(r_l+r_u)/2$;

Solve problem (P2.1) with visiting order $\hat{\pi}$ to derive traveling time $T_{\rm~tr}$ and waypoints $\{{\boldsymbol~g}_i\}$;

if $T_{\rm~tr}~>T$ then

Let $r_l=r$;

else

Let $r_u=r$;

end if

end while

Construct the initial trajectory based on $\{{\boldsymbol~g}_i\}$;

end if