基于節點屬性的機會網絡節能路由算法

鄭永剛 孫文勝

(杭州電子科技大學通信工程學院 浙江 杭州 310018)

0 引 言

隨著智能移動終端的普及和短距離無線通信技術的飛速發展，機會網絡這種新形式的網絡在過去幾年得到迅速發展。由于這種網絡的間歇性連接，源節點和目的節點之間很少存在端到端的路徑[1]。在延遲容忍網絡和機會網絡中，為了解決節點移動帶來的鏈路間歇性連接問題，基于存儲-攜帶-轉發的數據傳輸模式引起研究者的關注。

由于機會網絡的載體往往為微型嵌入式移動設備，因此節點的資源是有限的。資源有限主要分為兩個方面：一是節點的緩存空間是有限的。雖然目前存儲技術得到迅速發展，移動節點的緩存空間也得到較大的提升，但是如果毫無節制地轉發、復制、攜帶消息，緩存終將會耗盡，對節點自身也會帶來較大的負擔。二是節點攜帶的能量是有限的。由于移動節點一般采用電池來維持其通信所需的能量，再加上節點本身體積的限制，無法儲蓄太多電量。就機會網絡的實際應用場景而言，節點通常會被放在人煙稀少或者條件惡劣甚至危險的環境中，不易于更換電池或者進行能量的補給。如果某些節點的能量或者緩存耗盡，整個網絡的性能會因為這些節點無法轉發消息而迅速下降，最終使得網絡不能保證預期的服務質量[2]。

因此，在機會網絡當中如何以有限的能量完成消息的高效傳輸，達到低時延、高傳遞成功率、低功耗等效果，成為當前研究需要迫切解決的問題之一。

1 相關工作

為了應對機會網絡中節點資源過快耗盡的問題。研究者們提出了許多高效節能的路由算法。通過控制網絡中消息副本數量能夠有效地緩解緩存不足的問題。文獻[3]提出了一種基于節點質量度的Spray and Focus改進路由算法，該算法分為Spray和Focus兩個階段。在Spray階段時算法首先通過一個參數L限制網絡中消息的最大副本數，接著提取節點屬性值，計算每個節點的質量度，并將消息轉發給質量度高的節點，然后進入Focus階段。在這個階段中，攜帶消息副本的節點只有在遇到目的節點時才會進行消息傳輸。整個過程網絡中消息副本的數量是固定的，因此可以緩解節點緩存不足的壓力。

對于節點能量有限的問題，文獻[4]提出了一種基于接觸概率的低時延休眠算法。該算法通過預測節點之間的接觸概率來動態地調整休眠時間，確保節點間在喚醒狀態下有更多接觸機會，在休眠節能的同時不降低網絡的性能。

以攜帶智能無線設備的人類作為節點載體的網絡是機會網絡應用的重要領域之一。而人類的活動一般具有社區性、中心性、相似性等特點，這些特性都會影響節點消息的傳遞成功概率和節點能量的消耗。研究者提出了許多基于節點社會屬性的路由算法。在文獻[5]中，作者提出的Bubble Rap算法充分考慮了節點的社會屬性，引入節點全局中心度和局部中心度兩個特性，決定消息的下一個傳輸節點。該算法使網絡性能得到了較好的提升，但由于在選擇中繼節點時沒有考慮節點剩余能量和可用緩存等自身屬性，頻繁接收或轉發數據包的節點將迅速耗盡能量和緩存空間而“死亡”。這可能導致消息傳輸失敗，進而使得機會網絡的性能迅速下降。

為了解決上述問題，本文提出了一種更為實用的路由算法，稱為EABNA。該算法在選擇中繼節點時，充分考慮了節點本身的社會屬性，及剩余能量和緩存空間的動態變化情況。由于選擇中繼節點時考慮到能量和緩存等因素，該路由算法實現了在降低消息時延和提高消息傳遞成功率的同時延長了節點在網絡中的生命周期。

2 網絡模型和節點屬性

2.1 網絡模型

將機會網絡抽象為對稱加權圖G(V,E)，V是節點集合，V={V1,V2,…，VN},N≥1，N是網絡中的節點數量。E表示邊的集合，E={e12,e13，…，eij,…},i≠j，1≤i,j≤N，而eij表示節點i和j之間的權重。機會網絡結構的模型圖如圖1所示。該模型一共有五個節點，分別是1、2、3、4、5。每對節點之間的連線表示它們之間至少有一次物理接觸，連線上值表示兩個通信節點之間的權重。

圖1 機會網絡結構模型

在機會網絡中，每個節點可以移動，邊的權重eij被定義為節點i與節點j接觸的緊密程度，即到目前為止這兩節點之間的接觸次數在所有節點接觸次數中所占的比重。

2.2 節點屬性

在機會網絡中，哪個節點可以被選為最佳的中繼節點，何時以及如何傳遞消息是需要考慮的問題。為了解決這些問題，可以從網絡節點中提取一些屬性，并設計適當的轉發策略。社會屬性，如社區和中心地位相對穩定的節點，可以作為路由決策設計的基礎[6]；節點本身的屬性，例如能量和緩存空間是時變的，這些也是路由選擇的重要因素。以下是機會網絡中節點的幾個重要屬性的定義，可以根據這些屬性設計路由算法。

2.2.1 社 區

在實際應用中，構成機會網絡的節點通常是一些被人類攜帶的智能移動設備，而由于興趣、工作和一些其他方面的原因，大多數人的活動僅限于某一區域。整個網絡可以被劃分為若干個不同的社區，與社區之間的節點相比，社區內部節點間的連接更為緊密，擁有更高的消息傳遞成功概率以及更低的消息時延。通過分析節點的移動數據并提取其社區屬性，可以設計出更優的路由算法。

2.2.2 節點的中心性

中心性[8]反映了機會網絡中節點的社會狀態。如果一個節點具有較強的中心性，則代表著它有更多的機會遇到其他節點，因此比較適合作為消息轉發的中繼節點。

本文中，使用中心度表示節點與網絡中其他節點的關聯程度。在具有n個節點的無向圖中，一個節點的中心度指的是與該節點有直接接觸的相鄰節點的總數。通過歸一化消除節點之間的差異?？梢缘玫焦濣c的中心性表達式如下：

(1)

式中：xij表示節點i與節點j之間是否存在直接接觸，如果它們之間存在直接接觸，則xij為1，否則為0。

由于節點具有社區屬性，根據節點是否處于社區當中，可以將節點的中心性劃分為針對社區的局部中心和針對整個網絡的全局中心。相應地，當計算節點的全局中心度時，n指整個網絡的節點數量；當計算局部中心度時，n指當前社區的節點數量。

2.2.3 剩余能量

在實際應用環境中，任何節點的能量都是有限的，一旦節點的能量耗盡，將無法繼續工作。因此，設計路由策略時，能量也是一個需要關注的要素。假設節點的初始能量為Einit，能量消耗主要集中在消息轉發或接收、探測掃描周圍節點、響應周圍節點掃描等方面。

假設節點待機狀態下的功耗為Ps，能量更新的周期為Tr；接收或發送一次消息時的能耗都為Et，Tr時間內發送和接收消息的次數為Nt；掃描一次周圍節點的能耗為Es，Tr時間內掃描的次數為Ns；響應一次掃描的能耗為Er，Tr時間內響應掃描的次數為Nr。因此，根據上述條件能夠得出節點的剩余能量。剩余能量可以表示為[9]:

Enew=Eold-Et×Nt-Es×Ns-Ps×Tr

(2)

在初始階段Eold=Einit，當在仿真過程中更新能量時將最后剩余能量值設置為Eold。

2.2.4 剩余緩存空間

在實際環境中，節點的緩存空間也是有限的。節點攜帶或者轉發消息都需要一定的緩存空間，一旦節點的緩存空間耗盡，在接收到新消息時就可能將有用的消息丟棄，導致網絡的性能下降[10]。因此在指定下一跳節點時，需要考慮節點的剩余緩存空間。假設每個節點的初始緩存空間相同并且都為Binit，每個消息的大小為Bp，節點中當前攜帶的消息數量為Cn。因此，可以根據節點中攜帶的消息的數量來計算剩余緩存。節點的剩余緩存可以表示為：

Bres=Binit-Bp×Cn

(3)

仿真過程中在更新節點剩余能量的同時需要更新其剩余緩存空間的值。

3 EABNA算法設計

3.1 消息轉發度量

根據2.2節中定義的節點屬性，將消息的轉發度量如下定義：

Met=lg(aCD+10)lg(bE+10)lg(cB+10)

(4)

式中：CD代表節點的中心度，E代表節點的剩余能量，B代表節點的剩余緩存空間，a、b、c是調諧參數。對數運算是為了消除參數的異方差性。從式(4)可以看出，如a=1、b=0、c=0時，則節點轉發度量Met僅由中心度CD決定，即為Bubble Rap算法的做法。因為隨著存儲技術的發展，剩余緩存相比于節點中心度和剩余能量對整個網絡的性能的影響會稍差一些，因此可以取系數a=2、b=2、c=1。在后續的仿真實驗中可以看出，使用三個系數CD、E和B來決定轉發度量可以獲得更好的網絡性能并達到節能的效果。當CD為局部中心度時，可以通過式(4)計算得到局部轉發度量Met(Lo_Met)；當CD表示節點的全局中心度時，可計算得出全局轉發度量Met(Glo_Met)。其中Met可以表示為二元組(Lo_Met，Glo_Met)。當更新Met時，節點的局部和全局轉發度量值需要同時更新。

3.2 消息轉發策略

本文提出的EABNA算法實際上是對Bubble Rap算法的改進。它采用簡單檢測算法，將網絡劃分成若干個社區，并且每個節點的社區信息會隨著自身的移動實時更新。另外EABNA算法中存在兩張信息表，分別記錄了網絡中所有節點的全局轉發度量排名和局部轉發度量排名。該算法具體的轉發過程可以分為兩個階段：第一階段消息未進入目標節點的本地社區。當攜帶消息的節點在移動過程中遇到其他節點時，如果相遇節點為目標節點則直接進行消息傳遞，本次通信結束，否則判斷相遇節點是否與目標節點同屬一個社區。如果是，則將消息轉發給該節點，進入第二階段，否則查詢節點的全局轉發度量排名表，將消息轉發給第一個排名比自己大的相遇節點，由該節點重復上述流程。第二階段是消息進入目標節點的本地社區之后。在這個階段，根據局部轉發度量進行消息傳輸，節點在移動過程中向局部轉發度量比自身高的節點發送消息，直到遇到目標節點。EABNA算法轉發消息的具體過程如圖2所示。

圖2 EABNA算法示意圖

根據EABNA算法的轉發策略，總結其偽代碼如下：

ifj=Dthen

Forward(m,j);

Update(i,energy,buffer,Met);

Update(j,energy,buffer,Met);

end if

else ifComm(i)≠Comm(D) then

ifComm(j)=Comm(D) orGlo_Met(i)

Forward(m,j);

Update(i,energy,buffer,Met);

Update(j,energy,buffer,Met);

end if

else ifComm(j)=Comm(D) andLo_Met(i)

Forward(m,j);

Update(i,energy,buffer,Met);

Update(j,energy,buffer,Met);

end if

其中：Forward(m,j)表示將消息m轉發給節點j；Comm(j)=Comm(D)表示節點j和節點D在同一個社區當中；Update(i,energy,buffer,Met)表示同時更新節點i的剩余能量、剩余緩存和轉發度量。

4 仿真和結果分析

4.1 仿真環境設置

為了評估EABNA算法的性能，本文采用ONE模擬器搭建仿真平臺[11]，并與其他兩種路由算法進行對比。另外仿真中使用由Haggle Project收集的兩個實驗數據集，稱為Cambridge[12]和Infocom06[12]。在Infocom06中，人們大多數時間處在相對集中的會議廳中，活動范圍較小，節點之間的接觸比較密集。而Cambridge中由于實驗對象大多為學生，他們的活動范圍較大，因此該數據集中節點的接觸時間間隔較長。表1展示了兩個數據集的詳細信息。

表1 兩組實驗數據的特征

由于ONE模擬器對于外部輸入數據的格式有特殊的要求，而從DTN 數據集的提供者CRAWDAD社區[13]下載的Infocom06和Cambridge數據集無法直接使用，需要將其格式化成表2。

表2 ONE數據集標準格式

仿真相關參數設置如下：每個節點的緩存為50 MB，每個消息的大小為500 KB，每個節點的緩存管理模式是FIFO。設定消息的通信速率為250 KB/s，每個消息都有一個對應的TTL，用來表示它在網絡中的存活時長。當TTL變為0時，該消息自動被丟棄，節點屬性的更新周期為300 s。

根據在2.2.1節中對社區以及社區檢測的詳細介紹，仿真過程中社區檢測的相關參數設置如下：熟人個數的閾值α設置為5，即當兩個節點的歷史相遇次數大于5時，將相遇節點加入到對方的熟人集合中。熟人節點加入當前節點本地社區集合的閾值β設置為0.5。將相遇節點的本地社區與當前節點的本地社區合并的閾值γ設置為0.5，即當兩個節點本地社區的交集為并集的一半時，將兩個社區合并成一個本地社區。

網絡中節點工作時能量的消耗情況如表3所示。本文中節點攜帶的能量的初始值設定為100 kJ。

表3 節點能量消耗表

4.2 仿真結果與性能分析

EABNA算法是基于Bubble Rap改進的節能路由算法，它借鑒了Bubble Rap算法的思想，將機會網絡分成多個社區。但在轉發消息的過程當中不僅依靠節點的本地中心度和全局中心度等屬性，而且還考慮了節點的剩余能量以及剩余緩存空間。Epidemic算法是機會網絡中最為典型的一種路由算法，因此將Epidemic和Bubble Rap這兩種算法作為比較的對象來評價EABNA的性能。本文主要通過消息的傳遞成功概率、消息平均傳輸時延、節點存活率、路由開銷這四個指標來體現EABNA算法的優劣[14]。

(1) 消息傳遞成功率 圖3描繪了消息傳遞成功概率隨著消息存活時間(TTL)的變化情況。從整體上看三種路由算法在兩種數據集中的消息傳遞成功概率隨著TTL的增加而增加。當TTL較小時，由于機會網絡中消息的整體時延較大，部分消息在未到達目標節點時就提前失效，導致各種路由算法的消息傳遞成功概率也較低。但是隨著消息存活時間TTL的逐漸增加，有更多的消息成功到達目標節點，因此，消息的傳遞成功概率也相應地增大。

(a) 在Cambridge數據集中不同路由算法的消息傳遞成功概率

(b) 在Infocom06數據集中不同路由算法的消息傳遞成功概率圖3 消息傳遞成功概率

在相同的TTL下，Cambridge數據集中的消息傳遞成功概率會略小于Infocom06。因為Cambridge數據集節點的分布比較稀疏，平均每天每對節點的接觸次數遠小于Infocom06數據集。

對于實驗中的數據集來說，Epidemic算法消息傳遞成功概率最差，Bubble Rap次之，EABNA最好。EABNA算法的傳遞成功概率比Epidemic高約32%、比Bubble Rap高約17%。根據3.2節中定義的轉發度量函數，在初始階段由于每個節點具有相同的剩余能量和緩存空間，所以中繼節點的選擇主要依賴于節點的中心度CD。隨著時間的推移，具有較高中心度的節點的剩余能量和緩存空間迅速下降，而具有較低中心度的節點仍然具有較大的剩余能量和緩存空間。此時，尚未成功傳遞的消息可以由具有略低中心度和較高剩余能量及緩存空間的節點傳遞，從而避免由于高中心度的節點過早“死亡”導致的消息傳遞成功率快速降低。因此，EABNA算法可以實現比Bubble Rap和Epidemic更高的消息傳遞成功率。

(2) 消息平均傳輸時延 兩種數據集中應用不同的算法的消息平均傳輸時延如圖4所示。消息的平均傳輸時延隨TTL的增加而增大，到達一定值之后增長速度逐漸放緩。時延較大的消息在未到達目標節點之前就會因為存活時間不足而被丟棄，而這部分消息并不計算在消息的平均時延之內，因此消息的平均傳輸時延和TTL成正比關系。當TTL到達一定值后大部分消息都能夠在此TTL之內完成傳輸，于是消息平均時延的增速就會趨于平緩。

(a) 在Cambridge數據集中不同路由算法的消息平均傳輸時延

(b) 在Infocom06數據集中不同路由算法的消息平均傳輸時延圖4 消息平均傳輸時延

在相同TTL的條件下，Cambridge數據集中的消息平均時延會略大于Infoncom06數據集。造成這個結果的主要原因是Infoncom06數據集中的節點比較密集，消息有更多的機會傳輸到目標節點。

在兩種數據集當中EABNA算法的表現均優于Bubble Rap和Epidemic算法。從仿真結果來看，EABNA算法中消息的平均時延比Bubble Rap降低了10%左右，比Epidemic降低了28%左右。雖然在節點資源充足的情況下，Bubble Rap和Epidemic的消息時延都低于EABNA算法，但隨著部分節點資源耗盡，Epidemic和Bubble Rap算法的時延會迅速上升。因此，從整體上來看EABNA算法在消息平均時延方面的表現更好。

(3) 節點生存率 圖5反映了EABNA、Bubble Rap、Epidemic三種路由算法的節點存活率在兩種數據集中隨TTL的變化情況。從整體上來看，三種算法隨著消息存活時間TTL呈遞減趨勢，而且在Infocom06數據集中節點存活率下降的速度相對于Cambridge數據集較快。當TTL維持在一個較小值時，由于消息快速失效，節點間的通信頻率較低，減少了對節點的資源如能量和緩存空間的消耗，延長了節點的存活時間。但隨著消息存活時間TTL的增大，網絡中節點間通信次數也會遞增并伴隨資源消耗的增加，導致節點存活率下降。在節點通信相對頻繁的Infocom06數據集中，節點更加容易“死亡”，其存活率比Cambridge數據集低。

(a) 在Cambridge數據集中不同路由算法的節點存活率

(b) 在Infocom06數據集中不同路由算法的節點存活率圖5 節點生存概率

從兩種數據集中都能夠得出，在相同的TTL下Epidemic算法的節點存活率最低，Bubble Rap次之，而EABNA算法的節點存活率最高。與其他兩種算法相比，EABNA算法的節點存活率可以提高245%左右，即在仿真結束時還有更多的節點仍然存活。Epidemic算法采用消息的泛洪傳輸機制，因此表現最差。而Bubble Rap算法中一味將消息轉發給中心度高的節點，導致這些節點轉發過多的消息而耗盡資源的不足。EABNA算法在選擇中繼節點時均衡了節點中心度、剩余能量、剩余緩存空間三者之間的關系，從一定程度上延長了網絡生命周期。

(4) 路由開銷 圖6為三種算法在路由開銷方面的仿真結果。顯然在任何數據集當中，Epidemic的路由開銷是最大的，而Bubble Rap和EABNA算法的路由開銷的性能相差不大，都為Epidemic的1/3左右，并且隨著TTL的增大緩慢增加。因為Epidemic在傳輸消息的過程中會大量復制消息副本，并發送給所有接觸的節點，大大增加了路由開銷。而EABNA算法的路由開銷略微的大于Bubble Rap算法。Bubble Rap算法對節點中心度的依賴更高，在資源充足的情況下可以減少消息的轉發次數。但是當資源不足時，Bubble Rap算法的路由開銷會大于EABNA算法。綜合上述原因再結合仿真結果可得出EABNA和Bubble Rap算法的路由開銷基本相近。

(a) 在Cambridge數據集中不同路由算法的路由開銷

(b) 在Infocom06數據集中不同路由算法的路由開銷圖6 路由開銷

5 結 語

本文提出了一種基于節點屬性的高效節能路由算法EABNA。當選擇中繼節點時充分考慮了節點的社會屬性和其本身屬性的動態變化。本文使用兩種現實生活中的移動數據集對EABNA、BubbeRap、Epidemic三種算法進行仿真。通過詳細比較和分析實驗結果，最終可以得出EABNA算法雖然略微犧牲了路由開銷方面的性能，但是其消息傳遞成功率、消息平均傳輸時延、節點存活率方面的性能都有較大的提升，延長了機會網絡生命周期。

機會網絡中在選擇消息轉發的中繼節點時還可以考慮更多的屬性，例如節點的時空屬性[15]等。通過這些屬性減少轉發次數，延長網絡的生命周期，達到一定的節能效果。