機會網絡中轉發機制的研究

龔丁海

(1.廣西師范大學 計算機科學與信息工程學院，廣西 桂林 541004;2.河池學院 數學系，廣西 宜州 546300)

機會網絡中轉發機制的研究

龔丁海1，2

(1.廣西師范大學 計算機科學與信息工程學院，廣西 桂林 541004;2.河池學院 數學系，廣西 宜州 546300)

通過詳細描述路由轉發算法－傳染轉發算法的轉發過程，分析此種算法存在的不足，提出一種基于轉發度量的傳染算法，并對該算法進行簡要評價。

機會網路;轉發機制;傳染轉發

傳統的無線自組織網絡中的路由協議通常隱含以下假設:即網絡大部分時候是連通的，任一節點對之間存在至少一條完整的端到端的路由。機會網絡［1－2］是利用節點移動帶來的相遇機會實現通信的一種新型無線自組織網絡模型，其目的是為了解決頻繁間斷網絡中的數據通訊問題。在機會網絡中，由于節點移動不可預測、稀疏、能量和存儲受限等因素導致網絡拓撲出現割裂，使源和目標節點位于不同的連通域，導致傳統的無線自組網路由通信協議無法有效運行。機會網絡中這種節點間接觸率的不一致性，節點移動的隨機性和網絡信息的匱乏，導致通信必須依靠節點移動和多跳實現。因此，在機會網絡的路由設計中，常采用“存儲—攜帶—轉發”模式。近幾年來，很多學者對機會網絡的轉發機制做了大量的研究工作，并取得了一定的成果，其中，傳染轉發算法(Epidemic Forwarding，EF)［3］是比較經典的路由算法。本文主要對該算法進行評價分析，并針對傳染轉發算法存在的問題，提出一種基于轉發度量的傳染算法(Epidemic Based on Forwarding Metric，EFM)，最后對該算法進行簡單的評價。

1 傳染轉發算法的轉發機制

傳染轉發算法是為了解決部分連通的Ad hoc網絡的路由通信而提出，其設計目的:(1)提高消息的投遞率;(2)減少消息的傳輸延遲;(3)減少消息傳遞的總資源消耗［3］。為完成以上的設計目的，傳染轉發算法試圖通過洪泛將消息轉發給所有鄰居節點，直到消息過期或最終到達目的節點。圖1為消息源節點到目的節點的消息路由示意圖。(a)圖表示是在t1時刻，源節點S試圖將消息m發送給目的節點D，但不存在連接的路徑，S將消息m轉發給在其直接傳輸范圍內的鄰居節點N1和N2;(b)圖表示在某時刻t2＞t1，節點N2移動到節點N4的直接通信范圍內，將消息m轉發給節點N4，N4再將消息轉發給在其通信范圍內的目的節點D。

圖1 源節點到目的節點傳遞消息示意圖

傳染轉發算法的工作原理具體描述如下:網絡中每個節點都有一個存儲消息的緩存，每個消息有一個網絡中唯一的標識ID，節點以該標識為索引建立一個哈希索引表。同時節點維持一個向量表SV(Summary Vector)，用于記錄節點緩存中存儲的消息。當節點i和節點j相遇時，其轉發步驟如下:

Step1:節點i向節點j發送向量表SVi;

Step2:節點j收到i發送的SVi后，與SVj相比較，找出在SVi中有，而在SVj中沒有的項，構成另一個向量SV1，向量SV1記錄節點i緩存中有而節點j沒有的消息，并將SV1發送給節點i;

Step3:節點i收到SV1后，將向量SVi中標識的消息逐條發送;

Step4:節點j收到i發送的消息，更新SVj

通過以上四個步驟完成了節點i向j的消息傳送，圖2為傳染轉發算法中消息轉發的工作原理。同樣，節點j也通過以上步驟向節點i完成消息的傳送。當操作完成后，兩個節點的緩存里有同樣的消息。當碰到其他鄰居節點時，繼續重復以上步驟，直到消息過期(TTL過期或超出最大傳遞跳數)或消息到達目的節點。

圖2 消息轉發原理

2 傳染轉發算法的性能

傳染轉發算法的主要思想是“存儲—攜帶—轉發”，以洪泛的方式將消息轉發給相遇的節點，以期望能有更多的節點參與消息的轉發，最終以較高的成功傳達率到達目的節點。在傳染轉發算法中，實際上隱含有一個條件，即越多的節點參與消息的轉發，消息成功到達目的節點的可能性就越大。但以上隱含的條件忽略了一個事實，即并不是所有的節點，都是“好”的消息轉發者，如源節點S，將消息轉發給相遇節點A，但是節點A卻很少與其他節點相遇，很少有機會將來自源節點的消息成功轉發。這種情況下，源節點S到節點A的消息轉發造成了網絡帶寬的浪費，消息副本的產生也提高了消息轉發的成本。節點無限制的轉發消息，使網絡中存在大量的無用的消息副本，易造成網絡擁塞。另外一種情況是，當節點的緩存空間有限時，由于消息的洪泛，易造成節點緩沖的溢出，節點就會選擇將存儲時間較長的消息刪除。因此，在傳染轉發算法中，高傳達率的條件是要求網絡中的網絡帶寬和緩存等網絡資源充足。而在機會網絡中，實際網絡節點帶寬和緩存等資源是受限的，因此隨著網絡節點數的增大，其性能由于廣播導致的擁塞會急劇下降［2］。

3 基于轉發度量的傳染算法

從上面分析可知，傳染轉發算法實際上是一種洪泛算法，存在一定的缺陷，當網絡資源受限時，會由于無限制的洪泛，造成網絡擁塞，大大影響該算法的性能。改善該算法性能的一個方法就是通過某種方法限制洪泛，減少消息轉發過程中消息副本的數量。此外，網絡中一個活躍的節點會經常與網絡中其他節點相遇，也會不時地與目的節點相遇。因此，可根據這一特征設置一個轉發度量，作為轉發消息的依據，消息持有者只將消息轉發給轉發度量值比自己高的節點，限制網絡中的洪泛。

3.1 基于轉發度量的傳染算法轉發度量的估算

基于轉發度量的傳染算法在估算轉發度量時，同時考慮節點與其他節點的接觸率和與消息的目的節點最后相遇時間。設定時間窗口T，轉發度量x定義如下:

其中α是權重常量(α∈［0，1］)，r為消息持有者與其他節點的接觸率，即單位時間內，與其他節點的接觸次數;t為當前時間減去節點與目的節點最近接觸的時間，時間單位與窗口值T相同。α為零時，轉發度量只考慮與目的節點最后相遇的時間;α為1時，轉發度量只考慮節點與其他節點的接觸率。

由公式(1)可知，當節點與其他節點的接觸次數越多，且距離與目的節點最近相遇的時間越短，其轉發度量越高，則會有更多的消息轉發給該節點;當節點與其他節點長時間沒有接觸時，接觸率降低，則轉發度量值低，消息持有者不會將消息轉發給轉發度量值低于自己的節點。長時間沒有與其他節點或目的節點接觸的節點，其轉發度量隨時間不斷下降，當持有消息時，會在偶爾的與其他節點相遇時，將消息轉發給度量值高的節點。

3.2 基于轉發度量的傳染算法的轉發步驟

初始化:任意節點i和j分配有轉發度量值x，每個節點維持一個向量表SV，SV中含有該緩存區存儲的消息及轉發度量x。

假設節點i攜帶消息，目標節點為d，當節點i與j相遇時，i執行的消息轉發流程如下:

Step1:向j發送目標節點為j的消息，記錄其ID并將消息副本從緩存中刪除。

Step2:與j交換消息向量表SV，挑選出符合xi＜xj的消息，將其ID匯總成一個向量表SV1向j發送。

Step3:節點j接收到SV1后，從SV1中刪除其已經緩存消息對應的ID，并發回i。

Step4:節點i接收到j返回的SV1后，將SV1表中的消息按照xj從大到小排隊，組成消息轉發隊列L。

Step5:若L為空，則轉發結束，退出。否則取隊首消息，將消息轉發給j，并將其從L和緩存中刪除，轉Step5。

3.3 基于轉發度量的傳染算法的評價

基于轉發度量的傳染算法相對于傳染轉發算法，主要改進了消息無限制的洪泛，通過比較節點對某個消息的轉發度量，選擇是否進行消息轉發，從而限制了消息無限制的轉發，控制消息轉發過程中消息副本的數量，減少了轉發成本，即減少了網絡消息副本的數量，避免了網絡中由于消息廣播而引起的網絡擁塞。

4 結束語

機會網絡是最近引起廣泛關注的一種新興無線自組網，由于其網絡特性，傳統無線自組網中的路由轉發算法大多不適用于機會網絡，其轉發機制還有待進一步研究。傳染轉發算法是一種具有代表性的機會轉發機制，本文提出的基于轉發度量的傳染算法改進了傳染轉發算法的性能，較好的解決了傳染轉發算法中存在的問題。

［1］Hunag C H，Lan K C，Tsai C Z.A survey of opportunistic networks［C］//Proceeding of the22nd International Conference on Advanced Information Networking and Applications.Ginowan:IEEE Press，2008:1 672 － 1 677.

［2］熊永平，孫利民，牛建偉，等.機會網絡［J］.軟件學報，2009，20(1):124 －137.

［3］Vahdat A，Becker D.Epidemic routing for partially connected ad hoc networks，CS－2000－06［R］.Durham Nc:Department of Computer Science，Duke University，2000.

Research on Forwarding Mechanism in Opportunistic Networks

GONG Ding-hai1，2
(1.School of Computer Science and Information Engineering，Guangxi Normal University，Guilin，Guangxi 541004;2.Department of Mathematics，Hechi University，Yizhou，Guangxi 546300，China)

This paper describes the forwarding process of a routing forwarding algorithm，epidemic forwarding algorithm in detail and analyzes its deficiency.Then it proposes a new epidemic algorithm that is based on forwarding metric，and briefly evaluates this algorithm.

opportunistic network;forwarding mechanism;epidemic forwarding

TP393.0

A

1672－9021(2011)02－0049－03

龔丁海(1979－)，男，湖南郴州人，河池學院數學系講師，主要研究方向:計算機軟件與理論。

2011－03－10

［責任編輯 劉景平］