劉琳嵐 張 江 舒 堅(jiān) 郭 凱 孟令沖

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

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

劉琳嵐1張 江1舒 堅(jiān)2郭 凱1孟令沖1

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

(liulinlan@nchu.edu.cn)

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

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

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

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

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

1 相關(guān)研究

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

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

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

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

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

2 場(chǎng)景模型及定義

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

2.1 OSNs場(chǎng)景模型

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

Fig. 1 MOSNs scenario圖1 MOSNs場(chǎng)景

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

Fig. 2 MOSNs model圖2 MOSNs模型

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

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

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

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

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

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

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

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

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

證畢.

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

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

1) 將每個(gè)區(qū)域抽象成一個(gè)“超級(jí)節(jié)點(diǎn)”,稱區(qū)域節(jié)點(diǎn);

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

3) MOSNs中區(qū)域節(jié)點(diǎn)、Ferry節(jié)點(diǎn)及Sink節(jié)點(diǎn)均有唯一的標(biāo)識(shí);

4) MOSNs已具備時(shí)鐘同步機(jī)制.

2.3 階段貢獻(xiàn)度

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

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

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

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

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

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

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

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

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

2.4 區(qū)域貢獻(xiàn)度

定義6. 區(qū)域貢獻(xiàn)度(region contribution, RC). 時(shí)間T內(nèi),若Ferry節(jié)點(diǎn)Fi對(duì)區(qū)域Rj的第1階段、第2階段、第3階段的貢獻(xiàn)度分別為FSC(Fi,Rj),SSC(Fi,Rj),TSC(Fi,Rj),則稱RC(Fi,Rj)=αFSC(Fi,Rj)+βSSC(Fi,Rj) +γTSC(Fi,Rj)為Fi對(duì)區(qū)域Rj的區(qū)域貢獻(xiàn)度,記為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ū)域貢獻(xiàn)度RC反映Ferry節(jié)點(diǎn)對(duì)區(qū)域貢獻(xiàn)程度的同時(shí),也反映了區(qū)域?qū)erry節(jié)點(diǎn)的依賴程度,即Ferry節(jié)點(diǎn)對(duì)區(qū)域的RC越大,區(qū)域?qū)erry節(jié)點(diǎn)的依賴程度越高,移除此節(jié)點(diǎn)后,區(qū)域從網(wǎng)絡(luò)中分裂出去的可能性越大,則該節(jié)點(diǎn)為關(guān)鍵節(jié)點(diǎn)的可能性就越大.若Ferry節(jié)點(diǎn)Fi對(duì)某區(qū)域Rj的貢獻(xiàn)值為1,則表明Rj完全依賴于Fi,即移除Fi后,Rj從整網(wǎng)中分離.由此,可以得到推論2.

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

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

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

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

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

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

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

3.1 預(yù)測(cè)算法描述

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

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

(1)

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

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

(2)

(3)

(4)

(5)

其中,正理想方案為

(6)

負(fù)理想方案為

(7)

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

(8)

(9)

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

(10)

(11)

(12)

(13)

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

(14)

(15)

(16)

(17)

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

(18)

(19)

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

(20)

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

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

P(Fi)=

(21)

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

3.2 算法流程

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

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

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

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

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

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

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

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

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

4 實(shí)驗(yàn)設(shè)計(jì)與分析

4.1 實(shí)驗(yàn)場(chǎng)景與相關(guān)參數(shù)

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

Table 1 Parameters of Simulation Experiment

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

Table 2 The Number of Region Nodes in Four Scenarios

Fig. 5 Scenario 1圖5 場(chǎng)景1

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

Fig. 6 Scenario 2圖6 場(chǎng)景2

Fig. 7 Scenario 3圖7 場(chǎng)景3

Fig. 8 Scenario 4圖8 場(chǎng)景4

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

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

4.2 實(shí)驗(yàn)結(jié)果與分析

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

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

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

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

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

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

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

4.3 實(shí)驗(yàn)床實(shí)驗(yàn)

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

Fig. 14 The test bed圖14 實(shí)驗(yàn)床

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

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

Fig. 15 The predicted results of real scenario圖15 真實(shí)場(chǎng)景預(yù)測(cè)結(jié)果

5 結(jié)束語(yǔ)

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

[1]Xiong Yongping, Sun Limin, Niu Jianwei, et al. Opportunistic networks[J]. Journal of Software, 2009, 20(1): 124-137 (in Chinese)(熊永平, 孫利民, 牛建偉, 等. 機(jī)會(huì)網(wǎng)絡(luò)[J]. 軟件學(xué)報(bào), 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ò)拓?fù)浞指钐綔y(cè)研究[J]. 通信學(xué)報(bào), 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)洞”尋找社會(huì)網(wǎng)絡(luò)中最具影響力節(jié)點(diǎn)[J]. 物理學(xué)報(bào), 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)(周漩, 張鳳鳴, 李克武, 等. 利用重要度評(píng)價(jià)矩陣確定復(fù)雜網(wǎng)絡(luò)關(guān)鍵節(jié)點(diǎn)[J]. 物理學(xué)報(bào), 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)(馬守明, 王汝傳, 葉寧. 基于信譽(yù)度集對(duì)分析的WSN安全數(shù)據(jù)融合[J]. 計(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ú)線傳感器網(wǎng)絡(luò)路由算法[J]. 系統(tǒng)仿真學(xué)報(bào), 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é)點(diǎn)重要性的評(píng)價(jià)方法[J]. 通信學(xué)報(bào), 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é)點(diǎn)重要度貢獻(xiàn)的復(fù)雜網(wǎng)絡(luò)節(jié)點(diǎn)重要度評(píng)估方法[J]. 復(fù)雜系統(tǒng)與復(fù)雜性科學(xué), 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ú)線傳感器網(wǎng)絡(luò)關(guān)鍵節(jié)點(diǎn)判定算法[J]. 電子與信息學(xué)報(bào), 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)(舒堅(jiān), 耿瀟湉, 曾林新, 等. 機(jī)會(huì)傳感網(wǎng)絡(luò)連通度影響因素與連通度模型[J]. 北京郵電大學(xué)學(xué)報(bào), 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)(舒堅(jiān), 郭凱, 劉群, 等. 機(jī)會(huì)傳感網(wǎng)絡(luò)連通性參數(shù)研究[J]. 計(jì)算機(jī)學(xué)報(bào), 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)(于會(huì), 劉尊, 李勇軍. 基于多屬性決策的復(fù)雜網(wǎng)絡(luò)節(jié)點(diǎn)重要性綜合評(píng)價(jià)方法[J]. 物理學(xué)報(bào), 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]. 計(jì)算機(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ù)可用性量化評(píng)估模型[J]. 計(jì)算機(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

國(guó)家自然科學(xué)基金項(xiàng)目(61363015,61262020,61501217,61501218);江西省自然科學(xué)基金重點(diǎn)項(xiàng)目(20171ACB20018,20171BAB202009,20071BBH80022);江西省教育廳科學(xué)技術(shù)重點(diǎn)項(xiàng)目(GJJ150702); 江西省研究生創(chuàng)新專項(xiàng)資金項(xià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).

舒堅(jiān)(shujian@nchu.edu.cn)

TP393