帶有時(shí)間約束的機(jī)載自組網(wǎng)自適應(yīng)退避算法

趙瑋, 鄭博, 張衡陽, 劉煒倫

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

機(jī)載自組網(wǎng)(Airborne Ad hoc Network)是利用航空通信和移動Ad hoc網(wǎng)絡(luò)技術(shù),通過無線信道將一定空域內(nèi)的各種飛行器互聯(lián)互通,構(gòu)成的一個(gè)分布式、無中心的信息傳輸網(wǎng)絡(luò),具有部署快速、組網(wǎng)靈活、抗毀性強(qiáng)等優(yōu)勢[1-4]。機(jī)載自組網(wǎng)存在網(wǎng)絡(luò)拓?fù)淇焖賱討B(tài)變化、多優(yōu)先級業(yè)務(wù)并存、信道資源有限等問題,隨著網(wǎng)絡(luò)負(fù)載持續(xù)增大,易造成信道中發(fā)生大量擁塞和沖突,導(dǎo)致網(wǎng)絡(luò)性能急劇下降,無法保障指揮控制指令、武器協(xié)同信息等高優(yōu)先級業(yè)務(wù)低時(shí)延、高可靠的服務(wù)質(zhì)量(quality of service,QoS)[5-7]。針對這些問題,機(jī)載自組網(wǎng)的退避算法作為隨機(jī)競爭類媒質(zhì)接入控制(medium access control,MAC)協(xié)議的重要組成部分,要能夠有效避免大業(yè)務(wù)量時(shí)信道中的分組沖突,并滿足各優(yōu)先級業(yè)務(wù)的不同QoS需求,保證信息傳輸?shù)臅r(shí)效性、可靠性。因此,針對機(jī)載自組網(wǎng)MAC層設(shè)計(jì)一種合理、高效的退避算法是保證網(wǎng)絡(luò)良好性能的前提。

目前Ad hoc網(wǎng)絡(luò)MAC協(xié)議所采用的退避算法主要有以下3類。①二進(jìn)制指數(shù)退避(binary exponential backoff,BEB)算法及增強(qiáng)型分布式信道訪問(enhanced distributed channel access,EDCA)算法[8-9]。該類算法存在容易造成網(wǎng)絡(luò)不公平、當(dāng)負(fù)載變化時(shí)無法快速選取最佳競爭窗口,以及在飽和狀態(tài)時(shí)網(wǎng)絡(luò)性能下降嚴(yán)重等問題。②服務(wù)區(qū)分動態(tài)退避算法[10-11]。這類算法通過對不同優(yōu)先級業(yè)務(wù)采用不同的退避方式,有效保障高優(yōu)先級業(yè)務(wù)的傳輸,但該類算法的復(fù)雜程度會隨著優(yōu)先級數(shù)量的增加而指數(shù)上升。③自適應(yīng)退避算法。文獻(xiàn)[12]提出競爭窗口自適應(yīng)調(diào)整的退避算法,根據(jù)分組沖突的概率來估計(jì)活躍節(jié)點(diǎn)數(shù)量,從而動態(tài)調(diào)整競爭窗口,有效提升了網(wǎng)絡(luò)性能,但該算法無法實(shí)時(shí)準(zhǔn)確估計(jì)活躍節(jié)點(diǎn)數(shù)量;文獻(xiàn)[13]提出了一種區(qū)分業(yè)務(wù)優(yōu)先級的自適應(yīng)退避算法(PAB),通過實(shí)時(shí)調(diào)整節(jié)點(diǎn)相鄰?fù)吮茈A段的前后轉(zhuǎn)移概率,為多種優(yōu)先級業(yè)務(wù)提供不同的服務(wù),但其轉(zhuǎn)移概率的設(shè)定需要進(jìn)一步優(yōu)化。

為了實(shí)現(xiàn)機(jī)載自組網(wǎng)中多優(yōu)先級業(yè)務(wù)的并存?zhèn)鬏?以及保障高優(yōu)先級業(yè)務(wù)低時(shí)延、高可靠的傳輸需求,本文提出了一種帶有時(shí)間約束的多優(yōu)先級自適應(yīng)退避(time constraint based priority adaptive backoff,TC-PAB)算法。該算法一方面采用基于業(yè)務(wù)優(yōu)先級和網(wǎng)絡(luò)忙閑程度的競爭窗口自適應(yīng)調(diào)整機(jī)制,通過動態(tài)調(diào)整不同優(yōu)先級業(yè)務(wù)的競爭窗口大小,并在重負(fù)載時(shí)通過限制低優(yōu)先級分組接入來保證高優(yōu)先級業(yè)務(wù)的QoS傳輸需求;另一方面通過分組時(shí)間約束機(jī)制對各優(yōu)先級分組設(shè)定相應(yīng)的約束時(shí)間,對超過約束時(shí)間的分組直接丟棄,避免分組長時(shí)間占用發(fā)送隊(duì)列,保障各優(yōu)先級分組傳輸?shù)膶?shí)時(shí)性。

1　退避算法描述

由于機(jī)載自組網(wǎng)中各優(yōu)先級業(yè)務(wù)具有不同的QoS需求,本文所提TC-PAB算法主要采用了退避階段競爭窗口自適應(yīng)調(diào)整機(jī)制和時(shí)間約束機(jī)制,實(shí)現(xiàn)不同優(yōu)先級業(yè)務(wù)的區(qū)分服務(wù)。該算法的基本原理如圖1所示,首先對上層產(chǎn)生的業(yè)務(wù)分組進(jìn)行糾錯(cuò)編碼,然后分組進(jìn)入相應(yīng)的優(yōu)先級隊(duì)列等待發(fā)送,當(dāng)網(wǎng)絡(luò)忙閑程度小于該優(yōu)先級閾值時(shí),分組立即接入信道,反之則進(jìn)行退避等待,退避過程中首先判斷其約束時(shí)間,對于未超出約束時(shí)間的分組執(zhí)行自適應(yīng)退避機(jī)制,反之則直接丟棄該分組。該算法主要包含以下2個(gè)核心機(jī)制。

(1)自適應(yīng)退避機(jī)制。為保證最高優(yōu)先級業(yè)務(wù)傳輸?shù)膶?shí)時(shí)性,對最高優(yōu)先級分組不執(zhí)行退避算法,生成即發(fā)送,而其他優(yōu)先級業(yè)務(wù)則根據(jù)信道忙閑程度決定是否執(zhí)行退避算法,為不同優(yōu)先級業(yè)務(wù)設(shè)定不同的競爭窗口調(diào)整方式,其大小根據(jù)網(wǎng)絡(luò)負(fù)載程度和優(yōu)先級動態(tài)變化。

(2)分組時(shí)間約束機(jī)制。若分組經(jīng)過長時(shí)間退避等待,其所包含的信息已經(jīng)過時(shí),失去傳輸?shù)谋匾?所以TC-PAB算法針對不同優(yōu)先級業(yè)務(wù)的QoS需求,設(shè)置相應(yīng)時(shí)間約束長度,對超出時(shí)間約束值仍無法接入信道的分組不再執(zhí)行退避。

圖1　TC-PAB算法基本原理

定義突發(fā)占空比為R,表示發(fā)送拆分后的突發(fā)包所占用信道時(shí)間與發(fā)送原分組所占用信道時(shí)間的比值[14],l表示信道忙閑程度,設(shè)信道數(shù)為C,i(i=1,2,…,n)表示分組的優(yōu)先級,j表示分組所處的退避階段,網(wǎng)絡(luò)中所有節(jié)點(diǎn)的總分組到達(dá)率為G。根據(jù)泊松分布原理并參考文獻(xiàn)[14]的方法,l可由總分組到達(dá)率、信道數(shù)量和突發(fā)占空比來表示

(1)

根據(jù)TC-PAB算法思想,構(gòu)造優(yōu)先級i分組在第j個(gè)退避階段的競爭窗口長度Wi,j表達(dá)式為

(2)

設(shè)定各優(yōu)先級分組的時(shí)間約束值為Ti。若優(yōu)先級i分組已經(jīng)執(zhí)行了mi次退避依然不能接入信道,此時(shí)分組退避時(shí)間大于約束時(shí)間,則該分組將被丟棄。

2　建模分析

2.1　退避過程的馬爾科夫鏈模型

令pi表示優(yōu)先級i的分組到達(dá)發(fā)送緩沖區(qū)隊(duì)首時(shí)需執(zhí)行退避的概率,ui表示優(yōu)先級i的分組在約束時(shí)間內(nèi)能夠支持的最大重傳次數(shù),ψi,j表示優(yōu)先級i的分組在完成j(j∈[mi,ui])個(gè)退避階段后繼續(xù)退避的概率。令si(t)表示優(yōu)先級i的分組在t時(shí)刻所處的退避階段,bi(t)表示優(yōu)先級i的分組在t時(shí)刻退避計(jì)數(shù)器的值,則三維隨機(jī)過程(i,si(t),bi(t))構(gòu)成如圖2所示的離散馬爾科夫鏈,其各狀態(tài)穩(wěn)態(tài)概率為

(3)

由圖2可得

(4)

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

qi=1-exp(-λiTu)

(5)

當(dāng)k=0時(shí),將j(j∈[0,ui-1])代入式(4)中,可得bi,j,0(j∈[1,ui])的表達(dá)式

(6)

令Bi表示優(yōu)先級i的分組離開發(fā)送隊(duì)列(接入信道或者被丟棄)的概率,根據(jù)圖2中狀態(tài)轉(zhuǎn)移過程和式(6),可得

(7)

由式(4)中的第3式和式(7)可得

(8)

圖2　優(yōu)先級i分組退避狀態(tài)的三維馬爾科夫鏈模型

(9)

根據(jù)式(8)和式(9)可以求得圖2中每個(gè)狀態(tài)的取值。

2.2　閾值求解

對所有分組進(jìn)行RS-turbo級聯(lián)的糾錯(cuò)編碼[15],使分組具有一定的容錯(cuò)能力。令Nb為分組拆分后的突發(fā)包個(gè)數(shù),Mb為恢復(fù)原分組所需最少的突發(fā)包個(gè)數(shù)。

定義pb為單個(gè)突發(fā)包成功接收的概率,根據(jù)泊松分布公式易得

(10)

根據(jù)糾錯(cuò)編碼機(jī)制原理,可得分組成功傳輸概率為

(11)

根據(jù)系統(tǒng)對各優(yōu)先級業(yè)務(wù)最低分組成功傳輸概率的要求,并聯(lián)立式(10)、(11)可得各優(yōu)先級業(yè)務(wù)的閾值Gi。根據(jù)閾值Gi可得

(12)

2.3　時(shí)間約束參數(shù)求解

令Ti,j表示優(yōu)先級i分組在經(jīng)歷了j個(gè)退避階段后消耗的平均時(shí)長,易得

(13)

優(yōu)先級i的分組從開始退避到經(jīng)過j個(gè)退避階段所消耗時(shí)間的概率密度函數(shù)為

(14)

其概率母函數(shù)為

(15)

優(yōu)先級i的分組從開始退避到經(jīng)歷j個(gè)退避階段時(shí)分組剩余約束時(shí)間大于0的概率可表示為

(16)

優(yōu)先級i的分組在經(jīng)過j(j∈[mi,ui])個(gè)退避階段后依然不能接入信道,且在約束時(shí)間之內(nèi)的概率為

ψi,j=piγi,j-1,j∈[mi,ui]

(17)

根據(jù)式(13)～(17),可以求得所有ψi,j值。

3　性能分析

令S為網(wǎng)絡(luò)吞吐量,指單位時(shí)間內(nèi)信道實(shí)際傳輸?shù)目倲?shù)據(jù)量,表示為

(18)

式中:L為數(shù)據(jù)包長度;piin表示優(yōu)先級i分組經(jīng)過退避和信道檢測后接入信道的概率,表達(dá)式為

(19)

令E[Di]表示優(yōu)先級i分組的平均MAC時(shí)延,其值為分組到達(dá)相應(yīng)的優(yōu)先級隊(duì)列的隊(duì)首到該分組接入信道所需的時(shí)間均值,表示為

E[Di]=E[Ti]Tσ

(20)

式中:E[Ti]表示優(yōu)先級i的分組成功傳輸所需的平均時(shí)隙數(shù),表示為

(21)

4　仿真分析

下面利用OMNeT++仿真平臺對TC-PAB算法的性能進(jìn)行仿真分析。根據(jù)機(jī)載自組網(wǎng)的實(shí)際需求,這里對TC-PAB算法設(shè)定4個(gè)優(yōu)先級業(yè)務(wù),其中優(yōu)先級1為最高優(yōu)先級,其分組到達(dá)率固定為50包/s,優(yōu)先級2、3、4的分組到達(dá)率之比為1∶3∶6,綜合考慮各優(yōu)先級業(yè)務(wù)的QoS需求,設(shè)定優(yōu)先級1、2、3的最低分組成功傳輸概率分別為99%、90%、80%,其他參數(shù)設(shè)置見表1。設(shè)置仿真場景大小為500 km×500 km×10 km,所有節(jié)點(diǎn)在該場景中的隨機(jī)分布,每個(gè)節(jié)點(diǎn)隨機(jī)選擇目的節(jié)點(diǎn)通信,MAC層采用IEEE 802.11協(xié)議。其他主要仿真參數(shù)設(shè)置見表2。

首先對TC-PAB算法的性能和數(shù)學(xué)模型進(jìn)行驗(yàn)證。不同網(wǎng)絡(luò)負(fù)載下的競爭窗口數(shù)量、平均MAC時(shí)延,以及吞吐量的理論計(jì)算及仿真結(jié)果如圖3所示。由圖3a可以看出,在信道忙閑程度相同的情況下,由于優(yōu)先級的不同,所選取的競爭窗口數(shù)

表1　各優(yōu)先級參數(shù)設(shè)置

表2　仿真參數(shù)設(shè)置

呈現(xiàn)不同的梯度,從而為不同優(yōu)先級的分組提供相適應(yīng)的QoS支持。由圖3b可知,當(dāng)網(wǎng)絡(luò)處于輕負(fù)載時(shí)各優(yōu)先級的平均MAC時(shí)延均較低;在重負(fù)載時(shí)優(yōu)先級1業(yè)務(wù)時(shí)延不變,平均MAC時(shí)延在5 ms以內(nèi),其余各優(yōu)先級分組的時(shí)延隨網(wǎng)絡(luò)負(fù)載的增加而增加,最終趨于各優(yōu)先級相應(yīng)的約束時(shí)間。由圖3c可以看出TC-PAB算法在負(fù)載增大時(shí)能夠使吞吐量保持相對穩(wěn)定。由圖3可知,TC-PAB算法的理論值和仿真值基本一致,證明建模分析準(zhǔn)確有效。

(a)網(wǎng)絡(luò)負(fù)載對各優(yōu)先級競爭窗口長度的影響

(b)網(wǎng)絡(luò)負(fù)載對各優(yōu)先級平均MAC時(shí)延的影響

(c)網(wǎng)絡(luò)負(fù)載對吞吐量的影響圖3　網(wǎng)絡(luò)負(fù)載對TC-PAB算法性能的影響

下面通過仿真實(shí)驗(yàn)對TC-PAB算法、BEB算法、EDCA算法[10]和PAB算法[14]的性能進(jìn)行對比,其中EDCA算法包含4種優(yōu)先級業(yè)務(wù)類別,分別是語音(Voice,VO)、視頻(Video,VI)、盡力而為(Best-effort,BE)以及背景(Back-ground,BK)業(yè)務(wù),對PAB算法也設(shè)定4個(gè)優(yōu)先級,仿真實(shí)驗(yàn)結(jié)果如圖4、圖5所示。由圖4可知,相比PAB和EDCA,TC-PAB算法中雖然低優(yōu)先級業(yè)務(wù)的QoS保障能力較差,但能夠?yàn)楦邇?yōu)先級業(yè)務(wù)提供嚴(yán)格的QoS服務(wù)。由圖5可知,相比BEB、EDCA和PAB,TC-PAB算法在網(wǎng)絡(luò)負(fù)載較大時(shí)能夠使網(wǎng)絡(luò)吞吐量保持相對穩(wěn)定,具有明顯的性能優(yōu)勢,原因在于該算法通過限制低優(yōu)先級分組接入,把網(wǎng)絡(luò)中的沖突降到可控程度。

(a)TC-PAB算法與BEB和EDCA算法的對比

(b)TC-PAB算法與PAB算法的對比圖4　平均MAC時(shí)延性能分析及對比

圖5　吞吐量性能對比

綜合以上仿真結(jié)果,可以得到以下結(jié)論:①TC-PAB算法的理論和仿真結(jié)果吻合,證明了理論推導(dǎo)的正確性;②當(dāng)網(wǎng)絡(luò)處于輕負(fù)載時(shí),TC-PAB算法中低優(yōu)先級分組也可以獲得較好的QoS;③當(dāng)網(wǎng)絡(luò)負(fù)載加重時(shí),低優(yōu)先級的分組進(jìn)入退避階段,限制其接入信道,將信道中的沖突維持在可控范圍內(nèi),從而為高優(yōu)先級的分組提供嚴(yán)格的服務(wù);④對比BEB、EDCA和PAB,TC-PAB算法能夠?yàn)楦邇?yōu)先級業(yè)務(wù)提供更好的服務(wù),并使得網(wǎng)絡(luò)吞吐量性能保持穩(wěn)定。

5　結(jié)　論

本文為機(jī)載自組網(wǎng)MAC協(xié)議設(shè)計(jì)了一種帶有時(shí)間約束的多優(yōu)先級自適應(yīng)退避算法,針對機(jī)載自組網(wǎng)多優(yōu)先級業(yè)務(wù)并存的特點(diǎn),一方面對不同優(yōu)先級業(yè)務(wù)設(shè)定不同的競爭窗口調(diào)整方式,在重負(fù)載時(shí)通過限制低優(yōu)先級業(yè)務(wù)接入信道來保證高優(yōu)先級業(yè)務(wù)的傳輸;另一方面為各優(yōu)先級分組設(shè)定相應(yīng)的時(shí)間約束機(jī)制,對于超出約束時(shí)間的分組直接進(jìn)行丟棄,提高了分組傳輸?shù)膶?shí)時(shí)性。研究結(jié)果表明,本文算法能夠使網(wǎng)絡(luò)性能保持相對穩(wěn)定,并且根據(jù)網(wǎng)絡(luò)負(fù)載情況為不同優(yōu)先級業(yè)務(wù)提供相適應(yīng)的QoS保障。本文算法對機(jī)載自組網(wǎng)MAC協(xié)議的研究與應(yīng)用具有一定的參考價(jià)值。

參考文獻(xiàn):

[1]KWAH K J, SAGDUYU Y, YACKOSKI J. Airborne network evaluation: challenges and high fidelity emulation solution [J]. IEEE Communications Magazine, 2014, 52(10): 30-36.

[2]OZGUR K S. Networking models in flying ad-hoc network evaluation: challenges concepts and challenges [J]. Journal of Intelligent & Robotic Systems, 2014, 74(1/2): 513-527.

[3]梁一鑫, 程光, 郭曉軍, 等. 機(jī)載自組網(wǎng)體系結(jié)構(gòu)及其協(xié)議棧研究進(jìn)展 [J]. 軟件學(xué)報(bào), 2016, 27(1): 96-111.

LIANG Yixin, CHENG Guang, GUO Xiaojun, et al. Research progress on architecture and protocol stack of the airborne network [J]. Journal of Software, 2016, 27(1): 96-111.

[4]CHENG B N, FREDERICK J. Design considerations for next-generation airborne tactical networks [J]. IEEE Communications Magazine, 2014, 52(5): 138-145.

[5]BUCHTER K D. Availability of airborne ad-hoc communication network in global air traffic simulation [C]∥2016 10th International Symposium on Communication Systems, Networks and Digital Signal Processing. Piscataway, NJ, USA: IEEE, 2016: 7573927.

[6]WAN Y, KAMESH N, ZHOU Y, et al. A smooth-turn mobility model for airborne networks [J]. IEEE Transactions on Vehicular Technology, 2013, 62(7): 3359-3370.

[7]XU D H, ZHANG H Y, ZHANG B, et al. A priority differentiated and multi-channel MAC protocol for airborne networks [C]∥Proceedings of 2016 8th IEEE International Conference on Communication Software and Networks. Piscataway, NJ, USA: IEEE, 2016: 64-70.

[8]ULLAH A, AHN J S. Performance evaluation of X-MAC/BEB protocol for wireless sensor networks [J]. Journal of Communications and Networks, 2016, 18(5): 857-869.

[9]毛建兵, 毛玉明, 冷鵬, 等. 支持QoS的IEEE 802.11 EDCA性能研究 [J]. 軟件學(xué)報(bào), 2010, 21(4): 750-770.

MAO Jianbing, MAO Yuming, LENG Peng, et al. Research of the QoS-supporting IEEE 802.11 EDCA performance [J]. Journal of Software, 2010, 21(4): 750-770.

[10] 李瑞芳, 羅娟, 李仁發(fā). 適于無線多媒體傳感器網(wǎng)絡(luò)的MAC層退避算法 [J]. 通信學(xué)報(bào), 2010, 31(11): 107-116.

LI Reifang, LUO Juan, LI Renfa. Backoff algorithm in MAC layer for wireless multimedia sensor networks [J]. Journal on Communications, 2010, 31(11): 107-116.

[11] 趙慶敏, 錢雷, 熊鏑. 基于避免擁塞的優(yōu)先級退避算法 [J]. 吉林大學(xué)學(xué)報(bào), 2013, 43(6): 1072-1075.

ZHAO Qingmin, QIAN Lei, XIOANG Di. High priority backoff algorithm based on congestion avoidance [J]. Journal of Jilin University, 2013, 43(6): 1072-1075.

[12] SYED I, SHIN S H, ROH B H, et al. Performance improvement of QoS-enabled WLANs using adaptive contention window backoff algorithm [J]. IEEE Systems Journal, 2017, doi: 10.1109/JSYST. 2017. 2694859.

[13] 卓琨, 張衡陽, 鄭博, 等. 一種優(yōu)先級區(qū)分的機(jī)載無線網(wǎng)絡(luò)MAC層自適應(yīng)退避算法 [J]. 航空學(xué)報(bào), 2016, 37(4): 1281-1291.

ZHUO Kun, ZHANG Hengyang, ZHENG Bo, et al. An adaptive backoff algorithm in MAC layer for airborne network based on priority differentiation [J]. Acta Aeronautica et Astronautica Sinica, 2016, 37(4): 1281-1291.

[14] YANG T, GUO C X, ZHAO S W, et al. Channel occupancy cognition based adaptive channel access and back-off scheme for LTE system on unlicensed band [C]∥ IEEE Wireless Communications and Networking Conference.Piscataway, NJ USA: IEEE, 2016: 7565014.

[15] 肖雷蕾, 張衡陽, 毛玉泉, 等. 一種區(qū)分優(yōu)先級自適應(yīng)抖動的媒質(zhì)接入控制協(xié)議 [J]. 西安交通大學(xué)學(xué)報(bào), 2015, 49(10): 123-129.

XIAO Leilei, ZHANG Hengyang, MAO Yuquan, et al. An adaptive jitter based media access control with priorities [J]. Journal of Xi’an Jiaotong University, 2015, 49(10): 123-129.