基于無線自組織網(wǎng)MAC的FPRP協(xié)議改進研究

羅正華，孟 源，蘇文昊，楊煜婷

(成都大學(xué) 電子信息工程學(xué)院，四川 成都 610106)

0 引 言

無線自組織網(wǎng)(Ad Hoc)是由一組帶有無線收發(fā)裝置的移動節(jié)點組成的無中心、多跳的臨時自治系統(tǒng)，具有組網(wǎng)靈活、快速部署、無需基礎(chǔ)設(shè)施、成本低、抗毀性高與生存能力強等特點.目前，大多數(shù)信道接入?yún)f(xié)議(Medium Access Control，MAC)是針對單播業(yè)務(wù)設(shè)計的，支持廣播業(yè)務(wù)的信道接入?yún)f(xié)議有5 步預(yù)約(Five-Phase Reservation Protocol，F(xiàn)PRP)和可靠預(yù)約ALOHA(Reliable Reservation ALOHA，RRALOHA)協(xié)議［1］.研究發(fā)現(xiàn)，F(xiàn)PRP 協(xié)議不僅可以可靠完成時隙資源的預(yù)約，而且控制部分開銷極小.FPRP 協(xié)議通過隨機競爭接入，利用5 次握手機制來為廣播業(yè)務(wù)預(yù)約無沖突的廣播信息時隙，節(jié)點一旦預(yù)約成功，廣播業(yè)務(wù)的傳送具有較高的可靠性.由于時隙預(yù)約過程只是在兩跳范圍內(nèi)進行，所以，時隙分配的過程可以在網(wǎng)絡(luò)中的不同空間上并行進行，從而提高了系統(tǒng)的空間復(fù)用度［2－4］.本研究針對FPRP協(xié)議的不足，比如系統(tǒng)實現(xiàn)的復(fù)雜度等，對其進行了改進，并通過仿真實驗進行了性能驗證.

1 FPRP 協(xié)議

FPRP 協(xié)議是一種基于競爭的同步MAC 協(xié)議.一個預(yù)約幀(Reservation Frame，RF)后面緊跟若干個信息幀(Infromation Frame，IF).一個RF 包含N 個預(yù)約時隙(Reservation Slot，RS)，每一個IF 也包含N 個信息時隙(Information Slot，IS).每一個RS 對應(yīng)一個IS.TDMA 時隙分配表在RF 中產(chǎn)生，每一個IF 按照這個時隙分配表來分配時隙，當(dāng)下一個RF 到來時，重新進行時隙預(yù)約，時隙分配表也相應(yīng)進行更新.

一個RS 包括M 個預(yù)約周期(Reservation Cycle，RC)(M 值隨具體網(wǎng)絡(luò)變化)，一個RC 包括5 次握手過程.網(wǎng)絡(luò)中的節(jié)點通過5 次握手過程來進行時隙資源的競爭預(yù)約［5－6］.FPRP 協(xié)議的幀結(jié)構(gòu)如圖1所示.

圖1 FPRP 協(xié)議的幀結(jié)構(gòu)

在FPRP 協(xié)議下，一個完整的預(yù)約過程包括:

第1 階段，預(yù)約請求階段(Reservation Request Phase，RR).在該階段，節(jié)點有數(shù)據(jù)需要發(fā)送，則申請預(yù)約時隙以概率P 發(fā)送一個預(yù)約請求分組(Reservation Request Packet，RRP).此時該節(jié)點稱為請求節(jié)點(Requesting Node，RN)，處于監(jiān)聽狀態(tài)的節(jié)點可能沒有收到RR 分組，可能只收到1 個RR 分組，也可能收到多個RR 分組.若節(jié)點收到多個RR 分組，則視為監(jiān)聽到一次RR 包碰撞.

第2 階段，沖突報告階段(Collision Report Phase，CR).如果節(jié)點在RR 階段，監(jiān)聽到碰撞，它在CR 階段就會發(fā)送一個沖突報告分組(Collision Report Packet，CRP)來表明其在第1 階段監(jiān)聽到RR 分組的沖突，否則節(jié)點就保持靜默狀態(tài).RN 節(jié)點通過監(jiān)聽CR 分組，檢測是否發(fā)生了沖突.如果沒有收到CR 分組，RN 就認(rèn)為沒有發(fā)生沖突，此時RN 節(jié)點的狀態(tài)為發(fā)送節(jié)點(Transmission Node，TN).RR/CR的交互消除了隱藏終端問題.

第3 階段，預(yù)約證實階段(Reservation Confirmation Phase，RC).在該階段，處于TN 狀態(tài)的節(jié)點發(fā)送預(yù)約證實分組(Reservation Confirmation Packet，RCP)，TN 的鄰節(jié)點收到RC 分組后，將不再競爭這個時隙的使用，并在IF 幀中接收來自TN 節(jié)點的數(shù)據(jù).

第4 階段，預(yù)約確認(rèn)階段(Reservation Acknowledgment Phase，RA).該階段，TN 的鄰節(jié)點通過發(fā)送RA 分組來對RC 分組進行回應(yīng).RA 分組告訴TN節(jié)點相應(yīng)時隙的預(yù)約已經(jīng)成功，而TN 兩跳遠處的節(jié)點若收到RA 分組，則表示其兩跳遠處有節(jié)點已經(jīng)預(yù)約成功這個時隙.如果TN 沒有相連節(jié)點，它就收不到預(yù)約確認(rèn)分組，由此可以知道TN 是一孤立節(jié)點，TN 就沒必要進行信息的發(fā)送.

第5 階段，填充/消除階段(Packing/Elimination Phase，P/E).在該階段，網(wǎng)絡(luò)中有2 種類型的分組進行傳送，一種是PP(Packing Packet)，該分組由TN的兩跳鄰節(jié)點發(fā)送，收到PP 的節(jié)點知道三跳遠處的節(jié)點預(yù)約成功，將不能再競爭同一個時隙.利用這一點可以相應(yīng)提高三跳鄰節(jié)點的競爭概率p，增加距離TN 三跳遠處節(jié)點的預(yù)約成功率，加快預(yù)約收斂速度.另一種是EP(Elimination Packet)，該分組由TN 節(jié)點以0.5 的概率發(fā)送，用來消除相鄰節(jié)點之間可能存在的非孤立死鎖，如果TN 在這個狀態(tài)沒有發(fā)送但是收到了一個EP，說明存在非孤立死鎖，這時，收到EP 的TN 將放棄對該時隙的占用.

一個完整預(yù)約過程后，節(jié)點的可能狀態(tài)為:一跳鄰節(jié)點的狀態(tài)為接收狀態(tài)，預(yù)約成功的節(jié)點為傳遞狀態(tài);兩跳鄰節(jié)點的狀態(tài)為鎖狀態(tài)，預(yù)約時隙不允許再參與資源競爭;其余節(jié)點的狀態(tài)為空閑狀態(tài).只有處于傳遞狀態(tài)的節(jié)點才能在相應(yīng)的信息時隙中進行數(shù)據(jù)傳送.

2 協(xié)議改進

針對FPRP 協(xié)議的一些不足，本研究從以下幾方面對其進行了改進:

1)在FPRP 協(xié)議的假設(shè)中，認(rèn)為2 個節(jié)點間的無線通信是無噪且對稱的信道，這在實際應(yīng)用中是不存在的.實際場景中，節(jié)點發(fā)送數(shù)據(jù)時的射頻信號會對其他節(jié)點產(chǎn)生影響，空中一般也會有其他信號的干擾.在這種情況下，節(jié)點應(yīng)該具有可以測量出無線通信鏈路信噪比的能力，根據(jù)信噪比來判斷通信鏈路是否可靠，從而決定是否使用這條通信鏈路進行通信.

2)在FPRP 的5 階段握手過程中，為了使節(jié)點的干擾和沖突盡量減小，可以使不同階段的發(fā)射功率有所差別.在階段1、2，可以適當(dāng)增大節(jié)點發(fā)送RR 分組的無線發(fā)射功率，以便檢測到更多潛在的可能發(fā)生沖突的鄰節(jié)點;在階段3，對RC 分組的傳送只需要正常的無線發(fā)射功率即可;在階段4，對RA 分組的發(fā)送也應(yīng)該適當(dāng)增大發(fā)射功率，以通知更多的附近節(jié)點在兩跳遠處有節(jié)點預(yù)約時隙成功.

3)在現(xiàn)有的FPRP 協(xié)議中，節(jié)點在發(fā)送數(shù)據(jù)時，若在一幀內(nèi)數(shù)據(jù)沒有發(fā)送完成，則在下一幀要重新參與時隙的競爭預(yù)約，這樣不僅不利于實時業(yè)務(wù)的傳送，也會增加網(wǎng)絡(luò)進行時隙預(yù)約分配的收斂時間.對此，可以對FPRP 協(xié)議做如下調(diào)整:在每一個RS的末尾，再加上一個比特的信息，此信息由TN 節(jié)點發(fā)送，用于表示一幀結(jié)束后，節(jié)點是否釋放這個時隙.若此幀結(jié)束后節(jié)點不釋放此時隙，則將下一次競爭此時隙的概率置為1，相關(guān)鄰節(jié)點則將下一幀競爭此時隙的概率置為0，這樣就能保證業(yè)務(wù)的實時性，避免實時業(yè)務(wù)因為時隙競爭的失敗而產(chǎn)生過大的延遲.

4)通過FPRP 協(xié)議的5 次握手過程第5 階段的EP 分組，確實可以消除網(wǎng)絡(luò)的非孤立死鎖節(jié)點，但是并不能完全消除.這是因為，若一組非孤立死鎖節(jié)點中有2 個節(jié)點同時發(fā)送EP 分組，則這2 個節(jié)點還是無法發(fā)現(xiàn)自己是非孤立死鎖節(jié)點.針對這種情況，可以在接下來的RC 的第1 階段，繼續(xù)補充發(fā)送EP分組，經(jīng)過這樣的操作，若協(xié)議的M 參數(shù)取值合理，網(wǎng)絡(luò)中存在非孤立死鎖節(jié)點的概率就近似為零了.而且這些補充發(fā)送的EP 分組也不會被RR 分組所干擾，因為在TN 預(yù)約成功一個時隙后，其他節(jié)點就不會再參與這個時隙的競爭預(yù)約.

5)在網(wǎng)絡(luò)規(guī)模不大(三跳以內(nèi))且節(jié)點分布呈網(wǎng)格狀的時候，孤立死鎖節(jié)點和非孤立死鎖節(jié)點很難發(fā)生，且沒必要考慮三跳以外的節(jié)點，這樣，F(xiàn)PRP協(xié)議的第4 階段和第5 階段就可以省略，成為簡化的FPRP 協(xié)議，可以稱之為3 步預(yù)約協(xié)議(Three Phase Reservation Protocol，TPRP)協(xié)議，從而簡化系統(tǒng)實現(xiàn)的復(fù)雜性.

3 仿真及結(jié)果分析

為驗證改進后FPRP 協(xié)議的性能，設(shè)置網(wǎng)絡(luò)仿真參數(shù)如表1 所示.仿真實驗結(jié)果如圖2 ～5 和表2 所示.

表1 仿真參數(shù)設(shè)置表

圖2 按1)、2)改進后的效果

圖3 超長數(shù)據(jù)分組業(yè)務(wù)時隙平均競爭成功率

圖4 TPRP 與FPRP 協(xié)議在不超過三跳的微型自組網(wǎng)中MAC 接入時延對比

圖5 TPRP 與FPRP 協(xié)議在不超過三跳的微型自組網(wǎng)中吞吐量對比

表2 網(wǎng)絡(luò)中平均非孤立死鎖節(jié)點個數(shù)

從圖2 可看出，由于節(jié)點根據(jù)無線信道質(zhì)量做了選擇，并在5 次握手階段，采用動態(tài)功率調(diào)整措施，使得改進后的FPRP 協(xié)議的丟包率得到明顯降低.

在圖3 中，固定5 個節(jié)點發(fā)數(shù)據(jù)，形成超長數(shù)據(jù)分組業(yè)務(wù).在這種情況下，對比FPRP 協(xié)議改動前后時隙預(yù)約成功率，從仿真結(jié)果看出，由于改進后的FPRP 協(xié)議加上了節(jié)點在下一幀根據(jù)其數(shù)據(jù)是否發(fā)送完成來決定是否釋放時隙的機制，這樣就可以使得在一幀中沒有傳完數(shù)據(jù)的節(jié)點，在下一幀時優(yōu)先使用上一幀的時隙，當(dāng)節(jié)點的數(shù)據(jù)分組業(yè)務(wù)很長時，可以明顯提高節(jié)點競爭時隙的成功率.

在表2 的仿真場景中，本研究有意設(shè)置網(wǎng)絡(luò)結(jié)構(gòu)使非孤立死鎖節(jié)點發(fā)生的概率大大增加，對比FPRP 協(xié)議改動前后，預(yù)約幀結(jié)束后網(wǎng)絡(luò)中的平均非孤立死鎖節(jié)點個數(shù).由于當(dāng)時隙預(yù)約成功后，TN節(jié)點利用余下未用的RC 補發(fā)EP 分組，完全消除了網(wǎng)絡(luò)中的非孤立死鎖節(jié)點個數(shù).這個改動不僅提高了預(yù)約幀的利用率，而且提高了廣播業(yè)務(wù)的可靠性.

從圖4、圖5 可看出，在不超過三跳的微型自組網(wǎng)絡(luò)中，改進的FPRP 協(xié)議的接入時延、吞吐量和FPRP 協(xié)議基本相同.當(dāng)不超過三跳時，可以用改進的FPRP 協(xié)議代替FPRP 協(xié)議，以簡化協(xié)議實現(xiàn)的復(fù)雜度.

4 結(jié) 語

本研究對無線自組織時隙分配協(xié)議FPRP 進行了研究與改進.仿真結(jié)果表明，改進后的協(xié)議比改進前的協(xié)議性能有顯著提高，改進的結(jié)果與實際仿真結(jié)果一致.

［1］林淑藝.基于TDMA 的無線自組織網(wǎng)絡(luò)時隙分配機制研究與仿真［D］.廈門:廈門大學(xué)，2009.

［2］于宏毅.無線移動自組織網(wǎng)［M］.北京:人民郵電出版社，2005.

［3］Zhu C，Corson M S.A five phase reservation protocol(FPRP)for mobile ad hoc networks［C］//Proceedings of the 17th Annual Joint Conference of the IEEE Computer and Communicatoins Societies.San Francisco，CA，USA:IEEE Press，1998:322－331.

［4］楊雙懋，郭偉，蘇儉.基于FPRP 的無線自組織網(wǎng)的MAC協(xié)議［J］.計算機應(yīng)用研究，2008，25(1):68－70.

［5］Zhu C，Corson M S.An evolutionary-TDMA scheduling protocol(E-TDMA)for mobile ad hoc networks［C］//Proceedings of Advanced Telecommunications and Information Distribution Research Program，2000.College Park，MD:University of Maiyland，2000.

［6］黃偉.基于OPNET 的動態(tài)TDMA 接入網(wǎng)絡(luò)半實物仿真研究與實現(xiàn)［D］.西安:西安電子科技大學(xué)，2009.