移动自组网中的典型位置服务协议比较

【摘要】到目前为止，移动自组网已经开发很多基于不同策略的路由协议，这些路由协议可分为基于网络拓扑的路由协议和基于位置信息的路由协议。本文主要介绍基于位置信息的路由协议及几种典型协议的分析比较。

【关键词】无线自组网；位置服务协议；路由协议

一、位置服务协议定义

到目前为止，移动自组网已经开发很多基于不同策略的路由协议，根据在路由过程中是否依赖节点的位置信息，这些路由协议可分为基于网络拓扑的路由协议和基于位置信息的路由协议。基于网络拓扑的路由协议是利用链路信息进行路由的建立和分组转发，因此不可避免的会利用洪泛操作来查找目的节点的位置，为了减少弥补这些不足，将节点的位置信息引入路由协议中，当源节点要与目的节点进行通信时，只需知道目的节点的位置信息和下一跳邻居节点的位置信息即可，这就是基于位置信息的路由协议。在基于位置息的路由协议中，源节点欲与目的节点进行通信，必须通过两个步骤：

（1）获取目的节点的位置信息；

（2）根据第一步得到的目的节点位置信息，选取合适的路由协议转发数据包。

两个步骤中都离不开节点的位置信息，而目的节点位置信息的获取就得依靠位置服务协议来实现[1]。当源节点欲与目的节点进行通信时，只需发送“hello”查找数据包，启动合适的位置服务就可以获取目的节点的位置信息，从而使基于位置信息的路由协议更高效的把数据包转发到目的节点。由此可见，位置服务协议是管理位置信息的一种策略。所谓位置服务主要包括移动节点注册并随时更新自己的位置信息，以及源节点查询目标的确切位置两个步骤。网络中的节点根据一定算法周期性的把自身的位置信息分布式的保存在网络上的特定的节点或者某些特定区域，网络中的其他节点也可随时利用位置服务发送查询包以达到查找目标节点位置信息的目的。由于Ad hoc网络中的节点无时无刻存在移动的可能性，它的地理位置也在随时变化。因此，源节点如何既准确高效又方便的查询目的节点的地理位置是一个重要的研究方向。

在选择位置服务协议时，本文主要考虑以下两点：

（1）节点信息的更新：节点何时更新自身位置信息以及节点把自身的位置信息更新到网络中的哪些区域或着哪些节点。

（2）节点信息的查找：当节点需要目标节点位置信息时，应该如何去选择哪些区域或者节点来查询。

如图1，位置服务协议是专门为了源节点能够获得目的节点位置信息而建立的一种机制，从某种意义上来说，它起到了部分路由表的作用。图1给出了其中的一个较为简单的分类方法：基于洪泛的位置服务和基于交集的位置服务[2]；其中基于洪泛的位置服务又进一步分为主动式（proactive）洪泛和被动式（reactive）洪泛；基于交集（rendezvous-based）的位置服务协议又可分为显式（Explicit）Quorum位置服务和基于哈希散列（Hashing based）的位置服务。基于散列的位置服务根据在实施集合系统时是否使用递归层次来定义子区，可以进一步分为层次型和平面型。

二、四种典型位置服务协议的对比分析

通过前面的分析发现，学术界的学者提出了大量的位置服务协议，但是大多都是基于理论分析或者是模拟分析，很少有人对这些位置服务协议进行性能的比较[3]，尤其是在一个真实的移动环境中。因此本文依据上述分类，选取DLS、XYLS、GLS、GHLS这三种典型的协议进行定性定量对比分析。定量结果如表1所示。考虑到基于交集的位置服务协议的扩展性比基于洪泛的位置服务协议好，因此本文会重点分析XYLS，GLS[4]，GHLS，对于DLS仅在表中给出分析结果。为了让分析易于处理，本文假定网络是静止的，且节点均匀分布在地理区域中。同时为了便于三种交集型协议的分析，本文定义如下参数：节点的更新频率为f，GLS协议中order-1网格的边长为l，且GLS分层的高度为h，即整个网络可以分为order-h级。因此，对于order-i级网格，网格的边长为2i-1*l。整个网络的边长就可以用2h-1*l来表示。在GLS实际应用中，l是根IEEE802.11无线网络传输半径来选取的。接下来，为了简化分析，虽然在XYLS和GHLS中不存在分层的思想，本文仍将order的概念引入XYLS和GHLS中，如表1所示。

在XYLS中，每个更新间隔发起一次更新。更新时沿着纵向传播的，因此会覆盖个order-1网格，从理论上讲，每次更新会引起个数据包的传送。然而，由于在XYLS中，实际每跳的平均跨度是order-1网格边长的一半。通过上述分析，在南-北更新会有跳的距离，加上在每跳都会进行单播和广播数据包处理，可以得出结论：每次更新会产生个数据包。对于每个查询，两个查询数据包沿着东-西方向传播，且在每跳只进行单播。当某个方向（东方向或者西方向）的数据包到达节点的位置服务器时，则会停止转发。因此每个查询包的平均查找路径长度为，由于查询回复包由于只是由位置服务器节点朝着源节点单方向的转播，因此每个查询回复包的平均路径长度为。

由于在GLS中，在每个层次的的子网格中都会选举出位置服务器节点，因此，在每个更新间隔内，每个order-1层的节点会发送三个更新包给其他三个服务器节点；在每两个更新间隔内，在order-2层也会有三个更新包装法给同城的三个服务器节点......以此类推，在每个更新间隔，在order-（h-1）层三个更新包被转发给同层的三个位置服务器。因此，每个节点在每个更新时间间隔内更新的次数为：

当节点在order-1层时，每个更新包的跳数是1，1，，类似的，上层更新包的跳数根据网格的边长成比例的增加，因此每次更新间隔作于哦更新数据包的平均跳数为：

对于大小为网络，采用GLS协议进行查询时，任意两节点的平均查找跳数近似为两节点平均距离的两倍，大约。类似的，查询回复包的平均路径长度为。

同XYLS相同，在GHLS中，每个更新间隔内发起一次更新。在采用GHLS协议的网络中，两个任意节点间的平均跳数等同于他们间的平均距离，大约是，类似的，任意一个查询请求包或者回复包的平均路径长度为。

从以上的分析中，本文可以得出以下结论：

（1）采用GLS协议时，查询请求包的平均路径长度是GHLS协议的两倍，但却以的优势优于XYLS。

（2）GLS和GHLS协议查询回复包的平均路径长度相同，但却是XYLS平均回复包的2倍。

（3）XYLS和GHLS协议每个时间间隔内更新的数据包数目的数量级为o（2h），而GLS的数量级为o（h）。

从以上理论性分析，就更新包的数量而言，GLS优于XYLS和GHLS协议。为了证明这点，本文将每次更新发送的数据包数量作为网络高度的函数h，并规定大小为N网络中节点密度为。最终显示两者之间的关系如图2所示。结果显示，不管网络多大，GLS更新包的数量一直低于XYLS。当网络层次低于7时，GLS更新包的数量一直高于GHLS，但是当h大于7时，GLS更新包的数量就会低于GHLS协议。

三、小结

位置服务本质上就是如何传递和处理位置更新分组，使得传输时所消耗网络资源最少，同时使各节点获得较为精确的目标节点的位置。因此需要在网络传送的数据量和节点位置精度之间做出合理的权衡。本章从位置服务的角度出发，描述了现有的Ad hoc网络位置服务协议的分类及其特点，并对每个机制中的典型代表协议进行对比，评价了其优缺点，并对其性能做了定量和定性的比较。

参考文献

[1]马雯娟.Ad Hoc网络中基于位置服务协议的路由技术的研究与实现[D].西北大学硕士毕业论文，2009.

[2]郎为民.基于洪泛的物联网位置服务算法[J].现代电信科技，2012.

[3]门福军.Ad Hoc网络路由协议及性能研究[D].西安电子科技大学硕士毕业论文，2006.

[4]章忠究.Ad Hoc网络中基于位置的安全路由协议[D].计算机应用，2008.

作者简介：

刘扬（1973—），女，辽宁鞍山人，博士，辽宁科技大学电信学院副教授，主要从事数据库、人工智能领域的研究。

范景艳（1989—），女，山东菏泽人，辽宁科技大学电信学院研究生，研究方向：计算机应用技术。