论文部分内容阅读
摘要：节点定位技术是传感器网络关键技术之一，具有十分重要的地位。在对常用的节点定位算法进行分析比较的基础上，总结了现有定位算法存在成本和锚节点稀疏问题，并提出了利用移动锚节点来进行优化定位的方法，能够有效节约锚节点成本。
关键词：无线传感网络；节点定位；移动锚节点
无线传感器网络具有低功耗、低成本、自组织的能力， 能够自动进行配置和适应环境的变化， 具有动态可重构性等特点，能广泛应用于军事领域、精细农业、环境监测、智能家居、城市交通等方面。无线传感器网络节点定位技术，是无线传感器网络应用领域重要的共性支撑技术之一，对其研究具有非常重要的意义，无线网络的许多应用都与无线传感节点位置息息相关。传感器自身定位算法主要可以分为两类：基于测距的定位算法与非基于测距的定位算法。相比前者，后者由于具有成本和功耗等方面的优势，而成为业界研究热点。
1 节点定位算法
目前无线传感网络的节点定位算法有许多不同的分类的原则，如：基于有无锚点可以分为有锚点算法和无锚点算法；基于测距方式可以分为距离相关算法和距离无关算法；基于计算方式可以分为集中式算法和分布式算法；基于计算次数可以分为一次计算算法和循环求精算法。
1.1集中式算法和分布式算法
集中定位是指节点把定位所需信息传送到中心节点，在中心节点行节点位置计算；分布式定位通过节点问的信息交换和信标节点辅助的定位方式。分布式算法相对于集中式算法具有以下特点：自我组织能力强，不依赖于全局基施；健壮，能够容忍节点失效和测距误差；节能，只需要较少的计算和通信开销。因此分布式算法更适用于大规模的传感器网络。
1.2 距离相关算法和距离无关算法
距离相关算法通过测量节点之间的距离或角度信息，使用三边测量、三角测量或最大似然估计等定位算法计算节点位置。而无需测距定位算法则不需要距离和角度信息，算法根据网络的连通性等信息实现节点定位[1]。
1.2.1距离相关算法
此类定位算法分为两步：第一步测距，运用特定的测距技术测量未知节点与锚节点之间的距离；第二步计算，当未知节点获得的距离信息到达一个阀值时，使用三边测量法、三角测量法或最大似然估计法计算未知节点的位置。在距离无关定位算法中，测距的消耗在定位过程中占据了最大的比例，因此研究的重点是测距技术。
典型的测距方法有6种[2]：
（1）接收信号强度法（RSSI），将信号的传播损耗转化为距离；
（2）信号传输时间法（TOA），将电波的传输时间转化为距离，需要精确的时钟同步；
（3）信号往返时间差法（RTOF），通过计算往返时间、扣除处理时间的方法将时间转换为距离；
（4）信号到达时间差法（TDOA）将两种不同无线信号到达接收节点的时间差转化为距离，无需时钟同步；
（5）信号到达角法（AOA）通过antenna矩阵或多接收机感知发射节点信号的到达方向，计算接收节点和发射节点之间的相对方位或角度；
（6）信号到达相位差法（PDOA）利用传播往返时间粗估计距离，然后利用相位差精确估计距离。
测距精度和功耗成本是一对相互矛盾的性能指标，追求高精度的同时必然带来高的功耗和硬件成本。当精度要求高时，TODA和PDOA测距方法较优；当成本和功耗为主要考虑因素时，RSSI测距方法较优。距离相关定位方法能够实现精确定位，但对无线传感器节点的硬件、成本和功耗过要求高，而且在测量距离和角度的准确性方面也需要大量的研究。因此未来距离相关定位算法研究趋势是低成本、高能效、高精度的距离或角度测量技术。
1.2.2 距离无关定位算法
距离无关定位算法不需要使用测距技术，只利用连通情况来估测自己的位置。绝大多数距离无关定位算法采取分布式计算模式，因为其可扩展性好，每个节点的计算复杂度与网络的规模无关，计算简单而且容易实现，同时计算在节点进行，通信量小。
质心定位算法[3]：一个普通节点所有直接连通锚点组成的多边形的质心作为该节点的位置。质心算法的原理首先是确定包含未知节点的区域，计算这个区域的质心，并将其作为未知节点的位置。在这个算法中，信标节点周期性地向邻近节点广播信标分组。当未知节点接收到来自不同信标节点的信标分组数量超过某一个门限值k或接收一定时间后，就确定自身位置为这些信标节点所组成的多边形的质心。与未知节点处于邻近关系的所有锚节点，所组成的多边形区域的质心，作为未知节点的位置估计。
APIT算法[4]：与未知节点处于邻近关系的三个锚节点构成一个三角形，以多个这样的三角形的交叠区域的质心作为未知节点的位置。用该算法定位的具体步骤：（1）收集信息：未知节点收集邻近信标节点的信息，如位置、标识号、接收到的信号强度等，邻居节点之间交换各自接收到的信标节点的信息；（2）APIT测试：测试未知节点是否在不同的信标节点组合成的三角形内部；（3）计算重叠区域：统计包含未知节点的三角形，计算所有三角形的重叠区域；（4）计算未知节点位置：计算重叠区域的质心位置，作为未知节点的位置。
DV-Hop算法[5]由三个阶段组成。第一阶段，使用典型的距离矢量交换协议，使网络中所有未知节点获得距初始锚节点的跳数；第二阶段，在获得其他锚节点位置（ ， ）和相隔跳数后，各锚节点（ ， ）利用所收集的信息按式（1）计算平均跳距：
（1）
式中 是锚节点 的平均每跳距离， 为节点 和节点j之间的跳数；然后将平均每跳距离作为一个校正值广播至网络中，校正值采用可控洪泛法在网络中传播。第三阶段，在二维空间中，一旦一个未知节点获得与3个或更多锚节点的距离后，执行三边测量法或最大似然估计法计算自身的位置。
Amorphous算法与DV-Hop相似也有三个阶段，其中第一、第三阶段与DV-Hop算法相同，只是在第二阶Amorphous定位算法是假设段网络中节点的通信半径相同，平均每跳距离为节点的通信半径，未知节点计算到每个信标节点的跳段距离，误差比较大。该算法需要预知网络平均连通度，而且需要较高的节点密度。其相应的改进算法改进方向主要是重新计算平均每跳距离，或利用局部跳数的平均值代替总跳数，但是误差相较DV-Hop算法仍比较大。 2 移动锚节点的节点定位算法
从前面的分析可以看出成本和锚节点稀疏问题是目前定位算法最需要进一步解决的问题。如何以较少的成本获得较多的锚节点位置信息，同时处理锚节点稀疏问题是定位算法的一个重要的课题，有学者提出利用移动锚节点来进行定位。在这些方案中，一个移动锚节点在网络中移动并周期地发送含有锚节点位置信息的信标信号，未知节点接受这些信标信号并通过特定的算法估算自己的位置。其中利用RSSI测距技术进行定位的算法，信标信号中包含锚节点的位置信息和信号强度。利用TOA测距进行定位的算法，在发送信标的时候加入了时间信息，需要有较高的时间同步的要求。利用锚节点的移动性导致的信号到达时间差进行定位的算法。上述的3个方法都是利用的锚节点的移动性来节约锚节点成本，但是对未知节点的硬件成本和功耗的要求并未减少，因此低成本、高能效、高精度的距离或角度测量技术仍然是研究的重点。
3 结论
对现有常见的无线传感网络定位算法进行了对比分析，目前为止，各种定位算法都存在一定的技术缺陷，既便如此，这些已有的算法已经为无线传感技术的推广发展乃至整个人类社会的科技进步做出了不可磨灭的贡献。相信随着科学界对无线传感技术的更加深入、成熟的研究探索，人们一定会开发出技术更加全面的节点定位算法，为更多的行业发展带来活力。
项目基金：渭南师范学院研究生项目（11YKZ025）
参考文献：
[1] 孙利民，李建中，陈渝等.无线传感器网络[M].北京：清华大学出版社，2005.
[2] 王福豹，史龙，任丰原.无线传感网络中的自身定位系统和算法[J].软件学报，2005，16 （5）：858-868.
[3] 陈迅，唐红雨，涂时亮.无线传感器网络主动分布节点定位算法[J].计算机工程与设计， 2008，29（7）：1664-1667.
[4] 刘锋，张翰，杨骥 一种基于加权处理的无线传感器网络平均跳距离估计算法[J].电子与信息学报，2008，35（5）：1221-1224
[5] 姚忠孝，俞立，董齐芬.基于移动信标的 DV-hop无线传感网络定位算法[J].传感技术学报， 2009，22（10）：1504-1507.
作者简介：陈炜（1984-），女，河南淮阳人，2010年毕业于中国矿业大学（北京），硕士，渭南师范学院物理与电气工程学院助教，研究方向无线传感器网络及应用。电话：18700361080，邮箱：cwei62213891@163.com
关键词：无线传感网络；节点定位；移动锚节点
无线传感器网络具有低功耗、低成本、自组织的能力， 能够自动进行配置和适应环境的变化， 具有动态可重构性等特点，能广泛应用于军事领域、精细农业、环境监测、智能家居、城市交通等方面。无线传感器网络节点定位技术，是无线传感器网络应用领域重要的共性支撑技术之一，对其研究具有非常重要的意义，无线网络的许多应用都与无线传感节点位置息息相关。传感器自身定位算法主要可以分为两类：基于测距的定位算法与非基于测距的定位算法。相比前者，后者由于具有成本和功耗等方面的优势，而成为业界研究热点。
1 节点定位算法
目前无线传感网络的节点定位算法有许多不同的分类的原则，如：基于有无锚点可以分为有锚点算法和无锚点算法；基于测距方式可以分为距离相关算法和距离无关算法；基于计算方式可以分为集中式算法和分布式算法；基于计算次数可以分为一次计算算法和循环求精算法。
1.1集中式算法和分布式算法
集中定位是指节点把定位所需信息传送到中心节点，在中心节点行节点位置计算；分布式定位通过节点问的信息交换和信标节点辅助的定位方式。分布式算法相对于集中式算法具有以下特点：自我组织能力强，不依赖于全局基施；健壮，能够容忍节点失效和测距误差；节能，只需要较少的计算和通信开销。因此分布式算法更适用于大规模的传感器网络。
1.2 距离相关算法和距离无关算法
距离相关算法通过测量节点之间的距离或角度信息，使用三边测量、三角测量或最大似然估计等定位算法计算节点位置。而无需测距定位算法则不需要距离和角度信息，算法根据网络的连通性等信息实现节点定位[1]。
1.2.1距离相关算法
此类定位算法分为两步：第一步测距，运用特定的测距技术测量未知节点与锚节点之间的距离；第二步计算，当未知节点获得的距离信息到达一个阀值时，使用三边测量法、三角测量法或最大似然估计法计算未知节点的位置。在距离无关定位算法中，测距的消耗在定位过程中占据了最大的比例，因此研究的重点是测距技术。
典型的测距方法有6种[2]：
（1）接收信号强度法（RSSI），将信号的传播损耗转化为距离；
（2）信号传输时间法（TOA），将电波的传输时间转化为距离，需要精确的时钟同步；
（3）信号往返时间差法（RTOF），通过计算往返时间、扣除处理时间的方法将时间转换为距离；
（4）信号到达时间差法（TDOA）将两种不同无线信号到达接收节点的时间差转化为距离，无需时钟同步；
（5）信号到达角法（AOA）通过antenna矩阵或多接收机感知发射节点信号的到达方向，计算接收节点和发射节点之间的相对方位或角度；
（6）信号到达相位差法（PDOA）利用传播往返时间粗估计距离，然后利用相位差精确估计距离。
测距精度和功耗成本是一对相互矛盾的性能指标，追求高精度的同时必然带来高的功耗和硬件成本。当精度要求高时，TODA和PDOA测距方法较优；当成本和功耗为主要考虑因素时，RSSI测距方法较优。距离相关定位方法能够实现精确定位，但对无线传感器节点的硬件、成本和功耗过要求高，而且在测量距离和角度的准确性方面也需要大量的研究。因此未来距离相关定位算法研究趋势是低成本、高能效、高精度的距离或角度测量技术。
1.2.2 距离无关定位算法
距离无关定位算法不需要使用测距技术，只利用连通情况来估测自己的位置。绝大多数距离无关定位算法采取分布式计算模式，因为其可扩展性好，每个节点的计算复杂度与网络的规模无关，计算简单而且容易实现，同时计算在节点进行，通信量小。
质心定位算法[3]：一个普通节点所有直接连通锚点组成的多边形的质心作为该节点的位置。质心算法的原理首先是确定包含未知节点的区域，计算这个区域的质心，并将其作为未知节点的位置。在这个算法中，信标节点周期性地向邻近节点广播信标分组。当未知节点接收到来自不同信标节点的信标分组数量超过某一个门限值k或接收一定时间后，就确定自身位置为这些信标节点所组成的多边形的质心。与未知节点处于邻近关系的所有锚节点，所组成的多边形区域的质心，作为未知节点的位置估计。
APIT算法[4]：与未知节点处于邻近关系的三个锚节点构成一个三角形，以多个这样的三角形的交叠区域的质心作为未知节点的位置。用该算法定位的具体步骤：（1）收集信息：未知节点收集邻近信标节点的信息，如位置、标识号、接收到的信号强度等，邻居节点之间交换各自接收到的信标节点的信息；（2）APIT测试：测试未知节点是否在不同的信标节点组合成的三角形内部；（3）计算重叠区域：统计包含未知节点的三角形，计算所有三角形的重叠区域；（4）计算未知节点位置：计算重叠区域的质心位置，作为未知节点的位置。
DV-Hop算法[5]由三个阶段组成。第一阶段，使用典型的距离矢量交换协议，使网络中所有未知节点获得距初始锚节点的跳数；第二阶段，在获得其他锚节点位置（ ， ）和相隔跳数后，各锚节点（ ， ）利用所收集的信息按式（1）计算平均跳距：
（1）
式中 是锚节点 的平均每跳距离， 为节点 和节点j之间的跳数；然后将平均每跳距离作为一个校正值广播至网络中，校正值采用可控洪泛法在网络中传播。第三阶段，在二维空间中，一旦一个未知节点获得与3个或更多锚节点的距离后，执行三边测量法或最大似然估计法计算自身的位置。
Amorphous算法与DV-Hop相似也有三个阶段，其中第一、第三阶段与DV-Hop算法相同，只是在第二阶Amorphous定位算法是假设段网络中节点的通信半径相同，平均每跳距离为节点的通信半径，未知节点计算到每个信标节点的跳段距离，误差比较大。该算法需要预知网络平均连通度，而且需要较高的节点密度。其相应的改进算法改进方向主要是重新计算平均每跳距离，或利用局部跳数的平均值代替总跳数，但是误差相较DV-Hop算法仍比较大。 2 移动锚节点的节点定位算法
从前面的分析可以看出成本和锚节点稀疏问题是目前定位算法最需要进一步解决的问题。如何以较少的成本获得较多的锚节点位置信息，同时处理锚节点稀疏问题是定位算法的一个重要的课题，有学者提出利用移动锚节点来进行定位。在这些方案中，一个移动锚节点在网络中移动并周期地发送含有锚节点位置信息的信标信号，未知节点接受这些信标信号并通过特定的算法估算自己的位置。其中利用RSSI测距技术进行定位的算法，信标信号中包含锚节点的位置信息和信号强度。利用TOA测距进行定位的算法，在发送信标的时候加入了时间信息，需要有较高的时间同步的要求。利用锚节点的移动性导致的信号到达时间差进行定位的算法。上述的3个方法都是利用的锚节点的移动性来节约锚节点成本，但是对未知节点的硬件成本和功耗的要求并未减少，因此低成本、高能效、高精度的距离或角度测量技术仍然是研究的重点。
3 结论
对现有常见的无线传感网络定位算法进行了对比分析，目前为止，各种定位算法都存在一定的技术缺陷，既便如此，这些已有的算法已经为无线传感技术的推广发展乃至整个人类社会的科技进步做出了不可磨灭的贡献。相信随着科学界对无线传感技术的更加深入、成熟的研究探索，人们一定会开发出技术更加全面的节点定位算法，为更多的行业发展带来活力。
项目基金：渭南师范学院研究生项目（11YKZ025）
参考文献：
[1] 孙利民，李建中，陈渝等.无线传感器网络[M].北京：清华大学出版社，2005.
[2] 王福豹，史龙，任丰原.无线传感网络中的自身定位系统和算法[J].软件学报，2005，16 （5）：858-868.
[3] 陈迅，唐红雨，涂时亮.无线传感器网络主动分布节点定位算法[J].计算机工程与设计， 2008，29（7）：1664-1667.
[4] 刘锋，张翰，杨骥 一种基于加权处理的无线传感器网络平均跳距离估计算法[J].电子与信息学报，2008，35（5）：1221-1224
[5] 姚忠孝，俞立，董齐芬.基于移动信标的 DV-hop无线传感网络定位算法[J].传感技术学报， 2009，22（10）：1504-1507.
作者简介：陈炜（1984-），女，河南淮阳人，2010年毕业于中国矿业大学（北京），硕士，渭南师范学院物理与电气工程学院助教，研究方向无线传感器网络及应用。电话：18700361080，邮箱：cwei62213891@163.com