logo

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

More info
  • ReceivedApr 1, 2020
  • AcceptedJul 27, 2020
  • PublishedMar 5, 2021

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 [29]. 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

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

[2] 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

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

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

[5] 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

[6] 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

[7] 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

[8] 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

[9] 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

[10] 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

[11] 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

[12] 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

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

[14] 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

[15] 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

[16] 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

[17] 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

[18] 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

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

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

[21] 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

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

[23] 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

[24] 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

[25] 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

[26] 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

[27] 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

[28] 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

[29] 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

[30] 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

[31] 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

[32] 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

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

[34] 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

[35] 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 MeaningNotation 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 ValueParameter Value
    Total bandwidth: $B$10 MHzMinimum safe distance between the Ferry UAV and Super-CH UAVs: $d_{\min}$ $50$ m
    Noise power spectrum density: $N_0$ $-169$ dBm/HzTime step length: $\delta$ 4 s
    Channel power gain at the reference distance of $d_0=1$ m: $\lambda_0$ $-50$ dBThresholds in Algorithm 2: $\epsilon_1$,$\epsilon_2$ $10^{-2}$
    Transmit power of each Super-CH: $P_i$ 10 dBThreshold 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

    Design initial trajectory based on Case 1;

    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