劉琳嵐 張 江 舒 堅 郭 凱 孟令沖

1(南昌航空大學信息工程學院 南昌 330063)2 (南昌航空大學軟件學院 南昌 330063)

基于多屬性決策的機會傳感器網(wǎng)絡(luò)關(guān)鍵節(jié)點預(yù)測

劉琳嵐1張 江1舒 堅2郭 凱1孟令沖1

1(南昌航空大學信息工程學院 南昌 330063)2(南昌航空大學軟件學院 南昌 330063)

(liulinlan@nchu.edu.cn)

提前獲知或預(yù)測網(wǎng)絡(luò)的關(guān)鍵節(jié)點,便可根據(jù)關(guān)鍵節(jié)點的相關(guān)信息對網(wǎng)絡(luò)進行優(yōu)化,當網(wǎng)絡(luò)癱瘓時,可第一時間排查關(guān)鍵節(jié)點,減少網(wǎng)絡(luò)維護時間和成本.現(xiàn)有靜態(tài)無線傳感器網(wǎng)絡(luò)關(guān)鍵節(jié)點預(yù)測方法,不適用于機會傳感器網(wǎng)絡(luò)(opportunistic sensor networks, OSNs).針對機會傳感器網(wǎng)絡(luò)結(jié)構(gòu)動態(tài)變化、消息傳輸時延高的特點,分析多區(qū)域機會傳感器網(wǎng)絡(luò)分層結(jié)構(gòu)的消息傳輸過程,定義階段貢獻度反映Ferry節(jié)點在消息傳輸過程中的貢獻程度,定義區(qū)域貢獻度反映Ferry節(jié)點對區(qū)域的貢獻程度.在此基礎(chǔ)上,以Ferry節(jié)點在網(wǎng)絡(luò)中的綜合貢獻度作為判斷關(guān)鍵節(jié)點的依據(jù),提出基于多屬性決策中理想點法(technique for order preference by similarity to ideal solution, TOPSIS)的關(guān)鍵節(jié)點預(yù)測方法.實驗結(jié)果表明:采用改進TOPSIS算法能夠獲得更高的預(yù)測精度;搭建了實驗床以進一步驗證提出的預(yù)測方法,結(jié)果表明,采用改進TOPSIS算法的預(yù)測精度更高.

機會傳感器網(wǎng)絡(luò);關(guān)鍵節(jié)點;區(qū)域貢獻度;階段貢獻度;多屬性決策

機會傳感器網(wǎng)絡(luò)(opportunistic sensor networks, OSNs)是一種利用節(jié)點移動帶來的相遇機會實現(xiàn)通信的自組織網(wǎng)絡(luò),具有移動自組織網(wǎng)絡(luò)(mobile ad hoc network, MANET)和延遲容忍網(wǎng)絡(luò)(delay tolerant network, DTN)的特點[1],常被應(yīng)用于野生動物追蹤[2]、森林環(huán)境監(jiān)測[3]以及智能交通[4]等方面,網(wǎng)絡(luò)中某些節(jié)點的損壞可能導致整個網(wǎng)絡(luò)運行不正常,甚至癱瘓,這種節(jié)點被稱為關(guān)鍵節(jié)點.如能提前獲知或預(yù)測網(wǎng)絡(luò)的關(guān)鍵節(jié)點,便可根據(jù)關(guān)鍵節(jié)點的相關(guān)信息對網(wǎng)絡(luò)進行優(yōu)化,并盡可能地消除關(guān)鍵節(jié)點,以增強網(wǎng)絡(luò)的健壯性;網(wǎng)絡(luò)運行過程中,通過重點監(jiān)視關(guān)鍵節(jié)點的狀態(tài)、及時維護關(guān)鍵節(jié)點,以確保網(wǎng)絡(luò)正常運行;一旦網(wǎng)絡(luò)出現(xiàn)癱瘓,能夠第一時間排查關(guān)鍵節(jié)點是否正常,可減少網(wǎng)絡(luò)維護的時間和成本.本文研究OSNs的關(guān)鍵節(jié)點預(yù)測方法.

目前,主要有基于準則[5-6]、基于參數(shù)[7]和基于節(jié)點重要度[8-9]的關(guān)鍵節(jié)點預(yù)測方法.傳統(tǒng)網(wǎng)絡(luò)中關(guān)鍵節(jié)點的預(yù)測方法不再適用于機會傳感器網(wǎng)絡(luò).本文針對OSNs消息傳輸時延高、網(wǎng)絡(luò)拓撲變化頻繁的特點,探索其關(guān)鍵節(jié)點的預(yù)測方法,為OSNs的實際應(yīng)用提供支撐.

通過分析OSNs中區(qū)域節(jié)點與Sink節(jié)點之間的消息傳輸過程,以Ferry節(jié)點在該過程中的貢獻衡量Ferry節(jié)點的重要程度,主要工作如下:1)將OSNs抽象成多區(qū)域機會傳感器網(wǎng)絡(luò)(multi-region opportunistic sensor networks, MOSNs);2)分析OSNs的拓撲特性,定義關(guān)鍵節(jié)點及割點;3)分析 OSNs的分層結(jié)構(gòu),將其消息傳輸過程分為3個階段,定義Ferry節(jié)點的階段貢獻度及區(qū)域貢獻度;4)提出基于改進多屬性決策中理想點法(technique for order preference by similarity to ideal solution, TOPSIS)的OSNs關(guān)鍵節(jié)點預(yù)測方法;5)通過仿真實驗和實驗床實驗驗證本文提出的方法.

1 相關(guān)研究

國內(nèi)外學者對網(wǎng)絡(luò)割點(關(guān)鍵節(jié)點)的判定[5,10-12]、節(jié)點重要度的評估[13-15]、多屬性決策理論在無線傳感器網(wǎng)絡(luò)中的應(yīng)用[16-17]進行了研究.

文獻[5]將覆蓋網(wǎng)絡(luò)中的所有非葉子節(jié)點視為候選割點,每一個候選割點都可發(fā)起主動探測命令,如果某候選割點有2個或2個以上的鄰居之間不存在回路,則認定該疑似割點為實際割點;文獻[11]針對引起耦合網(wǎng)絡(luò)級聯(lián)失效的節(jié)點,提出Max-Cas算法,采用最大連通分支的節(jié)點數(shù)鑒別關(guān)鍵節(jié)點;文獻[12]利用前一時刻的關(guān)鍵節(jié)點集更新動態(tài)網(wǎng)絡(luò)的關(guān)鍵節(jié)點,達到自適應(yīng)探測關(guān)鍵節(jié)點的目的,針對動態(tài)網(wǎng)絡(luò),提出無需重復計算的關(guān)鍵節(jié)點自適應(yīng)檢測算法;文獻[6]提出適用于大規(guī)模ad hoc網(wǎng)絡(luò)的分布式拓撲分割探測算法(distributed partition detection protocol, DPDP),若網(wǎng)絡(luò)中節(jié)點的鄰節(jié)點度N和基本回路度M滿足N-M≥2,則判定該節(jié)點為割點.

文獻[18]指出加權(quán)網(wǎng)絡(luò)中,任意2個節(jié)點對之間最重要的節(jié)點是移除后使這2個節(jié)點間的最短距離增加最多的那個節(jié)點;文獻[19]比較通信網(wǎng)絡(luò)中生成樹的數(shù)目評價任意數(shù)目的2組節(jié)點的重要程度;文獻[20]考慮節(jié)點自身屬性及其m階鄰居節(jié)點的屬性,提出復雜網(wǎng)絡(luò)的節(jié)點重要度評價方法;文獻[8]利用領(lǐng)域“結(jié)構(gòu)洞”判別社會網(wǎng)絡(luò)的最具影響力節(jié)點,即關(guān)鍵節(jié)點;文獻[7]綜合考慮節(jié)點度、接近度[21]、介數(shù)[22]、等價拓撲結(jié)構(gòu)、鄰居列表的影響,評估節(jié)點在復雜網(wǎng)絡(luò)中的重要程度;文獻[9]針對節(jié)點刪除法存在的不足,定義節(jié)點效率和節(jié)點重要度評價矩陣,利用重要度評價矩陣確定復雜網(wǎng)絡(luò)的關(guān)鍵節(jié)點;文獻[23]提出以節(jié)點“移除”導致的網(wǎng)絡(luò)能耗值為衡量基準,并考慮節(jié)點剩余生命期,采用節(jié)點刪除法評價節(jié)點在無線傳感器網(wǎng)絡(luò)中的重要程度.

文獻[16]提出基于傳感器節(jié)點信譽度集對分析的安全數(shù)據(jù)進行融合,并采用多屬性決策方法選擇轉(zhuǎn)發(fā)下一跳數(shù)據(jù)的節(jié)點;文獻[17]針對無線傳感器網(wǎng)絡(luò)易出現(xiàn)數(shù)據(jù)流量集中于少數(shù)路徑的現(xiàn)象,提出基于多屬性決策的能量平衡路由策略MADMR(multiple attribute decision making routing).

本文參考文獻[6],考慮OSNs的傳輸特點,定義OSNs的關(guān)鍵節(jié)點及割點,定義區(qū)域貢獻度反映區(qū)域?qū)erry節(jié)點的依賴程度,采用多屬性決策(multiple attribute decision making, MADM)方法預(yù)測OSNs的關(guān)鍵節(jié)點.

2 場景模型及定義

根據(jù)OSNs分層結(jié)構(gòu)的特點,分析OSNs中關(guān)鍵節(jié)點的特點,定義OSNs關(guān)鍵節(jié)點、區(qū)域貢獻度.

2.1 OSNs場景模型

本文研究場景如圖1[24]所示,區(qū)域內(nèi)感知節(jié)點發(fā)送消息至移動節(jié)點,移動節(jié)點通過1次或多次轉(zhuǎn)發(fā)將消息發(fā)送至Sink節(jié)點.

Fig. 1 MOSNs scenario圖1 MOSNs場景

將一個區(qū)域抽象成一個“超級節(jié)點”,稱為區(qū)域節(jié)點,得到MOSNs模型,如圖2所示,R1,R2,R3,R4為區(qū)域節(jié)點,F1,F2,F3為Ferry節(jié)點.

Fig. 2 MOSNs model圖2 MOSNs模型

MOSNs由3類節(jié)點構(gòu)成:Sink節(jié)點、Ferry節(jié)點和區(qū)域節(jié)點.區(qū)域節(jié)點負責感知周圍物理世界,Sink節(jié)點負責匯聚網(wǎng)絡(luò)消息,區(qū)域節(jié)點和Sink節(jié)點固定不動,相互之間不連通;Ferry節(jié)點負責轉(zhuǎn)發(fā)消息,以隨機游走或按一定規(guī)律在區(qū)域節(jié)點和Sink間移動,通過“存儲—攜帶—轉(zhuǎn)發(fā)”方式建立區(qū)域節(jié)點與Sink節(jié)點之間的通信.根據(jù)節(jié)點功能的不同,將整個網(wǎng)絡(luò)劃分為3層,如圖3[25]所示.

Fig. 3 MOSNs hierarchical structure圖3 MOSNs的分層結(jié)構(gòu)

2.2 MOSNs的關(guān)鍵節(jié)點

關(guān)鍵節(jié)點的概念來自圖論,目前仍沒有統(tǒng)一的定義.本文針對MOSNs的特點,以網(wǎng)絡(luò)分裂概率為衡量標準,定義關(guān)鍵節(jié)點.

定義1. 關(guān)鍵節(jié)點.設(shè)G表示MOSNs,若G中某節(jié)點F移除后網(wǎng)絡(luò)產(chǎn)生分裂的可能性最大,則稱F為G的關(guān)鍵節(jié)點.

定義2. 割點.設(shè)G表示MOSNs,若移除某節(jié)點C后網(wǎng)絡(luò)G產(chǎn)生分裂,則稱C為網(wǎng)絡(luò)G的割點.

由定義1、定義2得到推論1、推論2.

推論1. MOSNs的割點一定是關(guān)鍵節(jié)點.

證明. 由定義2可知,移除MOSNs的割點后,網(wǎng)絡(luò)一定產(chǎn)生分裂.即移除MOSNs的割點后,網(wǎng)絡(luò)產(chǎn)生分裂的概率為100%,故MOSNs的割點一定是關(guān)鍵節(jié)點.

證畢.

與傳統(tǒng)無線傳感器網(wǎng)絡(luò)不同,MOSNs中Ferry節(jié)點的位置運動變化,其拓撲隨之變化,即MOSNs處于間歇性連通狀態(tài),只要該間歇時間間隔在實際應(yīng)用可容忍的范圍內(nèi),便可認為整個網(wǎng)絡(luò)是連通的.如果由于部分節(jié)點損毀、丟失或Ferry節(jié)點提供的通信機會不夠頻繁,使得網(wǎng)絡(luò)的間歇時間間隔大于最大容忍值,便認為MOSNs不連通,也就是說,MOSNs結(jié)構(gòu)出現(xiàn)了分裂,這些導致MOSNs產(chǎn)生分裂的節(jié)點就是關(guān)鍵節(jié)點.由上述分析可知,MOSNs的Ferry節(jié)點最有可能成為關(guān)鍵節(jié)點,但是,哪些Ferry節(jié)點是MOSNs的關(guān)鍵節(jié)點?這就是本文需要解決的問題.

為便于研究,本文進行如下假設(shè):

1) 將每個區(qū)域抽象成一個“超級節(jié)點”,稱區(qū)域節(jié)點;

2) 設(shè)Ferry節(jié)點的內(nèi)存足夠存儲其經(jīng)過區(qū)域時收集的全部消息;

3) MOSNs中區(qū)域節(jié)點、Ferry節(jié)點及Sink節(jié)點均有唯一的標識;

4) MOSNs已具備時鐘同步機制.

2.3 階段貢獻度

Ferry節(jié)點是MOSNs的消息傳輸媒介,對整個網(wǎng)絡(luò)至關(guān)重要,部分Ferry節(jié)點可能是關(guān)鍵節(jié)點.通過分析MOSNs的路由機制和分層結(jié)構(gòu),不難發(fā)現(xiàn),感知消息從產(chǎn)生到最終投遞到Sink的過程,可分為3個階段:消息投遞階段、消息轉(zhuǎn)發(fā)階段和消息到達階段,如圖4所示:

Fig. 4 MOSNs message transmission process圖4 MOSNs消息傳播過程

1) 消息投遞階段.Ferry節(jié)點將感知消息帶離區(qū)域.

2) 消息轉(zhuǎn)發(fā)階段.消息在Ferry節(jié)點間轉(zhuǎn)發(fā).

3) 消息到達階段.消息被Ferry節(jié)點投遞至Sink.

定義3. 第1階段貢獻度(first stage contribu-tion, FSC).設(shè)時間T內(nèi),Sink收到Mj條來自區(qū)域Rj的消息,如果Ferry節(jié)點Fi在消息投遞階段共接收ni j(ni j≤Mj)條來自區(qū)域Rj的消息,則Fi對區(qū)域Rj的第1階段貢獻度為ni jMj,記為FSC(Fi,Rj).

定義4. 第2階段貢獻度(second stage contri-bution, SSC). 設(shè)時間T內(nèi),Sink收到Mj條來自區(qū)域Rj的消息,如果Ferry節(jié)點Fi在消息轉(zhuǎn)發(fā)階段共轉(zhuǎn)發(fā)mi j(mi j≤Mj)條來自區(qū)域Rj的消息,則Fi對區(qū)域Rj的第2階段貢獻度為mi jMj,記為SSC(Fi,Rj).

定義5. 第3階段貢獻度(third stage contribu-tion, TSC). 設(shè)時間T內(nèi),Sink收到Mj條來自區(qū)域Rj的消息,如果Ferry節(jié)點Fi在消息到達階段共投遞ki j(ki j≤Mj)條來自區(qū)域Rj的消息至Sink節(jié)點,且Fi對區(qū)域Rj的第3階段貢獻度為ki jMj,記為TSC(Fi,Rj).

顯然,FSC反映了Ferry節(jié)點在消息投遞階段對消息傳輸?shù)呢暙I程度;SSC反映了Ferry節(jié)點在消息轉(zhuǎn)發(fā)階段對消息傳輸?shù)呢暙I程度;TSC反映了Ferry節(jié)點在消息到達階段對消息傳輸?shù)呢暙I程度.

2.4 區(qū)域貢獻度

定義6. 區(qū)域貢獻度(region contribution, RC). 時間T內(nèi),若Ferry節(jié)點Fi對區(qū)域Rj的第1階段、第2階段、第3階段的貢獻度分別為FSC(Fi,Rj),SSC(Fi,Rj),TSC(Fi,Rj),則稱RC(Fi,Rj)=αFSC(Fi,Rj)+βSSC(Fi,Rj) +γTSC(Fi,Rj)為Fi對區(qū)域Rj的區(qū)域貢獻度,記為RC(Fi,Rj),其中,α+β+γ=1,0<α,β,γ<1.

本文采用層次分析法[26-28](analytic hierarchy process, AHP),使用層次分析法軟件yaahp(yet another AHP)得到α=0.681 3,β=0.068 8,γ=0.249 9.

區(qū)域貢獻度RC反映Ferry節(jié)點對區(qū)域貢獻程度的同時,也反映了區(qū)域?qū)erry節(jié)點的依賴程度,即Ferry節(jié)點對區(qū)域的RC越大,區(qū)域?qū)erry節(jié)點的依賴程度越高,移除此節(jié)點后,區(qū)域從網(wǎng)絡(luò)中分裂出去的可能性越大,則該節(jié)點為關(guān)鍵節(jié)點的可能性就越大.若Ferry節(jié)點Fi對某區(qū)域Rj的貢獻值為1,則表明Rj完全依賴于Fi,即移除Fi后,Rj從整網(wǎng)中分離.由此,可以得到推論2.

推論2. 區(qū)域貢獻度為1的Ferry節(jié)點是MOSNs的割點.

由推論1、推論2得到推論3.

推論3. 區(qū)域貢獻度為1的Ferry節(jié)點是MOSNs的關(guān)鍵節(jié)點.

3 預(yù)測MOSNs的關(guān)鍵節(jié)點

MOSNs關(guān)鍵節(jié)點的預(yù)測步驟如下:

1) 根據(jù)推論2判定網(wǎng)絡(luò)中是否存在割點.計算每個Ferry節(jié)點對各區(qū)域的貢獻度,判斷是否存在對某區(qū)域貢獻度為1的Ferry節(jié)點.若存在,則該割點為網(wǎng)絡(luò)的關(guān)鍵節(jié)點,預(yù)測結(jié)束,否則進入步驟2.

2) 采用MADM方法找出導致網(wǎng)絡(luò)分裂可能性最大的節(jié)點,即為關(guān)鍵節(jié)點.用區(qū)域貢獻度表征區(qū)域?qū)erry節(jié)點的依賴程度,故Ferry節(jié)點的區(qū)域貢獻度越大,其導致網(wǎng)絡(luò)分割的可能性越大,因此本文采用改進TOPSIS方法將MOSNs中每個Ferry節(jié)點看作一個待評價方案,將Ferry節(jié)點對每個區(qū)域節(jié)點的貢獻度看作方案的屬性,對Ferry節(jié)點的區(qū)域貢獻度進行評價.

3.1 預(yù)測算法描述

MOSNs網(wǎng)絡(luò)結(jié)構(gòu)動態(tài)變化,用一個時間長度ΔT時間計算的結(jié)果作為最后的預(yù)測結(jié)果是不準確的,將每一個ΔT預(yù)測的結(jié)果稱為疑似關(guān)鍵節(jié)點.選取N×ΔT作為預(yù)測時間長度,得到N個疑似關(guān)鍵節(jié)點,統(tǒng)計每個Ferry節(jié)點被判定為疑似關(guān)鍵節(jié)點的次數(shù).

設(shè)MOSNs中有n個Ferry節(jié)點(方案)和m個區(qū)域節(jié)點(屬性),對決策矩陣X=(xi j)n×m歸一化,得到規(guī)范化決策矩陣Y=(yi j)n×m且:

(1)

其中,xi j為第i個Ferry節(jié)點對第j個區(qū)域節(jié)點的區(qū)域貢獻度,i=1,2,…,n,j=1,2,…,m.

確定正理想方案Y+和負理想方案Y-,以及各Ferry節(jié)點方案與Y+,Y-的距離D+,D-:

(2)

(3)

(4)

(5)

其中,正理想方案為

(6)

負理想方案為

(7)

根據(jù)指標權(quán)重對歐氏距離計算公式進行改進:

(8)

(9)

計算各Ferry節(jié)點與正理想解和負理想解的灰色關(guān)聯(lián)度:

(10)

(11)

(12)

(13)

對灰色關(guān)聯(lián)度和距離進行無量綱轉(zhuǎn)化:

(14)

(15)

(16)

(17)

其中，i=1,2,…,n.

(18)

(19)

其中,i=1,2,…,n；α為偏好系數(shù),取經(jīng)驗值0.5.則各Ferry節(jié)點的相對貼近度為

(20)

由于網(wǎng)絡(luò)中可能存在多個割點,故預(yù)測的結(jié)果可能是多個關(guān)鍵節(jié)點.這就需要計算某個Ferry節(jié)點為關(guān)鍵節(jié)點的概率.

設(shè)MOSNs中有d個Ferry節(jié)點且每個Ferry節(jié)點都可能導致網(wǎng)絡(luò)產(chǎn)生分割,若Ferry節(jié)點Fi被判定為疑似關(guān)鍵節(jié)點q次,則Fi為關(guān)鍵節(jié)點的概率為

P(Fi)=

(21)

計算出P(Fi)的最大值,記為max(P(Fi)),此時對應(yīng)Ferry節(jié)點記為Fk,k∈{1,2,…,d},即為關(guān)鍵節(jié)點.

3.2 算法流程

算法1. 基于灰關(guān)聯(lián)度的改進TOPSIS算法.

輸入:多屬性決策矩陣X=(xi j)n×m；

輸出:節(jié)點Fi的出現(xiàn)概率P(Fi).

Step1. 基于時間長度ΔT,對數(shù)據(jù)進行采樣分析,構(gòu)建決策矩陣X=(xi j)n×m,并依據(jù)式(1)進行歸一化,得到規(guī)范化矩陣Y=(yi j)n×m;

Step2. 根據(jù)式(2)～(5)分別計算決策的正理想方案Y+和負理想方案Y-,以及各節(jié)點方案與Y+,Y-的距離D+,D-;

Step3. 依據(jù)式(10)～(11)計算正理想方案和負理想方案的灰關(guān)聯(lián)度G+,G-;

Step4. 基于式(14)～(17)分別對距離和灰關(guān)聯(lián)度進行無量綱轉(zhuǎn)化;

Step6. 重復Step1～Step5共N次,統(tǒng)計每個Ferry節(jié)點被判定為疑似關(guān)鍵節(jié)點的次數(shù);

Step7. 根據(jù)式(21)計算每個節(jié)點的出現(xiàn)概率P(Fi),并進行排序,從中選出最大概率值所對應(yīng)的Ferry節(jié)點即為關(guān)鍵節(jié)點.

4 實驗設(shè)計與分析

4.1 實驗場景與相關(guān)參數(shù)

采用芬蘭赫爾辛基科技大學開發(fā)的ONE(opportunistic networking environment)進行仿真實驗,主要參數(shù)如表1所示,4種典型場景下區(qū)域節(jié)點數(shù)和各區(qū)域內(nèi)感知節(jié)點數(shù)如表2所示.

Table 1 Parameters of Simulation Experiment

如圖5所示,場景1不存在割點.Ferry節(jié)點fb,fc,fd在區(qū)域節(jié)點ra,rb,rc間移動,不能與Sink節(jié)點直接通信,Ferry節(jié)點fa,fe,fg為區(qū)域節(jié)點ra與Sink提供通信機會.ra與Sink間的絕大部分通信機會由fa提供,ra與Sink間極少部分的通信機會由fe,fg提供.因此,fa為場景1的關(guān)鍵節(jié)點.

Table 2 The Number of Region Nodes in Four Scenarios

Fig. 5 Scenario 1圖5 場景1

如圖6所示,場景2的關(guān)鍵節(jié)點為fd.如果移動節(jié)點fd丟失或失效,區(qū)域節(jié)點rc,rd,re無法將消息傳遞到Sink節(jié)點,網(wǎng)絡(luò)產(chǎn)生分割,故fd既是網(wǎng)絡(luò)的割點,也是網(wǎng)絡(luò)的關(guān)鍵節(jié)點.

Fig. 6 Scenario 2圖6 場景2

Fig. 7 Scenario 3圖7 場景3

Fig. 8 Scenario 4圖8 場景4

如圖7所示,場景3不存在割點.區(qū)域節(jié)點ra,rb與Sink節(jié)點間絕大部分的通信機會由移動節(jié)點fa提供,極少的通信機會由移動節(jié)點fe,fg提供.可見,fa為場景3的關(guān)鍵節(jié)點.

如圖8所示,場景4的關(guān)鍵節(jié)點為fd,fe.如果移動節(jié)點fd丟失或失效會導致區(qū)域節(jié)點rd,re從網(wǎng)絡(luò)分裂,移動節(jié)點fe失效會導致區(qū)域節(jié)點re從網(wǎng)絡(luò)分離.深入分析場景4,發(fā)現(xiàn)移動節(jié)點fc也是該網(wǎng)絡(luò)的1個割點,移動節(jié)點fa,fb,fc使區(qū)域節(jié)點ra,rb與Sink節(jié)點形成兩兩相互連通的穩(wěn)定狀態(tài),移動節(jié)點fc又連通著區(qū)域節(jié)點ra,rb,rc,若移動節(jié)點fc丟失或失效,則區(qū)域節(jié)點rc,rd,re均無法與Sink節(jié)點連通.所以,場景4的關(guān)鍵節(jié)點為移動節(jié)點fc,fd,fe.

4.2 實驗結(jié)果與分析

對上述4種場景進行了大量模擬實驗,采用TOPSIS算法和改進TOPSIS算法對實驗數(shù)據(jù)進行關(guān)鍵節(jié)點預(yù)測,預(yù)測結(jié)果如圖9～12所示:

Fig. 9 Predicted results of scenario 1圖9 場景1的預(yù)測結(jié)果

Fig. 11 Predicted results of scenario 3圖11 場景3的預(yù)測結(jié)果

Fig. 12 Predicted results of scenario 4圖12 場景4的預(yù)測結(jié)果

如圖9所示,場景1中移動節(jié)點fa被預(yù)測為關(guān)鍵節(jié)點的次數(shù)最多,與前述分析結(jié)果一致,說明采用本文預(yù)測算法的合理性;如圖10所示,場景2中被預(yù)測為關(guān)鍵節(jié)點次數(shù)最多的是移動節(jié)點fd;如圖11所示,場景3中被預(yù)測為關(guān)鍵節(jié)點次數(shù)最多的是移動節(jié)點fa,均與前述分析一致;如圖12所示的場景4中,移動節(jié)點fc,fd,fe多次被預(yù)測為關(guān)鍵節(jié)點,且三者的次數(shù)之和遠遠大于總實驗次數(shù)200,這是因為場景4中存在3個割點,因此每次預(yù)測的關(guān)鍵節(jié)點可能不唯一,Ferry節(jié)點fc,fd,fe均為該場景下的關(guān)鍵節(jié)點.

由圖9～12可得采用TOPSIS算法與改進TOPSIS算法預(yù)測關(guān)鍵節(jié)點的精度對比情況,如圖13所示.場景2與場景4存在割點,2種算法的預(yù)測精度接近;場景1與場景3不存在割點,采用TOPSIS算法的預(yù)測精度在60%～70%范圍內(nèi),而采用改進TOPSIS算法的預(yù)測精度達到80%～90%.可見,當MOSNs存在割點時,2種預(yù)測方法均較為準確;當MOSNs不存在割點時,采用改進TOPSIS算法的預(yù)測精度更高.

Fig. 13 The accuracy comparison chart of two measures圖13 2種方法的預(yù)測精度對比圖

4.3 實驗床實驗

搭建實驗床如圖14所示,在尋跡小車上捆綁美國Crossbow公司的TelosB節(jié)點,模擬MOSNs中移動節(jié)點尋跡移動,利用黑線規(guī)劃4條小車的移動軌跡.TelosB節(jié)點遵循IEEE802.15.4協(xié)議,通信范圍約100 m,在實驗中,將節(jié)點功率調(diào)至最低,并去掉天線,使節(jié)點的通信范圍為10～20 cm,以滿足圖1場景.

Fig. 14 The test bed圖14 實驗床

設(shè)置了3個區(qū)域節(jié)點,每個區(qū)域節(jié)點內(nèi)放置若干個感知節(jié)點,區(qū)域節(jié)點ra,rb與Sink節(jié)點間設(shè)置了2輛小車,為了模擬小車fa為區(qū)域ra,rb提供絕大部分通信機會,小車fb為區(qū)域ra,rb提供較少的通信機會,設(shè)置軌跡半徑較小的小車fa速度較快,軌跡半徑較大的小車fb速度較慢,那么該場景下,小車fa是關(guān)鍵節(jié)點.

利用TOPSIS算法與改進TOPSIS算法分別對實驗數(shù)據(jù)進行分析,100次實驗的預(yù)測結(jié)果如圖15所示.100次預(yù)測中,采用改進TOPSIS算法預(yù)測小車fa為關(guān)鍵節(jié)點的次數(shù)為73,預(yù)測精度為73%,采用 TOPSIS算法的預(yù)測精度為55%,顯然改進TOPSIS算法具有更高的預(yù)測精度.

Fig. 15 The predicted results of real scenario圖15 真實場景預(yù)測結(jié)果

5 結(jié)束語

本文分析了OSNs消息傳輸?shù)奶攸c,針對典型OSNs——多區(qū)域機會傳感器網(wǎng)絡(luò)MOSNs模型,定義了割點和關(guān)鍵節(jié)點,將MOSNs關(guān)鍵節(jié)點預(yù)測問題轉(zhuǎn)化為評估Ferry節(jié)點區(qū)域貢獻度的問題,采用改進TOPSIS算法預(yù)測關(guān)鍵節(jié)點.仿真實驗和實驗床實驗均說明本文的定義是合理的,通過評估Ferry節(jié)點區(qū)域貢獻度預(yù)測MOSNs關(guān)鍵節(jié)點是可行的,采用改進TOPSIS算法具有更高的預(yù)測精度.

[1]Xiong Yongping, Sun Limin, Niu Jianwei, et al. Opportunistic networks[J]. Journal of Software, 2009, 20(1): 124-137 (in Chinese)(熊永平, 孫利民, 牛建偉, 等. 機會網(wǎng)絡(luò)[J]. 軟件學報, 2009, 20(1): 124-137)

[2]Hull B, Bychkovsky V, Zhang Yang, et al. CarTel: A distributed mobile sensor computing system[C]Proc of ACM SenSys’06. New York: ACM, 2006: 125-138

[3]Wang Yu, Wu Hongyi. DFT-MSN: The delayfault-tolerant mobile sensor network for pervasive information gathering[C]Proc of INFOCOM’06. Piscataway, NJ: IEEE, 2006: 1021-1034

[4]Juang P, Oki H, Wang Yong, et al. Energy-efficient computing for wildlife tracking: Design tradeoffs and early experiences with ZebraNet[J]. ACM SIGPLAN Notices, 2002, 37(10): 96-107

[5]Liu Xiaomei, Xiao Li, Kreling A, et al. Optimizing overlay topology by reducing cut vertices[C]Proc of ACM NOSSDAV’06. New York: ACM, 2006

[6]Li Jiandong, Tian Ye, Sheng Min, et al. Partition detection for large scale ad hoc networks[J]. Journal on Communications, 2008, 29(9): 54-61 (in Chinese)(李建東, 田野, 盛敏, 等. 大規(guī)模ad hoc網(wǎng)絡(luò)拓撲分割探測研究[J]. 通信學報, 2008, 29(9): 54-61)

[7]Hu Jun, Wang Bing, Lee Deyi. Evaluating node importance with multi-criteria[C]Proc of IEEEACM GreenCom-CPSCom. Piscataway, NJ: IEEE, 2010: 792-797

[8]Su Xiaoping, Song Yurong. Leveraging neighborhood “structural holes” to identifying key spreaders in social networks[J]. Acta Physica Sinica, 2015, 64(2): 1-11 (in Chinese)(蘇曉萍, 宋玉蓉. 利用鄰域“結(jié)構(gòu)洞”尋找社會網(wǎng)絡(luò)中最具影響力節(jié)點[J]. 物理學報, 2015, 64(2): 1-11)

[9]Zhou Xuan, Zhang Fengming, Li Kewu, et al. Finding vital node by node importance evaluation matrix in complex networks[J]. Acta Physica Sinica, 2012, 61(5): 1-7 (in Chinese)(周漩, 張鳳鳴, 李克武, 等. 利用重要度評價矩陣確定復雜網(wǎng)絡(luò)關(guān)鍵節(jié)點[J]. 物理學報, 2012, 61(5): 1-7)

[10]Xiong Shuguang, Li Jianzhong. An efficient algorithm for cut vertex detection in wireless sensor networks[C]Proc of IEEE ICDCS’10. Piscataway, NJ: IEEE, 2010: 368-377

[11]Nguyen D T, Shen Y, Thai M T. Detecting critical nodes in interdependent power networks for vulnerability assessment[J]. IEEE Trans on Smart Grid, 2013, 4(1): 151-159

[12]Shen Yilin, Nguyen N P, Xuan Ying, et al. On the discovery of critical links and nodes for assessing network vulnerability[J]. IEEEACM Trans on Networking, 2013, 21(3): 963-973

[13]Nacher J C, Akutsu T. Analysis on critical nodes in controlling complex networks using dominating sets[C]Proc of IEEE SITIS’13. Piscataway, NJ: IEEE, 2013: 649-654

[14]Du Guiping, He Lidan, Fang Junxiang. The component importance evaluation of power converter based on complex network[C]Proc of IEEE PEAC’14. Piscataway, NJ: IEEE, 2014: 988-992

[15]Lin Jian, Dai Fei, Li Baichao, et al. Electromagnetic compatibility supernetwork modeling and node importance evaluation[C]Proc of the 5th Int Conf on Intelligent Human-Machine Systems and Cybernetics. Piscataway, NJ: IEEE, 2013: 306-310

[16]Ma Shouming, Wang Ruchuan, Ye Ning. Secure data aggregation algorithm based on reputation set pair analysis in wireless sensor networks[J]. Journal of Computer Research and Development, 2011, 48(9): 1652-1658 (in Chinese)(馬守明, 王汝傳, 葉寧. 基于信譽度集對分析的WSN安全數(shù)據(jù)融合[J]. 計算機研究與發(fā)展, 2011, 48(9): 1652-1658)

[17]Zeng Jia, Mu Chundi, Li Shu. Multiple attribute decision making routing in wireless sensor networks[J]. Journal of System Simulation, 2009,21(3): 878-881 (in Chinese)(曾加, 慕春棣, 李戍. 基于多屬性決策的無線傳感器網(wǎng)絡(luò)路由算法[J]. 系統(tǒng)仿真學報, 2009, 21(3): 878-881)

[18]Corley H W, Sha D Y. Most vital links and nodes in weighted networks[J]. Operations Research Letters, 1982, 1(4): 157-160

[19]Chen Yong, Hu Aiqun, Hu Xiao. Evaluation method for node importance in communication networks[J]. Journal on Communications, 2004, 25(8): 129-134 (in Chinese)(陳勇, 胡愛群, 胡嘯. 通信網(wǎng)中節(jié)點重要性的評價方法[J]. 通信學報, 2004, 25(8): 129-134)

[20]Zhang Xiping, Li Yongshu, Liu Gang, et al. Evaluation method of importance for nodes in complex networks based on importance contribution[J]. Complex Systems and Complexity Science, 2014, 11(3): 26-32 (in Chinese)(張喜平, 李永樹, 劉剛, 等. 節(jié)點重要度貢獻的復雜網(wǎng)絡(luò)節(jié)點重要度評估方法[J]. 復雜系統(tǒng)與復雜性科學, 2014, 11(3): 26-32)

[21]Sabidussi G. The centrality index of a graph[J]. Psychometrika, 1966, 31(4): 581-603

[22]Freeman L C. A set of measures of centrality based on betweenness[J]. Sociometry, 1977, 40(1): 35-41

[23]Liu Bin, Wang Wenji, Li Yaqian, et al. Crucial node decision algorithm based on energy in WSNs[J]. Journal of Electronics and Information Technology, 2014, 36(7): 1728-1734 (in Chinese)(劉彬, 王文吉, 李雅倩, 等. 基于能量因素的無線傳感器網(wǎng)絡(luò)關(guān)鍵節(jié)點判定算法[J]. 電子與信息學報, 2014, 36(7): 1728-1734)

[24]Shu Jian, Geng Xiaotian, Zeng Linxin, et al. Connectivity influencing factors and modeling for opportunistic sensor networks[J]. Journal of Beijing University of Posts and Telecommunications, 2015, 38(6): 109-114 (in Chinese)(舒堅, 耿瀟湉, 曾林新, 等. 機會傳感網(wǎng)絡(luò)連通度影響因素與連通度模型[J]. 北京郵電大學學報, 2015, 38(6): 109-114)

[25]Shu Jian, Guo Kai, Liu Qun, et al. Research of connectivity parameter in opportunistic sensor networks[J]. Chinese Journal of Computers, 2016, 39(5): 1067-1080 (in Chinese)(舒堅, 郭凱, 劉群, 等. 機會傳感網(wǎng)絡(luò)連通性參數(shù)研究[J]. 計算機學報, 2016, 39(5): 1067-1080)

[26]Yu Hui, Liu Zun, Li Yongjun. Key nodes in complex networks identified by multi-attribute decision-making method[J]. Acta Physica Sinica, 2013, 62(2): 46-54 (in Chinese)(于會, 劉尊, 李勇軍. 基于多屬性決策的復雜網(wǎng)絡(luò)節(jié)點重要性綜合評價方法[J]. 物理學報, 2013, 62(2): 46-54)

[27]Sha Letian, Fu Jianming, Chen Jing, et al. A sensitivity measurement for sensitive information processing[J]. Journal of Computer Research and Development, 2014, 51(5): 1050-1060 (in Chinese)(沙樂天, 傅建明, 陳晶, 等. 一種面向敏感信息處理的敏感度度量方法[J]. 計算機研究與發(fā)展, 2014, 51(5): 1050-1060)

[28]Wang Wenbin, Sun Qibo, Yang Fangchun. Environment-aware quantitative assessment model for service availability in MANET[J]. Journal of Computer Research and Development, 2012, 49(3): 558-564 (in Chinese)(王文彬, 孫其博, 楊放春. MANET下環(huán)境感知的服務(wù)可用性量化評估模型[J]. 計算機研究與發(fā)展, 2012, 49(3): 558-564)

Zhang Jiang, born in 1992. MSc candidate in Nanchang Hangkong University. His main research interests include opportunistic sensor networks (zhangjiangky@163.com).

Shu Jian, born in 1964. Received his MSc degree in computer networks from North-western Polytechnical University. Professor in Nanchang Hangkong University. Senior member of CCF. His main research interests include wireless sensor networks, embedded system and software engineering.

Guo Kai, born in 1990. MSc candidate in Nanchang Hangkong University. Student member of CCF. His main research interests include opportunistic sensor networks (1056692868@qq.com).

Meng Lingchong, born in 1991. MSc candidate in Nanchang Hangkong University. His main research interests include opportunistic sensor networks (282733193@qq.com).

Multiple Attribute Decision Making-Based Prediction Approach of Critical Node for Opportunistic Sensor Networks

Liu Linlan1, Zhang Jiang1, Shu Jian2, Guo Kai1, and Meng Lingchong1

1(SchoolofInformationEngineering,NanchangHangkongUniversity,Nanchang330063)2(SchoolofSoftware,NanchangHangkongUniversity,Nanchang330063)

If critical nodes have been predicted, the network can be optimized according to the information of the critical nodes. Furthermore, maintenance time and cost of network can be dramatically reduced by checking the critical nodes at the first time when the network is crashed. Unfortunately, the existing methods of predicting critical nodes in static wireless sensor networks are not suitable for opportunistic sensor networks (OSNs). According to the characteristics of dynamic changes of network topology and high latency, for multi-region OSNs (MOSNs) with hierarchical structure, this paper analyzes the message transferring process. The stage contribution is defined to reflect the contribution of Ferry nodes in the process of message transmission, and the region contribution is defined to reflect the contribution of Ferry nodes to regions. In terms of the comprehensive contribution of Ferry nodes, the prediction method of critical nodes is proposed, which is based on multiple attribute decision making—technique for order preference by similarity to ideal solution (TOPSIS). The experimental results show that the prediction method with improved TOPSIS algorithms achieves better accuracy. Furthermore, test bed is established so as to validate the proposed method. The test bed experimental results show that the prediction method with improved TOPSIS algorithms achieves better accuracy as well.

opportunistic sensor networks (OSNs); critical node; region contribution; stage contribution; multiple attribute decision making

her BSc degree in computer application from the National University of Defence Technology. Professor in Nanchang Hangkong University. Member of CCF. Her main research interests include software engineering and distributed system.

2016-08-22；

2017-02-06

國家自然科學基金項目(61363015,61262020,61501217,61501218);江西省自然科學基金重點項目(20171ACB20018,20171BAB202009,20071BBH80022);江西省教育廳科學技術(shù)重點項目(GJJ150702); 江西省研究生創(chuàng)新專項資金項目(YC2015-S324,YC2016-042) This work was supported by the National Natural Science Foundation of China (61363015, 61262020, 61501217, 61501218), the Natural Science Foundation of Jiangxi Province (20171ACB20018, 20171BAB202009, 20071BBH80022), the Key Research Foundation of Education Bureau of Jiangxi Province(GJJ150702), and the Innovation Foundation for Postgraduate Student of Jiangxi Province (YC2015-S324, YC2016-042).

舒堅(shujian@nchu.edu.cn)

TP393