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

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

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

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

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

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

1　退避算法描述

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

(1)自適應退避機制。為保證最高優先級業務傳輸的實時性,對最高優先級分組不執行退避算法,生成即發送,而其他優先級業務則根據信道忙閑程度決定是否執行退避算法,為不同優先級業務設定不同的競爭窗口調整方式,其大小根據網絡負載程度和優先級動態變化。

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

圖1　TC-PAB算法基本原理

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

(1)

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

(2)

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

2　建模分析

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

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

(3)

由圖2可得

(4)

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

qi=1-exp(-λiTu)

(5)

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

(6)

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

(7)

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

(8)

圖2　優先級i分組退避狀態的三維馬爾科夫鏈模型

(9)

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

2.2　閾值求解

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

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

(10)

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

(11)

根據系統對各優先級業務最低分組成功傳輸概率的要求,并聯立式(10)、(11)可得各優先級業務的閾值Gi。根據閾值Gi可得

(12)

2.3　時間約束參數求解

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

(13)

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

(14)

其概率母函數為

(15)

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

(16)

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

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

(17)

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

3　性能分析

令S為網絡吞吐量,指單位時間內信道實際傳輸的總數據量,表示為

(18)

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

(19)

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

E[Di]=E[Ti]Tσ

(20)

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

(21)

4　仿真分析

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

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

表1　各優先級參數設置

表2　仿真參數設置

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

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

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

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

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

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

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

圖5　吞吐量性能對比

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

5　結　論

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

參考文獻:

[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]. 軟件學報, 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] 李瑞芳, 羅娟, 李仁發. 適于無線多媒體傳感器網絡的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] 趙慶敏, 錢雷, 熊鏑. 基于避免擁塞的優先級退避算法 [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] 卓琨, 張衡陽, 鄭博, 等. 一種優先級區分的機載無線網絡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] 肖雷蕾, 張衡陽, 毛玉泉, 等. 一種區分優先級自適應抖動的媒質接入控制協議 [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.