任智，譚永銀，李季碧，陳前斌

?

可靠的機(jī)會(huì)網(wǎng)絡(luò)自私節(jié)點(diǎn)檢測(cè)算法

任智，譚永銀，李季碧，陳前斌

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

針對(duì)現(xiàn)有機(jī)會(huì)網(wǎng)絡(luò)自私節(jié)點(diǎn)檢測(cè)算法沒(méi)有考慮節(jié)點(diǎn)收到錯(cuò)幀和節(jié)點(diǎn)脫離通信范圍監(jiān)聽(tīng)失敗的情況而影響檢測(cè)準(zhǔn)確性的問(wèn)題，提出一種可靠的自私節(jié)點(diǎn)檢測(cè)新算法——RSND。采用基于跨層監(jiān)聽(tīng)機(jī)制的錯(cuò)幀解析、基于節(jié)點(diǎn)相遇的信息挖掘和基于RSSI的節(jié)點(diǎn)距離估計(jì)3種新機(jī)制消除錯(cuò)幀和節(jié)點(diǎn)脫離通信范圍監(jiān)聽(tīng)失敗對(duì)節(jié)點(diǎn)自私性檢測(cè)的影響，提升檢測(cè)可靠性。理論分析證明了RSND算法的有效性，仿真結(jié)果顯示，相對(duì)于現(xiàn)有的基于2-ACK的自私節(jié)點(diǎn)檢測(cè)算法和Watchdog檢測(cè)算法，新算法的自私節(jié)點(diǎn)檢測(cè)準(zhǔn)確率和網(wǎng)絡(luò)吞吐量至少提高了6%和4%。

機(jī)會(huì)網(wǎng)絡(luò)；自私節(jié)點(diǎn)；檢測(cè)算法；監(jiān)聽(tīng)；誤判

1 引言

機(jī)會(huì)網(wǎng)絡(luò)[1,2]是一種不需要源節(jié)點(diǎn)和目的節(jié)點(diǎn)之間存在完整鏈路，利用節(jié)點(diǎn)移動(dòng)帶來(lái)的相遇機(jī)會(huì)實(shí)現(xiàn)通信的時(shí)延和分裂可容忍的無(wú)線自組織網(wǎng)絡(luò)。目前，機(jī)會(huì)網(wǎng)絡(luò)路由協(xié)議均假設(shè)網(wǎng)絡(luò)中的節(jié)點(diǎn)具有良好的協(xié)作性。然而，由于機(jī)會(huì)網(wǎng)絡(luò)中節(jié)點(diǎn)的資源（包括能量和緩存等）有限，為了節(jié)約資源，節(jié)點(diǎn)會(huì)拒絕幫助其他節(jié)點(diǎn)轉(zhuǎn)發(fā)消息。這種自私行為使現(xiàn)有的路由機(jī)制無(wú)法正常工作，從而導(dǎo)致網(wǎng)絡(luò)性能退化[3,4]。機(jī)會(huì)網(wǎng)絡(luò)中不為系統(tǒng)作貢獻(xiàn)，只享受信息資源服務(wù)的節(jié)點(diǎn)稱(chēng)為自私節(jié)點(diǎn)。自私節(jié)點(diǎn)并不想要損害其他節(jié)點(diǎn)，從而造成信息傳遞的失敗，主要是在使用網(wǎng)絡(luò)資源的同時(shí)，拒絕消耗自身有限的能量為其他節(jié)點(diǎn)提供信息轉(zhuǎn)發(fā)服務(wù)，即不協(xié)作參與網(wǎng)絡(luò)中的信息轉(zhuǎn)發(fā)服務(wù)[5]。自私節(jié)點(diǎn)的存在會(huì)嚴(yán)重影響網(wǎng)絡(luò)性能以及網(wǎng)絡(luò)服務(wù)的可靠性，甚至?xí)茐木W(wǎng)絡(luò)的正常運(yùn)行。因此如何設(shè)計(jì)有效的自私節(jié)點(diǎn)檢測(cè)算法，促使數(shù)據(jù)能夠成功轉(zhuǎn)發(fā)到目的節(jié)點(diǎn)成為當(dāng)前機(jī)會(huì)網(wǎng)絡(luò)中亟待解決的問(wèn)題。

目前，可用于機(jī)會(huì)網(wǎng)絡(luò)的自私節(jié)點(diǎn)檢測(cè)算法主要有IRONMAN[6]、CORE[7]、CONFIDANT[8]、Watchdog[9]和2-ACK[10]等。IRONMAN是一種基于噴霧式路由的自私節(jié)點(diǎn)自主檢測(cè)機(jī)制，節(jié)點(diǎn)通過(guò)相遇并交換歷史記錄來(lái)判斷中間節(jié)點(diǎn)的自私性。由于機(jī)會(huì)網(wǎng)絡(luò)中節(jié)點(diǎn)是自由移動(dòng)的，任意2個(gè)節(jié)點(diǎn)相遇周期具有不確定性，這就使IRONMAN檢測(cè)算法對(duì)自私節(jié)點(diǎn)的檢測(cè)難以滿足實(shí)時(shí)性要求。CORE算法通過(guò)信譽(yù)值來(lái)判斷節(jié)點(diǎn)的自私性，信譽(yù)值包括主觀信譽(yù)值、間接信譽(yù)值和功能信譽(yù)值，最后的信譽(yù)評(píng)價(jià)是這3者的綜合。其中，間接信譽(yù)值來(lái)自社區(qū)中的其他節(jié)點(diǎn)，由于機(jī)會(huì)網(wǎng)絡(luò)中的節(jié)點(diǎn)移動(dòng)性較強(qiáng)，鄰居節(jié)點(diǎn)不固定，社區(qū)劃分不明顯，因此CORE機(jī)制的準(zhǔn)確性得不到保證。CONFIDANT機(jī)制也是根據(jù)信譽(yù)來(lái)判斷節(jié)點(diǎn)的自私性，但信譽(yù)值維護(hù)、傳播及節(jié)點(diǎn)信任機(jī)制復(fù)雜且不可靠，容易導(dǎo)致信譽(yù)不一致的問(wèn)題。Watchdog檢測(cè)算法的主要思想是利用廣播信道的特征，偵聽(tīng)下一跳節(jié)點(diǎn)是否轉(zhuǎn)發(fā)了該消息。若在規(guī)定的時(shí)間內(nèi)下一跳節(jié)點(diǎn)無(wú)更改地轉(zhuǎn)發(fā)了此消息，則說(shuō)明下一跳節(jié)點(diǎn)行為良好；反之則說(shuō)明下一跳節(jié)點(diǎn)出現(xiàn)了不合作行為。該算法在普通移動(dòng)自組織網(wǎng)絡(luò)中效果良好，但在機(jī)會(huì)網(wǎng)絡(luò)中，由于節(jié)點(diǎn)隨機(jī)移動(dòng)，節(jié)點(diǎn)可能脫離通信范圍，數(shù)據(jù)分組之間可能發(fā)生碰撞，造成檢測(cè)不準(zhǔn)確；當(dāng)節(jié)點(diǎn)沒(méi)監(jiān)聽(tīng)到數(shù)據(jù)分組時(shí)，認(rèn)為節(jié)點(diǎn)沒(méi)參與轉(zhuǎn)發(fā)，判斷過(guò)于嚴(yán)格?；?-ACK的自私節(jié)點(diǎn)檢測(cè)算法的主要思想是當(dāng)一個(gè)節(jié)點(diǎn)成功轉(zhuǎn)發(fā)數(shù)據(jù)分組后，其下一跳節(jié)點(diǎn)會(huì)向其上一跳節(jié)點(diǎn)發(fā)送一個(gè)2跳應(yīng)答數(shù)據(jù)分組，指示成功接收到數(shù)據(jù)。相對(duì)于Watchdog檢測(cè)算法，基于2-ACK的自私節(jié)點(diǎn)檢測(cè)算法在部分情況下能夠提高自私節(jié)點(diǎn)檢測(cè)的準(zhǔn)確率，但它要求存在2跳的路徑，而且引入了大量2-ACK應(yīng)答分組，增加了控制開(kāi)銷(xiāo)，容易引起網(wǎng)絡(luò)擁塞，進(jìn)而影響網(wǎng)絡(luò)性能以及檢測(cè)準(zhǔn)確性。

綜上所述，在機(jī)會(huì)網(wǎng)絡(luò)中應(yīng)用Watchdog算法是一種較為可行的選擇，但本文在研究中發(fā)現(xiàn)當(dāng)機(jī)會(huì)網(wǎng)絡(luò)節(jié)點(diǎn)收到錯(cuò)幀和節(jié)點(diǎn)脫離通信范圍監(jiān)聽(tīng)失敗時(shí)，Watchdog算法因未考慮應(yīng)對(duì)之策而會(huì)出現(xiàn)誤判，影響檢測(cè)準(zhǔn)確性。為解決此問(wèn)題，提出了一種可靠的機(jī)會(huì)網(wǎng)絡(luò)自私節(jié)點(diǎn)檢測(cè)算法。

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

2.1 假設(shè)

為準(zhǔn)確界定問(wèn)題，做出如下假設(shè)。網(wǎng)絡(luò)節(jié)點(diǎn)分為自私和不自私2種類(lèi)型。自私節(jié)點(diǎn)只發(fā)送自己的數(shù)據(jù)分組，不為其他節(jié)點(diǎn)轉(zhuǎn)發(fā)數(shù)據(jù)分組。節(jié)點(diǎn)都是使用全向天線，通信范圍相等[11,12]，無(wú)線鏈路為雙向鏈路。

2.2 問(wèn)題描述

由于機(jī)會(huì)網(wǎng)絡(luò)中存在無(wú)線信道質(zhì)量、干擾以及信號(hào)碰撞等不穩(wěn)定因素，造成幀的長(zhǎng)度、內(nèi)容等發(fā)生變化，節(jié)點(diǎn)收到的幀未能通過(guò)校驗(yàn)，也就是所謂的“收到錯(cuò)幀”，容易造成誤判，從而導(dǎo)致檢測(cè)不準(zhǔn)確。

由于節(jié)點(diǎn)的隨機(jī)移動(dòng)，攜帶數(shù)據(jù)分組的中間節(jié)點(diǎn)在移動(dòng)的過(guò)程中可能脫離節(jié)點(diǎn)的通信范圍，造成節(jié)點(diǎn)難以監(jiān)聽(tīng)中間節(jié)點(diǎn)是否轉(zhuǎn)發(fā)了數(shù)據(jù)分組，導(dǎo)致檢測(cè)困難。

前面提到的檢測(cè)算法中均沒(méi)有考慮到上述問(wèn)題，會(huì)造成部分行為良好（轉(zhuǎn)發(fā)了數(shù)據(jù)幀）的節(jié)點(diǎn)因?yàn)楸O(jiān)聽(tīng)節(jié)點(diǎn)沒(méi)有偵聽(tīng)到其轉(zhuǎn)發(fā)操作而被誤判為自私節(jié)點(diǎn)，導(dǎo)致它們受到不必要的懲罰（數(shù)據(jù)分組不能被轉(zhuǎn)發(fā)），從而降低網(wǎng)絡(luò)吞吐量。

3 RSND算法

為解決上述問(wèn)題，本文提出一種更可靠的自私節(jié)點(diǎn)檢測(cè)算法——RSND（reliable selfish node detection），它可在機(jī)會(huì)網(wǎng)絡(luò)相關(guān)路由協(xié)議中靈活使用。

3.1 RSND算法包含的新機(jī)制

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

3.1.1 錯(cuò)幀解析

當(dāng)前節(jié)點(diǎn)在監(jiān)聽(tīng)中間節(jié)點(diǎn)的行為時(shí)，收到未通過(guò)校驗(yàn)的幀后，不直接丟棄此幀，而是通過(guò)跨層提取幀中數(shù)據(jù)分組的頭部與中間節(jié)點(diǎn)保存的已發(fā)數(shù)據(jù)分組的頭部進(jìn)行比對(duì)，若二者相同，則說(shuō)明中間節(jié)點(diǎn)轉(zhuǎn)發(fā)了該數(shù)據(jù)分組；若二者不同，則提取一定長(zhǎng)度（缺省值建議為64 bit）的數(shù)據(jù)分組尾部信息和緩存分組進(jìn)行比對(duì)；如果相同，說(shuō)明中間節(jié)點(diǎn)進(jìn)行了數(shù)據(jù)分組轉(zhuǎn)發(fā)，不是自私節(jié)點(diǎn)；若不同，則將中間節(jié)點(diǎn)歸入難以確定的類(lèi)型。

3.1.2 基于節(jié)點(diǎn)相遇的信息挖掘

當(dāng)2個(gè)相遇節(jié)點(diǎn)交換數(shù)據(jù)分組時(shí)，收到數(shù)據(jù)分組后的節(jié)點(diǎn)提取分組頭部信息，判斷分組的源節(jié)點(diǎn)是否為對(duì)方節(jié)點(diǎn)；如果不是，說(shuō)明對(duì)方節(jié)點(diǎn)在為其他節(jié)點(diǎn)轉(zhuǎn)發(fā)數(shù)據(jù)分組，因此判定其不是自私節(jié)點(diǎn)；否則，對(duì)方節(jié)點(diǎn)便存在自私嫌疑，節(jié)點(diǎn)根據(jù)網(wǎng)絡(luò)中自私節(jié)點(diǎn)的比例，估計(jì)對(duì)方節(jié)點(diǎn)的自私性。

在節(jié)點(diǎn)存儲(chǔ)空間允許的情況下，節(jié)點(diǎn)建立一張與SV（summary vector）對(duì)應(yīng)的表，存儲(chǔ)每個(gè)數(shù)據(jù)分組的下一跳節(jié)點(diǎn)地址以及該數(shù)據(jù)分組的目的節(jié)點(diǎn)地址。數(shù)據(jù)分組的源節(jié)點(diǎn)如果發(fā)現(xiàn)相遇節(jié)點(diǎn)是目的節(jié)點(diǎn)且已收到該數(shù)據(jù)分組，則判定該數(shù)據(jù)分組的下一跳節(jié)點(diǎn)進(jìn)行了轉(zhuǎn)發(fā)，不是自私節(jié)點(diǎn)。

3.1.3 脫離判斷

節(jié)點(diǎn)采用跨層協(xié)作的方式判斷鄰居節(jié)點(diǎn)是否脫離通信范圍，具體思路為：節(jié)點(diǎn)通過(guò)在MAC層多次接收來(lái)自鄰居節(jié)點(diǎn)的幀（ACK幀、Hello幀等）并記錄收幀時(shí)間，采用RSSI[13]機(jī)制測(cè)收幀時(shí)節(jié)點(diǎn)間的間距，由記錄的時(shí)間和測(cè)得的間距計(jì)算節(jié)點(diǎn)運(yùn)動(dòng)的平均速度并確定運(yùn)動(dòng)方向，判斷鄰居節(jié)點(diǎn)是否已脫離通信范圍。如果在MAC層判斷鄰居節(jié)點(diǎn)已脫離通信范圍，則通過(guò)“跨層信息共享”的方式將該信息報(bào)告給網(wǎng)絡(luò)層；網(wǎng)絡(luò)層在未監(jiān)聽(tīng)到鄰居節(jié)點(diǎn)發(fā)送數(shù)據(jù)分組的情況下不將其判定為自私節(jié)點(diǎn)。

3.2 算法操作

RSND算法的具體操作步驟如下。

step1 節(jié)點(diǎn)周期性地廣播Hello消息進(jìn)行鄰居發(fā)現(xiàn)。在一個(gè)Hello周期內(nèi)，如果沒(méi)有收到任何一個(gè)鄰居節(jié)點(diǎn)回復(fù)的SV，則在該周期結(jié)束后，啟動(dòng)下一周期的鄰居發(fā)現(xiàn)過(guò)程；否則，進(jìn)入下一步。

step2 如果節(jié)點(diǎn)是源節(jié)點(diǎn)，則節(jié)點(diǎn)、均建立一張與SV對(duì)應(yīng)的表，存儲(chǔ)每個(gè)數(shù)據(jù)分組的下一跳節(jié)點(diǎn)地址以及該數(shù)據(jù)分組的目的節(jié)點(diǎn)地址。收到SV后，比較SV和SV，若在SV中發(fā)現(xiàn)其中包含自己的數(shù)據(jù)分組且正好是該數(shù)據(jù)分組的目的節(jié)點(diǎn)，則的下一跳節(jié)點(diǎn)不是自私節(jié)點(diǎn)。

step3 如果不確定節(jié)點(diǎn)、中是否存在源節(jié)點(diǎn)，則收到SV后，比較SV和SV，獲取緩存中有而自己沒(méi)有的數(shù)據(jù)分組信息并向發(fā)送Request請(qǐng)求消息，收到Request后，根據(jù)請(qǐng)求消息向發(fā)送數(shù)據(jù)分組，收到數(shù)據(jù)分組后，回復(fù)ACK給并更新自己的SV，節(jié)點(diǎn)通過(guò)提取分組頭部消息，判斷分組的源節(jié)點(diǎn)是否為，若不是，則不是自私節(jié)點(diǎn)，否則存在自私嫌疑，根據(jù)網(wǎng)絡(luò)中自私節(jié)點(diǎn)比例估計(jì)的自私性。

step4 節(jié)點(diǎn)收到來(lái)自節(jié)點(diǎn)的ACK時(shí)，記錄收到ACK的時(shí)間0，并采用RSSI機(jī)制測(cè)量節(jié)點(diǎn)、間的間距0。

step5 當(dāng)節(jié)點(diǎn)收到廣播的Hello消息時(shí)，記錄收到時(shí)間1、測(cè)量、間的間距1。由0、1、0和1計(jì)算的平均速度1，并比較0和1的大小，若0≥1且1不大，則、相互靠近且未脫離彼此的通信范圍，通過(guò)監(jiān)聽(tīng)收幀，判斷的自私性。若0＜1且1較大，則、可能脫離彼此的通信范圍，若未監(jiān)聽(tīng)發(fā)送數(shù)據(jù)分組，則不將節(jié)點(diǎn)判定為自私節(jié)點(diǎn)。如果收到的幀通過(guò)了幀校驗(yàn)，則判定不是自私節(jié)點(diǎn)；否則，進(jìn)入下一步。平均速度1的計(jì)算公式如下

其中，1、0、1和0分別表示收到的Hello、ACK消息時(shí)它們之間的間距和收到消息的時(shí)間。

step6收到未通過(guò)校驗(yàn)的幀后，不直接丟棄該幀，而是提取幀中數(shù)據(jù)分組的頭部并與保存的已發(fā)數(shù)據(jù)分組的頭部進(jìn)行比對(duì)，若二者相同，則說(shuō)明轉(zhuǎn)發(fā)了數(shù)據(jù)分組，不是自私節(jié)點(diǎn)；若二者不同，則提取一定長(zhǎng)度（缺省值建議為64 bit）的數(shù)據(jù)分組尾部信息和緩存分組進(jìn)行比對(duì)，如果相同，則不是自私節(jié)點(diǎn)，否則，將歸入難以確定類(lèi)型。

3.3 性能分析

關(guān)于RSND算法的性能，本文進(jìn)行了如下的理論分析。

引理1 在相同的網(wǎng)絡(luò)條件下，RSND算法的自私節(jié)點(diǎn)檢測(cè)準(zhǔn)確率高于現(xiàn)有相關(guān)自私節(jié)點(diǎn)檢測(cè)算法。

證明 假設(shè)網(wǎng)絡(luò)中每條無(wú)線信道出現(xiàn)干擾以及數(shù)據(jù)分組發(fā)生碰撞的概率分別為a和b。如圖1所示，在均不考慮節(jié)點(diǎn)脫離通信范圍的情況下，假設(shè)基于2-ACK的自私節(jié)點(diǎn)檢測(cè)算法出現(xiàn)誤判的概率為0，則

其中，0＜a＜1，0＜b＜1。假設(shè)RSND算法出現(xiàn)誤判的概率為1，則

(3)

比較式(2)和式(3)，顯然0>1，即相對(duì)于基于2-ACK的自私節(jié)點(diǎn)檢測(cè)算法，RSND檢測(cè)算法出現(xiàn)誤判的概率更低。

假設(shè)網(wǎng)絡(luò)中因數(shù)據(jù)分組發(fā)生碰撞而出現(xiàn)誤判的概率為(0＜＜1), 在均不考慮節(jié)點(diǎn)脫離通信范圍的情況下，假設(shè)Watchdog檢測(cè)算法檢測(cè)準(zhǔn)確的概率和RSND算法檢測(cè)準(zhǔn)確的概率分別為W和R，則

(5)

將式(5)化簡(jiǎn)可得

比較式(4)和式(6)，可知RSND檢測(cè)算法檢測(cè)準(zhǔn)確的概率高于Watchdog檢測(cè)算法。

在相同的網(wǎng)絡(luò)條件下，由于RSND檢測(cè)算法考慮了節(jié)點(diǎn)收到錯(cuò)幀和節(jié)點(diǎn)脫離通信范圍監(jiān)聽(tīng)失敗這2種情況，并采用了有效的機(jī)制進(jìn)行了合理的處理，因此相對(duì)于其他檢測(cè)算法, RSND檢測(cè)算法的自私節(jié)點(diǎn)檢測(cè)準(zhǔn)確率更高。

引理2 在相同的網(wǎng)絡(luò)條件下，RSND算法的控制開(kāi)銷(xiāo)低于現(xiàn)有自私節(jié)點(diǎn)檢測(cè)相關(guān)算法。

證明 假設(shè)節(jié)點(diǎn)發(fā)送消息的控制開(kāi)銷(xiāo)為，攜帶消息的平均控制開(kāi)銷(xiāo)為，網(wǎng)絡(luò)中產(chǎn)生的消息總量為，消息到達(dá)目的節(jié)點(diǎn)平均跳數(shù)為。

基于2-ACK的自私節(jié)點(diǎn)監(jiān)測(cè)算法中消息完成傳輸需要的總的控制開(kāi)銷(xiāo)為

RSND算法中消息完成傳輸需要的總的控制開(kāi)銷(xiāo)為

(8)

4 仿真分析

由于現(xiàn)實(shí)條件（如成本、時(shí)間等）的原因，同時(shí)考慮到專(zhuān)業(yè)網(wǎng)絡(luò)仿真軟件OPNET在網(wǎng)絡(luò)通信協(xié)議/算法性能比較方面的準(zhǔn)確性和接近網(wǎng)絡(luò)實(shí)際測(cè)量結(jié)果的可信度，本文選擇了業(yè)內(nèi)流行的OPNET軟件作為仿真平臺(tái)，對(duì)所提RSND算法的有效性進(jìn)行定量驗(yàn)證。

4.1 參數(shù)設(shè)置

在基于Epidemic[14~17]機(jī)制的路由算法上加載RSND算法、基于2-ACK的自私節(jié)點(diǎn)檢測(cè)算法和Watchdog檢測(cè)算法，分別將它們表示為R-Epidemic、A-Epidemic和 W-Epidemic。加載這些自私節(jié)點(diǎn)檢測(cè)算法的方法是在路由時(shí)避開(kāi)自私節(jié)點(diǎn)，不向這些節(jié)點(diǎn)發(fā)送數(shù)據(jù)分組。主要仿真參數(shù)設(shè)置如表1所示。

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

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

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

從圖2中可以看出，隨著自私節(jié)點(diǎn)比例的上升，RSND算法能維持較高的自私節(jié)點(diǎn)檢測(cè)準(zhǔn)確率，與基于2-ACK的自私節(jié)點(diǎn)檢測(cè)算法相比，RSND算法檢測(cè)準(zhǔn)確率提高了6%以上，主要原因在于提出的“錯(cuò)幀解析”、“信息挖掘”和“脫離判斷”3種新機(jī)制發(fā)揮了作用，使自私節(jié)點(diǎn)檢測(cè)的準(zhǔn)確率得到提高。

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

網(wǎng)絡(luò)吞吐量是在單位時(shí)間內(nèi)成功到達(dá)目的節(jié)點(diǎn)消息的比特?cái)?shù)。吞吐量受網(wǎng)絡(luò)的帶寬與網(wǎng)絡(luò)的額定速率的限制，計(jì)算公式為

其中，D表示成功到達(dá)目的節(jié)點(diǎn)消息的比特?cái)?shù)，T表示網(wǎng)絡(luò)運(yùn)行時(shí)間。

如圖3所示，相比與基于2-ACK的自私節(jié)點(diǎn)檢測(cè)算法，RSND算法能至少提高網(wǎng)絡(luò)吞吐量4%，主要原因是自私節(jié)點(diǎn)檢測(cè)準(zhǔn)確率高，被不合理懲罰的節(jié)點(diǎn)減少，因而有更多數(shù)據(jù)分組被轉(zhuǎn)發(fā)到目的節(jié)點(diǎn)。

4.2.3 投遞成功率

投遞成功率是指成功到達(dá)目的節(jié)點(diǎn)的消息數(shù)與源節(jié)點(diǎn)創(chuàng)建的消息數(shù)的比值。計(jì)算公式為

其中，D表示已到達(dá)目的節(jié)點(diǎn)的消息個(gè)數(shù)，S表示源節(jié)點(diǎn)所創(chuàng)建的消息個(gè)數(shù)。

如圖4所示，相比于基于2-ACK的自私節(jié)點(diǎn)檢測(cè)算法和Watchdog檢測(cè)算法，RSND算法的投遞成功率更高，主要原因是自私節(jié)點(diǎn)檢測(cè)準(zhǔn)確率提高后，更多行為良好節(jié)點(diǎn)發(fā)出的數(shù)據(jù)分組被轉(zhuǎn)發(fā)，從而到達(dá)目的節(jié)點(diǎn)的數(shù)據(jù)分組增加。

4.2.4 平均端到端時(shí)延

平均端到端時(shí)延是指所有消息到達(dá)目的節(jié)點(diǎn)時(shí)的平均時(shí)延，計(jì)算公式為

其中，T表示第個(gè)到達(dá)目的節(jié)點(diǎn)的消息時(shí)延，D表示已到達(dá)目的節(jié)點(diǎn)的消息個(gè)數(shù)。

如圖5所示，相比于基于2-ACK的自私節(jié)點(diǎn)檢測(cè)算法和Watchdog檢測(cè)算法，RSND算法能夠減少分組的端到端時(shí)延，其原因估計(jì)在于自私性檢測(cè)準(zhǔn)確性提高后，數(shù)據(jù)分組被傳送的概率在整體上有所增加，因而有利于它們更快地到達(dá)目的節(jié)點(diǎn)。

4.2.5 歸一化控制開(kāi)銷(xiāo)

歸一化控制開(kāi)銷(xiāo)是累加所有節(jié)點(diǎn)發(fā)出的控制消息的比特?cái)?shù)與到達(dá)目的節(jié)點(diǎn)消息的比特?cái)?shù)的比值，計(jì)算公式為

其中，C表示全網(wǎng)發(fā)出的控制消息包含的比特?cái)?shù)，D表示所有到達(dá)目的節(jié)點(diǎn)消息的比特?cái)?shù)。

如圖6所示，相比Watchdog檢測(cè)算法，RSND算法能夠降低歸一化控制開(kāi)銷(xiāo)15%以上，因而具有更高的效率，分析其主要原因在于自私節(jié)點(diǎn)檢測(cè)準(zhǔn)確率提高后，更多數(shù)據(jù)分組被送達(dá)它們的目的節(jié)點(diǎn)，使Request控制消息的數(shù)量在整體上會(huì)趨于減少，因而控制開(kāi)銷(xiāo)有所降低。

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

機(jī)會(huì)網(wǎng)絡(luò)中節(jié)點(diǎn)的自私行為對(duì)網(wǎng)絡(luò)吞吐量、投遞成功率和網(wǎng)絡(luò)開(kāi)銷(xiāo)等性能造成不良影響，本文為解決機(jī)會(huì)網(wǎng)絡(luò)現(xiàn)有典型自私性檢測(cè)算法在節(jié)點(diǎn)收到錯(cuò)幀和脫離通信范圍時(shí)自私檢測(cè)的準(zhǔn)確性降低的問(wèn)題，提出了一種可靠的機(jī)會(huì)網(wǎng)絡(luò)自私節(jié)點(diǎn)檢測(cè)算法并通過(guò)理論分析和仿真驗(yàn)證了其有效性。未來(lái)研究工作將圍繞節(jié)點(diǎn)相遇信息的更深度挖掘展開(kāi)。

[1] 熊永平, 孫利民, 牛建偉, 等. 機(jī)會(huì)網(wǎng)絡(luò)[J]. 軟件學(xué)報(bào), 2009, 20(1): 124-137.

XIONG Y P, SUN L M, NIU J W, et al. Opportunistic networks[J]. Journal of Software, 2009, 20(1): 124-137.

[2] STAVROULAKI V, TSAGKARIS K, LOGOTHETIS M, et al. Opportunistic networks[J]. IEEE Vehicular Technology Magazine, 2011, 6(3): 52-59.

[3] 劉喬壽, 周建二, 張普寧. 機(jī)會(huì)網(wǎng)絡(luò)中基于消息副本數(shù)量的自適應(yīng)緩存管理策略[J]. 重慶郵電大學(xué)學(xué)報(bào)(自然科學(xué)版), 2012,23(4): 394-399. LIU Q S, ZHOU J E, ZHANG P N. Adaptive cache management method for opportunistic network based on number of message copies[J]. Journal of Chongqing University of Posts and Telecommunications (Natural Science Edition), 2012,23(4): 394-399.

[4] RESTA G, SANTI G. A framework for routing performance analysis in delay tolerant networks with application to non-cooperative networks[J]. IEEE Transactions on Parallel and Distributed System, 2011, 23(1): 2-10.

[5] 張程, 劉慧君, 陳自郁, 等. 基于信用的重復(fù)博弈模型在節(jié)點(diǎn)轉(zhuǎn)發(fā)中的應(yīng)用[J]. 解放軍理工大學(xué)學(xué)報(bào), 2012, 13(2): 152-158.

ZHANG C, LIU H J, CHEN Z Y, et al. Credit-based repeated game model applied in transfer decision of opportunistic network[J]. Journal of PLA University of Science and Technology(Natural Science Edition), 2012, 13(2): 152-158.

[6] BIGWOOD G, HENDERSON T. IRONMAN: Using social networks to add incentives and reputation to opportunistic networks[C]//2011 IEEE International Conference on Privacy, Security, Risk and Trust, and IEEE International Conference on Social Computing. IEEE, c2011: 65-72.

[7] MICHIARDI P, MOLVA R. Core: a collaborative reputation mechanism to enforce node cooperation in mobile ad hoc networks[C]//IFIPTC6/TC11 Sixth Joint Working Conference on Communications and Multimedia Security: Advanced Communications and Multimedia Security. Portoroz, Slovenia, c2002: 107-121.

[8] BUCHEGGER S, BOUDEC J L. Performance analysis of the confidant protocol[C]//ACM International Symposium on Mobile Ad Hoc Networking Computing. Lausanne, Switzerland, c2002: 226-236.

[9] MARTI S, GIULI T J, LAI K, et al. Mitigating routing misbehavior in mobile ad hoc networks[C]//International Conference on Mobile Computing and Networking. Boston, USA, c2000: 255-265.

[10] 唐作用, 袁藝嘉, 董永強(qiáng), 等. 基于信譽(yù)值維護(hù)的機(jī)會(huì)網(wǎng)絡(luò)自私節(jié)點(diǎn)檢測(cè)機(jī)制[J]. 通信學(xué)報(bào), 2012,33 (z2): 217-221.

TANG Z Y, YUAN Y J, DONG Y Q, et al. Detection of selfish nodes based on credit mechanism in opportunistic networks[J]. Journal on Communications, 2012, 33(z2): 217-221.

[11] 曲大鵬, 王興偉, 黃敏. 移動(dòng)對(duì)等網(wǎng)絡(luò)中自私節(jié)點(diǎn)的檢測(cè)和激勵(lì)機(jī)制[J]. 軟件學(xué)報(bào), 2013, 24(4): 887-899.

QU D P, WANG X W, HUANG M. Selifish node detection and incentive mechanism in mobile P2P networks[J]. Journal of Software, 2013, 24(4): 887-899.

[12] 王立, 吳蒙, 常莉. 移動(dòng)ad hoc網(wǎng)絡(luò)基于信譽(yù)系統(tǒng)的節(jié)點(diǎn)協(xié)作方案[J].計(jì)算機(jī)技術(shù)與發(fā)展, 2010, 20(3): 32-35.

WANG L, WU M, CHANG L. A scheme to node cooperation based on reputation system in mobile ad hoc networks[J]. Computer Technology and Development, 2010, 20(3): 32-35.

[13] VIANI F, LIZZI L, ROCCA P, et al. Object tracking through RSSI measurements in wireless senor networks [J]. Electronics Letters, 2008, 44(10): 653-654.

[14] BECKER V D. Epidemic routing for partially connected ad hoc networks[R]. USA: Duke University, CS-2000-06, 2000.

[15] 趙廣松, 陳鳴. 自私性機(jī)會(huì)網(wǎng)絡(luò)中激勵(lì)感知的內(nèi)容分發(fā)的研究[J]. 通信學(xué)報(bào), 2013, 34(2): 73-84.

ZHAO G S, CHEN M. Research of incentive-aware data dissemination in selfish opportunistic networks[J]. Journal on Communications, 2013, 34(2): 73-84.

[16] 任智, 黃勇, 曹建玲, 等. 基于鄰居信息交換的機(jī)會(huì)網(wǎng)絡(luò)低時(shí)延路由算法[J]. 華中科技大學(xué)學(xué)報(bào)(自然科學(xué)版), 2011, 39(2): 94-97.

REN Z, HUANG Y, CAO J L, et al. Low-delay routing algorithm for opportunistic networks by exchanging the neighborhood information[J]. Journal of Huangzhong University of Science and Technology (Natural Science Edition), 2011, 39(2):94-97.

[17] 王汝言, 金勇, 吳大鵬, 等. 面向機(jī)會(huì)網(wǎng)絡(luò)的自適應(yīng)冗余副本刪除機(jī)制[J]. 重慶郵電大學(xué)報(bào)學(xué)報(bào)(自然科學(xué)版), 2013, 25(1): 59-63,74. WNAG R Y, JIN Y, WU D P, et al. Adaptive redundant message deletion mechanism for opportunistic networks[J]. Journal of Chongqing University of Posts and Telecommunications (Natural Science Edition), 2013, 25(1): 59-63,74.

Reliable selfish node detection algorithm for opportunistic networks

REN Zhi, TAN Yong-yin, LI Ji-bi, CHEN Qian-bin

(Chongqing Key Laboratory of Mobile Communication Technology, Chongqing University of Posts and Telecommunications, Chongqing 400065, China)

To address the problem of detection accuracy affected by situations like the omission of node receiving wrong frame and failure of monitoring beyond nodes’ communication range during the consideration of the existing selfish node detection algorithms in opportunistic networks, a novel and reliable selfish node detection algorithm——RSND algorithm for opportunistic networks was proposed. It employs wrong frame analysis based on cross-layer monitoring mechanism, information excavation based on node encounter and node distance estimation based on RSSI three new mechanisms to eliminate the influence of node’s selfishness detection due to wrong frame and failure of monitoring beyond nodes’ communication range, improving the reliability of detection. Theoretical analysis verifies the effectiveness of RSND, and simulation results show that RSND can improve selfish node detection accuracy ratio and network throughput at least 6% and 4%, as compared to the existing selfish node detection algorithm based on 2-ACK and watchdog detection algorithm.

opportunistic networks, selfish node, detection algorithm, monitor, misjudgment

TP393.04

A

10.11959/j.issn.1000-436x.2016047

2015-06-19；

2015-11-16

譚永銀，tyy0805@126.com

國(guó)家自然科學(xué)基金資助項(xiàng)目（No.61379159）；長(zhǎng)江學(xué)者和創(chuàng)新團(tuán)隊(duì)發(fā)展計(jì)劃基金資助項(xiàng)目（No.IRT1299）；重慶市自然科學(xué)基金資助項(xiàng)目（No.cstc2012jjA40051）；重慶市教委基金資助項(xiàng)目（No.Kizh11206）

The National Natural Science Foundation of China (No.61379159), The Program for Changjiang Schnolars and Innovative Research Team in University (No.IRT1299), The Natural Science Foundation of Chongqing (No.cstc2012jjA40051), The Special Fund of Chongqing Municipal Education Commission (No.Kizh11206)

任智（1971-），男，四川內(nèi)江人，重慶郵電大學(xué)教授，主要研究方向?yàn)閷拵o(wú)線通信網(wǎng)絡(luò)理論與技術(shù)。

譚永銀（1989-），男，湖南常寧人，重慶郵電大學(xué)碩士生，主要研究方向?yàn)闄C(jī)會(huì)網(wǎng)絡(luò)路由算法。

李季碧（1975-），女，四川開(kāi)江人，重慶郵電大學(xué)講師，主要研究方向?yàn)闊o(wú)線通信網(wǎng)絡(luò)。

陳前斌（1967-），男，四川南充人，重慶郵電大學(xué)教授、博士生導(dǎo)師，主要研究方向?yàn)闊o(wú)線通信與網(wǎng)絡(luò)。