地理感知组播的常规单播面路由策略（GMR）

地理组播的总体思路是使用节点的位置，实现高效的路由，而不需要构建和维护全局路由结构（如树状和网状结构）。这主要基于如下观测结果：除非与对应的地理信息关联起来，否则传感器的准确测量结果通常含义不准确。因此，假定传感器位置信息可用不是一个要求太高的假设。本书的第4章已经对地理单播进行了讨论。在本节中，我们将综述那些将地理路由扩展到组播场景的协议。首先，简要介绍一下子地理（但非局部）协议，虽然它在传感器与执行器网络环境中不是最优的。然后，我们对地理和局部协议进行综述。

作为首批非局部地理组播协议之一的轻量级自适应组播（Lightweight Adaptive Multicast，LAM）（Ji and Corson，1998），仍然采用了广播消息，因而不适用于大型无线传感器网络。另一个协议DDM（Ji and Corson，2001）出于同一作者，该协议将若干个单播数据表进行组合，构建组播数据转发。这些表的管理需要额外开销，从而使得该协议的应用范围仅限于小型组播组。最后，参考文献（Mizumoto et al.，2004）提出的协议使用位置信息来构建地理感知组播树，目标是实现链路数最小化。但是，正如前面所讨论的，实现边（跳）数最小化无法应用无线介质的一对多特性（无线组播优势）。此外，该协议构建了一个全局覆盖结构，维护成本较高，且在大型网络场景下，可扩展性不强。地理路由的最大优势当然是避开了构建和维护全局路由结构的必要性，且支持使用局部、无状态协议。在无状态协议中，所有用来路由消息的信息在内部进行传送，下一跳中继邻居的选择可以在每一跳上即时做出。这种路由要求每个节点知道：

1）使用类似全球定位系统（GPS）定位服务或虚拟坐标（见第4.7节或参考文献（Niculescu，2004））确定的节点自身位置；

2）节点直接邻居的位置（使用信标方案）；

3）通过使用位置服务（第8章将要讨论的主题）获取的转发数据到达的目标节点（执行器）的位置。下面讨论的组播协议（GMP、PBM、GMR、HGMR和HRPM）就属于这些协议。

GMP（Wu and Candan，2006）的工作原理如下：在每一跳中，当前转发节点构建一个虚拟组播Steiner树，自己充当树根，真正的目标节点作为树叶。该树可以通过成对合并目标节点得到，生成一个虚拟节点来代表目标节点。此过程以递归形式进行，直至无法进行简化。基于树和局部邻居位置信息，目标节点集可以划分为若干组，选择一个邻居为下一跳上的节点组提供服务。为了解决转发给目标节点子组时出现的空穴区问题，协议提出使用常规单播面路由（见第4.7节或参考文献（Bose et al.，1999）），在这种路由算法中，组中的目标节点全部被单一点所替代，成为其地理位置的平均值。GMP的主要缺点在于它使用启发式方法来构建Steiner树。实际上，它通过每次合并两个节点，来计算虚拟节点，这会导致错误的位置估计，尤其是如果目标节点散布在网络中，或者目标节点分布在源节点周围。

另一个协议PBM（Mauve et al.，2003）最初不是针对传感器网络设计的。但是，它满足了局部化和使用有限网络开销的标准。该协议是贪婪-面-贪婪（GFG）原理的一种推广形式（见第4.5节或参考文献（Bose et al.，1999）），主要应用于多目标节点场景。它依赖于根据所选的平衡参数λ，对每个目标节点的单个最短路径和整体成本最小化之间进行的折中。更准确地说，在每一步，当前转发节点对使用函数f（C）=λN+（1-λ）D来计算下一跳转发邻居可能形成的组合C，其中N为所选节点数与邻居节点总数之比，D为从这些邻居到目标节点的所有剩余距离（它与从当前节点到目标节点之间的距离总和成正比），λ是一个介于0和1之间的值。如果邻居的最佳子集是单个节点，则对于所有目标节点来说，该节点是唯一的中继节点。如果选择的是包含多个节点的组合，则每个节点将负责目标节点的不同部分。当无法提供针对一个或多个目标节点的进度时，可为这些目标节点选择使用面路由变形，而贪婪转发继续应用于其他目标节点。使用这种方法的主要问题是确定λ的最优值，因为不存在一个适用于所有应用场景的最优值。在密集网络或大型组播组（目标节点数目较大时）中，存在的另外一个问题是算法需要对目标与邻居之间所有可能的关联组合进行评估（其复杂性随着两个要素呈指数规律增加）。

GMR（Sanchez et al.，2007）是GFG针对组播场景的另一个修正版。GFG的高级修正版与PBM中的一个协议类似：当转发节点无法发现任何能够提供指向某些目标节点的进度（即已经实现局部最优）时，将这些目标节点放到一个称为组播面列表的表中，开始使用面路由来处理这些目标节点。在面路由中，对于给定目标节点来说，如果当前转发节点恰好比先前局部最优节点更靠近目标节点，则将该目标节点从面列表中删除，添加到贪婪表（采用贪婪路由算法来处理该目标节点）中。需要注意的是，当前节点可能选择同一邻居来为两种并发模式（针对不同目标节点）提供服务，在这种情况下，需要传送包含两种信息的单条消息。虽然在高级策略方面与PBM类似，但是GMR在转发邻居选择上与PMR存在较大差别。

为了解决因评估所有可能组合带来的复杂性问题，GMR提出了一种初始默认组合。在这种组合中，每个目标节点是由最方便的邻居（即能够提供指向目标节点最高进度的邻居）单独提供服务的。协议根据成本进度比（见第4.3节或提出一般定义的参考文献（Kuruvila et al.，2005））概念，分别对由此形成的多个划分进行评估，其成本由所选节点数来度量，进度由指向目标节点的剩余距离总体减少幅度来衡量（假定每个子集的邻居分配比较合理）。在如图5-2所示的实例中，GMR对初始划分P₁以及由于合并形成的划分P₂进行评估。在这种场景中，仅使用n₂给出了一种轻微距离惩罚，但成本降低了一半。因此，合并是非常有效的。在可能出现多个合并的更复杂应用场景中，GMR对所有合并进行评估，并采用最有效的合并，然后再次进行评估。

(www.xing528.com)

图5-2 使用GMR进行路由决策实例

虽然GMR解决了PBM的缺点，但它仍然存在着缺陷，即每个数据包的报头包含有数据包的每个目标节点信息。因此，每个数据包的编码开销是目标节点数的函数，如果目标节点数过大，则编码开销将变得不可接受。

HRPM（Das et al.，2008）是最近提出的一个协议，通过构建一个为目标节点提供服务的层次结构来解决这个问题。层次结构是通过将网络在地理上划分为多个小区来实现的。在小区内，每个目标节点移入和移出网络时，需要进行注册和注销。由于针对这些注册的管理比较复杂（后面将会进行描述），因而源节点可以得到至少包含一个目标节点的所有小区列表，然后将数据包发送给这些小区，而不关心哪些特定目标节点在哪个特殊小区。然后，每个小区将数据包转发给内部的目标节点。实际上，通常使用3级或4级层次结构，但作者说明这种两级层次结构足够支持多达5800个目标节点（报头长度与数据长度之比保持在适当水平）。该协议的主要优点是能够确保每个数据包的开销不超过预期常数ω。为了保证这一特性，小区的规模根据ω值和组播组的大小来确定。因此，每个组播组定义了一个特殊空间划分和小区管理。下面我们描述小区管理是如何实现的。

该协议假定每个组播组都有一个唯一标识符，且每个潜在目标节点知道它所在的所有组播组。该协议支持同一组的所有目标节点重新创建网络划分的相同局部表示。由于存在公共地理散列函数，因而每个组播组的标识符可以映射到网络中一个称为汇聚点（Rendezvous Point，RP）的特定位置，也可以映射到每个小区内称为接入点（Access Point，AP）的特殊位置，如图5-3所示。

图5-3 网络的地理划分，由同一组播组的所有节点共享

简单起见，我们首先考虑RP和AP都是位于预期位置上真实节点的情况（这实际上是假的，但有助于理解）。每当目标节点移动时，它将新的位置报告给所在小区的AP。当所在小区发生变化时，目标节点从一个AP注销，然后在另一个AP处注册。AP将这些成员情况报告给RP。当节点准备向给定组播组发送数据包时，它首先与该组的RP联系（使用组标识符和地理散列函数），RP将为节点回送至少包含一个目标节点的小区列表。收到这个列表后，发送节点构建一个由相应AP（除了根节点，即节点自身）构成的唯一虚拟树，并将数据沿着树进行发送（使用树中每个父节点与子节点之间的地理单播）。一旦消息到达某个AP，可使用另一组地理单播到达最终目标。RP和每个AP的作用，实际上是由最靠近对应位置的节点发挥的，当一个最近的节点发生变化时，会采用一种特殊的局部管理机制。保存AP和RP虚拟位置后，可以将它们看做是固定节点。对于两种单播（从源节点到AP，从AP到目标节点），采用的单播协议是GFG的修正版，它稍微对面路由模式进行了修改，以处理诸如AP和RP等虚拟目标节点问题（使用修正版协议来选择最近的节点）。

HRPM有几大优点。除了编码开销有限之外，它并不需要外部位置服务，且组管理成本较低（主要是由于RP和AP位置固定）。但是，它在通信方面是次优的。事实上，它采用了一组单播沿着树进行通信，这意味着它属于贪婪级别，在相同节点之间可能会出现多次重复发送同一信息的情况，且未考虑到无线组播的优势。

HGMR（Koutsonikolas et al.，2007）是HRPM的修正版，适用于相对密集和静态网络（如传感器与执行器网络）。HGMR的总体思路是整合GMR和HRPM的设计理念，即为大型网络提供转发效率和可扩展性。我们简单回顾一下子，采用HR-PM时，数据从源节点向AP传输（沿着AP虚拟树），然后从每个AP传送到对应的目标节点。当组播成员密度较大时（广播的优势发挥到最佳），GMR具有最高增益，但在稀疏网络中，由于编码开销变大（因为所有目标节点都包含在报头中），因而它相对于单播的优势减弱。这样，对于从源节点到AP的数据传输来说，由于AP的密度相对较低，HGMR仍然使用单播。但在每个小区内，目标节点相距非常近，此时HGMR使用GMR成本进度比组播算法在每一跳上选择下一个中继节点。如果某个小区内目标节点数太大，以至于无法包含在报头中，则相应对地理分解进行调整。因此，在每个小区内使用GMR，而不是使用HRPM基于单播的转发策略，有助于降低传输次数。HRPM另一个缺点是散列函数可能导致RP距离源节点非常远。正是由于这个原因，HGMR使用能够在整个区域中心某个正方形内产生位置信息的散列函数，从而限制了最坏情况的发生。