翻译徐建扬基于地理位置的能量感知路由协议.doc

地理位置和能量感知路由：无线传感器网络中迭代数据传播协议Yan Yu, Ramesh Govindan, Deborah Estr inEmail:yanyu/destrin@cs.ucla.eduzgovindan@ISLEDU08/14/2001摘要未来的传感器网络将由大量的密集部署的传感器或执行器组成这些网络的一个主要 特点是它们的节点是无人看守和无人管理的因此，设计这些网络时能源效率是一个重要 的考虑对象出于这一事实的考虑，传感器网络往往要知道节点的地理位置，我们设计和评 估一个高能效的路由算法是通过传播查询到相应的地理区域，而不是范洪明确的地理位置 和能量感知路由算法使用能量感知邻居选择将数据包路由到指定的rr标区域和递归的地理 范洪，或者限制范洪算法在目的区域内传播数据包使用模拟的方法评估GEAR协议我们发现，特别是对非均匀流量分布，GEAR相对于 其他无能量感知的地理位置路由协议明显有了更长的使用寿命1 介绍未来的传感器网络将由大量的密集部署的传感器或执行器组成传感器网络中的每个节 点可能包含一个或更多的传感器，低功耗的无限发射，，便携式电源和有可能本地化的硬件, 如GPS (全球定位系统)单位或一系列的设备。

这些网络的一个主要特点是它们的节点是 无人看守和无人管理的由此，它们只有有限的能量并且能量无法补充因此，设计这些网 络时能源效率是一个重要的考虑对象本论文主要研究能量效率中地理位置包的转发技术在许多的本地感知系统中，特别是 传感器网络，传播信息到一个地理区域是一种非常有用的方法例如，一个使用的传感器网 可能对在(tl, t2)时间段内一个区域的平均温度是多少感兴趣这个区域应该是明确的, 如一个二维的长方形为了完成上述的通信任务，该查询需要发到传感器指定的区域传播 本地查询到指定区域的一种有效方法是在查询中绑定本地信息，然后直接路由到该区域，而 不是向各处范洪然而，我们的工作与以往相比，地理位置路由如下：1. 不同于以往单播通信系统，我们主要研究在一•个目标区域内转发一个包到所有节点 的问题，在以数据为中心的传感器网络应用中这是一个共同的问题［10］2. 此外，我们的工作不需要有记录到节点位置的节点标识符的数据库，我们期望在通 信基本要素明确时传感器网络的数据中心不是由节点标识组成，而是由命名的数据 组成3. 我们的工作同时也要确保传感嘴是静止的（即不能移动），这不是简单的地理位置路 由问题，而是要确保使能一些我们所使用的路由学习技术。

4. 然而，和以往工作一样，我们也要确保现有的本地系统［22, 2, 18, 7, 19］能够使每 个节点知道自己的当前位置5. 在传感器网络中由于严格的能量限制，我们使用能魇感知方式，结合地理位置信息, 决定高效的能量路由在以往的工作中平衡能量使用已经不是一个主要的设计bl 标我们的地理和能量感知路由（GEAR）技术使用能量感知和地域通知邻居来选择启 发式的路线路由一个包到目标区域在一个区域内，它使用-•个递归地理转发技术传播 数据包尽管GEAR的能景平衡设计受传感器网络应用的影响，我们的协议仍普遍适用 于Ad・hoc网络我们在均匀和非均匀流量分布的情况下模拟GEAR,并把它和GPSR ［12］的性能 进行比较，GPSR是一•种非能量感知的地理路由算法对于非均匀流量分布，GEAR比 GPSR多发送70 %至80 %以上的数据包o对于均匀分布的流量，GEAR发送成功的 数据包也比GPSR多25 %至35 %以上然而，在这两种情况下，GEAR的性能明显的优于分割之后所组成的连接——部分 数据对在一次“分割”后仍然连接着（当所有的源数据从它们各自的目标区域被分割后） 目前我们在适度规模条件下试验GEAR协议的一种原型。

论文剩下的部分组织如下我 们将简短的讨论第二部分的工作，在第三部分将详细的讲解GEAR,然后在第四部分展示 我们的模拟结果，第五部分我们将讨论更多的设计细节和描述接下来要做的工作，第六 部分将给出我们的结论2 相关工作2.1基于地理位置的ad-hoc路由二.二IE1大部分以往的基于地理位置的路由协议都是使用贪婪算法将数据包转发到目的地 他们不同之处在于如何解决通信漏洞Finn［4］是巳知的最早使用基于地理位置的路由他使用限制范洪搜索定位到漏洞 附近这种机制的一•个缺点是在搜索时很难确定一个合适的范围由Karp et al ［12］所 设计的GPSR,通过巧妙得从原始的网络图中分离出了平面图而避免了这个问题 在GPSR中，包紧随在平面图附近从而避免漏洞分离出的平面图比原始的要小，并且流 量主要以周长模式集中在平面图的附件因此，平而图上的节点能量将很快被耗尽， 另外，节点被假定为在乱监听模式，因此消耗能源［21］可扩展的位置更新的路由协议（SULRP） ［24］不断维护网络中节点的大致位置信 息，并且在需要时准确得发现到特定节点的路由它使用了近似的地理位置路由将数据 包路由到包含目的地的区域，一旦数据包在这个区域内，它将使用源路由到这该目的地。

它依赖于路由请求绕过漏洞由于这条路线请求/应答开销和以SLURP方式不断窥探使 它不适合应用在传感器网络中Imielinski and Goel ［9］的工作不那么直接相关，他们提出了查询和监听数据空 间这个应用的一•个基本要素是发送一个查询到一•个数据方格中，这个方格类似于转发 一个查询到这个文件中的某个区域他们首先使用基于地理位置路由转发查洵到 geonode中负责指定查询的数据方格然后正在通信的geonode根据它预置的索引结 构广播该径询到相关节点C然而这样很难建立和维护高度移动中暴露的传感器网络的高 效的索引结构Koetal,提出了位置辅助路由(LAR)【13】，该协议限制了从一条新路由到一•个被 估计的“请求区域”的搜索位置辅助路由不适用于做出路由决定，而是限制路由请求 范洪到-个更小的区域该区域的选定是基于己知目的地的以往位置信息和它的移动方 式然而，当移动的信息不准确时，该请求区域可能需要扩大到整个网络Li et al ［15］提出了一种具有可扩展性和分布式位置数据库服务，该服务可以跟踪 移动节点的位置它可以选择多个位置服务器用于存储每个节点的位置信息移动节点 的位置问题可以通过使用预定义标识符标识和空间划分等级来为某个节点找到本地服 务器的方法解决。

如以前所提过的，这样的位置数据库服务不是目标应用中所必须的2.2其他相关工作Ad-hoc 路由(Ad-hoc routing)动态源路由(DSR) ［11］在需要时范洪路由请求，并且使用混杂监听学习新的路由传 感器网络相比Ad-hoc网络具有更加严格的能量限制，并且在传感器网络中它的带宽需求也 更小因此，范洪路由请求或者在混杂模式下工作使DSR不适用于传感器网络同时，对 于传感器网络，其他存在的Ad-hoc协议［17, 16］相比预期的情况也需要更多的能量资源和 更高的带宽需求然而，这些技术可能适用于这些协议中具有高能量效率的版本能量感知路由(Energy aware routing)Wooetal, ［23］提出了五种能量感知机制如“最大化时间分区”和“最小化最大节点代 价”取代传统的度量如跳数计数或延•迟来发现路由能量高效路由中有一些重要的度量机制, 然而当全局版本出现同样的NP完全问题时就很难直•接在本地算法中实现这些度量机制Chang etal.［3］提出了一种浮动的扩大算法和--种浮动的变向的算法，这种算法将节点 能量消耗的比例平衡到能量预留区这种方法的缺点是它必须先知道源节点和目的节点的设 置以及源节点信息产生的速率，因此，在持续的计算过程中至少拓扑和流量是固定的。

LEACH ［8］提出了-种基于多獴结构的路由协议，它利用随机循环地选择簇首节点将整 个网络的能量负载平均分配到每个传感器节点中它的实质和其他基于负载均衡的能量感知 路由协议是…样的然而，它们下面的假设和我们是不同的他们假设传送功率是可调节的 以及簇头和网间节点直接对话我们假设每个节点有固定的传送功率■在多条网络中最优化 的传送功率在文件范围的外面PAMAS ［20］提出了一种新的Ad-hoc无线网络功率感知多路存取的协议当节点不是处 于传送或者接受数据包的激活状态时它可以智能地切断节点的电源从而保存电池的能量他 们的高效的MAC设计补充了我们的工作传感器网络路由选择机制(Sensor network routing mechanism)传感器网络应用中定向扩散是一个数据中心的协议它通过选择已实验过的路径，并且在网 络中经过高速缓存和数据处理获得能量存储的电平然而，如果没有提供明确的地理位置信 息，最初周期出现的感兴趣的数据和低速率的数据将范洪到整个网络GEAR可以通过感兴 趣的高效的路由发送到目的区域来弥补这一点，从而保存了能量Gao and Pottie ［6Z 5］提出了在大量传感器网络和一个叫做USER的中心信息收集实体 中通信的表驱动、多路径网络结构。

然而，他们预先建立的路由表和多路径结构无法标识到 大型传感器网络再者，表驱动协议可能无法很好的适应动态网络或地代价下的动态流量本地化工作(Localization work)现在在本地系统中存在这感兴趣［22, 18, 2, 7, 19］的实体研究例如以地理位置路由和其他 传感器网络应用为先决条件的系统通过这些研究，Ward etal. ［22］提出了基于三边测量法 则的超声波本地系统；Bulusu etal.［2］提出了对于本地户外没有GPS时大致的跳数连接方 法；Girod and Estrin ［7］提出一种强健的范围估算技术，该技术了利用了声学和多种方式 的检测;Sawides et al. ［19］提出了 Ad-hoc本地话系统(AHLos),它是用于发现纹理的本 地化技术3地理位置和能量感知路由(GEAR)现在我们讨论地理位置和能量感知理由(GEAR)算法像在介绍中所述的，我们对于应用 型传感器网络中路由查询到达目的区域感兴趣转发一个包到目标区域中所有节点的过程包 括两个方面：1. 向目标区域转发包：GEAR使用基地理位-置和能量感知路由启发式地选择向目标区域路由包其中有亮点需 要考虑：(a) 当存在一个到达目的区域更近的邻居时：GEAR在所有邻居中选择到达目的区域更近的下一跳节点。

b) 当所有节点比自己更远时：在这种情况下，将出现漏洞GEAR选择邻居中代价值最小的下-•条节点 我们将在3.1.2中详细的讨论这个问题2. 在目标区域中传播包：在大多数情况下，我们使用迭代地理转发机制在目标区域内转发包然而，在低密度 的条件卜.，迭代地理转发机制有时不会终止，当传送的数据包经过的跳数超过一定的限度时, 包将在空的目标区域内做无用的路由在这种情况卜，我们建议使用限制性的范洪在我们详细讨论上面的算法以前，我们首先陈述假定事项：1. 每个查询包在某些方面都有一个特定的目标区域(对于所描述的算法，我们假定是在一个特定的长方形区 域)2. 每个节点知道自己的位置信息和剩余能量，以及通过一个简单的hello包获知邻居的位置信息和剩余能量 能够以较低的代价记录下从GPS或本地化系统［22, 18, 2, 7,19］中获得节点的地理位置信息，这大概 是归于传感器网络的应用3. 链路是双向传送的，比如，如果一个节点从邻居获得信息，则它传送的信息也同样可 以到达邻居在大部分的MAC层协议中这是合理的选择，例如IEEE802.il,假定链路是对 称的3.1能量感知邻居的计算在这一部分，我们将假定节点N正在转。