[發明專利]基于粒子群算法的二維片上網絡自適應路由方法

有效

• 申請號: 201810052222.6
• 申請日: 2018-01-19
• 公開（公告）號: CN108183860B
• 公開（公告）日: 2021-04-13
• 發明（設計）人: 王學香;鄭陽;齊志;張陽;蔣林洋;孫沖沖;時龍興
• 申請（專利權）人: 東南大學
• 主分類號: H04L12/721
• 分類號: H04L12/721;H04L12/727;H04L12/729;H04L12/933;G06N3/00
• 代理公司: 蘇州創元專利商標事務所有限公司 32103
• 代理人: 范晴;丁浩秋

1.一種基于粒子群算法的二維片上網絡自適應路由方法，其特征在于，在二維片上網絡中將源節點到目的節點的路徑編碼為一個粒子，將粒子所有可能的路徑編碼作為搜索空間，粒子有位置和速度兩個屬性，粒子的位置代表路徑中節點的有序編號，速度代表該粒子向最優路徑靠近的程度；路由方法包括以下步驟：

S01：源節點向目的節點按照確定性路由進行數據傳輸，選擇N條有效路徑作為N個初始種群粒子，進行粒子群算法路由選擇；初始化粒子群時，根據粒子的位置定義編碼矩陣，當產生新的位置時，采用深度優先搜索算法進行檢測是否有環；檢測編碼矩陣中為1的項，去除源節點和目的節點序號之后，剩余為1的節點序號都出現2次，則表示鏈路是連續的，即此鏈路從源節點首位相連至目的節點；若路徑成環且路徑連續，則為有效編碼路徑；

S02：每個粒子的適應度值由該粒子所包含路徑節點的延遲和節點的數據吞吐量決定，找出當前粒子種群中適應度最好的值，記為Gbest；同時記錄各粒子的歷史最好適應度值，記為P_nbest(n＝0，1，...，N-1)；

S03：進行粒子群算法迭代，對于每個粒子，如果粒子當前的適應度值優于歷史最好適應度值P_nbest(n＝0，1，2，...，N-1)，則進行替換；對于每個粒子種群，如果當前粒子種群的最好適應度值Gbest比原來好，則進行替換；

S04：根據各粒子的歷史最好適應度值P_nbest(n＝0，1，...，N-1)和粒子種群最好適應度值Gbest，更新各粒子的位置和速度變量；

S05：迭代完成后，粒子種群中具有歷史最好適應度值Gbest的粒子，其位置所代表的路徑即為最優的路由路徑。

2.根據權利要求1所述的基于粒子群算法的二維片上網絡自適應路由方法，其特征在于，初始化粒子種群時，將源節點到目的節點的曼哈頓距離相同的鏈路作為初始種群，從源節點到目的節點的曼哈頓距離為：

M_distance＝d_x+d_y；

其中，d_x＝|x_s-x_d|，d_y＝|y_s-y_d|，(x_s，y_s)和(x_d，y_d)表示源節點和目的節點的坐標；

從源節點到目的節點滿足曼哈頓距離最短的路徑數為：

N＝(d_x+d_y)！/(d_x！d_y！)；

判斷是否為有效編碼路徑，若路徑成環且路徑連續，則為有效編碼路徑。

3.根據權利要求1所述的基于粒子群算法的二維片上網絡自適應路由方法，其特征在于，用0、1的二值二維矩陣來表示網絡中的粒子，粒子的位置為：

其中，k表示粒子當前的代數，i表示的是粒子的序號；矩陣中x_ab，a、b分別表示鏈路所在源節點、目的節點的序號；x_ab只有2種取值，為1的時候表示鏈路存在，為0的時候表示鏈路不存在。

4.根據權利要求1所述的基于粒子群算法的二維片上網絡自適應路由方法，其特征在于，所述步驟S02中粒子的適應度值滿足如下的約束：

其中，i表示粒子的序號，m表示該粒子所在路徑中鏈路的數目；Bi＝∑(Bi₁+Bi₂+...Bi_m)，Bi表示網絡總吞吐量，Bi_m表示鏈路m上的吞吐量；bi_m表示鏈路m上的最低吞吐量，B_constrain表示鏈路m上的最大吞吐量；Di是鏈路平均延時的表現形式，Di_m指鏈路m上的數據包傳輸延時；Pi是每個粒子適應度。