王 鑫，李 彬

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

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

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

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

1.1 網絡模型與基本概念

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

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

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

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

1.2 網絡的抗毀性評估測度

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

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

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

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

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

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

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

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

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

1.3 網絡打擊方式

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

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

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

2 相關工作比較

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

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

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

表1 相關工作

3 仿真實驗與分析

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

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

在選擇性打擊sink節(jié)點附近的網絡節(jié)點時，從圖3可以看出:從文獻［8］的評估方法來看，網絡抗毀度只是有稍微的下降，而文中的評價方法來看，網絡抗毀性下降劇烈。這是因為沒有節(jié)點與sink節(jié)點相連時，數(shù)據就不能傳遞到sink節(jié)點網絡基本癱瘓?？梢娢闹蟹椒ǜ锌陀^準確性。

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］項慧慧，劉家康，匡鏡明，等.大規(guī)模通信網絡抗毀性評價方法［J］.通信學報，2008，29(3):38 －43.

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

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

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

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

［9］林力偉，許力，葉秀彩.一種新型WSN抗毀性評價方法及其仿真實現(xiàn)［J］.計算機系統(tǒng)應用，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.