具有退避機制的Epidemic路由算法的製作方法
2023-12-11 17:06:22 2
專利名稱：具有退避機制的Epidemic路由算法的製作方法
技術領域：
本發明涉及機會網絡路由算法，作用是使機會網絡中節點高效轉發數據包，同時儘可能減少網絡資源消耗。
背景技術：
機會網絡是一種不需要在源節點和目的節點之間存在完整路徑，利用節點移動帶來的相遇機會實現網絡通信的、時延和分裂可容忍的自組織網絡。機會網絡不同於傳統的多跳無線網絡，它的節點不是被統一部署的，網絡規模和節點初始位置未進行預先設置，源節點和目的節點之間的路徑事先不能確定是否存在。機會網絡以「存儲-攜帶-轉發」模式逐跳傳輸信息實現節點間通信，其體系結構與多跳無線網絡不同，它在應用層與傳輸層 之間插入一個被稱為束層的新的協議層。由於機會網絡能夠處理網絡分裂、時延等傳統無線網絡技術難以解決的問題，能滿足惡劣條件下的網絡通信需要，其主要應用於缺乏通信基礎設施、網絡環境惡劣以及應對緊急突發事件的場合。I.對照路由算法為和本發明路由算法對照，選取了 2種典型路由算法作為參照算法。Epidemic算法是基於泛洪策略路由算法的典型代表，很多基於泛洪策略的路由算法都可視為是由該算法衍生而來。Spray and Wait算法是按照一定策略進行泛洪，是基於有限度的泛洪策略，該算法的主要性能指標在多數場景下都具有顯著的優勢。(I) Epidemic 算法Epidemic算法的基本思想是當2節點相遇時交換對方沒有的數據包,經過足夠的交換後，理論上每個非孤立的節點將收到所有的數據包，從而實現數據包的傳輸。在Epidemic算法中，每個數據包有一個全局唯一的標識,每個節點中保存一個概要向量用來記錄節點中攜帶的數據包。當2節點相遇時，雙方首先交換概要向量，獲知對方攜帶數據包情況後，雙方僅傳送對方沒有的數據包。Epidemic算法本質上是一種泛洪算法，從理論上講該算法能最大化數據包傳輸的成功率，最小化傳輸延遲，但也會使網絡中存在大量的數據包副本，消耗大量的網絡資源。Epidemic算法有3個目標,分別是最大的傳輸成功率、最小的傳輸延遲和最小的網絡資源消耗。實現上述目標需要特定的場景，在多數場景下，由於過度泛洪導致路由算法的性能顯著下降。(2) Spray And Wait 算法Spray and Wait算法分為2個階段。首先是Spray階段,源節點中的部分數據包被擴散到鄰居節點；然後進入到Wait階段，若Spray階段沒有發現目標節點，包含數據包的節點以Direct Delivery方式將數據包傳送到目標節點，即只有在遇到目標節點時,發送數據包。該算法傳輸量顯著地少於Epidemic算法，傳輸成功率高，傳輸延遲較小，算法適用性強。
2.度量值評價機會網絡路由算法性能指標的度量值主要有(I)傳輸成功率傳輸成功率(Delivery Ratio)是在一定的時間內成功到達目標節點數據包總數和源節點發出的需傳輸數據包總數之比，該指標刻畫了路由算法正確轉發數據包到目標節點的能力，是最重要的指標。⑵傳輸延遲傳輸延遲(Delivery Delay)是數據包從源節點到達目標節點所需的時間,通常採用平均傳輸延遲來評價。傳輸延遲小意味路由算法傳輸能力強、傳輸效率高，也意味著在傳輸過程中將會佔用較少的網絡資源。 (3)路由開銷路由開銷(Overhead)是指在一定時間內節點轉發數據包的總數，通常用所有成功到達目標節點的數據包數與所有節點轉發的數據包總數之比來評價。路由開銷高，意味著節點大量地轉發數據包，會使網絡中充斥大量的數據包副本，增加數據包發生碰撞的概率，也會大量地消耗節點能量。3. Epidemic算法性能分析以表I場景為基礎，分別對數據包總數為50和每節點生成10個數據包2種情況進行仿真，得到圖I、圖2所示結果。圖I、圖2中以Spray And Wait作為對照算法,該算法在多數場景下可獲得接近最優的傳輸成功率和路由開銷，且無論網絡的規模大小都能保持較好的性能，有很好的可擴展性。由圖I、圖2可得到如下結論(I)在一些特定的場景下Epidemic算法的非常高的傳輸成功率和非常低的傳輸延遲，在這兩個指標上大大好於對照算法；(2)在數據包數量一定時，網絡中節點數量增加會改善路由算法的性能；(3)在某些場景下，存在一些和網絡應用環境緊密相關的因素會導致Epidemic算法的性能顯著下降。圖3以表I場景為基礎，描述了節點總數一定的情況下，數據包數量和傳輸成功率之間的關係。由圖3可知數據包增加時，傳輸成功率隨之下降。本發明將產生這種現象的原因稱之為擠出效應，即當網絡中需要傳輸數據包總數超過節點可存儲的數據包總量時，會發生節點緩存飽和現象，此時節點接收到新數據包時，不得不按照一定規則丟棄舊數據包，這種效應的存在導致Epidemic算法性能顯著下降。
發明內容
本發明涉及一種新的機會網絡路由算法，該算法在Epidemic路由算法基礎上引入了退避機制，當節點緩衝區被充滿時，與之相遇的節點按照一定規則不再向其轉發數據包，即進行退避。本發明算法可有效地抑制擠出效應，獲得較高的傳輸成功率和較低的網絡資源消耗。本發明算法的具體方案是在Epidemic算法原有機制基礎上增加下面(1)-(4)機制，本發明將其稱之為退避機制，將具有退避機制的Epidemic算法稱為Backoff Epidemic算法。機制的具體描述如下(I)節點維護一個欄位，該欄位用來存放閥值t ；(2)閥值t是隨機產生的，服從均勻分布，其值範圍是(0，x)，X是參數，根據網絡狀況確定；(3)當某一節點緩存充滿後，在時間t內，該節點拒絕接收目標節點不是該節點的數據包，即在閥值時刻內令其他節點的數據包退避；(4)當退避時間超過閥值t後，無論節點緩存狀態均接收數據包，此時依舊可能發生擠出事件。接收到數據包後，退避時間被重置為O。
圖I傳輸成功率比較圖2傳輸延遲比較圖3數據包數量對傳輸成功率影響圖4不同場景下改進算法的傳輸成功率圖5不同場景下改進算法的傳輸延遲圖6不同場景下改進算法的路由開銷
具體實施例方式以下對本發明的原理和特徵進行描述，所舉實例只用於解釋本發明，並非用於限定本發明的範圍。使用0NE(the Opportunistic Networking Environment)仿真平臺實施本發明涉及的路由算法。在下面的仿真中，模擬了攜有智能藍牙設備的行人步行於真實的城市場景中，並以此來實施、分析路由算法的性能。具體場景設置如表I所示。表I仿真場景設置
權利要求
1.一種機會網絡路由算法(在後面的敘述中簡稱為路由算法)，其特徵在於，包括該路由算法的原理、參數和工作過程。
2.根據權利要求I所述的路由算法，其特徵在於，該路由算法是對Epidemic路由算法的一種改進。
3.根據權利要求I至2所述的路由算法，其特徵在於，該路由算法是在Epidemic路由算法的基礎上引入了退避機制。
4.根據權利要求3所述的退避機制，其特徵在於，節點維護一個欄位，該欄位用來存放閥值t。
5.根據權利要求3至4所述的退避機制，其特徵在於，閥值t是隨機產生的，服從均勻分布，其值範圍是(O，X)，X是參數，根據網絡狀況確定。
6.根據權利要求3至5所述的退避機制，其特徵在於，當某一節點緩存充滿後，在時間t內，該節點拒絕接收目標節點不是該節點的數據包，即在閥值時刻內令其他節點的數據包退避。
7.根據權利要求3至6所述的退避機制，其特徵在於，當退避時間超過閥值t後，無論節點緩存狀態均接收數據包，當節點接收到數據包後，其退避時間被重置為O。
全文摘要
本發明涉及一種機會網絡路由算法，作用是改進了Epidemic路由算法，使機會網絡中節點高效轉發數據包，同時儘可能少地消耗網絡資源。Epidemic路由算法的在某些場景中可以取得很高的傳輸成功率和很低的傳輸延遲，但算法的適應性較差，在另一些場景中，算法性能會急劇下降。本發明提出了退避機制，並以該機制改進Epidemic路由算法。退避機制能有效地減少網絡中數據包副本的數量，抑制擠出效應，改善路由算法的性能，進而改善Epidemic路由算法的可擴展性。
文檔編號H04L12/721GK102970223SQ20121023980
公開日2013年3月13日 申請日期2012年7月12日 優先權日2012年7月12日
發明者孫踐知, 譚勵, 肖媛媛, 張迎新 申請人:北京工商大學