定向自組網(wǎng)中基于連通支配集優(yōu)化的信息共享算法*

程 帥，徐任暉，彭來(lái)獻(xiàn)，張 磊，楊曜旗

（陸軍工程大學(xué)，江蘇 南京 210007）

0 引言

無(wú)線自組織網(wǎng)絡(luò)通常采用全向傳輸方式進(jìn)行通信，因?yàn)橄啾扔诙ㄏ騻鬏敼逃械碾[藏節(jié)點(diǎn)、耳聾、暴露節(jié)點(diǎn)等問(wèn)題[1]，全向傳輸擁有更加簡(jiǎn)單的控制協(xié)議。但是在遠(yuǎn)距離、大容量通信時(shí)通常采用定向傳輸方式，這是由于定向傳輸在相同的發(fā)射功率時(shí)擁有更遠(yuǎn)的傳輸距離和更高的空分復(fù)用率，能夠有效減小被監(jiān)聽、定位的概率，增大網(wǎng)絡(luò)容量[1]。無(wú)線自組織網(wǎng)絡(luò)中的信息共享是每個(gè)節(jié)點(diǎn)都將自己所擁有的信息傳播到其他節(jié)點(diǎn)的行為，以此來(lái)完成節(jié)點(diǎn)對(duì)網(wǎng)絡(luò)環(huán)境的協(xié)同感知[2]。此類信息共享問(wèn)題也稱為全到全廣播（All-to-All Broadcasting）或流言傳播（Gossiping）問(wèn)題[3]。在時(shí)延敏感型的網(wǎng)絡(luò)中，節(jié)點(diǎn)需要將通過(guò)傳感器采集到的信息快速進(jìn)行分發(fā)，因而需要努力減小信息在共享過(guò)程的時(shí)延。由于所有節(jié)點(diǎn)需要并行地進(jìn)行消息的分發(fā)和轉(zhuǎn)發(fā)，對(duì)定向傳輸?shù)恼{(diào)度方法和分發(fā)策略等問(wèn)題提出了嚴(yán)峻的挑戰(zhàn)。本文以定向傳輸無(wú)線自組網(wǎng)的信息共享為背景，研究在配備了單波束定向天線的通信節(jié)點(diǎn)所構(gòu)成的無(wú)線網(wǎng)絡(luò)中，高效完成共享戰(zhàn)場(chǎng)態(tài)勢(shì)信息的方案。

無(wú)線自組網(wǎng)中解決全到全的廣播問(wèn)題時(shí)，最簡(jiǎn)單的是通過(guò)泛洪（Flooding）的方式進(jìn)行消息的廣播分發(fā)[4]，這在規(guī)模較小的網(wǎng)絡(luò)中是一種簡(jiǎn)單可行的信息共享方式。但隨著網(wǎng)絡(luò)規(guī)模的擴(kuò)大，由于移動(dòng)無(wú)線自組網(wǎng)固有的動(dòng)態(tài)性和不可預(yù)測(cè)性[5]，泛洪的方式將會(huì)產(chǎn)生嚴(yán)重的接入沖突以及信息轉(zhuǎn)發(fā)過(guò)程中的冗余傳輸問(wèn)題，致使信息共享的性能下降，造成大量的帶寬浪費(fèi)和較高的通信時(shí)延。當(dāng)前，為解決定向傳輸背景下的信息共享，主要是改造典型的UxDMA[6]、JazzyMAC[7]、ROMA[8]等定向MAC 協(xié)議[9]，使其能夠完成信息共享。但此類算法不能完全消除冗余傳輸，沒(méi)有充分利用定向傳輸?shù)膬?yōu)勢(shì)，導(dǎo)致網(wǎng)絡(luò)的性能難以提升，信息共享的時(shí)效性仍然較差。

因此，如果要高效地完成信息共享，必須建立起有效的控制機(jī)制和傳播策略，充分利用定向傳輸?shù)目辗謴?fù)用特點(diǎn)，改善信息共享的性能。因而本文從空分復(fù)用率、冗余傳輸控制、調(diào)度機(jī)制3 個(gè)方面進(jìn)行研究。連通支配集可以有效解決無(wú)線自組網(wǎng)中的冗余傳輸和拓?fù)渚S護(hù)等方面的問(wèn)題[10-12]。但是當(dāng)前對(duì)連通支配集的研究大多是基于全向網(wǎng)絡(luò)的，其策略大多以減小支配集節(jié)點(diǎn)數(shù)目為目標(biāo)，從而降低對(duì)網(wǎng)絡(luò)管理的復(fù)雜度。本文將連通支配集技術(shù)應(yīng)用于信息共享業(yè)務(wù)，提出了一種應(yīng)用于單波束定向自組網(wǎng)中的無(wú)沖突調(diào)度算法——單波束最深搜索樹（Maximum Depth Search Tree with Single Beam，MDST-SB）算法。該算法通過(guò)充分利用定向傳輸?shù)目辗謴?fù)用特性，加強(qiáng)傳輸過(guò)程中的冗余控制，提高了信息共享的效率。

論文其他部分組織結(jié)構(gòu)如下：第1 部分介紹了本文的基本通信模型和假設(shè)；第2 部分闡述了MDST-SB 算法的流程和算法分析；第3 部分給出了算法的仿真結(jié)果以及對(duì)照比較；第4 部分為總結(jié)部分，給出了現(xiàn)有研究的總結(jié)和后續(xù)研究方向。

1 系統(tǒng)模型

1.1 節(jié)點(diǎn)模型

在有N個(gè)節(jié)點(diǎn)的無(wú)線網(wǎng)絡(luò)中，V表示網(wǎng)絡(luò)所有節(jié)點(diǎn)的集合，任意節(jié)點(diǎn)vi∈V={x1,x2,…,xN}均存在一個(gè)的隨機(jī)位置Location(vi)=(xi,yi)，其中xi表示其橫坐標(biāo)，yi表示其縱坐標(biāo)。同時(shí)，每個(gè)節(jié)點(diǎn)都擁有一個(gè)可表示其身份的唯一ID，且Id(vi)=i。

1.2 通信模型

為簡(jiǎn)化分析，本文中的通信節(jié)點(diǎn)均采用最大通信距離為rmax的單波束定向天線，節(jié)點(diǎn)vi和vj的距離可以通過(guò)下面公式計(jì)算：

當(dāng)dij≤rmax且天線指向相互對(duì)準(zhǔn)后才能進(jìn)行通信。

在信道資源使用方面，本文通過(guò)將時(shí)間劃分為大小相等且為tslot的時(shí)間片，即時(shí)隙。并以時(shí)隙為單位對(duì)網(wǎng)絡(luò)節(jié)點(diǎn)的通信狀態(tài)進(jìn)行調(diào)度，在一個(gè)時(shí)隙內(nèi)節(jié)點(diǎn)只能處于發(fā)送或接收狀態(tài)之一。

1.3 定長(zhǎng)分組傳輸模型

研究信息共享問(wèn)題需要確定合理的分組傳輸模型，本文采用固定長(zhǎng)度的分組。節(jié)點(diǎn)vi將需要共享的本地信息mi封裝成長(zhǎng)度為L(zhǎng)的分組，分組在發(fā)送和轉(zhuǎn)發(fā)的過(guò)程中不能被拆分和重組。節(jié)點(diǎn)發(fā)送/接收速率為s，滿足L/s=tslot，即表示一個(gè)時(shí)隙節(jié)點(diǎn)只能發(fā)送/接收一個(gè)分組。

1.4 問(wèn)題描述

信息共享過(guò)程可描述如下：在共享時(shí)刻開始之初，節(jié)點(diǎn)vi將需要共享的信息封裝成固定長(zhǎng)度的分組mi，此時(shí)vi所擁有的消息集合Mi={mi},i∈{1,2,3,…,N}。在信息共享過(guò)程中vi不斷發(fā)送自己消息集合中或接收其他節(jié)點(diǎn)發(fā)送過(guò)來(lái)的消息，經(jīng)過(guò)若干次通信后，所有節(jié)點(diǎn)均擁有其他節(jié)點(diǎn)的消息，即M1=M2=…=MN={m1,m2,…mN}。

如圖1（a）所示，是4 個(gè)節(jié)點(diǎn)組成的網(wǎng)絡(luò)。初始時(shí)刻，節(jié)點(diǎn)分別包含的消息集合可表示為：M1={m1},M2={m2},M3={m3},M4={m4}。第一時(shí)隙可能的傳輸情況是節(jié)點(diǎn)v1發(fā)送m1到v2，v4發(fā)送m4到v3。因此，第一時(shí)隙結(jié)束時(shí)節(jié)點(diǎn)的消息集合狀態(tài)為M1={m1}，M2={m1,m2}，M3={m3,m4}，M4={m4}。過(guò)程中經(jīng)過(guò)若干次通信后最終達(dá)到M1=M2=M3=M4={m1,m2,m3,m4}，即如圖1（d）所示的所有節(jié)點(diǎn)均達(dá)到信息共享完成狀態(tài)。

圖1 固定長(zhǎng)度的信息共享模型

在信息共享過(guò)程中減小信息共享時(shí)延需要重點(diǎn)關(guān)注的是兩個(gè)方面：冗余傳輸和定向傳輸?shù)目辗謴?fù)用。圖1（c）展示了一種可能的冗余傳輸情況，在中間的某個(gè)時(shí)隙，v4向v2發(fā)送m4，由于v4并不知道在此之前v3已經(jīng)向v2發(fā)送過(guò)m4，導(dǎo)致該時(shí)隙的傳輸冗余。此外，定向傳輸相對(duì)于全向傳輸，可以通過(guò)控制波束的寬度、方向以及發(fā)射功率等因素，盡量減少對(duì)其他節(jié)點(diǎn)的干擾。在規(guī)模更大的一些網(wǎng)絡(luò)中，充分利用定向傳輸?shù)目辗謴?fù)用的特點(diǎn)，可以增大同一時(shí)刻并發(fā)通信數(shù)目，加快信息共享速度。

無(wú)線網(wǎng)絡(luò)中，一跳可達(dá)的網(wǎng)絡(luò)場(chǎng)景具備較好的連通性。在此場(chǎng)景下，假設(shè)網(wǎng)絡(luò)中節(jié)點(diǎn)數(shù)為N，每一個(gè)節(jié)點(diǎn)vi都可以直接將自己的信息發(fā)送給網(wǎng)絡(luò)中的其他節(jié)點(diǎn)。因此，一次完整的信息共享網(wǎng)絡(luò)中需要轉(zhuǎn)發(fā)的報(bào)文數(shù)量為N(N-1)。而在本文的通信模型和分組傳輸模型下，一個(gè)時(shí)隙網(wǎng)絡(luò)能夠發(fā)送分組的數(shù)量最多不超過(guò)N/2。因此，一次信息共享需要消耗的時(shí)隙數(shù)為N(N-1)/N/2。

然而，現(xiàn)實(shí)環(huán)境下無(wú)線網(wǎng)絡(luò)中的節(jié)點(diǎn)很難做到一跳可達(dá)。因此，無(wú)論采用什么樣的組網(wǎng)方式和傳播方案，在本文的系統(tǒng)模型下完成一次信息共享完成一次信息共享消耗的時(shí)隙數(shù)Ncomsume滿足：

同時(shí)，信息共享過(guò)程中需要交互的報(bào)文數(shù)量N(N-1)和消耗的總時(shí)隙數(shù)Ncomsume滿足如下關(guān)系：

式中，ni為時(shí)隙Slot=i時(shí)的網(wǎng)絡(luò)節(jié)點(diǎn)可以傳輸分組的數(shù)量。因此，為了減少共享過(guò)程消耗的時(shí)隙數(shù)目即Ncomsume，需要盡量增大每個(gè)時(shí)隙可以進(jìn)行傳輸報(bào)文的數(shù)量ni。所以該問(wèn)題可以轉(zhuǎn)化為求Ncomsume的近似最優(yōu)解問(wèn)題。

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

MDST-SB 算法是一種靜態(tài)網(wǎng)絡(luò)下的鏈路調(diào)度算法，其過(guò)程主要分為連通支配集的構(gòu)造和鏈路的貪心調(diào)度兩個(gè)階段。

首先，算法需要根據(jù)網(wǎng)絡(luò)其他節(jié)點(diǎn)位置信息進(jìn)行連通支配集的初步構(gòu)造集合。在得到的構(gòu)造集合中進(jìn)行優(yōu)化策略的篩選，刪除次優(yōu)的構(gòu)造結(jié)果，得到最終的構(gòu)造網(wǎng)絡(luò)并確定支配集節(jié)點(diǎn)。接下來(lái)，算法以時(shí)隙為單位進(jìn)行集中式的貪心調(diào)度，過(guò)程中分別記錄各個(gè)節(jié)點(diǎn)不同時(shí)隙的調(diào)度狀態(tài)。當(dāng)網(wǎng)絡(luò)再次有共享需求時(shí)只需將共享的數(shù)據(jù)封裝成定長(zhǎng)分組。并在約定的時(shí)刻開始按照既定通信序列進(jìn)行調(diào)度即可完成信息共享。表1 列舉了算法過(guò)程中使用的符號(hào)。

表1 主要符號(hào)說(shuō)明

2.1 連通支配集的構(gòu)造

連通支配集的構(gòu)造分為3 步：鄰接矩陣生成、最大深度搜索和負(fù)載及鏈路的優(yōu)化。鄰接矩陣生成是將實(shí)際網(wǎng)絡(luò)抽象化處理并作為后續(xù)步驟的輸入。最大深度搜索是以鄰接矩陣為輸入進(jìn)行先深搜索的遍歷。負(fù)載優(yōu)化和鏈路優(yōu)化將處理的結(jié)果進(jìn)行進(jìn)一步篩選和優(yōu)化。

2.1.1 鄰接矩陣生成

中心計(jì)算節(jié)點(diǎn)根據(jù)網(wǎng)絡(luò)各個(gè)節(jié)點(diǎn)的位置信息生成鄰接矩陣Φ，矩陣各個(gè)元素的值Φ(i,j)可由下公式確定：

2.1.2 支配集構(gòu)造

中心節(jié)點(diǎn)將鄰接矩陣Φ作為輸入?yún)?shù)，進(jìn)行先深搜索遍歷，并根據(jù)遍歷結(jié)果的深度信息不斷更新目標(biāo)結(jié)果集合R，當(dāng)發(fā)現(xiàn)深度更大的搜索結(jié)果時(shí)清空R，并存入新的遍歷結(jié)果，當(dāng)深度信息相同時(shí)在R中追加遍歷結(jié)果。支配集構(gòu)造算法的程序偽代碼如下：

輸入：網(wǎng)絡(luò)的鄰接矩陣Φ

輸出：臨界矩陣的深度最大的遍歷結(jié)果集合R

2.1.3 支配集優(yōu)化篩選

該步驟是針對(duì)上一步的得到的集合R進(jìn)行負(fù)載優(yōu)化篩選和鏈路消耗篩選。

（1）負(fù)載優(yōu)化篩選

負(fù)載優(yōu)化篩選過(guò)程是針對(duì)R中的每一個(gè)結(jié)果r根據(jù)每個(gè)節(jié)點(diǎn)的度的偏差之和進(jìn)行的篩選過(guò)程。節(jié)點(diǎn)的度越大其負(fù)載就越大。由于節(jié)點(diǎn)負(fù)載的不均衡將會(huì)限制算法的性能，因此，該篩選過(guò)程是一個(gè)均衡負(fù)載的過(guò)程。

遍歷結(jié)果r的不均衡負(fù)載的度Δload(r)的計(jì)算公式如下：

式中：N是節(jié)點(diǎn)個(gè)數(shù)；Wnode(vi)是節(jié)點(diǎn)vi的負(fù)載不均衡度，其計(jì)算方法如下所示：

式中：de(vi)表示在遍歷結(jié)果r中節(jié)點(diǎn)的度；ζ為修正系數(shù)，滿足1 ＜ζ＜2。在本文的定長(zhǎng)分組傳輸模型中，度數(shù)較大的節(jié)點(diǎn)在信息共享過(guò)程中擔(dān)負(fù)的向其鄰居轉(zhuǎn)發(fā)分組的任務(wù)過(guò)重將會(huì)成為算法性能提升的瓶頸節(jié)點(diǎn)。因此，通過(guò)平均負(fù)載的方法能夠較大程度分擔(dān)過(guò)程中節(jié)點(diǎn)的工作量，增大并行通信數(shù)量的目的。經(jīng)過(guò)負(fù)載不均衡度的計(jì)算后，得到更新集合R'=min{Δload(R)}。

當(dāng)|R'|=1 即目標(biāo)集合中只有一個(gè)遍歷結(jié)果時(shí)。該集合中的拓?fù)渚褪亲罱K求得的目標(biāo)解。當(dāng)|R'|≠1 時(shí)，進(jìn)行鏈路消耗篩選過(guò)程。

（2）鏈路耗費(fèi)篩選

鏈路耗費(fèi)篩選的意義是從集合中選擇整體鏈路耗費(fèi)最小的拓?fù)洌瑥亩鴾p少網(wǎng)絡(luò)內(nèi)可能的相互干擾。其篩選過(guò)程如下。

對(duì)于R'中的每一個(gè)構(gòu)造拓?fù)鋜∈R'，求出其鏈路消耗總和：

式中，N為節(jié)點(diǎn)數(shù)目，Φr(i,j)為構(gòu)造拓?fù)鋜對(duì)應(yīng)的包含鏈路權(quán)重的鄰接矩陣中第i行、第j列的元素值。則算法最優(yōu)結(jié)果rbest表達(dá)式如下：

在rbest中，當(dāng)且僅當(dāng)de(vi)≠1 時(shí)vi屬于支配集節(jié)點(diǎn)。至此，連通支配集節(jié)點(diǎn)劃分和信息共享網(wǎng)絡(luò)構(gòu)造完畢。

2.2 通信序列計(jì)算

通信序列計(jì)算是程序P 對(duì)全網(wǎng)節(jié)點(diǎn)的信息共享每個(gè)以時(shí)隙為單位進(jìn)行集中式的貪心調(diào)度的過(guò)程序列。過(guò)程中詳細(xì)記錄各個(gè)節(jié)點(diǎn)在每個(gè)時(shí)隙的天線指向、收發(fā)狀態(tài)、期望收發(fā)數(shù)據(jù)等信息，并將其作為算法執(zhí)行的依據(jù)。它的計(jì)算過(guò)程如下所述。

首先，根據(jù)rbest得到圖的鄰接矩陣Φbest。程序P 按照貪心原則不斷迭代完成一次完整的信息共享過(guò)程。迭代完成得到總的時(shí)隙數(shù)N以及每個(gè)周期網(wǎng)絡(luò)中各節(jié)點(diǎn)的通信序列，即每個(gè)時(shí)隙不同節(jié)點(diǎn)的收發(fā)狀態(tài)以及與之通信的鄰居節(jié)點(diǎn)。

這里需要兩個(gè)概念進(jìn)行說(shuō)明，一個(gè)是N維向量α=(a1,a2,a3…aN)，另一個(gè)是節(jié)點(diǎn)的轉(zhuǎn)發(fā)表項(xiàng)。N為網(wǎng)絡(luò)中節(jié)點(diǎn)的個(gè)數(shù)，向量則表示一個(gè)時(shí)隙中網(wǎng)絡(luò)節(jié)點(diǎn)的被占用狀態(tài)。在每次迭代任務(wù)開始之前，需要α重新置0。過(guò)程中根據(jù)任務(wù)情況不斷調(diào)整各個(gè)分量的值。當(dāng)ai=1 時(shí)表示節(jié)點(diǎn)vi在該時(shí)隙已經(jīng)有將要有通信任務(wù)，當(dāng)ai≠1 表示節(jié)點(diǎn)vi在該時(shí)隙尚未被分配通信任務(wù)。節(jié)點(diǎn)的轉(zhuǎn)發(fā)表是一個(gè)的廣播表，初始時(shí)刻節(jié)點(diǎn)根據(jù)鏈路信息生成針對(duì)自己共享信息的廣播表，在共享過(guò)程中每次接收/發(fā)送消息后都會(huì)不斷更新轉(zhuǎn)發(fā)表的內(nèi)容。

程序P 按照貪心調(diào)度算法進(jìn)行迭代，每次迭代可求出一個(gè)時(shí)隙網(wǎng)絡(luò)節(jié)點(diǎn)的調(diào)度情況。貪心調(diào)度算法的具體流程如下：

輸入：rbest對(duì)應(yīng)的鄰接矩陣Φbest

輸出：調(diào)度序列Seq

下面以3 個(gè)點(diǎn)組成的簡(jiǎn)單網(wǎng)絡(luò)為例簡(jiǎn)單說(shuō)明通信序列的作用。如圖2 所示，網(wǎng)絡(luò)包含3 個(gè)節(jié)點(diǎn)v1、v2、v3。節(jié)點(diǎn)擁有獨(dú)立的轉(zhuǎn)發(fā)表，表的第一列Slot 為時(shí)隙標(biāo)識(shí)，Dest 為定向天線指向的目標(biāo)節(jié)點(diǎn)，State 為收發(fā)狀態(tài)。

因?yàn)榫W(wǎng)絡(luò)中各節(jié)點(diǎn)位置已知，所以可以根據(jù)節(jié)點(diǎn)的編號(hào)對(duì)天線指向進(jìn)行定位。當(dāng)Dest=-1 時(shí)，表示節(jié)點(diǎn)此時(shí)隙處于空閑狀態(tài)。Dest=i且i=-1 時(shí)表示該節(jié)點(diǎn)的天線指向節(jié)點(diǎn)vi的方向。當(dāng)State=0 時(shí)表示節(jié)點(diǎn)處于發(fā)射狀態(tài)，State=1 時(shí)表示節(jié)點(diǎn)處于接收狀態(tài)，同樣當(dāng)節(jié)點(diǎn)在該時(shí)隙不工作時(shí)相應(yīng)的State=-1。

圖2 P 程序構(gòu)造的通信序列

當(dāng)中心計(jì)算節(jié)點(diǎn)得到計(jì)算各節(jié)點(diǎn)的通信序列后，通過(guò)已有的通用的通信協(xié)議將通信序列進(jìn)行全網(wǎng)的分發(fā)。

3 仿真分析

3.1 參數(shù)設(shè)置

為了保持網(wǎng)絡(luò)的連通性本文將網(wǎng)絡(luò)區(qū)域劃分為面積相等的正方形網(wǎng)格，每個(gè)網(wǎng)格內(nèi)只有一個(gè)節(jié)點(diǎn)在網(wǎng)格內(nèi)隨機(jī)分布。且每個(gè)節(jié)點(diǎn)均能夠跟相鄰網(wǎng)格內(nèi)的節(jié)點(diǎn)通信。如圖3 所示，以9 個(gè)節(jié)點(diǎn)組成的網(wǎng)絡(luò)為例介紹拓?fù)錁?gòu)建思想。圖3 中每個(gè)小的正方形代表邊長(zhǎng)為1 km 的正方形小區(qū)，每個(gè)網(wǎng)格內(nèi)只有一個(gè)節(jié)點(diǎn)隨機(jī)分布網(wǎng)格中。9 個(gè)網(wǎng)格共同組成一個(gè)大的通信區(qū)域。同時(shí)，節(jié)點(diǎn)的最大通信半徑設(shè)置為2.9 km，以確保網(wǎng)絡(luò)的連通性。其他仿真參數(shù)設(shè)置如下：時(shí)隙長(zhǎng)tslot=8 ms；分組長(zhǎng)度L=200 kB，通信速率s=2.5 Mb/s；網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)N=4,9,16,25,36,49。

圖3 9 個(gè)節(jié)點(diǎn)的網(wǎng)絡(luò)拓?fù)?/p>

為了確定算法的正確性，引入信息共享完成度的概念，η定義為：

式中：Nget表示接收到的不同的分組的個(gè)數(shù)；Nall為共享完成時(shí)應(yīng)該接收到的分組的個(gè)數(shù)，且滿足Nall=N-1，在數(shù)值上等于網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)減1。一次信息共享過(guò)程不同時(shí)隙節(jié)點(diǎn)不斷收到其他節(jié)點(diǎn)傳輸來(lái)的報(bào)文，完成度不斷增加。當(dāng)接收到所有節(jié)點(diǎn)的報(bào)文時(shí)完成度為1。

3.2 實(shí)驗(yàn)結(jié)果與分析

3.2.1 算法的正確性驗(yàn)證

圖4 展示了9 個(gè)節(jié)點(diǎn)下采用MDST-SB 算法時(shí)不同節(jié)點(diǎn)在一次信息共享過(guò)程中不同節(jié)點(diǎn)的信息共享完成度隨時(shí)隙變化的折線圖。

從第1 個(gè)時(shí)隙末開始，各個(gè)節(jié)點(diǎn)的完成度不斷增長(zhǎng)。8 號(hào)節(jié)點(diǎn)最早在第19 時(shí)隙接收完畢其他節(jié)點(diǎn)的共享分組，直到1 號(hào)節(jié)點(diǎn)最終接收完畢，共經(jīng)歷30 個(gè)時(shí)隙。完成度成階梯狀增長(zhǎng)的原因是因?yàn)楣?jié)點(diǎn)在完成度不增長(zhǎng)的時(shí)段處于發(fā)送或不工作狀態(tài)。只有在接收到一個(gè)新的分組后完成度才會(huì)隨之增長(zhǎng)。

圖4 完成度的增長(zhǎng)曲線

3.2.2 算法有效性驗(yàn)證

當(dāng)節(jié)點(diǎn)的個(gè)數(shù)分別為4、9、16、25、36、9 時(shí)，UxDMA、JazzyMAC、ROMA 和MDST-SB 算法完成信息共享的時(shí)隙關(guān)系如圖5 所示。其中，橫坐標(biāo)為節(jié)點(diǎn)的個(gè)數(shù)，縱坐標(biāo)為耗費(fèi)時(shí)隙數(shù)。由圖5 可知，消耗的時(shí)隙數(shù)隨節(jié)點(diǎn)數(shù)目的增長(zhǎng)而增長(zhǎng)。UxDMA、JazzyMAC、ROMA 算法的增長(zhǎng)速度要遠(yuǎn)遠(yuǎn)快于MDST-SB 算法的增長(zhǎng)速度。這是因?yàn)镸DST-SB 調(diào)度算法充分利用了定向傳輸?shù)目辗謴?fù)用特性增大網(wǎng)絡(luò)中同時(shí)傳輸?shù)膱?bào)文數(shù)目并具有較好的冗余控制能力。而JazzyMAC 算法通過(guò)傳遞令牌的方式雖然能夠避免鏈路沖突，但是限制了網(wǎng)絡(luò)的空分復(fù)用率；UxDMA 算法只通過(guò)隨機(jī)選擇不同的鏈路組合進(jìn)行調(diào)度，但是在轉(zhuǎn)發(fā)分組的選擇上并沒(méi)有有效的控制手段；ROMA 算法通過(guò)隨機(jī)的配對(duì)策略和優(yōu)先級(jí)比較的收發(fā)方案，使其信息共享的效率難以提高。相比與UxDMA，MDST-SB 在時(shí)延上平均可降低42%。

圖5 隨機(jī)拓?fù)湎臅r(shí)隙與節(jié)點(diǎn)數(shù)的關(guān)系

4 結(jié)語(yǔ)

本文提出了基于連通支配集的信息共享算法，該算法構(gòu)造定向傳輸場(chǎng)景下的連通支配集，并通過(guò)均衡網(wǎng)絡(luò)負(fù)載和減小網(wǎng)絡(luò)鏈路耗費(fèi)來(lái)提高共享性能和降低網(wǎng)絡(luò)發(fā)射干擾，從而實(shí)現(xiàn)態(tài)勢(shì)信息的快速共享。仿真分析表明，本文提出的算法相較于傳統(tǒng)的基于UxDMA，JazzyMAC，ROMA 的信息共享算法從空分復(fù)用率、冗余傳輸控制、調(diào)度機(jī)制三個(gè)方面做出了優(yōu)化，從而使性能有較大的提升。未來(lái)工作將主要關(guān)注算法在動(dòng)態(tài)場(chǎng)景下的應(yīng)用，提升算法在工程中的實(shí)用價(jià)值。