基于位置信息的自组织网络路由算法研究

范溥

摘要：随着定位技术的发展，位置信息的获取成本也在逐步降低，由于借助于位置信息可以使路由的开销大大降低，因此人们也越来越重视自组织网络基于位置信息的算法研究，为了使这种算法更成熟，性能更优良，该文分析了现有基于位置信息的路由算法，并重点研究了单播路由算法中的贪婪转发算法与空洞处理算法，以供同行参考。

关键词：位置信息；自组织网络；贪婪转发算法；空洞处理算法

中图分类号：TP393 文献标识码：A 文章编号：1009-3044（2016）04-0037-02

无线自组织网络属于多跳网络中的一种，它不同于之前的无线单跳通信网络。对于无线单跳网络来说需要固定网络设施做支撑，如要实现数据的转发需要由基站来支持，而对于无线自组织网络来说进行通信时不需设施作支持，并且无线自组织网络的各节点不但可以当做终端来收发数据，而且还可当做一种路由器来转发各种数据，由于新特征在无线自组织网络的融入，这也造成了之前的路由算法不能适应新形势的发展，于是人们开始探索研究基于位置信息的自组织网络路由算法。

1 基于位置信息的路由算法

由于自组织网络不存在固定的基础设施，自组织网络的各个节点与其他节点的通讯只能在通讯范围内，所以任意节点对之间要想实现自由通讯，只能依靠多个节点间的相互转发来实现，这也就是我们通常所说的多跳路由。按照路由算法使用的信息情况这种算法大致分为两类：基于位置信息的路由算法与基于拓扑信息的路由算法。下面我们就重点介绍一下基于位置信息的路由算法。

以节点的具体位置信息为基础进行转发是基于位置信息的路由算法的主要工作方式，它不同于最初的只借助目的节点位置信息的转发方式，当前的基于位置信息的路由算法不仅要用到目的节点的位置信息，而且还要用到节点自身位置信息与一跳后的邻居节点位置信息，在这个转发的过程中，中间节点对下一跳的具体转发节点可自主进行选择。所以该节点到相应目的节点间的路径不用具体的去进行维护，也不用发送相关控制包来对路径状态进行更新。由于网络拓扑的变化影响节点下一跳的选择也只是在该节点的一跳范围之内，因此网络拓扑发生变化时，影响基于位置信息的路由算法要远小于基于拓扑信息的路由算法，此外基于位置信息的路由算法局域性通常都比较好，因此它的网络扩展性也相对较好。

2 基于位置信息的单播路由算法

单播路由算法可实现从源节点至目标节点唯一连通路径的构建，若数据需要从源节点传输至目的节点时，可借助某种算法从相应邻居节点中挑选出某个节点来作为下一跳目标，数据到达目的节点的过程就是就是此算法在中间节点重复执行的过程。就当前的基于位置信息的路由算法而言，其中人们应用比较多的一种算法就是贪婪转发算法，它具有高效、简单的特点，但这种算法有个局限性，用想利用它转发数据，前提是当前的网络密度要足够高，但实际部署的网络，难免会有不连贯的区域出现在网络局部，而贪婪算法遇到不连贯区域时，由于局部最小化问题会导致贪婪转发算法的传输失败，我们通常把造成贪婪转发不能成功的不连贯区域统称为通讯空洞，为了更好应对贪婪转发算法的这样缺陷，人们研究了一种空洞处理算法，来承担起遇到空洞时贪婪算法的转发任务，实现路由任务的最终顺利完成，所以贪婪转发算法与空洞处理算法共同构成了一个全面完善的路由协议。下面我们就分别介绍一下这两种算法。

2.1贪婪转发算法

根据某种标准以当前节点的邻居节点位置信息以及目的节点位置信息为基础，来进行下一跳局部最优节点的选择，这种转发方式并重复应用于中间所有节点，直到目的节点的到达，这就是贪婪转发算法。当前，人们根据算法选择下一跳节点标准的不同，已经研究出了很多中贪婪转发算法。

最初的贪婪转发算法选择最优下一跳节点的标准是依据几何计算结果进行的，其具体选择过程如下图1所示：

当前节点用图中的S表示，目的节点用D表示，不同的选择标准，也会得到不同的下一跳节点，下面我们就总结一下各种贪婪转发的形式：

1） 随机转发

从当前的邻居所有邻居节点中随机任意选择一个距离目的节点更近的节点当做下一跳的目标节点，依次类推这就是随机转发过程。如在图1中，S节点的邻居节点有A、R、B、C、F，在这几个节点中，A、B、C、F节点与目的节点的距离都比S节点本身近，所以S节点的下一跳节点可从这四个节点中随机选取一个，这就是随机转发。

2） 最近方向转发

最近方向转发主要是按照在当前节点连接目的节点的方向上，选择一个距离目标节点最近的邻居节点作为最优下一跳节点。在图1中，依照这种转发方式，C节点将作为S节点的最优下一跳节点进行各项任务的转发。

3） MFR转发

在利用MFR转发时，节点的前进值根据当前节点与目的节点连线上的正交投影来定的，当前节点选择的下一跳最优节点是全部邻居节点中正向前进值最大的节点。在如图1所示，节点S与D连线上具有最大值投影的是A节点，所以S节点的下一跳节点将选择A节点。

4） NFP转发

在利用NFP转发时，下一跳最优节点我们选择的是与节点SD连线方向上，所有当前节点邻居中，正向前进值最小的邻居节点。如图1所示，S节点的最小正向前进值的邻居节点为G节点，所以S节点的最优下一跳节点将选择为G节点。

5） MAR转发

MAR转发是选择的下一跳节点是距离目的节点最近的邻居节点，如图1所示，目的节点D最近的节点为E，所以当前S节点的下一跳节点将选择节点E。

2.2 空洞处理算法

在贪婪转发失效的情况下，接下来的数据包转发任务将由空洞处理算法来继续作业，直到运行环境能够继续让贪婪转发运行为止，然后再由贪婪转发算法来完成任务，若贪婪转发一直都未能运行，哪就由空洞处理算法来完成任务，下图2为贪婪转发算法失效示意图。

如图2所示，由于在S节点的所有邻居节点中，任何一个邻居节点到目的节点D的距离都远于A节点，这样就造成了S节点无法利用贪婪转发方式来进行下一跳节点的选择，所以，如果只单单借助贪婪转发数据包将不能从当前节点S向目的节点D顺利传输。下面我们就来介绍几种常见的空洞处理法，来顺利解决此类问题。

1） 基于拓扑的空洞处理法

这种算法对空洞问题的处理是借助拓扑信息进行的，泛洪是这种算法中主要用到的方法，利用全网泛洪拓扑连通的具体路径在全网范围内找到，但其存在一个致命的缺点就是需要的开销通常都较高。为了减小其开销，我们通常不采用直接去查找到目的节点的路径，往往都是通过查找可以恢复贪婪转发节点的路径，来实现数据到目的地的最终传输。

2） 基于平面图的空洞处理算法

这种算法主要是根据平面图的特性来对数据包进行传输，这种算法在处理贪婪转发失效时的开销通常都比较低，这主要是由于网络平面图具有局部性的特点。我们所说的平面图是指一种非自交图，它能够在平面内嵌入，RNG以及GG是当前用来平面化处理网络的主要方式。对网络进行平衡化处理过后，然后按照转发策略自空洞边缘开始转发。

3） 基于几何特性的空洞处理算法

通过网络拓扑的几何特性来对数据包进行发送是该算法的主要工作模式，BOUDNHOLE算法是这类算法的代表，对于某节点贪婪转发成功与否的判断借助TENT规则来进行，若判断出该节点没有成功，那么就用Stuck节点来表示该节点，并且还要继续把这个空洞的所有Stuck节点全部找出来，在得到了同一空洞的所有Stuck节点之后，沿着Stuck节点进行数据包的发送，直到贪婪转发能正常进行。

3 结束语

总之，随着现代定位技术的飞速发展，基于位置信息的路由算法以其简单、高效的优势，在自组织网络路由算法的研究中也越来越受到人们的重视，我们可以推断在不久的将来，在自组织网络路由算法中基于位置信息的路由算法必然会成为主流，但就目前的基于位置信息的自组织网络路由算法而言，性能还不是很好，还有很大的可提升空间，为此我们必须坚持不懈，继续进行深入研究，只有这样才能使这种算法的性能更优良，才能使这种算法更好地为我们服务。

参考文献：

[1] 胡淼，李剑峰.车载自组织网络中基于贪婪算法的地理位置路由[J].中兴通讯技术，2011（3）.

[2] 张永晖，林漳希，刘建华，等.基于位置信息的仓储容迟网络路由算法[J].电信科学，2012（11）.

[3] 侯守峰，周小佳，闫斌.无线传感器网络中基于位置信息的路由算法研究[J].计算机工程与设计，2010（22）.