一種REB&PMDS的無線MAC協(xié)議

彭 聰，陳海榮，范 平

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

0 引言

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

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

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

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

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

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

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

(1)

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

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

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

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

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

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

1 本文提出的REB & PMDS協(xié)議算法

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

假設(shè)信道為分時隙且每個發(fā)送方能夠在每個時隙中執(zhí)行以下2種操作之一：載波偵聽操作或執(zhí)行一個短突發(fā)或干擾發(fā)送。發(fā)送方在每個時隙i以P(Ai=tx)=qi和P(Ai=cs)=1-qi=pi隨機選擇執(zhí)行哪個動作A。如果發(fā)送方偵聽到一個空閑信道，它就添加一個計數(shù)器IdleSlots。當IdleSlots=h時，則認為已贏得信道并開始發(fā)送。算法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所示。圖中灰色梯形為消除突發(fā)，白色梯形為載波偵聽操作，寬的深灰色梯形為數(shù)據(jù)發(fā)送。示例中n=6，h=4和q=0.5。最初，所有節(jié)點在隨機執(zhí)行載波偵聽(Ai=cs)或消除突發(fā)發(fā)送(Ai=tx)之前等待一個TIFS。在示例中，S2和S5偵聽到信道繁忙并離開爭用。在接下來的時隙中，S3和S6被消除。剩下的節(jié)點S1和S4在第一次消除中存活下來，并進入到第二次節(jié)點S1的消除中。S4執(zhí)行兩次額外的消除，直至IdleSlots=h并允許訪問為止。

圖1 有6個節(jié)點的REB & PMDS工作過程

2 算法性能分析

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

2.1 單次消除

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

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

(2)

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

(3)

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

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

(4)

對于較大的n近似為：

(5)

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

2.2 重復消除

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

(6)

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

pS=p1,h(n)

(7)

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

(8)

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

(9)

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

2.3 信道利用率

平均信道利用率ρ由一個周期中有用數(shù)據(jù)傳輸?shù)某掷m(xù)時間Tm除以該周期的持續(xù)時間再乘以該周期中成功發(fā)送的概率，即：

(10)

2.4 最佳參數(shù)的確定

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

2.5 Jain公平性指數(shù)

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

(11)

式中,xi為節(jié)點i的吞吐量。

2.6 實現(xiàn)差異化服務的優(yōu)先級機制

本節(jié)通過引入優(yōu)先級向量將REB & PMDS擴展為一個簡單的優(yōu)先機制，目的是通過相對優(yōu)先級實現(xiàn)差異化服務。

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

2.6.1 最佳爭用窗口

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

(12)

(13)

式中,P為優(yōu)先級類別的數(shù)量，ni為類別i中節(jié)點的數(shù)量。最后得到期望的爭用窗口大小為：

(14)

2.6.2 固定爭用窗口

2.6.3 本文提出的差異化服務優(yōu)先級機制

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

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

(15)

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

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

(16)

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

(17)

3 仿真結(jié)果與分析

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

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

3.1 仿真環(huán)境及模型

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

3.2 仿真結(jié)果

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

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

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

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

圖3 Jain公平指數(shù)作為時間的函數(shù)

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

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

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

圖5 有2個優(yōu)先級類別的總信道利用率和 每個類別的信道利用率

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

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

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

4 結(jié)束語

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

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

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