結合概率路由的機會網絡自私節點檢測算法

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

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

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

E-mail：2849819270@qq.com

1 引 言

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

2 相關工作

目前，國內外有很多關于自私節點檢測算法的文獻.

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

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

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

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

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

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

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

3 假設與問題描述

3.1 假設

假設1.網絡節點分為自私節點和非自私節點，自私節點不參與網絡中消息的轉發，即表現出不請求其它節點的數據消息或者請求了數據消息之后也是直接刪除，同時它只發送本節點產生的消息.

假設2.網絡中節點配置相同，即每個節點的通信范圍以及數據處理能力相同.

假設3.網絡中節點采用概率路由的轉發方式，即只有相遇節點與目的節點的相遇概率更高時才會對消息進行轉發.

3.2 問題描述

問題1.現有的2-ACK機制的自私性判定是在數據信息交互結束之后進行的，若此時判定相遇節點為自私節點，而在此之前將數據消息轉發給相遇節點，會導致數據消息被丟棄，從而導致了無效的網絡開銷.

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

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

4 SNPR算法

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

4.1 交互模型

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

圖1 節點間交互模型

圖2 SV列表

圖3 DP列表

4.2 SNPR算法包含的新機制

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

4.2.1 基于控制消息判定節點自私性

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

當與對方節點交互SV、DP列表以后，若未判定對方節點為自私節點，則向對方請求自身所沒有并且與目的節點相遇概率高于對方節點的消息，并將對方所請求的消息發送給對方.此過程存在以下檢測判定：

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

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

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

4.2.2 借助相遇節點信息判定節點自私性

當前節點(稱之為“節點A”，下同)與對方節點(稱之為“節點B”，下同)完成數據消息交互之后，節點A繼續監聽節點B的消息轉發行為.

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

圖4 機制1流程圖

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

圖5 記錄信息列表

Fig.5 Record information list

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

圖6 信息列表

Fig.6 Information list

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

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

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

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

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

一旦判斷出節點的類型，則刪除對應節點在信息列表中的記錄.

4.2.3 基于概率值捎帶節點自私信息

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

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

S1：機會網絡中的節點通過周期性的廣播Hello消息與其它節點進行鄰居發現，節點雙方發現彼此互為鄰居后，交互SV-DP列表消息；

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

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

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

4.3 算法操作

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

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

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

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

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

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

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

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

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

5 仿真驗證

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

5.1 仿真參數

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

表1 仿真參數設置

Table 1 Simulation parameter settings

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

5.2 仿真結果及分析

5.2.1 自私節點檢測準確率

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

圖7 自私節點檢測準確率

5.2.2 消息到達率

消息到達率是指所有目的節點接收到的數據總量R與所有源節點產生的數據總數S的比值，計算公式為：

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

(1)

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

圖8 消息到達率

5.2.3 吞吐量

吞吐量表示網絡傳輸數據消息的能力，它是指單位時間內網絡中成功傳輸數據消息的比特數，計算公式為：

Throughput=P/(Tend-Tstart)

(2)

其中P表示的是網絡中數據消息成功到達目的節點的總比特數,Tstart表示網絡仿真開始時間,Tend表示網絡仿真結束時間.

圖9 網絡吞吐量

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

5.2.4 平均時延

平均時延表示數據消息成功傳輸到目的節點所需要的平均時間，其計算公式是：

(3)

其中，D表示數據消息到達目的節點的個數,Ti表示第i個消息到達目的節點的時延.

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

圖10 網絡平均時延

6 結束語

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