基于隊(duì)列優(yōu)化的多優(yōu)先級(jí)媒體接入控制協(xié)議

于必成，趙學(xué)軍，袁修久，任耀軍，侯 蓓

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

0 引言

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

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

鑒于此，針對(duì)無人機(jī)自組網(wǎng)多優(yōu)先級(jí)業(yè)務(wù)并行傳輸，以及高優(yōu)先級(jí)業(yè)務(wù)低時(shí)延、高可靠服務(wù)質(zhì)量(QoS)需求的問題，本文提出一種基于隊(duì)列優(yōu)化的多優(yōu)先級(jí)媒體接入控制(QO-MAC)協(xié)議。

1 協(xié)議描述

為了保證無人機(jī)自組網(wǎng)中多優(yōu)先級(jí)業(yè)務(wù)并行傳輸?shù)男枨螅琎O-MAC協(xié)議采用多信道機(jī)制傳輸多種優(yōu)先級(jí)業(yè)務(wù)，同時(shí)為保證在重負(fù)載情況下最高優(yōu)先級(jí)業(yè)務(wù)嚴(yán)格的時(shí)效性(小于2 ms)、可靠性(大于99%)，和其他優(yōu)先級(jí)業(yè)務(wù)的性能均能保持在一個(gè)較高水平，該協(xié)議采用多優(yōu)先級(jí)隊(duì)列優(yōu)化算法，自適應(yīng)調(diào)整發(fā)送概率和選擇發(fā)送信道。多優(yōu)先級(jí)隊(duì)列優(yōu)化算法是該協(xié)議的核心機(jī)制，其目標(biāo)是最小化每個(gè)發(fā)送節(jié)點(diǎn)緩存隊(duì)列中數(shù)據(jù)分組總和，該算法通過對(duì)節(jié)點(diǎn)緩存隊(duì)列中不同優(yōu)先級(jí)數(shù)據(jù)積壓監(jiān)測(cè)和信道忙閑程度反饋，自適應(yīng)調(diào)整各節(jié)點(diǎn)當(dāng)前分組的發(fā)送概率以達(dá)到最優(yōu)的排隊(duì)性能。

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

1) 編碼：對(duì)節(jié)點(diǎn)產(chǎn)生的數(shù)據(jù)分組均采用RS-Turbo級(jí)聯(lián)的糾錯(cuò)編碼[18]，并將其拆分為長(zhǎng)度相等的若干個(gè)突發(fā)包，在每個(gè)突發(fā)包中加入分組序號(hào)和突發(fā)序列號(hào)。

2) 排隊(duì)過程：系統(tǒng)中不同優(yōu)先級(jí)業(yè)務(wù)具有不同的分組到達(dá)率，在節(jié)點(diǎn)的隊(duì)列緩沖區(qū)中不同優(yōu)先級(jí)業(yè)務(wù)按照優(yōu)先級(jí)順序進(jìn)行排列，高優(yōu)先級(jí)分組較低優(yōu)先級(jí)分組具有搶占優(yōu)先權(quán)。

3) 信道忙閑監(jiān)測(cè)：通過統(tǒng)計(jì)各個(gè)信道在一段時(shí)間內(nèi)接收到的突發(fā)數(shù)對(duì)信道忙閑程度進(jìn)行量化，計(jì)算處于各忙閑等級(jí)的信道數(shù)，并將結(jié)果反饋給各發(fā)送節(jié)點(diǎn)。

4) 發(fā)送節(jié)點(diǎn)分組積壓監(jiān)測(cè)：監(jiān)測(cè)當(dāng)前系統(tǒng)中各發(fā)送節(jié)點(diǎn)將要發(fā)送突發(fā)包的優(yōu)先級(jí)，統(tǒng)計(jì)當(dāng)前發(fā)送相同優(yōu)先級(jí)突發(fā)的節(jié)點(diǎn)數(shù)，并將結(jié)果反饋給各發(fā)送節(jié)點(diǎn)。通過與不同優(yōu)先級(jí)業(yè)務(wù)發(fā)送閾值比較，確定突發(fā)的發(fā)送權(quán)限，從而實(shí)現(xiàn)多優(yōu)先級(jí)業(yè)務(wù)區(qū)分傳輸。

5) 隊(duì)列優(yōu)化算法：通過對(duì)節(jié)點(diǎn)緩存隊(duì)列中不同優(yōu)先級(jí)數(shù)據(jù)積壓監(jiān)測(cè)和信道忙閑程度反饋，自適應(yīng)調(diào)整各節(jié)點(diǎn)分組的發(fā)送概率和發(fā)送信道，使各節(jié)點(diǎn)緩存隊(duì)列達(dá)到最優(yōu)。

6) 解碼：通過識(shí)別突發(fā)MAC頭部包含的分組號(hào)及突發(fā)序列號(hào)，對(duì)原分組進(jìn)行重組，對(duì)重組分組進(jìn)行譯碼，根據(jù)Turbo編碼原理，接收端只要接收到一半數(shù)量以上的突發(fā)包便可還原分組。

2 協(xié)議建模

2.1 信道忙閑程度量化

對(duì)于多信道網(wǎng)絡(luò)，單個(gè)信道可以通過接收機(jī)統(tǒng)計(jì)突發(fā)包接收的歷史數(shù)量信息，以N個(gè)時(shí)隙內(nèi)接收到的突發(fā)數(shù)量表示信道忙閑程度。如圖1所示為信道接收時(shí)頻圖，N為統(tǒng)計(jì)周期，f1,…,fM表示信道，M表示網(wǎng)絡(luò)中信道總數(shù)。

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

設(shè)在N個(gè)時(shí)隙內(nèi)，信道fi接收到的突發(fā)數(shù)為Nfi，Nfi反映信道忙閑程度，Nfi越大，信道越忙，反之，信道越閑。

2.2 設(shè)置各優(yōu)先級(jí)分組接入門限Wth

不同優(yōu)先級(jí)分組接入門限Wth不同，優(yōu)先級(jí)越高，接入門限Wth越高。當(dāng)信道忙閑程度低于該突發(fā)的優(yōu)先級(jí)門限時(shí)，則允許該優(yōu)先級(jí)突發(fā)發(fā)送；若信道的忙閑程度高于該分組的優(yōu)先級(jí)門限時(shí)，則禁止該優(yōu)先級(jí)突發(fā)發(fā)送。

2.3 發(fā)送節(jié)點(diǎn)緩存隊(duì)列模型

系統(tǒng)中節(jié)點(diǎn)共產(chǎn)生n種不同優(yōu)先級(jí)數(shù)據(jù)分組，各優(yōu)先級(jí)分組數(shù)據(jù)產(chǎn)生均服從泊松分布，各優(yōu)先級(jí)數(shù)據(jù)的分組到達(dá)率分別為λ1,…,λn，則根據(jù)泊松公式，在σ時(shí)間內(nèi)，節(jié)點(diǎn)i產(chǎn)生ki,j個(gè)數(shù)據(jù)的概率為：

(1)

式(1)中，ki,j表示優(yōu)先級(jí)j數(shù)據(jù)分組到達(dá)節(jié)點(diǎn)i緩存隊(duì)列的數(shù)目。發(fā)送節(jié)點(diǎn)緩存隊(duì)列模型如圖2所示。

圖2 發(fā)送節(jié)點(diǎn)緩存隊(duì)列模型Fig.2 Sending node cache queue model

(2)

由排隊(duì)論理論知：

(3)

(4)

由此可得Tk的表達(dá)式為：

(5)

2.4 多優(yōu)先級(jí)隊(duì)列優(yōu)化算法

該算法是一個(gè)最小化每個(gè)發(fā)送節(jié)點(diǎn)隊(duì)列長(zhǎng)度總和的優(yōu)化算法。我們用Qi,j(t)表示t時(shí)刻發(fā)送節(jié)點(diǎn)i的緩存隊(duì)列中優(yōu)先級(jí)j的突發(fā)數(shù)。隨著時(shí)間的推移，每個(gè)發(fā)送節(jié)點(diǎn)緩存隊(duì)列中優(yōu)先級(jí)j的突發(fā)數(shù)演變?yōu)椋?/p>

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

(6)

式(6)中，在t時(shí)刻，發(fā)送節(jié)點(diǎn)i將優(yōu)先級(jí)j的突發(fā)包傳輸成功，Di,j(t)取1，否則取0；Ai,j(t)是t時(shí)刻發(fā)送節(jié)點(diǎn)i中優(yōu)先級(jí)j的突發(fā)包到達(dá)數(shù)。

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

(7)

(8)

(9)

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

設(shè)P(Si|Qj)為給定發(fā)送優(yōu)先級(jí)j突發(fā)的緩存節(jié)點(diǎn)總數(shù)為Qj，突發(fā)包在通道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)

所以，當(dāng)我們已知Qj和Mj就可以求出最佳發(fā)送概率p*。為了保障最高優(yōu)先級(jí)業(yè)務(wù)的時(shí)效性，優(yōu)先級(jí)1分組的發(fā)送概率恒為1。

2.5 接入閾值求解

(16)

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

(17)

2.6 算法性能指標(biāo)

1) 分組的成功傳輸率

(18)

2) 丟包率

(19)

3) 平均時(shí)延

(20)

(21)

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

4)系統(tǒng)吞吐量

定義系統(tǒng)吞吐量Sthroughput為單位時(shí)間內(nèi)系統(tǒng)正確接收的分組比特?cái)?shù)之和，即：

(22)

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

5)信道利用率

定義信道利用率為單位時(shí)間內(nèi)信道傳輸?shù)姆纸M數(shù)，即：

(23)

式(23)中，Cch信道傳輸?shù)姆纸M數(shù)，T為傳輸時(shí)間。

3 仿真分析

本文采用OMNeT++仿真平臺(tái)對(duì)該協(xié)議性能進(jìn)行分析。仿真場(chǎng)景大小設(shè)置為200 km×200 km×10 km，所有節(jié)點(diǎn)在該場(chǎng)景中隨機(jī)分布，每個(gè)節(jié)點(diǎn)隨機(jī)選擇目的節(jié)點(diǎn)通信，并且構(gòu)成一個(gè)全連通網(wǎng)絡(luò)。根據(jù)無人機(jī)自組網(wǎng)的應(yīng)用需求，協(xié)議設(shè)定4種優(yōu)先級(jí)業(yè)務(wù)，其中優(yōu)先級(jí)1 業(yè)務(wù)分組到達(dá)率固定為100包/s，優(yōu)先級(jí)2、3、4業(yè)務(wù)的分組到達(dá)率的比例為1∶1∶1，具體仿真參數(shù)設(shè)置見表1。

表1 仿真參數(shù)設(shè)置Tab.1 Simulation parameters

隨著網(wǎng)絡(luò)負(fù)載的不斷增加，協(xié)議中各優(yōu)先級(jí)分組成功傳輸率、平均時(shí)延、丟包率以及網(wǎng)絡(luò)吞吐量等性能也在不斷變化。

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

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

圖4 平均時(shí)延Fig.4 Mean delay

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

圖5 各優(yōu)先級(jí)分組丟包率Fig.5 Packet loss rates for each priority group

圖6對(duì)協(xié)議的吞吐量進(jìn)行統(tǒng)計(jì)，在輕負(fù)載時(shí)，隨著網(wǎng)絡(luò)負(fù)載增加，各優(yōu)先級(jí)吞吐量均在不斷增加，系統(tǒng)最大的吞吐量達(dá)到20 Mb/s，在重負(fù)載時(shí)，隨著碰撞的增加，吞吐量有所下降，在較大負(fù)載區(qū)間，系統(tǒng)的吞吐量仍然保持在12 Mb/s以上。圖7所示為協(xié)議信道利用率，由于采用時(shí)隙競(jìng)爭(zhēng)方式，協(xié)議信道利用率有了較大提升，并且最大信道利用率達(dá)到0.3，在較大負(fù)載區(qū)間，信道利用率保持在0.23以上。

圖6 各優(yōu)先級(jí)分組吞吐量和系統(tǒng)吞吐量Fig.6 Packet throughput and system throughput for each priority

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

4 結(jié)論

本文提出了基于隊(duì)列優(yōu)化的多優(yōu)先級(jí)媒體接入控制協(xié)議。該協(xié)議通過多優(yōu)先級(jí)隊(duì)列優(yōu)化算法自適應(yīng)調(diào)整不同優(yōu)先級(jí)業(yè)務(wù)的發(fā)送概率和選擇發(fā)送信道，實(shí)現(xiàn)多優(yōu)先級(jí)業(yè)務(wù)區(qū)分服務(wù)。仿真結(jié)果表明：

1) 在重負(fù)載情況下，QO-MAC協(xié)議可以保證最高優(yōu)先級(jí)業(yè)務(wù)低時(shí)延(小于2 ms)、高可靠性(大于99% )的QoS需求以及系統(tǒng)較高的吞吐量，并且其他優(yōu)先級(jí)業(yè)務(wù)性能均能保持在一個(gè)較高的水平。系統(tǒng)的吞吐量最大能夠達(dá)到20 Mb/s，在較大網(wǎng)絡(luò)負(fù)載區(qū)間，系統(tǒng)的吞吐量保持在12 Mb/s以上。

2) 由于采用了時(shí)隙競(jìng)爭(zhēng)信道資源的方式，QO-MAC協(xié)議的數(shù)據(jù)分組碰撞區(qū)間減小，信道利用率得到了提升，信道利用率最大值達(dá)到0.3，并且在較大負(fù)載區(qū)間，信道利用率保持在0.23以上。

3) 與其他協(xié)議對(duì)比，QO-MAC協(xié)議在各優(yōu)先級(jí)業(yè)務(wù)的時(shí)延、成功傳輸率、信道利用率等性能方面均有較大提升。