鬼佬大哥大
  • / 10
  • 下載費用:30 金幣  

具有自適應能力的EPIDEMIC路由算法.pdf

關 鍵 詞:
具有 自適應 能力 EPIDEMIC 路由 算法
  專利查詢網所有資源均是用戶自行上傳分享,僅供網友學習交流,未經上傳用戶書面授權,請勿作他用。
摘要
申請專利號:

CN201210239801.4

申請日:

2012.07.12

公開號:

CN102724731B

公開日:

2015.01.14

當前法律狀態:

有效性:

法律詳情: 授權|||實質審查的生效IPC(主分類):H04W 40/02申請日:20120712|||公開
IPC分類號: H04W40/02(2009.01)I 主分類號: H04W40/02
申請人: 北京工商大學
發明人: 孫踐知; 譚勵; 張迎新
地址: 100048 北京市海淀區阜成路11號
優先權:
專利代理機構: 代理人:
PDF完整版下載: PDF下載
法律狀態
申請(專利)號:

CN201210239801.4

授權公告號:

102724731B||||||

法律狀態公告日:

2015.01.14|||2012.12.05|||2012.10.10

法律狀態類型:

授權|||實質審查的生效|||公開

摘要

本發明涉及一種機會網絡路由算法,作用是改進Epidemic路由算法,使機會網絡中節點高效轉發數據包,同時盡可能減少網絡資源消耗。Epidemic路由算法的在某些場景中可以取得很高的傳輸成功率和很低的傳輸延遲,但算法的適應性較差,在另一些場景中,算法性能會急劇下降。本發明提出了自適應機制,并以該機制改進Epidemic路由算法。自適應機制能有效地減少網絡中無效數據包副本的數量,減少網絡資源消耗,改善路由算法的性能,進而改善了Epidemic路由算法的可擴展性。

權利要求書

權利要求書
1.  一種機會網絡路由算法(在后面的敘述中簡稱為路由算法),其特征在于,包括該路
由算法的原理、參數和工作過程。

2.  根據權利要求1所述的路由算法,其特征在于,該路由算法是對Epidemic路由算法的一種改進。

3.  根據權利要求1至2所述的路由算法,其特征在于,該路由算法是在Epidemic路由算法的基礎上引入了自適應機制。

4.  根據權利要求3所述的自適應機制,其特征在于,機會網絡中每個節點維護一個字段用來存放閥值λ,λ∈[0,1],節點緩存中被占用空間的百分比若超過閥值λ,則認為節點緩存區飽和。

5.  根據權利要求3至4所述的自適應機制,其特征在于,節點i和任一節點j相遇時,節點i首先獲取節點j及周圍節點緩存狀況,統計和節點i接觸的節點個數Nai,緩沖飽和節點個數Nei。

6.  根據權利要求3至5所述的自適應機制,其特征在于,計算pi=Nei/Nai,由其定義可知pi∈[0,1]。

7.  根據權利要求3至6所述的自適應機制,其特征在于,節點i按照pi值,隨機復制數據包并發送到與之接觸的節點;即若節點i包含m個數據包,則節點i隨機復制m×pi個數據包,并傳輸給與之接觸的節點。

說明書

說明書具有自適應能力的Epidemic路由算法
技術領域
[0001]本發明涉及機會網絡路由算法,作用是使機會網絡中節點高效轉發數據包,同時盡可能減少節點的轉發量,從而減少網絡資源消耗。
背景技術
[0002]機會網絡是一種不需要在源節點和目的節點之間存在完整路徑,利用節點移動帶來的相遇機會實現網絡通信的、時延和分裂可容忍的自組織網絡。機會網絡不同于傳統的多跳無線網絡,它的節點不是被統一部署的,網絡規模和節點初始位置未進行預先設置,源節點和目的節點之間的路徑事先不能確定是否存在。機會網絡以“存儲-攜帶-轉發”模式逐跳傳輸信息實現節點間通信,其體系結構與多跳無線網絡不同,它在應用層與傳輸層之間插入一個被稱為束層的新的協議層。
[0003]由于機會網絡能夠處理網絡分裂、時延等傳統無線網絡技術難以解決的問題,能滿足惡劣條件下的網絡通信需要,其主要應用于缺乏通信基礎設施、網絡環境惡劣以及應對緊急突發事件的場合。
[0004]1.對照路由算法
[0005]為和本發明路由算法對照,選取了2種典型路由算法作為參照算法。Epidemic算法是基于泛洪策略路由算法的典型代表,很多基于泛洪策略的路由算法都可視為是由該算法衍生而來。SprayandWait算法是按照一定策略進行泛洪,是基于有限度的泛洪策略,該算法的主要性能指標在多數場景下都具有顯著的優勢。
[0006](1)Epidemic算法
[0007]Epidemic算法的基本思想是當2節點相遇時交換對方沒有的數據包,經過足夠的交換后,理論上每個非孤立的節點將收到所有的數據包,從而實現數據包的傳輸。
[0008]在Epidemic算法中,每個數據包有一個全局唯一的標識,每個節點中保存一個概要向量用來記錄節點中攜帶的數據包。當2節點相遇時,雙方首先交換概要向量,獲知對方攜帶數據包情況后,雙方僅傳送對方沒有的數據包。
[0009]Epidemic算法本質上是一種泛洪算法,從理論上講該算法能最大化數據包傳輸的成功率,最小化傳輸延遲,但也會使網絡中存在大量的數據包副本,消耗大量的網絡資源。[0010]Epidemic算法有3個目標,分別是最大的傳輸成功率、最小的傳輸延遲和最小的網絡資源消耗。實現上述目標需要特定的場景,在多數場景下,由于過度泛洪導致路由算法的性能顯著下降。
[0011](2)SprayAndWait算法
[0012]SprayandWait算法分為2個階段。首先是Spray階段,源節點中的部分數據包被擴散到鄰居節點;然后進入到Wait階段,若Spray階段沒有發現目標節點,包含數據包的節點以DirectDelivery方式將數據包傳送到目標節點,即只有在遇到目標節點時,發送數據包。該算法傳輸量顯著地少于Epidemic算法,傳輸成功率高,傳輸延遲較小,算法適用性強。
[0013] (3)Prophet算法
[0014]Prophet算法基于概率策略,該路由算法對報文傳輸成功的概率進行估算,選擇性地復制數據包,盡力避免生成低傳輸效率的副本。該算法定義了一個傳輸預測值來描述節點間成功傳輸的概率。當2個節點相遇時,節點更新各自的傳輸預測值,并利用該值來決定是否轉發數據包。
[0015]2.度量值
[0016]評價機會網絡路由算法性能指標的度量值主要有:
[0017](1)傳輸成功率
[0018]傳輸成功率(DeliveryRatio)是在一定的時間內成功到達目標節點數據包總數和源節點發出的需傳輸數據包總數之比,該指標刻畫了路由算法正確轉發數據包到目標節點的能力,是最重要的指標。
[0019](2)傳輸延遲
[0020]傳輸延遲(DeliveryDelay)是數據包從源節點到達目標節點所需的時間,通常采用平均傳輸延遲來評價。傳輸延遲小意味路由算法傳輸能力強、傳輸效率高,也意味著在傳輸過程中將會占用較少的網絡資源。
[0021](3)路由開銷
[0022]路由開銷(Overhead)是指在一定時間內節點轉發數據包的總數,通常用所有成功到達目標節點的數據包數與所有節點轉發的數據包總數之比來評價。路由開銷高,意味著節點大量地轉發數據包,會使網絡中充斥大量的數據包副本,增加數據包發生碰撞的概率,也會大量地消耗節點能量。
[0023]3.Epidemic算法性能分析
[0024]以表1場景為基礎,分別對數據包總數為50和每節點生成10個數據包2種情況進行仿真,得到圖1、圖2所示結果。
[0025]圖1、圖2中以SprayAndWait作為對照算法,該算法在多數場景下可獲得接近最優的傳輸成功率和路由開銷,且無論網絡的規模大小都能保持較好的性能,有很好的可擴展性。
[0026]由圖1、圖2可得到如下結論:
[0027](1)在一些特定的場景下Epidemic算法的非常高的傳輸成功率和非常低的傳輸延遲,在這兩個指標上大大好于對照算法;
[0028](2)在數據包數量一定時,網絡中節點數量增加會改善路由算法的性能;
[0029](3)在某些場景下,存在一些和網絡應用環境緊密相關的因素會導致Epidemic算法的性能顯著下降。
[0030] 圖3以表1場景為基礎,描述了節點總數一定的情況下,數據包數量和傳輸成功率之間的關系。由圖3可知數據包增加時,傳輸成功率隨之下降。本發明將產生這種現象的原因稱之為擠出效應,即當網絡中需要傳輸數據包總數超過節點可存儲的數據包總量時,會發生節點緩存飽和現象,此時節點接收到新數據包時,不得不按照一定規則丟棄舊數據包,這種效應的存在導致Epidemic算法性能顯著下降。
發明內容
[0031] 本發明涉及一種新的機會網絡路由算法,該算法在Epidemic路由算法基礎上引
入了自適應機制。該算法可減少無效數據包副本的轉發量,獲得較高的傳輸成功率和較低的網絡資源消耗。
[0032] Epidemic算法中擠出效應是導致算法性能下降的核心原因,減少網絡中數據包副本數量,可以抑制擠出效應的發生,但若副本數量過少也會使算法性能下降。若能根據網絡中節點緩存當前的狀況決定數據包副本發送數量,取得較好折衷,顯然可以提高算法性能,拓展算法的適用性。
[0033]本發明改進了Epidemic算法,目標是當網絡中節點緩存趨于飽滿時,主動減少注入網絡的數據包副本的數量,抑制擠出效應的發生,即使算法具有自適應能力。具體方案是在Epidemic算法基礎上增加下面機制,本發明將其稱之為自適應機制,將采用該機制算法稱為AdaptiveEpidemic算法。
[0034] (1)每個節點維護一個字段用來存放閥值λ,λ∈[0,1]。節點緩存中被占用空間的百分比若超過閥值λ,則認為節點緩存區飽和;
[0035] (2)節點i和任一節點j相遇時,節點i首先獲取j及周圍節點緩存狀況,統計和節點i接觸的節點個數Nai,緩沖飽和節點個數Nei;
[0036] (3)計算pi=Nei/Nai,由其定義可知pi∈[0,1];
[0037] (4)節點i按照pi值,隨機復制數據包并發送到與之接觸的節點。
[0038]在自適應機制下,p值可以反映周圍節點緩存飽和狀況,根據p值向網絡中注入數據包副本顯然可以抑制緩存飽和情況的普遍發生,抑制擠出效應的發生,從而改進路由算法的性能。
附圖說明
[0039] 圖1傳輸成功率比較
[0040] 圖2傳輸延遲比較
[0041] 圖3數據包數量對傳輸成功率影響
[0042] 圖4閥值對傳輸成功率的影響
[0043] 圖5不同場景下改進算法的傳輸成功率[0044] 圖6不同場景下改進算法的傳輸延遲[0045] 圖7不同場景下改進算法的路由開銷
具體實施方式
[0046] 以下對本發明的原理和特征進行描述,所舉實例只用于解釋本發明,并非用于限定本發明的范圍。
[0047] 使用ONE(theOpportunisticNetworkingEnvironment)仿真平臺實施本發明涉及的路由算法。下面的仿真中模擬了攜有智能藍牙設備的行人步行于真實的城市場景中,并以此來實施、分析路由算法的性能。具體場景設置如表1所示。
[0048] 表1仿真場景設置
[0049]
[0050](1)閥值的影響
[0051]以表1場景為基礎,以100節點,800數據包為例,來分析閥值對算法傳輸成功率的影響,結果如圖4所示。圖4中數據由(dae-de)/de計算而得,其中dae和de分別是AdaptiveEpidemic和Epidemic算法的傳輸成功率。
[0052]按照AdaptiveEpidemic算法機制,閥值為0時,該算法退化為Epidemic算法,圖
4中結果也驗證該結論。由圖4可以看出當閥值設置恰當時,算法的傳輸成功率可以較大幅度的提高,如當閥值為90%時,改善幅度達到了38.9%。
[0053](2)不同數據包數量影響
[0054]以表1場景為基礎,采用100節點,30-3600個數據包,數據包生存期為3小時,來評價算法的性能。
[0055]圖5-圖7中以Epidemic、Prophet、SprayAndWait作為對照算法。Prophet和AdaptiveEpidemic屬同類算法,都可視為在Epidemic算法基礎上通過限制數據包副本數量來改善算法性能,2種算法有較高的可比性。和SprayAndWait算法比較的原因是應為該算法適應性較強,在各種網絡環境下都可以取得較好的性能。
[0056]當數據包數量為30時,由于數據包數量少不會發生節點緩存飽和的情況,在此時AdaptiveEpidemic算法退化為Epidemic算法。圖5-圖7仿真結果顯示,2算法的所有指標相同,這與理論分析結果一致。
[0057] 圖5結果表明,在不同數據包數量下AdaptiveEpidemic算法的傳輸成功率均優于Epidemic和Prophet。如在1600數據包時,改善程度分別達到39.3%和25.6%。[0058] 圖5結果表明,和SprayAndWait算法相比在數據包數量較少時AdaptiveEpidemic可充分Epidemic優勢,傳輸成功率大幅領先。而在數據包很多時,由于自適應機制發揮作用抑制了數據包副本的傳輸,AdaptiveEpidemic也可取得優于或接近SprayAndWait算法的性能。
[0059]圖6結果表明,AdaptiveEpidemic算法傳輸延遲指標較Epidemic算法差,最大的差距發生在800個數據包時,此時傳輸延遲增加了17.6%,這一結果符合算法機理,當節點緩存區發生飽和時,數據包需要在源節點中等待,從而增加了傳輸延遲。
[0060]圖7結果表明,AdaptiveEpidemic算法和Epidemic相比全面地降低了路由開銷,
在節點較多時,尤其顯著,如在3600節點時,下降了87.1%;和SprayAndWait算法相比
也下降了79.2%
[0061]由圖5-圖7可以看出,AdaptiveEpidemic、Epidemic和Prophet算法的各指標趨勢高度一致,反映了3種算法內在的聯系;也表明Self-adaptive機制并不會改變Epidemic算法的核心機制。
[0062]圖5-圖7仿真結果支持了前面的理論分析,表明在某些場景下,自適應機制可以一定程度地抑制擠出效應,改善算法性能,拓寬算法的適用性。

關于本文
本文標題:具有自適應能力的EPIDEMIC路由算法.pdf
鏈接地址:http://www.wwszu.club/p-6421031.html
關于我們 - 網站聲明 - 網站地圖 - 資源地圖 - 友情鏈接 - 網站客服 - 聯系我們

[email protected] 2017-2018 zhuanlichaxun.net網站版權所有
經營許可證編號:粵ICP備17046363號-1 
 


收起
展開
鬼佬大哥大