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

有效

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

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

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

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

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

遍歷路由路徑集S中所有的路徑，對每條路由路徑R，都進行如下步驟：

對于路由路徑R，從其相應的序列表中，依次取出節點nodey[nodenodenumber-1,nodenodenumber-2...node1];]]>

如果當前的A[node_y，node_y+1]的記錄表明節點node_y與節點node_y+1沒有直接連接，說明連接<node_y，node_y+1>是一條新路徑，更新A[node_y，node_y+1]的值，A[node_y，node_y+1]的值表示節點node_y與節點node_y+1之間的直接連接與間接連接情況，按照定義要求對其值進行更新，并設置更新標志；否則該路徑已經進行了記錄，不需要進行更新；

路由路徑中node_z∈[node₁，node_y-1]，節點node_z到節點node_y+1不是直接，但存在著間接連接，即節點node_z到node_y+1可以通過其它節點到達，則對于的所有間接連接<node_z，node_y+1>，首先判定A[node_z，node_z+1]是否有直接連接，如果沒有，說明節點node_z到節點node_y+1的間接連接為新的連接，保持更新標志為真，否則更新標志為否；如果更新標志為否，就不對以后的間接連接：A[node_z，node_y+1]進行更新，遍歷生成所有以節點node_y+1為終點的間接連接后，對路由路徑R的處理結束；

反復進行對路由路徑集S循環操作，直到循環結束，就生成了直接/間接鄰接矩陣A[i，j]；

步驟3，基于鄰接矩陣A[i，j]，計算目標節點的保護路由：

對于一條給定的路由路徑R，在判定其是否受保護時，首先構造節點集S′={node1,node2,......nodenodenumber-1,};]]>

從節點集S′中依次取出節點

如果則節點node_y受保護，否則判斷節點node_y到節點node_y+1是否受保護：如果A[node_y，node_y+1]＜2，則節點node_y到節點node_y+1原來沒有任何一條間接邊，節點node_y不受到保護，則該路由路徑不是保護路由；當node_y被保護時，將其從節點集S′中去除，同時去除節點集S′中具有到node_y+1有兩條間接連接路由的節點node_z，如果節點集S′為空，則路由路徑R為保護路由；

反復進行循環操作，直到循環結束；

如果節點集S′中所有節點都滿足到其后的一個節點具有一條以上的連接，則說明所有節點都是受到保護的，根據此算法找到的路由即為保護路由。