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

（懷化學(xué)院計算機科學(xué)與工程學(xué)院/武陵山片區(qū)生態(tài)農(nóng)業(yè)智能控制技術(shù)湖南省重點實驗室，湖南懷化418008）

面向大規(guī)模農(nóng)業(yè)傳感器網(wǎng)絡(luò)的多目標鴿群優(yōu)化定位算法

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

（懷化學(xué)院計算機科學(xué)與工程學(xué)院/武陵山片區(qū)生態(tài)農(nóng)業(yè)智能控制技術(shù)湖南省重點實驗室，湖南懷化418008）

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

傳感器定位；多目標定位優(yōu)化；多目標鴿群優(yōu)化算法

1 引言

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

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

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

2 多目標節(jié)點定位模型

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

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

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

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

空間距離約束的目標函數(shù)表示為

幾何拓撲約束的目標函數(shù)表示為

幾何拓撲表示網(wǎng)絡(luò)連通性約束，它不滿足非信標節(jié)點的當(dāng)前估計位置[12].δij表示為

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

3 多目標鴿群優(yōu)化定位算法

3.1 多目標鴿群優(yōu)化的數(shù)學(xué)模型

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

3.2 多目標鴿群優(yōu)化算法

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

3.2.1 Pareto分類方法

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

（1）非支配分類算子

第i只鴿子的位置Xj優(yōu)于第j只鴿子的位置，當(dāng)且僅當(dāng)滿足如下條件：

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

（2）擁擠比較算子

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

j解的多樣性.

3.2.2 合并算子

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

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

n-t1er.

在導(dǎo)航工具過渡因子tr的作用下，兩種操作算子之間的交接工作能實現(xiàn)平穩(wěn)地過渡.

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

n-t1er.

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

SX

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

cn-t1e

r.

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

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

3.2.3 基于多目標鴿群優(yōu)化的定位算法

多目標鴿群優(yōu)化定位算法步驟如：

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

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

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

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

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

步驟6更新迭代次數(shù)nc=nc+1；

步驟7如果迭代次數(shù)小于最大迭代次數(shù)，則到步驟2繼續(xù)執(zhí)行，否則估算鴿群的當(dāng)前位置X，并輸出Pareto前沿

4 性能分析

4.1 評估參數(shù)

在matlab仿真實驗平臺構(gòu)建一個100 m×100 m二維區(qū)域?qū)Ρ疚奶岢龅亩ㄎ凰惴ㄟM行實驗仿真分析.隨機部署n個傳感器節(jié)點，其中信標節(jié)點為m個，未知節(jié)點為（n-m）個.假設(shè)RSSI測距誤差eij服從均值為零、方差為σ2=βr2ij（β=0.1）的高斯分布[15].

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

4.2 定位精度

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

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

4.3 MOPIOLA的魯棒性

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

4.3.1 節(jié)點密度對定位性能的影響

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

4.3.2 信標節(jié)點數(shù)比例對定位性能的影響

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

表1 單節(jié)點定位誤差OneError范圍分布

表2 不同節(jié)點數(shù)定位誤差

表3 不同信標節(jié)點比例的定位誤差

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

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

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

5 結(jié)束語

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

[1]張偉.面向精細農(nóng)業(yè)的無線傳感器網(wǎng)絡(luò)關(guān)鍵技術(shù)研究[D].杭州：浙江大學(xué)，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]肖曉麗，李旦江，譚柳斌.基于布谷鳥搜索算法的無線傳感器網(wǎng)絡(luò)節(jié)點定位[J].計算機工程與應(yīng)用，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

武陵山片區(qū)生態(tài)農(nóng)業(yè)智能控制技術(shù)湖南省重點實驗室項目（ZNKZ2016-07）；湖南省教育廳資助科研項目（16C1277）；懷化學(xué)院項目（HHUY2014-06）.

鄧小武，1973年生，男，湖南麻陽人，講師，研究方向：傳感器網(wǎng)絡(luò)及其應(yīng)用等.