基于排隊(duì)論的數(shù)據(jù)鏈網(wǎng)絡(luò)節(jié)點(diǎn)入退網(wǎng)時(shí)隙分配算法研究

盧 翰，田沿平，傅 偉

（1.海軍航空大學(xué)青島校區(qū)，山東 青島 264000；2.91206 部隊(duì)，山東 青島 264000）

0 引言

現(xiàn)代戰(zhàn)爭(zhēng)是系統(tǒng)間、體系間的對(duì)抗，以高度信息化的聯(lián)合作戰(zhàn)為基本樣式，包含多軍種、兵種的共同協(xié)作，統(tǒng)一的指揮、調(diào)度、控制等諸多問題都要建立在及時(shí)、準(zhǔn)確的信息傳遞基礎(chǔ)上。戰(zhàn)術(shù)數(shù)據(jù)鏈的出現(xiàn)使各個(gè)獨(dú)立的作戰(zhàn)平臺(tái)相互鏈接，是自動(dòng)化指揮系統(tǒng)的重要組成部分[1]。數(shù)據(jù)鏈作為現(xiàn)代戰(zhàn)爭(zhēng)的“倍增器”，是信息化作戰(zhàn)的“戰(zhàn)術(shù)神經(jīng)網(wǎng)絡(luò)”，在多場(chǎng)現(xiàn)代化戰(zhàn)爭(zhēng)中大放異彩[2]。但是，隨著數(shù)據(jù)鏈的不斷使用，越來越多的問題隨之暴露出來，其中節(jié)點(diǎn)的入退網(wǎng)時(shí)隙分配是一個(gè)關(guān)鍵問題。本文基于排隊(duì)論提出一種數(shù)據(jù)鏈網(wǎng)絡(luò)節(jié)點(diǎn)入退網(wǎng)時(shí)隙分配算法。

1 算法設(shè)計(jì)

1.1 算法總體設(shè)計(jì)思路

首先，將用戶節(jié)點(diǎn)的信息優(yōu)先級(jí)作為算法設(shè)計(jì)的重要參考指標(biāo)。在數(shù)據(jù)鏈的實(shí)際運(yùn)用中，優(yōu)先級(jí)的評(píng)估要根據(jù)節(jié)點(diǎn)位于網(wǎng)內(nèi)的戰(zhàn)略地位進(jìn)行重要程度排序。地位越重要的節(jié)點(diǎn)，其信息越需要優(yōu)先傳遞。通常情況下，指控中心或主控站等節(jié)點(diǎn)負(fù)責(zé)整個(gè)戰(zhàn)場(chǎng)態(tài)勢(shì)，擔(dān)負(fù)戰(zhàn)場(chǎng)的統(tǒng)籌、調(diào)度、指揮任務(wù)，需要保證優(yōu)先發(fā)送；而負(fù)責(zé)戰(zhàn)術(shù)偵察的各種偵察機(jī)、預(yù)警機(jī)等節(jié)點(diǎn)，由于其擔(dān)負(fù)著警戒、偵察、巡邏、預(yù)警等任務(wù)，因此應(yīng)當(dāng)配置位于上層的優(yōu)先級(jí)數(shù)，使得態(tài)勢(shì)情況可以及時(shí)匯報(bào)給主控站；各種戰(zhàn)斗機(jī)、運(yùn)輸機(jī)、轟炸機(jī)等因?yàn)槎鄶?shù)時(shí)刻處于接收、執(zhí)行指令信息的狀態(tài)，需要上報(bào)的信息量少，而且實(shí)時(shí)性的需求往往偏弱一些，所以往往可以分配較低的優(yōu)先級(jí)[3]。

其次，優(yōu)先級(jí)并不是一成不變的，在戰(zhàn)場(chǎng)上隨著戰(zhàn)場(chǎng)局勢(shì)的變化，各個(gè)節(jié)點(diǎn)的作用也會(huì)有所改變，導(dǎo)致節(jié)點(diǎn)的優(yōu)先級(jí)發(fā)生變化。同時(shí)，在算法設(shè)計(jì)的時(shí)候要盡量考慮因高優(yōu)先級(jí)節(jié)點(diǎn)占據(jù)大量時(shí)隙導(dǎo)致低優(yōu)先級(jí)節(jié)點(diǎn)出現(xiàn)“包餓死”的情況。

最后，當(dāng)網(wǎng)內(nèi)有節(jié)點(diǎn)增減后，需要依據(jù)節(jié)點(diǎn)的優(yōu)先級(jí)進(jìn)行排隊(duì)分配時(shí)隙資源[4]。

1.2 算法具體設(shè)計(jì)

本算法具體設(shè)計(jì)的步驟如下：

（1）進(jìn)行網(wǎng)絡(luò)的初始化，設(shè)定劃分總時(shí)隙的個(gè)數(shù)為N，網(wǎng)絡(luò)初始節(jié)點(diǎn)數(shù)為X，平均每段時(shí)隙長(zhǎng)度為L(zhǎng)；

（2）約定一個(gè)周期的時(shí)間T，則一個(gè)周期的時(shí)隙數(shù)目為T/L；

（3）在t時(shí)刻，1 個(gè)節(jié)點(diǎn)入網(wǎng)或退網(wǎng)，統(tǒng)計(jì)需要發(fā)送信息節(jié)點(diǎn)總數(shù)。如果沒有數(shù)據(jù)業(yè)務(wù)，算法自動(dòng)跳過下面的步驟，默認(rèn)完成分配周期，不分配，算法結(jié)束；如果總數(shù)不為0，代表此時(shí)存在信息任務(wù)，則按照優(yōu)先級(jí)先高后低的順序排序，形成一個(gè)分配順序表，依次對(duì)每個(gè)節(jié)點(diǎn)劃分一個(gè)數(shù)據(jù)時(shí)隙，依次分配至最低優(yōu)先級(jí)節(jié)點(diǎn)分得時(shí)隙，一輪分配結(jié)束；

（4）一輪分配結(jié)束后，開始第二輪分配，同樣按照分配順序表的安排為節(jié)點(diǎn)各分配一個(gè)時(shí)隙，方法同步驟（3）；

（5）按序執(zhí)行多輪時(shí)隙分配至最后一個(gè)時(shí)隙分配完畢，一個(gè)周期內(nèi)的時(shí)隙分配完成；

（6）若在一個(gè)周期內(nèi)時(shí)隙分配完成后，存在一個(gè)節(jié)點(diǎn)在連續(xù)兩輪未分配時(shí)隙的情況，則進(jìn)行節(jié)點(diǎn)的優(yōu)先級(jí)動(dòng)態(tài)調(diào)整；

（7）進(jìn)行節(jié)點(diǎn)優(yōu)先級(jí)調(diào)整后再進(jìn)行多輪時(shí)隙分配；若出現(xiàn)步驟（6）的情況，對(duì)節(jié)點(diǎn)優(yōu)先級(jí)進(jìn)行再調(diào)整和多輪時(shí)隙分配；

（8）時(shí)隙分配完畢。

整體算法流程如圖1 所示。

圖1 時(shí)隙分配算法流程圖

為了保證在時(shí)隙分配的過程中不出現(xiàn)較高的優(yōu)先級(jí)節(jié)點(diǎn)分配時(shí)隙時(shí)總是率先將時(shí)隙分配占有完畢而下層優(yōu)先級(jí)的數(shù)據(jù)分不到時(shí)隙的情況[5]，特別規(guī)定數(shù)據(jù)鏈節(jié)點(diǎn)優(yōu)先級(jí)動(dòng)態(tài)修正原則如下。

（1）依據(jù)節(jié)點(diǎn)優(yōu)先級(jí)進(jìn)行排序，形成時(shí)隙分配順序表。節(jié)點(diǎn)優(yōu)先級(jí)分為1～5 的級(jí)別，5 最高，1 最低，5 級(jí)作為應(yīng)急特需優(yōu)先級(jí)。

（2）若出現(xiàn)1 個(gè)節(jié)點(diǎn)連續(xù)2 輪時(shí)隙分配過程皆未分配到時(shí)隙的情況，則將該節(jié)點(diǎn)優(yōu)先級(jí)提高1 級(jí)。

2 算法仿真模型構(gòu)建

本文主要采用OPNET 軟件進(jìn)行算法建模仿真分析。由于節(jié)點(diǎn)退網(wǎng)建模模型與入網(wǎng)模型基本一致，本文主要介紹節(jié)點(diǎn)入網(wǎng)算法仿真模型。

設(shè)置網(wǎng)絡(luò)環(huán)境為：plane_0～plane_3 共4 個(gè)飛行節(jié)點(diǎn)組成初始數(shù)據(jù)鏈網(wǎng)絡(luò)，且設(shè)置它們的優(yōu)先級(jí)分別為5、4、3、1。因此可以得到這4 個(gè)節(jié)點(diǎn)的時(shí)隙分配順序?yàn)閜lane_0 →plane_1 →plane_2 →plane_3。

在工作一段時(shí)間后，新節(jié)點(diǎn)plane_4 入網(wǎng)，其優(yōu)先級(jí)為2，則形成的新的時(shí)隙分配順序?yàn)閜lane_0 →plane_1→plane_2→plane_4→plane_3。根據(jù)環(huán)境描述，建立的新的網(wǎng)絡(luò)環(huán)境如圖2 所示。

圖2 基于排隊(duì)論的算法網(wǎng)絡(luò)域建模圖

2.1 節(jié)點(diǎn)模型構(gòu)建

網(wǎng)內(nèi)節(jié)點(diǎn)應(yīng)當(dāng)具備以下模塊以實(shí)現(xiàn)不同功能。

（1）network 模塊。對(duì)應(yīng)網(wǎng)絡(luò)層，作為實(shí)現(xiàn)入退網(wǎng)管理過程的最主要模塊。將依據(jù)節(jié)點(diǎn)優(yōu)先級(jí)排列分配表的功能放在此模塊。網(wǎng)絡(luò)數(shù)據(jù)的產(chǎn)生、包創(chuàng)建、包處理也在這里進(jìn)行。

（2）mac 模塊。mac 模塊作為mac 層，但該模塊的功能有所縮減，時(shí)隙劃分放在上一層進(jìn)行，本模塊僅起上下層模塊間數(shù)據(jù)包的中繼、轉(zhuǎn)發(fā)的作用。

（3）phy 模塊。對(duì)應(yīng)物理層，控制收發(fā)信機(jī)及天線。

（4）rec 模塊和trans 模塊。對(duì)應(yīng)收發(fā)信機(jī)，其多項(xiàng)物理工作特性均由phy 模塊控制。

（5）ant 模塊。對(duì)應(yīng)天線，完成收發(fā)及轉(zhuǎn)換，可以在全向與定向之間轉(zhuǎn)換。

本文建立的節(jié)點(diǎn)域模型如圖3 所示。

圖3 基于排隊(duì)論的算法節(jié)點(diǎn)域建模圖

2.2 模塊模型構(gòu)建

2.2.1 network 模塊

network 模塊用于產(chǎn)生網(wǎng)絡(luò)戰(zhàn)術(shù)數(shù)據(jù)，按照網(wǎng)內(nèi)節(jié)點(diǎn)及相應(yīng)要求劃分時(shí)隙段，對(duì)節(jié)點(diǎn)的優(yōu)先級(jí)予以認(rèn)定。在新節(jié)點(diǎn)進(jìn)入網(wǎng)絡(luò)后，network 模塊形成新的時(shí)隙分配順序表，控制多輪對(duì)各節(jié)點(diǎn)的時(shí)隙劃分。同時(shí)需要考慮增加對(duì)特殊優(yōu)先級(jí)的判斷與設(shè)定進(jìn)程，以達(dá)到優(yōu)先級(jí)動(dòng)態(tài)提升的要求[6-7]?；谂抨?duì)論的算法network 模塊進(jìn)程如圖4 所示。

圖4 基于排隊(duì)論的算法network 模塊進(jìn)程圖

網(wǎng)絡(luò)運(yùn)行工作時(shí)，首先啟動(dòng)init 狀態(tài)將各變量進(jìn)行初始化，包括節(jié)點(diǎn)優(yōu)先級(jí)的確認(rèn)，都在此處完成。其中，對(duì)于普通節(jié)點(diǎn)優(yōu)先級(jí)的設(shè)置將按照要求設(shè)置為1～4。new 狀態(tài)代表接收到來自上級(jí)的包含有特殊任務(wù)的指令，經(jīng)判斷滿足judgement 要求后，啟用特殊優(yōu)先級(jí)5，初始化完成后，進(jìn)入wait 狀態(tài)等待其他驅(qū)動(dòng)指令。new 狀態(tài)代表有新節(jié)點(diǎn)入網(wǎng)，在經(jīng)過認(rèn)證運(yùn)行滿足judgement 條件后，運(yùn)行入網(wǎng)，還在init 狀態(tài)確定節(jié)點(diǎn)優(yōu)先級(jí)等信息，且在new_init 狀態(tài)完成初始變量的更新[8]。完成后運(yùn)送data產(chǎn)生的網(wǎng)絡(luò)數(shù)據(jù)經(jīng)過divide 狀態(tài)統(tǒng)計(jì)時(shí)隙段數(shù)量并完成時(shí)隙段劃分后，形成order 狀態(tài)內(nèi)的時(shí)隙分配順序，同時(shí)要將此輪分配的具體情況傳至special狀態(tài)審定后按順序進(jìn)行數(shù)據(jù)運(yùn)送與信息交流。如果存在算法中規(guī)定的“低優(yōu)先級(jí)節(jié)點(diǎn)連續(xù)兩次分得的時(shí)隙資源為0 或請(qǐng)求等待時(shí)間超過預(yù)定的時(shí)間長(zhǎng)度”的promote 條件，則在new_init 狀態(tài)內(nèi)將該節(jié)點(diǎn)優(yōu)先級(jí)提升1 級(jí)。

2.2.2 mac 模塊

mac 模塊進(jìn)程處于phy 模塊和network 模塊之間，任務(wù)相對(duì)輕松，作為中轉(zhuǎn)模塊，其負(fù)責(zé)包流的存儲(chǔ)和轉(zhuǎn)發(fā)[9]。mac 模塊進(jìn)程如圖5 所示。

圖5 基于排隊(duì)論的算法mac 模塊進(jìn)程圖

節(jié)點(diǎn)最初在init 狀態(tài)進(jìn)行變量初始化。初始化完成后，節(jié)點(diǎn)始終處于idle狀態(tài)，這是一個(gè)空閑狀態(tài)。當(dāng)網(wǎng)絡(luò)層和物理層上下層之間有包傳遞交流時(shí)，由強(qiáng)制狀態(tài)init_pk 狀態(tài)進(jìn)行包處理，結(jié)束后進(jìn)入end狀態(tài)。

2.2.3 phy 模塊

phy 模塊根據(jù)上層指令對(duì)收發(fā)機(jī)和天線等物理設(shè)備進(jìn)行工作參數(shù)的調(diào)節(jié)，指令通過包流內(nèi)的信息進(jìn)行傳達(dá)。同時(shí)，phy 模塊還承擔(dān)將系統(tǒng)接收到的包轉(zhuǎn)發(fā)至上層的任務(wù)。phy 模塊進(jìn)程如圖6 所示。

圖6 基于排隊(duì)論的算法phy 模塊進(jìn)程圖

網(wǎng)絡(luò)工作時(shí)，INIT 狀態(tài)負(fù)責(zé)對(duì)網(wǎng)元節(jié)點(diǎn)的天線參數(shù)、工作狀態(tài)以及收發(fā)頻率進(jìn)行初始配置。下一步進(jìn)入IDLE 狀態(tài)，等待網(wǎng)內(nèi)節(jié)點(diǎn)發(fā)送中斷狀態(tài)作為進(jìn)行下一步的驅(qū)動(dòng)力。如果有其他節(jié)點(diǎn)傳來數(shù)據(jù)包信息，在LOW 狀態(tài)解析處理數(shù)據(jù)包。如果是上層模塊的數(shù)據(jù)包時(shí)，到HIGH 狀態(tài)按照數(shù)據(jù)包內(nèi)的信息指示更改天線的參數(shù)和狀態(tài)，按指示把數(shù)據(jù)包發(fā)給指定節(jié)點(diǎn)。節(jié)點(diǎn)可以在SETMOD 狀態(tài)通過設(shè)置天線的指向等參數(shù)進(jìn)行對(duì)準(zhǔn)，定向接收數(shù)據(jù)[10]。

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

初始網(wǎng)絡(luò)由4 架戰(zhàn)機(jī)組成，分別為plane_0、plane_1、plane_2、plane_3。在某一時(shí)刻，新節(jié)點(diǎn)plane_4 進(jìn)入網(wǎng)絡(luò)。飛機(jī)的飛行方向?yàn)樘窖蠛Ｓ?。假定每個(gè)節(jié)點(diǎn)的信號(hào)發(fā)射功率足夠大，任意兩個(gè)節(jié)點(diǎn)都可以通信。仿真環(huán)境的基本情況如表1 所示。

表1 網(wǎng)絡(luò)環(huán)境參數(shù)

在進(jìn)行本文提出的基于排隊(duì)論的數(shù)據(jù)鏈節(jié)點(diǎn)入退網(wǎng)時(shí)隙分配算法仿真的同時(shí)，對(duì)目前數(shù)據(jù)鏈?zhǔn)褂玫幕谳喸儥C(jī)制數(shù)據(jù)鏈節(jié)點(diǎn)入退網(wǎng)時(shí)隙分配算法進(jìn)行仿真，并依據(jù)網(wǎng)絡(luò)吞吐量、隊(duì)列時(shí)延、時(shí)隙利用率這3 個(gè)指標(biāo)對(duì)網(wǎng)絡(luò)QoS 性能進(jìn)行判斷。網(wǎng)絡(luò)吞吐量指單位時(shí)間內(nèi)網(wǎng)絡(luò)中節(jié)點(diǎn)接收到數(shù)據(jù)的平均速率，隊(duì)列時(shí)延指每個(gè)數(shù)據(jù)包從進(jìn)入緩存到調(diào)度出去的平均時(shí)間，時(shí)隙利用率指網(wǎng)絡(luò)時(shí)隙發(fā)送數(shù)據(jù)包的比例。

3.1 網(wǎng)絡(luò)吞吐量

網(wǎng)絡(luò)吞吐量指單位時(shí)間內(nèi)網(wǎng)絡(luò)中節(jié)點(diǎn)接收到數(shù)據(jù)的平均速率。基于輪詢機(jī)制數(shù)據(jù)鏈節(jié)點(diǎn)入退網(wǎng)時(shí)隙分配算法和基于排隊(duì)論的數(shù)據(jù)鏈節(jié)點(diǎn)入退網(wǎng)時(shí)隙分配算法的網(wǎng)絡(luò)吞吐量分別如圖7、圖8 所示?？梢钥闯?，基于輪詢的節(jié)點(diǎn)入網(wǎng)時(shí)隙分配算法的網(wǎng)絡(luò)吞吐量在0.18 Mb·s-1左右，而基于排隊(duì)論機(jī)制網(wǎng)絡(luò)吞吐量平均在0.52 Mb·s-1左右。據(jù)此可以得出結(jié)論，排隊(duì)機(jī)制論的網(wǎng)絡(luò)吞吐量遠(yuǎn)大于輪詢機(jī)制，同時(shí)輪詢機(jī)制和排隊(duì)論機(jī)制的網(wǎng)絡(luò)吞吐量波動(dòng)較少，整體較為穩(wěn)定，說明排隊(duì)論機(jī)制更適合大信息量數(shù)據(jù)鏈網(wǎng)絡(luò)。

圖7 輪詢機(jī)制網(wǎng)絡(luò)吞吐量

圖8 排隊(duì)論機(jī)制網(wǎng)絡(luò)吞吐量

3.2 隊(duì)列時(shí)延

輪詢機(jī)制和排隊(duì)論機(jī)制的隊(duì)列時(shí)延情況分別如圖9 和圖10 所示。隊(duì)列時(shí)延指每個(gè)數(shù)據(jù)包從進(jìn)入緩存到調(diào)度出去的平均時(shí)間[11]。從圖9可以看出，輪詢機(jī)制的隊(duì)列時(shí)延大約在0.32 s 左右，波動(dòng)較小且較為平穩(wěn)。從圖10 可以看出，排隊(duì)論機(jī)制的隊(duì)列時(shí)延大約在0.21 s 左右，在網(wǎng)絡(luò)形成初期波動(dòng)較大，但逐漸趨于平穩(wěn)。通過分析可知，排隊(duì)論的隊(duì)列時(shí)延明顯小于輪詢機(jī)制，說明排隊(duì)論網(wǎng)絡(luò)較為暢通，數(shù)據(jù)傳輸速率快，實(shí)時(shí)性高。

圖9 輪詢機(jī)制隊(duì)列時(shí)延

圖10 排隊(duì)論機(jī)制隊(duì)列時(shí)延

3.3 時(shí)隙率利用率

輪詢機(jī)制和排隊(duì)論機(jī)制的時(shí)隙利用率對(duì)比情況如圖11 所示，其中，紅色線為基于輪詢機(jī)制數(shù)據(jù)鏈節(jié)點(diǎn)入退網(wǎng)時(shí)隙分配算法的時(shí)隙利用率，為60%，藍(lán)色線為基于排隊(duì)論機(jī)制數(shù)據(jù)鏈節(jié)點(diǎn)入退網(wǎng)時(shí)隙分配算法的時(shí)隙利用率，為75%?？梢?，排隊(duì)論的節(jié)點(diǎn)優(yōu)先級(jí)確定時(shí)隙分配和優(yōu)先級(jí)動(dòng)態(tài)調(diào)整的機(jī)制可以使得網(wǎng)絡(luò)中時(shí)隙資源的分配更加科學(xué)。通過優(yōu)先級(jí)動(dòng)態(tài)變化的機(jī)制適時(shí)增長(zhǎng)高優(yōu)先級(jí)節(jié)點(diǎn)的時(shí)延，適當(dāng)縮短低優(yōu)先級(jí)節(jié)點(diǎn)的時(shí)延，高優(yōu)先級(jí)節(jié)點(diǎn)“犧牲”時(shí)效，但更滿足作戰(zhàn)行動(dòng)中整體的信息交互要求。

圖11 輪詢機(jī)制與排隊(duì)論機(jī)制時(shí)隙利用率對(duì)比

4 結(jié)語

本文主要提出一種基于排隊(duì)論的數(shù)據(jù)鏈網(wǎng)絡(luò)節(jié)點(diǎn)入退網(wǎng)時(shí)隙分配算法。在設(shè)計(jì)思路上，一是利用排隊(duì)論的思想進(jìn)行時(shí)隙分配設(shè)計(jì)，二是設(shè)置最高特情優(yōu)先級(jí)以應(yīng)對(duì)戰(zhàn)場(chǎng)隨時(shí)會(huì)發(fā)生的特殊情況，三是規(guī)定優(yōu)先級(jí)的動(dòng)態(tài)修正原則防止低優(yōu)先級(jí)節(jié)點(diǎn)分配不到時(shí)隙資源而造成的資源浪費(fèi)，使網(wǎng)絡(luò)對(duì)于節(jié)點(diǎn)優(yōu)先級(jí)的管理更加靈活，在時(shí)隙資源分配上更加合理，這防止了網(wǎng)絡(luò)節(jié)點(diǎn)資源分配出現(xiàn)“兩極分化”的趨勢(shì)。

通過與傳統(tǒng)數(shù)據(jù)鏈?zhǔn)褂玫妮喸儥C(jī)制時(shí)隙分配算法進(jìn)行仿真分析對(duì)比可以得出，在網(wǎng)絡(luò)吞吐量上排隊(duì)論為0.52 Mb·s-1，輪詢機(jī)制為0.18 Mb·s-1，排隊(duì)論遠(yuǎn)大于輪詢機(jī)制；在隊(duì)列時(shí)延上排隊(duì)論為0.21 s，輪詢機(jī)制為0.32 s，排隊(duì)論網(wǎng)絡(luò)的實(shí)時(shí)性比輪詢機(jī)制高；在時(shí)隙利用率上，相比于輪詢的60%的利用率，排隊(duì)論利用率更高，為75%。綜合來看，基于排隊(duì)論的數(shù)據(jù)鏈節(jié)點(diǎn)入退網(wǎng)時(shí)隙分配算法的時(shí)隙資源分配率較高，且算法對(duì)節(jié)點(diǎn)優(yōu)先級(jí)較為敏感。算法適用于網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)目多且具備鮮明優(yōu)先級(jí)關(guān)系的網(wǎng)絡(luò)環(huán)境。短時(shí)間內(nèi)，時(shí)延特性迅速穩(wěn)定，可迅速投入戰(zhàn)斗使用，滿足對(duì)網(wǎng)絡(luò)穩(wěn)定性的較高要求。