災后應急通信網絡下的中繼選擇與軌跡優化研究

陳海華 高飛帆 何 明

①(南開大學電子信息與光學工程學院 天津 300350)

②(天津市光電傳感器與傳感網絡技術重點實驗室 天津 300350)

③(薄膜光電子技術教育部工程研究中心 天津 300350)

1 引言

近年來，無人機(Unmanned Aerial Vehicle, UAV)憑借其機動性強、部署靈活、可重構性強等特點，開始在災后救援工作中得到廣泛應用，承擔著災情檢測、通信覆蓋和數據收集等重要任務[1–4]。自然災害發生后，基站設備和主要道路往往會遭到破壞，使得災區無法與外界取得聯絡，外界救援人員也難以進入。此時，便可以利用無人機參與災后救援工作。無人機基站的快速部署可以迅速為災區提供應急通信服務[5]，而且無人機的高分辨率相機和低空飛行高度可以產生比衛星圖像更精確的2D圖像和3D地圖[6]，為后續大規模救援的開展提供極大的幫助。

關于中繼無人機在災后的部署，目前已有大量研究。文獻[7]使用遺傳算法優化中繼無人機的部署位置，以提高應急網絡的覆蓋范圍和吞吐量。文獻[8]通過K均值聚類算法優化災后中繼無人機的實時部署，并以最大化通信系統的能量效率為目標提出了資源分配算法。在無人機為災區提供應急通信網絡后，使用中繼選擇技術可以進一步提升通信網絡的質量，并降低中繼無人機的能耗，延長應急通信網絡的續航時間。文獻[9]研究了多無人機非正交多址接入(Non-O rthogona l M u ltip le A ccess,NOMA)網絡在過時信道下的中繼選擇算法，降低了系統的中斷概率。文獻[10]將無人機的信道競爭建模為擁塞博弈模型，研究了動態多無人機通信網絡的中繼匹配問題。

除了為災區提供應急通信網絡，無人機還經常被用來做災情檢測或數據收集等任務。文獻[11]中無人機通過災后地面的物聯網節點來收集數據，并提出了一種最小能耗的無人機軌跡方案。文獻[12]將任務分配問題轉化為動態匹配問題，為無人機合理分配災后監測任務。文獻[13]為多個無人機規劃飛行路線，以使無人機能在最短時間內收集到災后所有監測點的信息。

上述關于災后無人機的研究，大多都是單獨考慮無人機部署或任務分配場景。在復雜地形條件下，執行低空任務的無人機信道條件比較差，此時需要借助中繼無人機構建的應急通信網絡來傳輸數據。因此本文針對災后應急通信網絡下勘察無人機執行任務的場景，研究了中繼選擇和飛行軌跡與系統能量效率之間的關系。本文的主要貢獻如下：(1)考慮了中繼無人機的可用通信能量以及勘察無人機的最大飛行速度和實時通信質量，通過聯合優化中繼選擇和飛行軌跡來實現系統的能量效率最大化。(2)由于涉及問題是非確定性多項式難度(Nondeterm inistic Polynom ial hard,NP-hard)問題，難以直接求解。本文提出一種基于連續凸近似(Successive Convex App roxim ation,SCA)和禁忌搜索(Tabu Search,TS)的交替迭代算法，將原問題拆分成軌跡優化子問題和中繼選擇子問題分別求解，交替迭代直至收斂，得到原問題的近似最優解。(3)仿真結果表明，本文所提算法可以有效提高系統的能量效率，因而在保證勘察無人機的實時通信質量的同時，延長了應急通信網絡的整體續航時間。

2 系統模型

考慮如圖1所示的災后應急通信網絡的場景，該場景包括1個指揮中心(用D表示)，M個中繼無人機(用Um表示第m個中繼無人機)和1個勘察無人機(用S表示)。中繼無人機懸停在受災區域上空，為該區域提供應急通信服務。低空的勘察無人機S需要按照任務移動到指定地點，并且在飛行過程中與指揮中心D保持實時通信。由于地形因素的影響，勘察無人機S與指揮中心D之間無法形成直接鏈路，但可以通過多個中繼無人機構建的應急通信網絡與指揮中心D建立中繼通信鏈路。假設指揮中心D位于地面的固定位置，所有中繼無人機的懸停高度固定為H(U)，勘察無人機S的飛行高度為H(S)。設D的坐標為第m個中繼無人機的坐標為m=1,2,...,M，其中[·]T表示轉置。由于S的飛行軌跡是隨時間連續變化的，為了降低軌跡優化的復雜度，采用離散近似方法[14]將S的飛行時間范圍T平分成N個時隙，每個時隙的長度記為ΔT。當ΔT相對較小時，便可以近似認為S在該時隙內的位置是固定的。S在第n個時隙時的坐標可以記為q n=,n=1,2,...,N，因此可以將S的飛行軌跡記為Q=[q1,q2,...,q N]。設S的起點和終點坐標分別為q0和qN，則存在如式(1)的飛行速度約束

圖1 系統模型

其中，V表示S的最大飛行速度。

絕大部分情況下，中繼無人機與S和D的通信鏈路都可以近似為視距(Light-of-Sight,LoS)鏈路[15]。因此本文中只考慮信道的大尺度衰落，其遵循自由空間的路徑損耗模型。在第n個時隙中，S與Um的信道系數fn,m(q n)以及D與Um的信道系數gm分別可以表示為

其中，[X]n,m=xn,m，即矩陣X第n行第m列元素為xn,m。約束C1是對鏈路S-D的最小數據傳輸速率要求，以保證S的實時通信質量，其中Rmin是數據傳輸速率閾值。約束C2是S的飛行速度約束。約束C3是中繼無人機的通信能量約束，其中Em表示第m個中繼無人機的可用通信能量。而且約束C3可以保證單個中繼無人機的通信能量不被過度消耗，進而延長應急通信網絡的整體續航時間。本文中的飛行時間T根據勘察無人機S的具體任務來設定，并假設無人機動力能量足以支持飛行任務。約束C4是中繼選擇變量xn,m的整數約束。由于目標函數η(X,Q)以及約束C1和C4既包含連續變量Q，又包含整數變量X，因而該問題是NP-hard問題，難以在多項式時間內直接求解。本文提出一種基于SCA和TS的交替迭代算法求得其近似最優解。

3 算法設計

本文將問題(P1)拆分成兩個子問題交替求解，即在中繼選擇矩陣X固定的情況下，(P1)可以轉化為軌跡優化子問題；而在飛行軌跡Q固定的情況下，(P1)可以轉化為中繼選擇子問題。將上述兩個子問題分別求解，交替迭代直至收斂，便可得到問題(P1)的近似最優解。

3.1 軌跡優化子問題

在已知中繼選擇矩陣X的情況下，可以將問題(P1)寫成如式(12)的形式

問題(P2)只需要優化S的飛行軌跡Q即可。然而，由式(8)和式(10)可知，即使中繼選擇矩陣X已知，目標函數η(X,Q)和約束C1仍然是非凸的，所以問題(P2)難以求解。為了求解該問題，本文采用連續凸近似(Su ccessive Convex A p p rox im ation,SCA)方法將(P2)近似為一系列凸優化問題進行迭代求解。

令Q(i)表示第i次迭代時S的飛行軌跡，表示第i次迭代時S在第n個時隙的坐標。將式(2)、式(3)和式(5)代入式(9)并重新整理可得

3.2 中繼選擇子問題

由于約束C3是整數約束條件，因此問題(P4)是一個NP-hard的組合優化問題，通常難以在多項式時間內求得最優解。禁忌搜索(Tabu Search,TS)算法對局部搜索算法進行了改進，通過對當前解的鄰域進行搜索得到新的可行解，并利用禁忌表來避免陷入局部最優，因而對于上述組合優化問題具有很好的性能[17,18]。本文采用TS算法來求解問題(P4)。

3.2.1 TS算法改進

鑒于TS算法的特點，其關鍵在于初始解的選取、鄰域結構還有禁忌表與禁忌長度的設置。本文對TS算法進行了相應改進，使其更適用于求解問題(P4)。

(1)初始解。TS算法對初始解有較強的依賴性，好的初始解可以使算法在鄰域中更快搜索到好的解，而差的初始解則會影響算法的收斂速度。而且TS算法需要一個可行解作為初始解，才能進行后續的算法步驟。因此，本文利用貪心算法生成滿足約束條件的可行解X(0)作為初始解。

(2)鄰域結構。鄰域結構的設計是決定TS算法性能優劣的關鍵。鄰域結構的規模越大，TS算法每次迭代時搜索的解會越多，就會有更大的概率獲得全局最優解，但每次迭代所需時間也會更長。現階段，TS算法中常用的鄰域有2-opt鄰域、3-opt鄰域和Cross鄰域等[19]。本文針對帶約束條件的問題(P4)設置了特有的鄰域算子：隨機選擇兩個時隙節點，利用貪心算法重置這兩個時隙的中繼選擇變量。這樣可以保證生成的鄰域解都能滿足約束條件，避免生成大量不可行的鄰域解，節省了算法運行時間。

(3)禁忌表與禁忌長度。結合上述鄰域結構，本文將禁忌表中的元素設置為算法每次迭代時更改的時隙節點。而且本文采用可變禁忌長度來提高TS算法的性能[20]，其規則為：在TS算法初始化時設置初始禁忌長度，當搜索過程中發現更優解時，增加禁忌長度來提高解的集中性；否則，減少禁忌長度來擴大解的搜索范圍。

3.2.2 TS算法流程

結合上述的TS算法改進，本文中TS算法的流程如圖2所示，算法描述如下。

圖2 TS算法流程圖

步驟1初始化TS算法迭代次數j=0，收斂閾值ε0，利用貪心算法生成可行解X(0)作為初始解；

步驟2生成鄰域。以當前解為中心，利用設置的鄰域算子生成L個鄰域解，并將所有鄰域解按優化問題(P4)的目標函數值排序得到候選解集合；

步驟3判斷是否滿足特赦準則。當最優候選解的目標函數值大于當前的全局最優解時，忽略其是否被禁忌，直接采用其作為當前解；否則，采用未被禁忌的最優候選解作為當前解；

步驟4更新禁忌表和禁忌長度。將本次迭代中更改的時隙節點加入禁忌表，并釋放已滿足禁忌長度的禁忌屬性。如果在步驟3中滿足特赦準則，增加禁忌長度；否則，減少禁忌長度；

步驟5判斷是否滿足終止準則。若TS算法的迭代次數大于J(最大迭代次數)或者目標函數值在J0次迭代內的增加量小于ε0，此時TS算法結束循環，輸出全局最優解；否則，j=j+1，并轉到步驟2。

3.3 交替迭代算法

根據以上兩個子問題的解決方案，本文針對問題(P1)提出了基于SCA和TS的交替迭代算法，整個交替迭代算法的流程如圖3所示，算法描述如下。

圖3 交替迭代算法流程圖

步驟2根據Q(i)和X(i)，利用內點法求解問題(P3)得到Q(i+1)；

步驟3將X(i)作為TS算法的初始解，根據Q(i+1)執行TS算法求解問題(P 4)得到X(i+1)和；

令Q(i+1)表示第(i+1)次迭代時問題(P3)的最優解，此時有

4 仿真結果

為了驗證本文所提算法的有效性，本節對所提算法進行了仿真驗證。在仿真中，將指揮中心D的坐標設置為pD=[-1 000,1 000,0]T，受災區域設置為如圖4所示的正方形區域。假設中繼無人機在受災區域上空均勻分布，覆蓋整個受災區域來提供應急通信網絡，并且所有中繼無人機的可用通信能量Em和發射功率pm相同。勘察無人機S的起點和終點坐標分別設置為q0=[500,2 000,H(S)]T和q N=[1 500,0,H(S)]T，初始軌跡Q(0)設定為從起點到終點的直線，如圖4所示。其余仿真參數如表1所示。

表1 仿真參數

圖4 仿真區域

圖5給出了不同參數條件下，系統的能量效率與交替迭代次數i的關系。隨著交替迭代次數的增加，系統的能量效率會升高并最終收斂。由圖5可知，在不同的參數條件下，本文所提算法都可以在4次迭代后收斂，說明本文提出的基于SCA和TS的交替迭代算法具有較好的收斂性。

圖5 收斂性驗證

此外，本節還將本文所提的聯合優化方案與以下3種基準方案進行了對比：(1)只優化中繼：在該方案中，S的飛行軌跡采用初始軌跡Q(0)，并且采用TS算法對中繼選擇矩陣X進行優化。(2)只優化軌跡：在該方案中，中繼選擇矩陣采用貪心算法獲得的初始解X(0)，并且采用SCA方法對S的飛行軌跡Q進行優化。(3)初始方案：在該方案中，S的飛行軌跡采用初始軌跡Q(0)，而且中繼選擇矩陣采用貪心算法獲得的初始解X(0)。

圖6展示了經過不同方案優化后勘察無人機S的飛行軌跡。從圖6可以看出，相比于只優化中繼，在聯合優化和只優化軌跡時，S的飛行軌跡都會傾向于靠近離D更近的中繼無人機，因為這些中繼無人機具有更好的信道系數gm。而且相比于只優化軌跡的方案，聯合優化方案中S的飛行軌跡會更加平滑且靠近D。這是因為貪心算法只能獲得單個時隙內最優的中繼選擇，而經過TS算法優化后，S會在所有時隙中更合理地選擇中繼。兩種優化方案得到的中繼選擇矩陣不同，因而經過優化后S的飛行軌跡也會不同。

圖6 不同方案下的飛行軌跡

圖7給出了不同優化方案下，系統的能量效率與最大飛行速度V的關系。隨著V的增大，S的飛行軌跡可以更加靠近信道條件較好的中繼無人機，從而具有更高的能量效率。因此，在聯合優化或只優化軌跡時，系統的能量效率會隨著V的增大而增加，而且聯合優化方案的性能明顯優于其他3種方案。但在只優化中繼時，S的飛行軌跡始終是初始軌跡，因此系統的能量效率不受V的影響，是一個固定值。本文提出的聯合優化方案與只優化中繼和只優化軌跡的基準方案相比，在V=13 m/s時，分別能夠提升12.9%和13.6%的性能；在V=15 m/s時，分別能夠提升22.1%和21.3%的性能。

圖7 能量效率與最大飛行速度的關系

圖8給出了不同優化方案下，系統的能量效率與中繼無人機的可用通信能量Em的關系。從圖8可以看出，隨著Em的增大，系統的能量效率也會增加。因為當Em增大時，S可以在更多時隙內選擇到信道較好的中繼無人機。但當Em增大到一定值時，S在每個時隙內都能選擇到信道條件最好的中繼無人機，因此系統的能量效率不再增加。從圖8可以看出，在Em=50 J時，本文所提方案與只優化中繼和只優化軌跡的基準方案相比，分別能夠提升21.8%和22.6%的性能。相比于其他方案，本文所提出的聯合優化方案在Em較小時(比如Em≤70 J)，仍然可以大幅提高系統的能量效率，此時還可以有效防止單個中繼無人機的通信能量過度消耗，進一步延長應急通信網絡的整體續航時間。

圖8 能量效率與可用通信能量的關系

圖9給出了不同優化方案下，系統的能量效率與數據傳輸速率閾值Rmin的關系。從圖9中可以看出，隨著Rmin的增大，系統的能量效率會逐漸降低，但當Rmin≤3.8 bit/(Hz·s)時，每種優化方案所得到的能量效率會保持不變。這是因為當Rmin增大時，S需要選擇更多的中繼無人機來轉發信號，這樣才能滿足鏈路S-D的最小數據傳輸速率要求。此時S也會選擇一些信道條件較差的中繼，系統的能量效率便會降低。但當Rmin較小時，S在每個時隙中只需要選擇一個信道條件最好的中繼無人機便可以滿足最小數據傳輸速率要求，導致不同的Rmin最終會得到相同的中繼選擇矩陣X，因此系統的能量效率會保持不變。而且由圖9可知，當Rmin較大時，聯合優化方案的性能明顯優于與其他3種方案。在Rmin=4.4 bit/(Hz·s)時，與只優化中繼和只優化軌跡的基準方案相比，本文提出的聯合優化方案能夠提升31.1%和28.2%的性能。

圖9 能量效率與數據傳輸速率閾值的關系

上述結果均是在中繼無人機數量M=16的條件下進行的仿真，為了驗證所提算法的合理性，本文還對不同數量的中繼無人機進行了仿真。勘察無人機S的起點和終點坐標不變，中繼無人機在受災區域上空均勻分布。圖10和圖11分別是在M=25和M=36的條件下進行的仿真結果，即系統能量效率和最大飛行速度V的關系。從圖中可以看出，對于不同數量的中繼無人機，本文所提聯合優化方案的性能均明顯優于其他3種方案，從而驗證了所提算法的合理性。本文所提出的聯合優化方案與只優化中繼和只優化軌跡的方案相比，在M=25,V=13 m/s時，分別能夠提升19.4%和17.3%的性能；在M=36,V=13 m/s時，分別能夠提升21.5%和17.4%的性能。

圖10 M=25時能量效率和最大飛行速度的關系

圖11 M=36時能量效率和最大飛行速度的關系

綜合上述分析，在不同的參數條件下，本文所提出的聯合優化方案的性能均優于其他3種方案。因為與其他方案相比，聯合優化方案具有更多的自由度來優化系統的能量效率。在約束條件比較苛刻時，聯合優化方案與其他方案的性能差距更加明顯，說明本文所提算法可以有效提高系統的能量效率。

5 結論

針對災后應急通信網絡下勘察無人機執行任務的場景，本文考慮了中繼無人機的可用通信能量以及勘察無人機的最大飛行速度和實時通信質量，通過聯合優化中繼選擇和飛行軌跡來最大化系統的能量效率。針對該NP-hard優化問題，本文提出一種基于連續凸近似(SCA)和禁忌搜索(TS)的交替迭代算法，可以得到原問題的近似最優解。仿真結果表明，相比于只優化中繼和只優化軌跡的基準方案，本文所提出的聯合優化方案可以有效提高系統的能量效率，而且在約束條件較為苛刻時，與基準方案的性能差距會更加明顯。因此本文所提算法可以在保證勘察無人機實時通信質量的同時，延長應急通信網絡的整體續航時間。