龔丁海

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

機會網(wǎng)絡(luò)中轉(zhuǎn)發(fā)機制的研究

龔丁海1，2

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

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

機會網(wǎng)路;轉(zhuǎn)發(fā)機制;傳染轉(zhuǎn)發(fā)

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

1 傳染轉(zhuǎn)發(fā)算法的轉(zhuǎn)發(fā)機制

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

圖1 源節(jié)點到目的節(jié)點傳遞消息示意圖

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

Step1:節(jié)點i向節(jié)點j發(fā)送向量表SVi;

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

Step3:節(jié)點i收到SV1后，將向量SVi中標(biāo)識的消息逐條發(fā)送;

Step4:節(jié)點j收到i發(fā)送的消息，更新SVj

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

圖2 消息轉(zhuǎn)發(fā)原理

2 傳染轉(zhuǎn)發(fā)算法的性能

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

3 基于轉(zhuǎn)發(fā)度量的傳染算法

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

3.1 基于轉(zhuǎn)發(fā)度量的傳染算法轉(zhuǎn)發(fā)度量的估算

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

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

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

3.2 基于轉(zhuǎn)發(fā)度量的傳染算法的轉(zhuǎn)發(fā)步驟

初始化:任意節(jié)點i和j分配有轉(zhuǎn)發(fā)度量值x，每個節(jié)點維持一個向量表SV，SV中含有該緩存區(qū)存儲的消息及轉(zhuǎn)發(fā)度量x。

假設(shè)節(jié)點i攜帶消息，目標(biāo)節(jié)點為d，當(dāng)節(jié)點i與j相遇時，i執(zhí)行的消息轉(zhuǎn)發(fā)流程如下:

Step1:向j發(fā)送目標(biāo)節(jié)點為j的消息，記錄其ID并將消息副本從緩存中刪除。

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

Step3:節(jié)點j接收到SV1后，從SV1中刪除其已經(jīng)緩存消息對應(yīng)的ID，并發(fā)回i。

Step4:節(jié)點i接收到j(luò)返回的SV1后，將SV1表中的消息按照xj從大到小排隊，組成消息轉(zhuǎn)發(fā)隊列L。

Step5:若L為空，則轉(zhuǎn)發(fā)結(jié)束，退出。否則取隊首消息，將消息轉(zhuǎn)發(fā)給j，并將其從L和緩存中刪除，轉(zhuǎn)Step5。

3.3 基于轉(zhuǎn)發(fā)度量的傳染算法的評價

基于轉(zhuǎn)發(fā)度量的傳染算法相對于傳染轉(zhuǎn)發(fā)算法，主要改進(jìn)了消息無限制的洪泛，通過比較節(jié)點對某個消息的轉(zhuǎn)發(fā)度量，選擇是否進(jìn)行消息轉(zhuǎn)發(fā)，從而限制了消息無限制的轉(zhuǎn)發(fā)，控制消息轉(zhuǎn)發(fā)過程中消息副本的數(shù)量，減少了轉(zhuǎn)發(fā)成本，即減少了網(wǎng)絡(luò)消息副本的數(shù)量，避免了網(wǎng)絡(luò)中由于消息廣播而引起的網(wǎng)絡(luò)擁塞。

4 結(jié)束語

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

［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］熊永平，孫利民，牛建偉，等.機會網(wǎng)絡(luò)［J］.軟件學(xué)報，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－)，男，湖南郴州人，河池學(xué)院數(shù)學(xué)系講師，主要研究方向:計算機軟件與理論。

2011－03－10

［責(zé)任編輯 劉景平］