陳志泊，張蕾蕾，李巨虎，孫國(guó)棟

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)對(duì)目標(biāo)區(qū)域中物理信號(hào)的采集、監(jiān)測(cè)、傳輸?shù)裙δ?。與傳統(tǒng)有線網(wǎng)絡(luò)相比，無線傳感器網(wǎng)絡(luò)具有自組織、靈活、容錯(cuò)和快速部署等特點(diǎn)，廣泛應(yīng)用于環(huán)境監(jiān)測(cè)、天氣預(yù)報(bào)、家居生活、國(guó)防軍事、醫(yī)療護(hù)理等領(lǐng)域[1]。作為無線傳感器網(wǎng)絡(luò)的核心支撐技術(shù)，定位技術(shù)是當(dāng)前研究熱點(diǎn)，沒有位置屬性的消息是毫無意義的，同時(shí)定位技術(shù)也是研究其他技術(shù)的基礎(chǔ)[2]。

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

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

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

兩類方法有各自使用范圍和優(yōu)缺點(diǎn)，需要根據(jù)實(shí)際情況選擇。本文討論基于測(cè)距的定位?；跍y(cè)距的定位，常采用最小二乘法，由于定位誤差累積，誤差較大。王建剛[11]等人提出了將加權(quán)最小二乘估計(jì)應(yīng)用于Hop-Euclidea算法，以抑制累積誤差影響。陳曉輝[12]等人提出了利用累積相對(duì)誤差最小為指標(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)化問題。通過對(duì)單個(gè)未知節(jié)點(diǎn)的定位仿真，找到定位單個(gè)節(jié)點(diǎn)最適合的錨節(jié)點(diǎn)數(shù)，并根據(jù)未知節(jié)點(diǎn)到錨節(jié)點(diǎn)距離的倒數(shù)對(duì)適應(yīng)度函數(shù)進(jìn)行修正。定位整個(gè)網(wǎng)絡(luò)時(shí)，把部分定位精度較高的非錨節(jié)點(diǎn)，轉(zhuǎn)換為錨節(jié)點(diǎn)，以解決網(wǎng)絡(luò)中錨節(jié)點(diǎn)數(shù)較少，或分布不均勻時(shí)，大量節(jié)點(diǎn)無法定位的問題。通過不同測(cè)距誤差、不同通信半徑、不同錨節(jié)點(diǎn)數(shù)和不同節(jié)點(diǎn)數(shù)下定位精度的仿真，表明該方法能有效提高定位精度，具有優(yōu)良的定位性能。

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

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)，通過定位算法計(jì)算未知節(jié)點(diǎn)的過程。錨節(jié)點(diǎn)的位置通過人工測(cè)量或GPS進(jìn)行定位，一般認(rèn)為它們的位置是準(zhǔn)確的。在部署網(wǎng)絡(luò)時(shí)，無法對(duì)所有節(jié)點(diǎn)進(jìn)行精確定位，只能配備少量的錨節(jié)點(diǎn)，再通過錨節(jié)點(diǎn)對(duì)未知節(jié)點(diǎn)進(jìn)行定位。

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

圖1中空心的3個(gè)節(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 三邊測(cè)距法示意圖

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

圖2 最小二乘法示意圖

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

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

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

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

最小二乘法是一種簡(jiǎn)單高效的定位算法，可得到較精確的解。但是如果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ò)散和生長(zhǎng)成為新的雜草，當(dāng)種群數(shù)達(dá)到上限時(shí)，出現(xiàn)種群內(nèi)競(jìng)爭(zhēng)，適應(yīng)性好的個(gè)體得以生存，適應(yīng)性差的個(gè)體慘遭淘汰，不斷重復(fù)這個(gè)過程，直到得到最優(yōu)解，或者達(dá)到設(shè)定的最大進(jìn)化次數(shù)。IWO算法的基本流程如下：

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

（2）生長(zhǎng)繁殖：父代雜草生長(zhǎng)繁殖，產(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ù)。雜草種子個(gè)數(shù)確定方法如圖3所示。

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

圖3 雜草種子個(gè)數(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）競(jìng)爭(zhēng)生存：當(dāng)雜草數(shù)達(dá)到最大種群數(shù)PSIZE時(shí)，雜草間進(jìn)行競(jìng)爭(zhēng)性生存。將父代雜草和子代雜草按照適應(yīng)性進(jìn)行排序，適應(yīng)性好的個(gè)體得以生存，適應(yīng)性差的個(gè)體被淘汰。

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

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

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

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

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

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

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

對(duì)于定位算法，最主要的評(píng)價(jià)指標(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)估計(jì)坐標(biāo)，R為通信半徑。

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

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

簡(jiǎn)單起見，未知節(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ù)、不同測(cè)距誤差、不同網(wǎng)絡(luò)區(qū)域大小下，最小二乘法、利用式（6）作為適應(yīng)度函數(shù)的IWO算法（IWO-1）和利用式（9）作為適應(yīng)度函數(shù)的IWO算法（IWO-2）的平均定位誤差。

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

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

3.2 測(cè)距誤差對(duì)定位精度的影響

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

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

圖6 測(cè)距誤差-平均定位誤差

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

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

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

通過以上的仿真和分析，對(duì)于單個(gè)未知節(jié)點(diǎn)，當(dāng)錨節(jié)點(diǎn)數(shù)為6個(gè)時(shí)能得到較高的定位精度，計(jì)算量少。同時(shí)，在不同錨節(jié)點(diǎn)數(shù)、不用測(cè)距誤差和不同網(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個(gè)節(jié)點(diǎn)，其中M個(gè)為錨節(jié)點(diǎn)，則未知節(jié)點(diǎn)有(N-M)個(gè)。M個(gè)錨節(jié)點(diǎn)的坐標(biāo)是精確的，但是錨節(jié)點(diǎn)與未知節(jié)點(diǎn)，未知節(jié)點(diǎn)與未知節(jié)點(diǎn)間的測(cè)距都是有誤差的。

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

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

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

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

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

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

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

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

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

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

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

（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個(gè)錨節(jié)點(diǎn)，可信度為1/1=1。如果其他未知節(jié)點(diǎn)的鄰居錨節(jié)點(diǎn)數(shù)少于6個(gè)，則計(jì)算到這個(gè)新錨節(jié)點(diǎn)的距離，并存入Dist矩陣中。同時(shí)清空UNmax列的距離值，防止重復(fù)計(jì)算。

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

4.2 仿真與分析

假設(shè)仿真區(qū)域?yàn)閍xis([0 L 0 L])，L=100的正方形，共有N=100個(gè)節(jié)點(diǎn)，其中錨節(jié)點(diǎn)M=10個(gè)，節(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)定位過程在整個(gè)網(wǎng)絡(luò)區(qū)域內(nèi)是均勻擴(kuò)散的。

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

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

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

4.2.1 不同測(cè)量誤差的定位誤差

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

圖10 測(cè)距誤差-平均定位誤差

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

在仿真區(qū)域axis([0 L 0 L]),L=100內(nèi)均勻分布N=100個(gè)節(jié)點(diǎn)，其中錨節(jié)點(diǎn)為M=10個(gè)，測(cè)距誤差為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個(gè)節(jié)點(diǎn)，通信半徑R=30 m，測(cè)距誤差為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個(gè)，通信半徑 R=30 m，測(cè)距誤差為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)化算法對(duì)傳感器網(wǎng)絡(luò)進(jìn)行節(jié)點(diǎn)定位。以節(jié)點(diǎn)定位誤差為適應(yīng)度函數(shù)，把節(jié)點(diǎn)定位問題轉(zhuǎn)化為求解非線性方程組最優(yōu)化問題，同時(shí)利用未知節(jié)點(diǎn)到錨節(jié)點(diǎn)距離的倒數(shù)和新增錨節(jié)點(diǎn)數(shù)的倒數(shù)對(duì)適應(yīng)度函數(shù)進(jìn)行修正。仿真實(shí)驗(yàn)表明，對(duì)于單個(gè)節(jié)點(diǎn)定位，最適合的錨節(jié)點(diǎn)數(shù)為6個(gè)，與未知節(jié)點(diǎn)距離越大的錨節(jié)點(diǎn)對(duì)未知節(jié)點(diǎn)的定位精度影響越大。對(duì)于整個(gè)網(wǎng)絡(luò)節(jié)點(diǎn)的定位，本文提出的方法在不同測(cè)距誤差、不同通信半徑、不同錨節(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ì)算機(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)聲測(cè)距TOA值頻域估計(jì)方法[J].電子與信息學(xué)報(bào)，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é)報(bào)，2009，30（10）：107-113.

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

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

[13]歐陽丹彤，何金勝，白洪濤.一種約束粒子群優(yōu)化的無線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)定位算法[J].計(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é)報(bào)，2010，38（11）：1689-1693.

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