基于蟻群算法的網絡路由最優路徑判斷模塊設計與實現

徐虹+楊雅志+趙明

摘 要： 網絡中節點的能量是有限的，網絡拓撲結構具有波動性，導致傳統網絡路由算法不能有效適應這些變化，自組織性較差，無法及時獲取最優路徑，大大降低網絡性能。因此，設計基于蟻群算法的網絡路由最優路徑判斷模塊。其以FPGA為控制核心實現硬件設計，具體包括控制模塊、存儲器模塊、尋求后續節點集模塊、采集后續節點模塊、狀態調整模塊、信息素調整模塊和最優路徑判斷模塊。模塊實現部分給出了蟻群算法的核心代碼。實驗結果表明，所設計的最優路徑判斷模塊具有較高的收斂速率，獲取的路徑更短，能夠延長網絡的運行周期。

關鍵詞： 蟻群算法； 網絡路由； 最優路徑； FPGA

中圖分類號： TN711?34； TP393 文獻標識碼： A 文章編號： 1004?373X（2017）04?0036?03

Design and implementation of optimal path judgment module based on ant colony algorithm for network routing

XU Hong， YANG Yazhi， ZHAO Ming

（Department of Information and Computing Science， Chengdu Technological University， Chengdu 611730， China）

Abstract： Since energy in the network node is limited， and the network topology has volatility， which cause that the traditional network routing algorithm can not effectively adapt to these changes， the self?organizing is poor， the optimal path can not be got timely， and the network performance is reduced greatly， the optimal path judgment module based on ant colony algorithm for network routing is designed. The FPGA as the control core is used to realize the hardware design， including the control module， memory module， subsequent nodes set seeking module， subsequent node acquisition module， state adjustment module， information adjustment module， optimal path judgment module and multiplex selection module. The core code of ant colony algorithm is presented in the process of module implementation. The experimental result shows that the designed optimal path judgment module has high?speed convergence and shorter access path， and can lengthen the operation cycle of the network.

Keywords： ant colony algorithm； network routing； optimal path； FPGA

無線傳感器網絡（WSN）通常是由傳感器節點構成的自組織網絡，在軍事、醫療、工業等領域應用廣泛。WSN路由算法是尋求數據從源節點到目標節點間進行通信的最優路徑[1?3]。但是因為WSN網絡中節點的能量有限，網絡拓撲結構具有波動性，導致傳統網絡路由算法不能有效適應這些變化，自組織性較差，無法及時獲取最優路徑，大大降低網絡性能。因此，尋求一種有效的網絡路由最優路徑判斷方法，具有重要應用意義[4?6]。

1 網絡路由最優路徑判斷模塊設計與實現

1.1 系統總體設計

該系統塑造了基于蟻群算法的網絡路由最優路徑判斷模塊，其以現場可編輯門陣列（Field?Programmable Gate Array，FPGA）為控制核心實現硬件設計，其總體結構如圖1所示。其包括控制模塊、存儲器模塊、尋求后續節點集模塊、采集后續節點模塊、狀態調整模塊、信息素調整模塊和最優路徑判斷模塊。

1.2 存儲器模塊的設計

存儲器模塊采用Xilinx公司的IP Generator，IP Generator生成的RAM存儲器的結構示意圖如圖2所示。融合6個帶有端口ENA和讀/寫控制信號WEA 控制的RAM存儲器。網絡節點間的聚類信息采用位寬是5，深度是256的RAM存儲器保存；最佳路徑位寬為16，深度為 32的 RAM存儲器保存；其他能量采用位寬為8，深度是16的RAM存儲器保存。

1.3 后續節點選擇模塊設計

螞蟻的后續節點選擇模塊的原理結構圖如圖3所示。其中的參數delay，cost以及tau分別用于描述延時鄰接矩陣存儲單元、費用鄰接矩陣存儲單元以及信息素存儲單元；m1，m2以及a1分別用于描述乘法器以及加法器；pp（i）以及pcum（i）用于描述一個1*8—維數組；reg1，reg2以及reg3是三個寄存器。

螞蟻后續節點選擇的過程為：采用螞蟻轉移概率運輸模塊，對pp（i）以及pcum（i）等參數進行原始設置，采集w到各可選節點間的路徑費用、延時以及信息素等參數，再將路徑費用和延時參數取倒數后同信息素融合后反饋到乘法器m1中，將獲取的結果保存到pp（i）內，該過程如下：

（1）

式中：；表示可選節點集中的節點，表示w到的信息素參數，表示w到的費用參數，表示w到的延時參數。將預算內完的采用寄存器reg1逐次存儲到累加器a1中，并將最終的結果保存到內，則有：

（2）

通過reg2輸出的累加獲取sum：

（3）

對進行累加后，將sum同隨機數融入乘法器m2中，獲取sum_r，再將其保存到寄存器reg3內。若k>sum_r，則終止相應的對比，記錄下參數i，此時獲取的n_w為。

1.4 狀態調整模塊的設計

螞蟻狀態調整模塊的原理結構圖如圖4所示，螞蟻狀態調整狀態機如圖5所示。

Scenario ka ：ka表示復位，當res為低電平，系統進入Scenario ka，對相關信號進行清除和檢測。

Scenario ce1：對螞蟻路徑path進行調整，一個時鐘周期后進入ce2。

Scenario ce2：采用cost以及delay獲取螞蟻要運行所需的延時和費用等參數，再將這些參數反饋到加法器a1，a2內，并在禁忌列表中將螞蟻要運行的后續節點標識成零，再進入Scenario ce3。

Scenario ce3 ：將Scenario ce2內形成的相關參數存儲到taus，costs以及delays中，將w變成n_w，并輸出螞蟻狀態參數的調整結果，進入Scenario ka。

1.5 最優路徑選擇模塊設計

最優路徑的選擇模塊的原理結構圖如圖6所示，具體的運行過程如下：

Scenario ka：進行復位處理，若ceart為高電平，則進入Scenario ce1。

Scenario ce1：對螞蟻掃描節點的費用和延時兩個參數進行求和，并進入Scenario ce2。

Scenario ce2 ：如果螞蟻沒有達到目標節點，則將費用和延時參數都標識成inf（inf=0xFF），如果costkm

Scenario ce3：將Scenario ce2中獲取的目標節點參數保存到數組path中，一個時鐘后進入Scenario ce4。

Scenario ce4：運算path內的相關數據獲取跳數ts，一個時鐘周期后進入。

Scenario ce5：逐次采集路徑path中的當前節點以及后續節點參數x以及y。

Scenario ce6：系統按照ts判斷各路徑是否被掃描完，如果是，則進入Scenario ce7；否則進入Scenario ce5。

Scenario ce7：采集cost內完成掃描路徑的費用，并將其保存到相應的數組中，并對數組右上角的數據進行匯總，獲取各路徑的總費用，再進入Scenario ce77。

Scenario ce77：將最佳路徑的總費用存儲到寄存器tcsum中，一個時鐘周期后進入Scenario ce9。

Scenario ce8：從tcsum內采集出全部的數據，并且同最優路徑花費對比，如果數據低于目前的最優花費，則將其采集出，同時替換掉當前的數據保存到ram中，否則進入替換處理過程，再進入Scenario ce9。

Scenario ce9：如果全部螞蟻都完成路徑的選擇，則進入ceop，說明完成網絡路由最優路徑的選擇，否則進入Scenario ce1。

2 實驗分析

通過實驗驗證本文設計的基于蟻群算法的網絡路由最優路徑判斷模塊的性能。實驗分別從平均跳數、網絡能耗以及路徑長度三個指標評估本文方法和基于查詢驅動的路由方法的性能優劣。

2.1 平均跳數比較分析

本文方法和基本查詢驅動的路由方法的平均跳數對比圖，如圖7所示。能夠看出，隨著迭代次數的逐漸增加，兩種方法的平均跳數都不斷降低。本文方法的平均跳數在第55次迭代時收斂到8跳，而基于查詢驅動的路由方法僅收斂到13跳。說明相對于基于查詢驅動的路由方法，使用本文方法傳遞數據對網絡資源的占用率更少，對網絡帶寬的消耗更低，可降低網絡的擁塞率，提高網絡數據的傳輸效率，本文方法的效率更高。

2.2 網絡能耗對比分析

兩種方法的網絡能耗情況如圖8所示。從中能夠看出，隨著迭代次數的逐漸增加，各次迭代網絡消耗的總能量都降低。

在無線傳感網絡實驗時，若采用基于查詢驅動的路由方法，其單次迭代總能量消耗是0.348 J，而采用本文方法的單次迭代消耗的總能量是0.213 J，大大降低了網絡能耗量。并且本文方法在20次迭代就完成收斂，而查詢驅動方法需要在75次迭代后才可實現收斂。說明本文方法具有較高的收斂性，采用本文方法的無線傳感網絡的網絡能耗更低。

3 結 論

本文設計基于蟻群算法的網絡路由最優路徑判斷模塊。其以FPGA 為控制核心實現硬件設計，具體包括控制模塊、存儲器模塊、尋求后續節點集模塊、采集后續節點模塊、狀態調整模塊、信息素調整模塊和最優路徑判斷模塊。模塊實現部分給出了蟻群算法的核心代碼。實驗結果表明，所設計的最優路徑判斷模塊具有較高的收斂速率，獲取的路徑更短，能夠延長網絡的運行周期。

參考文獻

[1] 宋立新，戴赫.基于蟻群算法的WSN路由協議研究[J].哈爾濱理工大學學報，2014，19（6）：88?92.

[2] 張雙雙，王延年.節點分布不均勻的無線傳感網絡低功耗算法[J].西安工程大學學報，2015，29（6）：720?723.

[3] 馬學森，曹政，韓江洪，等.改進蟻群算法的無線傳感器網絡路由優化與路徑恢復算法[J].電子測量與儀器學報，2015，29（9）：1320?1327.

[4] 戴天虹，李昊.基于改進蟻群算法的無線傳感器網絡路由的優化[J].計算機測量與控制，2016，24（2）：321?324.

[5] 王洪元，劉志遠，卜瑩.基于蟻群優化算法的無線傳感器網絡跨層路由協議[J].常州大學學報（自然科學版），2014，26（2）：32?37.

[6] 王志勃，畢艷茹.基于Sarsa算法和蟻群優化的監測網絡路由控制設計[J].計算機測量與控制，2014，22（10）：3327?3329.