[發(fā)明專利]基于相依網(wǎng)絡(luò)相連邊的節(jié)點(diǎn)失效恢復(fù)方法

在審

• 申請(qǐng)?zhí)枺?/td>: 201810376219.X
• 申請(qǐng)日: 2018-04-24
• 公開（公告）號(hào): CN108566302A
• 公開（公告）日: 2018-09-21
• 發(fā)明（設(shè)計(jì)）人: 龔凱;吳佳鍵;康立
• 申請(qǐng)（專利權(quán)）人: 西南財(cái)經(jīng)大學(xué)
• 主分類號(hào): H04L12/24
• 分類號(hào): H04L12/24
• 代理公司: 成都金英專利代理事務(wù)所(普通合伙) 51218
• 代理人: 袁英

本發(fā)明公開了基于相依網(wǎng)絡(luò)相連邊的節(jié)點(diǎn)失效恢復(fù)方法，包括以下步驟：建立相依網(wǎng)絡(luò)的恢復(fù)模型；按比例隨機(jī)攻擊相依網(wǎng)絡(luò)的網(wǎng)絡(luò)節(jié)點(diǎn)，產(chǎn)生失效節(jié)點(diǎn)；通過擇優(yōu)恢復(fù)算法對(duì)失效節(jié)點(diǎn)進(jìn)行恢復(fù)；判斷相依網(wǎng)絡(luò)是否新增失效節(jié)點(diǎn)，若是，重復(fù)上一步，否則結(jié)束恢復(fù)流程；擇優(yōu)恢復(fù)算法具體步驟為確定相依網(wǎng)絡(luò)的共同邊界節(jié)點(diǎn)；計(jì)算共同邊界節(jié)點(diǎn)的邊界重要指數(shù)；根據(jù)邊界重要指數(shù)對(duì)共同邊界節(jié)點(diǎn)按比例進(jìn)行降序恢復(fù)；本發(fā)明通過擇優(yōu)恢復(fù)算法計(jì)算邊界節(jié)點(diǎn)的重要性,能夠在不同的相依網(wǎng)絡(luò)上識(shí)別對(duì)結(jié)構(gòu)連通性有重要影響的邊界節(jié)點(diǎn),有效阻止故障在網(wǎng)絡(luò)間的級(jí)聯(lián)擴(kuò)散，避免網(wǎng)絡(luò)發(fā)生結(jié)構(gòu)性破壞，極大提高了相依網(wǎng)絡(luò)遭受故障時(shí)的恢復(fù)能力。

技術(shù)領(lǐng)域

本發(fā)明涉及相依網(wǎng)絡(luò)技術(shù)領(lǐng)域，尤其涉及基于相依網(wǎng)絡(luò)相連邊的節(jié)點(diǎn)失效恢復(fù)方法。

背景技術(shù)

現(xiàn)實(shí)世界中,基礎(chǔ)設(shè)施網(wǎng)絡(luò)(如通訊、交通、能源等)之間相互依賴、協(xié)同工作的情況既是一種普遍現(xiàn)象,也是社會(huì)各界的共識(shí)，對(duì)此,有科研學(xué)者把這樣一些存在相互依賴關(guān)系的基礎(chǔ)網(wǎng)絡(luò)構(gòu)成的系統(tǒng)稱為相依網(wǎng)絡(luò)(interdependent networks)，網(wǎng)絡(luò)間的相互依賴一方面可以提高整個(gè)系統(tǒng)的運(yùn)轉(zhuǎn)效率,同時(shí)也帶來了意料之外的脆弱性和風(fēng)險(xiǎn)性。一旦這些關(guān)乎國家安全和民計(jì)民生的基礎(chǔ)網(wǎng)絡(luò)發(fā)生故障甚至癱瘓(例如2003年意大利“9.28”停電事故和2012年印度“7.31”停電事故),勢(shì)必會(huì)給社會(huì)造成極其嚴(yán)重的后果，因此,如何有效地應(yīng)對(duì)和控制故障傳播,避免相依網(wǎng)絡(luò)發(fā)生結(jié)構(gòu)性破碎,成為復(fù)雜網(wǎng)絡(luò)研究領(lǐng)域的新熱點(diǎn)問題之一。

如何有效地應(yīng)對(duì)和控制故障在相依網(wǎng)絡(luò)上的級(jí)聯(lián)擴(kuò)散避免系統(tǒng)發(fā)生結(jié)構(gòu)性破碎,對(duì)于相依網(wǎng)絡(luò)抗毀性研究具有十分重要的理論價(jià)值和現(xiàn)實(shí)意義。根據(jù)復(fù)雜網(wǎng)絡(luò)理論,采用鑒別關(guān)鍵節(jié)點(diǎn)并實(shí)施預(yù)先保護(hù)是一種主流思想，對(duì)于相依網(wǎng)絡(luò),國內(nèi)外研究學(xué)者也相繼提出了預(yù)先保護(hù)少數(shù)節(jié)點(diǎn)免受失效影響的策略,以此來減緩或阻止故障在整個(gè)系統(tǒng)中的傳播與爆發(fā)，例如從網(wǎng)絡(luò)中篩選出大度數(shù)或高介數(shù)節(jié)點(diǎn)作為不受耦合影響的自治節(jié)點(diǎn),或是提前保護(hù)那些相連邊數(shù)和相依邊數(shù)都很高的節(jié)點(diǎn),或是預(yù)先保護(hù)前5％的大度數(shù)或高Pagerank值的節(jié)點(diǎn)等等，不過,多數(shù)研究中的故障傳播和預(yù)先保護(hù)都是互不干涉的靜態(tài)過程，然而,瞬息萬變的真實(shí)世界更需要的是及時(shí)有效的動(dòng)態(tài)應(yīng)急措施,這樣的措施能夠在相依系統(tǒng)遭受故障時(shí)迅速做出響應(yīng),恢復(fù)失效節(jié)點(diǎn),盡可能將損失降低到最低,避免故障的升級(jí)擴(kuò)大；最新研究提出一種基于相依網(wǎng)絡(luò)的恢復(fù)模型，該模型的基本思想是通過定義共同邊界節(jié)點(diǎn),在每輪恢復(fù)階段找出符合條件的共同邊界節(jié)點(diǎn)并以一定比例實(shí)施恢復(fù)，當(dāng)前的做法是按照隨機(jī)概率進(jìn)行選擇，這種方法雖然簡單直觀,卻沒有考慮現(xiàn)實(shí)世界中資源成本的有限性和擇優(yōu)恢復(fù)的必然性。

發(fā)明內(nèi)容

為了解決上述問題，本發(fā)明提出基于相依網(wǎng)絡(luò)相連邊的節(jié)點(diǎn)失效恢復(fù)方法。

具體的，基于相依網(wǎng)絡(luò)相連邊的節(jié)點(diǎn)失效恢復(fù)方法，包括以下步驟：

S1.建立相依網(wǎng)絡(luò)的恢復(fù)模型；

S2.按1-P的比例隨機(jī)攻擊所述相依網(wǎng)絡(luò)的網(wǎng)絡(luò)節(jié)點(diǎn)使其發(fā)生故障并傳播,導(dǎo)致所述相依網(wǎng)絡(luò)產(chǎn)生失效節(jié)點(diǎn)，其中P為初始正常節(jié)點(diǎn)比例；

S3.通過擇優(yōu)恢復(fù)算法對(duì)所述失效節(jié)點(diǎn)進(jìn)行恢復(fù)，所述擇優(yōu)恢復(fù)算法具體步驟如下：

S31.確定所述相依網(wǎng)絡(luò)的共同邊界節(jié)點(diǎn)；

S32.遍歷所述共同邊界節(jié)點(diǎn)并計(jì)算每個(gè)所述共同邊界節(jié)點(diǎn)的邊界重要指數(shù)；

S33.根據(jù)所述邊界重要指數(shù)對(duì)所述共同邊界節(jié)點(diǎn)進(jìn)行降序恢復(fù)，恢復(fù)比例為λ；

S4.判斷所述相依網(wǎng)絡(luò)是否新增失效節(jié)點(diǎn)，若是，執(zhí)行S3,若否，執(zhí)行S5；

S5.結(jié)束恢復(fù)流程。

進(jìn)一步的，所述相依網(wǎng)絡(luò)至少包括兩個(gè)相互耦合的極大連通網(wǎng)絡(luò)GC_A和GC_B。