参考文献（Abraham et al.，2004）提出了一种采用分层螺旋定额的局部感知位置服务。根据其ID，每个执行器被散列到网络区域的一个点。对于每个执行器来说，使用其散列点作为起源（需要注意的是，在算法中，仅使用了节点的散列点），将网络区域递归划分成分层正方形。在最低级别（0级），每个正方形具有预定义大小；4个相邻k（k≥0）级正方形来自于级别k+1的一个正方形；最高级别的正方形覆盖了整个网络区域。对于每个执行器来说，分层正方形是局部可计算的。
考虑一个任意执行器A。它有一个居住正方形（即它所在的那个正方形），位于它自身分层正方形的每一级。所有这些居住正方形的角点形成一个围绕A的虚拟螺旋，距离呈指数规律增加，如图8-8所示。图中H为A的散列点。必要时，A沿着螺旋线更新其位置信息。传感器使用执行器ID，来计算执行器A的分层正方形，并沿着分层结构中围绕自身的相似螺旋线，启动执行器搜索过程。两条螺旋线必须相交，因为两条螺旋线是采用同一分层正方形进行计算的；可以在交点处找到A的位置，该交点不一定包含A的散列点H。地理路由和迭代有界洪泛的组合方案支持类似螺旋的消息传输。
图8-8 分层螺旋定额(www.xing528.com)
在分层正方形的每个级别上，执行器不仅向其居住正方形的4个角发布其位置信息，而且还向8个周围正方形发布位置信息。仅当执行器移出9个正方形边界时，才进行位置更新。为了降低成本，执行器位置信息仅存储在0级；在第k>0级，存储指向执行器可能存在的第k-1级正方形的指针。这种方案支持懒惰更新，即执行器不需要更新其第k级位置指针，除非它移动的总距离与2k-1成正比。
由于执行器具有不同的散列点、正方形分层，因而位置更新螺旋线也是不同的。这种不同导致节点之间的平衡存储负荷。文献证明，在平均情况下，执行器搜索的消息复杂度为O（d），但在最坏情况下，消息复杂度比较大，为O（d2）。这里，d是源节点和目标执行器之间的最短路径长度。如果执行器移动了距离d，则位置更新的平均成本为O（d log d）。
免责声明：以上内容源自网络，版权归原作者所有，如有侵犯您的原创版权请告知，我们将尽快删除相关内容。
