趙志信， 李加君， 江曉林， 謝玉鵬

(黑龍江科技大學(xué) 電子與信息工程學(xué)院， 哈爾濱 150022)

?

狹長(zhǎng)空間環(huán)境下改進(jìn)的WSN節(jié)點(diǎn)質(zhì)心定位算法

趙志信， 李加君， 江曉林， 謝玉鵬

(黑龍江科技大學(xué) 電子與信息工程學(xué)院， 哈爾濱 150022)

針對(duì)狹長(zhǎng)空間環(huán)境下信號(hào)傳播的多徑效應(yīng)等原因?qū)е鹿?jié)點(diǎn)定位的精度不足問題，提出一種改進(jìn)的WSN(無線傳感器網(wǎng)絡(luò))節(jié)點(diǎn)質(zhì)心定位算法。首先，給出狹長(zhǎng)空間環(huán)境下錨節(jié)點(diǎn)部署策略，采用shadowing模型將錨節(jié)點(diǎn)接收到的信號(hào)強(qiáng)度值轉(zhuǎn)換為距離值,使得未知節(jié)點(diǎn)的位置初步定位在最近的三個(gè)錨節(jié)點(diǎn)構(gòu)成的三角形內(nèi)；然后，以這三個(gè)錨節(jié)點(diǎn)的圓心距離值為半徑形成三個(gè)圓，根據(jù)得到的有效交點(diǎn)個(gè)數(shù)，分四種情況得到未知節(jié)點(diǎn)的位置估計(jì)。仿真結(jié)果表明，改進(jìn)質(zhì)心算法平均定位誤差在1 m左右，在定位區(qū)域不同位置仍能保持穩(wěn)定的定位性能，與極大似然估計(jì)法和質(zhì)心算法相比，該算法定位精度與穩(wěn)定性都得到提高。

多徑效應(yīng)； 錨節(jié)點(diǎn)； 定位； 狹長(zhǎng)環(huán)境； 質(zhì)心算法

0 引 言

無線傳感器網(wǎng)絡(luò)由大量的微型傳感器節(jié)點(diǎn)組成，并通過無線通信方式形成一個(gè)自組織的智能網(wǎng)絡(luò)系統(tǒng)，能夠?qū)崟r(shí)監(jiān)測(cè)監(jiān)控區(qū)域內(nèi)的各種環(huán)境信息，同時(shí)對(duì)這些信息進(jìn)行處理并傳輸[1-3]。WSN節(jié)點(diǎn)定位是無線傳感器網(wǎng)絡(luò)關(guān)鍵支撐技術(shù)。在狹長(zhǎng)空間環(huán)境下的WSN節(jié)點(diǎn)定位對(duì)于煤礦井下應(yīng)急救援，以及樓層走廊的消防救援等，有著重要的現(xiàn)實(shí)的意義。

根據(jù)是否需要測(cè)量實(shí)際節(jié)點(diǎn)間的距離，將定位算法分為基于測(cè)距(range-based)和與距離無關(guān)(range-free)兩種定位算法。兩者間的區(qū)別在于是否需要測(cè)量相鄰節(jié)點(diǎn)間的實(shí)際距離。基于測(cè)距的定位算法需要額外的硬件來協(xié)助定位，成本要高于與距離無關(guān)的定位算法，但是在精度與效率上，前者要優(yōu)于后者。

基于測(cè)距的定位算法中，基于接收信號(hào)強(qiáng)度指示(RSSI)[4]的定位，通過接收端接收的信號(hào)衰減估算節(jié)點(diǎn)間的距離，但是由于環(huán)境的不同，衰減系數(shù)也有所差異，導(dǎo)致定位存在較大誤差。

不需要測(cè)距的定位算法中，三角形內(nèi)點(diǎn)近似估計(jì)法(APIT)[5]通過判斷移動(dòng)節(jié)點(diǎn)是否在錨節(jié)點(diǎn)形成的三角形內(nèi)進(jìn)行定位，由于該算法要求節(jié)點(diǎn)一直處于移動(dòng)當(dāng)中，因此在實(shí)際應(yīng)用中不是很靈活。質(zhì)心算法[6]是通過計(jì)算錨節(jié)點(diǎn)形成的多邊形的質(zhì)心坐標(biāo)來進(jìn)行定位。針對(duì)狹長(zhǎng)空間環(huán)境下信號(hào)傳播的多徑效應(yīng)導(dǎo)致節(jié)點(diǎn)定位精度不足的情況，筆者提出一種改進(jìn)的WSN節(jié)點(diǎn)質(zhì)心定位算法。給出狹長(zhǎng)空間環(huán)境下錨節(jié)點(diǎn)部署策略，采用shadowing模型將錨節(jié)點(diǎn)接收到的信號(hào)強(qiáng)度值轉(zhuǎn)換為距離值,使得未知節(jié)點(diǎn)的位置初步定位在最近的三個(gè)錨節(jié)點(diǎn)構(gòu)成的三角形內(nèi)；然后以這三個(gè)錨節(jié)點(diǎn)為圓心距離值為半徑形成三個(gè)圓，根據(jù)得到的有效交點(diǎn)個(gè)數(shù)，分四種情況得到未知節(jié)點(diǎn)的位置估計(jì)。

1 算法模型

1.1 錨節(jié)點(diǎn)部署模型

在無線傳感器網(wǎng)絡(luò)中，每種定位算法都有其特定的應(yīng)用環(huán)境， 文中算法主要針對(duì)狹長(zhǎng)空間環(huán)境下的未知節(jié)點(diǎn)進(jìn)行定位。為了節(jié)約網(wǎng)絡(luò)成本，以較少的錨節(jié)點(diǎn)覆蓋整個(gè)狹長(zhǎng)空間，將錨節(jié)點(diǎn)均勻地部署在狹長(zhǎng)空間兩側(cè)，且距離相等，未知節(jié)點(diǎn)可位于定位區(qū)域內(nèi)任意一點(diǎn)。錨節(jié)點(diǎn)部署模型如圖1所示。在定位過程中，未知節(jié)點(diǎn)向通信范圍內(nèi)的錨節(jié)點(diǎn)發(fā)出一個(gè)包含自身ID的信息包，錨節(jié)點(diǎn)將接收到的信號(hào)強(qiáng)度值換算成距離值之后，轉(zhuǎn)發(fā)給匯聚節(jié)點(diǎn)，由匯聚節(jié)點(diǎn)進(jìn)行比較計(jì)算，給出未知節(jié)點(diǎn)的位置估計(jì)。

圖1 錨節(jié)點(diǎn)部署模型

1.2 理論傳播模型

已知發(fā)送信號(hào)的強(qiáng)度，通過測(cè)量接收信號(hào)強(qiáng)度，計(jì)算信號(hào)的傳播損耗，根據(jù)理論或經(jīng)驗(yàn)信號(hào)傳播衰減模型將傳播損耗轉(zhuǎn)化為距離。得到錨節(jié)點(diǎn)與未知節(jié)點(diǎn)之間的距離信息。

在實(shí)際狹長(zhǎng)空間環(huán)境定位中，shadowing模型[7-9]更符合實(shí)際環(huán)境，shadowing模型分為兩部分，第一部分為路徑損耗模型：

pr(d0)/pr(d)=(d/d0)n,

(1)

式中:pr(d0)——參考距離d0處的接收信號(hào)強(qiáng)度；

pr(d)——距離d時(shí)接收到的平均功率；

n——信號(hào)傳播路徑衰落系數(shù)。

Shadowing模型的第二部分，表示在同一距離上接收到的信號(hào)能量滿足高斯分布，即

(2)

式中:Xσ——由陰影效應(yīng)引起的正態(tài)分布的隨機(jī)變量。

2 算法描述

2.1 算法思想

未知節(jié)點(diǎn)向通信范圍內(nèi)的錨節(jié)點(diǎn)發(fā)送信號(hào)，錨節(jié)點(diǎn)通過shadowing模型將接收到的信號(hào)強(qiáng)度轉(zhuǎn)換為距離值，找出距離未知節(jié)點(diǎn)最近的三個(gè)錨節(jié)點(diǎn)a、b、c(對(duì)應(yīng)的到未知節(jié)點(diǎn)的距離分別為r1、r2、r3)。以錨節(jié)點(diǎn)為圓心，距離r1、r2、r3為半徑形成三個(gè)圓，根據(jù)得到的有效交點(diǎn)(位于定位區(qū)域內(nèi)的交點(diǎn))個(gè)數(shù)，對(duì)未知節(jié)點(diǎn)的定位分為以下四種情況：

(1)當(dāng)交點(diǎn)數(shù)為1時(shí)，則以此交點(diǎn)作為未知節(jié)點(diǎn)的坐標(biāo)；

(2)當(dāng)交點(diǎn)數(shù)為2時(shí)，則取兩交點(diǎn)連線的中點(diǎn)作為未知節(jié)點(diǎn)的坐標(biāo)；

(3)當(dāng)交點(diǎn)數(shù)為3或5時(shí)，則取3個(gè)交點(diǎn)構(gòu)成的三角形或5個(gè)交點(diǎn)構(gòu)成的多邊形的質(zhì)心作為未知節(jié)點(diǎn)的坐標(biāo)；

(4)當(dāng)交點(diǎn)數(shù)為4時(shí)，交點(diǎn)D、E、F、G將三圓交叉區(qū)域分為2個(gè)三角形DEF和三角形GEF，最后取面積稍小的三角形DEF的質(zhì)心作為未知節(jié)點(diǎn)的坐標(biāo)，原理如圖2所示。

圖2 有效交點(diǎn)為4時(shí)的算法定位原理

Fig. 2 Positioning principle of algorithm with effective intersection four points

2.2 算法實(shí)現(xiàn)

具體的定位過程可以分為以下幾個(gè)步驟：

(1) 接收信號(hào)強(qiáng)度值的采集與換算：通過式(3)計(jì)算錨節(jié)點(diǎn)與未知節(jié)點(diǎn)之間的距離：

d=d0×10[p0(d0)-pr(d)-Xσ]/10n。

(3)

(2) 尋找最近的錨節(jié)點(diǎn)：比較未知節(jié)點(diǎn)到不同錨節(jié)點(diǎn)的距離值，找出距離未知節(jié)點(diǎn)最近的三個(gè)錨節(jié)點(diǎn)。

(3) 計(jì)算有效區(qū)域內(nèi)的交點(diǎn)：以這3個(gè)錨節(jié)點(diǎn)為圓心，距離值為半徑形成的3個(gè)圓，利用式(4)分別計(jì)算處于有效區(qū)域內(nèi)每?jī)蓚€(gè)圓的交點(diǎn)，

(4)

式中：(x,y)——交點(diǎn)坐標(biāo)；

(xi,yi)、(xj,yj)——錨節(jié)點(diǎn)i和錨節(jié)點(diǎn)j的坐標(biāo)；

di、dj——未知節(jié)點(diǎn)到錨節(jié)點(diǎn)i和j距離，i,j=1,2,3,i≠j。

(4) 根據(jù)有效交點(diǎn)數(shù)的不同，對(duì)未知節(jié)點(diǎn)定位。定位方法分為以下四種情況：

(a)當(dāng)有效交點(diǎn)數(shù)為1時(shí)，則以此交點(diǎn)作為未知節(jié)點(diǎn)的坐標(biāo)；

(b)當(dāng)有效交點(diǎn)數(shù)為2時(shí)，則取兩交點(diǎn)連線的中點(diǎn)作為未知節(jié)點(diǎn)的坐標(biāo)；

(c)當(dāng)有效交點(diǎn)數(shù)為3或5時(shí)，則取3個(gè)交點(diǎn)構(gòu)成三角形或5個(gè)交點(diǎn)構(gòu)成的多邊形的質(zhì)心作為未知節(jié)點(diǎn)的坐標(biāo)，利用式(5)計(jì)算質(zhì)心坐標(biāo)：

(5)

式中:i——有效交點(diǎn)個(gè)數(shù)；

(X，Y)——質(zhì)心坐標(biāo)；

(xi，yi)——有效交點(diǎn)坐標(biāo)。

(d)當(dāng)交點(diǎn)數(shù)為4時(shí)，則尋找最小三角形：以中間兩個(gè)交點(diǎn)的連線為公共邊，將三圓交叉區(qū)域分為兩個(gè)三角形，分別計(jì)算公共邊兩側(cè)的交點(diǎn)到該公共邊的距離，距離值較小的點(diǎn)和中間兩個(gè)交點(diǎn)形成的三角形面積最小，取該三角形的質(zhì)心作為未知節(jié)點(diǎn)的坐標(biāo)。公共邊兩側(cè)的交點(diǎn)到公共邊的距離D為

(6)

式中：y=kx+b——中間兩交點(diǎn)的連線方程；

(x0,y0)——公共邊兩側(cè)任意一交點(diǎn)的坐標(biāo)。

3 仿真結(jié)果與分析

仿真實(shí)驗(yàn)在Matlab R2014a上進(jìn)行。在30 m×5 m的狹長(zhǎng)空間的兩側(cè)均勻部署9個(gè)錨節(jié)點(diǎn)，通過shadowing模型計(jì)算距離值時(shí)，隨機(jī)變量為均值0,方差0.5的高斯隨機(jī)變量。

仿真過程中錨節(jié)點(diǎn)個(gè)數(shù)不變，隨機(jī)產(chǎn)生10個(gè)未知節(jié)點(diǎn)進(jìn)行定位，圖3為采用改進(jìn)質(zhì)心算法得到的10個(gè)未知節(jié)點(diǎn)的位置估計(jì)。由圖3可知，改進(jìn)質(zhì)心算法的定位誤差較小。

圖3 10個(gè)未知節(jié)點(diǎn)分布

圖4給出了定位區(qū)域內(nèi)不同位置的定位誤差，顯示了定位誤差e在定位空間不同位置的變化情況。如圖4所示，在定位區(qū)域內(nèi)不同位置下的定位誤差波動(dòng)很小。結(jié)果表明，改進(jìn)質(zhì)心算法在狹長(zhǎng)空間環(huán)境下的不同位置，仍能保持高的定位精度和穩(wěn)定的定位性能。

圖4 改進(jìn)質(zhì)心算法在不同位置上的定位誤差

Fig. 4 Location error of improved centroid algorithm in different position

為了降低未知節(jié)點(diǎn)在定位區(qū)域隨機(jī)分布對(duì)仿真結(jié)果帶來的影響，仿真中，分別對(duì)10個(gè)未知節(jié)點(diǎn)的位置進(jìn)行1 000次估計(jì)，取定位誤差的平均值ev，改進(jìn)質(zhì)心算法、極大似然算法[10]和質(zhì)心算法的平均誤差曲線如圖5所示。由圖5可知，改進(jìn)質(zhì)心算法的平均誤差為1 m左右，定位精度以及穩(wěn)定性都要優(yōu)于極大似然估計(jì)法和質(zhì)心算法。

圖5 平均誤差曲線

4 結(jié)束語

筆者提出一種狹長(zhǎng)空間環(huán)境下改進(jìn)的WSN節(jié)點(diǎn)質(zhì)心定位算法。該算法首先通過shadowing模型將接收到的信號(hào)強(qiáng)度值轉(zhuǎn)換成距離值，再根據(jù)距離值找出距離未知節(jié)點(diǎn)最近的三個(gè)錨節(jié)點(diǎn)；然后，以這三個(gè)錨節(jié)點(diǎn)為圓心距離值為半徑形成三個(gè)圓，根據(jù)得到的有效交點(diǎn)個(gè)數(shù)，分四種情況得到未知節(jié)點(diǎn)的位置估計(jì)。仿真結(jié)果表明，改進(jìn)質(zhì)心算法定位誤差約1 m，且在定位區(qū)域內(nèi)不同位置下的定位誤差波動(dòng)很小，在狹長(zhǎng)空間環(huán)境下具有較高且平穩(wěn)的定位精度，與極大似然估計(jì)法和質(zhì)心算法相比較，改進(jìn)的質(zhì)心算法的定位精度要優(yōu)于兩者，證實(shí)了該算法的可行性與有效性。

[1] LI J, ZHONG X, LU I. Three-dimensional node localization algorithm for WSN based on differential RSS irregular transmission model [J]. Jounal of Communications, 2014, 9(5): 391-397.

[2] ZHANG Z, XU X, YAN L. Underground localization algorithm of wireless sensor network based on Zigbee [J]. Journal of China Coal Society, 2009, 34(1): 125-128.

[3] 陳 敏, 王 擘, 李軍華， 等. 無線傳感器網(wǎng)絡(luò)原理與實(shí)踐[M]. 北京: 化學(xué)工業(yè)出版社, 2011: 1-7.

[4] 章 磊， 黃光明. 基于RSSI的無線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)定位算法[J]. 計(jì)算機(jī)工程與設(shè)計(jì)， 2010, 31(2)： 291-294.

[5] DARGIE W, POOLLABAUER C. Fundamentals of wireless sensor networks: theory and practice [M]. Singapore: Markono, 2010: 259-260.

[6] 許紅艷， 王經(jīng)卓， 董自健, 等. 無線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)定位算法的改進(jìn)[J]. 微計(jì)算機(jī)信息, 2012, 28(10)： 303-305.

[7] WANG Y. A research on the localization technology of wireless sensor net works [D]. Hefei： University of Science and Technology of China, 2007.

[8] 喬鋼柱，曾建潮. 信標(biāo)節(jié)點(diǎn)鏈?zhǔn)讲渴鸬木聼o線傳感器網(wǎng)絡(luò)定位算法[J]. 煤炭學(xué)報(bào)， 2010, 35(7): 1229-1223.

[9] 方 震, 趙 湛, 郭 鵬, 等. 基于RSSI測(cè)距分析[J]. 傳感技術(shù)學(xué)報(bào), 2007, 20(11): 2526-2530.

[10] 李建坡, 鐘鑫鑫, 徐 純. 無線傳感器網(wǎng)絡(luò)動(dòng)態(tài)節(jié)點(diǎn)定位算法綜述[J]. 東北電力大學(xué)學(xué)報(bào)， 2015, 35(1): 52-58.

(編輯 晁曉筠 校對(duì) 李德根)

Improved WSN node centroid localization algorithm in long and narrow space environment

ZhaoZhixin,LiJiajun,JiangXiaolin,XieYupeng

(School of Electronics & Information Engineering, Heilongjiang University of Science & Technology, Harbin 150022, China)

This paper proposes an improved node centroid localization algorithm based on WSN as a solution to insufficient accuracy of sensor node positioning due to signal multipath effect result in narrow space. The study consists of providing a strategy of node deployment in narrow space, converting received signal strength value of anchor node to distance value, and leaving the unknown node primarily mapped in a triangle consisting of the nearest three anchor node; and then taking the three anchor node as the center and a radius of distance value to form three circles and dividing the position estimation of unknown nodes into four cases based on the number of effective cross points. Simulation results show that the improved algorithm working with a positioning error of around 1 m, boasts a higher positioning accuracy and stability than the maximum likelihood estimation method and the centroid algorithm.

multipath effect; anchor node; positioning; narrow space; centroid algorithm

2016-09-02

黑龍江省自然科學(xué)基金面上項(xiàng)目(F2015019;F2015017)

趙志信(1979-)，男，黑龍江省依蘭人，副教授，博士，研究方向：無線網(wǎng)絡(luò)資源管理，E-mail：zhaozhixin0830@163.com。

10.3969/j.issn.2095-7262.2016.05.022

TN914.5

2095-7262(2016)05-0577-04

A