面向定向天線無線網絡的快速廣播算法*

覃遠超，趙澤才

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

0 引 言

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

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

1 模型與問題描述

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

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

2 問題分析

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

證明 對于任意節點而言，至少需經過N-1次接收，方可獲得網絡中所有其他節點的報文，因此，為完成信息共享，全網至少需要進行N(N-1)次通信。考慮到一個時隙內，全網最多同時支持N/2次通信（N為偶數）或(N-1)/2次通信（N為奇數），因而至少需2(N-1)個時隙（N為偶數）或2N個時隙（N為奇數），方能完成信息共享。

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

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

結論2 若網絡中存在分割指數為K（K≥2）的割點，則完成信息共享所需的時間至少為KN，其中N為網絡節點數。

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

3 廣播調度算法的設計

廣播調度算法決定各個時隙內哪些節點發送，哪些節點接收，以及收發的內容是什么。在任意時隙的開始時刻，廣播調度算法計算出廣播調度表

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

3.1 隨機選擇算法

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

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

設網絡拓撲用無向圖G=表示，其中V為頂點集，E為邊集。隨機選擇算法的輸入為網絡拓撲G，輸出為廣播調度表T。隨機選擇算法的描述如圖1所示：

圖1 隨機選擇（RS）算法

在所有節點均掌握全網拓撲的前提下，可以通過設置相同的隨機數生成算法和隨機數種子，來實現鄰居節點間的收發同步。

3.2 編碼隨機選擇算法

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

3.3 最大差異度優先算法

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

MDF算法的輸入為網絡拓撲G，接收矩陣R，輸出為廣播調度表T。MDF算法的描述如圖2所示。

圖2 最大差異度優先（MDF）算法

3.4 編碼最大差異度優先算法

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

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

4 仿真結果

4.1 隨機拓撲

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

圖3 隨機生成的網絡拓撲

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

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

4.2 規則拓撲

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

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

圖4 規則網絡拓撲

表2 規則拓撲中的信息共享時間

4.3 拓撲特性的影響分析

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

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

圖5 d=15時，拓撲5和拓撲6中的節點鄰接關系

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

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

圖6 4種特殊拓撲

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

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

5 結論及下一步研究工作

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

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