[發明專利]一種求網絡最短路徑的商空間覆蓋模型及其構建方法

無效

• 申請號: 200810021101.1
• 申請日: 2008-07-24
• 公開（公告）號: CN101330417A
• 公開（公告）日: 2008-12-24
• 發明（設計）人: 張鈴;張燕平;何富貴;趙姝
• 申請（專利權）人: 安徽大學
• 主分類號: H04L12/28
• 分類號: H04L12/28;H04L12/56;G06F17/50
• 代理公司: 安徽省合肥新安專利代理有限責任公司
• 代理人: 汪祥虬

1、一種商空間覆蓋模型的構建方法，根據無向無權網絡中網絡拓撲結構的網絡中極大完全子圖，對節點粒度分類建立層次網絡模型；其特征在于：對于無向無權連通網絡從作為粒度最細、第0級商空間覆蓋網絡的初始網絡開始，搜索網絡中所有的極大完全子圖，以極大完全子圖為節點，兩極大完全子圖的節點間有公共節點或邊，定義兩節點相連，得到粒度較粗的商空間覆蓋，為初始網絡的一級商空間覆蓋網絡；然后再求初始網絡的一級商空間覆蓋網絡的所有極大完全子圖，并記錄極大完全子圖對應于初始網絡中的節點信息，以該級的極大完全子圖為節點，兩極大完全子圖的節點間有公共節點或邊，定義兩節點相連，得到粒度較粗的商空間覆蓋，構成初始網絡的二級商空間覆蓋網絡，求初始網絡的二級商空間覆蓋網絡的所有極大完全子圖，并記錄該級的極大完全子圖對應于初始網絡中的節點信息；繼續依此操作直至在商空間覆蓋網絡的極大完全子圖對應于初始網絡的節點信息中初始網絡的任意兩節點對都在同一個極大完全子圖中；各商空間覆蓋網絡按構成先后順序排列形成一個遞階商空間覆蓋網絡鏈；按遞階商空間覆蓋網絡鏈的順序，記錄各個商空間覆蓋網絡的所有極大完全子圖和各個極大完全子圖對應于初始網絡的節點信息為商空間覆蓋模型；對于無向無權的不連通網絡，先求出各個連通分支，對于每個連通分支，用無向無權連通網絡的方式來求解連通分支的商空間覆蓋模型。

2、如權利要求1所述商空間覆蓋模型的構建方法，特征在于具體操作步驟如下：

先針對具體網絡拓撲依據商空間理論給出具體組成元素的表達形式：

對已給定的無向無權網絡G(X，E)，由節點z∈X構成節點集X，符號∈表示“屬于”，由所有的邊e構成邊集E，邊e上的權值由0，1構成；根據相容關系，將網絡G(X，E)中在同一極大完全子圖節點歸為一覆蓋，將有公共節點或邊的兩覆蓋定義為一邊，形成網絡G(X，E)的商空間覆蓋網絡；

當無向無權網絡G(X，E)為連通網絡時，記節點集X＝X₀，邊集E＝E₀，求解網絡G(X₀，E₀)中的所有極大完全子圖，將網絡G(X₀，E₀)中在同一極大完全子圖的節點歸為一覆蓋，再將每個覆蓋當作一個節點，有公共邊或節點的兩覆蓋定義為一邊，構成網絡G(X₀，E₀)的一級商空間覆蓋網絡G₁(X₁，E₁)，其中X₁是由網絡G(X₀，E₀)中的極大完全子圖構成，E₁表示網絡G(X₀，E₀)中的極大完全子圖之間存在交集；

對于網絡G₁(X₁，E₁)，求解網絡G₁(X₁，E₁)中的所有極大完全子圖，并記錄極大完全子圖對應于初始網絡G(X₀，E₀)中的節點信息；在極大完全子圖對應于初始網絡G(X₀，E₀)的節點信息中，判斷初始網絡G(X₀，E₀)的任意兩節點對都是否在同一個極大完全子圖中，如果在，網絡G₁(X₁，E₁)為最粗的商空間覆蓋網絡G_k(X_k，E_k)，否則對于網絡G₁(X₁，E₁)將在同一極大完全子圖的節點歸為一覆蓋，再將每個覆蓋當作一個節點，有公共邊或節點的兩覆蓋定義為一邊，構成網絡G₁(X₁，E₁)的一級商空間覆蓋網絡，記為網絡G(X₀，E₀)的二級商空間覆蓋網絡G₂(X₂，E₂)，其中X₂是由網絡G₁(X₂，E₂)中的極大完全子圖構成，E₂表示網絡G₁(X₁，E₁)中的極大完全子圖之間存在交集；

…，依次類推，…；

對于網絡G_i(X_i，E_i)，求解網絡G_i(X_i，E_i)中的所有極大完全子圖，并記錄極大完全子圖對應于初始網絡G(X₀，E₀)中的節點信息；在極大完全子圖對應于初始網絡G(X₀，E₀)的節點信息中，判斷初始網絡G(X₀，E₀)的任意兩節點對都是否在同一個極大完全子圖中，如果在，網絡G_i(X_i，E_i)為最粗的商空間覆蓋網絡G_k(X_k，E_k)，否則對于網絡G_i(X_i，E_i)將在同一極大完全子圖的節點歸為一覆蓋，再將每個覆蓋當作一個節點，有公共邊或節點的兩覆蓋定義為一邊，構成網絡G_i(X_i，E_i)的一級商空間覆蓋網絡，記為網絡G(X₀，E₀)的i+1級商空間覆蓋網絡G_i+1(X_i+1，E_i+1)，其中X_i+1是由網絡G_i(X_i，E_i)中的極大完全子圖構成，E_i+1表示網絡G_i(X_i，E_i)中的極大完全子圖之間存在交集；

直到最粗的商空間覆蓋網絡G_k(X_k，E_k)，求解網絡G_k(X_k，E_k)中的所有極大完全子圖，并記錄極大完全子圖對應于初始網絡G(X₀，E₀)中的節點信息；在極大完全子圖對應于初始網絡G(X₀，E₀)的節點信息中，初始網絡G(X₀，E₀)的任意兩節點對都在同一個極大完全子圖中；

各商空間覆蓋網絡按構成先后順序排列形成一個遞階商空間覆蓋網絡鏈G(X₀，E₀)，G₁(X₁，E₁)，…，G_i(X_i，E_i)，…，G_k(X_k，E_k)；

按照遞階商空間覆蓋網絡鏈G(X₀，E₀)，G₁(X₁，E₁)，…，G_i(X_i，E_i)，…，G_k(X_k，E_k)順序，記錄各個商空間覆蓋網絡的極大完全子圖和各個極大完全子圖對應于初始網絡的節點信息為商空間覆蓋模型；

當無向無權網絡G(X，E)為不連通網絡時，先求出網絡G(X，E)的各個連通分支，再以每個連通分支為一個無向無權連通網絡，采用求無向無權連通網絡的方法來得到其商空間覆蓋模型。