自适应无线传感器网络室内定位算法研究*

周建国 张 鹏 冯 欣

(1)武汉大学测绘学院，武汉 430079 2)精密工程测量和工业测量国家测绘局重点实验室，武汉430079)

自适应无线传感器网络室内定位算法研究*

周建国1，2)张 鹏1，2)冯 欣1，2)

(1)武汉大学测绘学院，武汉 430079 2)精密工程测量和工业测量国家测绘局重点实验室，武汉430079)

传统的基于接收信号强度测距定位需要人工建模获取定位场景的先验测距模型参数，无法适应复杂及动态变化的环境。利用参考节点之间相互通信为每个参考节点赋予不同的路径损耗指数的特性，实现了室内定位的自适应和自动化。测试结果表明，与采用单一的测距模型参数相比，该算法提高了定位精度。

无线传感器网络;室内定位;接收机;信号强度;路径损耗指数

1 前言

基于位置的服务(LBS)需要知道用户的位置坐标，当前，绝大多数的定位都是通过全球卫星定位系统(GPS)实现的。但在室内、地铁、隧道等场景中，由于接收不到卫星信号导致无法利用GPS确定用户位置。此时需要寻找GPS的替代产品实现定位。无线传感器网络［1］以其低成本、低功耗成为了这些场景中定位的绝佳选择。

基于接收信号强度(RSSI)的无线传感器网络定位只需要具有无线收发功能的传感器节点，不像基于超声波、红外等的定位需要额外的硬件设备支持，进一步减少了设备成本，也使得该方法备受关注。无线室内定位技术主要分为三边测量法和场景分析法［2］。三边测量法通过测量未知点到多个已知参考点的距离计算其位置。场景分析法首先采集定位场景内的特征信息，然后在定位阶段通过匹配算法确定未知点的坐标。在利用RSSI定位时，无论是三边测量法还是场景分析法都需要在离线阶段人工采集数据建立测距模型或者是特征信息数据库。如何消除这一前期工作实现定位的自动化并提高定位精度和环境适应性是无线传感器网络定位的研究重点。

2 测距模型分析

采用基于RSSI的三边测量法进行室内定位时，首先需要建立RSSI与距离的关系，即测距模型;然后在定位阶段利用该测距模型将RSSI转换为距离再采用相应的定位算法求取未知点的坐标。

根据自由空间损耗模型［3］可知，接收信号功率(P)和信号传播路径长度(d)存在如下关系:

式中，Pt是发射器的发射功率，GT和GR分别是发射器和接收器的天线增益，λc是无线电波长，n是路径损耗指数。

在距离发射器为d1和d2两个不同位置测量接收信号功率P1和P2。即可得:

假设发射器和接收器的天线增益GT、GR相同，对式(2)、(3)进行处理，并取信号传播路径长度d1=1 m，即可得基于RSSI的测距模型:

式中PR是信号传播路径长度为d2时的接收信号强度，单位为dbm，A是距离发射器1 m处的接收信号强度，X是服从(0，δ)的正态分布的观测误差。

由测距模型可知，只要知道和路径损耗指数n，就可以通过测量接收器处的接收信号强度PR求得发射器和接收器之间的距离d2。

在假设发射器和接收器的天线增益GT、GR不变的情况下，A值可以认为与信号路径无关，仅受发射器的发射功率Pt的影响。故在采用未知节点发送参考节点接收的定位模式时，只需要一个A值。而路径损耗指数却受到定位场景内多路径效应、阴影、衰落以及环境动态变化等的影响。那么在环境复杂及动态变化的定位场景内仅使用同一个路径损耗指数n是不恰当的。为了提高该测距模型的定位精度，应根据定位场景的情况选取多个不同的路径损耗指数n。

3 算法分析及实现

传统的基于RSSI测距模型的定位算法中的测距模型参数是通过人工建模获取的［4］。对于A值，在天线各向同性的条件下，一般是通过测量距离发射节点1 m处的RSSI然后取平均获得。路径损耗指数n采用拟合的方法获取，即在定位场景内沿某一直线以一定的间隔测量多个RSSI，然后通过对数曲线拟合获取路径损耗指数n。或者选取几个坐标已知的点，通过测量参考节点到这些点的RSSI，再利用它们到参考节点的距离已知这一条件采用线性回归求取值和值。人工建模获取模型参数的缺点就是不能实现定位的自动化，且无法适应一些复杂及动态变化的定位场景。也有研究利用参考节点之间通信来获取测距模型参数［5］，但是在复杂的环境下只使用一个路径损耗指数是不够的，要根据参考节点的数量采用多个路径损耗指数。

3.1 算法描述

在采用WiFi无线接入点定位时，可以给每个无线接入点赋予不同的测距模型参数来提高定位精度［6］。但WiFi节点之间无法相互通信，需要用复杂的算法才能达到其目的，而无线传感器网络节点之间没有这个限制。于是可以充分利用作为参考节点的传感器节点相互通信来提高定位精度。本算法采用集中式定位模式，即未知节点发送信息参考节点测量RSSI传送到电脑终端进行处理取得未知节点的坐标(图1)。集中式计算的优点在于从全局统筹规划，能够进行复杂计算，可以获得相对精确的位置估计［7］。

图1 集中式定位模式Fig.1 Centralized location model

第一阶段，终端发送定位命令，未知节点收到命令后周期性地广播定位请求信息，处于通信范围内的参考节点收到该信息后测量RSSI并将数据最终传回电脑终端。当终端获得足够的RSSI数据时则发送命令让未知节点停止广播。此时终端虽然获得了多个未知节点到参考节点的RSSI，但没有测距模型参数无法将RSSI转化为距离值，所以也无法实现定位，这时需要利用参考节点相互通信获取测距模型参数。

第二阶段，终端根据RSSI值的大小选取N(N≥4)个参考节点发送其相互通信获取测距模型参数的命令。这些节点收到命令后开始互发信息。以参考节点i为例，节点i向其他参考节点发送信息，其他参考节点测量该信息的RSSI然后将结果转发至终端。当收集到足够的RSSI数据时终端即可计算出节点i的测距模型参数。因为参考节点的坐标已知，则参考节点i到其他参考节点的距离是已知的。即dij已知:

其中，dij是参考节点i到参考节点j的距离。(xi，yi)是节点i(i∈N)的坐标，(xj，yj)是参考节点j(j∈N，j≠i)的坐标。对于参考节点i，根据式(4)的测距模型，设参考节点i的模型参数为Ai和ni，可得:

式中Pj为节点j的RSSI。通过参考节点i到N-1个参考节点的RSSI可以采用线性回归求出节点i的模型参数为Ai和ni。同理，对于其他参考节点，可采用同样办法计算出它们的测距模型参数。由于我们采用的是集中式定位模式，需要的只是多个路径损耗指数，故此时将这些路径损耗指数保留，对于A值，我们并不需要。

第三阶段，利用第一阶段获取的RSSI求取未知节点的坐标。设未知节点的坐标为(x，y)，与发射功率相关的模型参数为A，可得

式Pi中是未知节点到参考节点i(i∈N)的RSSI，ni为参考节点i的已获取的路径损耗指数，(xi，yi)为参考节点i的坐标。由于Pi的观测误差服从(0，δ)正态分布，为最小二乘问题。即:

其中:

由于fi(X)并非线性函数，用Gause-Newton法解此非线性最小二乘问题。

1)取初始点X(1)=［A(1)，x(1)，y(1)］，并置精度要求为ε，令k=1;

得到Gause-Newton方向d(k);

4)令X(k+1)=X(k)+d(k);

5)令k=k+1，转2)。

3.2 精度分析

由Δx和Δy可以计算未知节点的点位真误差ΔP为:

未知数的协因数阵为:

3.3 算法实现

TinyOS是专为无线传感器网络设计的开放源代码的嵌入式操作系统，该系统及其应用程序采用nesC语言实现［8］。本定位算法在未知节点、参考节点以及基站节点端的程序即采用nesC语言实现。为了获取未知节点发送信息及参考节点相互通信时接收到的RSSI，需要定义消息数据结构，其中包含发送接收节点的ID及接收到数据包的RSSI，填充这些数据之后利用TinyOS自身的Collection收集协议将其多跳自组织的汇聚到基站节点。当需要发送定位命令或者是参考节点通信的命令时则利用Dissemination分发协议将基站传递过来的命令分发给目标节点。基站节点起到了连接计算机终端和传感器网络的桥梁作用。计算机终端的命令发送、数据接收以及数据处理程序采用Java语言来实现，充分利用了TinyOS提供的通信接口。具体的定位流图如图2所示。

4 测试结果分析

实际的室内定位测试采用的是Crossbow公司生产的IRIS型号传感器节点［9］。该节点采用符合IEEE802.15.4的Atmel RF230无线收发器和Atmega128l微处理器。实际测试时的节点分布如图3所示。共采用了5个参考节点，图中黑色点位为参考节点的位置，为了进行定位误差分析，一共选取了15个未知点位进行测试，如图中的白色点所示。参考节点通过相互通信计算得到的各自的路径损耗指数如表1所示。

图2 定位流程Fig.2 Positioning flowchart

图3 测试节点分布Fig.3 Distribution of test nodes

表1 各参考节点的路径损耗指数Tab.1 Path loss exponent of the reference nodes

先采用每个参考节点的路径损耗指数作为单一的测距模型参数，计算未知节点坐标并利用预先精确测量的真实坐标计算点位真误差;然后再给每个参考节点赋予不同路径损耗指数来计算未知节点坐标并同时计算点位真误差，最终的误差分布如图4所示，图中粗黑线代表给每个参考节点赋予不同的路径损耗指数获得的结果。由图4可以看出，与采用单一的路径损耗指数相比，给予每个参考节点赋予不同的路径损耗指数的确减小了未知节点的点位真误差。

图4 未知节点点位真误差Fig.4 Point true error of unknown nodes

5 总结

通过对无线室内定位的测距模型进行分析，认为在复杂的室内环境下，采用多个不同的路径损耗指数有利于提高室内定位的精度。同时为了克服传统的人工建模获取测距模型参数不能适应变化的环境问题，通过参考节点相互通信在定位时实时获取多个路径损耗指数。实际测试结果表明，与采用单一的路径损耗指数相比，赋予每个参考节点不同的路径损耗指数的确能够改善未知节点的定位误差。

1 任丰原，黄海宁，林闯.无线传感器网络［J］.软件学报，2003，14(7):1 282-1 291.(Ren Fengyuan，Huang Haining and Lin Chuang.Wireless sensor networks［J］.Journal of Software，2003，14(7):1 282-1 291)

2 HightowerJ and Borriello G.Location systems for ubiquitous computing［J］.Computer，2001，34(8):57-66

3 安德烈·戈德史密斯.无线通信［M］.北京:人民邮电出版社，2007.(Andrea Goldsmith.Wireless communication［M］.Beijing:Postsamp;Telecom Press，2007)

4 CC2431 location engine.Application Note AN042［EB/OL］.Texas Instruments，2006.

5 Janire Larranaga and Leire Muguira.An environment adaptive ZigBee-based indoor positioning algorithm［C］.2010 International Conference on Indoor Positioning and Indoor Navigation.2010:1-8.

6 Chintalapudi K，Iye A P and Padmanabhan V N.Indoor localization without the pain［A］.Proceedings of the sixteenth annual international conference on Mobile computing and networking［C］.Chicago，ACM2010:173-184.

7 王福豹，史龙，任丰原.无线传感器网络中的自身定位系统和算法［J］.软件学报，2005，16(5):857-868.(Wang Fubao，Shi Long and Ren Fengyuan.Self-localization systems and algorithms for wireless sensor networks［J］.Journal of Software，2005，16(5):857-868)

8 David Gay，et al.The nesC Language:A holistic approach to networked embedded systems［A］.Proceedings of the ACM SIGPLAN［C］.California:ACM2003:1-11.

9 Crossbow Corporation.MPR/MIB user’s manual［R］.Crossbow Corporation，2007.

STUDY ON ADAPTIVE ALGORITHM FOR WIRELESS SENSOR NETWORK INDOOR POSITIONING

Zhou Jianguo1，2)，Zhang Peng1，2)and Feng Xin1，2)

Indoor positioning by the use of wireless sensor networks is a hot topic for research.The traditional ranging positioning method based on the strength of

signals can not work in complex and dynamic environment because the necessary priori ranging model parameters of the positioning scene can only be obtained through artificial modeling.The current research based on the analysis of ranging models，by attaching different path loss exponents to each reference node through the communication between the reference nodes，achieves the self-adaptation and automation of indoor positioning.The experimental results show that the positioning accuracy is improved with this algorithm compared to the method through single model parameters.

wireless sensor network;indoor position;receiver;signal strength;path loss exponent

1671-5942(2012)02-0074-04

2011-11-03

国家自然科学基金(41074025);武汉大学青年教师资助项目(111172)

周建国，男，1988年生，硕士研究生，主要研究方向为无线传感器网络室内定位.E-mail:tinyos@whu.edu.cn

P227

A

(1)School of Geodesy and Geomatics，Wuhan University，Whan 430079 2)The key Lab.of Precise Engineering and Industry Surveying，SBSM，Wuhan 430079)