結(jié)合概率路由的機會網(wǎng)絡(luò)自私節(jié)點檢測算法

任 智，陳民華，康 健，李秀峰

1(重慶郵電大學 通信與信息工程學院，重慶 400065)

2(重慶郵電大學 移動通信技術(shù)重慶市重點實驗室，重慶 400065)

E-mail：2849819270@qq.com

1 引 言

機會網(wǎng)絡(luò)[1，2]是一種源節(jié)點與目的節(jié)點之間沒有完整的傳輸路徑，利用節(jié)點移動帶來的相遇機會來實現(xiàn)源節(jié)點與目的節(jié)點通信的移動自組織網(wǎng)絡(luò)，其數(shù)據(jù)傳輸模式為“存儲-攜帶-轉(zhuǎn)發(fā)”.概率路由機制[3]是機會網(wǎng)絡(luò)中一種消息只沿著與目的地址相遇概率更高的方向傳輸?shù)穆酚伤惴ǎ撍惴ㄍㄟ^計算節(jié)點之間的接觸概率來為消息選擇交付概率更大的中繼節(jié)點.由于機會網(wǎng)絡(luò)中節(jié)點自身的資源(節(jié)點能量、緩存空間等)有限，節(jié)點會為了節(jié)省自身資源而表現(xiàn)出拒絕向其它節(jié)點提供消息轉(zhuǎn)發(fā)服務(wù)的自私行為，這種自私行為會導(dǎo)致整個網(wǎng)絡(luò)的性能下降甚至無法正常工作[4,5].因此，如何設(shè)計高效的自私節(jié)點檢測機制來促進消息在非自私節(jié)點間順利傳輸是機會網(wǎng)絡(luò)中一項重要的研究課題.

2 相關(guān)工作

目前，國內(nèi)外有很多關(guān)于自私節(jié)點檢測算法的文獻.

Watchdog[6]算法的思想是：當前攜帶消息的節(jié)點將消息轉(zhuǎn)發(fā)給下一跳節(jié)點之后，通過對下一跳節(jié)點的行為進行監(jiān)聽.若下一跳節(jié)點在規(guī)定的時間內(nèi)對該數(shù)據(jù)消息進行了轉(zhuǎn)發(fā)，則表明當前節(jié)點的下一跳節(jié)點是非自私節(jié)點，其提供了轉(zhuǎn)發(fā)服務(wù)；若在規(guī)定的時間內(nèi)下一跳節(jié)點沒對該數(shù)據(jù)消息進行轉(zhuǎn)發(fā)，則表明當前節(jié)點的下一跳節(jié)點是自私節(jié)點.根據(jù)監(jiān)聽結(jié)果來判斷下一跳節(jié)點是否是自私節(jié)點存在一定的缺點，原因是下一跳節(jié)點有可能因為脫離監(jiān)聽范圍或鏈路不穩(wěn)定而造成當前節(jié)點對下一跳節(jié)點的誤判.

CORE[7]機制和CONFIDANT[8]機制是在Watchdog機制的基礎(chǔ)上給網(wǎng)絡(luò)中的節(jié)點設(shè)置一個量化的信譽值，同時每個節(jié)點維持一張信譽表來記錄網(wǎng)絡(luò)中其它節(jié)點的信譽值.網(wǎng)絡(luò)中每一個節(jié)點通過監(jiān)聽其鄰居節(jié)點是否轉(zhuǎn)發(fā)數(shù)據(jù)消息來動態(tài)地調(diào)整其鄰居節(jié)點的信譽值：若鄰居節(jié)點為自身轉(zhuǎn)發(fā)了數(shù)據(jù)消息，則在自身的信譽表上增加該鄰居節(jié)點的信譽值，否則降低該鄰居節(jié)點的信譽值.然后根據(jù)鄰居節(jié)點的信譽值是否超過預(yù)先設(shè)置的閾值來判斷鄰居節(jié)點的自私性.若該鄰居節(jié)點為自私節(jié)點，則對該節(jié)點進行懲罰.雖然通過設(shè)置信譽值的方式可以一定程度上避免Watchdog機制帶來的誤判，但是由于節(jié)點信譽機制計算與維護過程比較復(fù)雜且不可靠，容易導(dǎo)致信譽值不一致的問題.

IRONMAN檢測算法[9]是一種自主檢測算法，其核心思想是：通過節(jié)點相遇交互各自的歷史記錄信息來判斷中繼節(jié)點的自私性，若檢測出中繼節(jié)點為自私節(jié)點則降低該節(jié)點的信譽值.由于機會網(wǎng)絡(luò)中的節(jié)點是隨機移動的，因此節(jié)點之間的相遇就具有隨機性，不能滿足節(jié)點檢測的實時性，同時中繼節(jié)點有可能并未先于源節(jié)點遇到目的節(jié)點而產(chǎn)生誤判.

RADON[10]機制的核心思想是：每個節(jié)點存儲一張信譽表用來表征網(wǎng)絡(luò)中其它節(jié)點的信譽值，同時結(jié)合Watchdog的節(jié)點檢測機制來對節(jié)點的轉(zhuǎn)發(fā)行為進行檢測，并且根據(jù)檢測結(jié)果來更新節(jié)點的信譽值.當節(jié)點轉(zhuǎn)發(fā)數(shù)據(jù)消息時，會選擇信譽值最大的鄰居節(jié)點作為中繼節(jié)點，這種方式使消息朝著信譽值遞增的方向傳輸.但是由于該機制采用了Watchdog的監(jiān)聽機制，因此存在節(jié)點信譽值計算不準確的問題，同時對于低信譽值的節(jié)點不能對其進行激勵使其進行合作的問題.

基于2-ACK的自私節(jié)點檢測算法[11]是利用上一跳節(jié)點是否接收到當前節(jié)點的下一跳節(jié)點的ACK信息來判斷當前節(jié)點的自私性，但是基于2-ACK檢測算法中下一跳節(jié)點與上一跳節(jié)點之間可能存在相遇概率低的問題，導(dǎo)致檢測效率較低，易引起誤判.EACK機制[12]用于消息在轉(zhuǎn)發(fā)過程中，記錄參與轉(zhuǎn)發(fā)消息的節(jié)點ID及對應(yīng)跳數(shù)，參與消息轉(zhuǎn)發(fā)的當前節(jié)點的后L-2個節(jié)點都要向當前節(jié)點回復(fù)ACK消息，以此作為當前節(jié)點的下一跳節(jié)點轉(zhuǎn)發(fā)了消息的憑證，該算法改進了基于2-ACK檢測算法中下一跳節(jié)點與上一跳節(jié)點相遇概率低的不足，但是由于引入了過多的ACK回復(fù)消息，使得網(wǎng)絡(luò)開銷增大，同時容易引起網(wǎng)絡(luò)擁塞.

RSND檢測算法[13]采用錯幀解析等機制對相遇節(jié)點的自私性進行判斷，其可以很好地解決Watchdog機制中由于節(jié)點脫離通信范圍或鏈路不穩(wěn)定原因造成節(jié)點產(chǎn)生誤判的問題，但是其對難以確定類型的節(jié)點采用概率定性的方式來判定節(jié)點是否自私的方法容易引起誤判.

為解決上述中自私節(jié)點檢測算法開銷較大和節(jié)點自私行為判斷不夠準確的問題，本文提出了一種結(jié)合概率路由的機會網(wǎng)絡(luò)自私節(jié)點檢測算法.

3 假設(shè)與問題描述

3.1 假設(shè)

假設(shè)1.網(wǎng)絡(luò)節(jié)點分為自私節(jié)點和非自私節(jié)點，自私節(jié)點不參與網(wǎng)絡(luò)中消息的轉(zhuǎn)發(fā)，即表現(xiàn)出不請求其它節(jié)點的數(shù)據(jù)消息或者請求了數(shù)據(jù)消息之后也是直接刪除，同時它只發(fā)送本節(jié)點產(chǎn)生的消息.

假設(shè)2.網(wǎng)絡(luò)中節(jié)點配置相同，即每個節(jié)點的通信范圍以及數(shù)據(jù)處理能力相同.

假設(shè)3.網(wǎng)絡(luò)中節(jié)點采用概率路由的轉(zhuǎn)發(fā)方式，即只有相遇節(jié)點與目的節(jié)點的相遇概率更高時才會對消息進行轉(zhuǎn)發(fā).

3.2 問題描述

問題1.現(xiàn)有的2-ACK機制的自私性判定是在數(shù)據(jù)信息交互結(jié)束之后進行的，若此時判定相遇節(jié)點為自私節(jié)點，而在此之前將數(shù)據(jù)消息轉(zhuǎn)發(fā)給相遇節(jié)點，會導(dǎo)致數(shù)據(jù)消息被丟棄，從而導(dǎo)致了無效的網(wǎng)絡(luò)開銷.

問題2.現(xiàn)有的RSND機制對難以判斷的節(jié)點類型采用概率定性的方式來判斷節(jié)點的自私性，這種概率定性的方式容易造成對節(jié)點的自私性判斷不準確.

問題3.當前節(jié)點在檢測出其它節(jié)點為自私節(jié)點時，在散播自私節(jié)點信息時，需要單獨的控制信息或增加消息的長度，從而導(dǎo)致網(wǎng)絡(luò)的開銷增大.

4 SNPR算法

針對上述提出的問題，本文提出了一種結(jié)合概率路由的機會網(wǎng)絡(luò)自私節(jié)點檢測算法—SNPR，該算法能有效地提高節(jié)點自私性判斷的準確性和減少網(wǎng)絡(luò)開銷.

4.1 交互模型

機會網(wǎng)絡(luò)中相遇節(jié)點的通信過程如圖1所示，節(jié)點C接收到節(jié)點B周期性的Hello消息后，與節(jié)點B交換SV(Summary Vector)列表與DP(Delivery Predictability)列表信息，SV列表中儲存每個節(jié)點所攜帶的消息的摘要信息，如圖2所示，DP列表記錄了本節(jié)點與其它節(jié)點的相遇概率，如圖3所示，節(jié)點B與節(jié)點C比較彼此的SV列表與DP列表后，向?qū)Ψ秸埱笞陨硭鶝]有的并且自身與目的節(jié)點相遇概率更高的消息，以及發(fā)送對方所請求的消息.

圖1 節(jié)點間交互模型

圖2 SV列表

圖3 DP列表

4.2 SNPR算法包含的新機制

SNPR算法包含3種新機制，具體如下.

4.2.1 基于控制消息判定節(jié)點自私性

當前節(jié)點在接收到對方節(jié)點的SV-DP消息以后，首先利用對方的SV列表中的信息進行判斷對方節(jié)點是否是非自私節(jié)點：若對方SV消息列表中存在源地址不是對方節(jié)點的消息，則表示對方節(jié)點在為其它節(jié)點轉(zhuǎn)發(fā)數(shù)據(jù)消息，據(jù)此可以判定出對方節(jié)點是非自私節(jié)點；若對方節(jié)點SV列表中的消息的源地址都是對方節(jié)點，則判定其為難以判斷類型的節(jié)點.

當與對方節(jié)點交互SV、DP列表以后，若未判定對方節(jié)點為自私節(jié)點，則向?qū)Ψ秸埱笞陨硭鶝]有并且與目的節(jié)點相遇概率高于對方節(jié)點的消息，并將對方所請求的消息發(fā)送給對方.此過程存在以下檢測判定：

1)當前節(jié)點SV列表中包含有對方節(jié)點SV列表中沒有且目的地址不是對方節(jié)點并且對方節(jié)點與目的節(jié)點相遇概率更高的消息，但對方節(jié)點未請求這類消息，則可以判定對方節(jié)點為自私節(jié)點.

2)若對方節(jié)點請求了1)中所說的這類消息，當前節(jié)點將對方節(jié)點所請求的消息發(fā)送給對方，并采用監(jiān)聽機制監(jiān)聽對方節(jié)點是否進行了消息轉(zhuǎn)發(fā).若對方節(jié)點進行了消息轉(zhuǎn)發(fā)，則當前節(jié)點對監(jiān)聽到的數(shù)據(jù)消息進行頭部地址信息的提取，比較消息源地址是否是對方節(jié)點，若不是則判定對方節(jié)點是非自私節(jié)點；否則采用RSSI機制[14]判斷對方節(jié)點是否仍處于當前節(jié)點的監(jiān)聽范圍，若是則繼續(xù)監(jiān)聽，若不是則將對方節(jié)點的類型歸為難以判定類型.

如圖4所示為基于控制消息判定節(jié)點自私性機制的流程圖.

4.2.2 借助相遇節(jié)點信息判定節(jié)點自私性

當前節(jié)點(稱之為“節(jié)點A”，下同)與對方節(jié)點(稱之為“節(jié)點B”，下同)完成數(shù)據(jù)消息交互之后，節(jié)點A繼續(xù)監(jiān)聽節(jié)點B的消息轉(zhuǎn)發(fā)行為.

若監(jiān)聽到節(jié)點B與另一節(jié)點(稱之為“節(jié)點C”，下同)進行了數(shù)據(jù)傳輸，則在節(jié)點A中記錄節(jié)點C的地址信息，表示節(jié)點A在監(jiān)聽過程中發(fā)現(xiàn)節(jié)點B與節(jié)點C進行了消息交互，同時對監(jiān)聽到的數(shù)據(jù)消息進行頭部地址信息的提取，若消息源地址是節(jié)點B，與此同時節(jié)點A采用RSSI機制判斷節(jié)點B即將離開節(jié)點A的監(jiān)聽范圍時，那么根據(jù)“基于控制消息判定節(jié)點自私性”機制只能將節(jié)點B歸為難以判斷類型的節(jié)點.為了進一步對節(jié)點B的類型進行判斷，節(jié)點A接下來在一段時間內(nèi)如果遇到節(jié)點C，則根據(jù)“基于概率值捎帶節(jié)點自私信息”機制查看節(jié)點C的DP列表中對應(yīng)節(jié)點B的概率，若節(jié)點C根據(jù)“基于控制消息判定節(jié)點自私性”機制將節(jié)點B判定為自私節(jié)點或者非自私節(jié)點時，節(jié)點A則根據(jù)節(jié)點C的判斷結(jié)果將在自身DP列表對應(yīng)的節(jié)點B處判定為相應(yīng)的類型；若節(jié)點C將節(jié)點B判定為難以判斷類型的節(jié)點時，根據(jù)“基于控制消息判定節(jié)點自私性”機制可知節(jié)點B的SV列表中沒有源地址為其它節(jié)點的消息，而節(jié)點B與節(jié)點C交互之前節(jié)點A轉(zhuǎn)發(fā)了消息給節(jié)點B，由此可知節(jié)點B將節(jié)點A轉(zhuǎn)發(fā)的消息刪除了，因此判定節(jié)點B為自私節(jié)點.

圖4 機制1流程圖

若節(jié)點A在監(jiān)聽過程中沒有監(jiān)聽到節(jié)點B與其它節(jié)點進行數(shù)據(jù)交互時，則節(jié)點A按照如圖5所示的結(jié)構(gòu)記錄相應(yīng)的信息(Address表示相遇節(jié)點的地址；T表示相遇的時間點；Flag取值為0或1，用于表示當前節(jié)點是否轉(zhuǎn)發(fā)了目的地址不是相遇節(jié)點的消息給相遇節(jié)點；PreHop表示相遇節(jié)點在與當前節(jié)點相遇之前的上一個相遇節(jié)點地址).當節(jié)點B在脫離監(jiān)聽范圍后與其它節(jié)點(稱之為“節(jié)點E”，下同)進行數(shù)據(jù)交互時，若節(jié)點E在與節(jié)點B交互過程中將節(jié)點B判斷為自私節(jié)點或者非自私節(jié)點，則節(jié)點E不對節(jié)點B的信息進行記錄，原因是：根據(jù)“基于概率值捎帶節(jié)點自私信息”機制可知，當節(jié)點E與節(jié)點A相遇時，節(jié)點A查看節(jié)點E的概率列表就可以知道節(jié)點B是自私節(jié)點還是非自私節(jié)點.若節(jié)點E在與節(jié)點B交互過程中將節(jié)點B判斷為難以判斷類型的節(jié)點時，則按照圖5所示的結(jié)構(gòu)記錄節(jié)點B的信息，此時PreHop記為A節(jié)點地址.當節(jié)點A與節(jié)點E在某個時刻相遇時，根據(jù)記錄信息可知，節(jié)點A在與節(jié)點B交互完之后，節(jié)點B與節(jié)點E進行了消息交互，而由于節(jié)點A中的Flag等于1，因此可以判定節(jié)點B將節(jié)點A轉(zhuǎn)發(fā)的消息刪除了，從而判定節(jié)點B為自私節(jié)點.

圖5 記錄信息列表

Fig.5 Record information list

針對以上兩種情況提出一種融合機制，即節(jié)點A與節(jié)點B進行消息交互之后，若通過監(jiān)聽仍然無法判斷節(jié)點B的節(jié)點類型時，節(jié)點A采用如圖6所示的信息列表記錄節(jié)點B的信息(NextHop表示節(jié)點A監(jiān)聽到與節(jié)點B進行通信節(jié)點的地址).機制的具體實現(xiàn)過程如下：

圖6 信息列表

Fig.6 Information list

S1：節(jié)點A中的Address記為節(jié)點B的地址，T記為當前時間TAB，PreHop記錄節(jié)點B在與節(jié)點A進行交互之前的上一個交互節(jié)點，假設(shè)為節(jié)點G；

S2：若節(jié)點A在監(jiān)聽范圍內(nèi)監(jiān)聽到節(jié)點B與其它節(jié)點(例如，節(jié)點C)進行了消息交互，則在節(jié)點A的NextHop中記錄節(jié)點C的地址，否則記為0；

S3：節(jié)點A在與節(jié)點B進行消息交互時，若節(jié)點A轉(zhuǎn)發(fā)了目的地址不是節(jié)點B的消息給節(jié)點B，節(jié)點A中的Flag則記為1，否則記為0；

S4：當節(jié)點A與其它節(jié)點(假設(shè)為節(jié)點E)進行交互時，先根據(jù)“基于概率值捎帶節(jié)點自私信息”機制判斷節(jié)點B的類型，若節(jié)點E已判斷出節(jié)點B的類型，則節(jié)點A根據(jù)節(jié)點E的判斷結(jié)果進行修改，同時刪除記錄信息；

S5：若節(jié)點E只是將節(jié)點B判為難以判斷類型的節(jié)點時，節(jié)點A首先查看NextHop是否為0，若不為0則比較節(jié)點E的地址值是否等于NextHop的值，若相等則查看Flag的值是否等于1，若Flag=1，則判定節(jié)點B為自私節(jié)點，若Flag=0或者節(jié)點E的地址不等于NextHop的值，則判定節(jié)點B為難以判斷類型的節(jié)點；若節(jié)點A的NextHop值為0，且Flag=1，則查看節(jié)點E中Address值為節(jié)點B的記錄信息，若TEB的值大于TAB，且節(jié)點E中的PreHop的值為節(jié)點A的地址，則表示節(jié)點A在與節(jié)點B交互完之后，節(jié)點B與節(jié)點E進行了消息交互，因此可以判定節(jié)點B為自私節(jié)點.

一旦判斷出節(jié)點的類型，則刪除對應(yīng)節(jié)點在信息列表中的記錄.

4.2.3 基于概率值捎帶節(jié)點自私信息

在不增加額外控制開銷的情況下，節(jié)點將其它節(jié)點的自私性信息用DP列表中的概率值捎帶著傳輸：即將DP列表中到自私節(jié)點的概率值設(shè)置為負的當前值，將DP列表中到難以判斷的節(jié)點類型的概率值設(shè)置為當前值加1，將到非自私節(jié)點的概率值用正常的0和1之間的值表示.當收到了相遇節(jié)點發(fā)來的DP列表后，節(jié)點便能夠根據(jù)其DP列表中的概率值判斷對應(yīng)的節(jié)點的自私性.該機制能夠在不增加額外控制開銷的情況下有效地散播節(jié)點的自私性信息.

所述的“基于概率值捎帶節(jié)點自私信息”新機制在不增加網(wǎng)絡(luò)開銷的前提下，使節(jié)點將其它節(jié)點的自私性信息用DP列表中的概率值捎帶著傳輸，具體實現(xiàn)過程如下：

S1：機會網(wǎng)絡(luò)中的節(jié)點通過周期性的廣播Hello消息與其它節(jié)點進行鄰居發(fā)現(xiàn)，節(jié)點雙方發(fā)現(xiàn)彼此互為鄰居后，交互SV-DP列表消息；

S2：節(jié)點在發(fā)送SV-DP消息之前，根據(jù)自己掌握的其它節(jié)點自私性信息，將其它節(jié)點在DP列表中對應(yīng)的節(jié)點的概率值設(shè)置為負值、0～1之間的值或者1～2之間的值：自私節(jié)點的概率值在原值上取反成為負值、非自私節(jié)點的概率值在原來的0～1之間保持不變、難以判斷的節(jié)點的概率值在原值上加1，因此位于1～2之間；

S3：若一個節(jié)點收到相遇節(jié)點的SV-DP列表后，將該SV-DP列表中概率值為負的節(jié)點在本節(jié)點的SV-DP列表中相應(yīng)的節(jié)點處將概率值置為負的當前值；若收到的SV-DP列表中節(jié)點對應(yīng)的概率值在0～1之間，執(zhí)行步驟S4；若收到的SV-DP列表中節(jié)點對應(yīng)的概率值在1～2之間，不做處理；

S4：當收到的SV-DP列表中節(jié)點對應(yīng)的概率值在0～1之間時，表明節(jié)點是非自私節(jié)點，此時若本節(jié)點SV-DP列表中對應(yīng)的該節(jié)點概率值在1～2的范圍時，將該概率值減1；若概率值在其他范圍時，不做處理.

4.3 算法操作

SNPR算法的具體操作步驟如下：

Step 1.節(jié)點C接收到節(jié)點B廣播的Hello消息后，節(jié)點C查看自身的DP列表中是否有節(jié)點B.若有則表明節(jié)點非初次相遇，節(jié)點C根據(jù) DP列表判斷節(jié)點B是否是自私節(jié)點，如果沒有判定節(jié)點B為自私節(jié)點，則采用PROPHET算法[3]更改到該節(jié)點的相遇概率.若節(jié)點初次相遇則加入DP列表中并賦初值.

Step 2.如果節(jié)點B沒有被判定為自私節(jié)點，則節(jié)點C向節(jié)點B發(fā)送自身的SVC與DPC消息.

Step 3.節(jié)點B收到節(jié)點C的與消息后，先執(zhí)行“基于概率值捎帶節(jié)點自私信息”機制來更新自己的SV-DP列表，然后查看自身的DP列表來判定節(jié)點C是否是自私節(jié)點.若節(jié)點C為難以判定類型的節(jié)點或是初次相遇的節(jié)點，則根據(jù)節(jié)點C的SVC消息來判定節(jié)點C是否是非自私節(jié)點：如果節(jié)點C是非自私節(jié)點，則更新DP列表中對應(yīng)節(jié)點的概率值；否則DP列表維持不變.

Step 4.如果節(jié)點C沒有被判定為自私節(jié)點，則節(jié)點B向節(jié)點C發(fā)送自身的SVB與DPB消息以及發(fā)送請求消息.

Step 5.節(jié)點C收到節(jié)點B發(fā)送的SVB與DPB消息以及發(fā)送的請求消息后，執(zhí)行“基于概率值捎帶節(jié)點自私信息”機制來更新自己的SV-DP列表.如果節(jié)點B為難以判定類型的節(jié)點，則根據(jù)SVB消息來判定節(jié)點B是否是非自私節(jié)點：如果節(jié)點B是非自私節(jié)點，則更新DP列表中對應(yīng)節(jié)點的概率值；否則根據(jù)節(jié)點B發(fā)送的請求消息來判斷節(jié)點的自私性.

Step 6.如果節(jié)點B沒有被判定為自私節(jié)點，則節(jié)點C向節(jié)點B發(fā)送請求消息以及節(jié)點B所請求的消息.

Step 7.若節(jié)點B仍為難以判定類型的節(jié)點，則節(jié)點C發(fā)完消息后采用監(jiān)聽機制監(jiān)聽節(jié)點B的消息轉(zhuǎn)發(fā)行為，若監(jiān)聽到節(jié)點B與另一節(jié)點(稱之為“節(jié)點E”，下同)進行了數(shù)據(jù)傳輸，則記錄節(jié)點E的ID同時對監(jiān)聽到的數(shù)據(jù)消息頭部進行地址信息的提取，若消息源地址不是節(jié)點B，則判定節(jié)點B是非自私節(jié)點；否則判斷對方節(jié)點是否仍處于當前節(jié)點的監(jiān)聽范圍，若是則繼續(xù)監(jiān)聽，若不是則采用“借助相遇節(jié)點信息判定節(jié)點自私性”機制來對節(jié)點B的類型進行進一步地判定.

在每次判定中，若判定出對方節(jié)點為自私節(jié)點，則停止與其進行通信，并更新節(jié)點DP列表中對應(yīng)節(jié)點的概率值.

5 仿真驗證

本文采用OPNET14.5網(wǎng)絡(luò)仿真軟件對SNPR算法的性能進行仿真驗證，并將仿真結(jié)果同基于2-ACK算法和RSND算法的仿真結(jié)果進行對比.

5.1 仿真參數(shù)

本文在不同的自私節(jié)點比例場景中進行仿真，其仿真具體參數(shù)如表1所示.

表1 仿真參數(shù)設(shè)置

Table 1 Simulation parameter settings

參數(shù) 數(shù)值仿真時間/s3600模擬區(qū)域大小 1500 m×300 m節(jié)點數(shù)量50節(jié)點移動速率/(m·s-1)1～3自私節(jié)點所占比例/%{0～80}節(jié)點通信半徑/m10MAC層和物理層標準802.11a節(jié)點緩存大小/MB50消息生存時間/s300隨機種子值{64,128,256,512}

5.2 仿真結(jié)果及分析

5.2.1 自私節(jié)點檢測準確率

如圖7所示，隨著自私節(jié)點比例的增加，SNPR算法能夠保持較高的自私節(jié)點檢測準確率，并且檢測準確率明顯優(yōu)于RSND算法和2-ACK算法，其主要原因在于提出了“基于控制消息判定節(jié)點自私性”和“借助相遇節(jié)點信息判定節(jié)點自私性”這兩種新機制，使得自私節(jié)點檢測準確率得到提高.

圖7 自私節(jié)點檢測準確率

5.2.2 消息到達率

消息到達率是指所有目的節(jié)點接收到的數(shù)據(jù)總量R與所有源節(jié)點產(chǎn)生的數(shù)據(jù)總數(shù)S的比值，計算公式為：

η=R/S(其中η表示消息到達率)

(1)

如圖8所示，隨著網(wǎng)絡(luò)中自私節(jié)點比例的增加，消息到達率在減小.因為網(wǎng)絡(luò)中自私節(jié)點數(shù)越多，消息被轉(zhuǎn)發(fā)的次數(shù)就越少，從而導(dǎo)致消息到達率降低.從圖中可以看出SNPR算法的消息到達率相比于2-ACK和RSND算法得到了提高.其原因是RSND算法中，當對相遇節(jié)點的自私性無法判定時，采取網(wǎng)絡(luò)中的自私節(jié)點比例對相遇節(jié)點進行概率定性，當網(wǎng)絡(luò)中的自私節(jié)點比例增加時，對非自私節(jié)點誤判的概率也就越來越高，導(dǎo)致更多的消息無法成功傳送.SNPR算法采用了“借助相遇節(jié)點信息判定節(jié)點自私性”機制，使得對節(jié)點的自私行為判斷更為準確，并且不受自私節(jié)點比例的影響，因此消息到達率得到提高.

圖8 消息到達率

5.2.3 吞吐量

吞吐量表示網(wǎng)絡(luò)傳輸數(shù)據(jù)消息的能力，它是指單位時間內(nèi)網(wǎng)絡(luò)中成功傳輸數(shù)據(jù)消息的比特數(shù)，計算公式為：

Throughput=P/(Tend-Tstart)

(2)

其中P表示的是網(wǎng)絡(luò)中數(shù)據(jù)消息成功到達目的節(jié)點的總比特數(shù),Tstart表示網(wǎng)絡(luò)仿真開始時間,Tend表示網(wǎng)絡(luò)仿真結(jié)束時間.

圖9 網(wǎng)絡(luò)吞吐量

如圖9所示，吞吐量隨著網(wǎng)絡(luò)中自私節(jié)點的比例增加而減少，原因是網(wǎng)絡(luò)中自私節(jié)點數(shù)越多，消息到達率就減少，從而導(dǎo)致吞吐量下降.另外，從圖中可以看出 SNPR算法的吞吐量明顯高于2-ACK算法和RSND算法.其主要原因是SNPR能更準確的判斷相遇節(jié)點是否為自私節(jié)點，對自私節(jié)點和非自私節(jié)點所產(chǎn)生的消息都能進行正確處理，減少了對非自私節(jié)點判斷失誤而采取的懲罰策略，使更多的消息能傳遞到目的節(jié)點，因而吞吐量得到提升.

5.2.4 平均時延

平均時延表示數(shù)據(jù)消息成功傳輸?shù)侥康墓?jié)點所需要的平均時間，其計算公式是：

(3)

其中，D表示數(shù)據(jù)消息到達目的節(jié)點的個數(shù),Ti表示第i個消息到達目的節(jié)點的時延.

如圖10所示，隨著自私節(jié)點比例的增加，平均時延在上升，原因是網(wǎng)絡(luò)中提供消息轉(zhuǎn)發(fā)的節(jié)點數(shù)在減少，消息不能及時地進行轉(zhuǎn)發(fā).同時，SNPR算法的平均時延小于2-ACK算法和RSND算法，其原因是SNPR算法對自私節(jié)點的檢測更為準確，避免因?qū)Ψ亲运焦?jié)點判斷失誤而導(dǎo)致消息沒有及時轉(zhuǎn)發(fā)帶來的時延，使消息能更迅速的在非自私節(jié)點之間傳輸；同時由于“基于概率值捎帶節(jié)點自私信息”機制能夠減少網(wǎng)絡(luò)中的控制消息，使得數(shù)據(jù)消息能夠提前轉(zhuǎn)發(fā).

圖10 網(wǎng)絡(luò)平均時延

6 結(jié)束語

本文提出了一種結(jié)合概率路由的機會網(wǎng)絡(luò)自私節(jié)點檢測算法.該算法由“基于控制消息判定節(jié)點自私性”、“借助相遇節(jié)點信息判定節(jié)點自私性”和“基于概率值捎帶節(jié)點自私信息”三種新機制組成.通過采用“基于控制消息判定節(jié)點自私性”和“借助相遇節(jié)點信息判定節(jié)點自私性”這兩種機制能夠提高自私節(jié)點檢測的準確性并且能夠檢測出網(wǎng)絡(luò)中更多的自私節(jié)點，在傳輸數(shù)據(jù)包時減少將消息轉(zhuǎn)發(fā)給自私節(jié)點的情況，進而提高數(shù)據(jù)包到達目的節(jié)點的成功率；采用“基于概率值捎帶節(jié)點自私信息”機制能夠使節(jié)點在不增加字段或消息的前提下，將其它節(jié)點的自私性信息用DP列表中的概率值捎帶著傳播給相遇節(jié)點，從而降低了網(wǎng)絡(luò)控制開銷.由于機會網(wǎng)絡(luò)中消息的傳輸時延較大，因此下一步的工作是對機會網(wǎng)絡(luò)的路由轉(zhuǎn)發(fā)策略進行研究，通過研究路由轉(zhuǎn)發(fā)策略來提高消息的轉(zhuǎn)發(fā)效率.