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

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

(空軍工程大學(xué) 信息與導(dǎo)航學(xué)院， 西安 710077)

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

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

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

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

1 算法描述

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

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

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

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

圖1 MPABA原理Fig.1 Principle of MPABA

(1)

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

(2)

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

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

(3)

2 MPABA性能分析

2.1 退避過程三維Markov鏈模型

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

(4)

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

(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為單個(gè)節(jié)點(diǎn)有優(yōu)先級r分組進(jìn)入相應(yīng)隊(duì)列的概率。

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

又由圖2可得

(10)

結(jié)合式(10)及圖2推導(dǎo)可得

(11)

令λr表示單個(gè)節(jié)點(diǎn)中優(yōu)先級r的分組到達(dá)率，σ表示單位時(shí)隙長度，則在σ內(nèi)，單個(gè)節(jié)點(diǎn)有優(yōu)先級r分組進(jìn)入相應(yīng)隊(duì)列的概率qr為

qr=1-e-λrσ

(12)

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

(13)

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

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

(14)

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

(15)

則單個(gè)節(jié)點(diǎn)的分組接入速率λin為

(16)

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

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

(17)

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

(18)

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

(19)

(20)

2.3 系統(tǒng)吞吐量

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

S=λinNLpacPb

(21)

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

2.4 平均MAC時(shí)延

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

E[Dr]=E[Tr]σ

(22)

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

(23)

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

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

式(21)可表示為

(24)

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

(25)

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

(26)

整理式(26)可得

(27)

式中：

(28)

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

(29)

(30)

(31)

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

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

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

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

圖3 βCWI與Gtra及M的關(guān)系Fig.3 Relation of βCWI with Gtra and M

3 仿真分析

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

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

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

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

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

由圖5(a)、(b)可知，MPABA雖然對低優(yōu)先級業(yè)務(wù)的時(shí)延保障能力較差，但能為高優(yōu)先級業(yè)務(wù)提供嚴(yán)格的時(shí)效性保障。由圖5(c)可知，相比MPAB、Q-ABACW，MPABA在重負(fù)載時(shí)能夠使系統(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

綜合以上仿真結(jié)果，可以得到以下結(jié)論：

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

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

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

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

4 結(jié) 論

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

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

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