基于物联网空间划分的定位算法

摘 要：基于无线通信和网络技术的三维空间定位是目前物联网领域的一个研究热点，针对当前三维目标定位算法的精度低、复杂度高、功耗大等实际问题，提出了一种新型的分布式三维定位机制。该算法采用合作位置感应算法（CLS）来进行空间网格划分，通过距离估计判定目标位置，并结合了高斯拟合、信号排序机制以及Bounding-inbox等关键技术，有效降低了信号干扰，实现了局部网格划分，减少了网格投票开销。仿真结果表明，该算法与现有三维定位算法相比，有更好的定位精度，并且实现简单，定位功耗较低。

关键词：物联网；三维定位；高斯拟合；网格划分

中图分类号： TP393.07

文献标志码：A

Positioning algorithm based on Internet of things spatial meshing

HE Jia-hong*，ZHANG Xiao-ming，WANG Yong-heng

College of Information Science and Engineering， Hunan University， Changsha Hunan 410082， China

Abstract： The three-dimensional spatial target positioning based on wireless communication and networking technology is a hot research topic in the field of Internet of Thing （IoT）. However， there are still some problems like low accuracy， high complexity and big power consumption， etc. Thus， a distributed three-dimensional positioning mechanism for the environment of the IoT was proposed. The algorithm used Cooperative Location-Sensing （CLS） to mesh grid and determine the target location by the estimated distance. It combined Gaussian fitting， signal sorting mechanism and Bounding-inbox algorithm， which had effectively reduced signal interference. Moreover， it used local meshing to reduce the grid voting overhead. The simulation results show that the algorithm is better than the existing three-dimensional positioning algorithm in accuracy and has a lower power consumption.

英文关键词　Key words：

Internet of Things （IoT）； three-dimensional localization； Gaussian fiting； grid meshing

0 引言

目前，物联网技术已经广泛应用于环境、交通、军事、航空、医疗卫生等多方面[1]，而对于物联网中大多数应用来说，没有时空标识的数据用处有限，而且节点的位置信息是物联网进行上下文感知的依据，而目前的大多数定位算法都是针对平面环境，而且有算法复杂度高、定位不准确、实时性差等缺陷，难以应对物联网实际应用环境的复杂性。物联网应用环境复杂多样，涵盖室内与室外多种场合，因此物联网对定位算法提出自组织性、鲁棒性以及低能耗等要求。

定位算法根据定位机制的不同，分为两类：基于距离的（range-based）定位算法和与距离无关的（range-free）[2]定位算法，三维空间定位与二维平面定位相比，环境因素更加复杂，节点的计算量也有所增大。目前，对于三维定位算法的研究还处于起步阶段，成果较少，比较典型的有文献[3]提出的近似球形内点测试（Approximate Point-In-Sphere， APIS）算法，这是一种典型的距离无关算法，其思想与平面定位算法中的近似三角形内点测试（Approximate Point-In-Triangulation Test， APIT）算法类似，都是基于一种空间划分的思想：以一个锚节点为球心，分别以它到附近其他锚节点之间的距离为半径画球，就能把整个空间划分出大大小小的同心球体。待定位的节点通过判断自己“在”还是“不在”这些同心球体区域中，最终找到包含自己的最薄的一层球壳。然后以不同的锚节点作球心，找到一系列这样的最薄的球壳，最后求取包裹区域的质心。文献[4]提出无线传感器网络三维自身定位方法，通过改进APIT算法得到三维空间定位算法APIT-3D，该算法通过循环测试未知节点是处于由某4个节点所组成的四面体的内部或外部，筛选出所有可能的四面体，从而不断缩小未知节点的周边区域，得到节点的空间位置估计。文献[5]提出一种基于弧心的分布式无线传感器网络节点定位算法，针对每个未知节点，基于传感器节点之间的通信约束关系、空间几何关系和锚节点的已知位置信息，从而在几何学角度建立起包含未知节点的圆弧区域，将该圆弧区域的质心作为未知节点的估计位置。还有其他的一些三维定位算法包括Landscape-3D[6]、Constrained-3D、三维距离向量—跳段（Three-dimensional Distance Vector-Hop，3D-DV-Hop）[7]等。

三维定位算法普遍存在的问题是为了追求一定的定位精度导致计算量过大、定位时间过长、系统实时性大受限制，而且往往对网络密度要求高，系统能耗过大，这些都大大限制了三维定位算法的实用性。针对三维定位算法中的种种问题，提出一种基于空间网格思想的分布式三维定位算法3D-CLS，对传统平面网格算法合作位置感应算法（Cooperative Location-Sensing，CLS）[8]的定位思想进行扩充，解决信号干扰误差和网格划分带来的计算开销问题。结果表明该算法计算量小，无需额外的节点硬件支持，对网络拓扑具有一定的鲁棒性，通信开销和定位误差均比较小，弥补了目前许多方法存在的不足，非常适合应用于物联网环境中。