基于最大完全子圖與最小樹形圖的無線定向網絡廣播算法

鈕金鑫

(中國西南電子技術研究所第二事業部, 成都 610036)

定向天線可將能量輻射至空間特定方向,因此可有效提升天線收發增益,增強接收信噪比,進而提升通信距離,提高通信系統的抗干擾性能,減小端到端路由跳數?；诙ㄏ蛱炀€的通信系統目前已廣泛應用于5G通信[1-3]、車聯網[4-11]、軍事通信[12-13]等領域。

采用定向天線雖然可為通信系統帶來較大增益,但會降低廣播業務通信效率,主要體現在：節點采用全向天線發送消息,在其通信范圍內的所有一跳鄰居節點均可收到該消息,而采用定向天線后,只有波束覆蓋范圍內的鄰居節點可收到消息,若要實現消息廣播,中繼節點需多次調整波束指向覆蓋所有鄰居節點,導致定向廣播過程需要占用更多通信資源。因此,如何有效提升廣播效率,節省通信資源是定向廣播領域需要研究的關鍵問題。

現有關于廣播算法的研究主要分為全向廣播和定向廣播兩大類。全向廣播研究起步較早,其中,文獻[14-15]提出了基于連通支配集的廣播算法,該算法以網絡全局拓撲信息為輸入,將連通支配集中的節點作為中繼節點,實現全網廣播。文獻[16-17]以部分拓撲信息為輸入,利用不同節點鄰居集合的包含關系,以逐級擴散的方式指派部分節點作為中繼節點實現全網廣播。文獻[18]提出自裁剪算法,以兩跳范圍內的拓撲信息為輸入迭代選擇中繼節點。文獻[19]提出了一種應用于礦山應急網絡中的網狀網路由協議。定向廣播相關研究主要以全向廣播為理論基礎,將其擴展至定向通信場景,主要分為概率性廣播及確定性廣播兩大類。概率性定向廣播算法[20-21]以提升網絡中所有節點的覆蓋概率為目標,求解每個節點的轉發概率,當概率超出門限值時節點在特定方向上轉發消息。確定性定向廣播算法通過指定中繼節點的方式,將源節點產生的消息可靠發送至所有節點。文獻[22]以全向網絡的自裁剪算法為基礎,將中繼節點及其一跳鄰居視為可被波束覆蓋的節點,利用兩跳鄰居信息計算未覆蓋節點集合,進而求解中繼節點。文獻[23-24]采用基于鏈路消減的廣播算法,在給定扇區劃分策略的條件下,利用兩跳鄰居信息計算中繼節點。文獻[25]提出了基于貪婪搜索及流言擴散機制的中繼節點選擇算法確保中繼節點信息轉發可覆蓋全網節點。

車聯網領域涉及定向廣播的相關研究中,通常以給定道路模型作為先驗條件,以基站作為中心節點,利用網絡全局拓撲信息計算中繼節點,根據道路方向確定信息傳播方向[4-7]。文獻[8]將所有節點分布區域劃分為多個區,通過網絡分區技術減少車聯網中緊急消息傳播冗余,提升分組遞交率。文獻[9]在考慮車輛距離、車輛密度、波束樣式等因素的情況下分析了毫米波車聯網的定向廣播范圍。文獻[10]在車聯網場景下提出了一種基于速率與位置信息的廣播策略,用于改善端到端時延及分組遞交率。文獻[11]提出了一種基于位圖的多跳廣播協議降低消息轉發時延和碰撞概率。但上述關于車聯網的廣播策略均未給出定向網絡場景下的波束指向設置方法。

在部分定向網絡接入協議的相關研究中提出了定向波束干擾避免策略,從而提升廣播消息遞交率。文獻[26]研究了定向時分多址(time division multiple access,TDMA)網絡中減小定向天線信息傳播沖突的傳輸資源分配策略,提升了時隙利用率。文獻[27]通過設計基于RTS(request to send)/CTS(clear to send)的接入機制,避免了多節點同時進行數據傳輸的波束重疊干擾問題。但上述研究僅給出如何避免波束干擾的策略,仍未提出如何設置定向波束指向從而提升傳輸效率。

綜上所述,現有關于定向廣播的研究主要集中于在定向組網場景下如何選擇中繼節點,對于中繼節點的波束指向計算及廣播效率提升方面還存在局限性,主要體現在：確定性定向廣播算法雖然可以通過中繼節點選擇保證全網覆蓋性,但未說明中繼節點如何計算波束指向,無法保證中繼節點通過較少的轉發次數覆蓋全網所有節點;車聯網定向廣播依據基站提供的全局網絡信息及道路模型尋找中繼節點及計算波束指向,適用場景受限。

若要提升定向廣播效率,使用較少轉發次數覆蓋網絡中所有節點,需聯合考慮以下兩點：①波束指向計算,即如何選擇波束指向能夠使單個波束盡量覆蓋較多節點,提升傳輸效率;②中繼節點選擇,即如何選擇中繼節點,能夠使網絡中所有中繼節點的轉發次數之和盡量小,提升全網廣播效率。

現提出一種基于最大完全子圖與最小樹形圖的無線定向網絡廣播算法(maximum complete subgraph and minimum arborescence based directional broadcasting algorithm,MCSMA)。MCSMA算法適用于分布式定向組網場景。算法首先根據最大完全子圖理論給出覆蓋節點數量最多的波束指向計算方法,然后利用最小樹形圖理論求解中繼節點及其波束指向,最終達到減小消息轉發次數,提升廣播效率的目的。

1 場景模型

考慮圖1所示的分布式定向網絡。網絡中各節點裝配波束自適應天線,可任意設置波束指向(如自適應相控陣天線,可通過裝配多副天線實現全空域覆蓋)。天線波束覆蓋范圍為錐形區域[17],波束寬度為θ,定向傳輸范圍為d。對于節點u、v,若節點v在節點u的傳輸覆蓋范圍內,則稱v為u的一跳鄰居節點。位于v傳輸范圍內、u傳輸范圍外的節點為u的兩跳鄰居節點。在時分多址接入框架下,源節點采用天線的定向模式向鄰居節點發送數據,鄰居節點采用天線的全向模式(或通過多副定向天線同時輻射的方式)接收數據,并可通過全向模式獲取兩跳鄰居信息[22-23,28]。

圖1 場景示意圖

在分布式網絡場景下,各節點無法獲取網絡全局拓撲信息。為便于描述波束指向,每個節點將自身所處位置作為坐標原點,將水平面作為xy平面,將垂直于水平面向上的方向作為z軸方向,如圖2所示。以節點u所在位置為原點按上述方法構建的坐標系,定義為節點u的波束指向坐標系。

圖2 波束指向坐標系

2 問題描述

考慮如圖3(a)所示的通信場景,源節點u需將消息廣播至網絡中其他節點。若u按圖3(b)所示方式選擇錯誤的中繼節點r,或中繼節點r按圖3(c)所示方式選擇錯誤的波束指向,均可能增加消息轉發次數。只有聯合考慮中繼節點選擇及波束指向計算,才能達到減小消息轉發次數、提升廣播效率的目的,如圖3(d)所示。

圖3 定向廣播問題說明示意圖

全向網絡中,尋找最優中繼節點集合可建模為最小連通支配集求解問題,即使在獲得全局網絡拓撲信息的條件下,該問題仍為NP完全問題[18]。相比于全向網絡,定向網絡除需尋找最優中繼節點集合外,還需求解最優波束指向保證通過少量波束覆蓋多數節點,求解復雜度進一步增加。此外,分布式組網場景下節點無法直接獲得全局拓撲信息,獲取全局最優廣播策略難度較大。因此,需通過設計啟發式算法求解能夠減少消息轉發次數的高效定向廣播方案。

從以下兩方面出發獲得高效定向廣播方案：①利用最大完全子圖理論,通過一跳鄰居節點位置信息求解最優波束指向,使單個波束能夠覆蓋最多數量的鄰居節點,提升覆蓋效率;②以波束指向計算方法為基礎,利用最小樹形圖理論,通過兩跳鄰居信息確定中繼節點集合及對應波束指向,減少廣播過程中的消息轉發次數。

3 MCSMA算法

3.1 基于最大完全子圖的波束指向算法

基于最大完全子圖的波束指向算法目的是求解能夠覆蓋最多鄰居節點的波束指向,通過較少波束覆蓋所有鄰居節點。算法將源節點與鄰居節點之間的鏈路建模為平面圖的頂點,在夾角小于波束寬度的鏈路對應的頂點之間添加邊,形成無向圖。通過求解無向圖的最大完全子圖,獲得夾角小于波束寬度的最大鏈路集合,該集合對應的所有鄰居節點均可被源節點產生的單個波束覆蓋,進一步根據鄰居節點位置信息確定波束指向,達到單個波束覆蓋多個鄰居節點的目的。

算法1基于最大完全子圖的波束指向算法。

執行對象：鏈路源節點u。

輸出：u的指向列表。

步驟4計算圖G1的最大完全子圖對應的頂點集合為S。

步驟5計算節點u與集合S對應鄰居節點間的最大距離rmax。

步驟6在u的指向坐標系內,將u與集合S對應所有節點的連線長度延長至rmax,計算集合S對應的所有節點按該方法處理后的坐標,并以所有處理后的坐標為對象,分別求解x、y、z坐標軸上的最小值和最大值,記為xmin、xmax、ymin、ymax、zmin、zmax。

步驟8在圖G1的點集合中,去除波束指向覆蓋范圍內鏈路對應的頂點及與其向關聯的邊,重新執行步驟4,直至圖G1為空圖。

算法1中,步驟1用于計算節點與其一跳鄰居節點之間鏈路的夾角;步驟2、步驟3根據節點與一跳鄰居之間的鏈路夾角關系創建圖G1;步驟4利用最大完全子圖理論確定可被單個波束覆蓋的最大鄰居節點集合,任一求解最大完全子圖的算法均可帶入至步驟4;步驟5～步驟7用于在節點的指向坐標系中確定能夠覆蓋鄰居數量最多的波束指向;步驟8用于迭代計算能夠覆蓋所有一跳鄰居節點的波束指向。

3.2 MCSMA算法

以定向廣播覆蓋網絡所有節點為約束條件,若要提升定向廣播效率,需使源節點與所有中繼節點的波束數量之和最小。MCSMA算法基本思想是將源節點與其一跳鄰居節點建模為平面圖的頂點,源節點至鄰居節點的通信鏈路建模為二維平面圖的有向邊,將源節點指向鄰居節點的波束內可覆蓋節點總數量的倒數作為有向邊的權值,利用兩跳鄰居信息及算法1求解以源節點為根節點,可到達所有一跳鄰居且權值最小的有向樹(即求解有向圖的最小樹形圖),進而求得中繼節點集合及對應指向,達到通過少量波束覆蓋所有鄰居節點的目的。MCSMA算法無需網絡全局拓撲信息,僅需兩跳鄰居信息,適用于分布式網絡。

算法2MCSMA算法。

執行對象：廣播消息源節點或迭代過程產生的中繼節點,用u表示。

輸出：Ru、Pu、P′u。

步驟1初始化Ru、Pu、P′u為空集;若其他節點已指定u的指向,則將該指向加入Pu。

步驟5求解G2的最小樹形圖G′2。

步驟6G′2中,對于以u為起點的所有有向邊e(u,v),若存在有向邊e(v,m),則節點v為u選定的中繼節點,更新Ru;有向邊e(u,v)對應的波束指向為u的波束指向,更新Pu;以v為起點的有向邊對應的波束指向為v的指向,更新P′u。

分布式網絡中,任意節點均可能指定本節點為中繼節點,并為本節點指定波束指向,因此算法2的步驟1用于初始化節點指向集合;步驟2～步驟4用于構建有向賦權圖,節點與鄰居之間的鏈路建模為圖的有向邊,根據算法1計算波束指向,根據波束覆蓋范圍內的節點數量確定邊權值,覆蓋節點數越多邊權值越小;由于在步驟3中,源節點需以一跳鄰居為對象執行算法1,因此該步驟需用到兩跳鄰居信息;步驟5、步驟6通過求解最小樹形圖確定節點自身的波束指向、中繼節點集合、中繼節點波束指向,由于最小樹形圖在有向圖的所有樹形圖中權值最小,而權值越小,對應鏈路的波束指向覆蓋的節點越多,因此利用最小樹形圖求解的中繼節點及波束指向可達到用少量波束覆蓋多數鄰居節點的目的,節省廣播過程中的信息轉發次數

定理1圖G2存在至少一個以算法2執行對象為根的最小樹形圖。

證明：另算法2執行對象為u。G2的頂點集合由u及其一跳鄰居節點映射而成,u通過算法1計算得出的波束指向可覆蓋u的所有一跳鄰居節點,因此在圖G2中,節點u到其他鄰居之間必然存在一條由u指向鄰居節點的有向邊,故圖G2中必然存在一個以u為根節點的最小樹形圖。

定理2分布式組網場景中,MCSMA算法可覆蓋全網所有節點。

證明：源節點u執行算法2后,通過指定中繼節點及其波束指向,可保證覆蓋一跳傳輸范圍內的所有節點。各中繼節點以自身為算法2執行對象,繼續計算下一級中繼節點及指向,可保證源節點u兩跳傳輸范圍內的節點均被至少一個中繼節點的一個波束指向覆蓋。新生成的中繼節點繼續迭代執行算法2,可保證全網節點均被覆蓋。

4 仿真分析

仿真過程設置天線波束寬度為30°。節點隨機分布在500 m×500 m×500 m的三維區域內,定向天線傳輸范圍為100 km。節點數量考察范圍為3～20。仿真迭代次數設置為500。

為考察MCSMA算法在網絡覆蓋程度和廣播效率方面的性能,采用以下兩種方案作為對比方案。

(1)DSP(directional self-pruning)算法[22]。根據DSP算法確定中繼節點。由于DSP算法未說明如何設置波束指向,因此仿真過程假定若源節點或中繼節點發現未被波束覆蓋的鄰居節點,則直接將波束指向該鄰居節點。

(2)DSP算法加入波束指向優化。以DSP算法為基礎確定中繼節點,當通過未被波束覆蓋的鄰居節點確定波束指向后,將波束內的所有節點均判定為已覆蓋。

仿真過程通過考察源節點和中繼節點的波束指向比對不同算法的覆蓋情況,通過計算源節點和中繼節點的波束數量比對不同算法的廣播效率。

為考察不同算法的波束覆蓋情況,設置節點數量為15,分布情況如圖4所示。在該場景下, MCSMA算法、DSP算法、DSP算法加入波束指向優化的波束覆蓋情況分別如圖5～圖7所示?？梢钥闯?DSP算法中每個波束覆蓋的節點數量較少,相比于DSP算法,MCSMA及加入波束指向優化后的DSP算法中的一個波束均可覆蓋多個節點。MCSMA利用基于最大完全子圖的波束指向設置算法可通過一個波束覆蓋多個相近位置節點,因此覆蓋效率最高,覆蓋所有網絡所有節點需要的波束總數最少。

紅色圓點表示節點,每個紅色圓點代表一個節點

紅色圓點表示節點,每個紅色圓點代表一個節點

紅色圓點表示節點,每個紅色圓點代表一個節點

紅色圓點表示節點,每個紅色圓點代表一個節點

在不同節點數量場景下,MCSMA算法、DSP算法、DSP算法加入波束指向優化3種算法所需的波束數量和中繼數量分別如圖8、圖9所示。仿真過程取3種算法500次迭代的平均值作為仿真結果。如圖8所示,DSP算法所需的波束數量最多,原因是DSP算法僅以未覆蓋的鄰居節點為中心確認波束指向,效率較低,隨著網絡節點數增加,所需的波束數量增長較快。MCSMA算法所需的波束數量最少,原因是MCSMA算法一方面利用最大完全子圖理論計算能夠覆蓋多個鄰居的波束指向,另一方面通過最小樹形圖理論選取能夠用少量波束覆蓋多數鄰居的節點作為中繼節點,減少源節點和中繼節點在廣播過程中產生的波束數量,提升了廣播效率。如圖9所示,相比于DSP算法,MCSMA算法產生更多中繼節點,是因為MCSMA算法通過恰當選擇中繼節點及轉發指向的方式,達到中繼節點在廣播過程所需的波束數量最低的目的,實現了高效定向廣播。

圖8 不同節點數場景下波束數量對比

圖9 不同節點數場景下中繼節點數量對比

5 結論

為提升無線定向網絡廣播效率,提出一種基于最大完全子圖和最小樹形圖的定向廣播算法。MCSMA算法首先利用最大完全子圖理論計算波束指向,使單個波束覆蓋的節點數量最大,然后利用最小樹形圖理論計算中繼節點及其波束指向,減小定向廣播過程中的消息轉發次數。仿真結果表明,MCSMA算法在保證網絡所有節點均被波束覆蓋的約束下,通過中繼節點選擇及波束指向計算,可減少廣播過程中的波束數量,提升廣播效率。以MCSMA算法為基礎,設計適用于分布式定向網絡的廣播協議作為后續研究問題。