[發明專利]一種網狀網中環路路徑的查找方法及裝置

有效

• 申請號: 201010140691.7
• 申請日: 2010-03-26
• 公開（公告）號: CN101827414A
• 公開（公告）日: 2010-09-08
• 發明（設計）人: 喻磊
• 申請（專利權）人: 中興通訊股份有限公司
• 主分類號: H04W40/02
• 分類號: H04W40/02;H04W84/18
• 代理公司: 北京市浩天知識產權代理事務所 11276
• 代理人: 劉云貴

技術領域

本發明涉及網絡領域，更具體的涉及一種網狀網中環路路徑的查找方法 及裝置。

背景技術

首先，環路路徑是指在Mesh(網狀)網G(V，E)中的一條連通性路徑P＝[v ₁，v₂，……v_n，v₁](n≥3)，路徑中除首尾節點外，其他節點各不相同。此 路徑又叫做節點v1的一條環路路徑。

傳統的環路路徑的計算方法，則路徑p＝[v₁，v_m，v_n，v₁]為節點v₁的一條環路路徑。否則傳統的環路路徑計算方法采取遞歸遍歷的方式，其 Mesh網圖見圖1，計算v1的環路路徑，其流程圖如圖2所示：

第一步：查找與v₁相鄰的所有節點v_m，v_m＝{v∈V|(v₁，v)∈E}；

第二步：記錄v₁與相鄰節點的路徑信息；查找所有與v_m相鄰的所有節 點v_n，v_n＝{v∈V|(v_m，v)∈E}；

第三步：檢查v₁是否與v_n相鄰，如果是相鄰的節點，則找到節點v₁的一條環路路徑p＝[v₁，vm，vn，v₁]。否則重復第二步。

其中，要查找出節點v₁的所有環路徑，時間復雜度≥O(Kn³)(n為Mesh 網中的節點數)，當前的傳統方法存在查找環路路徑的效率較低的問題。

發明內容

本發明所要解決的技術問題是提供一種網狀網中環路路徑的查找方法 及裝置，解決了當前的傳統方法存在查找環路路徑的效率較低的問題，提高 了環路路徑查找的效率。

為了解決上述問題，本發明提供了一種網狀網中環路路徑的查找方法， 包括：

網絡側查找所述網狀Mesh網中與節點v₁相鄰的所有節點，在所述 Mesh網中將節點v₁和與其直接連接的節點形成的所有邊刪除；

所述網絡側對得到的與節點v₁相鄰的所有節點通過K優路徑算法進行 計算，得到與所述節點v₁相鄰的所有節點之間的所有路徑；

所述網絡側遍歷得到的所述與節點v₁相鄰的所有節點之間的所有路 徑，在每條路徑的起始處和終止處添加節點v₁，完成在Mesh網中查找節點 v₁的所有環路路徑。

進一步地，上述方法還可包括，所述網絡側計算后得到的與所述節點v ₁相鄰的所有節點之間的所有路徑的起始節點和終止節點不同，且都是所述 節點v₁的相鄰節點。

進一步地，上述方法還可包括，所述網絡側查找所述Mesh網中與節點 v₁相鄰的所有節點后，還包括通過存儲裝置對得到的與節點v₁相鄰的所有 節點的信息進行存儲。

進一步地，上述方法還可包括，所述網絡側得到與所述節點v₁相鄰的 所有節點之間的所有路徑后，還包括通過存儲裝置對得到的與節點v₁相鄰 的所有節點之間的所有路徑的信息進行存儲。

進一步地，上述方法還可包括，所述網絡側完成在Mesh網中查找節點 v₁的所有環路路徑后，還包括通過存儲裝置對得到的節點v₁的環路路徑的 信息進行存儲。

本發明還提供了一種網狀網中環路路徑的查找裝置，包括查找節點模 塊、計算模塊和環路路徑搜尋模塊，其中，

所述查找節點模塊，用于查找所述網狀Mesh網中與節點v₁相鄰的所 有節點，在所述Mesh網中將節點v₁和與其直接連接的節點形成的所有邊 刪除，并將得到的與節點v₁相鄰的所有節點的信息發送給所述計算模塊；