應用于航空Ad Hoc網(wǎng)絡的高負載優(yōu)先級均衡MAC協(xié)議*

張偉龍，呂 娜，杜思深

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

1 引言

Ad Hoc網(wǎng)絡多采用隨機接入類MAC協(xié)議，以實現(xiàn)對網(wǎng)絡拓撲變化的靈活適應，但其協(xié)議固有的競爭碰撞造成接入時延以及接入公平性問題，在高負載航空數(shù)據(jù)鏈環(huán)境中愈加突出［1－4］。通過改進RTS/CTS握手機制、載波偵聽機制、退避機制、交互預約機制、多信道機制等方法，衍生出了大量的MAC協(xié)議，以解決網(wǎng)絡負載逐漸提升帶來的時延和公平性問題。

CSMA［5］在ALOHA基礎上利用信道檢測初步解決碰撞問題，減小了一定的時延，但高負載時碰撞率依然較高;BTMA［6］協(xié)議利用多信道忙音一定程度上解決了CSMA節(jié)點隱藏問題帶來的接入時延問題，但會造成某些節(jié)點的饑餓問題，導致節(jié)點接入不公平;文獻［7］在IEEE 802.11基礎上引入博弈論思想，使用戶流獲取公平性的最優(yōu)信道競爭參數(shù)CWmin，但是忽略了高優(yōu)先級業(yè)務的高實時性要求，過分強調(diào)公平性。文獻［8］在IEEE 802.11e基礎上，不同優(yōu)先級業(yè)務采用不同的信道競爭能力，保證高優(yōu)先級業(yè)務低時延優(yōu)先接入，但低優(yōu)先級業(yè)務在高負載時將會出現(xiàn)高時延問題。

在業(yè)務高負載、節(jié)點高密度網(wǎng)絡中，上述MAC協(xié)議雖然考慮了時延與公平性，但當流量超過網(wǎng)絡容限時，沖突碰撞增加，網(wǎng)絡會迅速擁塞，實時性能將會急劇下降，導致重要信息不能及時發(fā)送［3］?；谛诺澜y(tǒng)計優(yōu)先的多址接入?yún)f(xié)議(Statistical Priority－ based Multiple Access，SPMA)［9］在多信道統(tǒng)計機制下，利用優(yōu)先級機制，在網(wǎng)絡負載超過容限時對低優(yōu)先級業(yè)務進行適時截流停發(fā)，維持網(wǎng)絡通暢且不迅速惡化，保證高優(yōu)先級業(yè)務低時延發(fā)送，但此時低優(yōu)先級業(yè)務時延較大。

本文基于SPMA協(xié)議思想，改進信道占用統(tǒng)計及閾值－回退算法，提出一種多信道MAC協(xié)議——基于低時延的高負載優(yōu)先級均衡(Priority Balancing based on Low Latency under High Load，PBLL/HL)，以改善航空環(huán)境下業(yè)務高負載、節(jié)點高密度的網(wǎng)絡性能:網(wǎng)絡流量未飽和時，提升網(wǎng)絡吞吐量，保證高優(yōu)先級業(yè)務低時延接入;網(wǎng)絡流量飽和過載時，優(yōu)化網(wǎng)絡流量，盡可能維持最優(yōu)網(wǎng)絡吞吐量，維持高優(yōu)先級業(yè)務低時延發(fā)送，降低低優(yōu)先級業(yè)務由于截流帶來的時延，使網(wǎng)絡不會迅速擁塞惡化。

2 收發(fā)信機制

MAC協(xié)議的性能與物理層波形設計密切相關［10－12］，依據(jù) SPMA 多信道機制，PBLL/HL 協(xié)議與收發(fā)機制進行聯(lián)合設計。

首先將物理收發(fā)信道擴展為5個，在5個動態(tài)分配信道上同時進行發(fā)送或者接收，即同時1路發(fā)送、4路接收，從物理設備上提供減小碰撞機率和增加用戶數(shù)量的性能改善基礎。

其次，原業(yè)務數(shù)據(jù)包MES采用LDPC糾錯擴展編碼，分割成N個待發(fā)送的子數(shù)據(jù)塊(SM)，SM在對應優(yōu)先級隊列排隊等待，根據(jù)PBLL/HL選擇信道發(fā)送，數(shù)據(jù)塊時頻分布如圖1所示，從數(shù)據(jù)幀結構上減小數(shù)據(jù)碰撞概率。

圖1 時間和頻率上消息MES波形圖Fig.1 Waveform of the MES in time and frequency

接收端多路接收子數(shù)據(jù)塊，部分子數(shù)據(jù)塊的碰撞丟失仍能依靠強糾錯解碼正確恢復。從編碼機制上提升誤碼糾正能力，進而改善沖突分解能力。

通過上述收發(fā)信機制，數(shù)據(jù)碰撞概率大為減小，碰撞誤碼對接收數(shù)據(jù)正確恢復的影響大為減小，數(shù)據(jù)傳輸容錯性增強。

3 PBLL/HL協(xié)議

傳統(tǒng)的競爭類MAC協(xié)議隨著負載的增加，吞吐量在過載時會急劇下降，如圖2曲線A所示，然而理想需求的是曲線B所示的穩(wěn)定性吞吐量，即需要對信道接入進行有效控制。

圖2 負載－吞吐量趨勢Fig.2 Trend of load － throughput

CSMA類接入控制，傳播時延大于分組幀長時，會導致碰撞檢測失真;TDMA類接入控制，由于固定時隙，造成不必要的時延和資源浪費;集中式控制類，由于節(jié)點數(shù)量和業(yè)務數(shù)量，使得成本高且難實現(xiàn)。

因此，PBLL/HL采用SPMA的分布式接入控制思想，利用多信道占用統(tǒng)計與優(yōu)先級閾值判別，適時截流停發(fā)低優(yōu)先級業(yè)務，盡可能實現(xiàn)理想曲線B的性能要求，確保高優(yōu)先級業(yè)務的絕對實時發(fā)送(小于2 ms)［4］。由于SPMA截流機制使得低優(yōu)先級業(yè)務接入時延較高，PBLL/HL設計了公平性優(yōu)先級閾值和沖突回退算法(Priority Threshold and Conflict Back off Algorithm，PCA)，在高優(yōu)先級業(yè)務低時延發(fā)送的前提下，改善低優(yōu)先級業(yè)務的較高時延問題，提高網(wǎng)絡吞吐量。

3.1 優(yōu)先級發(fā)送判別機制

PBLL/HL將業(yè)務進行優(yōu)先級分類，在網(wǎng)絡過載時，通過優(yōu)先級閾值和信道占用統(tǒng)計比較，使低優(yōu)先級業(yè)務停發(fā)等待，優(yōu)化網(wǎng)絡流量，保證高優(yōu)先級業(yè)務成功傳輸，網(wǎng)絡狀態(tài)良好時，再對低優(yōu)先級業(yè)務進行處理發(fā)送。既保證了重要業(yè)務通信的順暢，又不會使網(wǎng)絡過載，維持了比較穩(wěn)定的吞吐量。

優(yōu)先級閾值是各優(yōu)先級對應的發(fā)送判別門限;信道占用統(tǒng)計是預定周期內(nèi)信道上脈沖數(shù)量的累計，在此預定周期結束時，信道占用統(tǒng)計清零，再去生成新的信道占用統(tǒng)計。如圖3所示，PBLL/HL中T/R信道占用統(tǒng)計是對收發(fā)機數(shù)據(jù)在整個頻率－時間有效空間進行計算，得到5個單信道的占用統(tǒng)計值。

圖3 PBLL/HL協(xié)議流程Fig.3 Flow chart of PBLL/HL

SPMA只對接收機進行統(tǒng)計，由于節(jié)點自身業(yè)務量會導致信道占用統(tǒng)計失真，業(yè)務量較小節(jié)點信道占用統(tǒng)計偏大，下一時刻業(yè)務接入機率較小，業(yè)務量大節(jié)點反之，出現(xiàn)節(jié)點不公平現(xiàn)象，且有可能導致碰撞增加。

請求發(fā)送某優(yōu)先級數(shù)據(jù)包時，PBLL/HL會將各信道占用統(tǒng)計與該優(yōu)先級閾值進行比較，選擇滿足條件的信道進行數(shù)據(jù)發(fā)送。

協(xié)議判別如圖3所示，檢測優(yōu)先級隊列，無數(shù)據(jù)時持續(xù)檢測，有數(shù)據(jù)時先從高優(yōu)先級數(shù)據(jù)進行發(fā)送，將較高優(yōu)先級隊列數(shù)據(jù)包取出，判斷是否期滿，如果沒有期滿，將5個信道占用統(tǒng)計與對應優(yōu)先級閾值比較，如果有滿足條件的信道，即低于優(yōu)先級閾值，則隨機選擇滿足條件的信道發(fā)送;如果沒有滿足條件的信道，即都高于優(yōu)先級閾值，節(jié)點將按照該優(yōu)先級回退算法等待一個隨機回退間隔，并再次檢測信道占用統(tǒng)計。

如果在隨機回退期間，比它低的優(yōu)先級業(yè)務數(shù)據(jù)被排隊等待發(fā)送，則將低優(yōu)先級業(yè)務數(shù)據(jù)保存在對應優(yōu)先級隊列中，直到更高優(yōu)先級隊列數(shù)據(jù)發(fā)送為空;如果一個比它高的優(yōu)先級業(yè)務數(shù)據(jù)在回退間隔期間被排隊等待發(fā)送，則回退取消，立刻重新檢測較高優(yōu)先級業(yè)務閾值，與信道占用統(tǒng)計進行比較。隨后再次進行以上過程，將允許發(fā)送的數(shù)據(jù)包從隊列移除進行發(fā)送。

在預定周期內(nèi)，由于局部突發(fā)性數(shù)據(jù)，會導致局部節(jié)點信道占用統(tǒng)計迅速增長并高于最高優(yōu)先級閾值，所有業(yè)務數(shù)據(jù)將不能發(fā)送，造成接入時延增加、資源浪費。SPMA未考慮這種情況，此時，如果剩余預定周期大于其值的一半，PBLL/HL將使信道占用統(tǒng)計迅速歸零，以應對突發(fā)數(shù)據(jù)帶來的時延和資源浪費問題。

此優(yōu)先級發(fā)送機制使得高優(yōu)先級業(yè)務能夠盡可能短時間地進行發(fā)送，保證重要數(shù)據(jù)的實時性，在網(wǎng)絡高負載時可對低優(yōu)先級進行截流控制，維持網(wǎng)絡的通暢。

3.2 公平性PCA算法

信道占用統(tǒng)計失真、預定周期設置不合理、優(yōu)先級閾值不匹配當前網(wǎng)絡狀態(tài)、網(wǎng)絡的不確定性以及突發(fā)業(yè)務數(shù)據(jù)，都會使得信道占用統(tǒng)計達到一個門限，此時低優(yōu)先級業(yè)務被禁止發(fā)送，造成時延加大，高優(yōu)先級業(yè)務數(shù)量較小，造成信道資源的浪費，故而提出公平性的PCA算法。

各優(yōu)先級閾值Fi按照優(yōu)先級從高到低排列，高優(yōu)先級業(yè)務閾值相對較大，同時每個閾值設置一個浮動窗口［FMIN，F(xiàn)MAX］，各浮動窗口沒有交集，鑒于業(yè)務優(yōu)先級越高對高負載時在傳信息量影響越大，為了穩(wěn)定吞吐量，增加低優(yōu)先級業(yè)務接入機率，高優(yōu)先級浮動窗口較小，低優(yōu)先級浮動窗口較大，例如，優(yōu)先級 0的初始值取1000，浮動窗口為［950，1050］，優(yōu)先級 1的初始值取 800，浮動窗口為［700，900］。

Fi初始化為浮動窗口的中值，按照流量擁塞控制機制，當成功發(fā)送一個數(shù)據(jù)時，其對應優(yōu)先級閾值在原有基礎上進行一個增加，使得下次接入機率增加;當發(fā)送失敗時，即進行回退等待的情況，優(yōu)先級閾值直接降到浮動窗口最小值與當前優(yōu)先級閾值的中間值，以減少業(yè)務發(fā)送，保證網(wǎng)絡的通暢。Fi數(shù)值變化如式(1)所示:

在此基礎上，回退等待機制也充分考慮低優(yōu)先級問題。BEB退避算法，競爭窗口采用二進制指數(shù)，沖突時CW=min(2iCWMIN，CWMAX)，成功時直接讓窗口減小為CWMIN，造成小時間尺度的不公平性現(xiàn)象，發(fā)送時延抖動性強，不適用實時業(yè)務。MILD退避算法，信息發(fā)送沖突回退時，競爭窗口的值增加為原來的1.5倍，直至CWMAX;發(fā)送成功時，競爭窗口CW值減1，局限于信息量較少的網(wǎng)絡。MIMD退避算法，信息發(fā)送沖突回退時，競爭窗口的值增加為原來的2倍，直至CWMAX;發(fā)送成功時，競爭窗口CW變?yōu)樵瓉淼?.5倍，直至CWMIN，適用于節(jié)點多的場景，但沒有考慮業(yè)務優(yōu)先級問題［2－3］。

本文考慮到網(wǎng)絡信息量大、實時性要求高，以及公平性原則，某優(yōu)先級業(yè)務進行回退時，對應回退競爭窗口為［0，CWi］，［CWMIN，CWMAX］是 CWi對應的窗口范圍，高優(yōu)先級窗口最小值CWMIN較大，但窗口范圍較小，低優(yōu)先級反之;因為高優(yōu)先級發(fā)生碰撞回退時，說明信道負載過重趨于擁塞，需要對數(shù)據(jù)進行大量遏制截流，回退時間應該較大，但考慮到低時延要求，回退時間抖動應該較小。

CWi初始化為CWMIN，在發(fā)送沖突回退或者發(fā)送成功時，CWi按照回退次數(shù)和優(yōu)先級在窗口中進行優(yōu)化選擇。CWi數(shù)值變化如式(2)所示:

本文采用4個優(yōu)先級的消息體制，分別為0、1、2、3 級，0代表最高級，式(2)中 PF［i］=COi+2+i×0.1，COi代表i級優(yōu)先級業(yè)務在預定周期內(nèi)的回退次數(shù)，回退次數(shù)越多則回退時間越長;MF［i］=(4－i)×0.2，i代表優(yōu)先級數(shù)，優(yōu)先級越低回退時間越低，保證低優(yōu)先級業(yè)務盡快發(fā)送。

由于截流機制，網(wǎng)絡實際在傳流量很難達到飽和流量，高優(yōu)先級業(yè)務回退的機率較小?？紤]到公平性，PCA算法重點考慮低優(yōu)先級業(yè)務，在信道允許的情況下，既不影響高優(yōu)先級業(yè)務的實時發(fā)送，又充分利用信道資源，增加低優(yōu)先級業(yè)務接入成功率，提升網(wǎng)絡整體實時性。

4 仿真分析

利用Exata仿真平臺對PBLL/HL協(xié)議性能進行仿真測試，場景及參數(shù)如圖4所示，設置8組不同優(yōu)先級業(yè)務流，分別為業(yè)務優(yōu)先級為3的1～10、7～15數(shù)據(jù)流，業(yè)務優(yōu)先級為2的2～8、12～14數(shù)據(jù)流，業(yè)務優(yōu)先級為1的3～9、6～13數(shù)據(jù)流，業(yè)務優(yōu)先級為0的4～11、5～16數(shù)據(jù)流，共用5個信道。

2Mb/s的信道速率滿足大容量、高速率數(shù)據(jù)流傳輸，優(yōu)先級數(shù)根據(jù)真實指令等級數(shù)確定，設置8組不同優(yōu)先級的業(yè)務流，最大限度的逼近真實場景。為更加直觀便捷地統(tǒng)計時延及吞吐量，每架飛機只有特定的優(yōu)先級數(shù)據(jù)流，與真實場景有差異，但不影響性能參數(shù)的真實性、準確性。

圖4 三維仿真場景Fig.43 D simulation scenes

4.1 時延

網(wǎng)絡的業(yè)務量為0.5 Mb/s、1 Mb/s、1.5 Mb/s、2 Mb/s、2.5 Mb/s、3 Mb/s，依次增加進行時延統(tǒng)計，得到業(yè)務量由低負載到過載過程中的時延變化趨勢。仿真中使用PBLL/HL、SPMA兩種協(xié)議，后者按照優(yōu)先級采用固定的優(yōu)先級閾值和回退窗口，仿真中其值取PCA算法的初始值。

端到端時延仿真結果如圖5所示，PBLL/HL協(xié)議時延大體分布在0～1 s之間。當網(wǎng)絡流量不大、負載較輕時，各優(yōu)先級業(yè)務的時延都接近于0;隨著網(wǎng)絡負載不斷加重，高優(yōu)先級業(yè)務時延變化不大，其他優(yōu)先級業(yè)務時延增加幅度較大，如0優(yōu)先級業(yè)務基本不變，4優(yōu)先級業(yè)務時延上升明顯，最高時達到了1.02 s，說明協(xié)議通過對低優(yōu)先級業(yè)務的截流遏制，維持良好的網(wǎng)絡負載，實現(xiàn)了對高優(yōu)先級業(yè)務的低時延要求。

圖5 多節(jié)點多優(yōu)先級業(yè)務的時延性能Fig.5 The latency performance of multiple nodes with multiple priority data

從圖5還可以看出，對于高優(yōu)先級業(yè)務，兩條仿真曲線基本重合，差值最大為0.002 s，說明PCA公平性算法基本不影響高優(yōu)先級業(yè)務時延;而對于低優(yōu)先級業(yè)務，SPMA時延明顯高于PBLL/HL，而且優(yōu)先級越低，兩個協(xié)議時延差越大，例如3優(yōu)先級業(yè)務在業(yè)務量為3 Mb/s時，PBLL/HL時延比SPMA時延要低0.11 s，而2優(yōu)先級業(yè)務時延差0.08s，說明PCA算法對較低優(yōu)先級業(yè)務作用明顯;8條曲線對比說明采用PCA算法，既保證了高優(yōu)先級業(yè)務的低時延發(fā)送，又降低了低優(yōu)先級業(yè)務的接入時延，減小了網(wǎng)絡平均時延，更好地保證了網(wǎng)絡的實時性。

4.2 歸一化吞吐量

網(wǎng)絡業(yè)務量從0開始，以1為單位增加至30，進行吞吐量統(tǒng)計，得到PBLL/HL下業(yè)務量由低負載到嚴重過載過程中的吞吐量曲線，同時引入ALOHA、時隙 ALOHA 吞吐量曲線［3－13］，如圖 6 所示。純ALOHA當負載為0.5時，吞吐量最大達到18.4%;時隙ALOHA當負載為1時，吞吐量最大達到36.8%。由這兩條曲線可看出，當吞吐量達到最大值后，隨著負載繼續(xù)增加，吞吐量急劇下降，說明過載時數(shù)據(jù)沖突急劇增加，協(xié)議碰撞回避機制弱，不適用高負載網(wǎng)絡。

圖6 負載與吞吐量曲線Fig.6 Performance curve of load － throughput

如圖6所示，PBLL/HL仿真曲線隨著負載增加快速升高，負載達到10時開始緩慢下滑，直至負載為30時，曲線仍未急劇下降，且趨于平滑，說明PBLL/HL協(xié)議碰撞回避機制優(yōu)勢明顯，當網(wǎng)絡超載時，不會迅速趨于擁塞，能夠根據(jù)信道占用情況，遏制較低優(yōu)先級業(yè)務數(shù)據(jù)發(fā)送，達到截流目的，保證較高優(yōu)先級業(yè)務傳輸通暢，維持較穩(wěn)定的吞吐量。PBLL/HL流量為10時，吞吐量最大達到88.1%，說明PBLL/HL的負載性能明顯提升，吞吐量和信道利用率高。

5 結論

業(yè)務高負載、節(jié)點高密度的航空數(shù)據(jù)鏈網(wǎng)絡中，PBLL/HL區(qū)分不同業(yè)務等級，通過公平性優(yōu)先級截流機制，優(yōu)化網(wǎng)絡流量，使網(wǎng)絡實際在傳流量很難達到飽和，確保業(yè)務低時延發(fā)送的成功率;弱化甚至避免了流量過載帶來的高時延和網(wǎng)絡擁塞，維持了較為穩(wěn)定的吞吐量。本文中預定周期長度直接關系到信道占用統(tǒng)計的時效性，如何尋找最優(yōu)的預定周期將是后續(xù)工作研究的重點。

［1］Jurdak R，Lopes C V，Baldi P.A survey，classification and comparative analysis of medium access control protocols for ad hoc networks［J］.IEEE Communications Sur-veys ＆ Tutorials，2004，6(1):2 －16.

［2］張棋飛.無線自組織網(wǎng)絡路由及MAC協(xié)議關鍵技術研究［M］.武漢:湖北人民出版社，2012.ZHANG Qi－fei.Key Techniques of Routing and MAC Protocal in the Wireless Self－organized Network［M］.Wuhan:Hubei People's Publishing House，2012.(in Chinese)

［3］呂娜，杜思深.數(shù)據(jù)鏈理論與系統(tǒng)［M］.北京:電子工業(yè)出版社，2011.LV Na，DU Si－ shen.Theory and System of Data Link［M］.Beijing:Publishing House of Electronics Industry，2011.(in Chinese)

［4］駱光明，楊斌.數(shù)據(jù)鏈——信息系統(tǒng)連接武器系統(tǒng)的捷徑［M］.北京:國防工業(yè)出版社，2008.LUO Guang－ming，YANG Bin.Data Link——The Shorcut between Information System and Weapon System［M］.Beijing:National Defense Industry Press，2008.(in Chinese)

［5］Kleinrock L，Tobagi F A.Packet switching in radio channels:part I——carrier sense multiple － access modes and their throughput－ delay characteristics［J］.IEEE Transactions on Communications，1975，23(12):1400－1416.

［6］Tobagi F A，Kleinrock L.Packet switching in radio channels:part II——The hidden terminal problem in carrier sense multiple－access and the busy － tone solution［J］.IEEE Transactions on Communications，1975，23(12):1417－1433.

［7］張國鵬，張海林，趙力強.WLAN中基于協(xié)作博弈的比例公平性帶寬分配機制［J］.西安電子科技大學學報(自然科學版)，2009，36(1):87 －93.ZHANG Guo － peng，ZHANG Hai－ lin，ZHAO Li－ qiang.Cooperative game theoretic bandwidth sharing scheme for proportional fairness in WLAN［J］.Journal of Xidian University(Natural Science)，2009，36(1):87 －93.(in Chinese)

［8］李楠，蔡躍明，程乃平.Ad Hoc網(wǎng)絡中一種具有優(yōu)先控制的自適應協(xié)同 MAC協(xié)議［J］.信號處理，2011，27(3):450－455.LI Nan，CAI Yue － ming，CHENG Nai－ ping.An adaptive cooperative MAC with priority for Ad Hoc networks［J］.Signal Processing，2011，27(3):450－455.(in Chinese)

［9］Stephen M C，Hoback K A，Scott J F.Statistical priority －based multiple access:US，768077B1［P］.2010－03－16.

［10］Weingarten H T L，Viswanath P.The capacity region of the degraded multi－input multi－output compound broadcast Channel［J］.IEEE Transactions on Information Theory，2009，55(11):5011 －5023.

［11］Ekrem E，Ulukus S.The secrecy capacity region of the gaussian MIMO multi － receiver wiretap channel［J］.IEEE Transactions on Information Theory，2011，57(4):2083－2114.

［12］宋煜，左德承，楊孝宗，等.一種用于多信道Ad Hoc網(wǎng)絡MAC協(xié)議的匹配策略［J］.計算機學報，2012，35(5):1018－1030.SONG Yu，ZUO De － cheng，YANG Xiao － zong，et al.A matching algorithm for multichannel Ad Hoc medium access control protocol［J］.Chinese Journal of Computers，2012，35(5):1018 －1030.(in Chinese)

［13］Goldsmith A J，Wicker S B.Design challenges for energy － constrained ad hoc wireless networks［J］.IEEE Wireless Communications，2002，9(4):8 －27.