基于改進(jìn)蟻群算法的智慧農(nóng)業(yè)無(wú)線傳感器網(wǎng)絡(luò)路由優(yōu)化研究

劉彤彤　王磊

摘要：為了提高智慧農(nóng)業(yè)無(wú)線傳感器網(wǎng)絡(luò)路由的生存時(shí)間，節(jié)點(diǎn)能量消耗相對(duì)均衡，采用改進(jìn)蟻群算法。首先建立無(wú)線傳感器網(wǎng)絡(luò)模型和約束條件；接著通過(guò)消耗能量預(yù)測(cè)節(jié)點(diǎn)傳輸能力，剩余能量、過(guò)載區(qū)域以及覆蓋冗余度構(gòu)成適應(yīng)度函數(shù)；然后改進(jìn)蟻群算法，包括基于最佳路徑的目標(biāo)函數(shù)值信息素分配策略，二點(diǎn)交叉算子對(duì)信息素分配策略對(duì)應(yīng)的任意2個(gè)網(wǎng)絡(luò)節(jié)點(diǎn)序列進(jìn)行優(yōu)化；最后給出無(wú)線傳感器網(wǎng)絡(luò)路由優(yōu)化流程。試驗(yàn)仿真顯示本研究算法使無(wú)線傳感器網(wǎng)絡(luò)路由的節(jié)點(diǎn)間剩余能量差異性最小，網(wǎng)絡(luò)生存時(shí)間較長(zhǎng)，不同節(jié)點(diǎn)數(shù)接收數(shù)據(jù)包平均剩余能量較多。

關(guān)鍵詞：無(wú)線傳感器網(wǎng)絡(luò)；最佳路徑；改進(jìn)蟻群；剩余能量

中圖分類號(hào)： TP212.9；S126文獻(xiàn)標(biāo)志碼： A

文章編號(hào)：1002-1302（2017）15-0199-03

無(wú)線傳感器網(wǎng)絡(luò)被廣泛應(yīng)用在農(nóng)業(yè)生產(chǎn)、監(jiān)測(cè)、科研等智能領(lǐng)域，例如溫室大棚環(huán)境監(jiān)測(cè)、土壤水分監(jiān)測(cè)等可根據(jù)農(nóng)作物生長(zhǎng)需要進(jìn)行實(shí)時(shí)智能決策，并自動(dòng)開(kāi)啟或者關(guān)閉指定的環(huán)境調(diào)節(jié)設(shè)備，但是無(wú)線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)受到硬件資源和傳輸節(jié)點(diǎn)能量的限制，數(shù)據(jù)處理和傳輸能力較弱，如何有效利用能量，延長(zhǎng)無(wú)線傳感器網(wǎng)絡(luò)壽命并保證網(wǎng)絡(luò)功能成為智慧農(nóng)業(yè)無(wú)線傳感器研究的重要方向[1]。

目前關(guān)于智慧農(nóng)業(yè)無(wú)線傳感器網(wǎng)絡(luò)路由能量利用效率和能量均衡優(yōu)化研究方法有：蟻群算法（Ant Colony，AC），具有較強(qiáng)的全局尋優(yōu)能力[2]，但是需要收發(fā)雙向螞蟻大量、反復(fù)地更新信息素，若對(duì)鏈路穩(wěn)定性進(jìn)行考慮，那么最優(yōu)路徑中有可能包含不穩(wěn)定鏈路，因此路由生存時(shí)間受到影響，導(dǎo)致需要更大的網(wǎng)絡(luò)開(kāi)銷；粒子群算法（Particle Swarm Optimization，PSO），通過(guò)睡眠調(diào)度機(jī)制優(yōu)化網(wǎng)絡(luò)覆蓋性能[3]，但是沒(méi)有考慮覆蓋率、能量利用效率、節(jié)點(diǎn)生存率的均衡性；動(dòng)態(tài)分簇算法（Dynamic Clustering，DC），讓簇內(nèi)節(jié)點(diǎn)把數(shù)據(jù)發(fā)送至簇頭[4]，然后簇頭對(duì)匯總的數(shù)據(jù)進(jìn)行融合，再以多跳方式發(fā)送給匯聚節(jié)點(diǎn)，這種算法能夠節(jié)省能量，但是存在網(wǎng)絡(luò)延遲等問(wèn)題；定向擴(kuò)散算法（Directed Diffusion，DD），能夠減小數(shù)據(jù)冗余[5]，但是路由開(kāi)銷增加，效率低。

為了提高智慧農(nóng)業(yè)無(wú)線傳感器網(wǎng)絡(luò)路由優(yōu)化性能，本研究采用改進(jìn)蟻群算法（Improved Ant Colony，IAC）。首先建立無(wú)線傳感器網(wǎng)絡(luò)能耗模型和剩余能量約束條件；通過(guò)消耗能量預(yù)測(cè)節(jié)點(diǎn)傳輸能力，剩余能量、過(guò)載區(qū)域以及覆蓋冗余度構(gòu)成適應(yīng)度函數(shù)；改進(jìn)蟻群算法包括基于最佳路徑的目標(biāo)函數(shù)值信息素分配策略，二點(diǎn)交叉算子對(duì)信息素分配策略對(duì)應(yīng)的任意2個(gè)網(wǎng)絡(luò)節(jié)點(diǎn)序列進(jìn)行優(yōu)化；試驗(yàn)仿真顯示本研究算法使無(wú)線傳感器網(wǎng)絡(luò)路由的節(jié)點(diǎn)間剩余能量差異性最小，網(wǎng)絡(luò)生存時(shí)間較長(zhǎng)，不同節(jié)點(diǎn)數(shù)接收數(shù)據(jù)包平均剩余能量較多。

1系統(tǒng)模型

1.1網(wǎng)絡(luò)模型

無(wú)線傳感器網(wǎng)絡(luò)路由可抽象成帶權(quán)有向圖G（V，E），V={v1，v2，…，vn}為網(wǎng)絡(luò)中感知節(jié)點(diǎn)的集合[6-7]，E={e12，e23，…，eij}為相鄰節(jié)點(diǎn)之間通信鏈路的集合，其權(quán)值為路徑開(kāi)銷，用W{vi，vj}表示。假設(shè)相鄰2個(gè)節(jié)點(diǎn)之間最多僅有一條可通信鏈路，如節(jié)點(diǎn)i、j∈V連通，且i、j之間不存在其他節(jié)點(diǎn)，則稱i、j邊為鏈路且（i、j）∈E。節(jié)點(diǎn)序列p（i1，i2，…，im-1，im）是一條長(zhǎng)度為m的路徑，其中：il∈V，1≤l≤m，且，（il-1，il）∈E，2≤l≤m。

式中：Q為信息素濃度的常數(shù)；L為本次循環(huán)中所走路徑的長(zhǎng)度；Lworst為最長(zhǎng)路徑，如果第k只螞蟻沒(méi)有經(jīng)過(guò)邊（r′，s），則Δτkt（r′，s）的值為零。該策略在每一周期結(jié)束時(shí)，僅對(duì)最佳路徑包含的路段增加信息素，更新后每條邊的信息素限制在所經(jīng)過(guò)的最長(zhǎng)路徑信息素濃度和最短信息素濃度之間，避免某些邊上的信息素過(guò)大，使信息素能夠正確指導(dǎo)螞蟻在下一次迭代的搜索方向，從而避免了大量無(wú)效搜索，提高了數(shù)據(jù)處理效率。

2.2.2局部?jī)?yōu)化

為了避免蟻群優(yōu)化算法過(guò)早地陷入局部最優(yōu)，在每次迭代中，當(dāng)所有螞蟻完成解的構(gòu)造之后[14]，使用隨機(jī)函數(shù)rand（）生成（0，1]之間的隨機(jī)數(shù)，其個(gè)數(shù)與螞蟻數(shù)量一樣，若該隨機(jī)數(shù)落在交叉概率[0.75，0.85]的取值范圍內(nèi)，便應(yīng)用遺傳算法中的二點(diǎn)交叉算子對(duì)信息素分配策略對(duì)應(yīng)的任意2個(gè)網(wǎng)絡(luò)節(jié)點(diǎn)序列進(jìn)行優(yōu)化。在2個(gè)網(wǎng)絡(luò)節(jié)點(diǎn)序列編碼串中隨機(jī)設(shè)置2個(gè)交叉點(diǎn)；再交換2個(gè)網(wǎng)絡(luò)節(jié)點(diǎn)序列在所設(shè)定的2個(gè)交叉點(diǎn)之間的部分編碼串，若交換后的目標(biāo)函數(shù)較小，則用交換后的解替換之前的解。

2.3算法描述

（1）參數(shù)初始化，設(shè)無(wú)線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)、螞蟻個(gè)數(shù)、初始化各個(gè)節(jié)點(diǎn)的參數(shù)及各條邊的信息，同時(shí)給出約束限制值；（2）計(jì)算每個(gè)螞蟻到終點(diǎn)后與初始目標(biāo)點(diǎn)的距離，通過(guò)計(jì)算最優(yōu)化目標(biāo)函數(shù)的值，刪掉能量較小的傳感器節(jié)點(diǎn)，記錄并選擇當(dāng)前迭代次數(shù)中的最優(yōu)解，給予最短路徑較大的信息素增強(qiáng)，對(duì)各路徑上的信息素濃度進(jìn)行更新；（3）使用二點(diǎn)交叉算子對(duì)處理節(jié)點(diǎn)序列進(jìn)行優(yōu)化；（4）重新評(píng)價(jià)各個(gè)螞蟻的適應(yīng)度值，進(jìn)行局部?jī)?yōu)化；（5）滿足適應(yīng)度函數(shù)結(jié)束條件f（Xtk）≤f（Xt-1k）或達(dá)到最大迭代次數(shù)，進(jìn)行步驟（6），否則進(jìn)行步驟（2）；（6）輸出無(wú)線傳感器網(wǎng)絡(luò)路由優(yōu)化結(jié)果。

3試驗(yàn)仿真

本仿真試驗(yàn)中，網(wǎng)絡(luò)覆蓋范圍為150 m×150 m的矩形平面區(qū)域，隨機(jī)分布100個(gè)傳感器節(jié)點(diǎn)，統(tǒng)一對(duì)節(jié)點(diǎn)進(jìn)行編號(hào)，節(jié)點(diǎn)的初始能量為0.5 J，節(jié)點(diǎn)間的有效傳輸距離20 m，試驗(yàn)中選取的螞蟻總數(shù)120只，α′=1，β′=4，ρ=0.45，Q=50，交叉概率為0.8，每個(gè)節(jié)點(diǎn)的起始能量為110 J，發(fā)送/接收1 bit數(shù)據(jù)的能耗為0.05 J/bit，最大迭代次數(shù)120。仿真試驗(yàn)對(duì)蟻群算法（AC）、粒子群算法（PSO）、動(dòng)態(tài)分簇算法（DC）、定向擴(kuò)散算法（DD）和本研究算法進(jìn)行了比較。在試驗(yàn)環(huán)境參數(shù)均相同的前提下，每種算法各運(yùn)行20次蒙特卡羅試驗(yàn)，取平均值為最終結(jié)果。endprint

3.1節(jié)能分析

無(wú)線傳感器網(wǎng)絡(luò)路由節(jié)點(diǎn)間剩余能量差異性越小越使各節(jié)點(diǎn)剩余能量均衡，有利于網(wǎng)絡(luò)生存時(shí)間提升。圖1所示為節(jié)點(diǎn)間剩余能量差異性比較。

從圖1可以看出，本研究算法的各節(jié)點(diǎn)間能量差異最小，因?yàn)楸狙芯克惴▋H對(duì)最佳路徑包含的路段增加信息素，沒(méi)有頻繁地重建路徑，比較快速地建立了較優(yōu)路徑，數(shù)據(jù)傳輸能量消耗少，因而剩余能量最多，這樣簇內(nèi)節(jié)點(diǎn)能量消耗及每輪剩余能量的差異都較小，提高了全網(wǎng)能耗均衡性。

3.2網(wǎng)絡(luò)生存時(shí)間比較分析

網(wǎng)絡(luò)生存時(shí)間仿真結(jié)果如圖2所示。根據(jù)圖2對(duì)比結(jié)果可知，本研究算法的網(wǎng)絡(luò)生存時(shí)間遠(yuǎn)遠(yuǎn)大于AC算法、PSO算法、DC算法、DD算法，隨著感知節(jié)點(diǎn)數(shù)從逐漸減少，無(wú)線傳感器網(wǎng)絡(luò)生存時(shí)間逐步降低，但是本研究算法降低速度慢于其他算法，能夠有效延長(zhǎng)整個(gè)無(wú)線傳感器網(wǎng)絡(luò)的生存時(shí)間。

3.3不同匯聚節(jié)點(diǎn)數(shù)接收數(shù)據(jù)包平均剩余能量分析

不同匯聚節(jié)點(diǎn)數(shù)接收數(shù)據(jù)包平均剩余能量分析結(jié)果如圖3所示。

從圖3可以看出，隨著匯聚節(jié)點(diǎn)接收數(shù)據(jù)包增加，節(jié)點(diǎn)的平均剩余能量不斷降低，本研究算法的歸一化剩余能量值最大，能夠提供更長(zhǎng)的網(wǎng)絡(luò)壽命和消耗更少的能量。

4總結(jié)

本研究采用改進(jìn)蟻群算法包括基于最佳路徑的目標(biāo)函數(shù)值信息素分配策略，二點(diǎn)交叉算子對(duì)信息素分配策略對(duì)應(yīng)的任意2個(gè)網(wǎng)絡(luò)節(jié)點(diǎn)序列進(jìn)行優(yōu)化，試驗(yàn)仿真顯示本研究算法使無(wú)線傳感器網(wǎng)絡(luò)路由的節(jié)點(diǎn)間剩余能量差異性最小，不同節(jié)點(diǎn)數(shù)接收數(shù)據(jù)包平均剩余能量較多，從而有效延長(zhǎng)了整個(gè)無(wú)線傳感器網(wǎng)絡(luò)的生存時(shí)間，為智慧農(nóng)業(yè)無(wú)線傳感器網(wǎng)絡(luò)路由優(yōu)化提供了一種新思路。

參考文獻(xiàn)：

[1]李樹(shù)江，佟以鑫，王向東，等. 一種基于無(wú)線傳感器網(wǎng)絡(luò)安全的能量?jī)?yōu)化路由算法[J]. 大連理工大學(xué)學(xué)報(bào)，2016，56（2）：193-201.

[2]Tiwari P K，Vidyarthi D P. Improved auto control ant colony optimization using lazy ant approach for grid scheduling problem[J]. Future Generation Computer Systems，2016，60（6）：78-89.

[3]Azharuddin M，Jana P K. Particle swarm optimization for maximizing lifetime of wireless sensor networks[J]. Computers & Electrical Engineering，2016，51（4）：26-42.

[4]Gajjar S，Sarkar M，Dasgupta K. FAMACROW：Fuzzy and ant colony optimization based combined mac，routing，and unequal clustering cross-layer protocol for wireless sensor networks[J]. Applied Soft Computing，2016，43（6）：235-247.

[5]Peng S，Low C P. Energy neutral directed diffusion for energy harvesting wireless sensor networks[J]. Computer Communications，2015，63（1）：40-52.

[6]侯文哲，陳樂(lè)瑞，孔金生. 基于改進(jìn)的混沌蟻群算法的網(wǎng)絡(luò)路由優(yōu)化研究[J]. 計(jì)算機(jī)仿真，2016，32（2）：307-310.

[7]朱永紅，丁恩杰，胡延軍. PSO優(yōu)化的能耗均衡WSNs路由算法[J]. 儀器儀表學(xué)報(bào)，2015，36（1）：78-86.

[8]譚德坤，王冠. 基于反向?qū)W習(xí)粒子群算法的無(wú)線傳感器網(wǎng)絡(luò)路由優(yōu)化[J]. 計(jì)算機(jī)測(cè)量與控制，2013，21（10）：2885-2887.

[9]賈斌，谷孝東. WSN中基于節(jié)點(diǎn)能力的路由選擇方法[J]. 科技創(chuàng)新導(dǎo)報(bào)，2015（32）：137-138.

[10]王長(zhǎng)清，黃靜. 基于協(xié)同進(jìn)化粒子群算法的無(wú)線傳感器網(wǎng)絡(luò)節(jié)能優(yōu)化覆蓋算法[J]. 河南師范大學(xué)學(xué)報(bào)（自然科學(xué)版），2016，41（1）：54-58.

[11]趙麗萍. 基于蟻群優(yōu)化的無(wú)線傳感器網(wǎng)絡(luò)路由算法[J]. 傳感器與微系統(tǒng)，2014，33（4）：112-114.

[12]鄭慧君，陳俞強(qiáng). 基于改進(jìn)蟻群的路徑導(dǎo)航算法[J]. 控制工程，2016，23（4）：608-612.

[13]倪壯，肖剛，敬忠良，等. 改進(jìn)蟻群算法的飛機(jī)沖突解脫路徑規(guī)劃方法[J]. 傳感器與微系統(tǒng)，2016，35（4）：130-133.

[14]王靈霞，趙宏. 面向云計(jì)算環(huán)境任務(wù)調(diào)度的改進(jìn)蟻群算法[J]. 工業(yè)儀表與自動(dòng)化裝置，2016（2）：3-6，42.endprint