王 燦，吳 雪，羅小娟

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

0 引 言

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

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

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

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

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

如圖1 所示，當(dāng)匯聚節(jié)點(diǎn)在WSNs 的右側(cè)時(shí)，信息會(huì)由左向右傳遞，如箭頭所示，此時(shí)節(jié)點(diǎn)4 和5 將是網(wǎng)絡(luò)核心節(jié)點(diǎn)，其重要性最高。當(dāng)匯聚節(jié)點(diǎn)位于WSNs 的上方時(shí)，信息將沿著由下往上方向傳遞，此時(shí)網(wǎng)絡(luò)核心節(jié)點(diǎn)將是節(jié)點(diǎn)1和6。

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

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

其中，n 為網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)，nk(i)為節(jié)點(diǎn)k 到匯聚節(jié)點(diǎn)的最短路徑中經(jīng)過節(jié)點(diǎn)i 的個(gè)數(shù)，nk為節(jié)點(diǎn)k 到匯聚節(jié)點(diǎn)的所有最短路徑的個(gè)數(shù)，節(jié)點(diǎn)k 為網(wǎng)絡(luò)中除匯聚節(jié)點(diǎn)外的任意節(jié)點(diǎn)。

由圖2 所示為WSNs 拓?fù)浣Y(jié)構(gòu)，分別利用復(fù)雜網(wǎng)絡(luò)節(jié)點(diǎn)介數(shù)中心性度量方法和本文提出的WSNs 節(jié)點(diǎn)介數(shù)中心性來計(jì)算每個(gè)節(jié)點(diǎn)的中心性，結(jié)果如表1 所示。

圖2 一種典型的WSNs 拓?fù)浣Y(jié)構(gòu)Fig 2 A typical topology structure of WSNs

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

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

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

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

3 網(wǎng)絡(luò)抗毀性仿真分析

在Matlab 2014 環(huán)境下進(jìn)行模擬仿真研究，有WSNs 的網(wǎng)絡(luò)拓?fù)淙鐖D3 所示，分別對(duì)其采用基于度數(shù)的網(wǎng)絡(luò)結(jié)構(gòu)熵方法、文獻(xiàn)［4］中基于節(jié)點(diǎn)介數(shù)的網(wǎng)絡(luò)結(jié)構(gòu)熵方法、本文提出的介數(shù)熵方法進(jìn)行抗毀性測度分析，仿真結(jié)果見表2。

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

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

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

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

1)計(jì)算各節(jié)點(diǎn)至匯聚節(jié)點(diǎn)的最短路徑。

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

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

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

圖3 初始網(wǎng)絡(luò)拓?fù)鋱DFig 3 Initial network topology

圖4 節(jié)點(diǎn)6 失效后的網(wǎng)絡(luò)拓?fù)鋱DFig 4 Network topology after node 6 is failed

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

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

3.3 葉節(jié)點(diǎn)失效后網(wǎng)絡(luò)抗毀性測度分析

圖5 節(jié)點(diǎn)5 失效后的網(wǎng)絡(luò)拓?fù)鋱DFig 5 Network topology after node 5 is failed

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

圖6 節(jié)點(diǎn)1 失效后的網(wǎng)絡(luò)拓?fù)銯ig 6 Network topology after node 1 is failed

表2 基于不同網(wǎng)絡(luò)熵的抗毀性測度對(duì)比Tab 2 Invulnerability measurement comparison based on different WSNs entropy

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

4 結(jié) 論

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

［1］ 鄭耿忠，劉三陽，齊小剛.基于無標(biāo)度網(wǎng)絡(luò)的無線傳感器網(wǎng)絡(luò)拓?fù)溲莼Ｐ脱芯浚跩］.高技術(shù)通訊，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］ 鄒訓(xùn)麗.基于復(fù)雜網(wǎng)絡(luò)理論的無線傳感器網(wǎng)絡(luò)抗毀性測度研究［D］.上海:華東理工大學(xué)，2012:21－33.

［4］ 劉媛妮.復(fù)雜網(wǎng)絡(luò)抗毀性建模優(yōu)化及其評(píng)估技術(shù)研究［D］.北京:北京郵電大學(xué)，2011:97－112.

［5］ 吳 俊，譚躍進(jìn).網(wǎng)絡(luò)結(jié)構(gòu)熵及其在非標(biāo)度網(wǎng)絡(luò)中的應(yīng)用［J］.系統(tǒng)工程理論與實(shí)踐，2004(6):1－3.

［6］ 榮莉莉，郭天柱，王建偉.復(fù)雜網(wǎng)絡(luò)中心性［J］.上海理工大學(xué)學(xué)報(bào)，2008，30(3):227－236.

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