無線自組織網接入算法研究

魏長虎

摘要：無線自組織網因其快速自動組網和無中心節點等特性，得到越來越廣泛的應用。無線自組網的核心技術包括MAC層接入技術和網絡節點間的路由算法。不同的MAC接入技術適用于不同的應用場景，本文主要介紹幾種常用的接入技術，并對其做簡要對比。

關鍵詞：自組網;DCF;MACAW

1. 引言

無線自組網具有單獨組網能力和自組織的特點，特別適合應用于某些特殊場景。MAC層接入技術作為其核心技術，一直都是專家們研究的熱點內容。MAC層接入機制主要有競爭機制和預留機制以及混合機制三種方式。本文將分別介紹每一分類的特點及其典型的代表算法，并簡要對比其優缺點。

2.MAC層接入算法

自組網的接入在OSI模型的數據鏈路層實現，具體來講，應該是在數據鏈路層的媒介接入控制子層（MAC）實現。MAC層主要用來解決多個節點高效、合理地共享有限的信道資源這一問題，其主要工作內容包括信道劃分，信道接入，信道分配。其中信道接入主要有競爭機制，預留機制，混合機制三種（圖1）。

2.1 競爭機制

介紹競爭機制接入方式的三個代表：分布式協調功能DCF（distributed coordination function），MACAW （Multiple Access with Collision Avoidance for Wireless），MARCH （Media Access with reduced handshake）。其中DCF是所有競爭機制的基礎，其他方式都是在此基礎上的改進，重點介紹DCF。

2.1.1 分布式協調功能DCF

802.11協議因其簡單性、健壯性得到廣泛應用，并成為無線ad hoc網絡的MAC協議事實標準;802.11有DCP和Point Coordination Function（PCF）兩種接入方式，由于PCF需要AP作為中心來協調控制，所以不適用于自組織網絡，不做討論。

Distributed Coordination Function（DCF） [1]是802.11最基本的媒體接入方式，它的核心是CSMA/CA，包括載波檢測（CS）機制、幀間隔（IFS： 節點連續發送兩幀之間的時間間隔）和隨機退避 （Random Back-off）規程。

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

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

隨機退避。如圖中，DIFS后跟的一段時間稱為競爭窗口（Contention Window），只有在競爭窗口時間之后，才能發送幀。每當幀傳送失敗，就會從[CWmin，CWmax]間隨機選一個時間作為退避時間。

有了上面概念，就可以參照圖2了解DCF過程了。Sender在經過了DIFS和CW后，發送了RTS幀，receiver收到RTS后，得知sender要向自己發包，便會在SIFS之后回復CTS給sender;sender收到CTS后，在SIFS后發送data，receiver收到data后，在SIFS后回復ACK。而other stations在收到了sender的RTS后，得知NAV=3*SIFS+CTS+data+ACK，那么在此時間內不能發包，在收到CTS后，將NAV更新為2*SIFS+data+ACK。Other stations在NAV時間過后，再等待DIFS，就可以進入下一個競爭周期。

這里注意，通過RTS/CTS接入信道，鄰居節點獲知本次傳輸所需時間NAV，在NAV時間內保持靜默，直到傳輸完畢。下面的兩種方式都是對RTS、CTS做簡單優化。

2.1.2 MACAW

無線通信中存在暴露終端問題，暴露終端通常會降低媒介使用效率，如圖3，B1是暴露節點，B2通過及時發送DS，告知B1其已經與目的節點握手成功， B1可以靜默并及時競爭信道。這就是MACAW[3]算法。

圖4是另外一種場景，B1發送RRTS，A1直接發送RTS，開啟一個交互過程，避免了暴露節點帶來的信道資源浪費。

2.1.3 MARCH

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

2.2 預留機制

預留機制分為動態預留機制和固定預留機制，各介紹一例。

2.2.1 動態預留機制FPRP

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

FPRP五次握手：

FPRP協議的五次握手過程如下：

Step1：Reservation Request（RR）：參與預約的節點（預約節點RN）在此發包單元產生并發送預約請求幀。其余節點處于接收狀態，如果收到多個RR，則會產生沖突，檢測到沖突的節點向RN報告沖突，如step2。

Step2：Collision Report（CR）：某節點在step1收到兩個以上的RR幀，表明發生了預約沖突，節點要報告此沖突;如果收到一個RR幀，則表明沒有預約沖突，節點無動作。在這個發包單元，step1中的RN處于接收狀態，如果RN沒有收到沖突報告，則可以作為發送節點（TN）進一步預約時隙。

Step3：Reservation Confirmation（RC）：TN在此發包單元產生并發送預約批準幀（RC），收到RC幀的鄰居節點獲知本時隙已經被預約，將不會再競爭該時隙，相應IF中的時隙也將處于接收狀態。

Step4：Reservation Acknowledgement（RA）：收到RC幀的節點，在此發包單元產生并發送RA幀，收到RA的TN節點，繼續執行step5，沒收到的則預約失敗。RA的另外一個功能是，通知其兩跳鄰居，該時隙已經被預約成功。

Step5：Packing/Elimination：在此發包單元中，TN的兩跳鄰居產生并發送PP幀，某節點收到PP幀，則可以獲悉三跳以外節點預約到了時隙，即此節點的二跳鄰居不會競爭此時隙，接下來本節點就可以競爭此時隙。在此發包單元，還由TN隨機性的發出EP幀，收到EP幀的TN不再成功預約此時隙。

2.2.2 固定預留機制-基本TDMA協議

TDMA[3]協議中，時隙作為主要資源，是按照節點固定預留的。一組時隙形成一個時隙幀，如下圖列出了N個時隙幀，幀內的各個時隙按照約定的算法分配給各個節點。

Slot1 Slot2 Slot3 …… SlotN

算法優點：幾乎不存在控制協議方面的開銷，算法簡單且公平。

算法缺點：時隙幀的循環周期長度由網絡中的節點個數決定，較大規模的網絡，其時延顯著增加。此外，由于各個節點平均分配時隙，導致節點的高優先級業務得不到高優先級響應，不具備QoS特性。

2.3 混合機制

本文暫不詳細介紹混合機制。

3. 結束語

MAC接入技術在很大程度上影響著自組織網的性能，根據網絡的規模、具體的業務場景、以及成本的考慮，選擇合適的算法尤為重要。本文介紹了幾種常用算法的原理，但由于時間原因，還沒有給出對應算法的仿真結果。對算法的仿真將是本人下一步的研究重點。

參考文獻：

[1] Mattbew S. Gast. 802.11無線網絡權威指南第二版[M]. 南京.東南大學出版社，2007.

[2] 楊銀輝，吳國新. 移動自組網的MAC層研究與展望[J]. 數據通信. 2005. （3）：13-16.

[3] 高建康. 對802.11分布式協調功能的初步探討. 通信與信息系統. 2013.（20）.