基于最短路徑數的WSN抗毀性評價方法

王 鑫，李 彬

(西安電子科技大學理學院，陜西西安 710071)

無線傳感器網絡(WSN)是由一組具有感知、計算、通信和協同能力的傳感器節點以Ad Hoc方式構成無線網絡，能夠協作地感知、采集和處理網絡覆蓋的地理區域中感知對象的信息，并發布給觀察者［1］。WSN在多領域尤其在無人監測或環境惡劣的情況下，在對事件檢測和事件跟蹤中具有廣闊的應用前景［2］。然而，WSN網絡中的節點即傳感器能量小易失效，網絡中的部分節點失效會導致網絡拓撲分割，降低網絡的覆蓋率，甚至導致整個網絡失敗。一般認為網絡抗毀性是指網絡在自身老化或者遭受打擊時，導致節點失效的情況下網絡拓撲結構的可靠性。衡量網絡的抗毀性常用的測度指標是用最大簇大小，孤立簇和平均路徑長度等來衡量網絡破壞程度［3］。近年來許多學者對網絡抗毀性的測度做了大量研究，文獻［4］提出基于網團分層次分析大規模網絡的抗毀性方案。文獻［5］中介紹了基于緊密度和基于介數的抗毀性評估。文獻［6］中定義了連通系數，并以此介紹了基于緊密度和基于介數的抗毀性評估。文獻［6］中定義了連通系數，并以此來衡量網絡的抗毀性。另外，由于小世界網絡具有較小的平均路徑長度和大的集聚系數的特征，故網絡具有較強的抗隨機打擊能力，文獻［7］中指出具有小世界現象的無線傳感器網絡具有明顯的簇結構，即整個網絡中出現局部的網絡結構緊湊現象。文獻［8］中提出的基于平均等效最短路徑數的網絡抗毀度適合評價WSN網絡中簇的抗毀性，但對于WSN網絡來說，其工作的目的是把收集到的數據發送到sink節點，相比一般網絡有著更強的目的性。文獻［9］根據無線傳感器網絡數據傳輸的這個特點，描述了基于有效覆蓋的網絡抗毀性。那么組成網絡的簇的抗毀性也不能準確的反映WSN網絡抗毀性。

因此，為客觀地衡量WSN網絡的抗毀性，文中提出基于簇有效平均等效最短路徑數的抗毀性評估模型。

1 無線傳感器網絡抗毀性評估模型

1.1 網絡模型與基本概念

布置的網絡為具有小世界特性的WSN網絡，如果用G表示整個網絡，圖G=(V，E)由m個簇G1，G2，…，Gm構成，若一個簇中任意一個節點到匯聚節點都至少有一條路，則稱該簇在圖G中為有效連接的。

假設WSN網絡中構成后所有節點都是靜止的，只有一個基站，網絡中的節點均知道基站的位置。在網絡形成后，網絡內的節點把采集的信息傳送給簇頭，簇頭經過數據融合以后再傳送給sink節點。

WSN網絡工作一段時間以后，隨著節點能量的消耗或節點受到打擊，而又沒有任何補救措施，則當簇內部分或全部節點與sink節點之間沒有通路時，網絡節點將無法把數據傳送給sink節點，則該簇部分或全部失效。如圖1所示。

圖1 該簇部分或是全部失效

1.2 網絡的抗毀性評估測度

小世界網絡具有較高的聚集程度和較小的平均距離的特征，文獻［7］中指出具有小世界網絡特征的WSN網絡具有明顯的簇結構，即WSN網絡中簇的緊密程度較高，因此可以用平均等效最短路徑數來衡量簇的抗毀度。

WSN網絡由若干個簇組成的，簇即是其子網，WSN網絡工作時也以簇為單元把采集的數據處理融合后再發送到sink節點。故當WSN網絡節點面臨不同的攻擊失效時，網絡中每一個簇的抗毀性也反映了整個網絡的抗毀性。

簇是WSN網絡工作時數據傳送的單位，簇內網絡節點進行通信時，首先選擇最短路徑，最短路徑阻斷時才選擇更長的路徑，節點間的最短路越多通信能力越強，抗毀性就越強，可見全連通網絡的抗毀性是最強的，比較其他網絡與全連通網絡之間的差異可以衡量該網絡的抗毀能力，由此文獻［8］中提出了基于平均最短路徑數的網絡抗毀性。

定義1節點間最短路徑的數量x與全連通網絡節點間長度不大于k的路的數量u之比就是節點間的等效最短路經數［8］，記為

若全連通網絡的節點數為N，則任意節點之間不大于k的路的數量為

對于以數據傳遞為目的的WSN網絡來說，簇內節點相互連接并不意味著網絡就有好的抗毀性，還跟與sink節點是否連通有關，隨著簇內節點受到不同的攻擊，若簇內部分或全部節點與sink節點不連通，則該簇就已經部分或全部失效。只有那些與sink節點之間存在通路的部分有效。

假設WSN網絡的簇有ω個連通分支，則該簇的抗毀度等于全網的有效平均等效最短路徑數，記為

WSN網絡由若干個簇組成，則整體網絡的抗毀性可以用每個簇的抗毀性加權的和來衡量。

若一個WSN網絡中每個簇都為全連通網絡，則該WSN網絡的抗毀度最大為1。

1.3 網絡打擊方式

無線傳感器網絡面臨的打擊方式通常有兩種:隨機性打擊和選擇性打擊。隨機性打擊就是網絡中的節點都是以一個相同的概率遭受破壞，選擇性打擊就是按照一定的策略，有選擇地破壞網絡中部分節點。

定義3(容錯度)在無線傳感器網絡中，網絡滿足一定抗毀度閾值的前提下，可以隨機移除網絡中節點數量的最大值與網路中所有節點數目之比，稱為網絡節點的容錯度。

定義4(抗攻擊度)在無線傳感器網絡中，網絡在滿足一定抗毀度閾值的前提下，可以按照一定的策略，選擇性地移除網絡中節點的數量的最大值與網絡中所有節點數目之比，稱為網絡節點的抗攻擊度。

2 相關工作比較

文獻［8］指出了在通信網中網絡節點之間最短路越多網絡的抗毀性就越強，全連通網絡的抗毀性最強，通過比較其他網絡自身結構與全連通網絡的差異來衡量其抗毀性，提出了基于全網平均等效最短路徑數的網絡抗毀度，這種方法適合評估小世界網絡中緊密程度高的簇的抗毀性，但沒有考慮網絡有效性。

文獻［9］在用網絡連通系數衡量網絡抗毀性的基礎上考慮了在WSN網絡中以數據收集為中心的特征，添加了有效覆蓋，提出了更準確的衡量WSN的抗毀性的新測度。但是沒有利用具有小世界特征的WSN網絡的簇內緊密程度高的特征。

針對具有小世界特性WSN的具體情形，考慮到WSN網絡工作時以簇為單位進行數據收集，簇的緊湊程度較高，便采用簇的平均等效最短路徑數來衡量全網的抗毀性，同時考慮到了簇的有效性即簇頭收集的數據是否可以傳遞到sink節點。表1給出了相關工作的異同點。

表1 相關工作

3 仿真實驗與分析

仿真在Matlab環境中進行，初始網絡在500×500范圍內生成200個節點，信號覆蓋范圍內節點相連。首先生成具有小世界特性的無線傳感器網絡模型［7］，再采用SMCA算法［9］對網絡進行分簇，對生成的網絡進行隨機性打擊和選擇性打擊，之后采用介紹的測度衡量網絡的抗毀度，并與文獻［8］中提出的網絡抗毀性測度進行比較。仿真效果如圖2，圖3所示。

WSN節點在受到隨機性打擊的情況下，用文獻［8］中提出的抗毀性測度評價，網絡具有更好的抗毀性，但在WSN網絡中是不夠客觀的。事實上，只有在受到隨機性打擊打擊之后仍然與sink節點有通路的簇才是有效的，即網絡抗毀性應更低，由仿真可知文中方法更具有客觀性。

在選擇性打擊sink節點附近的網絡節點時，從圖3可以看出:從文獻［8］的評估方法來看，網絡抗毀度只是有稍微的下降，而文中的評價方法來看，網絡抗毀性下降劇烈。這是因為沒有節點與sink節點相連時，數據就不能傳遞到sink節點網絡基本癱瘓。可見文中方法更有客觀準確性。

4 結束語

文中在以具有小世界特性的無線傳感器網絡模型基礎上，根據小世界網絡的具有較高的聚集性和較小平均距離的特性，提出了基于有效覆蓋的WSN網絡的簇的平均等效最短路的抗毀性評估方法，進而用簇的抗毀性衡量整個網絡的抗毀性。并對WSN網絡通常面對的兩種打擊隨機打擊和選擇性打擊給出了兩種測度容錯度和抗攻度。仿真實驗表明當網絡受到以上兩種打擊時，文中的評估方法具有更強的客觀性，更能準確地反應WSN網絡的抗毀性。

［1］TILAK S，ABU －GHAZALEH N，HEINZELMAN W.A taxonomy of wireless micro － sensor network modle［J］.Mobile Computing and Communication Review，2002，1(2):1 －8.

［2］AKYILDIZ IF，SU W，SANKARASUBRAMANIAM Y，et al.Wireless sensor network:a survey［J］.Computer Networks，2002，38(4):393 －422.

［3］丁琳，譚敏生，肖煒.復雜網絡抗毀性研究綜述［J］.電腦知識與技術，2009，5(1):51 －53.

［4］項慧慧，劉家康，匡鏡明，等.大規模通信網絡抗毀性評價方法［J］.通信學報，2008，29(3):38 －43.

［5］陶鈞，沙基昌，王暉.大規模網絡存儲系統數據訪問抗毀性建模與評估方法［J］.系統工程理論與實踐，2009，5(29):158－165.

［6］吳俊，譚躍進.復雜網絡抗毀性測度研究［J］.系統工程學報，2005，20(2):128 －131.

［7］葉秀彩，許力，林力偉.基于小世界現象的無線傳感器網絡拓撲優化［J］.福建師范大學學報，2008，24(5):37 －40.

［8］饒育萍，林競羽，周東方.網絡抗毀度和節點重要性的評價方法［J］.計算機工程，2009，35(6):14－16.

［9］林力偉，許力，葉秀彩.一種新型WSN抗毀性評價方法及其仿真實現［J］.計算機系統應用，2010，19(4):32 －36.

［10］REKA A，HAWOONG J，ALBERT － LASZLO B.Error and attack tolerance of complex networks［J］.Nature，2000，406(6749):378－382.

［11］王良民，馬建峰，王超.無線傳感器網絡拓撲的容錯度與容侵度［J］.電子學報，2006，34(8):1446 －1451.