无线传感网络节点定位技术

杨 鹃，韩雪松

(承德石油高等专科学校计算机与信息工程系，河北承德 067000)

1 无线网络

网络体系主要由四部分构成，分别为传感节点、汇聚节点、通讯方式和数据终端。

传感节点由多个微型传感器节点构成，负责对本地信息进行采集，相互间采用无线、多跳、自组织的的网络连接方式。汇聚节点也被称为sink节点，主要负责采集传感节点信息、发布执行命令给本地。通信方式采用低功耗短距离的无线通信技术，目前采用的技术大多为IEEE802.15.4(zigbee技术)、Wi-Fi、蓝牙、UWB、3G、CDMA等，不同的应用需求可采用不同的通信技术。

传感节点中的未知节点的位置确定就是节点定位。目前采用的方法大多数是依靠锚节点的坐标来确定，锚节点的多少和分布情况影响着定位精度。节点定位按照锚节点的形式可分为静态定位技术和动态定位技术。静态定位技术将锚节点的位置固定，未知节点根据与锚节点的通信确定位置，该技术如果按照是否基于测距技术还可将其分为基于测距技术的定位和与距离无关的定位技术。动态定位技术中锚节点可以移动并周期性的发送自身位置信息给周围的未知节点，锚节点的数量要求比静态定位技术需要的少，减少了系统的成本，但是锚节点的移动需要按照算法首先进行路径规划，否则会在定位时间和节点功耗上浪费过多。本文主要研究基于节点静态定位技术的应用和发展。

2 常用的定位技术

2.1 基于测距技术的定位算法

在无线传感器网络中，基于测距的定位技术由测距和节点定位两部分组成。该方法首先测量节点间的角度或距离，然后再通过节点定位算法实现节点定位。

2.1.1 测距技术

测距技术主要有 RSSI、TDOA、AOA、TOA。

TDOA(time difference on arrival):系统应安装超声波收发器和RF收发器，测距时，同时发射信号，在接收端通过记录两种不同信号到达时间的差异，基于已知信号传播速度，直接把时间转化为距离。缺点是超声波距离有限或是NLOS问题对超声波信号的传播影响。

AOA(angle of arrival):通过天线阵列或是多个超声波接收器阵列来实现定位，除定位外还可进行角度估计。使用上要受到噪声和NLOS问题的影响，且需要额外硬件，可能无法满足传感器节点对硬件尺寸和功耗的要求。

TOA(time of arrival):利用测量信号传播时间来测量距离，网络系统需要利用GPS和高精度的电子设备来准确同步卫星时钟，故应用起来有一定的限制。

2.1.2 节点定位计算方法

三边算法:未知节点与至少三个以上的锚节点之间能够实现数据通信，通过检测未知节点到三个锚节点之间的距离，建立方程组，求解。

三角测量法:首先未知节点的接收器天线检测锚节点发射电波的入射角，从而求得未知节点与该锚节点的方向线。两个锚节点与未知节点的方向线的交点就是未知节点的估计位置。位置估计计算时，至少需要三个以上的锚节点与未知节点存在通信，假设有三个锚节点A、B、C，未知节点为D，则首先计算经过锚节点A、B、D的圆的半径和圆心位置，可根据锚节点A和B的位置和计算求得，以此方法依次求取A、C和与B、C和所构成的圆，最后采用三边测量法即可求得位置节点的坐标。

极大似然估计:该方法在至少有三个以上的锚节点的情况下使用。根据锚节点的位置和未知节点到锚节点的距离建立方程组，并使用最小方差估计求得未知节点的坐标。

2.1.3 目前基于测距技术的应用

孙懋珩等［1］提出采用RSSI检测未知节点与锚节点的距离，再用粒子群算法计算未知节点的估计坐标。粒子群算法在定位精度、算法收敛性、算法复杂度等方面比遗传算法和模拟退火算法更适用于需要低功耗、少计算量的无线网络定位中，但算法在仿真过程中存在容易陷入局部最优化的问题，未来使用该方法进行应用时应将研究放在如何摆脱局部最优化的问题上。

在TDOA定位的环境中，张宏君等［2］提出采用基于残差加权算法得出需要定位节点的初始值，再采用牛顿迭代定位算法进行精确定位，该方法解决了牛顿迭代算法可能存在的不收敛的问题，减少了节点计算量。

在AOA/TOA系统中，为提高定位精度，陈奎［3］等提出采用MPM方法对信道频率响应进行时延估计，然后天线接收信号的频域阵列信号进行AOA估计，根据估计的结果在二维平面内确定目标的位置。

为降低了定位误差，刘超［4］等研究由于天线发射角度的影响导致RSSI定位方法出现误差的问题，采用规划好的锚节点对未知节点进行未知估计，根据得到的天线的角度，补偿修正RSSI的值。

为提高定位精度，王伟［5］等提出在RSSI定位的节点定位系统中，采用最小均方差误差估计求解路径损耗指数及方差，并校正节点位置估计，在校正过程中，设定各个锚节点对未知节点的位置校正不相关，将所有参考节点的校正坐标的几何质心作为未知节点的校正位置。该方法在适当增加系统计算量的前提下，实现了精度的提高。

2.2 与距离无关的定位算法

2.2.1 DV-hop 算法［6］

DV-hop算法适用于各向同性的密集网络，该算法将未知节点到锚节点之间的距离用网络平均每跳距离和两者之间的跳数乘积表示。它采用较少的锚节点，并且不需要节点具备测距能力，计算和通信要求适中，定位精度较高。该算法执行时，如果节点间距离与平均每跳距离大致相近时才有较好的效果，实际情况往往不能满足，导致了误差的出现，并且当锚节点距离未知节点距离较远时，节点间的跳数较多，并且由于每跳距离误差的存在，导致距离误差也越大。

针对于本算法的改进研究，近年来也取得了一定的成果。申铉京［7］等将每个未知节点设定一个门限阈值，确定锚节点的位置信息和平均每跳的距离，未知节点选择最先接收的N个锚节点信息，用最小二乘法求取未知节点的坐标，该算法内存占用率低，且处理效率高。

郑君刚［8］等提出了采用二维空间的Cayley-Menger行列式提供的几何约束对未知节点到锚节点的距离进行优化修正，实验验证该方法有效减少了测量过程中出现的误差大小，提高了定位精度。

2.2.2 蒙特卡罗［9］定位算法

适用于移动传感器网络节点定位，系统中不设置锚节点，利用一系列加权采样值表示可能位置的后验概率分布，成本较低。在这个定位方法中，动态节点较静态节点在运动过程中能获得更多的信息，与传统定位算法相比，在移动状态下定位精度更高。但该算法的缺点在于:1)为获取有效样本，抽样次数过多，且容易出现粒子退化现象;2)部分位置估计值精度较高的待定节点并未有效利用，可以对这些节点用其它算法辅助定位其它节点。

W.Wang［10］等提出未知网络节点位置信息无需掌握的情况下，基于概率统计方法，采用序列蒙特卡罗定位方法，实现了用较少的导标对节点准确定位。

J.Sheu［11］等提出一种改进的蒙特卡罗算法，该算法中首先导标信息由未知节点接收，并根据一跳范围内已定位的未知节点的估计位置信息，预测节点的移动方向完成定位。

2.2.3 MDS-MAP［12］(MultiDimensional scaling MAP)定位算法

MDS-MAP是一种集中式定位算法，可在Range-Based和Range-Free两种方式下根据网络配置分别实现相对和绝对定位。该算法首先生成全局网络拓扑连通图，如果节点有测距能力，测距结果就是节点间拓扑图边线的距离值。如果节点间无须测距，只是节点间连通，则拓扑图边线长度赋值为1。根据生成的网络拓扑连通图，使用最短路径算法，生成节点间矩阵。根据节点间矩阵，应用MDS技术，生成多维相对坐标系统。如果锚节点足够多，再通过数据处理将其转换为绝对坐标系统。该算法系统无需设置锚节点，当网络的节点密度小时，定位误差大，因而使用与适用于节点密度大的网络环境。可能存在的问题是网络需要集中计算，部分节点能耗过大可能节点失效。

为提高定位精度，陈岁生［13］等在基于测距的MDS-MAP算法定位的基础上，应用扩展卡尔曼滤波和不敏卡尔曼滤波这两种非线性滤波算法对MDS-MAP的结果修正。该方法的缺点是加大了系统的计算量，系统能耗过大。

为减少节点能耗，马震［14］等将传感网络划分成多个具有簇首的局部网络。局部网络采用MDSMAP算法实现定位后，再通过网络融合算法将局部相对坐标图合并成全局绝对坐标图。该算法有效降低了系统的计算量，减少了节点能耗，但是在定位精度方面没有较大提高。

2.2.4 APIT［15］(Approximate point-in-triangulationtest)定位算法

APIT算法是针对WSN异构网络的定位算法，网络结构中锚节点和网络其他的未知节点通信半径不同，锚节点通信半径比未知节点的大。其主要思想是:首先未知节点收集所有邻近信标节点的信息，并通过测试求得未知节点是否位于不同的三个信标节点组成的三角形内，计算出所有符合上述条件的三角形的集合，取所有三角形公共区域的质心作为估计位置。相对于质心定位算法，APIT定位精度高，对信标节点的分布要求较低，但对网络的连通性有较高的要求，且所需的锚节点密度最大。该算法的不足在于定位覆盖率较DV-hop算法低，无法定位的节点率较高，其主要原因在于无法定位的节点邻居锚节点数量不足3个，或是未知节点在邻居锚节点构成的三角形的外部。

马刚等［16］提出将min-max算法应用到APIT定位算法中，如果符合APIT算法执行的条件，就执行传统的APIT算法，否则就执行MIN-MAX算法。该方法解决了APIT算法定位率低的问题，但是提高了通信费用，后期研究应放在如何降低定位开销上。

2.2.5 质心定位算法

基于网络的连通性进行定位的算法。未知节点至少与三个以上的锚节点实现通信。其中网络连通的每三个锚节点构成一个三角形，三角形的质心就是未知节点的估计值。锚节点的分布和密度对于节点定位有很大的影响，并且当未知节点位于靠近三角形某条边线时，容易造成测量错误，因而，人们又提出了质心算法的加权算法，即解决了检测错误的问题，也提高了锚节点对于未知节点的影响问题，锚节点越靠近未知节点，对于未知节点的位置估计影响越大。质心算法计算简单，但是精度较低，受环境影响较小，适合于复杂环境的定位计算。许多定位工作集中在如何提高质心算法的定位精度上。王琰琳［17］等提出将遗传算法用于对改进质心定位算法的权值加以修正，通过仿真验证了该方法能有效提高定位精度。

3 无线网络现有定位算法存在的问题

1)基于距离定位的算法大多需要硬件的支持。例如基于TOA定位的算法需要利用天线阵列或是多个超声波接收器阵列通信，提高了无线网络系统的价格。

2)与距离无关的定位算法大多要求锚节点密度，增加了系统的成本。如果采用移动锚节点，可有效解决密度问题，降低了价格，但是附加的问题是如何对移动节点进行路径规划以提高定位精度，这是目前的研究热点之一。

3)节点定位按照数据处理的方式分为集中式和分布式。集中式处理数据的方式是将传感节点收集到的信息汇聚到汇聚节点进行处理，需要大量的通信和计算开销，适用于静态节点定位。分布式的处理方式目前应用较多的是将网络划分出簇，簇内节点间经过信息融合后再传递给汇聚节点，这样减少了节点间的数据通信和能量损耗，适用于有实时性要求的移动节点定位。

4)靠近基站节点计算量过大，消耗了网络的大部分能量，容易造成网络不通。

5)很多定位算法不具有容错性和可扩展性。

4 结论

本文对现有的无线传感网络定位算法进行了对比分析，从中可以看出测距技术依赖硬件支持，研究的重点是低成本和低功耗的算法;而与距离无关的定位算法依赖于网络部署，因此研究趋势集中在低节点密度、低功耗和低复杂度的算法。目前，面对各种算法的各自优缺点，合理有效的选择适合于无线网络应用的定位算法是非常重要的。根据系统的环境状况和精度需求，设定合理的定位方法，也是研究的重点内容之一。

［1］孙懋珩，廖根健.基于最优锚WSNs中基于粒子群优化的节点定位算法［J］.测控技术，2011，30(12):111－117.

［2］张宏君，毛永毅.改进的无线传感器网络节点定位算法［J］.计算机应用，2012，32(8):2103－2105.

［3］陈奎，黄为勇，田传耕.基于Matrix Pencil的OFDM信号的TOA/AOA定位［J］.计算机应用研究，2013，30(2):534－540.

［4］刘超，王敬东，李鹏.考虑天线角度的无线传感器网络节点定位方法［J］.电子科技，2010，23(8):90－95.

［5］王伟，陈岱，周勇.基于测距修正和位置校正的RSSI定位算法［J］.计算机工程与设计，2011，32(2):409－415.

［6］Niculescu D，Nath B.DV based positioning in ad hoc networks［J］.Journal ofTelecommunication Systems，2003，22(1/4):267－280.

［7］申铉京，李成岳，王硕，等.基于最优锚节点的无线传感器网络节点定位算法［J］.吉林大学学报(工学版)，2011，41(1):208－211.

［8］郑君刚，吴成东，楚好，等.基于DV-Hop和距离几何约束的定位算法［J］.东北大学学报(自然科学版)，2011，32(4):457－462.

［9］HU L X，DAVID E.Localization for mobile sensor networks［A］.Proceedings of the 10th Annual International Conference on Mobile Computing and Networking［C］.2004，45 －47.

［10］Wang W D.Zhu Q X.sequential monte carlo localizartion in mobile sensor networks［J］.wireless networks，2009，15(4):481－495.

［11］Sheu J P，Hu W K，Lin J c.Distributed lovalization scheme for mobile sensor networks［J］.IEEE Transaction on mobile computing，2010，9(4):516 －525.

［12］黄书广.无线传感器网络定位算法研究［D］.北京邮电大学硕士论文，2011.

［13］陈岁生，卢建刚，楼晓春.基于MDS-MAP和非线性滤波的WSN定位算法［J］.浙江大学学报(工学版)，2012，46(5):866－872.

［14］马震，刘云，沈波.基分布式无线传感器网络定位算法MDS-MAP［J］.通信学报，2008，29(6):57－62.

［15］甘文杰.无线传感器网络节点定位算法研究及软件实现［D］.北京邮电大学硕士论文，2012.

［16］马刚，陈盛云.WSN中APIT节点定位改进算法研究［J］.微处理机，2011(3):68－72.

［17］王琰琳，黄友锐，曲立国.改进型质心算法在井下人员定位中的应用［J］.煤矿机械，2012，33(8):76－79.