基於概率的無線自組織網絡反應式路由方法
2023-05-30 21:02:36 2
專利名稱：基於概率的無線自組織網絡反應式路由方法
技術領域：
本發明屬於無線網絡路由協議領域。具體涉及一種在無線多跳網絡中建立信源和新宿之間路徑的方法。
背景技術：
無線自組織網絡在很多領域都有廣泛的應用。無線自組織網絡中，無線節點既 是終端，又是路由節點——負責為其他通信對轉發數據。通常無線節點由電池供電，具有有 限的通信範圍。無線自組織網絡具有動態性強、無線環境時變、傳輸具有丟失特性，因此設 計無線自組織網絡路徑建立方法具有重要的意義。無線自組織網絡路由協議分為先應式和反應式兩種。先應式路由協議時時刻刻需 要維護網絡中所有節點之間的通信路徑，無論這些路徑是否被實際用到。先應式路由開銷 大。反應式路由只有當一對信源和信宿之間需要通信時才被激活。反應式路由開銷小。一個反應式路由協議通常由路徑發現、路徑響應和路徑維護三個部分組成。路徑 發現通常由信源節點發起。當信源希望向某個新宿發送數據時，而又沒有到達新宿的路徑， 這時信源向網絡洪泛一個路由請求報文，收到該報文的中間節點(Intermediatenodes)將 繼續轉發非重複性(Non-duplicate)的路由請求報文，如果信宿收到一個路由請求報文，那 麼它就可以向信源返回一個路由應答報文，以通知信源已經找到一條兩者之間的路徑。當 路徑中斷(如由於節點移動或無線環境惡劣化)時，可以通過路徑維護進程修補之前找到的 路徑，也可以重新進行路徑選擇。A0DV[1]、DSR[2]以及基於這些協議的衍生協議都屬於上 述類型。這些反應式協議要求每個中間節點都需要對某個路由請求報文轉發一次，因此尋 徑開銷較大。現有文獻中，已經有了一些路由方法考慮如何降低反應式路由尋徑過程中產生的 協議開銷，具體包括以下幾種類型
(1)基於地理位置信息的先應式路由這類路由協議首先根據信源和信宿所在的地理 位置確定一個包含信源和信宿的矩形區域或橢圓形區域，然後在該區域內部尋找路徑，以 期在縮小尋徑範圍的基礎上找到連結源和宿的路徑。這類方法要求每個節點知道自己的位 置信息(如通過裝備GPS接收器)，因此增加了額外的成本，通用性不強。(2)基於連通支撐集合(ConnectedDominatingSet)的、GAF等)這些協議首 先根據局部拓撲知識或地理位置信息，構造一個基礎性的網絡連通支撐結構，然後通過處 在這一結構之上的節點轉發路由請求報文，尋找端到端路徑，並降低尋徑開銷。這類方案或 者需要預先交互相鄰狀態信息(如CEDAR)或者要求節點具備位置信息。前者開銷大，後者 要求額外的位置設備信息。(3)基於概率的方式轉發基於滲透理論(percolationtheory)，即對於一個無 線網絡，如果信源廣播一個分組後，每個中間節點以概率P轉發一個廣播報文，那麼如果P 的值足夠大，那麼全網節點會以較高的概率全部或絕大部分收到該分組。已有基於GOSSIP的尋徑方法是各向同性的，或尋徑範圍限制在以源和宿為焦點、以幾何距離為焦距的橢圓 範圍之內。上述方案雖然可以降低尋徑開銷，但前者浪費較為嚴重，因為尋徑消息是向網絡中各個方向以同等的概率擴散的；而後者路徑擴散具有定向性，但要求節點具備額外位置 fn息ο
發明內容
本發明面向無線自組織網絡，主要設計目的是降低尋找連接信源和信宿過程中所 消耗的信令開銷。本發明中的路由方法針對下述無線自組織網絡每個節點配備各項同性的無線天 線；節點具有移動性；當兩個節點在相互無線通信範圍時，兩者可以直接通信，否則不能直 接通信；節點不知道自身的位置信息。本發明充分利用已經中斷的舊路徑信息，結合基於概率的路由發現方法，有效地 控制尋徑的範圍，降低尋徑開銷，並保持較高的路徑質量。具體來說只有距離舊路徑一定 距離內(K跳以內)的中間節點參與路徑恢復，其中處在舊路徑上的節點以概率1參與，上述 範圍內的其它節點以概率P*參與轉發路由請求報文。如果當前尋徑或重尋徑一次廣播RREQ即成功找到端到端路徑，那麼則降低路由 請求報文轉發概率和尋徑範圍，並應用到下一次重尋徑中去；否則直接將本次尋徑的路由 請求報文轉發概率和尋徑範圍直接用於下一次重尋徑進程中去。對於持續時間較長的通信會話，本發明的方法能夠非常有效地降低通信開銷。
具體實施例方式本發明的路由方案如下
路由包括路由發現和路由維護兩個階段 路由發現過程(RouteDiscovery)如下
當信源s有數據向信宿t傳送，但沒有任何到達t的路徑信息時，信源s生成一個 路由請求報文(RREQ，RouteRequest)。RREQ包含以下信息信源ID、信宿ID、RREQ序列號、 中間節點轉發概率P*的值。然後，信源s向鄰居廣播該RREQ分組並啟動一個計時器。當一個非信宿節點(即中間節點)收到一個非重複RREQ時，該節點以概率P*將 該RREQ進行轉發。如果決定進行轉發的話，該節點將發給自己該RREQ分組的節點記為上一 跳節點，並在本節點為這個路由請求保存一條表項(記錄信源ID、上一跳ID、RREQ序列號、 信宿ID)，然後進行計時。如果超時沒有收到路由應答，則刪除該表項。如果信宿節點t收到一條RREQ報文後，那麼它立刻沿反向路徑向信源返回一 條路由應答報文(RREP，RouteReply)0如果信源s收到該報文，則可以沿著這條路徑發送分 組。如果一段時間沒有數據需要向t轉發，中間節點的路由表將超時並被刪除。如果信源超時沒有收到路由應答報文，那麼信源從新生成一個路由請求報文， 但其中的中間節點轉發概率P*的值設定為P*=maX{l，p*+D}，D是一個較小的值，D<1，如 D=O. 1。然後轉發光播該分組，中間節點和目的節點的操作與前面的描述相同。如果當ρ* 上升到1之後進行尋徑，仍然沒有找到到達信宿的路徑，我們認為網絡中不存在從信源到信宿的路徑。路由發現進程終止。路由維護(RouteMaintenance)進程
當由於某種原因(如節點移動等)發生路徑中斷時，發生中斷的鏈路的上遊節點立 即生成一個路由錯誤報文(RERR.RouteError)，通知信源路徑中斷的發生。注意收到該路 由錯誤報文的中間節點並不自動刪除自己保存的相關路由表項。信源收到路由錯誤報文後，如果有數據需要繼續發送，那麼它需要啟動路由重新 發現進程，具體如下
當信源s決定進行重尋徑時，它生成一個路由請求報文(RREQ)。RREQ報文包含以 下信息信源ID、信宿ID、RREQ序列號、中間節點轉發概率ρ*的值、正整數k的值、轉發跳 數K的值(一般K的初值不大，如k=2或3)。然後，信源s向鄰居廣播該RREQ分組並啟動一 個計時器。一個非信宿節點(即中間節點)收到一個非重複RREQ報文時，如果它是之前中斷 的路徑上的節點，那麼它將k的值置零，並以概率1轉發該RREQ報文；否則收到RREQ報文 攜帶的k的值小於K，那麼該節點執行k=k+l並以概率ρ*轉發該RREQ報文；否則丟棄該報 文。如果一個中間節點執行報文轉發，那麼它需要和之前路由發現進程中描述的路由表建 立保存相同的程序來進行路由表建立或刷新，以及超時刪除事項。如果信宿節點t收到一條RREQ報文後，那麼它立刻沿反向路徑向信源返回一條路 由應答報文(RREP)。如果信源s收到該應答報文，則可以沿著這條路徑發送分組。如果信源超時沒有收到路由應答報文，那麼信源從新生成一個路由請求報文，但 其中的中間節點轉發概率P*的值設定為p*=maX{l，p*+D}，K=K+DK，一般DK=I或2。然後轉 發光播該分組，中間節點和目的節點的操作與前面的描述相同。如果當P*上升到1且K的 值大於網絡的直徑(可以是一個預先估計的較大的值)之後進行尋徑，仍然沒有找到到達信 宿的路徑，我們認為網絡中不存在從信源到信宿的路徑。路由發現進程終止。第一次路由重發現過程中，ρ*和K的值採用預先設定的值；
如果第X(X>1)次路由重發現過程中，如果第一輪路由重發現就找到了連接源和宿的路徑，那麼p*=p*_D，K=K-DK,並將這些更新的ρ*和K值用到第x+1次路由重尋徑中去；否 則第χ次路由重發現中的ρ*和K值將直接應用到第x+1次路由重尋徑中去。
權利要求
基於概率的無線自組織網絡反應式路由方法，所述無線自組織網絡具有下列條件每個節點配備各項同性的無線天線；節點具有移動性；當兩個節點在相互無線通信範圍時，兩者可以直接通信，否則不能直接通信；節點不知道自身的位置信息，所述路由方法包括路由發現方法和路由維護方法，其特徵在於路由重發現方法是只有距離舊路徑一定距離內(K跳以內)的中間節點參與路徑恢復，其中處在舊路徑上的節點以概率1參與，上述範圍內的其它節點以概率p*參與轉發路由請求報文。
2.根據權利要求1的基於概率的無線自組織網絡反應式路由方法，其特徵在於路由 請求報文轉發概率和尋徑範圍更新方法是如果當前尋徑或重尋徑一次廣播RREQ即成功 找到端到端路徑，那麼則降低路由請求報文轉發概率和尋徑範圍，並應用到下一次重尋徑 中去；否則直接將本次尋徑的路由請求報文轉發概率和尋徑範圍直接用於下一次重尋徑進 程中去。
全文摘要
基於概率的無線自組織網絡反應式路由方法，屬於無線網絡協議領域，所述無線自組織網絡具有下列條件每個節點配備各項同性的無線天線；節點具有移動性；當兩個節點在相互無線通信範圍時，兩者才可以直接通信；節點不知道自身的位置信息，路由方法包括路由發現方法和路由維護方法，其特徵在於路由重發現方法是只有距離舊路徑一定距離內(K跳以內)的中間節點參與路徑恢復，其中處在舊路徑上的節點以概率1參與，上述範圍內的其它節點以概率p*參與轉發路由請求報文。對於持續時間較長的通信會話，本發明的方法能夠非常有效地降低通信開銷。
文檔編號H04W84/18GK101815337SQ20101015209
公開日2010年8月25日 申請日期2010年4月21日 優先權日2010年4月21日
發明者趙壯 申請人:無錫泛聯軟體科技有限公司