一種改進的動態TDMA時隙分配算法研究

秦 茜

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

一種改進的動態TDMA時隙分配算法研究

秦 茜

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

針對移動自組織網絡(Mobile Ad-Hoc Networks，MANET)對多節點場景的需求，在基于時分多址(Time Division Multiple Access,TDMA)固定時隙分配的基礎上提出了一種改進的動態TDMA時隙分配算法。該算法根據節點數目的改變，通過針對不同的節點等級動態調整時隙分配策略，提高傳輸效率。對2種算法進行了對比仿真，仿真結果表明，改進的動態TDMA時隙分配算法更能適應節點數目不斷變化的場景。

移動自組織網絡；時分多址；時隙分配

0 引言

隨著無線移動設備使用的普及率越來越高，無線移動通信網絡的快速建網和性能優化成為通信領域亟待解決的重要問題。目前絕大多數無線移動設備之間都是通過服務商提供的固定設施來進行通信的，即使2個臨近設備之間的通信也需要通過基站，一旦基站出現故障則整個網絡將陷入癱瘓之中。為了避免這種情況的發生，MANET應運而生[1-3]。

MANET通常由一組帶有無線收發裝置的移動終端構成，是一種不需要基礎設施支持的動態網絡。這些移動終端除了完成傳統網絡終端所具有的收發功能外還擔負著轉發功能[4-5]。MANET的正常運行并不依賴于任何有特殊性的移動終端，并且當一些終端離開或加入網絡時能夠實現對網絡的動態調整。

MANET靈活性強、覆蓋范圍大、系統容量高且有著高效自組織能力，可以適應軍事通信中面臨的復雜無線電環境，滿足即使沒有固定基礎設施也能保證通信性能的要求，具有很好的應用前景[6-7]。

MAC協議作為MANET的關鍵技術之一，為MANET提供了必要的信道資源的分配功能與業務調度策略，確保了節點之間可以進行高質量的無線多跳通信[8]。MANET具有無中心、自組織、動態拓撲等各種不同于傳統網絡的特點，因此傳統網絡中使用的MAC協議無法直接應用到MANET中。多年來研究人員針對MANET提出了一些專用的MAC協議，這些都有各自的優缺點和適用范圍，因此如何針對特定的需求選擇和設計合適的MAC協議也就成為了研究的熱點[9]。

為了配合多節點隨機移動場景的需求，本文提出了一種改進的動態TDMA時隙分配算法，根據網絡狀態及拓撲結構動態劃分節點等級，提高網絡的傳輸效率并利用仿真軟件對算法性能進行了仿真。

1 典型的動態TDMA時隙分配算法分析

目前主要的MANET的MAC協議可以分為3類：基于競爭的MAC協議、基于分配的MAC協議和混合的MAC協議[10]。

1.1 基于競爭的時隙分配算法

在基于競爭的MAC協議中，當節點有傳輸任務時，通常是通過自由競爭的方式占用信道。當同一時刻競爭同一個信道的節點數等于或大于2個時，就會出現沖突[11]?；诟偁幍腗AC協議可以在傳輸負載比較低的情況下運行良好。但是在傳輸負載很重時，基于競爭的MAC協議的性能就會非常不理想。隨網絡負載的增加，基于競爭的MAC協議的吞吐量性能如1所示[12]。

圖1 基于競爭的MAC協議性能示意

1.2 基于分配的時隙分配算法

在基于分配的MAC協議中，首先將物理信道劃分為較小的“段”，然后將這些“段”或動態或靜態地分配給需要通信的節點，以此來避免沖突，根據網絡通信流量最大限度地節省能量。

TDMA協議是一種常用的基于分配的MAC協議，其幀結構如圖2所示。TDMA將時間劃分成互不重疊的幀，然后將幀劃分為互不重疊的時隙，將不同時隙與不同的節點ID(Identity)相對應。TDMA協議網絡性能如圖3所示，隨著網絡負載的增加，基于TDMA的MAC協議的吞吐量在達到飽和之后就不再有所增加。

圖2 TDMA幀結構示意

圖3 基于分配的MAC協議性能示意

1.3 混合的時隙分配算法

基于競爭的MAC協議與基于分配的MAC協議各有利弊，因此如何取長補短發揮2種協議各自優勢同時又能盡量避免短板，這是MAC協議研究領域的挑戰和熱點。從PTDMA(Users-Probabilistic Time Division Multiple Access)混合協議[13]到混合TDMA/CMSA(Time Division Multiple Access/ Carrier Sense Multiple Access)協議[14]再到ADAPT(A Dynamically Self-Adjusting Protocol)協議[15]，都面臨著同樣的問題，即沒有一個避免沖突的有效機制，因此都沒有得到廣泛的應用。

2 基于TDMA的固定時隙分配算法

在基于TDMA的固定時隙分配算法中，正常運行狀態下每個節點將平均分配時隙，使系統具有最低延遲保障，保證數據發送的穩定性和時效性，其幀結構如圖4所示。

圖4 基于TDMA的固定時隙分配算法的幀結構

在基于TDMA的固定時隙分配算法中，各個節點均能夠平均地得到時隙，這在對傳輸效率需求不高的情況下，其延時性能以及節點的抗沖突性能都呈現良好的狀況。但是當節點數量逐漸增加，并相應地對網絡的傳輸效率提出更高的需求時，基于TDMA的固定時隙分配算法并不能良好地適應這樣的動態場景。因此有必要提出一種新的TDMA時隙分配協議，能夠根據節點數目動態地調整這些參數的方法。

3 改進的動態TDMA時隙分配算法

3.1 協議原理

在本文提出的改進算法里，一級節點為高等級節點，二級節點為低等級節點。一級節點通過基于TDMA的固定時隙分配算法來分配得到可固定使用的TDMA時隙，二級節點則沒有固定的時隙可用，通過定期檢測共享TDMA時隙是否可用來及時地占用空閑時隙進行通信。并且定期檢測的頻率根據其鄰居中二級節點的個數來進行動態調整。本文協議流程如圖5所示。

移動節點的等級劃分時刻遵循著一個根本原則，即每一個二級節點在一跳范圍內至少有一個一級節點。這意味在一條路由上，信息的傳輸過程大致可以進行這樣的描述。每個二級節點是路由可達的，但是不會被選為轉發節點，只有一級節點有機會被選為路由轉發節點，這就形成了由一級節點組成的高容量的虛擬主干覆蓋網絡，如圖6所示。

圖5 本文協議流程

圖6 MANET的2層結構設計示意

因此，當一個二級節點產生的數據包需要傳輸到比較遠的目的地時，數據包在它的第一跳可以達到一級節點，從而通過高傳輸速率的主干網絡上的路由到達目的節點。該主干網絡適合用戶數據包和MANET控制包的數據傳輸和延遲。因為每個一級節點在每一個幀周期都有一個分配給它的循環TDMA時隙，它通常既可以傳輸它產生的數據又可以傳遞來自其他節點的數據，每個功能都可以保持低延遲。

3.2 時隙幀結構的設計

根據本文提出的算法的工作原理，對幀結構進行了特定的設計，不同于傳統的TDMA幀結構，本文提出的改進算法對應的傳輸幀由信令間隔、競爭間隔和數據間隔3部分組成，如圖7所示。每個一級節點在每個幀周期內均會占有一個TDMA信令時隙，作為網絡中節點控制同步、時隙分配以及控制其他行為的信道，且每個信令時隙均在數據間隔內對應一個可用的數據發送時隙，作為每個節點的傳輸業務數據的信道。一級節點通過基于TDMA的固定時隙分配算法可以使得每個節點在數據間隔獲得至少一個固定的TDMA時隙，以便其進行大數據量的傳輸。二級節點則沒有固定的專用TDMA時隙，而是在需要傳輸的時候通過CSMA/CA(Carrier Sense Multiple Access with Collision Avoidance)機制在競爭間隔獲得TDMA時隙來傳輸。

圖7 幀結構的設計

由于幀結構的設計中，用于給一級節點分配的可以固定循環使用的TDMA時隙數量是有限的，因此改進的動態TDMA時隙分配算法通過超額的一級節點降為二級節點，來平衡不斷升級的節點數量。同時，如果一個二級節點發起一個大容量同步數據流，那么它就可以很容易地晉升為一級節點，從而獲取一個可循環使用的TDMA時隙。隨著二級節點數量增大，為了保持二級節點信道訪問正常運行，分配給每個二級節點的二級節點訪問信道必須愈來愈小。因此本文提出的改進的動態TDMA時隙分配算法可以將二級節點訪問信道靈活地切割成更小的時間段。

4 仿真與分析

4.1 仿真環境及參數設置

為了測試本文提出協議的合理性和性能，采用與基于TDMA的固定時隙分配算法進行對比的方式，分析2種算法在傳輸層時延和端到端吞吐量的仿真數據。仿真的具體參數設置如表1所示。

表1 仿真場景參數值

參數名稱參數值環境尺寸/km通信距離/km仿真時間/s節點最大移動速率/(km/h)20×2021080

4.2 仿真結果與分析

4.2.1 傳輸層時延

2種時隙分配算法的傳輸層時延變化曲線如圖8所示。從圖8可知，在基于TDMA的固定時隙分配算法中，在節點數量達到10時傳輸層時延一直在1 s以下，但是在節點數量超過10之后，延遲急劇增加；在改進的動態TDMA時隙分配算法中，其傳輸層時延并沒有明顯的改變。這主要是由于基于TDMA的固定時隙分配算法是注重公平性的策略，而本文提出的新算法由于更加注重效率，所以在部分固定時隙的基礎上加入了動態分配時隙策略，大幅度減少了等級高的節點的傳輸層時延。

圖8 2種算法的傳輸層時延對比

4.2.2 端到端吞吐量

基于TDMA的固定時隙分配算法與本文提出的改進的動態TDMA時隙分配算法的端到端吞吐量對比結果如圖9所示。

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

從圖9可以看出，基于TDMA的固定時隙分配算法由于不能動態適應節點數量的變化，對于節點數大于16之后的場景，其端到端的吞吐量急劇下降；相對于基于TDMA的固定時隙分配算法，本文提出的改進的動態時隙算法由于充分利用了固定時隙分配、動態時隙競爭的優點，引入動態分級原理應對節點數量的變化，針對不同等級的節點實時調整時隙分配策略，提高了傳輸效率。

5 結束語

目前，MANET的許多理論和技術仍處于探索階段，但其巨大的潛能會得到人們越來越多的重視。本文在基于TDMA的固定時隙分配算法的基礎上提出了一種改進的動態TDMA時隙分配算法，通過節點的動態分級和拓撲的2層結構，在保證基本業務質量的前提下，根據節點數量的增加，最大限度地滿足大數量用戶的通信需求。通過對比仿真可以看出，本文提出的改進的動態TDMA時隙分配算法大幅度地提高在大量節點的MANET場景中的網絡效率。

[1] 王寶康，陳強.一種改進的Ad hoc網絡中動態TDMA時隙分配方法[J].網絡天地,2011(14):50-52.

[2] FU W,AGRAWAL D P.Capacity of Hybrid Wireless Mesh Networks with Random APS[J].IEEE Transactions on Mobile Computing,2013,12(1):136-150.

[3] BAI F,SADAGOPAN N,KRISHNAMACHARI B,et al.Modelling PathDuration Distributions in MANETS and Their Import on Reactive Routing Protocols[J].IEEE J,on Selected Areas in Communications,2004,22(7):1357-1373.

[4] DJENOURI D,KHELLADI L,BADACHE N.A Survey of Security Issues in Mobile Ad Hoc and Sensor Networks[J].IEEE Communications Surveys & Tutorials,2005,7(4):2-28.

[5] 劉進軍，傅振宇，李濤,等.分布式TDMA網絡的時隙設計技術[J].移動通信,2013(22):58-61.

[6] 趙志峰，趙曦濱，陳丹寧.多維MANET可靠性建模研究[J].計算機科學,2011(5):60-63.

[7] CAMP T,BOLENG J.A Survey of Mobility Models for Ad Hoc Network Research[J].Wireless Communication & Mobile Computing(WCMC),Special Issue on Mobile Ad Hoc Networking:Research,Trends and Applications,2002,2(5):483-502.

[8] 王英杰，劉覓，吳振華,等.無線Mesh網絡的最大并發公平調度[J].北京郵電大學學報,2007,30(4):33-36.

[9] 岳鵬，王柯，鄭杰.一種基于優先級的TDMA時隙接入算法[J].無線互聯科技,2016(4):87-89.

[10] 劉慶剛.基于動態優先級表的TDMA時隙分配[J].通信技術,2013(7):44-46.

[11] 張揚，曾曉峰.一種基于分簇和概率函數的電力線通信MAC協議[J].武漢大學學報(工學版),2015,48(2):216-219.

[12] 李衛.Ad Hoc網絡中的混合類MAC協議研究[D].長沙:國防科學技術大學,2008:5-9.

[13] EPHREMIDES A,MOWAFI O A.Analysis of A Hybrid Access Scheme for Buffered Users-Probabilistic Time Division[J].IEEE Transactions on Software Engineering,1982,8(1):52-61.

[14] SHARP B A,GRINDROD E A,CAMM D A.Hybrid TDMA/CSMA Protocol for Self Managing Packet Radio Networks[J].IEEE International Conference on Universal Personal Communications,1995(10):929-933.

[15] CHLAMTAC I,FARAGO A,MYERS A.D.ADAPT:A Dynamically Self-adjusting Media Access Control Protocol for Ad-Hoc Networks[J].Global Telecommunications Conference,1999(1):11-15.

ResearchonImprovedDynamicTDMASlotAllocationAlgorithm

QIN Qian

(The54thResearchInstituteofCETC,ShijiazhuangHebei050081,China)

On the basis of static allocation algorithm based on TDMA,an improved dynamic TDMA slot allocation algorithm is proposed,which suits the scenario of multiple nodes moving stochastically.This algorithm can adjust slot scheduling strategy for nodes with different priorities according to the number of slots,so that high transmission efficiency can be achieved.The contrast simulation between the two algorithms is done in this paper,from which it can be concluded that the improved dynamic TDMA slot allocation algorithm is more suitable for the scenario that number of nodes keeps changing.

MANET;TDMA;slot allocation

10.3969/j.issn.1003-3106.2017.12.01

秦茜.一種改進的動態TDMA時隙分配算法研究[J].無線電工程,2017,47(12):1-4.[QIN Qian.Research on Improved Dynamic TDMA Slot Allocation Algorithm[J].Radio Engineering,2017,47(12):1-4.]

TN911

A

1003-3106(2017)12-0001-04

2017-02-16

國家科技重大專項基金資助項目(2015ZX03004002-004);國家自然科學基金面上項目(61671179)。

秦茜女，(1988—)，助理工程師。主要研究方向：無線通信。