一種網狀網中環路路徑的查找方法及裝置的製作方法

2023-05-01 18:49:21

專利名稱：一種網狀網中環路路徑的查找方法及裝置的製作方法
技術領域：
本發明涉及網絡領域，更具體的涉及一種網狀網中環路路徑的查找方法及裝置。
背景技術：
首先，環路路徑是指在Mesh(網狀)網G(V，Ε)中的一條連通性路徑P = [ν1 V2,……vn，V1] (η彡3)，路徑中除首尾節點外，其他節點各不相同。此路徑又叫做節點Vl 的一條環路路徑。傳統的環路路徑的計算方法，則路徑ρ = [V1, Vffl, vn, V1]為節點V1的一條環路路 徑。否則傳統的環路路徑計算方法採取遞歸遍歷的方式，其Mesh網圖見圖1，計算vl的環 路路徑，其流程圖如圖2所示第一步查找與V1相鄰的所有節點Vm，Vffl = {ν e ν (V1, ν) e Ε}；第二步記錄V1與相鄰節點的路徑信息；查找所有與Vm相鄰的所有節點vn，Vn = {ν e V (vm, ν) e Ε}；第三步檢查V1是否與Vn相鄰，如果是相鄰的節點，則找到節點V1的一條環路路 徑P = [V1, vm, vn, V1]。否則重複第二步。其中，要查找出節點V1的所有環路徑，時間複雜度彡0 (Κη3) (η為Mesh網中的節點 數)，當前的傳統方法存在查找環路路徑的效率較低的問題。

發明內容
本發明所要解決的技術問題是提供一種網狀網中環路路徑的查找方法及裝置，解 決了當前的傳統方法存在查找環路路徑的效率較低的問題，提高了環路路徑查找的效率。為了解決上述問題，本發明提供了一種網狀網中環路路徑的查找方法，包括網絡側查找所述網狀Mesh網中與節點V1相鄰的所有節點，在所述Mesh網中將節 點V1和與其直接連接的節點形成的所有邊刪除；所述網絡側對得到的與節點V1相鄰的所有節點通過K優路徑算法進行計算，得到 與所述節點V1相鄰的所有節點之間的所有路徑；所述網絡側遍歷得到的所述與節點V1相鄰的所有節點之間的所有路徑，在每條路 徑的起始處和終止處添加節點V1,完成在Mesh網中查找節點V1的所有環路路徑。進一步地，上述方法還可包括，所述網絡側計算後得到的與所述節點V1相鄰的所 有節點之間的所有路徑的起始節點和終止節點不同，且都是所述節點V1的相鄰節點。進一步地，上述方法還可包括，所述網絡側查找所述Mesh網中與節點V1相鄰的所 有節點後，還包括通過存儲裝置對得到的與節點V1相鄰的所有節點的信息進行存儲。進一步地，上述方法還可包括，所述網絡側得到與所述節點V1相鄰的所有節點之 間的所有路徑後，還包括通過存儲裝置對得到的與節點V1相鄰的所有節點之間的所有路徑 的信息進行存儲。進一步地，上述方法還可包括，所述網絡側完成在Mesh網中查找節點V1的所有環路路徑後，還包括通過存儲裝置對得到的節點V1的環路路徑的信息進行存儲。本發明還提供了一種網狀網中環路路徑的查找裝置，包括查找節點模塊、計算模 塊和環路路徑搜尋模塊，其中，所述查找節點模塊，用於查找所述網狀Mesh網中與節點V1相鄰的所有節點，在所 述Mesh網中將節點V1和與其直接連接的節點形成的所有邊刪除，並將得到的與節點V1相 鄰的所有節點的信息發送給所述計算模塊；所述計算模塊，用於對得到的與節點V1相鄰的所有節點通過K優路徑算法進行 計算，得到與所述節點V1相鄰的所有節點之間的所有路徑，並發送給所述環路路徑搜尋模 塊；所述環路路徑搜尋模塊，用於遍歷得到的所述與節點V1相鄰的所有節點之間的所 有路徑，在每條路徑的起始處和終止處添加節點V1,完成在Mesh網中查找節點V1的所有環 路路徑。進一步地，上述裝置還可包括，所述計算模塊計算後得到的與所述節點V1相鄰的 所有節點之間的所有路徑的起始節點和終止節點不同，且都是所述節點V1的相鄰節點。進一步地，上述裝置還可包括所述存儲模塊，用於存儲所述查找節點模塊得到的 與節點V1相鄰的所有節點的信息，存儲所述計算模塊得到的與節點V1相鄰的所有節點之間 的所有路徑的信息以及存儲所述環路路徑搜尋模塊得到的節點V1的環路路徑的信息。與現有技術相比，應用本發明，藉助KSP算法(K優路徑算法)，將環路路徑拆分為 兩部分，一部分為相鄰節點之間的路徑，另一部分為相鄰節點到Vl節點的路徑部分，本發 明方法的時間複雜度為所選擇的KSP算法的時間複雜度，解決了當前的傳統方法存在查找 環路路徑的效率較低的問題，提高了環路路徑查找的效率，降低了系統的負載。


圖1是傳統方法計算Vl的環路路徑時的遍歷過程的示意圖；圖2是傳統方法計算Vl的環路路徑的流程圖；圖3是本發明在Mesh網中查找節點vl的環路路徑的流程圖；圖4是本發明的網狀網中環路路徑的查找裝置的結構示意圖；圖5是環路路徑的示意圖；圖6是本發明實例中的一 Mesh網圖，基於該圖進行解釋說明；圖7是本發明實例中計算Vl相鄰節點之間路徑的說明的示意圖；圖8是本發明實例中計算Vl的環路路徑時的遍歷過程的示意圖。
具體實施例方式下面結合附圖和具體實施方式
對本發明作進一步說明。如圖3所示，本發明在Mesh網G(V，E)中查找節點vl的環路路徑，包括如下步驟步驟310 網絡側查找所述Mesh網中與節點vl相鄰的所有節點Vm，在Mesh網中 將節點vl和與其直接連接的節點形成的所有邊刪除；其中，Vm={v G V| (ν ，ν) G E}。網絡側查找所述Mesh網中與節點vl相鄰的所有節點Vm後，還包括通過存儲裝置對得到的與節點Vl相鄰的所有節點的信息進行存儲。步驟320 網絡側對得到的與節點vl相鄰的所有節點通過KSP算法進行計算，得 到與所述節點Vl相鄰的所有節點Vm之間的所有路徑；網絡側得到與所述節點Vl相鄰的所有節點Vm之間的所有路徑後，還包括通過存 儲裝置對得到的與節點Vl相鄰的所有節點Vm之間的所有路徑的信息進行存儲。其中，網絡側得到的所述路徑的起始節點和終止節點不同，且都是節點Vl的相鄰 節點。步驟330 網絡側遍歷得到的所述與節點vl相鄰的所有節點Vm之間的所有路徑， 在每條路徑的起始處和終止處添加節點vl，完成在Mesh網中查找節點vl的所有環路路徑， 並通過存儲裝置對得到的節點vl的環路路徑進行存儲。如圖4所示，一種網狀網中環路路徑的查找裝置，包括查找節點模塊、計算模塊、 環路路徑搜尋模塊和存儲模塊，其中，所述查找節點模塊，用於查找所述網狀Mesh網中與節點vl相鄰的所有節點，在所 述Mesh網中將節點vl和與其直接連接的節點形成的所有邊刪除，並將得到的與節點vl相 鄰的所有節點的信息發送給所述計算模塊；所述計算模塊，用於對得到的與節點Vl相鄰的所有節點通過K優路徑算法進行 計算，得到與所述節點vl相鄰的所有節點之間的所有路徑，並發送給所述環路路徑搜尋模 塊；所述環路路徑搜尋模塊，用於遍歷得到的所述與節點Vl相鄰的所有節點之間的 所有路徑，在每條路徑的起始處和終止處添加節點vl，完成在Mesh網中查找節點vl的所有 環路路徑。所述計算模塊計算後得到的與所述節點Vl相鄰的所有節點之間的所有路徑的起 始節點和終止節點不同，且都是所述節點vl的相鄰節點。所述存儲模塊，用於存儲所述查找節點模塊得到的與節點Vl相鄰的所有節點的 信息，存儲所述計算模塊得到的與節點vl相鄰的所有節點之間的所有路徑的信息以及存 儲所述環路路徑搜尋模塊得到的節點vl的環路路徑的信息。一條環路路徑也可以理解為是一條起始、終止節點相同的路徑。本方法定義節點 vm的環路路徑，即表示在該路徑中以vm作為該路徑的起始、終止節點，可表示為ρ = [vm, vl, ......vn, vm] (η > 2)。參考圖5，vl的一條環路路徑為ρ = [V1，V2，V3，V4，V5，V6，V1]。該路徑可以理解 為由兩部分組成。一部分為vl的相鄰節點(v2,v6)之間的路徑pa = [ν2, ν3, ν4, ν5, ν6], 另一部分為vl與相鄰節點(v2，v6)之間的路徑pb = [vl, v2]和pc = [vl, v6]。那麼所 求的環路路徑就是這兩部分路徑的相加之和P = [vl，v2, v3, v4, v5, v6, vl] = pb+pa+pc。 可將上述思路推廣到一般情況下，即在一個Mesh網G(V，E)中查找某個節點vm的所有環路 路徑。下面結合圖例說明具體的實施過程。如圖6所示，假設要在圖6中尋找節點Vl的 所有環路徑。首先獲得vl的相鄰節點v2，v3，v4，接下來分別計算這三個節點兩兩之間的路徑，推薦使用KSP算法(K優路徑算法)計算兩節點間的所有路徑。計算完畢後，可以得到下面的路徑(見圖7):pl23 = [v2, v5, v6, v7, v3]p223 = [v2, v6, v7, v3]pl24 = [v2, v5, v6, v7, v4]p224 = [v2, v6, v7, v4]pl34 = [v3, v7, v4]又已知vl與相鄰節點v2，v3, v4之間的路徑為pll2 = [vl, v2]pll3 = [vl, v3]pll4 = [vl, v4]把這兩部分相加就得到了 vl的所有環路徑(見圖8):pll = [vl, v2, v5, v6, v7, v3, vl]p21 = [vl, v2, v6, v7, v3, vl]p31 = [vl, v2, v5, v6, v7, v4, vl]p41 = [vl, v2, v6, v7, v4, vl]p51 = [vl, v3, v7, v4, vl]流程結束。以上所述，僅為本發明較佳的具體實施方式
，但本發明的保護範圍並不局限於此，任何熟悉該技術的人在本發明所揭露的技術範圍內，可輕易想到的變化或替換，都應涵蓋 在本發明的保護範圍之內。因此，本發明的保護範圍應該以權利要求的保護範圍為準。
權利要求
一種網狀網中環路路徑的查找方法，其特徵在於，包括網絡側查找所述網狀Mesh網中與節點v1相鄰的所有節點，在所述Mesh網中將節點v1和與其直接連接的節點形成的所有邊刪除；所述網絡側對得到的與節點v1相鄰的所有節點通過K優路徑算法進行計算，得到與所述節點v1相鄰的所有節點之間的所有路徑；所述網絡側遍歷得到的所述與節點v1相鄰的所有節點之間的所有路徑，在每條路徑的起始處和終止處添加節點v1，完成在Mesh網中查找節點v1的所有環路路徑。
2.如權利要求1所述的查找方法，其特徵在於，所述網絡側計算後得到的與所述節點V1相鄰的所有節點之間的所有路徑的起始節點 和終止節點不同，且都是所述節點V1的相鄰節點。
3.如權利要求1所述的查找方法，其特徵在於，所述網絡側查找所述Mesh網中與節點V1相鄰的所有節點後，還包括通過存儲裝置對 得到的與節點V1相鄰的所有節點的信息進行存儲。
4.如權利要求1所述的查找方法，其特徵在於，所述網絡側得到與所述節點V1相鄰的所有節點之間的所有路徑後，還包括通過存儲裝 置對得到的與節點V1相鄰的所有節點之間的所有路徑的信息進行存儲。
5.如權利要求1所述的查找方法，其特徵在於，所述網絡側完成在Mesh網中查找節點V1的所有環路路徑後，還包括通過存儲裝置對 得到的節點V1的環路路徑的信息進行存儲。
6.一種網狀網中環路路徑的查找裝置，其特徵在於，包括查找節點模塊、計算模塊和環路路徑搜尋模塊，其中，所述查找節點模塊，用於查找所述網狀Mesh網中與節點V1相鄰的所有節點，在所述 Mesh網中將節點V1和與其直接連接的節點形成的所有邊刪除，並將得到的與節點V1相鄰 的所有節點的信息發送給所述計算模塊；所述計算模塊，用於對得到的與節點V1相鄰的所有節點通過K優路徑算法進行計算， 得到與所述節點V1相鄰的所有節點之間的所有路徑，並發送給所述環路路徑搜尋模塊；所述環路路徑搜尋模塊，用於遍歷得到的所述與節點V1相鄰的所有節點之間的所有路 徑，在每條路徑的起始處和終止處添加節點V1,完成在Mesh網中查找節點V1的所有環路路 徑。
7.如權利要求6所述的查找裝置，其特徵在於，所述計算模塊計算後得到的與所述節點V1相鄰的所有節點之間的所有路徑的起始節 點和終止節點不同，且都是所述節點V1的相鄰節點。
8.如權利要求6所述的查找裝置，其特徵在於，還包括所述存儲模塊，用於存儲所述查找節點模塊得到的與節點V1相鄰的所有節點的 信息，存儲所述計算模塊得到的與節點V1相鄰的所有節點之間的所有路徑的信息以及存儲 所述環路路徑搜尋模塊得到的節點V1的環路路徑的信息。
全文摘要
本發明公開了一種網狀網中環路路徑的查找方法及裝置，包括網絡側查找所述網狀Mesh網中與節點v1相鄰的所有節點，在所述Mesh網中將節點v1和與其直接連接的節點形成的所有邊刪除；網絡側對得到的與節點v1相鄰的所有節點通過K優路徑算法進行計算，得到與所述節點v1相鄰的所有節點之間的所有路徑；網絡側遍歷得到的所述與節點v1相鄰的所有節點之間的所有路徑，在每條路徑的起始處和終止處添加節點v1，完成在Mesh網中查找節點v1的所有環路路徑。應用本發明，解決了傳統方法存在查找環路路徑的效率較低的問題，提高了環路路徑查找的效率。
文檔編號H04W40/02GK101827414SQ20101014069
公開日2010年9月8日 申請日期2010年3月26日 優先權日2010年3月26日
發明者喻磊 申請人:中興通訊股份有限公司