[發明專利]一種基于分組策略的機會網絡路由算法

有效

• 申請號: 201110130383.0
• 申請日: 2011-05-19
• 公開（公告）號: CN102209029A
• 公開（公告）日: 2011-10-05
• 發明（設計）人: 孫踐知;贠冰;肖媛媛;陳丹
• 申請（專利權）人: 北京工商大學
• 主分類號: H04L12/56
• 分類號: H04L12/56;H04W40/10
• 代理公司: 暫無信息
• 代理人: 暫無信息

技術領域

本發明涉及機會網絡路由算法，本發明的作用是使機會網絡中節點高效轉發數據包，同時盡可能少地消耗節點能量。

背景技術

機會網絡是一種不需要在源節點和目的節點之間存在完整路徑，利用節點移動帶來的相遇機會實現網絡通信的、時延和分裂可容忍的自組織網絡。機會網絡不同于傳統的多跳無線網絡，它的節點不是被統一部署的，網絡規模和節點初始位置未進行預先設置，源節點和目的節點之間的路徑事先不能確定是否存在。機會網絡以“存儲-攜帶-轉發”模式逐跳傳輸信息實現節點間通信，其體系結構與多跳無線網絡不同，它在應用層與傳輸層之間插入一個被稱為束層的新的協議層。

由于機會網絡能夠處理網絡分裂、時延等傳統無線網絡技術難以解決的問題，能滿足惡劣條件下的網絡通信需要，其主要應用于缺乏通信基礎設施、網絡環境惡劣以及應對緊急突發事件的場合。

在颶風、地震等嚴重自然災害發生后，電力、通訊等基礎設施遭到破壞，依賴固定基礎設施的通訊系統通常都無法使用。此時，由身處災難場景中個人攜帶的無線智能移動設備間相互通信，進而以這些設備為節點組成的通訊網絡將成為災區重要的通信手段。在災難場景下，無線智能移動設備難以得到能量補充，僅能靠設備中固有的能量維持通信，設備中的能量變成一種稀缺資源，低的能量消耗意味著節點有更長的生存期。

為和本發明路由算法對照，選取了3種傳統典型路由算法。Direct?Delivery算法是單副本路由算法的典型代表，該算法在任何情況下路由開銷均為0，是轉發量最小的路由算法，但該算法的傳輸成功率、傳輸延遲等指標較差。Epidemic算法是基于泛洪策略路由算法的典型代表，很多基于泛洪策略的路由算法都可視為是由該算法衍生而來。Direct?Delivery和Epidemic算法分別代表了2種極端情況，一種是不泛洪，另一種是無限制的泛洪。Spray?and?Wait算法是按照一定策略進行泛洪，從泛洪程度角度講是介于Direct?Delivery和Epidemic中間的一種算法，該算法的主要性能指標在多數場景下都具有顯著的優勢。

下面簡單介紹一下3種傳統典型路由算法的機理：

1.Direct?Delivery算法

Direct?Delivery(也稱Direct?Transmission)算法基于轉發策略，該路由算法數據包在傳輸過程中，節點不會對其進行復制，網絡中只有一個數據包副本在傳輸。源節點僅在遇到目標節點時將數據包交付給下一個節點。

2.Epidemic算法

Epidemic算法是基于泛洪策略，算法思想是當2節點相遇時復制并交換對方沒有的數據包，經足夠的交換后，理論上每個非孤立節點將收到所有數據包，從而實現數據包的傳輸。算法的優點是在某些場景下能最大化數據包傳輸的成功率，減少傳輸延遲，缺點是網絡中存在大量的數據包副本，會大量消耗網絡資源。

3.Spray?And?Wait算法

Spray?and?Wait算法分為2個階段。首先是Spray階段，源節點中的部分數據包被擴散到鄰居節點；然后是Wait階段，若Spray階段沒有發現目標節點，包含數據包的節點以Direct?Delivery方式將數據包傳送到目標節點。該算法基于泛洪策略，但傳輸量顯著地少于Epidemic算法；傳輸延遲較小，接近于最優。

評價機會網絡路由算法性能指標的度量值主要有如下3個：

1.傳輸成功率

傳輸成功率(Delivery?Ratio)是在一定的時間內成功到達目標節點數據包總數和源節點發出的需傳輸數據包總數之比，該指標刻畫了路由算法正確轉發數據包到目標節點的能力，是最重要的指標。

2.路由開銷

路由開銷(Overhead)是指在一定時間內節點轉發數據包的總數，通常用所有成功到達目標節點的數據包數與所有節點轉發的數據包總數之比來評價。路由開銷高，意味著節點大量地轉發數據包，會使網絡中充斥大量的數據包副本，增加數據包發生碰撞的概率，也會大量地消耗節點能量。

3.傳輸延遲

傳輸延遲(Delivery?Delay)是數據包從源節點到達目標節點所需的時間，通常采用平均傳輸延遲來評價。傳輸延遲小意味路由算法傳輸能力強、傳輸效率高，也意味著在傳輸過程中將會占用較少的網絡資源。