基于TDMA的空中自組網(wǎng)MAC層資源調(diào)度算法研究

張子?xùn)|，宋志群，劉玉濤，段嘯寒，于子婷

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

0 引言

空中移動(dòng)無(wú)線自組織網(wǎng)絡(luò)是一個(gè)新的研究領(lǐng)域，其基本思路是在空中的節(jié)點(diǎn)通過(guò)多跳的方式，遠(yuǎn)距離傳輸控制信息及數(shù)據(jù)信息從而達(dá)到遠(yuǎn)距離通信的目的[1]。在一定范圍內(nèi)的航空飛行器之間相互轉(zhuǎn)發(fā)控制指令信息，交換各自的飛行狀態(tài)、感知信息等數(shù)據(jù)，并自動(dòng)連接，以建立一個(gè)移動(dòng)自組網(wǎng)(MANET[2]，mobile ad hoc network)?？罩薪M網(wǎng)具有組網(wǎng)靈活擴(kuò)展且無(wú)需網(wǎng)絡(luò)基礎(chǔ)設(shè)施等優(yōu)勢(shì)，在航空通信中有著廣闊的發(fā)展前景。其具備的自組織、自恢復(fù)、高動(dòng)態(tài)、低時(shí)延等特點(diǎn)可以滿足高空無(wú)線通信的特定需求，是高空通信的重要發(fā)展方向，也是現(xiàn)代無(wú)線通信的重要組成部分[3]。

近些年針對(duì)空中自組網(wǎng)的媒體接入控制(MAC，media access control)協(xié)議研究較少，其中文獻(xiàn)[4]是無(wú)中心節(jié)點(diǎn)的分布式時(shí)分多址(TDMA，time division multiple access)協(xié)議，各個(gè)節(jié)點(diǎn)使用分配的時(shí)隙進(jìn)行數(shù)據(jù)傳輸。文獻(xiàn)[5]的無(wú)沖突MAC協(xié)議(CF-MAC，collision free media access control)通過(guò)載波監(jiān)聽(tīng)控制時(shí)隙的分配。文獻(xiàn)[6]通過(guò)規(guī)定不同節(jié)點(diǎn)有不同優(yōu)先級(jí)占用時(shí)隙，但是沒(méi)有考慮不同時(shí)隙的不同業(yè)務(wù)需求。文獻(xiàn)[7]提出的自組織時(shí)分多址接入?yún)f(xié)議(ESTDMA，evolutionary self-organized time division multiple access)可以通過(guò)對(duì)閑置時(shí)隙的二次預(yù)約合理的分配時(shí)隙。但是二次分配也會(huì)導(dǎo)致傳輸失敗增多使網(wǎng)絡(luò)時(shí)延難以控制。文獻(xiàn)[8]設(shè)計(jì)的并發(fā)傳輸MAC協(xié)議(CTMAC，concurrent transmission media access control)通過(guò)載波監(jiān)聽(tīng)與隨機(jī)退避機(jī)制。雖然可以提高TDMA協(xié)議的信道利用率，但是隨之而來(lái)的便是吞吐量的降低以及時(shí)延的增大。優(yōu)先級(jí)競(jìng)爭(zhēng)時(shí)分多址(P-TDMA，priority-based time division multiple access)協(xié)議[9]本質(zhì)上是動(dòng)態(tài)時(shí)隙分配算法，但是卻融合了靜態(tài)時(shí)隙分配的特點(diǎn)，構(gòu)造了一種特殊的幀結(jié)構(gòu)，避免了多節(jié)點(diǎn)的沖突碰撞問(wèn)題。P-TDMA 協(xié)議的缺點(diǎn)是沒(méi)有到考慮不同節(jié)點(diǎn)業(yè)務(wù)量不同。且混合分配模式在不同業(yè)務(wù)量下網(wǎng)絡(luò)性能不穩(wěn)定。

TDMA[10]協(xié)議的基本思想是將時(shí)間分割為幀的形式，每一幀將不同的信息儲(chǔ)存在不同的時(shí)隙之中，每個(gè)用戶通過(guò)算法被分配不同的時(shí)隙[11]。在不同時(shí)隙發(fā)送數(shù)據(jù)就表示發(fā)送的時(shí)間是何時(shí)，即數(shù)據(jù)傳輸?shù)牡却龝r(shí)延。傳輸時(shí)延主要受時(shí)隙分配結(jié)果、無(wú)線傳輸時(shí)延、處理時(shí)延以及總幀長(zhǎng)大小等因素的影響[12]。目前常見(jiàn)的TDMA時(shí)隙分配方法主要包含兩種：靜態(tài)分配法與動(dòng)態(tài)分配法。靜態(tài)分配法是給每個(gè)節(jié)點(diǎn)分配一定數(shù)量的時(shí)隙來(lái)保證數(shù)據(jù)發(fā)送與接收的及時(shí)性，擁有穩(wěn)定的時(shí)延；動(dòng)態(tài)分配法則是根據(jù)不同節(jié)點(diǎn)的需求不同，動(dòng)態(tài)調(diào)整時(shí)隙的分配數(shù)量，提高時(shí)隙的利用率，以此來(lái)適應(yīng)更大規(guī)模的網(wǎng)絡(luò)。本文采用的混合分配法綜合了靜態(tài)分配與動(dòng)態(tài)分配兩種分配方式的優(yōu)點(diǎn)具有更高的網(wǎng)絡(luò)效率。

針對(duì)高空高動(dòng)態(tài)遠(yuǎn)距離通信的場(chǎng)景，現(xiàn)有多跳TDMA協(xié)議存在的時(shí)延過(guò)大、吞吐量不足等問(wèn)題。本文結(jié)合定向天線的通信特點(diǎn)，參考P-TDMA協(xié)議算法設(shè)計(jì)了一種基于TDMA的定向分布式資源調(diào)度算法(M-TDMA，mix time division multiple access)。本文設(shè)計(jì)的M-TDMA算法有如下改進(jìn)創(chuàng)新：1)設(shè)計(jì)了一種基于拓?fù)涞泥従庸?jié)點(diǎn)分配算法，根據(jù)動(dòng)態(tài)變化的節(jié)點(diǎn)拓?fù)湫畔?，尋找各個(gè)節(jié)點(diǎn)的鄰居節(jié)點(diǎn)，按照點(diǎn)號(hào)依次為每個(gè)在網(wǎng)節(jié)點(diǎn)分配時(shí)隙。由于定向自組網(wǎng)是根據(jù)時(shí)隙對(duì)來(lái)通信，在網(wǎng)節(jié)點(diǎn)固定分并不適用，因此采用鄰居節(jié)點(diǎn)固定分策略。并通過(guò)靜態(tài)分配與動(dòng)態(tài)分配相結(jié)合的混合模式，提升了網(wǎng)絡(luò)吞吐量；2)靜態(tài)分配策略：為各個(gè)節(jié)點(diǎn)設(shè)置時(shí)延保障靜態(tài)時(shí)隙以應(yīng)對(duì)突發(fā)的業(yè)務(wù)需求，引入分配系數(shù)，分配系數(shù)隨節(jié)點(diǎn)空閑時(shí)隙的數(shù)量變化進(jìn)行動(dòng)態(tài)調(diào)整，以此來(lái)均衡靜態(tài)與動(dòng)態(tài)分配的的時(shí)隙數(shù)量有效降低了傳輸時(shí)延；3)動(dòng)態(tài)分配策略：在業(yè)務(wù)優(yōu)先級(jí)的基礎(chǔ)上設(shè)計(jì)節(jié)點(diǎn)流量預(yù)測(cè)算法，MAC層識(shí)別業(yè)務(wù)信息量不同，首先根據(jù)流量預(yù)測(cè)算法，通過(guò)歷史周期的鄰居節(jié)點(diǎn)業(yè)務(wù)量大小，預(yù)測(cè)本周期業(yè)務(wù)量大小，從而給不同業(yè)務(wù)需求的節(jié)點(diǎn)分配不同數(shù)量的時(shí)隙。隨后動(dòng)態(tài)分配時(shí)隙數(shù)量，當(dāng)預(yù)測(cè)到節(jié)點(diǎn)有大量業(yè)務(wù)需求時(shí)，優(yōu)先將空閑時(shí)隙分給預(yù)測(cè)業(yè)務(wù)量大的節(jié)點(diǎn)傳輸業(yè)務(wù)，剩余時(shí)隙分配給其它低業(yè)務(wù)量節(jié)點(diǎn)。節(jié)點(diǎn)分配的時(shí)隙數(shù)量隨著調(diào)度周期進(jìn)行動(dòng)態(tài)變化，最后根據(jù)業(yè)務(wù)優(yōu)先級(jí)算法，為各優(yōu)先級(jí)的業(yè)務(wù)分配不同數(shù)量的時(shí)隙。

1 自組網(wǎng)MAC協(xié)議

1.1 MAC協(xié)議原理

MAC層協(xié)議作為無(wú)線通信的基礎(chǔ)，在無(wú)線網(wǎng)絡(luò)通信中起著至關(guān)重要的作用，通過(guò)分配各個(gè)節(jié)點(diǎn)無(wú)線信道資源，在提升傳輸效率的基礎(chǔ)上保障公平性。對(duì)傳輸時(shí)延、網(wǎng)絡(luò)吞吐量等網(wǎng)絡(luò)性能指標(biāo)起著關(guān)鍵性作用[13]。隨著現(xiàn)代無(wú)線自組織網(wǎng)絡(luò)規(guī)模越來(lái)越大，服務(wù)質(zhì)量 (QoS，quality of service)指標(biāo)的保證顯得愈發(fā)關(guān)鍵，如何更好地進(jìn)行資源調(diào)度是MAC協(xié)議研究的熱點(diǎn)之一[14-22]。

通常MAC協(xié)議多采用集中式的調(diào)度方式，通過(guò)交互整個(gè)網(wǎng)絡(luò)拓?fù)涞墓?jié)點(diǎn)信息，根據(jù)節(jié)點(diǎn)優(yōu)先級(jí)不同分配不同的時(shí)隙，并使用中心節(jié)點(diǎn)廣播分配時(shí)隙。但由于高空環(huán)境下通信距離遠(yuǎn)，網(wǎng)絡(luò)拓?fù)鋭?dòng)態(tài)變化快，又有高帶寬的傳輸需求，需要采用定向天線。而定向天線同一時(shí)刻需要點(diǎn)對(duì)點(diǎn)收發(fā)波束朝向一致才可以通信，集中式協(xié)議不適用。因此只能使用無(wú)中心節(jié)點(diǎn)的分布式時(shí)隙分配方法[23]。這種方法不需要中心節(jié)點(diǎn)的參與，只通過(guò)部分節(jié)點(diǎn)的信息交互就可以完成網(wǎng)絡(luò)時(shí)隙的合理分配。

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

本文M-TDMA算法有3種幀類型，分別為鄰居發(fā)現(xiàn)幀、預(yù)約幀和數(shù)據(jù)幀。分別對(duì)應(yīng)鄰居發(fā)現(xiàn)、預(yù)約、數(shù)據(jù)傳輸3個(gè)階段。鄰居發(fā)現(xiàn)幀用于實(shí)現(xiàn)節(jié)點(diǎn)之間的波束對(duì)準(zhǔn)及網(wǎng)絡(luò)同步，預(yù)約幀用于實(shí)現(xiàn)節(jié)點(diǎn)間的分布式業(yè)務(wù)預(yù)約，數(shù)據(jù)幀用于業(yè)務(wù)傳輸。算法的時(shí)隙結(jié)構(gòu)如圖1所示。其中SYN為鄰居發(fā)現(xiàn)幀，DATA為數(shù)據(jù)幀，R1、R2為預(yù)約幀。每個(gè)調(diào)度周期有4個(gè)鄰居發(fā)現(xiàn)幀可以進(jìn)行4次鄰居發(fā)現(xiàn)。一個(gè)周期內(nèi)各種幀的幀長(zhǎng)與數(shù)量如表1所示。一個(gè)調(diào)度周期總共1 s。調(diào)度周期包含的各幀信息如下：

圖1 M-TDMA算法時(shí)隙結(jié)構(gòu)

表1 幀長(zhǎng)設(shè)計(jì)

1)鄰居發(fā)現(xiàn)幀的長(zhǎng)度。4個(gè)鄰居發(fā)現(xiàn)幀幀長(zhǎng)為10 ms。

2)預(yù)約幀的長(zhǎng)度。R1與R2長(zhǎng)度相同，本文設(shè)計(jì)為1.5 ms。

3)數(shù)據(jù)幀的長(zhǎng)度。由于數(shù)據(jù)時(shí)隙數(shù)量較多，每個(gè)數(shù)據(jù)幀長(zhǎng)度不能超過(guò)10 ms否則將會(huì)無(wú)空余時(shí)隙設(shè)置預(yù)約幀，本文數(shù)據(jù)幀長(zhǎng)為5 ms。

預(yù)約幀結(jié)構(gòu)如圖2所示，當(dāng)節(jié)點(diǎn)入網(wǎng)后，MAC層有數(shù)據(jù)需要傳輸，此時(shí)節(jié)點(diǎn)通過(guò)預(yù)約幀發(fā)送請(qǐng)求信息，其攜帶的信息有數(shù)據(jù)大小、優(yōu)先級(jí)節(jié)點(diǎn)ID、鄰居節(jié)點(diǎn)信息等。接收節(jié)點(diǎn)收到其他節(jié)點(diǎn)發(fā)送的預(yù)約幀后，將預(yù)約幀內(nèi)容匯總儲(chǔ)存并在預(yù)約確認(rèn)幀中發(fā)出反饋。預(yù)約確認(rèn)幀結(jié)構(gòu)與預(yù)約幀相同，二者使得全網(wǎng)鄰居信息互通。本文每個(gè)預(yù)約幀長(zhǎng)度均為1.5 ms，由預(yù)約時(shí)隙R1、預(yù)約確認(rèn)時(shí)隙R2和保護(hù)間隔組成。R1時(shí)隙和R2時(shí)隙長(zhǎng)度相同。每個(gè)預(yù)約幀中的發(fā)送節(jié)點(diǎn)對(duì)互相綁定，兩個(gè)節(jié)點(diǎn)互為目的節(jié)點(diǎn)。保護(hù)間隔長(zhǎng)度約占預(yù)約幀總長(zhǎng)度的10%，用以確保節(jié)點(diǎn)收到R1后能夠有充足時(shí)間解調(diào)并計(jì)算時(shí)隙資源，最終將結(jié)果附在R2中發(fā)出。

圖2 預(yù)約幀結(jié)構(gòu)

數(shù)據(jù)階段，節(jié)點(diǎn)間按照上個(gè)預(yù)約階段的預(yù)約結(jié)果進(jìn)行數(shù)據(jù)傳輸。在一個(gè)數(shù)據(jù)時(shí)隙進(jìn)行信息交互的兩個(gè)節(jié)點(diǎn)分別為發(fā)送數(shù)據(jù)節(jié)點(diǎn)和接收數(shù)據(jù)節(jié)點(diǎn)，二者已經(jīng)在之前的預(yù)約階段互相確定。在數(shù)據(jù)傳輸過(guò)程通信雙方的收發(fā)天線按照鄰居發(fā)現(xiàn)的結(jié)果相互對(duì)準(zhǔn)。為保證協(xié)議層數(shù)據(jù)的正確接收，數(shù)據(jù)幀應(yīng)預(yù)留一定的長(zhǎng)度間隔作為保護(hù)間隔，用于補(bǔ)償遠(yuǎn)距離數(shù)據(jù)的傳輸時(shí)延。剩余的時(shí)隙根據(jù)物理層幀結(jié)構(gòu)進(jìn)行靈活改動(dòng)，設(shè)計(jì)為一個(gè)或多個(gè)時(shí)隙，并根據(jù)需求發(fā)送至一個(gè)或多個(gè)目的節(jié)點(diǎn)。

2 資源調(diào)度算法

2.1 MAC協(xié)議資源調(diào)度算法

資源調(diào)度算法包括時(shí)隙預(yù)約、業(yè)務(wù)量統(tǒng)計(jì)、時(shí)隙排布三部分，業(yè)務(wù)量統(tǒng)計(jì)用于確定本次調(diào)度分配的時(shí)隙數(shù)量，隨后根據(jù)業(yè)務(wù)量統(tǒng)計(jì)的結(jié)果進(jìn)行預(yù)約，預(yù)約過(guò)程使用時(shí)隙排布策略以確保時(shí)隙的均勻分配。

資源調(diào)度算法流程為：首先進(jìn)行節(jié)點(diǎn)初始化，隨后的時(shí)隙請(qǐng)求階段，節(jié)點(diǎn)根據(jù)緩存的時(shí)隙需求，在對(duì)應(yīng)時(shí)隙發(fā)送請(qǐng)求并接受其他節(jié)點(diǎn)的請(qǐng)求信息。在響應(yīng)階段，節(jié)點(diǎn)依據(jù)之前階段的節(jié)點(diǎn)信息，與自身時(shí)隙狀態(tài)整合匯總，通過(guò)本文的資源調(diào)度算法分配時(shí)隙。最后進(jìn)入數(shù)據(jù)發(fā)送階段，各個(gè)節(jié)點(diǎn)根據(jù)資源調(diào)度算法分配的時(shí)隙發(fā)送數(shù)據(jù)。本文具體算法基本流程如圖3所示。

圖3 MAC協(xié)議算法流程

2.2 業(yè)務(wù)量統(tǒng)計(jì)策略

圖4 流量預(yù)測(cè)示意圖

(1)

(2)

節(jié)點(diǎn)根據(jù)鄰居節(jié)點(diǎn)的預(yù)測(cè)流量大小，對(duì)可分配時(shí)隙按比例進(jìn)行劃分，歷史業(yè)務(wù)量大的節(jié)點(diǎn)會(huì)分配更多的時(shí)隙，業(yè)務(wù)量小的節(jié)點(diǎn)會(huì)分配相對(duì)較少的時(shí)隙。此時(shí)由于分配比例系數(shù)與分配時(shí)隙總數(shù)無(wú)法整除可能會(huì)產(chǎn)生一定的時(shí)隙余量，將剩余時(shí)隙統(tǒng)一分配給預(yù)測(cè)業(yè)務(wù)量最大的節(jié)點(diǎn)。由于網(wǎng)絡(luò)拓?fù)涞膭?dòng)態(tài)變化，當(dāng)有新節(jié)點(diǎn)入網(wǎng)時(shí)，會(huì)分配一定比例的時(shí)隙。由于節(jié)點(diǎn)時(shí)隙分配比例是周期變化的，對(duì)于每個(gè)節(jié)點(diǎn)來(lái)說(shuō)，時(shí)隙的分配是公平的。最后給不同優(yōu)先級(jí)的業(yè)務(wù)劃分不同的時(shí)隙數(shù)目xi，業(yè)務(wù)優(yōu)先級(jí)越高分配時(shí)隙越多業(yè)務(wù)發(fā)送越快信道等待時(shí)延越低。業(yè)務(wù)量統(tǒng)計(jì)策略流程如圖5所示。

圖5 業(yè)務(wù)量統(tǒng)計(jì)流程

2.3 時(shí)隙預(yù)約策略

兩個(gè)節(jié)點(diǎn)之間的時(shí)隙分配通過(guò)預(yù)約時(shí)隙對(duì)，即預(yù)約時(shí)隙R1和預(yù)約時(shí)隙R2實(shí)現(xiàn)，如下為數(shù)據(jù)時(shí)隙分配過(guò)程，節(jié)點(diǎn)A和節(jié)點(diǎn)B互為鄰居業(yè)務(wù)傳輸節(jié)點(diǎn)。節(jié)點(diǎn)A為R1發(fā)送節(jié)點(diǎn)，節(jié)點(diǎn)B為R2發(fā)送節(jié)點(diǎn)。

2.3.1 節(jié)點(diǎn)A時(shí)隙預(yù)約步驟

步驟1：節(jié)點(diǎn)A在進(jìn)入自己的預(yù)約時(shí)隙后發(fā)送預(yù)約幀R1。節(jié)點(diǎn)A查看自己的緩存中是否有數(shù)據(jù)等待發(fā)送至節(jié)點(diǎn)B，如果需要預(yù)約數(shù)據(jù)時(shí)隙，則計(jì)算需要的時(shí)隙數(shù)，在預(yù)約幀R1中填充需要的時(shí)隙和本節(jié)點(diǎn)在數(shù)據(jù)階段的空閑時(shí)隙表。發(fā)送預(yù)約幀R1后，轉(zhuǎn)至步驟2。

步驟2：節(jié)點(diǎn)A持續(xù)收聽(tīng)信道，如果能夠正確接收預(yù)約確認(rèn)幀R2，則說(shuō)明在預(yù)約時(shí)隙節(jié)點(diǎn)A與節(jié)點(diǎn)B成功的進(jìn)行了信息交互。節(jié)點(diǎn)A讀取預(yù)約確認(rèn)幀R2中節(jié)點(diǎn)B回復(fù)的成功分配的時(shí)隙和數(shù)據(jù)時(shí)隙編號(hào)，在下一個(gè)數(shù)據(jù)階段，節(jié)點(diǎn)A將在數(shù)據(jù)時(shí)隙向節(jié)點(diǎn)B發(fā)送數(shù)據(jù)。同時(shí)節(jié)點(diǎn)A查看節(jié)點(diǎn)B是否有時(shí)隙需求。如果節(jié)點(diǎn)B有數(shù)據(jù)時(shí)隙需求，則讀取節(jié)點(diǎn)B的數(shù)據(jù)時(shí)隙需求和數(shù)據(jù)時(shí)隙號(hào)。在下一個(gè)數(shù)據(jù)階段，節(jié)點(diǎn)B將在這些數(shù)據(jù)時(shí)隙向節(jié)點(diǎn)A發(fā)送數(shù)據(jù)，在這些時(shí)隙節(jié)點(diǎn)A將切換為對(duì)節(jié)點(diǎn)B的接收狀態(tài)。

2.3.2 節(jié)點(diǎn)B時(shí)隙預(yù)約步驟

步驟1：在進(jìn)入預(yù)約時(shí)隙后持續(xù)收聽(tīng)信道。若接收到節(jié)點(diǎn)A發(fā)送的R1，則查看節(jié)點(diǎn)A是否申請(qǐng)分配數(shù)據(jù)時(shí)隙，若申請(qǐng)數(shù)據(jù)時(shí)隙，則查看需求的時(shí)隙數(shù)量，節(jié)點(diǎn)B根據(jù)自己的空閑時(shí)隙情況，安排盡可能符合需求的時(shí)隙。若節(jié)點(diǎn)A發(fā)送的R1幀中沒(méi)有申請(qǐng)分配數(shù)據(jù)時(shí)隙，則節(jié)點(diǎn)B根據(jù)自己緩存中待發(fā)數(shù)據(jù)的情況判斷是否需要申請(qǐng)數(shù)據(jù)時(shí)隙以及計(jì)算需要申請(qǐng)的數(shù)據(jù)時(shí)隙的數(shù)目，然后讀取預(yù)約幀R1中節(jié)點(diǎn)A的空閑時(shí)隙情況，同時(shí)根據(jù)自身的空閑時(shí)隙情況安排盡可能符合需求的時(shí)隙。

步驟2：進(jìn)入步驟2，節(jié)點(diǎn)B發(fā)送預(yù)約幀R2，告知節(jié)點(diǎn)A成功分配的數(shù)據(jù)時(shí)隙數(shù)目和數(shù)據(jù)時(shí)隙編號(hào)。時(shí)隙預(yù)約示意圖如圖6所示。

圖6 時(shí)隙預(yù)約示意圖

2.4 時(shí)隙排布策略

當(dāng)確定要分配的時(shí)隙數(shù)后，將確定分配的時(shí)隙排布到互相預(yù)約的兩個(gè)節(jié)點(diǎn)的空閑時(shí)隙交集中。時(shí)隙排布需要考慮的因素是時(shí)延抖動(dòng)。抖動(dòng)越大，說(shuō)明通信網(wǎng)絡(luò)越不穩(wěn)定。為了降低時(shí)延抖動(dòng)，需實(shí)現(xiàn)均勻間隔的時(shí)隙分配。本文采用貪心算法(又稱貪婪算法)：在對(duì)問(wèn)題求解時(shí)，總是做出在當(dāng)前看來(lái)的最好選擇。即不從整體最優(yōu)上加以考慮，所做出的僅是某種意義上的局部最優(yōu)解。貪心算法不是對(duì)所有問(wèn)題都能得到最優(yōu)解，但針對(duì)許多問(wèn)題，能產(chǎn)生整體最優(yōu)解或者是整體最優(yōu)解的近似解。分配時(shí)隙時(shí)采用貪心策略，只需考慮下個(gè)時(shí)隙與上個(gè)已分時(shí)隙的時(shí)隙間隔，而無(wú)需考慮整個(gè)時(shí)隙表的排布。

為保證傳輸時(shí)延，為每個(gè)節(jié)點(diǎn)分配的時(shí)隙與下個(gè)時(shí)隙的間隔不能過(guò)長(zhǎng)。為減小時(shí)延抖動(dòng)，相鄰兩個(gè)時(shí)隙的間隔數(shù)相對(duì)固定。由于時(shí)隙表的開(kāi)始部分存在鄰居發(fā)現(xiàn)幀，鄰居發(fā)現(xiàn)幀會(huì)帶來(lái)時(shí)延，剩余部分只存在預(yù)約幀，而預(yù)約幀有釋放的可能，所以兩種情況應(yīng)分別考慮。算法時(shí)隙排布流程如圖7(a)所示，其中LAST_NUM為上一次分配的時(shí)隙號(hào)。S為第一個(gè)空閑時(shí)隙號(hào)T為時(shí)隙分配步進(jìn)即每間隔T個(gè)時(shí)隙分一個(gè)時(shí)隙，N為所需分配時(shí)隙數(shù)。例如T=7時(shí)，隔7個(gè)數(shù)據(jù)時(shí)隙排布一個(gè)時(shí)隙。MAXNUM為時(shí)隙表數(shù)據(jù)時(shí)隙總數(shù)，若業(yè)務(wù)需求時(shí)隙數(shù)較少，則使時(shí)隙平均分配在總時(shí)隙表中。例如只需4個(gè)時(shí)隙時(shí)，時(shí)隙分配步進(jìn)為：

圖7 時(shí)隙排布策略流程及結(jié)果

(MAXNUM/4)-1

(3)

按照上述策略，節(jié)點(diǎn)分配時(shí)隙的結(jié)果如圖7(b)所示，其中灰色時(shí)隙為依據(jù)時(shí)隙排布策略所分配的時(shí)隙。

3 仿真與分析

3.1 仿真原理及參數(shù)

使用軟件Visual Studio進(jìn)行仿真代碼實(shí)現(xiàn)，使用Matlab對(duì)仿真數(shù)據(jù)進(jìn)行處理與分析。通過(guò)對(duì)算法的時(shí)延、吞吐量等性能指標(biāo)進(jìn)行優(yōu)化并與STDMA、P-TDMA等典型協(xié)議進(jìn)行性能對(duì)比，由此對(duì)M-TDMA算法性能進(jìn)行驗(yàn)證。主要仿真參數(shù)如表2所示。

表2 仿真參數(shù)設(shè)置

兩跳傳輸時(shí)延仿真首先輸入業(yè)務(wù)的發(fā)送節(jié)點(diǎn)和接收節(jié)點(diǎn)。根據(jù)時(shí)隙分配算法，計(jì)算出各節(jié)點(diǎn)的時(shí)隙表。通過(guò)產(chǎn)生一個(gè)隨機(jī)數(shù)作為起始時(shí)隙，從起始時(shí)隙的下一個(gè)時(shí)隙開(kāi)始搜尋時(shí)隙表，如果時(shí)隙表中該時(shí)隙的發(fā)送節(jié)點(diǎn)和業(yè)務(wù)發(fā)送節(jié)點(diǎn)相同，該時(shí)隙的接收節(jié)點(diǎn)與業(yè)務(wù)接收節(jié)點(diǎn)相同，則說(shuō)明數(shù)據(jù)會(huì)在該時(shí)隙發(fā)出。如果該時(shí)隙不是數(shù)據(jù)發(fā)送時(shí)隙，則繼續(xù)尋找。從起始時(shí)隙向后尋找發(fā)送時(shí)隙的過(guò)程即傳輸時(shí)延增加的過(guò)程，每過(guò)一個(gè)時(shí)隙，則傳輸時(shí)延增加一個(gè)時(shí)隙的時(shí)長(zhǎng)。找到發(fā)送時(shí)隙后，則返回總時(shí)長(zhǎng)即為傳輸時(shí)延。

多跳傳輸時(shí)延的計(jì)算為兩跳傳輸時(shí)延的多次調(diào)用。多跳傳輸時(shí)延的輸入為業(yè)務(wù)路徑。產(chǎn)生隨機(jī)數(shù)作為起始時(shí)隙，首先計(jì)算第1跳的傳輸時(shí)延，得出結(jié)果后，將第1跳傳輸時(shí)延的發(fā)時(shí)隙作為第2跳傳輸時(shí)延計(jì)算的起始時(shí)隙，繼續(xù)進(jìn)行第2跳傳輸時(shí)延的計(jì)算。整條業(yè)務(wù)路徑的傳輸時(shí)延依次疊加，得出總的傳輸時(shí)延。

在數(shù)據(jù)傳輸過(guò)程中由于在空中組網(wǎng)節(jié)點(diǎn)的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)變化較快，為保證QoS，通常MAC層仿真的多跳時(shí)延通常不能大于1 s，否則將會(huì)導(dǎo)致接收端丟包。仿真在統(tǒng)計(jì)接收數(shù)據(jù)包數(shù)量占總發(fā)送數(shù)據(jù)包的百分比即為丟包率。每一幀的最大數(shù)據(jù)載荷是固定的，節(jié)點(diǎn)之間有效數(shù)據(jù)的傳輸是通過(guò)數(shù)據(jù)時(shí)隙完成，通過(guò)計(jì)算在鏈路數(shù)據(jù)傳輸中使用的數(shù)據(jù)時(shí)隙總數(shù)即可計(jì)算出仿真數(shù)據(jù)傳輸過(guò)程的吞吐量大小。

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

為了評(píng)估M-TDMA算法的性能，分別從分配系數(shù)、網(wǎng)絡(luò)節(jié)點(diǎn)個(gè)數(shù)、數(shù)據(jù)發(fā)送速率等方面進(jìn)行仿真分析。其中分配系數(shù)是對(duì)M-TDMA算法進(jìn)行優(yōu)化；不同網(wǎng)絡(luò)節(jié)點(diǎn)個(gè)數(shù)與發(fā)送速率是用于對(duì)比M-TDMA與STDMA和P-TDMA三種算法的性能差異。通過(guò)網(wǎng)絡(luò)平均傳輸時(shí)延、網(wǎng)絡(luò)吞吐量、網(wǎng)絡(luò)丟包率等性能指標(biāo)對(duì)算法進(jìn)行優(yōu)化與分析。為了更好地驗(yàn)證M-TDMA 算法性能，本文進(jìn)行100次調(diào)度周期仿真并取平均值進(jìn)行結(jié)果分析。

3.2.1 不同拓?fù)鋱?chǎng)景與分配系數(shù)優(yōu)化

在節(jié)點(diǎn)高動(dòng)態(tài)場(chǎng)景下，網(wǎng)絡(luò)的拓?fù)湫问蕉鄻踊?，圖8為3種典型的網(wǎng)絡(luò)拓?fù)錉顟B(tài)，通過(guò)分別對(duì)比在3種不同拓?fù)湎乱惶潦臅r(shí)延大小來(lái)驗(yàn)證M-TDMA算法的網(wǎng)絡(luò)拓?fù)洵h(huán)境適用性。

圖8 3種不同網(wǎng)絡(luò)拓?fù)鋱D

根據(jù)圖9(a)結(jié)果可知：鏈狀拓?fù)溆捎诮Y(jié)構(gòu)簡(jiǎn)單且鄰居節(jié)點(diǎn)數(shù)相對(duì)固定，因此時(shí)延最小，且當(dāng)跳數(shù)增大時(shí)，時(shí)延上升最平穩(wěn)；而網(wǎng)狀與星狀拓?fù)溆捎诓煌?jié)點(diǎn)的鄰居節(jié)點(diǎn)數(shù)差異較大，因此時(shí)延的變化較為抖動(dòng)，但是單跳的平均時(shí)延仍在60 ms以內(nèi)，符合單跳傳輸指標(biāo)。綜上所述本文的M-TDMA算法在不同的拓?fù)錉顟B(tài)下網(wǎng)絡(luò)傳輸性能良好。

圖9 不同分配系數(shù)下網(wǎng)絡(luò)時(shí)延對(duì)比圖

分配系數(shù)RATTO的作用是：當(dāng)節(jié)點(diǎn)的可用空閑時(shí)隙較少時(shí)，通過(guò)RATTO使節(jié)點(diǎn)分配的靜態(tài)時(shí)隙減少、動(dòng)態(tài)時(shí)隙增多，使得傳輸時(shí)延相對(duì)穩(wěn)定。分配系數(shù)的優(yōu)化是通過(guò)在星狀網(wǎng)絡(luò)拓?fù)湎卤闅v分配系數(shù)，對(duì)比不同分配系數(shù)4跳傳輸路徑的時(shí)延大小。RATTO越小代表在節(jié)點(diǎn)可用時(shí)隙較少時(shí)分配的靜態(tài)時(shí)隙越少，W為參考靜態(tài)時(shí)隙閾值，用來(lái)設(shè)定靜態(tài)時(shí)隙數(shù)，在可用時(shí)隙足夠時(shí)，通常為總時(shí)隙的10%即可滿足靜態(tài)時(shí)隙需求。NUM為節(jié)點(diǎn)最大可分配時(shí)隙數(shù)。最終分配靜態(tài)時(shí)隙X為：

(4)

圖9為分配系數(shù)RATTO不同時(shí)，節(jié)點(diǎn)間不同鏈路網(wǎng)絡(luò)傳輸時(shí)延最大值、最小值以及平均值的變化對(duì)比圖，RATTO取值為15%、20%、25%、30%、50%五種不同的策略。不同鏈路路徑見(jiàn)表3所示。

表3 鏈路路徑設(shè)置

按照策略5即將當(dāng)前空閑時(shí)隙的一半進(jìn)行靜態(tài)分配，會(huì)導(dǎo)致先分配的節(jié)點(diǎn)靜態(tài)時(shí)隙過(guò)多而后分配節(jié)點(diǎn)出現(xiàn)“餓死”的現(xiàn)象使得時(shí)延增大。按照策略1與策略2進(jìn)行分配時(shí)，由于分配系數(shù)過(guò)小，分配的靜態(tài)時(shí)隙過(guò)少，導(dǎo)致無(wú)法及時(shí)發(fā)送突發(fā)業(yè)務(wù)導(dǎo)致時(shí)延增大。策略3與策略4的效果較好，通過(guò)對(duì)比可知由于策略3的分配系數(shù)較小，靜態(tài)時(shí)隙較少，應(yīng)對(duì)突發(fā)業(yè)務(wù)能力不足，從而導(dǎo)致出現(xiàn)節(jié)點(diǎn)傳輸最大時(shí)延與最小時(shí)延的差值較大，即產(chǎn)生了時(shí)延抖動(dòng)現(xiàn)象。策略4由于靜態(tài)時(shí)隙相對(duì)充足，沒(méi)有時(shí)延抖動(dòng)現(xiàn)象，仿真效果最優(yōu)。因此本文后續(xù)均采用策略4進(jìn)行仿真。

3.2.2 不同網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)

在自組網(wǎng)的網(wǎng)絡(luò)性能測(cè)試中，節(jié)點(diǎn)的數(shù)量是衡量MAC協(xié)議的負(fù)載能力的重要指標(biāo)，對(duì)網(wǎng)絡(luò)的性能起著關(guān)鍵的影響。本文針對(duì)不同的網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)，觀測(cè)對(duì)比網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)為2，4，6，8，10，12，14，16，18，20時(shí)M-TDMA與STDMA、P-TDMA協(xié)議的性能差異。

圖10為3種協(xié)議在不同節(jié)點(diǎn)數(shù)時(shí)網(wǎng)絡(luò)傳輸時(shí)延對(duì)比，當(dāng)節(jié)點(diǎn)增加時(shí)，網(wǎng)絡(luò)的傳輸時(shí)延逐漸增大，這是因?yàn)樵诙喙?jié)點(diǎn)的拓?fù)洵h(huán)境下節(jié)點(diǎn)的鄰居節(jié)點(diǎn)增多，緩存數(shù)據(jù)增大使得傳輸時(shí)延提升。而STDMA由于是全向天線協(xié)議，當(dāng)節(jié)點(diǎn)數(shù)量增多時(shí)可用時(shí)隙減少，當(dāng)節(jié)點(diǎn)數(shù)達(dá)到14節(jié)點(diǎn)后產(chǎn)生明顯的時(shí)延增大。P-TDMA算法由于其沒(méi)有考慮節(jié)點(diǎn)的不同業(yè)務(wù)量大小，當(dāng)節(jié)點(diǎn)增多時(shí)可用時(shí)隙減少時(shí)延增大加快，而M-TDMA協(xié)議獨(dú)特的節(jié)點(diǎn)流量預(yù)測(cè)算法，可以有效減少高業(yè)務(wù)量需求的時(shí)延，傳輸時(shí)延最低。

圖10 不同協(xié)議網(wǎng)絡(luò)時(shí)延對(duì)比圖

圖11為3種不同協(xié)議的網(wǎng)絡(luò)吞吐量隨節(jié)點(diǎn)數(shù)增多的變化圖。在節(jié)點(diǎn)數(shù)較少時(shí)，傳輸鏈路隨著節(jié)點(diǎn)數(shù)增多而增多，3種協(xié)議的吞吐量都隨著節(jié)點(diǎn)數(shù)的提升而提升。STDMA協(xié)議由于是全向天線協(xié)議，在8節(jié)點(diǎn)以上時(shí)，時(shí)隙數(shù)量減少，鏈路沖突幾率增大導(dǎo)致吞吐量開(kāi)始下降，而由于P-TDMA與M-TDMA協(xié)議是定向天線協(xié)議，通過(guò)空間復(fù)用實(shí)現(xiàn)同一個(gè)時(shí)隙多個(gè)鏈路同時(shí)發(fā)送數(shù)據(jù)，使得網(wǎng)絡(luò)吞吐量可以隨著節(jié)點(diǎn)的變多而增大。當(dāng)網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)增大到16個(gè)以上時(shí)，時(shí)隙資源使用充分，節(jié)點(diǎn)間可用鏈路減少，各個(gè)協(xié)議的吞吐量均開(kāi)始下降。并且M-TDMA由于使用混合分配模式，既有基于分配系數(shù)的靜態(tài)時(shí)隙又可使用預(yù)約幀為節(jié)點(diǎn)獲取更多的時(shí)隙資源發(fā)送數(shù)據(jù)，因此網(wǎng)絡(luò)吞吐性能最好。

圖11 不同協(xié)議網(wǎng)絡(luò)吞吐量對(duì)比圖

圖12為3種協(xié)議丟包率隨節(jié)點(diǎn)個(gè)數(shù)變化的情況。隨著節(jié)點(diǎn)數(shù)量增多，網(wǎng)絡(luò)拓?fù)鋸?fù)雜度逐漸增大，由于網(wǎng)絡(luò)節(jié)點(diǎn)高速動(dòng)態(tài)變化，網(wǎng)絡(luò)的傳輸路徑難以穩(wěn)定，網(wǎng)絡(luò)的擁塞度提升，傳輸時(shí)延增大，導(dǎo)致丟包現(xiàn)象產(chǎn)生。隨著節(jié)點(diǎn)的不斷增多，丟包率也逐步提升。P-TDMA協(xié)議由于競(jìng)爭(zhēng)分配機(jī)制，當(dāng)節(jié)點(diǎn)數(shù)增大時(shí)，沖突概率增加使得出現(xiàn)網(wǎng)絡(luò)堵塞，丟包率增大。而STDMA協(xié)議由于是全向天線協(xié)議沒(méi)有空間復(fù)用，節(jié)點(diǎn)數(shù)增大時(shí)在一個(gè)調(diào)度周期內(nèi)每個(gè)節(jié)點(diǎn)可用的數(shù)據(jù)時(shí)隙快速下降導(dǎo)致丟包率迅速上升。M-TDMA協(xié)議是定向協(xié)議，空間復(fù)用率高且使用混合資源分配模式，隨著節(jié)點(diǎn)增多，由于分配系數(shù)的引入，協(xié)議的靜態(tài)分配時(shí)隙隨之減少可用時(shí)隙不會(huì)快速下降，有效改善了網(wǎng)絡(luò)擁堵現(xiàn)象，丟包率相對(duì)較小。

圖12 網(wǎng)絡(luò)丟包率對(duì)比圖

3.2.3 不同的數(shù)據(jù)發(fā)送速率

本文通過(guò)改變節(jié)點(diǎn)的數(shù)據(jù)發(fā)送速率來(lái)觀察MAC協(xié)議在不同網(wǎng)絡(luò)負(fù)載下的性能，依據(jù)前文仿真數(shù)據(jù)將節(jié)點(diǎn)數(shù)目設(shè)置為14，在星狀拓?fù)湎逻M(jìn)行仿真。發(fā)送速率為100～1 000 kbps。

圖13為3種MAC協(xié)議在數(shù)據(jù)發(fā)送速率增大時(shí)平均時(shí)延的變化圖。數(shù)據(jù)發(fā)送速度在400 kbps以下時(shí)，各協(xié)議的傳輸時(shí)延為500 ms以內(nèi)。P-TDMA協(xié)議由于未考慮不同節(jié)點(diǎn)的業(yè)務(wù)量大小不同，當(dāng)傳輸速率在400 kbps以上時(shí)，大業(yè)務(wù)量節(jié)點(diǎn)的可用時(shí)隙減少，傳輸時(shí)延快速提升直至2.5 s左右。而STDMA協(xié)議的時(shí)延隨著發(fā)送速率的提升增大，在700 kbps以上時(shí)出現(xiàn)網(wǎng)絡(luò)擁塞，由于大量數(shù)據(jù)丟包，時(shí)延逐漸穩(wěn)定。而M-TDMA協(xié)議由于考慮了不同節(jié)點(diǎn)的業(yè)務(wù)量不同，按照流量預(yù)測(cè)結(jié)果合理分配時(shí)隙并且通過(guò)分配系數(shù)的引入動(dòng)態(tài)調(diào)整了可分配的動(dòng)態(tài)時(shí)隙數(shù)量。使得網(wǎng)絡(luò)平均時(shí)延相對(duì)較低。

圖13 網(wǎng)絡(luò)時(shí)延對(duì)比圖

數(shù)據(jù)發(fā)送速率在100～1 000 kbps時(shí)3種協(xié)議的網(wǎng)絡(luò)吞吐量變化情況如圖14所示。隨著數(shù)據(jù)發(fā)送速率的提升，所有協(xié)議的吞吐量均增大。STDMA協(xié)議的吞吐量小于數(shù)據(jù)發(fā)送速率，而定向MAC協(xié)議的吞吐量遠(yuǎn)大于數(shù)據(jù)發(fā)送速率。這是由于定向天線使得信道同時(shí)可以發(fā)送多條鏈路的數(shù)據(jù)，空間復(fù)用率增加，網(wǎng)絡(luò)吞吐量不斷提升。而相比于P-TDMA協(xié)議，本文設(shè)計(jì)的M-TDMA協(xié)議在數(shù)據(jù)發(fā)送速率達(dá)到1 000 kbps時(shí)，網(wǎng)絡(luò)吞吐量可以達(dá)到4 Mbps以上。這是因?yàn)樵诰W(wǎng)絡(luò)負(fù)載增大時(shí)，節(jié)點(diǎn)通過(guò)流量預(yù)測(cè)算法動(dòng)態(tài)調(diào)整不同節(jié)點(diǎn)分配的時(shí)隙數(shù)量，預(yù)測(cè)網(wǎng)絡(luò)流量大的節(jié)點(diǎn)優(yōu)先分配更多的時(shí)隙資源，吞吐量得以繼續(xù)提升。而STDMA與P-TDMA協(xié)議在發(fā)送速率達(dá)到700 kbps后由于沒(méi)有有效的資源動(dòng)態(tài)調(diào)整策略，吞吐量不再提升，達(dá)到滿負(fù)載狀態(tài)。

圖14 網(wǎng)絡(luò)吞吐量對(duì)比圖

圖15對(duì)比了當(dāng)數(shù)據(jù)發(fā)送速率提升時(shí)3種協(xié)議的丟包率變化情況。當(dāng)數(shù)據(jù)發(fā)送速率增大時(shí)，3種協(xié)議的丟包率也不斷增大，這是因?yàn)殡S著數(shù)據(jù)發(fā)送速率的增大網(wǎng)絡(luò)負(fù)載變大，數(shù)據(jù)緩存區(qū)的等待數(shù)據(jù)增多，丟包率也隨之增大。在100～300 kbps的發(fā)送速率時(shí)，3種協(xié)議丟包率控制在5%以內(nèi)。當(dāng)發(fā)送速率達(dá)到700 kbps時(shí)，P-TDMA協(xié)議由于沒(méi)有分配系數(shù)均衡靜態(tài)與動(dòng)態(tài)時(shí)隙，導(dǎo)致可用時(shí)隙減少丟包率增大。而STDMA協(xié)議是全向天線MAC協(xié)議，過(guò)大的負(fù)載使得節(jié)點(diǎn)可用時(shí)隙減少，由于過(guò)長(zhǎng)的排隊(duì)時(shí)間，導(dǎo)致數(shù)據(jù)大量丟失丟包率增大。而M-TDMA算法由于分配系數(shù)存在，可用時(shí)隙減少時(shí)靜態(tài)時(shí)隙會(huì)轉(zhuǎn)化為動(dòng)態(tài)時(shí)隙，可用時(shí)隙充足。且該算法根據(jù)預(yù)測(cè)各節(jié)點(diǎn)業(yè)務(wù)量大小，動(dòng)態(tài)調(diào)整各節(jié)點(diǎn)分配的時(shí)隙數(shù)，排隊(duì)時(shí)間縮短，數(shù)據(jù)丟包率降低，在1 000 kbps的速率時(shí)丟包率仍控制在20%以內(nèi)，算法性能最好。

圖15 網(wǎng)絡(luò)丟包率對(duì)比圖

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

近些年來(lái)隨著無(wú)線自組網(wǎng)研究與應(yīng)用的不斷深入，MAC協(xié)議作為自組網(wǎng)關(guān)鍵的組成部分具有很重要的研究意義。本文在研究過(guò)程中針對(duì)高空中拓?fù)涓邉?dòng)態(tài)變化的分布式定向自組網(wǎng)的特點(diǎn)，提出了一種基于TDMA的定向分布式資源調(diào)度算法M-TDMA，通過(guò)引入分配系數(shù)，有效均衡了動(dòng)態(tài)與靜態(tài)分配的效果；并通過(guò)流量預(yù)測(cè)算法對(duì)時(shí)隙進(jìn)行合理的分配，有效改善了網(wǎng)絡(luò)擁堵現(xiàn)象。仿真對(duì)比表明M-TDMA算法很好的應(yīng)用于多節(jié)點(diǎn)高動(dòng)態(tài)場(chǎng)景，有效減少了網(wǎng)絡(luò)平均時(shí)延，并提升了網(wǎng)絡(luò)吞吐量，提升了網(wǎng)絡(luò)效率。