一種基于區域分裂與合并的勢博弈網絡拓撲控制算法*

魏連鎖，陳齊齊，韓 建，蘇 揚

(齊齊哈爾大學計算機與控制工程學院，黑龍江 齊齊哈爾 161006)

1 引言

無線傳感器網絡WSN (Wireless Sensor Network)是一種由大量分散的微型節點組成的分布式網絡，由于其特殊的地理要求，部署的節點能量有限且不易更換電池，因此在設計無線傳感器網絡時要著重考慮能耗因素與影響[1 - 5]。

近年來，國內外學者提出了大量的拓撲控制算法[6 - 9]。從優化網絡生命周期角度出發，從各方面降低能耗。文獻[10]設計一種基于鏈路能耗博弈的拓撲控制算法，使其節點在最大功率下運行獲取最小跳數，通過最優響應策略選擇收益最大的節點功率和鏈路來降低網絡能耗。隨后Santi等人[11]以節點發射功率和通信范圍內鄰居節點的個數作為因子代入效用函數，提出一種基于博弈論的分布式非合作博弈拓撲控制算法MIA(Max-Improvement Algorithm)，但生成的網絡魯棒性較差，當節點執行順序不同時會生成不同的網絡拓撲結構；之后研究人員在MIA算法的基礎上提出了一種改進算法DIA[12]，該算法雖然能夠保證網絡拓撲結構的唯一性，最小化發射功率，達到納什均衡[13]，但隨著網絡的運行，節點的能量分布差異越來越大。為此，文獻[14]提出一種基于序數勢博弈的網絡拓撲控制算法DEBA(Distributed Energy-Balanced topology control Algorithm)，該算法綜合考慮節點剩余能量和節點功率等因素，結合勢博弈，動態調控網絡，均衡了節點負載，但卻沒有合理考慮網絡連通性和魯棒性問題。文獻[15]通過引入超模博弈理念，將節點度、網絡連通性和MAC層干擾程度融入效用函數中，提出一種跨層優化的WSN能耗均衡拓撲博弈算法COETG(Cross-layer Optimized WSN Energy balanced Topology Game algorithm)，該算法在保證網絡整體連通性的情況下降低了節點發射功率，均衡了網絡能耗。上述網絡拓撲控制算法達到了較好的網絡拓撲控制，在一定程度上提高了網絡性能，但是這些算法沒有考慮網絡節點的密集和稀疏問題，當監測區域中節點數量增加時，將出現個別節點負載過大、部分區域節點分布稀疏或出現瓶頸節點等問題，造成網絡節點能耗不均勻、個別節點過早死亡以及網絡生命周期短。

針對以上問題，本文提出一種基于區域分裂與合并的勢博弈網絡拓撲控制算法RSMA(Region Splitting and Merging Algorithm)。對目標區域進行劃分，區域內部進行博弈生成網絡拓撲結構，對密集區域實行分裂再博弈，減輕節點負載；對稀疏區域進行合并，以保證網絡整體連通。仿真實驗表明，該算法不僅解決了網絡的連通性與密集問題，而且還降低了節點負載，均衡了網絡整體能耗，進一步延長了網絡生命周期。

2 相關理論與模型

2.1 網絡模型

(1)網絡區域中的所有節點ID唯一。

(2)網絡中的每個節點都能獲取通信范圍內鄰居節點的ID、剩余能量、通信距離和節點之間最小通信功率。

(3)能從任意一個節點判斷整個網絡的連通性。

2.2 勢博弈網絡拓撲模型

勢博弈為策略博弈Γ=〈M,S,u(S)〉中的一種，主要包含3個要素，參與者M、策略空間S和效用函數u(S)，具體說明如下：

參與者M={1,2,…,m}表示博弈參與者集合，參與者數量為m；策略空間S是Si(i∈M)的笛卡爾積，若參與者i存在k個可選策略，則Si={s1,s2,…,sk}。通常用s=(si,s-i)∈S表示一個策略集合，其中si表示參與者i的策略選擇，s-i表示其余參與者的策略選擇；效用函數集合u表示為：u={u1,u2,…,um}，其中ui表示參與者i在策略集合(si,s-i)中所得到的效用值。

在網絡拓撲控制博弈模型搭建中，最重要的部分即為效用函數的建立。效用函數表示網絡中每個節點連入網絡中所能產生的效用值。在網絡中，對于網絡中任意一個節點i，節點的效用函數定義如式(1)所示：

(1)

(2)

其中，fi(pi,p-i)表示其網絡的連通性，通過深度遍歷算法判斷每一個節點接入網絡時，網絡是否連通。當fi(pi,p-i)=1時網絡連通，表示節點i可通過網絡鏈路與其他所有節點進行通信；當fi(pi,p-i)=0時網絡不連通，則節點i接入網絡時所產生的效用值為負數，在網絡拓撲搭建時基本上可以忽略該功率下節點i接入網絡的可能。α和β是權重因子，且α,β>0；pi表示節點發射功率；Eo(i)為節點i初始能量；Er(i)為節點i剩余能量；j為節點i當前功率pi下的鄰居節點，Eo(j)為節點j初始能量;Er(j)為節點j剩余能量。在效用函數中綜合考慮了網絡整體連通性、鄰居節點剩余能量和節點發射功率等因素。

3 分區域合并與分裂拓撲控制算法

3.1 區域劃分階段

當在監測區域內節點布署較多的情況下，生成的網絡拓撲結構局部區域會呈現出2種極端情況：部分節點負載過重以及出現瓶頸節點(在通信半徑內無鄰居節點或是網絡整體不連通)。針對這2種極端情況，本文提出區域劃分策略，按照實際情況將監測區域劃分為若干子區域。區域劃分策略有效控制了節點通信范圍內的鄰居節點個數，同時也降低了瓶頸節點產生的機率，保證了網絡連通性。

3.2 鄰居發現階段

3.3 區域內部博弈階段

各區域內部中所有節點輪流執行博弈，在每輪博弈中只有一個節點調整其發射功率,代入式(1)中獲取其對應效用值，選取最大效用值對應發射功率作為節點最終發射功率。此時，根據網絡中所有節點最終發射功率更新鄰居節點集合以及生成區域內部網絡拓撲結構。當每一個節點對應功率下的效用值達到最大時，且不存在隨意調整任意節點的功率使其網絡效用值變大，此時網絡達到一種最佳動態平衡，即納什均衡[13]。

3.4 分裂與合并階段

區域內部網絡拓撲結構生成后，在小概率下依然會出現部分子區域節點負載過重，以及出現瓶頸節點，為此本文提出區域內部的分裂與合并策略，進一步優化節點負載和瓶頸節點。在完成分區域博弈后，遍歷整個網絡中的所有節點，分別對節點度超過閾值的區域與出現瓶頸節點的區域進行標記。

對于節點度超過閾值的區域，其能量消耗過快，導致網絡整體能耗不均勻，考慮到延長網絡生命周期，本文對此區域進行左右均等分裂，對分裂后的子區域再次執行博弈后生成新的網絡拓撲結構。

對于存在瓶頸節點的區域，由于其整體網絡不連通，在此對該區域實行合并操作。通過鏈路權值函數計算得到瓶頸節點與其他節點所有鏈路對應效益值，并選取最大效益值對應鏈路，更新鄰居節點集合，生成新的網絡拓撲結構。

鏈路權值函數如式(3)所示：

(3)

(4)

其中，k1、k2表示權值調節系數，且k1+k2=1。Eij(t)表示節點剩余能量。LQij(dij)表示節點i與節點j之間的通信鏈路質量，γ為鏈路質量調節系數，γ越大表示鏈路質量LQij(dij)隨距離d(i,j)變化越敏感。鏈路權值函數ωij(t)綜合了網絡的通信質量和能耗均衡，當節點剩余能量降低時，權值函數中能耗權值占比增加，隨著網絡運行，能夠自適應地提高自身能耗均衡的效果。

3.5 簇首選舉及博弈階段

為了將網絡中所有節點連成一個整體，在所有子區域內部選舉簇首節點，執行博弈后生成對應網絡拓撲結構?？紤]到節點轉發跳數過多將影響網絡生命周期，本文在區域內部選取簇首節點時著重考慮節點的節點度，即優先考慮在一跳范圍內連接節點較多的節點，并綜合其鄰居節點集合選取簇首節點，對每個子區域選取一個簇首節點。簇首節點選取后調整其通信半徑，以最大功率廣播消息后獲取簇首鄰居節點集合，并按照不同節點間通信功率生成對應簇首策略集合，執行博弈后更新鄰居節點集合并生成簇首網絡拓撲結構。

3.6 拓撲維護階段

考慮到無線傳感器網絡中每個節點收發數據量不一致，在網絡長時間運行時導致節點能量消耗不均衡，以至于部分節點過早死亡，影響網絡整體生命周期，因此本文設定當網絡中出現節點的剩余能量低于預先設置的閾值時(低于初始能量的20%)，該節點廣播拓撲維護請求，請求重新執行算法生成新的網絡拓撲結構，以均衡節點能耗，進一步延長網絡生命周期。算法實現偽代碼如算法1所示：

算法1RSMA

輸入：節點個數N,通信半徑rc,初始能量Er,剩余能量Eo。

輸出：neb_i。

2.Determine the neighbor nodesneb_i；

3.Determine the power for nodei；

4.computehavilable communication power values of nodei；

5.foralli≤Ndo

6 Choose power based on；

10.endif

11. Updatepi,update neighbor；

12.iflen(neb_i)≥value；

13. Split district；

14.endif

15.ifdistrictfi(pi,p-i)=0；

16. Merge district；

17.endif

18. Select cluster；

19. cluster game；

20.ifEr≤min_value

21. Re-executes the algorithm;

22.endif

23.endfor

4 仿真結果及分析

本文采用PyCharm2019仿真軟件進行實驗仿真,分別選取DEBA算法[14]、COETG算法[15]作為本文算法對比對象。具體仿真參數如表1所示。

Table 1 Simulation parameter settings表1 參數設置

仿真實驗的性能評價指標為:

(1)平均節點度：每個傳感器節點度之和與網絡節點總數之比，計算方式如式(5)所示：

(5)

其中，Di表示節點i的節點度，b表示區域節點數量，a表示所在區域,N為網絡節點總數。

(2)網絡生命周期：本文設置網絡生命周期計算公式如式(6)所示：

(6)

(3)剩余能量標準差：網絡剩余能量平均值與每個節點剩余能量的標準差，計算方式如下：

(7)

(8)

為了客觀展示本文提出的區域劃分以及分裂、合并策略相比傳統算法的優勢，在區域內布置節點數量較多情況下對比DEBA算法產生的網絡鏈路結構。如圖1所示，當區域內部署節點數量較多時，DEBA算法表現出網絡通信鏈路過于復雜，出現了瓶頸節點；易造成網絡整體能耗不均衡、網絡不連通以及網絡生命周期短。顯然在節點數量布置過多的情況下，該算法不太實用。

Figure 1 Traditional network link diagram圖1 傳統網絡鏈路圖

在本文提出的區域策略劃分下，網絡整體鏈路如圖2所示，區塊內部網絡鏈路清晰，有效減少了冗余鏈路。而在分裂與合并策略下優化的網絡鏈路如圖3所示，進一步減少了冗余鏈路，并解決了瓶頸節點問題，且各區域網絡處于連通狀態。

Figure 2 Partition game link diagram圖2 分區博弈鏈路圖

Figure 3 Split and merge game link diagram圖3 分裂、合并博弈鏈路圖

在執行區域劃分策略以及分裂、合并策略后，區域內部節點分簇、簇首節點網絡拓撲如圖4和圖5所示，在簇首機制下節點通信鏈路清晰，網絡整體連通。

Figure 4 Node clustering diagram圖4 節點分簇圖

Figure 5 Network topology of cluster head node圖5 簇首節點網絡拓撲圖

為了更客觀地反映本文算法的性能，本文進行了5組對比實驗，節點數量從250依次增加到600，通過觀察3種算法在網絡平均節點度、最大節點度、平均發射功率、平均生命周期和剩余能量標準差5個方面的表現來進行對比。

圖6和圖7顯示了3種算法的網絡平均節點度和最大節點度對比。在本文提出的RSMA算法中，隨著節點數量增加，平均節點度趨于穩定；而DEBA算法和COETG算法在節點數量增加時，節點度也隨著攀升，當節點個數增加至一定數量時，平均節點度與最大節點度出現跳躍式增長。由于本文RSMA算法考慮到節點分布時呈現隨機性，當區域節點數量增加時，網絡冗余鏈路隨之提升，而冗余鏈路將導致部分節點的節點度過大，因此RSMA算法將冗余鏈路過大區域進行分割，有效地減少了冗余鏈路，降低了部分節點的節點度，故網絡平均節點度與最大節點度相對較低。

Figure 6 Comparison of average node degree圖6 平均節點度對比圖

Figure 7 Comparison of maximum node degree圖7 最大節點度對比圖

圖8為3種算法的節點平均發射功率，可以看出，本文提出的RSMA算法具有很好的穩定性，且平均發射功率低于DEBA算法的，COETG算法在節點較少的情況下節點平均發射功率較低，但穩定性不強，當節點數量超過一定限度時，功率隨之急速增加。由于RSMA算法采取區域劃分策略，降低了區域內部節點通信能耗，而分裂機制有效緩解了節點負載，所以整體上降低了節點平均發射功率。

Figure 8 Comparison of average transmit power圖8 平均發射功率對比圖

圖9為3種算法的網絡平均生命周期(式(6))的對比圖，可以看出網絡平均生命周期隨著節點數量的增加而變短，但本文提出的RSMA算法網絡生命周期相比其他2種算法表現出較好的穩定性，隨著節點數量增加波動較小。由于RSMA算法加入了分裂、合并策略，在保證網絡連通的情況下以較低的功率構建網絡拓撲結構，有效地降低了節點能耗，從而延長了網絡平均生命周期。

Figure 9 Comparison of average life cycle圖9 平均生命周期對比圖

節點剩余能量標準差由式(7)和式(8)計算得到，3種算法的網絡節點剩余能量標準差具體情況如圖10所示。

可以看出，DEBA算法和COETG算法的剩余能量標準差上升較快，因為其部分節點負載過大，消耗能量較快；而對于其產生的瓶頸節點而言，節點消耗忽略不計，從而導致網絡整體能耗不均衡，節點剩余能量標準差過大。而本文提出的RSMA算法綜合考慮了這2種因素，降低了密集區域節點負載，增加了稀疏區域節點連通性，且自適應調節機制動態地均衡了網絡整體能耗，降低了網絡整體節點剩余能量標準差。

Figure 10 Comparison of residual energy standard deviation圖10 剩余能量標準差對比圖

5 結束語

本文綜合考慮了鏈路冗余、節點負載、瓶頸節點和生命周期等問題，采用勢博弈理論，劃分目標區域并結合分裂、合并策略，提出了一種基于區域分裂與合并的勢博弈網絡拓撲控制算法RSMA。其中區域劃分策略有效剔除了冗余鏈路，分裂與合并策略有效均衡了節點負載，解決了瓶頸節點問題，并保證了網絡整體連通性。仿真結果表明，對比現有算法，RSMA算法生成的網絡拓撲結構中平均節點度下降18%，最大節點度下降49%，平均發射功率下降25%，平均生命周期提高31%，剩余能量標準差下降20%，整體提升了網絡性能。

后續工作中，將綜合考慮無線傳感器節點布置的隨機性，根據其節點分布情況的特征展開研究，結合真實情況對不同環境、不同區域改進算法，進一步優化網絡性能。