基于介數中心性的無線傳感器網絡抗毀性評價方法*

王 燦，吳 雪，羅小娟

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

0 引 言

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

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

1 WSNs 節點介數中心性

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

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

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

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

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

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

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

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

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

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

2 WSNs 介數熵測度模型

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

3 網絡抗毀性仿真分析

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

3.1 介數中心性最高節點失效后抗毀性分析

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

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

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

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

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

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

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

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

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

3.2 節點度最高節點失效后抗毀性分析

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

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

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

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

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

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

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

4 結 論

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

［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］ 劉媛妮.復雜網絡抗毀性建模優化及其評估技術研究［D］.北京:北京郵電大學，2011:97－112.

［5］ 吳 俊，譚躍進.網絡結構熵及其在非標度網絡中的應用［J］.系統工程理論與實踐，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.