蜂群無人機自組網(wǎng)多優(yōu)先級自適應退避算法

劉煒倫， 張衡陽， 鄭博， 高維廷

(空軍工程大學 信息與導航學院， 西安 710077)

無人機蜂群作戰(zhàn)的概念是美軍于20世紀90年代末率先提出的。無人機蜂群由若干配備多種任務載荷的低成本小型無人機組成，相比有人戰(zhàn)機，其個體分散性較強，作戰(zhàn)時無人機蜂群可進行專業(yè)化分工，每架無人機的功能不盡相同，因而可以執(zhí)行多種任務。由于無人機蜂群作戰(zhàn)技術對協(xié)同和自主的要求極高，并且需要建立全新的大規(guī)模蜂群指揮控制模式，因此需要解決協(xié)同作戰(zhàn)算法、集群個體間通信、遠程指揮控制等關鍵技術[1-2]。蜂群無人機自組網(wǎng)，也稱飛行自組網(wǎng)(Flying Ad hoc Networks，F(xiàn)ANETs)[3-5]，是無人機蜂群協(xié)同作戰(zhàn)的基礎和前提，性能將直接決定協(xié)同作戰(zhàn)目標能否實現(xiàn)。它的基本思想是：多無人機間的通信不完全依賴于地面控制站或衛(wèi)星等基礎通信設施，而是將無人機作為網(wǎng)絡節(jié)點，各節(jié)點能夠相互轉發(fā)控制指令，交換態(tài)勢感知、情報搜集等數(shù)據(jù)，并自動建立一個Ad hoc網(wǎng)絡。FANETs采用動態(tài)組網(wǎng)、無線中繼等技術實現(xiàn)無人機間的互連互通，具備自組織、自修復能力和高效、快速組網(wǎng)優(yōu)勢，可使無人機蜂群形成一個整體去執(zhí)行作戰(zhàn)任務。

FANETs存在大尺度稀疏分布、多業(yè)務并存、信道質量不穩(wěn)定等問題。隨著網(wǎng)絡負載的增大，易使信道中產(chǎn)生大量擁塞和沖突，導致網(wǎng)絡性能的下降，將無法保障控制指令等高優(yōu)先級業(yè)務低時延、高可靠的服務質量(Quality of Service, QoS)需求[6]。針對上述問題，退避算法作為FANETs媒質接入控制(MAC)協(xié)議的重要組成部分，其設計的關鍵在于有效降低信道中的大量沖突，同時兼顧各優(yōu)先級業(yè)務的不同QoS需求，保證信息傳輸?shù)臅r效性、可靠性。因此，針對FANETs設計一種高效、合理的退避算法是有效提升網(wǎng)絡性能的關鍵。

目前移動Ad hoc網(wǎng)絡廣泛采用的是二進制指數(shù)退避(Binary Exponential Backoff, BEB)算法[7-9]。研究表明，該類算法存在無法根據(jù)網(wǎng)絡負載情況快速選取最佳競爭窗口、在飽和狀態(tài)時網(wǎng)絡性能急劇下降且不能區(qū)分服務類別等不足。近年來，許多研究者針對BEB算法的不足，根據(jù)網(wǎng)絡實際需求提出并設計了多種退避算法。例如，文獻[10]提出一種增強型退避(Enhanced Backoff, EBO) 算法，能夠有效降低重負載下網(wǎng)絡中的沖突，并提高短期公平性，但無法區(qū)分優(yōu)先級，且不能根據(jù)負載情況將競爭窗口收斂到最佳狀態(tài)；文獻[11]提出一種支持QoS的自適應競爭窗口退避算法(Adaptive Contention Window Backoff Algorithm for QoS, Q-ABACW)，根據(jù)分組碰撞概率估計網(wǎng)絡中的不同業(yè)務的活躍節(jié)點數(shù)量并動態(tài)調整各優(yōu)先級競爭窗口，實現(xiàn)了多業(yè)務區(qū)分，但對于大尺度稀疏分布的FANETs，活躍節(jié)點數(shù)量難以準確估計；文獻[12]提出一種區(qū)分業(yè)務優(yōu)先級的自適應退避 (Priority Adaptive Backoff, PAB) 算法，通過實時調整節(jié)點相鄰退避階段的前后轉移概率，為多種優(yōu)先級業(yè)務提供區(qū)分服務，但其通過載波偵聽判定信道忙閑從而決定節(jié)點下一階段退避狀態(tài)的方法并不準確，無法實際應用于FANETs。

針對文獻[10-12]存在的不足并結合FANETs特點，本文提出并設計了一種基于負載反饋和競爭窗口實時更新的多優(yōu)先級自適應退避算法(Multiple Priority Adaptive Backoff Algorithm,MPABA)。本文算法采用忙閑因子自適應機制和最優(yōu)競爭窗自適應機制，通過信道忙閑程度自適應調整各優(yōu)先級的忙閑自適應因子，并依據(jù)網(wǎng)絡狀態(tài)信息自適應調整最優(yōu)競爭窗自適應因子，從而實時動態(tài)更新各優(yōu)先級競爭窗口長度并使其快速收斂到最佳狀態(tài)，實現(xiàn)了多優(yōu)先級業(yè)務區(qū)分服務、改善了網(wǎng)絡在重負載下的性能且能有效保障高優(yōu)先級業(yè)務低時延、高可靠的QoS需求。

1 算法描述

由于FANETs中各優(yōu)先級業(yè)務具有不同的QoS需求，MPABA可通過忙閑因子自適應機制和最優(yōu)競爭窗自適應機制，實現(xiàn)對不同優(yōu)先級業(yè)務的區(qū)分服務和最優(yōu)的系統(tǒng)吞吐量性能。該算法的基本原理如圖1所示，首先對上層產(chǎn)生的業(yè)務分組進行糾錯編碼[13]，然后分別插入各自的優(yōu)先級隊列等待發(fā)送。到達隊首的分組接入信道前需要進行信道忙閑判定，若信道忙閑程度小于其對應的接入門限，分組立即接入信道，反之執(zhí)行退避機制，并根據(jù)忙閑因子自適應機制和最優(yōu)競爭窗自適應機制實時更新競爭窗口長度并使其快速收斂到最佳狀態(tài)。其中，最高優(yōu)先級(優(yōu)先級1)業(yè)務具有嚴格的時效性與可靠性需求，不對其進行接入控制。

該算法主要包含以下2大核心機制：

1) 忙閑因子自適應機制。用節(jié)點接收機在一段時間內收集到的負載數(shù)目量對下一時刻的負載數(shù)目接收值實時預測，并根據(jù)預測值量化信道忙閑程度[14]，然后將結果反饋給接入判定模塊，根據(jù)信道忙閑程度確定各優(yōu)先級業(yè)務不同的忙閑自適應因子從而實現(xiàn)多業(yè)務區(qū)分服務。

2) 最優(yōu)競爭窗自適應機制。為了獲得飽和狀態(tài)下的最優(yōu)接入?yún)?shù)，假設各優(yōu)先級業(yè)務存在同一最優(yōu)競爭窗自適應因子βCWI，算法能根據(jù)網(wǎng)絡狀態(tài)信息(信道負載、節(jié)點數(shù)量及信道數(shù)目等)自適應調整βCWI，以適應動態(tài)網(wǎng)絡變化，從而獲得更好的網(wǎng)絡性能(系統(tǒng)吞吐量最優(yōu))。

圖1 MPABA原理Fig.1 Principle of MPABA

(1)

令i表示優(yōu)先級r分組在第j次退避階段時根據(jù)信道忙閑程度所確定的忙閑自適應因子i∈[1,lr]，其值由式(2)確定，即

(2)

式中：?」表示向下取整。

將i作為競爭窗口調整參數(shù)，構造優(yōu)先級r分組在第j個退避階段的競爭窗口表達式為

(3)

2 MPABA性能分析

2.1 退避過程三維Markov鏈模型

令pr表示優(yōu)先級r的分組到達緩沖區(qū)隊首時經(jīng)信道忙閑判定后不能接入的概率，m表示最大退避次數(shù)。令gr(t)表示優(yōu)先級r的分組在t時刻的忙閑自適應因子，sr(t)表示優(yōu)先級r的分組在t時刻所處的退避階段，br(t)表示優(yōu)先級r的分組在t時刻退避計數(shù)器的值，則三維隨機過程(gr(t),sr(t),br(t))構成如圖2所示的離散三維Markov鏈，其各狀態(tài)穩(wěn)態(tài)概率為

(4)

引入狀態(tài)(0,-1,0)表示發(fā)送緩沖區(qū)隊首恰好為空的概率(即前一分組服務完成時，后一分組還未進入隊首的瞬時狀態(tài))，由圖2可得，節(jié)點退避狀態(tài)的一步轉移概率可表示為

(5)

圖2 優(yōu)先級r分組退避狀態(tài)的三維Markov鏈模型Fig.2 Three-dimensional Markov chain model of backoff stage for priority r traffic

Pr{i,j,k|i,j,k+1}=1

(6)

(7)

Pr{0,-1,0|i,j,0}=1-pr

i∈[1,lr];j∈[0,m)

(8)

Pr{0,-1,0|i,m,0}=1i∈[1,lr]

(9)

式中：qr為單個節(jié)點有優(yōu)先級r分組進入相應隊列的概率。

式(5)表示發(fā)送緩沖區(qū)隊首分組經(jīng)信道忙閑判定后首次執(zhí)行退避的概率；式(6)表示狀態(tài)轉移圖中同一行向左轉移的概率；式(7)表示狀態(tài)轉移圖中分組經(jīng)信道忙閑判定后無法接入信道并根據(jù)式(2)重新確定忙閑自適應因子并進入下一退避階段的概率；式(8)表示分組經(jīng)信道忙閑判定后允許接入信道并回到初始狀態(tài)的概率；式(9)表示分組經(jīng)m次退避后仍不能接入信道，節(jié)點將分組丟棄并回到初始狀態(tài)的概率。

又由圖2可得

(10)

結合式(10)及圖2推導可得

(11)

令λr表示單個節(jié)點中優(yōu)先級r的分組到達率，σ表示單位時隙長度，則在σ內，單個節(jié)點有優(yōu)先級r分組進入相應隊列的概率qr為

qr=1-e-λrσ

(12)

根據(jù)三維Markov鏈的歸一化條件，一個節(jié)點所有狀態(tài)概率應滿足

(13)

根據(jù)式(10)～式(13)可求解圖2中每個狀態(tài)的取值。

定義τr表示優(yōu)先級r分組經(jīng)退避和信道忙閑判定后允許接入的概率，即

(14)

由于采用優(yōu)先搶占式的信道接入策略，節(jié)點發(fā)送端服務器每次僅能服務一個分組，因此可得分組在任一時隙σ能接入信道的概率為

(15)

則單個節(jié)點的分組接入速率λin為

(16)

2.2 各優(yōu)先級接入門限求解

由于接入網(wǎng)絡的分組會在時域、頻域發(fā)生碰撞。因此，分組成功接收需保證在同一條信道上，當前分組與其前后一個分組的發(fā)送間隔時間同時大于其信道傳輸時延Tsend。對于單個信道，假設接入網(wǎng)絡中的分組在間隔時間上服從參數(shù)為λper=Nλin/M(N為節(jié)點數(shù)量，M為信道數(shù)量)的負指數(shù)分布[15]。定義Pb表示分組成功接收概率，則

(17)

令Nb為分組拆分后的突發(fā)包個數(shù)，Mb為恢復原分組所需最少突發(fā)個數(shù)。根據(jù)糾錯編碼機制原理，可得分組成功傳輸概率ppac為

(18)

假設最高優(yōu)先級業(yè)務所要求的最低傳輸成功概率為99%，則令ppac=99%，聯(lián)立式(17)～式(18)可得當前網(wǎng)絡所對應的信道負載為Gmax。

(19)

(20)

2.3 系統(tǒng)吞吐量

定義S表示系統(tǒng)吞吐量，表示單位時間內信道實際傳輸成功的所有優(yōu)先級分組比特數(shù)之和，即

S=λinNLpacPb

(21)

式中：Lpac為數(shù)據(jù)分組的比特長度。

2.4 平均MAC時延

令E[Dr]表示優(yōu)先級r分組的平均MAC時延，即分組到其相應優(yōu)先級隊首至該分組接入信道前所需時間的平均值，表示為

E[Dr]=E[Tr]σ

(22)

式中：E[Tr]為優(yōu)先級r的分組成功傳輸所需的平均時隙數(shù)，可表示為

(23)

2.5 最優(yōu)競爭窗自適應因子求解

為提高接入方案的吞吐量性能，通過式(21)求解可使S達到最優(yōu)的λin，并通過λin求解最優(yōu)競爭窗自適應因子βCWI的值，從而通過自適應調整βCWI，使S達到最優(yōu)。

式(21)可表示為

(24)

通過求吞吐量S關于λin的偏導數(shù)，令?S/?λin=0，易知式(24)存在唯一極大值點可使S達到最大。解得該極大值為

(25)

聯(lián)立式(16)和式(25)，可得

(26)

整理式(26)可得

(27)

式中：

(28)

將式(28)進行整理，并對其取以e為底的對數(shù)可得

(29)

(30)

(31)

由式(27)和式(31)可知，最優(yōu)競爭窗自適應因子βCWI與信道負載(網(wǎng)絡中所有節(jié)點分組接入速率之和)Gtra、信道數(shù)目M直接相關。在表1和表2的參數(shù)設置下，得到βCWI與信道負載、信道數(shù)目的關系圖3。由圖3可知，相同信道數(shù)目下的βCWI與信道負載呈正比關系；信道負載相同的情況下βCWI與信道數(shù)目呈反比關系。

定義信道負載Gtra表示網(wǎng)絡中所有節(jié)點的分組接入網(wǎng)絡的速率之和。

表1 仿真參數(shù)設置Table 1 Simulation parameter setting

表2 各業(yè)務類型相關參數(shù)Table 2 Related parameters of each priority type

圖3 βCWI與Gtra及M的關系Fig.3 Relation of βCWI with Gtra and M

3 仿真分析

下面采用OMNeT++仿真平臺對MPABA的性能進行仿真分析。仿真場景大小設置為200 km×200 km×10 km，所有節(jié)點在該場景中的隨機分布，每個節(jié)點隨機選擇目的節(jié)點通信，MAC層采用多信道ALOHA協(xié)議。仿真結果取2 000次蒙特卡羅實驗的平均值，具體參數(shù)設置見表1。

根據(jù)FANETs的實際應用需求，對MPABA設定4種優(yōu)先級業(yè)務，其中優(yōu)先級1為最高優(yōu)先級，其分組到達率固定為60 packet/s，優(yōu)先級2、3、4的分組到達率之比為1∶3∶6。在設定優(yōu)先級1分組最低成功傳輸概率為99%的條件下，在表1的參數(shù)設置下解得Gmax=1 875 packet/s，其他相關參數(shù)如表2所示。

圖4 信道負載對MPABA性能的影響Fig.4 Influence of channel loads on performance of MPABA

首先對MPABA性能的數(shù)學模型進行仿真驗證。不同信道負載下的平均MAC時延和系統(tǒng)吞吐量的理論計算和仿真結果如圖4所示。由圖4(a)可以看出，當信道處于輕負載時，各優(yōu)先級的平均MAC時延均相對較低，表明此時信道負載小于各優(yōu)先級接入門限，各優(yōu)先級業(yè)務均能保證良好的時延性能；在重負載時，優(yōu)先級1業(yè)務MAC時延保持穩(wěn)定且在2 ms以內，其余各優(yōu)先級業(yè)務的時延均顯著增大，表明此時開始執(zhí)行退避算法，由于各優(yōu)先級業(yè)務每次退避時的忙閑自適應因子不同，導致不同業(yè)務每次選取的競爭窗口長度不同，從而實現(xiàn)了區(qū)分服務。由圖4(b)可以看出，在重負載時，MPABA能使吞吐量達到最大且穩(wěn)定在最大值6.7 Mbit/s，表明MPABA可自適應調整βCWI，使吞吐量達到最優(yōu)值。由圖4可知，MPABA的理論計算結果和仿真實驗數(shù)據(jù)基本吻合，表明理論計算結果準確有效。

下面將本文提出的MPABA與Q-ABACW[11]、PAB算法[12]的性能進行仿真實驗對比，其中PAB算法、Q-ABACW均包含4種與表2相同的優(yōu)先級業(yè)務類別，在相同仿真參數(shù)設置下得到仿真對比結果如圖5所示。

由圖5(a)、(b)可知，MPABA雖然對低優(yōu)先級業(yè)務的時延保障能力較差，但能為高優(yōu)先級業(yè)務提供嚴格的時效性保障。由圖5(c)可知，相比MPAB、Q-ABACW，MPABA在重負載時能夠使系統(tǒng)吞吐量保持最優(yōu)且穩(wěn)定，具有明顯的性能優(yōu)勢，可為FANET提供較高的系統(tǒng)容量需求。

圖5 MPABA、PAB算法與Q-ABACW性能對比Fig 5 Comparison of performance among MPABA, PAB algorithm and Q-ABACW

綜合以上仿真結果，可以得到以下結論：

1) 當信道輕負載時，MPABA中各優(yōu)先級業(yè)務均可獲得較好的QoS性能。

2) 當信道重負載時，低優(yōu)先級的分組需執(zhí)行退避算法，根據(jù)信道忙閑程度確定各自的忙閑自適應因子并自適應調整競爭窗口大小，從而將沖突維持在可控范圍內，為高優(yōu)先級的分組提供嚴格的時效性需求。

3) MPABA可根據(jù)網(wǎng)絡狀況自適應調整βCWI，從而可使系統(tǒng)吞吐量達到最優(yōu)。

4)對比PAB算法、Q-ABACW，MPABA能為高優(yōu)先級業(yè)務提供更好的服務，并使得系統(tǒng)吞吐量達到最優(yōu)。

4 結 論

本文為FANETs提出并設計了一種多優(yōu)先級自適應退避算法，旨在實現(xiàn)多業(yè)務區(qū)分服務并有效改善網(wǎng)絡在重負載下的性能。

1) 能根據(jù)信道忙閑程度和網(wǎng)絡狀態(tài)參數(shù)自適應調整各優(yōu)先級競爭窗口長度，從而可將競爭窗口收斂到最佳狀態(tài)，為不同優(yōu)先級業(yè)務提供了不同的QoS保障能力，得到了最優(yōu)的系統(tǒng)性能。

2) 仿真實驗驗證了所建模型準確有效，與Q-ABACW和PAB算法相比，算法在吞吐量性能上具有明顯的優(yōu)勢。