任意播：保证传输的可靠解决方案

在任意播问题中，源节点希望将信息发送到属于给定目标集的任意节点。在IP网络环境中，RFC 1546最先对该问题描述如下：“主机向任意播地址传输数据报，互联网负责为至少一个目标提供数据报的尽力而为传送，且最好只有一个目标”（后来，RFC 2373针对IPv6环境，对该描述进行了修订）。但是，许多论文在解决不同问题时，涉及任意播问题。例如，在参考文献（Chen et al.，2004；Jeon and Kesidis，2007）中，术语任意播对应于某些地域群播的第一阶段（见第5.2节），它支持数据到达给定地理区域内的任意节点。

当传感器准备将数据报告给执行器，但不关注哪个执行器会有效接收该报告，即可采用任意播。在本节中，我们主要讨论这种情况。任意播协议应当能够到达距离报告事件最近的执行器，以实现由报告引发的能耗最小化。最后，任意播协议必须考虑执行器可能散布于整个网络中的情况。

许多任意播协议是为有线网络设计的（Wu et al.，2007），只有几种协议是针对无线网络设计的，且大多数是针对有线网络的任意播路由协议的修正版（Awer-buch et al.，2003），这些协议依赖于洪泛技术。在其他针对无线传感器网络的任意播协议中，参考文献（Hu et al.，2005）针对每个事件源构建了一棵最短路径任意播树，树根为每个源节点。汇聚节点只是树叶，且能够动态地加入/离开树，树会相应地进行更新。数据被传送到树上最近的汇聚节点。这样，算法可以同步维护指向汇聚节点的路径，且需要记忆路由步骤。基于洪泛的算法在大型网络中成本变得非常高，而那些基于全局结构（如树）的算法，当网络规模变大或成为动态时，其构建和维护成本会非常高。正是由于这些原因，在传感器与执行器环境中，比较适合采用基于位置（地理）的局部协议，虽然它们要求传感器节点知道执行器的位置信息。

这里，我们引入几个符号。下面几段将会用到这些符号。给定两个节点u和v，我们用|uv|表示两个节点之间的距离。给定距离d，我们用power（d）表示在该距离上传输一条消息需要消耗的功率。该功率大致与dα+c成正比，其中α代表信号强度衰减因子，c是一个常数，代表传输导致的最小能耗（更多能量模型见第1章）。最后，给定传感器节点s，我们用A（s）表示最靠近s的执行器。

第一个基于位置的任意播协议是由参考文献（Melodia et al.，2005）提出的。该协议试图实现能耗最小化，其工作原理如下：在启动阶段，每个传感器节点s选择它的一个邻居充当指向某个执行器的下一跳节点。通过选择能够实现power（|sn|）+power（|nA（n）|）最小化的邻居n，可以完成该过程。无论作者如何宣称，这种局部任意播算法无法实现真正意义上的功耗优化，因为邻居选择是基于长边|nA（n）|的，这无法实现功率最优。同时，该协议无法确保空穴区的数据传输。

参考文献（Mitton et al.，2009）提出了3种基于位置的局部协议。这些协议是针对任意播环境中GFG原理的3种不同修正版，因而能够保证指向目标节点（即任意执行器）的数据传输。第一个协议GFGA试图实现跳数最小化，第二个协议COPA和第三个EEGDA主要关注能耗最小化问题。下一段我们将简要描述这3种选择方法。

（1）GFGA选择能够实现|nA（n）|最小化（|sA（s）|-|nA（n）|最大化）的邻居n。换句话说，它选择能够提供指向任意执行器最快进度的邻居。需要注意的是，在这个公式中，A（s）和A（n）可能是不同的，这反映了任意播的核心概念。(www.xing528.com)

（2）COPA依赖于成本进度比（见参考文献（Kuruvila et al.，2005），或第4.3节），成本为下一跳的能耗估计值，进度为指向任意执行器的距离进度。更准确地说，对于传感器s来说，选择能够实现power（sn）/sA（s）-nA（n）最小化的邻居n（人们还提出了两种更为复杂的变形，但性能非常类似）。

（3）EEGA是COPA的增强版，其灵感来自于EtE协议（Elhafsi et al.，2008）。这种解决方案比COPA更节能，但计算复杂性比较高。它的基本思路是选择邻居n为下一跳节点（根据任意能量相关成本公式），有时使用一个或多个额外邻居到达n（尤其是当信号强度衰减因子α比较高时），可能会更加节能。这可以通过计算从当前节点到每个邻居的能量加权最短路径（Energy-weighted Shortest Path，ESP）来实现（它能够在本地完成，因为节点知道其邻居的位置），然后将消息转发给指向n的ESP上的第一个节点。

关于任意播问题，所有这些解决方案的本质是在路由过程中，目标节点可以发生变化，如果条件允许，可以选择另一个执行器。这种场景如图5-14所示，其中传感器节点S准备启动一次报告过程。根据与执行器的相对距离S选择A₁作为目标节点，然后启动针对该目标的贪婪进度。一旦到达B，不存在与任意执行器的距离比B与A₁的距离近的邻居。这样，协议切换到恢复模式（此处启动了一次右手面遍历过程）。如果此处采用GFG的单播版，则恢复模式将继续进行，直至到达节点D，指向A₁的贪婪进度继续进行。但是，此时节点C注意到执行器A₂与C之间的距离要比A₁与B之间的距离近。于是，A₂被选为新的目标节点，指向它的贪婪模式继续进行。最后，当接收到消息后，节点E在不中断贪婪进程的前提下，执行最后一次修改，将目标节点切换到A₃，因为它比A₂更近。

图5-14 基于GFG修正版的地理任意播