災后無人機不確定偏好序下穩定中繼選擇方法

徐子蒙，王博文，云 霄，王曉琳

(1.中國礦業大學 信息與控制工程學院，江蘇 徐州 221116；2.中國礦業大學 礦業工程學院，江蘇 徐州 221116)

2019年，應急管理部發布《應急管理信息化發展戰略規劃框架》，要求整合無人機(Unmanned Aerial Vehicle，UAV)等空基網絡資源，實現對災害事故易發、多發、頻發區域的全方位、立體化、無盲區的災情監測與通信覆蓋。無人機憑借靈活度高、操控方便和可重構性強等特點，能快速保障通信基礎設施損毀的受災地區用戶恢復正常通信，可更為高效地完成應急通信任務，因此在應急通信中發揮越來越重要的作用[1-4]。無人機除了作為空中基站覆蓋因基礎設施損毀產生的通信盲點，還可以作為機會中繼改善系統通信性能。考慮到無人機中繼輔助基站、車輛和無人機等傳輸信息，具有擴大通信范圍，提高系統吞吐量等優勢，國內外學者對此開展了一系列研究[5-9]，相關工作的優劣處對比如表1所示。無人機作為中繼能增強通信和網絡性能，應用日趨廣泛，災害事故對極端環境下應急通信網絡快速重組與災情信息實時回傳提出了嚴峻挑戰，因此，在應急通信場景中考慮無人機中繼提高應急通信保障能力十分必要。

表1 無人機中繼相關工作

匹配理論作為分析用戶互利關系的數學工具，被廣泛應用于分布式無線資源分配與中繼選擇算法設計中。文獻[10]在D2D(Device-to-Device)通信場景中，利用人際社會關系建立社會穩定匹配模型，實現物理層安全性和吞吐量性能的折中。文獻[11]在無人機輔助的車聯網中，提出基于GS算法的無人機任務分配方法，最大化用戶的利潤。在災后應急通信場景中，為了保障救援人員及時有效溝通，允許多個D2D對復用同一中繼無人機，但同時也帶來同群效應的問題，因此前述文獻中的一對一匹配方法不適用。文獻[12]提出了一種交換操作來解決多對一匹配中的同群效應，可文獻中提出的算法是集中式的，不適用于分布式場景中。文獻[13]提出了雙邊交換穩定匹配算法，在具有同群效應的動態分布式網絡中找到穩定匹配方案。

上述文獻的匹配過程需要雙邊主體間的連接權重等準確信息，而在現實情況中由于決策環境的模糊性和復雜性，匹配雙邊中一邊更容易獲得另一邊個體的不精確的序區間偏好信息，因此，有學者對基于不完全偏好序、不確定偏好序以及弱偏好序等信息的雙邊匹配問題展開研究[14-17]。文獻[15]針對偏好序值不完全情況下的婚姻匹配問題，采用近似算法得到穩定匹配的數量并提高近似比。文獻[16]通過求解弱穩定匹配、α-穩定匹配等的多目標優化模型，獲得序區間偏好信息下的最優雙邊穩定匹配。文獻[17]將同群效應引入不確定偏好下的雙邊匹配模型中，實現最大化滿意度并最小化個體間差異的雙目標。針對無人機動態飛行且軌跡未知的情況，文獻[18]提出了一種中繼無人機實時位置調整方法，確保信息可靠傳輸至地面站。文獻[19]提出了一種在線分布式的方法解決了動態網絡中的中繼選擇和信道選擇問題。受上述文獻啟發，結合實際的災后應急場景，比如地震、火災等災害事故導致房屋建筑的坍塌等，產生的遮蔽、濃煙造成應急救援人員難以獲取用戶的準確位置信息等動態不確定性，展開了災后無人機不確定偏好下雙邊穩定匹配中繼選擇方法的研究工作，主要研究內容如下：

(1) 建立災后無人機輔助的D2D用戶成功傳輸優化模型，最大化D2D用戶的傳輸成功率。考慮網絡的不確定性和該問題是NP難問題，很難直接求解，因此將優化問題轉為D2D用戶中繼無人機選擇問題。

(2) 根據D2D用戶和中繼無人機的不確定偏好序建立D2D用戶和中繼無人機的偏好列表，首先利用多對一雙邊穩定匹配理論解決中繼無人機選擇問題，然后給出了文中的算法步驟、穩定性分析和計算復雜度分析。

(3) 仿真結果表明，筆者所提的帶有同群效應的中繼無人機選擇算法下D2D用戶具有很好的數據成功傳輸性能。與窮舉算法、一對一匹配算法以及隨機中繼選擇算法對比，驗證了文中方法的有效性。

1 系統模型

1.1 網絡模型

如圖1所示，無人機在空中執行災情勘察、信息采集等任務，地面D2D用戶(如救援人員、指揮人員等)可以選擇無人機協作通信。假設系統中有M架無人機，表示為U={U1，…，Um，…，UM}，有K個D2D對，表示為K={1，…，k，…，K}，其中一對D2D用戶包含一個D2D發射端和一個D2D接收端，分別表示為S={S1，…，Sk，…，SK}和D={D1，…，Dk，…，DK}。任務傳輸周期劃分成T個離散的等間隔時隙，并表示為{1，…，t，…，T}，時隙長度為τ，并假設每個時隙長度足夠短，在單個時隙內，D2D對可獲得的中繼UAV和網絡中各節點的位置大致不變。LUm(t)=(xUm(t)，yUm(t)，zUm(t))表示無人機Um的實時位置，則無人機Um在下一時隙t+1的位置為LUm(t+1)=LUm(t+1)+vτ·ωUm(t)，v為無人機的飛行速度，ωUm(t)表示無人機Um在時隙t的飛行方向。

圖1 無人機輔助的應急通信場景

假設系統中信道數與中繼無人機數目一致。考慮到災后應急場景對遠距離傳輸的實際需求，為了便于分析中繼選擇算法的性能，文中假設同一D2D對發射端和接收端之間的傳輸數據率較低，均需要通過無人機中繼輔助傳輸。如果多個D2D對有相同的無人機選擇，無人機采用時分多址接入(Time Division Multiple Access，TDMA)技術來服務這些D2D對，因此不同的無人機服務的D2D對之間的干擾得以避免。

1.2 傳輸模型

Pavg，mr(t)=PLoS，mr(t)PLLoS，mr(t)+PNLoS，mr(t)PLNLoS，mr(t) ，

(1)

假設每架無人機或每個D2D用戶裝備單根天線，一架無人機可以協助多個D2D用戶傳輸數據，一個D2D對最多只能選擇一架無人機協助傳輸數據。當存在多個D2D用戶選擇相同的無人機時，D2D用戶機會均等地共享信道資源。D2D對k有大小為fk的數據需要傳輸，數據包逐幀傳輸，每幀的長度均相等。一幀分為2個階段：階段1，發射端Sk將數據傳輸至中繼無人機Um；階段2，中繼無人機Um將數據傳輸至接收端Dk。在中繼傳輸模式下，采用解碼轉發(Decode-and-Forward，DF)協議進行數據傳輸。因此，在t時隙，D2D對k的發射端Sk通過無人機Um傳輸至接收端Dk的數據速率為

(2)

2 問題表述

網絡的動態特性導致數據速率在不同時隙可能不同，從而成功傳輸的D2D對數量可能不同，因此，通過優化實時中繼無人機分配最大化D2D用戶的平均總傳輸成功率，即最大化網絡中傳輸成功的D2D對數量與D2D對總數比值在整個傳輸周期的平均值：

(3)

s.t.amk(t)∈{0，1}，bmk(t)∈{0，1} ，

(4)

(5)

其中，限制條件式(4)表示amk(t)和bmk(t)為二進制數。限制條件式(5)表示每個D2D對至多能選擇一架無人機作為中繼，每架無人機至多可協助q0(Um)個D2D對傳輸數據。

該優化問題是NP難問題，并且解決難點有以下幾個方面：首先，由于無人機動態飛行，位置實時變化，因此最佳無人機中繼分配是隨時間變化而變化的；其次，無人機的飛行軌跡是由它們的任務決定的，對于地面用戶來說是未知的，因此，離線規劃方法不可取，需要在線方法。下面將優化問題轉為中繼選擇的優化進行求解。

3 實現方法

在經典的匹配模型中，匹配雙方可以根據確定的偏好列表信息決定匹配策略，但在災后場景中，無人機和D2D用戶的動態位置可能導致匹配策略的不確定性，因此，僅根據在某些時刻的傳輸性能得到的匹配策略是不準確的，要分析基于偏好不確定性匹配博弈的中繼無人機選擇問題。針對多對一雙邊匹配中存在同群效應的問題，需進一步對相應的匹配結果進行交換操作解決。

3.1 確定偏好序下的雙邊匹配

(6)

(7)

為了解決式(3)中的問題，筆者運用博弈論中雙邊匹配知識。匹配理論允許每個參與者(D2D對和無人機)定義各自的效用，可以分布式解決中繼無人機選擇問題。受經濟學中畢業生與實習醫院相匹配問題[24]的啟發，本文將D2D用戶的中繼無人機選擇問題定義為多對一匹配博弈，即雙邊匹配是在D2D對集合中的元素與中繼無人機集合中的元素之間進行多對一的匹配。傳統的匹配問題需要匹配雙方建立完整精確的偏好列表，實際情況中，災后環境的復雜性、無人機和D2D用戶的移動性以及參與者數量較多等因素，容易導致匹配雙方的偏好列表具有不完整性[14]和模糊性[17]，因此提出基于不完整不確定偏好序的多對一匹配算法。先給出如下多對一匹配定義：

定義1給定兩個不同的有限參與集合K和U，ω定義為多對一匹配關系，一個匹配是滿足以下條件的雙映射ω：K∪U→K∪U∪?：① ?k∈K，ω(k)?U∪?，|ω(k)|≤1；② ?Um∈U，ω(Um)?K∪ ?，|ω(Um)|≤q0；③ ?k∈K，?Um∈U，ω(k)=Um?ω(Um)=k。

為了得到匹配結果ω，無人機與D2D用戶雙方根據偏好關系對另一方降序排列形成偏好列表N，匹配的對象在各自偏好列表中越靠前，相應地在系統中獲得的利益也越大。根據上述雙邊匹配模型，提出基于不確定偏好序的多對一匹配算法(UMA)。在每個時隙，D2D用戶通過預測中繼無人機的位置來計算傳輸性能，得到不確定偏好序，在此基礎上綜合評估生成相應的偏好列表。D2D用戶根據偏好列表，對中繼無人機進行排序和選擇。中繼無人機收到D2D用戶的請求后，在滿足配額約束要求下，接受最佳候選者的匹配請求，拒絕其他的D2D用戶。被接受的D2D用戶停止匹配過程，而被拒絕的D2D用戶繼續向次優中繼無人機發出匹配請求。過程不斷迭代，直到D2D用戶被中繼無人機匹配或拒絕，由于偏好列表可能不完整，匹配結果可以是部分匹配。相應的過程見算法1。

算法1基于不完整不確定偏好序的多對一匹配算法(UMA)。

輸入：U，K，t，q0(Um)。

loop fort=1，…，T

fork∈K和Um∈U分別對在各自探測范圍內的UAV和D2D do

構建偏好列表Nk和Nm；

while ?k∈K，|ω(k)|=0，且Nk≠? do

for 所有k∈Kdo

向位于Nk第一位的中繼無人機Um*發送請求；

將bm*k設置為1，更新Nk=Nk/Um*；

end for

for 所有Um∈Udo

if 當前請求數量>q0(Um) then

Um根據Nm，接受q0(Um)個D2D對，拒絕其他的D2D對；

被拒絕的D2D對bm*k值設置為0；

else

Um接受當前所有的請求者；

end if

end for

end while

end for

for未匹配的k∈K和Um∈Udo

等待t+1時隙用戶動態加入

end for

返回匹配結果ω(t)；

end loop

輸出：匹配結果ω(t)。

基于不確定偏好序的多對一匹配算法中參與匹配的D2D對和無人機的數量分別為K和M，在最壞情況下，任意D2D對的候選中繼集合中都包含所有的無人機，所有的中繼無人機對D2D用戶的偏好都不滿足中繼無人機的要求，在這種情況下參與匹配的D2D用戶需要不斷地向其他中繼無人機發送請求并被拒絕，因此算法的最壞時間復雜度為O(MK)，在系統整個任務傳輸周期算法的最壞時間復雜度為O(TMK)。

復用同一中繼無人機的D2D對數量會根據算法的匹配結果不同而不同，導致D2D用戶的傳輸速率發生變化，相應的偏好列表改變，因此D2D用戶可能會出現相較于當前的匹配對象，更喜歡其他中繼無人機的情況，故不確定偏好序下的多對一匹配算法的匹配結果是不穩定的。為了得到穩定的匹配結果，D2D用戶既要關注無人機的選擇情況，也要關注復用同一無人機中繼的D2D對情況，即需要考慮同群效應的影響。

3.2 帶有同群效應的中繼無人機選擇算法

由定義2可知，交換匹配是在交換限制對之間進行的。交換后，所有參與交換的D2D對的傳輸速率不會降低，而至少其中一個D2D對的傳輸速率會增加，這同時也避免了在等價匹配之間循環。交換操作在效用值的基礎上進行，基于預測范圍內的速率增加作為交換條件體現出傳輸過程中的不確定性。

定義3對于多對一雙邊匹配ω，如果不存在交換限制對，則稱匹配ω是雙邊交換穩定的。

雙邊交換穩定性概念與傳統穩定性概念[24]相比有所不同，這與D2D對和中繼無人機根據實際匹配狀態動態的改變偏好策略有關。如前所述，同群效應的存在使得匹配結果不穩定，需要進行交換匹配來消除同群效應的影響。然而，在分布式方法中，并不能像集中式方法那樣直接對交換限制對中的用戶進行交換[13]。因此，提出算法2，即帶有同群效應的中繼無人機選擇算法(UMPA)，對算法1中匹配結果ω(tn)的交換限制對迭代完成每個交換操作，最終得到雙邊交換穩定匹配結果，相應的過程見算法2。

算法2帶有同群效應的中繼無人機選擇算法(UMPA)。

輸入：算法1中匹配結果ω(t)，K，U，q0(Um)。

初始化D2D對k向k′發送交換請求的次數，即Ckk′=0；

Repeat

每個D2D對k∈K搜索另一個D2D對k′∈{K/k}以形成交換限制對；

if(k，k′)形成交換限制對，并滿足Ckk′+Ck′k≤2 then

根據算法1更新匹配結果ω(t)，Ckk′=Ckk′+1；

else

保持當前的匹配狀態；

end if

直到當前匹配中不存在任何交換限制對；

end Repeat

輸出：更新后的匹配結果ω(t)。

在算法2中，將Ckk′表示為D2D對k向k′發送交換請求的次數，且k最多可與k′交換2次，這避免了乒乓效應，保證了算法收斂[13]。當前匹配中不存在任何交換限制對時，交換匹配過程結束，更新匹配結果ω(t)。下面分析算法的穩定性和計算復雜度。

①穩定性：提出的算法最終得到的匹配ω是雙邊交換穩定的。

證明：假設最終得到的匹配結果ω不是雙邊交換穩定的，則至少存在一個交換限制對(k，k′)，但雙邊交換穩定匹配中繼選擇算法在存在交換限制對的情況下是不會終止的，因此，該匹配結果ω不是最終結果，與假設條件沖突。因此，文中所提算法得到的匹配是雙邊交換穩定的。

4 仿真分析

使用MATLAB R2015a工具對提出的算法進行100次獨立重復仿真實驗仿真，并采用與其他方案對比的方式評價筆者所提算法的性能。D2D對隨機分布在3 km×3 km區域內，發射端與對應的接收端之間的距離隨機取值于(100 m，200 m)以內，且發射端與接收端用戶每個時隙隨機在(1 m，2 m)范圍內移動。無人機隨機選擇飛行方向，且不飛出規定區域。部分仿真參數設置如表1所示，與郊區環境不同[18]，考慮城市環境，綜合分析城市地形和建筑高度，將UAV飛行高度設置為[100 m，500 m]。

表2 實驗仿真參數

圖2 D2D用戶傳輸成功率隨中繼無人機數量變化的關系

圖2是在K=50時D2D用戶傳輸成功率隨中繼無人機數量M的變化曲線。圖3是在M=10時D2D用戶傳輸成功率隨D2D對數量K的變化曲線。圖2和圖3中D2D用戶傳輸數據期望值為0.5 MB，多對一匹配算法中無人機配額設置為5。由圖2可知，隨著中繼無人機數量的增加，中繼無人機協作的D2D對數量增加，并且D2D用戶選擇性能更優的中繼提高傳輸成功率的機會更大，D2D用戶傳輸成功率隨著中繼無人機數量的增加而增加。由于偏好列表不完整，中繼無人機數量達到50之后，EA算法和UMPA算法的D2D用戶傳輸成功率逐漸接近1。EA算法從D2D用戶選擇中繼無人機的所有情況中得到最佳的分配結果，因此D2D用戶傳輸成功率最高。文中所提算法能夠實現D2D用戶和中繼無人機間的多對一匹配，能讓更多的D2D用戶同時進行通信，因此D2D用戶傳輸成功率高于OM算法。RRS算法雖然是多對一匹配算法，但是RRS算法忽略了用戶偏好的指向性，與文中所提算法相比，更易于為D2D用戶分配通信質量差的中繼無人機，因此D2D用戶傳輸成功率低。當M=30時，UMPA算法的D2D用戶傳輸成功率低于EA算法約7%，高于UMA算法1約12%、OM算法約52%和RRS算法約533%。從圖3中可知，隨著D2D用戶數量的增加，D2D用戶傳輸成功率呈遞減的趨勢。原因是D2D用戶傳輸成功率為成功傳輸的D2D對數與D2D對總數的比值，當中繼無人機可協助的D2D對數一定時，D2D用戶數量增多，傳輸成功率降低。當K=35時，UMPA算法得到的D2D用戶傳輸成功率低于EA算法約30%，高于UMA算法約25%、OM算法約79%和RRS算法約462%。

圖3 D2D用戶傳輸成功率隨D2D對數量變化的關系

圖4 D2D用戶傳輸成功率隨傳輸數據期望值變化的關系

圖4是在K=50，M=10的條件下D2D用戶傳輸成功率隨傳輸數據期望值的變化曲線。多對一匹配算法中無人機配額設置為5。D2D用戶傳輸數據期望值越大，對傳輸速率的要求越高，EA算法和多對一匹配算法下的D2D用戶傳輸成功率逐漸減小。多對一匹配中受同群效應影響，D2D用戶的平均傳輸速率會小于OM算法中的D2D用戶的平均傳輸速率，滿足成功傳輸要求的D2D用戶減少，而OM算法中不存同群效應，D2D用戶的平均傳輸速率相對較高，滿足成功傳輸要求的D2D用戶數相等，因此傳輸成功率保持不變。當數據期望值為0.5 MB時，UMPA算法得到的D2D用戶傳輸成功率低于EA算法約60%，高于UMA約19%、OM算法約115%和RRS算法約746%。

圖5和圖6是在K=50，M=10的條件下D2D用戶傳輸成功率分別隨無人機配額q0和探測范圍的變化曲線。D2D用戶傳輸數據期望值為0.5 MB。從圖5中可知，筆者所提算法的D2D用戶傳輸成功率隨著無人機配額的增加先增大后減小，原因是當無人機配額小于5時，隨著無人機配額數的增加，無人機可協助的D2D用戶數越多，而D2D對總數一定，D2D用戶傳輸成功率上升。當無人機配額大于5時，無人機可協助的D2D對數超過網絡中D2D對總數，多對一匹配算法的D2D用戶的傳輸速率隨著相關的D2D用戶增多而減小，滿足成功傳輸要求的D2D用戶減少，傳輸成功率降低。EA算法包含滿足無人機配額約束下D2D對所有可能的中繼無人機選擇情況，因此傳輸成功率最高。OM算法中不考慮無人機配額限制，因此傳輸成功率保持不變。特別地，當無人機配額為1時，多對一匹配算法退化為一對一匹配算法。當q0=5時，UMPA算法得到的D2D用戶傳輸成功率低于EA算法約37%，高于UMA約10%、OM算法約170%和RRS算法約896%。圖6中，隨著無人機與D2D裝備雷達探測范圍的擴大，偏好信息越完整，多對一算法下參與數據傳輸的D2D用戶增多，D2D用戶傳輸成功率上升。OM算法中無同群效應，匹配到中繼無人機的D2D用戶數據速率高，因此在探測范圍為1 500 m后D2D用戶傳輸成功率穩定保持在0.2左右。當探測范圍為 2 000 m 時，UMPA算法得到的D2D用戶傳輸成功率低于EA算法約20%，高于UMA約13%、OM算法約249%和RRS算法約221%。

圖5 D2D用戶傳輸成功率隨無人機配額變化的關系

圖6 D2D用戶傳輸成功率隨探測范圍變化的關系

進一步分析實驗結果，EA算法搜索D2D用戶選擇中繼無人機的所有情況，并從中得到最佳的分配結果，因此D2D用戶傳輸成功率最高。RRS算法能在極短的決策時間內給出中繼決策方案，適用于網絡拓撲快變場景，但由于隨機選擇忽略了用戶偏好的指向性，且在偏好列表不完整的情況下，極有可能匹配到傳輸成功概率較低的鏈路，難以實現問題的最優化，因此D2D用戶傳輸成功率較低。OM算法考慮了用戶偏好的指向性，且算法中不存在同群效應，因此單個D2D用戶的數據速率高，但是匹配成功的用戶少，多個D2D用戶無法傳輸，導致總的傳輸成功率低。UMA算法和UMPA算法中存在同一時隙多個D2D用戶均等分享同一無人機資源的情況，單個D2D用戶的數據速率會低于OM算法。UMPA算法中考慮了同群效應，通過交換匹配保證了結果的穩定性，進一步優化了D2D用戶傳輸成功率，因此算法性能優于UMA算法。綜上所述，相較于EA算法，筆者所提算法復雜度更低。與RSS算法相比，所提算法的匹配結果具有穩定性，且能得到較高的D2D用戶傳輸成功率。對比于OM算法，所提算法下中繼無人機利用率高，能使用較少的中繼無人機得到較高的D2D用戶傳輸成功率。因此，筆者所提算法性能是優于其他對比方法的，且更能滿足動態應急通信場景的需求。

5 結束語

筆者研究了災后應急通信場景中D2D通信系統的無人機輔助中繼選擇問題。考慮網絡中無人機的軌跡未知和D2D用戶動態移動性等導致的不確定因素，首先提出一種基于不確定偏好序的帶有同群效應的多對一匹配中繼選擇算法，并通過交換匹配消除同群效應的影響，然后從穩定性和復雜度等方面綜合分析算法的性能。從仿真結果上看，筆者提出的算法得到的D2D用戶傳輸成功率雖然低于窮舉算法的傳輸成功率，得到次優的結果，但是所提算法的計算復雜度較窮舉算法大幅度降低，并且所提算法允許同一中繼無人機在同一時隙協作多對D2D用戶進行通信，保障救援人員及時有效溝通。總體來說，所提算法具有復雜度低、穩定性強和無人機利用率高的性能優勢，更適用于應急動態分布式場景。