[發明專利]基于直接/間接矩陣的無線自組織網絡保護路由生成算法

有效

• 申請號: 201210002447.3
• 申請日: 2012-01-06
• 公開（公告）號: CN102573000A
• 公開（公告）日: 2012-07-11
• 發明（設計）人: 林闖;祝林;孟坤
• 申請（專利權）人: 清華大學
• 主分類號: H04W40/24
• 分類號: H04W40/24;H04W84/18
• 代理公司: 西安智大知識產權代理事務所 61215
• 代理人: 賈玉健

技術領域

本發明涉及無線網絡技術領域，適用于無線自組織網絡應用環境下的路由生成及保護，具體涉及一種基于直接/間接矩陣的無線自組織網絡保護路由生成算法。

背景技術

2010年論文《On?the?Feasibility?and?Efficacy?of?Protection?Routing?in?IP?Networks》首次提出了路由保護(protection?routing)的概念，在IP網絡單點失效時確保整個路由轉發還能保持正常，但其提出的路由保護算法無法應用于無線網絡環境，因此路由保護功能無法應用于無線網絡環境。本發明針對無線網絡的特點，在基于傳統的AODV路由協議的基礎上，構建了適用于無線環境的保護路由協議，在獲取路由路徑基礎上生成直接/間接連接矩陣，并基于直接/間接連接矩陣創新性的提出了無線保護路由算法設計，有效保證了保護路由在無線網絡中的廣泛應用。

無線自組網按需平面距離矢量路由協議(Ad?hoc?On-Demand?Distance?Vector?Routing，AODV)是應用于無線Ad?hoc網絡中進行路由選擇的路由協議。具體來說，其是一種反應式路由協議，需要向目標節點發送數據時，源節點才在網絡中發起路由查找過程，找到相應的路由。而很多其它路由協議都是先驗式的，也就是說它們查找路由是不依賴于路徑上的節點是否要發包，而是每個節點維護一張包含到達其它節點的路由信息的路由表，節點間通過周期性的交換路由信息來不斷更新自身的路由表，以便能夠及時的反映網絡拓撲結構和變化，以維護一致的、及時的、準確的路由信息。不同于先驗式的路由協議，AODV路由協議是一種平面距離矢量路由協議。

在AODV中，一個網絡節點需要建立連接時才廣播一個連接建立的請求，其他的AODV節點轉發這個請求消息，并記錄源節點和回到源節點的臨時路由。當接收連接請求的節點知道到達目標節點的路由時，就把這個路由信息按照先前記錄的回到源節點的臨時路由發回源節點。源節點就開始使用這個經由其他節點并且有最短跳數的路由。當鏈路出現節點故障時，路由錯誤就被回送給源節點，于是源節點就重新發起路由查找的過程。

在發生單個節點失效后，會由源節點重新發起路由請求，重新找尋一條新的路由路徑。由于AODV路由協議在單個路由節點的失效時無法再保持正常通信，因此為了有效保障在單個節點失效時無線自組織網絡還能正常通信，我們引入了保護路由功能。首先給出相關概念，節點被保護的定義：節點s在目標節點為節點d的路徑中，如果節點s的下一節點出現故障，這時還可以找到第二下一跳節點k(secondary?next-hop，簡稱SNH)到達目標節點d，那么稱該節點s對于節點d是被保護的。從被保護節點概述得到保護路由的定義：一條路由的所有節點都是被保護的，那么這條路由就是保護路由。

路由保護原始應用場景為具有中心節點的IP網絡，即網絡中有一個中心節點能獲取整個網絡的拓撲情況，從而進行相關路由計算，而無線網絡中不存在中心節點感知全局拓樸，故無法應用其算法進行保護路由的生成；同時原算法還存在算法效率問題，基于目前的算法生成針對全網的保護路由，算法開銷太大，也不適合無線環境。

發明內容

為了克服上述現有技術的不足，本發明的目的在于提供了一種基于直接/間接矩陣的無線自組織網絡保護路由生成算法，將保護路由功能應用到無線自組織網絡應用環境，從而有效提高了無線路由傳輸的可靠性，使得采用該算法的無線自組織網絡具有在單個節點失效情況下保持正常數據傳輸的能力，極大提高了無線自組織網絡的傳輸可靠性，并且算法易于實現、算法復雜度低。

為了實現上述目的，本發明采用的技術方案是：

于直接/間接矩陣的無線自組織網絡保護路由生成算法，包括以下步驟：

步驟1，基于AODV擴展的路由協議獲取路由路徑R：

在原始的AODV中加入定義為路由請求分組所經過節點的序列表的字段，如果路由請求經過節點B轉發時，節點B就將自己的IP地址寫入該序列表，在路由請求開始發送時默認經過節點的序列表為空，當跳計數加一時同時將轉發節點B加入序列中；任一中間節點對其接收到的每個路由請求分組，首先檢查自己是否在所述序列表中，如果已經存在，則將該路由請求分組丟棄，如果不存在，則轉發該路由請求分組；目標節點收到從源節點發出的大量路由請求分組，每個路由請求分組中都包含了其經過的節點記錄，形成了相應的路由路徑R，目標節點將所有的路由路徑R保存起來，就形成了路由路徑集S；

步驟2，目標節點生成直接/間接鄰接矩陣A[i，j]：