基于匹配博弈的無人機(jī)群多跳中繼路徑優(yōu)選算法*

曾弘揚(yáng)，安思璇

（陸軍工程大學(xué) 通信工程學(xué)院，江蘇 南京 210007）

0 引言

無人機(jī)集群是由眾多無人機(jī)單機(jī)構(gòu)成的群體，基于信息交互和群體智能技術(shù)，可在危險(xiǎn)、惡劣環(huán)境中自主協(xié)同完成多類復(fù)雜任務(wù)[1]。無人機(jī)群在執(zhí)行數(shù)據(jù)采集等集群任務(wù)時(shí)，需要將采集的數(shù)據(jù)及時(shí)準(zhǔn)確地傳輸至遠(yuǎn)距離的地面遙控中心。由于單個(gè)無人機(jī)傳輸距離有限，通常需要多跳中繼以保障傳輸性能[2]。無人機(jī)群具有分布式組網(wǎng)、高機(jī)動性、能量受限等典型特點(diǎn)，因此在局部信息交互下實(shí)現(xiàn)自組織多跳中繼節(jié)點(diǎn)優(yōu)選，同時(shí)盡可能提升無人機(jī)群能量效率是中繼傳輸優(yōu)化必須實(shí)現(xiàn)的目標(biāo)。

匹配博弈理論作為一種數(shù)學(xué)工具[1]，主要用于對具有矛盾的雙邊決策者進(jìn)行建模分析，近年來在協(xié)同頻譜共享[3]、微蜂窩D2D 通信[4]等網(wǎng)絡(luò)模型得到了廣泛關(guān)注，是解決分布式無線資源優(yōu)化的有效方法。中繼節(jié)點(diǎn)優(yōu)選問題很適合利用匹配博弈進(jìn)行建模分析，源節(jié)點(diǎn)和中繼節(jié)點(diǎn)分別基于不同的優(yōu)化目標(biāo)設(shè)計(jì)自身的偏好函數(shù)，構(gòu)建匹配列表，實(shí)現(xiàn)分布式節(jié)點(diǎn)互選。不同于其他博弈模型，匹配博弈的優(yōu)化目標(biāo)一般為穩(wěn)定匹配，非常適合無人機(jī)群這種高動態(tài)網(wǎng)絡(luò)的快速穩(wěn)定優(yōu)化。目前，利用匹配博弈進(jìn)行的中繼選擇研究主要集中在協(xié)同通信[5]、基站選擇[6-8]等場景，典型特點(diǎn)是只需進(jìn)行一跳范圍內(nèi)的節(jié)點(diǎn)優(yōu)選。在多跳中繼傳輸?shù)难芯恐校墨I(xiàn)[9-10]提出了分布式多跳節(jié)點(diǎn)選擇算法，但算法不具穩(wěn)健性，無法適應(yīng)拓?fù)鋭討B(tài)變化的無人機(jī)群協(xié)同網(wǎng)絡(luò)。文獻(xiàn)[11-12]研究了分層匹配模型，但只是簡單地將單層的匹配重復(fù)應(yīng)用至多層網(wǎng)絡(luò)，無法保障多跳中繼傳輸?shù)娜中阅堋?/p>

因此，本文以無人機(jī)集群的網(wǎng)絡(luò)能量效率為優(yōu)化目標(biāo)，基于匹配博弈理論提出了一種分布式多跳中繼路徑優(yōu)選算法。所提算法僅需要鄰域范圍內(nèi)的無人機(jī)位置信息，即可獲得接近全局最優(yōu)的多跳傳輸性能。仿真結(jié)果表明，所提算法能夠適應(yīng)不同的網(wǎng)絡(luò)拓?fù)洌諗垦杆伲浅＿m合高動態(tài)的無人機(jī)群通信場景。

1 系統(tǒng)模型

本文研究的系統(tǒng)模型如圖1 所示。無人機(jī)群在執(zhí)行偵察等數(shù)據(jù)采集任務(wù)時(shí)，源節(jié)點(diǎn)無人機(jī)需要在動態(tài)變化的網(wǎng)絡(luò)拓?fù)渲凶灾鬟x擇合適的多跳中繼路徑，將數(shù)據(jù)及時(shí)回傳給地面遙控中心。假設(shè)網(wǎng)絡(luò)中有N個(gè)有數(shù)據(jù)傳輸需求的源節(jié)點(diǎn)，M個(gè)可提供中繼傳輸?shù)闹欣^節(jié)點(diǎn)。無人機(jī)均裝配半雙工單天線，發(fā)射功率可調(diào)，中繼傳輸采用譯碼轉(zhuǎn)發(fā)方式。本文所提算法需要獲知鄰域范圍內(nèi)無人機(jī)的位置信息，而為了實(shí)現(xiàn)自主飛行控制，集群網(wǎng)絡(luò)中的無人機(jī)均會周期性地在鄰域范圍內(nèi)廣播包含自身地理位置的飛行控制信息。假設(shè)源節(jié)點(diǎn)sn(n=1,2,…,N)的數(shù)據(jù)經(jīng)由K跳傳輸?shù)竭_(dá)地面遙控中心d，即需要依次選擇K-1 個(gè)中繼節(jié)點(diǎn)。為了統(tǒng)一標(biāo)記，將多跳中繼鏈路sn→d上的所有節(jié)點(diǎn)依次記為rn(0),rn(1),…,rn(k)，其中rn(0)表示源節(jié)點(diǎn)sn(0)，rn(K)表示目的節(jié)點(diǎn)d。則多跳中繼鏈路sn→d的傳輸容量[13]為：

圖1 系統(tǒng)模型

所以，全網(wǎng)能量效率最大的多跳中繼路徑選擇優(yōu)化問題可以表示為：

其中，第一條約束條件表示無人機(jī)之間的連接關(guān)系是一對一的，第二條約束條件中表示多跳中繼鏈路sn→d上第k+1 個(gè)節(jié)點(diǎn)能夠正確解調(diào)時(shí)第k個(gè)節(jié)點(diǎn)的最小發(fā)射功率門限，Pmax表示最大發(fā)射功率限制。

在式（6）描述的多跳鏈路優(yōu)選S 問題中，可以利用匹配博弈模型實(shí)現(xiàn)鄰域節(jié)點(diǎn)之間的互選。匹配博弈模型可以表示為：

其中，(S,R) 表示兩組決策者；qi,qj(i∈S,j∈R)表示每一決策者所能匹配的最大節(jié)點(diǎn)數(shù)，稱為匹配配額；?i,?j(i∈S,j∈R)分別表示決策者(S,R)的偏好關(guān)系，用于對另一方的用戶進(jìn)行排序，構(gòu)建匹配偏好列表。可見，構(gòu)建合適的偏好關(guān)系對節(jié)點(diǎn)的匹配選擇非常重要。在無人機(jī)集群網(wǎng)絡(luò)中，節(jié)點(diǎn)一般僅根據(jù)鄰域范圍內(nèi)無人機(jī)的狀態(tài)信息建立偏好關(guān)系，很難優(yōu)選出全局能量效率最優(yōu)的多跳鏈路。因此，本文首先對全局最優(yōu)的多跳中繼節(jié)點(diǎn)位置進(jìn)行了分析證明，并基于此設(shè)計(jì)了匹配博弈中的偏好關(guān)系。

2 能量效率最優(yōu)的中繼節(jié)點(diǎn)位置

假設(shè)網(wǎng)絡(luò)中每個(gè)節(jié)點(diǎn)的解調(diào)信干噪比門限均為γTH，路徑損耗指數(shù)m>0，噪聲方差為σ2，表示節(jié)點(diǎn)rn(k-1)到節(jié)點(diǎn)rn(k)的距離，本文主要考慮大尺度損耗對發(fā)射功率的影響，則：

其中(xn(k),yn(k),zn(k))(k=0,1,…,K-1)表示節(jié)點(diǎn)的地理位置坐標(biāo)。若每個(gè)發(fā)射節(jié)點(diǎn)均以功率傳輸數(shù)據(jù)，則：

其中θn(k,K+1)表示節(jié)點(diǎn)rn(k)到節(jié)點(diǎn)rn(k+1)的向量和源節(jié)點(diǎn)sn到目的節(jié)點(diǎn)d的向量之間的夾角，Drn(0)→rn(K)表示源節(jié)點(diǎn)sn到目的節(jié)點(diǎn)d的直線距離。從式（8）的推導(dǎo)過程可以看出，在多跳中繼鏈路sn→d上，當(dāng)K-1 個(gè)中繼節(jié)點(diǎn)剛好在的K個(gè)均分點(diǎn)位置時(shí)，整條鏈路可以達(dá)到最大的能量效率。本文根據(jù)這個(gè)結(jié)論設(shè)計(jì)了匹配博弈的偏好關(guān)系，尋找sn→d鏈路上距離最優(yōu)中繼節(jié)點(diǎn)最近的無人機(jī)中繼數(shù)據(jù)，僅通過鄰域范圍內(nèi)的位置信息交互實(shí)現(xiàn)了接近全局最優(yōu)的多跳中繼傳輸性能。

3 偏好關(guān)系建模

將多跳傳輸中有數(shù)據(jù)需要發(fā)送的節(jié)點(diǎn)稱為發(fā)送方，即節(jié)點(diǎn)rn(k)(k=0,1,2,…,K-1)；接收數(shù)據(jù)的節(jié)點(diǎn)稱為接收方，即節(jié)點(diǎn)rn(k+1)(k=0,1,2,…,K-1)。在rn(k)→rn(k+1)的節(jié)點(diǎn)匹配博弈中，偏好關(guān)系設(shè)計(jì)如下。

3.1 發(fā)送方的偏好

為了提高全網(wǎng)的能量效率，發(fā)送方在設(shè)計(jì)偏好關(guān)系時(shí)考慮兩個(gè)因素。一個(gè)是傾向于選擇在其一跳范圍內(nèi)的多個(gè)節(jié)點(diǎn)中選擇距離最優(yōu)中繼節(jié)點(diǎn)位置最近節(jié)點(diǎn)；二是在候選節(jié)點(diǎn)中剔除掉距離最優(yōu)中繼節(jié)點(diǎn)過遠(yuǎn)的節(jié)點(diǎn)，以提高匹配效率。因此，發(fā)送方選擇下一跳中繼節(jié)點(diǎn)的偏好規(guī)則為：

發(fā)送方根據(jù)偏好關(guān)系對可選擇的下一跳中繼節(jié)點(diǎn)排序，選擇偏好列表中最優(yōu)的中繼節(jié)點(diǎn)rn(k+1)發(fā)出中繼申請，同時(shí)將的值發(fā)送給選中的節(jié)點(diǎn)。

3.2 接收方的偏好

為了提高全網(wǎng)的能量效率，接收方更傾向于在提出中繼申請的節(jié)點(diǎn)中選擇值最小的發(fā)送方，其偏好規(guī)則為：

接收方根據(jù)上述偏好規(guī)則建立自身的匹配列表，選擇最優(yōu)的發(fā)送方同意其中繼請求。

4 多跳中繼節(jié)點(diǎn)交換匹配算法

基于所設(shè)計(jì)的偏好關(guān)系，本文提出了一種多跳中繼路徑優(yōu)選算法。所提算法采用交換匹配[12]的思想，分為鏈路計(jì)算、匹配發(fā)現(xiàn)和匹配交換3個(gè)階段。同時(shí)，采用多檔功率傳輸，即如果在多跳鏈路匹配過程中某一節(jié)點(diǎn)無法以當(dāng)前發(fā)射功率匹配到合適的下一跳節(jié)點(diǎn)，則該鏈路的源節(jié)點(diǎn)會提高發(fā)射功率重新進(jìn)行多跳匹配嘗試。這樣發(fā)送方能夠通過增大發(fā)射功率擴(kuò)大選擇范圍，保證了源節(jié)點(diǎn)到目的節(jié)點(diǎn)的連通性。無人機(jī)群多跳中繼路徑優(yōu)選算法的具體流程如下。

初始化：集群網(wǎng)絡(luò)中每一個(gè)無人機(jī)在鄰域范圍內(nèi)周期性廣播自己的地理位置信息，設(shè)置功率檔位i=0，設(shè)置跳數(shù)k=0。

步驟1：鏈路計(jì)算

（1）設(shè)置發(fā)射功率檔位i=i+1；

（2）第n個(gè)源節(jié)點(diǎn)根據(jù)當(dāng)前功率檔位、自身和目的基站的位置，判斷所需中繼跳數(shù)，并計(jì)算最優(yōu)中繼節(jié)點(diǎn)的位置。

步驟2：匹配發(fā)現(xiàn)

（1）K=K+1；

（2）發(fā)送方rn(k-1)根據(jù)式（11）的偏好規(guī)則建立下一跳節(jié)點(diǎn)的偏好列表，挑選最優(yōu)節(jié)點(diǎn)發(fā)送匹配申請，同時(shí)將、多跳鏈路中最優(yōu)中繼節(jié)點(diǎn)位置以及功率檔位信息攜帶發(fā)送。

步驟3：匹配交換

（1）接收方rn(k)根據(jù)式（12）進(jìn)行偏好排序，對提交申請的發(fā)送方建立偏好列表，選擇最優(yōu)的發(fā)送方接受匹配申請；

（2）如果接收方已有連接，則根據(jù)式（12）判斷新申請匹配的發(fā)送方效用值是否大于已有連接的效用值，如果是，接收方同意發(fā)送方的匹配請求，匹配結(jié)果進(jìn)行交換；否則，接收方拒絕請求，匹配結(jié)果保持不變；

（3）匹配請求被拒絕的發(fā)送方將依次選擇偏好列表中的次優(yōu)節(jié)點(diǎn)發(fā)送匹配請求；直到發(fā)送方rn(k-1)和接收方rn(k)的匹配關(guān)系穩(wěn)定不變，交換匹配結(jié)束。

（4）如果發(fā)送方所有匹配請求均被拒絕，則通過已建立的鏈路將失敗信息返回給源節(jié)點(diǎn)，重復(fù)步驟1；否則，重復(fù)步驟2，直到sn→d的多跳中繼鏈路匹配成功。

5 仿真結(jié)果與分析

本文從集群規(guī)模、源節(jié)點(diǎn)數(shù)量、中繼節(jié)點(diǎn)數(shù)量、門限因子α共4 個(gè)角度對所提出的多跳鏈路優(yōu)選算法進(jìn)行仿真分析。仿真中，固定源節(jié)點(diǎn)在網(wǎng)絡(luò)左側(cè)邊緣均勻分布，目的節(jié)點(diǎn)在網(wǎng)絡(luò)右側(cè)中點(diǎn)，中繼節(jié)點(diǎn)在網(wǎng)絡(luò)內(nèi)部隨機(jī)分布。如果發(fā)送方已達(dá)到最大發(fā)射功率仍無法形成有效多跳鏈路，則匹配失敗。主要仿真參數(shù)如表1 所示。

表1 仿真參數(shù)表

5.1 網(wǎng)絡(luò)覆蓋范圍對算法性能的影響

仿真中，設(shè)源節(jié)點(diǎn)數(shù)N=4，中繼節(jié)點(diǎn)數(shù)M=50，門限因子α=0.3。圖2（a）、圖2（b）分別為網(wǎng)絡(luò)覆蓋范圍500 m×500 m、2 000 m×2 000 m 時(shí)，基于所提算法4 個(gè)源節(jié)點(diǎn)獲得的多跳傳輸路徑。可以看出，所提算法能夠根據(jù)網(wǎng)絡(luò)覆蓋范圍的大小以不同發(fā)射功率自主匹配多跳路徑。在如圖2（b）所示的遠(yuǎn)距離通信場景中，更愿意通過增加跳數(shù)來提升多跳鏈路的能量效率。

圖2 不同網(wǎng)絡(luò)規(guī)模下的網(wǎng)絡(luò)連接拓?fù)?/p>

5.2 源節(jié)點(diǎn)數(shù)量對算法性能的影響

仿真中，設(shè)網(wǎng)絡(luò)覆蓋范圍為1 000 m×1 000 m，中繼節(jié)點(diǎn)數(shù)M=50，門限因子α=0.3。圖3（a）、圖3（b）、圖3（c）分別為源節(jié)點(diǎn)數(shù)量N為2、4和6 時(shí)基于所提算法源節(jié)點(diǎn)獲得的多跳傳輸路徑。可以看出，源節(jié)點(diǎn)數(shù)量增大后，所提算法依然可以有效支持源節(jié)點(diǎn)尋找到多跳路徑。但是，由于競爭增大，部分鏈路可能由于某個(gè)中繼申請被拒絕而被迫尋找次優(yōu)的路徑，符合算法設(shè)計(jì)預(yù)期。

圖3 不同源節(jié)點(diǎn)數(shù)量下的網(wǎng)絡(luò)連接拓?fù)?/p>

5.3 中繼節(jié)點(diǎn)數(shù)量對算法性能的影響

仿真中，設(shè)網(wǎng)絡(luò)覆蓋范圍為1 000 m×1 000 m，源節(jié)點(diǎn)數(shù)N=4，門限因子α=0.3。圖4（a）、圖4（b）、圖4（c）分別為中繼節(jié)點(diǎn)數(shù)M為8、32 和128 時(shí)基于所提算法源節(jié)點(diǎn)獲得的多跳傳輸路徑。可以看出，當(dāng)中繼節(jié)點(diǎn)數(shù)量較小時(shí)，源節(jié)點(diǎn)難以找到合適的中繼節(jié)點(diǎn)，可能會選擇直連鏈路；當(dāng)中繼節(jié)點(diǎn)數(shù)量增大時(shí)，源節(jié)點(diǎn)會有更高的概率發(fā)現(xiàn)合適的中繼節(jié)點(diǎn)，更傾向于選擇多跳傳輸提升能量效率。

圖4 不同中繼節(jié)點(diǎn)數(shù)量下的網(wǎng)絡(luò)連接拓?fù)?/p>

5.4 門限因子α 對算法性能的影響

仿真中，設(shè)網(wǎng)絡(luò)覆蓋范圍500 m×500 m，源節(jié)點(diǎn)數(shù)N=4，中繼節(jié)點(diǎn)數(shù)M=50。圖5 仿真了不同的α對網(wǎng)絡(luò)能量效率的影響。若α過小，發(fā)送方提出匹配申請的條件過于嚴(yán)格，很難匹配到合適的中繼節(jié)點(diǎn)，最終可能會選擇直傳鏈路，導(dǎo)致能量效率降低；而α過大時(shí)，發(fā)送方提出匹配申請的條件放寬，可能會選到性能較差的中繼節(jié)點(diǎn)，最終也會導(dǎo)致能量效率降低。所以，從圖5 可以看出，門限因子α存在一個(gè)最優(yōu)值。通過多種網(wǎng)絡(luò)拓?fù)涞姆抡姘l(fā)現(xiàn)，α取0.3 附近比較合適。

圖5 不同門限因子α 下的網(wǎng)絡(luò)能量效率

6 結(jié)語

本文以無人機(jī)集群的網(wǎng)絡(luò)能量效率為優(yōu)化目標(biāo)，分析證明了多跳鏈路中最優(yōu)中繼位置的存在性，在此基礎(chǔ)上利用匹配博弈理論，提出了一種基于分布式多跳中繼路徑優(yōu)選算法。所提算法僅需要鄰域范圍內(nèi)的無人機(jī)位置信息，即可獲得接近全局最優(yōu)的多跳傳輸性能。仿真結(jié)果表明，所提算法能夠適應(yīng)不同的網(wǎng)絡(luò)拓?fù)洌沂諗垦杆伲浅＿m合高動態(tài)的無人機(jī)群通信場景。