基于隊列優化的多優先級媒體接入控制協議

于必成，趙學軍，袁修久，任耀軍，侯 蓓

(空軍工程大學研究生院，陜西 西安 710051)

0 引言

隨著科學技術不斷發展以及作戰環境日趨復雜，無人機將在未來戰爭中起著舉足輕重的作用。由于單個無人機生存能力較弱，可擴展性較差，無法完成對整個戰場環境的感知，無人機自組網應運而生。無人機自組網[1-4]是移動自組網[5]和車載自組網[6]概念的拓展，其基本思想是網絡中各無人機不依賴于固定的基礎設施，而是將自身作為網絡節點，相互之間分發和傳遞指控指令、態勢信息。無人機自組網是一類特殊的無線自組網，不僅具有多跳、自組織、無中心等特點，同時由于無人機的高速移動，使其具有高動態的網絡拓撲結構以及大尺度稀疏分布等特點。由于無人機自組網有著區別于傳統自組網的諸多特性，使其在軍事上具有極高的應用價值，但同時也面臨著諸多技術挑戰。隨著戰爭形態的不斷演變，戰爭節奏不斷加快，無人機發送控制指令必須滿足低時延和較高的一次接入成功概率的需求[7]，多無人機系統才能實現對時延敏感目標的精確打擊，同時對于語音、圖片、視頻等態勢信息則需要保證其較高的吞吐量和時效性。這就需要無人機為不同類型業務提供相應的服務質量(QoS)支持。媒體接入控制(MAC)協議是無人機自組網協議棧的重要組成部分，作為數據鏈路層的核心機制，在保證通信系統吞吐量、數據傳輸成功率和時延等性能方面起著至關重要的作用。

按照節點對信道資源的不同占用方式，無人機自組網MAC協議大致可以劃分為3類： 1) 以時分多址(TDMA)[8-9]為代表的固定分配類協議，該類協議無競爭沖突，重負載時吞吐量穩定，但是時延較大，魯棒性較差，一般難以滿足時延敏感信息毫秒級別的軍事需求； 2) 以IEEE 802.11 DCF[10-11]為代表的預約競爭類協議，該類協議采用請求發送/清除發送(RTS/CTS)交互機制預約競爭時隙，能夠保證系統穩定的吞吐量，但預約信道可能存在競爭沖突，對于拓撲結構變化大的無人機網絡，將會產生較大的時延; 3) 以Aloha[12-13]為代表的隨機競爭類協議，網絡節點通過競爭使用信道，大大降低接入時延，符合無人機自組網的需求。美軍新一代戰術目標瞄準網絡技術采用的統計優先級多址接入(SPMA)協議[14]，利用多信道隨機競爭、信道監測、多優先級發送判決、數據包編碼以及流量控制等機制，可以支持大量用戶傳輸多種不同優先級業務，并且保證最高優先級業務傳輸延遲在2 ms以內，一次接入成功概率達到99%以上，但是其技術相對保密。文獻[15]在無線自組網時隙Aloha協議的基礎上，提出了一種傳輸控制算法，得到了最優的排隊性能，降低了數據分組的傳輸時延，但系統傳輸業務單一。文獻[16]提出了面向無人機網絡的媒體接入控制協議，該協議基于時間重用思想，利用較大的傳播時延使并發傳輸成為了可能，通過這種方法提高了信道利用率和網絡吞吐量，但在重負載時，協議時延性能較差。文獻[17]提出了一種支持混合業務傳輸的多路訪問控制協議，該協議中最高優先級業務和其他優先級業務分別采用不同的信道接入策略，并且采用基于信道忙閑感知的多優先級避退機制，保證了最高優先級業務的低時延和高可靠性，但其他優先級業務的性能較差。

鑒于此，針對無人機自組網多優先級業務并行傳輸，以及高優先級業務低時延、高可靠服務質量(QoS)需求的問題，本文提出一種基于隊列優化的多優先級媒體接入控制(QO-MAC)協議。

1 協議描述

為了保證無人機自組網中多優先級業務并行傳輸的需求，QO-MAC協議采用多信道機制傳輸多種優先級業務，同時為保證在重負載情況下最高優先級業務嚴格的時效性(小于2 ms)、可靠性(大于99%)，和其他優先級業務的性能均能保持在一個較高水平，該協議采用多優先級隊列優化算法，自適應調整發送概率和選擇發送信道。多優先級隊列優化算法是該協議的核心機制，其目標是最小化每個發送節點緩存隊列中數據分組總和，該算法通過對節點緩存隊列中不同優先級數據積壓監測和信道忙閑程度反饋，自適應調整各節點當前分組的發送概率以達到最優的排隊性能。

本文提出的QO-MAC協議具體過程如下：

1) 編碼：對節點產生的數據分組均采用RS-Turbo級聯的糾錯編碼[18]，并將其拆分為長度相等的若干個突發包，在每個突發包中加入分組序號和突發序列號。

2) 排隊過程：系統中不同優先級業務具有不同的分組到達率，在節點的隊列緩沖區中不同優先級業務按照優先級順序進行排列，高優先級分組較低優先級分組具有搶占優先權。

3) 信道忙閑監測：通過統計各個信道在一段時間內接收到的突發數對信道忙閑程度進行量化，計算處于各忙閑等級的信道數，并將結果反饋給各發送節點。

4) 發送節點分組積壓監測：監測當前系統中各發送節點將要發送突發包的優先級，統計當前發送相同優先級突發的節點數，并將結果反饋給各發送節點。通過與不同優先級業務發送閾值比較，確定突發的發送權限，從而實現多優先級業務區分傳輸。

5) 隊列優化算法：通過對節點緩存隊列中不同優先級數據積壓監測和信道忙閑程度反饋，自適應調整各節點分組的發送概率和發送信道，使各節點緩存隊列達到最優。

6) 解碼：通過識別突發MAC頭部包含的分組號及突發序列號，對原分組進行重組，對重組分組進行譯碼，根據Turbo編碼原理，接收端只要接收到一半數量以上的突發包便可還原分組。

2 協議建模

2.1 信道忙閑程度量化

對于多信道網絡，單個信道可以通過接收機統計突發包接收的歷史數量信息，以N個時隙內接收到的突發數量表示信道忙閑程度。如圖1所示為信道接收時頻圖，N為統計周期，f1,…,fM表示信道，M表示網絡中信道總數。

圖1 信道接收時頻圖Fig.1 Time-frequency diagram of channel reception

設在N個時隙內，信道fi接收到的突發數為Nfi，Nfi反映信道忙閑程度，Nfi越大，信道越忙，反之，信道越閑。

2.2 設置各優先級分組接入門限Wth

不同優先級分組接入門限Wth不同，優先級越高，接入門限Wth越高。當信道忙閑程度低于該突發的優先級門限時，則允許該優先級突發發送；若信道的忙閑程度高于該分組的優先級門限時，則禁止該優先級突發發送。

2.3 發送節點緩存隊列模型

系統中節點共產生n種不同優先級數據分組，各優先級分組數據產生均服從泊松分布，各優先級數據的分組到達率分別為λ1,…,λn，則根據泊松公式，在σ時間內，節點i產生ki,j個數據的概率為：

(1)

式(1)中，ki,j表示優先級j數據分組到達節點i緩存隊列的數目。發送節點緩存隊列模型如圖2所示。

圖2 發送節點緩存隊列模型Fig.2 Sending node cache queue model

(2)

由排隊論理論知：

(3)

(4)

由此可得Tk的表達式為：

(5)

2.4 多優先級隊列優化算法

該算法是一個最小化每個發送節點隊列長度總和的優化算法。我們用Qi,j(t)表示t時刻發送節點i的緩存隊列中優先級j的突發數。隨著時間的推移，每個發送節點緩存隊列中優先級j的突發數演變為：

Qi,j(t+1)=
max(Qi,j(t)-Di,j(t),0)+Ai,j(t)

(6)

式(6)中，在t時刻，發送節點i將優先級j的突發包傳輸成功，Di,j(t)取1，否則取0；Ai,j(t)是t時刻發送節點i中優先級j的突發包到達數。

ΔLj(Q(t))=Lj(Q(t+1))-Lj(Q(t))

(7)

(8)

(9)

式(9)中，Si= 1或0表示突發包在通道i上傳輸成功或失敗，Mj表示t時刻信道忙閑程度低于優先級j閾值的信道總數。

設P(Si|Qj)為給定發送優先級j突發的緩存節點總數為Qj，突發包在通道i上傳輸成功的條件概率，則：

E[Si]=1·P(Si|Qj)+0·(1-P(Si|Qj))

(10)

我們可以將式(10)改寫為：

(11)

(12)

(13)

將式(12)、式(13)代入式(11)整理得：

(14)

p*=min(1,Mj/Qj)

(15)

所以，當我們已知Qj和Mj就可以求出最佳發送概率p*。為了保障最高優先級業務的時效性，優先級1分組的發送概率恒為1。

2.5 接入閾值求解

(16)

定義Pp為分組成功接收概率。根據譯碼原理，一個分組中只要有Mp個突發被成功接收，就能解碼出原分組，根據排列組合原理得：

(17)

2.6 算法性能指標

1) 分組的成功傳輸率

(18)

2) 丟包率

(19)

3) 平均時延

(20)

(21)

式(21)中，d為單跳最大通信距離，v為光的傳播速度。

4)系統吞吐量

定義系統吞吐量Sthroughput為單位時間內系統正確接收的分組比特數之和，即：

(22)

式(22)中，LP為分組比特長度，η為編碼效率，T為傳輸時間。

5)信道利用率

定義信道利用率為單位時間內信道傳輸的分組數，即：

(23)

式(23)中，Cch信道傳輸的分組數，T為傳輸時間。

3 仿真分析

本文采用OMNeT++仿真平臺對該協議性能進行分析。仿真場景大小設置為200 km×200 km×10 km，所有節點在該場景中隨機分布，每個節點隨機選擇目的節點通信，并且構成一個全連通網絡。根據無人機自組網的應用需求，協議設定4種優先級業務，其中優先級1 業務分組到達率固定為100包/s，優先級2、3、4業務的分組到達率的比例為1∶1∶1，具體仿真參數設置見表1。

表1 仿真參數設置Tab.1 Simulation parameters

隨著網絡負載的不斷增加，協議中各優先級分組成功傳輸率、平均時延、丟包率以及網絡吞吐量等性能也在不斷變化。

如圖3(a)所示，隨著網絡負載的增加，網絡碰撞加劇，各優先級分組成功傳輸率隨之下降，但是優先級1分組始終保持99%以上的成功傳輸率；由圖3(b)知，在網絡負載為104包/s時，其他優先級業務依然能夠保證50%以上的成功傳輸率。圖4所示為各優先級分組平均時延，隨著網絡負載的增加，各優先級分組的平均時延依次增加，在重負載時，優先級1分組的平均時延仍然保持在2 ms以內，此外，由于各優先級負載增加，為保證高優先級業務的傳輸，優先級4分組被發送概率降低，在重負載時，優先級4分組幾乎不能被發送，所以優先級4分組的平均時延略有下降。由圖4(b)可知，當網絡處于負載在104包/s以內時，各優先級分組的平均時延均能保持一個較低值。

圖3 分組成功傳輸率Fig.3 Rate of successful transmission

圖4 平均時延Fig.4 Mean delay

圖5所示為各優先級分組丟包率，各優先級分組丟包率隨著網絡負載增加不斷增加，而優先級1分組丟包率始終為0。文獻[17]提出的MPS-MAC協議可以保證最高優先級分組嚴格的時效性和可靠性，但是在重負載時，優先級3、4分組的成功傳輸率低于0.5，且平均時延均在200 ms以上。文獻[20]提出的PAJ-MAC協議中最高優先級分組的成功傳輸率只能維持在95%。與之相比，本文提出的QO-MAC協議在保證最高級優先級分組的低時延、高可靠性的同時，其他優先級分組的成功傳輸率、平均時延、丟包率等性能均有較大提升。

圖5 各優先級分組丟包率Fig.5 Packet loss rates for each priority group

圖6對協議的吞吐量進行統計，在輕負載時，隨著網絡負載增加，各優先級吞吐量均在不斷增加，系統最大的吞吐量達到20 Mb/s，在重負載時，隨著碰撞的增加，吞吐量有所下降，在較大負載區間，系統的吞吐量仍然保持在12 Mb/s以上。圖7所示為協議信道利用率，由于采用時隙競爭方式，協議信道利用率有了較大提升，并且最大信道利用率達到0.3，在較大負載區間，信道利用率保持在0.23以上。

圖6 各優先級分組吞吐量和系統吞吐量Fig.6 Packet throughput and system throughput for each priority

圖7 信道利用率Fig.7 Channel utilization

4 結論

本文提出了基于隊列優化的多優先級媒體接入控制協議。該協議通過多優先級隊列優化算法自適應調整不同優先級業務的發送概率和選擇發送信道，實現多優先級業務區分服務。仿真結果表明：

1) 在重負載情況下，QO-MAC協議可以保證最高優先級業務低時延(小于2 ms)、高可靠性(大于99% )的QoS需求以及系統較高的吞吐量，并且其他優先級業務性能均能保持在一個較高的水平。系統的吞吐量最大能夠達到20 Mb/s，在較大網絡負載區間，系統的吞吐量保持在12 Mb/s以上。

2) 由于采用了時隙競爭信道資源的方式，QO-MAC協議的數據分組碰撞區間減小，信道利用率得到了提升，信道利用率最大值達到0.3，并且在較大負載區間，信道利用率保持在0.23以上。

3) 與其他協議對比，QO-MAC協議在各優先級業務的時延、成功傳輸率、信道利用率等性能方面均有較大提升。