定向自組網中基于連通支配集優化的信息共享算法*

程 帥，徐任暉，彭來獻，張 磊，楊曜旗

（陸軍工程大學，江蘇 南京 210007）

0 引言

無線自組織網絡通常采用全向傳輸方式進行通信，因為相比于定向傳輸固有的隱藏節點、耳聾、暴露節點等問題[1]，全向傳輸擁有更加簡單的控制協議。但是在遠距離、大容量通信時通常采用定向傳輸方式，這是由于定向傳輸在相同的發射功率時擁有更遠的傳輸距離和更高的空分復用率，能夠有效減小被監聽、定位的概率，增大網絡容量[1]。無線自組織網絡中的信息共享是每個節點都將自己所擁有的信息傳播到其他節點的行為，以此來完成節點對網絡環境的協同感知[2]。此類信息共享問題也稱為全到全廣播（All-to-All Broadcasting）或流言傳播（Gossiping）問題[3]。在時延敏感型的網絡中，節點需要將通過傳感器采集到的信息快速進行分發，因而需要努力減小信息在共享過程的時延。由于所有節點需要并行地進行消息的分發和轉發，對定向傳輸的調度方法和分發策略等問題提出了嚴峻的挑戰。本文以定向傳輸無線自組網的信息共享為背景，研究在配備了單波束定向天線的通信節點所構成的無線網絡中，高效完成共享戰場態勢信息的方案。

無線自組網中解決全到全的廣播問題時，最簡單的是通過泛洪（Flooding）的方式進行消息的廣播分發[4]，這在規模較小的網絡中是一種簡單可行的信息共享方式。但隨著網絡規模的擴大，由于移動無線自組網固有的動態性和不可預測性[5]，泛洪的方式將會產生嚴重的接入沖突以及信息轉發過程中的冗余傳輸問題，致使信息共享的性能下降，造成大量的帶寬浪費和較高的通信時延。當前，為解決定向傳輸背景下的信息共享，主要是改造典型的UxDMA[6]、JazzyMAC[7]、ROMA[8]等定向MAC 協議[9]，使其能夠完成信息共享。但此類算法不能完全消除冗余傳輸，沒有充分利用定向傳輸的優勢，導致網絡的性能難以提升，信息共享的時效性仍然較差。

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

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

1 系統模型

1.1 節點模型

在有N個節點的無線網絡中，V表示網絡所有節點的集合，任意節點vi∈V={x1,x2,…,xN}均存在一個的隨機位置Location(vi)=(xi,yi)，其中xi表示其橫坐標，yi表示其縱坐標。同時，每個節點都擁有一個可表示其身份的唯一ID，且Id(vi)=i。

1.2 通信模型

為簡化分析，本文中的通信節點均采用最大通信距離為rmax的單波束定向天線，節點vi和vj的距離可以通過下面公式計算：

當dij≤rmax且天線指向相互對準后才能進行通信。

在信道資源使用方面，本文通過將時間劃分為大小相等且為tslot的時間片，即時隙。并以時隙為單位對網絡節點的通信狀態進行調度，在一個時隙內節點只能處于發送或接收狀態之一。

1.3 定長分組傳輸模型

研究信息共享問題需要確定合理的分組傳輸模型，本文采用固定長度的分組。節點vi將需要共享的本地信息mi封裝成長度為L的分組，分組在發送和轉發的過程中不能被拆分和重組。節點發送/接收速率為s，滿足L/s=tslot，即表示一個時隙節點只能發送/接收一個分組。

1.4 問題描述

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

如圖1（a）所示，是4 個節點組成的網絡。初始時刻，節點分別包含的消息集合可表示為：M1={m1},M2={m2},M3={m3},M4={m4}。第一時隙可能的傳輸情況是節點v1發送m1到v2，v4發送m4到v3。因此，第一時隙結束時節點的消息集合狀態為M1={m1}，M2={m1,m2}，M3={m3,m4}，M4={m4}。過程中經過若干次通信后最終達到M1=M2=M3=M4={m1,m2,m3,m4}，即如圖1（d）所示的所有節點均達到信息共享完成狀態。

圖1 固定長度的信息共享模型

在信息共享過程中減小信息共享時延需要重點關注的是兩個方面：冗余傳輸和定向傳輸的空分復用。圖1（c）展示了一種可能的冗余傳輸情況，在中間的某個時隙，v4向v2發送m4，由于v4并不知道在此之前v3已經向v2發送過m4，導致該時隙的傳輸冗余。此外，定向傳輸相對于全向傳輸，可以通過控制波束的寬度、方向以及發射功率等因素，盡量減少對其他節點的干擾。在規模更大的一些網絡中，充分利用定向傳輸的空分復用的特點，可以增大同一時刻并發通信數目，加快信息共享速度。

無線網絡中，一跳可達的網絡場景具備較好的連通性。在此場景下，假設網絡中節點數為N，每一個節點vi都可以直接將自己的信息發送給網絡中的其他節點。因此，一次完整的信息共享網絡中需要轉發的報文數量為N(N-1)。而在本文的通信模型和分組傳輸模型下，一個時隙網絡能夠發送分組的數量最多不超過N/2。因此，一次信息共享需要消耗的時隙數為N(N-1)/N/2。

然而，現實環境下無線網絡中的節點很難做到一跳可達。因此，無論采用什么樣的組網方式和傳播方案，在本文的系統模型下完成一次信息共享完成一次信息共享消耗的時隙數Ncomsume滿足：

同時，信息共享過程中需要交互的報文數量N(N-1)和消耗的總時隙數Ncomsume滿足如下關系：

式中，ni為時隙Slot=i時的網絡節點可以傳輸分組的數量。因此，為了減少共享過程消耗的時隙數目即Ncomsume，需要盡量增大每個時隙可以進行傳輸報文的數量ni。所以該問題可以轉化為求Ncomsume的近似最優解問題。

2 算法設計

MDST-SB 算法是一種靜態網絡下的鏈路調度算法，其過程主要分為連通支配集的構造和鏈路的貪心調度兩個階段。

首先，算法需要根據網絡其他節點位置信息進行連通支配集的初步構造集合。在得到的構造集合中進行優化策略的篩選，刪除次優的構造結果，得到最終的構造網絡并確定支配集節點。接下來，算法以時隙為單位進行集中式的貪心調度，過程中分別記錄各個節點不同時隙的調度狀態。當網絡再次有共享需求時只需將共享的數據封裝成定長分組。并在約定的時刻開始按照既定通信序列進行調度即可完成信息共享。表1 列舉了算法過程中使用的符號。

表1 主要符號說明

2.1 連通支配集的構造

連通支配集的構造分為3 步：鄰接矩陣生成、最大深度搜索和負載及鏈路的優化。鄰接矩陣生成是將實際網絡抽象化處理并作為后續步驟的輸入。最大深度搜索是以鄰接矩陣為輸入進行先深搜索的遍歷。負載優化和鏈路優化將處理的結果進行進一步篩選和優化。

2.1.1 鄰接矩陣生成

中心計算節點根據網絡各個節點的位置信息生成鄰接矩陣Φ，矩陣各個元素的值Φ(i,j)可由下公式確定：

2.1.2 支配集構造

中心節點將鄰接矩陣Φ作為輸入參數，進行先深搜索遍歷，并根據遍歷結果的深度信息不斷更新目標結果集合R，當發現深度更大的搜索結果時清空R，并存入新的遍歷結果，當深度信息相同時在R中追加遍歷結果。支配集構造算法的程序偽代碼如下：

輸入：網絡的鄰接矩陣Φ

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

2.1.3 支配集優化篩選

該步驟是針對上一步的得到的集合R進行負載優化篩選和鏈路消耗篩選。

（1）負載優化篩選

負載優化篩選過程是針對R中的每一個結果r根據每個節點的度的偏差之和進行的篩選過程。節點的度越大其負載就越大。由于節點負載的不均衡將會限制算法的性能，因此，該篩選過程是一個均衡負載的過程。

遍歷結果r的不均衡負載的度Δload(r)的計算公式如下：

式中：N是節點個數；Wnode(vi)是節點vi的負載不均衡度，其計算方法如下所示：

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

當|R'|=1 即目標集合中只有一個遍歷結果時。該集合中的拓撲就是最終求得的目標解。當|R'|≠1 時，進行鏈路消耗篩選過程。

（2）鏈路耗費篩選

鏈路耗費篩選的意義是從集合中選擇整體鏈路耗費最小的拓撲，從而減少網絡內可能的相互干擾。其篩選過程如下。

對于R'中的每一個構造拓撲r∈R'，求出其鏈路消耗總和：

式中，N為節點數目，Φr(i,j)為構造拓撲r對應的包含鏈路權重的鄰接矩陣中第i行、第j列的元素值。則算法最優結果rbest表達式如下：

在rbest中，當且僅當de(vi)≠1 時vi屬于支配集節點。至此，連通支配集節點劃分和信息共享網絡構造完畢。

2.2 通信序列計算

通信序列計算是程序P 對全網節點的信息共享每個以時隙為單位進行集中式的貪心調度的過程序列。過程中詳細記錄各個節點在每個時隙的天線指向、收發狀態、期望收發數據等信息，并將其作為算法執行的依據。它的計算過程如下所述。

首先，根據rbest得到圖的鄰接矩陣Φbest。程序P 按照貪心原則不斷迭代完成一次完整的信息共享過程。迭代完成得到總的時隙數N以及每個周期網絡中各節點的通信序列，即每個時隙不同節點的收發狀態以及與之通信的鄰居節點。

這里需要兩個概念進行說明，一個是N維向量α=(a1,a2,a3…aN)，另一個是節點的轉發表項。N為網絡中節點的個數，向量則表示一個時隙中網絡節點的被占用狀態。在每次迭代任務開始之前，需要α重新置0。過程中根據任務情況不斷調整各個分量的值。當ai=1 時表示節點vi在該時隙已經有將要有通信任務，當ai≠1 表示節點vi在該時隙尚未被分配通信任務。節點的轉發表是一個的廣播表，初始時刻節點根據鏈路信息生成針對自己共享信息的廣播表，在共享過程中每次接收/發送消息后都會不斷更新轉發表的內容。

程序P 按照貪心調度算法進行迭代，每次迭代可求出一個時隙網絡節點的調度情況。貪心調度算法的具體流程如下：

輸入：rbest對應的鄰接矩陣Φbest

輸出：調度序列Seq

下面以3 個點組成的簡單網絡為例簡單說明通信序列的作用。如圖2 所示，網絡包含3 個節點v1、v2、v3。節點擁有獨立的轉發表，表的第一列Slot 為時隙標識，Dest 為定向天線指向的目標節點，State 為收發狀態。

因為網絡中各節點位置已知，所以可以根據節點的編號對天線指向進行定位。當Dest=-1 時，表示節點此時隙處于空閑狀態。Dest=i且i=-1 時表示該節點的天線指向節點vi的方向。當State=0 時表示節點處于發射狀態，State=1 時表示節點處于接收狀態，同樣當節點在該時隙不工作時相應的State=-1。

圖2 P 程序構造的通信序列

當中心計算節點得到計算各節點的通信序列后，通過已有的通用的通信協議將通信序列進行全網的分發。

3 仿真分析

3.1 參數設置

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

圖3 9 個節點的網絡拓撲

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

式中：Nget表示接收到的不同的分組的個數；Nall為共享完成時應該接收到的分組的個數，且滿足Nall=N-1，在數值上等于網絡節點數減1。一次信息共享過程不同時隙節點不斷收到其他節點傳輸來的報文，完成度不斷增加。當接收到所有節點的報文時完成度為1。

3.2 實驗結果與分析

3.2.1 算法的正確性驗證

圖4 展示了9 個節點下采用MDST-SB 算法時不同節點在一次信息共享過程中不同節點的信息共享完成度隨時隙變化的折線圖。

從第1 個時隙末開始，各個節點的完成度不斷增長。8 號節點最早在第19 時隙接收完畢其他節點的共享分組，直到1 號節點最終接收完畢，共經歷30 個時隙。完成度成階梯狀增長的原因是因為節點在完成度不增長的時段處于發送或不工作狀態。只有在接收到一個新的分組后完成度才會隨之增長。

圖4 完成度的增長曲線

3.2.2 算法有效性驗證

當節點的個數分別為4、9、16、25、36、9 時，UxDMA、JazzyMAC、ROMA 和MDST-SB 算法完成信息共享的時隙關系如圖5 所示。其中，橫坐標為節點的個數，縱坐標為耗費時隙數。由圖5 可知，消耗的時隙數隨節點數目的增長而增長。UxDMA、JazzyMAC、ROMA 算法的增長速度要遠遠快于MDST-SB 算法的增長速度。這是因為MDST-SB 調度算法充分利用了定向傳輸的空分復用特性增大網絡中同時傳輸的報文數目并具有較好的冗余控制能力。而JazzyMAC 算法通過傳遞令牌的方式雖然能夠避免鏈路沖突，但是限制了網絡的空分復用率；UxDMA 算法只通過隨機選擇不同的鏈路組合進行調度，但是在轉發分組的選擇上并沒有有效的控制手段；ROMA 算法通過隨機的配對策略和優先級比較的收發方案，使其信息共享的效率難以提高。相比與UxDMA，MDST-SB 在時延上平均可降低42%。

圖5 隨機拓撲消耗時隙與節點數的關系

4 結語

本文提出了基于連通支配集的信息共享算法，該算法構造定向傳輸場景下的連通支配集，并通過均衡網絡負載和減小網絡鏈路耗費來提高共享性能和降低網絡發射干擾，從而實現態勢信息的快速共享。仿真分析表明，本文提出的算法相較于傳統的基于UxDMA，JazzyMAC，ROMA 的信息共享算法從空分復用率、冗余傳輸控制、調度機制三個方面做出了優化，從而使性能有較大的提升。未來工作將主要關注算法在動態場景下的應用，提升算法在工程中的實用價值。