[發(fā)明專利]一種針對分層流量復雜網絡的路徑優(yōu)化方法

在審

• 申請?zhí)枺?/td>: 201711452300.3
• 申請日: 2017-12-28
• 公開（公告）號: CN107872354A
• 公開（公告）日: 2018-04-03
• 發(fā)明（設計）人: 穆獻中;李國昊;胡廣文;吳玉鋒
• 申請（專利權）人: 北京工業(yè)大學
• 主分類號: H04L12/24
• 分類號: H04L12/24;H04L12/721;H04L12/801
• 代理公司: 北京思海天達知識產權代理有限公司11203
• 代理人: 張慧

技術領域

本發(fā)明屬于網絡路徑優(yōu)化技術領域，尤其涉及一種針對分層流量復雜網絡的動態(tài)路徑優(yōu)化方法。

背景技術

城市發(fā)展進程的不斷加快在帶來便捷、高水平生活的同時，也帶來交通擁堵、電力緊張以及通訊阻塞等問題。解決交通堵塞問題、緩解能源供需矛盾、減輕信息通訊壓力已成為當前城市發(fā)展難以回避的“困局”之一，而優(yōu)化運輸網絡、電力網絡以及通訊網絡是解決這一困局的有效途徑。網絡優(yōu)化是運用運籌學手段對網絡中節(jié)點、路徑和流量進行優(yōu)化以提升網絡傳輸性能，然而隨著近年運輸、電力、通訊網絡的高速發(fā)展，網絡節(jié)點路徑呈指數型增長，網絡規(guī)模不斷擴張，復雜程度不斷增加，極大地增加了網絡優(yōu)化的難度；與此同時，城市發(fā)展進程的不斷推進導致網絡形態(tài)逐漸實體化，使得完全打破既有網絡幾乎成為不可能。基于此，在不完全打破既有網絡空間結構的前提下，擴展運輸網絡維度，改變網絡邏輯結構以提高網絡性能是目前較為認可的解決思路。運用分層流量復雜網絡模型優(yōu)化運輸、電力、通訊網絡的思想正是在這一背景下提出的。

分層流量復雜網絡泛指一類節(jié)點眾多、流量龐大的網絡群體，其區(qū)別于一般復雜網絡的一個重要特征是網絡中的節(jié)點存在邏輯分層，即部分節(jié)點與其他節(jié)點不處于同一邏輯層級。這些節(jié)點相較于其他節(jié)點一般具有更高的流量通行優(yōu)先級和更大的吞吐量，與一般的網絡樞紐不同的是，這些節(jié)點只與少部分其他節(jié)點聯(lián)通且具備分配低層級節(jié)點流量的權限。分層流量復雜網絡的優(yōu)勢在于可以通過設置部分低層級網絡節(jié)點與高層及網絡節(jié)點的連通性提高網絡流量同時降低流量網絡路徑長度，并降低網絡先天路徑約束與流量約束的干擾。分層流量復雜網絡多見于電力、通訊、物流等領域，目前在電力運輸網絡、信息傳輸平臺、地下物流系統(tǒng)等一類網絡系統(tǒng)進行了一些應用，尤其在近年來我國電力傳輸、信息通訊、物流運輸需求不斷提高、規(guī)模持續(xù)擴大、基礎建設相對成型背景下，緩解能源供需矛盾、減輕信息通訊壓力、解決交通堵塞問題具有廣闊的應用前景。

分層流量復雜網絡是在已有網絡模型的基礎上通過設置邏輯分層節(jié)點，達到提高網絡流量的同時降低網絡路徑長度和結構復雜程度的目的。盡管如此，分層流量復雜網絡的節(jié)點選擇和路徑優(yōu)化算法設計往往是限制這一模型應用的主要難題。由于算法設計過程中需要對網絡拓撲結構和邏輯分層進行設計，運用常規(guī)的通用網絡結構設計流程和優(yōu)化算法往往會遇到高維次、高復雜度的模擬運算和優(yōu)化過程，此外多層級的節(jié)點聯(lián)通測試和魯棒性分析也是阻礙了分層流量復雜網絡應用的主要問題。因此，盡管分層流量復雜網絡的研究和應用頗具前瞻性和發(fā)展?jié)摿?，高難度的算法設計帶來的高風險和高成本是限制其發(fā)展的一個重要原因。

目前，地下物流系統(tǒng)、智能電網、電子商務等是分層流量復雜網絡技術起步較早的領域。物流、電網、電商依賴于交通、輸電線路以及互聯(lián)網等基礎設施，隨著消費需求的不斷增加，現有條件已經很難滿足發(fā)展需求，地下物流系統(tǒng)、智能電網、電子商務等分層流量復雜網絡技術的運用由此產生。地下物流系統(tǒng)是指城市內部及城市間通過類似地鐵的地下管道或隧道運輸貨物的運輸和供應系統(tǒng)，具有減輕地面道路的交通壓力；有效減輕城市污染；不受復雜天氣等外界條件干擾等優(yōu)點。新能源間歇式無縫接入是智能電網的一項重要特征，通過簡化新能源發(fā)電入網程序，基于互聯(lián)網標準將新能源電力無縫接入電網，實現不同容量、等級的發(fā)電儲能設備互聯(lián)。電子商務是基于信息網絡手段實現商務活動的手段，隨著電子商務的蓬勃發(fā)展，憑借快速、便捷、安全的電子商務平臺，網上購物、交易等諸多活動得以實現。

可以看出，隨著地下物流系統(tǒng)、智能電網、電子商務的不斷發(fā)展，對于網絡性能的要求也不斷提高。分層流量復雜網絡技術對于降低大型城市交通擁堵程度、緩解電力供需壓力、優(yōu)化信息網絡傳遞層級和路徑都具有非常大的應用前景，然而其在世界范圍內尚缺乏成熟的案例可供參考?，F有主要研究手段多基于多目標規(guī)劃(總費用、最大單程距離最?。蛔畲罅髯畲?、最短路徑最小等)、動態(tài)規(guī)劃、智能算法(啟發(fā)式算法、遺傳算法、蟻群算法等)、網絡優(yōu)化算法(Dijkstra算法、二叉樹、最短路徑、最小生成樹等)等傳統(tǒng)算法。這些算法盡管具有一定的參考價值，但由于缺乏恰當的分層節(jié)點表達形式和分層節(jié)點與其他節(jié)點邏輯路徑計算方法，因此對于復雜的分層流量網絡路徑選擇性能欠佳。

經過對現有技術、方法梳理分析認為：基于一般網絡路徑優(yōu)化算法在分層流量復雜網絡中應用的局限性主要體現在：

①以多目標規(guī)劃方法為代表的一類優(yōu)化算法，盡管在目標設計上直觀性很強，但僅適用于節(jié)點數目不多，網絡結構簡單的一半網絡，對于復雜網絡存在計算效率低下、計算精度不高、難以求解等問題。