[發(fā)明專利]基于三路子拓?fù)錅y(cè)量的網(wǎng)絡(luò)拓?fù)浒l(fā)現(xiàn)方法

有效

• 申請(qǐng)?zhí)枺?/td>: 202010884969.5
• 申請(qǐng)日: 2020-08-28
• 公開（公告）號(hào): CN111970202B
• 公開（公告）日: 2021-09-10
• 發(fā)明（設(shè)計(jì)）人: 潘勝利;梁應(yīng)敞;易長(zhǎng)勝;張宗旺
• 申請(qǐng)（專利權(quán)）人: 電子科技大學(xué)
• 主分類號(hào): H04L12/751
• 分類號(hào): H04L12/751;H04L12/721;G06K9/62
• 代理公司: 成都虹盛匯泉專利代理有限公司 51268
• 代理人: 王偉

1.一種基于三路子拓?fù)錅y(cè)量的網(wǎng)絡(luò)拓?fù)浒l(fā)現(xiàn)方法，其特征在于，包括：

A1、在待測(cè)量的拓?fù)渚W(wǎng)絡(luò)中，隨機(jī)選擇三個(gè)葉子節(jié)點(diǎn)組成初始三路子拓?fù)渥鳛槌跏纪負(fù)洌?/p>

A2、從剩下的葉子節(jié)點(diǎn)中隨機(jī)選擇葉子節(jié)點(diǎn)作為下一個(gè)待插入節(jié)點(diǎn)；

A3、找到當(dāng)前拓?fù)渲袚碛凶铋L(zhǎng)公共路徑的兩個(gè)葉子節(jié)點(diǎn)，選擇從源節(jié)點(diǎn)到這兩個(gè)葉子節(jié)點(diǎn)之間的二分內(nèi)部節(jié)點(diǎn)，以該二分內(nèi)部節(jié)點(diǎn)作為公共祖先節(jié)點(diǎn)，隨機(jī)選擇一個(gè)節(jié)點(diǎn)，若該節(jié)點(diǎn)與兩個(gè)葉子節(jié)點(diǎn)中的其中一個(gè)葉子節(jié)點(diǎn)的最近公共祖先節(jié)點(diǎn)為二分內(nèi)部節(jié)點(diǎn)，則選擇該節(jié)點(diǎn)，進(jìn)而將該節(jié)點(diǎn)與這個(gè)葉子節(jié)點(diǎn)作為選出的兩個(gè)節(jié)點(diǎn)，與待插入節(jié)點(diǎn)組成新的三路子拓?fù)洌?/p>

A4、測(cè)量新的三路子拓?fù)涞念愋停?/p>

A5、根據(jù)新的三路子拓?fù)涞念愋停_定該待插入節(jié)點(diǎn)的插入位置，從而得到更新的拓?fù)洌?/p>

A6、重復(fù)步驟A2-A5，直至所有剩下的葉子節(jié)點(diǎn)完成插入，從而恢復(fù)整個(gè)拓?fù)渚W(wǎng)絡(luò)。

2.根據(jù)權(quán)利要求1所述的一種基于三路子拓?fù)錅y(cè)量的網(wǎng)絡(luò)拓?fù)浒l(fā)現(xiàn)方法，其特征在于，步驟A4包括以下分步驟：

A41、獲得當(dāng)前三路子拓?fù)鋬蓛陕窂降南嗨贫攘考希?jì)算相似度平均相對(duì)偏差；

A42、將平均相對(duì)偏差作為無(wú)監(jiān)督聚類方法的輸入，進(jìn)行二元聚類，得到當(dāng)前三路子拓?fù)涞念愋汀?/p>

3.根據(jù)權(quán)利要求2所述的一種基于三路子拓?fù)錅y(cè)量的網(wǎng)絡(luò)拓?fù)浒l(fā)現(xiàn)方法，其特征在于，步驟A5具體為：設(shè)定源節(jié)點(diǎn)為s，待插入節(jié)點(diǎn)為k，公共祖先節(jié)點(diǎn)為m，距離m最近的兩個(gè)葉子節(jié)點(diǎn)分別記為i、j；

若聚類結(jié)果為0，則當(dāng)前三路子拓?fù)漕愋蜑棣?p_i,p_j,p_k)＝0，該待插入節(jié)點(diǎn)的插入位置為節(jié)點(diǎn)m；

若S(p_i,p_j)S(p_i,p_k)＝S(p_j,p_k)，則當(dāng)前三路子拓?fù)漕愋蜑棣?p_i,p_j,p_k)＝1，該待插入節(jié)點(diǎn)的插入位置為節(jié)點(diǎn)s到m之間的鏈路；

若S(p_i,p_k)S(p_i,p_j)＝S(p_j,p_k)，則當(dāng)前三路子拓?fù)漕愋蜑棣?p_i,p_j,p_k)＝2，該待插入節(jié)點(diǎn)的插入位置為節(jié)點(diǎn)m到i之間的鏈路；

若S(p_i,p_k)＝S(p_i,p_j)S(p_j,p_k)，則當(dāng)前三路子拓?fù)漕愋蜑棣?p_i,p_j,p_k)＝3，該待插入節(jié)點(diǎn)的插入位置為節(jié)點(diǎn)m到j(luò)之間的鏈路；

其中，p_i,p_j,p_k為當(dāng)前三路子拓?fù)鋵?duì)應(yīng)的三條路徑，S(p_i,p_j)表示p_i與p_j的相似度量，S(p_i,p_k)表示p_i與p_k的相似度量，S(p_j,p_k)表示p_j與p_k的相似度量。

4.根據(jù)權(quán)利要求3所述的一種基于三路子拓?fù)錅y(cè)量的網(wǎng)絡(luò)拓?fù)浒l(fā)現(xiàn)方法，其特征在于，任意兩兩路徑p_i和p_j的相似度量計(jì)算為：

Cov(X,Y)＝E[XY]-E[X]E[Y]

其中，X表示路徑p_i的M次探測(cè)得到的時(shí)延數(shù)據(jù)，Y表示路徑p_j的M次探測(cè)得到的時(shí)延數(shù)據(jù)，E[X]為X期望值，E[Y]為Y的期望值，E[XY]為X和Y的聯(lián)合期望值。