一種兩點間或者多點間的多線程網絡智能選徑方法
2023-04-27 22:52:06
專利名稱：一種兩點間或者多點間的多線程網絡智能選徑方法
技術領域：
本發明涉及一種網絡智能選徑方法，尤其涉及一種兩點間或者多點間的多線程網 絡智能選徑方法。
背景技術：
據專利申請號為200810021101. 1的《一種求網絡最短路徑的商空間覆蓋模型及 其構建方法》中技術背景的提及和實際情況。對於交通網絡、電力網絡及信息傳輸網絡(如 網際網路)，現在的兩點間最短路徑搜索方法還是以Dijkstra算法為主。雖然，通過Dijkstra 算法已可獲得最短路徑，但對於線路複雜的網絡，其運算時間會以幾何級數遞增或佔用巨 量內存。而通常線路複雜的網絡都是動態網絡，其處理時間又決定其跟蹤的精度，故現有的 網絡選經方法的精度都較差。發明內容
針對現有技術的缺點，本發明的目的是提供一種處理時間較短、精度較高的兩點 間或者多點間的多線程網絡智能選徑方法。
為實現上述目的，本發明的技術方案為一種兩點間的多線程網絡智能選徑方法， 其包括以下步驟
a.按照網絡的拓撲結構建立電子網絡拓撲結構圖，對結構圖各邊及各節點進行 編號，且每一節點均連接有一節點寄存器，節點寄存器上設有存儲位、信號識別位及量記錄 位；
b.定義結構圖上需尋徑的兩點01、02，由兩點輸入信號，兩信號分別沿電子網絡 拓撲結構圖傳輸，形成兩信號樹，當其中任一信號樹中的信號經過某一邊或某些邊後最先 到達某一節點時，該節點的節點寄存器存儲位記錄下該邊或該些邊的編號；
c.當信號識別位識別到兩信號第一次分別觸發兩相鄰節點A、B時，假設從信號的 輸入點01、02分別到節點A、B所用的時間量分別為a、b，此兩點間的邊的時間量設為x，則 以(x-|a-b|)/2為範圍界限，在此界限內繼續搜索這兩信號所觸發的其他兩相鄰節點；
d.將L減去繼續尋徑觸發其他兩相鄰節點所花費的時間量所得到的結果，與在後 兩相鄰節點間的邊的時間量作比較，保留較小的時間量並繼續重複以上步驟的比較，直至 在先兩相鄰節點對應的時間量減去繼續尋徑所花費時間量的值為零時止，保留的量所對應 的邊及記錄下與其連接的邊為兩點間最短的路徑。
步驟b中，各邊末端連接有用於調節各邊信號傳輸時間的脈衝計數觸發器，脈衝 計數觸發器的觸發輸出端連接對應的節點寄存器；
當信號到達邊末端的脈衝計數觸發器時，脈衝計數觸發器開始計算信號的脈衝 數，在脈衝數達到設定的觸發數時，脈衝計數觸發器觸發，並向下一節點輸出信號，節點寄 存器記錄對應邊的編號。
通過調節對應的邊末端脈衝計數觸發器的脈衝觸發數或輸入信號的頻率，以調節邊間信號的傳輸時間；通過在邊上串接可控開關元件，實現對邊的通斷進行控制。
步驟b中，各邊上連接有一定數量的阻抗值相同的可控電器元件，每一個可控電 器元件通過開關元件與電源連接，邊末端連接單向電壓觸發單元；
由起點輸入信號，信號經過邊上的可控電器元件，到達邊末端的單向電壓觸發單 元，經電荷的積累，到達閥值，單向電壓觸發單元觸發；分別輸出信號到節點寄存器記錄邊 的編號，及向相連的邊繼續輸出信號。
步驟b中，各邊上連接有阻抗值可變的可控電器元件，邊末端連接單向電壓觸發 單元，通過設置可控電器元件的阻抗大小或單向電壓觸發單元的觸發閥值，來調節觸發閥 值電壓的集電時間，以調節邊間信號的傳輸時間；通過在邊上串接可控開關元件，實現對邊 的通斷進行控制。
步驟d中，保留次最小的量所對應的邊及記錄下與其連接的邊為兩點間次最短的 路徑，該次最短的路徑作為第一條後備路徑，重複以上步驟，根據保留時間量的大小，就在 有向網絡中獲得多條後備路徑。
進一步地，本發明提供了一種兩點間的多線程網絡智能選徑方法，其包括以下步 驟
a.按照網絡的拓撲結構建立電子網絡拓撲結構圖，對結構圖各邊及各節點進行編 號，且每一節點均連接有一節點寄存器；
b.定義結構圖上需尋徑的兩點，由兩點輸入信號，兩信號分別沿電子網絡拓撲結 構圖傳輸，形成兩信號樹，當其中任一信號樹中的信號經過某一邊或某些邊後最先到達某 一節點時，該節點的節點寄存器記錄下該邊或該些邊的編號；
c.各節點上設有檢測分別被不同的信號觸發的信號檢測裝置，並根據檢測到的最 先觸發的兩信號，追溯各自經過節點寄存器記錄的邊的編號，從而獲得兩點間的信號傳輸 時間最短的路徑。
進一步地，本發明基於兩點間的多線程網絡智能選徑方法，提供了一種多點間的 多線程網絡智能選徑方法，其中，在無向網絡中，電子網絡拓撲結構圖上定義需尋徑的多個 點，多點同時生成多個信號樹，尋徑系統根據所述的兩點間的多線程網絡智能選徑方法，記 錄每個點與最近點的最短路徑，在每個點都獲得與最近點的最短路徑時，即得出多點間的 最短路徑。
進一步地，本發明基於兩點間的多線程網絡智能選徑方法，提供了一種多點間的 多線程網絡智能選徑方法，其中，在無向網絡中，電子網絡拓撲結構圖上定義需尋徑的多個 點，以其中任一點為起點，根據所述的兩點間的多線程網絡智能選徑方法，同時尋找該起點 到所選其它點的最短路徑，然後依次以其他點作為起點，重複以上選徑方法，得到多條路 徑，在這些路徑上執行最小樹生成算法，生成最小樹，從而得到多點間的最短路徑。
進一步地，本發明提供了一種多點間的多線程網絡智能選徑方法，其包括以下步 驟a.按照網絡的拓撲結構建立有向電子網絡拓撲結構圖，對結構圖各邊及各節點進行編 號，且每一節點均連接有一節點寄存器；
b.定義結構圖上選取需尋徑的多個點，以其中任一點為起點輸入信號，並形成一 信號樹，當信號經過某一邊後最先到達某一節點時，該節點的節點寄存器記錄下該邊或該 些邊的編號；c.信號再根據網絡拓撲結構沿能傳輸方向向下一節點放射傳輸，直至所選其他點獲得信號；d.追溯其經過節點寄存器記錄的邊的編號，從而獲得該起點到所選其它點 的信號傳輸時間最短的路徑；e.然後依次以其他點作為起點，重複以上選徑方法，得到多 條路徑，在這些路徑上執行帶方向的I^rim算法，其中只選取與起點信號同向的方向，生成 最小樹，從而得到多點間的最短路徑。
與現有技術相比，本發明具有如下有益效果
本發明的尋徑方法是以量為尺度，評測路徑，即邊的優劣，淘汰非最短路徑。由於 尋徑過程無實數運算，且尋徑方式以多線程同時進行，不需考察所有點的路徑，所以它比 Dijkstra尋徑方式更快。且量權比(在同一弧上的量與權值之比)可作為調節閥，(在量 的單位不變的情況下)對於特大網絡可以降低精度為代價提高處理速度，達到要求精度與 處理速度的動態平衡，從而適應各種不同的網絡。另外，單位量還可與其它網絡的不同考察 量置換，以獲得針對此網絡的最優解決方法。這比A*算法適應力更強、處理速度更快。
本發明提出了兩點的選徑方法，其相對單點選徑而言，其選徑時間縮小了一半，大 大提高了選徑時間及處理速度。
本發明也提出了多點的選徑方法，通過多點同時進行尋徑，達到了在網絡中更快 速地實現使用繁雜的複合算法才能達到的效果，體現出協作的優勢。
圖1為本發明兩點間的多線程網絡智能選徑方法的結構示意圖2為本發明多點間的多線程網絡智能選徑方法的結構示意圖。
具體實施方式
以下結合附圖對本發明進行詳細的描述。
實施例1
本實施例提供了一種兩點間的多線程網絡智能選徑方法，其包括以下步驟
a.按照網絡的拓撲結構建立電子網絡拓撲結構圖，對結構圖各邊及各節點進行 編號，且每一節點均連接有一節點寄存器，節點寄存器上設有存儲位、信號識別位及量記錄 位；
b.如圖1所示，定義結構圖上需尋徑的兩點01、02，由兩點輸入信號，兩信號分別 沿電子網絡拓撲結構圖傳輸，形成兩信號樹，當其中任一信號樹中的信號經過某一邊或某 些邊後最先到達某一節點時，該節點的節點寄存器存儲位記錄下該邊或該些邊的編號；
c.當信號識別位識別到兩信號第一次分別觸發兩相鄰節點A、B時，假設從信號的 輸入點01、02分別到節點A、B所用的時間量分別為a、b，此兩點間的邊的時間量設為x，則 以(x-|a-b|)/2為範圍界限，在此界限內繼續搜索這兩信號所觸發的其他兩相鄰節點；
d.將L減去繼續尋徑觸發其他兩相鄰節點所花費的時間量所得到的結果，與在後 兩相鄰節點間的邊的時間量作比較，保留較小的時間量並繼續重複以上步驟的比較，直至 在先兩相鄰節點對應的時間量減去繼續尋徑所花費時間量的值為零時止，保留的量所對應 的邊及記錄下與其連接的邊為兩點間最短的路徑。
步驟b中，各邊末端連接有用於調節各邊信號傳輸時間的脈衝計數觸發器，脈衝 計數觸發器的觸發輸出端連接對應的節點寄存器；當信號到達邊末端的脈衝計數觸發器時，脈衝計數觸發器開始計算信號的脈衝數，在脈衝數達到設定的觸發數時，脈衝計數觸發 器觸發，並向下一節點輸出信號，節點寄存器記錄對應邊的編號。
通過調節對應的邊末端脈衝計數觸發器的脈衝觸發數或輸入信號的頻率，以調節 邊間信號的傳輸時間；通過在邊上串接可控開關元件，實現對邊的通斷進行控制。
對於邊權值變動的動態網絡，可調節對應的邊末端脈衝計數觸發器的脈衝觸發數 或輸入脈衝信號的頻率，以達到對此動態網絡的跟蹤。而對於網絡拓撲結構不定的動態網 絡，可在邊上串接開關元件，如開關三極體，控制此邊的通斷，從而實現對此類網絡的跟蹤。 其中，權值就是定義的邊上的值，為節點間的距離或走完節點間的路徑所花的時間。
步驟b中，各邊上還可以為連接有一定數量的阻抗值相同的可控電器元件，每一 個可控電器元件通過開關元件與電源連接，邊末端連接單向電壓觸發單元；由其中一點輸 入信號，信號經過邊上的可控電器元件，到達邊末端的單向電壓觸發單元，單向電壓觸發單 元經電荷的積累，到達閥值，觸發器觸發；分別輸出信號到節點寄存器記錄邊的編號，及向 相連的邊繼續輸出信號。本實施例中，所述可控電器元件為可控PN結，開關元件為開關PN 結，單向電壓觸發單元為單向階躍二極體與可控矽連接所組成的單元或為施密特觸發器。
步驟b中，各邊上連接有阻抗值可變的可控電器元件，每一個可控電器元件通過 開關元件與電源連接，邊末端連接單向電壓觸發單元。該可控電器元件為可控電位器。
通過設置可控電器元件的阻抗大小，調節邊的權值，或單向電壓觸發單元的觸發 閥值，調節觸發閥值電壓的集電時間，以調節邊間信號的傳輸時間。
通過在邊上串接可控開關元件，實現對邊的通斷進行控制。
以其中一點釋放信號，信號立即經過邊上的可控電器元件，沿可傳輸方向到達邊 末端的單向電壓觸發單元，該可傳輸方向由可控開關電器元件控制。經電荷的積累，電荷到 達閥值，單向電壓觸發單元觸發；分別輸出信號到節點寄存器記錄邊的編號，及向相連的邊 繼續輸出與信號釋放點相同的信號。重複以上過程，直到另外一點獲得信號。由於信號經 過的節點都寄存了信號來源的路徑，所以追溯其經過節點寄存器記錄的路徑就獲得最優路 徑。
對於邊權值變動的動態網絡，可調節對應邊上可控電器元件的總阻抗值大小，或 單向電壓觸發單元的觸發閥值，從而調節觸發閥值電壓的集電時間，達到對此動態網絡的 跟蹤。對於網絡拓撲結構不定的動態網絡，可通過控制可控開關元件，對弧的方向、邊的通 斷進行控制，從而實現對此類網絡的跟蹤。
在上述步驟d中，保留次最小的量所對應的邊及記錄下與其連接的邊為兩點間次 最短的路徑，該次最短的路徑作為第一條後備路徑，重複以上步驟，根據保留時間量的大 小，就在有向網絡中獲得多條後備路徑。
實施例2
本實施例提供了另外一種兩點間的多線程網絡智能選徑方法，其包括以下步驟
a.按照網絡的拓撲結構建立電子網絡拓撲結構圖，對結構圖各邊及各節點進行編 號，且每一節點均連接有一節點寄存器；
b.定義結構圖上需尋徑的兩點，由兩點輸入信號，兩信號分別沿電子網絡拓撲結 構圖傳輸，形成兩信號樹，當其中任一信號樹中的信號經過某一邊或某些邊後最先到達某 一節點時，該節點的節點寄存器記錄下該邊或該些邊的編號；
c.各節點上設有檢測分別被不同的信號觸發的信號檢測裝置，並根據檢測到的最 先觸發的兩信號，追溯各自經過節點寄存器記錄的邊的編號，從而獲得兩點間的信號傳輸 時間最短的路徑。
此種方法中，不同的起點輸入不同的信號。信號到達節點，觸發節點寄存器後可直 接輸出輸入信號，同一信號樹的信號統一。這時只需在各節點上加信號檢測裝置，可為電平 檢測或檢波裝置，當節點被不同的信號觸發後，檢測信號的衝突，再追溯造成衝突的兩信號 各自經過節點寄存器記錄的邊的編號，以確定最短路徑。
實施例3
本實施例基於兩點間的多線程網絡智能選徑方法上，提供了一種多點間的多線程 網絡智能選徑方法，其中，在無向網絡中，電子網絡拓撲結構圖上定義需尋徑的多個點，這 裡的多點指的是大於或等於三點，本實施例為5個點，如圖2所示，為A、B、C、D、E，根據最小 樹生成算法，如Kruska 1算法，多點同時生成多個信號樹，尋徑系統根據所述的兩點間的多 線程網絡智能選徑方法，記錄每個點與最近點的最短路徑，在每個點都獲得與最近點的最 短路徑時，即得出多點間的最短路徑。
實施例4
本實施例基於兩點間的多線程網絡智能選徑方法上，提供了一種多點間的多線 程網絡智能選徑方法，其中，在無向網絡中，電子網絡拓撲結構圖上定義需尋徑的多個點， 以其中任一點為起點，根據所述的兩點間的多線程網絡智能選徑方法，同時尋找該起點到 所選其它點的最短路徑，有N-I條，然後依次以其他點作為起點，重複以上選徑方法，得到 N* (N-I) /2條路徑，在這些路徑上執行最小樹生成算法，如Kruskal算法，生成最小樹，從而 得到多點間的最短路徑。
實施例5
本實施例基於兩點間的多線程網絡智能選徑方法上，提供了一種多點間的多線程 網絡智能選徑方法，其中，在有向網絡中，電子網絡拓撲結構圖上定義需尋徑的多個點，其 有以下幾種情況
1、所選的點中有一個點的入度為零(信號只出不進)。
這個入度為零的點，就是尋徑的起點。根據最小樹生成算法，如I^rim算法，從起 點向電子拓撲網絡輸出信號，(除輸出點外)到第一獲得信號的所選點，就是第一段最短路 徑。再從已經獲得信號的所選點(包括起點)同時輸出信號，同樣(除輸出點外)到第一 獲得信號的所選點，就是第二段最短路徑。如果所選點數為N，則重複以上步驟N-I次就得 出以上情況的最短路徑。
2、所選的點中有不止一個點的入度為零。這樣就不存在最短路徑。
3、所選的點中沒有一個點的入度為零。
由於所有所選點之間都可構成迴路，若所選點數為N，則起點可有N種情況。
a、根據不同的起點，重複第1點所述的尋徑步驟。獲得N個最小樹後，比較所有最 小樹所含的總量，選擇最少量的樹。這樣就可找出最短路徑了。
b、直接以其中任一點為起點，根據所述的兩點間的多線程網絡智能選徑方法，同 時尋找同一起點到所選其它點的最短路徑，有N-I條，然後依次以其他點作為起點，重複以 上選徑方法，得到N* (N-I)條路徑，在這些路徑上執行帶方向的I^rim算法，其中只選取與起點信號同向的方向，生成最小樹，從而得到多點間的最短路徑。上述的有向網絡通過在無向 網絡中的各邊上串接用於限制信號傳輸方向的限流元件實現。該限流元件可為限流二極體。
這種方法在網絡運營決策中更具有實用意義，是Dijkstra與Kruskal或I^rim算 法方式不可比擬的。
權利要求
1.一種兩點間的多線程網絡智能選徑方法，其特徵在於包括以下步驟a.按照網絡的拓撲結構建立電子網絡拓撲結構圖，對結構圖各邊及各節點進行編號， 且每一節點均連接有一節點寄存器，節點寄存器上設有存儲位、信號識別位及量記錄位；b.定義結構圖上需尋徑的兩點01、02，由兩點輸入信號，兩信號分別沿電子網絡拓撲 結構圖傳輸，形成兩信號樹，當其中任一信號樹中的信號經過某一邊或某些邊後最先到達 某一節點時，該節點的節點寄存器存儲位記錄下該邊或該些邊的編號；c.當信號識別位識別到兩信號第一次分別觸發兩相鄰節點A、B時，假設從01到達A及 02到達B所用的時間量分別為a、b，此兩點間的邊的時間量設為X，則以L = (x-|a-b|)/2 為範圍界限，在此界限內繼續搜索這兩信號所觸發的其他兩相鄰節點；d.將L減去繼續尋徑觸發其他兩相鄰節點所花費的時間量所得到的結果，與在後兩相 鄰節點間的邊的時間量作比較，保留較小的時間量並繼續重複以上步驟的比較，直至在先 兩相鄰節點對應的時間量減去繼續尋徑所花費時間量的值為零時止，保留的量所對應的邊 及記錄下與其連接的邊為兩點間最短的路徑。
2.根據權利要求1所述的兩點間的多線程網絡智能選徑方法，其特徵在於步驟b中， 各邊末端連接有用於調節各邊信號傳輸時間的脈衝計數觸發器，脈衝計數觸發器的觸發輸 出端連接對應的節點寄存器；當信號到達邊末端的脈衝計數觸發器時，脈衝計數觸發器開始計算信號的脈衝數，在 脈衝數達到設定的觸發數時，脈衝計數觸發器觸發，並向下一節點輸出信號，節點寄存器記 錄對應邊的編號。
3.根據權利要求2所述的兩點間的多線程網絡智能選徑方法，其特徵在於通過調節 對應的邊末端脈衝計數觸發器的脈衝觸發數或輸入信號的頻率，以調節邊間信號的傳輸時 間；通過在邊上串接可控開關元件，實現對邊的通斷進行控制。
4.根據權利要求1所述的兩點間的多線程網絡智能選徑方法，其特徵在於步驟b中， 各邊上連接有一定數量的阻抗值相同的可控電器元件，每一個可控電器元件通過開關元件 與電源連接，邊末端連接單向電壓觸發單元；由起點輸入信號，信號經過邊上的可控電器元件，到達邊末端的單向電壓觸發單元，經 電荷的積累，到達閥值，單向電壓觸發單元觸發；分別輸出信號到節點寄存器記錄邊的編 號，及向相連的邊繼續輸出信號。
5.根據權利要求1所述的兩點間的多線程網絡智能選徑方法，其特徵在於步驟b中， 各邊上連接有阻抗值可變的可控電器元件，邊末端連接單向電壓觸發單元，通過設置可控 電器元件的阻抗大小或單向電壓觸發單元的觸發閥值，來調節觸發閥值電壓的集電時間， 以調節邊間信號的傳輸時間；通過在邊上串接可控開關元件，實現對邊的通斷進行控制。
6.根據權利要求1所述的兩點間的多線程網絡智能選徑方法，其特徵在於步驟d中， 保留次最小的量所對應的邊及記錄下與其連接的邊為兩點間次最短的路徑，該次最短的路 徑作為第一條後備路徑，重複以上步驟，根據保留時間量的大小，就在有向網絡中獲得多條 後備路徑。
7.一種兩點間的多線程網絡智能選徑方法，其特徵在於包括以下步驟a.按照網絡的拓撲結構建立電子網絡拓撲結構圖，對結構圖各邊及各節點進行編號， 且每一節點均連接有一節點寄存器；b.定義結構圖上需尋徑的兩點，由兩點輸入信號，兩信號分別沿電子網絡拓撲結構圖 傳輸，形成兩信號樹，當其中任一信號樹中的信號經過某一邊或某些邊後最先到達某一節 點時，該節點的節點寄存器記錄下該邊或該些邊的編號；c.各節點上設有檢測分別被不同的信號觸發的信號檢測裝置，並根據檢測到的最先觸 發的兩信號，追溯各自經過節點寄存器記錄的邊的編號，從而獲得兩點間的信號傳輸時間 最短的路徑。
8.一種多點間的多線程網絡智能選徑方法，其特徵在於包括以下步驟a.按照網絡的拓撲結構建立有向電子網絡拓撲結構圖，對結構圖各邊及各節點進行編 號，且每一節點均連接有一節點寄存器；b.定義結構圖上選取需尋徑的多個點，以其中任一點為起點輸入信號，並形成一信號 樹，當信號經過某一邊後最先到達某一節點時，該節點的節點寄存器記錄下該邊或該些邊 的編號；c.信號再根據網絡拓撲結構沿能傳輸方向向下一節點放射傳輸，直至所選其他點獲得 信號；d.追溯其經過節點寄存器記錄的邊的編號，從而獲得該起點到所選其它點的信號傳輸 時間最短的路徑；e.然後依次以其他點作為起點，重複以上選徑方法，得到多條路徑，在這些路徑上執行 帶方向的I^rim算法，其中只選取與起點信號同向的方向，生成最小樹，從而得到多點間的 最短路徑。
9.一種多點間的多線程網絡智能選徑方法，其特徵在於在無向網絡中，電子網絡拓 撲結構圖上定義需尋徑的多個點，多點同時生成多個信號樹，尋徑系統根據權利要求1所 述的兩點間的多線程網絡智能選徑方法，記錄每個點與最近點的最短路徑，在每個點都獲 得與最近點的最短路徑時，即得出多點間的最短路徑。
10.一種多點間的多線程網絡智能選徑方法，其特徵在於在無向網絡中，電子網絡拓 撲結構圖上定義需尋徑的多個點，以其中任一點為起點，根據權利要求1所述的兩點間的 多線程網絡智能選徑方法，尋找該起點到所選其它點的最短路徑，然後依次以其他點作為 起點，重複以上選徑方法，得到多條路徑，在這些路徑上執行最小樹生成算法，生成最小樹， 從而得到多點間的最短路徑。
全文摘要
本發明公開兩點間的多線程網絡智能選徑方法，包括建立結構圖，對結構圖各邊及各節點編號，每節點連接帶存儲位、信號識別位及量記錄位的節點寄存器；定義結構圖需尋徑兩點，由兩點輸入信號，經某邊後最先到達某節點，存儲位記錄該邊編號；信號識別位識別兩信號首次分別觸發兩相鄰節點，設從信號輸入點分別到某節點所用時間量分別為a、b，此兩點間的邊的時間量為x，以(x-|a-b|)/2為界限，在此界限內繼續搜索這兩信號觸發的其他兩相鄰節點；將在先兩相鄰節點時間量減去尋徑後兩相鄰節點所花費時間量所得結果，與在後兩相鄰節點對應時間量比較，保留較小時間量並重複以上比較，保留量對應的邊及記錄的與其連接的邊為兩點間最短路徑。
文檔編號G06F17/50GK102033970SQ20091019290
公開日2011年4月27日 申請日期2009年9月30日 優先權日2009年9月30日
發明者林定偉 申請人:林定偉