一種改進的動態(tài)TDMA時隙分配算法研究

秦 茜

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

一種改進的動態(tài)TDMA時隙分配算法研究

秦 茜

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

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

移動自組織網(wǎng)絡(luò)；時分多址；時隙分配

0 引言

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

MANET通常由一組帶有無線收發(fā)裝置的移動終端構(gòu)成，是一種不需要基礎(chǔ)設(shè)施支持的動態(tài)網(wǎng)絡(luò)。這些移動終端除了完成傳統(tǒng)網(wǎng)絡(luò)終端所具有的收發(fā)功能外還擔(dān)負著轉(zhuǎn)發(fā)功能[4-5]。MANET的正常運行并不依賴于任何有特殊性的移動終端，并且當(dāng)一些終端離開或加入網(wǎng)絡(luò)時能夠?qū)崿F(xiàn)對網(wǎng)絡(luò)的動態(tài)調(diào)整。

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

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

為了配合多節(jié)點隨機移動場景的需求，本文提出了一種改進的動態(tài)TDMA時隙分配算法，根據(jù)網(wǎng)絡(luò)狀態(tài)及拓撲結(jié)構(gòu)動態(tài)劃分節(jié)點等級，提高網(wǎng)絡(luò)的傳輸效率并利用仿真軟件對算法性能進行了仿真。

1 典型的動態(tài)TDMA時隙分配算法分析

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

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

在基于競爭的MAC協(xié)議中，當(dāng)節(jié)點有傳輸任務(wù)時，通常是通過自由競爭的方式占用信道。當(dāng)同一時刻競爭同一個信道的節(jié)點數(shù)等于或大于2個時，就會出現(xiàn)沖突[11]。基于競爭的MAC協(xié)議可以在傳輸負載比較低的情況下運行良好。但是在傳輸負載很重時，基于競爭的MAC協(xié)議的性能就會非常不理想。隨網(wǎng)絡(luò)負載的增加，基于競爭的MAC協(xié)議的吞吐量性能如1所示[12]。

圖1 基于競爭的MAC協(xié)議性能示意

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

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

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

圖2 TDMA幀結(jié)構(gòu)示意

圖3 基于分配的MAC協(xié)議性能示意

1.3 混合的時隙分配算法

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

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

在基于TDMA的固定時隙分配算法中，正常運行狀態(tài)下每個節(jié)點將平均分配時隙，使系統(tǒng)具有最低延遲保障，保證數(shù)據(jù)發(fā)送的穩(wěn)定性和時效性，其幀結(jié)構(gòu)如圖4所示。

圖4 基于TDMA的固定時隙分配算法的幀結(jié)構(gòu)

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

3 改進的動態(tài)TDMA時隙分配算法

3.1 協(xié)議原理

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

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

圖5 本文協(xié)議流程

圖6 MANET的2層結(jié)構(gòu)設(shè)計示意

因此，當(dāng)一個二級節(jié)點產(chǎn)生的數(shù)據(jù)包需要傳輸?shù)奖容^遠的目的地時，數(shù)據(jù)包在它的第一跳可以達到一級節(jié)點，從而通過高傳輸速率的主干網(wǎng)絡(luò)上的路由到達目的節(jié)點。該主干網(wǎng)絡(luò)適合用戶數(shù)據(jù)包和MANET控制包的數(shù)據(jù)傳輸和延遲。因為每個一級節(jié)點在每一個幀周期都有一個分配給它的循環(huán)TDMA時隙，它通常既可以傳輸它產(chǎn)生的數(shù)據(jù)又可以傳遞來自其他節(jié)點的數(shù)據(jù)，每個功能都可以保持低延遲。

3.2 時隙幀結(jié)構(gòu)的設(shè)計

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

圖7 幀結(jié)構(gòu)的設(shè)計

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

4 仿真與分析

4.1 仿真環(huán)境及參數(shù)設(shè)置

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

表1 仿真場景參數(shù)值

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

4.2 仿真結(jié)果與分析

4.2.1 傳輸層時延

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

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

4.2.2 端到端吞吐量

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

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

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

5 結(jié)束語

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

[1] 王寶康，陳強.一種改進的Ad hoc網(wǎng)絡(luò)中動態(tài)TDMA時隙分配方法[J].網(wǎng)絡(luò)天地,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網(wǎng)絡(luò)的時隙設(shè)計技術(shù)[J].移動通信,2013(22):58-61.

[6] 趙志峰，趙曦濱，陳丹寧.多維MANET可靠性建模研究[J].計算機科學(xué),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網(wǎng)絡(luò)的最大并發(fā)公平調(diào)度[J].北京郵電大學(xué)學(xué)報,2007,30(4):33-36.

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

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

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

[12] 李衛(wèi).Ad Hoc網(wǎng)絡(luò)中的混合類MAC協(xié)議研究[D].長沙:國防科學(xué)技術(shù)大學(xué),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

秦茜.一種改進的動態(tài)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);國家自然科學(xué)基金面上項目(61671179)。

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