含網(wǎng)關(guān)節(jié)點(diǎn)的高時(shí)隙復(fù)用率TDMA協(xié)議

韋 亮，任 智，陳 凱，張關(guān)鑫

(重慶郵電大學(xué) 通信與信息工程學(xué)院，重慶 400065)

0 引 言

較于移動(dòng)自組網(wǎng)，無(wú)人機(jī)自組網(wǎng)[1-7]的研究起步較晚。早期MAC層采用ALOHA協(xié)議，隨后被載波偵聽(tīng)多路訪問(wèn)/沖突避免協(xié)議(carrier sense multiple access with collision avoid，CSMA/CA)取代，文獻(xiàn)[8]對(duì)CSMA/CA協(xié)議的結(jié)構(gòu)做了部分調(diào)整，但調(diào)整后仍不能滿足無(wú)人機(jī)自組網(wǎng)的需求。文獻(xiàn)[9]保證控制信息的及時(shí)交付，但其沒(méi)考慮新節(jié)點(diǎn)的入網(wǎng)，靈活性較差。文獻(xiàn)[10]采用定向天線，把每個(gè)節(jié)點(diǎn)的一跳鄰域劃分為完全連接的一跳鄰域，在一定的程度下提高了時(shí)隙復(fù)用率，但該協(xié)議的幀結(jié)構(gòu)較為復(fù)雜，且控制開(kāi)銷較大，并不適合無(wú)人機(jī)自組網(wǎng)。文獻(xiàn)[11]中每個(gè)節(jié)點(diǎn)僅需要自己鄰居節(jié)點(diǎn)的節(jié)點(diǎn)信息，不需要整個(gè)網(wǎng)絡(luò)的拓?fù)浜土髁啃畔?，因此降低了控制開(kāi)銷，但是由于無(wú)人機(jī)的移動(dòng)性，使得天線難以實(shí)時(shí)校準(zhǔn)。文獻(xiàn)[12]提出一種基于閑置時(shí)隙預(yù)約傳輸機(jī)制的ISR-TDMA協(xié)議，但并未充分考慮業(yè)務(wù)優(yōu)先級(jí)且靈活性不高。文獻(xiàn)[13]動(dòng)態(tài)地切換CSMA和TDMA狀態(tài)，但僅適用于星型網(wǎng)絡(luò)，仍不能較好滿足無(wú)人機(jī)多跳網(wǎng)絡(luò)的需求。文獻(xiàn)[14]提出了一種雙向管道TDMA協(xié)議，能夠較好保障無(wú)人機(jī)節(jié)點(diǎn)在多跳網(wǎng)絡(luò)場(chǎng)景中數(shù)據(jù)傳輸?shù)目煽啃?，但也產(chǎn)生了一定的控制開(kāi)銷、部分信道資源的浪費(fèi)和數(shù)據(jù)時(shí)隙沖突問(wèn)題。文獻(xiàn)[15]減少了現(xiàn)有協(xié)議的部分控制開(kāi)銷，改進(jìn)了現(xiàn)有的TDMA協(xié)議在節(jié)點(diǎn)高速移動(dòng)的情況下未及時(shí)更新時(shí)隙請(qǐng)求參數(shù)的問(wèn)題，但也增加了節(jié)點(diǎn)時(shí)隙沖突的可能性。

為解決現(xiàn)有文獻(xiàn)存在的問(wèn)題，在文獻(xiàn)[14，15]的基礎(chǔ)上，提出了FU-TDMA協(xié)議。本文的貢獻(xiàn)如下：①提出時(shí)隙請(qǐng)求時(shí)期快速收斂機(jī)制，對(duì)現(xiàn)有相關(guān)TDMA協(xié)議中的控制時(shí)期網(wǎng)絡(luò)收斂慢問(wèn)題進(jìn)行改進(jìn)；②空閑時(shí)隙公平重用機(jī)制，解決了現(xiàn)有相關(guān)TDMA協(xié)議中的中心節(jié)點(diǎn)時(shí)隙分配沖突的問(wèn)題，提高了時(shí)隙的復(fù)用率；③一跳鄰居多層次調(diào)度機(jī)制，保障了節(jié)點(diǎn)的公平性，降低了節(jié)點(diǎn)調(diào)度的時(shí)延性，增強(qiáng)了網(wǎng)絡(luò)的可靠性。

1 網(wǎng)絡(luò)模型、幀結(jié)構(gòu)及問(wèn)題描述

1.1 網(wǎng)絡(luò)模型

網(wǎng)絡(luò)拓?fù)淙鐖D1所示。由一個(gè)中心節(jié)點(diǎn)(central node，CN)、部分普通節(jié)點(diǎn)、個(gè)別網(wǎng)關(guān)節(jié)點(diǎn)(gateway node，GN)和一個(gè)地面站(ground station，GS)構(gòu)成。CN負(fù)責(zé)在時(shí)隙分配時(shí)期廣播全網(wǎng)時(shí)隙表；GN負(fù)責(zé)傳遞GS的指控信息給網(wǎng)絡(luò)其余節(jié)點(diǎn)和把其余節(jié)點(diǎn)采集的數(shù)據(jù)信息發(fā)送給GS；普通節(jié)點(diǎn)負(fù)責(zé)數(shù)據(jù)的采集及其余信息的中繼；GS負(fù)責(zé)控制空中無(wú)人機(jī)集群執(zhí)行任務(wù)。

圖1 網(wǎng)絡(luò)拓?fù)?/p>

1.2 幀結(jié)構(gòu)

協(xié)議的幀結(jié)構(gòu)如圖2所示。該幀結(jié)構(gòu)由CMOP時(shí)期(CP)、Data時(shí)期(DP)和SMOP時(shí)期(SP)組成且各個(gè)時(shí)期長(zhǎng)度受CN控制。在每個(gè)幀開(kāi)始，CN在CP的第一個(gè)時(shí)隙廣播新的時(shí)隙分配表，收到這個(gè)CMOP幀的節(jié)點(diǎn)更新自己在當(dāng)前幀內(nèi)新分配的時(shí)隙信息及梯度值(CN的梯度值為0，距離CN跳數(shù)為n跳的節(jié)點(diǎn)梯度值為n)，然后在自己的CP時(shí)隙廣播CMOP幀。在DP期間，節(jié)點(diǎn)根據(jù)在當(dāng)前幀內(nèi)的CP接收的時(shí)隙分配表，在自己的時(shí)隙傳輸上行監(jiān)視、偵察數(shù)據(jù)和下行命令數(shù)據(jù)。在SP期間，節(jié)點(diǎn)發(fā)出SMOP幀，在自己的SP時(shí)隙傳遞自己的時(shí)隙請(qǐng)求和中繼子節(jié)點(diǎn)的時(shí)隙請(qǐng)求；對(duì)于多個(gè)父節(jié)點(diǎn)存在的情況時(shí)，子節(jié)點(diǎn)依據(jù)上一幀收到的父節(jié)點(diǎn)的時(shí)隙請(qǐng)求消息，按照負(fù)載均衡的思想，選擇目的父節(jié)點(diǎn)。在SP的競(jìng)爭(zhēng)時(shí)期，用于處理新節(jié)點(diǎn)的入網(wǎng)請(qǐng)求及失敗節(jié)點(diǎn)的重傳。在CP期間，節(jié)點(diǎn)梯度值越大，時(shí)隙越靠前；在SP期間，反之。CMOP幀格式及SMOP幀格式如圖3所示。

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

圖3 幀格式

1.3 問(wèn)題描述

(1)中心節(jié)點(diǎn)在全網(wǎng)廣播CMOP幀之前(即在SP時(shí)期)，其余節(jié)點(diǎn)會(huì)向中心節(jié)點(diǎn)發(fā)送SMOP幀用于申請(qǐng)時(shí)隙，其中申請(qǐng)的時(shí)隙信息包括節(jié)點(diǎn)自身和子節(jié)點(diǎn)的時(shí)隙請(qǐng)求。在此過(guò)程中，若網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)為N，SP時(shí)隙長(zhǎng)度為L(zhǎng)，因?yàn)樵诿總€(gè)SP時(shí)隙，僅有一個(gè)節(jié)點(diǎn)占用該時(shí)隙并發(fā)送SMOP幀，那么SP時(shí)期則需要(N-1)*L個(gè)SP時(shí)隙。如圖1所示，當(dāng)節(jié)點(diǎn)信息傳輸滿足一定范圍互不影響時(shí)，帶有粗線的節(jié)點(diǎn)9、節(jié)點(diǎn)11及節(jié)點(diǎn)13和帶有粗線的節(jié)點(diǎn)4及網(wǎng)關(guān)節(jié)點(diǎn)就可以在兩個(gè)SP時(shí)隙分別調(diào)度，因?yàn)樵诠?jié)點(diǎn)9、節(jié)點(diǎn)11及節(jié)點(diǎn)13同時(shí)發(fā)送SMOP幀時(shí)，不會(huì)產(chǎn)生沖突，不會(huì)造成節(jié)點(diǎn)重新發(fā)送時(shí)隙請(qǐng)求信息。此時(shí)原本需要5個(gè)SP時(shí)隙而現(xiàn)在僅需2個(gè)SP時(shí)隙就能把節(jié)點(diǎn)時(shí)隙請(qǐng)求傳遞成功，極大地節(jié)約了信道資源。在現(xiàn)有協(xié)議的標(biāo)準(zhǔn)中，由于在一個(gè)SP時(shí)隙僅由一個(gè)節(jié)點(diǎn)占用，浪費(fèi)了大量的時(shí)隙資源，造成了網(wǎng)絡(luò)在SP階段收斂較慢。

(2)節(jié)點(diǎn)在發(fā)送SMOP幀時(shí)，采用單跳廣播方式。節(jié)點(diǎn)梯度值小于SMOP幀字段Hop Count時(shí)，節(jié)點(diǎn)會(huì)聚合大于自身梯度值且與其為一跳鄰居的節(jié)點(diǎn)發(fā)送的時(shí)隙請(qǐng)求消息，當(dāng)部分節(jié)點(diǎn)存在多個(gè)小于其梯度值的一跳鄰居時(shí)，節(jié)點(diǎn)廣播SMOP幀，多個(gè)小于其梯度值的鄰居節(jié)點(diǎn)都會(huì)中繼其時(shí)隙請(qǐng)求。如圖1所示，節(jié)點(diǎn)10廣播時(shí)隙請(qǐng)求，節(jié)點(diǎn)5、節(jié)點(diǎn)6收到時(shí)隙請(qǐng)求信息并中繼時(shí)隙請(qǐng)求信息。雖然現(xiàn)有的研究通過(guò)增加一個(gè)中繼字段，采用負(fù)載均衡的方式，有效地解決了這個(gè)問(wèn)題，但也增加了節(jié)點(diǎn)時(shí)隙沖突的可能性。在中心節(jié)點(diǎn)調(diào)度節(jié)點(diǎn)的時(shí)隙分配時(shí)，由于形成的拓?fù)浯嬖谂紶柌煌暾那闆r，致使在拓?fù)鋱D內(nèi)三跳及以上跳數(shù)的節(jié)點(diǎn)在同一時(shí)隙發(fā)包時(shí)會(huì)產(chǎn)生沖突。如圖1所示，節(jié)點(diǎn)2收到了節(jié)點(diǎn)5、節(jié)點(diǎn)6廣播的時(shí)隙請(qǐng)求信息，因?yàn)楣?jié)點(diǎn)5和節(jié)點(diǎn)6廣播的時(shí)隙請(qǐng)求信息里都包括了節(jié)點(diǎn)10的時(shí)隙請(qǐng)求，然而節(jié)點(diǎn)2僅會(huì)留下節(jié)點(diǎn)10的一個(gè)時(shí)隙請(qǐng)求，在中心節(jié)點(diǎn)收到全網(wǎng)節(jié)點(diǎn)的時(shí)隙請(qǐng)求時(shí)，可能會(huì)誤判節(jié)點(diǎn)10與節(jié)點(diǎn)5為一跳鄰居而與節(jié)點(diǎn)6為3跳鄰居或節(jié)點(diǎn)10是與節(jié)點(diǎn)6為一跳鄰居而與節(jié)點(diǎn)5為3跳鄰居，導(dǎo)致分配同一個(gè)時(shí)隙給節(jié)點(diǎn)10和節(jié)點(diǎn)5或節(jié)點(diǎn)10和節(jié)點(diǎn)6，發(fā)生時(shí)隙分配沖突。

(3)在競(jìng)爭(zhēng)時(shí)期，節(jié)點(diǎn)調(diào)度形式過(guò)于單一化，時(shí)隙爭(zhēng)用僅按照梯度值作為信道的訪問(wèn)優(yōu)先級(jí)，極大可能存在部分同梯度節(jié)點(diǎn)同時(shí)發(fā)送SMOP幀，致使沖突，延長(zhǎng)節(jié)點(diǎn)SMOP幀的重傳時(shí)間，嚴(yán)重時(shí)可導(dǎo)致當(dāng)前競(jìng)爭(zhēng)時(shí)隙損壞，使得節(jié)點(diǎn)在下一幀無(wú)時(shí)隙分配。

2 FU-TDMA

針對(duì)上述問(wèn)題，提出了FU-TDMA協(xié)議。該協(xié)議包含3個(gè)新機(jī)制：①時(shí)隙請(qǐng)求時(shí)期快速收斂機(jī)制，中心節(jié)點(diǎn)并行調(diào)度節(jié)點(diǎn)上傳時(shí)隙請(qǐng)求，減少網(wǎng)絡(luò)收斂時(shí)間；②空閑時(shí)隙公平重用機(jī)制，消除因中心節(jié)點(diǎn)維護(hù)的拓?fù)浔聿煌暾麜r(shí)所造成的沖突問(wèn)題，挖掘出所有空閑時(shí)隙，提高信道利用率；③一跳鄰居多層次調(diào)度機(jī)制，節(jié)點(diǎn)計(jì)算所有一跳鄰居的優(yōu)先級(jí)，使較高優(yōu)先級(jí)節(jié)點(diǎn)先重傳，降低碰撞概率。

2.1 時(shí)隙請(qǐng)求時(shí)期快速收斂機(jī)制

針對(duì)1.3節(jié)問(wèn)題描述(1)，本文提出時(shí)隙請(qǐng)求時(shí)期快速收斂機(jī)制。該機(jī)制的核心思想是：在SP階段，考慮各節(jié)點(diǎn)控制時(shí)隙調(diào)度順序。中心節(jié)點(diǎn)建立并維護(hù)全網(wǎng)拓?fù)浜?，制訂一個(gè)用于觸發(fā)部分節(jié)點(diǎn)并行調(diào)度的閾值，用于通知節(jié)點(diǎn)傳遞位置信息，然后再根據(jù)中心節(jié)點(diǎn)維護(hù)的包含位置信息的拓?fù)洌捎没诰嚯x的并行調(diào)度算法，快速地調(diào)度各節(jié)點(diǎn)控制時(shí)隙，以較短的時(shí)間獲取全網(wǎng)拓?fù)浼皶r(shí)隙請(qǐng)求信息。

2.1.1 基于距離的并行調(diào)度算法

基于距離的并行調(diào)度算法具體流程如下：

步驟1 從拓?fù)鋱D中選出葉子節(jié)點(diǎn)及相連的父節(jié)點(diǎn)構(gòu)建二部圖G(v，e)，記梯度值為奇數(shù)的節(jié)點(diǎn)集為V奇，梯度值為偶數(shù)的節(jié)點(diǎn)集為V偶，其中X∈V奇，Y∈V偶。

步驟2 根據(jù)形成的二部圖，每個(gè)葉子節(jié)點(diǎn)計(jì)算與其余不相連的父節(jié)點(diǎn)的距離da→b，表示為

(1)

(2)

(3)

步驟4 在拓?fù)鋱D中剔除篩選邊的葉子節(jié)點(diǎn)，更新拓?fù)鋱D。

步驟5 若在拓?fù)鋱D中只剩下CN，則結(jié)束；否則，轉(zhuǎn)步驟1。

2.1.2 時(shí)隙請(qǐng)求時(shí)期快速收斂機(jī)制具體流程

時(shí)隙請(qǐng)求時(shí)期快速收斂機(jī)制具體流程如下：

步驟1 在SP期間，由梯度值最大的節(jié)點(diǎn)發(fā)起時(shí)隙請(qǐng)求，該節(jié)點(diǎn)創(chuàng)建自己的所需時(shí)隙請(qǐng)求的聚合信息，廣播SMOP幀。上層父節(jié)點(diǎn)收到子節(jié)點(diǎn)的SMOP幀后，更新自己的一跳鄰居表，查看收到的SMOP幀里的ECG字段信息，將子節(jié)點(diǎn)發(fā)送的SMOP幀里的ECG字段的信息聚合在本節(jié)點(diǎn)待發(fā)送的SMOP幀里的ECG字段里，然后廣播SMOP幀。

步驟2 CN收到所有下層普通節(jié)點(diǎn)發(fā)出的SMOP幀后，查看各普通節(jié)點(diǎn)的時(shí)隙申請(qǐng)信息并匯總創(chuàng)建維護(hù)全網(wǎng)節(jié)點(diǎn)拓?fù)鋱D。根據(jù)其拓?fù)鋱D的復(fù)雜程度及其規(guī)模來(lái)確定是否在當(dāng)前幀內(nèi)節(jié)點(diǎn)上傳地理位置信息。若全網(wǎng)拓?fù)鋱D還沒(méi)到達(dá)閾值，繼續(xù)執(zhí)行步驟3，否則轉(zhuǎn)步驟4。

步驟3 若不需要節(jié)點(diǎn)上傳地理位置信息，在下一幀的CP，CN廣播一個(gè)更新后的時(shí)隙分配圖且在CMOP幀中的時(shí)隙分配字段按照節(jié)點(diǎn)梯度值順序排列。普通節(jié)點(diǎn)收到CN發(fā)出的CMOP幀后，首先更新自己的一跳鄰居信息表，然后查看自己申請(qǐng)的時(shí)隙位并在自己的CP時(shí)隙廣播CMOP幀。轉(zhuǎn)步驟1。

步驟4 若需要節(jié)點(diǎn)上傳地理位置信息，在下一幀的CP，CN發(fā)放全網(wǎng)節(jié)點(diǎn)時(shí)隙分配圖。其時(shí)隙分配圖按照節(jié)點(diǎn)梯度值逆序排列，表明在當(dāng)前幀的SP，如果各普通節(jié)點(diǎn)廣播SMOP幀，不僅需要在ECG字段聚合子節(jié)點(diǎn)和自己的時(shí)隙請(qǐng)求信息還需要聚合當(dāng)前所在的位置信息。然后節(jié)點(diǎn)在自己的CP時(shí)隙廣播CMOP幀，轉(zhuǎn)步驟5。

步驟5 各普通節(jié)點(diǎn)收到其由CN廣播的CMOP幀，在當(dāng)前SP，由梯度值最大的節(jié)點(diǎn)開(kāi)始調(diào)度，向網(wǎng)絡(luò)廣播包含時(shí)隙請(qǐng)求和地理位置的SMOP幀。父節(jié)點(diǎn)收到子節(jié)點(diǎn)發(fā)送的SMOP幀，匯總自己的時(shí)隙請(qǐng)求、地理位置和子節(jié)點(diǎn)的時(shí)隙請(qǐng)求、地理位置，在自己的SP時(shí)隙廣播聚合的SMOP幀。

步驟6 所有節(jié)點(diǎn)在SP期間上傳地理位置，CN收到所有子節(jié)點(diǎn)發(fā)的SMOP幀。在形成新的全網(wǎng)拓?fù)鋱D的基礎(chǔ)上，CN根據(jù)各節(jié)點(diǎn)的位置信息，采用并行調(diào)度算法，在下一幀的SP，并行調(diào)度部分節(jié)點(diǎn)的時(shí)隙請(qǐng)求。

步驟7 CN按照所維護(hù)的全網(wǎng)拓?fù)鋱D，在節(jié)點(diǎn)不沖突的情況下，計(jì)算普通節(jié)點(diǎn)SP時(shí)隙的分配。在下一個(gè)CP期間，CN廣播CMOP幀，若其中時(shí)隙分配字段里節(jié)點(diǎn)時(shí)隙分配按照調(diào)度順序順序排列，則表明在當(dāng)前SP，普通節(jié)點(diǎn)聚合的信息字段里，仍然需要包含節(jié)點(diǎn)當(dāng)前所在的地理位置信息；如果時(shí)隙分配字段里的節(jié)點(diǎn)時(shí)隙分配按照調(diào)度順序逆序排列，則表明在當(dāng)前SP，普通節(jié)點(diǎn)不需要再上傳自己當(dāng)前所在地理位置信息。在時(shí)隙分配圖中，節(jié)點(diǎn)ID、上行時(shí)隙和下行時(shí)隙順序排列表示節(jié)點(diǎn)占一個(gè)調(diào)度時(shí)隙；節(jié)點(diǎn)ID、下行時(shí)隙和上行時(shí)隙逆序排列表示此節(jié)點(diǎn)同上一個(gè)節(jié)點(diǎn)一起調(diào)度。

步驟8 普通節(jié)點(diǎn)收到了CN廣播的CMOP幀，記錄自己的時(shí)隙信息，發(fā)現(xiàn)時(shí)隙分配圖按照調(diào)度順序順序排列，繼續(xù)在即將到來(lái)的SP聚合自己的位置信息；若發(fā)現(xiàn)時(shí)隙分配圖按照調(diào)度順序逆序排列，則在SP不聚合節(jié)點(diǎn)所在位置信息，并在自己的CP時(shí)隙廣播CMOP幀。

步驟9 普通節(jié)點(diǎn)根據(jù)在CP時(shí)隙收到的CMOP幀里的時(shí)隙分配圖的順序，在SP時(shí)隙開(kāi)始其節(jié)點(diǎn)的調(diào)度。并行調(diào)度的節(jié)點(diǎn)創(chuàng)建自己的時(shí)隙請(qǐng)求聚合信息，至SP結(jié)束。轉(zhuǎn)步驟2。

基于上述方案設(shè)計(jì)的時(shí)隙請(qǐng)求時(shí)期快速收斂流程如圖4所示。

圖4 時(shí)隙請(qǐng)求時(shí)期快速收斂流程

2.2 空閑時(shí)隙公平重用機(jī)制

針對(duì)1.3節(jié)問(wèn)題描述(2)，為了充分地使用信道和消除中心節(jié)點(diǎn)分配時(shí)隙時(shí)導(dǎo)致的沖突問(wèn)題，本文提出空閑時(shí)隙公平重用機(jī)制。該機(jī)制的核心思想是：CN根據(jù)分配給各個(gè)節(jié)點(diǎn)的時(shí)隙，詳細(xì)地挖掘出每個(gè)節(jié)點(diǎn)的空閑時(shí)隙。針對(duì)空閑時(shí)隙，CN消除其中會(huì)致使沖突的時(shí)隙，進(jìn)行公平的時(shí)隙分配。

空閑時(shí)隙公平重用機(jī)制具體步驟如下：

步驟1 普通節(jié)點(diǎn)在SP上傳時(shí)隙請(qǐng)求信息且攜帶位置信息，SP結(jié)束，中心節(jié)點(diǎn)查看各節(jié)點(diǎn)的時(shí)隙請(qǐng)求。

步驟2 CN依據(jù)各節(jié)點(diǎn)時(shí)隙請(qǐng)求分配時(shí)隙。

步驟3 針對(duì)已分配的時(shí)隙，CN記錄給每個(gè)節(jié)點(diǎn)分配的時(shí)隙ASk。

步驟4 對(duì)各個(gè)節(jié)點(diǎn)，計(jì)算各節(jié)點(diǎn)未使用的時(shí)隙NASk，則NASk表示為

NASk=Ttotal-ASk

(4)

Ttotal為數(shù)據(jù)時(shí)期的總時(shí)隙數(shù)。

步驟5 根據(jù)節(jié)點(diǎn)傳遞的位置信息，計(jì)算dk->i≤2R，找出該節(jié)點(diǎn)所有兩跳內(nèi)的節(jié)點(diǎn)，并求出節(jié)點(diǎn)可采用時(shí)隙PUSk。dk->i≤2R、PUSk表示如下

(5)

(6)

圖5 兩跳內(nèi)鄰居數(shù)計(jì)算

(7)

步驟7 對(duì)于兩跳內(nèi)節(jié)點(diǎn)共有的部分時(shí)隙，CN按照每個(gè)節(jié)點(diǎn)申請(qǐng)時(shí)隙權(quán)重的比值進(jìn)行公平的分配，故所有時(shí)隙已完全分配。

基于上述方案設(shè)計(jì)的空閑時(shí)隙公平重用算法流程如圖6所示。

圖6 空閑時(shí)隙公平重用算法流程

2.3 一跳鄰居多層次調(diào)度機(jī)制

針對(duì)1.3節(jié)問(wèn)題描述(3)，本文提出一跳鄰居多層次調(diào)度機(jī)制。該機(jī)制的核心思想是：相鄰的一跳鄰居節(jié)點(diǎn)分別計(jì)算各自鄰居的優(yōu)先級(jí)，依據(jù)優(yōu)先級(jí)的多樣性，使優(yōu)先級(jí)高的節(jié)點(diǎn)優(yōu)先使用時(shí)隙，增強(qiáng)了網(wǎng)絡(luò)可靠性。

考慮節(jié)點(diǎn)在競(jìng)爭(zhēng)時(shí)期調(diào)度單一的問(wèn)題，加入鄰居節(jié)點(diǎn)請(qǐng)求時(shí)隙數(shù)量、子節(jié)點(diǎn)數(shù)量、平均時(shí)隙請(qǐng)求數(shù)量及子節(jié)點(diǎn)變化率(sub-node change rate，SCR)，多層次調(diào)度節(jié)點(diǎn)爭(zhēng)用順序，保證各節(jié)點(diǎn)公平性。一跳鄰居多層次調(diào)度機(jī)制具體步驟如下：

(8)

其中，Nrn為節(jié)點(diǎn)n的一跳鄰居集、Subk為節(jié)點(diǎn)k的子節(jié)點(diǎn)集。在競(jìng)爭(zhēng)階段，對(duì)于鄰居節(jié)點(diǎn)時(shí)隙請(qǐng)求數(shù)量、鄰居攜帶子節(jié)點(diǎn)數(shù)量及平均時(shí)隙數(shù)量較大的鄰居節(jié)點(diǎn)優(yōu)先級(jí)更高，這些節(jié)點(diǎn)可以獲得較低的端到端時(shí)延，從而降低整個(gè)網(wǎng)絡(luò)的時(shí)延。

(9)

子節(jié)點(diǎn)變化率反映了鄰居節(jié)點(diǎn)部分的拓?fù)渥兓癄顩r，變化率越大，說(shuō)明拓?fù)浞€(wěn)定性較差，對(duì)于變化率較小的優(yōu)先級(jí)越高，可以減少節(jié)點(diǎn)因?yàn)椴环€(wěn)定因素導(dǎo)致的數(shù)據(jù)丟失，提升網(wǎng)絡(luò)穩(wěn)定性。

步驟3 在競(jìng)爭(zhēng)階段，一跳鄰居節(jié)點(diǎn)內(nèi)優(yōu)先級(jí)表示為

(10)

步驟4 在一跳鄰域內(nèi)，節(jié)點(diǎn)按照梯度值和Pk的大小及優(yōu)先級(jí)大小對(duì)時(shí)隙爭(zhēng)用，梯度值越大節(jié)點(diǎn)優(yōu)先爭(zhēng)用，同梯度值節(jié)點(diǎn)，Pk越大的節(jié)點(diǎn)在競(jìng)爭(zhēng)階段優(yōu)先爭(zhēng)用。

基于上述方案設(shè)計(jì)的一跳鄰居多層次調(diào)度算法流程如圖7所示。

圖7 一跳鄰居多層次調(diào)度算法流程

3 仿真驗(yàn)證

本文使用OPNET14.5通信網(wǎng)絡(luò)仿真軟件，對(duì)比CSMA協(xié)議、BiPi-TMAC協(xié)議、ERMH-TDMA協(xié)議以及FU-TDMA協(xié)議的性能，分析仿真結(jié)果。

3.1 仿真流程

(1)設(shè)置MAC層進(jìn)程模型及應(yīng)用層模型。其中MAC層進(jìn)程模型包括INIT、CMOP、Data及SMOP狀態(tài)機(jī)，用于完成初始化和時(shí)幀的控制信息及業(yè)務(wù)信息傳輸；應(yīng)用層模型包括Sink和Source模塊，用于數(shù)據(jù)包的發(fā)送與接收。

(2)設(shè)置節(jié)點(diǎn)模型。物理層采用全向天線，網(wǎng)絡(luò)層采用OLSR協(xié)議，傳輸層采用透?jìng)髂K。

(3)設(shè)置網(wǎng)絡(luò)模型。4種協(xié)議采用一樣的場(chǎng)景，中心節(jié)點(diǎn)處于網(wǎng)絡(luò)中心，其余普通節(jié)點(diǎn)圍繞中心節(jié)點(diǎn)層層擺放，地面站與網(wǎng)絡(luò)邊界的網(wǎng)關(guān)節(jié)點(diǎn)通信。

(4)收集所需的統(tǒng)計(jì)量。

(5)仿真結(jié)果分析。對(duì)收集的統(tǒng)計(jì)量進(jìn)一步分析，得出吞吐量、數(shù)據(jù)傳輸時(shí)延及時(shí)隙利用率。

3.2 仿真參數(shù)設(shè)置

仿真參數(shù)設(shè)置見(jiàn)表1。

表1 主要的仿真參數(shù)設(shè)置

3.3 仿真結(jié)果分析

本文通過(guò)以下性能指標(biāo)來(lái)驗(yàn)證網(wǎng)絡(luò)性能：

(1)SP時(shí)期網(wǎng)絡(luò)收斂時(shí)間：全網(wǎng)節(jié)點(diǎn)在上傳SMOP幀至中心節(jié)點(diǎn)所需的總時(shí)間。

(2)數(shù)據(jù)傳輸平均時(shí)延：數(shù)據(jù)包從源傳輸?shù)侥康牡氐钠骄鶗r(shí)間。

(3)數(shù)據(jù)傳輸成功率：目的地收到的數(shù)據(jù)包與源產(chǎn)生的數(shù)據(jù)包之間的平均比值。

3.3.1 SP時(shí)期節(jié)點(diǎn)收斂時(shí)間

圖8為不同網(wǎng)絡(luò)規(guī)模下FU-TDMA、ERMH-TDMA、BiPi-TMAC和CSMA協(xié)議的SP時(shí)期網(wǎng)絡(luò)收斂時(shí)間對(duì)比。由圖可知，隨著節(jié)點(diǎn)個(gè)數(shù)增加，SP時(shí)期收斂時(shí)間逐漸增大，這是因?yàn)楦嗟墓?jié)點(diǎn)上傳時(shí)隙請(qǐng)求。仿真結(jié)果表明，在節(jié)點(diǎn)數(shù)低于7時(shí)CSMA在SP時(shí)期是最快收斂的，但是隨著節(jié)點(diǎn)數(shù)的增多，導(dǎo)致SMOP幀的數(shù)量增多，從而導(dǎo)致無(wú)線信道中碰撞概率增大，因此在節(jié)點(diǎn)數(shù)8及其以后網(wǎng)絡(luò)的收斂時(shí)間是偏高于另3種協(xié)議。ERMH-TDMA與BiPi-TMAC收斂時(shí)間一致，其原因?yàn)椋涸赟P時(shí)期中心節(jié)點(diǎn)會(huì)給各節(jié)點(diǎn)分配一個(gè)不同的SMOP時(shí)隙(分配的總時(shí)隙數(shù)為節(jié)點(diǎn)數(shù)減一)。在節(jié)點(diǎn)數(shù)為30時(shí)，F(xiàn)U-TDMA相比于ERMH-TDMA和BiPi-TMAC下降了17.2%，其原因?yàn)椋篎U-TDMA的時(shí)期請(qǐng)求時(shí)期快速收斂機(jī)制采用基于距離的并行調(diào)度算法相比于ERMH-TDMA和BiPi-TMAC的每個(gè)節(jié)點(diǎn)分配一個(gè)不同的SMOP時(shí)隙的方式，F(xiàn)U-TDMA在一個(gè)SMOP時(shí)隙并行調(diào)度節(jié)點(diǎn)上傳時(shí)隙請(qǐng)求信息，因此收斂更快。注意在節(jié)點(diǎn)數(shù)25時(shí)，F(xiàn)U-TDMA相比于ERMH-TDMA 和BiPi-TMAC降低了20.8%，比節(jié)點(diǎn)數(shù)30時(shí)更小，這是因?yàn)榛诰嚯x的并行調(diào)度算法計(jì)算的結(jié)果不一定是全局最優(yōu)的，但整體而言FU-TDMA的收斂時(shí)間低于ERMH-TDMA和BiPi-TMAC。

圖8 SP時(shí)期網(wǎng)絡(luò)收斂時(shí)間

3.3.2 數(shù)據(jù)傳輸平均時(shí)延

圖9為節(jié)點(diǎn)數(shù)20時(shí)，3種協(xié)議的數(shù)據(jù)傳輸平均時(shí)延對(duì)比。由圖可知，隨著節(jié)點(diǎn)速率的增加，端到端時(shí)延逐漸增大，這是因?yàn)楣?jié)點(diǎn)移動(dòng)過(guò)快，導(dǎo)致鏈路穩(wěn)定性下降，從而導(dǎo)致部分幀重傳。上行端到端時(shí)延與下行端到端時(shí)延有顯著差距是因?yàn)樯闲袃?yōu)先級(jí)高于下行，可能會(huì)導(dǎo)致部分節(jié)點(diǎn)上行數(shù)據(jù)隊(duì)列更長(zhǎng)。況且時(shí)隙請(qǐng)求大小與隊(duì)列長(zhǎng)度成正比，這使得節(jié)點(diǎn)為上行業(yè)務(wù)存儲(chǔ)更長(zhǎng)的時(shí)間，從而增大了下行業(yè)務(wù)的傳輸時(shí)延。仿真結(jié)果表明，在上行端到端平均時(shí)延中，BiPi-TMAC較CSMA下降了32.2%～36.1%，ERMH-TDMA較BiPi-TMAC下降了3.2%～4.7%，F(xiàn)U-TDMA較ERMH-TDMA下降了5.5%～8.9%；在下行端到端時(shí)延中，BiPi-TMAC較CSMA下降了47.1%～50.8%，ERMH-TDMA較BiPi-TMAC下降了2.6%～7.7%，F(xiàn)U-TDMA較ERMH-TDMA下降了4.5%～11.1%。主要原因有如下3點(diǎn)：①CSMA通過(guò)競(jìng)爭(zhēng)的方式爭(zhēng)用信道，隨著節(jié)點(diǎn)移動(dòng)性的增大，使得業(yè)務(wù)在隊(duì)列里持久堆積，所以端到端時(shí)延較大，且調(diào)度類的BiPi-TMAC有時(shí)隙的分配，所以時(shí)延較??；②ERMH-TDMA相比于BiPi-TMAC及時(shí)更新節(jié)點(diǎn)時(shí)隙請(qǐng)求信息，減少重傳次數(shù)及丟包率，從而降低了時(shí)延；③FU-TDMA相比于ERMH-TDMA采用“SP時(shí)期快速收斂”新機(jī)制，中心節(jié)點(diǎn)基于距離的并行調(diào)度算法，使得網(wǎng)絡(luò)在SP時(shí)期快速收斂，縮短時(shí)幀長(zhǎng)度，從而導(dǎo)致中心節(jié)點(diǎn)更新拓?fù)淇?，增?qiáng)鏈路的實(shí)時(shí)性，可有效降低時(shí)延；采用“空閑時(shí)隙公平重用”新機(jī)制，消除了中心節(jié)點(diǎn)調(diào)度節(jié)點(diǎn)時(shí)隙時(shí)產(chǎn)生的沖突問(wèn)題，使節(jié)點(diǎn)充分公平地利用時(shí)隙，提高了時(shí)隙復(fù)用率，減少了數(shù)據(jù)和指控業(yè)務(wù)的排隊(duì)時(shí)延，增加了網(wǎng)絡(luò)的吞吐量；采用“一跳鄰居多層次調(diào)度”新機(jī)制，讓優(yōu)先級(jí)高的節(jié)點(diǎn)優(yōu)先爭(zhēng)用競(jìng)爭(zhēng)時(shí)隙，防止因節(jié)點(diǎn)調(diào)度太過(guò)單一造成碰撞，降低了節(jié)點(diǎn)重傳和節(jié)點(diǎn)入網(wǎng)的時(shí)延。

圖9 數(shù)據(jù)傳輸平均時(shí)延

3.3.3 數(shù)據(jù)傳輸成功率

圖10為節(jié)點(diǎn)數(shù)為20時(shí)，數(shù)據(jù)傳輸成功率在不同的移動(dòng)性下的映射。因?yàn)楣?jié)點(diǎn)移動(dòng)性越高會(huì)導(dǎo)致節(jié)點(diǎn)鄰居關(guān)系變化越快，丟包率越大，所以隨著節(jié)點(diǎn)移動(dòng)性的增加，4種協(xié)議的數(shù)據(jù)傳輸成功率呈下降趨勢(shì)。由圖可知，BiPi-TMAC較CSMA成功率提高了7.2%～17.3%，ERMH-TDMA較BiPi-TMAC提高了0.9%～2.1%，F(xiàn)U-TDMA較ERMH-TDMA提高了2.2%～3.9%，其原因?yàn)椋孩儆捎诠?jié)點(diǎn)移動(dòng)性，相對(duì)于CSMA，調(diào)度類的ERMH-TDMA、BiPi-TMAC和FU-TDMA協(xié)議有動(dòng)態(tài)分配的屬于節(jié)點(diǎn)的時(shí)隙，且在SMOP時(shí)期緊隨一個(gè)競(jìng)爭(zhēng)時(shí)期，所以具有更高的可靠性；②相比于BiPi-TMAC，ERMH-TDMA降低了時(shí)隙請(qǐng)求的開(kāi)銷，實(shí)時(shí)讓節(jié)點(diǎn)更新拓?fù)?，提高了時(shí)隙請(qǐng)求成功率，從而提高了數(shù)據(jù)傳輸成功率；③FU-TDMA相比于ERMH-TDMA，使得網(wǎng)絡(luò)快速收斂，縮短了時(shí)幀長(zhǎng)度，提高了拓?fù)涓骂l率，鏈路實(shí)時(shí)性更高，從而提高了數(shù)據(jù)傳輸成功率；解決了時(shí)隙復(fù)用導(dǎo)致的沖突問(wèn)題，提高了時(shí)隙復(fù)用率，增強(qiáng)了網(wǎng)絡(luò)可靠性，從而提高了成功率；通過(guò)在競(jìng)爭(zhēng)階段，計(jì)算一跳鄰居優(yōu)先級(jí)，降低了節(jié)點(diǎn)的碰撞率，增加了時(shí)隙請(qǐng)求成功率，進(jìn)一步增強(qiáng)網(wǎng)絡(luò)可靠性，從而提高成功率。

圖10 數(shù)據(jù)傳輸成功率

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

針對(duì)無(wú)人機(jī)自組網(wǎng)控制時(shí)隙收斂慢，時(shí)隙沖突，時(shí)隙未充分利用及SMOP幀重傳易碰撞等問(wèn)題，提出了一種名為FU-TDMA協(xié)議。機(jī)制一中心節(jié)點(diǎn)通過(guò)維護(hù)的全網(wǎng)拓?fù)鋱D，依據(jù)位置信息計(jì)算并行調(diào)度的節(jié)點(diǎn)。機(jī)制二中心節(jié)點(diǎn)消除了時(shí)隙分配時(shí)產(chǎn)生的沖突問(wèn)題，挖掘出浪費(fèi)的時(shí)隙并對(duì)此時(shí)隙公平的利用。機(jī)制三普通節(jié)點(diǎn)計(jì)算自己一跳鄰居內(nèi)節(jié)點(diǎn)的優(yōu)先級(jí)，降低了碰撞概率，保證了更高的可靠性。仿真驗(yàn)證了FU-TDMA協(xié)議的有效性，可應(yīng)用在無(wú)人機(jī)移動(dòng)場(chǎng)景。在未來(lái)的研究中，可針對(duì)TDMA協(xié)議仍然存在的問(wèn)題，深入挖掘時(shí)隙的復(fù)用性，進(jìn)一步提高網(wǎng)絡(luò)性能。