基于改進粒子群的農田WSN 路由優化方法

繆祎晟，趙春江，吳華瑞

（1.北京工業大學 信息學部，北京 100124；2.國家農業信息化工程技術研究中心，北京 100097；3.農業農村部農業信息技術重點實驗室，北京 100097）

0 概述

以無線傳感器網絡（Wireless Sensor Network，WSN）為代表的物聯網技術，是實現農業生產中環境、土壤、動植物生理等實時監測以及溫度、水肥在線調控的重要技術手段。通過對環境、水肥等進行精確感知與精準調控，可以減少不必要的水肥藥消耗，提高農產品的產量與品質，實現綠色高效生產。WSN 本身具有能量敏感、成本低等特點，而大規模農田監測網絡還存在覆蓋區域廣、種植周期長、能量供給不便、環境復雜多變等現實情況，如何實現穩定可靠的數據傳輸匯集是實際應用中的難點所在［1］。

在農田WSN 監測應用中，節點異構、環境動態變化等原因進一步提高了優化網絡能耗和負載均衡的難度［2］。為提高農田環境下網絡的使用壽命與長周期工作時的穩定性，本文從動態環境適配角度開展農田WSN路由優化研究，并提出一種基于改進粒子群（Particle Swarm Optimization，PSO）的路由優化算法RD-PSO。將農田WSN 路由路徑作為粒子進行尋優，以鏈路質量、節點剩余能量等作為粒子參數并量化，優先選擇鏈路質量好、剩余能量高的路徑進行數據傳輸，以延長無線監測網絡在農田WSN 復雜動態環境中的使用壽命。

1 農業WSN 路由研究現狀

WSN 具有資源受限的特點，其網絡能耗優化一直以來都是研究人員關注的焦點，而路由是實現低能耗傳輸的重要環節。孫想等［3］針對頻繁簇首選舉產生過多能耗的問題，提出一種能量逼近式的簇首選擇方法，該方法連續任命某一節點擔任簇首直至逼近簇內平均剩余能量，有效減少了簇首選舉產生的開銷，延長了網絡壽命。李華等［4］提出一種基于近源數據聚合的低能耗路由協議，其根據WSN 中數據分布密度的不同來選擇數據融合的節點組合與轉發路徑，實現了網絡能耗下降與擁塞控制。黃博文等［5］提出一種K 中心的近似算法來挑選簇首，使簇內節點到簇首的距離最優，進而降低與均衡能耗。上述方法在優化WSN 網絡能耗時均針對靜態的網絡條件，而農田WSN 監測應用中的環境是動態變化的，從而對網絡路由優化算法提出了新的挑戰。

群體智能算法［6］是求解復雜動態問題的有效手段，國內外學者在基于群體智能算法的WSN 路由算法優化方面開展了諸多研究。牛祺君等［7］設計一種基于節點剩余能量的簇首輪換機制，并通過蜂群算法優化簇首節點路由選擇，減少了節點能量消耗，延長了網絡壽命。謝英輝等［8］采用遺傳算法縮短了sink 節點的移動距離，在簡化網絡拓撲結構的同時也得出了近似最優的能耗優化方案。ARJUNAN等［9］首先采用聚類算法進行節點分簇，再通過蟻群算法優化簇首節點間路由，提高了路由算法在寬矩形區域中的適應度。FU等［10］基于人工勢場法，結合節點采集的數據判斷節點所處環境的狀況，進而使得優化后的路由盡可能地避開了一些不期望到達的節點。

利用群體智能算法可以在迭代次數較少的情況下求得動態條件下近似的全局最優解，算法效率高，適合于資源受限的農田WSN。針對農田應用場景下環境、作物生長等對無線網絡傳輸的影響，本文提出一種基于改進PSO 的路由優化算法，通過引入網絡鏈路質量因子提高PSO 算法的環境適配性，同時綜合考慮節點剩余能量、路徑轉發跳數等因素，以期實現農田復雜動態環境下的能耗性能最優。

2 網絡模型與定義

2.1 網絡模型

本文討論的大規模農田WSN 場景假定有N個傳感節點隨機地被部署在一個二維矩形區域內，同時假定該WSN 具有如下性質［2，11］：

1）網絡屬于密度較高的靜態網絡，即傳感節點部署后位置保持不變，節點密度足以保證網絡連通性以及對監測區域的覆蓋度。

2）sink 節點位置固定且唯一，其無線發射功率可控且能量不受限制。

3）傳感節點類型同構，初始能量均相同，為E0，且不能補充。

4）傳感節點每輪消耗的能量不一定相同，即能量異構。

5）節點具有自我能量感知的能力，可獲得剩余能量數據。

2.2 能耗模型

基于文獻［12］的無線通信能耗模型，可以認為節點發送lbit 數據需要消耗的能量Etx為：

其中：Eelec代表發射電路或接收電路傳輸1 bit 數據消耗的能量；d為發射節點與接收節點之間的距離；d0=為模型的距離閾值；εf和εm為2 種模式下的功率放大系數。

3 基于反向探測的改進PSO 算法

農田WSN 中的路由選擇是典型的組合優化問題，而群體智能算法具有自關聯和自組織的特點［13］，適用于解決農田WSN 路由尋優問題。灰狼算法［14］、蟻群算法［15］等新興智能方法具有參數少、結構簡單、易于實現的特點，在WSN 路由協議優化方面已被廣泛應用，但對于動態環境仍存在精度低、優化維數低、收斂速度慢等不足。在求解規模較大的優化問題時，PSO 算法能夠在更短時間內獲得優化解［16］，有利于農田感知數據的迅速傳輸。本文提出一種基于反向探測的改進PSO（Reverse Detection based PSO，RD-PSO）算法，通過改進算法的適應度函數與初始化方法減少網絡傳輸能耗，進一步提高PSO 算法對路由路徑的搜索迭代效率。

3.1 適應度函數構建與粒子更新

農田WSN 路由優化問題示意圖如圖1 所示，從初化化路徑s1開始，通過算法迭代向最優路徑s2逼近。優化過程中首先需要考慮的是降低節點能耗以及提高節點間的能量均衡性，因此，考慮從節點剩余能量和路徑轉發能耗2 個方面進行加權，優化算法適應度函數，即最優路徑應滿足路徑能耗盡可能小、路徑上節點平均剩余能量以及最低剩余能量盡可能高。同時，考慮到跳數對路由算法的效率以及網絡能耗性能有顯著影響，因此，在求解最優路徑時需要使得跳數盡可能少。此外，由于農田環境具有動態多徑衰落特性，因此本文將鏈路質量也作為適應度函數的權重因子之一。

圖1 基于PSO 的WSN 路徑選擇示意圖Fig.1 Schematic diagram of WSN path selection based on PSO

從圖1 可以看出，當前路徑和最優路徑存在多個交點cross1，cross2，…，crossn，這些交點可以理解為路徑選擇中的關鍵點，也是WSN 常見的能耗節點，對于網絡能耗優化有著重要影響。對于一次數據傳輸路徑選擇過程，記源節點到sink 節點的一條多跳路徑為Pi，其對應PSO 算法中的一個粒子i，定義適應度函數f如式（2）所示［12，17］：

RD-PSO 算法根據初始化位置與速度計算個體最優和全局最優位置，并開始迭代尋優。粒子速度更新方法如式（3）所示［19］：

其中：ω是慣性因子；c1、c2是學習因子；r1、r2為0～1 之間的隨機數，它們可使粒子變異時具有一定的隨機性，避免落入局部最優。

粒子位置的更新方法如式（4）所示：

3.2 基于反向探測的粒子初始化

在基于PSO 的WSN 路由優化問題中，一個粒子初始化就是隨機生成一條從源節點到sink 節點的路徑。傳統方法以sink 節點向網絡發送探測包的方式，確定各個節點到sink 節點的跳數值［20］。在生成初始化拓撲時，當前節點始終選擇跳數值小于自身跳數值的節點作為下一跳節點，并保留跳數小于所設定最大跳數的路徑，從而保證路徑方向總體趨向于sink 節點。傳統探測包方法適用于管道、深井等帶狀空間，但由于缺少在橫向空間上的約束，使得其在寬矩形區域中易出現迭代效率低等問題［21］。為此，本文提出一種針對寬矩形農田WSN 的反向探測粒子初始化方法。

在本文方法中，由sink 節點向其一跳范圍內的傳感節點廣播發送探測包信息，傳感節點接收到探測包后保存其距sink 節點的跳數值，并將值加1 后轉發至其他節點，若某節點接收到多個值，則以收到的最小值作為其自身的值。由此近似地形成以sink 節點為圓心、半徑不同的多個圓環，各圓環區域內的值相同。同時，為了建立橫向維度上的重復路徑約束，選擇一條區域邊界，如圖2 中右側邊界所示，以最靠近邊界的傳感器（圖2中的節點1）發送反向探測包，記節點1的值為1，其他轉發節點的值增加方法與相同。

圖2 基于反向探測的初始化過程Fig.2 Initialization process based on reverse detection

其中：eva（i）為根據Ni節點

值計算的節點得分，其值為i節點

差值的倒數，如式（6）所示：

3.3 RD-PSO 算法步驟

RD-PSO 算法在農田WSN 節點初始化完成后，按照3.2 節所述內容進行反向探測，完成粒子位置和速度的初始化，并依據節點能耗、剩余能量、距離sink 的最小跳數以及鏈路質量等構造適應度函數，通過粒子群迭代優化確定符合農田復雜動態環境的最優路由路徑。算法具體步驟如下：

1）根據3.2 節內容進行網絡節點反向探測，建立各節點到sink 節點的初始化路徑Pi以及相應粒子i的初始化位置與速度。

2）按照式（2）計算每個粒子i的適應度函數值。

3）按照式（3）、式（4）求解個體極值、全局極值以及粒子位置、速度更新值。

4）重復第2 步和第3 步，直至個體極值穩定收斂于全局極值或達到最大迭代次數。

5）根據得出的最優路由路徑開始進行數據多跳傳輸，同時獲取節點能量、鏈路質量的數據，在下一步數據傳輸時進行路由路徑更新。

根據上述算法流程可知，本文通過反向探測對傳輸路徑、粒子速度與位置進行初始化優化，然后利用粒子更新得到農田WSN 路由。因此，本文算法復雜度為O(iter1·N1·T1(f))，其中：iter1為迭代次數；N1為粒子數量；T1（f）為與適應度函數、粒子維度等因素相關的一次迭代時間。灰狼算法的復雜度為O(iter2·N2·T2(f))，其中：iter2為迭代次數；N2為種群數量；T2（f）為與適應度函數、種群維度等因素相關的一次迭代時間。樽海鞘群算法的復雜度為O(iter3·N3·T3(f))，其中：iter3為迭代次數；N3為種群數量；T3（f）為與適應度函數、種群維度等因素相關的一次迭代時間。本文算法與灰狼算法等群體智能算法的復雜度一致，但在求解大規模優化問題時，灰狼算法等存在精度低、優化維數低、收斂速度慢等不足，而PSO 算法能夠在更短時間內獲得優化解［16］，有利于提高農田監測網絡的整體效率。本文算法基于反向探測包理論縮短了初始位置與最優解的距離，進一步提高了PSO 算法的收斂速度。

4 實驗與結果分析

為對RD-PSO 算法的性能進行驗證，首先將其與傳統PSO 算法［22］進行算法迭代收斂性能仿真對比，然后選取ELMR［23］、EEABR［24］和MR-PSO 算法［25］進行對比實驗。實驗場景具體參數設置如表1 所示。

表1 仿真參數設置Table 1 Simulation parameters setting

在目標區域內隨機部署100 個節點，完成20 次獨立隨機部署并分別進行性能仿真實驗，取平均值作為最終結果。

對比RD-PSO算法與傳統PSO算法［15］的收斂速度，20 組獨立實驗中算法收斂迭代次數對比結果如圖3 所示。從圖3 可以看出，與傳統PSO 算法相比，RD-PSO算法收斂所需的迭代次數整體較低，且波動幅度比傳統PSO 算法小。傳統PSO 算法由于隨機性較大，路由算法的收斂會因節點分布和狀態的不同而產生較大波動。對于每組實驗節點而言，本文改進算法的收斂速度均優于傳統PSO 算法，其原因有2 個方面：一是本文算法優化了粒子初始化方法，使得初始化粒子更接近最優解；二是虛擬力影響粒子的尋優過程，使得一條路徑向全局最優路徑的擬合速度加快。

圖3 RD-PSO 算法與傳統PSO 算法的收斂速度對比Fig.3 Comparison of convergence speed between RD-PSO algorithm and traditional PSO algorithm

不同路由算法的網絡生存周期對比如圖4 所示，可以看出，當系統運行約300 輪時，EEABR、MR-PSO算法開始出現死亡節點，當系統運行約400輪時，ELMR、RD-PSO 算法開始出現死亡節點。從10%節點死亡時間來看，ELMR 算法為520 輪，EEABR 算法為450 輪，MR-PSO 算法為700 輪，RD-PSO 算法約為820 輪；從全部節點死亡時間來看，ELMR 算法約為700 輪，EEABR和MR-PSO 算法約為800 輪，RD-PSO 算法約為850 輪，表明RD-PSO 算法的能耗性能最優，其次是MR-PSO 算法，ELMR 和EEABR 這2 種算法相對較 差。

圖4 不同路由算法的網絡生命周期對比Fig.4 Comparison of network life cycle of different routing algorithms

不同路由算法的網絡節點剩余能量均方差對比如圖5 所示，從中可以看出：ELMR 算法剩余能量均方差從一開始就迅速上升，在250 輪～450 輪時達到較高水平，300 輪峰值處約為E0的4.5%，450 輪后ELMR算法的剩余能量均方差開始逐步下降，對應圖6 中也開始出現明顯的存活節點數量減少，直到700 輪附近開始逐步減少至0；EEABR 算法剩余能量均方差在100 輪處達到最高，約為E0的2%，之后略微下降，在200～500 輪間維持在0.004～0.005 J 之間，之后緩慢下降至0；MR-PSO 算法剩余能量均方差整體上明顯低于ELMR 和EEABR，但高于RD-PSO，其剩余能量均方差大部分保持在0.002 J 附近；RD-PSO 算法的能耗均衡性最好，其剩余能量均方差始終維持在0.001 J以下。圖5表明，ELMR 和EEABR 算法的能耗均衡效果欠佳，而RD-PSO 算法從節點剩余能量角度對路由算法進行的能耗均衡改進取得了顯著效果。

圖5 不同路由算法的節點剩余能量均方差對比Fig.5 Comparison of mean square error of node residual energy between different routing algorithms

不同路由算法的網絡傳輸平均跳數對比如圖6所示，從中可以看出：整體上ELMR 算法的平均跳數最多，RD-PSO 算法最低，EEABR 與MR-PSO 算法居中，MR-PSO算法略高于EEABR算法；從平均跳數變化上看，ELMR算法初始跳數最大，開始后逐步下降，約至300輪時降到局部低點，后逐步上升，在500輪后迅速下降至最低，EEABR算法初始跳數最大，后逐步下降至6跳并穩定，在700輪后迅速下降至最低，MR-PSO算法在前300輪時平均跳數穩定在6跳，后整體提高到7跳、8跳，在750輪后迅速降至最低，RD-PSO算法在前450輪穩定在4跳、5跳，550輪后整體上升至5跳、6跳并保持穩定，在850輪后迅速降至最低。

圖6 不同路由算法的平均跳數對比Fig.6 Comparison of average hops of different routing algorithms

從適應度函數對跳數的約束定義中不難得出，跳數較小的算法具有更佳的能耗性能，因此，圖6 結果也驗證了圖4、圖5中算法的能耗分析結果。

5 結束語

路由協議作為網絡數據采集過程中的重要環節，對網絡性能的影響重大，路由能耗優化是近年來農田WSN 領域的研究熱點。本文針對農田復雜動態環境下WSN 監測應用中的能耗優化問題，在PSO算法的基礎上提出一種改進的路由優化算法RDPSO，其根據農田WSN 應用中的剩余能量、傳輸跳數、鏈路質量等因素構建適應度函數，并采用反向探測的方式提高粒子初始化的效率。實驗結果表明，相對ELMR、EEABR 和MR-PSO 路由算法，RD-PSO算法可以提高節點間的能耗均衡效果，延長網絡生命周期，在農田復雜動態環境下實現高效可靠的WSN 數據匯集。開放農田中氣象環境復雜，作物分布密集，這造成了農田WSN 中傳輸鏈路質量不穩定、數據傳輸可靠性不高等問題。因此，后續將引入機會路由理論，結合群體智能算法設計高效的農田數據機會傳輸機制，進一步提高網絡能效并延長網絡壽命。