[發明專利]一種基于半監督聚類的局部網絡拓撲測量任務選擇方法

有效

• 申請號: 201810666646.1
• 申請日: 2018-06-25
• 公開（公告）號: CN108923962B
• 公開（公告）日: 2021-05-28
• 發明（設計）人: 張宇;余卓勛;張曄;張宏莉
• 申請（專利權）人: 哈爾濱工業大學
• 主分類號: H04L12/24
• 分類號: H04L12/24;H04L12/26;G06K9/62
• 代理公司: 哈爾濱市松花江專利商標事務所 23109
• 代理人: 楊立超

1.一種基于半監督聚類的局部網絡拓撲測量任務選擇方法，其特征在于，所述方法的實現過程為：

(1)生成局部網絡的測量任務集，利用局部網絡的目的IP地址和looking Glass測量點生成測量任務集；確定局部網絡對外連接IP地址；

所述確定局部網絡對外連接IP地址的過程為：

每個任務執行測量后可獲得一條有向traceroute路徑，對原始traceroute路徑做如下處理：從每個TTL中選取第一個IP地址作為有效IP地址，保留第一個時間延遲信息，最后生成的TTL-IP地址對；由于任務元素中的測量點位于局部網絡外，目的IP地址位于局部網絡內，如果該traceroute路徑有效，那么可認為在traceroute路徑中第一個出現的位于局部網絡內的IP地址為對外連接IP地址；

(2)從測量任務集中選擇少量的測量任務執行測量作為已知樣本，剩余的測量任務作為未知樣本，進行半監督聚類，循環多輪直到滿足停止條件，找到局部網絡對外連接IP地址；

所述半監督聚類的算法流程為：

(2.1)定義局部網絡的測量任務集具有M個測量點與N個目的IP地址，得到具有M*N個測量任務的測量任務集，對所述測量任務集中的每個測量任務的屬性進行標注；初始待測任務集采用啟發式選取方案，具體為：按照以矩陣對角線下滑的方式選取N個任務元素作為初始測量任務，執行測量后標記初始集類別，記為標記樣本，其余任務元素記為未標記樣本；

(2.2)此步驟為半監督算法的核心流程，同一個類別的標記樣本數據生成該類別質心向量，具體生成方法為：統計每個屬性中不同屬性值出現的次數，每個屬性的總權重為1，按照屬性值出現比例分割權重，所有的屬性量化后合并在一起后構成初始類別的質心向量；令記為每個任務的屬性向量集，記為初始待測任務集發現的類別集合，則類別的質心向量形式描述如下：

得到初始類別的質心后，依次遍歷所有的未標記樣本，計算未標記樣本到每個類別質心的歐式距離，如果該樣本到距離最近的類別質心小于閾值α，則將樣本標記為該類別，否則認為樣本不屬于任何已知類別，不執行聚合，用于生成下一輪的待測任務集；

(2.3)最后將已經標記的樣本從所有測量任務集中剔除，再從剩下的未標記樣本中隨機選取任務加入待測任務集并執行測量，分析測量結果，如果沒有新的類別出現則結束算法，否則利用新的測量結果生成新的類別質心，再按照上述(2.2)中算法重新聚合未標記樣本，選擇待測任務集。

2.根據權利要求1所述的一種基于半監督聚類的局部網絡拓撲測量任務選擇方法，其特征在于，在步驟(2.1)中，測量任務的屬性為，選取目的IP地址的屬性四個屬性“AS號、國家、城市、IP地址前綴”和測量點IP地址的屬性“國家”這五個屬性作為測量任務的屬性。

3.根據權利要求2所述的一種基于半監督聚類的局部網絡拓撲測量任務選擇方法，其特征在于，在步驟(2.2)中，所述閾值α確定如下：通過固定測量任務屬性和待測任務集規模設置不同的距離閾值，進行比較實驗，選擇發現局部網絡對外連接IP地址最多的實驗結果中對應的閾值。