信号强度和运动向量结合的无线传感器网络移动节点定位
信号强度和运动向量结合的无线传感器网络移动节点定位
李东岳1,2,王英龙1,魏 诺1,刘颖慧1,3,于 伟1,4,郭 强1
(1.山东省计算中心,山东济南 250014;2.山东轻工业学院,山东济南 250000;
3.山东科技大学,山东青岛 266510;4.山东师范大学,山东济南 250000)
摘 要: 无线传感器网络的定位是近年来无线传感器网络研究的重要课题.本文首先介绍了无线传感器网络的
来源、重要性以及无线传感器网络定位的分类.然后提出了一种全新定位算法,信号强度和运动向量结合的无线传感
器网络移动节点定...
信号强度和运动向量结合的无线传感器网络移动节点定位
李东岳1,2,王英龙1,魏 诺1,刘颖慧1,3,于 伟1,4,郭 强1
(1.山东省计算中心,山东济南 250014;2.山东轻工业学院,山东济南 250000;
3.山东科技大学,山东青岛 266510;4.山东师范大学,山东济南 250000)
摘 要: 无线传感器网络的定位是近年来无线传感器网络研究的重要课题.本文首先介绍了无线传感器网络的
来源、重要性以及无线传感器网络定位的分类.然后提出了一种全新定位算法,信号强度和运动向量结合的无线传感
器网络移动节点定位,简称SSMV算法,在外围布置四个锚节点,得用信号强度和未知节点在运动中向量的变化,对锚
节点在内的未知节点进行定位,并对该算法进行了仿真和总结.通过与凸规划法进行比较,仿真结果表明,该算法有更
高的定位精度.
关键词: 无线传感器网络;移动节点;定位
中图分类号: TP393 文献标识码: A 文章编号: 03722112(2010)2A22104
LocalizationAlgorithmforMobileNodesinWirelessSensor
NetworksBasedonSingleStrengthandMotionVector
LIDongyue1,2,WANGYinglong1,WEINuo1,LIUYinghui1,3,YUWei1,4,GUOQiang1
(1.ShandongComputerScienceCenter,Jinan,Shandong,250014,China;2.ShandongInstituteofLightIndustry,Jinan,Shandong,250000,China;
3.ShandongUniversityofScienceandTechnology,Qingdao,Shandong266510,China;4.ShandongNormalUniversity,Jinan,Shandong,250000,China)
Abstract: Inrecentyears,thepositionofwirelesssensorisanimportissuesinwirelesssensornetwork(WSN).Thisarticle
firstintroducedthesourceofwirelesssensornetworks,andtheimportanceofpositionclassification.andthenthispaperproposedthe
newmethodlocationalgorithm,localizationalgorithmformobilenodesinwirelesssensornetworksbasedonsinglestrengthandmo
tionvector(namedasSSMV),whichdeployfouranchornodesintheexternal,usethesignalstrengthandthechangeofnodevector
inmotiontolocatetheunknownnodes,andsimulatethealgorithmandconclude.Thesimulationresultswiththeconvexprogram
mingmethodofcomparison,theresultsshowthatthealgorithmhashigherpositioningaccuracy.
Keywords: wirelesssensornetwork;mobilenodes;localization
1 引言
无线传感器网络[1](wirelesssensornetwork,简称WSN)
是由微机电系统、片上系统、无线通信和低功耗嵌入式的
飞速发展而产生.随着无线传感器网络的发展,它也被应
用到更广阔的领域:生态环境监测、反恐的信息收集、火灾
地震的人员求助、地下煤矿信息采集和预测等生活的方方
面面,已成为各发达国家研究的重点和热点[2,3].
近年来,位置定位被无线传感器研究者视为最重要的
课题之一.在部署了大量节点的无线传感器网络中,定位
往往是必须的[4],不携带位置信息的数据通常是无效的.
无线传感器网络定位中一般分为[5]:基于测距的定
位(rangebased)和无须测距的定位(rangefree).基于距
离的常用测距技术有:接收信号强度(RSSI),已知发射
功率,在接收节点测量接收功率,计算传播损耗,使用理
论或经验的信号传播模型将传播损耗转化为距离;到达
时间(TOA)定位,通过测量信号传播时间来获得距离信
息,因此需要节点间精确的时间同步.GPS就是一个采
用 TOA技术实现的定位系统;时间差(TDOA),一般是在
节点上安装超声波收发器和 RF收发器,两种收发器同
时发射信号,利用声波与电磁波在空气中传播速度的巨
大差异在接收端通过
两种不同信号到达时间的差
异,基于已知信号传播速度,直接把时间转化为距离.而
此技术又受到超声波传播距离的限制;到达角度
(AOA),使得邻居节点之间估计和映射相对的角度信
息,这是一种估算邻居节点发送信号方向的技术,可通
过天线阵列或多个接收器结合来实现.
基于距离的有关算法有着一定的局限性[6]:RSSI
收稿日期:20090710;修回日期:20091104
基金项目:国家自然科学基金(No.60802030);山东省中青年科学家科研奖励基金(No.2007BSC01002);山东省科技攻关计划(No.2007GG2QT01007)
第2A期
2010年2月
电 子 学 报
ACTAELECTRONICASINICA
Vol.38 No.2A
Feb. 2010
更多技术文章,
请登录www.srvee.com
内容版权归作者所有
定位的主要误差来源是环境所造成的建模复杂性:反
射,多径传播、非视距等问题都会对相同的距离产生不
同的能量传播消耗.TOA往往会用到 GPS,而 GPS有在
以下地点会受到限制[7]:在地下,比如隧道,沙坑,或洞
穴,在水下,条件恶劣的户外环境,如山谷,森林和峡谷
等,这些环境都不适 GPS定位.GPS大量的能耗也会缩
短节点的生命周期.
无须测距的定位技术有:DVhop算法,将未知节点
到锚节点之间的距离用网络平均每跳距离和两者之间
的路数乘积表示;MDSMAP定位,是一种集中式定位算
法,可以在基于测距和无须测距两种情况下运行,并可
根据情况实现相对定位和绝对定位;凸规划定位算法,
将节点间点到点的通信连接视为节点位置的几何约
束,把整个网络模型化为一个凸集,从而将节点定位问
题转化为凸约束优化问题,然后使用半定规划和线性
规划
得到一个全局优化的解决
,确定节点的
位置.凸规划算法是无须测距定位常用的方法之一.
基于测距的定位算法需要测量相邻节点间的绝对
距离或方位,并利用节点实际距离来计算节点位置;后
者无需测量节点间的绝对距离或方位,而是利用节点
间的估计距离计算节点位置.而且无须测距的定位算
法基本不需要额外的硬件.本文提出了一种无须测距
的新的定位算法:信号强度和运动向量相结合的无线
传感器网络移动节点定位(LocalizationAlgorithmforMo
bileNodesinWirelessSensorNetworksBasedonSingle
StrengthandMotionVector简称SSMV).
2 SSMV算法
将四个已知锚节点:N1,N2,N3,N4布置成正方形,
如图1所示,未知节点为 U在其中移动.其中 N1与 N2
相距 D1,N1的通讯半径为 D2;D1 >=D2 >=(N2,
N4)/2(若 D2小于这个区域的话,则无法保证 U在正方
形中心的时候,能接收到所有的信号;若 D2大于等于
这个区域的话,则精确度下降);通讯时间相隔 t.
21 SSMV算法原理
(1)据信号强度将 N1N2N3N4所组成的正方形划分
成若干个区域,然后确定未知节点 U所在的区域组成
的多边形P.
(2)点 U在正方形中移动时,U会判断它所能接收
到的信号强弱,若 U接收到的信号强度越强,则 U记
录其锚节点的位置;接收到的信号强度越弱,设 U从上
一个位置到现在的位置的向量为S1S→2=(xa,ya)[8,9],则
U记录上一个位置的锚节点位置加上向量S1S→2,即NN→′
=S1S→2=(xa,ya),可以得到;N′=(xn′,yn′)=(xa+xn,
ya+yn).
(3)在得到三个以上的锚节点位置时,会组成一个
三角形 T或一个四边形Q.最后由 P和T或Q相交得
到一个多边形Z,则 Z的中心为U所在位置;若 T和Q
没有形成,或 P和T或Q不相交,则多边形 P的中心为
U所在的位置.
22 SSMV算法步骤
以图1中 N1所在的四分之一区域为例:
(1)先根据信号强度确定未知节点 U所在的一个
多边形P
(ⅰ)如果 U与N1,N2,N3,N4之间信号强度相等,
则 U在中心位置
(ⅱ)只接收1个信号时,则 U一定在与其相邻的
N2,N4通信区域外,U在AE区域,则 P为AE区域所组
成的四边形.
(ⅲ )只接收2个信号时
假设接收信号的是 N1,N2.则 U在F区域,则多边
形 P为F区域的边所组成的梯形.
假设接收信号的是 N1,N4.则 U在B区域,则多边
形 P为B区域的边所组成的梯形.
(ⅳ)只能接受3个信号时
假设接收信号的是 N1,N2,N3.如图1不可能出现
种情况,因为在 N4以外的区域,只有 EF,而 EF都不在
N3的范围内.
假设接收信号的是 N1,N2,N4.则 CG区域,若 N2
>N4,则 U在G区域,则 P为G区域所组成的三角形;
若 N2<N4,则 U在C区域,则 P为C区域所组成的三
角形,若 N2=N4,则 U在CG的中心,则 P为 CG区域
所组成的三角形.
(ⅴ)接收4个信号时
假设接收信号的是 N1,N2,N3,N4.则 U在DH区
域.若 N2>N4,则 U在H区域,P为H区域所组成的三
角形;若 N2<N4,则 U在D区域,P为D区域所组成的
三角形;若 N2=N4,则 U在 DH的中心,P为 DH区域
所组成的三角形.
(2)再根据 U在移动过程中所接收到的信号,确定
一个三角形 T或一个四边形Q.
222 电 子 学 报 2010年
更多技术文章,论文请登录www.srvee.com
内容版权归作者所有
假设 U的位置坐标为 M1(x,y),如图2所示,若 U
收到的 N3的信号强度越大,即 U与 N3越近,U由 M1
运动到 M2(x+xa,y+ya),U在 M2收到的信号强度大
于在 U在 M1收到的信号强度,则 U仍记录 N3相对于
U的位置为(D1,D1),当 U运动到 M3(x+xa+xb,y+ya
+yb),U接收信号强度与以前所接受到的信号强度做
相比较,信号强度弱了,
则 U记录 N3的位置跟
随 U的向量移动,U从
M2到 M3移动了(xb,
yb),则记 N3′的位置为
(D1+xb,D1+yb).当
U记录信号来自三个
节点时,如图2所示,生
成一个三角形 T,即
ΔN3″N2′N1.当接收到四
个锚节点的信号时,会生成四边形 T.当 U越接近四个
锚节点时,所形成的三角形 T或四边形 Q会越小.
若 U在N2,N3,N4区域里,以次类推.
(3)若 U没有接收到三个信号,则 U的位置定位
为P的中心;若 U接收到三个或四个信号,则 U
的位置定位为:以 P与T或Q相交后所形成的多边形
的中心.如图2所示,三角形ΔN3″N2′N1与三角形 G相
交,得新的多边形,新多边形的中心为估计定位位置.
3 仿真分析
本节以 Matlab平台进行仿真实验并分析算法的性
能,最后在相同的环境下与凸规划算法进行比较,进一
步验证该算法的优越性.
设锚节点之间距离为 D1=100m,锚节点的通讯半
径为 D2=80m.如图3所示,未知节点以螺旋曲线的方
式,由中心到边上匀速运动1m/s.
节点的误差为:error= (xe-xr)2-(ye-yr)槡 2,
定位精度为:PositioningAccuracy=
(xe-xr)2-(ye-yr)槡 2
D2
其中 xe,ye表示节点的估计定位,xr,yr代表节点的真
正位置,D2为通讯半径.
节点的定位误差如图4所示:图中很明显有两条定位
误差所形成的曲线,都是先减小后增大.图1被分割成许
多小的多边形,未知节点先开始在整个多形边的中心位
置,随着节点的移动,越来越靠近每个多边形的中心位置,
而后又渐渐远离,所以会有先减小后增大的趋势.
由一个多边形运动到另一个多边形时,就形成了
在一个时间段内,有两条变化的曲线.由于开始的时
候,在运动中所形成的多边形 T或Q面积很大,对节点
误差的变化影响不大,但随着节点以螺旋曲线的方式
运动,越来越接近锚节点,T或Q的面积越来越小,如
图5所示.当 t运动到 25以后,随着多边形面积的稳
定,节点的误差也越来越稳定,误差定位在5~15之间.
322第 2A 期 李东岳:信号强度和运动向量结合的无线传感器网络移动节点定位
更多技术文章,论文请登录www.srvee.com
内容版权归作者所有
若节点从螺旋曲线外围开始向中心移动,如图6所
示,节点的定位误差分布在515之间,最大的误差没有
超过20,证明了节点的运动中,越接近锚节点,则定位
误差会越小.
从图7中,我们可以看到,使用凸规划算法和SSMV
算法在刚开始时定位误差相差不大,但在节点运动中,
节点在远离中心位置后,凸规划算法误差总体上会越
来越大.因为使用凸规划算法,越靠近中心位置,节点
的误差越小.随着 t的变化,SSMV算法体现其优势,未
知节点越来越靠近锚节点,所形成的 T或Q越来越小,
近一步缩小未知节点所在的区域,降低未知节点的定
位误差.
100个节点在正方形区域内运动,随着节点的增
加,凸规划和SSMV算法的平均定位精度的变化如图8
所示,SSMV算法定位精度比凸规划方法高2倍多.
因此,根据比较后的结果,进一步证明本文的算法
更优.
4 结论
目前的算法大多都是节点的静态定位,本文提出
了一种基于信号强度和向量结合的无线传感器网络移
动节点的定位算法,先利用移动节点接收信号强度的
不同,确定未知节点的区域;根据节点在移动中向量和
信号强度的变化得到节点所在的大体区域;再由两个
相交后的区域来确定未知节点的位置,最后进行了仿
真分析.结果表明,该算法定位精度高,需要的锚节点
数量也较少,从而减少成本和通信开销.
从实验中我们可以得到:未知节点在运动中,越靠
近锚节点,形成的多边形 T或Q会越小,定位精度会越
高;如果未知节点的运动中,如果始终离锚节点较远,
那么节点在运动中会无法形成多边形 T或Q或生成的
多边形较大,只能依靠信号强度来确定大体区域,无法
进一步降低定位误差.对于这个问题,将是下一步需要
研究的内容.
参考文献:
[1]孙利民等编著.无线传感器网络[M].北京:清华大学出
版社,2005.
[2]WeiWang,SrinivasanV,BangWang,KeeChaingChua,Cov
eragefortargetlocalizationinwirelesssensornetworks[J].
IEEETransactionsonWirelessCommunications,2008,7(2):
667-676.
[3]YiQian,KejieLu,TipperD.,Adesignforsecureandsurviv
ablewirelesssensornetworks[J].IEEEWirelessCommunica
tions,2007,14(5):30-37.
[4]YounisM.F.,GhummanK.,EltoweissyM.,LocationAware
CombinatorialKeyManagementSchemeforClusteredSensor
Networks[J].IEEETransactionsonParallelandDistributed
Systems,2006,17(8):865882.
[5]段渭军,王建刚,王福豹.无线传感器网络节点定位系统
与算法的研究和发展[J].信息与控制.2006,02:239-
345.
[6]史龙,王福豹,段渭军等.无线传感器网络 RangeFree自
身定位机制与算法[J].计算机工程与应用,2004,23:127
-130.
[7]JungeunPark;Demaine,E.D.Teller,S.MovingBaselineLo
calization[A].InformationProcessinginSensorNetworks[C].
IPSN’08.InternationalConferenceon,2008.15-16.
[8]ChiaHoOu.Rangefreenodelocalizationformobilewireless
sensornetworks[A].WirelessPervasiveComputing,ISWPC
2008[C].3rdInternationalSymposiumon,2008.1-8.
[9]B.A.VanDerPluijmandS.Marshak,EarthStructure:AnIn
troductiontoStructuralGeologyandTectonics[M].NewYork:
WWNorton&CoInc,2003.
作者简介:
李东岳 男,1982年生于山东济宁,山东轻
工业学院在读硕士研究生,主要研究方向为无线
传感器网络.
Email:lidy@keylab.net
王英龙 男,汉族,1965年生于山东菏泽,山
东大学信息科学与工程学院博士,研究员,博士生
导师.现任山东省科学院副院长,山东省信息系统
测评工程技术研究中心主任,兼任省信息化专家
组成员、山东计算机学会副理事长兼秘书长、中国
计算机学会嵌入式系统专委、山东省信息
化
技术委员会副主任委员、山东省电子政务建设特
邀专家、济南市客座信息化专 家委员会委员.
魏 诺 女,1982年生于枣庄,毕业于中国
海洋大学,硕士,主要研究方向为无线传感器网
络.
Email:wein@keylab.net
422 电 子 学 报 2010年
更多技术文章,论文请登录www.srvee.com
内容版权归作者所有
本文档为【信号强度和运动向量结合的无线传感器网络移动节点定位】,请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑,
图片更改请在作品中右键图片并更换,文字修改请直接点击文字进行修改,也可以新增和删除文档中的内容。
[版权声明] 本站所有资料为用户分享产生,若发现您的权利被侵害,请联系客服邮件isharekefu@iask.cn,我们尽快处理。
本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用。
网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。