基于接触预测的大规模移动容迟网络分簇路由方法及其系统

摘要

本发明涉及基于接触预测的大规模移动容迟网络分簇路由方法及其系统，包括：分析大规模城市出租车网络的真实数据集，揭示其固有的接触与分簇特性；设计节点间的接触模型，确定节点间接触间隔时间的概率分布表达形式；设计并实现基于接触预测的分布式分簇路由算法，在大规模的动态环境下把彼此间接触概率较大的节点划分到同一分簇内部；设计并实现基于直接投递的簇内路由算法和基于洪泛的簇间路由算法，在分簇的基础上保证路由传输的有效性和可扩展性。本发明可以广泛应用在大规模城市交通网络的消息通信当中，如动态导航系统、车辆自动驾驶系统、车载娱乐系统等。

主权项

一种基于接触预测的大规模移动容迟网络分簇路由方法，其特征在于包含以下步骤：步骤1)、分析城市出租车网络轨迹数据集的网络特征；根据城市出租车网络轨迹数据集对网络的接触间隔时间持续时长进行特性分析，确定接触间隔时间的概率分布形式，对网络的平均聚类系数进行分析，揭示网络中节点的分簇行为；在对网络特性进行分析的基础上，提出网络满足的三个假设，并推导出接触间隔时间概率分布的具体表达形式，具体的在网络满足：对于任意的两个节点来说，在很短的Δt时间内，同时接触两次或者两次以上是个小概率事件；在不重叠的时间段内，节点A,B接触次数是互相独立的；接触持续时间相对接触间隔时间忽略不计的三条基本假设条件下，任意的节点对之间接触次数满足泊松分布，节点对之间的ICT服从指数分布，同时节点对之间的相遇次数服从泊松分布，在定数截尾实验条件下，利用贝叶斯参数估计的方法，计算r个ICT的联合密度函数，对接触概率进行预测；步骤2)、以节点间的接触概率作为分簇的标准，把未来一段时间内接触概率大于设定阈值的节点划分到同一个簇内部；每个节点根据本地发生的事件触发来更新本地保留的分簇信息表和网关信息表；当两个节点发生接触时更新彼此之间的接触概率，交换彼此的表信息，并进行所在分簇是否满足分簇标准的检查过程；并且每隔一定的周期更新相关表的接触概率信息，并判断是否要更换分簇；且在网关有效时间超时时重置分簇的网关节点或置网关节点失效；步骤3)、网络中的节点可根据分簇的信息动态地选择路由策略；该网络的路由策略划分为簇内路由和簇间路由策略，当节点发现数据包的目的节点与本地节点属于同一个分簇时，节点将执行簇内路由算法，此时采用直接投递的策略，即节点遇到数据包的目的节点后才转发数据包，考虑到同一簇内的节点间接触概率较大，在未来的一段时间内两节点发生接触的可能性较高，进行直接投递在保证一定成功投递率的同时可以减少数据包的副本数量；当目的节点与本地节点不属于同一个分簇时，执行簇间路由算法，采用基于洪泛的路由策略，节点把数据包转发给网关节点，或者当该节点与不同分簇的节点接触时，如果这个分簇内部没有该数据包的副本，则同样向对方节点转发数据包，实现高效的消息传输机制。