地理速率组播技术简介

参考文献（Liu et al.，2009）提出了两种局部地理多速率组播协议：最大速率组播（Maximum Rate Multicast，MRM）和最优速率成本组播（Optimal Rate Cost Multicast，ORCM）。这两种协议与PBM和GMR类似（第5.1节已描述过），它们都是将GFG原理（见参考文献（Bose et al.，1999）或第4.5节）扩展到组播环境中，并将无线组播优势考虑在内。主要区别在于在决策时，它们考虑了不同速率，目标是为了实现前一段中所描述的基于速率的度量最小化。假设方面，协议采用了一种没有损耗的理想MAC层，每个节点都能单独以最大速率向目标节点转发数据。通过查找与目标位置相关的局部邻居位置，每个节点可以独立地选择路由。既不存在路由表，也不需要构建全局覆盖结构。最后，在两个连续路由任务之间，网络拓扑可以发生变化。如果拓扑发生变化，除了更新目标节点或源节点的新位置的成本之外，不存在其他成本。

两种协议的区别在于它们的贪婪模式。贪婪模式如下：在每一跳上，当前节点选择下一个转发节点集。每个节点被赋予向一个或部分目标节点发送数据的职责，且在后期不断重复相同的选择过程，直至到达目标节点。提出的两种协议唯一区别在于它们在每一跳上选择恰当邻居的方法。第一种协议MRM，通过赋予那些要求紧急的目标节点高优先级来实现线性选择，而第二种协议ORCM通过将距离进程与速率行期进行组合，来评估各种不同可能的路由选择，从而实现了更一般的最佳成本进度比概念（见参考文献（Kuruvila et al.，2005）或第4.3节）。

需要注意的是，为了采用这些路由方案，除了节点自身位置信息外，消息报头必须包含目标节点的速率要求。

1.最大速率组播（MRM）协议

MRM的基本思路是优先考虑那些速率要求最高的目标节点。更准确地说，在每一跳上，当前节点考虑那些速率要求最高的目标节点，来确定哪个邻居能够提供指向该目标节点的最快进度。选择邻居之后，将它提供进度的所有目标节点分配给该邻居。然后，不断针对剩余目标节点重复该过程，直至将所有目标节点分配给邻居。最后，消息被发送。图5-12给出了该过程的一个简单应用场景。

图5-12 MRM的应用场景实例

2.最优速率成本组播

根据PBM和GMR（两种协议在上面的第5.12节中进行了讨论）的实例，OR-CM的思路是评估不同路由选择，然后选择评价最好的。为了保持计算复杂性适中，ORCM根据目标节点数来调整策略。如果目标节点数低于某个给定阈值，则ORCM通过生成和评估所有可能的组合（即目标子集或划分的所有可能配置，以使得每个子集的目标节点分配给同一邻居），采用与PBM相同的策略。如果目标节点数高于某个给定阈值，则它采用GMR的策略，即计算一个初始默认划分（根据能够为目标节点提供服务的最佳邻居，来对目标节点进行分组），然后以迭代方式启动一个合并进程，来对其进行优化。

我们考虑图5-13中给出简单的场景。当前节点c要选择指向d₁、d₂、d₃和d₄（每个目标节点可能具有不同的速率要求）的下一跳转发节点，且针对不同目标节点，可以选择仅使用n₁、仅使用n₂或同时使用n₁和n₂。这里，我们描述两种高级策略，选择哪种策略取决于目标节点数（4）是低于阈值，还是高于阈值。

图5-13 ORCM应用场景实例

策略1：对所有目标节点集划分进行评价。目标节点有14种划分方法：

(www.xing528.com)

由于这边仅考虑了两个邻居，从P₉到P₁₄的划分是不可行的，因而将其丢弃。然后，ORCM对从P₁到P₈的每个划分进行评估，然后选择评价最好的。基于这种最佳划分，将每个子集分配给指定邻居（该邻居能够实现指向对应目标节点的剩余距离最小化）。

策略2：初始划分与合并过程

当采用GMR协议时，生成一个初始划分，每个子集代表最佳邻居相同的目标节点，从而有P′={{d₁，d₂}，{d₃，d₄}}，其中n₁为{d₁，d₂}提供服务，n₂为{d₃，d₄}提供服务。然后，合并过程形成P″={d₁，d₂，d₃，d₄}，因为它比P′评价好。这样，所有目标节点都被分配给同一邻居（该邻居能够实现指向这些目标节点的剩余距离最小化）。

针对给定划分的评价问题，与GMR一样，ORCM实现了成本进度比概念。但是，此处给出的成本进度比公式目标是实现基于速率的新度量最小化。参考文献（Liu et al.，2009）给出了给定划分的成本进度比计算方法，但其中一种方法总比其他两种方法好。因此，我们主要介绍这种方法。为了简化公式，我们引入如下符号：

（1）给定目标节点集D={d₁，d₂，…，d_D}，符号rate（D）=max（rate（d）：d∈D）代表这些目标节点中的最高速率。

（2）给定当前节点c，它的一个邻居n和目标节点d，符号progress（c，n，d）=dist（c，d）-dist（n，d）表示n提供从c到d的进度。

（3）给定当前节点c，它的一个邻居n和目标节点集D={d₁，d₂，…，d_D}，符号progress（c，n，D）=progress（c，n，d_i）代表n提供从c到这些目标节点的累积进度。

（4）最后，N（c）代表节点c的邻居集。

给定划分P={M₁，M₂，…，M_D}，其中每个M_i是一个子集，定义为所有子集速率之和除以所有最大子集距离进度之和。这种方法的直观思路是为每个独立子集，选择最适合整个目标节点集的转发邻居：

需要注意的是，对于任意子集来说，如果progress（c，n，M_i）∶n∈N（c）为负数，则丢弃相应划分。

在基于速率的新指标中，当考虑的目标节点数较小（即当ORCM计算所有可能的组合）时，仿真结果表明，ORCM比MRM具有微弱优势，而在其他情况下，MRM具有较大优势。MRM还具有较低计算成本的优势，即使当ORCM不考虑所有目标节点集划分时。关于这些协议的绝对效率，将它们与一系列单播协议进行对比的仿真已经开始进行，且表明在总体成本方面，这些协议比单播之和具有较大优势。需要注意的是，随着速率分布变化加剧，单播之和比不是基于速率的组播协议（这些协议采用最高速率向所有节点发送消息）效率更高。一个有意思的问题是这些协议是如何与最优解决方案进行比较的。回答这个问题需要现在就为这个NP完全问题设计较好的近似算法。