徐虹+楊雅志+趙明

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

關(guān)鍵詞： 蟻群算法； 網(wǎng)絡(luò)路由； 最優(yōu)路徑； FPGA

中圖分類號(hào)： TN711?34； TP393 文獻(xiàn)標(biāo)識(shí)碼： A 文章編號(hào)： 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ú)線傳感器網(wǎng)絡(luò)（WSN）通常是由傳感器節(jié)點(diǎn)構(gòu)成的自組織網(wǎng)絡(luò)，在軍事、醫(yī)療、工業(yè)等領(lǐng)域應(yīng)用廣泛。WSN路由算法是尋求數(shù)據(jù)從源節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)間進(jìn)行通信的最優(yōu)路徑[1?3]。但是因?yàn)閃SN網(wǎng)絡(luò)中節(jié)點(diǎn)的能量有限，網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)具有波動(dòng)性，導(dǎo)致傳統(tǒng)網(wǎng)絡(luò)路由算法不能有效適應(yīng)這些變化，自組織性較差，無(wú)法及時(shí)獲取最優(yōu)路徑，大大降低網(wǎng)絡(luò)性能。因此，尋求一種有效的網(wǎng)絡(luò)路由最優(yōu)路徑判斷方法，具有重要應(yīng)用意義[4?6]。

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

1.1 系統(tǒng)總體設(shè)計(jì)

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

1.2 存儲(chǔ)器模塊的設(shè)計(jì)

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

1.3 后續(xù)節(jié)點(diǎn)選擇模塊設(shè)計(jì)

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

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

（1）

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

（2）

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

（3）

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

1.4 狀態(tài)調(diào)整模塊的設(shè)計(jì)

螞蟻狀態(tài)調(diào)整模塊的原理結(jié)構(gòu)圖如圖4所示，螞蟻狀態(tài)調(diào)整狀態(tài)機(jī)如圖5所示。

Scenario ka ：ka表示復(fù)位，當(dāng)res為低電平，系統(tǒng)進(jìn)入Scenario ka，對(duì)相關(guān)信號(hào)進(jìn)行清除和檢測(cè)。

Scenario ce1：對(duì)螞蟻路徑path進(jìn)行調(diào)整，一個(gè)時(shí)鐘周期后進(jìn)入ce2。

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

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

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

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

Scenario ka：進(jìn)行復(fù)位處理，若ceart為高電平，則進(jìn)入Scenario ce1。

Scenario ce1：對(duì)螞蟻掃描節(jié)點(diǎn)的費(fèi)用和延時(shí)兩個(gè)參數(shù)進(jìn)行求和，并進(jìn)入Scenario ce2。

Scenario ce2 ：如果螞蟻沒有達(dá)到目標(biāo)節(jié)點(diǎn)，則將費(fèi)用和延時(shí)參數(shù)都標(biāo)識(shí)成inf（inf=0xFF），如果costkm

Scenario ce3：將Scenario ce2中獲取的目標(biāo)節(jié)點(diǎn)參數(shù)保存到數(shù)組path中，一個(gè)時(shí)鐘后進(jìn)入Scenario ce4。

Scenario ce4：運(yùn)算path內(nèi)的相關(guān)數(shù)據(jù)獲取跳數(shù)ts，一個(gè)時(shí)鐘周期后進(jìn)入。

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

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

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

Scenario ce77：將最佳路徑的總費(fèi)用存儲(chǔ)到寄存器tcsum中，一個(gè)時(shí)鐘周期后進(jìn)入Scenario ce9。

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

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

2 實(shí)驗(yàn)分析

通過實(shí)驗(yàn)驗(yàn)證本文設(shè)計(jì)的基于蟻群算法的網(wǎng)絡(luò)路由最優(yōu)路徑判斷模塊的性能。實(shí)驗(yàn)分別從平均跳數(shù)、網(wǎng)絡(luò)能耗以及路徑長(zhǎng)度三個(gè)指標(biāo)評(píng)估本文方法和基于查詢驅(qū)動(dòng)的路由方法的性能優(yōu)劣。

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

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

2.2 網(wǎng)絡(luò)能耗對(duì)比分析

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

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

3 結(jié) 論

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

參考文獻(xiàn)

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

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

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

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

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

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