[發(fā)明專利]用于多路徑路由的多條部分不相交最短路徑快速尋找方法

有效

• 申請(qǐng)?zhí)枺?/td>: 201810841121.7
• 申請(qǐng)日: 2018-07-27
• 公開（公告）號(hào): CN108924053B
• 公開（公告）日: 2021-01-29
• 發(fā)明（設(shè)計(jì)）人: 郭龍坤;鄧蕓蕓;黃培煌;郝震東;陳建利;楊旸
• 申請(qǐng)（專利權(quán)）人: 福州大學(xué)
• 主分類號(hào): H04L12/721
• 分類號(hào): H04L12/721;H04L12/735;H04L12/24
• 代理公司: 福州元?jiǎng)?chuàng)專利商標(biāo)代理有限公司 35100
• 代理人: 蔡學(xué)俊

本發(fā)明涉及一種用于多路徑路由的多條部分不相交最短路徑快速尋找方法，將有向網(wǎng)絡(luò)表示為有向圖模型；從所述有向圖模型中獲取一條最短路徑，并令；根據(jù)中的所有路徑，建立對(duì)應(yīng)有向圖的一個(gè)傳統(tǒng)余圖；基于傳統(tǒng)余圖，構(gòu)造點(diǎn)分解余圖；從點(diǎn)分解余圖中獲取一條最短路徑，沿此路徑對(duì)路徑進(jìn)行增廣；分解獲取螺旋最優(yōu)路徑。本發(fā)明提出的一種用于多路徑路由的多條部分不相交最短路徑快速尋找方法，提高了在網(wǎng)絡(luò)中尋找不相交最短路徑的效率和可行性，能夠快速地找到部分不相交最短路徑。

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

本發(fā)明涉及網(wǎng)絡(luò)優(yōu)化領(lǐng)域，特別是一種用于多路徑路由的多條部分不相交最短路徑快速尋找方法。

背景技術(shù)

網(wǎng)絡(luò)擁塞是數(shù)據(jù)傳輸網(wǎng)絡(luò)的痼疾，因?yàn)閭鹘y(tǒng)數(shù)據(jù)傳輸網(wǎng)絡(luò)主要使用基于單最短路徑的數(shù)據(jù)傳輸方法，由于其選擇最優(yōu)的鏈路(帶寬最大/時(shí)延最低等)進(jìn)行數(shù)據(jù)傳輸，數(shù)據(jù)傳輸?shù)膲毫Ω菀准性谛阅芰己玫哪切╂溌放c結(jié)點(diǎn)上，從而產(chǎn)生擁塞。不相交路徑路由被視為可徹底解決網(wǎng)絡(luò)擁塞的一種路由方案，且具有更好的容錯(cuò)性與網(wǎng)絡(luò)負(fù)載均衡，但其節(jié)點(diǎn)或鏈路完全不相交的要求太過嚴(yán)格并且需要過多的資源。

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

本發(fā)明的目的在于提供一種用于多路徑路由的多條部分不相交最短路徑快速尋找方法，以克服現(xiàn)有技術(shù)中存在的缺陷。

為實(shí)現(xiàn)上述目的，本發(fā)明的技術(shù)方案是：一種用于多路徑路由的多條部分不相交最短路徑快速尋找方法，按照如下步驟實(shí)現(xiàn)：

步驟S1：將有向網(wǎng)絡(luò)表示為有向圖模型G＝(V，E)；

步驟S2：從所述有向圖模型G中獲取一條最短s-t路徑P^*，并令Ω＝{P^*}，Ω表示有向圖模型G中最短s-t路徑的集合；

步驟S3：根據(jù)Ω中的所有路徑，建立對(duì)應(yīng)所述有向圖G的一個(gè)傳統(tǒng)余圖

步驟S4：基于所述傳統(tǒng)余圖構(gòu)造點(diǎn)分解余圖

步驟S5：從所述點(diǎn)分解余圖中獲取一條最短s-t路徑Q^*，沿此路徑Q^*對(duì)路徑P^*進(jìn)行增廣(增廣過程詳見S5的具體描述)；

步驟S6：分解獲取螺旋最優(yōu)路徑；

步驟S7：返回所述步驟S3，直到所有最短s-t路徑P^*處理完后結(jié)束。

在本發(fā)明一實(shí)施例中，在所述步驟S1中，

將所述有向網(wǎng)絡(luò)表示為所述有向圖模型G＝(V，E)，其中，V為有向圖中的頂點(diǎn)，E為有向圖中的邊，n＝|V|表示有向圖G中頂點(diǎn)的個(gè)數(shù)，m＝|E|則表示有向圖G中邊的條數(shù)，確定源點(diǎn)s和目的節(jié)點(diǎn)t，定義權(quán)重函數(shù)w(e)，共享點(diǎn)數(shù)目的花費(fèi)函數(shù)c(e)、共享點(diǎn)數(shù)目的上界δ，從節(jié)點(diǎn)u到節(jié)點(diǎn)v的一條路徑P(u，v)。

尋找部分不相交最短路徑方法的目標(biāo)是得到一組路徑，使得路徑的總權(quán)重最小，并且滿足下列3個(gè)約束條件：1)除源點(diǎn)和目的節(jié)點(diǎn)外，圖中每個(gè)節(jié)點(diǎn)的出度等于入度；2)所有路徑的共享點(diǎn)至多δ個(gè)；3)0-1變量：若邊包含在所求路徑內(nèi)，則取1；反之，取0；即優(yōu)化以下數(shù)學(xué)模型：

x_e∈{0，1}e∈E

其中上述公式中的變量：x_e表示集合{0，1}的非空真子集，w(e)表示邊e的權(quán)重，k表示不相交路徑的條數(shù)，s表示最短路徑P^*的起點(diǎn)，t表示最短路徑P^*的終點(diǎn)，δ⁺(v)表示離開點(diǎn)v的邊集，δ^-(v)表示進(jìn)入點(diǎn)v的邊集，c(e)邊e的花費(fèi)，表示點(diǎn)分解余圖。