网格定额技术：iMesh及其优势

参考文献（Li et al.，2008；Li et al.，2009）提出了一种称为iMesh的局部网格定额技术，主要用于发现附近的执行器。术语“附近”意味着发现的执行器距离至多是最近执行器的2倍。定额方案基于一种新型平面结构信息网格。该网格是通过在基于定额的网格构建中，采用形式化阻塞规则（Tchakarov and Vaidya，2004）生成的。

在iMesh中，执行器采用GFG路由协议（Bose et al.，1999），向4个地理方向发送位置（即北、西、南、东）更新消息。在消息传播过程中，根据局部阻塞规则，这些消息相互之间发生同线或正交阻塞：接收来自多个执行器局部更新消息的节点，仅转发从最近执行器接收的消息。

当存在异步时，可能会出现违背阻塞的情况。但是，假定在某个节点处，阻塞规则可以使用，则该节点能够以局部方式识别出传输错误，并对其进行修复。这些节点沿着错误转发位置更新的路径发送撤销消息，来删除不一致的信息。位置更新的合理传播路径形成一个信息网格，如图8-7所示。需要注意的是，根据GFG特性，网络外边界被包含在网格结构中。

图8-7 网格定额(www.xing528.com)

为了发现附近执行器的位置，源S在其所在的网格单元中，进行一次简单的交叉查找过程。也就是说，它们在4个地理方向上发送执行器搜索消息，并确保消息到达本地网格单元的主导节点处，如图8-7所示。然后，汇聚节点使用它记录的最近执行器信息来回复源节点。

阻塞规则降低了执行器被发现的可能性，同时限制了消息传输，减小了通信开销。参考文献（Li et al.，2008；Li et al.，2009）将附近/最近执行器选择受到破坏的情形进行了描述，并提出了一种扩展规则：在节点W处，来自于E的信息正交阻塞来自于D的信息。节点W沿着D信息的后向传输路径，将E的信息传输一段有限距离，如图8-7所示。扩展规则没有改变信息网格结构。但是，它有效降低了非理想远程执行器选择的发生概率。

通过分析研究，作者们表明，与带状定额方法（Stojmenovic，1999；Liu et al.，2006；Stojmenovic et al.，2008）相比，iMesh可以大大降低消息复杂性，且它为每个节点生成了固定的存储负荷，这是其他类似定额算法所不具备的唯一特性。大量仿真实验表明，iMesh确保附近服务选择的概率>99%（确保最近服务选择的概率为95%）。

作者们表示，如何处理节点移动性：当执行器开始移动前，它发起一次撤销过程，将其自身信息从信息网格中删除，当节点处于稳定状态时，它充当新来者，以更新其位置信息。