英语原文共 6 页，剩余内容已隐藏，支付完成后下载完整资料
自组网定位系统
Dragos Niculescu and Badri Nath
Computer Science Department
Rutgers University
Piscataway, NJ 0885
摘 要
许多自组网网络协议和应用程序都假设已知节点地理位置信息，然后将感测到的信息呈现在地理地图上以便查找位置。在没有GPS的帮助下，尤其是在GPS功率受限，形状因素或视线条件无法使用或不实用的情况下，查找自组织网络的每个节点中是非常重要的。节点定位是使用在各向同性的大型网络中的路由，而不使用大路由表。 我们提出的APS —一个分布式的，逐跳的定位算法，利用两个扩展距离向量的路由和GPS定位，来提供网络中所有节点大致的位置。整个网络中只有少部分节点具有自我定位的能力
关键字：自组网络，定位，GPS，传感器网
1 引言
大部分自组织网络被认为具有高移动性，高功率节点，和中等网络规模的特点，然而具有典型特点的低功率节点、低移动性、大规模传感器网络在许多案例中仍被分类为自组网络，这里确定性的放置节点是不可能的。最近随着传感器器件的结构的发展，可以预见，成本低廉甚至一次性的节点将在未来，特别是在将来的一系列新的农业、气象和军事领域得到应用。这些大的低功率节点面临一系列挑战：不使用大规模常规路由表进行路由，在间歇状态下的适应性，网络划分和生存能力。在本文中，我们解决了在区域中节点自我定位的问题，这给第一个问题提供了解决方案，也解决了其他实际的问题。涉及传感器网络的一种情况是频繁在文献中提到的利用飞机部署的无线传感器网络。在巡航传感器领域，通常利用飞机来收集数据。这和其它的气象应用都隐含的假定传感器提供的数据传伴随着传感器的位置，使得可以将此位置信息附加到地理图监控区域。了解观测数据是绝对必要的，准确定位也可能用于路由和协调目的算法例如GEDIR [1]或geocast [2]算法启用路由时完全没有使用路由表或缩略表。对于像Rene mote [4]这样的设备是合理的，它只有500字节的RAM。一些可以适用于某些的改进特设路由方案，定位辅助路由[11]限制搜索到较小请求区域的新路由。同样，另外，APS适用于室内位置感知应用，这时网络的主要特征不是不可预料性、高移动性，而是随机部署，自组织。这些网络并不能像[7][8][9]提出的那样来判断建立的结构定位的花费是否合理。
作为一项公共服务，GPS可以满足上面的一些要求。然而给每个节点配备一个GPS接收机并不是一个完美的解决方案。有如下几个理由：成本——如果我们把网络扩展为上千个甚至上万个节点（这个因素在将来可能会不怎么重要）；功率受限——根据摩尔定律，电池储蓄能力增长的越来越慢；不可接入性——节点可能放在室内，或者GPS接收可能会受到气候条件的阻碍；不精确性——定位误差有时可以达到10-20m,这甚至比某些网络中的一个跳距还大；外形因素——一个雷内板的如今和一个小硬币一般大。
这里的一些要求定位算法必须满足。第一，它应该被分配一个大规模网络，低存储，低带宽节点，专为间歇状态设计操作，甚至将整个拓扑连接到服务器。一个一个的跳跃方式将会给靠近基站/服务器的节点带来很大的压力。分区使得集中式更加不可能，各种异性网络会使得某些节点相对其他节点承担更多的转发压力。变化的拓扑结构也使得集中式解决方案不可取。第二，它必须最小化节点到节点的通信功率和计算量，因为无线电和处理器是耗尽电池寿命的主要来源。另外在动态的拓扑网络结构中，具有低信令复杂度才是可取的。第三，定位系统应当工作即使网络并不处于连接状态——在一些传感器网络中，数据可以稍后通过飞跃基站来收集。最后我们的目的是在GPS全球坐标系中提供绝对定位，而不是相对定位。有如下一些理由：开当网络拓扑变化时相对定位可能需要更高的信令开销，而绝对位置在GPS坐标系中有一个唯一的命名空间。
本文的其余部分组织如下：下一节总结了目前研究中的相关成果，第三部分
提供一个简短的GPS概述，因为GPS定位原理是我们的核心基础定位方法 第四部分提出了APS方法和传播方式。第五部分展示了仿真结果，我们总结了一些基于节点的移动性对APS的影响的注意事项。
2 相关工作
文献[3]提出了一种集中式的定位方法，这是一种通过在服务器收集整个网络拓扑，然后处理一个大规模的系统，这可以使得每个节点的定位误差最小。文献[5]展示了一种相对定位系统，没有使用GPS定位，其中坐标系是通过节点的集合来表示，称为参考组。至于缺点，除了相对定位与绝对定位的关系，当参考点移动时，没有移动的节点的位置要重新计算。如果中间节点移动了，即使不知道参考点是否移动了，那些依赖于这些节点的固定节点都要要重新计算位置。然而，坐标系传输系统适合对锚节点距离的跳数也能够应用于我们基于距离的方法。在定位系统[8]基于一个统一的强大的网格基站（与节点相比）来作为地标网络。网络中的随机节点能够通过估计它与已知位置的最近的基站之间的距离来确定自己的位置。雷达[9]是一种利用无线电传输特性来测量整个地图的方案，然后通过识别先前绘制的位置指印来实现定位。蟋蟀定位系统使用无线电和超声波信号来估计与已知节点之间的距离，然后执行三角测量法。AHLOS提出一种协作多边形，节点并不能通过常规三边法来确定位置，我们提出来的方法，与以上所有方法相比，最大的不同是它是非集中式的。它并不需要特殊的结构，并且提供绝对的定位。
3 GPS概述
在全球定位系统中（Global Position System）[6]，使用至少四颗卫星来找到接收机的坐标并实现接收机的时钟偏置。对于我们的节点定位来说，我们使用简化版的GPS三角测量法，这里我们只处理距离，这里并不需要同步。
图 1 简化GPS
三角测量步骤优先开始估计位置并稍后对真正的位置进行纠正。在图1中:为估计距离，为真实距离第i个GPS对应的范围为=|| 和=|| 。Delta;rho;是近似线性校准值。如果是矢量的单位矢量，那么=minus;，∆rho;=⋍minus;sdot;Delta;r Delta;ϵ。每个卫星独立的组成一个线性系统，其中定位校准值为Delta;r=.
经过多次重复后，校准值和可以被应用到估计定位上，只有校准值低于我们选择的阈值的时候才停止。这个系统可以利用任何最小平方法完成。
4 自组网定位系统（APS）
如果图形充分连接，并且它的边缘长度已知，那么就可以构建它的平面拓扑结构。但究竟什么才是充分连接呢？如果我们用有线架构来分析图形，其中节点就像是枢纽，我们的目的是确定图形中哪一部分是不移动的，这些节点可以知道它们自己的位置。一旦这种有线结构固定了，它会有一个自己的参考系统，并最终与GPS坐标系对齐。为了在全部平面上固定一些地方的有线结构，至少三个节点（称为锚节点）需要展示在连接图上。这些节点是通过GPS定位，或者通过其它的一些方法知道他们自己的位置。
简单如雷内板这样的结构都可以通过软件来获知无线电信号的信号强度，因此提供了一种方法来估计与最邻近节点的距离，但这种测量方法受误差影响较大。我们定位系统的目标之一是随着整个规模中部分锚节点的增多，来提高定位精度。即使理论上有三个锚节点就足够了，减小测量误差就需要更多的锚节点，具体的要取决于应用。
A. APS算法
让锚节点有足够大的发射功率来覆盖整个网络并不是理想的。有如下一些理由：本地通信之间的碰撞，高功率使用，移动时的覆盖问题。假定锚节点的位置是固定不变同样不可取。因为我们扩展的一些应用中要么是在不可接入的地方飞行放置，要么可能涉及到运动和网络的重构。在这些例子中可以通过网络的跳数转发来确定未知节点与锚节点之间的距离。一般来说，我们利用和GPS相同的原理，不同的是锚节点之间是通过跳数来确定，而不是直接的。任意节点一旦估计了与一些（大于三个）锚节点的距离，它就能够，使用我们在上一章节描述的，基于GPS定位计算的相似步骤来计算它在平面中的位置。我们开始的估计是节点收集的地标的质心。
接下来我们只会参考一个锚节点，因为对于网络中的所有锚节点算法行为是独立的相同的。很明显锚节点邻近的节点可以通过直接的信号强度测量措施来估计与锚节点之间的距离。使用一些传播方法，第二跳节点能够推断出它们与锚节点之间的距离，其他的节点也可以这样做。信令复杂度因此是计算总的锚节点数量，每个节点还要去个平均。使这种方法与距离矢量路由相似的是，在任何时间，每个节点只与它最近的节点进行通信。在每个消息交换中进行通信是其对目前获得的地标的可用估计。这对于那些能力受限节点，他们不需要也不能够处理整个环境、可能的网络移动问题。我们探讨了三种跳数距离传播方法，并且对比了它们的优点和缺点。受到信令数量，功率消耗，和实现定位精度的影响，每种传输方法只对于一些确定的问题是有效的。
B. “DV-Hop”传播方法
这是一种比较基础的方法，利用典型的距离矢量交换以获得网络中所有的节点的基于锚节点的距离。每个节点有坐标{}，并且只与它的领点交换信息更新，一旦一个锚节点获得了它与其他节点的距离，它就可以估计出每一跳的平均距离。这可以作为整个网络的基值，未知节点可以估计它与锚节点之间的距离（单位米）。这里通常使用三角测量法，锚节点{}的校准值计算为：
图 2 DV-hop定位
在图2的例子中，节点是锚节点。节点已知与，的欧式距离分别对应两跳和六跳。计算基值为，这事实上是一跳的平均距离。要么计算一个单一的基值并广播到网络中，要么优先从不同的路径发送不同的基值。我们在实验中采用了前一个方法。类似的，计算基值为16.42，计算基值为。一个常规节点从它的锚节点之一获得更新，它一般来说是最近的一个，这取决于放置规则。和每个锚节点开始的APS基准时间。基值通过洪泛法广播，这意味着一旦节点得到并转播基值后，它会抛弃随之而来的值。这个规则确保大多数节点只从最近的锚节点获得一个基值。当网络很大时，为了减少信令开销，通常为每个传输包设置TTL（ Time To Live）；这可以限制节点获得的锚节点数量。控制洪泛法帮助基值定位于他们产生的锚节点附近，考虑非同性网络，在上面的例子中，假设节点A就获得了一个定位基值，那么它估计与的距离是216.42,与的距离是。这个值会被加入到先前描述的三角测量法的步骤中，这样A就获得了一个定位估计值。距离矢量跳数传播方法的优点是它足够简单，并不依赖于测量误差。缺点在于它只能工作于同性网络，这里指地图的特性都在同一方向。
C 路径矢量距离传输方法
这个方法和先前的类似，不同的是相邻节点间的距离是通过无线电信号强度来测量的。并且是通过米级传播而不是跳数，作为度量，距离矢量算法使用累积的传播距离（单位米）。另一方面这个方法比跳数距离方法要好。因为并不是所有的跳数都有规则的形状，但是另一面这种方法对测量错误很敏感。
D 欧几里得传输方法
第二种方法是通过传播与锚节点的欧式距离来工作的，所以这种方法是最接近GPS的特性。未知节点A需要至少两个相邻节点B和C；它们都已经估计了与锚节点L之间的距离。节点A还测量了AB边、AC边、BC边的距离。这里就是条件：要么B和C除了是A的邻点外，还要是彼此的邻点；要么A已知BC边的距离。这样才能描述它在地图中所有的邻点。
图 3 欧几里得传输方法
无论怎样，对于四边形ABCL，所有的边都是已知的。其中一条对角线BC也是已知的。这就使节点A能够计算第二条对角线AL。这也是A到节点L的欧式距离。很可能A在BC边的另一边。如图中所示的.这时候到L的欧式距离就不一样了。在这两种可能中做出选择基于A要么当A有几组相邻节点来估计L来表决，如果不能在A和中作出准确的判断，这时需要更多的邻点对L的估计适合表决；更多的第二跳邻点估计到L的距离。这时才能做出准确的判断，一旦正确的选择对A是可用的。实际上的估计是通过在三边ACB、BCL和ACL上应用毕达哥拉斯存在定理来确定AL的长度。一种减少误差的措施对欧几里得传输方法是可用的，但不适合于基于距离矢量方法。对于一个锚节点，它去纠正它转发的所有的值使用的是GPS坐标，而不是依赖于测量的接收信号值。
5．仿真结果
我们在ns-2中用提出的传播方法对APS进行仿真，随机生成一个100个节点的类型。自组网定位的两个主要目标是为了描绘地图来获取位置，并且使用测量的路径来路由，仿真基于这些目标来评价这三种传输方法。这里考虑了两种结构类型：一种是具有100个节点的同性结构，平均节点度是7.6；直径是10。这些节点随机均匀分布，所以整个网络中各部分的密度、连接度和通信范围大致相同。我们检测的第二个类型在连接度上是非同性的，它具有字符“C”的形状；所以跳数的数量并不能完美的指示地理距离。这个网络具有100个节点，最大和最小的部分分别具有24跳和1跳。所有好的地图会有GPS比例使得在X轴的节点和纠正几条曲线在信号强度上的距离判断。这个测量误差在常规值的2％—90％之间均匀分布。DV-hop传播方法不受测量误差的影响，在DV—distance和Euclidean中代表着一条厚重的线；也是这三种方法中最容易比较的。
图 4 定位误差-同性结构，“DV-distance”(top)“Euclidean”(bottom)
图4展示了定位的百分比误差（百分百误差意味着没有连通）。欧几里得方法的优点在于能够通过GPS比例提高精度。DV-based算法更加适合应用低锚节点比例的环境下。
图5展示了一个各向异性结构的定位误差。这里有两件事需要注意：第一，由于欧几里得方法测量误差与各向异性误差相比并没有什么不同。欧几里得
全文共9802字，剩余内容已隐藏，支付完成后下载完整资料
资料编号：[144611]，资料为PDF文档或Word文档，PDF文档可免费转换为Word
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
