基于入侵雜草優(yōu)化算法的無線傳感網(wǎng)節(jié)點(diǎn)定位

陳志泊，張蕾蕾，李巨虎，孫國棟

CHEN Zhibo,ZHANG Leilei,LI Juhu,SUN Guodong

北京林業(yè)大學(xué) 信息學(xué)院，北京 100083

School of Information Science and Technology,Beijing Forestry University,Beijing 100083,China

1 引言

無線傳感器網(wǎng)絡(luò)（Wireless Sensor Network，WSN）是由部署在目標(biāo)區(qū)域內(nèi)一定數(shù)量的傳感器節(jié)點(diǎn)組成的無線通信網(wǎng)絡(luò)，可實(shí)現(xiàn)對目標(biāo)區(qū)域中物理信號的采集、監(jiān)測、傳輸?shù)裙δ堋Ｅc傳統(tǒng)有線網(wǎng)絡(luò)相比，無線傳感器網(wǎng)絡(luò)具有自組織、靈活、容錯和快速部署等特點(diǎn)，廣泛應(yīng)用于環(huán)境監(jiān)測、天氣預(yù)報、家居生活、國防軍事、醫(yī)療護(hù)理等領(lǐng)域[1]。作為無線傳感器網(wǎng)絡(luò)的核心支撐技術(shù)，定位技術(shù)是當(dāng)前研究熱點(diǎn)，沒有位置屬性的消息是毫無意義的，同時定位技術(shù)也是研究其他技術(shù)的基礎(chǔ)[2]。

目前主要有兩類定位方法，基于測距（range-based）的定位和無需測距（range-free）的定位[3]。

基于測距的定位通過測量節(jié)點(diǎn)間距離或角度，采用相應(yīng)的定位算法進(jìn)行定位。包含兩個步驟：測距和定位算法。測距方法有測量傳播時間差（TDOA[4-5]）、到達(dá)時間（TOA[6]）、接收信號到達(dá)角（AOA[7]）和接收信號強(qiáng)度（RSSI[8]）等。定位算法有三角測量法、三邊測量法和最小二乘法等。基于測距的定位方法定位精度高，但需要額外的硬件設(shè)備，相應(yīng)的成本較高。

因此，學(xué)者們提出了無需測距的定位方法，即通過網(wǎng)絡(luò)連通度等信息實(shí)現(xiàn)定位。該方法也包含兩個步驟：距離的估計和定位算法。由于距離估計階段誤差較大，再加上定位算法的誤差，無需測距的定位方法定位精度不高，用于精度要求不高場合。隨著學(xué)者們不斷研究，定位精度不斷提高，能夠滿足大多數(shù)需求。主要方法有質(zhì)心算法[9]、DV-HOP[10]算法等。

兩類方法有各自使用范圍和優(yōu)缺點(diǎn)，需要根據(jù)實(shí)際情況選擇。本文討論基于測距的定位。基于測距的定位，常采用最小二乘法，由于定位誤差累積，誤差較大。王建剛[11]等人提出了將加權(quán)最小二乘估計應(yīng)用于Hop-Euclidea算法，以抑制累積誤差影響。陳曉輝[12]等人提出了利用累積相對誤差最小為指標(biāo)選擇基準(zhǔn)錨節(jié)點(diǎn)的改進(jìn)最小二乘法。歐陽丹彤[13]等人提出了利用約束粒子群優(yōu)化算法，將節(jié)點(diǎn)定位問題轉(zhuǎn)化為約束優(yōu)化問題。曹松[14]提出了利用改進(jìn)的螢火蟲算法和改進(jìn)的蝙蝠算法，實(shí)現(xiàn)節(jié)點(diǎn)定位。

本文提出了一種解決傳感器網(wǎng)絡(luò)中定位誤差累積的新思路。利用入侵雜草優(yōu)化算法，以定位誤差為適應(yīng)度函數(shù)，把節(jié)點(diǎn)定位問題轉(zhuǎn)化為求非線性方程組最優(yōu)化問題。通過對單個未知節(jié)點(diǎn)的定位仿真，找到定位單個節(jié)點(diǎn)最適合的錨節(jié)點(diǎn)數(shù)，并根據(jù)未知節(jié)點(diǎn)到錨節(jié)點(diǎn)距離的倒數(shù)對適應(yīng)度函數(shù)進(jìn)行修正。定位整個網(wǎng)絡(luò)時，把部分定位精度較高的非錨節(jié)點(diǎn)，轉(zhuǎn)換為錨節(jié)點(diǎn)，以解決網(wǎng)絡(luò)中錨節(jié)點(diǎn)數(shù)較少，或分布不均勻時，大量節(jié)點(diǎn)無法定位的問題。通過不同測距誤差、不同通信半徑、不同錨節(jié)點(diǎn)數(shù)和不同節(jié)點(diǎn)數(shù)下定位精度的仿真，表明該方法能有效提高定位精度，具有優(yōu)良的定位性能。

2 網(wǎng)絡(luò)模型與預(yù)備知識

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

本文研究基于各向同性網(wǎng)絡(luò)，節(jié)點(diǎn)靜態(tài)分布于二維空間，在以下參數(shù)下進(jìn)行仿真：

（1）所有節(jié)點(diǎn)具有相同性能和通信能力。在互不干擾的情況下，節(jié)點(diǎn)間發(fā)送和接收能力相同。

（2）所有節(jié)點(diǎn)具有相同的通信半徑R。通信范圍為以節(jié)點(diǎn)為圓心通信半徑為R的圓內(nèi)。

（3）節(jié)點(diǎn)均勻分布[15]。

2.2 節(jié)點(diǎn)定位

無線傳感網(wǎng)節(jié)點(diǎn)定位就是利用少量已知位置的節(jié)點(diǎn)，通過定位算法計算未知節(jié)點(diǎn)的過程。錨節(jié)點(diǎn)的位置通過人工測量或GPS進(jìn)行定位，一般認(rèn)為它們的位置是準(zhǔn)確的。在部署網(wǎng)絡(luò)時，無法對所有節(jié)點(diǎn)進(jìn)行精確定位，只能配備少量的錨節(jié)點(diǎn)，再通過錨節(jié)點(diǎn)對未知節(jié)點(diǎn)進(jìn)行定位。

以二維平面為例進(jìn)行分析，三維或多維空間可以用相似的方法。三邊測量法是最直觀的定位算法，未知節(jié)點(diǎn)通過不在一條線上的3個鄰居錨節(jié)點(diǎn)進(jìn)行定位。如圖1（a）所示。

圖1中空心的3個節(jié)點(diǎn)為錨節(jié)點(diǎn)，坐標(biāo)為(xi，yi)，i=1，2，3，與未知節(jié)點(diǎn)的距離分別為 d1，d2，d3，未知節(jié)點(diǎn)的坐標(biāo)用(x，y)表示，則有：

圖1 三邊測距法示意圖

如果測距精確，則可以得到(x，y)的精確解，而實(shí)際上d1，d2，d3的值存在一定誤差，因此以錨節(jié)點(diǎn)為圓心，以距離為半徑的3個圓可能不會相交，出現(xiàn)無解的情況，如圖1（b）所示。因此在實(shí)際應(yīng)用中一般不采用三邊測量法，而采用最小二乘法，通過加入更多的約束條件，減少由于個別測距誤差引起的定位誤差。如圖2所示。

圖2 最小二乘法示意圖

若已知 n(n＞3)個鄰居錨節(jié)點(diǎn)的坐標(biāo) p1(x1，y1)，p2(x2，y2)，…，pn(xn，yn)，同時測得未知節(jié)點(diǎn)到各個錨節(jié)點(diǎn)的距離，d1，d2，…，dn，則有：

式（2）是一個非線性方程組，不便于計算，將其轉(zhuǎn)換為線性方程組求解。用第一個式子減去最后一個式子，可以得到：

該線性方程組可以表示為AX=B，其中：

由于測距誤差的存在，實(shí)際的方程為AX+N=B，N為(n-1)維隨機(jī)測量誤差。通過最小二乘法可以求得該線性方程組的解為：

最小二乘法是一種簡單高效的定位算法，可得到較精確的解。但是如果dn存在誤差，則所有約束條件都有誤差，嚴(yán)重影響定位算法的精度。因此本文提出了一種利用入侵雜草優(yōu)化算法求解式（2）的方法。

由式（2）可得：

求解式（5）就是求使方程：

取到最小值minf(x，y)的最優(yōu)解[13]。因此該問題轉(zhuǎn)化為求解非線性方程組最優(yōu)化問題。以 f(x，y)為雜草算法的適應(yīng)度函數(shù)，求使適應(yīng)度最小的最優(yōu)解。實(shí)驗(yàn)證明用入侵雜草優(yōu)化算法求解非線性方程組是高效可行的[16]。

2.3 入侵雜草優(yōu)化算法

入侵雜草優(yōu)化算法[17-18]（Invasive Weed Optimization，IWO）是一種基于種群的數(shù)值優(yōu)化算法。在IWO中，雜草代表問題的可行解或最優(yōu)解。在不斷進(jìn)化的過程中，父代雜草通過繁殖生成種子，種子通過空間擴(kuò)散和生長成為新的雜草，當(dāng)種群數(shù)達(dá)到上限時，出現(xiàn)種群內(nèi)競爭，適應(yīng)性好的個體得以生存，適應(yīng)性差的個體慘遭淘汰，不斷重復(fù)這個過程，直到得到最優(yōu)解，或者達(dá)到設(shè)定的最大進(jìn)化次數(shù)。IWO算法的基本流程如下：

（1）種群初始化：在二維空間內(nèi)，均勻分布GSIZE個雜草，初始雜草個數(shù)根據(jù)實(shí)際情況進(jìn)行調(diào)整。

（2）生長繁殖：父代雜草生長繁殖，產(chǎn)生種子。種子數(shù)與父代雜草的適應(yīng)性成線性關(guān)系。

式中，weed為產(chǎn)生的種子數(shù)，f為當(dāng)前雜草適應(yīng)性，fmax，fmin，smax，smin分別為雜草的最大、最小適應(yīng)性和能夠產(chǎn)生的最大、最小種子數(shù)。雜草種子個數(shù)確定方法如圖3所示。

（3）空間擴(kuò)散：以父代雜草位置為期望，種子以正態(tài)分布方式擴(kuò)散在父代雜草周圍。在迭代的過程中，標(biāo)準(zhǔn)差σ動態(tài)變化，在迭代初期，σ較大，種子分布在更廣的空間，體現(xiàn)算法的全局搜索；在迭代后期，σ不斷變小，種子分布在父代周圍，體現(xiàn)算法的深度搜索。

圖3 雜草種子個數(shù)確定方法

式中，iter為當(dāng)前的迭代次數(shù)，itermax為設(shè)定的最大迭代次數(shù)，σiter為當(dāng)前標(biāo)準(zhǔn)差，σinit和σfinal分別為標(biāo)準(zhǔn)差的初始值和最終值，m為非線性調(diào)和因子，一般設(shè)定m=3。σiter隨著iter的不斷增大而減少，體現(xiàn)了算法從全局搜索到深度搜索的轉(zhuǎn)變。

（4）競爭生存：當(dāng)雜草數(shù)達(dá)到最大種群數(shù)PSIZE時，雜草間進(jìn)行競爭性生存。將父代雜草和子代雜草按照適應(yīng)性進(jìn)行排序，適應(yīng)性好的個體得以生存，適應(yīng)性差的個體被淘汰。

（5）重復(fù)（2）到（4）的步驟，直到得到最優(yōu)解或達(dá)到最大迭代次數(shù)。

3 單個節(jié)點(diǎn)定位算法

利用入侵雜草優(yōu)化算法求解單個節(jié)點(diǎn)定位問題，需要考慮兩個方面：

（1）錨節(jié)點(diǎn)的個數(shù)是否越多越好?錨節(jié)點(diǎn)多，相應(yīng)的定位精度會提高，但是算法的計算量也增加了。在適應(yīng)度函數(shù)式（6）中方程的個數(shù)越多，單個方程的誤差對最終求解的影響越小，但是方程個數(shù)越多，計算復(fù)雜度也越大。因此在可接受的定位誤差內(nèi)，錨節(jié)點(diǎn)越少越好。

（2）如果每個錨節(jié)點(diǎn)到未知節(jié)點(diǎn)的測距都存在誤差（如距離的30%），則距離越大對未知節(jié)點(diǎn)的定位精度影響越大。在適應(yīng)度函數(shù)式（6）中，每個定位方程的權(quán)重都相同，沒有考慮誤差越大的方程對最優(yōu)解精度的影響越大，需要弱化該方程對適應(yīng)度函數(shù)的影響。因此對式（6）的適應(yīng)度函數(shù)作如下修正：

以下利用Matlab對單個節(jié)點(diǎn)的定位進(jìn)行仿真。雜草算法的參數(shù)設(shè)置如表1所示。

表1 雜草算法的參數(shù)設(shè)置

對于定位算法，最主要的評價指標(biāo)是定位精度，一般采用誤差值與節(jié)點(diǎn)通信半徑的比值來表示[19]。即

式中N為節(jié)點(diǎn)總數(shù)，M為錨節(jié)點(diǎn)數(shù)，則(N-M)為未知節(jié)點(diǎn)數(shù)，xi，yi為未知節(jié)點(diǎn)實(shí)際坐標(biāo)，xi'，yi'為未知節(jié)點(diǎn)估計坐標(biāo)，R為通信半徑。

由于之后將討論不同通信半徑下定位精度，本文討論定位精度時不考慮通信半徑的影響。

即本文使用的定位精度為：

簡單起見，未知節(jié)點(diǎn)定位于(0，0)，錨節(jié)點(diǎn)均勻分布于正方形區(qū)域，在此區(qū)域內(nèi)，節(jié)點(diǎn)間可以自由通信。如圖4所示，圖中*表示未知節(jié)點(diǎn)，○表示錨節(jié)點(diǎn)，節(jié)點(diǎn)分布空間為axis([-L L-L L])，L=30。為了討論的普遍性，平均定位誤差重復(fù)50次求平均。

圖4 仿真節(jié)點(diǎn)分布圖

以下分別比較不同錨節(jié)點(diǎn)數(shù)、不同測距誤差、不同網(wǎng)絡(luò)區(qū)域大小下，最小二乘法、利用式（6）作為適應(yīng)度函數(shù)的IWO算法（IWO-1）和利用式（9）作為適應(yīng)度函數(shù)的IWO算法（IWO-2）的平均定位誤差。

3.1 錨節(jié)點(diǎn)數(shù)對定位精度的影響

仿真區(qū)域?yàn)閍xis([-L L-L L])，L=30，未知節(jié)點(diǎn)到錨節(jié)點(diǎn)的測距誤差為30%，平均定位誤差重復(fù)50次求平均，錨節(jié)點(diǎn)數(shù)是變化的。如圖5所示，隨著錨節(jié)點(diǎn)數(shù)的增加，平均定位誤差減小。錨節(jié)點(diǎn)數(shù)從4個到6個時，平均定位誤差下降快，當(dāng)錨節(jié)點(diǎn)數(shù)大于6個時，平均定位誤差趨于穩(wěn)定，為了減少計算量，之后的討論中，錨節(jié)點(diǎn)數(shù)取6個。在相同錨節(jié)點(diǎn)數(shù)下，IWO-2的平均定位誤差比IWO-1和最小二乘法小。

3.2 測距誤差對定位精度的影響

仿真區(qū)域?yàn)閍xis([-L L-L L])，L=30，錨節(jié)點(diǎn)數(shù)為6個，平均定位誤差重復(fù)50次求平均，未知節(jié)點(diǎn)到錨節(jié)點(diǎn)的測距誤差是變化的。如圖6所示，隨著測距誤差的增大，平均定位誤差增大。在相同測距誤差下，IWO-2的平均定位誤差比IWO-1和最小二乘法小。這說明IWO-2比IWO-1、最小二乘法具有更優(yōu)的抗誤差性。

圖5 錨節(jié)點(diǎn)數(shù)-平均定位誤差

圖6 測距誤差-平均定位誤差

3.3 網(wǎng)絡(luò)區(qū)域大小對定位精度的影響

錨節(jié)點(diǎn)數(shù)為6個，未知節(jié)點(diǎn)到錨節(jié)點(diǎn)的測距誤差為30%，平均定位誤差重復(fù)50次求平均，仿真區(qū)域?yàn)閍xis([-L L-L L])，L是變化的。如圖7所示，隨著仿真區(qū)域的增大，平均定位誤差增大。在相同仿真區(qū)域下，IWO-2的平均定位誤差比IWO-1和最小二乘法小。

圖7 網(wǎng)絡(luò)區(qū)域-平均定位誤差

通過以上的仿真和分析，對于單個未知節(jié)點(diǎn)，當(dāng)錨節(jié)點(diǎn)數(shù)為6個時能得到較高的定位精度，計算量少。同時，在不同錨節(jié)點(diǎn)數(shù)、不用測距誤差和不同網(wǎng)絡(luò)區(qū)域下，IWO-2的平均定位誤差比IWO-1都小，說明用未知節(jié)點(diǎn)到錨節(jié)點(diǎn)距離的倒數(shù)修正適應(yīng)度函數(shù)式（6）是可行的，能夠得到更高的定位精度。

4 全網(wǎng)節(jié)點(diǎn)定位算法

4.1 算法步驟

設(shè)網(wǎng)絡(luò)中共有N個節(jié)點(diǎn)，其中M個為錨節(jié)點(diǎn)，則未知節(jié)點(diǎn)有(N-M)個。M個錨節(jié)點(diǎn)的坐標(biāo)是精確的，但是錨節(jié)點(diǎn)與未知節(jié)點(diǎn)，未知節(jié)點(diǎn)與未知節(jié)點(diǎn)間的測距都是有誤差的。

本文的討論有3個前提：（1）不存在孤立節(jié)點(diǎn)。當(dāng)節(jié)點(diǎn)的鄰居節(jié)點(diǎn)數(shù)小于3個時，該節(jié)點(diǎn)成為孤立節(jié)點(diǎn)，無法定位。（2）錨節(jié)點(diǎn)分布均勻。（3）最初至少有一個未知節(jié)點(diǎn)有3個以上的鄰居錨節(jié)點(diǎn)，否則最小二乘法無法進(jìn)行計算。這幾個問題涉及傳感器網(wǎng)絡(luò)布局問題，不在本文的討論范圍之內(nèi)。

參考譯文：高水平的展品、高質(zhì)量的觀眾、廣泛的國際參與度和鮮明的時代感將有力烘托CIMT2009的展會主題。

隨著傳感器節(jié)點(diǎn)定位計算進(jìn)行，將一些定位精度較高的未知節(jié)點(diǎn)加入到錨節(jié)點(diǎn)，參與其他未知節(jié)點(diǎn)的定位。由于原始錨節(jié)點(diǎn)的位置是沒有誤差的，而之后計算得到的錨節(jié)點(diǎn)都是有誤差的，因此它們的坐標(biāo)可信度較低。由于誤差的疊加，越晚計算的節(jié)點(diǎn)，可信度越低，本文利用新產(chǎn)生錨節(jié)點(diǎn)數(shù)的倒數(shù)作為該新錨節(jié)點(diǎn)的可信度。對式（9）作如下修正：

式中，ηi為第i個錨節(jié)點(diǎn)的可信度，其計算式為ηi=(1/新增錨節(jié)點(diǎn)總數(shù))。

根據(jù)上面的分析，在仿真環(huán)境下，用IWO算法求解整個網(wǎng)絡(luò)節(jié)點(diǎn)定位的步驟如下：

（1）在二維空間內(nèi)均勻分布N個節(jié)點(diǎn)，選取前M個節(jié)點(diǎn)作為錨節(jié)點(diǎn)，原始錨節(jié)點(diǎn)的可信度為1。計算每個未知節(jié)點(diǎn)到錨節(jié)點(diǎn)的距離，存入距離矩陣Dist。

（2）從(N-M)個未知節(jié)點(diǎn)中，選取鄰居錨節(jié)點(diǎn)數(shù)最多的節(jié)點(diǎn)進(jìn)行定位計算。設(shè)該節(jié)點(diǎn)為UNmax，鄰居錨節(jié)點(diǎn)數(shù)為k個。

（3）根據(jù)鄰居錨節(jié)點(diǎn)的坐標(biāo)和UNmax與它們之間的距離，可以得到k個約束方程，使用式（12）作為IWO算法的適應(yīng)度函數(shù)（IWO-3），求解該方程組的最優(yōu)解。

（4）在二維空間內(nèi)，隨機(jī)初始化一定數(shù)量的雜草。

（5）計算父代雜草適應(yīng)性，根據(jù)式（7）計算每個雜草產(chǎn)生的種子數(shù)，以父代雜草坐標(biāo)為期望，以式（8）計算值為標(biāo)準(zhǔn)差正態(tài)分布在父代雜草周圍。

（6）計算種子適應(yīng)性，合并父代雜草和種子數(shù)，如果總數(shù)大于種群最大數(shù)PSIZE，則對父代雜草和種子按照適應(yīng)性進(jìn)行排序，適應(yīng)性好的個體作為下一次迭代的父代雜草。

（7）重復(fù)（5）和（6），直到得到最優(yōu)解或者達(dá)到最大迭代次數(shù)。

（8）由（1）～（7）得UNmax節(jié)點(diǎn)的坐標(biāo) (x，y)。將它加入錨節(jié)點(diǎn)矩陣，可信度為1/(新增錨節(jié)點(diǎn)總數(shù))，例如求得的第1個錨節(jié)點(diǎn)，可信度為1/1=1。如果其他未知節(jié)點(diǎn)的鄰居錨節(jié)點(diǎn)數(shù)少于6個，則計算到這個新錨節(jié)點(diǎn)的距離，并存入Dist矩陣中。同時清空UNmax列的距離值，防止重復(fù)計算。

（9）如果錨節(jié)點(diǎn)數(shù)達(dá)到了 N個，則算法結(jié)束，否則回到第（1）步，繼續(xù)計算網(wǎng)絡(luò)中其他未知節(jié)點(diǎn)。

4.2 仿真與分析

假設(shè)仿真區(qū)域?yàn)閍xis([0 L 0 L])，L=100的正方形，共有N=100個節(jié)點(diǎn)，其中錨節(jié)點(diǎn)M=10個，節(jié)點(diǎn)間的通信半徑R=30 m。平均定位誤差，重復(fù)10次求平均。初始錨節(jié)點(diǎn)和未知節(jié)點(diǎn)分布如圖8所示。

圖8 初始錨節(jié)點(diǎn)和未知節(jié)點(diǎn)分布圖

初始條件下，IWO-3算法錨節(jié)點(diǎn)擴(kuò)散如圖9所示。為了清楚顯示錨節(jié)點(diǎn)的擴(kuò)散，圖9中略去了未知節(jié)點(diǎn)。可以看出本文算法下，節(jié)點(diǎn)定位過程在整個網(wǎng)絡(luò)區(qū)域內(nèi)是均勻擴(kuò)散的。

圖9 IWO-3算法錨節(jié)點(diǎn)擴(kuò)散圖

雜草算法的參數(shù)同表1。

以下分別比較在不同測量誤差、不同通信半徑、不同錨節(jié)點(diǎn)數(shù)、不同節(jié)點(diǎn)數(shù)下，最小二乘法與IWO-3方法的定位誤差。

4.2.1 不同測量誤差的定位誤差

在仿真區(qū)域axis([0 L 0 L]),L=100內(nèi)均勻分布N=100個節(jié)點(diǎn)，其中錨節(jié)點(diǎn)為M=10個，通信半徑為R=30 m，測距誤差是變化的。如圖10所示，隨著測距誤差的增大，平均定位誤差也增大。在相同的測距誤差下，IWO-3方法能夠比最小二乘法得到更小的平均定位誤差，并且測距誤差越大，定位精度提高的趨勢越明顯。

圖10 測距誤差-平均定位誤差

4.2.2 不同通信半徑的定位誤差

在仿真區(qū)域axis([0 L 0 L]),L=100內(nèi)均勻分布N=100個節(jié)點(diǎn)，其中錨節(jié)點(diǎn)為M=10個，測距誤差為30%，通信半徑R是變化的。如圖11所示，隨著通信半徑的增大，平均定位誤差也增大。在相同通信半徑下，IWO-3方法能夠比最小二乘法得到更小的平均定位誤差。

圖11 通信半徑-平均定位誤差

4.2.3 不同錨節(jié)點(diǎn)數(shù)的定位誤差

在仿真區(qū)域axis([0 L 0 L]),L=100內(nèi)均勻分布N=100個節(jié)點(diǎn)，通信半徑R=30 m，測距誤差為30%，錨節(jié)點(diǎn)數(shù)M是變化的。如圖12所示，隨著錨節(jié)點(diǎn)數(shù)的增加，平均定位誤差先是快速下降，之后趨于平穩(wěn)。錨節(jié)點(diǎn)的成本較高，需要根據(jù)實(shí)際情況選擇。在相同錨節(jié)點(diǎn)數(shù)下，IWO-3方法比最小二乘法能得到更小的平均定位誤差。

圖12 錨節(jié)點(diǎn)數(shù)-平均定位誤差

4.2.4 不同節(jié)點(diǎn)數(shù)的定位誤差

在仿真區(qū)域axis([0 L 0 L]),L=100內(nèi)錨節(jié)點(diǎn)數(shù)為M=10個，通信半徑 R=30 m，測距誤差為30%，節(jié)點(diǎn)數(shù) N是變化的。如圖13所示，隨著節(jié)點(diǎn)數(shù)的增加，平均定位誤差變化不大。在相同節(jié)點(diǎn)數(shù)下，IWO-3方法比最小二乘法能得到更小的平均定位誤差。

圖13 節(jié)點(diǎn)數(shù)-平均定位誤差

5 結(jié)束語

本文提出了利用入侵雜草優(yōu)化算法對傳感器網(wǎng)絡(luò)進(jìn)行節(jié)點(diǎn)定位。以節(jié)點(diǎn)定位誤差為適應(yīng)度函數(shù)，把節(jié)點(diǎn)定位問題轉(zhuǎn)化為求解非線性方程組最優(yōu)化問題，同時利用未知節(jié)點(diǎn)到錨節(jié)點(diǎn)距離的倒數(shù)和新增錨節(jié)點(diǎn)數(shù)的倒數(shù)對適應(yīng)度函數(shù)進(jìn)行修正。仿真實(shí)驗(yàn)表明，對于單個節(jié)點(diǎn)定位，最適合的錨節(jié)點(diǎn)數(shù)為6個，與未知節(jié)點(diǎn)距離越大的錨節(jié)點(diǎn)對未知節(jié)點(diǎn)的定位精度影響越大。對于整個網(wǎng)絡(luò)節(jié)點(diǎn)的定位，本文提出的方法在不同測距誤差、不同通信半徑、不同錨節(jié)點(diǎn)數(shù)和不同節(jié)點(diǎn)數(shù)下，都能得到比最小二乘法更高的定位精度。

[1]孫利民.無線傳感器網(wǎng)絡(luò)[M].北京：清華大學(xué)出版社，2005：135-155.

[2]肖美華.無線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)定位關(guān)鍵技術(shù)研究[D].南昌：南昌航空大學(xué)，2010.

[3]張佳.基于DV-HOP的無線傳感器網(wǎng)絡(luò)定位算法[J].計算機(jī)應(yīng)用，2010，30（2）：323-326.

[4]Reynet O，Jaulin L，Chabert G.Robust TDOA passive location using interval analysis and contractor programming[C]//International Radar Conference，2009.

[5]Xu Bin，Sun Guodong，Yu Ran，et al.High-accuracy TDOA-based localization with time synchronization[J].IEEE Trans on Parallel and Distributed Systems，2013，24（8）：1567-1576.

[6]孟令軍，王宏濤，夏尚紅.WSN節(jié)點(diǎn)聲測距TOA值頻域估計方法[J].電子與信息學(xué)報，2010，32（4）：993-997.

[7]Dragos N，Badri N.Ad hoc positioning system using AOA[C]//Proc of the IEEE INFOCOM 2003，San Francisco，2003.

[8]Niculescu D，Nath B D.DV based positioning in ad hoc networks[J].Journal of Telecommunication System，2003，22（1/4）：267-280.

[9]Jose A C，Patwari N，Hero A.Distributed weighted-multidimensional scaling for node localization in sensor networks[J].ACM Transactions on Sensor Networks，2006，2（1）：39-64.

[10]林金朝，陳曉冰，劉海波.基于平均跳距修正的無線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)迭代定位算法[J].通信學(xué)報，2009，30（10）：107-113.

[11]王建剛，王福豹，段渭軍.加權(quán)最小二乘估計在無線傳感器網(wǎng)絡(luò)定位中的應(yīng)用[J].計算機(jī)應(yīng)用研究，2006，23（9）：41-43.

[12]陳曉輝，陳錦鵬，雷邦軍.無線傳感器節(jié)點(diǎn)定位中基準(zhǔn)錨節(jié)點(diǎn)的選擇研究[J].計算機(jī)工程與應(yīng)用，2012，48（3）：76-78.

[13]歐陽丹彤，何金勝，白洪濤.一種約束粒子群優(yōu)化的無線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)定位算法[J].計算機(jī)科學(xué)，2011，38（7）：46-50.

[14]曹松.基于兩種智能搜索算法的無線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)定位技術(shù)[D].上海：華東理工大學(xué)，2012.

[15]吳黎愛.基于不同網(wǎng)絡(luò)模型的無線傳感器網(wǎng)絡(luò)定位算法研究[D].南昌：南昌航空大學(xué)，2012.

[16]陳歡.入侵雜草優(yōu)化算法的改進(jìn)分析與應(yīng)用研究[D].南寧：廣西民族大學(xué)，2013.

[17]Mehrabian A R，Lucaz C.A novel numerical optimization algorithm inspired from weed colonization[J].Ecological Informatics，2006，1（4）：355-366.

[18]張氫，陳丹丹，秦仙蓉，等.雜草算法收斂性分析及其在工程中的應(yīng)用[J].同濟(jì)大學(xué)學(xué)報，2010，38（11）：1689-1693.

[19]吳嘉瑋.一種改進(jìn)的無線傳感器網(wǎng)絡(luò)DV_HOP定位算法的研究[D].上海：東華大學(xué)，2013.