一种基于栅格预置点匹配的无线传感器网络目标定位方法

闫新乐，谭 真，唐国明，封孝生

（国防科技大学 信息系统工程重点实验室，湖南 长沙 410073）

一种基于栅格预置点匹配的无线传感器网络目标定位方法

闫新乐，谭 真，唐国明，封孝生

（国防科技大学 信息系统工程重点实验室，湖南 长沙 410073）

目标定位是无线传感器网络应用领域中一个重要的问题，是进行目标跟踪的前提和基础。节点呈栅格部署的无线传感器网络由于拓扑结构特殊，在目标定位应用领域具有独特的优势。本文基于栅格部署的无线传感器网络，提出了栅格预置点目标定位方法，通过设定和选择合适的栅格预置点进行目标定位。仿真实验和实际测试实验表明，该方法在定位准确性和实时性方面较先前的单层栅格定位和双层栅格定位都有较大幅度的提高。

无线传感器网络；目标定位；栅格定位；预置点

无线传感器网络[1-3]（Wireless Sensor Networks， WSN）中的目标定位是由多个传感器节点对目标信号进行分别感知，然后利用协同感知结果配合特定的定位算法得到关于目标位置的过程。由于易部署、易安装、易扩展等特性，无线传感器网络技术在目标定位中体现出众多优势，一度成为国内外学者理论和实践研究的热点。

传感器节点按栅格部署构成的无线传感器网络是一种具有特殊结构的网络，虽然这种特殊拓扑结构对传感器部署的要求较高，但在定位实时性方面体现出巨大优势，即利用节点部署的规律性可以大大降低目标定位算法的复杂度，提高定位的速度。

本文基于栅格部署的无线传感器网络，在文献[4]双层栅格定位方法基础上，提出了一种使用多个预置点进行目标定位的策略，该方法不仅提高了传统的栅格定位方法和双层栅格定位方法的定位精度，而且降低了双层栅格定位方法的计算量和复杂度，进一步提高了定位的实时性。

1 相关工作

目前，国内外利用无线传感器网络进行目标定位跟踪的研究中，定位方法可分为基于距离的定位和与距离无关的定位两类。基于距离的定位方法主要是利用信号的衰减测算点对点的距离或角度，包括基于到达时间的方法 （如TOA[5]、TDOA[6]等）和基于信号到达角度的方法（如AOA[7]等）。与距离无关的定位方法主要利用感知信号的有无来判断目标是否出现在感知范围内，或根据信号强度计算感知节点序列等方法，通过多个节点协作完成目标定位，如二元传感器定位法[8]、近似三角形内点测试法APIT[9]、质心方法[10]和节点序列定位[11]等。

与上述基于节点随机分布传感器网络的目标定位方法不同，利用节点栅格部署的传感器网络确定目标位置是一类特殊的目标定位方法，目前针对该领域的研究也较少，主要方法有单层栅格定位和双层栅格定位。

单层栅格定位方法[4]是最简单、理想情况下的一种栅格定位方法，它将传感器节点收集到的目标信号强度按大小排列，从中选取强度最大的3个信号，这3个信号对应的感知节点所确定的正方形就是目标所处的栅格，然后将目标近似定位于该栅格的中心。然而，由于传感器节点本身分辨率的限制或者环境噪声的影响，当目标出现在距离两个或两个以上传感器节点相近的位置上时，便会出现传感器节点无法准确判断目标位置的现象。该方法由于没有考虑实际应用环境，只是一种理想化的理论方法，实用性较低。

双层栅格定位方法[4]是在理想栅格定位方法基础上，考虑实际使用过程中出现的环境噪声和测量误差提出来的，其核心思想是在栅格部署节点的拓扑结构下，划分了基本定位层和扩展定位层两类不同的栅格进行定位，使得基本定位层的栅格顶点或边界区域恰好是扩展定位层栅格的中心区域。这样，当目标出现在基本定位层栅格的顶点或边界等不确定区域内时，即可切换至扩展定位层进行定位。该方法考虑了实际使用过程中出现的环境噪声和测量误差，具有较强的实用性，但由于存在两层栅格划分和存储，计算量大且过程繁琐。

2 单、双层栅格定位

单层栅格定位是将感知信号强度按大小排列，从中选取强度最大的3个信号，这3个信号对应的感知节点所确定的正方形就是目标所处的栅格，进而可将目标近似定位于该栅格的中心处，如图1所示。

图1 单层栅格划分下的定位方法Fig.1 Sample of single layer grid division

在使用单层栅格定位过程中，由于传感器节点自身感知误差的存在或环境噪声的影响，文献[4]指出了该方法失效的两类情况：

1）如图 2（a），当目标出现在栅格顶点 a附近时，节点 b、c、d、e的信号强度大小可能无法正确区分，所强度最大的3个信号可能是（a，b，c）、（a，c，d）、（a，d，e）、（a，e，b）等，对应的定位栅格可能是栅格1、栅格2、栅格3或栅格4，故无法正确定位目标所在栅格；

2）如图 2（b），当目标出现在栅格线（b，e）附近时，节点 a、f、c、d的信号强度大小无法正确区分，所以强度最大的3个信号可能是（b，e，a）、（b，e，f）、（b，e，c）、（b，e，d）等，对应的定位栅格可能是栅格1或栅格2，故也无法确定目标所在栅格。

图2 单层栅格定位法失效的两种情况Fig.2 Two different failure case of single grid localization

针对单层栅格定位失效的问题，文献[4]提出了双层栅格定位方法，将栅格部署的传感器网络划分为基本定位层和扩展定位层，并使得基本定位层栅格的顶点和边界区域在扩展定位层栅格的中心区域，拓展定位层栅格的边界区域在基本定位层栅格的中心附近，如图3所示[4]。

图3 双层栅格划分示意图Fig.3 Sample of double layers grid division

双层栅格定位方法虽然解决了单层栅格定位过程中出现的两类失效问题，但是存在两个问题：1）两层栅格的划分需要更多的数据存储量和计算量，从而增加了算法的时空复杂度；2）扩展定位层栅格面积明显大于基本定位层栅格，导致该层的定位误差较大。这两个问题直接影响到栅格定位的实时性和准确性。

3 预置点定位

定义1：预置点，指栅格拓扑中易获取坐标值的特殊位置点，如栅格顶点、栅格中心等。

通过对单层和双层栅格定位的过程分析可知，其定位的本质是通过传感器获取的信号判断并选择合适的栅格预置点，并将目标定位在预置点处。单层栅格定位中的预置点是每个栅格的中心，而双层栅格定位中的预置点包括每个栅格的中心和4个顶点。

与双层栅格划分不同，本文通过增加栅格预置点的方法解决单层栅格定位失效的问题，一方面避免了双层栅格划分加大运算量的问题，提高了实时性；另一方面更有针对性地进行预置点选择和目标定位，提高了定位的准确性。

3.1 算法描述

3.1.1 预置点设置

在双层栅格定位的栅格预置点基础上，增加每条栅格边的中点为预置点，如图4所示。

图4 栅格预置点定位中预置点的设置图Fig.4 Preset positions settings in grid preset positions localization

如图4所示，将栅格中心、栅格顶点以及栅格线的中点设置为预置点，即作为目标位置的候选匹配点。这样，当目标出现在栅格顶点或栅格线附近时，通过匹配目标所在区域的预置点进行定位。

3.1.2 预置点匹配定位

在获取了所有节点对目标信号的感知强度之后，选择强度最大的3个节点由大到小排列，对应的节点序号构成定位节点序列。在一个极小的时间段内重复进行该过程k（k＞2）次，得到k个定位节点序列，然后按以下步骤进行目标的预置点匹配定位，以图4为例。

1）当 k 个节点序列相同，如栅格{S22，S21，S12}，则判断此时目标不处于两类不确定区域内，将目标定位于节点序列确定的栅格中心处，即预置点C11；

2）当k个节点序列确定的k个栅格共一个栅格顶点，如栅格{S22，S21，S12}、{S22，S23，S12}、{S22，S21，S32}、{S22，S23，S32}，或其 中的任意3个，则判断此时目标处于Ⅰ型不确定区域内，将目标定位于栅格的共同顶点处，即预置点S22；

3）当k个节点序列确定的k个栅格共一条栅格线，如栅格{S22，S23，S12}和{S22，S23，S32}，则判断此时目标处于Ⅱ型不确定区域内，将目标定位于栅格的共同边的中点处，即预置点L22-23。

3.2 算法设计

假设一个包含N个传感器节点的无线传感器网络，栅格行列为 n×m（n＞2，m＞2，n×m=N），进行栅格预置点定位只需记录以下信息：1）构成每个栅格的节点序号及其位置信息，2）当前获取的定位节点序列，故该方法的空间复杂度为O（n×m）+O（3）。而根据文献[4]，双层栅格划分定位方法的空间复杂度为 O（n×m）+O（（n+1）×（m+1））+O（4），可见栅格预置点方法的空间复杂度更小。

令每次定位时的节点序列采样次数为C（C＞2），设计栅格预置点目标定位的具体算法，使用伪代码描述如下：

Algorithm:栅格预置点定位法

其中GetSeq（int，int）为获取定位节点序列的方法，tempSeq[3]为定位节点序列；Gridmatch（Seq[]， Seq[]）为定位节点序列与栅格序列的匹配方法；SameGrid（·）、SameVertex（·）和SameSide（·）分别为判断C个栅格是否相同、共顶点和共线的方法，Grid.centre[x， y]、Vertex[x， y]和 Side.midpoint[x.y]分别为栅格中心、顶点和边中点的坐标。

由算法设计可知，该方法的时间复杂度为 O（n×m）+O（3），根据文献[4]，双层栅格划分定位方法的时间复杂度为O（n×m）+O（（n+1）×（m+1））+O（1），可见栅格预置点方法的时间复杂度更小。

3.3 算法分析

文献[4]根据测试数据，近似描绘出了确定区域和两类不确定区域。用不同区域的面积与总面积的比值近似目标出现在该区域的概率，进而可以近似定位误差。根据该思想，单层栅格定位、双层栅格定位和栅格预置点定位的平均误差可分别近似表示如下：

4 仿真实验

4.1 仿真模型及参数

实验采用随机路点模型（Random Way-point）模拟目标移动，即移动目标首先在仿真区域内选择一个目标路点，然后以不大于Vmax的速度向该路点做直线运动，到达该路点后，目标先停止一段时间，然后选择新的路点继续运动，如此往复。此外，为仿真传感器对目标信号探测具有一定的感知误差，在仿真过程中使用带噪声的Logarithmic信号衰减模型。

采用OPNET[12]Modeler 14.5网络仿真器构建无线传感器网络模型，进行单层栅格、双层栅格和栅格预置点3种不同定位方法的对比仿真实验，所涉及到的实验参数如表1所示。

4.2 实验结果与分析

跟踪效果的好坏通常由准确性和实时性反应，本文分布通过均方根误差（RMSE，Root Mean Square Error）和定位响应时间来度量跟踪的准确性和实现。其中，RMSE反映的是位置估计值与目标真实位置的偏离程度，定位响应时间是指仿真程序模拟一次从获取定位节点序列至得到定位结果所消耗的时间。

表1 仿真实验参数设置Tab.1 Settings in simulation experiment

针对不同的栅格边长和采样次数，分别测试单层栅格定位、双层栅格定位和栅格预置点定位的RMSE值和定位响应时间，并根据实验结果对3种方法的准确性和实时性进行分析。

4.2.1 准确性分析

图5显示了不同栅格边长下3种栅格定位方法的定位误差RMSE值。由图可知，3种定位方法中，单层栅格定位误差最大，平均定位误差值为10.4 m；双层栅格其次，平均定位误差值为8.5 m；栅格预置点定位的误差最小，平均定位误差值为6.9 m。这是因为栅格预置点定位方法与比其他两种方法相比，有效定位点数目更多，因此提高了定位精度。

图5 不同栅格边长下3种栅格定位方法的RMSE值Fig.5 RMSE values in 3 grid localization approaches with different edge length settings

4.2.2 实时性分析

不同采样次数下3种栅格定位方法的单次定位响应时间如图6所示。由图中3种定位方法的对比可知，单层栅格定位的响应时间最短，平均响应时间仅为2.3×10-2s；栅格预置点定位其次，平均响应时间为4.1×10-2s；双层栅格定位的响应时间最长，平均响应时间达到5.7×10-2s。与双层栅格定位算法相比，栅格预置点定位算法的时空复杂度较低，因此运算速度更快，实时性更强。

图6 不同采样次数下3种栅格定位方法的单次定位响应时间值Fig.6 Single localization response time in three grid localizationapproaches with different sampling frequencies

5 实际系统测试

为进一步测试双层栅格定位法在实际应用中的效果，我们使用实验室采购的传感器节点搭建了实际系统的测试平台。所使用的设备是美国Crossbow公司研发的MICA和Imote2平台产品，其中传感板采用MTS300CA模块，处理器和射频板采用XM2110CA模块，网关采用MIB520模块。

为比较双层栅格定位与栅格预置点定位方法的效果，采用与文献[4]相同测试场景，即在40 m×40 m的平坦区域内，按照栅格边长L=10 m进行传感器节点部署；共部署节点25个，其中普通节点21个，簇头节点4个；生成定位节点序列是采用的采样次数k=5。移动目标采用微型遥控汽车模拟，按照文献[4]中的预设路线移动，速度约为1 m/s；遥控汽车顶部载有一普通传感器节点，以10 Hz的频率向四周发射与其他节点相同频率的无线信号，用以模拟移动目标发出的物理信号。

6 测试结果

系统测试的结果如图7所示。从测试结果的对比中可以看出，相比较与双层栅格定位，栅格预置点定位描绘的预测目标轨迹更接近于目标的实际运动轨迹。数据结果显示，双层栅格定位的平均误差2.83 m，而栅格预置点定位的平均误差仅为1.22 m，后者的准确性明显高于前者。

7 结束语

基于节点栅格的无线传感器网络由于其特殊的拓扑结构，在目标定位应用领域具有非常强的实用性，利用其优势可以大大降低计算复杂度，满足特定用户对高定位实时性的需求。

本文基于栅格部署的无线传感器网络，根据合理设定和选择栅格预置点进行定位的思想，提出了栅格预置点目标定位方法。仿真实验和实际系统的测试结果表明，与单层栅格定位方法相比，该方法的定位精度大幅度提高；与双层栅格定位方法相比，该方法不仅具有更高的定位准确性，而且计算量和复杂度更小，实时性更高。

[1]刘云浩.物联网导论[M].北京：科学出版社，2011.

[2]孙利民.无线传感器网络[M].北京:清华大学出版社，2005.

[3]Akyildiz L F，et al.Wireless sensor networks:A survey.Computer Networks，2002，38（4）:393-422.

[4]唐国明，周广新，谢羿，等.一种基于双层栅格划分的无线传感器网络目标定位方法[J].计算机科学，2012，39（6）:25-29.

TANG Guo-ming，ZHOU Guang-xin，XIE Yi，et al.A doublelayer grid division based wireless sensor network target localization approach[J].Computer Science，2012，39（6）:25-29.

[5]Xinrong L.Collaborative Localization with Received-Signal Strength in Wireless Sensor Networks[C]//IEEE Transactions on Vehicular Technology，2007，56（6）:3807-3817.

[6]Boukerche A，Oliveira H A，et a1.Localization Systems for Wireless Sensor Networks[C]//IEEE Wireless Communications，2007，l4（6）:6-12.

[7]Kim D H，Lee SH，Park K S，et al.Development of an AOA location method using covariance estimation[C]//Proceedings ofCommunication Systemsand Networks， Palma De Mallorca，2007:14-18.

[8]Djuric P M，Vemula M，Bugallo M F.2004.Signal processing by particle ltering forbinary sensornetworks[C]//In Proceedings of the 11th IEEE Digital Signal Processing Workshop and IEEE Signal Processing Education Workshop.263-267.

[9]He T，Huang C，Blum B M，Stankovic J A，Abdelzaher T.Range-free localization schemesforlarge scale sensor networks[C]//In:Proc 9th Annual Int’l Conf on Mobile Computing and Networking （MobiCom） [San Diego， CA.2003：81-95.

[10]Gupta R，Das S R.Tracking moving targets in a smart network[C]//The VTC Fall 2003 Symposium，Oct.2003.

[11]Ziguo Zhong，Ting Zhu，Dan Wang and Tian He， Tracking with Unreliable Node Sequences[C]//28th IEEE Conference on Computer Communications， Apr.2009， Rio de Janeiro，Brazil.

[12]陈敏.OPNET网络仿真[M].北京：清华大学出版，2004.

Target localization based on grid preset-points in wireless sensor networks

YAN Xin-le， TAN Zhen， TANG Guo-ming， FENG Xiao-sheng
（Information Systems Engineering Key Laboratory， National University of Defense Technology， Changsha 410073， China）

Target localization is an important issue in the field of wireless sensor networks applications，which is also the prerequisite and basis for target tracking.Because of the special topology structure，grid-deployed wireless sensor networks have unique advantage in target localization.Based on the grid-deployed networks，this paper proposed a preset-points localization method by setting and selecting preset-points in grids.Simulation and real system test results showed that compared with singlelevelgridslocalizationanddouble-levelgridslocalization，thismethoddidbetterinthecapacitiesofaccuracyandreal-time.

wireless sensor networks； target localization； grid localization； preset-points

10.14022/j.cnki.dzsjgc.2014.16.042

TP393

A

1674-6236（2014）16-0139-05

2012-09-12 稿件编号：201209073

闫新乐（1986—），男，新疆维吾尔自治区昌吉人，硕士。研究方向：无线传感器定位，指控系统设计。