基于距离和角度信息的无线传感网节点定位问题研究

摘要

无线传感器网络(wirelesssensornetwork，WSN)节点定位通常是指在给定或获取足够多的邻节点之间信息基础上，准确地分布式地估算出未知节点的位置坐标。该课题近几年来一直是WSN的研究热点，一方面由于节点位置信息是绝大多数应用所必需的，另一方面，节点位置信息也是不少网络协议和算法设计中的支撑信息。虽然已有不少二维平面(2D)中的具体定位方法被提出，但是这一课题的研究进展也存在着明显的薄弱环节。一是缺乏WSN系统可定位性数学理论基础，在实现定位之前节点的唯一可定位性研究不足，尤其三维空间(3D)的成果就更少;二是还没有针对无锚节点环境状况下的物理位置定位方法;三是3D中WSN定位方法很有限。为此，本论文利用邻节点之间的距离信息和方位角信息，结合刚性图理论、组合最优化理论和图形变换理论，对WSN节点唯一精确定位问题进行较为全面深入地研究，并提出2D和3D的实现算法。
　　 首先，将WSN唯一定位问题转化为对应图的框架的全局刚性判定问题，分析可定位性。从刚性图的角度，一个无线传感网可以唯一定位的充分必要条件是，它所对应的图G的映射框架是全局刚性的。全局刚性的弱化情形是刚性，因此在距离约束条件下，首先讨论并示例了多种刚性和全局刚性判定定理。由于在3D中全局刚性判定是NP-难的，所以分析了角度约束的优点和平行刚性判定定理。进而把距离约束和角度约束联合考虑，研究混合框架刚性判定定理。最后通过具体反例，验证了在3D中Laman条件加3-连通仅是框架刚性的必要条件，而不是充分条件。并在“完全联合约束”条件下，提出了全局刚性判定命题，来推进3D中的WSN唯一定位问题研究。
　　 其次，在可定位性分析与判定的启发下，利用邻节点之间的距离信息和角度信息，设计分布式轻量级定位算法。具体实现分为四个步骤，包括若干子算法，执行流程为先进行系统初始化，再建立节点本地坐标系，然后计算节点本地坐标，最后将局部的本地坐标转换为全网唯一的全局坐标。2D中的算法称为uniqueanchor-freelocalizationalgorithm(UAFL)，是不需要锚节点支持且能物理定位的精细类定位算法。UAFL在本地坐标系建立阶段，利用角度信息有效地解决了反转分歧（flipambiguilty，FA）。本地坐标计算阶段，充分考虑了24种不同的拓扑结构，使得待定位节点只需有1个额外邻节点就能进行计算。全局坐标转换是重点和难点，采用齐次坐标系统一了平移变换和旋转变换矩阵表达形式，并求解了邻节点坐标系转换矩阵，实现了全局坐标计算。在把sink节点设定为全局坐标系参考原点时，就在无锚节点辅助情况下实现了物理位置定位。通过数值计算实例，验证了UAFL的有效。仿真结果表明，UAFL在同类算法中具有较好的定位覆盖率、定位精度等性能。从节点定位角度看，当网络密度为9～12时，可以获得WSN工程部署的最优性价比。
　　 注意到很多2D中的定位技术实际上并不能拓展到3D，总体上3D定位方法很有限，本文根据UAFL的思路，进一步提出了threedimensionalanchor-freelocalizationalgorithm(3D-AFL)。从帧格式层面设计了邻节点发现和本地坐标系建立等子算法，利用方位角信息解决了3D中的FA问题。局部坐标到全局坐标的转换同样也是3D中的重点和难点，为此，深入分析并求解了邻接转换矩阵。可以看出，本文提出的定位方法避免了复杂计算，属于轻量级算法实现，完全符合WSN的特性要求。通过仿真，检验了3D-AFL的性能，并得出工程部署时比较好的参数范围为网络密度为11～13。同时发现，3D定位实现与可定位性判定一样，具有很大的研究开发空间，比如采用分簇机制，在全局坐标计算环节减少转换次数（跳数），探索增强网络扩展性的方法。
　　 最后，根据跨层设计思想，提出了路由-定位联合优化协议。由于全局坐标转换的目标节点是唯一的sink节点，并且数据汇聚(datagathering)过程中的目标节点也是sink节点，必然涉及报文路由，因此将跳数作为路径长短评价指标，设计跨层优化协议。在不产生广播风暴的情况下，在各节点建立下一跳绑定表，既是可选的路由机制，又优化了3D-AFL。仿真结果表明，提出的联合优化协议较好地缩减了定位时间。
　　 综上所述，本文研究了WSN定位问题的理论基础，给出了3D中验证刚性判定充分条件的反例和基于完全约束的全局刚性判定命题，利用测量信息研究并提出了2D和3D中高准确度的免锚点且能物理定位的分布式定位算法UAFL和3D-AFL，设计了路由-定位联合优化协议，并通过仿真结果分析和给出了工程实践参数。

目录

声明

摘要

第一章 绪论

1．1 课题背景和意义

1．2 WSN定位系统指标分析

1．3 WSN定位算法与可定位性

1．3．1 WSN可定位性问题

1．3．2 定位系统执行步骤

1．4 论文的主要工作

1．5 论文的结构

第二章 WSN精细类定位算法分析

2．1 邻节点测量技术和位置计算方法

2．2 典型精细定位算法分析

第三章 WSN唯一定位性分析与判定

3．1 定位系统模型

3．2 基于距离约束的唯一定位性分析与判定

3．2．1 刚性条件

3．2．2 全局刚性条件

3．2．3 引导式刚性构建(inductive rigid construction)

3．3 基于角度约束的唯一定位性分析与判定

3．4 基于联合约束的唯一定位性分析与判定

3．5 基于混合边的三维空间框架刚性研究

3．6 本章小结

第四章 二维平面中基于联合约束的定位算法

4．1 系统的初始化

4．2 建立本地坐标系

4．3 本地坐标计算

4．4 全局坐标计算

4．4．1 全局坐标变换原理

4．4．2 图形变换与齐次坐标

4．4．3 转换矩阵计算

4．5 数值计算示例

4．6 性能评价与仿真

4．6．1 定位误差来源与评价

4．6．2 仿真参数与评价指标

4．6．3 结果与分析

第五章 三维空间中基于联合约束的定位算法

5．1 系统的初始化

5．2 建立本地坐标系

5．3 本地坐标计算

5．4 全局坐标计算

5．4．1 3D全局坐标变换原理

5．4．2 3D齐次坐标

5．4．3 3D转换矩阵计算

5．5 定位与路由联合优化

5．6 性能评价与仿真

5．6．1 3D仿真参数

5．6．2 结果与分

5．7 本章小结

第六章 总结与展望

6．1 论文总结

6．2 工作展望

参考文献

致谢

攻读博士学位期间发表的学术论文

攻读博士学位期间参与的科研项目

附录 发表的英文论文