基于蟻群算法的網(wǎng)絡路由最優(yōu)路徑判斷模塊設計與實現(xiàn)

徐虹+楊雅志+趙明

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

關鍵詞： 蟻群算法； 網(wǎng)絡路由； 最優(yōu)路徑； 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

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

1 網(wǎng)絡路由最優(yōu)路徑判斷模塊設計與實現(xiàn)

1.1 系統(tǒng)總體設計

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

1.2 存儲器模塊的設計

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

1.3 后續(xù)節(jié)點選擇模塊設計

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

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

（1）

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

（2）

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

（3）

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

1.4 狀態(tài)調整模塊的設計

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

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

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

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

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

1.5 最優(yōu)路徑選擇模塊設計

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

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

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

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

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

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

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

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

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

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

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

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

2 實驗分析

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

2.1 平均跳數(shù)比較分析

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

2.2 網(wǎng)絡能耗對比分析

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

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

3 結 論

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

參考文獻

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

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

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

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

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

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