基于次錨節(jié)點(diǎn)的無線傳感器網(wǎng)絡(luò)改進(jìn)加權(quán)質(zhì)心定位算法

張先超，劉興長，張春園

(后勤工程學(xué)院 后勤信息與軍事物流工程系，重慶401311)

0 引 言

無線傳感器網(wǎng)絡(luò)(wireless sensor networks，WSNs)是由隨機(jī)部署在目標(biāo)區(qū)域內(nèi)的數(shù)量巨大的離散傳感器節(jié)點(diǎn)組成，通過無線通信方式形成的一個(gè)多跳的自組織網(wǎng)絡(luò)系統(tǒng)［1］。節(jié)點(diǎn)的位置信息對無線傳感器網(wǎng)絡(luò)十分重要，是其支撐技術(shù)，并且具有廣泛的應(yīng)用［2］。研究提高定位精度是當(dāng)前無線傳感器網(wǎng)絡(luò)研究的熱點(diǎn)［3～7］。

無線傳感器網(wǎng)絡(luò)的定位技術(shù)可分為兩類:基于測距(range-based)的技術(shù)和無需測距(range-free)的技術(shù)［8］。到達(dá)時(shí)間差(time difference of arrival，TDOA)測距技術(shù)廣泛應(yīng)用于無線傳感器網(wǎng)絡(luò)定位，在不考慮非視距(NLOS)誤差的情況下可取得較高的測距精度［9］?；赥DOA 測距的粒子群優(yōu)化(PSO)無線傳感器網(wǎng)絡(luò)定位算法可比較準(zhǔn)確地估計(jì)節(jié)點(diǎn)位置，但需要額外測距設(shè)備，增加了節(jié)點(diǎn)能耗?；诮邮招盘枏?qiáng)度指示(RSSI)的加權(quán)質(zhì)心算法通信開銷小，算法簡單［10］，但定位覆蓋率和定位精度受錨節(jié)點(diǎn)數(shù)目影響較大。

本文提出了一種基于次錨節(jié)點(diǎn)的改進(jìn)加權(quán)質(zhì)心定位算法(IWCLA-SAN)，以克服加權(quán)質(zhì)心定位算法(WCLA)對錨節(jié)點(diǎn)數(shù)量要求較高和定位精度較低的缺陷。

1 粒子群優(yōu)化定位算法

文獻(xiàn)［11，12］將粒子群優(yōu)化算法應(yīng)用于無線傳感器網(wǎng)絡(luò)定位中，驗(yàn)證了該定位算法的可靠性。粒子群優(yōu)化算法的實(shí)現(xiàn)原理如下:

假設(shè)在D 維的搜索空間內(nèi)，存在一個(gè)種群大小為M 的粒子群，即無線傳感器網(wǎng)絡(luò)中的錨節(jié)點(diǎn);存在一個(gè)數(shù)量為N的搜索目標(biāo)群，即無線傳感器網(wǎng)絡(luò)中的未知節(jié)點(diǎn)。每個(gè)粒子在空間中的位置坐標(biāo)xi=(xi1，xi2，…，xid)，搜索速度vi=(vi1，vi2，…，vid)，搜索到的個(gè)體最優(yōu)位置為pi=(pi1，pi2，…，pid)，搜索到的全局最優(yōu)位置為gb=(gb1，gb2，…，gbd)，其中，i=1，2，…，M，d=1，2，…，D。該算法采用下列公式對粒子操作

學(xué)習(xí)因子c1和c2是非負(fù)的常數(shù)，常設(shè)c1=c2=2;r1和r2是介于［0，1］的隨機(jī)數(shù);w 為慣性權(quán)重，用來保持局部搜索和全局搜索的平衡，較大的w 有利于算法的全局搜索能力，較小的w 有利于算法的局部搜索能力;vid∈［-vmax，vmax］，vmax太大容易使粒子飛離最優(yōu)解，vmax太小容易使粒子陷入局部最優(yōu)，粒子的速度通常設(shè)為每維變換范圍的10%～20%;k 為當(dāng)前迭代次數(shù)，T 為終止迭代次數(shù);f 為適應(yīng)度函數(shù)，di為未知節(jié)點(diǎn)到各錨節(jié)點(diǎn)的距離;錨節(jié)點(diǎn)的坐標(biāo)Ai(xi，yi)，未知節(jié)點(diǎn)坐標(biāo)Nj(xj，yj)，其中，i=1，2，…，M，j=1，2，…，N。

2 測距原理與質(zhì)心定位算法

2.1 RSSI 測距原理

節(jié)點(diǎn)在通信時(shí)可以直接獲取RSSI 值，估計(jì)出未知節(jié)點(diǎn)與錨節(jié)點(diǎn)的距離。針對室外定位環(huán)境，文中采用自由空間傳播模型(free space propagation model)和對數(shù)—常態(tài)分布(log-normal distribution)模型，用于分析和仿真［13］。自由空間模型無線信道的數(shù)學(xué)模型如下

對數(shù)—常態(tài)分布模型無線信道的數(shù)學(xué)模型如下

式中 PL(d0)為距離錨節(jié)點(diǎn)d0處的信號強(qiáng)度;PL(d)為距離錨節(jié)點(diǎn)d 處的信號強(qiáng)度;d 為未知節(jié)點(diǎn)與錨節(jié)點(diǎn)之間的距離;f 為頻率;d0為參考距離，一般取為1 m，將d=1 m 代入式(6)得到Loss，即PL(d0)的值;n 為信道衰減指數(shù)，一般取值2～4;Xδ為均值為零、方差δ 的高斯隨機(jī)噪聲變量。

通常情況下，測距誤差隨著測量距離的增加而增大［14］，即較大的RSSI 值計(jì)算得到的距離值誤差較小，而較小的RSSI 值計(jì)算得到的距離值誤差較大。

2.2 質(zhì)心定位算法

圖1 CLA 示意圖Fig 1 Schematic diagram of centroid localization algorithm

2.3 WCLA

WCLA 通過對不同的錨節(jié)點(diǎn)賦予不同權(quán)值，達(dá)到了提高定位精度的目的。通常加權(quán)值是未知節(jié)點(diǎn)到錨節(jié)點(diǎn)距離的函數(shù)［15］，一般將未知節(jié)點(diǎn)與錨節(jié)點(diǎn)距離的倒數(shù)作為加權(quán)值，得到加權(quán)質(zhì)心定位算法，其計(jì)算公式為

式中 (xi，yi)為錨節(jié)點(diǎn)的坐標(biāo)，wi為加權(quán)因子，di為未知節(jié)點(diǎn)到錨節(jié)點(diǎn)的距離，i=1，2，…，n。

2.4 IWCLA

為了更加體現(xiàn)未知節(jié)點(diǎn)到通信范圍各錨節(jié)點(diǎn)距離對定位精度的影響，提出一種修正系數(shù)不固定的IWCLA。該算法對加權(quán)因子進(jìn)行改進(jìn)，設(shè)其為

其中，k 為修正系數(shù)，設(shè)定為

其中，D 為未知節(jié)點(diǎn)到通信范圍內(nèi)錨節(jié)點(diǎn)距離集合元素方差的歸一化值，D 值的大小反映了未知節(jié)點(diǎn)通信范圍內(nèi)各錨節(jié)點(diǎn)分布的均勻程度，分布越均勻D 值越小。根據(jù)D 值的不同設(shè)定k 的值，使得計(jì)算不同未知節(jié)點(diǎn)的坐標(biāo)時(shí)，修正系數(shù)k 的值不同。如圖2 所示，對于錨節(jié)點(diǎn)分布均勻程度不同的兩種情況，圖2(a)的k 值大于圖2(b)的。本文根據(jù)通信范圍內(nèi)各錨節(jié)點(diǎn)分布的均勻程度設(shè)定k 值，這樣更能增加距離未知節(jié)點(diǎn)較近的錨節(jié)點(diǎn)的權(quán)重，減少距離較遠(yuǎn)的錨節(jié)點(diǎn)的權(quán)重。因此，與WCLA 相比，定位精度進(jìn)一步提高。

2.5 IWCLA 描述

IWCLA 的定位步驟如下:

1)錨節(jié)點(diǎn)周期性發(fā)送自身節(jié)點(diǎn)ID 和自身節(jié)點(diǎn)位置信息，與鄰居節(jié)點(diǎn)進(jìn)行通信。

圖2 錨節(jié)點(diǎn)分布圖Fig 2 Diagram of anchor nodes distribution

2)未知節(jié)點(diǎn)收到錨節(jié)點(diǎn)信息后，分別記錄同一個(gè)錨節(jié)點(diǎn)的RSSI 均值。

3)根據(jù)公式(6)計(jì)算出未知節(jié)點(diǎn)到各錨節(jié)點(diǎn)的距離di。

4)當(dāng)未知節(jié)點(diǎn)接收到的錨節(jié)點(diǎn)信息達(dá)到閾值N 時(shí)，建立以下3 個(gè)集合:

錨節(jié)點(diǎn)集合Sbeacon={a1，a2，…，an};錨節(jié)點(diǎn)位置集合Sposition={(x1，y1)，(x2，y2)，…，(xn，yn)};未知節(jié)點(diǎn)到錨節(jié)點(diǎn)的距離集合Sd={d1，d2，…，dn}。

5)對未知節(jié)點(diǎn)到錨節(jié)點(diǎn)的距離集合中的各元素按從小到大依次排序，組成新的集合;對應(yīng)的新的錨節(jié)點(diǎn)位置集合。由2.1 節(jié)分析可知，距離值越小，測距越準(zhǔn)確，故優(yōu)選距離值較小的錨節(jié)點(diǎn)估計(jì)未知節(jié)點(diǎn)坐標(biāo)，以提高定位精度。

7)根據(jù)公式(7)計(jì)算出未知節(jié)點(diǎn)的坐標(biāo)(X，Y)。

2.6 仿真與分析

利用Matlab 軟件進(jìn)行仿真。設(shè)錨節(jié)點(diǎn)數(shù)量為M，未知節(jié)點(diǎn)數(shù)量為N，錨節(jié)點(diǎn)和未知節(jié)點(diǎn)均隨機(jī)分布在室外100 m×100 m 的區(qū)域內(nèi);通信半徑r=30 m;信道衰減指數(shù)n=3.2，高斯隨機(jī)噪聲變量Xδ的標(biāo)準(zhǔn)差取為4，不考慮NLOS 誤差對定位結(jié)果的影響。

設(shè)錨節(jié)點(diǎn)數(shù)目為50，未知節(jié)點(diǎn)數(shù)目為20。圖3 為三種算法的定位誤差，對于大多數(shù)未知節(jié)點(diǎn)，IWCLA 的定位誤差明顯低于其它兩種CLA。

設(shè)定不同的錨節(jié)點(diǎn)個(gè)數(shù)，在每種錨節(jié)點(diǎn)個(gè)數(shù)情況下，獨(dú)立進(jìn)行30 次實(shí)驗(yàn)求出平均定位誤差。圖4 反映了三種定位算法平均定位誤差與錨節(jié)點(diǎn)數(shù)目關(guān)系。錨節(jié)點(diǎn)數(shù)目越多，三種定位算法的平均定位誤差越小，且IWCLA 定位效果始終優(yōu)于另外二種定位算法。

圖3 各未知節(jié)點(diǎn)的定位誤差Fig 3 Positioning error of each unknown node

圖4 錨節(jié)點(diǎn)數(shù)目對定位精度的影響Fig 4 Influence of number of anchor node on positioning precision

3 IWCLA-SAN

3.1 算法描述

錨節(jié)點(diǎn)的數(shù)量對IWCLA 的定位精度和定位覆蓋率有很大影響，但帶有GPS 的錨節(jié)點(diǎn)造價(jià)是普通節(jié)點(diǎn)的10 倍，不適宜大規(guī)模部署。為了提高IWCLA 的定位精度和定位覆蓋率，本文將基于TDOA 測距的粒子群優(yōu)化定位算法的未知節(jié)點(diǎn)升級為次錨節(jié)點(diǎn)(SAN)，再采用IWCLA 對其它未知節(jié)點(diǎn)進(jìn)行定位。

3.2 仿真與分析

設(shè)錨節(jié)點(diǎn)數(shù)量為M，SAN 數(shù)為R，未知節(jié)點(diǎn)數(shù)量為N，錨節(jié)點(diǎn)、SAN 和未知節(jié)點(diǎn)均隨機(jī)分布在室外100 m×100 m的區(qū)域內(nèi);通信半徑r=30 m;信道衰減指數(shù)n=3.2，高斯隨機(jī)噪聲變量Xδ的標(biāo)準(zhǔn)差取為4，不考慮NLOS 誤差對定位結(jié)果的影響。

在錨節(jié)點(diǎn)數(shù)目有限的情況下，研究加入SAN 對定位精度的影響。設(shè)錨節(jié)點(diǎn)數(shù)目依次為10，20，30，40，50;SAN 數(shù)目為20;未知節(jié)點(diǎn)數(shù)目為20。分別獨(dú)立進(jìn)行30 次實(shí)驗(yàn)，求出平均定位誤差和定位覆蓋率。由圖5、圖6 可知，IWCLASAN 與IWCLA 相比可以一定程度上提高定位精度和定位覆蓋率。盡管將未知節(jié)點(diǎn)升級為SAN 會帶來一定的誤差累積，但基于TDOA 測距的粒子群優(yōu)化無線傳感器網(wǎng)絡(luò)定位算法具有較高定位精度，將其作為SAN 具有一定可靠度。

4 結(jié)束語

圖5 錨節(jié)點(diǎn)數(shù)目對定位精度的影響Fig 5 Influence of number of anchor node on positioning precision

圖6 錨節(jié)點(diǎn)數(shù)目對定位覆蓋率的影響Fig 6 Influence of number of anchor node on localization coverage rate

本文針對定位精度較低的缺陷，在加權(quán)因子中引入了修正系數(shù);針對CLA 對錨節(jié)點(diǎn)數(shù)量要求較高的缺陷，為減少錨節(jié)點(diǎn)數(shù)量，降低成本，將基于TDOA 測距的粒子群優(yōu)化無線傳感器網(wǎng)絡(luò)定位算法的未知節(jié)點(diǎn)升級為SAN。本文提出的IWCLA 定位精度相較于WCLA 有較大提高;在錨節(jié)點(diǎn)數(shù)目有限的情況下，加入SAN 可以提高定位精度和定位覆蓋率。但本文并未考慮NLOS 誤差對定位精度的影響，這需進(jìn)一步研究該算法在NLOS 環(huán)境中的可靠性。

［1］ 宋 文，王 兵，周應(yīng)兵，等.無線傳感器網(wǎng)絡(luò)技術(shù)與應(yīng)用［M］.北京:電子工業(yè)出版社，2007:1-10.

［2］ 孫利民，李建中.無線傳感器網(wǎng)絡(luò)［M］.北京:清華大學(xué)出版社，2005:135-154.

［3］ Li F F，Luo F，Wang J X，et al.An effective self-adapting localization algorithm in wireless sensor networks［J］.J of Applied Mechanics and Materials，2011，58-60:1013-1017.

［4］ Jian L R，Zheng Y，Liu Y H.Beyond triangle inequality:Sifting noisy and outlier distance measurements for localization［C］∥Proc of IEEE INFOCOM 2010，San Diego:IEEE，2010:1-9.

［5］ Kung H T，Lin C K，Lin T H，et al.Localization with snap-inducing shaped residuals:Coping with errors in measurement［C］∥Proc of MobiCom 2009，Beijing:ACM，2009:333-344.

［6］ Li Z，Trappe W，Zhang Y，et al.Robust statistical methods for securing wireless localization in sensor networks［C］∥Proc of IPSN 2005，Los Angeles:IEEE，2005:91-98.

［7］ Zhang Q X，Di Q L，Xu G Y，et al.A RSSI-based localization algorithm for multiple mobile robots［C］∥Proc of CMCE 10，Changchun:IEEE，2010:190-193.

［8］ 李曉維，徐勇軍，任豐原.無線傳感器網(wǎng)絡(luò)技術(shù)［M］.北京:北京理工大學(xué)出版社，2007:191-199.

［9］ 彭 宇，王 丹.無線傳感器網(wǎng)絡(luò)定位技術(shù)綜述［J］.電子測量與儀器學(xué)報(bào)，2011，25(5):389-399.

［10］方 震，趙 湛，郭 鵬，等.基于RSSI 測距分析［J］.傳感技術(shù)學(xué)報(bào)，2007，20(11):2526-2530.

［11］王曉樂，徐家品.基于粒子群優(yōu)化算法的WSNs 節(jié)點(diǎn)定位研究定位［J］.計(jì)算機(jī)應(yīng)用，2009，29(2):494-499.

［12］邢明彥，李臘元.粒子群優(yōu)化算法在無線傳感器網(wǎng)絡(luò)中的應(yīng)用［J］.計(jì)算機(jī)工程與應(yīng)用，2009，45(32):72-74.

［13］陳維克，李文鋒，首 珩，等.基于RSSI 的無線傳感器網(wǎng)絡(luò)加權(quán)質(zhì)心算法定位［J］.武漢理工大學(xué)學(xué)報(bào)，2006，30(2):265-268.

［14］Chen W，Mei T，Sun L，et al.Error analyzing for RSSI-based localization in wireless sensor networks［C］∥7th World Congress on Intelligent Control and Automation，WCICA 2008，IEEE，2008:2701-2706.

［15］楊新宇，孔慶茹，戴湘軍.一種改進(jìn)的加權(quán)質(zhì)心定位算法［J］.西安交通大學(xué)學(xué)報(bào)，2010，44(8):1-4.