淺談Ad—Hoc網絡中的單信道接入?yún)f(xié)議

潘星宇 陳鳳玲

【摘 要】單信道接入?yún)f(xié)議是Ad-Hoc網絡中的一類重要MAC層協(xié)議。通過分析具有代表性的MACA協(xié)議及其改進協(xié)議，對比它們的優(yōu)缺點和不同之處，對協(xié)議的后續(xù)改進方向提出了建議。

【關鍵詞】MACA；MACAW；MACA-BI；MACA-PR

引言

單信道接入?yún)f(xié)議是基于這樣一個模型：即只有一個共享信道，所有的控制報文和數(shù)據(jù)報文都在一個信道上發(fā)送和接收。單信道的Ad-Hoc網絡有可能在控制報文之間、控制報文和數(shù)據(jù)報文以及數(shù)據(jù)報文之間發(fā)生沖突。一般來講數(shù)據(jù)報文要比控制報文長得多，所以數(shù)據(jù)報文更容易發(fā)生沖突，從而影響信道的利用率。如何通過控制報文減少甚至消除數(shù)據(jù)報文的沖突，設計出合理的沖突避免策略，是單信道接入?yún)f(xié)議的主要目標之一。

經典的基于單信道的Ad-Hoc接入?yún)f(xié)議有MACA協(xié)議以及它的三種改進協(xié)議MACAW、MACAW-BI、MACA-PR。

0. MACA協(xié)議

多路訪問沖突避免（multiple access collision avoidance）簡稱MACA，它起源于CSMA/CA（載波監(jiān)聽多路訪問/沖突避免）協(xié)議。CSMA/CA基于以下思想：多個節(jié)點同時監(jiān)聽載波信道，若信道閑，則發(fā)送數(shù)據(jù)；反之，就進行退避直到信道閑為止。然而由于“隱藏終端”的存在，即使監(jiān)聽到信道閑也未必能成功發(fā)送數(shù)據(jù)；另外由于“暴露終端”的存在，即使監(jiān)聽到信道忙也未必不能發(fā)送數(shù)據(jù)。所以CSMA/CA的CS常常是無效的，所以去掉載波監(jiān)聽即CA，該協(xié)議就演變成了MACA。

MACA的主要思想就是通過控制報文避免數(shù)據(jù)報文的沖突。當發(fā)送節(jié)點向接收節(jié)點發(fā)送RTS控制報文時，接收節(jié)點會向相鄰的節(jié)點發(fā)送CTS控制報文，從而相鄰的節(jié)點將被阻塞一段時間，這樣當發(fā)送節(jié)點向接收節(jié)點發(fā)送數(shù)據(jù)時，接收節(jié)點附近的相鄰節(jié)點就不會向接收節(jié)點發(fā)送數(shù)據(jù)，從而不會產生數(shù)據(jù)報文的沖突。

然而以上只是在理想情況下，實際中大多數(shù)情況下，仍會產生報文沖突，如圖1所示：

當接收節(jié)點A向其鄰近節(jié)點B發(fā)送CTS報文時，若正好D也向B發(fā)送RTS報文，此時就會產生控制報文之間的沖突；D由于產生了沖突退避了一段時間之后，再向B發(fā)送RTS報文成功，此時B需要向鄰近節(jié)點A發(fā)送CTS報文，而C正好也要向A發(fā)送數(shù)據(jù)報文，這樣就會產生數(shù)據(jù)報文和控制報文的沖突。

節(jié)點之間一旦發(fā)生沖突，就要進行退避。MACA協(xié)議采用的退避算法為二進制指數(shù)退避算法即BEB算法。其核心計算公式如下所示：

FInc=min（2×COUNTER，MAX）

FDec=FMIN

當沖突產生時，沖突計數(shù)器COUNTER值翻倍并與計數(shù)器上限值MAX比較，取較小的那個值作為新的計數(shù)器的值開始退避計數(shù)；反之，若數(shù)據(jù)發(fā)送成功，則計數(shù)器的值直接取計數(shù)器下限值MIN。

BEB算法具有明顯兩個缺點：第一，一次交互成功的節(jié)點計數(shù)器的值就歸于最小值，不能反映信道的爭用情況；第二，帶來不公平現(xiàn)象，交互成功的節(jié)點計數(shù)器的值小，而失敗的節(jié)點計數(shù)器的值大，在后續(xù)的競爭中，前者獲勝的概率更大。

由以上可以得出MACA的缺點如下：

（1）不具備鏈路確認機制即ACK應答，這勢必要加重傳輸層的負擔；

（2）退避算法具有明顯的缺陷；

（3）不能解決控制報文之間的沖突；

（4）僅部分解決了“隱藏終端”的問題，完全沒有解決“暴露終端”的問題。

當然，MACA也有其優(yōu)點：

（1）提高了信道利用率，由于采用了RTS-CTS控制報文分組，一般控制報文比數(shù)據(jù)報文短得多，這樣沖突的時間和概率都比不采用控制報文時大大降低了；

（2）部分解決了“隱藏終端”的問題。

1. MACAW協(xié)議

由于MACA協(xié)議的優(yōu)點可以繼承，而缺點需要改進，就產生了MACA的改進協(xié)議，在這些改進協(xié)議中，MACAW協(xié)議是最接近MACA協(xié)議的。

MACAW，MACA同MACA協(xié)議，而W則是為了無線傳輸（for wireless）的意思。MACAW協(xié)議針對MACA協(xié)議改進了其控制報文分組和退避算法兩個方面。

在控制報文分組方面，加入了DS-ACK報文，如圖2所示：

其中，D是A的“隱藏終端”，C是A的“暴露終端”。對比圖1，MACAW在“隱藏終端”方面并沒有作出改進。當A向B發(fā)送數(shù)據(jù)時，先發(fā)送RTS報文，之后B向相鄰節(jié)點發(fā)送CTS報文，A在發(fā)送數(shù)據(jù)報文之前，還要發(fā)送一組DS報文，之后發(fā)送數(shù)據(jù)報文，當數(shù)據(jù)報文接收成功后，B還要回傳ACK應答。

DS報文用于解決“暴露終端”的問題，當C收到A的RTS報文之后，它會處于阻塞中，若之后未收到DS報文，證明A的RTS-CTS報文交換失敗，此時D就無需等待，可以發(fā)送數(shù)據(jù)；反之若D在收到A的RTS報文之后又收到了DS報文，則D就必須繼續(xù)處于阻塞狀態(tài)一段時間后，才能夠向A發(fā)送數(shù)據(jù)。實際上DS報文就是“暴露終端”用于確認自己身份的控制報文。

MACAW協(xié)議針對MACA的BEB算法作出了改進，它采用倍數(shù)增線性減算法即MILD。其核心計算公式如下所示：

FInc=min（α×COUNTER，MAX）

FDec=max（COUNTER-β，MIN）

對比BEB算法，交換失敗后，節(jié)點計數(shù)器COUNTER不再固定翻倍，而是乘以一個系數(shù)α，若α值選取適合，則沖突后計數(shù)器的值不會急劇增加；同時，交互失敗后，計數(shù)器的值也不會固定變?yōu)樽钚≈?，而是減去一個可調的值β，若β值選取合適，則各節(jié)點后續(xù)競爭獲勝幾率幾乎相等，實現(xiàn)了公平接入。

由以上可以看出MACAW的優(yōu)點如下：

（1）加入DS報文，一定程度上解決了“暴露終端”的問題；

（2）加入ACK應答機制，使鏈路層具有錯誤重傳機制，降低了傳輸層的負擔；

（3）改進了退避算法，很大程度上提升了信道競爭的公平性；

（4）相比MACA協(xié)議，系統(tǒng)的吞吐量顯著提升。

然而MACAW仍有以下兩個缺點：

（1）控制報文過于復雜，交互次數(shù)多，開銷大；

（2）仍然只是部分解決了“暴露終端”和“隱藏終端”的問題。

2 .MACA-BI協(xié)議

MACA-BI是四個協(xié)議中唯一一個接收節(jié)點主動的協(xié)議。BI即通過邀請的意思。它的流程如圖3所示：

作為一個接收節(jié)點主動的協(xié)議，MACA-BI協(xié)議不使用RTS-CTS控制報文，而是接收節(jié)點向發(fā)送節(jié)點發(fā)送一個RTR（準備好接收了）報文，之后發(fā)送節(jié)點再向接收節(jié)點發(fā)送數(shù)據(jù)。

MACA-BI適用于業(yè)務模式可以預測的Ad-Hoc網絡中，其優(yōu)點在于減少了控制報文的交互次數(shù)，提高了系統(tǒng)的吞吐量，但缺點是對于突發(fā)性的性業(yè)務，MACA-BI協(xié)議就相當于MACA協(xié)議。

3. MACA-PR協(xié)議

MACA-PR協(xié)議的PR是捎帶預約的意思。該協(xié)議中，節(jié)點發(fā)送數(shù)據(jù)前，需要等待預約表中有空閑的窗口（即時隙），只有當有空閑的窗口時才會去監(jiān)聽信道是否空閑，空閑時發(fā)送數(shù)據(jù)。并且每一個節(jié)點都負責一個預約表，該表記錄該節(jié)點傳輸范圍內的任何發(fā)送和接收窗口。

所以，MACA-PR實際上是一個基于時分復用的協(xié)議。

MACA-PR協(xié)議中，發(fā)送節(jié)點與接收節(jié)點之間首先也會建立RTS-CTS控制報文分組，之后就靠PKT-ACK分組來進行數(shù)據(jù)的傳輸，每兩個PKT之間間隔一定的時間，只有當N次未收到ACK應答時，才重新建立RTS-CTS分組。同時，每個分組中都會捎帶下一個分組的預約信息。

MACA-PR協(xié)議中，當預約表穩(wěn)定時，數(shù)據(jù)發(fā)送不會產生沖突，也不會有“隱藏終端”和“暴露終端”的問題，因為每個節(jié)點都會在規(guī)定的窗口時間內發(fā)送數(shù)據(jù)。但是當節(jié)點發(fā)生移動或者預約表沒有及時更新時會出現(xiàn)暫時的沖突。

MACA-PR協(xié)議優(yōu)點是預約表穩(wěn)定時，可以完全避免沖突和解決“隱藏終端”及“暴露終端”的問題，缺點是，路由表的維護增加了節(jié)點的能量開銷，同時由于Ad-Hoc網絡的移動性特點，預約表總是處于暫時穩(wěn)定的狀態(tài)，需要時時更新。

4.總結

通過以上分析，MACA協(xié)議及其改進協(xié)議有有一些共同的問題：

（1）控制報文要盡可能的優(yōu)化；

（2）退避算法要保證公平性；

（3）盡量提高信道利用率；

（4）由于節(jié)點大多使用電池，要降低能耗；

（5）“隱藏終端”和“暴露終端”的問題。

這些也是MACA協(xié)議后續(xù)改進協(xié)議應該考慮的問題及研究的方向。

參考文獻：

[1]吳亞平，MACA-PR協(xié)議淺析.

[2]杜成，MACA協(xié)議的研究.

[3]楊春等，無線傳感器網絡經典MAC協(xié)議驗證與分析.

[4]董學潤，移動Ad hoc 網絡的單信道媒體接入?yún)f(xié)議.

[5]何俊，移動自組織網絡中的MAC協(xié)議分析比較.

[6]EEFOCUS，Ad hoc幾種接入?yún)f(xié)議.