分层环定额方案的优化设计方法

参考文献（Liu et al.，2008）提出了一种分层环定额方案。在该方案中，每个执行器为自己构建和维护一个分层环。这些环具有倍增半径，即k阶半径是k-1阶半径的2倍，在起始阶段，环的中心位于执行器处，当执行器移动时，它们不再拥有一个公共的中心。

0阶环也称为核心环。当执行器移动时，每个执行器使用当前位置重构其核心环（这样环通常是以中间位置为中心），并采用洪泛向环中的所有传感器先应式更新其位置信息。当执行器离开第k（k>0）阶环时，它使用当前位置作为中心来重构环，并仅向新环上的传感器发送位置更新消息。位置更新是带时戳的，这样可以对位置信息的新鲜程度进行测量。图8-9给出了执行器D如何执行位置更新。执行器沿着轨迹P₀，P₁，…，P₅移动。破坏的圆是执行器在其移动过程中构建的环，它当前的分层环R⁰_D，R_D¹，…，R³_D用连续圆表示。

图8-9 分层环定额

a）基于参数的搜索 b）直接搜索(www.xing528.com)

传感器还为自己维护分层环。这些环用于执行器搜索。执行器搜索包含两个阶段。在第一阶段，源传感器首先沿着其核心环搜索目标执行器D的位置，如果搜索没有成功，它将沿着1阶环搜索等。搜索在分层环中逐步上升，最后到达一个足够大的、能够与D环相交的环。然后，开始第二阶段。

第二阶段可以通过两种不同方式实现，这里分别称为基于参数的方法和直接方法。在基于参数的方法中，执行器搜索在交点处D的环中切换，通常按顺时针方向沿着更新环进行。如果搜索在特定环上走了一个完整的圆，则它被定向到最好的D已知位置。在搜索过程中，当发现D的更新环时，参数搜索开始。最后，搜索到达D，D使用其最新位置信息回复S。这种方法要经历类似螺旋的长搜索路径。

在直接方法中，执行器搜索通常定向到D的上次报告位置。当搜索消息靠近D时，它到达D的所有低阶环，并被重定向到越来越精确的D的位置。当它进入D的核心环时，它被第一个接收传感器重定向到D，然后D使用最新位置信息来回复S。这两种执行器搜索方法如图8-9所示，图中执行器D位于位置P₅处，而搜索路径被突出显示，并用箭头标示出来。显而易见，与基于参数的方法相比，直接方法具有较好的局部感知能力。

如果源传感器和目标执行器在地理上相互接近，则他们的分层环将在低阶相交，因而执行器搜索将会很快被定向到目标执行器，而不需要从源传感器处扩展太远。只有当源和目标执行器相距较远时，才会遍历分层结构中的高阶大环。这种分层算法能够实现较好的局部感知能力，同时避免大规模洪泛，因而具有较小的总体通信成本。