王 燦，吳 雪，羅小娟

(華東理工大學 信息科學與工程學院，上海200237)

0 引 言

抗毀性是衡量無線傳感器網絡(wireless sensor networks，WSNs)在部分節(jié)點發(fā)生內部故障或者受到外界有意攻擊而失效時，網絡仍能維持其正常功效的能力［1］。目前國內外針對網絡抗毀性測度的研究很多，大部分的方法都是以網絡連通性來進行衡量。文獻［2］首先從網絡連通度角度考慮提出了WSNs 的兩個抗毀性測度:有效連通子圖和最大連通子圖。文獻［3］提出了基于節(jié)點重要度的WSNs 抗毀熵測度模型。文獻［4］提出了基于節(jié)點介數(shù)的網絡結構熵，該方法可以有效地評估一般復雜網絡的抗毀性特征。

WSNs 不同于一般復雜網絡之處在于它以數(shù)據(jù)收集為中心，本文針對這一特性，提出了WSNs 節(jié)點介數(shù)中心性概念，用以評估網絡中節(jié)點的重要性?；谖墨I［5］提出的網絡結構熵，本文提出了介數(shù)熵抗毀性測度模型，仿真結果表明:它能全面、準確地評估WSNs 抗毀性。

1 WSNs 節(jié)點介數(shù)中心性

節(jié)點之間數(shù)據(jù)的傳輸主要依賴于最短路徑，如果某個節(jié)點被許多最短路徑經過，則說明該節(jié)點在網絡中很重要。介數(shù)中心性定義為網絡中所有最短路徑中經過某一節(jié)點的路徑數(shù)目在最短路徑總數(shù)中占有的比例，反映了相應的節(jié)點在整個網絡中的作用和影響力［6］。因此，可利用介數(shù)中心性來度量節(jié)點重要性。

相比于一般復雜網絡，WSNs 是以數(shù)據(jù)收集為目的，每個節(jié)點都要將收集到的數(shù)據(jù)傳遞給匯聚節(jié)點。因此，還需要考慮匯聚節(jié)點的因素。

如圖1 所示，當匯聚節(jié)點在WSNs 的右側時，信息會由左向右傳遞，如箭頭所示，此時節(jié)點4 和5 將是網絡核心節(jié)點，其重要性最高。當匯聚節(jié)點位于WSNs 的上方時，信息將沿著由下往上方向傳遞，此時網絡核心節(jié)點將是節(jié)點1和6。

圖1 匯聚節(jié)點位置對節(jié)點中心性的影響Fig 1 Effect of location of sink node on node centrality

本文基于復雜網絡的介數(shù)中心性［7］，并結合WSNs以數(shù)據(jù)收集為中心這一特點，提出WSNs 介數(shù)中心性定義為

其中，n 為網絡節(jié)點數(shù)，nk(i)為節(jié)點k 到匯聚節(jié)點的最短路徑中經過節(jié)點i 的個數(shù)，nk為節(jié)點k 到匯聚節(jié)點的所有最短路徑的個數(shù)，節(jié)點k 為網絡中除匯聚節(jié)點外的任意節(jié)點。

由圖2 所示為WSNs 拓撲結構，分別利用復雜網絡節(jié)點介數(shù)中心性度量方法和本文提出的WSNs 節(jié)點介數(shù)中心性來計算每個節(jié)點的中心性，結果如表1 所示。

圖2 一種典型的WSNs 拓撲結構Fig 2 A typical topology structure of WSNs

表1 兩種中心性度量對比Tab 1 Comparison of two centrality measurement

分析表1 可以看到:利用復雜網絡節(jié)點介數(shù)中心性，節(jié)點3 和節(jié)點4 都比節(jié)點2 的數(shù)值大，但是在實際網絡中，一旦節(jié)點2 失效，整個網絡就會崩潰，而節(jié)點3 或者節(jié)點4 失效后，網絡50%的節(jié)點依舊可以正常工作，因此，在實際網絡中節(jié)點2 比節(jié)點3 和節(jié)點4 都重要。對比分析本文提出的WSNs 介數(shù)中心性，節(jié)點2 的WSNs 介數(shù)中心性值是節(jié)點3 和節(jié)點4 數(shù)值的2 倍，而其他節(jié)點的介數(shù)中心性值都要比上述三個節(jié)點小，這與實際網絡結構是相符的。由此可見，本文提出的WSNs 介數(shù)中心性可以更準確地定量描述一個節(jié)點的重要性。

2 WSNs 介數(shù)熵測度模型

由于網絡拓撲結構中含有核心節(jié)點，這些節(jié)點往往處于比較重要的位置，這就意味著利用該節(jié)點進行信息傳遞的次數(shù)可能會遠遠超過其他節(jié)點。另外，這些節(jié)點承受的信息負載量重。轉發(fā)信息時更容易出現(xiàn)數(shù)據(jù)包丟失，擁塞加劇，最終導致鏈路中斷等情況。因此，可從節(jié)點重要性考慮，建立抗毀性測度模型。由前述可知，本文提出的WSNs節(jié)點介數(shù)中心性可以有效地評估網絡中節(jié)點的重要性，在此基礎上，給出節(jié)點的抗毀度概念，節(jié)點抗毀度表示為

3 網絡抗毀性仿真分析

在Matlab 2014 環(huán)境下進行模擬仿真研究，有WSNs 的網絡拓撲如圖3 所示，分別對其采用基于度數(shù)的網絡結構熵方法、文獻［4］中基于節(jié)點介數(shù)的網絡結構熵方法、本文提出的介數(shù)熵方法進行抗毀性測度分析，仿真結果見表2。

3.1 介數(shù)中心性最高節(jié)點失效后抗毀性分析

為整個網絡所有節(jié)點的WSNs 介數(shù)中心性之和，提出的節(jié)點抗毀度用來衡量節(jié)點對網絡抗毀性的貢獻。如果網絡是均勻的，各個節(jié)點的抗毀度相差不大，則認為該網絡是均勻的;反之，如果網絡中有少量的關鍵節(jié)點，其抗毀度較大，另外還有很多的邊緣節(jié)點，節(jié)點的抗毀度較小，則可以認為這種網絡是不均勻的。為度量WSNs 節(jié)點抗毀度的均勻性，本文提出了介數(shù)熵測度模型，WSNs 介數(shù)熵為

其中，Si為節(jié)點i 的抗毀度。介數(shù)熵反映的是節(jié)點抗毀度分布的差異性，網絡節(jié)點抗毀度差異性越小，熵值就越大，面對選擇性攻擊的抗毀性能越好;反之，則面對選擇性攻擊的抗毀性能越差。

基于介數(shù)熵的WSNs 抗毀性評價方法的算法步驟:

1)計算各節(jié)點至匯聚節(jié)點的最短路徑。

3)根據(jù)公式(2)計算每個節(jié)點的WSNs 抗毀度Si。

4)根據(jù)公式(3)計算該網絡的介數(shù)熵E，給出網絡的抗毀性測度。

在圖3 所示的網絡拓撲圖中，選擇攻擊介數(shù)中心性最高的節(jié)點6，節(jié)點6 失效后，網絡拓撲圖如圖4 所示。分析表2 中數(shù)據(jù)可以看出:基于節(jié)點度的網絡結構熵評估出的網絡抗毀能力，在節(jié)點6 失效后，基本沒有發(fā)生變化(變化率約為0.08%);而文獻［4］中提出的基于節(jié)點介數(shù)網絡結構熵，得出的結果顯示，網絡抗毀性下降了52.4%;根據(jù)本文提出的介數(shù)熵模型計算結果為0，表示網絡中不存在通往匯聚節(jié)點的最短路徑。從節(jié)點6 失效的實際意義來看，節(jié)點6 是連接節(jié)點5、節(jié)點7、節(jié)點12 三個節(jié)點所控制的各自小網絡的樞紐，節(jié)點6 失效后，這三個小網絡就只能在各自內部通信，失去了和匯聚節(jié)點通信的能力，對于WSNs 而言，網絡已經崩潰。因此，前兩種方法在評估節(jié)點6 這樣的度數(shù)雖然不大，但是介數(shù)很大的節(jié)點受到攻擊后，對WSNs連通性造成的影響方面存在著極大的不足，而本文提出的介數(shù)熵，則可以有效地評估網絡抗毀能力。

圖3 初始網絡拓撲圖Fig 3 Initial network topology

圖4 節(jié)點6 失效后的網絡拓撲圖Fig 4 Network topology after node 6 is failed

3.2 節(jié)點度最高節(jié)點失效后抗毀性分析

在圖3 中，節(jié)點度最高的點是節(jié)點5、節(jié)點7 和節(jié)點12，且三個節(jié)點的失效對網絡影響是等效的，不失一般性，選擇攻擊節(jié)點5，圖5 為節(jié)點5 失效后的網絡拓撲。再次分析表2 中的數(shù)據(jù)，基于節(jié)點度的網絡結構熵和文獻［4］中的基于節(jié)點介數(shù)網絡結構熵熵值都有所下降，下降的比值分別為14.7%和19.9%，本文提出的介數(shù)熵則下降了33.3%。結合實際網絡分析，節(jié)點5 失效后，節(jié)點5 所控制的那部分小網絡失去了跟匯聚節(jié)點通信的能力，即節(jié)點5的失效直接導致了網絡中有1/3 的節(jié)點隨之失效，網絡整體連通性下降了1/3，由此可見，本文提出的介數(shù)熵更準確地反映了這種破壞程度下網絡的抗毀性測度。

3.3 葉節(jié)點失效后網絡抗毀性測度分析

圖5 節(jié)點5 失效后的網絡拓撲圖Fig 5 Network topology after node 5 is failed

在圖3 所示的網絡拓撲圖中，除節(jié)點5、節(jié)點6、節(jié)點7和節(jié)點12 外，剩余節(jié)點都是葉節(jié)點，且這12 個葉節(jié)點的失效對網絡影響是等效的，不失一般性，選擇攻擊節(jié)點1，節(jié)點1 失效后的網絡拓撲如圖6 所示。分析表2 中的數(shù)據(jù)，基于節(jié)點度的網絡結構熵和文獻［4］中的基于節(jié)點介數(shù)網絡結構熵的熵值都有所下降，下降的比值分別為12.23%和12.22%，本文提出的介數(shù)熵則下降了6.25%。結合實際網絡分析，節(jié)點1 失效后，僅節(jié)點1 失去了跟匯聚節(jié)點通信的能力，網絡失去了16 條通信鏈路中的一條，對比之下，本文提出的介數(shù)熵更好地反映了WSNs 在這種破壞情況下的抗毀性程度。

圖6 節(jié)點1 失效后的網絡拓撲Fig 6 Network topology after node 1 is failed

表2 基于不同網絡熵的抗毀性測度對比Tab 2 Invulnerability measurement comparison based on different WSNs entropy

綜上，可以得出結論:本文提出的介數(shù)熵在評估WSNs抗毀性能時，具有更好的效果，并且利用該測度模型來評估網絡抗毀性能的好壞時考慮了選擇性打擊的方式，因而，該方法更全面地評估了網絡的抗毀性。

4 結 論

網絡抗毀性在一定程度上反映了網絡能夠抵御攻擊的能力?，F(xiàn)實中的網絡呈現(xiàn)出節(jié)點度分布符合冪率分布的無標度特性，即大量的節(jié)點擁有較小的連接，而少數(shù)節(jié)點卻存在較大的連接。網絡的這種不均勻特性，可以用物理意義上的“熵”來表征。由此，本文提出了介數(shù)熵的網絡抗毀性測度模型，仿真分析表明:使用該測度模型能夠有效、客觀地反映網絡在受到不同程度攻擊后網絡抗毀性的變化情況。

［1］ 鄭耿忠，劉三陽，齊小剛.基于無標度網絡的無線傳感器網絡拓撲演化模型研究［J］.高技術通訊，2011，21(11):1219－1225.

［2］ Fu Xiuwen，Li Wenfeng.Empowering the invulnerability of wireless sensor networks through super wires and super nodes［C］∥13th IEEE/ACM International Symposium on Cluster，Cloud，and Grid Computing，2013:561－568.

［3］ 鄒訓麗.基于復雜網絡理論的無線傳感器網絡抗毀性測度研究［D］.上海:華東理工大學，2012:21－33.

［4］ 劉媛妮.復雜網絡抗毀性建模優(yōu)化及其評估技術研究［D］.北京:北京郵電大學，2011:97－112.

［5］ 吳 俊，譚躍進.網絡結構熵及其在非標度網絡中的應用［J］.系統(tǒng)工程理論與實踐，2004(6):1－3.

［6］ 榮莉莉，郭天柱，王建偉.復雜網絡中心性［J］.上海理工大學學報，2008，30(3):227－236.

［7］ Freeman C.A set of measures of centrality based upon betweenness［J］.Sociometry，1977，40(1):35－41.