帶有時間約束的機載自組網自適應退避算法

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

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

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

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

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

1　退避算法描述

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

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

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

圖1　TC-PAB算法基本原理

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

(1)

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

(2)

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

2　建模分析

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

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

(3)

由圖2可得

(4)

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

qi=1-exp(-λiTu)

(5)

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

(6)

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

(7)

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

(8)

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

(9)

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

2.2　閾值求解

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

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

(10)

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

(11)

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

(12)

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

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

(13)

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

(14)

其概率母函數(shù)為

(15)

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

(16)

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

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

(17)

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

3　性能分析

令S為網絡吞吐量,指單位時間內信道實際傳輸?shù)目倲?shù)據(jù)量,表示為

(18)

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

(19)

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

E[Di]=E[Ti]Tσ

(20)

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

(21)

4　仿真分析

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

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

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

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

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

(a)網絡負載對各優(yōu)先級競爭窗口長度的影響

(b)網絡負載對各優(yōu)先級平均MAC時延的影響

(c)網絡負載對吞吐量的影響圖3　網絡負載對TC-PAB算法性能的影響

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

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

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

圖5　吞吐量性能對比

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

5　結　論

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

參考文獻:

[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]梁一鑫, 程光, 郭曉軍, 等. 機載自組網體系結構及其協(xié)議棧研究進展 [J]. 軟件學報, 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]. 軟件學報, 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ā). 適于無線多媒體傳感器網絡的MAC層退避算法 [J]. 通信學報, 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]. 吉林大學學報, 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ū)分的機載無線網絡MAC層自適應退避算法 [J]. 航空學報, 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)先級自適應抖動的媒質接入控制協(xié)議 [J]. 西安交通大學學報, 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.