基于能量加權的無線傳感器網絡拓撲抗毀算法

劉玉偉， 陳雯柏，馬 航，蘭少峰，吳 昊

(北京信息科技大學 自動化學院， 北京 100020)

無線傳感器網絡(Wireless Sensor Networks，WSNs)以網絡節點輕便、廉價、低功耗且易自組織和信息采集等特點被廣泛應用于軍事、安防等各種復雜場景[1-3]，是當前物聯網的重要部分和研究熱點。如今，5G技術興起并迅速發展，以低延遲、高速率傳輸等優點，促進了傳感器節點越來越多的應用到窄帶物聯網(NB-IoT)的部署方案中，將位置、圖像、天氣等大量數據信息收集注入到網絡中，使信息得到更廣泛有效的利用；同時，移動5G網絡將使無線通信設備如無線傳感器節點在軍用通信系統中實現更高效的應用[4]。而無線傳感器節點具有能量有限且易受外界復雜因素影響的特點，如何利用拓撲控制提高網絡的抗毀性，進而保證網絡執行各種復雜任務的能力，對無線傳感網絡應用具有重要意義[5]。

拓撲控制是節點以一定的規則進行鄰居節點的選擇并形成優化網絡結構的過程，是網絡實現協議的基礎，形成的拓撲結構是網絡生存的根基。為了延長拓撲中傳感器節點的使用壽命，Fujii S等[6]提出了簇頭選擇和旋轉等理論。 Zebbane B等[7]提出了一種基于組的能量守恒協議(Group-based Energy Conservation Protocol,GECP)，通過傳感器節點之間的睡眠調度來延長網絡生命周期，以確保網絡連接；A?M等[8]提出了基于Esau-Williams(E-W)算法的設計，解決無線傳感器網絡中的CMST問題，降低了算法的能耗；Dorogovtsev等[9]提出了一種具有類循環拓撲的集中式連通感知算法，實現了更好的拓撲和物理連接要求；Hu S等[10]提出了一種無標度拓撲演化機制(Scale Free Topological Evolution Mechanism,SFTEM)，提高了網絡的生存能力并保持能量平衡；Jemal A F等[11]提出了一種基于簇的無線傳感器網絡能量高效路由器布局方案，該方案采用K均值算法選擇初始簇頭，然后選擇電池能量充足的簇頭以及選擇備用簇頭，達到降低能耗的目標；Sun等[12]提出了以最小生成樹為基礎在連通拓撲構造中考慮剩余能量信息的能量感知加權動態拓撲控制(Weighted Dynamic Topology Control,WDTC)算法。WDTC基于鏈路權重函數工作，平衡了節點的能量消耗。

以上這些算法都在拓撲控制中對網絡拓撲從節能角度和如何延長網絡壽命角度考慮模擬搭建網絡[7]，大量工作僅集中在考慮平衡節點的能量消耗及節點的生存時間問題，而沒有從整個網絡考慮其抗毀性[13-16]。本文從無線傳感網絡的抗毀角度出發，為增強網絡拓撲的抗毀性，提出了能量加權的拓撲抗毀控制算法(Energy-aware Wighted Topology Invulnerability Control,EWTIC)，對網絡進行構建并進行仿真驗證。

1 系統模型及相關定義

1.1 系統模型

系統模型：假設一個面積為l×lm2的矩形區域，n個傳感器節點隨機撒播在此區域中[12]。假設每個節點通過GPS或是其他基于距離的定位技術獲取自己的位置信息，每個節點具有唯一的ID，且節點是靜態節點。傳感器節點的傳輸范圍有限，其通信半徑R是無線電傳播所能到達的最大歐幾里得距離，無線電范圍是平等且有限的，通信鏈路是對稱的。假設節點功率可調，任意兩節點u,v若可進行通信，則兩節點距離d(u,v)≤R，記duv=1,否則duv=0。

定義1E={(u,v)∶d(u,v)≤dmax,u,v∈V}為邊集，V為節點集，dmax為每個節點的最大傳輸范圍，即為通信半徑R。圖G=(V,E)中的邊(u,v)為無序，則稱圖G為無向圖。無向圖用來表示網絡中傳感器節點的拓撲結構，已連接的節點間可進行雙向通信和信息傳遞。

定義2對于無向圖G=(V,E)中的任意兩個節點u,v，若兩個節點之間的距離d(u,v)小于等于通信半徑R，即d(u,v)≤R，同時滿足duv=1，則稱節點v為節點u的1跳鄰居節點，記作v∈N(u)。

定義3在無向圖G中，若頂點u,v間存在兩條路徑，除u,v兩頂點之外，兩條路徑不經過相同的頂點，則稱這兩條路徑為頂點不相交路徑。

定義4若無向圖中任意兩節點間至少存在一條相通的路徑，則稱圖是單連通的。

定義5網絡由n個節點構成，k

定義6NVu={v∈V(G)∶d(u,v)≤dmax}定義為節點的可見鄰域，Gu=(NVu,Eu)表示為G的生成子圖。

1.2 能量模型

無線傳感器網絡(WSNs)中通常將第一個節點的死亡時間定義為網絡的生存時間，網絡的生存時間是網絡性能評估的重要指標之一。網絡的生存壽命與節點能量消耗緊密相關，本節建立網絡拓撲的能量模型，確定能量消耗與通信距離等參數的關系。

網絡的能量消耗主要來自于節點間的數據發送與接收，因此，主要依照節點數據的收發來構建能量模型。節點發送數據時，能量損耗分為發射電路損耗和功率放大損耗兩部分。設有傳輸距離閾值d0，當兩節點間的傳輸距離小于閾值d0,功率放大損耗為自由空間損耗；當大于等于閾值d0時，則為衰減空間損耗。

節點發送數據長度為lbit數據包的能耗為：

ETX(l,d)=lEelec+lEfsd2+Edad≤d0

(1)

ETX(l,d)=lEelec+lEmpd4+Edad>d0

(2)

節點接收數據長度為lbit數據包時，能量損耗僅為電路消耗，能耗為：

ERX(l)=lEelec

(3)

式(1)～(3)中，d為節點間距離；l為數據包長度；Eelec為收發每單位bit長度的數據所消耗的能量；Eda為多路徑衰減能量。

網絡中任意節點的能量消耗為發送和接收數據的能耗之和，所以任意節點u每lbit數據平均消耗的能量為：

ETX(l,d)=2lEelec+lEfsd2+Edad≤d0

(4)

ETX(l,d)=2lEelec+lEmpd4+Edad>d0

(5)

由式(4)、式(5)可知，網絡拓撲中的節點的能量消耗主要取決于節點間的通信距離，節點的通信距離越大，能量消耗的越快，通信的節點間距離當小于閾值時，能量與距離的二次方成正比消耗，大于閾值時，則與距離的四次方成正比消耗，進而導致節點的剩余能量越低。

2 基于能量加權的拓撲抗毀算法

本文提出的基于能量加權的拓撲抗毀算法不同于LMST(Local Minimum Spanning Tree,LMST)算法和WDTC算法，主要思路在于能量加權的權重值下節點的選擇和構建K連通的拓撲，從而實現抗毀效果。

2.1 LMST算法

能量感知加權動態拓撲控制(WDTC)算法是基于局部最小生成樹LMST算法對網絡進行拓撲構建的，LMST算法由以下4個步驟組成：(1)信息收集；(2)拓撲結構，每個節點構建其幾何圖的最小生成樹(Minimum Spanning Tree,MST)；(3)傳輸功率的確定，每個節點調整其傳輸功率，使其能夠到達最遠的鄰居；(4)只具有雙向邊的拓撲結構構建。LMST具有3個顯著特點：(1)構造的拓撲保持了網絡的連通性；(2)構建網絡的拓撲中節點的邏輯度不超過6；(3)拓撲只有雙向鏈路。

然而，在LMST構建的MST類拓撲中，每個節點的負載和傳輸功率分布都具有很大的不平衡性。因此，節點的能耗嚴重失衡，導致網絡生存壽命縮短。因為LMST具有能耗不平衡、網絡壽命有限等缺點，只要節點位置保持不變，LMST算法構建的拓撲不會改變，所以為延長網絡壽命，使每個節點的剩余能量趨于均衡，提出WDTC算法。

2.2 WDTC算法

WDTC算法在LMST算法只利用幾何信息的基礎上，將節點的剩余能量信息添加進拓撲構建中，通過邊權函數將幾何圖轉化為加權圖，每個節點利用新的加權圖構建MST拓撲網絡,邊緣權重反映邊緣上的通信成本。在每一階段，隨著網絡中各節點剩余能量的消耗，邊緣的權重是不同的，因此產生的MST也是不同的[12]。

WDTC算法步驟如下：

步驟1：每個節點以其最大傳輸功率周期性地廣播Hello消息,消息包含節點的ID、位置和剩余能量。

步驟3：每個節點在加權W(u,v)的角度下，用Kruskal算法計算Gu的MST加權圖。MST加權圖既反映了邊緣長度，又反映了節點的能量消耗信息。因此，節點u的鄰域集隨距離和能耗的變化而周期性變化，最終能耗趨于均衡。

構建的簡易拓撲示意圖如圖1，根據WDTC算法步驟，依據權值得到加權圖，根據Kruskal算法，以節點1為起點，通過權值選擇，以1、3、4、6、5、2、1的順序進行拓撲連接從而得到拓撲結果。

圖1 WDTC算法拓撲示意圖

WDTC算法重新配置拓撲時， WDTC和LMST的拓撲結構重構頻率相同的情況下，WDTC不會產生任何額外的能量消耗和計算開銷，因為剩余的能量信息可以通過交換消息中的位置信息來承載;當節點處于平穩狀態時，WDTC下的拓撲重構頻率要比LMST高得多;在WDTC和LMST中，每個節點都用相同的頂點和邊構建其圖的局部MST，因此WDTC和LMST具有相同的時間復雜度O(eloge)，其中e是邊的數目。在WDTC中將拓撲重新構建M次，因此WDTC的計算開銷也將是LMST的M倍。

2.3 基于能量加權的拓撲抗毀算法

網絡中每個節點連通的鄰居節點數量少，某些節點間的不相交路徑只有一條，圖1中關鍵鏈路一旦受損，數據的傳輸則會受到影響，網絡便呈現出脆弱性，面對隨機失效或是范圍性失效，網絡的受損程度會增大，抵御風險的能力偏低，從而影響網絡的正常運行。同時，面對由靜態節點組成的網絡，節點的位置信息不變，網絡中變化的是各節點的剩余能量，根據能量信息構建網絡拓撲的WDTC算法達到了能耗均衡的效果，但為進一步提高網絡的穩定性和抗毀性，提高其抵御風險的能力，本研究將給出相應改進方案，提出基于能量加權的拓撲抗毀算法(EWTIC算法)。

2.3.1EWITC算法

根據文獻[12]，將能量信息添加在拓撲結構中，通過邊權函數將幾何圖轉化為加權圖。根據文獻[12]定義，權函數為W(u,v)=W(duv,Eu,Ev)>0，duv≤dmax,其中duv是u與v之間的歐氏距離，Eu,Ev分別是u和v的剩余能量。函數W是變量duv的增函數，是變量Eu和Ev的減函數，提出的算法依據邊緣權重的不同應用K連通網絡的思想進行連接，單個節點執行至多K次的鄰居節點間權重值查找，對符合預設條件(包括能量閾值、距離閾值、權重值等)的節點進行拓撲連接，直至網絡中所有節點重復相同的操作步驟，則完成網絡的拓撲構建。

算法中，每個節點周期性地廣播一個具有最大傳輸能量的Hello消息，以收集其可見鄰居的位置和能量信息。根據節點的剩余能量信息重新配置拓撲，EWITC算法具有類似于WDTC的特性，與WDTC拓撲結構重構頻率相同時，因為剩余的能量信息可以通過交換消息中的位置信息來承載，不會產生任何額外的能量消耗和計算開銷；重構頻率高于WDTC時，EWITC的能量消耗和計算開銷相較于WDTC增加。

如圖2所示，以6個節點的簡易網絡為例，對算法思想進行簡要說明。利用邊權函數已計算好加權值，在上圖中以線段長短表示權值的大小。以節點1開始進行拓撲構建，節點1的鄰居節點有節點2，3，4，5，經查找，節點1與節點3之間的加權值最小，對節點1和3進行連接，之后，同樣以1為起點，查找與未連接節點間的最小加權值，節點1與2進行連接，重復上述查找，節點1與4進行連接，示例中以3為連通度，完成節點1的鏈路連接，以節點2為首，重復上述查找，依次連接到節點4與節點5。 其余節點同樣依據此思想進行連接。

圖2 EWITC算法拓撲示意圖

2.3.2算法步驟

EWTIC算法步驟如下：

步驟1：網絡初始化，節點隨機布置在一定區域內，并根據實際情況對各節點能量設初值，節點ID、坐標信息等初始化。

步驟2：每個節點以其最大功率周期性廣播Hello消息，消息中含有節點的ID、坐標以及剩余能量信息，完成信息交互。

步驟4：每個節點在加權W(u,v)的角度下，以K連通網絡思想為基礎，滿足距離閾值、能量閾值的條件下，每個節點重復K次查找最小權重值，對符合條件的鄰居節點進行拓撲連接并對節點鄰居矩陣標記，直至網絡中全部節點完成查找與連接，則完成拓撲構建。能量隨著網絡的運行而不斷消耗，節點的鄰接矩陣也會隨能耗變化而定期變化，最終能耗均衡且抗毀性提高。

相較于LMST、WDTC算法，EWITC算法在同頻率拓撲構建時不會產生額外的能量消耗和計算開銷，因其剩余能量的信息可在交換位置信息時承載。EWITC算法的重構頻率比LMST算法高，且EWITC算法的計算開銷與WDTC算法相類似，同重構次數M成正比。

3 仿真與分析

本文采用Matlab R2015b對EWITC算法進行性能仿真驗證，并與WDTC算法進行性能比較。通過仿真比較分析WDTC算法與EWITC算法的平均連通度、魯棒性、介數中心性等性能指標的差異。

3.1 仿真結果

在WDTC的基礎上，為了提高網絡拓撲的抗毀性，提高網絡抵御風險的能力，提出EWTIC算法以達到更好的拓撲質量。首先，對EWITC算法如何工作進行演示，搭建一個網絡場景，將50個節點隨機布置在100 m×100 m的方形區域內，節點的傳輸半徑設置為40 m，實驗中采用多路徑傳播的方式進行數據傳輸，為公平起見，一半的節點隨機分配為源節點，另一半則作為目的節點。每個源節點以2包/s的速率向目的地發送數據包，節點的初始能量容量為E±0.05 J內隨機分配，以貼近實際節點的能量容量分布，r為數據包傳輸的次數，最大運行次數rmax設為40，設置每次數據包大小l為4 000 bit。

圖3中給出了EWITC算法的拓撲演化情況，類比最大功率傳輸，明顯每個節點的連接路徑減少，網絡拓撲復雜度降低，每個節點需要通訊的節點減少。實驗采用循環次數表示時間，隨著運行次數的變化，可觀察到拓撲隨著能量分布變化而演化。

圖3 EWTIC拓撲演化示意圖

3.2 性能評價

在這一部分中，為了對EWITC算法從抗毀性角度[12,14]進行評價，實驗中3個性能指標的計算將參照文獻[5]中的3個性能指標的計算公式，即魯棒性評價指標、平均連通度以及介數中心性評價指標進行抗毀性評估，通過計算驗證算法的有效性。這里，實驗將EWITC算法與WDTC和LEECH算法進行比較。n個節點分布在500 m ×500 m區域。每個節點的傳輸范圍為100 m。實驗中選擇節點的連通度為4作為連通上界，連通度過大會造成網絡能耗過大。表1中顯示了其他模擬參數值。實驗中節點n的數目以50到150為區間。每個數據點平均30次模擬運行。

表1中，α:指數，E:初始能量,Efs:自由空間損耗,Emp:衰減空間損耗,Eda:多路徑衰減能量，Eelec單位數據傳輸損耗。

表1 仿真參數

節點的度通常是指與某個節點直接相連的邊個數，反映對網絡連通性影響的大小。網絡的平均度(平均連通度)是網絡中所有節點度的平均值。

從圖4(a) 可以看出，EWITC算法的平均連通度明顯優于WDTC和LEECH，隨著節點數量的增加，曲線都有明顯的增加，所提算法在連通度上始終比WDTC高，由此表明網絡中節點的連通路徑比WDTC多，因此信息的傳輸更有保證，網絡的穩定性增加，這與實際拓撲情況相符。

網絡的魯棒性是指網絡中任意節點被移除之后，網絡中剩余節點間仍能保持連通的平均影響力。定義為任意節點被移除后，網絡中的剩余連通節點對數與網絡中的總節點對數的比值的均值。

由圖4(b) 可知，EWTIC算法的魯棒性隨著節點的增加明顯增加，增速明顯高于其他算法。由此說明EWITC算法相較于其他算法，某節點的移除對網絡的影響力更小，對網絡造成的影響更低。WDTC算法由于采用最小生成樹思想，某些節點失效可直接導致網絡的斷裂，魯棒性低，對網絡影響較大，故而EWITC算法在魯棒性評價上更優。

節點的介數反映節點在整個系統中的影響力，定義為網絡中所有的最短路徑之中，經過節點的最短路徑數占所有最短路徑的比值。

介數中心性的比較中，為了更清晰顯示仿真結果，實驗中選擇了50個節點下介數中心性圖對WDTC算法和EWITC算法的進行比較。

EWITC與WDTC算法的介數中心性對比如圖4(c) 所示。 WDTC算法構建的網絡中，每個節點的介數中心性相對較小，大部分節點的介數偏小，某些節點如3、15等節點失效，則其他節點之間不連通，所以節點的介數相對較小且低于0.05。EWITC算法構建的網絡，由于連通度相比于WDTC提高，且多路徑通信下，更多節點分擔通信路徑的任務，因此節點介數增加，這明顯也與實際情況相符合的。

仿真結果表明，從平均連通度、魯棒性以及介數中心性角度來看，EWITC算法構建的拓撲的抗毀性更好。

圖4 各評價指標曲線

4 結論

1) 針對加權拓撲算法構建拓撲結構的易受損性，提出了一種有效的能量加權的抗毀拓撲EWTIC算法。

2) 將能量加權與k連通思想結合構建出了穩定的拓撲結構，隨著能量的消耗，網絡的拓撲結構定期調整，網絡仍然保持拓撲結構的均衡性，多路徑傳輸得到保證。

3) 算法在魯棒性、介數中心性、網絡平均連通度評價指標評估下，EWITC抗毀算法表現出高連通度、強魯棒性和更優的介數中心性，有效地增強了網絡拓撲的抗毀能力，對網絡拓撲結構穩定具有參考意義。