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

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

?

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

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

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

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

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

1 引言

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

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

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

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

2.1 假設(shè)

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

2.2 問題描述

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

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

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

3 RSND算法

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

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

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

3.1.1 錯幀解析

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

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

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

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

3.1.3 脫離判斷

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

3.2 算法操作

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

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

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

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

step4 節(jié)點收到來自節(jié)點的ACK時，記錄收到ACK的時間0，并采用RSSI機(jī)制測量節(jié)點、間的間距0。

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

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

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

3.3 性能分析

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

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

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

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

(3)

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

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

(5)

將式(5)化簡可得

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

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

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

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

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

RSND算法中消息完成傳輸需要的總的控制開銷為

(8)

4 仿真分析

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

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

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

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

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

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

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

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

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

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

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

4.2.3 投遞成功率

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

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

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

4.2.4 平均端到端時延

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

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

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

4.2.5 歸一化控制開銷

歸一化控制開銷是累加所有節(jié)點發(fā)出的控制消息的比特數(shù)與到達(dá)目的節(jié)點消息的比特數(shù)的比值，計算公式為

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

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

5 結(jié)束語

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

[1] 熊永平, 孫利民, 牛建偉, 等. 機(jī)會網(wǎng)絡(luò)[J]. 軟件學(xué)報, 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ī)會網(wǎng)絡(luò)中基于消息副本數(shù)量的自適應(yīng)緩存管理策略[J]. 重慶郵電大學(xué)學(xué)報(自然科學(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é)點轉(zhuǎn)發(fā)中的應(yīng)用[J]. 解放軍理工大學(xué)學(xué)報, 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), 等. 基于信譽值維護(hù)的機(jī)會網(wǎng)絡(luò)自私節(jié)點檢測機(jī)制[J]. 通信學(xué)報, 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] 曲大鵬, 王興偉, 黃敏. 移動對等網(wǎng)絡(luò)中自私節(jié)點的檢測和激勵機(jī)制[J]. 軟件學(xué)報, 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] 王立, 吳蒙, 常莉. 移動ad hoc網(wǎng)絡(luò)基于信譽系統(tǒng)的節(jié)點協(xié)作方案[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ī)會網(wǎng)絡(luò)中激勵感知的內(nèi)容分發(fā)的研究[J]. 通信學(xué)報, 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ī)會網(wǎng)絡(luò)低時延路由算法[J]. 華中科技大學(xué)學(xué)報(自然科學(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ī)會網(wǎng)絡(luò)的自適應(yīng)冗余副本刪除機(jī)制[J]. 重慶郵電大學(xué)報學(xué)報(自然科學(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

國家自然科學(xué)基金資助項目（No.61379159）；長江學(xué)者和創(chuàng)新團(tuán)隊發(fā)展計劃基金資助項目（No.IRT1299）；重慶市自然科學(xué)基金資助項目（No.cstc2012jjA40051）；重慶市教委基金資助項目（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é)教授，主要研究方向為寬帶無線通信網(wǎng)絡(luò)理論與技術(shù)。

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

李季碧（1975-），女，四川開江人，重慶郵電大學(xué)講師，主要研究方向為無線通信網(wǎng)絡(luò)。

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