一種基于區(qū)域分裂與合并的勢博弈網(wǎng)絡拓撲控制算法*

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

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

1 引言

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

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

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

2 相關理論與模型

2.1 網(wǎng)絡模型

(1)網(wǎng)絡區(qū)域中的所有節(jié)點ID唯一。

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

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

2.2 勢博弈網(wǎng)絡拓撲模型

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

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

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

(1)

(2)

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

3 分區(qū)域合并與分裂拓撲控制算法

3.1 區(qū)域劃分階段

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

3.2 鄰居發(fā)現(xiàn)階段

3.3 區(qū)域內部博弈階段

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

3.4 分裂與合并階段

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

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

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

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

(3)

(4)

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

3.5 簇首選舉及博弈階段

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

3.6 拓撲維護階段

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

算法1RSMA

輸入：節(jié)點個數(shù)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]作為本文算法對比對象。具體仿真參數(shù)如表1所示。

Table 1 Simulation parameter settings表1 參數(shù)設置

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

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

(5)

其中，Di表示節(jié)點i的節(jié)點度，b表示區(qū)域節(jié)點數(shù)量，a表示所在區(qū)域,N為網(wǎng)絡節(jié)點總數(shù)。

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

(6)

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

(7)

(8)

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

Figure 1 Traditional network link diagram圖1 傳統(tǒng)網(wǎng)絡鏈路圖

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

Figure 2 Partition game link diagram圖2 分區(qū)博弈鏈路圖

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

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

Figure 4 Node clustering diagram圖4 節(jié)點分簇圖

Figure 5 Network topology of cluster head node圖5 簇首節(jié)點網(wǎng)絡拓撲圖

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

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

Figure 6 Comparison of average node degree圖6 平均節(jié)點度對比圖

Figure 7 Comparison of maximum node degree圖7 最大節(jié)點度對比圖

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

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

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

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

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

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

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

5 結束語

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

后續(xù)工作中，將綜合考慮無線傳感器節(jié)點布置的隨機性，根據(jù)其節(jié)點分布情況的特征展開研究，結合真實情況對不同環(huán)境、不同區(qū)域改進算法，進一步優(yōu)化網(wǎng)絡性能。