带状定额技术在执行器中的应用

参考文献（Stojmenovic，1999；Liu et al.，2006；Stojmenovic et al.，2008）提出了一种局部带状定额技术，它主要针对采用基于连通性位置更新策略的无线Ad Hoc网络。每个执行器监测其事件链路状态。每当链路破坏/生成发生（可能由于自身的运动）时，它向其邻居报告当前位置。当链路变化达到特定值时，它将当前的位置信息转发给所有位于某“列”的节点。也就是说，它采用GFG路由协议（Bose et al.，1999），在南北两个方向上发送其位置信息，直至其南北边界。沿着这列的节点形成一个更新定额。需要注意的是，GFG将沿着网络的外边界路由位置更新消息，因而外边界也包含在更新定额中。

针对目标执行器位置，源传感器查询其q跳区域。如果回复是否定的，或者它获取的信息不是最新的，则搜索继续在东西方向进行。这些搜索独立执行。东行搜索和西行搜索的轨迹形成一“行”，即一个搜索定额，它与每个执行器的更新定额相交。

当搜索消息沿着搜索定额传输时，它选择目标执行器的最新位置信息。到达定额末端（最西边或最东边的节点）后，位置更新消息被转发给目标执行器，然后它使用正确的位置信息直接回复源节点。或者，如果它们存储的目标执行器位置信息足够新，则源定额和目标执行器更新定额相交的传感器可能会立即回复。

图8-6给出了参考文献（Stojmenovic，1999；Liu et al.，2006；Stojmenovic et al.，2008）中提出的一种称为CR+CR的、带状定额技术的变形。在这种变形中，执行器D在4个地理方向上发送位置更新信息，形成两个更新定额。传感器S在4个方向上发送针对D的搜索消息，构建两个搜索定额。这两个搜索定额与两个更新定额相交。交点处的节点能够为S提供D的位置信息。需要注意的是，该图仅说明了执行器D的更新定额。当存在多个执行器时，每人执行器将拥有与D类似的更新定额，所有更新定额一起形成一种网格结构。

(www.xing528.com)

图8-6 带状定额（CR+CR变形）

这种定额技术具有明显的优势。不需要在网络范围内进行查询，每个传感器就可以找到每个执行器。因为位置更新和执行器搜索限制在两条带中，从而大大降低了通信开销。不需要指定特殊节点来存储特定执行器的位置信息，因而在网络中不会生成瓶颈。如果目标执行器就在源的附近，由于更新定额和搜索定额的相交时间，要比目标执行器远离源时早，因而源将迅速得到答案。但是，这种方案也有不可忽略的缺点。位置更新和执行器搜索必须穿越整个网络；为了保证行、列交叉，网络外边界必须包含在每个定额中，从而增加了边界节点的存储负荷，使得电源消耗加快。

考虑到传感器是静态的这个事实，参考文献（Yu et al.，2009），可以通过牺牲4个方向上的末端传感器，来避免所有边界节点过载。思路是采用预处理步骤来替换更新/搜索触发的外边界遍历。在这一步骤中，使用现有边界检测算法来检测边界节点；然后，从预定义发起者节点开始启动面遍历，来识别整个网络4个方向上的末端节点。这一步结束后，位置更新消息被定位到最北边和最南边的节点，而搜索被路由到东西方向的末端节点处。确保了这两种路由（定额）相交，位于相交区域的传感器回复位置查询。

在密集网络中，由于太多节点参与处理搜索消息，因而带状定额方案性能下降。参考文献（Melamed et al.，2007；Zhang et al.，2007）提出了该问题的解决方案，即把网络划分为等大小的网格，并在每个网格中选择一个主导传感器来构建骨干网。骨干网传感器通过其他传感器连接起来，然后带状定额主要应用于骨干网节点上。参考文献（Liu et al.，2007）讨论了基于网格的定量技术的优缺点，并引入了一种性能优越的改进方案。该方案基于局部连通支配集（CDS），将位置更新和执行器搜索限制在来自于CDS的传感器中间，从而提高了方案性能。