冬小麥大田中基于改進蟻群算法的傳感器部署優化

王森 姚建斌

摘 ?要：我國作為當今世界的農業大國，小麥的產量在很大程度上影響著我國的糧食總產量和人民的生活水平。以當今智慧農業為導向，分析了傳統農業和早期智慧農業的特點及其在傳感器部署方面存在的問題。利用蟻群算法并結合傳感器距離、覆蓋范圍兩個貪婪因子優化了傳感器的節點部署，實現了通信覆蓋范圍更廣、網絡連通率更高、網絡功耗更低的目標。仿真實驗結果表明，該算法的傳感器部署密度和部署數量均有明顯的降低。

關鍵詞：智慧農業；小麥生長環境監測；節點優化部署

中圖分類號：TP393 ? 文獻標識碼：A 文章編號：2096-4706（2023）14-0142-05

Sensor Deployment Optimization Based on Improved Ant Colony Algorithm in Winter Wheat Field

WANG Sen， YAO Jianbin

（School of Information Engineering， North China University of Water Resources and Electric Power， Zhengzhou ?450046， China）

Abstract： As a major agricultural country in the world today， the output of wheat has a great impact on China's total grain output and people's living standards. Guided by today's smart agriculture， this paper analyzes the characteristics of traditional agriculture and early smart agriculture and the problems in sensor deployment. Using ant colony algorithm and combining sensor distance and coverage two greedy factors， the sensor node deployment is optimized， achieving the goal of wider communication coverage， higher network connectivity and lower network power consumption. The simulation results show that the deployment density and deployment number of sensors of the algorithm are both significantly reduced.

Keywords： smart agriculture; wheat growth environment monitoring; node optimization deployment

0 ?引 ?言

傳統農業中，小麥的監測基本上停留在人工肉眼監測階段，人工監測小麥的生長狀態不僅存在經驗化的問題，而且還需要投入大量的勞動力和時間。黨的十九屆五中全會審議通過的“十四五”規劃和2035年遠景目標建議中明確指出：未來五年中要持續強化農業科技，深入推進農業可持續發展，加快農業農村現代化建設，這對農作物的生長監測便顯得尤為重要。

而節點的部署優化直接關系到整個無線傳感網的覆蓋率、傳輸速度、傳輸質量、節點成本等問題。優質的節點部署不僅可以節約成本，而且還可以在低成本的基礎上完成高覆蓋率、高傳輸速度。隨著人工智能的不斷發展，許多學者將群優化算法應用到節點部署中，經典的算法如蟻群算法、粒子群算法，近年來也有新的算法——松鼠算法被國內外專家提出和應用。但這些算法都或多或少地存在一些缺點，如收斂性差、容易陷入局部最優等問題，需要與實際應用結合分析后再進行改進或適配。因此對傳統尋優算法做出改進后應用到傳感器節點部署中去，對智慧農業的發展具有重大意義。

1 ?智慧農業信息網絡組網結構

在現代智慧農業應用領域中，網絡中的節點主要包括感知節點、傳輸節點、動作節點。感知節點由不同類別的傳感器組成；傳輸節點主要由網絡中的路由節點、中繼節點等組成；動作節點為負責執行最終指令的節點，為了保證信息傳輸的準確性和及時性，有效降低傳輸過程中的丟包率，決定采用多個采集區域的分布式信息傳輸，具體組網設計如圖1所示。

此方案下的智慧農業通信網絡具有以下優點：

1）穩定性強。在傳感器與數據采集節點之間采用有線組網的方式可最大限度保證數據的穩定性。

2）各數據采集節點間相互獨立。星型拓撲結構保證了各數據采集節點之間不會相互影響。

3）低功耗、低成本。在混合型組網方案中，長距離傳輸均采用無線通信方式，相對于大批量部署長電纜成本大大減少。

2 ?基于改進蟻群算法的傳感器部署

傳統的蟻群算法主要應用在TSP即旅行商問題中尋找最優路徑，而將蟻群算法應用于節點部署中的卻很少。蟻群算法之所以能夠應用在節點部署中，得益于它的高魯棒性和獨立性。

2.1 ?基于網格點部署的定義與描述

本文的無線傳感器網絡節點部署是基于網格點形式的，并進行如下定義：

1）小麥監測點（CP）。在監測空間中需要被傳感器監測到的且位于網格線交叉處的節點。用兩個集合WP和DP分別表示小麥待監測的點集合和小麥已經被監測到的點集合。

2）有效點（SP）。候選網格點，即傳感器下一步可部署的網格點。

根據以上定義，首先將監測空間進行網格點劃分，如圖2所示。

基于網格點的部署問題描述如下：在基于網格點劃分的區域中，部署一組傳感器節點，使得所有小麥監測點都在所部署的傳感器節點覆蓋范圍內，且保證每個傳感器都能與sink節點直接或間接通信。

2.2 ?基于蟻群算法的節點部署設計

蟻群算法是得益于真實螞蟻群覓食行為的啟發而提出的群優化算法，被廣泛應用到旅行商（TSP）等問題中，最近也被應用到網絡優化即路由節點部署等問題中。

本文將蟻群算法應用于節點部署中，即將網格中所有有效網格SP點類比為TSP問題中的城市點，將覆蓋所有小麥監測點CP作為螞蟻覓食的終結。

在算法中利用sink節點的通信范圍R，將螞蟻的初始位置全部放在以sink節點為圓心，以R為半徑的通信范圍內，然后將螞蟻每次搜索的范圍限制為小于半徑R，以此來保證每次搜索的結果可與sink節點進行通信。當第一個節點部署完后，下一個節點可部署在由sink節點與第一個傳感器節點的通信范圍共同構成的區域內，以此達到與sink節點間接通信的目的。所有節點部署完后，傳感器節點能夠完成對小麥監測點的最大覆蓋，螞蟻的一次迭代完成，過程如圖3所示。

如圖3（a）所示，當節點1部署后，螞蟻的尋優范圍擴大到由sink節點與節點1所組成范圍的并集中。該并集中的節點均可與sink節點直接或間接通信。在該并集中部署節點2，使得網絡的覆蓋范圍和通信范圍再次擴大，依此類推，部署節點3、4、5，直至傳感器全部部署完畢，且覆蓋的小麥監測點（實心圓）最多，如圖3（b）所示。下面需要解決的問題是，如何在部署少量傳感器的情況下達到上述效果，即盡可能覆蓋更多的小麥監測點。

3 ?算法改進

當小麥監測點過多時，螞蟻尋優的范圍就會迅速擴大，導致算法收斂性下降至出現無法找到最優解的情況。

3.1 ?在有效網格點集合中加入貪心策略

在實際的大田小麥監測環境中，小麥監測點的數量多達成千上萬，遠遠大于TSP問題中城市點的數量，因此本文在傳統蟻群算法中的螞蟻選擇下一城市點的步驟內加入了貪心策略，其核心思想就是在螞蟻搜索下一步的部署網格點時，剔除掉無法覆蓋其他小麥監測點的網格點，以此減小螞蟻本次的搜索范圍。對此，在2.1節中基于蟻群算法在網格中部署問題提出的兩點定義中給出了進一步的定義：

1）候選網格點集合C [ ]。既要滿足SP點定義的所有點集合，同時也要能夠覆蓋未被覆蓋的小麥監測點（WP）的點的集合。

2）待監測點集合W [ ]。滿足2.1節中對WP點定義的所有點集合，即還未被已部署傳感器覆蓋到的小麥監測點的集合。

3）有效部署網格點集合CE [ ]。既滿足SP點的定義，同時也要能夠覆蓋未被覆蓋的小麥監測點（WP）的點的集合。

3.2 ?改進算法在網格點部署中的模型

為了提高蟻群算法的適用性以及降低螞蟻的搜索空間，結合傳統蟻群算法的模型提出以下優化算法策略。

3.2.1 ?下一個部署網格點的選擇

下一個部署網格點的選擇共有兩個步驟：一是螞蟻識別出下一個候選點的集合（C [ ]）。二是螞蟻利用隨機局部決策策略選擇候選點集合中的某個點作為下一個部署的位置。在這個過程中，采用貪心策略來減少候選網格點的數量，在有效的部署網格點集合（CE [ ]）中選擇某個點作為下一個部署目標。在實際算法中用CN [ ]表示下一次可以部署的網格點集合。

依據傳統蟻群算法，螞蟻k從一個網格點i移動到網格點j的選擇概率公式為：

（1）

其中，τim表示m的信息素值，α表示控制信息素影響的參數，β表示控制 ?影響的參數。這里，α反映了搜索過程中網格點剩余信息素濃度的相對重要性，β反映了影響啟發式信息的相對重要性（期望）。如果α和β的值恒定，則算法會在前期陷入局部最優的情況，為解決這種問題，需要對α做出如下修改：

（2）

其中，γ和λ表示常數，且γ ∈ [0，1]，λ ∈ [0，1]，n表示當前的搜索次數，Nmax表示最大的搜索次數。通過（2）式的操作，在算法早期，即n值較小時，算法的搜索速度較快，隨著算法的迭代，搜索速度又會逐漸趨于緩慢。這樣可保證螞蟻的搜索能力，使螞蟻更難陷入局部最優的情況。

在式（1）中， 表示第k只螞蟻選擇鏈路i、j的期望值，即選擇i、j的貪婪因素，可定義為：

（3）

其中，Cu表示u節點可以覆蓋的小麥待監測點（WP）的集合， 表示小麥待監測點m的未覆蓋次數，Distanceij表示i、j兩點之間的歐氏距離。引入Distanceij的目的是使下一個待部署的網格點能夠部署在更遠的位置，從而減少傳感器部署的密度。使用CoverWP來表示目前沒有被傳感器覆蓋的小麥監測點集合（W []），即：

（4）

（5）

3.2.2 ?息素更新策略

網格點從i到j的信息素更新執行如下：

（6）

其中，ρ表示信息素消散系數，引入信息素消散系數的目的是在蟻群的搜索過程中，將不好網格點的信息素濃度慢慢消散掉，以減少該點對后續螞蟻的吸引，如果點j被當作當前迭代中的最優解，則：

（7）

其中，Lbest表示最優解中使用的傳感器數量。所使用的傳感器數量越少，增加的信息素濃度 ?越大，后續螞蟻選擇該點的概率就越大。在式（6）中，i、j兩點信息素的值被約束在τmin和τmax之間，即τmin≤τij≤τmax，τmax可表示為：

（8）

其中，對τmax的限制，是為了防止早期螞蟻在某個網格點獲得較大的信息素濃度時，陷入局部最優導致算法早期收斂的情況。即信息素蒸發系數越大，相對的信息素濃度最大值則會越小。

通過以上對蟻群算法做的改進（即加入貪婪因子CoverWP和Distanceij），使算法能夠在保證覆蓋范圍的同時降低傳感器部署密度，從而降低部署成本和網絡功耗。此外，通過對影響因子α的修改以及對信息素濃度τmax的限制來保證算法不會在早期陷入局部最優的情況，得出改進蟻群算法（ACO-EDY）。

4 ?算法評價

為了驗證ACO-EDY算法在網格點部署問題中的實際性能，在MATLAB 2016a中對該算法進行仿真實驗。分析了ACO-EDY算法在部署平臺中的運行實例，將ACO-EDY算法與基本蟻群算法在網格點部署中的應用上與算法PSO-ACO進行比較。分別基于傳感器數量、覆蓋密度等評價指標對三個算法的性能進行比較。

在ACO-EDY算法中，取α = 1，β = 5，ρ = 0.5。算法的仿真運行結果如圖4所示。

觀察可得，網格的步長和傳感器的通信范圍對算法的結果均有影響，但在圖4（c）和圖4（d）中，即使是再次縮小了網格步長，圖4（d）在相同的傳感器個數情況下，覆蓋的監控點卻比圖4（c）多。這說明對網格點進行精細的劃分，最終并不會對算法結果產生很大影響，而改變傳感器和sink節點的通信半徑卻會對算法的結果產生較大的影響。

在一塊區域面積固定的網格區域中，在不同的網格劃分和通信半徑上與傳統蟻群算法ACO和PSO-ACO進行比較，如表1所示。

依據表1的對比試驗分析，隨著網格被劃分得更加精細，相較于PSO-ACO，ACO-EDY算法能夠提供更好的部署方案。然而，在基本蟻群算法中，由于螞蟻的搜索空間不斷增加，導致最終得出的傳感器部署數量遠遠大于優化算法的部署數量。

5 ?結 ?論

本文將蟻群算法與對冬小麥監測傳感器的部署問題相結合，在保證網絡全連通的情況下，在基本蟻群算法內加入了貪心因子CoverWP和Distanceij，得出優化后的算法ACO-EDY。并在結果分析中分別考慮了傳感器部署對監測點的覆蓋情況和部署傳感器的密度，相比基本蟻群算法有效降低了傳感器的部署數量，同時將本文算法與PSO-ACO作對比，節點的部署數量下降7%～11%，同時節點的分布密度趨于合理，能夠進一步降低部署成本和網絡功耗。本文的研究結果將為冬小麥生長環境監測提供有益參考。

參考文獻：

[1] 周國民.淺議智慧農業 [J].農業網絡信息，2009（10）：5-7+27.

[2] 李保國，劉忠.數字農業與農業信息化發展的現狀與趨勢 [C]//2005年中國數字農業與農村信息化學術研究研討會.北京：中國農業出版社，2005：157-163.

[3] 李寒.基于物聯網的智慧農業大棚控制系統設計 [D].保定：河北大學，2021.

[4] CRUZ D P F，MAIA R D，CASTRO L N D. A critical discussion into the core of swarm intelligence algorithms [J].Evolutionary Intelligence，2019，12（2）：189-200.

[5] ZHANG Z J，HU F N，ZHANG N. Ant colony algorithm for satellite control resource scheduling problem [J].Applied Intelligence，2018，48（10）：3295-3305.

[6] WU X X，SUN M Y，CHEN X，et al. Empirical study of particle swarm optimization inspired by Lotka–Volterra model in Ecology [J].Soft Computing，2019，23（14）：5571-5582.

[7] JAIN M，SINGH V，RANI A. A novel nature-inspired algorithm for optimization： Squirrel search algorithm [J].Swarm and evolutionary computation，2018，44：148-175.

[8] 劉昊，李靜，魯旭濤.5G背景下智慧農業通信節點部署策略 [J].西安交通大學學報，2020，54（10）：45-53.

[9] 趙春江.智慧農業的發展現狀與未來展望 [J].中國農業文摘-農業工程，2021，33（6）：4-8.

[10] GOSS S，ARON S，DENEUBOURG J L，et al. Self-organized shortcuts in the Argentine ant [J].Naturwissenschaften，1989，76（12）：579-581.

[11] 李道亮.物聯網與智慧農業 [J].農業工程，2012，2（1）：1-7.

[12] 張新，陳蘭生，趙俊.基于物聯網技術的智慧農業大棚設計與應用 [J].中國農機化學報，2015，36（5）：90-95.

[13] 康孟珍，王秀娟，華凈，等.平行農業：邁向智慧農業的智能技術 [J].智能科學與技術學報，2019，1（2）：107-117.

[14] 黃亮.基于改進蟻群算法的無線傳感器網絡節點部署 [J].計算機測量與控制，2010，18（9）：2210-2212.

[15] WANG H，LI Y M，ZHANG L L，et al. A Self-Deployment Algorithm for Maintaining Maximum Coverage and Connectivity in Underwater Acoustic Sensor Networks Based on an Ant Colony Optimization [J].Applied Sciences，2019，9（7）：1479.

[16] 張熒.改進蟻群算法在車載自組網節點部署中的應用 [D].蘭州：蘭州大學，2014.

[17] 姚建斌，張英娜，劉建華.基于卷積神經網絡和遷移學習的小麥病蟲害識別 [J].華北水利水電大學學報：自然科學版，2022，43（2）：102-108.

作者簡介：王森（1998—），男，漢族，河南鄭州人，碩士研究生在讀，研究方向：物聯網、智慧農業研究；姚建斌（1982—），男，漢族，山西運城人，副教授，博士研究生，研究方向：農業信息化管理、圖像處理等方面的研究。