基于ＦＰＲＰ的無線自組織網的ＭＡＣ協議

摘要：基于FPRP的用于同步無線自組織網的MAC協議采用分布式控制和同步競爭接入，能夠支持QoS業務的傳輸，較好地解決了隱藏終端和暴露終端問題。仿真結果表明，該協議在吞吐率和媒體接入時延上較同步FPRP有所提高。

關鍵詞：多跳無線網;媒體接入控制;五階段預留協議

中圖分類號：TN925．93文獻標志碼：A

文章編號：1001－3695(2008)01－0068－03

多跳無線網(也稱Ad hoc網絡)以其廣泛的應用前景，目前已成為無線通信領域發展的熱點之一。由于多跳無線網絡是一種特殊的分布式對等網絡，網絡中沒有中心控制器；與傳統網絡相比，它又是一個多跳共享的信道，一般的無線媒介接入控制協議都不能直接很好地工作。MAC協議的設計成為多跳無線網絡中的關鍵。目前，在民用領域使用最廣泛的就是IEEE 802.11系列[1]。802.11協議基于CSMA/CA，通過短幀RTS/CTS信息的交互，分配幀長大于RTS/CTS的數據幀，從而提高無線資源的利用率。但是協議沒能完全解決隱藏終端和暴露終端的問題，QoS和公平接入問題也有待進一步完善。這些問題最終都會給網絡容量和傳輸時延帶來負面的影響。因此802.11協議的效率較低。

目前，典型的應用于同步網絡的MAC層協議有FPRP[2]、E(evolutionary) TDMA[3]和RR ALOHA[4，5]等。FPRP只是一個廣播調度協議，如果調度單播將導致其效率不高。E TDMA是基于FPRP的改進版本，它與FPRP一樣需要五次握手實現節點的接入。因此，該協議雖然能保證實時業務無沖突地發送，同時也能避免時延抖動，但控制開銷較大、實現復雜、效率不高。在RR ALOHA中，每個節點都要求占用一個basic channel(BC)，因此網絡中每幀所包含的時隙數N應大于網絡中節點的數量。當網絡中節點數較多時，幀的長度也相應增加，效率不高且可擴充性差。

本文提出一種基于FPRP的分布式MAC協議，該協議將信道劃分為控制信道和業務信道兩部分。節點通過在控制信道的競爭獲得業務信道的使用權；通過獲得的控制信道來預約和維護業務信道，并傳遞節點狀態信息。在同步Ad hoc網絡中實現了全分布式的信道接入控制，可以在兩跳范圍內無沖突地為節點預約單播和廣播業務時隙，支持QoS及各種業務。

1改進的FPRP協議

本文所設計的協議適用于全網同步劃分時隙的多跳無線網絡。系統同步可以有兩種實現方式。一種是通過GPS接收機從空間取得高精度的頻率標準，與受控時鐘相配合，節點可以獲得與世界協調時（UTC）為參照的時間基準的時間同步。另一種是通過自校時的方式實現一定精度的時鐘同步。本文所設計的協議要求在支持分組突發業務的同時，充分考慮對實時業務的支持，通過區分服務實現業務的QoS保障。為實現這個目的，采用了優先競爭和非優先競爭信道的劃分、資源周期性預約等機制保證實時業務的傳送。另外，通過對一跳鄰居預約過程的感知，增加了資源競爭的成功率，較好地解決了隱藏、暴露終端問題。

1．1信道的劃分

無線網絡發展之初，受到硬件和軟件環境的限制，主要是使用單信道，由此而發展出了一批典型的有實用價值的MAC協議。在民用領域使用最廣泛的就是IEEE 802.11系列。但是單信道無法完全解決隱藏終端和暴露終端問題，并且QoS保障困難，所以后來的MAC協議都向著多信道方向發展。實現多信道的方式有多種辦法，當解決了全網的同步時，TDMA是一種簡潔有效的劃分方式。

本文所設計的協議把信道劃分為一個個的時幀，每個時幀都是一次獨立的信道預約和數據傳送過程。如圖1所示，每個時幀又分為業務信道和控制信道。每個業務信道分為K個信息幀；每個信息幀又分為N個信息時隙。每個控制信道分為前后兩次預約過程。第一次預約過程分為N個預約時隙，分別預約對應序號的業務時隙，每一次成功的預約將占用其后業務信道中序號相同的K個信息時隙，而每個預約時隙包含M次相同的FPRP預約周期；第二次預約過程與第一次預約過程的劃分是基本一致的，其主要目的是解決暴露終端問題，讓網絡承載更多的并行傳輸。其預約時隙包含M0次FPRP預約周期。

1．2協議工作方式

基于多信道的自組網MAC協議用于具有多個信道的自組網絡，它主要研究信道分配和接入控制兩個方面的內容。前者負責為通信節點對分配相應的信道，使盡量多的節點可以無沖突地同時通信；后者負責確定節點接入信道的時機、沖突的避免和解決方式。因此本文的MAC協議主要實現上述兩種功能。TDMA系統中的信道分配就是為網絡中的節點分配發送時隙，實現相鄰節點之間分組的無碰撞傳送，獲得盡可能高的無線信道利用率和空分重用。接入控制主要采用改進的FPRP預約方式，接入概率p采用的是多跳Pseudo Baysian算法[6]。

1．2．1QoS保障機制

區分服務優先級和資源預留是自組織網絡中主要使用的兩種保障QoS的方法。只要能夠使用戶業務的性能達標的方法都可以視為QoS保障。QoS保障需要在每一層實現、多層協調來完成業務的需求。區分服務優先級主要是把所支持的業務歸納為幾類，分配不同的接入優先級別，采用發送概率或退避算法的方式來實現，保證高優先級別的業務能夠高概率地優先占用信道。資源預留方式主要是保留信道的一部分資源，保證恒比特率高優先級業務的信道使用權，對于實時業務總是能夠提供傳輸的信道。

本文所設計的協議采用區分服務的方式實現QoS保障。對于上層給予的數據報文分成三種，分別放在三個不同的數據緩沖區內。這三個數據緩沖區分別是緊急業務區、實時業務區和普通業務區。協議在為數據報文進行預約時，對這三種不同緩沖區內的報文采用的是不同的策略。對于緊急業務是只要存在就高概率地去占用信道，一旦失敗則反復預約；在一個時幀內若沒能預約到信道就向上層報告，然后拋棄失敗的數據報文；實時業務要達到一定數量才能激活預約過程。普通業務則要達到K個數據報文才能激活預約過程。

1．2．2改進的FPRP預約機制

FPRP預約方式是專門針對廣播的調度式接入協議，通過五次握手過程實現時隙的預留。本協議在FPRP的基礎上進行，使其能夠預約單播、組播和廣播以及支持QoS。其預留過程只涉及其兩跳范圍內的站點，是一個本地過程，能夠支持信道在空間上的重用。其算法主要工作步驟如下：

a)預約請求階段(reservation request phase，RR)。在該階段中，當三個緩沖區內有滿足激活預約條件的數據報文時，節點需要預約資源。此時節點以概率p向一跳鄰節點廣播一個預約請求RR分組。在RR分組中必須包括發送節點的ID和數據報文的目的節點的ID，不需要進行資源預約的節點在該階段進行偵聽，這些節點可能從鄰節點那里收不到RR分組，也可能會收到一個或多個RR分組。有多個RR分組到達時，節點將在信道上偵聽到一次碰撞。發送RR分組的節點在協議中稱為預約節點 (reservation node，RN)。

b)沖突報告階段(collision report phase，CR)。如果節點在階段l收到兩個或兩個以上的預約請求分組，則節點檢測到沖突，就知道在該預約周期中有多個預約節點同時進行競爭預約，于是該節點在階段2廣播一個沖突報告CR分組；否則它保持沉默。通過在該階段對CR的偵聽，RN判斷它的RR是否與別人發生碰撞。如果未接收到CR，RN認為它所發送的RR被每個鄰節點正確接收。這樣，一個RN節點就變成了一個傳遞節點(transmission node，TN)，在下面的預約證實階段就可以預約時隙。很明顯，RR/CR交互消除了隱藏終端問題。

c）預約證實階段(reservation confirmation phase，RC)。在這個階段中，預約被建立。TN在這個狀態中廣播一個預約證實RC分組通知一跳鄰節點相應的時隙被預約。每一個正確接收到這個RC的一跳鄰節點都知道了該時隙已被預約，它們將在業務信道的相應時隙中從TN接收信息，并且不再競爭該時隙。

d）預約確認階段(reservation acknowledgement phase，RA)。收到預約證實RC分組的節點，發送預約確認RA分組通知TN及TN的兩跳鄰節點，使兩跳鄰節點知道兩跳遠處有節點預約資源成功。如果TN沒有相連節點，它就收不到預約確認分組，由此可以知道TN是一孤立節點，TN就沒必要進行信息的發送。

e)填充/消除階段(packing/elimination phase，P/E)。在該階段，網絡中有兩種類型的分組進行傳送。一種是PP(packing packet)。該分組由TN的兩跳鄰節點發送，收到PP的節點知道三跳遠處的節點預約成功；相應地，部分節點將不能再競爭同一個時隙。利用這一點可相應提高三跳鄰節點的競爭概率p，增加距離TN三跳遠處節點的預約成功率，加快預約收斂速度。另一種是EP(elimination packet )。該分組由TN節點以0．5的概率發送，用來消除相鄰節點之間可能存在的非孤立死鎖。如果TN在這個狀態沒有發送但是收到了一個EP，說明存在非孤立死鎖。這時收到EP的那個TN將放棄對該時隙的占用。

經過上述的一個完整預約過程后，節點的可能狀態為：一跳鄰節點的狀態為接收狀態，預約成功的節點為傳遞狀態；其兩跳鄰節點的狀態為鎖狀態，一個預約時隙中不允許再參與資源競爭；其余節點的狀態為空閑狀態。只有處于傳遞狀態的節點才能在相應的信息時隙中進行數據傳送。

1．2．3第二次預約過程

協議經過第一次預約過程就為需要發送數據的部分節點預約了時隙，保證業務的傳輸。但是經過第一次預約完畢后，網絡中的相鄰節點之間并不存在并行傳輸的情況，只有間隔兩跳的才會存在并行傳輸。這說明暴露終端降低了網絡的空間復用率，因此協議增加了一次改進的預約過程以提高空間復用率。

第二次預約過程基本與第一次預約過程類似，最大的不同是在預約請求階段和沖突報告階段。由于經過第一次的預約過程，節點都掌握了一張鄰居節點的時隙占用表。在預約請求階段，有資源要發送的節點將檢查鄰居的狀態，只有欲發送節點的鄰居節點和本次報文的目的節點都不處于接收狀態時才能發送RR分組；在沖突報告階段，當節點收到來自鄰居的RR分組時，且自己是RR分組中的目的地址域中的一個時，將根據鄰居節點和自己在當前業務時隙的狀態進行判斷，只有鄰居節點不處于發送而自己處于空閑狀態時，才同意對方的預約請求。這樣將充分利用暴露節點可以與鄰居節點并行傳輸的能力提高空間復用率。

2協議性能分析

本文所設計的協議采用OPNET仿真平臺實現，并對協議性能作了初步分析。吞吐率和媒體接入時延是MAC層為上層提供服務質量的重要指標，因此協議將與FPRP協議的吞吐率和媒體接入時延進行對比。在協議中定義：

每個節點的吞吐率（bps）=正確接收的報文數×

報文長度/（節點個數×仿真時長）

報文的媒體接入時延（s）＝報文發送的時刻-MAC層接收到上層遞交的報文時刻

平均媒體接入時延(s)＝Σ每個正確接收的報文的媒體接入時延/正確接收的報文數

網絡中的參數N、M、M0和K可在仿真時進行設置。協議中還有一個很重要的參數des，即上層平均發送des個報文就轉換目的地址。由于仿真的主要對象是MAC協議，假設上層傳遞給下層MAC的數據報文的目的地址就是該節點的鄰居節點，這樣可以避免路由模塊對媒體接入時延的影響。

仿真環境中設置了100個節點，均勻分布在1 250×1 250 m2的范圍內，每個節點的傳輸范圍為125 m；上層業務發送報文模塊為100 packets/s，目的節點均勻分布到鄰居節點，報文長度為1 024 bit；底層物理信道速率為1 Mbps；節點隨機移動，移動速率為25 m/s；仿真時長為30 s。經過多次仿真得到不同參數下的媒體接入時延和吞吐率。

平均媒體接入時延仿真的結果（圖2）反映了不同參數下協議的性能。特別當M0＝0時，協議就簡化成了單純的FPRP協議。從圖 2的結果中可以看出，改進后的協議平均媒體接入時延有20％左右的降幅，而幾個參數對接入時延的影響也比較明顯。當M增大、K增大、N增大時，由于時幀變長，接入時延都會有所增加；而des偏小時，由于目的地址轉換頻繁，協議耗費增大，接入時延也會有所增加。

協議的吞吐率也受仿真設置的參數的影響。從圖 3來看，當前仿真環境下效果最明顯的曲線速率已經達到上層遞交速率的95％以上。可以看出，改進后的協議吞吐率FPRP有了提高。

在引入QoS保障機制后，仿真圖 4中選取的是N=4，M=4，K=4，des=7這種平均媒體接入時延最小的配置。仿真時設置緊急業務和實時業務分別占總業務量的10％和20％。結果是緊急業務和實時業務都取得較小的接入時延，僅僅是平均媒體接入時延的53.8％和62.1％，達到了數十毫秒這個數量級，能滿足實時業務傳輸的要求。

3結束語

本文提出了一種改進的用于同步無線自組織網的MAC協議。該協議能夠同時支持保障QoS業務的傳輸，并且解決了隱藏終端和暴露終端問題。在使用相同物理層的前提下，其性能比同步FPRP有所提高，特別體現在吞吐率和媒體接入時延上。在這里，展示了該協議的可行性并且對其有效性進行了分析。但是在細節方面，如概率值p的調整、業務時隙的選擇策略、支持的業務類型、時隙分配策略的改進、功率控制等，還需要更進一步的深入研究。

參考文獻：

[1]IEEE Std 802.11—1997，Wireless LAN medium access control (MAC) and physical layer(PHY) specifications[S].1997.

[2]ZHU Chen xi，CORSON M S.A five phase reservation protocol (FPRP) for mobile Ad hoc networks[C]//Proc of the 17th Annual Joint Conference on IEEE Computer and Communications Societies.Hingham，MA:Kluwer Academic Publishes，1998:322－331.

[3]ZHU Chen xi，CORSON M S.An evolutionary TDMA scheduling protocol(E TDMA) for mobile Ad hoc networks，CSHCN TR 2001 17[R]. Maryland:University of Maryland，2001.

[4]BORGONOVO F，CAPONE A，CESANA M，et al.ADHOC:a new， flexible and reliable MAC architecture for Ad hoc networks[C]//Proc of IEEE Wireless Communications and Networking Conference.New Orleans:[s.n.]，2003:965－970.

[5]BORGONOVO F，CAPONE A，CESANA M，et al.RR ALOHA，a reliable R ALOHA broadcast channel for Ad hoc inter vehicle communication networks[C]//Proc of Med Hoc Net 2002.Sardegna:[s.n.]，2002.

[6]于宏毅.無線移動自組織網[M].北京:人民郵電出版社，2005:97 102.

“本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文”