蜂群無人機自組網多優先級自適應退避算法

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

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

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

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

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

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

1 算法描述

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

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

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

2) 最優競爭窗自適應機制。為了獲得飽和狀態下的最優接入參數，假設各優先級業務存在同一最優競爭窗自適應因子βCWI，算法能根據網絡狀態信息(信道負載、節點數量及信道數目等)自適應調整βCWI，以適應動態網絡變化，從而獲得更好的網絡性能(系統吞吐量最優)。

圖1 MPABA原理Fig.1 Principle of MPABA

(1)

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

(2)

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

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

(3)

2 MPABA性能分析

2.1 退避過程三維Markov鏈模型

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

(4)

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

(5)

圖2 優先級r分組退避狀態的三維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為單個節點有優先級r分組進入相應隊列的概率。

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

又由圖2可得

(10)

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

(11)

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

qr=1-e-λrσ

(12)

根據三維Markov鏈的歸一化條件，一個節點所有狀態概率應滿足

(13)

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

定義τr表示優先級r分組經退避和信道忙閑判定后允許接入的概率，即

(14)

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

(15)

則單個節點的分組接入速率λin為

(16)

2.2 各優先級接入門限求解

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

(17)

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

(18)

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

(19)

(20)

2.3 系統吞吐量

定義S表示系統吞吐量，表示單位時間內信道實際傳輸成功的所有優先級分組比特數之和，即

S=λinNLpacPb

(21)

式中：Lpac為數據分組的比特長度。

2.4 平均MAC時延

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

E[Dr]=E[Tr]σ

(22)

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

(23)

2.5 最優競爭窗自適應因子求解

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

式(21)可表示為

(24)

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

(25)

聯立式(16)和式(25)，可得

(26)

整理式(26)可得

(27)

式中：

(28)

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

(29)

(30)

(31)

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

定義信道負載Gtra表示網絡中所有節點的分組接入網絡的速率之和。

表1 仿真參數設置Table 1 Simulation parameter setting

表2 各業務類型相關參數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，所有節點在該場景中的隨機分布，每個節點隨機選擇目的節點通信，MAC層采用多信道ALOHA協議。仿真結果取2 000次蒙特卡羅實驗的平均值，具體參數設置見表1。

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

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

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

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

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

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

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

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

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

3) MPABA可根據網絡狀況自適應調整βCWI，從而可使系統吞吐量達到最優。

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

4 結 論

本文為FANETs提出并設計了一種多優先級自適應退避算法，旨在實現多業務區分服務并有效改善網絡在重負載下的性能。

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

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