[發明專利]一種基于位置融合的分布式協作網絡坐標確定方法

無效

• 申請號: 200710035565.3
• 申請日: 2007-08-16
• 公開（公告）號: CN101106484A
• 公開（公告）日: 2008-01-16
• 發明（設計）人: 王意潔;符永銓;鄭重;楊永滔;孫偉東;李小勇
• 申請（專利權）人: 中國人民解放軍國防科學技術大學
• 主分類號: H04L12/26
• 分類號: H04L12/26;H04L12/28
• 代理公司: 國防科技大學專利服務中心
• 代理人: 郭敏

技術領域：本發明涉及廣域網環境中的網絡坐標確定方法，尤其是廣域網環境中分布式網絡坐標的確定方法。

背景技術：

網絡坐標確定是網絡計算領域亟待解決的核心問題之一。基于網絡坐標進行網絡距離測量是目前廣泛采用的網絡距離測量方法之一，它通過在特定坐標空間給結點賦予一個坐標位置，利用結點間的坐標距離來近似網絡延遲。網絡應用系統的執行策略大多是以結點之間的網絡距離為基礎的，網絡坐標確定的精度、穩定性和效率將直接影響到網絡距離測量的效果，從而影響網絡應用系統的運行效率。

現有的確定網絡坐標的典型方法有：1)GNP(Global?Networking?Positioning)方法，它利用一組地標結點作為靜態的集中探測點，采用基于迭代的非線性方法集中計算結點的網絡坐標，缺乏擴展性；沒有考慮地標結點的部署問題，有限的地標結點很容易成為系統的性能瓶頸，從而直接影響網絡坐標確定的效率；它的網絡坐標不變特性難以根據網絡狀態的不斷變化及時更新網絡坐標，從而直接影響到網絡坐標確定的精確程度。2)PIC(Practical?Internet?coordinates)方法，它采用混合式的地標選擇方法，與GNP方法相比，其擴展性有所提高，但是它的收斂速度低，難以根據網絡狀態的不斷變化及時更新網絡坐標，從而直接影響到網絡坐標確定的精確程度，網絡距離較遠的結點的網絡坐標的偏差更大。3)Vivaldi方法，它利用結點之間的不斷交互來及時更新網絡坐標，它的擴展性較好；但它沒有考慮網絡中惡意結點提供的虛假坐標所引起的坐標計算的震蕩問題，以及網絡中存在的三角不等式違例所引起的坐標計算的差錯問題，這些都會影響到網絡坐標確定的穩定性。

總之，現有的網絡坐標確定方法的主要不足之處在于：1)地標瓶頸效應，靜態網絡坐標確定方法以集中式的地標結點為基礎計算網絡坐標，有限的地標結點很容易成為系統的性能瓶頸，從而直接影響網絡坐標確定的效率；2)低精度，靜態網絡坐標確定方法的網絡坐標不變特性和動態網絡坐標確定方法的收斂速度低都將難以根據網絡狀態的不斷變化及時更新網絡坐標，從而直接影響到網絡坐標確定的精確程度；3)穩定性差，網絡中惡意結點提供的虛假坐標將引起坐標計算的震蕩問題，網絡中存在的三角不等式違例將引起坐標計算的差錯問題，都會影響到網絡坐標確定的穩定性。因此，如何提高網絡坐標確定的精度、穩定性和效率已經成為網絡計算領域的熱點研究問題。

發明內容：

本發明要解決的技術問題是針對現有的網絡坐標確定方法存在的地標瓶頸效應、低精度和穩定性差等不足而提出的基于位置融合的分布式協作網絡坐標確定方法。

解決本發明技術問題所采用的技術方案是：動態選擇已有結點用于確定新結點的坐標，從而有效避免地標瓶頸效應的產生；利用多種坐標確定方法確定新結點坐標，提高坐標確定的收斂速度，及時適應網絡狀態的不斷變化，有效保證坐標確定的精度；利用位置融合來減弱惡意結點提供的虛假坐標帶來的位置震蕩影響，利用任意播選擇距離較遠的結點進行坐標確定來減弱選擇距離較近結點引起的三角不等性違例影響，有效提高坐標確定的穩定性和容錯性。

具體的技術方案是：

第一步，系統初始化。

1.依據結點功能將結點分為服務結點和用戶結點。用戶結點僅能夠查詢自己的坐標；服務結點除具有用戶結點的功能外，還負責響應其它結點的坐標確定請求。

2.利用分布式哈希表DHT(Distributed?Hash?Table)組織服務結點和用戶結點。每個結點具有一個唯一標識符ID，結點ID是一個m(m＝160)位的二進制串(即ID是0到2^m之間的整數)，它根據結點的IP地址通過哈希函數(SHA-1算法)獲得。

3.設定網絡坐標的維數D，結點網絡坐標的維數D越多，網絡坐標的精度越高，坐標確定的復雜度越高，通常，網絡坐標的維數D定為7。

4.在系統初始狀態，所有結點都設置為服務結點，任意選擇一個服務結點作為根結點，根結點利用多點坐標確定方法Coordinate_M設置所有服務結點的初始網絡坐標。

多點坐標確定方法Coordinate_M的具體流程是：

1)假設初始狀態系統中共有N個服務結點，N為正整數；

2)利用網絡探測方法，獲取N個服務結點之間的實際網絡延遲，并構成網絡延遲矩陣M，