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

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

2(重慶郵電大學(xué) 移動(dòng)通信技術(shù)重慶市重點(diǎn)實(shí)驗(yàn)室，重慶 400065)

E-mail：2849819270@qq.com

1 引 言

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

2 相關(guān)工作

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

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

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

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

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

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

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

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

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

3.1 假設(shè)

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

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

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

3.2 問(wèn)題描述

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

問(wèn)題2.現(xiàn)有的RSND機(jī)制對(duì)難以判斷的節(jié)點(diǎn)類型采用概率定性的方式來(lái)判斷節(jié)點(diǎn)的自私性，這種概率定性的方式容易造成對(duì)節(jié)點(diǎn)的自私性判斷不準(zhǔn)確.

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

4 SNPR算法

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

4.1 交互模型

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

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

圖2 SV列表

圖3 DP列表

4.2 SNPR算法包含的新機(jī)制

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

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

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

當(dāng)與對(duì)方節(jié)點(diǎn)交互SV、DP列表以后，若未判定對(duì)方節(jié)點(diǎn)為自私節(jié)點(diǎn)，則向?qū)Ψ秸?qǐng)求自身所沒(méi)有并且與目的節(jié)點(diǎn)相遇概率高于對(duì)方節(jié)點(diǎn)的消息，并將對(duì)方所請(qǐng)求的消息發(fā)送給對(duì)方.此過(guò)程存在以下檢測(cè)判定：

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

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

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

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

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

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

圖4 機(jī)制1流程圖

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

圖5 記錄信息列表

Fig.5 Record information list

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

圖6 信息列表

Fig.6 Information list

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

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

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

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

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

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

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

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

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

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

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

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

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

4.3 算法操作

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

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

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

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

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

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

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

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

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

5 仿真驗(yàn)證

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

5.1 仿真參數(shù)

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

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

Table 1 Simulation parameter settings

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

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

5.2.1 自私節(jié)點(diǎn)檢測(cè)準(zhǔn)確率

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

圖7 自私節(jié)點(diǎn)檢測(cè)準(zhǔn)確率

5.2.2 消息到達(dá)率

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

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

(1)

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

圖8 消息到達(dá)率

5.2.3 吞吐量

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

Throughput=P/(Tend-Tstart)

(2)

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

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

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

5.2.4 平均時(shí)延

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

(3)

其中，D表示數(shù)據(jù)消息到達(dá)目的節(jié)點(diǎn)的個(gè)數(shù),Ti表示第i個(gè)消息到達(dá)目的節(jié)點(diǎn)的時(shí)延.

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

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

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

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