[發明專利]基于概率的無線自組織網絡反應式路由方法

無效

• 申請號: 201010152092.7
• 申請日: 2010-04-21
• 公開（公告）號: CN101815337A
• 公開（公告）日: 2010-08-25
• 發明（設計）人: 趙壯
• 申請（專利權）人: 無錫泛聯軟件科技有限公司
• 主分類號: H04W40/22
• 分類號: H04W40/22;H04W40/24;H04W84/18
• 代理公司: 江蘇英特東華律師事務所 32229
• 代理人: 邵鋆

技術領域

本發明屬于無線網絡路由協議領域。具體涉及一種在無線多跳網絡中建立信源和新宿之間路徑的方法。

背景技術

????無線自組織網絡在很多領域都有廣泛的應用。無線自組織網絡中，無線節點既是終端，又是路由節點——負責為其他通信對轉發數據。通常無線節點由電池供電，具有有限的通信范圍。無線自組織網絡具有動態性強、無線環境時變、傳輸具有丟失特性，因此設計無線自組織網絡路徑建立方法具有重要的意義。

無線自組織網絡路由協議分為先應式和反應式兩種。先應式路由協議時時刻刻需要維護網絡中所有節點之間的通信路徑，無論這些路徑是否被實際用到。先應式路由開銷大。反應式路由只有當一對信源和信宿之間需要通信時才被激活。反應式路由開銷小。

一個反應式路由協議通常由路徑發現、路徑響應和路徑維護三個部分組成。路徑發現通常由信源節點發起。當信源希望向某個新宿發送數據時，而又沒有到達新宿的路徑，這時信源向網絡洪泛一個路由請求報文，收到該報文的中間節點(Intermediate?nodes)將繼續轉發非重復性（Non-duplicate）的路由請求報文，如果信宿收到一個路由請求報文，那么它就可以向信源返回一個路由應答報文，以通知信源已經找到一條兩者之間的路徑。當路徑中斷（如由于節點移動或無線環境惡劣化）時，可以通過路徑維護進程修補之前找到的路徑，也可以重新進行路徑選擇。AODV[1]、DSR[2]以及基于這些協議的衍生協議都屬于上述類型。這些反應式協議要求每個中間節點都需要對某個路由請求報文轉發一次，因此尋徑開銷較大。

現有文獻中，已經有了一些路由方法考慮如何降低反應式路由尋徑過程中產生的協議開銷，具體包括以下幾種類型：

????（1）基于地理位置信息的先應式路由：這類路由協議首先根據信源和信宿所在的地理位置確定一個包含信源和信宿的矩形區域或橢圓形區域，然后在該區域內部尋找路徑，以期在縮小尋徑范圍的基礎上找到鏈接源和宿的路徑。這類方法要求每個節點知道自己的位置信息（如通過裝備GPS接收器），因此增加了額外的成本，通用性不強。

????（2）基于連通支撐集合(Connected?Dominating?Set)的、GAF等)：這些協議首先根據局部拓撲知識或地理位置信息，構造一個基礎性的網絡連通支撐結構，然后通過處在這一結構之上的節點轉發路由請求報文，尋找端到端路徑，并降低尋徑開銷。這類方案或者需要預先交互相鄰狀態信息（如CEDAR）或者要求節點具備位置信息。前者開銷大，后者要求額外的位置設備信息。

（3）基于概率的方式轉發：基于滲透理論（percolation?theory），即：對于一個無線網絡，如果信源廣播一個分組后，每個中間節點以概率p轉發一個廣播報文，那么如果p的值足夠大，那么全網節點會以較高的概率全部或絕大部分收到該分組。已有基于GOSSIP的尋徑方法是各向同性的，或尋徑范圍限制在以源和宿為焦點、以幾何距離為焦距的橢圓范圍之內。

上述方案雖然可以降低尋徑開銷，但前者浪費較為嚴重，因為尋徑消息是向網絡中各個方向以同等的概率擴散的；而后者路徑擴散具有定向性，但要求節點具備額外位置信息。

發明內容

本發明面向無線自組織網絡，主要設計目的是降低尋找連接信源和信宿過程中所消耗的信令開銷。

本發明中的路由方法針對下述無線自組織網絡：每個節點配備各項同性的無線天線；節點具有移動性；當兩個節點在相互無線通信范圍時，兩者可以直接通信，否則不能直接通信；節點不知道自身的位置信息。

本發明充分利用已經中斷的舊路徑信息，結合基于概率的路由發現方法，有效地控制尋徑的范圍，降低尋徑開銷，并保持較高的路徑質量。具體來說：只有距離舊路徑一定距離內（K跳以內）的中間節點參與路徑恢復，其中處在舊路徑上的節點以概率1參與，上述范圍內的其它節點以概率p*參與轉發路由請求報文。

如果當前尋徑或重尋徑一次廣播RREQ即成功找到端到端路徑，那么則降低路由請求報文轉發概率和尋徑范圍，并應用到下一次重尋徑中去；否則直接將本次尋徑的路由請求報文轉發概率和尋徑范圍直接用于下一次重尋徑進程中去。

對于持續時間較長的通信會話，本發明的方法能夠非常有效地降低通信開銷。

具體實施方式

????本發明的路由方案如下：

????路由包括路由發現和路由維護兩個階段：

????路由發現過程（Route?Discovery）如下：