JoumalofComputerApplications
计算机应用，2012，32(12)：3517—3520
ISSN1001—9081
CODENJYIIDU
2012．12．01
http：／／www．joca．cn
文章编号：1001—9081(2012)12—3517一04doi：lO．3724／SP．J．1087．2012．03517
基于物联网空间划分的定位算法
何佳鸿8，张小明，王永恒
(湖南大学信息科学与工程学院，长沙410082)
(}通信作者电子邮箱heji“ong—conan@163，com)
摘要：基于无线通信和网络技术的三维空间定位是目前物联网领域的一个研究热点，针对当前三维目标定位
算法的精度低、复杂度高、功耗大等实际问题，提出了一种新型的分布式三维定位机制。该算法采用合作位置感应算
法(cIs)来进行空间网格划分，通过距离估计判定目标位置，并结合了高斯拟合、信号排序机制以及Bounding．inb似等
关键技术，有效降低了信号干扰，实现了局部网格划分，减少了网格投票开销。仿真结果表明，该算法与现有三维定位
算法相比，有更好的定位精度，并且实现简单，定位功耗较低。
关键词：物联网；三维定位；高斯拟合；网格划分
中图分类号：TP393．07文献标志码：A
PositioIlingaIgorithmb嬲edonInternetofthingsspatialmeshing
HEJia_hong+，ZHANGXiao—IIling，WANGYong—heng
(cof蛔e妒蚴)丌m￡ionScie聊eo砌E增i删一增，肌mn‰i抛”溉∞Ⅱ咿k肌眦R4l0082，C^im)
Abstract：Thethree—dimensionalspatialtargetpositioningbasedonwirelesscommunicationandnetworkingtechnologyis
ahotresearchtopicinthe6eldofIntemetofThing(IoT)．However，therearestillsomeproblemslikelowaccuracy，high
complexityandb逗powerconsumption，etc．Thus，adist“butedthree—dimensionalpositioningmechanismfortheenvironment
oftheIoTwa8pmposed．ThealgorithmusedCooperativeI．ocation-Sensing(CLs)tomesh画danddete珊inethetarget
10cationbytheestimateddistance．ItcombinedGaussianfitting，signalsonir曙mechanismandBounding—inboxalgorithm，
whichhadeffbctivelyreducedsignalinteIference．Moreover，itusedlocalmeshingtoreducetheg匕idvotingoverhead．The
simulationresultsshowthatthealgorithmisbetterthantheexistingthree—dimensionalpositioninga190dthminaccuracyaIld
hasalowerpowerco璐umption．
Keywords：IntemetofThings(IoT)；three—dimensionallocalizatjon；eaussianfi￡ing；副dmeshing
0引言
目前，物联网技术已经广泛应用于环境、交通、军事、航
空、医疗卫生等多方面…，而对于物联网中大多数应用来说，
没有时空标识的数据用处有限，而且节点的位置信息是物联
网进行上下文感知的依据，而目前的大多数定位算法都是针
对平面环境，而且有算法复杂度高、定位不准确、实时性差等
缺陷，难以应对物联网实际应用环境的复杂性。物联网应用
环境复杂多样，涵盖室内与室外多种场合，因此物联网对定位
算法提出自组织性、鲁棒性以及低能耗等要求。
定位算法根据定位机制的不同，分为两类：基于距离的
(range-based)定位算法和与距离无关的(range—free)旧。定位
算法，三维空间定位与二维平面定位相比，环境因素更加复
杂，节点的计算量也有所增大。目前，对于三维定位算法的研
究还处于起步阶段，成果较少，比较典型的有文献[3]提出的
近似球形内点测试(AppmximatePoint—In—sphere，APIs)算法，
这是一种典型的距离无关算法，其思想与平面定位算法中的
近似三角形内点测试(AppmximatePoint—In—TrianglIlalionTest，
APIT)算法类似，都是基于一种空间划分的思想：以一个锚节
点为球心，分别以它到附近其他锚节点之间的距离为半径画
球，就能把整个空间划分出大大小小的同心球体。待定位的
节点通过判断自己“在”还是“不在”这些同心球体区域中，最
终找到包含自己的最薄的一层球壳。然后以不同的锚节点作
球心，找到一系列这样的最薄的球壳，最后求取包裹区域的质
心。文献[4]提出无线传感器网络三维自身定位方法，通过
改进APIT算法得到三维空间定位算法APIT-3D，该算法通过
循环测试未知节点是处于由某4个节点所组成的四面体的内
部或外部，筛选出所有可能的四面体，从而不断缩小未知节点
的周边区域，得到节点的空间位置估计。文献[5]提出一种
基于弧心的分布式无线传感器网络节点定位算法，针对每个
未知节点，基于传感器节点之间的通信约束关系、空间几何关
系和锚节点的已知位置信息，从而在几何学角度建立起包含
未知节点的圆弧区域，将该圆弧区域的质心作为未知节点的
估计位置。还有其他的一些三维定位算法包括Landscape．
3D。61、Constmined一3D、三维距离向量一跳段(nree．
dimensionalDistallceVector-H叩，3D．DV—H叩)‘71等。
三维定位算法普遍存在的问题是为了追求一定的定位精
度导致计算量过大、定位时间过长、系统实时性大受限制，而
且往往对网络密度要求高，系统能耗过大，这些都大大限制了
三维定位算法的实用性。针对三维定位算法中的种种问题，
提出一种基于空间网格思想的分布式三维定位算法3D—cLs，
对传统平面网格算法合作位置感应算法(co叩erative
收稿日期：2012．06．06；修回日期：2012一07—2l。基金项目：湖南省质量技术监督局项目(2011004)。
作者简介：何佳鸿(1988一)，男，湖南永州人，硕士研究生，主要研究方向：物联网、嵌入式系统；张小明(1971一)，男，山西太原人，副教
授，博士，主要研究方向：物联网、云计算、数字卫生医疗；王永恒(1973一)，男，河北廊坊人，助理教授，博士，主要研究方向：物联网、数据挖掘。
万方数据
3518计算机应用第32卷
kc砒ion—sensjng，cLS)伸’的定位思想进行扩充，解决信号干扰
误差和网格划分带来的计算开销问题。结果表明该算法计算
量小，无需额外的节点硬件支持，对网络拓扑具有一定的鲁棒
性，通信开销和定位误差均比较小，弥补了目前许多方法存在
的不足，非常适合应用于物联网环境中。
1算法概述
定位区域的网格化思想因为其计算简便的特点，在平面
定位中得到广泛的应用。cLs算法就是一种很好的基于网格
化思想的定位算法。其算法基本思想是通过测距来对待定位
节点的位置进行估计，每个待定位节点都包含着一个被网格
化表示的区域，根据距离信息对网格投票，每个格子(cell)票
值的大小反映着锚节点对该格子的认同程度，票值越大，就表
示待定位节点在该格子内的可能性越大，最后所有票数最高
的格子构成了待定位节点的可能所在区域。该算法用测距来
作为未知节点位置估计的依据，所以算法对测距精度的依赖
性并不是很高，而又兼有非测距算法中计算简单的特点。3D—
cLS算法基于这种思想在测距稳定性和算法复杂性方面做出
了很大改进，并应用到三维环境中。
3D—cLs算法大体上可以分为测距通信过程、网格划分过
程和投票过程三个部分。测距通信过程主要通过节点间通信
来完成测距以及根据距离选取参与投票锚节点，在网格划分
过程中完成各个待定位节点自身的网格初始化，然后各个待
定位节点根据上一过程的结果完成各自的投票过程，计算出
自身的位置坐标。
整个网络由锚节点和未知节点两种角色组成，锚节点是
未知节点的参考点，在网络节点中所占的比例很小，可以通过
携带GPs定位设备等手段获得自身的精确位置。除锚节点
外的其他传感器节点都是未知节点，它们通过锚节点的位置
信息来确定自身的位置。所有节点均随机分布在模拟物联网
环境的三维无线传感网络的应用区域内。未知节点本身能够
维护用以存储相关信息的数据结构，包括节点ID、测距信息、
锚节点坐标等。
23D—CLS定位过程
2．1测距通信过程
测距通信过程第一步首先是测距过程，由待定位节点发
起，节点通信范围统一设定为R，任意待定位节点m首先不断
向周围一跳范围内锚节点广播信标消息，信标消息包含自身
的节点谢。，向周围的锚节点发起测距请求。锚节点n接收到
待定位节点的信标消息后，首先记录下节点m的网络地址
口d西。，然后进行高斯拟合滤波处理，过滤掉大范围的信号波
动，得出待定位节点m与锚节点件之间的距离d。。。根据测出
的距离得出容错区间(d…一占，d…+占)，占是容错参数。之后
锚节点n封装一个回复消息，包括锚节点n的ID峨、自身坐
标(z。，h，气)及得出的距离区间(d。，d。。)等信息。
3D·cLS算法中距离的确定采用接收信号强度(Reeeived
Signalstren殍hIndicator，RsSI)测距技术，由于无线电波在空
间传输过程中会受到多径、障碍物、绕射等随机因素影响，因
此需要选取一种信号模型，来减少这种误差，实际中常采用对
数一常态分布模型(109—distancedist抽ution)。9j，其数学表达
式如下：
P三(d)=PL(矗)+10xn×19(d／而)+丑j(1)
式中：甩(d)为经过距离d后的路径损耗；咒(cf0)为经过单
位距离后的路径损耗，取d=1，即可得到单位路径损耗
PL(磊)的值；氏为单位距离，通常取1m；瓦为均值为O的高
斯分布随机数，其标准差范围为4～10；n为信号衰减因子，范
围为一般为2～4。
在信号滤波处理过程中采取高斯拟合滤波处理。RssI
值测量过程中，大多数干扰使得测量值变小，所以同一个值对
应多个点的位置，这些现象使得强度值和距离的对应关系被
破坏，所以均值处理会造成很大的误差，HLM算法。10。提高了
10m内测距的精度，但需测量大量的环境参数，不便于使用。
高斯滤波¨叫被证明是一种十分有效的滤波方式，它的依据是
在自然现象和社会现象中，大量随机变量都服从或近似正态
分布，实验证实信号的误差分布也符合类似的原理，所以高斯
滤波能有效地减少测距误差的出现。其拟合函数为：
，(z)=÷孑e一学；
盯~，Z霄
卜2去弘弘
{臣■————■(2)
l／>。(雕港，．～肛)2【盯=√笪丰
其中：尺5田。为第i个信号强度值，m为接收到的信标。取
，(z)E[O．6，1]为大概率事件区，可以保留，然后取保留的
RSSI值平均。
测距通信过程第二步是要从各个锚节点收集到的距离回
复消息中选出矗群个节点(A抒作为参数可实验测试得到最佳
数值)参与接下来的投票过程。当待定位节点收到从锚节点
发出的回复消息，每个待定位节点会维护一个cLS消息表，
将收集到的所有回复消息都按照距离从小到大排序保存起
来。然后选取出前f4日个距离最小且处于通信范围尺之内的
锚节点参与到下一个的投票过程中。
2．2局部网格划分
经过测距通信过程之后得到参与投票的AH个锚节点，接
下来的就进入投票过程。首先要进行空问立体网格划分，三维
立体空间被划分为很多立方体小网格，网格密度理定义为一
个网格的边长。每一个未知节点维护自己独有的网格数据结
构。假设G。是待定位节点m维护的网格集合，％(i，j，七)是节
点m的投票结果集，ind(x，y，z)是网格的重心坐标集，其中i、
j、≈是溺格序号，它与网格坐标互、y、。的转换为(i√，^)Q+
a／2=(茗，y，。)。在待定位节点初始化完成之后，会根据每个
锚节点对未知节点位置区域的估计，对自己维护的网格进行
投票，一个格子票值的大小反映着锚节点对该格子的认同程
度，票值越大，表示待定位节点在该格子内的可能性越大，所
有票数最高的格子构成了待定位节点的可能所在区域。
在所有基于网格划分的定位算法中，都要面对的一个重
要的问题就是网格化以及它的检索所带来的开销问题，而这
一问题对于三维空间的网格划分的影响更加严重，全局的网
格划分必然带来巨大的开销负担，3D-cLs算法为了解决这一
问题而引入了一种改进Bounding．inbox【1。”3的思想，来对三
维空间进行局部网格划分，从而大大减少了网格划分所引起
的系统开销问题。
万方数据
第12期何佳鸿等：基于物联网空间划分的定位算法3519
Bounding-inbox是由加州大学伯克利分校的semic等提
出的一种非常简便的平面定位方法。本文对其进行了改进，，
然后将其应用于三维场景中。基本思想是构造以锚节点为球
心，未知节点到该锚节点的距离为半径所构成的球的外接正
方体，则未知节点必定位于锚节点的外接正方体之内，多个这
种锚节点的外接正方体形成一交叉区域，该交叉区域为一立
方体，则未知节点也必定位于该交叉立方体之内，因此可取该
交叉立方体的几何中心作为未知节点的初始估计坐标。该方
法只需一些简单的加减运算即可得到节点的初始坐标，可有
效地减小计算量，降低能量消耗。在3D-CLs算法中，本文使
用这种思想来预估计未知节点的所在区域，图1展示的是三
维改进Bounding—inbox算法示意图。
图1中点Js为未知节点，点A、B、C为锚节点，A、日、C在点
s的通信区域内，d。、d：、也分别为A、B、c到Js的距离，每个锚
节点构造一个以自身坐标(z。，n，毛)为球心，以各自距离为半
径的球的外接正方体，外接正方体形成的交叉立方体为这些
正方体的交集D，该交集在三维空间中对应的坐标范围为：
D=[max(戈。一d；)，max()，!一d。)，max(t—df)]×
[min(x。+d；)，min(y。+di)，min(z。+di)]；(3)
i=1，2，…，％
这种空间交集是对未知节点所在位置范围的最小估计，
对处于交集空间中的区域进行局部网格划分，大大降低了网
格划分所带来的系统开销，彻底解决了网格划分思想面临的
最大问题。
2．3投票过程
完成网格划分之后就要进行网格的投票过程，定义P…
为锚节点n对未知节点m投票结束后所认同的一系列小格子
的集合，设定投票权重为1，n包括所有参与本次投票的锚节
点。根据cLstable中收集的信息，进行投票过程。
P…={(戈，，，，z)∈G，nD，
d。i。≤~／(x。一∞)2+(y。一y)2+(=。一z)2≤d。。}
(4)
投票过程如下：
步骤1票值初始化。对于任意的小格子i蒯(x，，，，。)，设
置对应的口。(i，j，^)=O。
步骤2计算Pm。，对于ind(戈，)，，z)∈P…，得到"。(i，j，
％)并进行如下计算：
％(i，，，￡)=口。(i，，，玉)+1
步骤3所有锚节点投票结束后，选择得票值最高的小
格子组成的空间区域作为未知节点的可能位置区域。
由于空间测距误差和信号干扰等因素会影响投票结果，
3D—cLs设定了两个变量来作为判定定位成功与否的依据，分
别是投票门限(VotingThreshold，VT)和定位误差控制门限
(LocalErrorComrol鸭reShold，LECT)。投票门限"决定了
所有参与投票的锚节点对位置估计的赞同程度，即定位最大
可能区域内的格子的票值必须大于旧值，而三Ecr值是对最
大网格数量的限制，直接影响定位精度，不满足这两个参数都
视作定位失败，要准备新一轮定位过程。yr和￡Ecr值的选取
依赖于定位网络的具体情况，综合考虑如锚节点与未知节点
的比例、定位误差等因素。
步骤4选取可能位置区域组成几何体的质心作为未知
节点的估计位置。
3算法性能分析
为了验证3D—cLs算法的性能，首先考察在仿真环境下
3D-cLs算法中涉及的定位参数对算法定位误差的影响，然后
选取一种常见的定位算法DV—HOP算法的三维版本3D-DV—
HOP，分别从定位误差与通信报文数来与3D—cLs算法做对
比。仿真实验在100m×100m×100m的正方体空间中进
行，在该区域内随机部署100个传感器节点，每个节点的通信
半径均相同，设定为50m。为消除随机分布产生的误差，所
得仿真结果均为同样参数下仿真100次所得结果的平均值。
定位误差定义为节点估计位置与实际位置的距离与节点
通信半径的比值，如下：
4，——————————————————————————————————————————————一
∑√(；。1)2+(；。叶)2+(：。’)2er=堕—————i广——～(5)
见XⅡ
其中：n表示网络中未知节点总数目，(z。，y。，盈)是节点i的真
实位置坐标，(z。，)，。，毛)是节点i的估计位置，R为通信半径。
预先设定定位参数占=2m，A曩=5，网格密度d=2，投
票门限w与定位误差控制门限加C丁分别设定为4和30。在
锚节点比例为20％时各未知节点平均定位误差在o．18左
右，对相同条件下3D—DV．HOP算法定位误差进行考察，平均
定位误差为0．35左右，节点误差分布分别如图2～3所示。
椭
嗤
蛆
删
椭
赋
疆
删
节点编号
图23D．cIs定位误差分布
节点编号
图33D．DV—HOP定位误差分布
定位参数4H和Ⅱ的选取对定位准确性有一定影响，通过
0
9
8
7
6
5
4
3
2
l
0
l
0
O
0
0
O
O
O
0
0
O
9
8
7
6
5
4
3
2
1
0¨∞％叮％％㈣∞毗叫。
万方数据
3520计算机应用第32卷
仿真观察不同的参数所对应的定位准确性，从而选取最佳方
案，结果如图4—5所示。
黼
；2|《
魁
波
删
魃
增
删
参与投票节点数榭
图4A抒参数对定位误差的影响
网格密度口
图5a参数对定位误差的影响
从图4中可以看出，参与投票的节点数4H数值越大，定
位误差越小，这表明更多的节点参与投票，投票结果就越精
确，但同时参与投票的节点数增加也会增加算法开销。
图5表现的是网格密度n的变化给定位误差带来的影
响。从图中可知，网格密度越大，也就是单个网格越大，定位误
差越大，网格密度过小也会带来很大的算法开销。通过综合考
察两个参数与算法开销的关系，发现实际A日=5，d=4可以
得到相对理想的结果。
锚节点比例也是影响算法性能的重要指标，本文对3D—
cLs和3D—DV—HOP两种算法的定位误差进行对比仿真，结果
如图6所示。
锚节点比例7％
图6不同锚节点比例时两种算法定位误差对比
从图6可以看出，锚节点比例越高，定位误差越小，而且
3D—cLs算法的误差明显小于3D—DV．HOP算法。
通信报文数通常是无线网络中能耗的重要体现，而物联
网环境中对能耗要求比其他应用场合更加严格，与传统定位
思想相比，3D—cLS算法的低能耗特点能很好地满足物理网环
境对低功耗的要求，对比仿真如图7所示。
4结语
本文针对物联网应用环境的特点，提出了一种基于空间
网格划分的三维定位算法3D-cLs算法，该算法不需增加额
外的设备，算法计算量小，对网络拓扑具有一定的鲁棒性，定
位开销和定位误差均比较小。通过算法仿真可知该算法与同
类算法相比有着定位精度高，算法开销低等显著优势，能很好
地适应物联网环境的复杂特性。为了进一步提高节点三维空
问定位的精度和定位的稳定性，在未来的工作中需要进一步
研究如何建立较好的Rss衰减模型，或者如何减少环境对测
距的干扰，尤其是在非视距情况下的干扰，并进一步提升算法
实时性，使得算法能在保证高定位精度的同时还能对目标进
行动态跟踪定位。
锚节点比例／％
图7不同锚节点比例对两种算法通信报文数对比
参考文献：
【1]杨震．物联网发展研究[J]．南京邮电大学学报：社会科学版，
2010，12(2)：1—10．
[2】Y0uzHuHONG，MENGMQH，uANGHuAwEI，e￡。f．AIocali—
z“ona190rithminwirelesssensornetworksusingamobilebeacon
110de[C】／／IntemationalConferenceonIn』b肿ationAcquisition．
NewYork：IEEE．2007：420一426．
[3]吕良彬，曹阳，高洵，等．基于球壳交集的传感器网络三维定位算
法【J】．北京邮电大学学报，2006，29(5)：48—51．
[4]刘玉恒，蒲菊华，赫阳，等．无线传感器网络三维自身定位方法
(J】．北京航空航天大学学报，2∞8，34(6)：647—651．
【5】曾桂秀．基于弧心的无线传感器网络节点定位算法研究【D】．长
沙：中南大学，2007．
[6]zHANGLIQIANG，zHOuxlAOBO，CHENGQIANG．Landscape·
3D：Arobustloca】jzationschemeforsensornetworksovercomplex
3DteⅡains[C】／／Proceedings0f20016the31stIEEEConf毫renceon
I．，ocalComputerNetworks．升ewYork：lEEE，2006：239—246．
【7】曹敦，张静，傅明，基于移动代理的三维DV-HOP算法【J]．计算
机应用，2012，32(1)：134—138．
[8】FRETZAGIASC，PAPADOPOULIM．Co叩eratiVelocation喝ensing
forwirelessnetworks[c1／／Proceedings0fthe2ndIEEEAnnual
CoI讧erence仰PervasiveCompu虹nga!lCommunicalions．Washi“g-
toJl．DC：IEEEComputerS0cjet，''2004：121—131．
【9】张洁颖．王侠．基于RssI与LQI的动态距离估计算法[J】．电子
测量技术，2007，30(2)：142—145．
[10]孙佩刚．赵海，罗玎玎．智能空间中RssI定位问题研究[J】．电
子学报，2007，35(7)：1240—1245．
[11]詹杰，刘宏立，刘述钢，等基于RSSI的动态权重定位算法研究
【J]．电子学报，2011．39(1)：82—88．
[12】SIMICSN，SASTRYS．Adistlibutedalgorithmforlocalizalionin
randomwirelessnetwDrks【EB／0L】．[2012-05—12】．http：／／wen—
ku，baidu．coIn／view／ad67b4{8f越)069dc50220lOe．html．
[13】石为人，许磊，徐扬生．一种基于移动锚节点的静态无线传感器
网络定位算法【J】．仪器仪表学报，2007，28(3)：385—393．
纂钗辎迎圈
∞驺{；；巧∞¨¨∞0
O
O
O
O
O
0
O
O
万方数据
基于物联网空间划分的定位算法
作者：何佳鸿，张小明，王永恒，HEJia-hong，ZHANGXiao-ming，WANGYong-heng
作者单位：湖南大学信息科学与工程学院,长沙,410082
刊名：计算机应用
英文刊名：JournalofComputerApplications
年，卷(期)：2012,32(12)
本文链接：http://d.g.wanfangdata.com.cn/Periodical_jsjyy201212061.aspx
|
|
