一種分布式無線網絡自適應拓撲抗毀性優化機制*

毛建兵，鄧偉華

（中國電子科技集團公司第三十研究所，四川 成都 610041）

0 引言

在Ad hoc分布式無線網絡中，網絡可靠連通是發揮網絡效能的重要基礎[1]，拓撲控制是增強網絡連通性和抗毀性的重要手段[2]。通常對網絡采取拓撲控制決策，需要首先獲取網絡當前的拓撲狀態信息。對于較大規模的網絡而言，獲取全網拓撲信息需要網絡節點之間進行大量的控制信令交互，這些交互將為網絡帶來大量的通信開銷，甚至產生“信令風暴”這一不良影響，加重網絡負擔[3]。因此，為了彌補全網拓撲信息獲取的不足，基于局部網絡拓撲信息實現分布式網絡自適應拓撲控制優化的方法被提出，這是網絡抗毀性增強研究的一個重要方向。

分布式網絡的拓撲結構影響著網絡的通信性能和抗毀性能[4]。基于分布式網絡的多智能體系統應用中，一致性協議的收斂速率跟網絡拓撲密切相關。相關研究表明，一階多智能體系統在漸進收斂的一致性協議驅動下，系統的收斂速度由分布式網絡拓撲的代數連通度所決定。網絡拓撲的代數連通度越大，其一致性協議的收斂速率越高[5]。

在網絡抗毀性研究方面，基于代數連通度的方法從圖的頻譜角度進行拓撲結構的抽象分析[6]。網絡拓撲的代數連通度越大，直接反映出網絡的抗毀性和魯棒性越好[7]。代數連通度分析在各類網絡的設計與研究中都扮演著重要的角色[7-8]。

為獲得代數連通度最大的網絡拓撲，相關研究將拓撲優化問題建模為數學優化問題，并利用優化算法進行求解。但最大化代數連通度的優化問題并不是一個嚴格凸的規劃問題，而已被證明是一個NP難問題[5]。不僅如此，一般網絡拓撲的優化問題通常也同樣是一個NP難問題[9]。因此，啟發式算法被設計用于提高網絡的代數連通度，從而得到較優的網絡拓撲。

針對分布式無線網絡，本文研究提出了一種自適應網絡拓撲抗毀性優化機制，并設計了分布式啟發式算法。通過利用代數連通度計算對節點k跳鄰域范圍內的網絡拓撲結構進行分析，選取其中的冗余節點，然后對冗余節點進行局部移動，調整優化網絡拓撲結構，實現網絡整體代數連通的提升，增強網絡抗毀性能力。仿真分析結果表明，所提算法能夠顯著有效改善網絡的連通性和抗毀性，大幅提升網絡的代數連通度。

1 網絡模型及相關定義

1.1 網絡模型

考慮無線網絡由N個節點構成，N個節點根據應用或任務需要，部署工作在一定區域范圍內，形成一個多跳的無線自組織網絡。非鄰居節點可通過其他節點提供的路由中繼服務實現多跳連通。網絡中節點可根據需要移動，并改變網絡的拓撲形態。網絡中節點通過路由協議的拓撲學習功能，可以掌握鄰近k跳范圍內節點之間的連接信息，獲得k跳鄰域網絡拓撲。

為了描述方便，本文以圖論模型的無向圖G=(V,E)來表示網絡拓撲，其中，V為網絡中的節點集合，E為網絡中節點之間的鏈路集合。如果網絡中兩個節點vi，vj可以直接通信，則兩個節點之間存在一條鏈路e(vi,vj)∈E。拓撲圖G中節點的度定義為節點連接的鏈路數目。網絡中兩個節點vi，vj之間的跳數定義為連接vi和vj路徑的最小鏈路數。

1.2 代數連通度

設A(G)是網絡拓撲圖G的鄰接矩陣表示，其表達式為：

式中：矩陣元素aij=1表示節點vi,vj之間存在鏈路；否則，aij=0。特別地，aii=0。

以D(G)表示圖G各節點的度所構成的對角矩陣，則有：

以L(G)表示圖G的拉普拉斯矩陣（Laplacian matrix），其計算表示為：

拉普拉斯矩陣L(G)是一個實對稱矩陣，其特征值均為非負實數，最小的特征值是0，全部N個特征值經排序后可以表示為0=λ1≤λ2≤…≤λN。圖G的代數連通度表示為λ(G)，其值為矩陣L(G)的第二小特征值，即有：

相關研究指出[5-6]，網絡拓撲圖的代數連通度越大，表明網絡的連通性越好，網絡拓撲具有更好的魯棒性和抗毀性。

2 優化機制與算法設計

2.1 主要思路

對于大規模網絡而言，獲取全網拓撲信息往往存在一定困難，同時網絡節點數量越多，計算網絡拓撲圖矩陣信息及拓撲優化調整的維度也越大，因此優化過程的計算復雜度非常高，難以求得優化解。在此條件下，為了增強網絡的抗毀性能，提高整體網絡拓撲的代數連通度，引入啟發式算法實現網絡中節點分布式自適應地拓撲優化調整。本文研究的啟發式算法設計，從評估節點鄰近k跳范圍的網絡拓撲出發，選取對局部網絡拓撲連通性影響最小的冗余節點，小范圍內調整優化這類節點的位置部署，以提高局部k跳鄰域范圍內的網絡拓撲代數連通度。通過網絡中各個節點分布式自適應優化動作，提升各所在局部鄰域網絡拓撲的代數連通度，并經過多次迭代優化，最終實現網絡整體代數連通度和抗毀性能的總體提升。

2.2 冗余節點分析

定義冗余節點為k跳鄰域范圍內網絡拓撲刪除該節點后對代數連通度下降影響最小的節點。以Gi表示節點i獲取的k跳鄰域范圍內網絡拓撲圖，Gi′表示圖Gi刪除節點i及與節點i相關的連接邊后的子圖。分別計算Gi和Gi′的代數連通度，對應表示為λ(Gi)和λ(Gi′)。計算節點i刪除后代數連通度變化的歸一化值ηi：

式（5）中，由于λ(Gi′)≥0，有ηi≤1。

節點計算ηi后，將結果ηi在k跳鄰域范圍內進行通告，同時也收集其他節點通告的計算結果。設節點i在k跳鄰域范圍內共有Ni個節點，相應代數連通度變化的歸一化值計算表示為ηj，1≤j≤Ni。節點i通過比較ηj，確定k跳鄰域范圍內的冗余節點。若鄰域節點m滿足：

則節點m即為節點i在k跳鄰域范圍內的一個冗余節點。為了使得拓撲優化在達到一定條件時消除冗余節點，并且算法終止，這里設置閾值參數α，要求冗余節點滿足ηm≤α。

在評估網絡拓撲過程中，k取值越大，獲取的鄰域范圍內網絡拓撲信息越多，則對冗余節點的判定就越準確。通常網絡條件下，設置k=2。特別說明，如果節點i是一個割點，刪除節點i后，網絡拓撲不連通，代數連通度計算有λ(Gi′)=0，相應有ηi=1。割點是拓撲連通的關鍵節點，不能被選為冗余節點，因此ηi=1的節點不能判定為冗余節點。除去特殊的鏈狀網絡拓撲結構，節點k跳鄰域范圍內ηj(1≤j≤Ni)的最小值ηm通常有ηm＜1。

圖1給出了一種鄰域網絡拓撲，通過對網絡拓撲進行冗余節點分析，節點1成為鄰域范圍內的冗余節點。

圖1 鄰域網絡拓撲

2.3 拓撲優化策略

冗余節點移動部署的目的在于提升k跳鄰域范圍網絡拓撲的代數連通度。因此，所針對的目標節點應該是k跳鄰域范圍內網絡拓撲代數連通度較小的節點。本文算法按k跳鄰域范圍內節點代數連通度λ(Gi)進行排序，從λ(Gi)最小的節點開始選取為目標節點Obji執行拓撲優化操作。

一個節點k跳鄰域范圍內拓撲代數連通度較小，說明節點的k跳鄰居之間的相互連接不夠緊密。利用冗余節點進行拓撲優化的目的是盡可能地強化鄰居節點之間的連接關系。同時，還需要兼顧冗余節點只在鄰近范圍內近距離移動，避免遠距離、大范圍的移動影響節點執行應用任務。

對于目標節點Obji，如何通過冗余節點Rx移動增加其鄰域范圍內的連接，使得目標節點拓撲的代數連通度得到最大的改善，是優化設計需要追求的目標。相關研究指出，通過向給定圖中添加邊來最大化代數連通度是一個困難的組合問題，其難以求得確定的最優解[5]。

受文獻[10]研究的啟發，連接拓撲圖中最小度節點與邊距離（最短路徑上包含的邊數）最大的節點可以較大程度上提高代數連通度的大小。本文算法設計連接目標節點Obji的k跳鄰域范圍內的最小度節點Vd，以及最小度節點k跳范圍內跳數h最大并且歐式距離d最近的節點Vh。為了限制冗余節點的移動范圍，約束在冗余節點Rx的k跳鄰域范圍內搜尋目標節點Obji鄰域的最小度節點Vd，并且距離d要求不超過節點通信半徑r的2倍。為了連接節點Vd和Vh，冗余節點Rx需要向節點Vd和Vh的中間位置進行移動部署。針對特殊通信環境，也可以利用無線傳播模型進行鏈路預測分析，尋找最佳的移動部署位置。

2.4 算法工作流程

網絡中一個節點可能被多個鄰居節點選取為冗余節點。定義節點i的冗余權重參數wi為節點被k跳鄰域范圍內鄰居節點選中為冗余節點的重數。權重參數wi越大，表明冗余節點在k跳鄰域范圍內對鄰居節點拓撲的影響越小。因此，在拓撲優化過程中，算法將優先對權重更高的冗余節點進行優化移動。

算法設計主要工作流程如下：

（1）節點i采集k跳鄰域范圍內的局部網絡拓撲信息，計算鄰域拓撲圖Gi，生成鄰接矩陣A(Gi)，并計算代數連通度λ(Gi)。

（2）計算節點i刪除后代數連通度變化的歸一化值ηi，并向k跳鄰域內節點進行通告。節點i同時也收集鄰域內其他節點通告的信息。

（3）節點i選取k跳鄰域范圍內ηm=min{ηj,1≤j≤Ni}且ηm≤α的節點m為冗余節點，并向鄰域內節點進行通告。

（4）節點計算冗余權重參數wi，并在鄰域內進行通告。k跳鄰域范圍內，權重參數wi最大的冗余節點Rx優先調度用于執行拓撲優化。

（5）冗余節點Rx選取k跳鄰域范圍內代數連通度λ(Gi)最小的節點為優化目標節點Obji。

（6）在目標節點Obji與冗余節點Rx共同的k跳鄰域范圍內搜尋最小度節點Vd，以及最小度節點k跳范圍內跳數h最大并且歐式距離d最近的節點Vh。

（7）根據鏈路預測分析，將冗余節點Rx向連接節點Vd和Vh的最佳位置進行移動部署。

（8）重復上述算法步驟，直至所有冗余節點完成自適應優化移動部署，網絡中不再存在冗余節點，或者冗余節點對目標節點Obji代數連通度λ(Gi)的優化提升小于預期目標。

3 仿真分析

通過軟件模擬，對提出的拓撲抗毀性優化機制進行了仿真。默認情況下，設置節點通信半徑r=5 km，參數α=0.1。為了比較直觀地顯示拓撲優化帶來的效果，首先針對圖2（a）所示的一個小型網絡拓撲進行仿真試驗。仿真網絡拓撲圖中節點以圓圈表示，虛線表示節點間鏈路，數字標注表示節點的編號。優化前網絡拓撲的代數連通度為λ(G)=0.538 6；執行算法優化，網絡拓撲調整后的結構狀態如圖2（b），其中代數連通度為λ(G)=0.982 5。可見，網絡拓撲的代數連通度得到了大幅度提升，提升幅度達到82.4%。直觀來看，優化后的網絡拓撲中節點6的鄰居節點之間的連接更為緊密了，其割點身份消除了，并且優化后的網絡拓撲中也不再存在割點。

圖2 網絡拓撲示例（N=9）

進一步地，將拓撲優化算法應用于更復雜的大規模網絡。設置網絡分布場景大小為20 km×20 km，N=50個節點以均勻概率隨機部署在場景內，生成的網絡拓撲如圖3所示。

對圖3所示隨機網絡拓撲進行了k跳鄰域范圍內局部拓撲代數連通度的計算分析，其結果如圖4所示。同時，對全網拓撲的代數連通度進行計算，結果有λ(G)=0.196 2。對比結果可以看出，當k=2時，鄰域范圍內拓撲的代數連通度λ(Gi)最小值已經很接近全網拓撲的代數連通度λ(G)計算結果。因此，通過拓撲優化提升k=2跳鄰域范圍內的λ(Gi)最小值，可以達到間接提升全網拓撲的λ(G)的目的。

圖3 網絡拓撲示例（N=50）

圖4 k跳鄰域范圍拓撲代數連通度計算

圖5給出了通過算法冗余節點分析得到的全網各個節點的冗余權重參數wi結果，其中wi=0表明節點非冗余節點。可以看到，全網僅少部分節點被選取為冗余節點。全網有N=50個節點，冗余節點僅選出其中7個節點，不到全網節點數的15%。執行拓撲優化的冗余節點數較少，避免了算法執行中大量網絡節點移動部署產生的較高代價，減小了對網絡節點應用任務的影響。

圖5 節點冗余權重wi的計算結果

圖6給出了圖3所示隨機網絡拓撲執行拓撲優化后的最終網絡拓撲結構狀態。可以看出，優化后的網絡拓撲節點之間連接更為緊密，能夠更好地應對部分節點損毀導致的拓撲連接中斷或是分裂。

圖6 優化后網絡拓撲（N=50）

針對圖3所示網絡拓撲的優化結果，圖7給出了算法迭代運行過程中全網拓撲代數連通度λ(G)的結果變化。經過算法的多次迭代，最終網絡拓撲的代數連通度提升到了λ(G)=0.502 6，與初始網絡拓撲的代數連通度λ(G)=0.196 2相比，提升幅度達到了156.2%。可見，所提算法對網絡拓撲的抗毀性優化效果顯著，并且優化過程僅需較少的迭代次數。

圖7 算法多次迭代過程中全網λ(G)變化

4 結語

拓撲優化控制能夠使得分布式無線網絡的連通性和抗毀性得到顯著改善，并維持在一個較高的水平。對于拓撲不斷變化的網絡而言，根據實時網絡拓撲分析進行自適應優化控制顯得非常必要。針對獲取全網拓撲信息受限的大規模網絡，本文提出了一種基于鄰域網絡拓撲信息的自適應抗毀性優化機制，并設計了啟發式算法。通過算法的迭代運行，自適應選取網絡中的冗余節點，并將冗余節點在小范圍內局部移動，使得網絡拓撲結構的連通性和抗毀性得到改善。仿真實驗結果表明，所提算法能夠有效提升整體網絡的代數連通度和抗毀性。