分簇無線傳感器網絡級聯失效抗毀性研究

符修文 李文鋒 段 瑩

1(河南科技大學車輛與交通工程學院 河南洛陽 471003)2(武漢理工大學物流工程學院 武漢 430063)(fuxiuwen1987@163.com)

?

分簇無線傳感器網絡級聯失效抗毀性研究

符修文1李文鋒2段 瑩2

1(河南科技大學車輛與交通工程學院 河南洛陽 471003)2(武漢理工大學物流工程學院 武漢 430063)(fuxiuwen1987@163.com)

無線傳感器網絡(wireless sensor network, WSN)級聯失效對象多以對等平面結構為對象，但在現實情形中，多數無線傳感器網絡采用典型分簇結構進行數據采集與傳遞.因此，考慮分簇傳感器網絡中節點所擁有連接的異質性，引入感知負載與中繼負載等概念，建立分簇級聯失效模型，探討分簇無標度網絡和分簇隨機網絡的級聯失效抗毀性能與模型關鍵參數之間的關聯特征，并研究如何選取合適的簇頭節點擴充容量達到抑制網絡級聯失效規模的目的.數值模擬與理論分析結果表明：分配系數A與網絡級聯失效性能正相關，簇頭比例p與網絡抗毀性能負相關.當調節參數α=1時，網絡級聯失效抗毀性能達到最優；當調節參數α<1時，選取簇-簇連接度較小的簇頭節點擴充容量能夠更為有效地提升網絡級聯失效抗毀性能；當調節參數α>1時，選取簇-簇連接度較大的簇頭節點擴充容量抗毀性能提升效果更為明顯；當調節參數α=1時，網絡級聯失效規模與簇頭選取策略無關.

無線傳感器網絡；級聯失效；分簇結構；抗毀性；無標度拓撲；隨機拓撲

布置在惡意環境中的無線傳感器網絡(wireless sensor network, WSN)常會因為人為入侵或自然災害等外部原因導致節點失效.除此之外，傳感器節點通常采用移動電源供電，常因成本受限或部署環境惡劣等原因，導致節點能量耗盡或軟硬件故障而無法正常工作.失效節點會使得原本連通的網絡拓撲分割，從而大大降低網絡的連通度與覆蓋度，甚至導致全局網絡癱瘓[1-4].由于規模巨大、資源受限、傳遞時延與有向傳輸等內在因素產生的非線性網絡行為難以預測，研究WSN抗毀性行為對解決WSN規模應用瓶頸具有重要的理論價值.

現有WSN抗毀性研究多從靜態角度，研究移除點或邊對網絡拓撲連通性與可用性的影響，并未考慮網絡的動態性過程.但在現實WSN中，網絡拓撲結構的改變將會造成網絡數據流的重新分配，導致網絡通信負載動態變化.受制于硬件成本，傳感器節點往往鏈路帶寬受限，當實時通信負載高于節點額定載荷，將導致節點因鏈路堵塞而引發過載失效.WSN作為典型的以數據為中心的任務驅動型網絡，節點失效的發生將導致網絡負載再分配，進而可能造成其他節點因過載而失效，從而引發新一輪的負載分配，并最終導致大規模網絡級聯失效的發生.因此，級聯失效普遍存在于現實WSN中，是影響WSN抗毀性能的主要因素[5-7].

當前針對網絡級聯失效問題，有眾多學者展開研究.Motter等人[8]最早提出負載-容量模型，該模型定義每個節點均擁有一定容量并承擔相關負載.當節點失效行為發生，則該節點所承擔負載按照預設規則轉移至網絡中剩余其他節點.而其他節點也將可能因負載超出自身容量而導致失效，并引發新一輪的負載轉移.后續諸如CASACADE模型[9]、OPA模型[10]等均是在負載-容量模型基礎之上發展而來.現實世界中，不同類型網絡所對應級聯失效情形各不相同.研究表明：輸配電網絡[11]、物流保障網絡[12]、交通網絡[13]及因特網[14]等均具有明顯的級聯失效特征且彼此間具有明顯差異.在歸納總結基礎上，現實網絡通常被劃分為：隨機網絡、小世界網絡與無標度網絡.因而，有眾多學者針對這3種廣義網絡類型展開級聯失效抗毀性研究.WSN作為數據驅動型的新興信息網絡也得到越來越多學者的重視.Liu等人[15]基于介數定義節點負載，建立WSN級聯失效模型，并在此基礎上提出級聯失效抗毀性測度.由于節點介數計算依賴于全網最短路徑的獲取，這就要求節點必須擁有全局網絡路由信息，但對于多數WSN而言，全局信息的獲取十分困難；Yin等人[16]根據節點可變負載與恒定容量等特點，針對WSN無標度拓撲展開研究，得到度分布指數和冪律系數與WSN容錯性能正相關這一結論；李雅倩等人[5]則在此研究基礎上，借助概率母函數法求解WSN無標度拓撲級聯失效的臨界負載值.盡管現有WSN級聯失效研究取得一定成果，但所針對WSN對象均為對等平面結構，即網絡內所有節點角色、功能均完全一致.然而在現實情形中，由于受網絡規模和以能耗與延時為代表的服務質量要求，多數WSN均采用典型分簇結構進行數據采集與傳遞.現有WSN級聯失效研究對于此類普遍情形并不適用.

基于上述考慮，本文針對真實情形下WSN普遍存在的分簇結構，引入中繼負載與感知負載等概念，建立分簇WSN級聯失效模型.基于網絡演化分別提出分簇WSN的無標度與隨機拓撲演化模型.在此基礎上，通過理論推導與仿真分析相結合的方式，驗證級聯失效模型中各關鍵參數對所提分簇WSN模型級聯失效抗毀性能的影響，獲得了節點隨機失效情形下分簇WSN大規模級聯失效臨界負載值與網絡分簇概率、負載和容量參數之間的關聯特征.除此之外，研究如何選取合適的簇頭節點擴充容量達到抑制網絡級聯失效規模的目的.通過以上研究為后期構建具有較強級聯失效抗毀性能的分簇WSN拓撲提供了理論參考.

1 分簇WSN級聯失效模型

1.1 負載-容量模型

分簇WSN通常由簇頭節點與簇內成員節點構成.簇內成員節點負責采集所覆蓋區域內的環境信息，將數據匯聚至所屬簇頭節點.簇頭節點負責簇內信息的集中處理與發送，除此之外，還需承擔來自其他簇頭節點中繼數據的轉發任務.由于節點負載通常與節點自身度存在明顯關聯[5-6,16-17]，且在分簇WSN中，節點所擁有連接具有明顯的異質性，定義網絡中任意節點j的初始負載Lj為

(1)

在實際網絡中，由于每個節點處理負載的能力通常受布設成本等因素制約，節點間容量并不相同.在確定節點的容量時通常遵循“按需定容”原則[5-13].所以，一般認為節點的負載容量Cj與其初始負載Lj成正比，即:

(2)

其中，T(T≥1)為網絡容忍系數，顯然T值越大，節點處理額外負載的能力越強.

1.2 負載分配策略

在文獻[5，15]中，當WSN中任意節點j發生失效，它的自身負載將平均分配至與其相鄰的其他節點.正如1.1節所述，對于傳感器節點而言，負載分為感知負載與中繼負載.當節點失效行為發生，節點因無法感知周邊環境，沒有感知數據產出.它的感知負載也隨之消失，因而無法轉移至其他節點.但對于中繼負載，當節點失效發生，原本需要通過它轉發的數據量需要重新路由，從而產生新一輪的負載分配.但該過程的負載重新分配僅限于中繼負載.因而，以往文獻中，有關全部負載均全部用于重分配過程的策略設計與真實情形相比并不準確.除此之外，當節點確定有負載需要重新分配，則與之直接相連的節點中，度數越高的節點有更高的概率承擔更多的負載.因而，以往文獻中有關負載的平均分配策略具有明顯的局限性.

因此，針對上述不足，本節針對分簇WSN給出4項負載分配策略：

1) 初始狀態.WSN中任意節點負載均小于其容量，網絡處于正常運行狀態.當有節點發生失效時，其中繼負載將重新分配到與其相鄰的節點，引起網絡中負載重新分配.該過程又可能導致新的節點失效行為發生，從而引發新一輪的負載重分配.該級聯過程持續到沒有新的失效節點出現時才完全停止.

2) 當簇內成員節點發生失效，因自身感知任務無法繼續進行，所以無法向所屬簇頭節點發送數據，自身不承擔中繼轉發任務，無中繼負載需要分配.因此，并不會引發負載重分配過程，則級聯失效過程不會發生.

3) 當簇頭節點發生失效，因自身無法進行中繼傳輸，則所轄簇內成員節點因無法借助簇頭節點向簇外傳遞數據也隨之失效.原有途經失效簇頭節點的中繼數據根據局域擇優分配原則分配至周邊與之相連的其他簇頭節點.

4) 假定網絡中簇頭節點j失效，則與之直接相連的簇頭節點i獲得的負載Δij為

(3)

其中，Ωj為簇頭節點j所擁有鄰居簇頭節點集合.假設負載分配完成時刻為t，則此時簇頭節點i所承擔負載為Li(t)=Li(t-1)+Δij.若Li(t)>Ci，則節點i在時刻t+1陷入失效狀態，并引發新一輪的負載分配.不難理解，依照本文所提分配策略，若鄰居簇頭節點擁有的簇-簇連接數越多，則所獲得的負載分配比例越高.正如1.1節所述，在分簇WSN中，一個簇頭節點所連接的簇頭節點數量表明了該節點在網絡數據轉發任務中的重要性程度.因而，本文給出負載分配策略合理有效.

(4)

當中繼負載重分配過程完成后，若簇頭節點a，b，c中有節點因新增負載使得節點實時載荷超過額定容量，即存在Li(t+1)>Ci，i={a,b,c}，則產生新的簇頭節點失效，新增失效簇頭節點將自身負載按策略重分配至仍可正常工作的鄰居簇頭節點.該過程一直重復至網絡中剩余簇頭節點實時負載均未超過其自身容量為止.

Fig. 1 Local allocation strategy of clustering WSN.圖1 分簇WSN局域分簇分配策略

1.3 級聯失效抗毀性測度

根據負載分配策略，當簇內成員節點發生失效后，并不會引發級聯失效.因此，本文重點研究對象為移除簇頭節點所引發的級聯失效對網絡的破壞程度.為了量化網絡被破壞的程度,首先給出失效節點的歸一化指標.從初始網絡中移除一個簇頭節點j，并計算因其所產生的失效規模Sj(級聯失效過程完全停止后，失效節點的累計和)，然后依次對網絡中的每個簇頭節點進行移除并計算其失效規模，再取所有簇頭節點失效規模之和，作歸一化處理，得到網絡級聯失效規模S：

(5)

其中，C為網絡中所有簇頭所組成的集合，|C|為簇頭節點數量，N為節點總數.顯然，當S≈0時，網絡可用節點數量在級聯失效發生前后幾乎不發生改變，具有很強的級聯失效抗毀性能;反之，當S≈1時，說明網絡中任意一個節點的失效都將導致網絡因級聯失效而陷入癱瘓.正如文獻[17]所述，對于級聯失效，比起關注級聯失效對網絡的破壞程度，人們更關心網絡應對級聯失效所能承載的極限.由分簇WSN級聯失效的負載-容量模型與負載分配策略可知，容忍系數T越大，則網絡承載級聯失效的能力越強.因此，必然存在一個臨界值Tc，當T≥Tc時，任意節點的移除都不會導致級聯失效的發生且網絡構造成本最低.不難理解，Tc即為網絡為避免級聯失效所應具備容忍能力T的最小值.顯然，Tc值越小，網絡應對級聯失效的抗毀性能越強.

2 分簇WSN演化模型

由于網絡拓撲結構對網絡動力學特征行為有著至關重要的影響，本文選取2種典型WSN分簇拓撲來研究不同網絡拓撲應對級聯失效抗毀性能的差異.

2.1 分簇WSN無標度演化模型

分簇WSN無標度演化模型具體生成步驟為:

1) 初始化.開始給定m0個簇頭節點與e0條邊,為保證網絡中不出現孤立節點，各個簇頭節點至少存在一條邊與其他簇頭節點相連.

2) 擇優增長連接.在每個單位時間步增加一個新節點，則該節點成為簇頭節點的概率為p，并連接到網絡中一個已經存在的簇頭節點上.簇頭節點j依照擇優概率Π(i→j)與新入節點i建立連接，擇優概率Π(i→j)與被選擇簇頭節點j的度數kj成正比,Π(i→j)表達示為

(6)

其中，N(t)為在當前時刻t網絡所擁有簇頭節點數量.

2.2 分簇WSN隨機演化模型

分簇WSN隨機演化模型具體生成步驟為：

1) 初始化.開始給定m0個簇頭節點與e0條邊.為保證網絡中不出現孤立節點，各個簇頭節點至少存在一條邊與其他簇頭節點相連.

2) 擇優增長連接.在每個單位時間步增加一個新節點，則該節點成為簇頭節點的概率為p，并隨機連接到一個網絡中已經存在的簇頭節點上.則簇頭節點j被選擇連接概率為

Π(i→j)=1N(t).

(7)

按照上述規則經過一定時間演化，2個模型均可得時刻t時網絡擁有節點總數S(t)=m0+t，簇頭節點數量N(t)=m0+pt.顯然，當t→∞時，S(t)≈t，N(t)≈pt.

Fig. 2 Evolution model of clustering WSN.圖2 分簇WSN演化模型

圖2為初始網絡與新加入節點位置均為一致，依照參數設定：簇頭比例p=0.2，網絡規模N=100所生成網絡拓撲情形，此時節點平均度k=2.如圖2(a)所示，在所得分簇WSN無標度拓撲中，絕大多數簇頭節點度數為1，但少數簇頭節點占用了網絡中絕大多數連接，最高簇頭節點度數可達11，具有明顯的無標度特征.如圖2(b)所示，分簇WSN隨機拓撲度分布較無標度拓撲勻質性明顯增強，網絡中絕大多數簇頭節點度數均為3～5，符合隨機網絡特征.

圖3為將節點規模擴大至500后在雙對數坐標系下所提分簇WSN無標度拓撲與隨機拓撲的網絡度分布情形.分簇WSN無標度拓撲度分布具備典型的冪律分布特征，對度分布曲線進行擬合，可得無標度拓撲服從冪律分布P(k)=1.6k-2.7.分簇WSN隨機拓撲服從典型的指數分布，擬合后結果為隨機拓撲服從指數分布P(k)=exp(-3.1k).為更準確驗證所提2種網絡演化模型的度分布特征，隨后將對其度分布做進一步理論推導與分析.

Fig. 3 Degree distribution of clustering WSN.圖3 分簇WSN度分布

3 仿真分析

本節主要探討級聯失效模型和拓撲構造所涉及的關鍵參數(分配系數A、調節參數α、簇頭比例p、容忍系數T)對網絡級聯失效抗毀性能的影響以及如何選取合適的簇頭節點擴充容量抑制級聯失效規模.

在仿真過程中，設定網絡規模為400，且其他參數設置完全一致.仿真數值均為20次生成全新網絡后獲得的平均結果.根據網絡演化機制，每單位時刻，2種網絡模型均新增1個節點，且僅與網絡內1個已有簇頭節點相連.因此，最終所得2種網絡拓撲節點總數、簇頭節點數、邊數及節點平均度在概率條件下將會完全一致.

3.1 模型關鍵參數對網絡級聯失效抗毀性能影響

圖4為不同參數α取值時，容忍系數T與所引發級聯失效規模S之間的關聯.由圖4不難發現，參數α的取值對網絡級聯失效抗毀性能有著重要影響.當α=1時，網絡抗毀性能最優，此時，對于分簇無標度網絡，關鍵閾值Tc=1.08，即當T>Tc=1.08時，網絡對級聯失效完全免疫.對于分簇隨機網絡，抗毀性能稍弱，關鍵閾值Tc=1.14.對于隨機網絡模型，有關S的性能曲線表現出明顯的階躍特征.這是由于α值越小，初始網絡中度數較大節點與度數較小節點間的負載差異性也越不明顯，從而降低整個網絡系統對T值變化的響應度.僅當T達到某個局部階躍值時，網絡才會在局部范圍出現節點崩塌現象.根據圖4所示，當節點負載與自身度呈線性關系時(α=1)，網絡抗毀性能最優，這為網絡抵御級聯失效提供有益參考.后續仿真實驗均選取α=1進行對比分析.

Fig. 4 Relation of α，T and S in two models (p=0.3，A=0.5).圖4 2種網絡模型中α，T與S關系(p=0.3，A=0.5)

如圖5所示，分配系數A取值的上升將能夠有效提升網絡的級聯失效抗毀性能.舉例說明，對于無標度網絡分簇模型，當A=0.3時，關鍵閾值Tc=1.14；當A上升至0.7，關鍵閾值Tc則下降至1.04.根據負載分配策略，對于簇頭節點，當節點失效后，僅自身所承擔的中繼負載參與負載重分配過程.因此，A值的上升意味著網絡中可供分配的中繼負載數據量份額下降，而此時網絡容量并沒有因A值的變化而發生明顯下降，從而使網絡抵御級聯失效的能力得到提升.這就告訴網絡建設者在構造網絡過程中，為提升網絡抗毀性能，應盡可能減少因多跳轉發所帶來的數據增量.

Fig. 5 Relation of A，T and S in two models (p=0.3，α=1).圖5 2種網絡模型中A，T與S關系(p=0.3，α=1)

如圖6所示，隨著簇頭比例p取值的上升，網絡級聯失效抗毀性能也隨之下降.p值的上升意味著單個簇頭節點將可能擁有更多的鄰居簇頭節點.根據負載-容量模型，簇頭節點中繼流量與鄰居簇頭節點數量正相關，使得網絡中可供重分配的中繼負載數據量將隨著p值的上升而增加，進而導致網絡中簇頭節點面臨更大的容量過載風險.因此，為優化網絡抗毀性能，應合理控制網絡中簇頭節點規模，減少數據從采集端到Sink節點的中繼轉發環節.

Fig. 6 Relation of p，T and S in two models (A=0.5，α=1).圖6 2種網絡模型中p，T與S關系(A=0.5，α=1)

Fig. 7 Relation of p，A and Tc in two models (α=1).圖7 2種網絡模型中p，A與Tc關系(α=1)

圖7為在無標度模型與隨機模型中p，A與Tc的關系示意圖.為方便表示，在圖7中無標度模型簡寫為BA，隨機模型簡寫為ER.不難發現，在相同參數設置條件下，無標度網絡的關鍵閾值Tc均明顯小于隨機網絡，進而得到無標度網絡應對級聯失效抗毀性能優于隨機網絡這一結論.這是由于無標度網絡中絕大多數節點度數較小，移除這一類節點并不能觸發級聯失效過程.但值得注意的是，盡管無標度網絡觸發級聯失效的難度明顯高于隨機網絡，但并不意味著級聯失效過程對于無標度網絡的影響小于隨機網絡.綜合圖4至圖6分析，當級聯失效過程發生，無標度網絡級聯失效規模S高于隨機網絡.這是由于在無標度網絡中，一旦級聯失效過程發生，就通常意味著網絡中的高度數中心節點陷入失效，從而極易導致與之相連的節點相繼陷入失效狀態，進而引發大范圍網絡失效.

3.2 容量擴充策略分析

從分簇WSN級聯失效過程可以發現，當網絡中有簇頭節點失效行為發生，則失效簇頭節點所承擔的中繼負載將根據鄰居簇頭節點所擁有簇-簇連接數按比例進行重新分配.若鄰居簇頭節點容量能夠滿足失效簇頭節點中繼負載轉移的需求，則網絡級聯失效終止.因此，設計合適策略選擇網絡中部分關鍵節點進行擴容，可以達到降低網絡級聯失效規模的目的.

與無區別提升全網節點容量相比，引入針對性策略選擇關鍵節點擴充容量，可在提升網絡應對級聯失效抗毀性能的同時降低網絡硬件投入成本.因此，在本節初步探討如何設計合理的容量擴充策略控制網絡級聯失效規模.3種面向簇頭節點的容量擴充選擇策略為

1) 度大擴容策略(higher-degree scheme， HDS).依照所擁有的鄰居簇頭節點數量從高至低，從全網簇頭節點中選取比例為G的簇頭節點進行容量擴充，使擴充后的容量較初始容量提升10%.

2) 度小擴容策略(lower-degree scheme， LDS).依照所擁有的鄰居簇頭節點數量從低至高，從全網簇頭節點中選取比例為G的簇頭節點進行容量擴充，使擴充后的容量較初始容量提升10%.

3) 隨機擴容策略(random scheme， RS).從全網簇頭節點中隨機選取比例為G的簇頭節點進行容量擴充，使擴充后的容量較初始容量提升10%.

為更好對比3種擴容策略對網絡級聯失效抗毀性能的影響，分別考慮α<1，α=1，α>1這3種情形，結合3.1節關鍵參數(分配系數A、調節參數α、簇頭比例p、容忍系數T)對網絡級聯失效抗毀性能影響的仿真分析，不難得到分配系數A、簇頭比例p、容忍系數T與網絡抗毀性能均呈明顯的單調相關.而調節參數α與網絡抗毀性能具有典型的單峰函數關聯特征，僅當α=1時，網絡抗毀性能最優.因其特殊性，將調節參數α分為3個區間，重點分析不同α區間下所提3種擴容策略的效用.

Fig. 8 Comparison of lifting effects of various capacity-enlarging schemes (A=0.5，p=0.3).圖8 不同擴容策略對網絡提升效果對比(A=0.5，p=0.3)

如圖8所示，針對α<1，α=1，α>1這3種情形，3種擴容策略對網絡級聯失效抗毀性能的提升效果各不相同.針對α<1情形，設置α=0.6，無論對于無標度網絡或是隨機網絡，度小擴容策略的網絡抗毀性能提升效果最優；針對α=1情形，3種擴容策略效果相近；針對α>1情形，設置α=1.4，相比其他2種擴容策略，度大擴容策略能夠更為有效地抑制網絡級聯失效行為的發生.通過歸納不難得到：針對α<1情形，網絡中度數較小的簇頭節點失效更容易觸發級聯失效過程，因而度小擴容策略效果更為明顯；相反，對于α>1情形，網絡中度數較大的節點可被視為影響網絡級聯失效抗毀性能的主要短板，因而度大擴容策略效果更優；而針對α=1情形，網絡級聯失效抗毀性能的高低對于選取哪一類簇頭節點進行擴容并不敏感.后續理論分析針對不同擴容策略對網絡抗毀性能的提升效果做進一步闡述.

4 理論分析

本節首先對所提的2種網絡演化模型進行理論分析，以求得精確的理論度分布.并在此基礎上，理論驗證所提級聯失效模型中各關鍵參數對所提分簇WSN模型級聯失效性能的影響和不同擴容策略對網絡級聯失效抗毀性能的提升效用.

4.1 網絡模型度分布

度分布P(k)表示網絡中任意節點度數為k的概率，是評估網絡拓撲類型最直觀的參數.在本文模型中，普通簇內成員節點僅可與簇頭節點相連，因此該類節點度k始終為1.而對于簇頭節點i而言，伴隨網絡演化時刻t，ki(t)動態增長.因此，基于平均場理論[17]分別求解分簇WSN無標度拓撲與隨機拓撲度分布.

1) 分簇WSN無標度演化模型度分布

由演化機制易得，ki(t)滿足動力學方程：

(8)

考慮網絡長時間演化情形，可得：

(9)

k(t)

(10)

將式(9)與式(10)帶入式(8)，則式(8)可化簡為

(11)

對式(11)做等價變換：

(12)

式(12)為ki(t)隨t變化的微分方程，由網絡生成規則可知：節點i初加入網絡時度數為1，可得初始條件ki(ti)=1，對其進行求解，可得特解：

(13)

則簇頭節點i在時刻t滿足ki(t)

(14)

本文僅考慮以最常見的等時間間隔方式添加節點，因此，ti具有等概率密度P(ti)=1(m0+t)，則式(14)可進一步轉變為

(15)

則概率密度函數P(k)為

(16)

由冪律分布一般形式P(k)～k-γ可以看出，網絡度分布P(k)符合典型冪律分布特征，且冪律指數γ=-2-p.P(k)與簇頭比例p有密切關聯，但與網絡生長規模t無關，因此具有明顯的無標度特征.不難發現，當p=1時，網絡中所有節點均為簇頭節點，此時網絡等價為平面結構網絡，此時P(k)=2k-3與m=1時的BA無標度網絡度分布P(k)=2mk-3完全一致，P(k)正確性得到進一步驗證.

2) 分簇WSN隨機演化模型度分布

由演化機制可得，對于隨機拓撲，當前時刻t網絡中已存在簇頭節點獲得新加入連接概率完全一致，則對于簇頭節點i，ki(t)滿足動力學方程：

(17)

與無標度演化模型證明過程類似，因篇幅限制，直接給出P(k)為

(18)

P(k)為典型指數分布，與文獻[19]有關隨機網絡度分布結論一致.根據理論分析所得度分布公式，當簇頭比例p=0.2時，所提分簇WSN無標度與隨機演化模型分別服從理論度分布P(k)=1.2k-2.2與P(k)=exp(-0.2k).與圖3擬合后度分布曲線進行對比，不難得到實際度分布與理論度分布僅存在細微差異.這是由于在理論推導過程中，通常基于網絡規模足夠大這一理想情形，從而導致誤差的產生.但隨著網絡規模的擴大，理論與實際度分布曲線的重合程度將進一步得到提升.

4.2 級聯失效模型關鍵參數分析

根據負載分配策略，若簇內成員節點失效，將不會引發級聯失效過程.因此，本節僅討論簇頭節點失效對網絡拓撲影響.基于所提局域擇優分配策略與節點負載-容量模型，為避免級聯失效的發生，對于簇頭節點j，應滿足：

(19)

根據Lj與Δji定義，不等式(19)可轉化為

(20)

又因簇頭占網絡比例為p，僅考慮網絡規模足夠大情形，則不難得到cj=pkj與mj=(1-p)kj，代入式(20)，化簡可得：

(21)

[17]解析方法，根據網絡度及概率論知識，可以得知：

(22)

其中P(k′|ki)表示度為ki的簇頭節點鄰域中度為k′的條件概率，kmax和kmin分別為網絡簇頭節點度數的最大值與最小值.由4.1節關于度分布理論解析可知，所提分簇無標度演化模型與分簇隨機演化模型的拓撲性質分別與BA網絡[18]和ER網絡[19]近似，而BA網絡與ER網絡均具有典型的度-度無關特性.因此，P(k′|ki)=k′P(k′)k.進而可得的另一種表達形式：

(23)

將式(23)代入式(21)，可得:

(24)

關鍵閾值Tc為滿足式(24)條件下T值最小值，則分別考慮α<1，α=1與α>1這3種情形：

(25)

通過對式(25)解析，不難發現Tc隨著A的增大而減小，隨著p的增大而增大.結合Tc值越小網絡級聯失效抗毀性能越強這一結論，可得調節系數A與分簇WSN級聯失效抗毀性呈正相關，簇頭比例p與網絡級聯失效抗毀性能呈負相關，進一步驗證了3.1節仿真結果.進一步觀察式(25)，不難發現，當α<1時，kmin是影響Tc值的主要因素，因而擴充簇-簇連接較少的簇頭節點的容量能夠更為有效地改善網絡級聯失效抗毀性能；同理，當α>1時，擴充擁有較多鄰居簇頭數量的簇頭節點的容量，抗毀性能提升效果更為明顯；當α=1時，Tc取值僅與k和k2有關、與kmin和kmax無關，因而對于執行哪種簇頭擴容策略并不敏感.下一步我們將探討當α取何值時Tc最小，即網絡應對級聯失效的抗毀性最優.首先分析α<1情形：

(26)

可得Tc(α<1)>Tc(α=1)；同理，針對α>1情形，可證得Tc(α>1)>Tc(α=1)；因此，不難得到，當α=1時Tc最小，與3.1節仿真結果一致.

5 結 論

當前WSN抗毀性研究多從靜態角度研究移除點或邊對網絡拓撲魯棒性的影響，而忽略了網絡拓撲因負載動態變化所引發的級聯失效.因此，本文針對真實情形下普遍存在的分簇WSN，設計了參數可調的分簇WSN級聯失效演化模型，并研究分簇無標度網絡與分簇隨機網絡應對級聯失效的抗毀性能.通過仿真分析與數據推導相結合的方式得到：1)分配系數A與網絡級聯失效性能正相關；2)簇頭比例p與網絡抗毀性能負相關；3)當調節參數α=1時，網絡級聯失效抗毀性能達到最優；4)當調節參數α<1時，選取簇-簇連接度較小的簇頭節點擴充容量能夠更為有效地提升網絡級聯失效抗毀性能；5)當調節參數α>1時，選取簇-簇連接度較大的簇頭節點擴充容量抗毀性能提升效果更為明顯；6)當調節參數α=1時，網絡級聯失效規模與簇頭選取策略無關.研究成果對于預防WSN級聯失效具有實際的參考價值.在現有研究基礎上，如何有針對性地構建一種考慮擴充節點對象與擴充節點容量大小的綜合優化策略將是未來研究的重點.

參考文獻

[1]Li Jianzhong, Gao Hong. Survey on sensor network research[J]. Journal of Computer Research and Development, 2008, 45(1): 1-15 (in Chinese)(李建中, 高宏. 無線傳感器網絡的研究進展[J]. 計算機研究與發展, 2008, 45(1): 1-15)

[2]Li Wenfeng, Fu Xiuwen. Invulnerability of wireless sensor networks[J]. Chinese Journal of Computers, 2015, 38(3): 625-647 (in Chinese)(李文鋒, 符修文. 無線傳感器網絡抗毀性[J]. 計算機學報, 2015, 38(3): 625-647)

[3]Wang Liangmin, Ma Jianfeng. Self-regeneration based method for topology control with intrusion tolerance in wireless sensor networks[J]. Journal of Computer Research and Development, 2009, 46(10): 1678-1685 (in Chinese)(王良民, 馬建峰. 基于再生技術的無線傳感器網絡容侵拓撲控制方法[J]. 計算機研究與發展, 2009, 46(10): 1678-1685)

[4]Fang Xiaolin, Shi Shengfei, Li Jianzhong. A disjoint multi-path routing algorithm in wireless sensor network[J]. Journal of Computer Research and Development, 2009, 46(12): 2053-2061 (in Chinese)(方效林, 石勝飛, 李建中. 無線傳感器網絡一種不相交路徑路由算法[J]. 計算機研究與發展, 2009, 46(12): 2053-2061)

[5]Li Yaqian, Yin Rongrong, Liu Bin, et al. Cascading failure research on scale-free fault tolerance topology in wireless sensor networks[J]. Journal of Beijing University of Posts and Telecommunications, 2014, 37(2): 74-78 (in Chinese)(李雅倩, 尹榮榮, 劉彬, 等. 無線傳感器網絡無標度容錯拓撲的級聯失效研究[J]. 北京郵電大學學報, 2014, 37(2): 74-78)

[6]Yin Rongrong, Liu Bin, Liu Haoran, et al. Dynamic fault-tolerance analysis of scale-free topology in wireless sensor networks[J]. Chinese Journal of Physics, 2014, 63(11): 35-42 (in Chinese)(尹榮榮, 劉彬, 劉浩然, 等. 無線傳感器網絡中無標度拓撲的動態容錯性分析[J]. 物理學報, 2014, 63(11): 35-42)

[7]Fu Xiuwen, Li Wenfeng. Cascading failures of wireless sensor networks[C] //Proc of the 11th Int Conf on Networking, Sensing and Control (ICNSC). Piscataway, NJ: IEEE, 2014: 631-636

[8]Motter A E, Lai Y C. Cascade-based attacks on complex networks[J]. Physical Review E, 2002, 66(6): 065102

[9]Dobson I, Carreras B A, Newman D E. A loading-dependent model of probabilistic cascading failure[J]. Probability in the Engineering and Informational Sciences, 2005, 19(1): 15-32

[10]Nedic D P, Dobson I, Kirschen D S, et al. Criticality in a cascading failure blackout model[J]. International Journal of Electrical Power & Energy Systems, 2006, 28(9): 627-633

[11]Wang J W, Rong L L. Robustness of the western United States power grid under edge attack strategies due to cascading failures[J]. Safety Science, 2011, 49(6): 807-812

[12]Li Yong, Lü Xin, Tan Yuejin. Optimizing node capacity of campaign logistics networks based on cascading failures[J]. Complex System and Complexity Science, 2009, 6(1): 69-76 (in Chinese)(李勇, 呂欣, 譚躍進. 基于級聯失效的戰域保障網絡節點容量優化[J]. 復雜系統與復雜性科學, 2009, 6(1): 69-76)

[13]Yin Hongying, Quan Xiaofeng. The cascading influence law and influence scope of a failure in transportation networks[J]. Journal of Systems & Management, 2013, 22(6): 869-875 (in Chinese)(尹洪英, 權小鋒. 交通運輸網絡級聯失效影響規律及影響范圍[J]. 系統管理學報, 2013, 22(6): 869-875)

[14]Liu Y, Peng W, Su J, et al. Assessing the impact of cascading failures on the inter-domain routing system of the Internet[J]. New Generation Computing, 2014, 32(3/4): 237-255

[15]Liu H, Zhao L, Yin R, et al. A metric of topology fault-tolerance based on cascading failures for wireless sensor networks[J]. Journal of Information & Computational Science, 2011, 14(8): 3227-3237

[16]Yin R R, Liu B, Liu H R, et al. The critical load of scale-free fault-tolerant topology in wireless sensor networks for cascading failures[J]. Physica A: Statistical Mechanics and its Applications, 2014(409): 8-16

[17]Wang Jianwei, Rong Lili. Cascading failures on complex networks based on the local preferential redistribution rule of the load[J]. Chinese Journal of Physics, 2009, 58(6): 3714-3721 (in Chinese)(王建偉, 榮莉莉. 基于負荷局域擇優重新分配原則的復雜網絡上的相繼故障[J]. 物理學報, 2009, 58(6): 3714-3721)

[18]Barabási A L, Albert R, Jeong H. Mean-field theory for scale-free random networks[J]. Physica A: Statistical Mechanics and Its Applications, 1999(272): 173-187

[19]Newman M E J, Strogatz S H, Watts D J. Random graphs with arbitrary degree distributions and their applications[J]. Physical Review E, 2001, 64(2): 026118

Fu Xiuwen, born in 1987. PhD. His main research interests include the invulnerability of wireless sensor networks and the theory of complex networks.

Li Wenfeng, born in 1966. PhD, professor and PhD supervisor. His main research interests include the technologies of Internet of things and robots, and wireless sensor networks.

Duan Ying, born in 1983. PhD candidate. Her main research interests include the theory of industrial wireless sensor networks and data mining (able0607@163.com).

Invulnerability of Clustering Wireless Sensor Network Towards Cascading Failures

Fu Xiuwen1, Li Wenfeng2, and Duan Ying2

1(School of Vehicle & Transportation Engineering, Henan University of Science and Technology, Luoyang, Henan 471003)2(SchoolofLogisticsEngineering,WuhanUniversityofTechnology,Wuhan430063)

Current researches of cascading failures of wireless sensor network (WSN) mainly focus on peer-to-peer (P2P) structure. However, in real scenarios most of sensor networks always collect and deliver environmental data via clustering structure. Therefore, through observing the heterogeneity of connections in clustered networks, we construct a cascading failure model of wireless sensor network by introducing the concept of “sensing load” and “relay load”. Besides that, we discuss the relevant features between key parameters of cascading model and invulnerability of two typical clustering topologies (i.e., scale-free topology and random topology). In order to constrain the scale of cascading failures, we also discuss how to select cluster heads to enlarge their capacity to achieve this purpose. The simulation and theoretical results show that the network invulnerability is negatively correlated to the proportion of cluster headspand positively correlated to the allocation coefficientA. When adjustment coefficientα=1, the invulnerability of the network is optimized. When adjustment coefficientα<1, choosing cluster heads with fewer cluster-cluster connections is a more efficient way to enhance the network invulnerability. When adjustment coefficientα>1, choosing cluster heads with more cluster-cluster connections is more cost-effective. When adjustment coefficientα=1, the scale of cascading failures is not related to the selecting schemes of cluster heads.

wireless sensor network (WSN); cascading failures; clustering structure; invulnerability; scale-free topology; random topology

2015-06-09；

2015-09-21

國家自然科學基金項目(61571336)；中央高校基本科研業務費專項資金項目(135118003) This work was supported by the National Natural Science Foundation of China (61571336) and the Fundamental Research Funds for the Central Universities (135118003).

李文鋒(liwf@whut.edu.cn)

TP393