機會網絡中計算節點間相似度的路由算法

林玉成,陳志剛,吳 嘉

1(中南大學 軟件學院,長沙 410075) 2(“移動醫療”教育部-中國移動聯合實驗室,長沙 410083) E-mail:yucheng@csu.edu.cn

1 引 言

機會網絡(Opportunistic Network，OPN)最初起源容忍延遲網絡(Delay Tolerant Network，DTN)和移動自組網(Mobile Ad-Hoc Network，MANET)[1].機會網絡中的節點不是統一部署的，無法事先確定源節點到目的節點是否存在可以通信的鏈路[2].它是利用節點的移動性帶來的機會，采用"存儲-攜帶-轉發"的路由機制來完成網絡的通信[3].由于應用特點、環境、成本等多種因素的限制，在很多應用領域中無法建立傳統的全連通網絡，而機會網絡由于其固有的特點能夠滿足某些特定的應用需求.機會網絡的典型應用主要有：野外數據收集[4]、以人為搭載節點的手持設備組網[5]、車載網[6]、落后地區的網絡通信[7]等.

機會網絡的建立相對比較靈活、快捷，但是由于節點的移動導致拓撲結構的不穩定性，使得傳統的路由算法難以適應到機會網絡中。所以，合理地選擇中繼節點，使信息能夠在較短的延遲內交付到目的節點成為了機會網絡研究中的關鍵問題之一.目前針對機會網絡中的路由問題，已經提出了一些解決辦法，主要有先驗知識和基于移動模型的預測路由等。但由于無線連接的間歇性和節點自身移動帶來的不可靠因素，依然存在節點選擇不合理，傳輸成功率不高和傳遞目的性不強的問題[8]，使得路由性能沒有太大的突破.

在實際的應用環境中， 機會網絡中的節點往往是具有一定社會屬性的， 其進行信息的交互行為與移動模式都具有社會性.相對于節點的頻繁移動以及網絡拓撲結構不斷變化， 人類的社會性以及社會關系是相對穩定的，更加地適用于機會網絡動態變化的要求.通過對上述問題的分析， 從機會網絡與節點的社會屬性相結合的角度， 本文提出了一種基于節點相似度的路由算法(ONNS)(Opportunistic Network Routing Algorithm Based on Node Similarity)，其中節點所攜帶的數據分組就是衡量節點間相似度的關鍵.首先計算節點間數據分組的編輯距離，然后根據得到的編輯距離計算節點間的相似度，當兩個節點間相似度較高時，說明該兩個節點在網絡中有著相對比較密切的社會關系.通過對節點間的相似度進行一定條件地篩選，得到一條或多條有效性較大的且比較可靠的路徑，從而有更多的機會將數據轉發給目的節點，完成信息傳輸.

2 相關工作

在機會網絡中,采用“存儲—攜帶—轉發”的路由機制進行數據的傳輸[9].如何合理地選擇鄰居節點,高效地進行數據轉發是現今機會網絡研究的一個重要方向[10].目前,對于機會網絡路由算法的研究,主要有以下一些方法.

Epidemic算法[11]的核心思想就是網絡中的每個節點都維持一個數據分組,當節點相遇時,首先交換彼此的數據分組.通過數據分組確認對方緩存中缺少的數據,雙方再交換彼此缺少的數據.其主要的優就是可以極大地增加數據傳遞的成功率,降低傳輸延遲,主要缺點是網絡中會產生非常多的數據分組副本,會占用大量的網絡資源,造成不必要的浪費[12].

文獻[13]中提出了Spary and Wait算法,Spary and Wait算法分為兩個階段,Spray階段和Wait階段.在Spray階段,源節點將其緩存中的每個數據分組向網絡中轉發一定數量的數據分組副本,若這一階段沒有發現目的節點,則進入Wait階段,那么攜帶該數據分組副本的節點利用復制轉發策略把數據傳輸到目的節點.該策略有效的控制了網絡中數據分組的副本數量,降低了路由開銷,能夠較好地適應網絡負載的變化.

文獻[14]中提出了基于概率策略的PRoPHET算法,該算法定義了一個預測值來描述節點間信息傳輸成功的概率.當兩個節點相遇時,節點更新各自的預測值,并根據該值來判斷是否進行數據傳輸.在社區模型場景中,PRoPHET算法的性能要好于Epidemic算法[15].

文獻[16]深入了解了社區形成的本質,并利用節點間的社會屬性進行機會網絡中的數據轉發.利用真實世界的節點移動記錄,首先推導出每個節點的鄰接列表,并形成節點間的接觸圖.從社交網絡的角度分析節點的不同屬性,如中心度、聚類系數以及平均路徑長度等,提出了兩個以社會為基礎的路由,分別是基于接觸的轉發策略和基于社區意識的兩跳路由策略.

本文從機會網絡與社交網絡相結合的角度去分析節點轉發數據的特點,根據節點間數據分組的編輯距離計算節點間社會關系的強弱,提出了基于節點相似度的轉發策略.

3 基于節點相似度的轉發策略

3.1 機會網絡拓撲結構

根據機會網絡中節點的移動性,整個網絡并不是全連通網絡,網絡的拓撲結構也是隨機變化的,因此在網絡中隨機選取某一個子網絡作為研究對象.假設該子網絡包含的節點集合為V={S,A,D,F,G,H,I,L,K,E,J},共11個節點,所有節點都為中繼節點,皆可以進行消息的攜帶與轉發,子網絡的拓撲結構如圖1所示.

圖1 子網絡拓撲結構Fig.1 Topology structure of sub-network

在當前時段,假設節點S為源節點需要發送數據,并且數據在節點之間的傳遞速率大于節點的相對移動速率,即信息在當前時段在子網絡中傳遞時,子網絡的拓撲結構不會發生本質上的變化,不會有節點離開或進來.

在網絡拓撲結構中,每個節點與其鄰居之間都可以進行數據傳遞.此時,需要在鄰居節點中選擇相對比較可靠且有效性較大的節點進行傳遞.在現實場景中,機會網絡中的節點是具有社會性質的,相對于頻繁變化的網絡拓撲結構,節點間的社會關系是相對穩定的并且是可靠的,能更好地適應網絡動態變化.本文通過節點間社會相似度在該子網絡拓撲結構中選擇代理節點進行信息傳輸,而節點間的相似度則是通過節點間數據分組的編輯距離計算得到的.

3.2 數據分組之間的編輯距離和節點間的相似度

定義1.編輯距離DIS,是指由一個字符串轉換為另一個字符串所需要的最少編輯操作次數,許可的操作包括替換、插入以及刪除.假設長度為x的字符串a和長度為y的字符串b,則字符串a和字符串b的編輯距離計算如下.

初始化:創建一個x+1行和y+1列的矩陣,Matrix,其中第一行寫入0-x,第一列寫入0-y.

賦 值:為矩陣的每一個元素分配一個值,Matrixi,j(1≤i≤x+1;1≤j≤y+1).如果a的第i個字符與b的第j個字符相等,則設置一個開銷值cost為0,否則令cost為1.比較Matrixi,j-1,Matrixi-1,j,Matrixi,j,三者值的大小,取其最小值為min.如果min為Matrixi,j-1或Matrixi-1,j,則Matrixi,j=min+1,否則Matrixi,j=min+cost.

用DISab表示節點a和節點b數據分組之間的編輯距離.

定義2.相似度SIM,節點間數據分組的相似度等同于節點間的相似度,節點所攜帶的數據分組就是衡量其社會性的指標.當兩個節點間的相似度越高,則說明這兩個節點在社會中聯系越緊密.用SIMab表示節點a和節點b之間的相似度,其計算公式為:

SIMab=1-DISab/maxLen(a,b)

(1)

其中maxLen(a,b)表示節點a和節點b消息隊列的最大長度.

定義3.下閾值r,當一個節點與其鄰居節點的相似度大于下閾值時,則將該鄰居作為下一跳的候選項之一.如果一個節點與所有的鄰居節點的相似度都小于下閾值,則選擇相似度最大的節點進行信息傳輸.當節點遍歷完所有鄰居節點時,就可能得到多條路徑,有效地提高了傳輸成功率.

定義4.上閾值R,上閾值的作用是用來控制下一跳節點的個數,避免在網絡中出現過多的數據副本.如果一個節點存在多個可候選鄰居節點時,則需要計算候選節點之間的相似度,如果兩個候選節點之間的相似度大于上閾值時,則丟掉其中與當前節點相似度較小的一方,保留較大的一方.通過定義上閾值,可以有效地控制網絡的路由開銷.

定義5.訪問控制數N，定義一個常量N，用來控制節點訪問鄰居節點的個數.當一個節點要訪問的鄰居節點的個數大于N時，則根據當前節點與所有鄰居節點的傳輸距離進行排序，優先選擇前N個傳輸距離比較近的鄰居節點進行訪問，對于第N個之后的鄰居節點則不再進行訪問.通過定義訪問控制數N，可以有效地控制ONNS算法的計算復雜度，避免了隨著網絡中節點數量的增加節點之間對比的次數會顯著增多的情況.

3.3 節點信息遍歷過程

網絡中的所有節點都維持一個緩沖區,將節點需要轉發的數據分組存放在緩沖區中.假設節點集合V中每個節點的數據分組如表1所示.

表1 節點數據分組Table 1 Data packet of nodes

基于圖1的節點遍歷過程如下:

1)初始化一個樹Tree,把當前要發送信息的節點S插入樹中作為根節點,創建節點S的鄰居節點集合US={A,D,F,G},并按照傳輸距離由近至遠的順序將節點集合US中的鄰居節點進行排序，采用廣度優先搜索依次遍歷US中節點S的前N個鄰居節點,如圖2所示.

2)開始訪問當前節點S的鄰居節點A,計算節點S和節點A數據分組間的編輯距離與相似度.

DISSA=4

SIMSA=1-DISSA/maxLen(S,A)=0.2

(2)

由于當前節點S沒有子節點,則將節點A插入到樹Tree中作為節點S的子節點.

3)繼續訪問下一個鄰居節點D,計算節點S和節點D數據分組間的編輯距離以及相似度.

DISSD=3

SIMSD=1-DISSD/maxLen(S,D)=0.4

(3)

由于SIMSD>SIMSA,假設此時SIMSA小于下閾值r,那么把節點A從樹Tree中刪除并將節點D插入樹中作為根節點S的子節點.

4)繼續訪問下一個鄰居節點F,計算節點S和節點F數據分組間的編輯距離以及相似度.

DISSF=4

SIMSF=1-DISSF/maxLen(S,F)=0.33

(4)

假設此時SIMSF>r,且當前節點S中還存在子節點D,SIMSD>r.此時,鄰居節點D和F都作為當前節點S下一跳的候選項,則需要計算節點D和節點F數據分組的編輯距離以及相似度.

DISDF=3

SIMDF=1-DISDF/maxLen(D,F)=0.4

(5)

假設此時SIMDF

5)繼續訪問下一個鄰居節點G,計算節點S和節點G數據分組間的編輯距離以及相似度.

DISSG=2

SIMSG=1-DISSG/maxLen(S,G)=0.6

(6)

假設此時SIMSG>r,且當前節點S中還存在子節點D和子節點F,則首先計算節點D和節點G數據分組的編輯距離以及相似度.

DISDG=2

SIMDG=1-DISDG/maxLen(D,G)=0.5

(7)

假設此時SIMDG

DISFG=1

SIMFG=1-DISFG/maxLen(F,G)=0.8

(8)

假設此時SIMFG>R,則將節點F和節點G中與當前節點S相似度較小的一方丟棄,保留較大的一方.由于SIMSF

圖2 節點遍歷圖Fig.2 Traversal process of node

6)此時,當前節點S的所有鄰居節點已經遍歷結束.根據(5)得到的樹Tree,選取根節點S的一個子節點D為當前節點,創建D節點的鄰居節點集合UD={A,B,D,J,K,L},并作UD=UD-US,得到UD={H,I,L}.并按照傳輸距離由近至遠的順序將節點集合UD中的鄰居節點進行排序，優先訪問前N個鄰居節點。并按照傳輸距離由近至遠的順序將節點集合UD中的鄰居節點進行排序，優先訪問前N個鄰居節點.按照上述過程依次訪問節點D的鄰居H、I、L,如圖2所示.當訪問完節點D的所有鄰居時,得到下一跳節點I,將I插入樹Tree中作為D的子節點.

7)根據5)得到的樹Tree,選擇節點S的另一個子節點G作為當前節點,創建G節點的鄰居節點集合UG={A,D,E,G,H,I},并作UG=UG-US,得到UG={K,E,J}.同時按照傳輸距離由近至遠的順序對節點集合UG中的鄰居節點進行排序，優先訪問前N個鄰居節點。按照上述過程依次訪問G節點的鄰居K、E、J,如圖2所示.當訪問完節點G的所有鄰居時,得到下一跳節點E,將E插入樹Tree中作為G的子節點.

訪問完節點G的所有鄰居節點得到樹Tree的結構圖,如圖3所示.

圖3 Tree的結構圖Fig.3 Structure of the Tree

8)至此,圖1所示的子網絡拓撲結構已經遍歷結束,根據樹Tree的結構可以得到最終的傳輸路徑:S→D→I和S→G→E.

當前要發送信息的節點S將要發送的數據在上述得到的兩條路徑上進行傳遞.

3.4 算法設計

根據上一節的節點在子網絡拓撲結構中的遍歷過程推導出該算法執行過程,如下:

1)初始化樹Tree,插入當前要發送信息的節點s作為根節點.

2)創建當前節點s的鄰居節點集合Us.并按照傳輸距離由近至遠的順序將節點集合Us中的鄰居節點進行排序，優先訪問前N個鄰居節點.若是在樹Tree的結構中當前節點s存在父節點p,則創建父節點p的鄰居集合Up,并作Us=Us-Up.

3)根據BFS訪問Us中當前節點s的鄰居節點c,計算節點s和c之間數據分組的編輯距離DISsc,根據得到的編輯距離計算節點s和節點c的相似度SIMsc.

4)如果當前節點s沒有子節點,則把節點c插入樹Tree中作為s的子節點.

5)如果當前節點s只存在一個子節點d,則判斷SIMsc和SIMsd的大小.

如果min(SIMsc,SIMsd)≥r;

則計算節點c與d之間數據分組的編輯距離DIScd,根據得到的編輯距離計算c與d的相似度SIMcd.如果SIMcd≥R,則將c和d中與當前節點s相似度較小的一方丟棄,保留較大的一方作為s的子節點.若是SIMcd

其他情況下,保留相似度較大的一方,并插入樹Tree中作為當前節點的子節點,丟掉相似度較小的一方.

6)如果當前節點s存在兩個以及兩個以上的子節點d1,d2,…,dn,則判斷節點c與s的全部子節點的相似度.

計算節點c與d數據分組的編輯距離DIScd,根據得到的編輯距離計算節點c與d的相似度SIMcd,d∈{d1,d2,…,dn}.

若是對于所有的子節點都有SIMcd

若是存在子節點d,使得SIMcd>R,則將節點c和節點d中與當前節點s相似度較小的節點丟棄,保留較大的節點作為當前節點的子節點.

7)繼續遍歷當前節點s的其他鄰居節點,重復3)、4)、5)、6),直到當前節點的全部鄰居遍歷完畢.

8)選擇當前節點s的所有子節點依次作為當前節點,重復2)、3)、4)、5)、6)、7),直至訪問完子網絡拓撲結構中樹Tree中的所有節點的所有鄰居節點.

9)根據上述過程得到的樹Tree,可以得到一條或多條傳輸路徑,將數據通過復制策略在這些路徑上進行轉發.

按照上述的算法執行流程,可以設計出基于節點相似度的路由算法.算法偽代碼如下.

算法1.Opportunistic Network Routing Algorithm Based on Node Similarity

1.Input:A graphG(V,E),a sourceS,Dz:the correlative information collection ofz(z∈V);

2.Output:A or more paths.

3.Init:InitTree(T)

4.Set:CurrentNode(i,S),T.setRootNode(i),Ui;/*A set of neighbor nodes of nodei*/

5.Sort(Ui):Ui.Delete(N);/*Sorting neighbor nodes inUiaccording to the transmission distance,and delete the neighbor nodes afterN*

6.while(!Empty(Ui))

7.for(Neighborj:Ui)

8.DISij=DIS(i,j);SIMij=1-DISij/maxLen(i,j);

9.Num=T.getChildNodeNum(i);/*get the number of child node of nodei*/

10.Switch(Num)

11.Case 0:T.setChildNode(i,j);/*Set nodejas the child node of nodei*/

12.Case 1:ChildNodek=T.getChildNode(i);

13. if(min(SIMij,SIMik)≥r)

14.DISkj=DIS(k,j);SIMkj=1-DISkj/maxLen(k,j);

15. if(SIMkj≥R)T.setChildNode(i,max(SIMij,SIMik));

16. elseT.setChildNode(i,j)

17. else T.setChildNode(i,max(SIMij,SIMik));

18.Default:for(ChildNodek:T.getChildNode(i))/*Nodeihas multiple child nodes.*/

19.DISkj=DIS(k,j);SIMkj=1-DISkj/maxLen(k,j);

20. if(SIMkj≥R)T.setChildNode(i,max(SIMij,SIMik)),break;

21. elseT.setChildNode(i,j);

22.end for;end for;

23.for(ChildNodek:T.getChildNode(i))

24.CurrentNode(i,k),continue;

25.end for;

26.Nodep=T.getParentNode(i);Up;Ui=Ui-Up;Sort(Ui),Delete(N);

27.end while;

28.getPath(T);/*Gets the transmission paths based on the tree T*/

4 實驗結果與分析

本文使用機會網絡仿真模擬平臺ONE(Opportunistic Networking Environment),將ONNS算法、PRoPHET算法和Epidemic算法在該仿真平臺上進行比較分析.文中選取三個參數對上述的三種路由算法進行分析,分別為信息傳輸的成功率、傳輸延遲以及整個網絡的路由開銷.表2為仿真場景的參數設置,表3為ONNS算法的參數設置.

通過多次仿真實驗表明,當下閾值r=0.3，上閾值R=0.8，且訪問控制數N為5、6或7時，ONNS算法性能綜合最優.

下面是在不同節點數量的情況下ONNS算法、PRoPHET算法以及Epidemic算法的表現.圖4為節點緩存對三種算法的傳輸成功率的影響，圖5、圖6、圖7分別是在節點數量改變的情況下三種算法的傳輸成功率、傳輸延遲和路由開銷的實驗結果.

表2 仿真場景設置Table 2 Simulation parameter setting

由圖4可知，節點緩存對ONNS算法傳輸成功率的影響比其他兩種路由算法更加顯著.當節點緩存小于15M時，隨著節點緩存的不斷增加，ONNS算法的傳輸成功率呈現出大幅度上升的趨勢.當節點緩存達到15M時，ONNS算法的傳輸成功率已經接近80%.之后，ONNS算法的傳輸成功率則是緩慢增長，最終穩定在90%左右.而節點緩存對PRoPHET算法和Epidemic算法的傳輸成功率的影響相對較小.隨著節點緩存的增加，該兩種算法的傳輸成功率都表現出相對穩定地增長趨勢，最終都保持在65%左右.

圖4 節點緩存對傳輸成功率的影響Fig.4 Impact of node buffer size on deliver ratio

表3 算法參數設置Table 3 Algorithm parameter setting

從圖5可以看出，三種路由算法的傳輸成功率與節點數量呈現出正相關關系，且節點數量的變化對三種路由算法的傳輸成功率均有較大的改變.在節點數量偏少時，三種路由算法的傳輸成功率都比較低，且沒有明顯的差別.當節點的數量不斷增多時，三種算法的傳輸成功率均有一定程度的增加.其中PRoPHET算法與Epidemic算法的成功率增長的比較緩慢，在節點數量大于400時，該兩種路由算法的成功率都維持在40%上下，與PRoPHET算法相比較而言，Epidemic算法的傳輸成功率稍微高一些.而ONNS算法的傳輸成功率增加比較顯著，當節點數量到達500時，其成功率可以達到75%上下，根本原因在于ONNS算法構建子網絡拓撲結構，通過計算節點間的相似度選擇出一條或多條比較可靠高效的通信路徑進行信息傳遞，從而有效地提高傳輸成功率.

圖5 傳輸成功率Fig.5 Delivery ratio

圖6 傳輸延遲Fig.6 Delivery delay

圖6為節點數目的變化對三種算法傳輸延遲的影響.由圖6可知,伴隨節點數目的不斷增多,PRoPHET算法和Epidemic算法的傳輸延遲均有一定程度上的增加,當節點數目到達600時,PRoPHET算法和Epidemic算法的傳輸延遲要高于5000.節點數目的變化對ONNS算法的傳輸延遲的影響相對較小,隨著節點數量的不斷增加,ONNS算法的傳輸延遲呈現出緩慢增加的趨勢.當節點數量小于150時,ONNS算法的傳輸延遲要比其他兩個算法稍微高一點,這是因為ONNS算法的復雜度比其他兩種算法都要高,隨著節點數量的不斷的增加,該算法得到的傳輸路徑的數量有所增加并且傳輸路徑的可靠性也有所提高,從而在一定程度減少了該算法復雜度對傳輸延遲的影響.最終,ONNS算法的傳輸延遲維持在3000上下.

節點數量對三種算法路由開銷的影響如圖7所示.初始時,節點數量比較少,各算法的路由開銷都比較低,且相差無幾.隨著節點數目的增多,PRoPHET算法和Epidemic算法的路由開銷出現大幅度增加,其中Epidemic算法的路由開銷增加的程度最大.在節點數量達到600時,Epidemic算法的路由開銷是3500左右,PRoPHET算法的路由開銷是3000左右.這表明了伴隨節點數目的增多,使用該兩種路由算法會使得在網絡中產生大量的消息副本,這些副本數據會占用大量的網絡資源,造成網絡資源的過度浪費,容易導致網絡阻塞,使得網絡難以正常的進行數據轉發.

圖7 路由開銷Fig.7 Overhead

ONNS算法的路由開銷與前兩種算法相比有著相對顯著的優勢,伴隨網絡中節點數目的增多,相似度算法的路由開銷增長緩慢,當節點數量在600左右時,ONNS算法的路由開銷還沒有1500,遠低于前兩種算法.這是因為ONNS算法中通過定義下閾值和上閾值可以有效的將傳輸路徑的數量控制在一定范圍,避免了向一些不必要的節點轉發數據分組,從而不會在網絡中產生太多的數據分組副本.

實驗結果表明,相對于Epidemic算法和PRoPHET算法,ONNS算法能夠有效地降低網絡的路由開銷,節省網絡資源.

5 結束語

針對機會網絡中節點傳遞信息的特點以及節點間存在的社會關系,從社會網絡的角度出發,提出一種基于節點間社會相似度的路由策略,通過節點間數據分組的編輯距離來計算節點間社會相似度的大小,并通過相似度閾值可以有效地控制代理節點的個數,最終得到一條或多條相對比較可靠聯系比較緊密的傳輸路徑.通過與機會網絡中傳統的路由算法對比,仿真實驗表明,ONNS算法能夠有效地提高傳出成功率,并且降低路由開銷,減少網絡資源的占用.ONNS算法的高效性表明了節點間的社會社會屬性對機會網絡中信息傳遞起到了非常關鍵的作用.

在實際場景中,社會網絡中人類的行為模型以及人與人之間的社會關系是極其復雜,消息的傳播還會受到多種因素的影響,如個體的興趣、個體的意愿程度和個體所在的社群等.下一步的工作就是對節點間的多種社會關系、節點的行為模型以及節點所在的群體進行綜合分析,在ONNS算法的基礎上進一步的提高傳輸成功率,并增強該算法在不同現實場景中的適用性.