基于多屬性決策的機會傳感器網絡關鍵節點預測

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

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

基于多屬性決策的機會傳感器網絡關鍵節點預測

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

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

(liulinlan@nchu.edu.cn)

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

機會傳感器網絡;關鍵節點;區域貢獻度;階段貢獻度;多屬性決策

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

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

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

1 相關研究

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

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

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

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

本文參考文獻[6],考慮OSNs的傳輸特點,定義OSNs的關鍵節點及割點,定義區域貢獻度反映區域對Ferry節點的依賴程度,采用多屬性決策(multiple attribute decision making, MADM)方法預測OSNs的關鍵節點.

2 場景模型及定義

根據OSNs分層結構的特點,分析OSNs中關鍵節點的特點,定義OSNs關鍵節點、區域貢獻度.

2.1 OSNs場景模型

本文研究場景如圖1[24]所示,區域內感知節點發送消息至移動節點,移動節點通過1次或多次轉發將消息發送至Sink節點.

Fig. 1 MOSNs scenario圖1 MOSNs場景

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

Fig. 2 MOSNs model圖2 MOSNs模型

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

Fig. 3 MOSNs hierarchical structure圖3 MOSNs的分層結構

2.2 MOSNs的關鍵節點

關鍵節點的概念來自圖論,目前仍沒有統一的定義.本文針對MOSNs的特點,以網絡分裂概率為衡量標準,定義關鍵節點.

定義1. 關鍵節點.設G表示MOSNs,若G中某節點F移除后網絡產生分裂的可能性最大,則稱F為G的關鍵節點.

定義2. 割點.設G表示MOSNs,若移除某節點C后網絡G產生分裂,則稱C為網絡G的割點.

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

推論1. MOSNs的割點一定是關鍵節點.

證明. 由定義2可知,移除MOSNs的割點后,網絡一定產生分裂.即移除MOSNs的割點后,網絡產生分裂的概率為100%,故MOSNs的割點一定是關鍵節點.

證畢.

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

為便于研究,本文進行如下假設:

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

2) 設Ferry節點的內存足夠存儲其經過區域時收集的全部消息;

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

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

2.3 階段貢獻度

Ferry節點是MOSNs的消息傳輸媒介,對整個網絡至關重要,部分Ferry節點可能是關鍵節點.通過分析MOSNs的路由機制和分層結構,不難發現,感知消息從產生到最終投遞到Sink的過程,可分為3個階段:消息投遞階段、消息轉發階段和消息到達階段,如圖4所示:

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

1) 消息投遞階段.Ferry節點將感知消息帶離區域.

2) 消息轉發階段.消息在Ferry節點間轉發.

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

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

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

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

顯然,FSC反映了Ferry節點在消息投遞階段對消息傳輸的貢獻程度;SSC反映了Ferry節點在消息轉發階段對消息傳輸的貢獻程度;TSC反映了Ferry節點在消息到達階段對消息傳輸的貢獻程度.

2.4 區域貢獻度

定義6. 區域貢獻度(region contribution, RC). 時間T內,若Ferry節點Fi對區域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對區域Rj的區域貢獻度,記為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.

區域貢獻度RC反映Ferry節點對區域貢獻程度的同時,也反映了區域對Ferry節點的依賴程度,即Ferry節點對區域的RC越大,區域對Ferry節點的依賴程度越高,移除此節點后,區域從網絡中分裂出去的可能性越大,則該節點為關鍵節點的可能性就越大.若Ferry節點Fi對某區域Rj的貢獻值為1,則表明Rj完全依賴于Fi,即移除Fi后,Rj從整網中分離.由此,可以得到推論2.

推論2. 區域貢獻度為1的Ferry節點是MOSNs的割點.

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

推論3. 區域貢獻度為1的Ferry節點是MOSNs的關鍵節點.

3 預測MOSNs的關鍵節點

MOSNs關鍵節點的預測步驟如下:

1) 根據推論2判定網絡中是否存在割點.計算每個Ferry節點對各區域的貢獻度,判斷是否存在對某區域貢獻度為1的Ferry節點.若存在,則該割點為網絡的關鍵節點,預測結束,否則進入步驟2.

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

3.1 預測算法描述

MOSNs網絡結構動態變化,用一個時間長度ΔT時間計算的結果作為最后的預測結果是不準確的,將每一個ΔT預測的結果稱為疑似關鍵節點.選取N×ΔT作為預測時間長度,得到N個疑似關鍵節點,統計每個Ferry節點被判定為疑似關鍵節點的次數.

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

(1)

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

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

(2)

(3)

(4)

(5)

其中,正理想方案為

(6)

負理想方案為

(7)

根據指標權重對歐氏距離計算公式進行改進:

(8)

(9)

計算各Ferry節點與正理想解和負理想解的灰色關聯度:

(10)

(11)

(12)

(13)

對灰色關聯度和距離進行無量綱轉化:

(14)

(15)

(16)

(17)

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

(18)

(19)

其中,i=1,2,…,n；α為偏好系數,取經驗值0.5.則各Ferry節點的相對貼近度為

(20)

由于網絡中可能存在多個割點,故預測的結果可能是多個關鍵節點.這就需要計算某個Ferry節點為關鍵節點的概率.

設MOSNs中有d個Ferry節點且每個Ferry節點都可能導致網絡產生分割,若Ferry節點Fi被判定為疑似關鍵節點q次,則Fi為關鍵節點的概率為

P(Fi)=

(21)

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

3.2 算法流程

算法1. 基于灰關聯度的改進TOPSIS算法.

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

輸出:節點Fi的出現概率P(Fi).

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

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

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

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

Step6. 重復Step1～Step5共N次,統計每個Ferry節點被判定為疑似關鍵節點的次數;

Step7. 根據式(21)計算每個節點的出現概率P(Fi),并進行排序,從中選出最大概率值所對應的Ferry節點即為關鍵節點.

4 實驗設計與分析

4.1 實驗場景與相關參數

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

Table 1 Parameters of Simulation Experiment

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

Table 2 The Number of Region Nodes in Four Scenarios

Fig. 5 Scenario 1圖5 場景1

如圖6所示,場景2的關鍵節點為fd.如果移動節點fd丟失或失效,區域節點rc,rd,re無法將消息傳遞到Sink節點,網絡產生分割,故fd既是網絡的割點,也是網絡的關鍵節點.

Fig. 6 Scenario 2圖6 場景2

Fig. 7 Scenario 3圖7 場景3

Fig. 8 Scenario 4圖8 場景4

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

如圖8所示,場景4的關鍵節點為fd,fe.如果移動節點fd丟失或失效會導致區域節點rd,re從網絡分裂,移動節點fe失效會導致區域節點re從網絡分離.深入分析場景4,發現移動節點fc也是該網絡的1個割點,移動節點fa,fb,fc使區域節點ra,rb與Sink節點形成兩兩相互連通的穩定狀態,移動節點fc又連通著區域節點ra,rb,rc,若移動節點fc丟失或失效,則區域節點rc,rd,re均無法與Sink節點連通.所以,場景4的關鍵節點為移動節點fc,fd,fe.

4.2 實驗結果與分析

對上述4種場景進行了大量模擬實驗,采用TOPSIS算法和改進TOPSIS算法對實驗數據進行關鍵節點預測,預測結果如圖9～12所示:

Fig. 9 Predicted results of scenario 1圖9 場景1的預測結果

Fig. 11 Predicted results of scenario 3圖11 場景3的預測結果

Fig. 12 Predicted results of scenario 4圖12 場景4的預測結果

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

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

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

4.3 實驗床實驗

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

Fig. 14 The test bed圖14 實驗床

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

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

Fig. 15 The predicted results of real scenario圖15 真實場景預測結果

5 結束語

本文分析了OSNs消息傳輸的特點,針對典型OSNs——多區域機會傳感器網絡MOSNs模型,定義了割點和關鍵節點,將MOSNs關鍵節點預測問題轉化為評估Ferry節點區域貢獻度的問題,采用改進TOPSIS算法預測關鍵節點.仿真實驗和實驗床實驗均說明本文的定義是合理的,通過評估Ferry節點區域貢獻度預測MOSNs關鍵節點是可行的,采用改進TOPSIS算法具有更高的預測精度.

[1]Xiong Yongping, Sun Limin, Niu Jianwei, et al. Opportunistic networks[J]. Journal of Software, 2009, 20(1): 124-137 (in Chinese)(熊永平, 孫利民, 牛建偉, 等. 機會網絡[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)(李建東, 田野, 盛敏, 等. 大規模ad hoc網絡拓撲分割探測研究[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)(蘇曉萍, 宋玉蓉. 利用鄰域“結構洞”尋找社會網絡中最具影響力節點[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)(周漩, 張鳳鳴, 李克武, 等. 利用重要度評價矩陣確定復雜網絡關鍵節點[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安全數據融合[J]. 計算機研究與發展, 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)(曾加, 慕春棣, 李戍. 基于多屬性決策的無線傳感器網絡路由算法[J]. 系統仿真學報, 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)(陳勇, 胡愛群, 胡嘯. 通信網中節點重要性的評價方法[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)(張喜平, 李永樹, 劉剛, 等. 節點重要度貢獻的復雜網絡節點重要度評估方法[J]. 復雜系統與復雜性科學, 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)(劉彬, 王文吉, 李雅倩, 等. 基于能量因素的無線傳感器網絡關鍵節點判定算法[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)(舒堅, 耿瀟湉, 曾林新, 等. 機會傳感網絡連通度影響因素與連通度模型[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)(舒堅, 郭凱, 劉群, 等. 機會傳感網絡連通性參數研究[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)(于會, 劉尊, 李勇軍. 基于多屬性決策的復雜網絡節點重要性綜合評價方法[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]. 計算機研究與發展, 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下環境感知的服務可用性量化評估模型[J]. 計算機研究與發展, 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);江西省教育廳科學技術重點項目(GJJ150702); 江西省研究生創新專項資金項目(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