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

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

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

?

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

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

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

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

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

0 引 言

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

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

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

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

1 算法模型

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

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

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

1.2 理論傳播模型

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

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

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

(1)

式中:pr(d0)——參考距離d0處的接收信號強度；

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

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

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

(2)

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

2 算法描述

2.1 算法思想

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

(1)當交點數(shù)為1時，則以此交點作為未知節(jié)點的坐標；

(2)當交點數(shù)為2時，則取兩交點連線的中點作為未知節(jié)點的坐標；

(3)當交點數(shù)為3或5時，則取3個交點構成的三角形或5個交點構成的多邊形的質(zhì)心作為未知節(jié)點的坐標；

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

圖2 有效交點為4時的算法定位原理

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

2.2 算法實現(xiàn)

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

(1) 接收信號強度值的采集與換算：通過式(3)計算錨節(jié)點與未知節(jié)點之間的距離：

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

(3)

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

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

(4)

式中：(x,y)——交點坐標；

(xi,yi)、(xj,yj)——錨節(jié)點i和錨節(jié)點j的坐標；

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

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

(a)當有效交點數(shù)為1時，則以此交點作為未知節(jié)點的坐標；

(b)當有效交點數(shù)為2時，則取兩交點連線的中點作為未知節(jié)點的坐標；

(c)當有效交點數(shù)為3或5時，則取3個交點構成三角形或5個交點構成的多邊形的質(zhì)心作為未知節(jié)點的坐標，利用式(5)計算質(zhì)心坐標：

(5)

式中:i——有效交點個數(shù)；

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

(xi，yi)——有效交點坐標。

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

(6)

式中：y=kx+b——中間兩交點的連線方程；

(x0,y0)——公共邊兩側任意一交點的坐標。

3 仿真結果與分析

仿真實驗在Matlab R2014a上進行。在30 m×5 m的狹長空間的兩側均勻部署9個錨節(jié)點，通過shadowing模型計算距離值時，隨機變量為均值0,方差0.5的高斯隨機變量。

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

圖3 10個未知節(jié)點分布

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

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

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

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

圖5 平均誤差曲線

4 結束語

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

[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)絡原理與實踐[M]. 北京: 化學工業(yè)出版社, 2011: 1-7.

[4] 章 磊， 黃光明. 基于RSSI的無線傳感器網(wǎng)絡節(jié)點定位算法[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)絡節(jié)點定位算法的改進[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] 喬鋼柱，曾建潮. 信標節(jié)點鏈式部署的井下無線傳感器網(wǎng)絡定位算法[J]. 煤炭學報， 2010, 35(7): 1229-1223.

[9] 方 震, 趙 湛, 郭 鵬, 等. 基于RSSI測距分析[J]. 傳感技術學報, 2007, 20(11): 2526-2530.

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

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

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

黑龍江省自然科學基金面上項目(F2015019;F2015017)

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

10.3969/j.issn.2095-7262.2016.05.022

TN914.5

2095-7262(2016)05-0577-04

A