面向定向天線無線網(wǎng)絡(luò)的快速廣播算法*

覃遠超，趙澤才

（中國人民解放軍92830部隊，海南 ?？?571122）

0 引 言

與全向天線相比，定向天線能夠顯著提升無線網(wǎng)絡(luò)容量[1]，并具備更好的安全性和抗干擾能力。對于較高頻段的微波通信而言，采用定向天線是必然的選擇。當(dāng)前，隨著無線通信速率的飛速提升，以及智能天線技術(shù)的快速發(fā)展，采用定向天線已成為民用5G移動通信系統(tǒng)[2]以及多種先進軍事無線通信系統(tǒng)[3]的必然選擇。然而，定向天線在帶來諸多優(yōu)勢的同時，卻給無線網(wǎng)絡(luò)廣播算法的設(shè)計帶來了挑戰(zhàn)。特別對于軍用通信網(wǎng)絡(luò)而言，由于信息分發(fā)、態(tài)勢信息共享等重要業(yè)務(wù)都是廣播業(yè)務(wù)，因此，設(shè)計面向定向天線無線網(wǎng)絡(luò)的、快速高效的廣播算法就具有非常重要的意義。當(dāng)前，針對定向天線無線網(wǎng)絡(luò)中的廣播算法的研究，主要針對一個接入點（Access Point，AP）、多個客戶端（Client）的場景，且采用的天線模型均為定向發(fā)送、全向接收。文獻[4]基于一個中心AP和多個Client所構(gòu)成的網(wǎng)絡(luò)場景中，分析了在考慮到信道容量的差異的前提下，如何實現(xiàn)最小時延廣播的問題。文獻[5]基于同樣的網(wǎng)絡(luò)場景，將文獻[4]所提出的問題作了進一步的推廣，討論了在使用多波束定向天線，并且發(fā)射能量在不同的波束之間不均勻分配的前提下，如何實現(xiàn)最小時延廣播的問題。文獻[6]同樣基于一個AP，多個Client的網(wǎng)絡(luò)場景，針對多媒體業(yè)務(wù)廣播的特殊需求，提出了相應(yīng)的組播組劃分及天線調(diào)度策略。

本文研究采用窄波束定向發(fā)送、定向接收的多跳無線網(wǎng)絡(luò)中的最小時延廣播算法的設(shè)計問題。定向發(fā)送、定向接收能夠最大限度的實現(xiàn)空間復(fù)用，提升網(wǎng)絡(luò)容量，增強通信的保密性和抗干擾能力，對于軍事通信系統(tǒng)而言也具有非常重要的價值[3][4]。同時，相對于單跳網(wǎng)絡(luò)，研究多跳網(wǎng)絡(luò)中的廣播問題更具有一般性的意義。

1 模型與問題描述

假設(shè)網(wǎng)絡(luò)中共包括N個節(jié)點，各節(jié)點的通信距離均為R。所有節(jié)點均采用窄波束的定向天線進行定向收發(fā)，不考慮無線信號干擾。假設(shè)網(wǎng)絡(luò)工作在同步的方式，時間被劃分為連續(xù)、等長的時隙；在1個時隙內(nèi)，節(jié)點可發(fā)送或者接收1個報文。假設(shè)所有信道無誤碼、無丟包。

將時間劃分為連續(xù)的通信時隙。在0時隙，節(jié)點ni擁有且僅擁有報文pi，i∈[1,N]。此后，所有節(jié)點將其所擁有的報文在全網(wǎng)進行廣播，直至任意節(jié)點均擁有報文p1,p2,…,pN。上述過程是一次全體到全體的廣播（All-to-all Broadcast），簡稱為信息共享。之所以研究全體到全體的廣播問題，是因為在軍事通信網(wǎng)絡(luò)中的一類重要業(yè)務(wù)，即態(tài)勢信息共享，就是典型的全體到全體廣播。本文所研究的最小時延廣播問題所探究的，是如何安排各個時隙內(nèi)節(jié)點間的通信關(guān)系以及通信內(nèi)容（也即，如何進行廣播調(diào)度），使得完成信息共享所需的時間最短。

2 問題分析

結(jié)論1 假設(shè)網(wǎng)絡(luò)節(jié)點數(shù)為N，則完成信息共享的最短時間為2(N-1)（N為偶數(shù)）或2N（N為奇數(shù)）。若網(wǎng)絡(luò)拓撲是全連通的full mesh結(jié)構(gòu)，則上述下限是可達的。

證明 對于任意節(jié)點而言，至少需經(jīng)過N-1次接收，方可獲得網(wǎng)絡(luò)中所有其他節(jié)點的報文，因此，為完成信息共享，全網(wǎng)至少需要進行N(N-1)次通信?？紤]到一個時隙內(nèi)，全網(wǎng)最多同時支持N/2次通信（N為偶數(shù)）或(N-1)/2次通信（N為奇數(shù)），因而至少需2(N-1)個時隙（N為偶數(shù)）或2N個時隙（N為奇數(shù)），方能完成信息共享。

若網(wǎng)絡(luò)拓撲是full mesh結(jié)構(gòu)，且N為偶數(shù)，則容易給出一種節(jié)點收發(fā)配對方式，使得恰好經(jīng)過2(N-1)個時隙，全網(wǎng)可完成信息共享。若N為奇數(shù)，則可以在網(wǎng)絡(luò)中增加一個虛擬節(jié)點，此時網(wǎng)絡(luò)節(jié)點數(shù)N+1為偶數(shù)，因而遵循偶數(shù)個節(jié)點時的收發(fā)配對方式，恰好經(jīng)過2(N+1-1)=2N個時隙，全網(wǎng)可完成信息共享。

定義1 設(shè)網(wǎng)絡(luò)拓撲用無向圖G=表示，其中V為頂點集，E為邊集。對于任意頂點v∈V，將v及所有和v相連的邊從G中刪除，所得到的新的拓撲記作Gv′。若Gv′包含K（K≥2）個互不連通的子圖，則稱頂點v為圖G的割點，稱K為頂點v的分割指數(shù)。

結(jié)論2 若網(wǎng)絡(luò)中存在分割指數(shù)為K（K≥2）的割點，則完成信息共享所需的時間至少為KN，其中N為網(wǎng)絡(luò)節(jié)點數(shù)。

證明 不妨設(shè)節(jié)點v為分割指數(shù)為K的割點。對于v而言，至少需N-1次接收，方能獲得網(wǎng)絡(luò)中所有其他節(jié)點的信息。此外，為了幫助其他節(jié)點轉(zhuǎn)發(fā)報文，至少需(K-1)(N-1)次發(fā)送；為了將自己的報文廣播給其他所有節(jié)點，至少需K次發(fā)送。故節(jié)點v所需的總的發(fā)送次數(shù)為(K-1)(N-1)+K次?？紤]到在一個時隙內(nèi)，v要么發(fā)送，要么接收，故至少需N-1+(K-1)(N-1)+K=KN個時隙，節(jié)點v方能完成其所承擔(dān)的所有通信任務(wù)。因此，全網(wǎng)完成信息共享所需的時間至少為KN。

3 廣播調(diào)度算法的設(shè)計

廣播調(diào)度算法決定各個時隙內(nèi)哪些節(jié)點發(fā)送，哪些節(jié)點接收，以及收發(fā)的內(nèi)容是什么。在任意時隙的開始時刻，廣播調(diào)度算法計算出廣播調(diào)度表

其中si為發(fā)送節(jié)點，di為接收節(jié)點，pi為通信內(nèi)容。廣播調(diào)度算法的設(shè)計目標是使得完成信息共享所需的時間最短。本節(jié)按照從簡單到復(fù)雜的順序，依次給出4種廣播調(diào)度算法，分別是隨機選擇（Random Selection，RS）算法、編碼隨機選擇（Random Selection with Network Coding，RS-NC） 算 法、 最大差異度優(yōu)先（Max Discrepancy First，MDF）算法和編碼最大差異度優(yōu)先（Max Discrepancy First with Network Coding，MDF-NC）算法。RS算法需要維護本地接收狀態(tài)表；RS-NC算法不需要維護任何接收狀態(tài)信息；MDF和MDF-NC算法則需要維護全局接收狀態(tài)表。

3.1 隨機選擇算法

隨機選擇（Random Selection，RS）算法的基本思想是每個時隙隨機的選擇一些節(jié)點對進行通信，通信雙方的收發(fā)關(guān)系隨機決定。任意節(jié)點i維護有一個本地的接收狀態(tài)表Li，Li是一個N×N的矩陣，若節(jié)點j是節(jié)點i的鄰居節(jié)點，則Li的第j行就記錄了節(jié)點i和節(jié)點j的報文交互情況。假設(shè)節(jié)點i向節(jié)點j發(fā)送了一個報文p，則節(jié)點i將Li的第j行第p列置為1，而節(jié)點j需將Lj的第i行、第p列和第j行、第p列均置為1。發(fā)送節(jié)點根據(jù)本地接收狀態(tài)表，判斷哪些報文鄰居節(jié)點已經(jīng)擁有，從而避免重復(fù)發(fā)送。

為了更準確的獲得鄰居節(jié)點的報文接收信息，發(fā)送節(jié)點可以將其本地接收狀態(tài)表附帶在發(fā)送報文中一并發(fā)送。例如，節(jié)點i在向節(jié)點j發(fā)送報文時，可以將Li的第i行附帶在報文中一同發(fā)給節(jié)點j（所增加的通信開銷為N比特）。這樣，節(jié)點j在收到報文后，將Lj的第j行、第p列置為1，且將Lj的第i行置為Li的第i行。

設(shè)網(wǎng)絡(luò)拓撲用無向圖G=表示，其中V為頂點集，E為邊集。隨機選擇算法的輸入為網(wǎng)絡(luò)拓撲G，輸出為廣播調(diào)度表T。隨機選擇算法的描述如圖1所示：

圖1 隨機選擇（RS）算法

在所有節(jié)點均掌握全網(wǎng)拓撲的前提下，可以通過設(shè)置相同的隨機數(shù)生成算法和隨機數(shù)種子，來實現(xiàn)鄰居節(jié)點間的收發(fā)同步。

3.2 編碼隨機選擇算法

編碼隨機選擇（Random Selection with Network Coding，RS-NC）算法在確定收發(fā)關(guān)系時所采用的方法和隨機選擇算法一致；其與隨機選擇算法的不同之處是每次通信中節(jié)點發(fā)送的內(nèi)容為其當(dāng)前所擁有的報文的隨機線性組合，而非原始報文（圖1中的步驟3）。節(jié)點在接擁有了N個線性無關(guān)的編碼報文之后，即可解碼得到原始的N個報文。此外，由于不需要維護任何接收狀態(tài)信息，故更新接收狀態(tài)信息的過程也可省略（圖1中的步驟5）。

3.3 最大差異度優(yōu)先算法

最大差異度優(yōu)先（Max Discrepancy First，MDF）算法的設(shè)計思想是優(yōu)先選擇存在鄰居關(guān)系，且當(dāng)前所擁有的信息的差異度最大的節(jié)點對進行通信。MDF算法需維護接收矩陣R，設(shè)其第i行、第j列的元素為rij。若rij為1，則表示節(jié)點i已經(jīng)接收到了節(jié)點j的報文；否則，rij為0。在0時隙，?i,j∈[1,N]，rii=1，rij=0(i≠j)；隨后每個時隙結(jié)束時，均需要更新R。節(jié)點i和節(jié)點j之間的信息差異度D(i,j)定義為節(jié)點i的接收向量（R的第i行）和節(jié)點j的接收向量（R的第j行）的異或向量的元素之和，即

MDF算法的輸入為網(wǎng)絡(luò)拓撲G，接收矩陣R，輸出為廣播調(diào)度表T。MDF算法的描述如圖2所示。

圖2 最大差異度優(yōu)先（MDF）算法

3.4 編碼最大差異度優(yōu)先算法

編碼最大差異度優(yōu)先（Max Discrepancy First with Network Coding，MDF-NC）算法確定收發(fā)關(guān)系的方法和MDF算法相同。與MDF算法的不同之處在于每次通信中節(jié)點發(fā)送的內(nèi)容為其當(dāng)前所擁有的報文的隨機線性組合，而非原始報文。此外，MDF-NC算法計算節(jié)點的信息差異度的方法和MDF算法也有所區(qū)別。假設(shè)Ci和Cj分別為節(jié)點i和節(jié)點j當(dāng)前所接收到的線性無關(guān)的編碼報文系數(shù)矩陣，則節(jié)點i和節(jié)點j之間的信息差異度D′(i,j)定義為

其中Rank(X)為矩陣X的秩。

4 仿真結(jié)果

4.1 隨機拓撲

仿真實驗假設(shè)網(wǎng)絡(luò)中共包含N=20個節(jié)點，分布在40×40的正方形區(qū)域內(nèi)，節(jié)點的通信距離為d=20。假設(shè)鏈路誤碼率為0，且不考慮定向天線波束的旁瓣干擾，以及主瓣的共線干擾。仿真工具為Matlab 2017a。

圖3 隨機生成的網(wǎng)絡(luò)拓撲

表1給出了4個隨機拓撲中的信息共享的時間，RS算法和MDF算法的結(jié)果為100次仿真的平均值；其它算法的結(jié)果為20次仿真的平均值。

表1 隨機拓撲中的信息共享時間

4.2 規(guī)則拓撲

生成規(guī)則拓撲的參數(shù)條件和生成隨機拓撲時的參數(shù)條件一致。手工生成的規(guī)則拓撲如圖4所示。

表2給出了4個規(guī)則拓撲中的信息共享的時間，RS算法和MDF算法的結(jié)果為100次仿真的平均值；其它算法的結(jié)果為20次仿真的平均值。

圖4 規(guī)則網(wǎng)絡(luò)拓撲

表2 規(guī)則拓撲中的信息共享時間

4.3 拓撲特性的影響分析

表3給出了通信距離d取不同值時，拓撲1～8中節(jié)點的平均鄰居數(shù)、最小鄰居數(shù)以及相應(yīng)的信息共享時間。RS算法和MDF算法的結(jié)果為100次仿真的平均值；其它算法的結(jié)果為20次仿真的平均值。

表3 不同拓撲特性下的信息共享時間

圖5 d=15時，拓撲5和拓撲6中的節(jié)點鄰接關(guān)系

對比表3中d=15和d=30的信息共享時間可以看出，總體而言，平均鄰居數(shù)越大，即網(wǎng)絡(luò)連通性越好，則信息共享所需的時間越少?？梢姡畔⒐蚕頃r間受網(wǎng)絡(luò)拓撲特性的影響較大；然而，這種拓撲特性并不能簡單的用平均鄰居數(shù)和最少鄰居數(shù)來衡量。例如，當(dāng)d=15時，拓撲5和拓撲6的平均鄰居數(shù)和最少鄰居數(shù)均相等，但是此時兩者的信息共享時間卻相差較大。究其原因，是因為d=15時，拓撲5中并不存在割點，而拓撲6中卻存在分割指數(shù)K為2和3的割點，如圖5所示。由結(jié)論2可知，拓撲6中信息共享的時間至少為60；MDF-NC算法給出的結(jié)果為66，比理論下限高出了10%。

為了進一步考察拓撲特性對于信息共享時間的影響，我們設(shè)計了幾種特殊拓撲用于仿真實驗，如圖6所示。這4種特殊拓撲中均包含多個割點，其中拓撲9中割點的最大的分割指數(shù)為2；拓撲10中割點的最大的分割指數(shù)為3；拓撲11和拓撲12中割點的最大的分割指數(shù)均為4。

圖6 4種特殊拓撲

表4給出了圖6所示的4種特殊拓撲中的信息共享時間。RS算法和MDF算法的結(jié)果為100次仿真的平均值；其它算法的結(jié)果為20次仿真的平均值。表4中的“理論下限”是根據(jù)本文第2節(jié)的結(jié)論2計算得到的。

表4 特殊拓撲中的信息共享時間

5 結(jié)論及下一步研究工作

本文主要得出了如下結(jié)論。首先，最大差異度優(yōu)先（MDF）算法能夠獲得最佳的性能，但同時其所需要的決策信息也最多。其次，信息共享時間受網(wǎng)絡(luò)拓撲特性的影響較大，割點是制約信息共享時間的一個重要因素。最后，在強連通網(wǎng)絡(luò)中，應(yīng)用網(wǎng)絡(luò)編碼可減少決策信息依賴，簡化算法設(shè)計；在弱連通網(wǎng)絡(luò)中，應(yīng)用網(wǎng)絡(luò)編碼的意義不大。

下一步的研究工作，可以從以下兩個方面展開。首先，本文所有的仿真實驗中均假設(shè)信道誤碼率為0，需要進一步分析鏈路丟包率對于算法性能的影響，并完成從理想算法到實用協(xié)議的設(shè)計轉(zhuǎn)變。其次，對于多波束模型下，最小時延信息共享算法的設(shè)計問題展開研究。