淺談Ad-Hoc網(wǎng)絡(luò)中的單信道接入?yún)f(xié)議

潘星宇陳鳳玲/ .鄭州華航科技股份有限公司.鄭州電力高等?？茖W(xué)校

淺談Ad-Hoc網(wǎng)絡(luò)中的單信道接入?yún)f(xié)議

潘星宇1陳鳳玲2/ 1.鄭州華航科技股份有限公司2.鄭州電力高等專科學(xué)校

單信道接入?yún)f(xié)議是Ad-Hoc網(wǎng)絡(luò)中的一類重要M AC層協(xié)議。通過(guò)分析具有代表性的M ACA協(xié)議及其改進(jìn)協(xié)議，對(duì)比它們的優(yōu)缺點(diǎn)和不同之處，對(duì)協(xié)議的后續(xù)改進(jìn)方向提出了建議。

M ACA；M ACAW；M ACA-BI；M ACA-PR

引言

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

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

0. MACA協(xié)議

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

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

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

圖 1 MACA協(xié)議報(bào)文沖突示意圖

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

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

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

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

由以上可以得出MACA的缺點(diǎn)如下：

(1)不具備鏈路確認(rèn)機(jī)制即ACK應(yīng)答，這勢(shì)必要加重傳輸層的負(fù)擔(dān)；

(2)退避算法具有明顯的缺陷；

(3)不能解決控制報(bào)文之間的沖突；

(4)僅部分解決了“隱藏終端”的問(wèn)題，完全沒(méi)有解決“暴露終端”的問(wèn)題。

當(dāng)然，MACA也有其優(yōu)點(diǎn)：

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

(2)部分解決了“隱藏終端”的問(wèn)題。

1. MACAW協(xié)議

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

MACAW，MACA同MACA協(xié)議，而W則是為了無(wú)線傳輸(for wireless)的意思。MACAW協(xié)議針對(duì)MACA協(xié)議改進(jìn)了其控制報(bào)文分組和退避算法兩個(gè)方面。

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

圖 2 MACAW協(xié)議流程圖

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

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

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

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

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

(1)加入DS報(bào)文，一定程度上解決了“暴露終端”的問(wèn)題；

(2)加入ACK應(yīng)答機(jī)制，使鏈路層具有錯(cuò)誤重傳機(jī)制，降低了傳輸層的負(fù)擔(dān)；

(3)改進(jìn)了退避算法，很大程度上提升了信道競(jìng)爭(zhēng)的公平性；

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

然而MACAW仍有以下兩個(gè)缺點(diǎn)：

(1)控制報(bào)文過(guò)于復(fù)雜，交互次數(shù)多，開(kāi)銷大；

(2)仍然只是部分解決了“暴露終端”和“隱藏終端”的問(wèn)題。

2 .MACA-BI協(xié)議

MACA-BI是四個(gè)協(xié)議中唯一一個(gè)接收節(jié)點(diǎn)主動(dòng)的協(xié)議。BI即通過(guò)邀請(qǐng)的意思。它的流程如圖3所示：

圖 3 MACA-BI流程圖與MACA對(duì)比

作為一個(gè)接收節(jié)點(diǎn)主動(dòng)的協(xié)議，MACA-BI協(xié)議不使用RTSCTS控制報(bào)文，而是接收節(jié)點(diǎn)向發(fā)送節(jié)點(diǎn)發(fā)送一個(gè)RTR(準(zhǔn)備好接收了)報(bào)文，之后發(fā)送節(jié)點(diǎn)再向接收節(jié)點(diǎn)發(fā)送數(shù)據(jù)。

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

3. MACA-PR協(xié)議

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

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

圖 4 MACA-PR協(xié)議流程圖

MACA-PR協(xié)議中，發(fā)送節(jié)點(diǎn)與接收節(jié)點(diǎn)之間首先也會(huì)建立RTS-CTS控制報(bào)文分組，之后就靠PKT-ACK分組來(lái)進(jìn)行數(shù)據(jù)的傳輸，每?jī)蓚€(gè)PKT之間間隔一定的時(shí)間，只有當(dāng)N次未收到ACK應(yīng)答時(shí)，才重新建立RTS-CTS分組。同時(shí)，每個(gè)分組中都會(huì)捎帶下一個(gè)分組的預(yù)約信息。

MACA-PR協(xié)議中，當(dāng)預(yù)約表穩(wěn)定時(shí)，數(shù)據(jù)發(fā)送不會(huì)產(chǎn)生沖突，也不會(huì)有“隱藏終端”和“暴露終端”的問(wèn)題，因?yàn)槊總€(gè)節(jié)點(diǎn)都會(huì)在規(guī)定的窗口時(shí)間內(nèi)發(fā)送數(shù)據(jù)。但是當(dāng)節(jié)點(diǎn)發(fā)生移動(dòng)或者預(yù)約表沒(méi)有及時(shí)更新時(shí)會(huì)出現(xiàn)暫時(shí)的沖突。

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

4.總結(jié)

MACA協(xié)議及其三種改進(jìn)協(xié)議的對(duì)比如表1所示：

表 1 MACA及其改進(jìn)協(xié)議對(duì)比

通過(guò)以上分析，MACA協(xié)議及其改進(jìn)協(xié)議有有一些共同的問(wèn)題：

(1)控制報(bào)文要盡可能的優(yōu)化；

(2)退避算法要保證公平性；

(3)盡量提高信道利用率；

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

(5)“隱藏終端”和“暴露終端”的問(wèn)題。

這些也是MACA協(xié)議后續(xù)改進(jìn)協(xié)議應(yīng)該考慮的問(wèn)題及研究的方向。

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

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

[3]楊春等，無(wú)線傳感器網(wǎng)絡(luò)經(jīng)典MAC協(xié)議驗(yàn)證與分析.

[4]董學(xué)潤(rùn)，移動(dòng)Ad hoc 網(wǎng)絡(luò)的單信道媒體接入?yún)f(xié)議.

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

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