基于面树深度优先搜索的地域群播遍历方法

参考文献（Bose et al.，2001）提出了另外一种保证将数据包传输给区域内所有节点的地域群播算法。与前一个协议类似，它不需要记忆任何位于节点的信息，仅需要消息中添加少量信息。协议采用GFG来寻找指向区域内某个节点的路由，然后搜索所有位于区域内的面，或者与区域相交的面。这种搜索后面要进行详细描述，它基于如下事实，即构成任意面的边集，可以根据边与平面内给定参考点的相对位置进行总体排序。基于这种排序关系，面与面之间可以相互关联，形成一个面树，树根为包含参考点的面。然后，可以通过在面树中使用深度优先搜索，来对整个区域进行访问。整个过程可以应用于网络的一个平面子集（如Gabriel图，见第4.5节）。

给定一个面f和位于面外的一点p，可以根据f的边集到点p的距离（实际上是边中最靠近p的点到点p的距离），对边集进行整体排序。假设给定边与边之间的关系，基于地理特性，并考虑到其他比较因素，可以使整个排序变得更为严谨。基于排序，每个面（除了包含点p的那个面）可以与自己的一个边建立关联，称为entry（f，p），这是最靠近p的边。现在，如果我们考虑到每个入口边位于两个不同面的边缘，则这些边定义了面的一个层次结构（因而生成一个面的隐式树），这样除了包含点p的面外，对于每个面f来说，parent（f，p）是边中包含有entry（f，p）的面f′≠f。

该算法的工作原理如下：采用GFG协议，一旦到达某个区域内的节点N时，该节点选择位于任意邻近面（根据定义，应当位于该区域内，或与该区域相交）内的附近地理点p。该面变成了面树的根。在地域群播运行期间，开始构建面树，事实上，它属于地域群播操作。从包含点p的面开始运行，在节点N处，算法将访问整个面，但在通过每条边之前，它检查该边是不是相反面的入口边（我们将在下一段中讨论这种检查过程）。如果事实如此，则当前面遍历中断，以访问子面。该过程以递归形式进行，直至无法发现子面，在该点上继续父面遍历（在入口边的另一端点）。为了限制对地域群播区域的访问，仅仅针对那边位于区域内的面，或与区域相交的面来定义入口边。算法如图5-8所示。在该图中，从外部到达N的粗路径代表第一个路由阶段（如GFG协议），连续虚线对应于穿过整个区域的面树深度优先遍历，该遍历在N处开始，N处结束。面按照访问次序进行编号。最后，黑色虚线边代表入口边，而带箭头的灰色虚线代表相应的父/子关系。

图5-8 面树遍历

由于算法访问了面树（它是由所有与区域相交或位于区域内的面组成的）中的所有面，因而它必须访问这些面中的所有边，从而访问了区域内的所有节点。但是，算法面临着隐性成本：为了获知给定边是否为相反面的入口边，必须访问该面。这会给算法带来较大的消息开销。用来缓解这种问题的一个可能方案是对于所有网络来说，仅在开始时确定一次入口边，并在端点节点记住这些入口边（假定之后拓扑没有发生变化）。这意味着在部署时，需要协商好公共参考点p，可以对该算法进行修改以处理那些可能不包含p的地域群播区域。我们假定在第一步，消息从地域群播源被路由到区域内的任意节点（如果源节点不在该区域内），用s′表示该节点。如果p位于区域内，则地域群播开始使用父链路从s′回溯到p，然后从p处运行常规深度优先搜索算法。如果p位于区域外，则算法从s′回溯到p，但只要到达位于区域外的节点（即p′）就停止。从p′处开始，面遍历将沿着区域外的边进行，它与图5-8中虚线外面部分相对应。沿着周边，在每个入口边（它们是已知的）开始独立的深度优先搜索遍历，它会访问区域内的每个面。(www.xing528.com)

采用最初的版本，仅当地域群播是凸的时，算法才有效。例如，我们可以采用类似月牙的“C”形与位于形状两个端点附近的p。另一端的面可能具有位于区域之外的父面，从而可能无法访问。通过采用一种类似的周边遍历可以解决该问题，在这种方法中，将会检测到所有的入口边，并引发独立的深度优先搜索。

针对该算法的另一种常用优化方法可用于精心挑选的一个子集的节点，即连通支配集（CDS，详细信息见本书第2章）。更准确地说，我们首先在区域内的节点中找到一个CDS，然后采用面树遍历仅访问这些节点。根据定义，每个非CDS节点与CDS节点的距离为1。因此，仅让CDS进行重传，来将数据包转发给所有节点就足够了。参考文献（Datta et al.，2002）提出了一种基于CDS的面遍历方案，用于优化GFG的面模式。但是，这种优化从来没有在地域群播和面树遍历环境中提出过。为了方便图示，图5-9给出了与图5-8中描述相同的拓扑场景，唯一区别是面树遍历在区域内节点的CDS上执行。这里，面树仅由两个面构成：包含p的根和一个子面。浅灰色代表非CDS节点（及其边），而正常颜色代表CDS节点（及其节点之间的边）。

图5-9 基于CDS的面树遍历