APIT算法在不同传播模型中定位性能分析

陈 强

(1.西安电子科技大学电子工程学院，陕西西安 710071;2.重庆三峡学院信号与信息处理重点实验室，重庆万州 404100)

无线传感器网络由部署在监测区域内的大量微型传感器节点组成，它们通过无线通信方式形成一个多跳的自组织的网络系统［1］。在许多无线传感器网络应用中，传感器节点的位置信息尤为重要。但为每个传感器节点配置定位装置是不现实的，通行的做法是为其中小部分的节点配置GPS接收器(锚节点)，其他节点(未知节点)的位置开始时是未知的，它们利用锚节点信息来估计自己的位置感器节点的定位问题，在许多无线传感器网络应用中是一个重要的问题。在无线传感器网络系统中，物理层非理想特性是一种常见的且不容忽略的形成定位误差的因素，可具体表现为无线信号传输的不规则性(Radio Irregularity)。由于无线信号受到周围环境的影响，一些定位算法根本无法被某些未知节点所执行，或者定位算法的性能会变得很差。传统的定位算法并没有考虑到实际环境中通信模型的不规则带来的影响，即使有些算法描述了不规则通信模型给算法带来的影响，但没有计算出各种算法在不同传播模型中定位误差，文中用仿真实验的方法，分析 APIT(Approximate Point－In－Triangulation Test)算法在不同通信模型中的性能，为无线传感器网络不同场景具体应用过程中传播模型选择提供理论支撑［2－3］。

1 传播模型

1.1 规则传播模型

在规则传播模型(Regular model)中［3－4］，信号接收强度的表达式为

其中，PR(d)为接收信号功率;PT为发送信号功率;PL(d0)为参考距离d0的路径损耗功率;η为路径损耗指数;d为发送端和接收端的距离。这种模型是各向同性(Isotropic Radio)的，即信号变弱都来自同一方向。但事实上信号的变弱来自不同的方向，实际中规则传播模型不能实现信号的最大传输。

1.2 不规则传播模型

无线信号的传播会受到阴影传播、反射传播、折射传播、散射传播、衍射传播等因素的影响，使接受信号强度与距离之间的关系难以确定，用规则的通信模型难以模拟出定位算法在实际应用中可能取得怎样的性能。不规则传播模型有 RIM模型、DOI(Degree of Irregularity)模型两种，相对于规则传播模型，不规则传播模型主要提出了各向异性(Anisotropy)、连续变异和不均匀等3个无线信号的主要特征。

1.2.1 Logarithmic Attenuation模型

Logarithmic Attenuation模型在仿真实验中常用来产生接收信号强度的值，是一典型不规则通信模型，表达式如下

Logarithmic Attenuation模型中PR(d)为是距离发送节点d m的位置接收到的信号强度，PR(d)是距离发送节点d m的位置接收到的信号强度的均值，Xσ·N(0，δ2)是信号强度的衰减部分，它是一个服从标准正态分布的随机变量。

1.2.2 DOI模型

为表示无线模型的不规则程度，T.He等人引入了参数 DOI［4］(Degree of Irregularity)定义为在无线通信中单位方向上最大路径损耗的百分比变化程度，如图1所示。在此基础上提出DOI模型，DOI模型表达式如式(4)所示。

当DOI=0时，通信范围没有变化，图形是圆形的，相当于规则的传播模型。随着DOI值的增大，通信范围也变得越来越不规律，所以不规则传播模型是一个通用的无线传播模型。当DOI=0时，DOI模型就变成了规则模型。

图1 Degree of Irregularity

1.2.3 RIM模型

Zhou等人在 DOI模型的基础上［5］，通过基于MICA2节点的实际测量研究，提出了一种更为精确的RIM(Radio Irregularity Model)模型。表达式如下

其中，Ki为不同传播方向上的路径损耗协同系数，计算公式为

这样就可以算出360°方向上的不同Ki值，但有的起始方向上的角度不是整数，插入的Ki是基于在起始方向上相邻角度上的整数角度。

2 APIT定位算法

2.1 算法简介

近似三角形内点测试(Approximate Point－In－Triangulation Test，APIT)算法［4，6］是一种非测距定位算法，其基本思想是利用由锚节点(信标节点)形成的三角形覆盖区域来确定未知点的位置。利用无线信号的传播特性来判断是否远离或靠近锚节点，通常在给定方向上，一个节点距离另一个节点越远，接收到的信号就越弱。邻居节点通过交换各自接收到信号的强度，判断距离某一信标节点的远近，从而模仿PIT中节点移动。

APIT理论:如果M节点不存在同时远离或接近于A，B，C的邻居节点，则判定M位于△ABC内部，否则的话，判定M位于△ABC外部。

2.2 APIT步骤

APIT 定位具体步骤:收集信息:未知节点收集邻居锚节点的信息，如位置、标识号、接收到的信号强度等，邻居节点之间交换各自接收到的信标节点的信息;APIT:测试未知节点是否在不同信标节点组成的三角形内部;计算重叠区域:统计包含未知节点的三角形，计算所有三角形的重叠区域;计算未知节点位置:计算重叠区域的质心位置，作为未知节点的位置。图2是APIT节点定位算法流程图［7］。

3 APIT算法通过不同传播模型性能仿真

在Matlab平台上对APIT算法在4个传播模型中的情况进行仿真研究，对其性能进行了对比。场景设置:仿真条件采用随机产生的拓扑场景，节点数为400，节点分布在1 200 m×1 200 m的二维区域内，其中80个锚节点，未知节点与锚节点的通信半径皆为200 m。通过APIT算法在Matlab平台上的仿真分析，4种模型下的定位误差情况，分别如图3～图6所示。图中，“*”表示锚节点，“O”表示未知节点的估计位置，“O”表示不能被定位的未知节点，“—”表示未知节点的定位误差。

图5 DOI通信模型定位误差图

图6 RIM通信模型定位误差图

图3～图6中的网络网络的平均连通度、网络的邻居锚节点平均数目、不能被定位的未知节点数、定位误差等定位性能数值比较如表1所示。通过表1可大致分析出APIT算法在不同通信模型中的定位性能。

表1 APIT算法在4种通信模型中的定位性能比较

4 结束语

介绍了4种传播模型和APIT算法后，对APIT算法在不同的传播模型中的定位误差进行了仿真。在仿真实验中，接收信号的强度是根据某个通信模型的公式将距离转换为信号强度得出的，因此在试验中采用不同的通信模型，相同的距离得出的信号强度不同。通过图3～图6以及表1可见，虽然APIT算法被认为是一种脱离理想规则的无线信号传输模型假设的实用算法，但在 T.He 等人［4］，Zhou 等人［5］提出的 DOI以及RIM通信模型下，对APIT算法性能仿真分析发现，尤其是在不规则的通信模型下，算法性能会受到严重影响，定位误差以及网络连通度也保持增长态势。为设计者在无线传感器网络实际应用过程中，根据不同应用场景选用适当模型提供了理论依据。

［1］AKYILDIZ I F，SU W，SANKARA S，et al.A survey on sensor networks［J］.IEEE Communications Magazine，2002，40(8):102－114.

［2］王福豹，史龙，任丰原.无线传感器网络中的自身定位系统和算法［J］.软件学报，2005，16(5):857－868.

［3］董振中.无线传感器网络无需测距的高效定位算法的研究［D］.合肥:中国科学技术大学，2010.

［4］HE T，HUANG C，BLUM B M，et al.Range － free localization schemes for large scale sensor networks［C］.San Diego，CA:in Proc.ACM Int.Conf.Mobile Computing etworking(MOBICOM)，2003:81 －95.

［5］ZHOU G，HE T，KRISHNAMURTHY S，et al.Models and solutions for radio irregularity in wireless sensor networks［J］.ACM Transactions on Sensor Networks，2006，2(2):221 －226.

［6］ZHOU G，HE T，KRISHNAMURTHY S，et al.Impact of radio irregularity on wireless sensor networks［C］.In Proceedings of the 2nd International Conference on Mobile Systems，Applications，and Services，ACM Press，2004:125 －138.

［7］中国矿业大学.改进APIT节点定位系统软件V1.0软件文档［D］.北京:中国矿业大学，2011.