[發明專利]AntNet路由算法在二維網格拓撲片上網絡中的實現方法

在審

• 申請號: 201610070920.X
• 申請日: 2016-02-01
• 公開（公告）號: CN105610707A
• 公開（公告）日: 2016-05-25
• 發明（設計）人: 王學香;高滔;吳建輝
• 申請（專利權）人: 東南大學
• 主分類號: H04L12/701
• 分類號: H04L12/701;H04L12/801;H04L12/803;G06F15/78
• 代理公司: 江蘇永衡昭輝律師事務所 32250
• 代理人: 王斌

技術領域

本發明是一種應用于嵌入式處理器系統級設計中的二維網格拓撲片上網絡 AntNet路由算法的實現方法，屬于嵌入式處理器系統級設計領域。

背景技術

目前，單顆芯片中一般最多集成數十至上百個處理核，連接這些IP核的互 連結構主要是片上總線，它是通過仲裁和譯碼的方式來完成不同主、從部件之間 的通信與媒介復用。在不久的將來，隨著集成電路制造工藝的不斷發展，集成電 路的規模將超過數十億晶體管，為了滿足市場需求，單顆芯片將要求集成成百上 千個處理核。這樣一來，基于片上總線的互連結構面臨日益嚴峻的挑戰。為此， 研究人員借鑒并行分布式計算機通信網絡中的思想，提出了一種全新的互連架構 ——片上網絡。片上網絡可視為由多個通信節點(稱為路由器)通過相互之間的 通信鏈路(一般稱為通道)連結而成的網絡，采用數據包交換和路由來完成通信任 務，有望替代總線成為下一代片上互連通信架構。

路由算法決定了在給定片上網絡拓撲的情況下決定消息如何從源節點到目 的節點實際經過的路徑。AntNet路由算法是一種基于蟻群優化算法的自適應路 由算法，具有良好的網絡負載均衡擁塞控制能力，主要應用于計算機網絡中。 AntNet路由算法信息素(即數據包發送概率)的增減是基于學習自動機 (LearningAutomata,LA)理論的。LA使用狀態、動作、狀態或動作的概率和環 境響應代表了通用隨機系統。自動機的設計目標是利用過去的動作與當前的環境 響應信息應指導每一步的動作選擇以提高性能。每一步，自動機從有限動作集合 中選取特定動作，同時環境給出隨機響應。在變結構隨機自動機中，各個動作的 概率是根據環境給出的信息來進行更新的。在每一步，動作概率的更新采用逐步 加強的方式。自動機可定義為四元組{α,β,p,T}，其中α是動作，是自動機的輸出， 從該自動機r個元素的動作集合{α₁,α₂,…,α_r}中選取，β是[0,1]區間的隨機變 量，p是自動機或代理的動作概率矢量，T代表動作概率更新周期。自動機的輸 出α是環境的輸入，自動機的輸入β是環境輸出的響應信息。

動作概率p的線性更新方式常見的有線性獎勵-懲罰、線性獎勵-不動、線性 獎勵-∈-懲罰三種。這些方式的核心思想是當某個動作輸入給環境后，環境狀況 得以改善則給出正反饋信息給自動機增加該動作的概率值，否則環境給出負反饋 信息降低該動作概率值，如下兩個公式所示。常數a與b分別是獎勵與懲罰的參 數。當a＝b時，稱為線性獎勵-懲罰(L_R-P)；當b＝0時，稱為線性獎勵-不動 (L_R-I)；a＝0時，稱為線性獎勵-∈-懲罰(L_R-∈-P)。

p_i(n+1)＝p_i(n)+a(1-β(n))(1-p_i(n))-bβ(n)p_i(n)

如在n時刻選擇α_i作為輸出

p_j(n+1)＝p_j(n)-a(1-β(n))p_j(n)+bβ(n)[(r-1)^-1-p_j(n)]

如α_j≠α_i

AntNet路由算法采用L_R-I，網絡節點可以看作LA，每次路由選擇相當于LA 對環境施加動作α。AntNet路由算法使用前進螞蟻包和回退螞蟻包兩種移動代理， 將評估與改進的過程完全分開，使用前進螞蟻包對路由器動作對環境(即網絡) 造成的影響進行評估，使用回退螞蟻包對動作概率進行改進。使用前進螞蟻包從 本節點到目標節點的傳遞時間評估網絡狀態，維護節點的本地流量統計模型，相 當于LA的環境信息輸入β。回退螞蟻包根據評估的結果對本地路由表進行改進 更新，相當于更新LA的動作概率p。路由表的更新周期相當于LA的動作概率更 新周期T。因為β(n)是懲罰因子，所以1-β(n)就是加強因子r。

發明內容