[發明專利]一種樹結構網絡的管理結構分裂方法

有效

• 申請號: 201410725489.9
• 申請日: 2014-12-03
• 公開（公告）號: CN105721182B
• 公開（公告）日: 2018-11-13
• 發明（設計）人: 王勁林;尤佳莉;劉學;程鋼;鄧浩江
• 申請（專利權）人: 中國科學院聲學研究所;上海尚恩華科網絡科技股份有限公司;北京中科海力技術有限公司
• 主分類號: H04L12/24
• 分類號: H04L12/24
• 代理公司: 北京方安思達知識產權代理有限公司 11472
• 代理人: 王宇楊;楊青

本發明涉及一種樹結構網絡的管理結構分裂方法，包括：如果Q(R)大于L，假設一節點o為動態根節點，對于節點o的任意子節點p_i，若Q(p_i)<Q(o)/2，則對所有子節點聚成兩類；部署或指派一個新的節點o′作為新分裂出的管理根節點，所聚出的兩類中的其中一類節點在管理結構中的父節點指向該新的管理根節點o′，結束操作；否則，若Q(p_i)＝Q(o)/2，則將p_i及其子樹提出，作為一顆新的管理樹，接著在p_i位置或者p_i之上的網絡位置部署新的管理根節點，將p_i指向該新的管理根節點，結束操作；否則，Q(p_i)>Q(o)/2，將該節點p_i設為動態根節點o，然后重新執行。

技術領域

本發明涉及計算機網絡技術，特別涉及一種樹結構網絡的管理結構分裂方法。

背景技術

隨著計算機和網絡的不斷發展，互聯網中節點的規模不斷增加，服務質量的要求也逐漸提高。大規模節點的協同處理和管理在許多系統中都是一個關鍵問題，在實際網絡中，節點的管理結構和拓撲通常呈樹形，而在樹結構中，根節點經常承擔檢索、查詢、定位、服務響應等工作，當網絡規模變大時，根節點的壓力也呈快速上升趨勢。因此，當規模超過一定程度時，需要額外部署根節點或者選擇新的節點緩解根節點壓力。近年來，諸如P2P網絡的網絡節點自治管理系統發展迅速，在這些存在大量子節點的樹形結構中，如何對原有樹結構分裂，從而部署或者指派新的根節點對原有節點管理進行分流，是一個重要問題。

發明內容

本發明的目的在于克服現有技術中的樹結構網絡在規模過大時根節點壓力過大的缺陷，從而提供一種樹結構網絡的管理結構分裂方法。

為了實現上述目的，本發明提供了一種樹結構網絡的管理結構分裂方法，所述樹結構網絡包括一根節點R與若干個子節點，各個節點均包括子節點列表、子節點數計數器、鄰居節點列表和父節點指針；該方法包括：

步驟1)、如果Q(R)大于一預設參數L，則轉步驟2)，否則，退出本操作；其中， Q(x)用于表示以x為根節點的樹中，根節點以下子代的所有節點總數目的計算函數；

步驟2)、假設一節點o為動態根節點，以節點o為父節點的子節點列表為 P＝{p₁,p₂,...,p_i,...}；其中，在初始時，所述節點o為根節點R；

步驟3)、對于節點o的下一代的所有子節點p_i，若均滿足Q(p_i)&lt;Q(o)/2，則對所有子節點聚成兩類，聚類時的聚類優化目標為兩類的節點子代節點總數之差最小；聚成兩類后，部署或指派一個新的節點o′作為新分裂出的管理根節點，所聚出的兩類中的其中一類節點在管理結構中的父節點指向該新的管理根節點o′，然后結束本操作；否則，執行步驟4)；

步驟4)、對于節點o的下一代中的任意一個子節點p_i，若Q(p_i)＝Q(o)/2，則將p_i及其子樹提出，作為一顆新的管理樹，接著在p_i位置或者p_i之上的網絡位置部署新的管理根節點，將p_i指向該新的管理根節點，然后結束本操作；否則，執行步驟 5)；

步驟5)、對于節點o的下一代中的任意一個子節點p_i，若Q(p_i)&gt;Q(o)/2，則將該節點p_i設為動態根節點o，然后重新執行步驟3)。

本發明的優點在于：

本發明的方法能夠提高網絡中節點管理效率，緩解根節點服務壓力。

附圖說明