災害應急通信自組網與航跡優化研究

災害應急通信自組網與航跡優化研究

高" 睿， 王" 霄， 徐凌樺

（貴州大學 電氣工程學院， 貴州 貴陽" 550025）

摘" 要： 針對災害場景下的應急通信網絡恢復問題，提出一種分布式無人機部署方法，旨在利用無人機在通信網絡受損的災區建立多跳自組織網絡，為該地區提供應急通信服務。首先，定義了無人機自組網約束函數、三維空間搜索方向約束函數和障礙物約束函數，將無人機輔助的多跳自組織網絡問題抽象為基于規則法的目標函數；其次，改進了慣性權重和學習因子來提高粒子群算法的全局搜索效率和準確性，并設計多跳自組織網絡無人機部署算法，以保證無人機能夠以最優的航跡進行自組織網絡部署；最后，通過計算目標函數進行無人機部署，并繪制無人機的三維部署航跡圖。設計仿真樣例對基于規則法的多跳自組織網絡無人機部署方法進行驗證，仿真結果證明了該方法的有效性。

關鍵詞： 無人機； 自組織網絡； 避障控制； 規則法； 粒子群算法； 航跡優化； 三維部署； 節能部署

中圖分類號： TN91?34； V279.2" " " " " " " " " " 文獻標識碼： A" " " " " " " " " " " 文章編號： 1004?373X（2024）19?0008?06

Research on disaster emergency communication ad hoc network and route optimization

GAO Rui， WANG Xiao， XU Linghua

（School of Electrical Engineering， Guizhou University， Guiyang 550025， China）

Abstract： In view of the recovery of the emergency communication network in the case of disaster， a distributed UAV （unmanned aerial vehicle） deployment method is proposed. It strives to establish a multi?hop ad hoc network by the UAV in disaster areas where the communication network is damaged， and provides emergency communication services for the region. The ad hoc network constraint function， the 3D search direction constraint function and the obstacle constraint function are defined. The UAV?aided multi?hop ad hoc network problem is abstracted as an objective function with behavior?based method. The inertia weight and the learning factors are improved to enhance the efficiency and accuracy of the particle swarm optimization （PSO） algorithm. The UAV deployment algorithm for multi?hop ad hoc network is designed， so that the UAV can realize the ad hoc network deployment with the optimal route. The UAV is deployed by calculating the objective function. The 3D deployment route map of the UAV is drawn. Simulation examples are designed to verify the behavior?based UAV deployment method for multi?hop ad hoc network. The simulation results show the effectiveness of the proposed method.

Keywords： UAV; ad hoc network; obstacle avoidance control; behavior?based method; PSO algorithm; track optimization; 3D deployment; energy efficient deployment

0" 引" 言

通信基礎設施受損時，需要建立有效的通信渠道以協調搜救行動。無人機（Unmanned Aerial Vehicle， UAV）是一種有吸引力的選擇，可在通信基礎設施受損的情況下建立穩定的自組織網絡，以支持搜救行動和恢復通信[1]。

在災害環境下，無人機充當自組織網絡節點代替受損的通信基礎設施。災害環境具有不可預知性，文獻[2]提出一種基于規則法的無人機集群編隊算法，在面對未知環境時的適應性更好。文獻[3]提出一種基于規則的無人機集群系統飛行與規避自主協同控制方法，能夠進行更加高效的實時無人機部署任務。文獻[4]提出一種利用多架無人機建立最優多跳自組網的方法，為災區提供應急通信。文獻[5]研究了多個無人機架載的航空基站，為一組遠程物聯網地面智能設備提供服務，并且通過最大限度地減少所需的無人機數量來提高能源效率。文獻[6]提出一種改進的禿鷹搜索優化算法，用以解決三維空間復雜環境下的無人機航跡規劃問題。文獻[7]針對固定翼無人機編隊在未知障礙環境下的安全飛行進行了控制方法的研究，并結合人工勢場和領從一致性設計了僚機群避障避碰控制策略，實現了無人機編隊的協同飛行。文獻[8]提出研究針對無人機作為臨時基站與地面終端用戶通信問題，優化了節點的三維部署和功率分配，以提高系統能效和用戶覆蓋率。文獻[9]提出了一種改進的基于球面向量的粒子群優化算法，用于無人機在復雜環境下的航跡規劃問題。文獻[10]通過雙門限約束提高網絡性能，有效增強了局部地區網絡性能，并且用甲蟲搜索來改進粒子群算法。文獻[11]提出改進粒子群遺傳算法，使無人機三維路徑規劃具備更好的魯棒性。文獻[12]提出一種改進的A*算法，使無人機避障航線規劃更加連續和順暢。

上述工作探討了無人機在復雜環境下的避障問題，但是缺乏對災害環境下多無人機組網問題的研究。針對災害場景下無人機充當自組織網絡節點代替受損的通信基礎設施的情形，本文在粒子群算法的基礎上，通過對加速系數的動態調整，可以使得算法更靈活地適應不同類型的優化問題，從而提升算法的性能和魯棒性。

1" 系統模型和問題描述

文獻[2?6]研究了基于規則法和人工勢場法等無人機編隊避障控制算法，結合災害應急通信場景下環境的不可預知性，結合無人機自組網約束函數、三維空間搜索方向約束函數、障礙物約束函數建立基于規則法的目標函數。

1.1" 場景描述

如圖1所示，本文主要研究了一種無人機輔助的災害應急通信自組織網絡模型。圖1中的通信鏈路有無人機間（UAV to UAV， U2U）通信，無人機與地面（UAV to Ground， U2G）基站、地面用戶間通信。災害發生時部分地面基站受損導致災害地區通信網絡中斷，無法及時傳遞災情，此時無人機充當自組織網絡節點代替受損的地面基站。

1.2" 無人機自組網約束函數

假設一個2 000 m×2 000 m的矩形區域[R]，其中包含[L]個地面基站，用集合[l]=1，2，…，[L]表示，[li=（lxi，lyi）]表示第[i]個地面基站的水平坐標。假設[N]個無人機分布其中，[ui=（xi，yi）]表示第[i]架無人機的水平坐標。[hi]、[Ri]表示第[i]架無人機的高度和通信半徑。用[Zi=（zxi， zyi）]表示矩形區域內任意一點處的水平坐標。任意兩個無人機之間的距離不能小于安全距離[dmin]，也不能超過最大通信距離[dmax]。無人機之間的距離表示為：

[di，k=（hi-hk）2+（ui-uk）2] （1）

無人機之間的連通率表示為：

[Pui，li=1，" " "0≤h2i+（lxi-xi）2+（lyi-yi）2≤dmax0，" " "h2i+（lxi-xi）2+（lyi-yi）2gt;dmax] （2）

無人機自組網約束函數為：

[f1=li∈RPui，li] （3）

1.3" 三維空間搜索方向約束函數

用[Zi=（zxi， zyi， zhi）]表示矩形區域內障礙物的中心坐標，用[Ui=（xi， yi， zi）]表示矩形區域內無人機的坐標，為使無人機能夠快速移動到下一個自組織節點，對無人機的搜索方向做出以下約束：

[U*i=xi，yi， zi+Hyi，xi] （4）

[Ui+1=（xi+1，yi+1， zi+1）] （5）

[U*i+1=xi+1，yi+1， zi+1+Hyi+1，xi+1] （6）

[Z*i=zxi， zyi， zhi+Hzyi，zxi] （7）

[Vec1=UiU*i] （8）

[Vec2=UiZ*i] （9）

搜索方向約束函數為：

[f2=arctan2Vec1×Vec2，Vec1·Vec2] （10）

1.4" 障礙物約束函數

設障礙物的半徑為[Rzi]，無人機與障礙物的預警距離為20 m。

障礙物約束函數為：

[f3=10 000，" "（zxi-xi）2+（zyi-yi）2+（zhi-hi）2lt;RziRzi+20-（zxi-xi）2+（zyi-yi）2+（zhi-hi）2，" 其他0，" " （zxi-xi）2+（zyi-yi）2+（zhi-hi）2gt;Rzi+20] （11）

1.5" 目標函數

將無人機自組網約束函數、三維空間搜索方向約束函數、障礙物約束函數加權綜合，構建一個基于規則法的適用于災害場景下部署無人機充當自組織網絡節點的目標函數，公式如下：

[F=Zf1+kf2+ff3] （12）

式中：[Z]為無人機約束函數的行為權重系數，設置為6；[k]為搜索方向約束函數的行為權重系數，設置為3；[f]為障礙物約束函數的行為權重系數，設置為10。

2" 多跳自組織網絡無人機部署算法設計

公式（12）定義的函數是一個關于無人機充當自組織網絡節點的航跡規劃多峰函數。元啟發式算法在處理多峰函數時具有較好的全局搜索能力、魯棒性和適應性。它們可以通過多策略搜索和可擴展性來克服多峰函數的挑戰，提供有效的解決方案。

2.1" 標準粒子群優化算法原理

粒子群優化（Particle Swarm Optimization， PSO）算法是一種元啟發式優化算法，靈感來源于鳥群或魚群等集體行為。該算法最早由Eberhart和Kennedy在1995年提出，并在優化領域中得到廣泛研究和應用。

粒子群算法中，每個粒子的位置可以表示為一個[d]維向量[Xi=（Xi1，Xi2，…，Xid）]，每個粒子的速度也是一個[d]維向量[Vi=（Vi1，Vi2，…，Vid）]。在初始時刻，每個粒子的位置和速度是根據隨機分布進行初始化的。在粒子群算法中，每個粒子根據自身歷史最優位置[Pbesti]和全局歷史最優位置[Gbest]進行位置和速度的更新。粒子位置的更新可以寫為：

[Xij（t+1）=Xij（t）+Vij（t+1）] （13）

粒子速度的更新可以寫為：

[Vij（t+1）=wVij（t）+c1r1（Pbestij-Xij（t））+c2r2（Gbestj-Xij（t））] （14）

式中：[Vij（t+1）]表示第[i]個粒子在[t+1]時刻的速度；[w]是慣性權重；[c1]、[c2]是學習因子；[r1]、[r2]是[0，1]之間的隨機數。

2.2" 改進粒子群算法

2.2.1" 慣性權重更新策略

慣性權重更新策略是粒子群算法中的一個關鍵因素。選擇合適的慣性權重更新策略可以更好地平衡全局搜索和局部搜索，提高粒子群算法的搜索性能。非線性遞減慣性權重策略通過調整慣性權重的變化率，在搜索過程中平衡全局搜索和局部搜索的能力[13]。對于多峰函數，希望算法能夠在探索各個峰值之間進行平衡，以獲取全局最優解。

[ωt = 0.5tan0.8751-ttmax0.6" +0.4] （15）

式中：[t]為當前的迭代次數；[tmax]為初始設置的最大迭代次數。

2.2.2" 學習因子更新策略

學習因子是粒子群算法中的重要參數，影響全局搜索、局部搜索、收斂速度和搜索魯棒性。非對稱學習因子更新策略可以使得粒子在靠近全局最優解時減速更快、更慎重，以便更好地細致搜索最優解附近的區域；而在遠離全局最優解時加速更快，以便更好地擴大搜索范圍，從而更可能找到其他潛在的最優解。這種策略增加了算法對多峰函數的探索能力，有助于提高全局搜索的效率和準確性。

[ct1=2.5-2×ttmax] （16）

[ct2=1-1.25×ttmax] （17）

粒子速度公式更新為：

[Vij（t+1）=0.5tan0.8751-ttmax0.6+0.4?" " " " Vij（t）+2.5-2×ttmaxr1Pbestij-Xij（t）+" " " " 1-1.25×ttmaxr2Gbestj-Xij（t）] （18）

2.2.3" 改進粒子群優化算法步驟

改進粒子群優化（Improved Particle Swarm Optimization， IPSO）算法步驟如下。

1.初始化粒子群：隨機生成粒子的位置和速度，將每個粒子的最佳位置設置為初始位置，初始化全局最佳位置。

2.迭代優化過程：

2.1.對于每個粒子，更新粒子速度，計算速度變化量，限制速度在最小速度和最大速度之間；更新粒子位置，將速度加到當前位置上，檢查位置是否超出取值范圍，如果超出范圍，則將速度反向操作，限制位置在最小值和最大值之間；計算粒子位置的目標函數，如果當前成本優于個體最佳目標函數值，更新個體最佳位置和目標函數值，如果個體最佳成本優于全局最佳目標函數值，更新全局最佳位置和目標函數值。

2.2.更新慣性權重值、學習因子值。

2.3.將當前迭代的全局最佳目標函數存儲。

3.返回全局最佳位置作為優化結果。

2.2.4" 多跳自組織網絡無人機部署算法步驟

多跳自組織網絡無人機部署算法步驟如下：

1.初始化無人機的起始位置、速度、搜索方向。

2.根據定義的搜索范圍，將無人機移動到它通信半徑內所能達到的最遠目標附近。

3.在通信半徑范圍內，計算無人機到每個目標的距離。

4.根據距離、速度等條件，選擇下一個要追蹤的臨時目標。

5.如果存在臨時目標：

5.1.根據無人機的速度和時間間隔，計算無人機從當前位置到臨時目標位置所需的時間。

5.2.計算無人機需要前往的下一個目標位置，這個位置是根據無人機的搜索方向和速度計算得出的。

5.3.根據計算得到的位置更新無人機的搜索方向。

5.4.利用無人機的速度和時間間隔，在無人機的當前位置和下一個目標位置之間進行插值，獲得無人機經過的路徑點。

5.5.更新無人機的當前位置為下一個目標位置。

5.6.將無人機的當前位置和路徑點添加到路徑中。

6.重復步驟3～步驟5，直到無人機達到終點或搜索完所有目標。

7.繪制無人機的路徑。

3" 仿真數值結果及討論

仿真實驗平臺為AMD R7?5800H CPU，16 GB，64位WIN10操作系統，編程工具為Matlab R2021a。

3.1" 參數設置

相關參數設置如表1所示。

3.2" 仿真實驗結果及分析

3.2.1" 算法收斂性能分析

對于時間復雜度，算法中最耗時的部分是迭代循環，它的運行次數等于迭代次數乘以粒子數目。假設粒子數目為[Pn]、迭代次數為[tmax]，則迭代循環的時間復雜度為[O（Pn?tmax）]。

對于空間復雜度，算法需要存儲每個粒子的位置、速度、最佳位置等信息，并且需要存儲其他問題相關的變量和參數，如變量的上下界、慣性權重、加速度常數等。因此，算法的空間復雜度為[O（Pn）]。

圖2為不同算法下適應度曲線對比圖，IPSO算法搜索能力更強，能更好地執行災害應急通信場景下的多跳自組織網絡無人機部署任務。

3.2.2" 多跳自組織網絡無人機部署仿真（隨機分布小型障礙點）

圖3為小型障礙點多跳自組織網絡無人機部署航跡路線圖。

在2 000 m×2 000 m的矩形區域[R]內，設置地面基站的水平坐標分別為（10，10）、（1 820，1 800），無人機初始坐標為（10，10，100），無人機任務坐標為（1 820，1 800，200）。兩個地面基站之間的其余地面通信基礎設施均受損，并且存在一些小型障礙點，這些障礙點在兩個地面基站的直線路徑上隨機分布。無人機在兩個地面基站間充當臨時通信節點搭建多跳自組織網絡。無人機最大通信半徑為300 m，無人機與障礙點預警距離為20 m，無人機數目為9架。

如圖3所示，根據地面基站的水平坐標以及無人機最大通信距離可以計算最少需要9架無人機可以實現無人機輔助多跳自組織網絡搭建，本文所提方法可以在小型障礙點下實現最少無人機部署。

圖4為多跳自組織網絡無人機部署最佳適應度曲線圖，算法在迭代25次后逐漸收斂。本文所提方法在隨機分布小型障礙點下可以實現無人機輔助多跳自組織網絡搭建。

3.2.3" 多跳自組織網絡無人機部署仿真（對稱分布大型障礙點）

圖5為大型障礙點多跳自組織網絡無人機部署航跡路線圖。

在2 000 m×2 000 m的矩形區域[R]內，設置地面基站的水平坐標分別為（10，10）、（1 870，1 870），無人機初始坐標為（10，10，100），無人機任務坐標為（1 870，1 870，200）。兩個地面基站之間的其余地面通信基礎設施均受損，并且存在一些大型障礙點，這些障礙點在兩個地面基站的直線路徑上對稱分布。無人機在兩個地面基站間充當臨時通信節點搭建多跳自組織網絡。無人機最大通信半徑為300 m，無人機與障礙點預警距離為20 m，無人機數目為10架。

如圖5所示，根據地面基站的水平坐標以及無人機最大通信距離可以計算最少需要9架無人機可以實現無人機輔助多跳自組織網絡搭建，本文所提方法需要10架無人機部署任務。

圖6為多跳自組織網絡無人機部署最佳適應度曲線圖，算法在迭代50次后逐漸收斂。本文所提方法在復雜的大型障礙點下可以實現無人機輔助多跳自組織網絡搭建。

3.2.4" 能耗分析

單個無人機基站的能耗表示如下：

[EUAV=Pt*t+（13.04hi+196.89）?t+4.68h2i-11.97hi+245.28Lhorizontal+135.31] （19）

式中：[EUAV]表示單個無人機能量，設為600 W·h；[Pt]表示無人機發射功率，設為30 dBm；[Lhorizontal]表示無人機飛行路徑；[t]表示無人機可用時間。

根據公式（19）及無人機飛行航跡路線圖，總結出無人機能耗如表2所示。

由表2可知：當無人機遇到障礙物不采取避障行為，而是直接飛到超出障礙物高度，再朝下一目標部署點飛去，隨機小型障礙點場景下無人機平均可用時間為476 s，復雜大型障礙點場景下無人機平均可用時間為469 s；當無人機遇到障礙物時采取本文所提的基于規則法的多跳自組織網絡的無人機部署方法，此時隨機小型障礙點場景下無人機平均可用時間為913 s，增加了91.8%的可用時間，復雜大型障礙點場景下無人機平均可用時間為965 s，增加了105.7%的可用時間。

4" 結" 語

針對災害場景下地面基礎設施受損導致的通信中斷問題，本文提出了一種災害應急通信多跳自組織網絡無人機部署方法。該方法利用無人機充當自組織網絡節點代替受損的通信基礎設施，并且充分考慮了未知的受災環境下的無人機避障問題。通過仿真驗證了該方法的可行性。

盡管本文算法實現無人機輔助多跳自組織網絡的搭建，但該方法存在一定的限制。具體而言，該算法未考慮復雜的動態環境。因此，在未來的研究中將考慮資源約束和能源管理，進一步研究在資源有限的情況下最大化無人機組網的效率和覆蓋范圍。

注：本文通訊作者為王霄。

參考文獻

[1] GUTIERREZ REINA D， LEON?COCA J M， ASKALANI M， et al. A survey on ad hoc networks for disaster scenarios [C]// 2014 International Conference on Intelligent Networking and Collaborative Systems. New York： IEEE， 2014： 433?438.

[2] 馮一飛.基于行為法的分布式無人機集群控制方法與仿真研究[D].長春：吉林大學，2023.

[3] 周歡，趙輝，韓統，等.基于規則的無人機集群飛行與規避協同控制[J].系統工程與電子技術，2016，38（6）：1374?1382.

[4] THUY N D T， BUI D N， PHUNG M D， et al. Deployment of UAVs for optimal multihop ad?hoc networks using particle swarm optimization and behavior?based control [C]// 2022 11th International Conference on Control， Automation and Information Sciences. New York： IEEE， 2022： 304?309.

[5] NOURI N， ABOUEI J， SEPASIAN A R， et al. Three?dimensional multi?UAV placement and resource allocation for energy?efficient IoT communication [J]. IEEE Internet of Things journal， 2022， 9（3）： 2134?2152.

[6] 黃鶴，溫夏露，王會峰，等.基于IBES優化的三維無人機自主避障[J].復旦學報（自然科學版），2023，62（5）：615?626.

[7] 黃號，馬文卉，李家誠，等.未知環境下無人機編隊智能避障控制方法[J].清華大學學報（自然科學版），2024，64（2）：358?369.

[8] 石東森，田峰.基于多目標粒子群算法的無人機通信三維位置部署及優化研究[J].南京郵電大學學報（自然科學版），2022，42（4）：45?55.

[9] 宋志強，夏慶鋒，陳少博，等.基于改進球面向量粒子群優化的UAV航跡規劃[J].電光與控制，2023，30（4）：56?60.

[10] 陳佳美，李世昂，李玉峰，等.基于甲蟲搜索的改進粒子群無人機輔助網絡部署優化算法[J].電子與信息學報，2023，45（5）：1697?1705.

[11] 胡觀凱，鐘建華，李永正，等.基于IPSO?GA算法的無人機三維路徑規劃[J].現代電子技術，2023，46（7）：115?120.

[12] 高九州，徐威峰，張立輝，等.基于改進A*算法的無人機避障航線規劃[J].現代電子技術，2023，46（8）：181?186.

[13] 于桂芹，李劉東，袁永峰.一種結合自適應慣性權重的混合粒子群算法[J].哈爾濱理工大學學報，2016，21（3）：49?53.

作者簡介：高" 睿（1997—），男，江蘇鹽城人，碩士研究生，研究方向為應急通信無人機部署。

王" 霄（1985—），男，黑龍江哈爾濱人，博士研究生，副教授，研究方向為物聯網理論及應用、人工智能理論及應用。

徐凌樺（1976—），男，貴州貴陽人，碩士研究生，副教授，研究方向為嵌入式系統、傳感器網絡、工業自動化及智能控制。

收稿日期：2024?02?07" " " " " "修回日期：2024?03?05

基金項目：國家自然科學基金項目（61861007）；國家自然科學基金項目（61640014）；貴州省科技計劃項目（黔科合基礎?ZK[2021]一般303）；貴州省科技支撐計劃（黔科合支撐[2022]一般017，黔科合支撐[2023]一般096，黔科合支撐[2022]一般264）；貴州省教育廳創新群體項目（黔教合KY字[2021]012）；貴大人基合字（2014）08號