分层本地区域的8.6.2方案

参考文献（Li et al.，2000）提出了一种网格位置服务（Grid Location Service，GLS）。网络区域被均匀地划分为许多1阶正方形。4个来自（k+1）阶正方形的相邻k（k≥1）阶正方形，一个k阶正方形是（k+1）阶正方形的一部分。采用这种方法，在不同大小的正方形上构建四叉树，且在分层中，每个节点恰好位于每种尺寸的一个正方形中。这种划分可看做是GLS的基础，属于全局知识。以一种统一的不同方式，为执行器和传感器分配标识符。位置更新服从基于距离的策略。

在每级分层中，节点（无论是传感器还是执行器）T选择3个节点作为位置服务器，每个节点来自于相邻3个正方形。特殊情况下，它采用地理转发，向所选k阶正方形发送一条位置更新消息。正方形的第一个接收节点W启动一个更新过程：它在正方形内向ID最靠近T（即至少在一个ID圆形空间中比其他ID大）的节点转发消息，该节点采用同样方法依次进行转发。当消息到达正方形范围内最靠近T（在ID方面）的节点时，该过程终止，该节点成为正方形内T的位置服务器。

此更新过程发挥作用的原因是要求1阶正方形中的节点在启动阶段立即交换其位置信息，且在针对低阶正方形的前一个过程中，k阶正方形中的所有节点在整个正方形内分发其位置信息。

目标（无论是传感器还是执行器）搜索执行方式与位置更新类似。源节点S向ID最靠近目标D的节点，发送包含其当前位置的搜索消息，因为该节点当前拥有目标D的位置信息。每个中间节点以同样的方式转发该消息。最后，消息将到达D的位置服务器。采用地理转发，该位置服务器将消息转发给D，然后D使用当前位置信息直接回复S。为了容忍移动性，在节点移动到另一个1阶正方形之前，它在当前1阶正方形中留下一个“转发指针”。该指针可用于在针对节点的搜索到来时，对节点进行定位。

图8-11给出了节点ID，并用它来表示节点。该图说明了GLS原理。在该实例中，节点B（其ID为17），选择其位置服务器，服务器的ID在网格分层中用圆圈表示；分别从节点76和90，发起了两个针对节点B的目标搜索，其搜索轨迹用箭头突出显示。

(www.xing528.com)

图8-11 网格位置服务器

由于采用了分层设计，因而网格位置服务具有良好的可扩展性。在节点附近，节点位置服务器相对比较密集；在远离节点的位置，节点位置服务器相对比较稀疏。这样能够确保当目标附近的节点使用附近位置服务器来寻找目标位置时，提高其局部感知能力。在位置更新频繁的高度移动网络中，网格位置服务可能会带来较大的消息开销，因为每个节点必须向其网络范围内的分布式位置服务器发送位置更新信息。类似之字形的消息传输也会提高消息开销和搜索延迟。如果1阶正方形中的所有节点移出，则将没有节点为其存储转发指针，从而会导致搜索失败。

目前，人们已经提出了基于分层划分的许多类似算法，如DLSP（Chen et al.，2006）、HLS（Kieb et al.，2004）、MLS（Flury and Wattenhofer，2006），仅举几例。在DLSP（Chen et al.，2006）中，在网格分层中的每一级中，通过使用公共散列函数，每个执行器选择8个位于8个相邻正方形中的位置服务器。不同级别的位置服务器更新速率不同。执行器搜索从最低级别开始，穿越分层直至满足要求为止。如果搜索失败，则从失败点启动新一轮搜索。

在HLS（Kieb et al.，2004）中，通过公共散列函数，每个执行器在每种级别的分层小区中，选择每个单元中的一个最小划分单元，来构建一棵个性化树。位置（指针）更新沿着从树根到树叶的下行路径进行。执行器搜索在同一树中沿着从树叶到树根的上行路径进行。如果搜索路径在到达树根之前与更新路径相交，则会很早满足要求。在位置更新方面，MLS（Flury and Wattenhofer，2006）与HLS非常类似。但是，它没有采用上行路径遍历，而是采用针对目标执行器的扩展环搜索。