移动自组网络无GPS定位技术可行性研究

王艳 张明 刘衍民 张博扬

摘 要：与其他移动网络相比，移动自组网络的自组织性、健壮性、高效性更强，特点鲜明优势明显，而移动自组网络中对节点进行定位的方法多数基于GPS系统和固定或移动基站，限制了移动自组网络优势的发挥。文章基于定位系统的空间特性对移动自组网络定位方法进行研究，重点分析了不依赖GPS系统进行网内节点定位的技术可行性。

关键词：移动自组网络；定位；无GPS

1 典型定位技术和定位系统

移动自组网络属于无线网络的一种，网内单元由可移动的节点按照一定的协议组织，与其他无线网络不同的是，移动自组网可以不依赖于中心路由设备，可以以无基站的状态运行。目前有关终端定位的方法很多，移动自组网中节点的定位方法因为网络组网形态和无基站运行等因素，是一个涉及交叉学科领域的问题，目前对这一问题的研究也比较多。从分类方法上可从系统使用环境、采用的坐标系、采用的定位算法、采用的无线信号源等方面进行定位。本节从系统采用的定位算法入手，对几种典型定位方法进行分析比较，对定位方法从算法分析的角度进行分类，为不依赖GPS系统进行网内节点定位的技术可行性分析奠定基础。

1.1 位置概念

位置，是指某一时刻物体在空间中所处的点。对位置的描述有多种形式，可以是绝对的也可以是相对的，对位置的表征可以是绝对的也可以是相对的。以空间中唯一的位置点为例，西安钟楼的位置点在某一时刻是唯一固定的，如果采用物理位置对其进行描述，可以采用经纬度加高度的形式，表征为北纬34°15'39.90''，东经108°56'33.32''，海拔586 m；如果采用象征位置对其进行描述，可以表征为南大街以北，北大街以南，东大街以西，西大街以东。当要量化使用位置时，单纯的物理位置必须依托于一个数据库系统进行物理位置向象征位置的转换后才可以使用。对物理位置的使用必须参考一个坐标系，相对位置和绝对位置的概念就是对应坐标系而来的，一般绝对物理位置对应的是绝对坐标系，常用的有以地心为原点建立的三维坐标系，相对位置对应的是相对坐标系，相对坐标系可以有多种定义方法，可以满足不同的实际应用需求。

1.2 定位方法

本节从定位方法的算法角度出发，重点介绍三角定位法和对照定位法的实现方法和特点，并对每种定位方法的优缺点进行比较分析。

1.2.1 三角定位法

三角定位算法根据三角形的几何特征来计算顶点的位置，最初由英国历史学家汤姆·布鲁克斯提出，广泛应用在全球卫星定位技术中。定位系统所提供的位置信息的精确程度是衡量定位系统的重要指标，目前常用的定位算法横向对比，三角定位方法的定位精度是比较高的。

下面主要介绍三角定位算法中常用的多边形定位算法。根据定位过程中是否需要测量节点间的距离，可以将定位算法分为距离有关的定位和距离无关的定位两种，距离有关的定位方法通过测量相邻节点间的距离或角度实现对未知位置节点的定位。多边形定位法属距离有关的定位算法，是通过计算某一节点到与其不共线的其他3个节点之间的距离来得出该节点的位置。基于测距的原理，多边形定位法的测距方法可分为3种[1]。

（1）接触测距法。

接触测距法顾名思义，是采用物理介质由一个节点出发直接触碰到相邻节点，从而直接得到两节点间的物理距离，这种方法简单直接，但只适用于距离较小、节点分布简单的网络结构，并且测量效率不高。

（2）基于时间及时间差的测距法。

基于时间的测距法首先要知道信号传播的速度，再测得信号传播的时间，然后采用三边或极大似然估计法利用节点间的信号传播时间计算节点间的距离。在这个过程中，同步时钟的校准、信号传播过程中的干扰和测量精度等都会对结果产生影响。为尽量减少这些误差，还可以采用基于时间差的测距方法，以到达时间差（Time Difference of Arrival ，TDOA）技术为例，发射信号的节点同时发射两种信号，两种信号的传播速度不同，接收节点接收到这两种信号后，根据接收时间差和信号的传播速度采用三边或极大似然估计法计算距离，从而得到发射节点的位置。

（3）基于信号强度及角度的测距法。

信号的传播距离的平方与信号强度成反比，基于信号强度的测距法就是通过计算信号在传播过程中的衰减来估计节点之间的距离。基于信号角度的测距法，在接收侧布置接收阵列或多个接收节点，通过感知接收到的信号角度不同计算出接收端与发送端之间的角度，再通过三角测量法计算接收端与发送端之间的距离，这个过程一般包括确定邻节点间夹角、测量信标节点方位角和利用方位信息计算节点间物理距离等三步。

1.2.2 对照定位法

对照定位法也可称场景定位法，简单讲是将待定位节点发来的信号与已有记录相对照，选出最接近的结果，再进行一定的修正工作来达到定位的目的。要实现对照定位，首先需要建立基础数据库，数据库中需要包含网络中所有节点的位置信息等以供参考，这一部分的工作一般在具體实施定位前完成，数据库可以以离线的方式处理，可以以增量更新的方式实现定期或不定期的刷新。数据库中节点定位信息的确定方法有很多，可以是人工测量，也可以通过自动扫描实现。当待定位节点发来信号后，将接收到的信号信息与库中记录的信息进行比对，得出的结果可能是一个确定的节点，可能是一个范围内的多个节点，也有可能是一个区域，这取决于数据库建立时的粒度，粒度越小，精度越高，得到的结果准确性越高。当结果是一个范围内的多个节点或一个区域时，还需要进行进一步的处理，以得到最佳匹配结果，提高定位精度。对照定位法在室内范围较小且节点分布复杂度不高的情景下效果较好。

在对照定位法中，最常见的情况是对照返回的结果不是数据库中已记录的唯一节点，而是与待定位节点相邻的节点或一个区域范围，这样就需要再优化的机制对结果进行进一步处理，确定待定位节点的位置或区域范围。再优化机制实现相邻定位主要有3种方式：感知、计算和监视。感知是一种最直接简单的方法，可以通过压力、光线、微电流等多种方式感知待定位节点是否在返回节点附近或返回区域内。感知方式常用在医学领域，利用微距感知技术实现人体内的定位，保证治疗的准确性。计算是一种利用区域覆盖实现定位的方式，一般认为一个节点的作用范围不仅局限于节点自身大小而是一个以节点为中心的三维区域内，可以将这样的节点理解为基站，多个相邻基站的信号覆盖范围是有重叠的，当一个待定位节点同时出现在几个基站的覆盖范围内时，就可以通过计算几个基站的相交部分实现节点的定位。监视定位方法的实现需要有更加智能的终端系统支持，终端系统可以是刷卡机或计算机终端等，这类系统本身具有身份标示，身份标示可以与安装使用位置相关联，从系统发出的数据带有标示身份信息的内容，定位时通过监视使用信息就可实现对终端的自动定位。

2 移动自组网中的定位技术

从上述分析可以看出，定位方法大部分是依赖于GPS、已知网格结构、已知位置的节点或基站等实现定位的，存在前期工作量大、硬件依赖高和承担计算任务的基站或节点负载高等问题。为充分发挥自组网络在扩展性、精确性、移动性和自组织性方面的优势，我们考虑在移动自组网络中能否不依赖于GPS和已知网格结构实现节点的快速定位，本节在理论上对这种定位方法的技术可行性进行分析。

2.1 问题的提出

具有高移动性和自组织性网络可以理解为在一定的空间内，节点以自由或组合的方式分布，为实现无GPS和无已知网格结构定位，可以将问题描述为网络中节点的定位只依赖于节点间的互联关系和位置关系，与除节点外的其他定位设备无关，并且节点的自由移动和网络拓扑的变化对定位能力不产生影响。为实现这种不依赖于外界定位设备的定位，首先需要建立一个对应于网络结构的相对坐标系，在相对坐标系内标注节点的相对位置，在网内节点相对移动较小时整个网络对外可呈现为一个整体。当需要对网络进行整体定位时，可以通过细化网络结构，选取网内不共面的4个节点作为基准计算绝对坐标，实现相对坐标向绝对坐标的转换。在本节中，我们的研究对象为网络内的节点定位问题，下述均为相对坐标系。

相对坐标系确定后，明确节点的分布情况是实现网内节点定位的重要一步。可以采用上一节介绍的三角定位法实现待定位节点与其他节点之间的距离和夹角计算。选取网内不共面的4个节点作为基准节点，通过三角函数计算这4个节点与待定为节点之间的距离和夹角，从而可以得到待定位节点与4个节点间的空间关系和相对位置。节点的分布情况不仅影响相对坐标系的建立，而且对系统定位的准确性影响很大，为提高定位方法的通用性，可选取随机分布模型进行节点分布。

如何得到节点间距离和夹角值是实现定位的实质问题，节点间的关联性涉及通信机制和网络性能等多方面，目前在信号传输方面技术相对成熟，实现节点间互通的方法很多，例如可以采用射频技术、声波技术、光波技术及多种技术的结合使用。在具体验证时，可以采用基于时间和时间差的测距方法和基于信号强度和角度的测角方法这两种方法的结合，两种方法的结合可以在一定程度上减少某一种方法带来的误差，提高精准度，但同时也会增加硬件开销和计算复杂度，需综合考量。

2.2 研究假设

本节基于上述问题的提出和描述，提出研究假设并分析其中关键技术实现的可行性，为建立物理模型奠定基础。

目标网络整体结构是全分布的，其中包含的节点个体间相对独立，不存依附关系，即节点在网络中的地位是一致的，没有作为中心节点为其他节点提供服务的情况，网络中的每个节点有唯一的标识。节点按随机分布模型随机分布在网络域中，不存在人为设定或按某种规律分布的情况，也不存在网络域中特定区域对应特定节点的情况；网络中的通信机制采用无线通信，节点间均可互联，通信范围为以发射端为球心的球体，球体内各处通信状态良好无盲区，网络中所有节点共享无线信道，通信协议统一，节点间所有传输信息均以数据报的形式打包传输；网络内时间同步，可采用基于时间和时间差的测距方法和基于信号强度和角度的测角方法及这两种方法的结合通过计算节点间的距离和夹角；在相对坐标系建立过程中，为提高坐标系建立的准确度，认为网络内节点相对位移较小或静止，保证节点移动距离与网络通信范围具有不可比性，网内节点数量不少于4个、节点自身具备数据计算能力是相对坐标系建立的基本需求。

2.3 可行性分析

不依赖于GPS或已知网格对无线自组网络中节点进行定位必须依靠节点间的通信来实现，节点间的通信状况直接影响定位能力。上述问题的提出和研究假设中指出，通过计算待定位节点与其他4个与其不共面的4个节点之间的距离和夹角实现定位的首要条件是能够建立相对坐标系并可以寻找到4个不共面的节点，再通过计算得到结果。在坐标系和4个节点数量满足条件后，节点间如何实现跳转通信是计算的前提。

跳转可分为单跳和多跳两种方式。如果一个节点发出信号，在其通信范围内的其他所有节点不需要通过其他节点或设备中继都可以直接接收到信号，就属于单跳方式。单跳实现的是本地广播，只需一次传播就可以实现信号的范围内广播。在单跳方式中，通信范围内任一节点都可以通过与其不共面的其他4个节点之间的直接通信实现定位。如果一个节点发出信号，其通信范围内的节点并不是都能直接接收到，有的节点还需要通过其他节点中继一次或多次才能接受到信号，就属于多跳方式。多跳方式中，定位可分为两种，一种与单跳方法原理类似，不能直接通信的节点间通过中继实现连通并在全网中选取用来计算的4个不共面的节点，再通过中继的方式将不共面节点的信息向全网广播，以实现待定位节点的定位。另外一种方法将多跳网络划分为多个单跳网络，每个单跳网络中的定位方法与单纯的单跳网络相同，待定位节点利用其所在的單跳网络中的4个不共面的节点来实现定位。第一种方法中，中继次数和跳数由网络拓扑和节点分布情况决定，有可能出现中继次数较多、跳数较多带来节点计算量和复杂度较大的情况，再加之建立相对坐标的过程中，如果节点间距离和夹角的计算量较大，整个网络计算量会很大，时间开销和硬件开销不好控制，另外，要实现全网络的广播通信，任一节点发出的信号其他节点均能直接收到，每个节点中都要存储相邻节点的配置信息，重复计算的量也很大。无线自组网络的带宽资源非常宝贵，应该尽量避免内部重复计算带来的消耗。因此，采用第二种方法可以规避过多带宽的消耗，将网络看作一个或多个单跳网络，节点的定位在局部单跳网络中实现[2]。

具体实现思路是，将待定位节点所在的可建立的最小单跳网络定义为局部单跳网络，在其中建立局部坐标系，寻找不共面的4个节点作为基准，利用很小的计算开销和带宽实现待定位节点在局部坐标系中的定位，再通过局部坐标系向网络相对坐标系的转换实现待定位节点在整个网络中的定位。在建立坐标系的过程中，节点的实时位置移动对坐标系的建立难易和准确性影响很大，因此，最好选取节点间相对距离和夹角变化较小的情况下建立局部坐标系和相对坐标系，当相对坐标系建立完成，整个网络就可以作为一个整体，网络内节点的移动属坐标系内变化，不影响网络的整体状态。通过这种方法，可以尽量减少由建立坐标系和维护相邻信息带来的网络开销和硬件开销，同时，在网络内节点位置发生变化的情况下将变化影响的范围缩小到其所在的局部单跳网络中，提高定位效率和精度。

需要注意的是，坐标系的建立依赖于节点的分布情况和节点间的通信情况，所以网络内部节点数量、相对位置关系、互联互通能力、呈现的网络结构、节点移动速度方向等因素都关系到相对坐标系建立、维护和更新，并对节点定位的准确程度、时效性有很大的影响。在上述具体实现思路中，首先需确定待定位节点所在的局部单跳网络，网络的划分和建立取决于能否找到不共面的4个节点，如果找不到这样的节点，即使网络内节点再多、范围再大也无法建立坐标系。另外，如果网内节点相对位移较大或移动速度较快，超出节点自身维护信息的能力和计算能力，势必会影响定位精度。因此，在选取定位技术之前，需对网络整体结构、节点分布情况、节点运动情况进行综合评估，寻找最优、最快、最准确、最适合的定位方法。

上述技术实现思路是以相对静止自组织网络为应用场景提出的，即网络内节点静止或相对位移很小，小到与网络覆盖范围不可比，那么当网络内节点自由移动时，定位机制会产生变化，区别主要体现在坐标系维护、节点位置信息更新机制和节点分布情况更新机制等几个方面。动态数据的更新会带来通信带宽和计算量的增大，可能会对定位的时效性和准确性产生影响，如何平衡各因素是后续需要持续研究的问题。

3 结语

本文对典型定位技术和定位系统进行了介绍，针对移动自组网络中的定位技术背景和相关工作进行了研究，在移动自组网络面临的诸多问题中，对节点位置的计算和管理是一个基础性的问题，如何有效确定对象的位置，还有很多优化工作需要做。本文对一种全新的无GPS、自组织的三维定位系统的可行性进行了分析，为优化工作奠定了理论基础。

[参考文献]

[1]彭沛.移动自组网络中的广播与路由问题研究[D].长沙：国防科技大学，2001.

[2]PATWARI N.Relative location estimation in wireless sensor network[J].IEEE Transactions on Signal Processing，2003（8）：2137-2148.