面向大規模農業傳感器網絡的多目標鴿群優化定位算法

鄧小武，石元泉，李森林，李偉，鄧紹偉

（懷化學院計算機科學與工程學院/武陵山片區生態農業智能控制技術湖南省重點實驗室，湖南懷化418008）

面向大規模農業傳感器網絡的多目標鴿群優化定位算法

鄧小武，石元泉，李森林，李偉，鄧紹偉

（懷化學院計算機科學與工程學院/武陵山片區生態農業智能控制技術湖南省重點實驗室，湖南懷化418008）

針對單目標優化函數的農業傳感器網絡定位精度不高問題，基于多目標鴿群優化算法，提出了多目標鴿群定位算法，用于求解傳感器網絡的多目標優化定位問題.多目標優化函數由空間距離函數與幾何拓撲函數構成，通過多目標鴿群優化算法得到其優化解.仿真實驗表明，該方法具有良好的魯棒性，極大地提高了傳感器節點的定位精度.

傳感器定位；多目標定位優化；多目標鴿群優化算法

1 引言

傳感器網絡是由大量部署在監控區域內的、由具有無線通信與計算能力的傳感器節點通過自組織方式組成的分布式智能化網絡系統，是物聯網的關鍵技術之一[1].可以實時感知所需要的信息，以實現實時監控對象，并對這些信息進行處理，傳送給用戶.因此，傳感器網絡成為采集農田信息、提高農田管理水平及增加作物產量的重要手段[2].農業傳感器網絡能精準地獲取農作物的生長信息，并即使將信息反饋給用戶，為操作者提供現場監控的依據.在農業傳感器網絡中，位置信息對傳感器網絡的監測活動至關重要，傳感器節點定位是重要環節，大量節點必須確定位置信息才能進行有效的環境信息監測.而農業節點位置變化較多，而且傳感器網絡節點受能量有限、規模較大和軟硬件條件復雜、通信環境多變通信距離有限等因素限制，制約了節點位置信息的獲取，因此，如何在這些制約因素條件下提供高精度的定位信息是大規模農業傳感器網絡系統的研究重點之一.

群體智能優化算法是一種新型的概率搜索算法，在求解優化問題時，不要求求解問題必須具備完整的數學意義，即不要求計算處理的問題是連續可導.在求解無法建立精確數學模型與非線性問題方面，群體智能優化算法比傳統數學算法有效、簡潔.近年來，群體智能優化算法在農業傳感器網絡定位應用越來越廣泛.文獻[3-5]將遺傳算法應用于解決傳感器節點定位問題，表現出了較好的定位效果.在文獻[6]中，Gopakumar等人運用粒子群優化（Particle Swarm Optimization，PSO）算法求解定位誤差最小化問題.在文獻[7]中，Namin等首先應用Dv-distance方法估計未知節點位置，再應用PSO算法進行定位；文獻[8]將PSO與Dv-hop算法結合對未知節點進行定位.文獻[9]對最小二乘方法對測距誤差敏感的不足，提出一種基于布谷鳥搜索算法的無線傳感器網絡節點定位算法.該算法利用全局和局部尋優能力強的布谷鳥算法求解定位過程中的多維約束優化問題，通過設定相應的約束適應度函數來減小定位過程的搜索范圍，加快了收斂速度，能夠快速地確定未知節點的位置.通過引入群體智能優化算法，在一定程度上減少了定位誤差，但是這些方法主要是針對單目標優化函數求解傳感器節點定位問題，未知節點定位只滿足空間距離約束，而沒有涉及到幾何拓撲約束，導致定位精度不高.鴿群優化算法[10]作為一種新興的仿生群體智能算法，具有簡單可行、良好的魯棒性等優點，這為優化傳感器節點的定位性能提供了新的研究思路.

文本提出了一種面向農業傳感器網絡定位的多目標鴿群優化算法，該方法首先將傳感器定位轉化為空間距離約束與幾何拓撲約束的多目標優化問題，然后引入多目標鴿群優化算法對定位目標函數求解，估計未知節點位置，最后從不同方面對算法性能進行了實驗驗證.實驗結果表明，該方法明顯優于單目標定位問題的群體智能算法，有效地提高了定位精度.

2 多目標節點定位模型

未知節點的坐標需要滿足空間距離約束和幾何拓撲約束，空間距離約束主要目的是使估計的坐標值更加逼近實際值，而幾何拓撲約束能使網絡拓撲避免形成與實際情況不一致的拓撲結構.

假設n個傳感器節點被部署在二維空間，其中包括m個信標節點（位置已知）和（n-m）個未知節點（m

傳感器節點i的鄰居節點集Ni和其補集Ni定義為

其中R是傳感器節點i的通信半徑.

空間距離約束的目標函數表示為

幾何拓撲約束的目標函數表示為

幾何拓撲表示網絡連通性約束，它不滿足非信標節點的當前估計位置[12].δij表示為

空間距離和幾何拓撲約束隱含傳感器節點坐標的精度.未知節點的估計坐標精度越高，會使兩個目標函數的值就越小，因此，將計算未知節點的坐標轉化為求解多目標優化解問題.

3 多目標鴿群優化定位算法

3.1 多目標鴿群優化的數學模型

在多目標鴿群優化定位算法（multi-objective pigeon-inspiredoptimizationlocalizationalgorithm，MPIOLA）中，將（n-m）個未知傳感器節點的坐標作為決策變量，而由目標函數（3）和（5）式構成多目標函數F（X），因此，將多目標鴿群優化定位形式化如下的數學模型

3.2 多目標鴿群優化算法

多目標鴿群優化算法框架涉及一些關鍵性方法[13]，如合并算子（consolidation operator）和Pareto分類方法（Paretosortingscheme）.Pareto分類方法主要實現對鴿群個體的分類和等級劃分，而合并算子是將用于鴿群導航的地圖和指南針算子與地標算子進行融合形成一個整體.

3.2.1 Pareto分類方法

Pareto分類方法通過非支配分類算子（nondominated sorting operator）與擁擠比較算子（crowdedcomparison operator）來實現鴿群的分類和等級劃分.

（1）非支配分類算子

第i只鴿子的位置Xj優于第j只鴿子的位置，當且僅當滿足如下條件：

其中fk為第k個目標函數.（8）式是一個最小化問題，而對于最大化問題，fk越大越好.通過非支配分類算子將鴿群中的鴿子分類到不同子集中.

（2）擁擠比較算子

假如所有的鴿子已經被分類到m個集合中，擁擠比較算子通過比較鴿子的擁擠距離將每個集合中的鴿子進行等級劃分.集合中第i只鴿子的擁擠距離定義為：

j解的多樣性.

3.2.2 合并算子

在多目標鴿群優化算法中，地圖和指南針算子與地標算法進行融合，合并在一個迭代循環中.

其中Ndec為每次迭代循環中被淘汰的鴿子數量，NCmax表示最大的迭代數次，tr為過渡因子（transition factor）.隨著迭代次數nc的增加，Xgbest對Xnic的影響力逐漸下降，Xnic更多地取決Xncec

n-t1er.

在導航工具過渡因子tr的作用下，兩種操作算子之間的交接工作能實現平穩地過渡.

在多目標鴿群優化算法中，歸檔A用于存儲非支配方法和求解Xgbest與Xncec

n-t1er.

首先，在將X存儲在X*后，將

SX

1中鴿子添加到歸檔A，通過等式（11）求解Xnce

cn-t1e

r.

其次，Pareto分類方法用于估算A中每個鴿子的適應度值，因此，根據鴿子的適應度確定其是否能被存儲在歸檔A[14].這樣歸檔A就吸收SA中當前優勝非支配

1解，而淘汰其他集中的劣勢解.第三步，隨機在歸檔A選擇一個鴿子作為Xgbest.

3.2.3 基于多目標鴿群優化的定位算法

多目標鴿群優化定位算法步驟如：

步驟1隨機初始化鴿群的位置X1和速度V1，確定最大的迭代次數NCmax

步驟2通過Pareto分類方法估算鴿子的位置X，由式（11）計算并將的鴿子添加到歸檔A；

步驟3通過非支配排序方法估算A中鴿子位置，A=SA1；

步驟4在A中隨機選擇一個鴿子作為Xgbest；

步驟5根據等式（10）更新鴿子位置X與速度V；

步驟6更新迭代次數nc=nc+1；

步驟7如果迭代次數小于最大迭代次數，則到步驟2繼續執行，否則估算鴿群的當前位置X，并輸出Pareto前沿

4 性能分析

4.1 評估參數

在matlab仿真實驗平臺構建一個100 m×100 m二維區域對本文提出的定位算法進行實驗仿真分析.隨機部署n個傳感器節點，其中信標節點為m個，未知節點為（n-m）個.假設RSSI測距誤差eij服從均值為零、方差為σ2=βr2ij（β=0.1）的高斯分布[15].

定位誤差一般與傳感器節點的通信半徑有關，因此，基于通信半徑，我們定義了兩種定位誤差用于評估算法的定位性能.一種是通過式（12）計算單個未知節點的定位誤差（OneErrors），只要用于評估每個節點的性能.另外一種是由（13）式定義的平均定位誤差（AvgError），

4.2 定位精度

在信標節點占傳感器網絡節點數20%的條件下，用100個未知節點的單個定位誤差來評估MOPIOLA和PIO算法[16]的定位精度.單個節點定位誤差的分布情況如表1所示，在MOPIOLA算法中，45個傳感器節點的單個節點誤差在0~5%之間，而在PIO算法中，只有10個節點在0~5%之間.PIO算法有20個傳感器節點的單個節點定位誤差超過30%，而MOPIOLA只有5個傳感器節點.

表1表明，MOPIOLA算法的定位精度明顯比PIO算法要高，即MOPIOLA算法估計位置與實際位置的偏差更小.這說明MOPIOLA算法穩定性更好，能有效地提高節點的定位精度.這是由于通過目標函數f2將幾何拓撲約束限制在一個合理的拓撲結構中，這能降低定位誤差.

4.3 MOPIOLA的魯棒性

下面分別從節點密度、信標節點數和通信半徑的情況下，通過平均定位誤差比較算法的魯棒性.

4.3.1 節點密度對定位性能的影響

在保持信標節點比例為20%和通信半徑R=20 m的情況下，改變節點密度和傳感器網絡節點總數得到表2所示三種算法的平均定位誤差.可以看出，隨著傳感器網絡節點數的不斷增加，三種算法的平均定位誤差都逐漸減少，當節點數超過100時，對定位誤差的影響力變小.由于MOPIOLA算法考慮了幾何拓撲約束，因此，它產生的定位誤差比PIO和PAES小.

4.3.2 信標節點數比例對定位性能的影響

在網絡節點總數n=120和通信半徑R=20 m的條件下，不同信標節點數量的平均定位誤差如表3所示.可以看出，隨著信標節點數量的不斷增加，三種算法的平均定位誤差都逐漸減小，這是由于未知節點四周的信標節點增多，提高了定位精度.在相同信標節點數量的情況下，MOPIOLA算法的定位精度要高于PIO和PAES算法，這是因為PIO與PAES算法只考慮空間距離約束目標函數，并沒有涉及幾何拓撲約束目標函數所導致的.

表1 單節點定位誤差OneError范圍分布

表2 不同節點數定位誤差

表3 不同信標節點比例的定位誤差

表4 不同通信半徑的定位誤差

4.3.3 通信半徑對定位性能的影響

傳感器網絡節點總數為n=120和信標節點數量為20%，通信半徑R與平均定位誤差的關系如表4所示.可以看出，隨著通信半徑的不斷增大，三種算法的定位誤差呈現減小趨勢，這是因為節點通信半徑增大時，未知節點能與更多的鄰居節點進行通信，進而提高了智能優化算的搜索性能.當通信半徑增大到30 m時，MOPIOLA算法能使定位誤差繼續減小，而PAES算法開始增大，這是由于較大的通信半徑使第一層和第二層的鄰居節點增多，進一步導致在PAES中定義的兩類未知節點距離誤差增大所致.

5 結束語

本文提出了一種基于多目標鴿群優化的傳感器網絡定位算法，該算法將節點定位問題轉化為空間距離約束和幾何拓撲約束的優化模型，引入多目標鴿群優化對其進行求解.實驗表明，相比于PIO與PASE算法，在不同信標節點、不同通信半徑和節點密度的情況下，MOPIOLA算法的單個節點定位誤差與平均定位誤差更小，具有更好的魯棒性.

[1]張偉.面向精細農業的無線傳感器網絡關鍵技術研究[D].杭州：浙江大學，2013.

[2]Brinis N，Saidane L A.Context Aware Wireless Sensor Network Suitable for Precision Agriculture[J].Wireless Sensor Network，2016，8（01）：1.

[3]Yun S，Lee J，Chung W，et al.A soft computing approach to localization in wireless sensor networks[J].Expert Systems with Applications，2009，36（4）：7552-7561.

[4]Chen Y C，Deng D J，Chen Y S.Localization Algorithm for Wireless Sensor Networks[M]//Advanced Technologies，Embedded and Multimedia for Human-centric Computing.Springer Netherlands，2014：135-141.

[5]Zhang Q，Huang J，Wang J，et al.A new centralized localization algorithm for wireless sensor network[C]//Communications and Networking in China.Third International Conference on.IEEE，2008：625-629.

[6]Gopakumar A，Jacob L.Localization in wireless sensor networks using particle swarm optimization[C]//Wireless，Mobile and Multimedia Networks.IETInternational Conference on.IET，2008：227-230.

[7]Namin P H，Tinati M A.Node localization using particle swarm optimization[C]//Intelligent Sensors，Sensor Networks and Information Processing（ISSNIP），Seventh International Conference on.IEEE，2011：288-293.

[8]Chuang PJ，WuCP.Employing PSO to enhanceRSS range-based node localization for wireless sensor networks[J]. Journal of information science and engineering，2011，27（5）：1597-1611.

[9]肖曉麗，李旦江，譚柳斌.基于布谷鳥搜索算法的無線傳感器網絡節點定位[J].計算機工程與應用，2015.

[10]Duan H，Qiao P.Pigeon-inspired optimization：a new swarm intelligence optimizer for air robot path planning[J].International Journal of Intelligent Computing and Cybernetics，2014，7（1）：24-37.

[11]Kannan A A，Mao G，Vucetic B.Simulated annealing based wirelesssensornetworklocalizationwithflipambiguity mitigation[C]//2006IEEE63rdVehicularTechnology Conference.IEEE，2006（2）：1022-1026.

[12]Vecchio M，López-Valcarce R，Marcelloni F.A two-objective evolutionary approach based on topological constraints for node localizationinwirelesssensornetworks[J].AppliedSoft Computing，2012，12（7）：1891-1901.

[13]Qiu H X，Duan H B.Multi-objective pigeon-inspired optimization for brushless direct current motor parameter design[J].Science China Technological Sciences，2015，58（11）：1915-1923.

[14]Santos Coelho L，Barbosa L Z，Lebensztajn L.Multiobjective particle swarm approach for the design of a brushless DC wheel motor[J].IEEE Transactions on Magnetics，2010，46（8）：2994-2997.

[15]Sun Z，Tao L，Wang X，et al.Localization algorithm in wireless sensornetworksbasedonmultiobjectiveparticleswarm optimization[J].International Journal of Distributed Sensor Networks，2015：11.

[16]Duan H，Qiao P.Pigeon-inspired optimization：a new swarm intelligence optimizer for air robot path planning[J].International Journal of Intelligent Computing and Cybernetics，2014，7（1）：24-37.

Multi-objective Pigeon-inspired Optimization Localization Algorithm for Large-scale Agricultural Sensor Network

DENG Xiao-wu，SHI Yuan-quan，LI Sen-lin，LI Wei，DENG Shao-wei
（School of Computer Science and Engineering/Hunan Provincial Key Laboratory of Ecological Agriculture Intelligent Control Technology，Huaihua University，Huaihua，Hunan 418008）

Focusing on the lower localization accuracy of agricultural sensor network for single objective optimization，multi-objective pigeon-inspired optimization localization algorithm is presented to solve the multi-objective optimization localization problems in this paper.The multi-objective optimization function is composed of the spatial distance function and the geometric topology function.The optimal solution is obtained by multi-objective pigeon-inspired optimization algorithm.The simulation results show that the proposed method has good robustness，and greatly improves the positioning accuracy of the sensor nodes.

localization of sensor；multi-objective optimization；multi-objective pigeon-inspired optimization algorithm

TP3

A

1671－9743（2017）05－0037－04

2016-12-21

武陵山片區生態農業智能控制技術湖南省重點實驗室項目（ZNKZ2016-07）；湖南省教育廳資助科研項目（16C1277）；懷化學院項目（HHUY2014-06）.

鄧小武，1973年生，男，湖南麻陽人，講師，研究方向：傳感器網絡及其應用等.