一種固定分配與動態競爭結合的MAC層協議算法

秦 茜，宋志群，劉玉濤

(中國電子科技集團公司第五十四研究所，河北 石家莊050081)

一種固定分配與動態競爭結合的MAC層協議算法

秦 茜，宋志群，劉玉濤

(中國電子科技集團公司第五十四研究所，河北 石家莊050081)

為提升移動自組織 (MANET)網絡效率，動態時分多址 (TDMA)時隙分配算法已經成為MANET網絡的研究熱點之一。提出了一種新穎的固定分配與動態競爭結合的媒體訪問控制 (MAC)層協議算法。該算法能在保證基本話音通信需求的基礎上，根據不同業務特點動態調整時隙，保證網絡對空閑時隙資源競爭使用的效率。仿真結果表明，相對于固定分配時隙算法，該算法大幅度提高了MANET網絡的效率。

MANET網絡;TDMA協議;MAC協議

0 引言

MANET網絡作為一種無中心節點的移動通信網絡，自20世紀70年代被提出后，就因其無需固定基礎設施支持、組網快速和靈活等特點而一直受到廣泛關注，尤其是在戰術通信、搶險救災、大型集會等突發性和臨時性場合中得到應用［1］。其中，MAC協議處于MANET網絡協議棧的底層，控制著節點接入共享無線信道的方式與獲得信道資源的多少，MAC層的性能高低直接影響著MANET網絡的整體性能。

MAC協議主要解決2個問題:①如何將頻譜劃分為不同的信道;② 如何將不同的信道分配給不同的節點［2］。研究這2個問題最佳組合的最終目的是在保證MANET網絡間終端正常通信的前提下，盡可能地提高網絡的吞吐量。按照信道分配方式的不同，MANET網絡現有的MAC協議可以分為3類:基于分配的MAC協議、基于競爭的MAC協議和混合MAC協議［3］。

目前，基于分配的MAC協議一般采用同步通信方式［4］。這類協議不能根據節點業務需求變化動態調整分配方案，導致資源浪費，實用性較差;基于競爭的MAC協議通常采用異步通信模式，當節點有數據要傳輸時，節點自由競爭并在競爭成功的情況下占用信道，因此存在沖突較多、吞吐量小和時隙浪費嚴重等問題;混合MAC協議在節點需要發送數據時，才分配給其所需時隙，數據發送完畢，節點取消對時隙的占用，信道利用率得以提高，但也存在一些不足，如空閑時隙的利用率低等［5］。

為了提高MANET網絡的端到端吞吐量，本文提出了一種新的混合式MAC協議，即固定分配與動態競爭結合的MAC層協議。既保證每個節點都至少擁有一個固定的時隙，又能夠根據業務傳輸的需求對升級了的節點競爭空閑時隙，實現對空閑時隙的充分利用。

1MANET網絡MAC協議

1．1 基于分配的MAC協議

基于分配的MAC協議采用同步通信模式，時隙與節點的映射決定了一個節點在其特定時隙內允許訪問的信道。該類協議在中等到繁重的傳輸載荷條件下運行良好，但信道時隙化導致在輕傳輸載荷條件下的時延相對于競爭協議較大。常見的基于分配的協議包括5步預留協議(FPRP)［6］、空間時分多址協議(STDMA)［7］和統一時隙分配協議(USAP)［8］等。

基于分配的 MAC協議主要有頻分多址(FDMA)、時分多址(TDMA)和碼分多址(CDMA)。FDMA實現簡單，但是頻帶利用率低，抗干擾能力差，尤其是在節點高速運動的網絡中產生的多普勒效應對它造成的影響非常大;CDMA要求發送方與接收方必須保持嚴格的同步，傳輸時延和強烈的時延起伏使得實現精確定時十分困難;TDMA將不同的時隙分配給不同的用戶，是一種目前比較常用的戰術數據鏈多址接入方式，但是目前的MAC算法在網絡規模大、節點數量多和數據業務負載高時，由于所采用的時隙與幀結構較長導致網絡延遲大，接入延時較長。

1．2 基于競爭的MAC協議

在基于競爭的MAC協議中，當節點需要傳輸數據時，就對信道發起競爭，并在競爭成功后占用該信道;如果競爭失敗則根據所采用的退避算法修改下次競爭的時間或者概率。典型的基于競爭的MAC協議有載波監聽多址接入(CSMA)［9］協議、避免沖突的多路訪問(MACA)［10］協議和無線局域網的分布式協調功能(IEEE 802．11 DCF)協議等。

該類MAC協議的性能主要由其采用的競爭機制所決定，這其中包括信道競爭方式和退避算法等。該類MAC協議可以在低傳輸載荷下運行良好，具有信道利用率高、碰撞次數少以及分組傳輸時延小等特點。隨著傳輸載荷的增大，會導致碰撞次數增多，協議性能下降。在傳輸載荷很重的時候，競爭協議可能會隨著信道利用率下降而變得非常不穩定。這就很有可能導致分組傳輸時延呈指數形式增大，甚至網絡服務的崩潰。

1．3 混合類MAC協議

混合協議能夠保持所組合的協議的優點又能避免其缺陷，在傳輸載荷輕的時候表現為基于競爭的協議性能，而在傳輸載荷重的時候近似表現為基于分配的協議性能。典型的協議有基于優先級的時分多址協議(PTDMA)［11］、混合 TDMA/CSMA［12］和動態自適應媒體訪問控制(ADAPT)［1 3］等。

為了解決基于競爭與基于分配的MAC協議在不同網絡環境下應用受限的問題，融合了基于競爭和基于分配的混合MAC協議被提了出來。基于競爭和基于分配是2種明顯不同的機制，所以如何在混合2種機制時取得最優化的效果成了難題。

主流的混合類MAC協議都基于TDMA協議并引入了 CSMA技術和請求發送/清除發送(RTS/ CTS)握手機制［14］。混合類 MAC協議的幀結構中總會包含競爭階段和發送階段。顯然，混合類MAC協議的設計難題就是如何在競爭階段使得節點高效的競爭空閑時隙，以及在發送階段如何更新己分配時隙。

2 固定分配與動態競爭結合的MAC層協議

2．1 協議原理

由于單一的固定時隙分配與動態競爭時隙分配算法各自均存在不足，為此，基于競爭理論，利用2種算法的優點，克服各自的缺點，提出了一種固定與動態競爭相組合的MAC層協議。該協議的幀結構為:每個幀的時隙由2部分組成:一部分稱為控制時隙，用于時隙的競爭與預約;另一部分時隙是數據時隙，用于已分配預約成功后數據的傳送，2部分一一搭配組成一組稱為一個時隙。這種幀結構的設計有利于節點在競爭階段高效地競爭空閑時隙，以及在發送階段更快地更新時隙分配信息。該協議基本思想為:網絡中的每個節點固定分配得到一個時隙，然后將網絡傳輸需求大的節點進行升級，使得其具有格外競爭更多時隙的權利。這樣就可以實現在保證常規的語音通信任務的條件下，靈活高效地分配剩余時隙資源。幀結構的設計如圖1所示。

圖1 協議幀結構

2．2 協議算法步驟

2．2．1 固定時隙分配階段

將一幀劃分為2部分，一部分用于固定分配，即采用固定分配策略為網絡中的每個節點分配一個固定時隙，主要承擔常規的語音通信任務，重點是保證其低延時性能，而且固定時隙數根據當前活動節點的數目進行調整。

在該階段，節點開機之后的時隙申請和時隙分配功能，通過接收來自其他節點的控制時隙信息，進行分析和處理，進而控制終端節點在合適的時刻發送信令信息。其輸入是來自其他節點的控制時隙的信令信息，輸出對這些信息的處理結果，信息格式相同，同時輸出還包括在哪個時隙進行發送。

2．2．2 時隙動態競爭階段

根據網絡層的監控，對于有高業務傳輸需求的節點，設計將該類節點進行升級，定義高優先級，并設計其額外競爭更多的幀周期中的空閑時隙，用于支持高數據率傳輸和高服務質量等級需求。最后，當傳輸結束后，釋放此階段占用的時隙，以供其他傳輸所用。

具體地說，對于有高業務傳輸需求的節點，若在一跳范圍內的2個節點需要進行高服務質量等級業務傳輸，該算法可以很快地完成時隙預約，并在當前幀周期內就進行數據傳輸;若源節點和目的節點之間是多跳，高業務需求的源節點競爭的是2跳之內絕對可用的時隙，其過程是先在控制時隙預約下一幀的數據時隙使用權。當傳輸過程結束后，節點的高優先級權限取消，并且釋放占用的額外時隙。具體流程如圖2所示。

圖2 協議流程

3 仿真與分析

3．1 仿真環境及參數設置

為了測試文章中提出的協議合理性和性能，采用與固定時隙分配算法進行對比的方式，分析2種算法在傳輸層時延和端到端吞吐量的仿真數據。仿真中，以7個節點為例，7個節點在多跳之內隨機分布，并按照隨機生成的移動路徑進行動態移動，其拓撲結構如圖3所示。仿真中設置的場景尺寸為4．5 km×3 km，節點的通信距離是2 km，場景中的節點個數是7，節點的最大移動速率是80 km/h，最大的中繼次數為4，仿真時間為10 s。

圖3 仿真場景拓撲

3．2 仿真結果與分析

3．2．1 傳輸層時延

2種時隙分配算法的平均時延變化曲線如圖4所示。link1－1和link2－1是典型 TDMA固定時隙分配算法的時延數據，由于LINK 1是4跳，LINK 2 是2跳，因此2條時延數據線雖形狀相同，但是收斂數值相差0．2 s。link1－2和 link2－2則是固定分配與動態競爭結合的MAC層協議的仿真數據。在該算法中，由于時隙的動態分配，占用時隙多的LINK 1的傳輸層時延與固定分配算法相比，下降了0．28 s，相對地，LINK 2占用的時隙數減少造成時延增大了0．7 s。從圖4可知，隨著時間的增加，2條路由的固定時隙分配算法的平均時延均保持不變，而文章中提出的混合式時隙分配算法的平均時延，由于LINK 1業務量大，節點級別高，時延降低，相反LINK 2的時延增大。這主要是由于固定時隙分配算法是注重公平性的策略，而文章中提出的新算法由于更加注重效率，所以在部分固定時隙的基礎上加入了動態分配時隙策略，大幅度地減少了等級高的節點的平均時延。

圖4 2種時隙分配算法的平均時延變化曲線

3．2．2 端到端吞吐量

固定時隙分配與本文提出的混合式時隙分配算法的端到端吞吐量對比結果如圖5所示，link1－1和link2－1是典型TDMA固定時隙分配算法的吞吐量數據，2條線完全重合體現了該算法的公平性原則。link1－2和link2－2則是改進算法效率原則的體現，根據業務的大小將時隙更多地分配給業務量大或者業務更為重要的節點，在仿真中LINK 1上的業務量更大而且具有優先級，則將時隙更多地分配給LINK 1，相應地，LINK 2上所占用的時隙就相對減少。從圖5可以看出，固定時隙分配算法由于不能動態適應業務的變化，2條路由上其端到端吞吐量是完全一樣的，導致時隙浪費比較嚴重;相對于固定時隙分配算法，本文提出的時隙算法由于充分利用了固定時隙分配、動態時隙競爭的優點，引入動態分級原理對有突發業務的節點進行升級，通過調整空閑時隙給高等級節點，提高了傳輸效率。

圖5 2種算法的端到端吞吐量對比

4 結束語

隨著MANET網絡技術的不斷發展，MAC層協議算法的研究日新月異，本文在分析典型TDMA時隙分配算法的基礎上，提出了一種新穎的混合式MAC層協議算法。算法根據不同業務的不同需求，動態調整時隙分配策略，在保證基本話音業務需求的前提下，最大限度地滿足突發大業務量用戶的通信需求。從仿真結果可以看出，本文提出的固定分配與動態競爭結合的MAC層協議算法實現了在基本兼顧公平的同時，大幅度地提高了MANET網絡的效率。

［1］ 霍金海，王 鉞，徐贊新，等．基于負載和優先級的MANET優化策略［J］．清華大學學報(自然科學版)，2012，52(9):1 270－1 274．

［2］ 王英杰，劉 覓，吳振華，等．無線Mesh網絡的最大并發公平調度［J］．北京郵電大學學報，2007，30(4): 33－36．

［3］ 李 勇，匡坤高，王 平，等．分布式自組織網絡動態功率控制機制的研究與實現［J］．東南大學學報(自然科學版)，2011，41(2):296－300．

［4］ 羅正華，孟 源，蘇文昊，等．基于無線自組織網MAC 的FPRP協議改進研究［J］．成都大學學報(自然科學版)，2015，34(2):152－155．

［5］ DHIRAJ S P，RAHUL G．A New Protocol Design for Location Based Ad-Hoc Networks［C］∥India:2015 InternationalConference on IndustrialInstrumentation and Control(ICIC)，2015:988－991．

［6］ ZHU C X，CORSON M S．A Five-Phase Reservation Protocol (FPRP)for Mobile Ad hoc Networks［C］∥America:Seventeenth Annual Joint Conference of the IEEE Computer and Communications Societies，1998:322－331．

［7］ NELSO R，KLEINROCK L．Spatial TDMA:A Collision-Free Multihop Channel Access Protocol［C］∥America: IEEE Trans．Communication，1985:934－944．

［8］ YOUNG C D．USAP:A UnifyingDynamicDistributed MultichannelTDMA SlotAssignmentProtocol［C］∥America:IEEE Conference on Military Communications，1996:235－239．

［9］ KLEINROCK L，TOBAGI F A．Packet Switching in Radio Channels:Part I-carrier Sense Multiple Access Modes and Their Throughput-delay Characteristics［C］∥America: IEEE Transition Communication，1975:1 400－1 416．

［10］KARN P．MACA-A NewChannelAccessMethodfor Packet Radio［C］∥ARRL/CRRL AmateurRadio9th Computer Networking Conference，1990:134－140．

［11］EPHRIMIDES A，MOWAFI O A．Analysis ofaHybrid Access Scheme for Buffered Users-probabilistic Time Division［C］∥IEEE Transactions on Software Engineering，IEEE，1982:52－61．

［12］SHARP B，GRINDROND E，CAMM D．Hybrid TDMA/ CSMA Protocol for Self-Managing Packet Radio Networks ［C］∥Tokyo:1995 Fourth IEEE International Conference on Universal Personal Communications，1995:929－933．

［13］CHLAMTAC I，FARAGOEA，MYERSA D，etal．ADAPT:A DynamicallySelf-AdjustingMediaAccess Control Protocol for Ad-hoc Networks［C］∥America: Global Telecommunications Conference，1999:11－15．

［14］羅 濤，趙 明，李靜葉，等．認知無線電自組織網絡MAC協議［J］．計算機學報，2013，36(7):1 337-1 348．

An Algorithm Combining Static Allocation with Dynamic Contention in MAC Protocol

QIN Qian，SONG Zhi-qun，LIU Yu-tao
(The 54th Research Institute of CETC，Shijiazhuang Hebei 050081，China)

In order to improve the MANET network efficiency，dynamic TDMA time slots assignment algorithm now becomes one of the hot research topics in MANET network．This paper proposes a new algorithm combining static allocation with dynamic contention in MAC protocol．Based on ensuring the basic communication requirements of users，this algorithm can adjust in dynamic mode the time slots according to different business characteristics，so that it can make efficient use of slot resource．The simulation results show that compared with the static allocation algorithm，the proposed algorithm can significantly improve the efficiency of MANET network．

MANET;TDMA protocol;MAC protocol

TN911

A

1003－3106(2017)02－0011－04

10．3969/j．issn．1003－3106．2017．02．03

秦 茜，宋志群，劉玉濤．一種固定分配與動態競爭結合的MAC層協議算法［J］．無線電工程，2017，47(2):11－14．

2016-11-04

通信網信息傳輸與分發技術重點實驗室開放基金資助項目(EX156410046)。

秦 茜女，(1988—)，碩士研究生。主要研究方向:無線通信。

宋志群男，(1963—)，研究員。主要研究方向:無線通信。