基于边界相交的面遍历实现地域群播

在考虑的平面子图中，我们将位于区域内（外）、且在区域外（内）至少有一个邻居的某个节点称内部（外部）边界节点。参考文献（Seada and Helmy，2004）提出了一种算法，它采用GFG算法将数据转发给区域，然后激活一个周边机制来保证数据传输给区域内的所有节点。但是，参考文献（Stojmenovic and Wu，2006）表明，这种机制实际上无法保证传输，虽然它与下面的有效算法非常类似。

1）如果接收节点位于区域内，则它以广播的方式重传该消息。这仅适用于接收节点首次接收到消息的情形（不考虑多次复制的情况）。如果该节点是内部边界节点，则它在消息中包含了一条与其外部边界邻居有关的指令，要求它们启动右手面遍历（见下面的第2种情形）。

2）如果接收节点是外部边界节点，它接收到来自于一个内部边界邻居的消息，则它启动右手面遍历来检查与内部边界邻居共享的每个边的外部连续性。来自于任意内部边界邻居的更多消息将被忽略。

3）与参考文献（Seada and Helmy，2004）中提出的协议相反，如果接收节点是一个外部边界节点，且发送方是区域外节点，则接收节点不忽略该消息（即使它已经完成了第2种情形中描述的步骤），并将该消息沿着与接收使用的同一面进行转发。在特殊情况下，后一步对于保证传输非常必要。

(www.xing528.com)

图5-7 遍历与边界相交的面

所有这些操作如图5-7场景所示。首先，源节点S使用GFG到达区域，并在节点N处完成。根据情形1，N在区域内启动一次洪泛，节点M沿着边NM的外部连续启动一次右手面遍历过程（需要注意的是，在外部节点在内部节点之前得到消息的特殊情况下，则没有必要等待用于启动面遍历的指令）。面遍历到达I，它忽略消息，因为它已经从内部接收到该消息。同时，节点K启动延续边IK的右手面遍历。该遍历经过整个区域（经过节点H），直至回到J。节点O启动延续边JO的面遍历，它靠近N处的环路。

同时，从N开始的首次洪泛到达节点W，节点W向A发送一条指令，来启动延续WA的面遍历。该遍历在节点C（重传数据）处结束。节点B开始与CB有关的面遍历，到达F（如果已经接收到来自于C的消息，则忽略节点B发送的消息，否则对消息进行重传）。最后，E启动返回到A的面遍历。在这一点上，参考文献（Seada and Helmy，2004）提出的算法终止。A采用第3种情形来继续面遍历，到达节点D。最后一次面遍历靠近W处的环路，于是忽略该消息。在一些情形中，保证传输意味着要访问整个网络。如果H和G之间的虚线圆边没有映射到连通节点的实集上，就会出现这种情况。然后，面遍历将转向网络的其他面（读者可以想象面遍历从节点H掉头，到达M，然后通过源S，再次到达M，一直遍历直至到达G，然后返回，最后到达J）。