基于记忆的地理位置路由保证传输

根据所选的推进机制（如减小到目标的距离），如果当前节点无法找到任何能够推进进度邻居，则贪婪路由停止工作。但是，从源节点到目标节点的路由可能依然存在。当所选的贪婪路由失败后，我们仅考虑采用局部方法来寻找路由。这些局部路由方法通常分为两类，取决于任何与路由有关的信息是否留在了受访节点，这些信息可用于后续可能发生的协商过程。在所有必要信息全部包含在数据包里的无记忆路由中，这是不允许的。我们首先研究一些支持记忆的关键技术。在某些情况下，记忆是正当的。举例来说，在两个正在处理流量（如基于QoS的应用）的节点之间建立一条路径，路径上的节点需要记忆下一跳信息。显而易见，另一种可选方案是在消息中记录整条路径，但随着路径长度不断增加，这种方法的可扩展性不太好，因为随着消息长度的增加，会提高碰撞概率，降低可用带宽。我们将对几种基于记忆的恢复机制进行描述。

参考文献（Stojmenovic and Lin，2001a）提出了两种基于洪泛的方法，即f-greedy和f-MFR，这些方法在中间节点处分别采用贪婪路由和MFR路由，并在凹节点处使用恢复机制。每个凹节点记忆消息ID，并拒绝对同一消息进行多次复制。也就是说，凹节点C的邻居根据数据包可以获知节点C的凹状态，但在未来尝试中，不会选择C作为下一跳转发节点。凹节点的每个邻居并行启动一次面向目标节点的独立路由过程。如果前一条路径已经通过某个节点完成过同一路由任务，则当某些路径经过该节点时，将在稍后某个时刻被终止。

参考文献（Stojmenovic et al.，2002）提出了一种局部深度优先搜索（Depth First Search，DFS）路由算法。与f-greedy不同，它是一种单路径路由算法。如果每个节点已经被DFS以遍历的方式访问，则它将记忆该信息以及首次接收消息的节点。将所有邻居节点按照距离目标D的远近进行排列，并选择与D距离最近的节点，来完成数据包转发过程。由于受访节点已经传输了一个转发数据包，该数据包被该节点的邻居获知，邻居们知道它们的状态，因而受访节点不会选择这些邻居再次转发数据（Vukojevic et al.，2008）。返回的消息将被送给下一个所选节点，该节点位于所有下一跳节点的排列表中。如果所有邻居都被使用过，并返回了消息，则该消息将被送回到首次接收它的节点处。DFS方法（Vukojevic et al.，2008）适用于任意成本度量标准。当前节点的邻居根据它们提供的成本进度比进行排列，这样它们在尝试中依次被用来发现路由。

在图4-5所示的实例中，根据参考文献（Stojmenovic et al.，2002）提出的DFS算法，源节点S根据3个邻居到D的距离进行排序，然后将数据转发给距离D最近的节点B。同样，B对除发送方S之外的邻居A、C、F进行排列，并将数据转发给F。F将数据转发给N，N再将数据转发给M。M将数据转发给F，F已经被访问过。因此，F拒绝为M转发该消息。然后，由于节点M没有可用的邻居，因而它将消息转发给N。同样，N将消息返回给F。F不再将数据转发给它的第二个邻居M，因为它已经收到过来自于M的转发消息。于是，F将消息转发给它的上一个邻居G。G将消息转发给H，最终通过HLKJD到达D。在方案改进之前，DFS的路由路径为SBFNMFMNFGHLKJD。在DFS增强版（Vukojevic et al.，2008）中，节点可以通过偷听受访邻居的传输信息，来“获知邻居所处的状态”。在该实例中，当F将消息转发给N后，它将N和M从其可用邻居列表中删除。这样，改进的DFS路由路径为SBFNMNFGHLKJD。

图4-5 DFS路由路径(www.xing528.com)

（改进前为SBFNMFMNFGHLKJD，改进后为SBFNMNFGHLKJD）

然而，DFS方法在节点密集部署的“孤岛”区域应用效果并不好，因为在退出孤岛之前，当源节点开始尝试通往目标节点的另一条路由时，所有这些节点将被访问。为了解决这个问题，DFS仅应用于CDS节点（Vukojevic et al.，2008）。

参考文献（Stojmenovic et al.，2002）对支持QoS的DFS路由应用进行了深入讨论。基于自身物理位置信息，以及所有邻居周期性更新的位置信息，每个节点能够估计任意邻居当前的速度，估计链路将会存在多长时间。这些信息可用于发现一条支持特定连接时间要求的路由。此外，在进行DFS遍历时，需要将最低带宽要求和最大延迟考虑在内。一旦超过最大延迟，或者没有输出边能够满足最低带宽要求，将返回一条消息。路径上的中间节点记忆路径的上行链路和下行链路，这样就可以建立起源节点和目标节点之间的QoS通信。

针对任意地理路由协议，参考文献（Ma et al.，2008）提出了一种迂回模式（但它对贪婪路由没有影响）。当对第一个数据包进行路由时，可以采取策略来修剪根据地理路由协议建立起来的路径。当传输完第一个数据包后，得到一个修剪后的路径，后续数据包可以使用修剪路径进行转发。假定节点A转发一个数据包给B，之后又收到由另一个邻居C转发的同一数据包，则节点A立即寻找捷径直接向C转发其他数据包，至少绕过了节点B。这种算法需要寻找捷径的节点记忆一些状态信息。在参考文献（Stojmenovic et al.，2002）中，类似的迂回算法最初作为DFS进程的一部分，应用于DFS路由算法的特殊情况，如当C=A时，这是根据初始路由构建QoS路由的一部分。假设节点B获知其邻居A正在转发某个数据包，之后邻居C也在转发在该数据包，则跳数至少增加了2。然后，节点B可能让节点A来转发未来的数据包，这些数据包将被转发给邻居C，这样从A到C迂回了2跳。