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

意义上来说，它起到了部分路由表的作用。图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中，在每个层次的的子网格中都会选举出位置服务器节点，因此