基于复杂网络理论的移动自组网路由算法刍议

来源:用户上传      作者:

　　摘要移动自组网中节点通信时路由开销较大，从而引起整个自组网的能耗过高。为了解决这一问题，针对移动自组网的现实组网特征进行了研究，提出了基于复杂网络理论的移动自组网路由算法。
　　关键词移动自组网复杂网络理论OLSR协议AODV协议路由算法
　　
　　移动自组网的最大特征是具有多跳性、动态拓扑性以及对等性，它是一种无线分布式移动通信网络。目前关于移动自组网的路由研究都是在以下几个前提下进行的：（1）任意节点间都存在一条从源节点到目的节点的完整路由路径。（2）大部分路由研究都基于节点链路是双向的，即节点通信具有交互性。因此，基于移动自组网路由算法的研究成熟的有三大类，分别是先验式路由，反应式路由和混合式路由。先验式路由是指节点在路由发现之前首先维护自己的路由表信息，当网络拓扑结构发生变化时，对路由表信息进行即时更新，源节点发送报文时，根据路由表获取目的节点路由路径。例如OLSR[1]协议。反应式路由是指源节点广播路由请求，该请求被邻居节点进行转发，路由路径依照路由请求的路径建立。例如AODV[2]协议。混合式路由指节点在以自己为中心的区域内按照表驱动路由，在区域外按照按需路由。而在实际的移动自组网中，存在节点的孤立性和边缘性。文献[3]通过实验验证了移动自组网中存在单向、非均衡路径。文献[4]通过对文献[5]的实验数据集进行研究，发现节点的移动具有以下特点：（1）趋向性。大部分节点趋向于某个特定位置。（2）特异性。某些节点能够和大多数节点建立通信。（3）时变性。节点的移动随时间变化。这一现象类似于现实生活中的人类社会，一部分节点具有领导感染力，促使其他节点向其凝聚；某些节点活跃，善于和大多数节点通信；节点的活动具有时间性，我们称之为复杂性。本文基于此，提出符合移动自组网节点复杂性的路由算法，能有效的提高节点路由效率，降低路由开销。
　　一、基于复杂网络理论的移动自组网路由发现机制
　　在移动自组网中，节点移动从广义角度说，具有随机性和任意性，即节点在任意时刻都有可能发生位置的变化；从狭义角度说，节点移动具有社区性，即节点大多数时间总是在某个区域内移动。这一现象用复杂网络的“六度分离”理论[6]来解释，即节点之间的平均距离为六，在一定的条件和环境下，任意两个节点建立路由路径最多经过六次数据转发即可到达。这个距离是整个网络的平均距离，有可能在六级转发内节点的路由路径还没有建立，也有可能早已建立了路由路径，但是从整个网络的整体路由建立上来说，其路由建立的平均跳级数为六。
　　1.1 路由发现。路由发现发生于源节点到目的节点的半圆弧范围内，在梯度方向上选取最优路径进行建立。路由发布消息由源节点序号、源节点地址、广播ID、目的地址、目的节点序号、跳级计数器等六部分组成。具体的路由步骤如下：
　　步骤1：源节点在从自身到目的节点的梯度方向范围内向邻域广播路由消息。
　　步骤2：中间节点接收到路由消息后，作判断
　　步骤3 ：若跳级计数器<=6，路由消息已经传递到目的节点，则沿梯度方向选取最佳步长建立路由路径；否则，转到步骤4。
　　步骤4 ：源节点在路由方向上选择其邻域范围内最接近的，符合最佳步长条件的节点作为第一级跳节点，该节点在自身到目的节点的梯度方向范围内向邻域广播路由消息，重复步骤2，3，4，直到建立源节点到目的节点的路由路径时，停止路由消息的广播。
　　1.2 路由管理和维护。在该路由算法中，各节点需要对路由信息记录表进行管理和维护。当路由消息在节点的路由记录表中时，再次接收到该路由消息则予以丢弃，否则，存储入路由信息记录表。当路由信息在移动自组网整个节点路由建立时间范围内，则继续存储该路由消息，否则，删除该记录消息。
　　二、实验分析与评估
　　本实验重点从节点数目和移动速度两个角度考察路由开销指标，并与AODV 协议和OLSR协议进行对比。其星号表示AODV协议，方块表示OLSR协议，圆圈表示本文路由算法。
　　实验场景一：1000m×800m 的拓扑区域，最大运动速度1m/s，10 个数据连接，节点数分别为15、30、50 个。当移动自组网中节点的数目发生变化时，最优路径的选择会产生相应的变化，从而引起路由开销的变化当移动自组网中节点的数目增加时，路由中转的几率增大，整个移动自组网中由于通信需要，路由开销逐渐增加。当节点数目增加到一定程度时，由于AODV 协议是向可通信的邻域范围内广播路由消息，此时所耗费的路由开销最高，而OLSR协议是在路由表信息里有选择的发布路由消息，所消耗的路由开销较低。本文的路由算法中，有针对性的沿路由方向发布路由消息，能够获得较少的跳级数。有利于路由路径建立，当节点数目增多时，路径建立的路由开销相对较小。
　　在移动自组网中，节点移动速度的变化同样会引起路由路径建立开销的增大，当节点移动速度变化时，初期各协议的路由开销总体都是增加的，但是由于路由路径建立方式的不同，不同协议之间路由开销有一定的差异，当节点速度达到一定程度时，各节点之间路由建立较为容易，此时路由开销又会逐渐减少。本文的路由算法由于对梯度方向做及时的路由方向调整，总体效果优于AODV协议和OLSR协议。
　　三、 结语
　　通过对移动自组网节点真实路由情况进行研究发现，节点的移动具有复杂性，基于此，对移动自组网节点的路由路径选择应用复杂网络理论是具有价值的，不仅可以降低路由开销，而且可以减轻整个移动自组网的存储压力，进一步提升网络的健壮性。在对节点的路由路径进行选择时，提出了最优路径的选择依据，即在梯度方向夹角较小的条件下，寻求沿源节点到目的节点的梯度方向中具有最速下降特点的节点作为下一级跳路由节点，该思想在一定程度上有助于路由路径的快速建立，并且具有较少的跳级数。未来的研究将重点放在网络路径平均建立时间和最优路径规则性判断条件。
　　
　　作者简介：
　　任岩（1989― ）男，汉族，西北民族大学电气工程学院，籍贯：山西省大同市，研究方向

转载注明来源:https://www.xzbu.com/1/view-14618543.htm