秦 茜

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

一種改進(jìn)的動(dòng)態(tài)TDMA時(shí)隙分配算法研究

秦 茜

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

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

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

0 引言

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

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

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

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

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

1 典型的動(dòng)態(tài)TDMA時(shí)隙分配算法分析

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

1.1 基于競(jìng)爭(zhēng)的時(shí)隙分配算法

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

圖1 基于競(jìng)爭(zhēng)的MAC協(xié)議性能示意

1.2 基于分配的時(shí)隙分配算法

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

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

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

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

1.3 混合的時(shí)隙分配算法

基于競(jìng)爭(zhēng)的MAC協(xié)議與基于分配的MAC協(xié)議各有利弊，因此如何取長(zhǎng)補(bǔ)短發(fā)揮2種協(xié)議各自優(yōu)勢(shì)同時(shí)又能盡量避免短板，這是MAC協(xié)議研究領(lǐng)域的挑戰(zhàn)和熱點(diǎ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]，都面臨著同樣的問(wèn)題，即沒(méi)有一個(gè)避免沖突的有效機(jī)制，因此都沒(méi)有得到廣泛的應(yīng)用。

2 基于TDMA的固定時(shí)隙分配算法

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

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

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

3 改進(jìn)的動(dòng)態(tài)TDMA時(shí)隙分配算法

3.1 協(xié)議原理

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

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

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

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

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

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

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

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

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

4 仿真與分析

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

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

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

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

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

4.2.1 傳輸層時(shí)延

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

圖8 2種算法的傳輸層時(shí)延對(duì)比

4.2.2 端到端吞吐量

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

圖9 2種算法的端到端吞吐量對(duì)比

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

5 結(jié)束語(yǔ)

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

[1] 王寶康，陳強(qiáng).一種改進(jìn)的Ad hoc網(wǎng)絡(luò)中動(dòng)態(tài)TDMA時(shí)隙分配方法[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] 劉進(jìn)軍，傅振宇，李濤,等.分布式TDMA網(wǎng)絡(luò)的時(shí)隙設(shè)計(jì)技術(shù)[J].移動(dòng)通信,2013(22):58-61.

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

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

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

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

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

秦茜.一種改進(jìn)的動(dòng)態(tài)TDMA時(shí)隙分配算法研究[J].無(wú)線電工程,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

國(guó)家科技重大專項(xiàng)基金資助項(xiàng)目(2015ZX03004002-004);國(guó)家自然科學(xué)基金面上項(xiàng)目(61671179)。

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