高效的動態按需時隙分配協議

李楊，韓志韌

(1.哈爾濱工程大學信息與通信工程學院，黑龍江哈爾濱150001;2.武漢船舶通信研究所，湖北武漢430079)

海上無線自組網是一種具有高度動態特性的網絡.在網絡運行過程中，如網絡規模、拓撲結構等各種直接影響網絡性能的因素隨時會發生變化.因而要求適用于海上無線自組網的MAC層協議必須能夠適應網絡的各種變化，并保持相對穩定的性能.

以TDMA(time division maltiple access)為基礎的分配類MAC層協議具有性能穩定、可靠，平均傳輸時延等QoS指標可控、便于管理等特點，近年來在對MANET(mobile Ad Hoc networks)的相關研究中受到廣泛的關注.其核心問題是如何有效地為各節點分配時隙資源.針對該問題，文獻[1-5]采用集中式的染色算法完成網內對節點或鏈路的時隙分配，該算法必須首先獲得節點2～3跳范圍內其他節點的拓撲和狀態信息，增加了協議的開銷和復雜度.以FPRP(five-phase reservation protocol)為代表的動態競爭類時隙分配協議[6-11]通過簡單而可靠的握手機制與鄰居節點協調預留時隙資源，但此類協議均以平均分配為原則，并沒有根據實際業務負載情況對有限的時隙資源進行按需分配.文獻[11]提出一種新的ODSA(on-demand and dynamic slot assign-ment)協議，以按需的策略動態分配時隙，改善了網絡效率，但引入了一定的協議開銷.文獻[12]提出采用動態調整時幀長度的方法匹配當前業務量，具有一定的理論價值.

針對時隙分配中的預留沖突和網絡效率較低的問題提出了一種新的動態競爭類時隙分配協議，即按需隨機時隙分配協議(DRSA).該協議在時隙競爭過程中采用全新的隨機化競爭策略，可以有效減小競爭分配過程中的碰撞概率.同時，本協議還能夠根據當前業務量需求和拓撲情況靈活地為網絡節點分配時隙資源，以適應網絡及業務的變化，提高網絡效率.

1 DRSA協議設計

在典型的海上無線自組網絡環境中，網絡節點通常具有較強的移動性，因而導致網絡規模、節點分布密度、拓撲結構等網絡參數變化較快.其次，平臺上需要承載各種不同類型的數據業務，導致網絡中業務負載的分布情況差異較大.為適應海上自組網的特點，DRSA協議主要采用動態競爭的時隙分配策略，根據業務量的負載情況動態地為各節點分配所需時隙資源，同時采用全新的按需跳躍預留算法(on-demand hop slot reservation，ODHR)有效地提高了時隙分配的效率和有效性.協議默認全網時間同步.

1.1 協議幀結構

DRSA協議幀格式如圖1所示.在DRSA協議中，基本的周期性時間單位為時元.時元內包含1個競爭幀和若干個信息幀，其中信息幀的個數可根據需要進行裁剪.每個信息幀可分為N個信息時隙，分配給不同網絡節點用于傳輸數據.競爭幀可分為M個競爭時隙.有需求的網絡節點需在競爭幀內隨機選擇某一競爭時隙，以握手方式參與競爭.

協議的具體握手過程借鑒FPRP[6]協議中的5步握手機制，但采用全新的ODHR算法，通過在握手數據包中增加攜帶競爭標識字段和采用跳躍預留策略，有效提高時隙分配的效率和有效性.競爭標識字段記錄了當前握手數據包的種類和預留發起節點需求的目標信息時隙編號.

1.2 ODHR時隙預留算法

ODHR時隙預留算法主要分為業務量評估競爭仲裁過程和跳躍時隙預留過程.算法默認全網各節點擁有相同的協議參數配置.設整個時元共配置KF個信息幀，每個信息幀中有N個信息時隙，配置一個競爭幀，包含M個競爭時隙.

業務量評估競爭仲裁過程負責評估當前業務量及可獲得的時隙資源，以判定是否需要競爭新的時隙.設當前MAC層發送隊列中緩沖的實際業務量為Db.而根據協議評估，某節點在當前時元內能支持的業務量為已經預留到的信息時隙資源Sp，計劃預留的信息時隙資源Pp，信息幀個數KF和信道帶寬B的函數:

當Db≤時，該節點已獲得足夠時隙資源，協議不允許該節點競爭新的時隙;而當Db＞時，協議允許該節點繼續競爭新的時隙.

協議一般將競爭幀內的M個競爭時隙分為n個競爭組，每組m個競爭時隙.當某節點需要新的時隙時，跳躍時隙預留過程要在當前競爭組內選定競爭時隙號ci和目標信息時隙號rj:

式中:Rf為空閑時隙集，若Rf=?則當前時元內無可用時隙.當時間到達選定的競爭時隙時，協議在握手數據包競爭標識字段中填入選定的目標信息時隙rj，開始競爭.

設在當前競爭組內有k個節點同時參與競爭，每個節點選定的競爭時隙為

當某節點選定競爭時隙cl滿足式(4)條件時，

協議即可為該節點完成其對目標時隙的預留，并在隨后的每個信息幀內均有權使用該信息時隙.在預留完成后需要更新Sp、Pp、Rf和時隙預留表.

在隨后的競爭組內，重復該算法，繼續為有需求的節點分配空閑的信息時隙.當整個競爭幀完成時，仍空閑的時隙將無法被使用，造成時隙浪費.設已經完成分配的時隙總數為wcell，則協議在當前時元內的時隙分配效率為

1.3 協議流程

DRSA協議共有5個主要狀態，狀態轉移圖如圖2所示.當協議檢測到MAC層隊列中有業務數據緩沖時，從等待狀態進入競爭準備狀態，并完成業務量評估及競爭仲裁過程，根據仲裁結果決定是否需要預留新的時隙資源;若需要，協議開啟跳躍時隙預留過程，根據時隙預留表隨機選擇當前空閑的信息時隙和競爭時隙，準備參與競爭.待時間到達選定的競爭時隙，協議即可進入競爭狀態.當協議在等待狀態時，若收到其他節點的時隙預留請求，會被動進入競爭狀態配合預留發起節點完成競爭過程.在競爭完成后，協議進入更新預留狀態，記錄預留結果更新時隙預留表.而后，協議回到等待狀態.當時間進行到本節點成功預留的信息時隙時，協議即進入業務數據發送狀態，發送MAC層隊列中緩沖的業務數據.

圖2 DRSA協議狀態轉移Fig.2 The state machine of DRSA

2 DRSA協議性能分析與仿真

2.1 協議時隙分配效率分析與仿真

根據DRSA協議，時隙的分配過程完全獨立.容易證明Ωg的統計平均值可以成為 E[Ωg]的無偏估計.由此，定義協議時隙分配效率Ωp為

設競爭幀的第Gj個競爭組中共有K個節點利用組內的m個競爭時隙參與競爭.各節點選擇競爭時隙的所有結果可以表示為如下數學模型:

式中:a1、a2、…、am分別代表編號為1～m的競爭時隙.將該表達式逐步完全展開為多項式形式可得:

式中:

將所有同類項合并，可將式(8)簡化為

式中:每項都代表所有K個節點隨機選定競爭時隙的一種結果，指數k1、k2、…、km代表該結果中選擇相應競爭時隙的節點數，系數 Ak1，k2，…，km代表產生相應結果的情況總數.根據式(4)定義的條件，當?kj∈{k1，k2，…，km}∪kj=1時，在該競爭時隙內不會發生競爭碰撞，節點可完成預留.則在當前競爭組內能成功分配d個時隙的概率為

式中:

由此，在當前第Gj個競爭組內能夠成功分配的時隙數的期望為wgroup(Gj):

假設，平均每個競爭組內均有K個節點參與競爭，則在當前時元內，能夠成功分配時隙總數的期望為

將式(14)代入式(6)，即可得到協議的時隙分配效率.

通過蒙特卡洛仿真，圖3給出了在同一競爭域內，不同數量節點同時參與競爭情況下的協議時隙分配效率Ωp.圖中m×n代表不同競爭時隙總數及其分組方法，K為在同一競爭域內參與競爭的節點總數.

圖3 不同參數配置下時隙分配效率Fig.3 The efficiency of slot assignment under different parameters

從圖3中可以看出，競爭時隙總數對Ωp有直接影響.隨著競爭時隙總數的增加，協議可有效支持更多節點同時參與競爭并保持協議時隙分配效率穩定在85%以上，但同時會增加協議的開銷.在競爭時隙總數一定時，不同的分組方法也會對協議時隙分配效率造成影響.適當調整競爭組數n和每組競爭時隙數m可以在不增加協議開銷的基礎上進一步提高協議時隙分配效率.

同時通過圖3還可以看到，適當選定競爭時隙總數及分組方法后，協議可以保證競爭節點總數K的值在較寬范圍內變化時仍然有較高的協議時隙分配效率.這說明本協議具有較強的適應性和健壯性，對于因節點移動、業務分布變化而引起的網絡環境變化，仍然能夠保證網絡的高效運行.

2.2 DRSA協議在海上自組網中的性能

使用Qualnet網絡仿真軟件，在典型海上自組網應用場景下，對DRSA協議、802.11以及靜態TDMA協議在不同的業務負載情況下的平均吞吐量性能進行充分地仿真.仿真場景的相關主要參數如表1所示.

表1 仿真場景主要參數Table 1 The main parameters of simulation scenario

吞吐量仿真結果如圖4所示.從圖4中可以看出，當網絡處于輕負載時，3種協議吞吐量性能相當.當網絡處于中度負載時，由于靜態TDMA協議服從固定的時隙分配方案，不能在空間中形成有效的時隙復用，導致靜態TDMA協議的平均吞吐量性能出現瓶頸;而DRSA與802.11協議在中度負載時的吞吐量性能相當，均明顯優于靜態TDMA.隨著網絡中業務負載的進一步加重，DRSA協議與802.11協議的平均吞吐量性能開始分化.借助于ODHR時隙預留算法，DRSA協議可以在擁擠的網絡環境和密集的業務環境下根據業務需求有效地協調各發送節點，高效地分配和利用空閑的時隙資源，在空間上形成有效復用，使平均吞吐量性能得到進一步提高.最終DRSA協議的平均吞吐量穩定在4×105bit/s水平，而802.11協議的平均吞吐量穩定在2.5×105bit/s水平.DRSA協議的吞吐量較802.11協議提高約60%.

圖4 吞吐量對比仿真結果Fig.4 The performance comparison on throughput

3 結束語

根據建模分析和仿真驗證，DRSA協議能夠根據當前網絡中各節點的業務負載情況，以完全分布式的方式按各節點的業務需求高效地為各節點分配時隙資源，而不依賴任何關于當前網絡拓撲情況的先驗信息，使得協議具有較強的適應性、健壯性和可擴展性.

[1]MOSCIBRODA T，WATTENHOFER R.Coloring unstructured radio networks[C]//Proceedings of the 17th Annual ACM Symposium on Parallelism in Algorithms and Architectures.New York，USA，2005:39-48.

[2]SAGDUYU Y E，EPHREMIDES A.On joint MAC and network coding in wireless Ad Hoc networks[J].IEEE Transactions on Information Theory，2010，53(10):3697-3713.

[3]SRINIVASAN P，RAJIV G.Distributed algorithms for coloring and domination in wireless Ad Hoc networks[C]//Proceedings of FSTTCS＇04.Chennai，India，2004:447-459.

[4]胡致遠，郭建丁，王景，等.多接口無線mesh網絡的信道時空分配[J].重慶大學學報，2011，34(2):26-31.HU Zhiyuan，GUO Jianding，WANG Jing，et al.Spatiotemporal channel assignment in multi-radio wireless mesh networks[J].Journal of Chongqing University，2011，34(2):26-31.

[5]RHEE I，WARRIER A，JEONGKI M，et al.DRAND:distributed randomized TDMA scheduling for wireless Ad Hoc networks[J].IEEE Transactions on Mobile Computing，2009，8(10):1384-1396.

[6]ZHU C X，CORSON M S.A five-phase reservation protocol(FPRP)for mobile ad hoc networks[C]//Proceedings of Seventeenth Annual Joint Conference of the IEEE Computer and Communications Societies.San Francisco，USA 1998:322-331.

[7]SAYADI A，WEHBI B，LAOUITI A.One shot TDMA-based reservation MAC protocol for wireless Ad Hoc networks[C]//Proceedings of Vehicular Technology Conference.Evry，France，2011:1-5.

[8]ZHU C X，CORSON M S.An evolutionary-TDMA scheduling protocol(E-TDMA)for mobile Ad Hoc networks[R].Baltimore:University of Maryland，2000.

[9]VALLATI C.Dynamic resources allocation in wireless mesh networks[C]//Proceedings of IEEE International Symposium on World of Wireless，Mobile and Multimedia Networks.Pisa，Italy，2011:1-3.

[10]LI Hongyan，VALAEE S.An efficient algorithm for time slot assignment in Ad Hoc networks[C]//Proceedings of 22nd Biennial Symposium in Commucications.Kingston，Canada，2004:225-227.

[11]XU Mingxia，ZHAO Minjian，SONG Zhengwei，et al.An on-demand and dynamic slot assignment protocol for Ad Hoc networks[C]//Proceedings of APCC＇06.Busan，Korea，2006:1-5.

[12]馬柯，俞能海，楊福榮.EASA:一種分簇Ad Hoc網絡高效自適應TDMA時隙分配算法[J].電子學，2010，38(7):1678-1682.MA Ke，YU Nenghai，YANG Furong.EASA:an efficient adaptive TDMA slot assignment protocol for clustered Ad Hoc network[J].Acta Electronica Sinica，2010，38(7):1678-1682.