[發明專利]一種啟發式網絡負載均衡方法

有效

• 申請號: 201710097167.8
• 申請日: 2017-02-22
• 公開（公告）號: CN106789712B
• 公開（公告）日: 2019-07-23
• 發明（設計）人: 徐小龍;諶運
• 申請（專利權）人: 南京郵電大學
• 主分類號: H04L12/803
• 分類號: H04L12/803
• 代理公司: 南京經緯專利商標代理有限公司 32200
• 代理人: 田凌濤

1.一種啟發式網絡負載均衡方法，實現節點網絡中源交換機節點至目的交換機節點之間最優路徑的獲得，其特征在于，包括如下步驟：

步驟A.初始化N個粒子，以及初始化計數參數i＝0，然后進入步驟B；

步驟B.分別針對各個粒子，將源交換機節點作為粒子當前已探索網絡路徑中的第一個交換機節點，并按如下步驟B01至步驟B07，執行第i次迭代，然后進入步驟C；

步驟B01.判斷i是否等于0，是則針對粒子當前已探索網絡路徑中末交換機節點的各個相鄰交換機節點，根據節點網絡中各鏈路的可用帶寬，分別計算該各個相鄰交換機節點分別作為末交換機節點的下一交換機節點的概率，然后進入步驟B02；否則分別針對粒子當前已探索網絡路徑中末交換機節點的各個相鄰交換機節點，按如下公式(1)：

獲得相鄰交換機節點作為末交換機節點的下一交換機節點的概率p_鄰，進而分別獲得該各個相鄰交換機節點分別作為末交換機節點的下一交換機節點的概率，然后進入步驟B02；其中，α表示相鄰交換機節點出現在全局最優路徑中的權重；β表示相鄰交換機節點出現在粒子所對應局部最優路徑中的權重；p'_鄰表示相鄰交換機節點第i-1次迭代過程中的概率；n_鄰1表示相鄰交換機節點在當前所有全局路徑中出現的次數，n_鄰2表示相鄰交換機節點在當前所有局部路徑中出現的次數；n_all鄰3表示末交換機節點的所有相鄰交換機節點在當前所有全局路徑中出現的次數，n_all鄰4表示末交換機節點的所有相鄰交換機節點在當前所有局部路徑中出現的次數；

步驟B02.針對粒子當前已探索網絡路徑中末交換機節點的各個相鄰交換機節點進行隨機排序，并根據各個相鄰交換機節點分別所對應的概率，按各個相鄰交換機節點的排序，由0開始累加，劃分獲得各個相鄰交換機節點分別所占概率份額，然后進入步驟B03；

步驟B03.獲得隨機數X∈(0,1)，基于各個相鄰交換機節點分別所占概率份額，選擇X所在概率份額對應的相鄰交換機節點，然后判斷該相鄰交換機節點是否位于粒子當前已探索網絡路徑中，是則進入步驟B04；否則將該相鄰交換機節點作為粒子當前已探索網絡路徑中末交換機節點的下一交換機節點，加入到粒子當前已探索網絡路徑中，然后進入步驟B05；

步驟B04.判斷粒子當前已探索網絡路徑中末交換機節點的各個相鄰交換機節點是否都已經過步驟B03的判斷，是則定義粒子當前已探索網絡路徑無效，將粒子當前已探索網絡路徑作為粒子對應于第i次迭代的局部路徑，并定義粒子對應于第i次迭代的局部路徑的舒適度為0，然后進入步驟B07；否則返回步驟B03；

步驟B05.判斷粒子當前已探索網絡路徑中末交換機節點是否為目的交換機節點，是則將粒子當前已探索網絡路徑作為粒子對應于第i次迭代的局部路徑，并進入步驟B06；否則返回步驟B01；

步驟B06.根據如下公式：

獲得粒子對應于第i次迭代的局部路徑的舒適度F，然后進入步驟B07；其中，S_i表示粒子對應于第i次迭代的局部路徑的總可用帶寬；L_i表示粒子對應于第i次迭代的局部路徑中鏈路條數；L_max表示節點網絡中源交換機節點至目的交換機節點所對應所有路徑中的最大路徑長度；L_min表示節點網絡中源交換機節點至目的交換機節點所對應所有路徑中的最短路徑長度；0≤ω≤1，ω表示預設調節系數；D表示源交換機節點至目的交換機節點所對應所有路徑中最大路徑長度、與源交換機節點至目的交換機節點所對應所有路徑中最短路徑長度的差值；

步驟B07.判斷i是否等于0，是則將粒子對應于第i次迭代的局部路徑作為粒子所對應的局部最優路徑；否則基于粒子對應于第i次迭代的局部路徑的舒適度，以及粒子對應于前i-1次迭代中各次局部路徑的舒適度，選擇最大舒適度所對應的局部路徑，更新為粒子所對應的局部最優路徑；

步驟C.根據第i次迭代中，各個粒子分別所對應局部路徑舒適度，選擇最大舒適度所對應的局部路徑作為第i次迭代的全局路徑，則該最大舒適度即為第i次迭代全局路徑的舒適度，然后進入步驟D；

步驟D.判斷i是否等于0，是則將第i次迭代的全局路徑作為全局最優路徑；否則基于第i次迭代的全局路徑的舒適度，以及前i-1次迭代中各次全局路徑的舒適度，選擇最大舒適度所對應的全局路徑，更新為全局最優路徑，然后進入步驟E；

步驟E.判斷i是否等于預設迭代次數，是則全局最優路徑即為節點網絡中源交換機節點至目的交換機節點的最優路徑；否則針對i所對應的值進行加1更新，并返回步驟B。