WSN中節(jié)點(diǎn)定位方法的改進(jìn)*

馬淑麗，趙建平，張炳婷，盛艷梅，陳 麗

(曲阜師范大學(xué) 物理工程學(xué)院,山東 曲阜 273165 )

WSN中節(jié)點(diǎn)定位方法的改進(jìn)*

馬淑麗，趙建平，張炳婷，盛艷梅，陳 麗

(曲阜師范大學(xué) 物理工程學(xué)院,山東 曲阜 273165 )

無線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)位置信息的獲取非常關(guān)鍵。首先考慮節(jié)點(diǎn)分布問題提出了一種新的節(jié)點(diǎn)分布模式，并改進(jìn)定位算法，將節(jié)點(diǎn)定位過程主要分為一級(jí)定位和二級(jí)定位。一級(jí)定位采用基于優(yōu)先值閾值的質(zhì)心定位算法，并將一級(jí)定位的節(jié)點(diǎn)作為新錨節(jié)點(diǎn)參與二級(jí)定位。二級(jí)定位使用基于優(yōu)先值閾值的DV-Hop最小二乘定位算法。Matlab仿真結(jié)果證明，提出的節(jié)點(diǎn)分布模式利于節(jié)點(diǎn)定位，一級(jí)定位算法降低了計(jì)算量，并與二級(jí)定位算法一起提高了定位精度。

節(jié)點(diǎn)定位；DV-Hop；最小二乘法；質(zhì)心定位法

0 引 言

無線傳感器網(wǎng)絡(luò)(WSN，Wireless Sensor Network)傳感器節(jié)點(diǎn)通常部署在人不能長時(shí)間滯留的環(huán)境中，由于成本原因傳感器節(jié)點(diǎn)只有少數(shù)帶有GPS或北斗等定位裝置。節(jié)點(diǎn)定位根據(jù)已知節(jié)點(diǎn)位置信息求未知節(jié)點(diǎn)位置，方法主要分為兩大類：一是基于測(cè)距的節(jié)點(diǎn)定位方法，定位精度高，但硬件成本、通信量、計(jì)算量高[1]；二是無需測(cè)距定位方法，成本低，定位精度低，能滿足一般粗精度定位的應(yīng)用。無需測(cè)距的定位算法包括 DV-Hop、質(zhì)心定位法、凸規(guī)劃定位算法、Amorphous定位算法、APIT算法、AHLos算法、N-Hop Multilateration Primitive算法、SeRLoc算法等[1]。本文主要研究并改進(jìn)DV-Hop定位算法和質(zhì)心定位算法。

1 典型定位算法概述

1.1 DV-Hop算法

DV-Hop定位算法是由美國羅格斯大學(xué)(Rutgers University)Dragos Niculescu等人提出的6種分布式定位算法之一[1]。主要分為4個(gè)過程：1.錨節(jié)點(diǎn)以泛洪的方式廣播位置信息和初始跳數(shù)值0，每被轉(zhuǎn)發(fā)一次跳數(shù)值加1。接收節(jié)點(diǎn)只保留每個(gè)錨節(jié)點(diǎn)最小的跳數(shù)值，最終得每個(gè)節(jié)點(diǎn)間的最小跳數(shù)。2.根據(jù)已知的錨節(jié)點(diǎn)位置信息計(jì)算錨節(jié)點(diǎn)間平均每一跳的距離如式(1)，并將其作為校正值廣播。

(1)

式中，xi，yi是錨節(jié)點(diǎn)i坐標(biāo)值，xj，yj是錨節(jié)點(diǎn)j坐標(biāo)值，hij是錨節(jié)點(diǎn)i、j間的最小跳數(shù)，dHopi是錨節(jié)點(diǎn)i到其他錨節(jié)點(diǎn)的平均每一跳距離。3.未知節(jié)點(diǎn)到每個(gè)錨節(jié)點(diǎn)的跳數(shù)分別乘以與之最小跳數(shù)錨節(jié)點(diǎn)的校正值，得到未知節(jié)點(diǎn)與每個(gè)錨節(jié)點(diǎn)間的估算距離。4.利用最小二乘法或三邊測(cè)距等定位方法計(jì)算未知節(jié)點(diǎn)坐標(biāo)。

1.2 最小二乘法原理

為了使節(jié)點(diǎn)定位誤差降到最低，需滿足下式[2]

(2)

式中，n是錨節(jié)點(diǎn)個(gè)數(shù)，x，y是未知節(jié)點(diǎn)真實(shí)坐標(biāo)值，di是未知節(jié)點(diǎn)與錨節(jié)點(diǎn)i間的估算距離。根據(jù)以下式子，利用最小二乘法最終估算出未知節(jié)點(diǎn)坐標(biāo)：

(3)

將式(3)前(n-1)個(gè)方程分別減去第n個(gè)方程得：

AX=b

(4)

(5)

(6)

(7)

1.3 質(zhì)心定位算法

質(zhì)心定位算法由南加利福尼亞大學(xué)(University of Southern California)Nirupama Bulusu等人提出[1]，是將未知節(jié)點(diǎn)定位在錨節(jié)點(diǎn)的幾何中心的定位方法如下式：

(8)

式中，(x，y)是未知節(jié)點(diǎn)坐標(biāo)，xi，yi是未知節(jié)點(diǎn)通信范圍內(nèi)的錨節(jié)點(diǎn)i的坐標(biāo)值，n是未知節(jié)點(diǎn)通信范圍內(nèi)錨節(jié)點(diǎn)個(gè)數(shù)。

質(zhì)心定位算法計(jì)算量比DV-Hop算法計(jì)算量小，不需要廣播信息得到所有跳數(shù)值和廣播校正值，降低了無線傳感器網(wǎng)絡(luò)能量消耗。但其定位精度依賴于節(jié)點(diǎn)分布的均勻性。

1.4 其他概念

絕對(duì)誤差：指未知節(jié)點(diǎn)估測(cè)坐標(biāo)與實(shí)際坐標(biāo)距離，一般作為節(jié)點(diǎn)的定位誤差。定位精度：平均定位誤差與節(jié)點(diǎn)通信半徑的比率值，值越小定位精度越高。

2 改進(jìn)的節(jié)點(diǎn)定位方法

2.1 改進(jìn)節(jié)點(diǎn)分布模式

對(duì)于節(jié)點(diǎn)定位算法的研究首先要根據(jù)實(shí)際應(yīng)用建立節(jié)點(diǎn)分布環(huán)境模型。許多文獻(xiàn)如文獻(xiàn)[3]采用未知節(jié)點(diǎn)與錨節(jié)點(diǎn)隨機(jī)均勻分布的仿真環(huán)境如圖1所示。

圖1 文獻(xiàn)[3]節(jié)點(diǎn)分布

為了更進(jìn)一步提高節(jié)點(diǎn)定位精度，本文提出了錨節(jié)點(diǎn)完全均勻分布，其他節(jié)點(diǎn)隨機(jī)均勻分布的仿真環(huán)境。將監(jiān)控區(qū)域劃分為m(4、9、16等)個(gè)相同的小幾何區(qū)域，在每個(gè)小區(qū)域的幾何中心放置1個(gè)錨節(jié)點(diǎn)。如圖2所示。

圖2 本文節(jié)點(diǎn)分布圖m=9

2.2 改進(jìn)節(jié)點(diǎn)定位方法

文獻(xiàn)[4]提出一種按優(yōu)先級(jí)定位節(jié)點(diǎn)的方法，并將先定位的節(jié)點(diǎn)升級(jí)為錨節(jié)點(diǎn)后再進(jìn)行下一級(jí)定位的方法，直到所有節(jié)點(diǎn)定位完成，提高了定位精度。但是該方法定位分為多次進(jìn)行，每次都采用改進(jìn)的DV-Hop算法，節(jié)點(diǎn)廣播信息次數(shù)多，會(huì)增加節(jié)點(diǎn)的能量消耗[5]。本文提出二級(jí)節(jié)點(diǎn)定位，第一級(jí)采用優(yōu)先值閾值的質(zhì)心節(jié)點(diǎn)定位方法，第二級(jí)將第一級(jí)定位節(jié)點(diǎn)升級(jí)為錨節(jié)點(diǎn)后采用優(yōu)先值閾值的DV-Hop定位算法定位。剩余未定位節(jié)點(diǎn)(少量)可通過DV-Hop定位，或使用優(yōu)先值閾值的DV-Hop再進(jìn)行分級(jí)定位。比文獻(xiàn)[4]降低了計(jì)算量與泛洪次數(shù)，減少了節(jié)點(diǎn)能量消耗。

2.3 基于優(yōu)先值閾值的質(zhì)心定位

文獻(xiàn)[3]采用基于加權(quán)的質(zhì)心定位方法，提高了定位精度，但是需要進(jìn)行(n-2)次三邊測(cè)量計(jì)算，最后根據(jù)加權(quán)質(zhì)心法定位節(jié)點(diǎn)，計(jì)算量大。本文一級(jí)定位采用優(yōu)先值閾值的質(zhì)心定位方法：每個(gè)未知節(jié)點(diǎn)都有自己的優(yōu)先值，未知節(jié)點(diǎn)每檢測(cè)到1個(gè)與之一跳距離的錨節(jié)點(diǎn)，優(yōu)先值加1。當(dāng)優(yōu)先值大于閾值時(shí)，未知節(jié)點(diǎn)參與定位。將參與一級(jí)定位的未知節(jié)點(diǎn)一跳距離的錨節(jié)點(diǎn)位置信息代入式(8)，求出未知節(jié)點(diǎn)坐標(biāo)，并升級(jí)為新錨節(jié)點(diǎn)參與下一級(jí)節(jié)點(diǎn)定位。比文獻(xiàn)[3]計(jì)算量降低。

2.4 基于優(yōu)先值閾值的DV-HOP定位

新錨節(jié)點(diǎn)廣播位置信息和初始跳數(shù)值0。二級(jí)未知節(jié)點(diǎn)優(yōu)先值更新，優(yōu)先值大于二級(jí)閾值的參與二級(jí)定位。根據(jù)錨節(jié)點(diǎn)位置信息與新錨節(jié)點(diǎn)的估算位置信息求出二級(jí)錨節(jié)點(diǎn)平均每跳距離，廣播校正值。二級(jí)未知節(jié)點(diǎn)計(jì)算出與每個(gè)錨節(jié)點(diǎn)間的距離di。將與二級(jí)定位未知節(jié)點(diǎn)有一跳距離的錨節(jié)點(diǎn)位置信息代入式(3)中的相應(yīng)方程，用最小二乘法估算每個(gè)二級(jí)節(jié)點(diǎn)坐標(biāo)。

3 仿真結(jié)果分析

3.1 仿真環(huán)境驗(yàn)證

在邊長為100 m的正方形區(qū)域分布109個(gè)節(jié)點(diǎn)并編號(hào)，其中9個(gè)錨節(jié)點(diǎn)的編號(hào)從1到9，未知節(jié)點(diǎn)的編號(hào)從10到109。節(jié)點(diǎn)通信半徑30 m。文獻(xiàn)[3]的仿真環(huán)境中所有節(jié)點(diǎn)隨機(jī)均勻分布，本文仿真環(huán)境將其中9個(gè)錨節(jié)點(diǎn)分布在9個(gè)小正方形區(qū)域的幾何中心，其他節(jié)點(diǎn)與文獻(xiàn)[3]未知節(jié)點(diǎn)分布相同。用DV-Hop算法定位本文與文獻(xiàn)[3]仿真環(huán)境中的未知節(jié)點(diǎn)，并對(duì)兩種環(huán)境下節(jié)點(diǎn)定位誤差進(jìn)行比較，如圖3所示。

圖3 兩種環(huán)境下DV-Hop定位誤差對(duì)比

仿真80次，在本文提出的的節(jié)點(diǎn)分布環(huán)境下定位精度為33%，比在文獻(xiàn)[3]節(jié)點(diǎn)分布環(huán)境下定位精度提高約5.3%。證明本文提出的節(jié)點(diǎn)分布方法有利于提高DV-Hop算法定位精度。

3.2 一級(jí)基于優(yōu)先值閾值的質(zhì)心定位

未知節(jié)點(diǎn)通信范圍內(nèi)錨節(jié)點(diǎn)個(gè)數(shù)大于等于3時(shí)質(zhì)心定位才有一定準(zhǔn)確度。本文一級(jí)閾值設(shè)為3。將本文一級(jí)定位算法與文獻(xiàn)[4]一級(jí)定位算法和DV-Hop算法在本文環(huán)境中仿真定位，并進(jìn)行一級(jí)定位節(jié)點(diǎn)誤差對(duì)比，如圖4所示。

圖4 本文一級(jí)定位、DV-Hop、文獻(xiàn)[4]算法定位誤差對(duì)比

仿真100次，本文算法一級(jí)定位精度15%，比文獻(xiàn)[4]一級(jí)定位算法和DV-Hop算法分別提高約10%、11%。一級(jí)定位節(jié)點(diǎn)個(gè)數(shù)占總節(jié)點(diǎn)個(gè)數(shù)8%。

3.3 二級(jí)基于優(yōu)先值閾值的DV-HOP定位

二級(jí)定位采用基于優(yōu)先值閾值的DV-Hop最小二乘法定位。二級(jí)閾值取1到11的整數(shù)，分別進(jìn)行100次仿真并與DV-Hop算法對(duì)比。當(dāng)二級(jí)閾值為2、3時(shí)，本文算法二級(jí)定位精度分別提高約2%、3%，如圖5所示。

圖5 本文二級(jí)定位與DV-Hop定位精度對(duì)比

3.4 二級(jí)基于優(yōu)先值閾值的質(zhì)心定位

本文將二級(jí)定位方法改為基于優(yōu)先值閾值的質(zhì)心定位法進(jìn)行仿真，并將一、二級(jí)定位精度與DV-Hop算法對(duì)比，如圖6所示。

圖6 兩種定位算法對(duì)比

隨著二級(jí)閾值增大，一、二級(jí)基于優(yōu)先值閾值質(zhì)心算法定位精度逐漸提高。當(dāng)閾值達(dá)到8時(shí)開始定位精度比DV-Hop定位精度高，但是定位節(jié)點(diǎn)率低。

3.5 一級(jí)、二級(jí)基于優(yōu)先值閾值定位

將本文一級(jí)基于優(yōu)先值閾值的質(zhì)心定位、二級(jí)基于優(yōu)先值閾值的DV-HOP定位算法的定位精度與DV-Hop相應(yīng)的節(jié)點(diǎn)定位精度對(duì)比，如圖7所示。仿真證明本文提出的分級(jí)定位算法比DV-Hop算法定位精度高。二級(jí)閾值為9時(shí)，本文算法相應(yīng)節(jié)點(diǎn)定位精度比原算法定位精度高9%。

圖7 本文一、二級(jí)定位與DV-Hop定位精度對(duì)比

一、二級(jí)定位精度提高的同時(shí)，定位節(jié)點(diǎn)個(gè)數(shù)下降。二級(jí)閾值越大，二級(jí)定位節(jié)點(diǎn)個(gè)數(shù)越少。二級(jí)閾值為1時(shí)，一、二級(jí)節(jié)點(diǎn)定位率達(dá)85%，定位精度比DV-Hop高2%；二級(jí)閾值為2時(shí)，一、二級(jí)節(jié)點(diǎn)定位率達(dá)70%，定位精度比DV-Hop高3.7%。二級(jí)閾值從5開始越大需要的一級(jí)節(jié)點(diǎn)定位個(gè)數(shù)越多，如圖8所示。

圖8 定位節(jié)點(diǎn)個(gè)數(shù)與二級(jí)閾值關(guān)系

4 結(jié) 語

本文節(jié)點(diǎn)分布模式能提高DV-Hop定位精度5.3%，但增加了人力負(fù)擔(dān)。本文模式中一級(jí)算法與文獻(xiàn)[3]加權(quán)質(zhì)心算法相比，降低了計(jì)算量并提高10%定位精度，與DV-Hop算法相比，提高11%。本文模式中：二級(jí)優(yōu)先DV-Hop算法，在閾值為2、3時(shí)與DV-Hop算法相比，定位精度分別提高2%、3%；二級(jí)優(yōu)先質(zhì)心算法，在閾值為9到11的整數(shù)時(shí)，定位精度比DV-Hop算法提升，但是犧牲二級(jí)定位節(jié)點(diǎn)數(shù)。本文一、二級(jí)方法與DV-Hop算法在相同模式下，提高了定位精度，比文獻(xiàn)[4]分多輪算法減少了泛洪次數(shù)，降低了節(jié)點(diǎn)能耗。本文定位方法能滿足一般二維WSN應(yīng)用，缺點(diǎn)是定位節(jié)點(diǎn)率達(dá)不到100%。下一步將改進(jìn)的方法應(yīng)用到三維仿真驗(yàn)證。

[1] 陳敏，王擘，李軍華.無線傳感器網(wǎng)絡(luò)原理與實(shí)踐[M].北京：化學(xué)工業(yè)出版社，2011. CHEN Min, WANG Bo, LI Jun-hua. Wireless Sensor Network Theory and Practice [M]. Beijing: Chemical Industry Press, 2011.

[2] 張是，李德敏，張曉露.基于ZIGBEE的自適應(yīng)動(dòng)態(tài)區(qū)域誤差因子算法[J].通信技術(shù)，2014,2(47):179-183. ZHANG Shi, LI Min-de, ZHANG Xiao-lu. Adaptive Dynamic Regional Error Factor Algorithm based on ZIGBEE [J]. Communications Technology, 2014,2 (47): 179-183.

[3] 夏少波，連麗君，王魯娜等.基于DV-Hop定位算法的改進(jìn)[J].計(jì)算機(jī)應(yīng)用，2014,34(05)：1247-1250. XIA Shao-bo, LIAN Li-jun, WANG Lu-na, et al.Improved DV-Hop Localization Algorithm[J]. Computer Application,2014,34 (05): 1247-1250.

[4] 楊石磊，樊曉平，劉少強(qiáng)等.一種改進(jìn)的無線傳感器網(wǎng)絡(luò)DV-Hop定位算法[J].智能儀表與傳感器，2008,16(09)：1356-1358. YANG Shi-lei, FAN Xiao-ping, LIU Shao-qiang, et al.An Improved DV-Hop Positioning Algorithm for Wireless Sensor Networks [J]. Intelligent Instruments And Sensors, 2008,16 (09): 1356-1358.

[5] (德)達(dá)爾吉,(美)玻爾拉伯爾.無線傳感器網(wǎng)絡(luò)基礎(chǔ)理論與實(shí)踐[M].孫利民等譯.北京：清華大學(xué)出版社，2014. Dargie W(Germany),Poellabaure C(America). The Wireless Sensor Network Basic Theory and Practice [M]. SUN M L Translation. Tsinghua University Press, 2014.

Supported by the science and technology project of higher education of Shandong province(No.J12LN08);National Natural Science Foundation of China(No.11302118)

Improvement of Node Locating Algorithm in WSN

MA Shu-li，ZHAO Jian-ping，ZHANG Bing-ting，SHENG Yan-mei，CHEN Li

(College of Physics Engineering ，Qufu Normal University ， Qufu Shandon 273165，China )

It is of great importance to acquire the node location information of wireless sensor network. Firstly, for the problem of node distribution, a novel node distribution model is proposed, and the locating algorithm modified. Meanwhile,the node locating process is divided into first-stage locating and second-stage locating. The first-stage locating adopts centroid locating algorithm based on priority threshold, with its node as a new anchor node participating in the second-stage locating,while the second-stage locating uses DV-Hop locating algorithm based on least square priority threshold. Matlab simulation results show that the proposed node distribution model could facilitate node locating, the first-stage locating algorithm could reduce the amount of calculation and together with the second-stage locating algorithm,improve the locating precision.

node locating; DV-Hop; least square method; centroid locating algorithm

date:2014-10-09；Revised date：2014-02-17

山東省高等學(xué)?？萍加?jì)劃項(xiàng)目資助(No.J12LN08)；國家自然科學(xué)基金資助項(xiàng)目(No.11302118)

TP393

A

1002-0802(2015)04-0453-05

馬淑麗(1989-)，女，碩士研究生，主要研究方向?yàn)闊o線傳感器網(wǎng)絡(luò)、無線通信技術(shù);

趙建平(1964-)，男，教授，主要研究方向?yàn)闊o線通信技術(shù);

張炳婷(1990-)，女，碩士研究生，主要研究方向?yàn)闊o線通信技術(shù);

盛艷梅(1991-)，女，碩士研究生，主要研究方向?yàn)橹悄苄畔⑻幚?

陳 麗(1990-)，女，碩士研究生，主要研究方向?yàn)楣饫w通信。

10.3969/j.issn.1002-0802.2015.04.014

2014-10-09；

2015-02-17