無線自組織網(wǎng)接入算法研究

魏長(zhǎng)虎

摘要：無線自組織網(wǎng)因其快速自動(dòng)組網(wǎng)和無中心節(jié)點(diǎn)等特性，得到越來越廣泛的應(yīng)用。無線自組網(wǎng)的核心技術(shù)包括MAC層接入技術(shù)和網(wǎng)絡(luò)節(jié)點(diǎn)間的路由算法。不同的MAC接入技術(shù)適用于不同的應(yīng)用場(chǎng)景，本文主要介紹幾種常用的接入技術(shù)，并對(duì)其做簡(jiǎn)要對(duì)比。

關(guān)鍵詞：自組網(wǎng);DCF;MACAW

1. 引言

無線自組網(wǎng)具有單獨(dú)組網(wǎng)能力和自組織的特點(diǎn)，特別適合應(yīng)用于某些特殊場(chǎng)景。MAC層接入技術(shù)作為其核心技術(shù)，一直都是專家們研究的熱點(diǎn)內(nèi)容。MAC層接入機(jī)制主要有競(jìng)爭(zhēng)機(jī)制和預(yù)留機(jī)制以及混合機(jī)制三種方式。本文將分別介紹每一分類的特點(diǎn)及其典型的代表算法，并簡(jiǎn)要對(duì)比其優(yōu)缺點(diǎn)。

2.MAC層接入算法

自組網(wǎng)的接入在OSI模型的數(shù)據(jù)鏈路層實(shí)現(xiàn)，具體來講，應(yīng)該是在數(shù)據(jù)鏈路層的媒介接入控制子層（MAC）實(shí)現(xiàn)。MAC層主要用來解決多個(gè)節(jié)點(diǎn)高效、合理地共享有限的信道資源這一問題，其主要工作內(nèi)容包括信道劃分，信道接入，信道分配。其中信道接入主要有競(jìng)爭(zhēng)機(jī)制，預(yù)留機(jī)制，混合機(jī)制三種（圖1）。

2.1 競(jìng)爭(zhēng)機(jī)制

介紹競(jìng)爭(zhēng)機(jī)制接入方式的三個(gè)代表：分布式協(xié)調(diào)功能DCF（distributed coordination function），MACAW （Multiple Access with Collision Avoidance for Wireless），MARCH （Media Access with reduced handshake）。其中DCF是所有競(jìng)爭(zhēng)機(jī)制的基礎(chǔ)，其他方式都是在此基礎(chǔ)上的改進(jìn)，重點(diǎn)介紹DCF。

2.1.1 分布式協(xié)調(diào)功能DCF

802.11協(xié)議因其簡(jiǎn)單性、健壯性得到廣泛應(yīng)用，并成為無線ad hoc網(wǎng)絡(luò)的MAC協(xié)議事實(shí)標(biāo)準(zhǔn);802.11有DCP和Point Coordination Function（PCF）兩種接入方式，由于PCF需要AP作為中心來協(xié)調(diào)控制，所以不適用于自組織網(wǎng)絡(luò)，不做討論。

Distributed Coordination Function（DCF） [1]是802.11最基本的媒體接入方式，它的核心是CSMA/CA，包括載波檢測(cè)（CS）機(jī)制、幀間隔（IFS： 節(jié)點(diǎn)連續(xù)發(fā)送兩幀之間的時(shí)間間隔）和隨機(jī)退避 （Random Back-off）規(guī)程。

載波檢測(cè)是用于判斷傳輸媒介是否可用的手段。一般分為物理載波偵聽和虛擬載波偵聽。物理載波偵聽一般用于有線媒介，依賴的是有線線路上的電壓值的變化，常見算法有CSMA/CD等;虛擬載波偵聽一般由軟件實(shí)現(xiàn)，多用于無線媒介。由于物理載波偵聽依賴于有線線路，所以很多情況下其不能提供所有必要信息。802.11協(xié)議中，虛擬載波偵聽通過網(wǎng)絡(luò)分配矢量（Network Allocation Vector，簡(jiǎn)稱NAV） [1] 來實(shí)現(xiàn)。在MAC幀中包含一個(gè)表示時(shí)間長(zhǎng)度的Duration字段，此字段表示接下來某一段時(shí)間由本節(jié)點(diǎn)占用，收到此MAC幀的其它節(jié)點(diǎn)，取出Duration字段后，便可獲知接下來某段時(shí)間媒介處于被占用狀態(tài)，將NAV設(shè)定為此值，并做遞減處理，直到NAV變?yōu)榱?，?jié)點(diǎn)才可以嘗試接入媒介。這便是虛擬載波偵聽的基本原理。

幀間間隔主要有短幀間間隔（Short inter-frame space，簡(jiǎn)稱SIFS），DCF幀間間隔（DCF inter-frame space，簡(jiǎn)稱DIFS）[1]，其使用方法見下面圖2。

隨機(jī)退避。如圖中，DIFS后跟的一段時(shí)間稱為競(jìng)爭(zhēng)窗口（Contention Window），只有在競(jìng)爭(zhēng)窗口時(shí)間之后，才能發(fā)送幀。每當(dāng)幀傳送失敗，就會(huì)從[CWmin，CWmax]間隨機(jī)選一個(gè)時(shí)間作為退避時(shí)間。

有了上面概念，就可以參照?qǐng)D2了解DCF過程了。Sender在經(jīng)過了DIFS和CW后，發(fā)送了RTS幀，receiver收到RTS后，得知sender要向自己發(fā)包，便會(huì)在SIFS之后回復(fù)CTS給sender;sender收到CTS后，在SIFS后發(fā)送data，receiver收到data后，在SIFS后回復(fù)ACK。而other stations在收到了sender的RTS后，得知NAV=3*SIFS+CTS+data+ACK，那么在此時(shí)間內(nèi)不能發(fā)包，在收到CTS后，將NAV更新為2*SIFS+data+ACK。Other stations在NAV時(shí)間過后，再等待DIFS，就可以進(jìn)入下一個(gè)競(jìng)爭(zhēng)周期。

這里注意，通過RTS/CTS接入信道，鄰居節(jié)點(diǎn)獲知本次傳輸所需時(shí)間NAV，在NAV時(shí)間內(nèi)保持靜默，直到傳輸完畢。下面的兩種方式都是對(duì)RTS、CTS做簡(jiǎn)單優(yōu)化。

2.1.2 MACAW

無線通信中存在暴露終端問題，暴露終端通常會(huì)降低媒介使用效率，如圖3，B1是暴露節(jié)點(diǎn)，B2通過及時(shí)發(fā)送DS，告知B1其已經(jīng)與目的節(jié)點(diǎn)握手成功， B1可以靜默并及時(shí)競(jìng)爭(zhēng)信道。這就是MACAW[3]算法。

圖4是另外一種場(chǎng)景，B1發(fā)送RRTS，A1直接發(fā)送RTS，開啟一個(gè)交互過程，避免了暴露節(jié)點(diǎn)帶來的信道資源浪費(fèi)。

2.1.3 MARCH

MARCH[2]減少了多跳傳輸中的RTS開銷;用第N跳中的鄰居節(jié)點(diǎn)的CTS，代替第N+1跳中的RTS;CTS需要擴(kuò)展包含路由信息，以避免干擾。

2.2 預(yù)留機(jī)制

預(yù)留機(jī)制分為動(dòng)態(tài)預(yù)留機(jī)制和固定預(yù)留機(jī)制，各介紹一例。

2.2.1 動(dòng)態(tài)預(yù)留機(jī)制FPRP

FPRP[3]協(xié)議分為預(yù)約階段和信息階段。如圖6所示，RF為預(yù)約階段，IF為信息階段。由于RF為信令幀，IF才能承載數(shù)據(jù)業(yè)務(wù)，所以為提高信道利用率，通常一個(gè)RF后面會(huì)跟著多個(gè)IF，。預(yù)約階段RF又可分為N個(gè)預(yù)約時(shí)隙，記為RS，與之對(duì)應(yīng)的是IF中的信息時(shí)隙IS。很容易聯(lián)想到，一旦某節(jié)點(diǎn)在RF階段預(yù)約成功了，那么緊隨其后的所有IF中對(duì)應(yīng)的IS時(shí)隙都將為本節(jié)點(diǎn)占用，直到下一次預(yù)約。預(yù)約時(shí)隙又由預(yù)約周期RC組成，每個(gè)預(yù)約周期都由5個(gè)發(fā)包單元組成，這5個(gè)發(fā)包單元完成信道預(yù)約的5次握手。

FPRP五次握手：

FPRP協(xié)議的五次握手過程如下：

Step1：Reservation Request（RR）：參與預(yù)約的節(jié)點(diǎn)（預(yù)約節(jié)點(diǎn)RN）在此發(fā)包單元產(chǎn)生并發(fā)送預(yù)約請(qǐng)求幀。其余節(jié)點(diǎn)處于接收狀態(tài)，如果收到多個(gè)RR，則會(huì)產(chǎn)生沖突，檢測(cè)到?jīng)_突的節(jié)點(diǎn)向RN報(bào)告沖突，如step2。

Step2：Collision Report（CR）：某節(jié)點(diǎn)在step1收到兩個(gè)以上的RR幀，表明發(fā)生了預(yù)約沖突，節(jié)點(diǎn)要報(bào)告此沖突;如果收到一個(gè)RR幀，則表明沒有預(yù)約沖突，節(jié)點(diǎn)無動(dòng)作。在這個(gè)發(fā)包單元，step1中的RN處于接收狀態(tài)，如果RN沒有收到?jīng)_突報(bào)告，則可以作為發(fā)送節(jié)點(diǎn)（TN）進(jìn)一步預(yù)約時(shí)隙。

Step3：Reservation Confirmation（RC）：TN在此發(fā)包單元產(chǎn)生并發(fā)送預(yù)約批準(zhǔn)幀（RC），收到RC幀的鄰居節(jié)點(diǎn)獲知本時(shí)隙已經(jīng)被預(yù)約，將不會(huì)再競(jìng)爭(zhēng)該時(shí)隙，相應(yīng)IF中的時(shí)隙也將處于接收狀態(tài)。

Step4：Reservation Acknowledgement（RA）：收到RC幀的節(jié)點(diǎn)，在此發(fā)包單元產(chǎn)生并發(fā)送RA幀，收到RA的TN節(jié)點(diǎn)，繼續(xù)執(zhí)行step5，沒收到的則預(yù)約失敗。RA的另外一個(gè)功能是，通知其兩跳鄰居，該時(shí)隙已經(jīng)被預(yù)約成功。

Step5：Packing/Elimination：在此發(fā)包單元中，TN的兩跳鄰居產(chǎn)生并發(fā)送PP幀，某節(jié)點(diǎn)收到PP幀，則可以獲悉三跳以外節(jié)點(diǎn)預(yù)約到了時(shí)隙，即此節(jié)點(diǎn)的二跳鄰居不會(huì)競(jìng)爭(zhēng)此時(shí)隙，接下來本節(jié)點(diǎn)就可以競(jìng)爭(zhēng)此時(shí)隙。在此發(fā)包單元，還由TN隨機(jī)性的發(fā)出EP幀，收到EP幀的TN不再成功預(yù)約此時(shí)隙。

2.2.2 固定預(yù)留機(jī)制-基本TDMA協(xié)議

TDMA[3]協(xié)議中，時(shí)隙作為主要資源，是按照節(jié)點(diǎn)固定預(yù)留的。一組時(shí)隙形成一個(gè)時(shí)隙幀，如下圖列出了N個(gè)時(shí)隙幀，幀內(nèi)的各個(gè)時(shí)隙按照約定的算法分配給各個(gè)節(jié)點(diǎn)。

Slot1 Slot2 Slot3 …… SlotN

算法優(yōu)點(diǎn)：幾乎不存在控制協(xié)議方面的開銷，算法簡(jiǎn)單且公平。

算法缺點(diǎn)：時(shí)隙幀的循環(huán)周期長(zhǎng)度由網(wǎng)絡(luò)中的節(jié)點(diǎn)個(gè)數(shù)決定，較大規(guī)模的網(wǎng)絡(luò)，其時(shí)延顯著增加。此外，由于各個(gè)節(jié)點(diǎn)平均分配時(shí)隙，導(dǎo)致節(jié)點(diǎn)的高優(yōu)先級(jí)業(yè)務(wù)得不到高優(yōu)先級(jí)響應(yīng)，不具備QoS特性。

2.3 混合機(jī)制

本文暫不詳細(xì)介紹混合機(jī)制。

3. 結(jié)束語

MAC接入技術(shù)在很大程度上影響著自組織網(wǎng)的性能，根據(jù)網(wǎng)絡(luò)的規(guī)模、具體的業(yè)務(wù)場(chǎng)景、以及成本的考慮，選擇合適的算法尤為重要。本文介紹了幾種常用算法的原理，但由于時(shí)間原因，還沒有給出對(duì)應(yīng)算法的仿真結(jié)果。對(duì)算法的仿真將是本人下一步的研究重點(diǎn)。

參考文獻(xiàn)：

[1] Mattbew S. Gast. 802.11無線網(wǎng)絡(luò)權(quán)威指南第二版[M]. 南京.東南大學(xué)出版社，2007.

[2] 楊銀輝，吳國(guó)新. 移動(dòng)自組網(wǎng)的MAC層研究與展望[J]. 數(shù)據(jù)通信. 2005. （3）：13-16.

[3] 高建康. 對(duì)802.11分布式協(xié)調(diào)功能的初步探討. 通信與信息系統(tǒng). 2013.（20）.