论文部分内容阅读
摘 要：本文基于WSN的典型Range-based定位算法RSSI的特点，引入Range-free中APIT定位算法寻找重叠区域的思想，提出了对RSSI定位算法的改进方案。
关键词：定位；APIT；RSSI
1 概述
无线传感器网络（Wireless Sensor Networks，WSN） [1]是由部署在监测区域内的大量微型移动传感器节点组成、通过无线通信方式形成的一个多跳自组织网络系统，广泛应用在军事、医疗、交通和环境监测等领域。
定位，就是确定目标的位置信息。对于WSN的应用，不知道传感器位置而感知的数据是没有意义的。传感器节点必须明确自身位置才能详细说明“在什么位置或区域发生了特定事件”，实现对外部目标的定位和追踪。而人工部署和为所有网络节点安装GPS 接收器都会受到成本、功耗、扩展性等问题的限制，因此必须采用一定的机制与算法实现WSN 的自身定位。
2 无线传感器网络节点定位算法
WSN已经发展了很多定位算法，不同算法有各自的侧重点，对于网络拓扑结构、节点密度、能量消耗、定位精度等方面有不同的要求和表现。按照定位算法是否需要距离信息，可分为基于测距（Range-based）和非基于测距（Range-free）的定位。基于测距的定位有RSSI，TOA和TDOA测距法。非基于测距的定位有质心算法、DV-Hop算法和APIT算法等。本文对RSSI定位算法进行讨论。
3 RSSI测距算法的改进
3.1 RSSI测距算法
RSSI测距算法[2]的原理是，已知发射节点的发射信号强度，接收节点根据接收到的信号强度，计算出信号的传播损耗，利用无线电传播理论和经验模型将传播损耗转化为距离。符合低功率、低成本的要求，但在实际应用中测距误差较大。RSSI节点定位算法分为测距和定位两个阶段。
1. 测距阶段。使用无线电信号强度测量距离。对某一节点其电磁传输模型可用具有视距传输的对数距离路径损耗模型来描述，其大尺度传输模型如式（1）：
（1）
式中，只Pr（d）为距离发射点d米处的接收信号强度表达式，d0为接收功率的参考点，A0为该节点的发射功率，r为实际的路径损耗指数，r0为自由空间路径损耗指数， 为0均值的正态分布随机变量，标准偏差为 。由式（1）可推出d和E（d）。
2. 定位阶段。在WSN中大部分定位都可近似基于二维平面。在传感器网络所在平面建立直角坐标系，假设待测节点的坐标为（x，y），并且已知一组锚节点坐标为{（Xi，Yi）}，{di}，i =1，…，n，n为锚节点的总个数。待测节点接收到各锚节点的信号强度为。可分别计算出待测节点与各锚节点的期望距离。这样节点定位问题可以表述为：已知，，i=l，…，n，求（x，y）。根据平面内两点间距离公式，可以得到方程组求解。若要求锚节点的总数n>=3，就是过定义方程组，采用最小二乘法，即可解出待测节点的坐标。
3.2 APIT定位算法
近似三角形内点测试法（Approximate Point-in-triangulation Test，APIT），定位思想是：如图1所示，首先未知节点从它所有能够与之通信的锚节点中选择三个节点，测试它自身是在这三个锚节点所组成的三角形内部还是在其外部；然后再选择另外的三个锚节点进行同样的测试，直到穷尽所有的组合或达到定位精度；最后计算包含目标节点所有三角形的重叠区域，将重叠区域的质心作为未知节点的位置。
APIT测试误差概率相对较小，在无线信号传播不规则、节点随机布置的情况下，APIT算法的定位精度高，性能稳定。由于未知节点定位时需要反复的进行APIT测试，计算复杂度大。而且未知节点必须与锚节点相邻，该算法要求较高的锚节点密度。
3.3 RSSI定位算法的改进
对RSSI定位算法的改进是借鉴APIT定位算法寻找重叠区域的思想。改进算法的基本思想是：首先确定多个包含未知节点的三角形区域。通过RSSI测距方法得出未知节点与每个三角形的三个定点的近似距离，进一步采用三边测量法计算出未知节点的位置集。这个位置集将确定一个更小的包含未知节点的目标区域。因此，可将这个位置集的坐标均值作为未知节点的位置。
改进的RSSI定位算法的具体定位步骤如下：
1. 未知节点以广播形式向周围发送定位请求。
2. 锚节点回复自身信息，包括：节点编号、自身位置信息。
3. 未知节点在收到信息后，只记录从同一个锚节点接收到的无线信号强度（RSSI）大小的值。
4. 未知节点在收到超过m个锚节点信息后：
4.1 如果m<3，则利用RSSI测距算法中第一阶段的传播损耗模型来直接求解未知节点的位置；
4.2 如果m=3，则利用RSSI测距算法求解未知节点的位置；
4.3 如果m>3，对锚节点依其RSSI值从大到小排序（RSSI值越大，说明离该锚节点越近），并建立RSSI值与节点到锚节点距离的映射。
5. 采用RSSI值大的前几个锚节点进行自身定位计算：
5.1 在锚节点集合中依据前述对无线电传播路径损耗模型的分析结论，优先选择RSSI值大的锚节点组合成下面的三角形集合，这是提高定位精度的关键：
三角形集合：
{（A1，A2，A3），（A1，A2，A4），……，（A1，A3，A4），（A1，A3，A5）}
5.2 对三角形集合中任一个三角形，采用WSN的APIT算法判定未知节点是否在该三角形的内部，去除三角形集合中不包含未知节点的三角形。
5.3 对三角形集合中剩余的每个三角形（Aip，Ajp，Akp），采用三边测量法确定未知节点坐标（Xp，Yp），得到未知节点的坐标集。
5.4 对上一步所得近似位置的坐标集求均值，即得到未知節点的坐标。
4 小结
后续可使用OMNET++仿真工具来评价改进的RSSI定位算法的性能。该改进的RSSI定位算法，比单纯基于RSSI测距的定位具有更好的定位精度。特别是在锚节点相对密度较低时，仍具有较高的定位精度。虽然比RSSI定位的复杂度要高，但相对APIT算法来说仍具有较低的复杂度。
参考文献
[1] 王福豹，史龙，任丰原.无线传感器网络中的自身定位系统和算法[J].软件学报，2005，16（02），857-868.
[2] 马祖长， 孙怡宁. 无线传感器网络节点的定位算法[J].计算机工程，2004，30（07）：13-14，48.
关键词：定位；APIT；RSSI
1 概述
无线传感器网络（Wireless Sensor Networks，WSN） [1]是由部署在监测区域内的大量微型移动传感器节点组成、通过无线通信方式形成的一个多跳自组织网络系统，广泛应用在军事、医疗、交通和环境监测等领域。
定位，就是确定目标的位置信息。对于WSN的应用，不知道传感器位置而感知的数据是没有意义的。传感器节点必须明确自身位置才能详细说明“在什么位置或区域发生了特定事件”，实现对外部目标的定位和追踪。而人工部署和为所有网络节点安装GPS 接收器都会受到成本、功耗、扩展性等问题的限制，因此必须采用一定的机制与算法实现WSN 的自身定位。
2 无线传感器网络节点定位算法
WSN已经发展了很多定位算法，不同算法有各自的侧重点，对于网络拓扑结构、节点密度、能量消耗、定位精度等方面有不同的要求和表现。按照定位算法是否需要距离信息，可分为基于测距（Range-based）和非基于测距（Range-free）的定位。基于测距的定位有RSSI，TOA和TDOA测距法。非基于测距的定位有质心算法、DV-Hop算法和APIT算法等。本文对RSSI定位算法进行讨论。
3 RSSI测距算法的改进
3.1 RSSI测距算法
RSSI测距算法[2]的原理是，已知发射节点的发射信号强度，接收节点根据接收到的信号强度，计算出信号的传播损耗，利用无线电传播理论和经验模型将传播损耗转化为距离。符合低功率、低成本的要求，但在实际应用中测距误差较大。RSSI节点定位算法分为测距和定位两个阶段。
1. 测距阶段。使用无线电信号强度测量距离。对某一节点其电磁传输模型可用具有视距传输的对数距离路径损耗模型来描述，其大尺度传输模型如式（1）：
（1）
式中，只Pr（d）为距离发射点d米处的接收信号强度表达式，d0为接收功率的参考点，A0为该节点的发射功率，r为实际的路径损耗指数，r0为自由空间路径损耗指数， 为0均值的正态分布随机变量，标准偏差为 。由式（1）可推出d和E（d）。
2. 定位阶段。在WSN中大部分定位都可近似基于二维平面。在传感器网络所在平面建立直角坐标系，假设待测节点的坐标为（x，y），并且已知一组锚节点坐标为{（Xi，Yi）}，{di}，i =1，…，n，n为锚节点的总个数。待测节点接收到各锚节点的信号强度为。可分别计算出待测节点与各锚节点的期望距离。这样节点定位问题可以表述为：已知，，i=l，…，n，求（x，y）。根据平面内两点间距离公式，可以得到方程组求解。若要求锚节点的总数n>=3，就是过定义方程组，采用最小二乘法，即可解出待测节点的坐标。
3.2 APIT定位算法
近似三角形内点测试法（Approximate Point-in-triangulation Test，APIT），定位思想是：如图1所示，首先未知节点从它所有能够与之通信的锚节点中选择三个节点，测试它自身是在这三个锚节点所组成的三角形内部还是在其外部；然后再选择另外的三个锚节点进行同样的测试，直到穷尽所有的组合或达到定位精度；最后计算包含目标节点所有三角形的重叠区域，将重叠区域的质心作为未知节点的位置。
APIT测试误差概率相对较小，在无线信号传播不规则、节点随机布置的情况下，APIT算法的定位精度高，性能稳定。由于未知节点定位时需要反复的进行APIT测试，计算复杂度大。而且未知节点必须与锚节点相邻，该算法要求较高的锚节点密度。
3.3 RSSI定位算法的改进
对RSSI定位算法的改进是借鉴APIT定位算法寻找重叠区域的思想。改进算法的基本思想是：首先确定多个包含未知节点的三角形区域。通过RSSI测距方法得出未知节点与每个三角形的三个定点的近似距离，进一步采用三边测量法计算出未知节点的位置集。这个位置集将确定一个更小的包含未知节点的目标区域。因此，可将这个位置集的坐标均值作为未知节点的位置。
改进的RSSI定位算法的具体定位步骤如下：
1. 未知节点以广播形式向周围发送定位请求。
2. 锚节点回复自身信息，包括：节点编号、自身位置信息。
3. 未知节点在收到信息后，只记录从同一个锚节点接收到的无线信号强度（RSSI）大小的值。
4. 未知节点在收到超过m个锚节点信息后：
4.1 如果m<3，则利用RSSI测距算法中第一阶段的传播损耗模型来直接求解未知节点的位置；
4.2 如果m=3，则利用RSSI测距算法求解未知节点的位置；
4.3 如果m>3，对锚节点依其RSSI值从大到小排序（RSSI值越大，说明离该锚节点越近），并建立RSSI值与节点到锚节点距离的映射。
5. 采用RSSI值大的前几个锚节点进行自身定位计算：
5.1 在锚节点集合中依据前述对无线电传播路径损耗模型的分析结论，优先选择RSSI值大的锚节点组合成下面的三角形集合，这是提高定位精度的关键：
三角形集合：
{（A1，A2，A3），（A1，A2，A4），……，（A1，A3，A4），（A1，A3，A5）}
5.2 对三角形集合中任一个三角形，采用WSN的APIT算法判定未知节点是否在该三角形的内部，去除三角形集合中不包含未知节点的三角形。
5.3 对三角形集合中剩余的每个三角形（Aip，Ajp，Akp），采用三边测量法确定未知节点坐标（Xp，Yp），得到未知节点的坐标集。
5.4 对上一步所得近似位置的坐标集求均值，即得到未知節点的坐标。
4 小结
后续可使用OMNET++仿真工具来评价改进的RSSI定位算法的性能。该改进的RSSI定位算法，比单纯基于RSSI测距的定位具有更好的定位精度。特别是在锚节点相对密度较低时，仍具有较高的定位精度。虽然比RSSI定位的复杂度要高，但相对APIT算法来说仍具有较低的复杂度。
参考文献
[1] 王福豹，史龙，任丰原.无线传感器网络中的自身定位系统和算法[J].软件学报，2005，16（02），857-868.
[2] 马祖长， 孙怡宁. 无线传感器网络节点的定位算法[J].计算机工程，2004，30（07）：13-14，48.