考慮級聯失效的有向WSNs節點重要度評估模型

鄧玉靜,王倩悅,尹榮榮,劉 彬

1(燕山大學 信息科學與工程學院,河北 秦皇島 066004)2(燕山大學 電氣工程學院,河北 秦皇島 066004)

1 引 言

近年來,隨著無線通信技術及傳感器設備的發展,采用大量具有傳感、處理和無線通信能力的傳感器節點來監視指定傳感領域的無線傳感器網絡(Wireless Sensors Networks,WSNs)被廣泛應用在智能交通、智慧城市、工農業控制及生物醫療等控制領域[1,2].現實世界中的網絡多數是有向無標度網絡,即度分布服從冪律分布的非同質拓撲結構的有向網絡,如食物鏈網絡[3]和引文網絡[4].當網絡面對隨機攻擊時,無標度網絡比隨機網絡的抗毀性更強,而當網絡面對蓄意攻擊,尤其是攻擊關鍵節點時,無標度網絡的抗毀性異常脆弱.這是由于當無標度網絡中5%的重要節點受到攻擊時,會引發節點的級聯失效致使整個網絡快速崩潰,降低網絡的抗毀性.因此,建立能夠判定網絡關鍵節點的算法,并對關鍵點進行針對性的分析和維護,有助于提高整個網絡的可靠性與抗毀性[5,6],這也就使網絡關鍵節點的判定研究成為研究者們關注的熱點.

目前,對于有向無線傳感器網絡的關鍵節點判定問題,研究者們做了大量研究.文獻[7]利用引文分析方法,根據超文本中鏈接結構計算網絡中每個網頁的被訪問頻率,提出了PageRank算法,該算法成功地設計了可伸縮的搜索引擎Google.文獻[8] 基于擴展哈希技術和網頁的唯一訪問數,使用基于哈希的索引數據結構動態地對web查詢進行分類,提出了一種改進的PageRank算法對web頁面進行排序.文獻[9]針對傳統PageRank算法精度不高的問題,提出一種逆向隨機游走PageRank算法,該算法具有更好的穩定性,并在迭代次數較少時也能保持較高精度.文獻[10]考慮到有向網絡的方向特性的問題,基于網絡基序和多元統計分析,提出了一種新的方法來描述有向生物網絡中節點的重要性,為進一步挖掘有向生物網絡中未發現的節點特征提供新方法.文獻[11]為了分析有向通信網絡的中間節點的重要性,提出一種以節點表示端到端路由的快速尋找算法,該方法運算簡單,具有一定的實用性.文獻[12] 建立了一種度量加權有向網絡中節點中心度的指標,以有向度中心性為初始值,引入了異步更新過程,迭代使用更多的網絡信息更新節點的重要性.文獻[13]考慮多種指標,構建了三種影響力矩陣,采用層次分析法構建了有向加權網絡模型節點重要性評價方法.然而,以上節點重要度的評估方法皆局限于節點間的相互獨立性,未考慮網絡傳輸負載的時變動力學特征.當節點的負載大于其容量時,節點出現故障,則其負載會被分配到其他節點上,這就加劇了其他節點的負載壓力,而當鄰居節點的負載超過自身容量時也會失效,產生級聯故障傳播,造成大規模網絡的癱瘓[14].針對這個問題,文獻[15] 考慮級聯失效局域信息,構建了最近鄰分配和全局分配兩種規則的復雜網絡節點重要度判定模型.文獻[16]針對級聯失效問題,建立了一種重載函數模型,提出了一種考慮級聯失效的節點重要性評估方法,可以找到一些潛在的關鍵節點.文獻[15,16]雖然考慮了節點間相互影響可能會造成的級聯效應,但是沒有考慮網絡的方向性特征.

以上研究雖然取得了一定的成果,但均未綜合節點之間的相互影響以及節點之間相互影響的方向性.針對以上問題,本文在有向無線傳感器網絡中基于級聯失效對節點重要度進行分析.首先,考慮網絡節點層級關系、負載、容量及負載重分配規則,建立有向網絡級聯失效模型,并推導出節點失效后引起的負載震蕩狀態值.然后,引入經典Pagerank算法,建立節點度擇優的分配規則對其平均分配規則進行改進,將失效節點引發的鄰居節點平均負載震蕩狀態值作為節點的初始重要度值,構建考慮級聯失效的有向無線傳感器網絡節點重要度判定算法——NCFD(Noderank considering cascading failure in directed wireless sensor networks).最后,通過實驗仿真驗證算法的有效性.

2 有向網絡級聯失效模型

本節考慮無線傳感器網絡中節點的負載、容量和負載重分配規則三種因素,對有向網絡級聯失效進行建模,分析有向網絡的級聯失效過程.運用數學公式,推導得到節點失效后在其分配范圍內引起的負載和能量的震蕩狀態值,為下一節構建級聯失效相關的節點重要性評估模型奠定基礎.

2.1 級聯失效模型

現實生活中很多網絡都是有向的,例如無線傳感器網絡中數據在實際傳輸過程中總是朝著基站方向傳播,網絡中的節點由sink節點和普通節點組成,而處于不同層級的節點所承擔的負載也不同.本文按照網絡中普通節點到sink節點的跳數對網絡拓撲進行分層.有向網絡分層結構如圖1所示,按照圖1網絡中的數據傳輸方向,處于n層的節點是處于n-1層節點的父節點,相應地,處于n-1層節點是處于n層節點的子節點(如2號節點是8號節點和12號節點的子節點;相應的8號節點和12號節點均為2號節點的父節點).

圖1 網絡分層示意圖Fig.1 Layered network

根據有向分層網絡拓撲結構特性,節點的入度越大,說明其接收的數據量越大,其負載也會相應的增大.而當鄰居節點的入度較大時,鄰居節點傳輸過來較大的數據量也會增加節點的負載.因此,本節考慮節點的層級關系、節點入度以及鄰居節點的入度對節點的影響來定義節點負載的非線性函數,具體表達式如下:

(1)

節點的容量是節點能夠承擔負載的極限值,根據ML模型,節點容量與其初始負載呈正比關系,即:

Ci=(1+τ)Li,τ≥0

(2)

其中,Ci是節點i的容量,τ是網絡的能力容量參數,表示節點處理額外負載的能力,Li是節點i的初始負載.

圖2 有向網絡級聯失效后的負載重分配示意圖Fig.2 Load redistribution after cascade failure in directed networks

由圖2的有向網絡可以看出,當節點i意外失效后,來自其父節點j1,j3的數據將無法流入,同時流出到其子節點j2的數據也將被中斷.這就導致父節點j1,j3的負載以一定的分配規則被重新分配給其父節點或其他的子節點,也將導致這些節點因過載而失效,此過程循環進行,直到網絡中的再分配節點不出現過載現象.同時,而子節點j2無法接收來自i的數據,會因數據少載而被禁用.最終,這兩種失效現象導致大規模網絡崩潰.

根據有向網絡節點數據傳輸的方向性,當節點i失效時,其負載將返回給其父節點,也可能會轉移到該父節點的其他子節點.父節點j增加的負載將按照公式(3)所示的負載重分配規則進行分配[18]:

(3)

當節點i失效時,其子節點因無法接收其傳輸過來的數據而導致負載減少,根據子節點的承載能力,子節點w減少的負載將按照公式(4)所示的負載重分配規則進行分配:

(4)

因此,根據以上原則,節點i失效后,它的父節點負載更新為:

(5)

子節點負載更新為:

(6)

上述是一次有向網絡失效節點的負載重分配的過程.節點負載更新完成后,若節點j的負載超過其容量,則節點j也會因過載而失效,網絡將進行新一輪的負載重分配,而新的負載重分配將導致更多節點失效,形成級聯失效,負載重分配一直進行到網絡中沒有負載過載現象停止.

2.2 級聯失效震蕩狀態值

若使節點j不會引發后續的級聯失效,則其負載更新之后該滿足如下條件:

Lj+ΔLj→i≤Cj

(7)

根據公式(1)和公式(2),上面的不等式可以細化為:

(8)

化簡為:

(9)

(10)

若F(i)的值大于1則節點j過載,若F(i)的值小于或等于1則節點j不過載.

(11)

3 節點重要度評估方法建立

本節借鑒PageRank算法[15]的網頁連接價值重要性排名的思想,結合上一節推導得到的級聯失效震蕩狀態值,建立考慮級聯失效的有向無線傳感器網絡節點重要性評估模型NCFD.

PageRank算法是用于搜索引擎中網頁排序的經典算法.其數學公式如下:

(12)

其中,PR(x)為網頁x的重要度值;σ為阻尼系數;n為指向x的網頁數目;PR(Yi)為指向x的網頁Yi的重要度值;Cout(Yi)為Yi的出邊數量.由公式(12)可以看出,當n越大,x的鏈接源越多,PR(Yi)越大,指向x的網頁的重要度越高,則網頁x越重要.

現實網絡中節點因所處的層級、負載及容量不同而其對應的重要度也不同.PageRank 算法的平均分配思想,在一定程度上降低了節點重要度的排序準確率.因此,本文將每一個節點的初始重要度定義為節點級聯失效后引起的平均震蕩狀態值,同時將其按照節點度所占比例進行分配.在有向網絡G(V,E)中,節點數N=|V|,節點v與節點v1,v2,…,vf相連,則節點v的重要度NR(v)為:

(13)

NCFD計算各個節點的重要度的算法步驟如算法1所示.

算法1.NEIAlgorithm輸入:AdjacencymatrixA=(aij)N×NofdirectednetworkGwithNnodes輸出:TheorderSofnodevStep1.Initializetheloadadjustableparameterandcapacityparameter,andcalculatetheinitialloadandcapacityofthenodebyEq.(1)andEq.(2).Step2.Deletenodev.Step3.UpdatenodeloadbyEq.(5)andEq.(6).Step4.Judgewhetheranewfailurenodeisadded,ifso,deletethefailurenodeandreturntoStep3,otherwiseturntoStep5.Step5.CalculatetheaverageoscillationstatevalueF(i)byEq.(11).Step6.CalculatetheimportanceNR(v)ofnodev.Step7.Whetherallnodesaretraversed,ifso,turntoStep7,otherwise,selectdifferentnodespandreturntoStep2.Step8.S=SortvbyNR(v).

4 仿真實驗

本節仿真實驗中,首先對比分析PageRank算法與本文NCFD算法所判定出無標度網絡的節點重要度,然后分別采取刪除兩種算法判定的關鍵節點和保護所判定出的關鍵節點兩種措施下的網絡抗毀性進行分析和評估,以驗證本文所構建模型的準確性和合理性.本實驗的實驗結果均取50次實驗的平均值.具體的實驗環境參數見表1.

表1 NCFD實驗數據表
Table 1 Experimental parameters

參 數取值節點個數N100節點分布區域A/m2500×500節點最大傳輸半徑R/m100sink節點坐標(m,m)(250,250)負載參數β12/3負載參數β21/3容量參數τ1.5阻尼系數σ0.85

4.1 節點重要度分析

在圖3所示的網絡拓撲結構(其中sink節點在監測區域的正中心)上,分別根據公式(12)和公式(13)計算PageRank算法和本文NCFD算法的節點重要度值,并繪制出如圖4所示的節點的重要度分布圖.

由圖4中可知,PageRank算法與本文NCFD算法判定出的節點重要度分布趨勢一致,節點5,23,25,68,74,86,89,90,92,93,94,95,97,98都是網絡中的重要節點,驗證了本文NCFD算法的有效性.本文NCFD算法判定出節點8,28,60,80,87,100的重要性也較高,這是由于本文考慮了節點失效引發級聯失效的震蕩程度以及節點所處不同層級的因素,這些節點失效極有可能觸發節點間的“級聯效應”,加速網絡崩潰.說明本文NCFD算法能夠判斷出網絡中潛在的關鍵節點,使得節點重要度的判定更加全面.

由表2可知,PageRank算法中重要度值最高的節點是95號節點,而其在NCFD算法中排名僅為第4.在NCFD算法中100號節點重要度值排名第3,而PageRank算法中其排名并未進入前10.這是由于NCFD算法考慮了節點失效后引發的級聯震蕩的作用.由于95號節點的震蕩狀態值較93號節點低,所以其重要度低于93號節點,而100號節點的震蕩狀態值較高,其失效后引發網絡級聯失效的可能性很大,所以100號節點重要度較高.因此,NCFD算法判定的結果更加全面.

圖3 網絡拓撲結構Fig.3 Network topology

圖4 節點重要度分布Fig.4 Node importance distribution

4.2 網絡抗毀性分析

統計PageRank算法和本文NCFD算法所判定出的節點重要度排名靠前的10個節點,排序結果如表2所示.

表2 節點重要度排名前10的節點編號
Table 2 Node numbers with node importance in Top 10

排序PageRankNCFD19593293923941004595592946989079797889899685107486

為了進一步驗證算法的準確性與合理性,分別按照兩種算法所判定出的重要度順序逐次移除節點,并觀察包含sink節點的連通塊中節點數目的變化情況,統計結果如圖5所示.

圖5 移除關鍵點后連通塊的變化情況Fig.5 Change of connected block after removing critical nodes

由圖5中可知,選擇性移除兩種算法所判定出的關鍵節點,包含sink節點連通塊中節點數目均呈下降趨勢,且NCFD算法的下降速度明顯較快.當移除4個關鍵節點時,PageRank算法的網絡連通塊中節點數目約為35%,而NCFD算法已經少于總節點數目的20%了.這是由于NCFD算法不僅對PageRank算法平均分配的不合理性進行了改進,而且考慮一個節點失效可能引發的網絡級聯失效效應,引入了級聯失效震蕩狀態值參數,使得判定結果減少了遺漏關鍵點的情況.

下面分別對網絡中由兩種算法所判定出的重要度排名前10的節點采取保護措施,然后逐次隨機移除網絡中的節點,并觀察網絡中包含sink節點的連通塊中節點數目的變化情況,統計結果如圖6所示.

圖6 隨機移除下連通塊的變化情況Fig.6 Change of connected blocks under random removal

由圖6可知,面對節點隨機失效,保護由NCFD算法所判定出的關鍵點時,網絡的容忍力均比保護PageRank算法和未采取保護措施時強.隨著網絡中失效節點數量的增加,保護由NCFD算法所判定出的關鍵點時,網絡中包含sink節點的連通塊節點數目下降速度最慢.而且,當隨機移除20個節點時,可以看出包含sink節點的連通塊中仍有30個節點,而在另外兩種措施下,網絡包含sink節點的連通塊的數目均遠少于30個.同時圖6也說明了保護由NCFD算法判定所得關鍵點比保護由PageRank算法判定所得關鍵點的網絡能表現出更強的抗毀性,這也進一步驗證了NCFD算法的準確性.

5 結 論

本文針對目前無線傳感器網絡節點重要性評估方法中未綜合考慮節點之間相互作用及數據傳輸具有方向性的問題,提出了考慮級聯失效的有向WSNs節點重要性評估模型.通過Matlab仿真實驗驗證了該方法能有效地評估有向無線傳感器網絡節點的重要性.而且采取選擇性移除和隨機移除兩種攻擊下本文NCFD算法可以明顯地增強網絡的抗毀性,因此,本文構建的有向WSNs節點重要度評估模型及級聯失效模型可以為提高網絡魯棒性研究提供理論支持.本文僅采用了Matlab仿真實驗進行驗證,如何在實際網絡中驗證及應用將是下一步的研究工作.