一种无线移动网络路由选择的优化方法

技术领域

本发明涉及无线移动网络，尤其涉及高动态的无线移动网络中，路由选择的优化方法。

背景技术

随着无线移动网络的发展，各种无线移动网络在人们生活中被广泛应用，如车载自组织网络，车载自组织网络作为一种高动态的无线移动网络，具备以下几个方面的显著特点：

（1）节点密度分布不均匀，不同位置区域，不同时段内，节点的密度分布不同，例如在城市繁华区、上下班高峰期节点密度很大，而在高速公路、郊区等区域节点密度很小；

（2）网络拓扑变化频繁，各节点的位置变化速率取决于其所处区域的节点密度，如节点高速移动，位置变化很快；

（3）各节点能实时获取其所在位置信息，如通过节点（如车辆）上所配备的GPS设备；

（4）由于通信障碍物（如高楼建筑等）的存在，会导致节点虽然在彼此间的通信范围内，但是不能通信的情况；

针对上述特点的高动态无线移动网络，一般很难建立比较稳定的端到端的通信，所以如何能够快速而准确的进行路由选择成为该类无线网络（如车载自组织网络）的一个至关重要的任务，它直接决定了从源节点到目的节点的路由跳数、数据投递率、时延等重要性能指标。当前，针对高动态的无线移动网络的路由协议主要有基于拓扑的路由协议和基于地理位置的路由协议。

在基于拓扑的路由协议中，当两个节点的距离小于无线信号通信范围时，互为邻居节点，所有的路由学习完全依靠邻居节点之间交换路由项，节点通过链路状态协议向邻居节点通告链路状态。基于拓扑的路由方法主要分成两大类：主动路由和被动路由。主动路由基本思想是主动地定期进行路由表的广播和更新，在主动路由中，可以实时更新路由表，信息转发时延小，投递成功率高，但是频繁更新路由表会占用大量网络资源，利用率低，特别在节点密度很大时很容易造成网络拥塞。被动路由是只有源节点在有通信需求时才创建路由，通信结束后不维护路由，直到收到下一次需求，被动路由模式下总的路由开销较小，但是实时性不好而导致时延较大，成功率低的缺点。

在基于拓扑的路由协议中，需要知道全网的链路信息，目前MOPR（MOvement Predictionbased Routing，运动预测算法）算法是使用较多的一种，它通过节点的位置、速度和方向等信息来改善路由算法。该算法通过节点现在的位置来预测节点未来可能出现的位置，从而估计一条链路的生存时间。源点可以根据生存时间估计报文的传输时间从而选出一条最稳定的链路。

由此可见，基于拓扑的路由协议存在以下两个不容克服的缺陷：

（1）虽然处理过程快速收敛，找出的路径也是源点到目的点的比较短的路径，但是在应用于高动态的无线移动网络时，由于其网络拓扑变化非常频繁，特别是节点密度不是很大的情况下，节点移动速度很快，往往在报文还没有从源点转发到目的点时，链路节点已经移动，链路频繁断裂，在转发报文时找不到节点，造成丢包；

（2）在网络拓扑结构较大或者节点密度很大时，想要实时知道整个网络的拓扑是不现实的，也将造成相当大的网络负载，导致网络拥塞严重影响网络性能。

在基于地理位置的路由协议中，只需要知道本节点、邻居节点和目的节点的位置信息就可以进行路由转发，大大降低了路由开销。基于地理位置的路由投递策略思想几乎都遵循贪婪算法，即每一次总是选择距离目的点更近的邻居节点，因为基于位置的路由只知道本地的位置信息，并不知道全网的位置信息，所以很容易陷入局部最优，即在发送节点的通信范围内的所有节点中，发送节点距离目的节点最近，而陷入死循环中，一般来说基于位置的路由都有针对于局部最优的修复策略。

目前使用比较广泛的就是GPSR（Greedy Perimeter Stateless Routing，贪婪周边无状态路由）算法，GPSR算法的核心思想是贪婪路由和修复策略。所谓的贪婪路由就是永远朝着离目的节点更近的下一个节点投递报文，如图1所示，D为目的节点，当节点S有报文要向节点D发送时，节点S会在自己的所有邻居节点中选择一个距离节点D最近的节点作为下一跳节点，此时是节点B；修正策略，就是指当节点要向目的节点发送数据时，节点在其邻居节点中找不到比本节点距离目的节点更近的节点时，则采用修复策略——右手定则，如图2所示，当节点F从邻居节点E收到一个报文时，根据右手定则把报文转发给节点F的第一个逆时针反向上的邻居节点H。

由于在城市环境中，存在许多障碍物阻挡，使得GPSR路由性能不是很好，对此GPCR（Greedy Perimeter Coordinator Routing，贪婪周边协调路由）引入了协调节点，所谓的协调节点指位于十字路口处的节点，每个节点根据自己的邻居节点的位置坐标判定本节点是否为协调节点。在GPCR协议中，如果下一跳中有协调节点，则优先把报文转发给协调节点，否则按照贪婪路由思想进行路由，即在本地邻居节点中选择距离目的节点最近的节点作为发送报文的下一跳节点，当陷入局部最优时采用右手定则进行修复。

虽然相对于基于拓扑的路由方法，基于位置的路由不需要维护太多的路由信息，比较适合高度动态的无线移动网络，但是仍然存在以下缺陷：

（1）当网络节点比较密集时，例如上下班车辆高峰期或者市中心繁华区，此时节点移动速度较慢，拓扑结构变化缓慢，但每次转发报文仍然通过贪婪路由寻找下一跳节点，造成很多无谓的投递，增加网络负载和时延；

（2）修复策略中的右手定则，所选出的下一跳节点很有可能会向着远离目的节点的方向转发，增加时延，并且非常有可能耗尽转发时间而造成丢包。

发明内容

本发明的发明目的在于：针对上述存在的问题，提供一种增加报文投递成功率，降低时延，减少源点到目的点的跳数，提高网络的整体性能的路由选择优化方法。

本发明的一种无线移动网络路由选择的优化方法，包括下列步骤：

步骤1：构建局部区域的网络拓扑：

各节点周期性的判断本节点的邻居表中的邻居数目是否大于或等于定值Q，若是，则洪泛本节点的邻居表；

各接收节点根据所述邻居表在本地维护当前发送节点的邻接关系，若接收节点的邻居数目大于或等于定值Q，则所述接收节点洪泛当前发送节点的邻居表；

步骤2：发送节点的路由选择：

步骤201：判定发送节点的邻居数目是否大于或等于定值Q，若是，则根据发送节点的局部区域的网络拓扑，基于单源最短路径进行路由，若路由失败，则执行步骤202；

步骤202：根据发送节点、发送节点的邻居节点和报文目的节点的地理位置信息，基于地理位置的路由协议进行路由，若路由失败，则执行步骤203；

步骤203：发送节点存储待发送的报文，并在时间T后，返回步骤201。

本发明在同一无线移动网络拓扑中，根据节点密度的不同调用不同的路由协议，在节点密度大的局部区域（即发送节点的邻居数目是否大于或等于定值Q），因为密度大，故节点移动速度慢，拓扑变化缓慢，此时链路不会频繁断裂，基于单源最短路径进行路由，如常用的迪杰斯特拉Dijkstra算法，发挥其快速找出最短路径的优点，避免报文无谓的投递；在局部区域以外拓扑，基于地理位置的路由协议进行路由，如GPSR、GPCR等，利用其路由开销小能适应拓扑频繁变化的优点。本发明的实现，提升了报文投递成功率，降低时延，减少源点到目的点的跳数，提高网络的整体性能。

为了进一步保证本发明中，所构建局部区域的网络拓扑的准确性，在步骤1中，各节点每隔周期T1，对本节点的局部区域的网络拓扑进行老化处理：取本节点收到邻居节点的邻居表报文的时间为t1，老化处理的当前时间为t2，若所述t2、t1之差大于周期T1，则将所述邻居节点的邻接关系从本节点的局部区域的网络拓扑中删除。

本发明中，为了提升各节点维护其邻居表的实时与准确性，各节点的邻居表的维护操作为：

各节点周期性的广播节点位置信息，所述位置信息中包含信息产生的时间戳；各接收节点根据所接收的位置信息，更新邻居表，所述邻居表中包含邻居更新的时间戳；各节点每隔周期T2，启动对本节点的邻居表的老化处理：取本节点收到邻居节点的位置信息的时间为t3，当前启动老化处理的时间为t4，若所述t3、t4之差大于周期T2，则将所述邻居节点从本节点的邻居表中删除。

进一步的，为了克服现有的贪婪路由协议的修复策略中的右手定则所选出的下一跳节点很有可能会向着远离目的节点的方向转发，增加时延，导致因耗尽转发时间而造成丢包的缺陷，本发明对贪婪路由协议的修复策略进行了改进，即：当前发送节点在选择下一跳节点时，在本地邻居节点中选择距离目的节点最近的节点作为下一跳节点（若邻居节点中存在协调节点，则优先选择协调节点为下一跳节点），且当在发送节点的通信范围内的所有节点中，发送节点距离目的节点最近，则选择离目的节点方向最近的邻居节点为下一跳节点。

综上所述，由于采用了上述技术方案，本发明的有益效果是：

（1）本发明在原有传统路由协议的基础上，提出改进，将基于地理位置的路由和基于网络拓扑的路由结合起来，分场合调用，充分利用它们的优点，利用最少的软件和开销，增加了报文投递成功率，减少了时延，减少了从源点到目的点的跳数，提高了网络的整体性能。

（2）改进的贪婪路由的修复策略有效的降低了报文朝着远离目的节点投递导致丢包的可能性。

(3)本发明的路由选择方法覆盖范围广，能快速、准确的适合各种大小的无线移动网络。

附图说明

本发明将通过例子并参照附图的方式说明，其中：

图1是现有贪婪路由示意图，图中虚线表示节点通信范围；

图2是现有贪婪路由中的右手定则示意图；

图3是本发明具体实施方式中，局部区域划分示意图；

图4是本发明具体实施方式中，节点的邻居表洪泛流程图；

图5是本发明具体实施方式中，节点的邻居表广播流程图；

图6是本发明具体实施方式中，节点接收邻居表的处理流程图；

图7是本发明具体实施方式中，对局部区域的网络拓扑老化流程图；

图8是本发明具体实施方式中，节点的邻居表更新流程图；

图9是本发明具体实施方式中，节点的邻居表老化流程图；

图10是本发明具体实施方式中，贪婪路由的修复策略示意图。

具体实施方式

本说明书中公开的所有特征，或公开的所有方法或过程中的步骤，除了互相排斥的特征和/或步骤以外，均可以以任何方式组合。

本说明书（包括任何附加权利要求、摘要和附图）中公开的任一特征，除非特别叙述，均可被其他等效或具有类似目的的替代特征加以替换。即，除非特别叙述，每个特征只是一系列等效或类似特征中的一个例子而已。

本发明为了将基于地理位置的路由和基于网络拓扑的路由结合实现，首先需要针对节点的密度状况进行局部区域的划分，因为在局部区域（节点密度大的区域）内，本发明采用基于单源最短路径进行路由，所以还需要知道这个局部区域的网络拓扑结构。整个网络拓扑中，密度大小的判定主要以节点的邻居数目为标准。当节点邻居数大于或等于定值Q1（根据实际网络情况给定Q1，通常可设定为6～16个），则认为该节点处于密度大的局部区域，否则认为该节点位于密度大的局部区域外，以车载自组织网络为例，图3给出了一个划分出局部区域的示意图，图中共涉及两个局部区域，局部区域I、局部区域II。参见图4、5、6，局部区域的网络拓扑的建立流程如下：

(1)每个节点周期性的判断其邻居表中邻居数目是否大于或等于一定值Q1，节点可通过周期性的产生检查邻居数目的自消息来启动判断操作，在本发明中，节点会产生多个不同操作的自消息，如用于检查邻居数目的自消息，用于老化邻居表的自消息，用于老化局部区域的网络拓扑的自消息等；

(2)如果某个节点（如节点A）的邻居数目大于或等于一定值Q1，那么通过广播消息洪泛节点A的邻居表，该广播消息中包含时间戳；

(3)收到报文（上述广播消息）的接收节点（如节点B）根据报文产生的时间，即上述广播消息中包含的时间戳，首先判断是否已收到过该报文，若否，则更新网络拓扑结构，即更新节点A的位置信息，并且将节点A的邻居表转为节点A的邻接关系存储；否则删除所收到的报文；

(1.4)如果节点B邻居数目大于或等于一定值Q1，那么节点B再次洪泛节点A的邻居表，即广播所收到的报文。

因为网络自身的高动态性，所以本发明建立的这些局部区域也是动态的，随着节点的运动局部网络拓扑产生，随着节点的运动建立好的局部拓扑也会老化，以进一步确保本发明的准确性，参见图7，具体的老化流程为：

首先，节点以周期T1（T1的取值实际应用情况，通常为1s～1.5s）产生老化拓扑的自消息，该自消息用来老化局部区域的网络拓扑，每过T1时间产生一个老化拓扑的自消息；

取t1表示当前时间，t2表示节点A收到节点B的邻居表报文的时间，当t2-t1≥T1时,将节点B的邻接关系从节点A的局部拓扑中删除。

不管是用基于地理位置的路由还是选用基于拓扑的路由，邻居表的维护是否实时直接影响报文投递的成功率，传统的邻居表的更新和老化根据所收到的报文的条数，当节点收到的报文条数达到一定值M（根据实际网络给定）时，老化邻居表。但是对于高动态的无线移动网络，由于节点密度分布非常不均匀，很难给定一个特定的值满足全局网络，M值较大时，在节点密度稀疏的区域，报文条数达到M所需时间很慢，有的节点已经移动出无线通信范围，但是报文条数未达到M值，邻居表还没有老化，这个节点还存在于邻居表中；M值较小时，在节点密度大的区域，报文条数很快就能达到M，邻居表老化过快。导致邻居表的维护不够实时，本发明对现有的邻居表实时维护方法进行了改进，主要包括邻居表的更新和老化，以确保邻居表的实时性和准确性。

参见图8，邻居表的更新流程如下：

(1)节点位置发生变化后，广播位置信息，该信息中包含信息产生的时间戳；

(2)收到此信息的节点立即保存上述节点的位置信息，并且更新邻居表，其中邻居表中包含邻居更新的时间戳。

参见图9，邻居表实时老化的流程如下：

(3)节点以周期T2（T2的取值实际应用情况，通常为1s～1.5s）产生邻居表老化自消息，用于启动老化邻居表的操作；

(4)取t3表示当前时间，t4表示节点A收到节点B上一次位置发生变化而广播报文的时间，当t3-t4≥T2时，将节点B从节点A的邻居表中删除。

本发明中，若当前发送节点在局部区域内，则发送节点基于单源最短路径进行路由，所谓单源最短路径，即用于计算一个节点到其他所有节点可达的最短路径。按照递增长度来计算，源点到其它节点的路径，先求出一条最短的路径，每次参考最短的路径求出路径次短的一条最短路径，如常用的Dijkstra算法。本发明中，在密度大的局部区域内，节点基于单源最短路径进行路由选择时，有两种可选方案：一种是在局部区域的网络拓扑建立好的同时，根据单源最短路径算法实时动态地计算出每个点到其他节点的最短路径，并将其存储在路由表中，路由时直接查找；另外一种是节点在路由时，调用单源最短路径算法直接寻找到目的点的最短路径。

而在非局部区域，即密度低的区域，基于地理位置进行路由，即可以是已有的基于地理位置路由协议，也可以是本发明改进的贪婪路由协议，本发明对现有贪婪路由协议的改进在于修复策略的改进，当本节点陷入局部最优模式时，总是选择离目的节点方向最近的邻居节点为下一跳节点，即所选择的邻居节点为：发送节点与该邻居节点所在直线，与发送节点与目的节点所在直线的夹角最小。参见图10，节点A为发送节点，节点D为目的节点，节点B、C、M为节点A的邻居节点，θ₁、θ₂、θ₃分别为节点B、C、M与节点A所在的直线，与节点A与节点D所在直线的夹角。若按照已有的右手定则，则会选择节点B为下一跳节点，但是节点B方向远离目的节点D，很有可能在后面的转发过程中因为耗尽转发时间而丢包；而基于本发明的修复策略则是选择节点M为下一跳节点，因为夹角θ₃是其中最小的，即在节点A的所有邻居节点（节点B、C、M）中，节点M离目的节点方向最近。从而客服了右手定则朝着远离目的节点的方向转发报文的缺陷，有效降低了因为耗尽转发时间造成丢包的概率。将本发明改进的修复策略应用到现有的GPSR或GPCR协议中，可得到改进的GPSR+、GPCR+协议。基于GPSR+、GPCR+的方案实施，依赖于本节点（当前发送节点）、邻居节点和目的节点的实时地理位置信息，每个节点可以配备GPS或者其他本地服务，从而节点能够方便快捷地得到自己的位置信息，邻居节点的位置信息通过邻近的节点周期性地交换地理位置信息获得，目的节点的位置信息通过数据包中的内容获得。

一般来说由于城市中障碍物的阻挡和无线通信范围的限制，每个密度大的局部区域不会太大，但不排除有特殊情况的出现，当局部区域的范围较大时，即节点数目较多，因为单元最短路径算法需要知道局部区域所有节点的位置信息和邻接关系，这时可以采用OSPF(OpenShortest Path First开放式最短路径优先）分区域协议将范围大的局部区域通过分区域来通告拓扑信息，不至于在这些大范围的局部区域内造成网络拥塞。调用OSPF分区域协议的局部区域节点个数根据网络情况而定，本发明中可设为200个，当某个局部区域的网络节点超过200个时，调用OSPF分区域协议对该局部区域进行分区。

实施例1

以车载自组织网络为例，实现本发明的路由选择的具体步骤如下：

S101：节点收到单播报文；

S102：如果报文的目的节点不是本节点，那么需要路由；

S103：判断本节点是否在局部区域内，即本节点的邻居数目是否大于或等于定值Q1（本实施例中，Q1取为8），若是，则执行S103-1；否则，执行S103-2；

S103-1：采用Dijkstra算法进行路由，如果路由失败，说明目的节点不在该局部区域内，那么执行步骤S103-2；

S103-2：采用GPCR+算法进行路由，如果路由失败（即节点在所收到报文的转发时间内，未能将报文投递成功），那么执行步骤S103-3。

S103-3：存储本报文，定时一段时间T（时间T根据实际网络给定，通常可设为0.2s-1s，本实施例1中设为0.5s）后，再次执行步骤S103。若失败5次后，还是路由失败，那么删除本报文。

实施例2

当源点和目的点距离太远，受无线电传播距离和城市环境中障碍物的阻挡等影响，报文丢失现象会比较严重。本发明的路由算法可以引进路边单元RSU进行辅助，来改进源点和目的点太远时的缺陷。RSU只有在两种情况下转发报文，分别是GPCR+路由转发陷入局部最优、源节点和目的节点距离太远时，RSU不参与局部区域的路由选择。本发明引进的RSU存在两种：普通RSU和中心RSU。

普通RSU：由无线模块和有线模块组成，无线模块与普通车辆进行通信，有线部分与中心RSU进行通信。其分布是由无线通信的有效距离来确定。普通RSU扮演报文转发的角色，它接收车辆以及中心RSU发过来的报文，并进行转发。

中心RSU：只有有线模块，只与普通RSU通信，记录着所有普通RSU的位置信息，中心RSU只接收普通RSU发来的报文，然后选择距离目的节点最近的普通RSU作为下一跳进行转发。

普通车辆与普通RSU之间的无线交互流程为：

(1)普通车辆通过无线方式向普通RSU发送数据；

(2)普通RSU通过无线方式向普通车辆回传数据。

普通RSU与中心RSU的有线交互流程为：

(1)普通RSU通过有线方式向中心RSU发送数据；

(2)中心RSU通过有线方式向普通RSU回传数据。

本发明中，RSU只有在以下两种情况下参与报文的转发，普通RSU、中心RSU、车辆处理报文的流程如下：

(1)在使用GPCR+算法时，报文转发陷入局部最优，启动修复模式时，如果本节点的邻居里有RSU，则将报文发往离本节点最近的RSU（选择离本节点最近的RSU为下一跳节点），提高报文发送成功率；否则按照本发明的GPCR+的修复策略进行修复；

(2)当本节点与目的节点之间的距离超过一定限度时，如果本节点的邻居节点中存在RSU，则将报文发往离本节点最近的RSU，利用RSU进行报文转发，来减少报文丢失的概率。

本发明基于RSU辅助的车载自组织网络报文处理具体步骤如下：

S201：节点收到单播报文；

S202：如果报文的目的节点不是本节点，那么需要路由；

S203：判断本节点和目的节点的距离是否大于定值d，

若否，则再判断本节点是否在局部区域内，若是，则执行步骤S204；否则执行步骤S205；

S204：采用Dijkstra算法进行路由，如果路由失败，说明目的节点不在该局部区域内，那么执行步骤S205；

S205：基于本发明的GPCR+路由协议、普通RSU、中心RSU进行路由，具体如下：

S205-1：判断发送节点的邻居节点是否有RSU，若有，则执行步骤S205-2；否则执行步骤S205-3；

S205-2：将报文发送给离本节点最近的RSU，若所述RSU为普通RSU，则将报文发送给中心RSU；再由中心RSU将报文发送给离本节点最近的RSU，然后执行步骤S205-3；

S205-3：采用GPCR协议进行路由，若陷入局部最优，则判断当前发送节点的邻居节点是否存在RSU，若是，则执行步骤S205-4；否则，执行步骤S205-5；

S205-4：将报文发送给离本节点最近的RSU，若所述RSU为普通RSU，则将报文发送给中心RSU；再由中心RSU将报文发送给离本节点最近的RSU，然后继续执行步骤S205-3；

S205-5：采用GPCR+的修复模式，即选择离目的节点方向最近的邻居节点为下一跳节点；

S206：如果路由失败，那么存储本报文，并且定时一段时间后，再次执行步骤S205。如果路由失败次数超过预设阈值N（本实施例中N取5），如当累计重复执行步骤205超过5次时，那么删除本报文。

本发明并不局限于前述的具体实施方式。本发明扩展到任何在本说明书中披露的新特征或任何新的组合，以及披露的任一新的方法或过程的步骤或任何新的组合。