基於智能水滴的移動自組網路由系統及方法

2023-04-24 06:48:01

專利名稱：基於智能水滴的移動自組網路由系統及方法
技術領域：
本發明涉及無線傳感器網絡領域，尤其將智能水滴引用到了移動自組網的路由問題中。
背景技術：
傳統的網絡，無論是有線網還是無線網，都需要事先鋪設的基礎設施才能進行通信，比如網關或路由器。但在一些特殊的情況下，不能提供預先架設的網絡基礎設施，卻仍然對網絡通信有著較高的要求，比如戰場通信環境，災難救援環境等等。針對這些特殊的應用環境，人們提出了移動自組網的概念來滿足這些條件下的通信需求。移動自組網繼承了一般意義無線網絡的特徵，並且具有很多自身獨特的特點。節點之間無需電纜即可傳輸數據，並且共享同一媒介；移動自組網是由無線節點按需、動態組成的臨時網絡；自製且無需基礎設施。移動自組網不依賴於任何已經存在的網絡設施，無需統一的管理。每個節點以分布式點對點模式運行，每個節點獨立地產生數據，並且獨立的進行路由；多跳路由，移動自組網無需專門的路由器設備，每個節點都具有路由功能，並且轉發來自其他節點的數據，從而使得全網範圍內任意兩個節點之間能夠相互傳輸數據；移動性，每個節點都可以在與其他節點通信的同時進行移動。移動自組網由不斷移動的節點組成，網絡拓撲天然地具有動態特性，也就導致了節點之間的通信環境持續變化。綜上所述，移動自組網擺脫了網絡基礎設施的限制，使得在很多應用場景中無線節點可以任意的快速創建和加入網絡。但在移動自組網環境下，傳統的路由協議大多不能取得很好的效果，需要提出新的針對移動自組網環境的路由協議。移動自組網路由協議的主要目的是在兩個節點之間正確、高效地建立路由，使得信息能夠在該對節點之間可靠快速的傳遞。路由的建立過程應當儘可能少的引入額外的流量開銷和對帶寬的消耗。現有的基於距離向量和基於鏈路狀態的路由協議是針對靜態網絡環境而設計的，從而不適合應對移動自組網快速變化的網絡拓撲結構，繼而導致性能的下降 ，包括路由收斂速度慢，通信吞吐量低，在某些節點失效後可能產生網絡環路。新的路由協議需要專門為移動自組網環境而設計，以適應其移動性的需要，並儘可能減少帶寬和能量的消耗。假設智能水滴在某種環境當中流動，從起點流向某個終點。而在這一環境中，從起點到達終點的路徑可能不止一條。這裡所說的環境，也即實踐當中需要解決的問題，可以分為兩類。其一是終點已知的情形。在這種情況下，問題的解決需要按照某個標準(通常是距離)找到從起點到達終點的最佳路徑。另一類問題中，終點的位置是事先不知道的。在這一類問題中，解決問題就是要依照代價或者其他問題當中定義的條件找到終點最優的位置。在自然界的實際環境裡水流是連續流動的。而在抽象的智能水滴環境中，水滴是按照離散的步驟運動的。水滴從當前位置i移動到下一個位置j，其速度值的增量定義為Avelocity(IffD)。按照前文所述，該速度增量是與從位置i到位置j之間路徑上的泥土量相關的。具體說來，智能水滴速度的增量Ave1city(IWD)非線性反比於從位置i到位置j之間路徑上的泥土量soil (i, j)。Avelocity(IWD) ^nl.■上 、式(I)這裡使用符號oc Nl來表示非線性正比關係。下面給出一種可能的表達式，其中智能水滴的速度用AVel1TO(t)來表示，它是位置i於位置j之間路徑上的泥土量soil (i，j)
的函數。(2)這裡的av，bv，Cv和a都是用戶選定的大於0的參數。此外，由於從連接位置i和位置j的路徑當中移動了部分泥土，智能水滴中攜帶的泥土量soil (IWD)也相應的增加。路徑當中減少的泥土量和智能水滴中增加的泥土量是相等的。A soil (IffD) = A soil (i, j)式(3)而泥土的增量 非線性反比於水滴從當前位置i移動到下一位置j所需要花費的時間 time (i, j ；IWD)。
_2] —-^^式⑷—種可能的解析表達式在下面給出。其中time(i, j ；velIWD)是智能水滴以速度vel1 從位置i移動到位置j需要的時間。在這一過程中智能水滴所攜帶泥土的增量為:
_4] —式(5)這裡as，bs，Cs和0都是大於0的參數，由用戶自行定義。智能水滴由位置i移動到位置j移動的時間可以由物理學中的勻速直線運動模型計算出來。因此，智能水滴的移動時間正比於位置i到位置j之間的距離，反比於水滴的移動速度。
, d(hj) ,其中d(i，j)為位置i於位置j之間的距離，表示線性正比的關係。下面給出一種可能的解析表達形式，可以計算出智能水滴從位置i以vel 移動到位置j所需要的時間。time(i,j',velmD) = ^式⑵
vel這裡沒有直接使用位置i到位置j的距離d(i，j)，而是使用了更廣義的本地啟發函數HUD (Heuristic Undesirability)。HUD(i,j)表徵了智能水滴拒絕從位置i移動到位置j的程度。而距離是水滴拒絕移動的因素之一，當位置i與位置j距離較遠時，水滴的移動較為困難；而當位置i與位置j距離較近時，水滴能夠更加輕易地進行移動，因此事實上d(i，j)是HUD(i，j)的特殊化情形。HUD的值能夠為智能水滴對於下一位置的選擇提供參考，在實際的優化問題中代表了優化依據的條件。在位置i到位置j的路徑上，由智能水滴的移動而帶走了一定量的泥土。用soil (i, j)代表路徑當中的剩餘的泥土量，它與路徑中失去的泥土量，S卩Asoil(i,j)成正比:
soil(i, j) L A soil (i, j)式(8)從位置i到位置j路徑當中的泥土量通過由智能水滴帶走的泥土量來更新，一種可能的解析表達式為:soil (i, j) = P -soil (i, j)_p n A soil (i, j)式(9)在該表達式中P ^和P 通常是用戶選擇的小於I的正數。一般使得Pc^P P1Ji足以下條件:P0= 1-Pn式(10)而智能水滴中攜帶的泥土量soil 按照以下關係更新:soil = soil +A soil (IWD)式(11)智能水滴的另一項行為機制是在遇到多條可選路徑時，會更傾向於選擇泥土量較少的路徑而不是泥土量較多的路徑。為實現這一路徑選擇的機制，這裡引入了均勻分布的路徑選擇概率。對於智能水滴可能選擇的多個下一位置，每個位置以一定的概率被選擇。以P(i，j ;IWD)代表智能水滴在位置i時選擇j作為下一位置的概率，它與路徑當中的泥土量成反比。
權利要求
1.一種基於智能水滴的移動自組網路由系統，路由發現模塊，環路消除模塊，路由維護模塊。其中，路由表設計模塊負責設計路由器的核心數據結構，包含了一系列路由信息條目，每個條目通常包括目的節點的地址、要到達目的節點而需要轉發的下一跳節點地址，以及另外一些輔助進行路由選擇的鏈路狀態信息。路由發現模塊是在數據傳輸的源節點、目的節點以及中途的所有中繼節點當中構建初始的路由表。環路消除模塊負責消除環路的存在。路由維護模塊負責選擇最優的傳輸路徑。
2.如權利要求1所述的一種基於智能水滴的移動自組網路由系統，其特徵是:所述的路由表設計模塊負責設計路由器的核心數據結構，包含了一系列路由信息條目，每個條目通常包括目的節點的地址、要到達目的節點而需要轉發的下一跳節點地址，以及另外一些輔助進行路由選擇的鏈路狀態信息。
3.如權利要求1所述的一種基於智能水滴的移動自組網路由系統，其特徵是:所述的路由發現模塊在源節點試圖與目的節點建立數據連接，但是發現本地並沒有與目的節點相關的路由信息時，源節點開始進行路由發現的過程。源節點生成前向的發現者包，將其中的源節點地址初始化為自身的地址，目的節點地址初始化為需要建立數據連接的目的節點地址，將本地地址記錄到已經經歷的節點地址列表中，而將已經經歷的跳數初始化為I。接下來源節點將發現者包向其鄰居節點廣播出去。而鄰居節點收到發現者包之後會遞歸地使轉發過程進行下去，從而使發現者包在整個網絡範圍內洪泛地轉發。
4.如權利要求1所述的一種基於智能水滴的移動自組網路由系統，其特徵是:所述的環路消除模塊，在前向發現者包和反向發現者包當中都包含了已經經歷的節點列表，該列表採用堆棧的結構進行存儲。發現者包每經過一個網絡節點，就將該節點的地址壓入節點地址列表堆棧中，並對堆棧當中的其他節點地址進行搜索。如果剛剛入棧的節點地址M已經在堆棧中出現過，則將兩次出現的節點M之間的地址元素全部彈出堆棧，而堆棧當中只保留之前一次出現的節點M的地址。這就從發現者包的層面上保證了記錄的路徑當中不存在環路。而每個節點路由表當中的條目由且僅由發現者包在路由發現階段進行創建，於是節點的路由表當中記錄的路由信息也就相應的消除了環路的存在。
5.如權利要求1所述的一種基於智能水滴的移動自組網路由系統，其特徵是:所述的路由維護模塊，引入一種額外的數據包，稱為智能水滴包，用來在網絡節點之間傳遞並對所經過節點的路由表中相應條目的路徑泥土量信息進行更新。首先在源節點生成智能水滴包，將其源節點地址初始化為本地地址，將目的節點地址初始化為鏈路的目的節點地址。水滴的速度和泥土量的值都是可以自行選擇的靜態參數，需要根據網絡規模的大小、對算法收斂速度的要求等不 同情況進行不同的選擇，但是對於同一網絡中不同的智能水滴包裡的這些參數應當保持一致。對於生存期參數，需要根據網絡規模的大小進行設定，當網絡規模較大時，生存期也應當較長；當網絡規模較小時，水滴的生存期也較短。
全文摘要
本發明將智能水滴引用到了移動自組網路由中，很好的處理網絡的高度動態特性和網路拓撲結構經常產生的變化。該系統由路由表設計模塊，路由發現模塊，環路消除模塊，路由維護模塊組成(見附圖
)。其中，路由表設計模塊負責設計路由器的核心數據結構，包含了一系列路由信息條目，每個條目通常包括目的節點的地址、要到達目的節點而需要轉發的下一跳節點地址，以及另外一些輔助進行路由選擇的鏈路狀態信息。路由發現模塊是在數據傳輸的源節點、目的節點以及中途的所有中繼節點當中構建初始的路由表。環路消除模塊負責消除環路的存在。路由維護模塊負責選擇最優的傳輸路徑。
文檔編號H04W40/24GK103228020SQ20121054371
公開日2013年7月31日 申請日期2012年12月14日 優先權日2012年12月14日
發明者孫學斌, 趙成林, 孫珊珊, 楊帆 申請人:北京郵電大學