一種REB&PMDS的無線MAC協議

彭 聰，陳海榮，范 平

(1.湖北科技學院 計算機科學與技術學院，湖北 咸寧 437100；2.內蒙古工業大學 輕工與紡織系，呼和浩特 010000)

0 引言

對于分散無線網絡的媒質訪問控制(MAC,medium access control)協議[1-2]來說，需要同時滿足多個相互沖突的目標：高信道利用率、高發送成功概率和高公平性；協議還應當易于理解和實現，并能提供絕對或相對的差異化服務；高發送成功概率對于自動重傳請求(ARQ,automatic re-transmission query)較難和模糊的廣播傳輸尤為重要[3]。

現有的MAC協議通常采用3種基本機制來分配信道訪問(接入)：載波偵聽、載波突發和樹分裂。在基于載波偵聽的協議如基于帶沖突避免的載波偵聽多路訪問(CSMA/CA,carrier sense multiple access with collision avoidance)的IEEE 802.11標準中，節點反復偵聽信道，然后在有足夠空閑時隙的情況下執行發送；在基于載波突發的協議如Hiperlan/1中采用的消除產生非搶占式優先級多點接入(EY-NPMA,elimination yield non-preemptive priority multiple access)中，節點嘗試通過突發(即阻塞信道，時間比其他節點長)來贏得信道；在樹分裂協議如無線網絡分布式排隊隨機訪問協議(DQRAP-WN,distributed queuing random access protocol in wireless networks)中，節點通過分布式深度優先樹遍歷進行操作。

IEEE 802.11中采用的MAC算法[4]是CSMA/CA協議。在CSMA/CA中，節點首先在一個稱為幀間間隔(IFS,inter frame space)的短時間內偵聽信道。如果信道繁忙或發生碰撞，節點將從U{0,CW}中采樣大量的退避時隙，其中CWmin≤CW≤CWmax為爭用窗口。當檢測到媒質空閑時，退避計數器自減即每個時隙減1。節點將在其退避計數器為零時訪問信道。接收節點等待一個短的IFS(SIFS,short IFS)，然后發送一個ACK。在一個不成功的發送嘗試后，CW加倍。嘗試成功后，將CW設置為CWmin。

在數據傳輸之前的控制幀交換可選擇地按以下方式執行。發送方以發送一個請求發送(RTS, request to send)開始，接收方在首先等待一個SIFS之后，以一個清除發送(CTS,clear to send)數據包作出響應。在接收方、發送方或兩者范圍內的節點，在完成幀交換序列期間將延遲訪問。

在一個IEEE 802.11網絡中，碰撞允許相關節點調整它們的爭用窗口。關于條件的信息以很高的代價(碰撞)收集，但不與非碰撞節點共享。這導致了公平性和低信道利用率的問題。

文獻[5]提出的指數倍增方案有利于最后成功的節點，但又造成了公平性問題；當采用非最佳爭用窗口時，信道利用率問題由高碰撞概率引起。文獻[6]表明，優化爭用窗口大小的一個關鍵問題是準確估計節點的數量。碰撞概率僅依賴于最小爭用窗口和節點數量，將最小爭用窗口減半相當于將用戶數量加倍。文獻[7-8]對這兩個問題提出了不同的爭用窗口調節方案；文獻[9]提出了一種改進自適應的退避算法來解決當接入網絡用戶數較多時系統性能的優化。通過對經典的二進制指數退避機制的改進，得到一種改進的自適應退避機制使得調節退避窗口時能夠自適應地感知網絡環境的變化。該機制主要考慮3個方面：引入窗口劃分的思想，使得競爭窗口的值僅限于在不同退避階段的非重疊區間取得。加入凍結概率使模型更符合無線信道中實際傳輸的過程。設置與信道利用率有關的參數控制退避窗口調節幅度，從而減小碰撞發生的可能性；文獻[10] 針對802.11網絡或其他無線網絡中的CSMA/CA提出了一種半窗方案，通過添加概率預測因子改進退避時間的計算方法。概率預測因子用于調整介質訪問概率計算退避時間的競爭窗口，將窗口劃分為至少2個半窗，然后根據窗口的信息增益選擇其中一個半窗進行概率預測，從而減少介質的競爭。

EY-NPMA即Hiperlan/1中規定的信道分配和沖突解決協議工作如下：在成功發送后，節點在下一次爭用開始前等待一個IFS。爭用分為3個階段：優先級確定、消除和產生。在優先級確定階段，節點必須在發送優先級確定突發之前，偵聽到信道空閑的時隙數目等于它們的優先級(0～4，其中0為最高優先級)。具有較低優先級的節點偵聽到信道繁忙并放棄爭用，而剩余的節點根據幾何分布突發一個隨機數量的時隙X，即X～Geom(P)且:

(1)

式中,pE為每個消除時隙中突發的概率，mES為最大突發時間。在生存驗證時隙中驗證了其生存之后，節點可以訪問U{0,mYS}個時隙。采樣次數最少的一個或多個節點將訪問該信道。

在標準中，時隙長度是根據位周期來指定的，并不是所有類型的時隙都相同。在分析協議時，為了簡化和可比性，一般采用統一的時隙長度τ。EY-NPMA中的默認參數為pE=0.5、mES=12和mYS=9都不是最優的。

文獻[11]提出的交叉感知層MAC控制方案是另一種基于發送方優先級算法分配突發長度的突發協議。

基本的樹分裂算法工作如下[12]：當在一個時隙i中發生碰撞時，所有涉及到的節點被分割成許多子集，第一個子集在時隙i+1中重傳，第二個子集在時隙i+2中重傳，以此類推。如果一個子集中的節點之間發生了另一個碰撞，則這個子集就會遞歸地分裂成兩個。子集允許發送的順序可以是廣度優先遍歷，也可以是深度優先遍歷。由于每個節點在每輪中只成功發送一次，因此保證了公平性，但這種協議算法不考慮丟包和干擾，因此降低了信道吞吐量和利用率。

文獻[13]針對有線網絡提出了分布式排隊隨機訪問協議(DQRAP,distributed queuing random access protocol)，文獻[14]將其改進為具有中央控制器的無線網絡DQRAP協議即DQRAP-WN，但該協議的操作相當復雜，工作如下：在無爭用的情況下，節點只要有一個可用的數據包，就發送一個數據包。如果存在碰撞和包丟失即沒有ACK，則節點切換到基于爭用的操作。在每個固定長度的數據時隙之后，涉及碰撞的節點隨機選擇兩個小時隙中的一個來發送一個最小的數據包。所有非發送節點在每個小時隙之后的微時隙中提供反饋。如果涉及的節點檢測到碰撞，它們就發送一個NACK，并將自己放置在處理隊列(RQ,resolution queue)中。如果存在一個單獨的節點即沒有NACK，則把它放在傳輸隊列(TQ,transmission queue)中。在兩個小時隙之后，TQ中的第一個節點訪問信道。節點維護兩個隊列的長度和它們自己在其中的位置；文獻[15]提出了另一種樹分裂協議，其中控制器由獲勝發送方動態指定，在第一次成功處截斷樹的深度優先遍歷。

以上所提出的各種協議都不能滿足分散無線網絡對MAC協議的所有要求，因此本文提出了一種新的協議。算法根據幾何分布采用隨機長度的突發來重復消除信道訪問節點。為了獲得期望的相對優先級，基于基本優先級向量提出了一種實現差異化服務的相對優先級機制，從而提高整個網絡的信道總利用率。

1 本文提出的REB & PMDS協議算法

為便于分析，把本文提出的協議算法稱之為重復消除突發和帶差異化服務優先級機制(REB & PMDS,repeated elimination bursts and prioritization mechanisms with differentiated service)的無線媒體訪問控制協議。

假設信道為分時隙且每個發送方能夠在每個時隙中執行以下2種操作之一：載波偵聽操作或執行一個短突發或干擾發送。發送方在每個時隙i以P(Ai=tx)=qi和P(Ai=cs)=1-qi=pi隨機選擇執行哪個動作A。如果發送方偵聽到一個空閑信道，它就添加一個計數器IdleSlots。當IdleSlots=h時，則認為已贏得信道并開始發送。算法1為描述REB & PMDS算法的偽代碼。

算法1:REB & PMDS

1.偵聽信道空閑TIFS

2.IdleSlots=0,i=1

3.whileIdleSlots

4. ifAi=tx then

5. TransmitNoise(τ)

6. else//Ai=cs

7. if busy=SenseChannel(τ) then

8. else

9.IdleSlots=IdleSlots+1

10. end if

11. end if

13.i=i+1

14.end while

15.TransmitMessage(Tm)

REB & PMDS算法的運行示例如圖1所示。圖中灰色梯形為消除突發，白色梯形為載波偵聽操作，寬的深灰色梯形為數據發送。示例中n=6，h=4和q=0.5。最初，所有節點在隨機執行載波偵聽(Ai=cs)或消除突發發送(Ai=tx)之前等待一個TIFS。在示例中，S2和S5偵聽到信道繁忙并離開爭用。在接下來的時隙中，S3和S6被消除。剩下的節點S1和S4在第一次消除中存活下來，并進入到第二次節點S1的消除中。S4執行兩次額外的消除，直至IdleSlots=h并允許訪問為止。

圖1 有6個節點的REB & PMDS工作過程

2 算法性能分析

接下來對所提出的REB & PMDS算法性能進行分析。假設信道工作在飽和條件下，沒有隱藏終端，信道噪聲等不影響結果，所有數據包的長度相同。文中采用的記號及其含義和值如表1所示。

2.1 單次消除

在每次消除中，突發時間最長的節點將存活下來。n個節點間最長突發的期望長度為[16]：

表1 文中采用的記號含義和值(時間單位為μs)

(2)

精確式(2)對于較大的n來說是不實用的，所以排除誤差項后消除階段的期望長度近似為：

(3)

式中,γ=0.577為歐拉常數。在本文的數值示例中，當n>50時采用這個近似式。

n個節點中有m個節點在消除階段存活下來的概率為[17]：

(4)

對于較大的n近似為：

(5)

式中,δm(x)=1/m!·∑j≠0Γ(m-2jπi/log(q-1))e2jπix且Γ為Γ函數。在本文的數值示例中，當n<10時，可以采用精確式(4)。

2.2 重復消除

通過遞歸擴展式(4)，可以得到n個節點中有m個節點在第k次消除中存活的概率為：

(6)

發送成功的概率等于h次消除后僅剩下一個節點的概率，即：

pS=p1,h(n)

(7)

第k次消除的期望長度同樣可得到如下：

(8)

代入數值可知，對于大多數n值，當q=0.5和h=1時，pS≈0.721。檢測到h個空閑時隙后，一個節點成為唯一獲勝者的概率為：

(9)

由近似式(9)得到的數值結果與精確式(7)的數值結果很接近，例如，對于n=50時誤差在±0.02以內。

2.3 信道利用率

平均信道利用率ρ由一個周期中有用數據傳輸的持續時間Tm除以該周期的持續時間再乘以該周期中成功發送的概率，即：

(10)

2.4 最佳參數的確定

采用數值技術和式(10)并結合表1中給定的其他一些參數可計算最佳參數h和q。對于給定的h，存在相應的最佳q值。h越低，q越高，反之亦然。對于大范圍的n值、h=4和q=0.5可以接近最佳值，在后面的分析和仿真中，除非另有說明，將采用h=4和q=0.5。

2.5 Jain公平性指數

前面分析中的信道利用率與歸一化總吞吐量是相同的，即總吞吐量除以調制速率就是信道利用率；而Jain公平性指數是一種度量公平性的指標，即資源分配的平等性。Jain公平性指數為1表示絕對公平，數值越低(最小值為零)，表示不公平程度越高。Jain公平性指數定義為[18]：

(11)

式中,xi為節點i的吞吐量。

2.6 實現差異化服務的優先級機制

本節通過引入優先級向量將REB & PMDS擴展為一個簡單的優先機制，目的是通過相對優先級實現差異化服務。

針對IEEE 802.11網絡提出了3種基本的服務機制：設置不同的CW[19]、允許高優先級業務使用較短的IFS 和限制最大傳輸時間。在IEEE 802.11 e中，所有這些機制都以服務類別的形式組合在一起，每個服務類別都是上述因素的特定組合[20]。在IEEE 802.11中，這種搶占式優先級可以通過2種機制來實現：為每個優先級類別設置最佳爭用窗口或為每個類別設置固定爭用窗口。

2.6.1 最佳爭用窗口

不同的CW可以這樣設置：首先計算每個優先級類別的最佳p-堅持傳輸概率：

(12)

(13)

式中,P為優先級類別的數量，ni為類別i中節點的數量。最后得到期望的爭用窗口大小為：

(14)

2.6.2 固定爭用窗口

2.6.3 本文提出的差異化服務優先級機制

在本文的REB & PMDS算法中，如果一個時隙為忙，則停留在爭用的概率為：

P(停留)=P(停留(A=cs)p+P(停留(A=tx)q

(15)

在基本機制P(停留|A=cs, 信道忙)=0和P(停留|A=tx)=1中，可得到P(停留|信道忙)=q=0.5。調整兩種“停留”概率中的任何一種，如通過給予節點額外的生存期，將意味著在無線媒體中可用的信息與某些節點的內部狀態之間存在差異，這樣就得到一個基于對每個節點調整q的機制。由于爭用中的時隙數量事先是未知的，具有不相等但固定的q值將使預測一類節點的最終優先級變得困難。因此，我們選擇通過為每個節點和時隙分配不同的q值來實現。

分析表明，具有q={1,0.5,0.5,…}的節點在第一次消除中獲勝的概率是原來的2倍，它相當于2個虛擬節點。基本優先級向量為q={0.5,0.5,…}。對于任意的q向量，獲勝概率即相對優先級可以計算為：

(16)

式中,k為消除長度。注意，qi(j)(j>k)的元素對最終結果沒有任何影響。為了簡化分析，假設對于任意的j≤≈k，qi(j)=0.5。

(17)

3 仿真結果與分析

為便于比較，對提出的REB & PMDS稍作改進，得到一種稱為REB & PMDS-β的改進形式。在REB & PMDS-β中，用合適的RTS數據包取代消除突發，把每個時隙分為2部分。第一部分中每個節點隨機選擇發送或不發送一個RTS數據包。非發送節點偵聽信道并在信道忙時離開爭用。第二部分中節點視情況發送CTS數據包，除非一個節點接收到一個CTS數據包，否則它將在最大h次消除內保持爭用。

首先采用在飽和條件下的仿真來驗證解析模型，然后通過在可變負荷條件下的仿真來擴展研究，并在信道利用率和公平性方面與IEEE 802.11、REB & PMDS-β和DQRAP-WN的性能進行比較。

3.1 仿真環境及模型

采用GloMoSim仿真器環境。對于物理層建模，采用一個沒有額外衰落的簡單雙射線傳播模型，仿真區域為邊長=200 m的正方形。對于不同仿真情形，發送方的數量n可變。假設沒有移動性，且在仿真區域內隨機設置每個發送方的位置。更多仿真參數見表1；每個發送方根據泊松過程發送數據包，速率為每秒發送λ個數據包。對于每次發送，接收方都是從每個發送方的鄰居中均勻選擇的。

3.2 仿真結果

圖2(a)為本文REB & PMDS協議算法與DQRAP-WN、EY-NPMA和IEEE 802.11協議的信道利用率的解析計算比較結果，圖2(b)為在飽和條件下，隨著競爭發送方數量的增加，對于REB & PMDS、REB & PMDS-β、DQRAP-WN和IEEE 802.11的信道利用率的實際仿真結果。其中EY-NPMA值與其他協議采用相同的時隙長度、幀間間隔、數據包長度和開銷；從圖2可見，REB & PMDS和IEEE 802.11的分析結果與仿真結果吻合較好，分析模型對REB & PMDS的仿真結果有輕微高估。當存在許多節點時，分析模型低估了IEEE 802.11的信道利用率。這是因為該模型沒有考慮到所有影響IEEE 802.11性能的相關參數，例如擴展的IFS (Extended IFS,EIFS)。圖2(a)中的DQRAP-WN是對仿真DQRAP-WN結果的良好預測器。總之，仿真結果驗證了分析的正確性。

從圖2(b)還可看見，當n增加時，REB & PMDS和DQRAP-WN的性能穩定，而對于IEEE 802-11和REB & PMDS-β，信道利用率略有下降；當n較小時，DQRAP-WN有較小的下降。這是反饋機制的結果。如果一個節點在另一個時隙發送數據，那么它只能為一個小時隙提供反饋。如果所有節點都選擇相同的小時隙，且在處理隊列或傳輸隊列中沒有節點，那么就不會有任何節點為特定的時隙提供反饋。當n很小時，這種情況更有可能發生。結果是不正確的反饋導致不連貫的隊列狀態，最終導致數據時隙碰撞。

圖2 DQRAP-WN、IEEE 802.11、REB & PMDS和 REB & PMDS-β的信道利用率比較

圖3為DQRAP-WN、REB & PMDS-β、REB & PMDS和IEEE 802.11在飽和條件下的公平性隨時間的收斂情況。DQRAP-WN幾乎很快達到理想的公平。采用FIFO隊列的全局連貫狀態的結果。其他3個協議收斂到大致相同的公平性水平，但IEEE 802.11收斂較慢。在引言部分討論了IEEE 802.11協議中的公平性問題。值得注意的是，盡管每個協議的公平性收斂速度或多或少有些慢，但相對排序是相同的。還應當注意到，對于所有協議，服務的數據包的數量是不一樣的，因為吞吐量是不一樣的。采用服務的數據包數量而不采用運行時間不會改變協議的相對排序。

圖3 Jain公平指數作為時間的函數

圖4為對于100個節點時，當總負荷增加時的總吞吐量變化。從圖5可見，REB & PMDS、REB & PMDS-β和DQRAP-WN的總吞吐量都呈線性增加，直到飽和，然后保持穩定；另一方面，IEEE 802.11的吞吐量在達到飽和點后逐漸降低。REB & PMDS達到飽和點的時間要長得多。

圖4 n=100時總吞吐量作為流量負荷的函數

對于優先級機制，仿真比較3種方法：可變q的REB & PMDS和IEEE 802.11中的最佳CW和固定CW。考慮兩類節點，類型1具有基本優先級，類型2具有優先級r21=5.589 5，這種選擇能在兩個節點之間獲得相對優先級。

圖5 有2個優先級類別的總信道利用率和 每個類別的信道利用率

仿真考慮了2種情形，結果如圖5(a)和(b)所示。圖中對于每種協議從上到下依次為：總信道利用率、高優先級業務信道利用率和低優先級業務信道利用率。可以看到，在這2種情形，REB & PMDS和最佳CW的總信道利用率都是魯棒的，但REB & PMDS略好一些。在固定CW的情形下，IEEE 802.11的總信道利用率迅速下降。

在第一種情形，如圖5(a)所示，基本優先級節點數量固定即n1=50，同時在網絡中注入越來越多的高優先級節點。在REB & PMDS和最佳CW中，高優先級類別的信道所占的份額越來越大，基本優先級類別保持某個份額。在固定CW的情形下，幾乎所有減少的信道利用率都進入了高優先級類別。

在第二種情形，如圖5(b)所示，兩種類別以相同的速度增加。REB & PMDS和最佳CW在類別之間保持恒定的關系，而固定的CW對于基本優先級類別導致份額不斷下降。在維持期望的相對優先級方面，REB & PMDS略優于最佳CW。

4 結束語

本文提出了一種新的無線信道分配協議REB & PMDS。REB & PMDS與EY-NPMA的相似之處在于根據幾何分布采用隨機長度的突發來消除信道訪問節點。不同之處在于突發是未截斷的，允許大量的節點，采用不截斷的消除和非固定突發概率，允許提供相對優先級，而EY-NPMA僅提供非搶占式的絕對優先級，同時REB & PMDS采用反復消除來微調成功概率。

分析和仿真結果表明，REB & PMDS具有較高的信道利用率和成功概率。與IEEE 802.11相比，REB & PMDS的無記憶特性使得每個爭用都獨立于之前的爭用，因而具有良好的公平性。

對于未來的研究，將考慮隱藏終端條件下的性能并分析通過REB & PMDS的TCP/IP業務。進一步的研究還包括與IEEE 802.11e標準進行比較，即研究如何將REB & PMDS上的多播與IEEE 802.11上的單播結合起來。