地理位置路由

地理位置路由（共7篇）

地理位置路由 篇1

0 引言

近年来, 随着低功耗、微型化GPS的发展, 以及三边测量等定位技术的日趋成熟, 使得基于地理信息位置的路由算法日益成为研究的热点。而且在无线传感网络中, 很多应用都与节点的位置信息有关, 甚至某些应用必须知道节点的位置信息后, 传感器节点采集的信息才有真正的价值和意义[1]。例如, 在环境监测中, 需要知道被监测点的位置信息;在森林火灾监测和煤矿安全事故监测中, 需要知道发生险情的位置信息;在跨海大桥桥梁安全监测中, 桥梁摆动的幅度需要精确知道其位置偏移信息。以地理信息位置为导向的路由同时具有很强的路由导向性。以往传统的路由需要存储大量的路由表或者在整个网络内泛洪路由请求数据包来寻找数据包发送的路径, 而基于地理信息的位置路由, 可以缩减路由请求的泛洪区域, 甚至取消泛洪, 大大降低整个网络的能耗、拥塞, 使得网络的生存时间得以提高、网络的规模得以提升[2]。

1 相关算法研究

在基于地理信息位置路由算法依靠单跳邻居节点和目标节点的位置信息来确定路由, 路由选择比本节点更接近于目标节点的邻居节点作为下一跳节点[3,4,5]。但当网络中存在空洞的时候, 该种贪婪算法有可能失效。对此, 很多文章提出绕过空洞的解决方法, 这些算法大体可以分为三类:局部泛洪机制、消息回退机制和面路由机制。其中以GPSR算法应用最为基础和广泛。

GPSR算法[6]结合了贪婪转发路由和周边路由, 源节点先用贪婪转发策略发送数据包, 当数据包到达局部最小节点时, 算法进入周边模式, 即节点采用右手法则选择下一跳节点。在周边模式中如果一个节点到目标节点的距离小于局部最小节点到目标节点的距离, 则在此算法由周边模式恢复到贪婪算法模式中, 依次重复直到到达目标节点。

虽然当源节点和目标节点存在连接的时候, GPSR算法总能保证数据包的发送, 但GPSR算法存在三角路由问题和盲目路由问题。对此GLR算法[7]将算法由周边模式恢复到贪婪转发模式的节点称为信标节点 (landmark) , 源节点在知道到达目标节点的信标节点位置信息后, 可以直接将数据发送到目标节点而不经过局部最小节点, 从而优化三角路由问题。同时信标节点的发现过程采用前向发现与后向发现相结合的方式, 避免盲目路由问题时数据包绕整个网络转发的情况。

相对于GLR一个目标节点对应一个信标缓存的情况, ITGR算法[8]提出目标阴影区域的概念。通过一次信标发现过程, 发现到目标节点路径上的信标节点和局部最小节点后;通过源节点、局部最小节点、信标节点的平面直线方程不等式组划定目标节点阴影区域的范围, 一个信标节点对应目标阴影区域范围内的所有节点。ITGR算法大大降低信标缓存的大小, 并且减少信标发现过程, 降低了控制开销。

2 基于信标的地理信息位置路由协议的改进

本文在ITGR算法基础上提出信标后退算法, 试图扩大目标节点的阴影区域, 让一次信标发现过程发现更大的目标节点阴影区域, 让更多的节点使用信标节点作为间接目标节点转发数据, 并减少算法进入周边模式的次数, 缩短路由路径。

下面我们通过举例来说明如何扩大目标节点阴影区域范围。在图1中, S为源节点, D为目标节点, 阴影区域为VOID区域 (由于阴影区域中存在障碍物等原因, 网络无法通过此区域通信) , P为局部最小节点, B1为ITGR算法的信标节点, 实线为源节点S按照ITGR算法发送数据包到目标节点D的路径, 虚线为更新信标节点后的路径。

ITGR和GLR算法中定义信标节点为路由算法由周边模式恢复到贪婪转发模式的节点。假设用DISTANCE (X, Y) 来代表X与Y点之间的距离, B代表信标节点, 则信标节点B满足公式 (1) 。由图1可以发现, 不仅仅在信标节点B满足公式 (1) , 按照数据包所走的路径往后推, E、C、N、B2点都满足公式 (1) , 直到到达M点, M点并不满足公式 (1) 。所以在B2同时满足公式 (2) 与公式 (3)

因此我们可以在ITGR发现信标节点的路径上逆向寻找第一个DISTANCE (X, Y) 的峰值, 并将其称为新信标节点。当知道更新过信标节点后, 下次S点再发送数据包到D时, 直接将数据包发送给B2, 然后由B2转发给D点。从图1中可见, 未更新信标节点前, 数据包发送路径为实线代表的路径, 共16跳;更新过信标节点后, 数据包发送的路径为虚线所代表的路径, 共12跳。可见更新过信标节点后, 可以节省路由跳数。采用ITGR算法, S点第二次向D点发送数据时, 先将数据发送给间接目标节点B1点, 但在使用贪婪算法向B1点发送数据的时候, 到达Z点遇到空洞问题, 此时Z点使用周边模式向B1转发数据包。而如果采用了更新信标算法, S点第二次向D点发送数据的时候直接将数据包发送给B2, 此时, 路由路径不需要进入周边算法模式, 从S到B2和B2到D点都可以直接使用贪婪算法转发。

假设X为射线SB2上的一点, Y为射线SB1上的一点, Z为射线SP上的一点。则ITGR算法中目标节点阴影区域为YB2PZ, 如图2中的斜线区域;更新信标节点后, 目标节点阴影区域为XB2PZ, 如图中的网状区域。由图2可见区域XB2PZ比区域YB2PZ更大, 说明采用新信标节点可以扩大目标节点阴影区域范围。

改进后的路由算法描述如下:源节点向目标节点发送数据时, 按照ITGR算法将数据包转发到B1点, 在B1点按照ITGR算法数据发送模式由周边算法模式恢复到贪婪算法模式中。我们在此加入LBD (landmark backward discovery) 算法, 即信标节点后向推移算法。根据ITGR算法, 路由模式mode在B1点将变为GREEDY, 此时节点将采用LBD算法转发数据, 算法伪代码如表1所示。LBD首先判断信标节点的上一跳节点是否比信标节点到目标节点的距离更远。如果不是, 则直接继续按ITGR原来算法运行;如果是, 则更改数据包模式并将数据包发送给上一跳节点, 然后按照左手法则依次向回查找距离目标节点, 直到查找到新的信标节点或者回传数据包到局部最小节点。

3 仿真结果

本文使用离散仿真器OMNeT++4.0对ITGR算法和更新信标后的ITGR+LBD算法进行仿真对比。整个实验网络为1500m×2000m, 网络内随机分布200到400个节点, 每次仿真增加50个节点, 节点保持静止状态, 网络中间存在一个900m×200m的空洞, 空洞上方的一个源节点向空洞下方的10个目标节点各发送10次数据。

仿真主要测量平均路由跳数和路由路径平均长度, 仿真结果如图3和图4所示。由图3可见更新信标节点后, 平均路由跳数最少减少9.46%, 最多减少21.92%, 平均减少15.18%。由图4可见, 更新信标节点后, 路由路径平均长度最少减少6.46%, 路由路径平均长度最多减少15.72%, 平均减少11.03%。采用ITGR算法第二次向目标节点发送数据的时候首先使用贪婪算法转发到信标节点。但当网络中存在窄带型空洞的时候, 使用贪婪算法向信标节点转发数据有可能重新遇见空洞, 造成迂回路径。而采用新的信标节点后, 由于新的信标节点一般位于窄带型空洞的两端, 所以有效地减少了向信标节点发送数据的时候重新遇见空洞的问题, 缩短了路由路径长度。另外当后移了信标节点后扩大了目标节点阴影区域, 使得更多的目标节点可以使用已发现的信标节点, 避免了二次重复信标发现。仿真实验结果证明了采用新的信标节点后, 可以降低路由路径的平均跳数和路由路径的长度。

4 结论

本文提出一种ITGR的改进算法, 通过逆着到目标节点的路由路径方向选择新的中信标节点, 可以扩大ITGR算法中目标节点阴影区域范围, 减少算法进入周边模式的次数, 改进的算法既能有效地绕过空洞, 又能有效地缩短绕空洞时路由路径的迂回长度。仿真实验表明, 当网络中存在窄带型空洞时, 更新信标节点可以有效降低ITGR算法的路由跳数并缩短路由路径的长度。

参考文献

[1]宋文, 王兵, 周应宾.无线传感器网络技术与应用[M].北京:电子工业出版社, 2007:65-92.

[2]Alotaibi E, Mukherjee B.A survey on routingalgorithms for wireless Ad-Hoc and mesh networks[J].Computer Networks, 2012 (56) :940-965.

[3]孙利民, 李建中, 陈渝, 等.无线传感器网络[M].北京:清华大学出版社, 2010:27-55.

[4]Li C, Zhang H, Hao B, et al.A survey on routingprotocols for large-scale wireless sensor networks[J].Sensors, 2011 (4) :3498-3526.

[5]Xiaoli M, Min-Te Sun, Gang Zhao, et al.An efficientpath pruning algorithm for geographical routing inwireless networks[J].Vehicular Technology, 2008 (57) :2474-2488.

[6]Karp B, Kung H T.GPSR:Greedy perimeter statelessrouting for wireless networks[C]//Proceedings ofthe Sixth Annual ACM/IEEE International Conferenceon Mobile Computing and Networking, 2000:243-254.

[7]Jongkeun Na, Chong-kwon Kim.GLR:A novelgeographic routing scheme for large wireless ad-hocnetworks[J].Computer Networks, 2006 (12) :3434-3448.

[8]Yang Jianjun, Fei Zongming.ITGR:Intermediatetarget based geographic routing[C]//Proceedings of19th International Conference on ComputerCommunications and Networks (ICCCN) , 2010:1-6.

地理位置路由 篇2

关键词：无线传感器,伪三维地理位置,算法分析

一、前言

在一个三维无线传感网络中, 我们用S来表示源节点, 用D来表示目的节点, 在与S相邻的节点内, 我们将距离节点D欧氏距离最近的节点用C表示。根据三维无线路由策略, S会选择C作为数据发送的下一跳。在理想情况下, 这种基于欧氏距离的选择策略, 可以保证数据传输的范围围绕着目的节点上下浮动, 维持源节点到目的节点的最短距离。但就实际情形而言, 传感器的节点经常是在高低不同的曲面上分布, 所以传输路线只能延路面起伏传播, 而不能按照我们设想的理想路线进行, 起伏地势表面的路径必然比其他邻居节点到目标节点的沿起伏地势的表面路径长, 所以, 基于欧氏距离的选择路径参考标准来说, 这种计算方式效果并不是很理想。为了能够满足实际的需求, 获得最理想的起点到目标点的路径长度, 需要根据起伏路的实际地势, 通过电子地图来对节点之间的起伏地势进行最短路径进行分析, 探讨新的计算距离的方法。

二、起伏地势上的最短路径的计算方式

电子地图是可以通过卫星来进行遥感的技术, 它以数字的形式存储在介质上, 采集到的信息精度可以到深入到厘米, 包含河流、道路、等高线、建筑物标等多方面的信息。在一个电子地图上, 某一地点的地理位置要通过x轴、y轴、z轴表示。我们假设R点是在电子地图上的一个位置, 那么在x轴、y轴信息已知的情况下, 我们就可以通过电子地图得到P点的Z坐标。即Z=f (x, y) 。

针对上文中所描述的三维无线路由算法在崎岖不平的地势情形下, 利用欧氏距离的选择路径算法不理想的现象, 我们用起伏地势上的近似最短路径来代替欧氏距离的方式, 利用电子地图空间取点的做法, 采用起伏地势上的近似最短路径, 在电子地图表面选取几个离散点进行计算。但这些离散点的选择要能从整体上反映电子地图表面的起伏趋势。对相邻离散点直接的欧氏距离进行计算后, 便可以将相邻两点之间的关系映射到一个二维平面上。根据上文提到的计算路径最短的方法, 计算出电子地图表面各个离散点之间的最短路径, 这条路径是通过对电子地图上的各个离散点的选取得来的, 所以能够很好的反应出其实际的最短路径。每次当传感器节点散落在电子地图所设计的区域时, 节点就会根据自己所在的地理坐标寻找到离自己最近的那个离散点, 然后根据离散点之间的最短距离去映射实际地势上两点之间的最短距离。

要计算出起伏地势上最短的路径, 首先要建立网格, 在电子地图上寻找离散点。建立网格的第一步是要截取要建立传感器网络区域内的电子地图, 根据这部分电子地图在电子地图的垂直投影面上按照横轴X方向和纵轴Y方向建立一个正方形的网格;第二步是把这些网格产生的交点从其垂直方向找出其与电子地图的交点, 同时要求每个交点的横轴X方向和纵轴Y方向上的距离是相等的, Z坐标则取电子地图与网格交点的垂线。其次要对电子地图上交点之间的相邻关系进行确定。电子地图上的交点投影到横轴X方向和纵轴Y方向上面得到一些按照正方形网格分布的离散点, 每个点只能与周围的8个点相邻, 并且每个点之间只计算它与相邻点之间的距离。再次, 将三维空间上的点映射到二维平面上, 并建立邻接。每个相邻点投影之间的记录与空间相邻点之间的距离对应, 这就便可以将计算空间内各相邻点之间的距离问题转化为计算二维图上的点与点之间的距离问题, 如此根据矩阵的行数与列数都为空间中点或者投影点的个数来建立邻接矩阵。邻接矩阵建立之后要寻找最短路径, 对应已经建立邻接矩阵的根据最短路径计算法计算投影面上任意点与点之间的最短距离, 得出的结果就是在电子地图上所选取的对应两点之间在起伏地势上的拟最短路径。最后当实际已知自己地理位置的传感器节点, 便可以依靠横轴X方向和纵轴Y方向来对相近的离散点进行定位, 确定了当前传感器节点对应的离散点和目标传感器节点对应的离散点就可以将实际中传感器节点的地理位置映射到与之相对应的离散点, 得出最短距离。

三、起伏地势上最短路径对下一跳的选择

为了方便计算, 我们在对电子地图采样选点的时候, 大部分取的是有规律的分布均匀的点, 但是当传感器上的节点在起伏的地势上随机分布时, 一定要采取定位策略使节点在最近的采样点上定位。即根据传感器节点上自身的坐标, 去找寻与这个节点相邻的四个采样点, 然后分别求得这四个采样点与目标节点之间的最短距离, 取与目标距离最短的那个点作为这个传感器节点对应的采样点。当多个采样点到目标节点之间的距离一样时, 则可以通过空间欧氏距离的计算方式来进行下一跳的选择。

利用无线传感器网络的过程中, 当源节点S向目标节点D进行数据转发时, 首先获得的是相邻节点的位置, 获取位置后再进行判断, 看一下目标节点是不是在它的邻居节点内。当目标节点在它的邻居节点内时可以直接发送数据, 如果目标节点不在它的邻居节点内便要采用上面描述的四个采样点选最短的方式进行选择。如果同时存在多个邻居节点对应到该采样点的情形, 那么就可以利用空间欧氏距离的方式对下一跳进行选择, 如果不这样就应该选取与这一采样点对应的邻居节点作为下一跳。如此不断的重复, 一直将数据传到目标节点。

此外, 理想的传感器节点应该是均匀分布的, 有着同电子地图的采样点一样的X坐标和Y坐标轴, 并且可以在电子地图上获取Z坐标。采用这种理想的分布方式, 既可以在路由的过程中可以避免定位和采样点带来的误差, 又可以有意识的避开有较大起伏的地势, 进行理想的路径选择。

四、小结

文章基于实际情况下无线传感网络分布的地势环境, 提出伪三维地理位置网络的路由算法, 并对其进行分析, 其核心思想是运用起伏地势上的拟最短路径取代过去一直运用的空间欧氏距离, 使路由选择能够更贴近现实。伪三维地理位置网络的路由算法对建立在有起伏路上的无线传感器网络而言, 用上文描述的以起伏地势上的最短路径代替空间距离, 一方面可以有效的减少路由的跳数, 另一方面也可以减少能量的损耗, 延长网络的生存时间。

参考文献

[1]张衡阳, 李莹莹;基于地理位置的无线传感器网络路由协议研究进展[J];计算机应用研究;2008-01

[2]林观康, 程良伦;基于地理信息静态分簇的无线传感器网络路由算法[J];计算机应用与软件;2011-02

地理位置路由 篇3

发布/订阅系统[1]在信息生成和接受两者间具有弱耦合、非同步及多点通信的特点,成为很多网络应用的一种重要组件[2],尤其适用于具有动态拓扑特性的移动Ad hoc(自组织)网络。

针对移动Ad hoc网络中基于位置的发布/订阅路由算法,目前已有一些研究。文献[3]提出了一种STEAM(基于附近和分布式过滤的区域事件转发群组算法),在该算法中,订阅节点只订阅附近发布方的内容。这导致只能在发布内容时分发内容给目标区域内的节点,限制了内容的发布与匹配。文献[4]提出了INGEO(基于内部地理位置的路由协议)算法,该算法以速度位移矢量来重新定位移动的订阅节点。文献[5]提出了基于位置的自适应路由算法,在合理的区域内实现内容的分发和匹配。但该算法较少考虑节点的移动性,以节点的请求频次计算的结果因节点频繁移动而不准确,并且所有节点的区域频繁更新所带来的开销很大。文献[6]提出的Courier算法(基于位置感知的有效群组通信算法),类似源路由算法LGS(以位置为导向的小区多播生成树算法)[7],订阅节点将速度位置信息嵌在Hello包内,再转发至内容发布方,依靠订阅节点及时更新信息,发布方计算发布内容所需转发的路径转发树和受限泛洪区域的大小,实现目标区域节点的内容匹配。基于上述分析,以Courier算法为代表的基于位置感知的路由算法对于位置速度信息的更新要求频繁,且Hello包存在冗余广播问题。本文在文献[6]的基础上提出一种EPRLM(基于位置感知的移动Ad hoc网络高效发布/订阅路由算法)。本文的主要贡献有:(1)在内容消息接收过程中,节点通过计算自身是否移出区域来判断是否更新位置速度信息,从而减少了不必要的控制数据包转发;(2)订阅节点的回应包可以捎带之后的Hello包信息,减少了冗余Hello包的广播。

1 网络模型与问题描述

1.1 网络模型

定义1(节点转发区域)如图1所示。在t1时刻,源节点srcA收到订阅节点memB的位置更新信息;在t2时刻(t2>t1),srcA发送数据给memB;memB在t1~t2这个时间段内能够移动的范围是以srcA存储的memB位置为中心、半径为VB(t2-t1)的圆形区域,即NFZ(节点转发区域)。

定义2(群组转发区域)如图2所示。srcA发布内容给多个订阅节点时,需要优化转发区域。首先srcA降序排列订阅节点的NFZ大小,然后判断NFZC和NFZB的关系。如果二者相交,并且半角α1小于阈值[6],则合并两区域;如果两区域中的一个区域包含另一区域,则将其合并为一个区域;如果两区域并不包含或者相交,但是半角α1小于阈值[6],则合并两区域。至此,形成GFZ(群组转发区域)。

定义3(欧几里德Steiner树)如图3所示。A、B和C为网络中的3个节点,S为欧几里德Steiner节点(即网络中的虚拟中继节点)。节点A发送给B和C的总的开销,可以经过S(实际中也可以是S的附近节点)再分别分发至B和C。而对于多个订阅节点的GFZ,此时可以通过迭代计算出适合的欧几里德Steiner树。

1.2 问题描述

以Courier算法为代表的基于位置感知的路由算法存在以下问题:

(1)位置速度信息需要通过Hello消息频繁更新。而在节点没有离开NFZ时,上次更新的信息依然可以将内容转发至此区域,并实现区域泛洪,使得节点收到此发布内容。此时,更新导致冗余开销。

(2)在订阅节点回应源节点的请求包(Join Request)时,回应包(Join Reply)和之后一次的Hello包所起作用重复,产生冗余。

2 EPRLM

EPRLM采用基于NFZ的信息更新以及Join Reply包的捎带等新机制,从而达到内容消息与订阅节点的高效匹配,降低控制开销的效果。

2.1 EPRLM新机制

2.1.1 基于NFZ的信息更新机制

Courier算法只考虑了订阅节点位置速度信息改变后,通过Hello消息通知发布节点。但是,如果订阅节点在接收内容消息时并没有移出NFZ,此时内容消息已经在转发的路径上,那么此次位置速度信息的更新就不会起作用,发布节点基于上次的位置速度信息依然可以将消息泛洪至订阅节点。因此,订阅节点在接收内容消息时,位置速度信息如果发生变更,首先判断订阅节点自身是否移出上次位置速度信息更新到目前为止的NFZ。如果已经移出,则通过Hello包更新位置速度信息,否则,在位置速度信息失效前不再更新。

通过基于NFZ的信息更新,可以减少频繁转发至发布节点的信息更新Hello包,从而减少网络的控制开销,减缓网络的通信负荷。

2.1.2 Join Reply包的捎带机制

在Courier原算法中,订阅节点收到发布节点的请求包Join Request时,需要回应Join Reply包;并且在回应包到达发布节点的过程中,对应路径上的节点须转发此消息。此后,产生或转发回应包的节点需要广播Hello包告知邻居节点自己的状态信息,而该Hello包的信息与先前回应包的信息重合,产生冗余。本算法提出了Join Reply包的捎带机制,改变Join Reply包的消息类型并在转发时广播此消息,此时除转发至发布节点路径上的节点需要继续广播此包外,其余节点收到Join Reply包后将其当作Hello包提取信息。

Join Reply包的捎带机制将订阅节点至发布节点路径上所有节点的一次Hello包广播的信息由Join Reply包捎带完成,降低了冗余控制开销,减少了信道资源的竞争。

2.2 算法操作

EPRLM的主要操作步骤如下:

(1)发布节点周期性全网泛洪Join Request包(包含发布节点ID、位置及内容摘要等信息)。

(2)节点收到Join Request包后,如需要发布节点所拥有的内容,则回复Join Reply包(包含该节点ID、位置和速度等信息)并在转发时广播此消息,此时除转发至发布节点路径上的节点需要继续广播此包外,其余节点收到Join Reply包后将其当作Hello包提取信息。

(3)节点收到Join Request包后,如不需要发布节点所拥有的内容,则继续广播此消息。

(4)发布节点在发布内容时,首先根据订阅节点的位置速度信息计算各个订阅节点的NFZ,再生成GFZ,然后依次迭代计算出抽象的欧几里德Steiner树,并依此树的虚拟路径分发内容消息至订阅节点。

(5)订阅节点的位置速度发生变化需要更新时,首先判断订阅节点自身是否移出上次位置速度信息更新到目前为止的NFZ。如果已经移出,则通过Hello包更新位置速度信息;否则,在位置速度信息失效前不再更新。

3 仿真

本文使用OPNET[8]作为仿真软件平台,选取LGS算法和Courier算法作为与EPRLM进行比较的对象,在相同仿真条件下(仿真参数设置如表1所示)分析比较3种算法的消息传送成功率、消息端到端时延、内容消息转发次数和控制包开销等性能。其中,实际的消息端到端时延等于平均跳数乘以每一跳的平均转发时间,而每一跳的平均转发时间依赖于具体的硬件条件;内容消息转发次数为内容消息成功到达所有订阅节点所需转发的总次数。

(1)消息传送成功率

3种算法的消息传送成功率仿真结果如表2所示。从表中可以看出,EPRLM的消息传送成功率高于Courier和LGS算法,这是因为基于NFZ的信息更新机制减少了Hello包的产生和转发,而且此时减少的Hello包原本是沿着与内容消息传播的反方向路径转发的,由此减少了冲突和资源竞争。同样,Join Reply包的捎带机制也降低了信道中资源的竞争。

(2)消息端到端时延

3种算法的消息端到端时延仿真结果如图4所示。由图可见,EPRLM的消息端到端时延低于Courier和LGS算法,这是因为EPRLM中基于NFZ的位置信息更新机制减少了Hello包的数量,降低了与反方向路径内容消息的转发而产生的信道和资源竞争,减少了同一路径上转发消息的负担;另外,Join Reply包的捎带机制同样降低了信道中资源的竞争。平均跳数随网络中节点数目增加而减少的原因是:在密集网络中发现源节点到目的节点之间最短路径的概率会更高一些。

(3)内容消息转发次数

在不同节点数时3种算法的内容消息转发次数比较如图5所示。从图中可以看出,随着节点数的增多,3种算法的内容消息转发次数都是递增的。EPRLM的内容消息转发次数比其他两种算法低,主要是因为EPRLM的两种新机制减少了Hello包的产生和转发,减少了信道资源的竞争和冲突,因而减少了内容消息转发次数。

(4)控制包开销

图6给出了不同节点数下3种算法的控制包开销的比较。由图可见,相对于Courier和LGS算法,EPRLM在不同节点数下的控制包开销都是最少的,这是因为基于NFZ的位置信息更新机制和Join Reply包的捎带机制都减少了Hello包的产生和转发,且减少的冲突和资源竞争带来的控制包开销的降低也很可观。

4 结束语

针对结合地理位置信息的发布/订阅内容路由算法中节点频繁更新位置信息和控制包存在冗余的问题,本文提出了EPRLM。仿真验证表明,与Courier和LGS算法相比,EPRLM能够很好地提高网络中节点的消息传送成功率,并降低网络吞吐量,减少消息时延和发送次数,降低控制开销。

参考文献

[1]Carzaniga A,Rosenblum D S,Wolf A L.Design and evaluation of a widearea event notification service[J].ACM Transactions on Computer Systems,2001,19(3):332-383.

[2]Rezende G C,Rocha B,Loureiro A.Publish/subscribe architecture for mobile ad hoc networks[C]//Proc of the ACM Symposium on Applied Computing2008.Fortaleza,Brazil:ACM,2008:1913-1917.

[3]Rene M,Vinny C.On event-based middleware for location-aware mobile applications[C]//IEEE Transactions on Software Engineering 2010.Los Alamitos:IEEE,2010,36(3):409-430.

[4]Hai L,Houda L.INGEO:indoor geographic routing protocol for MANETs[C]//In Proceedings of the 3rd International Conference on Mobile Computing and Ubiquitous Networking 2006.San Jose:ACM,2006:224-229.

[5]Holzer A,Eugster P,Garbinato B.ALPS-Adaptive Location-based Publish/Subscribe[J].Computer Networks,2012,56(12):2949-2962.

[6]Mitra P,Poellabauer C.Efficient group communications in location aware mobile ad-hoc networks[J].Pervasive and Mobile Computing,2012,(8):229-248.

[7]Chen K,Nahrstedt K.Effective location-guided tree construction algorithms for small group multicast in MANET[C]//In Proceedings of the 21st Annual Joint Conference of the IEEE Computer and Communications Societies 2002.New York:IEEE,2002:1180-1189.

地理位置路由 篇4

Ad hoc网络是由一组带有无线收发装置的移动终端组成的多跳临时自治系统。路由协议一直是Ad hoc网络研究的重点。根据不同的路由策略,Ad hoc网络的路由协议可以分为基于拓扑的路由协议和基于位置的路由协议。与传统的基于拓扑的路由协议相比,基于位置的路由协议利用节点的位置信息来指导包的转发,其基本思想是利用节点的位置信息来选择下一跳,将包向目的节点的方向上进行转发,不需要对路由进行建立和维持,具有开销小、高可扩展性、高性能等优点。为使位置信息得以有效利用,基于位置的路由协议的研究有两个要点:一是假设源节点在发消息时已知目的节点的位置信息的基础上,设计出基于位置的路由协议;二是位置信息服务的实用性,位置信息服务需要记录节点位置信息的实时更新情况,以应答位置查询。

2 基于位置的路由协议与比较

基于位置的路由协议主要有:DREAM、基于定额的位置信息服务GL、基于家乡区域的位置信息服务SLURP,以及基于位置的路由协议LAR、GPSR、GRA、GEDIR、ZHLS、GRID、Geo TORA、GDSR和GZRP等。

(1)协议对位置信息的利用程度

Ad hoc网络的路由协议包括3个部分:查找路由、转发数据分组、路由维护。根据对位置信息的利用程度,可以将这些协议分为部分的和完全基于位置信息的路由协议。在此介绍的几种路由协议中,只有GRID仅根据节点位置信息就能解决路由协议的3个问题,因此,它是完全基于位置信息的路由协议。其他协议仅利用位置信息解决其中部分问题。

(2)协议间比较

影响位置的路由协议性能的两个重要因素是网络规模和网络拓扑变化程度。位置辅助的路由协议和基于位置信息的路由协议差别在于是否保存路由表。当网络规模很大时,前者将增加节点的存储开销。若网络拓扑变化频繁,位置辅助的路由协议需要不停地发送RREQ查找路由,这会引入过多的找路时延和开销。同时,链路变化快,导致很多数据分组在传输过程中丢失。而对于基于位置信息的路由协议,节点根据自己掌握的当前位置信息转发数据分组,不存在事先找路的问题,没有找路时延。此外,基于位置信息的路由协议只需要知道本地的拓扑信息,即便网络拓扑变化频繁时,也可根据本地拓扑信息找到最新的有效路径。LAR在DSR中用地理位置信息限制路由查找分组广播的范围,它可用于其他采用泛洪找路的协议(比如AODV)中,以降低开销。LAR可根据实际定义相应的期望域和寻找域,其本质仍为反应式路由,当网络变化快时,将频繁修复链路,但不适合网络拓扑变化过快的环境。DREAM能保证无路由环路。每次转发都将分组发送给目的节点方向的多个节点,类似于提供了到目的节点的多条路径,且某条链路上分组的丢失不会影响其它链路上的分组,鲁棒性好,DREAM中的控制分组只有位置更新分组和ACK分组,且分组携带信息较少;更重要的是,节点根据自己的移动速度独立确定发送位置更新分组的周期,且只有移动节点才发送位置更新分组,最大限度地节省了控制分组占用带宽。DREAM虽然限制了到目的节点的泛洪范围,但其本质还是基于泛洪的。因此,DREAM不适用于节点数目多、数据量大的网络。Terminodes和GRID属于分层路由,适合于大规模网络。在Terminodes中,节点同时保存多条到某个节点的anchor路径,可适应高速变化的网络拓扑;同时,在多条独立的路由上传输数据分组可均衡网络中的流量,降低网络拥塞发生的可能性。GRID中的路由生存时间较长,路由对节点的移动不太敏感。另外,路由控制分组的开销与网络中节点密度关系不大。相反,在其他路由协议(如DSR,AODV,LAR,ZRP等)中,一旦路径上的任一中间节点移动,就可能导致整条路由失败。

3 Ad hoc网络位置信息服务

基于位置的路由协议研究中的一个主要挑战为,如何得知目的节点的准确位置信息。一些协议(如,DREAM和LAR)在协议中包含了位置信息交换的过程,而大部分基于位置的路由协议假设有一个独立的机制为节点提供位置信息。比如所有地理转发路由协议都假设目的节点的位置为已知。实际上,在这些协议的仿真过程中,位置信息不产生任何开销的提供给了全部节点。这样会导致仿真结果显示包含了对目的节点位置信息维持过程的某些协议的开销要更高,如DREAM协议。因此,对这种独立的位置交换机制,即位置信息服务的研究是对基于位置的路由协议的研究过程中的重要组成部分。

目前已有的Ad hoc网络位置信息服务可以被分为三种类型:反应式位置系统,先验式位置数据库系统和先验式位置分发系统。

3.1 反应式位置系统(RLS)

反应式位置服务系统基于需要对位置进行查询。反应式位置服务系统可以归为all-for-some方式,网络中的所有节点保持所需的某些其它节点的位置信息。反应式位置服务可以分为RLS和RLS’。

在RLS协议中,当移动节点需要另一个节点的位置,且该位置信息未知时,发起节点首先向邻居节点询问所需节点的位置信息。当邻居节点在一定时间内未对其有所反馈时,节点将全网泛洪位置查询包。与RLS相类似的按需协议有LAR,DSR和LOTAR等。

3.2 先验式位置数据库系统

先验式位置数据库系统可以分为两种类型:家乡区域型位置服务和基于定额的位置服务。在先验式位置数据库系统中,网络中的一些特定节点充当其它一些特定节点的位置数据库。节点移动至一个新的位置时将位置信息更新给该节点的位置数据库节点,即位置数据库服务器;当需要寻找节点的位置时,对该节点位置数据库服务器查询其所在位置。大部分位置数据库系统可以称为all-for-some模式。即网络中所有节点都作为数据库服务器,并且每个数据库服务器维持网络中一些特定节点的位置信息。

3.3 先验式位置分发系统

在先验式位置分发系统中,网络中所有节点都定期接收一个指定节点的位置更新。即,在某个指定节点的位置信息表中,所有节点的位置信息都是有效的。先验式位置分发系统可以称之为all-for-all方式,网络中每个节点维持所有其它节点的位置信息。

先验式位置分发系统可以分为六类:DLS(DREAM位置服务),SLS(简单位置服务),LEAP(图例交换与增加协议),蚁群算法,地理区域概要服务,航位推测法(位置预测技术)。

DREAM位置服务(DLS)由DREAM协议作者提出。每个更新位置信息表的位置信息包(LP)包含源节点的调整,这些调整基于源节点的速度和LP包传输的时间等。当Ad hoc网络中的每个节点以指定速率传输LP包给较近的节点,并以较低速率传递给较远节点。移动节点传输LP包的速率取决于从它最近一次位置更新点移动的距离。

DREAM通过对LP包传输的频率及长度对位置信息的精确程度进行控制。

近距离LP包传输:

远距离LP包传输:每个近距离LP包发一个远距离LP包,或每秒发送一个远距离LP包,

其中,为移动节点传输范围,为移动节点平均速率,为比例因子。在DLS中,较近节点为1跳邻居节点;更新至较远节点的LP包全网节点更新,包括较近节点。

4 结论

基于位置的Ad hoc网络路由协议一般要求每个节点都必须配有一个可以确定自身位置的定位系统。各个节点周期性地广播Hello包,将自己的当前状态、准确的地理位置告知其通信半径内的邻节点。这样,每个节点都存有一张表,用来记录邻节点的地理位置信息。在进行数据传输之前,源节点需要知道目的节点的地理位置,并把这个信息写入数据包头部,目的节点地理位置的确定由位置信息服务来完成,源节点首先更新该信息,然后根据某种数据包传输策略选择一个合适的邻节点进行数据转发,直至到达目的节点完成整个传输过程。为维持位置信息的实时性和有效性,基于位置的Ad hoc网络路由协议需要有位置信息服务来辅助其完成数据包的转发过程。为此,本为主要介绍了现有基于位置的路由协议以及位置信息服务的研究情况。

基于位置的路由算法既不需要建立、也不需要维护路由,因此通常认为基于位置的路由具有高度的扩展性,对于经常的拓扑变化也具有较好的鲁棒性。移动自组织网络中的节点通常采用便携式的电池供电,由于它常处于比较恶劣的工作环境,所以它的能量资源、计算能力和带宽都非常有限。这就决定了移动自组织网络协议的设计应以能源有效性为研究目标。在设计基于位置的Ad hoc网路路由协议时,协议的开销应成为衡量位置路由协议优劣的重要因素。

参考文献

[1]R.Jain,A.Puri,and R.Sengupta.Geographical routing using partial information for wireless ad hoc networks.IEEE Personal Communications,pp.48-57,February2001.

地理位置路由 篇5

在国内外研究人员的积极努力下, 针对无线传感器网络节点能量有限的问题, 提出了许多能量高效的路由协议, 其中地理路由协议由于简单和良好的扩展性备受关注[1]。地理路由协议, 以地理信息为基础来有效地进行路由选择, 在路由建立的过程中, 某一节点不需要知道整个网络中的所有节点的地理位置信息, 只知道其邻居节点以及目标节点的地理位置信息的;通过计算其诸多邻居节点和目标节点的距离来选择下一跳节点;这样就将路由选择的范围只限定在邻居节点范围, 从而大大降低了网络流量, 节约电池电量[2]。其中, 典型的地理位置路由协议为无状态的贪婪周边路由协议GPSR[3]。本文将结合无线网络能耗模型和邻居节点数量, 基于GPSR路由协议提出了一种自适应的三维地理路由机制。

一、能耗模型

为了研究无线传感器网络, Heinzelman提出First Order射频模型[6]。发射机和接收机工作时的电路损耗为Eelec=50n J/b it, 发射机发射放大器损耗为着amp=100p J/b it/m2。对于发射机来说, 发送k bit信息, 传输距离为d, 消耗能量为:Es (k, d) =Eelec (k) +Eamp (k, d) , 则有:Es (k, d) =Eelec*k+着amp*k*d2;对于接收机, 接收kbit信息, 消耗能量为:ER (k, d) =Eelec (k) =Eelec*k。对于传感器节点来说, 发送和接收的能耗都和数据包的大小有关, 降低数据包发送的频率, 减小数据包的长度可以有效的降低单个节点的能耗。

二、基于邻居数量的自适应三维地理路由策略

2.1能耗分析与平衡机制

因为无线传感器网络是以数据为中心的, 传感信息的采集有着规律性, 这里可以假设节点数据采集的时间间隔为Ts, 节点更新状态信息的时间间隔为TM。

另外, 由于无线节点存储空间有限, 因此进一步考虑能量平衡机制是必要的[7]。设无线节点仅能保存窗口时间Twin时间段内的数据量记录, 用指数加权移动平均法来衡量一个节点的数据量:P (i) = (1-琢) P (i) +琢Pwin (i) , 式中Pwin (i) 表示Twin时间内数据量多少, 琢为权重因子, 反映了节点数据量的实时变化程度。P (i) 表示节点i在网络中对于数据包传输的重要性, P (i) 越大, 就需要为节点i预留更多的能量, 以防止节点失效造成数据包传输的能耗增加。用下面的公式来表述节点i的能耗平衡情况:W (i) =E (i) /P (i) , 选择W (i) 最大的节点u作为下一跳转发节点。

2.2基于邻居数量的自适应地理路由策略

(a) 邻居节点数目与自适应转发选择机制

当网络中的一些节点以为电量耗完或其他原因失效, 节点密度变得稀疏, 就开始采用基于区域的转发策略。每个节点都维护着一个邻居节点集合N (i) , 每当收到邻居节点的Hello信息, 节点都会自动的更新这张表, 与此同时更新邻居度:

(b) 基于邻居数量的自适应地理路由算法

当无线传感网络启动, 各节点的位置信息初始化并且稳定后。开始进行数据包的接发工作。下面给出基于邻居数量的自适应地理路由策略, 源节点S发送信息给目标节点D, 如图1所示, 并以此为顶点建立一个次极小椭球, 并绕SD旋转成为次极小椭球。算法的具体执行如下:

Step1:初始化, i=S, N (i) 。

Step2:i查看自己的邻居节点, 如果D是自己的邻居节点, 直接发送给D。

三、结论

本文针对传感器节点能量的有限性, 综合考虑了能量与通信量平衡的策略, 并结合邻居节点数量和次极小椭球机制, 提出了一种基于邻居数量的自适应三维地理路由选择方法。该方法对于研究更加高效的无线传感器网络节能机制和路由策略, 延长网络生命周期, 具有重要的现实意义。

参考文献

[1]杨冕, 秦前清.基于无线传感器网络的路由协议[J].计算机工程与应用, 2004, 32 (3) :130-131.

[2]张衡阳, 李莹莹, 刘云辉.基于地理位置的无线传感器网络路由协议研究进展倡[J].计算机应用研究, 2008, 25 (1) .

[3]Karp B, Kung H T.GPSR:Greedy Perimeter Stateless Routing for wireless networks[C].In:MOBICOM 2000, 2000.243-254.

[6]Heinzelman W R, Chandrakasan A, Balakrishnan H.Energy-efficient communication protocol for wireless microsensor networks[C].In:33rd Annual Hawaii International Conference on System Sciences, 2000.10-12.

[7]陈衡, 钱德沛, 伍卫国, 等.传感器网络基于邻居信息量化的能量平衡路由[J].西安交通大学学报, 2012, 46 (4) :1-6.

地理位置路由 篇6

车联网VANET (Vehicular Ad Hoc Networks) , 最前沿的物联网络应用, 尤其是车辆移动网络技术, 实现过程是通过安装在车辆上的通信设备, 电子标签等, 实现车辆信息的网络交互, 来提升车辆和道路的效率或者安全水平。在VANET网络中, 各个网络节点通常部署于汽车之上, 而且汽车的运动特性需要收到道路条件的限制。这些特性使得车辆的运动轨迹在某种程度上能够进行预测, 从而使得VANET网络显著区别于普通的移动Ad Hoc网络中节点能够随机运动。相应的在VANET网络路由协议的设计中, 若能够充分利用这些信息, 则能够为路由协议提供一些优化[1,2]。因此在本文的研究中, 将节点的地理和交通信息引入到VANET网络路由协议的设计中, 基于这两方面的信息对路由协议进行一定的优化。

1 路由过程设计分析

1.1 路由发现

当一个网络节点请求发起通信, 源节点首先要看节点存在于路由表中的路由条目中的目标。根据目的节点的位置寻求信息确认消息记录在传输路径如果条目存在, 中间节点接收到带有标准的传输过程中的查询消息的方法, 直到目的节点接收到该消息, 该消息根据您的确认立即返回路径信息可用消息, 如果消息没有达到TTL的目的节点应该被丢弃。如果在路由表中的条目的源节点不立即发出向目的地节点, 或为时间 (0.5秒) , 在一定期间内没有收到返回确认消息以激活路由发现过程。

路由查找过程中各个节点将有各种不同的操作行为。源节点发起RREQ消息, 并填写在背后的目的地址字段的位置的消息的地址, 并一路上扬的广播消息的初始化。经过一个中间节点收到RREQ消息, 以确定该组根据消息内容是否被覆盖。不是的话可以丢弃该消息, 另一种是更新有关消息的路由信息, 包括锚定序列和路径的质量分数, 只有当此中间节点位于某个锚点范围内, 并且锚不被RREQ记录加入RREQ分组, 当信息被更新之前经过的中间节点将播出这一消息。

1.2 路由决策与返回

如果接收节点接收到使用它作为整个系统RREQ消息路由决策阶段的第一个信息。首先, 目标节点运行的等待时间 (0.5秒) , 以接收相同的源节点是另一种方式来传递的RREQ消息, 目的节点是第一个多路中最高得分的计算选择作为传输路径方式, 然后通过预测得到自己所驶向的锚点剪接的最优路径的完整路径, 形成以填充在为正确的结果, 源节点在新的RREP头被选择作为相邻节点的位置按照最近邻贪婪转发到之间的距离的原理提前转发出去。

当一个中间节点接收到RREP消息中提取从锚定到RREP序列作为靶附着点贪婪转发应该被发送到的RREP消息, 直到在中间的当前节点, 更换锚定序列是锚定连接点到新的目标。源节点接收到RREP消息, 并提取从路径的信息发送到目的地节点, 该信息被存储在路由表中。当数据传输后, 源节点从路由表中的目标的查询的信息可以开始。

2 路由协议性能仿真

2.1 仿真参数的设置考虑

为了对本文所涉及的协议的性能进行检验, 因此我们在NS2仿真平台中构造相应的方针模型, 同时为了使仿真结果更加逼近于现场的实际应用效果, 设定建筑穿透损耗的模型的损耗概率p为30%, 即发射的无线信号有30%的概率会被周围的建筑给遮挡, 具体仿真中, 路由协议则是考虑基于GPSR新设计, 传输模型为TwoRayGround (双线大地) , MAC层协议为IEEE 802.11, 运动模型为基于受限连通域节点移动模型;分组发送率为5 packets/s;平均运动速度为5、10、15、20、25m/s; 仿真时间为900s。

2.2 仿真结果及分析

为了评估本文所设计的路由协议在不同场景中的性能, 在仿真中分别针对目的节点移动和目的节点静止两种场景分别进行了仿真实验。

2.2.1 目的节点移动场景

在仿真中, 我们主要关注在不同网络节点数目情况下, 协议的各项指标的性能。因此方针中我们以40个节点为间隔对80~320个节点数量范围内的网络协议的性能进行评估。

从显示的性能指标的关系, 目标节点的运动的协议的节点数量, 所呈现的数据上面GPSR新的协议。GPSR临时策略可以通过将节点划分成跨越网络边界的数据包的帮助。所述协议数据随车辆及减少延迟的数目的两个端部。可以看出新协议的物理层数据发送总量大于GPSR, 这是由于新协议在找不到合适的下一跳节点时, 使用探寻机制发送探寻数据包而使物理层发送的数据量增多。

2.2.2 目的节点静止场景

从仿真结果可以看出, 新协议在目的节点固定的情况系统性能比GPSR略差。即新协议更适合处理目的节点移动的情况, 即更适合真实的城市车辆运动场景应用。截取下图描述目的节点静止情况下协议相关性能指标与节点数的关系。

3 结语

对现有的路由算法进行改进, 实时的道路交通信息和车辆移动位置预测信息引入到路由选择策略中, 从而对路由机制进行改进。从数据包递交率、端到端延迟、平均跳数以及物理层发送总数据量等几项重要指标对路由机制的性能进行分析和对比, 新的路由协议具有更高的数据递交率及信息交换速度, 更适合城市场景下车辆运动时的应用。

参考文献

[1]Chisalita I, Shahmehri N.A Peer-to-Peer Approach for Vehicular Communication for Support ofTraffic Safety Applications[C].In:Proc.of the IEEE 5th International Conference on IntelligentTransportation Systems.Singapore.2002:336-341.

[2]杨东凯, 吴今培, 张其善.智能交通系统 (ITS) 的发展及其模型化研究[J].北京航空航天大学学报, 2000, 26 (1) :22-25.

[3]孔驰.智能交通系统中基于DSR协议的无线通讯[D].湖北:武汉理工大学控制理论与控制工程, 2007.5.

地理位置路由 篇7

由于WSN中节点资源异构性、通信链路不对称等因素，导致数据链路容易发生断裂。为了保证可靠的数据传输，多径路由机制被广泛应用，其利用数据链路冗余方式传输数据，有效地提高了通信可靠性[3]。

1 相关工作

文献[4]描述了一种基于代理的多径路由(Agent Based Multipath Routing,ABMR)发现方案。ABMR考虑了传感器节点的一些参数，如剩余能量、距离、信道可靠性来计算从源节点到Sink节点的多径路由。从源节点触发移动代理，在传感参数的基础上，在网络中移动直到到达目的节点。每个节点上的移动代理都会移动到邻居节点来收集信息，用来在邻居节点中选择出最好的节点。一旦从邻居中选择出了最好节点，则这个最好邻居节点触发自身的移动代理到它的邻居，重复执行上述任务，选择最佳节点直到到达Sink节点。Sink节点根据代理带来的路径信息来计算多径路由。然而其存在着一些缺陷，要计算多径路由，源节点需要同时发出多个代理，ABMR中的代理从源节点到目的节点的过程中，要收集很多节点的信息，几乎遍历了整个网络。这就导致大量的额外能量消耗。

对于一些现有的多径路由技术存在的缺点，如在路径发现和路径建立过程中缺乏智能，中继节点选择机制的灵活性较小，计算多径路由的能量消耗较大，对关键信息的传输缺乏鲁棒性机制等。本文提出一种基于位置感知的代理的智能多径路由发现机制(Location aware and Agent Based Multipath Routing,LABMR)。利用传感器位置信息寻找特殊中间节点来构建多径路由，并触发代理在路径上移动，来收集多径路由的局部拓扑结构信息，Sink节点根据这些信息，计算出最优不相交路径。并根据事件重要性，选择一条或多条路径传输数据。

提出的LABMP和ABMR的根本区别如下:1)LABMP只使用局部拓扑信息来寻找从源到Sink节点的多条路径;2)建立了完善的代理机构，Sink节点能够根据代理收集的信息寻找最优路径，可靠传输关键信息;3)使用基于GPS(全球定位系统)的位置信息，能够更准确地计算多条路径。通过实验，与ABMR方法相比，LABMP在数据包投递率、能量消耗、额外开销和延迟方面具有更好的性能。

传感器节点位置信息的获取是通过内置GPS模块实现。为了尽可能减少成本，本文只在少量传感器节点上使用GPS定位模块，其他节点通过节点之间的通信来估计自己的位置。相比于GPS模块的成本，位置信息对整体网络性能更具价值。

2 提出的LABMR方案

2.1 相关概念

提出的LABMP方案中的主要名词如下:

事件节点(Event node)，即在事件影响区域，用来检测事件的传感器节点。事件节点能够触发到Sink节点的路由发现过程。节点会向其他邻居节点宣布自己为一个事件节点，防止其他节点去事件影响区域重复检测事件[5]。

中点(Midpoint)，是连接事件节点和Sink节点直线(X轴)上的中间位置点。若不存在严格中点，可将离中间位置最近的节点为中点。

特殊中间节点(Special intermediate nodes)，在事件和Sink节点之间，近似位于中点垂直上方和下方的节点。

上升角度(Rising Angle)，是指事件节点和X轴上方的特殊中间节点之间的连线与X轴的角度。

下降角度(Falling angle)，是指事件节点和X轴下方的特殊中间节点之间的连线与X轴的角度。

跳数(Hop count)，是指事件节点到Sink节点路径的中继节点总数。

2.2 网络环境

本文中的网络环境如图1所示，由多个具有数据感知能力的微小传感器节点和Sink节点组成。当传感器节点检测到一个事件时，它们会将数据通过无线多跳通信方式发送到Sink节点[6]。本文假设网络中的所有节点(传感器节点和Sink节点)都是静态的，且在初始部署阶段，所有的传感器节点具有相同的能量。在本文所提出的LABMP中，假设只有少量传感器节点具有GPS功能，其余节点根据具有GPS节点的位置，使用定位算法来估算自己的位置，以此来降低系统的成本。每个传感器节点都具有一个代理机构。

2.3 多径路由发现

2.3.1 路径参数

本节描述了本文方案中所用到的路径参数，包括链接和路径的效率、能量比率和跳距离因子。

设C是离散信道的容量，B是信道的比特率，Ei是在链路i上传输1 bit数据消耗的总能量，SNR是信噪比。信道i的容量计算公式为[7]

设定Et为1 bit数据每传输d距离所消耗的能量，则Ei可用下式计算

链接效率(Leffi)计算公式为

路径效率(Peff)为整条路径上的n个链接效率的最低值，表达式如

路径能量比率(Eeff)为每条从事件节点到Sink节点路径中节点最小剩余能量和最大剩余能量之比。设定ER(1)到ER(n)为路径上n个中间节点的剩余能量。路径上n个节点的最小(ERmin)和最大(ERmax)剩余能量表达式如式(5)，式(6)所示，Eeff表达式如式(7)所示。

一条路径的跳距离因子(Hdf)表达式如式(8)所示，其中，事件节点到Sink节点路径的欧式距离为Pd，路径上跳数的总和为Phc

2.3.2 局部拓扑结构发现

图2显示了从事件节点到Sink节点的多径局部拓扑结构发现过程。S1和S7分别是事件节点和Sink节点。以S1和S7的直线连接为X轴，S2,S4和S6节点近似位于X轴上。根据GPS位置信息，设定以(xe,ye)和(xs,ys)分别作为事件节点和Sink节点的位置坐标，根据式(9)、式(10)找出S1到S7直线上的中间位置点(中点)为节点S4，其坐标为(xmid,ymid)。

当中点确定后，在中点位置垂直X轴上，寻找2个特殊中间节点S11和S12。以(x'mid,y'mid)和(x″mid,y″mid)分别作为S11和S12的位置，设定x'mid=xmid且x″mid=xmid,y'mid和y″mid的计算公式分别为

式中:n和R分别是中点的节点度和传输范围。

每个节点处的上升和下降的角度计算公式如

式中:θr1是上升角度，同理可得下降角度θf1表达式为

在下面的描述中，代理会在这3条路径上移动只到Sink节点，以此来收集路径节点和邻居的参数信息，这些信息将被Sink节点用来构建局部拓扑结构和发现多路径。

2.4 代理机构

本文方案中，为路径发现和路径计算设置了一组静态和动态代理，并为普通传感器节点和Sink节点的构建代理机构。本节介绍了提出的代理机构和相应的代理。

2.4.1 普通节点代理机构

本文中普通节点代理机构是由节点管理者代理(NMA)、路径发现代理(PDA)和多径路由知识库(MKRB)组成，其中NMA是静态代理，PDA是移动代理。节点代理机构和它们之间的相互作用如图3所示。

节点管理者代理(NMA):是一个静态代理，用来检测可有信息，如信号强度、传输范围、剩余能量，并计算链路效率，最小和最大剩余能量比和跳距离等参数。当检测到事件时，NMA开始根据位置信息，计算中点和特殊中间节点(SINs)。然后，NMA创建PDA和MKRB，使用MKRB更新路径信息。运行过程中，NMA会根据节点剩余能量，使节点进入睡眠或活动模式。NMA会和邻居节点的NMA进行交流，以此得到邻居节点信息，如节点ID、位置，并更新MKRB。

路径发现代理(PDA):一旦检测到事件，事件节点的NMA会创建一个事件节点的PDA(移动代理)，并复制成3个。3个PDA在3条路径上移动，第1个PDA几乎在X轴上移动，直到到达Sink节点;第2个PDA先以上升角度移动，到达SIN节点后，再以下降角度迁移，直到到达Sink节点。第3个PDA先以下降角度移动，到达SIN节点后以上升角度迁移。最后，PADs将收集的局部拓扑信息传递给Sink节点。

多径路由知识库(MKRB):是基于网络路径相关信息建立的知识库，通过代理可以读取和更新。它包括节点ID、活动/睡眠模式、剩余能量、邻居节点之间的距离、Sink节点ID、SINs的ID、Sink节点和SINs的位置信息、事件感知时间、信号强度、可用带宽、自身和Sink节点之间的距离、上升和下降的角度等信息。它也保存着邻居节点的信息，如节点的ID和位置信息。

2.4.2 Sink节点代理机构

Sink节点代理机构由Sink管理者代理(SMA)、路径设置代理(PSA)和Sink知识库(SKB)组成。Sink节点代理机构的组成以及之间的相互作用如图4所示。

Sink知识库(SKB):是用于Sink节点计算路径的信息知识库，能够被SMA、PDA和PSA读取和更新。它存储了与网络有关的信息，包括路径长度、跳总数、剩余能量、每条路径剩余能量的最小和最大值、可用带宽、信道容量、到事件节点的可用路径数量、路径权重因子等。

Sink管理者代理(SMA):是存在于Sink节点中的一个静态代理，检测网络相关信息。基于收集的信息，如剩余能量、可用带宽、每条路径的跳总数和路径距离，SMA能够计算出从Sink节点到事件节点的不相交路径。同时计算每条路径的路径权重因子，根据事件的重要性，决定选择一条或多条路径进行传输。根据路径权重因子决定路径的优先级，如果事件是重要的，则选择出多条路径，并使PSAs在这些路径上移动到事件节点。为了减少开销，本文考虑最多选择3条最优不相交路径。如果事件是不重要的，则只选择一条最优路径给PSA移动，当事件节点收到PSA时，开始传输信息数据。

路径设置代理(PSA):是通过SMA构建的移动代理，其从Sink节点的SKB获得路径信息，从Sink节点移动到事件节点来检查路径上的节点。在到达事件节点后，它根据路径信息更新事件节点的MKRB。

2.4.3 示例场景

本文方案的一个应用示例场景如图5所示。图中数字表示的本文方法步骤的序号，执行步骤如下:

1)传感器节点S1检测到一个事件时，事件节点的NMA启动到Sink节点的路径发现过程。

2)NMA产生PDA,PDA产生3个PDA复制品，并计算得出特殊中间节点(S11和S12)和移动的角度;3个PDA按3条路径移动，直到它们分别到达Sink节点、S11和S12，在迁移过程中，它们收集路径信息。

3)PDA的两个复制品在S11和S12处分别改变移动的角度，只到Sink节点并传递路径信息给Sink节点。

4)Sink节点的SMA计算到事件节点的不相交多路径，根据每条不相交路径的权重因子来设定优先级。

5)根据事件的重要性，SMA触发单条或多条最佳路径上的PSA，并移动到事件节点。

3 实验及分析

为了评估本文算法的有效性，利用MATLAB仿真各种网络环境，将本文方案与现有的基于代理多径路由的ABMR方案进行比较。

3.1 仿真模型

网络模型:本文考虑一个l×b(平方米)区域的WSN网络，由N个随机布置的静态节点组成。设定以一跳距离相互连接的节点的信道带宽为BWsingle-hop，本文假设所有信道都是可用的。仿真网络参数如表1所示。

传播模式:本文使用一个传播常数为β的自由空间传播模型，WSN节点的传输范围为R。假设在任何给定的时间上，节点传输一个数据包所需的能量为Eu(焦耳)，节点的R正比于Eu,R=CEu，其中比例常数C取决于传输介质常数β[9]。

3.2 性能参数

本文通过以下几种性能参数来比较本文方法和ABMR算法。

数据包投递率(PDR):指接收和发送的数据包的比例。

能耗(EC):指在网络中路径发现、路径设置和事件节点向Sink节点发送数据包所消耗的总能量，以毫焦耳(m J)表示。

延迟(Delay):从事件节点传输数据到Sink节点的总时间，以毫秒(ms)表示。

额外开销(Overhead):指获得可用的通信路径所需的能量开销。

3.3 实验结果

3.3.1 数据包投递率和能量消耗

图6显示了在给定数量节点和传输范围下，两种算法的数据包投递率(PDR)。在ABMR和LABMP中，PDR都随着节点数量的增加而减小，随着通信范围的增加而增加。然而，相比于ABMR,LABMP具有更好的PDR。当节点数量增加时，节点信息数据的量也随之增加，这就导致需要更多的带宽，因此，可用带宽可能不足以来成功传输数据，使得PDR下降。LABMP方案提供较好的可用带宽，这是因为它在可用路径计算中考虑了链接效率，均衡了信道带宽。LABMP在较高传输范围下的PDR表现更好，这是因为减少了孤立节点的数量。

图7描述了在给定数量节点和传输范围下，网络运行单位时间的总能量消耗。随着节点数量和传输范围的增加，ABMR和LABMP的能量消耗都会增加，然而LABMP具有较好的性能。能量消耗主要由收集局部拓扑结构信息、路径计算、路径信息发送和接收形成。提出的LABMP方案具有较少的能量消耗，这是因为它在计算路径时，考虑了局部拓扑、跳距离因素和能量信息。而ABMR只使用基本拓扑信息来计算路径。

3.3.2 延迟和额外开销

图8描述了在给定节点数量和通信范围下的延迟。由于节点数量和通信范围的增加，收集和计算多条不相交路径的时间需求也增加。LABMP比ABMR需要较少的时间，因为LABMP只利用局部拓扑结构信息来寻找路径，而ABMR则利用全局拓扑结构信息，需要更多时间来收集信息。

图9和图10显示了在给定节点数量和通信范围下，传输关键和非关键数据时的额外开销。开销随着通信范围和节点数量的增加而增加。LABMP比ABMR具有较少的开销，因为LABMP对于关键信息通信，选择多径路由来实现可靠传输，而对于非关键信息通信，只选择具有最高权值因子的单一路径来传输信息。由于LABMP利用代理在设定的方向上移动来获得局部拓扑结构信息，寻找多径路由所需的通信量比ABMR少。

4 小结

本文提出了一种基于代理和位置感知，由事件驱动的多径路由发现方案。事件节点根据位置信息，动态寻找事件节点和Sink节点之间的特殊中间节点，来构建多径路由。并利用移动代理来收集多径路由的的局部拓扑结构信息，并发送给Sink节点，Sink节点根据链接效率、能量比率和跳距离因子来计算路径权值，以此选择最优不相交路径。对于关键信息，Sink节点通过多条较优路径发送信息给事件节点，保证传输可靠性;对于非关键信息，Sink节点只利用具有最大权值的单路径发送信息。由于LABMP只利用局部拓扑信息构建路由，不需要了解全局节点的信息，从而节省了带宽和能量。与现有的ABMR方法相比，本文提出的LABMP在数据包投递率、能量消耗、开销和延迟方面具有更好的性能。

参考文献

[1]杨银堂,高翔,柴常春,等.一种WSN中的能耗优化动态路由算法[J].西安电子科技大学学报,2010,37(5):777-782.

[2]刘新华,李方敏,旷海兰,等.基于能量异构的无线传感器网络分布式成簇算法[J].小型微型计算机系统,2010,34(1):26-31.

[3]卢莉萍,黄飞,张宏,等.基于网络编码的传感器网络多径路由模型能量分析[J].南京理工大学学报:自然科学版,2010,34(4):124-130.

[4]RAMADAN R A.Agent based multipath routing in wireless sensor networks[J].IEEE Wireless Communications,2009,11(6):63-69.

[5]冯江,茅晓荣,吴春春.一种能量均衡有效的WSN分簇路由算法[J].计算机工程,2012,38(23):88-91.

[6]LUO R C,CHEN O.Mobile sensor node deployment and asynchronous power management for wireless sensor networks[J].IEEE Trans.Industrial Electronics,2012,59(5):2377-2385.

[7]KATIYAR V,CHAND N,SONI S.A survey on clustering algorithms for heterogeneous wireless sensor networks[J].International Journal of Advanced Networking&Applications,2011,2(4):122-129.

[8]王建生,曹叶文.基于动态组播代理的移动组播协议[J].计算机工程,2010,36(1):87-90.

[9]MIAO G W,HIMAYAT N,LI G Y.Energy efficient link adaptation in frequency-selective channels[J].IEEE Trans.Commun,2010,58(2):146-152.