一種分布式無線網(wǎng)絡自適應拓撲抗毀性優(yōu)化機制*

毛建兵，鄧偉華

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

0 引言

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

分布式網(wǎng)絡的拓撲結(jié)構(gòu)影響著網(wǎng)絡的通信性能和抗毀性能[4]?；诜植际骄W(wǎng)絡的多智能體系統(tǒng)應用中，一致性協(xié)議的收斂速率跟網(wǎng)絡拓撲密切相關。相關研究表明，一階多智能體系統(tǒng)在漸進收斂的一致性協(xié)議驅(qū)動下，系統(tǒng)的收斂速度由分布式網(wǎng)絡拓撲的代數(shù)連通度所決定。網(wǎng)絡拓撲的代數(shù)連通度越大，其一致性協(xié)議的收斂速率越高[5]。

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

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

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

1 網(wǎng)絡模型及相關定義

1.1 網(wǎng)絡模型

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

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

1.2 代數(shù)連通度

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

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

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

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

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

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

2 優(yōu)化機制與算法設計

2.1 主要思路

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

2.2 冗余節(jié)點分析

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

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

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

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

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

圖1給出了一種鄰域網(wǎng)絡拓撲，通過對網(wǎng)絡拓撲進行冗余節(jié)點分析，節(jié)點1成為鄰域范圍內(nèi)的冗余節(jié)點。

圖1 鄰域網(wǎng)絡拓撲

2.3 拓撲優(yōu)化策略

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

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

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

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

2.4 算法工作流程

網(wǎng)絡中一個節(jié)點可能被多個鄰居節(jié)點選取為冗余節(jié)點。定義節(jié)點i的冗余權(quán)重參數(shù)wi為節(jié)點被k跳鄰域范圍內(nèi)鄰居節(jié)點選中為冗余節(jié)點的重數(shù)。權(quán)重參數(shù)wi越大，表明冗余節(jié)點在k跳鄰域范圍內(nèi)對鄰居節(jié)點拓撲的影響越小。因此，在拓撲優(yōu)化過程中，算法將優(yōu)先對權(quán)重更高的冗余節(jié)點進行優(yōu)化移動。

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

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

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

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

（4）節(jié)點計算冗余權(quán)重參數(shù)wi，并在鄰域內(nèi)進行通告。k跳鄰域范圍內(nèi)，權(quán)重參數(shù)wi最大的冗余節(jié)點Rx優(yōu)先調(diào)度用于執(zhí)行拓撲優(yōu)化。

（5）冗余節(jié)點Rx選取k跳鄰域范圍內(nèi)代數(shù)連通度λ(Gi)最小的節(jié)點為優(yōu)化目標節(jié)點Obji。

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

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

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

3 仿真分析

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

圖2 網(wǎng)絡拓撲示例（N=9）

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

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

圖3 網(wǎng)絡拓撲示例（N=50）

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

圖5給出了通過算法冗余節(jié)點分析得到的全網(wǎng)各個節(jié)點的冗余權(quán)重參數(shù)wi結(jié)果，其中wi=0表明節(jié)點非冗余節(jié)點?？梢钥吹?，全網(wǎng)僅少部分節(jié)點被選取為冗余節(jié)點。全網(wǎng)有N=50個節(jié)點，冗余節(jié)點僅選出其中7個節(jié)點，不到全網(wǎng)節(jié)點數(shù)的15%。執(zhí)行拓撲優(yōu)化的冗余節(jié)點數(shù)較少，避免了算法執(zhí)行中大量網(wǎng)絡節(jié)點移動部署產(chǎn)生的較高代價，減小了對網(wǎng)絡節(jié)點應用任務的影響。

圖5 節(jié)點冗余權(quán)重wi的計算結(jié)果

圖6給出了圖3所示隨機網(wǎng)絡拓撲執(zhí)行拓撲優(yōu)化后的最終網(wǎng)絡拓撲結(jié)構(gòu)狀態(tài)?？梢钥闯?，優(yōu)化后的網(wǎng)絡拓撲節(jié)點之間連接更為緊密，能夠更好地應對部分節(jié)點損毀導致的拓撲連接中斷或是分裂。

圖6 優(yōu)化后網(wǎng)絡拓撲（N=50）

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

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

4 結(jié)語

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