二次栅格扫描的无线传感器网络定位算法

无线传感器网络是由大量的具有信息感知功能的传感节点通过无线通信方式形成一个多跳的自组织网络系统[1]。位置是判断人或物体所处情形和环境的直接依据[2]，在无线传感器网络中利用节点发送与接收无线信号确定物体的位置称为无线传感器网络节点定位[3]。根据定位机制，可将现有的定位算法分为两类[4]：基于测距(Range-based)的定位算法和无需测距(Range-free)的定位算法[5]。Range-based的定位对网络的硬件设施提出了较高的要求，各种测量技术也存在各自的局限性[6]。此外，Range-based的定位经常采用多次测量, 循环求精[7],这些都将产生大量计算和通信开销[8]，因而基于测距定位算法并不适用于低功耗、低成本的应用领域[9]。与Range-based机制相比，Range-free定位机制对硬件的要求较低，因此，成本和功耗较低，且网络生存能力强[10]，定位精度基本满足实际需要，是目前研究工作的重点之一[11]。文中将栅格扫描定位算法得到的位置坐标作为初始位置估计，在此基础上提出了一种改进的Range-free定位算法，减小了平均相对定位误差。

Grid-Scan算法是在APIT算法中提出的一种典型的无需测距的定位算法[12]，文献[13]提出的VGrid-Scan算法主要通过改变锚节点的通信半径，但不影响未知节点搜索邻居锚节点，从而缩小未知节点的定位区域，该方法在一定程度上提高了定位精度。

Grid-Scan算法分为3个步骤[15]：

第一步：网络部署，待定位的未知节点搜索其通信范围内所有锚节点，并记录被搜索到的锚节点的ID和坐标信息，这些被搜索到的锚节点称为邻居锚节点。

第二步：将未知节点Uj所有邻居锚节点的通信圆交集以其外接矩形代替，得到外接估计矩形ER (Estimative Rectangle)[14]。如图1所示，ER的四条边分别平行于x轴和y轴。ER的大小由式(1)确定。

图1   外接估计矩形示意图

(lx，ly)为未知节点所属的ER大小，i为锚节点下标，(xi，yi)为锚节点的位置坐标，r为锚节点的通信半径。

第三步：划分栅格并计算未知节点的坐标。设栅格的边长为l，ER的长为 L×l，宽为 W×l，则ER可表示为L×W个栅格的集合G。

将网络中所有栅格的初始值赋为0，Cm为栅格的中心，若ER内栅格Gm和Cm均位于n个邻居锚节点的通信范围内，则将栅格Gm赋值为n。ER内赋值最大的所有栅格组成的区域对应为一个未知节点的估计区域Ej，如图2所示赋值最大的栅格组成的区域即为估计区域Ej，最后，计算该估计区域Ej的质心位置，实现对未知节点的定位。

图2   ER内栅格赋值

文中通过对Grid-Scan定位算法的研究发现，该算法允许未知节点只存在一个邻居锚节点的情况下进行定位，且在随机产生的网络拓扑中，未知节点的实际位置可能位于以估计位置到邻居锚节点的距离为半径的圆内，这样的未知节点存在着可再定位性，对这些有可再定位性的未知节点，文中利用Grid-Scan算法允许一个锚节点定位的特点，采用最近锚节点对具有可再定位性的未知节点进行二次定位，提高定位精度。

首先由邻居锚节点的位置信息可以得到未知节点的初始位置估计，然后利用邻居锚节点坐标信息与初始位置估计的坐标信息得到未知节点更小更精确的位置估计区域，最后进行二次求精。改进算法具体分为3个阶段。

(1)初始位置估计

设未知节点的邻居锚节点个数为n，利用传统的Grid-Scan算法对某未知节点进行定位，得到未知节点的初始位置估计坐标(xe，ye)，此时对应该未知节点ER区域内的栅格已被赋值完成，得到Ej区域所有被赋值为n的栅格Grid。

(2)判断可再定位性

求出所有邻居锚节点到该未知节点的信号强度，设未知节点接收到所有邻居锚节点的信号强度为RSS，而RSS中的最大信号强度RSSu对应的锚节点即为最近锚节点。由式(3)计算初始位置估计到最近锚节点的距离dist。

(xe，ye)为初始位置估计坐标，(xist，yist)为最近锚节点坐标，将dist代入 (4)可得初始位置到最近锚节点的理论信号强度RSSe。

其中，PT为发送信号功率；PL(d0)为参考距离d0的路径损耗功率；η为路径损耗指数。当RSSu>RSSe时，判定未知节点存在可再定位性；当RSSu≤RSSe时，判定未知节点不可再定位，该未知节点最终定位的位置即为初始位置估计。

(3)栅格二次赋值

对可再定位的未知节点进行二次栅格扫描。计算Ej区域内所有栅格的Cm到最近锚节点的距离D。

当dm>dist时，dm对应在Grid内的值不变；当dm < dist时，dm对应在Grid内的栅格值为n+1，赋值为n+1的栅格集合为Gridmap；由Gridmap产生一个新的估计区域ENj，计算ENj的质心位置得到最终定位的位置。

如图2所示，设未知节点有三个邻居锚节点A1，A2，A3相交区域为Ej，A1为最近锚节点，在Ej区域内得到未知节点的初始位置估计，得到Ej区域内栅格赋值为3的Grid，以初始位置到A1的距离dist为半径对Ej区域进行栅格扫描得到估计区域ENj，ENj区域内栅格值在Grid基础上加1，得到ENj区域所有被赋值为4的栅格集合Gridmap，计算最终定位坐标。

图3   二次栅格扫描示意图

文中实验在Matlab平台上进行，设节点个为N，并在100×100m监测区域内产生随机的拓扑场景，节点通信半径为r，栅格边长为l，节点发送信号功率PT=0dB，参考距离d0=1m，参考距离d0的路径损耗功率PL(d0)=55dB，路径损耗指数η=4。将文中改进算法记为SGrid-Scan算法，并与传统的Grid-Scan算法及文献[13]中的VGrid-Scan算法在归一化的平均相对定位误差上进行对比。其中，VGrid-Scan算法依然采用文献[13]中锚节点通信半径的设定方法，设置为节点通信半径的0.7倍。

网络中每个可定位节点的误差为：

其中：(xes，yes) 为未知节点最终的估计坐标，(xtr，ytr)为未知节点的实际坐标，r为节点的通信半径。网络中所有未知节点的归一化的平均相对定位误差为:

其中：文中实验设k=100，即产生100个随机网络拓扑，nr为可定位的节点个数。

为了使两种算法的仿真误差更具对比性，将每次产生的随机网络拓扑场景分别提供给SGrid-Scan算法、Grid-Scan算法和VGrid-Scan算法进行仿真，确保三种算法在相同环境下进行定位误差的计算，增加实验数据对比的可靠性。

通过式(1)可以发现，节点的通信半径可以影响未知节点的外接矩形的大小，进而影响邻居锚节点个数。设节点个数N=200，锚节点个数为40，栅格边长l=2m。

图4   通信半径对算法定位误差的影响               如图6所示，栅格边长越小，三种算法的定位误差越低，且SGrid-Scan算法的定位误差较Grid-Scan算法平均减小了2.37%；SGrid-Scan算法较VGrid-Scan算法的定位精度平均提高了1.15%；随着栅格边长的增大，三种算法的定位误差就越接近，但SGrid-Scan算法的定位误差始终最低。

锚节点密度影响邻居锚节点个数，邻居锚节点个数可以影响估计区域Ej的大小。在固定区域内。设节点个数N=200，节点通信半径r=20m，栅格边长l=2m。

图5   锚节点个数对算法定位误差的影响

如图5所示，三种算法的定位误差均随锚节点个数增加而逐步减小。SGrid-Scan算法的定位误差较Grid-Scan算法平均减小了3.92%；SGrid-Scan算法较VGrid-Scan算法的定位精度平均提高了1.77%。

节点总数是衡量网络密集度的一个重要参数，因此仿真了节点总数对两种算法定位性能的影响。设节点通信半径r=20m，锚节点个数为0.2N，栅格边长l=2m。

图6   节点个数对算法定位误差的影响

如图6所示，随着节点个数的增多，网络密集度随之变大，三种算法的定位误差均随之减小。SGrid-Scan算法较传统Grid-Scan算法的定位误差平均减小了4.11%。当节点个数N=150时，两种算法定位精度的差值最大，为5.12%；SGrid-Scan算法较VGrid-Scan算法的定位精度平均提高了1.45%。

由Grid-Scan算法的定位原理可知，栅格的边长会对估计区域Ej边缘的栅格数量产生影响，从而影响Ej质心的位置。设节点个数N=200，锚节点个数为40，节点的通信半径r=20m。

图7   栅格边长对算法定位误差的影响

如图6所示，栅格边长越小，三种算法的定位误差越低，且SGrid-Scan算法的定位误差较Grid-Scan算法平均减小了2.37%；SGrid-Scan算法较VGrid-Scan算法的定位精度平均提高了1.15%；随着栅格边长的增大，三种算法的定位误差就越接近，但SGrid-Scan算法的定位误差始终最低。

结束语文中首先采用传统的Grid-Scan算法得到一个初始位置估计，然后通过对初始位置估计到最近锚节点位置的理论信号强度与未知节点到最近锚节点的信号强度进行对比，判断未知节点的可再定位性，再以最近锚节点到初始位置的距离为半径对可再定位的未知节点进行二次栅格扫描，从而进一步缩小了未知节点的定位区域，一定程度上提高了定位精度。仿真结果表明，在变通信半径、变锚节点个数、变节点个数和变栅格边长的条件下，改进算法均有效降低了平均相对定位误差。

完整的Word格式文档51黑下载地址：
二次栅格扫描的无线传感器网络定位算法.docx (265.47 KB, 下载次数: 6)

2018-6-4 15:12 上传

点击文件名下载附件
定位算法.pdf
下载积分: 黑币 -5