改定位

总第１９６期

２０１０年第１Ｏ期

舰船电子工程

Ｓｈｉｐ Ｅｌｅｃｔｒｏｎｉｃ Ｅｎｇｉｎｅｅｒｉｎｇ

Ｖｏ１．３Ｏ Ｎｏ．１０

６９

一种基于ＲＳＳＩ的无线传感器网络的改进定位算法

冯成旭刘忠程远国

（海军工程大学电子工程学院武汉４３００３３）

摘要在无线传感器网络的各种应用中，传感器节点必须首先知道自身的地理位置信息，才能进一步进行目标实时

监测、目标跟踪等应用。目前的节点自定位算法主要分为两大类：基于距离的和与距离无关的算法。文章提出了一种基于

ＲＳＳＩ的改进定位算法，从三角形质心定位的模型和加权质心的权重系数这两个方面分别进行了优化。最后经过Ｍａｔｌａｂ仿

真表明，该改进的算法比传统的ＲＳＳＩ算法有更小的定位误差。

关键词无线传感器网络；节点定位；接受信号强度指示；近似三角形内点测试

中图分类号ＴＰ３９１．９

Ａｎ Ｉｍｐｒｏｖｅｄ Ｌｏｃａｌｉｚａｔｉｏｎ Ａｌｇｏｒｉｔｈｍ

Ｂａｓｅｄ ｏｎ ＲＳＳＩ ｉｎ Ｗｉｒｅｌｅｓｓ Ｓｅｎｓｏｒ Ｎｅｔｗｏｒｋｓ

Ｆｅｎｇ Ｃｈｅｎｇｘｕ Ｌｉｕ Ｚｈｏｎｇ Ｃｈｅｎｇ Ｙｕａｎｇｕｏ

（Ｃｏｌｌｅｇｅ ｏｆ Ｅｌｅｃｔｒｉｃａｌ Ｅｎｇｉｎｅｅｒｉｎｇ，Ｎａｖａｌ Ｕｎｉｖｅｒｓｉｔｙ ｏｆ Ｅｎｇｉｎｅｅｒｉｎｇ，Ｗｕｈａｎ ４３００３３）

Ａｂｓｔｒａｃｔ Ｉｎ ｔｈｅ ａｐｐｌｉｃａｔｉｏｎｓ ｏｆ ｖａｒｉｅｓ ｋｉｎｄｓ ｏｆ ｗｉｒｅｌｅｓｓ ｓｅｎｓｏｒ ｎｅｔｗｏｒｋ．ｓｅｎｓｏｒ ｎｏｄｅｓ ｍｕｓｔ ｋｎｏｗ ｔｈｅｉｒ １ｏｃａｔｉｏｎ ｉｎｆｏｒ—

ｍａｔｉｏｎｓ ｆｉｒｓｔｌｙ ＳＯ ａｓ ｔｏ ｌａｎｃｈ ｆｕｒｔｈｅｒ ａｐｐｌｉｃａｔｉｏｎｓ ｓｕｃｈ ａｓ ｔａｒｇｅｔ ｒｅａｌ—ｔｉｍｅ ｍｏｎｉｔｏｒｉｎｇ ｏｒ ｔａｒｇｅｔ ｔｒａｃｋｉｎｇ．Ｔｈｅ ｃｕｒｒｅｎｔ ｎｏｄｅ

ｓｅｌｆ－ｌｏｃａｌｉｚａｔｉｏｎ ａｌｇｏｒｉｔｈｍ ｉｓ ｄｉｖｉｄｅｄ ｉｎｔｏ ｔｗｏ ｃａｔｅｇｏｒｉｅｓ：ｒａｎｇｅ－ｂａｓｅｄ ａｌｇｏｒｉｔｈｍ ｒａｎｇｅ－ｆｒｅｅ ａｌｇｏｒｉｔｈｍ．Ａ ｎｅｗ ｉｍｐｒｏｖｅｄ ａｌｇｏ—

ｒｉｔｈｍ ｗｈｉｃｈ ｉｓ ｂａｓｅｄ Ｏｎ ｔｈｅ ＲＳＳＩ，ＷａＳ ｐｒｏｐｏｓｅｄ．Ｉｔ ｏｐｔｉｍｉｚｅ ｔｈｅｓｅ ｔｗｏ ａｒｅａｓ：ｔｒｉａｎｇｌｅ ｃｅｎｔｒｏｉｄ ｌｏｃａｔｉｏｎ ｍｏｄｅｌ ａｎｄ ｔｈｅ ｗｅｉｇｈｔ

ｃｏｅｆｆｉｃｉｅｎｔｓ ｏｆ ｔｈｅ ｗｅｉｇｈｔｅｄ ｅｅｎｔｒｏｉｄ．Ｉｎ ｔｈｅ ｅｎｄ，ｔｈｅ Ｍａｔｌａｂ ｓｉｍｕｌａｔｉｏｎ ｓｈｏｗｓ ｔｈａｔ ｔｈｅ ｉｍｐｒｏｖｅｄ ａｌｇｏｒｉｔｈｍ ｈａｓ ａ ｓｍａｌｌｅｒ ｐｏ—

ｓｉｔｉｏｎ ｅｒｒｏｒ ｃｏｍｐａｒｅｄ ｔＯ ｔｈｅ ｔｒａｄｉｔｉｏｎａｌ ＲＳＳＩ ａｌｇｏｒｉｔｈｍ．

Ｋｅｙ Ｗｏｒｄｓ ｗｉｒｅｌｅｓｓ ｓｅｎｓｏｒ ｎｅｔｗｏｒｋｓ（ＷＳＮ），ｎｏｄｅ ｌｏｃａｌｉｚａｔｉｏｎ，ＲＳＳＩ，ＡＰＩＴ

Ｃｌａｓｓ Ｎｕｍｂｅｒ ＴＰ３９］．９

１ 引言

在无线传感器网络的许多应用中，监测到事件

的位置信息至关重要，定位技术是关键的技术之

一

。提到定位技术，我们不难想到全球定位系统

ＧＰＳ。但是采用ＧＰＳ技术的系统，往往用户节点

能耗高、体积大、成本高，这些特点使得ＧＰＳ技术

并不适用于低成本自组织的无线传感器网络。因

此，无线传感器网络定位已经成为当今一个很重要

的研究方向和热点问题。

在传感器网络中，定位算法通常划分为基于距

离（ｒａｎｇｅ—ｂａｓｅｄ）的定位算法和与距离无关（ｒａｎｇｅ—

ｆｒｅｅ）的定位算法ｌ２ｊ。基于距离的定位中，常采用的

方法有：基于到达时间ＴＯＡ的定位、基于到达时

间差ＴＤＯＡ的定位、基于接受信号强度指示ＲＳＳＩ

的定位和基于到达角度ＡＯＡ的定位等。与距离

无关的定位算法主要有：质心算法、ＤＶ—Ｈｏｐ算法、

Ａｍｏｒｐｈｏｕｓ算法、ＡＰＩＴ算法等等ｌ１Ｊ。其中最常用

的是利用锚节点到未知节点的ＲＳＳＩ（接受信号强

度指示）ｌ＿４ 值来估算未知节点到锚节点的距离，从

而实现未知节点的定位，因为它不需要添加任何额

外的硬件设备，只是在现有的硬件基础上读取信号

＊收稿日期：２０１０年５月２５日，修回日期：２０１０年６月２８日

作者简介：冯成旭，男，硕士研究生，研究方向：无线传感器网络。刘忠，男，教授，博士生导师，研究方向：无线传感器

网络、系统建模与仿真等。程远国，男，博七，副教授，研究方向：无线通信与网络等。

７０ 冯成旭等：一种基于ＲＳＳＩ的无线传感器网络的改进定位算法 总第１９６期

的场强值再经过数据处理和算法实现便可定位。

２ 算法原理

２．１三边测量法

在基于ＲＳＳＩ的定位中，最常见的便是 角形

图１三边测量法

质心定位算法＿６ 和加权质

心定位算法［引。而三角形

质心定位算法的理论基础

是三边测量法＿１］。如图１

所示。

如图１所示，已知Ａ、

Ｂ、Ｃ三个节点的坐标分别

是（ ，Ｙ ）、（ ＾， ６）、（ ，

Ｙ ），Ｄ点的坐标是（ｚ， ），它们到Ｄ点的距离分别

为ｄ ，ｄ ，ｄ ，则它们存在下列关系：

的坐标为：

２（ 一 ）］

２（ 一 ）Ｊ

广 ：一ｚ 十Ｙ：－－ｙｊ＋ 一 ］

Ｌ ：一ｚ；十 一 ＋ 一

２．２三角形质心定位法

然而，在实际的基于ＲＳＳＩ距离的定位中，由锚

节点到未知节点的ＲＳＳＩ值换算出来的距离值并不

是精确的，而且由于电磁场信号的衰减，换算出来

的这个距离值要大于从未知节点到锚节点的实际

距离。因此，三边测量法只是理想状态下的模型，

然而真实的模型应该是如图２所示。

如图２所示，Ｄ为未知节

点，Ａ、Ｂ、Ｃ为锚节点。分别以

通过Ａ、Ｂ、Ｃ到Ｄ的ＲＳＳＩ值

换算出的距离值为半径作圆。

由于Ｄ必定在Ａ、Ｂ、Ｃ相应的

通信半径以内，因此三圆必定

会有重叠的区域，如图中弧

图２三角形质心ＥＦ

、弧ＦＧ和弧ＧＥ所包围的

定位算法 区域就是该重叠区域

。而且，

未知节点Ｄ的实际位置必定在该重叠区域内。然

后，再对ＡＥＦＧ求质心，未知节点Ｄ的位置就是该

质心的坐标。即Ｄ的坐标为

ｆ墨± ＿玉Ｙ￣－ｂＹ ／－＋－Ｙｅ），这就是三角形质 １ ０ ， ｑ Ｊ， Ｌ肛一 ， ，火

心定位算法的基本原理。该算法复杂度低，易于实

现，适用于低成本、低功耗、硬件设备简单的无线传

感器网络。

２．３改进的算法分析

但是，三角彤质心定位算法在实际环境测试中

也有诸多不足：

１）三角形质心定位算法只适用于理想三角

形，即未知节点的位置在三个参与定位的锚节点所

构成的三角形的内部如图３。在实际的环境中，因

为锚节点是大规模随机布放的，因此必定存在一些

非理想的三角形的情形并不适用于三角形质心定

位算法，如图４未知节点并不在锚节点三角形

ＡＢＣ的内部；如图５，与未知节点相邻的３个锚节

点并不能构成三角形。在这些非理想三角形的情

形下，三角形质心定位算法并不适用，如果不予考

虑的话必定带来更严重的误差。所以，考虑将该算

法进行优化，在进行三角形质心定位算法之前进行

理想三角形验证。验证未知节点Ｄ是否在由三个

锚节点所构成的三角形内部，如果不在其内部则将

该三角形进行舍弃，继续寻找，直到找到理想的三

角形后再进行三角形质心定位算法。

Ｃ

图３理想 图４非理想 图５非理想

三角形 三角形 三角形

２）三角形质心定位算法只是采用了３个锚节

点的ＲＳＳＩ数据进行定位，并未利用整个网络的数

据，从而造成了有效资源的浪费。而且，当这锚节

点因偶然因素造成数据失真时，会给定位带来更大

的误差。因此，考虑将网络中更多的理想三角形参

与定位，从而给未知节点一个更准确的定位。

３）三角形质心定位算法并没有考虑ＲＳＳＩ数

值对距离的影响程度。在实际的无线电传播路径

损耗模型中，ＲＳＳＩ值的衰减与距离的增加并不是

线性关系。随着未知节点到锚节点距离的增加，由

ＲＳＳＩ数值的偏差产生的换算距离的误差会迅速增

大。因此，考虑在进行定位算法时引人权重系数来

体现锚节点对未知节点位置的影响程度，从而来减

小误差。其基本思想是：ＲＳＳＩ数值越大的锚节点，

对未知节点位置的影响力越大。在进行质心定位

算法时，将每一个决定质心的点的坐标都乘以一个

权重系数，以此来综合权衡计算得出最终的未知节

２｛）１０年第１Ｏ期 舰船电子工程

点位置。

２．４改进的算法原理

针对第一个问题，理想三角形优选的解决方

案，最佳莫过于近似三角形内点测试法ＡＰＩＴ。 中

的核心思想。ＡＰＩＴ测试的基本原理如图６、 ７

所示。

ｊ４ ……～７８

Ｃ

图６近似三角形

内点测试原理

……一 口

，

／＼

．

Ｃ

图７近似三角形

内点测试原理

假设存在一个方向，节点Ｄ沿着这个方向移

动时会同时接近或者远离Ａ、Ｂ、Ｃ三个节点。那么

节点Ｄ位于２ｘＡＢＣ之外，如图７；否则节点Ｄ位于

△ＡＢＣ之内，如图６。

而在实际的环境测试中，如果未知节点Ｄ收

到的ＲＳＳＩ数值在增大，则说明Ｄ在远离锚节点；

反之，如果Ｄ收到的ＲＳＳＩ数值在减小，则说明Ｄ

在接近锚节点。

利用ＡＰＩＴ算法的核心思想来进行理想三角

形的优化选择，可以看到如上图中的两种非理想三

角形在ＡＰＩＴ测试中会得出未知节点Ｄ在△ＡＢＣ

之外，对这种三角形予以舍弃，只保留未知节点在

其内部的理想三角形。

对于第二个问题，改进后的算法采用了更多的

锚节点的有效数据。对ＲＳＳＩ数值达到一定门限的

锚节点都认为是可以参与定位算法的有效节点。

而ＲＳＳＩ数值低于这个门限的锚节点因为会带来比

较大的误差所以就予以舍弃。

针对第三个问题，权重系数的选择是一个重

点。由于在自由空间无线电传播路径损耗模型中，

ＲＳＳＩ数值与距离的函数关系类似一个反比例曲线

的模型。所以，在进行加权定位计算时，给定这个

权重系数为距离的倒数。在具体的环境测试中，将

每个优选的理想三角形进行质心定位计算后得出

一个未知节点的近似坐标，所有的理想三角形的计

算结果组成～个质心坐标的序列，其中的每个质心

的权重系数为每个参与定位的三个圆的半径之和

的倒数。例如，在图２中，对于理想ＡＡＢＣ的定位

结果是Ｄ的坐标，然后Ｄ的权重系数就是

』ＪＵ权质心算法，得出的结果就是最后更精确的未知

节点的坐标。

３ 算法过程

定位算法的整体流程：

１）收集所有锚节点到未知节点的ＲＳＳＩ数值，

并多次采集取其均值。然后，设定一个ＲＳＳＩ值门

限，将ＲＳＳＩ数值低于这个门限的锚节点予以舍弃，

高于这个门限的锚节点视为有效节点，将其数据保

留。

２）将所有有效节点按照ＲＳＳＩ数值的大小进

行降序排序，假设有九个有效的锚节点即（Ｒｉ，Ｒｚ，

Ｒ 一，Ｒ ），这里Ｒ 为最大的ＲＳＳＩ值，＿Ｒ 为最小

的ＲＳＳＩ值。

３）将所有的ＲＳＳＩ数值根据无线电传播路径

损耗模型进行换算出距离，得出一个相应的距离序

列（ｒ１，ｒ２，ｒ．｛，…，ｒ ），因此有，Ｅｌ＜ ＜ｒ３＜…＜ 。

４）将所有的有效锚节点所组成的三角形集，进

行理想三角形的优化选择。因此，共有 个三角形，

进行 次近似三角形内点测试后，将测试结果为理

想的三角形予以保留，非理想的三角形予以舍弃。

５）将保留的理想三角形进行如图２所示的质

心定位算法，得出未知节点第一阶段定位的近似位

置（ ， ），共有＂ｚ组近似位置。

６）分别计算各理想三角形的权重系数，令权

１ 重系数为Ｑ，Ｑｉ－ 干 １ ，其中 ， ，ｒｃ 分别

为各理想三角形中各锚节点到未知节点的距离，共

有 组。

７）将所有的理想三角形的输出结果（即未知

节点第一阶段定位的近似位置（ ，， ））分别与其

相应的权重系数相乘，进行加权质心定位。最后的

输出结果就是未知节点的坐标（ ，ｙ），即

干 １

。在此，对于圆Ａ的半径Ｄ就是通过 ４

ＲＳＳＩ数值换算后锚节点Ａ到未知节点Ｄ的距离。

最后将所有的理想三角形计算出的点的坐标进行

∑Ｑｚ Ｊ…

Ｘ＝＝￡土一

∑Ｑ

ｉ：】

∑ＱｉＹ

ｙ一 Ｌ一

∑Ｑ

算法仿真

在Ｍａｔｌａｂ平台上进行该改进的定位算法仿

（下转第８８页）

贾莉娜等：某通信中央控制器仿真检测平台的设计与实现 总第１９６期

Ｃ＃语言使用起来便捷，功能强大，是微软主推的编

程语言之一。配合Ｖｉｓｕａｌ Ｓｔｕｄｉｏ ２００８集成开发环

境，高效的实现人机交互界面，外观美观，并且软件

的稳定性高。

向某通信中央控制器

发送初始采集数据

Ｊ是 Ｉ

采集中央控制ｌ ｌ处理与上位机

器反馈的数据Ｉ随讯非文时部

更新匹配状态

图３通信中央控制器仿真检测平台软件设计流程

４ 结语

基于ＰＯｗＥＲＰＣ硬件系统的实时ＲＴＩ ｉｎｕｘ

系统可完成３０ｋＨｚ的实时数据采样频率，根据采

样定理，通信中央控制器仿真和检测平台可还原

１５ｋＨｚ模拟和数字信号。在通信装备维修保障的

实际工作中，此仿真和检测平台不但可以检测某通

信中央控制器的故障，而且还可以在实验室里仿真

通信中央控制器的实际工作状态。同时，此平台的

实现对提高我军通信维修保障装备的数字化维修、

精确化保障等都具有重要意义。

参考文献

Ｅ１］姜智华，付字卓，何双江，等．基于ＰｏｗｅｒＰＣ嵌入式硬件

的Ｌｉｎｕｘ桌面系统构建［Ｊ］．计算机工程，２００７，３３（２４）

［２］罗维斌．ＣＰＬＤ技术在密频比宽域广谱伪随机信号发生

中的应用研究［Ｄ］．中南大学，２００７

［３］吴继华，王诚．Ａｌｔｅｒａ ＦＰＧＡ／ＣＰＬＤ设计（高级篇），２００５

Ｅ４］Ｔｅｘａｓ Ｉｎｓｔｒｕｍｅｎｔｓ．ＳＮ７４ＶＭＥＨ２２５０１Ａ ＤＡＴＡＳＨＥ—

ＥＴ．２００７

［５］王亚玲，周安栋，曹旭峰，等．基于嵌入式系统的备件检

测平台的设计与实现［Ｊ］．微计算机信息，２００８，２４（２０）：

２６～２８

Ｉ－６］曲晓明，孟哲．对ＭＹＳＱＬ数据库的访问方法的研究

［Ｊ］．计算机科学技术，２００７

绵 ｛！： ’ ’ ： ！ 币 ｛’ ！；

（上接第７１页）

真。组建一个虚拟的实验场景，初始条件为无线传

感器网络在一个１００ｍ＊１００ｍ的正方形区域内。在

此，锚节点是随机的分布在这个正方形的区域内的。

节点的有效通信半径设定为５０ｍ。每次仿真结果都

是通过运行算法１００次，然后取平均值得到的。

图８仿真结果分析

减小了。

５ 结语

由图８分析可知，当

锚节点数目较少（１０个）

的时候，改进的算法对于

普通的质心定位算法误差

并没有明显的提升。但是

随着锚节点数目的增加

（２０个以上），误差就明显

本文提出了一种基于ＲＳＳＩ的改进定位算法。

仿真结果表明，本文算法比传统的ＲＳＳＩ定位算法

有更好的定位精度。将近似三角形内点测试的核

心思想引入理想三角形的筛选，加权算法中权重系

数模型的选择，都能够明显减小定位误差。但是同

时也带来了算法复杂度的提高。因此，下一步的工

作是研究理想三角形的优化选择机制，以降低算法

的复杂度。以进一步优化算法的整体性能，从而得

到更好的定位效果。

参考文献

Ｅ１］孙利民，李建中，陈渝，等，无线传感器网络［Ｍ］．北京：

清华大学出版社，２００５

［２］王福豹，史龙，任丰原．无线传感器网络中的自定位系

统和算法［Ｊ］．软件学报，２００５，１６（５）：１１４８￣１１５７

［３］陈维克，李文峰，首珩，等．基于ＲＳＳＩ的无线传感器网

络加权质心定位算法［Ｊ］．武汉理工大学学报（交通科

学与工程版），２００６，３Ｏ（２）

［４］Ｈｅ Ｔ，Ｈｕａｎｇ Ｃ，Ｂｌｕｍ Ｂ Ｍ，ｅｔ ａ１．Ｒａｎｇｅ－ｆｒｅｅ ｌｏｃａｌｉｚａ—

ｔｉｏｎ ｓｃｈｅｍｅｓ ｆｏｒ ｌａｒｇｅ ｓｃａｌｅ ｓｅｎｓｏｒ ｎｅｔｗｏｒｋｓ［Ｃ］／／Ｐｒｏｃ

９ｔｈ Ａｎｎｕａｌ Ｉｎｔ’１ Ｃｏｎｆ ｏｎ Ｍｏｂｉｌｅ Ｃｏｍｐｕｔｉｎｇ ａｎｄ Ｎｅｔ—

ｗｏｒｋｉｎｇ（ＭｏｂｉＣｏｍ），Ｓａｎ Ｄｉｅｇｏ，ＣＡ．，２００３：８１～９５

［５］赵昭，陈小惠．无线传感器网络中基于ＲＳＳＩ的改进定

位算法ＥＪ］．传感技术学报，２００９（３）

［６３林玮，陈传峰．基于ＲＳＳＩ的无线传感器网络三角形质

心定位算法［Ｊ］．现代电子技术，２００９（２）

［７］周四清，陈锐标．无线传感器网络ＡＰＩＴ定位算法及其

改进［Ｊ］．计算机工程，２００９（４）

亟