[發(fā)明專利]基于復(fù)雜網(wǎng)絡(luò)的互聯(lián)網(wǎng)拓?fù)涮綔y(cè)節(jié)點(diǎn)優(yōu)化部署方法

在審

• 申請(qǐng)?zhí)枺?/td>: 201710749344.6
• 申請(qǐng)日: 2017-08-28
• 公開（公告）號(hào): CN107395440A
• 公開（公告）日: 2017-11-24
• 發(fā)明（設(shè)計(jì)）人: 費(fèi)高雷;洪瀟翼;何俊武;胡光岷
• 申請(qǐng)（專利權(quán)）人: 電子科技大學(xué)
• 主分類號(hào): H04L12/24
• 分類號(hào): H04L12/24;H04L12/751;H04L12/753;H04L12/733
• 代理公司: 成都宏順專利代理事務(wù)所(普通合伙)51227
• 代理人: 周永宏

1.基于復(fù)雜網(wǎng)絡(luò)的互聯(lián)網(wǎng)拓?fù)涮綔y(cè)節(jié)點(diǎn)優(yōu)化部署方法，其特征在于，包括：

S1、利用輸入的部分拓?fù)鋵?duì)整體拓?fù)涞亩然パa(bǔ)累積概率分布進(jìn)行估計(jì)；

S2、根據(jù)估計(jì)的互補(bǔ)累積概率分布生成隨機(jī)拓?fù)洌?/p>

S3、基于最小相對(duì)顯著性優(yōu)先原則選擇當(dāng)前隨機(jī)拓?fù)湎碌牟渴鸸?jié)點(diǎn)；并記錄選擇的部署節(jié)點(diǎn)；

S4、判斷生成隨機(jī)拓?fù)浯螖?shù)是否已經(jīng)達(dá)到設(shè)定的數(shù)目，如果沒有達(dá)到要求，則轉(zhuǎn)至步驟S2；否則執(zhí)行步驟S5；

S5、從記錄中選擇出現(xiàn)次數(shù)最多的Max個(gè)節(jié)點(diǎn)，作為最終的部署節(jié)點(diǎn)；

其中，Max為部署節(jié)點(diǎn)個(gè)數(shù)上限；

所述步驟S3具體為：

S31、計(jì)算隨機(jī)拓?fù)渌锌刹渴鸸?jié)點(diǎn)的最短路徑樹SPT可覆蓋的邊；

S32、計(jì)算當(dāng)前仍未被覆蓋的邊在當(dāng)前仍未被選中的可部署節(jié)點(diǎn)集合上的相對(duì)顯著性，并選擇相對(duì)顯著性最小的一條邊；邊e的相對(duì)顯著性指可部署節(jié)點(diǎn)集合N中的每一個(gè)節(jié)點(diǎn)對(duì)應(yīng)的SPT集合中，可覆蓋到邊e的SPT的個(gè)數(shù)；

S33、對(duì)所選擇的邊的關(guān)聯(lián)節(jié)點(diǎn)集合中的每個(gè)節(jié)點(diǎn)，計(jì)算其能覆蓋到剩余邊的條數(shù)，并選擇可覆蓋邊數(shù)最多的一個(gè)節(jié)點(diǎn)作為部署節(jié)點(diǎn)，然后從關(guān)聯(lián)節(jié)點(diǎn)集合中移除該節(jié)點(diǎn)，以及將該節(jié)點(diǎn)的SPT可覆蓋的邊從當(dāng)前仍未被覆蓋的邊集中移除；邊e的關(guān)聯(lián)節(jié)點(diǎn)集合指屬于可部署節(jié)點(diǎn)的集合N且其對(duì)應(yīng)的SPT可覆蓋到邊e的節(jié)點(diǎn)集合；

S34、重復(fù)步驟S32至步驟S33直至所有邊都被覆蓋。

2.根據(jù)權(quán)利要求1所述的基于復(fù)雜網(wǎng)絡(luò)的互聯(lián)網(wǎng)拓?fù)涮綔y(cè)節(jié)點(diǎn)優(yōu)化部署方法，其特征在于，所述步驟S1具體為：

S11、統(tǒng)計(jì)輸入的部分拓?fù)渲卸戎荡笥?的節(jié)點(diǎn)的度概率分布率；

S12、根據(jù)步驟S11得到的各節(jié)點(diǎn)的度概率分布率計(jì)算得到互補(bǔ)累積概率函數(shù)；

S13、對(duì)步驟S12得到的互補(bǔ)累積概率函數(shù)進(jìn)行雙對(duì)數(shù)坐標(biāo)變換；

S14、對(duì)經(jīng)步驟S13雙對(duì)數(shù)坐標(biāo)變換后得到的函數(shù)采用線性回歸方法進(jìn)行線性擬合，得到對(duì)應(yīng)的擬合系數(shù)，從而得到估計(jì)的互補(bǔ)累積概率分布。

3.根據(jù)權(quán)利要求1所述的基于復(fù)雜網(wǎng)絡(luò)的互聯(lián)網(wǎng)拓?fù)涮綔y(cè)節(jié)點(diǎn)優(yōu)化部署方法，其特征在于，所述步驟S2具體為：

S21、將所有節(jié)點(diǎn)分為拓?fù)湟阎?jié)點(diǎn)集合與拓?fù)湮粗?jié)點(diǎn)集合；

S22、根據(jù)步驟S1估計(jì)的拓?fù)涠然パa(bǔ)累積概率分布，對(duì)從拓?fù)湮粗?jié)點(diǎn)集合中選取的節(jié)點(diǎn)進(jìn)行拓?fù)渖伞?/p>

4.根據(jù)權(quán)利要求3所述的基于復(fù)雜網(wǎng)絡(luò)的互聯(lián)網(wǎng)拓?fù)涮綔y(cè)節(jié)點(diǎn)優(yōu)化部署方法，其特征在于，所述步驟S22包括以下分步驟：

A1、從拓?fù)湮粗?jié)點(diǎn)集合中選取一個(gè)節(jié)點(diǎn)，對(duì)該節(jié)點(diǎn)生成一個(gè)0到1之間的隨機(jī)數(shù)，根據(jù)隨機(jī)數(shù)估計(jì)該節(jié)點(diǎn)的出度；

A2、若該節(jié)點(diǎn)的出度對(duì)應(yīng)的待連接的節(jié)點(diǎn)屬于拓?fù)湟阎?jié)點(diǎn)集合，則以第一概率從拓?fù)湟阎?jié)點(diǎn)集合中選取待連接節(jié)點(diǎn)；

若該節(jié)點(diǎn)的出度對(duì)應(yīng)的待連接的節(jié)點(diǎn)屬于拓?fù)湮粗?jié)點(diǎn)集合，則以第二概率從拓?fù)湮粗?jié)點(diǎn)集合中選取待連接節(jié)點(diǎn)。

5.根據(jù)權(quán)利要求4所述的基于復(fù)雜網(wǎng)絡(luò)的互聯(lián)網(wǎng)拓?fù)涮綔y(cè)節(jié)點(diǎn)優(yōu)化部署方法，其特征在于，所述第一概率為：

其中，k_u表示節(jié)點(diǎn)u當(dāng)前的度，u表示待連接的節(jié)點(diǎn)，V₁表示拓?fù)湟阎?jié)點(diǎn)集合。

6.根據(jù)權(quán)利要求4所述的基于復(fù)雜網(wǎng)絡(luò)的互聯(lián)網(wǎng)拓?fù)涮綔y(cè)節(jié)點(diǎn)優(yōu)化部署方法，其特征在于，所述第二概率為：

其中，V₂表示拓?fù)湮粗?jié)點(diǎn)集合。