基于交通流量的分簇路由查找的方法、装置及系统

摘要

本发明提供一种基于交通流量的分簇路由查找的方法、装置及系统，该方法，包括：接收车辆节点发送的数据请求；根据所述数据请求对应的源节点信息、目标节点信息，在路由信息表中查找是否存在与所述数据请求对应的中继簇首节点，其中路由信息表存储有多个中继簇首节点；若不存在与所述数据请求对应的中继簇首节点，则通过路由获得所述数据请求对应的至少一个中继簇首节点；将所述数据请求通过对应的至少一个中继簇首节点发送至目标节点。以降低路由查找中的网络开销，增加网络的有效吞吐量，提升路由查找的效率。

权利要求

1.一种路由查找的方法，其特征在于，包括：

接收车辆节点发送的数据请求；

根据所述数据请求对应的源节点信息、目标节点信息，在路由信息表中查找是否存在与所述数据请求对应的中继簇首节点，其中路由信息表存储有多个中继簇首节点；

若不存在与所述数据请求对应的中继簇首节点，则通过路由获得所述数据请求对应的至少一个中继簇首节点；

将所述数据请求通过对应的至少一个中继簇首节点发送至目标节点；

其中，建立路由信息表，包括：

确定当前道路交通流量，并判断当前道路交通流量是否大于预设门限流量；

若所述当前道路交通流量大于所述门限流量，则按照道路路段进行簇划分，得到中继簇首节点；

若所述当前道路交通流量小于等于所述门限流量，则按照预设通信范围距离进行簇划分，得到中继簇首节点；

将所述中继簇首节点进行标识，生成路由信息表；

其中，按照道路路段进行簇划分，得到中继簇首节点，包括：

根据电子地图保存的多个路段信息，并按照预设路段间隔将所述路段划分为至少一个网格簇；

根据车辆节点当前的位置和移动速度在所述网格簇中确定所述网格簇的中继簇首节点；对应的，所述中继簇首节点为簇内停留时间最长，和簇内成员连通性最好的节点，具体根据节点的稳定性获得，其中根据网格簇的边界范围参数（x1,x2,y1,y2）和车辆节点当前的运行方向，得到车辆节点和网格簇边界的距离，且得到车辆节点在簇内停留时间；节点之间周期性传播hello包的时候，如果在同一个簇内的节点与当前节点进行hello通信，则将当前节点的Count+1，每次节点进入一个新簇则Count清零，并获得节点的稳定性：Stabilization=|x-x1|/vx+Count，且选择簇内稳定性最大的节点作为所述中继簇首节点，其中车辆节点当前的位置（x,y）和移动速度v，车辆节点当前的位置表示所述当前节点的位置；

其中，按照预设通信范围距离进行簇划分，得到中继簇首节点，包括：将包括所有车辆节点的通信范围距离区域划分为一个网络簇；

根据每个车辆节点的平均位置信息和平均速度信息，分别计算每个车辆节点的值数据，对应的，选择一个节点作为簇首，(x,y,v)分别是簇内节点的平均位置和平均速度信息，(xi, yi, vi)是簇内成员的位置和速度信息，获得节点的值数据（Value），；

将所述值数据最小时对应的所述车辆节点作为所述中继簇首节点，所述当前节点为所述网络簇中的节点。

2.根据权利要求1所述的方法，其特征在于，还包括：建立路由信息表。

3.根据权利要求1所述的方法，其特征在于，在路由信息表中查找是否存在与所述数据请求对应的至少一个中继簇首节点信息之前，还包括：若当前节点所在的网格簇中包括所述目标节点信息，则通过簇首节点发送所述数据请求至所述目标节点，且所述目标节点返回应答信息；

所述当前节点包括源节点。

4.根据权利要求1所述的方法，其特征在于，还包括：

若在路由信息表中存在与所述数据请求对应的中继簇首节点，则通过所述中继簇首节点向所述目标节点发送所述数据请求。

5.根据权利要求1所述的方法，其特征在于，通过路由获得所述数据请求对应的至少一个中继簇首节点信息，包括：根据源节点信息、目标节点信息确定中继节点的范围，判断所述源节点与所述目标节点是否在同一道路上；

若所述源节点与所述目标节点在同一道路上，则在中继节点范围的第一预设区域内判断当前节点是否属于所述第一预设区域，若所述当前节点属于所述第一预设区域，则所述当前节点向所述第一预设区域的中继簇首节点发送所述数据请求；若所述当前节点不属于所述第一预设区域，则丢弃所述当前节点，其中所述第一预设区域包括若目标节点D在源节点S的正东/南/西/北方向上，源节点S朝着目标节点D所在的1/2区域；

若所述源节点与所述目标节点不在同一道路上，则在中继节点范围的第二预设区域内判断所述当前节点是否属于所述第二预设区域，若所述当前节点属于所述第二预设区域，则所述当前节点向所述第二预设区域的中继簇首节点发送所述数据请求；若所述当前节点不属于所述第二预设区域，则丢弃所述当前节点，其中，所述第二预设区域包括若目标节点D在源节点S的东北/西北/东南/西南上，源节点S朝着目标节点D所在的1/4区域。

6.根据权利要求1所述的方法，其特征在于，还包括：

在预设时间段内未查找到所述数据请求对应的至少一个中继簇首节点，则结束所述数据请求的转发。

7.根据权利要求1所述的方法，其特征在于，还包括：备用簇首节点，且所述备用簇首节点根据节点的稳定性和节点拥塞状态，通过节点质量 获得，所述节点拥塞状态采用 得到，其中，Q代表该节点所有等待分组的长度总和，M表示节点缓存队列的长度；

根据节点的稳定性Stabilization和节点拥塞状态Cro，获得节点质量，为节点拥塞状况的权值系数，并将节点

质量最大的节点作为所述中继簇首节点。

8.一种路由查找的装置，其特征在于，包括：

接收模块，用于接收车辆节点发送的数据请求；

查找模块，用于根据所述数据请求对应的源节点信息、目标节点信息，在路由信息表中查找是否存在与所述数据请求对应的中继簇首节点，其中路由信息表存储有多个中继簇首节点；

判断模块，用于若不存在与所述数据请求对应的中继簇首节点，则通过路由获得所述数据请求对应的至少一个中继簇首节点；

发送模块，用于将所述数据请求通过对应的至少一个中继簇首节点发送至目标节点；

其中，建立路由信息表，包括：

确定当前道路交通流量，并判断当前道路交通流量是否大于预设门限流量；

若所述当前道路交通流量大于所述门限流量，则按照道路路段进行簇划分，得到中继簇首节点；

若所述当前道路交通流量小于等于所述门限流量，则按照预设通信范围距离进行簇划分，得到中继簇首节点；

将所述中继簇首节点进行标识，生成路由信息表；

其中，按照道路路段进行簇划分，得到中继簇首节点，包括：

根据电子地图保存的多个路段信息，并按照预设路段间隔将所述路段划分为至少一个网格簇；

根据车辆节点当前的位置和移动速度在所述网格簇中确定所述网格簇的中继簇首节点；对应的，所述中继簇首节点为簇内停留时间最长，和簇内成员连通性最好的节点，具体根据节点的稳定性获得，其中根据网格簇的边界范围参数（x1,x2,y1,y2）和车辆节点当前的运行方向，得到车辆节点和网格簇边界的距离，且得到车辆节点在簇内停留时间；节点之间周期性传播hello包的时候，如果在同一个簇内的节点与当前节点进行hello通信，则将当前节点的Count+1，每次节点进入一个新簇则Count清零，并获得节点的稳定性：Stabilization=|x-x1|/vx+Count，且选择簇内稳定性最大的节点作为所述中继簇首节点，其中车辆节点当前的位置（x,y）和移动速度v，车辆节点当前的位置表示所述当前节点的位置；

其中，按照预设通信范围距离进行簇划分，得到中继簇首节点，包括：将包括所有车辆节点的通信范围距离区域划分为一个网络簇；

根据每个车辆节点的平均位置信息和平均速度信息，分别计算每个车辆节点的值数据，对应的，选择一个节点作为簇首，(x,y,v)分别是簇内节点的平均位置和平均速度信息，(xi, yi, vi)是簇内成员的位置和速度信息，获得节点的值数据（Value），；

将所述值数据最小时对应的所述车辆节点作为所述中继簇首节点，所述当前节点为所述网络簇中的节点。

9.一种路由查找的系统，其特征在于，包括：存储器和处理器，存储器中存储有所述处理器的可执行指令；其中，所述处理器配置为经由执行所述可执行指令来执行权利要求1-7任一项所述的路由查找的方法。

10.一种计算机可读存储介质，其上存储有计算机程序，其特征在于，该程序被处理器执行时实现权利要求1-7任一项所述的路由查找的方法。

说明书

基于交通流量的分簇路由查找的方法、装置及系统

技术领域

[0001] 本发明涉及通信网络技术领域，尤其涉及一种基于交通流量的分簇路由查找的方法、装置及系统。

背景技术

[0002] 路由协议按照网络路基管理结构可以分为平面路由协议和分层路由协议，其中，虽然平面路由协议结构简单、鲁棒性好，但缺乏对通信资源的优化管理，对网络动态变化的反应速度较慢。分层路由中，网络节点时按照不同的分簇算法分成相应的簇，但是簇首节点的可靠性和稳定性对全网影响大，信息的采集和处理会大量消耗簇首的能量。

[0003] 现有技术中已有很多成熟的分簇协议，例如节点的路由信息分组被节点周期性地广播到网络中，以进行节点路由信息的交换，这种去往目的节点路由发现的方法传递数据的时延较小，但节点需要保持网络中的其他节点地址，这样一直保持网络其他节点的地址所带来的能量、存储资源的消耗很大。

[0004] 且现有技术中每种分簇协议都是针对所有的情况制定同一种方案，没有按照节点实际的流量变化进行调整，例如在节点密度低速度快的场景下指定的，簇首节点可以承担所有的信息，但是当在密度大速度慢的情形下，簇首节点可能会过分忙碌以导致信息丢失或者崩溃等问题的出现。

发明内容

[0005] 本发明提供一种基于交通流量的分簇路由查找的方法、装置及系统，以降低路由查找中的网络开销，增加网络的有效吞吐量，提升路由查找的效率。

[0006] 第一方面，本发明实施例提供的一种路由查找的方法，包括：

[0007] 接收车辆节点发送的数据请求；

[0008] 根据所述数据请求对应的源节点信息、目标节点信息，在路由信息表中查找是否存在与所述数据请求对应的中继簇首节点，其中路由信息表存储有多个中继簇首节点；

[0009] 若不存在与所述数据请求对应的中继簇首节点，则通过路由获得所述数据请求对应的至少一个中继簇首节点；

[0010] 将所述数据请求通过对应的至少一个中继簇首节点发送至目标节点。

[0011] 在一种可能的设计中，还包括：建立路由信息表。

[0012] 在一种可能的设计中，所述建立路由信息表，包括：

[0013] 确定当前道路交通流量，并判断当前道路交通流量是否大于预设门限流量；

[0014] 若所述当前道路交通流量大于所述门限流量，则按照道路路段进行簇划分，得到中继簇首节点；

[0015] 若所述当前道路流量小于等于所述门限流量，则按照预设通信范围距离进行簇划分，得到中继簇首节点；

[0016] 将所述中继簇首节点进行标识，生成路由信息表。

[0017] 在一种可能的设计中，按照道路路段进行簇划分，得到中继簇首节点，包括：

[0018] 根据电子地图保存的多个路段信息，并按照预设路段间隔将所述路段划分为至少一个网格簇；

[0019] 根据车辆节点当前的位置和移动速度在所述网格簇中确定所述网格簇的中继簇首节点。

[0020] 在一种可能的设计中，按照预设通信范围距离进行簇划分，得到中继簇首节点，包括：

[0021] 将包括所有车辆节点的通信范围距离区域划分为一个网络簇；

[0022] 根据每个车辆节点的平均位置信息和平均速度信息，分别计算每个车辆节点的值数据；

[0023] 将所述值数据最小时对应的所述车辆节点作为所述中继簇首节点。

[0024] 在一种可能的设计中，在路由信息表中查找是否存在与所述数据请求对应的至少一个中继簇首节点信息之前，还包括：

[0025] 若当前节点所在的网格簇中包括所述目标节点信息，则通过簇首节点发送所述数据请求至所述目标节点，且所述目的节点返回应答信息。

[0026] 在一种可能的设计中，还包括：

[0027] 若在路由信息表中存在与所述数据请求对应的中继簇首节点，则通过所述中继簇首节点向所述目标节点发送所述数据请求。

[0028] 在一种可能的设计中，通过路由获得所述数据请求对应的至少一个中继簇首节点信息，包括：

[0029] 根据源节点信息、目标节点信息确定中继节点的范围，判断所述源节点与所述目标节点是否在同一道路上；

[0030] 若所述源节点与所述目标节点在同一道路上，则在中继节点范围的第一预设区域内判断当前节点是否属于所述第一预设区域，若所述当前节点属于所述第一预设区域，则所述当前节点向所述第一预设区域的中继簇首节点发送所述数据请求；若所述当前节点不属于所述第一预设区域，则丢弃所述当前节点；

[0031] 若所述源节点与所述目标节点不在同一道路上，则在中继节点范围的第二预设区域内判断所述当前节点是否属于所述第二预设区域，若所述当前节点属于所述第二预设区域，则所述当前节点向所述第二预设区域的中继簇首节点发送所述数据请求；若所述当前节点不属于所述第二预设区域，则丢弃所述当前节点。

[0032] 在一种可能的设计中，还包括：

[0033] 在预设时间段内未查找到所述数据请求对应的至少一个中继簇首节点，则结束所述数据请求的转发。

[0034] 第二方面，本发明实施例提供的路由查找的装置，包括：

[0035] 接收模块，用于接收车辆节点发送的数据请求；

[0036] 查找模块，用于根据所述数据请求对应的源节点信息、目标节点信息，在路由信息表中查找是否存在与所述数据请求对应的中继簇首节点，其中路由信息表存储有多个中继簇首节点；

[0037] 判断模块，用于若不存在与所述数据请求对应的中继簇首节点，则通过路由获得所述数据请求对应的至少一个中继簇首节点；

[0038] 发送模块，用于将所述数据请求通过对应的至少一个中继簇首节点发送至目标节点。

[0039] 在一种可能的设计中，还包括：建立路由信息表。

[0040] 在一种可能的设计中，所述建立路由信息表，包括：

[0041] 确定当前道路交通流量，并判断当前道路交通流量是否大于预设门限流量；

[0042] 若所述当前道路交通流量大于所述门限流量，则按照道路路段进行簇划分，得到中继簇首节点；

[0043] 若所述当前道路流量小于等于所述门限流量，则按照预设通信范围距离进行簇划分，得到中继簇首节点；

[0044] 将所述中继簇首节点进行标识，生成路由信息表。

[0045] 在一种可能的设计中，按照道路路段进行簇划分，得到中继簇首节点，包括：

[0046] 根据电子地图保存的多个路段信息，并按照预设路段间隔将所述路段划分为至少一个网格簇；

[0047] 根据车辆节点当前的位置和移动速度在所述网格簇中确定所述网格簇的中继簇首节点。

[0048] 在一种可能的设计中，按照预设通信范围距离进行簇划分，得到中继簇首节点，包括：

[0049] 将包括所有车辆节点的通信范围距离区域划分为一个网络簇；

[0050] 根据每个车辆节点的平均位置信息和平均速度信息，分别计算每个车辆节点的值数据；

[0051] 将所述值数据最小时对应的所述车辆节点作为所述中继簇首节点。

[0052] 在一种可能的设计中，在路由信息表中查找是否存在与所述数据请求对应的至少一个中继簇首节点信息之前，还包括：

[0053] 若当前节点所在的网格簇中包括所述目标节点信息，则通过簇首节点发送所述数据请求至所述目标节点，且所述目的节点返回应答信息。

[0054] 在一种可能的设计中，还包括：

[0055] 若在路由信息表中存在与所述数据请求对应的中继簇首节点，则通过所述中继簇首节点向所述目标节点发送所述数据请求。

[0056] 在一种可能的设计中，通过路由获得所述数据请求对应的至少一个中继簇首节点信息，包括：

[0057] 根据源节点信息、目标节点信息确定中继节点的范围，判断所述源节点与所述目标节点是否在同一道路上；

[0058] 若所述源节点与所述目标节点在同一道路上，则在中继节点范围的第一预设区域内判断当前节点是否属于所述第一预设区域，若所述当前节点属于所述第一预设区域，则所述当前节点向所述第一预设区域的中继簇首节点发送所述数据请求；若所述当前节点不属于所述第一预设区域，则丢弃所述当前节点；

[0059] 若所述源节点与所述目标节点不在同一道路上，则在中继节点范围的第二预设区域内判断所述当前节点是否属于所述第二预设区域，若所述当前节点属于所述第二预设区域，则所述当前节点向所述第二预设区域的中继簇首节点发送所述数据请求；若所述当前节点不属于所述第二预设区域，则丢弃所述当前节点。

[0060] 在一种可能的设计中，还包括：

[0061] 在预设时间段内未查找到所述数据请求对应的至少一个中继簇首节点，则结束所述数据请求的转发。

[0062] 第三方面，本发明实施例提供的一种路由查找的系统，包括：存储器和处理器，存储器中存储有所述处理器的可执行指令；其中，所述处理器配置为经由执行所述可执行指令来执行第一方面任一项所述的路由查找的方法。

[0063] 第四方面，本发明实施例提供的一种计算机可读存储介质，其上存储有计算机程序，该程序被处理器执行时实现第一方面所述的路由查找的方法。

[0064] 本发明提供一种基于交通流量的分簇路由查找的方法、装置及系统，该方法，包括：接收车辆节点发送的数据请求；根据所述数据请求对应的源节点信息、目标节点信息，在路由信息表中查找是否存在与所述数据请求对应的中继簇首节点，其中路由信息表存储有多个中继簇首节点；若不存在与所述数据请求对应的中继簇首节点，则通过路由获得所述数据请求对应的至少一个中继簇首节点；将所述数据请求通过对应的至少一个中继簇首节点发送至目标节点。以降低路由查找中的网络开销，增加网络的有效吞吐量，提升路由查找的效率。

附图说明

[0065] 为了更清楚地说明本发明实施例或现有技术中的技术方案，下面将对实施例或现有技术描述中所需要使用的附图作一简单地介绍，显而易见地，下面描述中的附图是本发明的一些实施例，对于本领域普通技术人员来讲，在不付出创造性劳动性的前提下，还可以根据这些附图获得其他的附图。

[0066] 图1为本发明实施例一提供的路由查找的方法的流程图；

[0067] 图2为本发明实施例一提供的路由查找的方法的部分流程图；

[0068] 图3为本发明实施例一提供的路由查找的方法中二维位置的效果示意图；

[0069] 图4为本发明实施例二提供的路由查找的方法的部分方法流程图；

[0070] 图5为本发明实施例二提供的车辆速度与车辆密度之间的线性关系示意图；

[0071] 图6为本发明中二提供的车辆密度与交通流量之间的关系示意图；

[0072] 图7为本发明实施例二提供的路由查找的方法中簇划分的效果示意图；

[0073] 图8为本发明实施例二提供的路由查找的方法中簇生成的流程图；

[0074] 图9为本发明实施例三提供的路由查找的方法中簇形成的效果示意图；

[0075] 图10为本发明实施例四提供的路由查找的装置的结构示意图；

[0076] 图11为本发明实施例五提供的路由查找的系统的结构示意图。

具体实施方式

[0077] 为使本发明实施例的目的、技术方案和优点更加清楚，下面将结合本发明实施例中的附图，对本发明实施例中的技术方案进行清楚、完整地描述，显然，所描述的实施例是本发明一部分实施例，而不是全部的实施例。基于本发明中的实施例，本领域普通技术人员在没有做出创造性劳动前提下所获得的所有其他实施例，都属于本发明保护的范围。

[0078] 本发明的说明书和权利要求书及上述附图中的术语“第一”、“第二”、“第三”“第四”等(如果存在)是用于区别类似的对象，而不必用于描述特定的顺序或先后次序。应该理解这样使用的数据在适当情况下可以互换，以便这里描述的本发明的实施例例如能够以除了在这里图示或描述的那些以外的顺序实施。此外，术语“包括”和“具有”以及他们的任何变形，意图在于覆盖不排他的包含，例如，包含了一系列步骤或单元的过程、方法、系统、产品或设备不必限于清楚地列出的那些步骤或单元，而是可包括没有清楚地列出的或对于这些过程、方法、产品或设备固有的其它步骤或单元。

[0079] 下面以具体地实施例对本发明的技术方案进行详细说明。下面这几个具体的实施例可以相互结合，对于相同或相似的概念或过程可能在某些实施例不再赘述。

[0080] 本发明设计一个适合城市环境网络的分簇算法，由于城市路况复杂，随着车辆在道路的地理位置和时间的变化，交通状况会发生很大的差别，例如在城市中心地带或者上下班高峰时期，车辆节点，密度大，车辆节点运行速度慢；又例如在城市郊区车辆节点的密度明显下降，车辆速度增大等不同的网络流量场景，可以实现降低路由查找中的网络开销，增加网络的有效吞吐量，提升路由查找的效率。

[0081] 图1为本发明实施例一提供的路由查找的方法的流程图，如图1所示，本实施例中的方法可以包括：

[0082] S101、接收车辆节点发送的数据请求。

[0083] 本实施例中，针对道路情况复杂，随地理位置和时间变化，车辆交通状态也会发生较大差别的环境，例如城市环境，以解决车辆节点发送数据过程中的路由查找问题，以及提高路由查找的效率。路由查找系统可以实时监测道路上各个车辆节点的网络信息，故例如路由查找系统可以接收车辆节点A发送的数据请求，也可以同时接收多个车辆节点发送的数据请求。

[0084] S102、根据数据请求对应的源节点信息、目标节点信息，在路由信息表中查找是否存在与数据请求对应的中继簇首节点，其中，路由信息表中存储有多个中继簇首节点。

[0085] 本实施例中，车辆节点发送的数据请求中包含有源节点信息(即本车辆节点的信息)、目标节点信息(该数据请求最终发送的目的节点，可以包括目的节点的IP、地址等信息)。在预设存储的路由信息表中查找是否存在与数据请求对应的中继簇首节点，在一种可选的实施例中，若该路由信息表中可以查找到存在与数据请求对应的一个或者多个中继簇首节点，则该数据请求可以通过一个或者多个中继簇首节点从源节点最终发送至目标节点，完成该数据请求的传输。其中路由信息表中包含有至少一个簇首节点，路由信息表中可以包含簇首节点的类型标示(例如簇首设置为0)、簇ID、簇首ID、簇内成员数、簇内成员节点ID；路由信息表中还可以包括簇内成员维护信息，例如簇ID、簇首ID、簇节点类型标示(例如网关节点设置为1，普通节点设置为2)。在一种可选的实施例中，簇首节点会通知簇内成员该簇首节点的簇首ID。

[0086] 在一种可选的实施中，若在路由信息表中存在与数据请求对应的中继簇首节点，则通过中继簇首节点向目标节点发送数据请求。

[0087] 例如，根据数据请求中对应的源节点信息(例如A)、目标节点信息(例如B)，在路由信息表中查找到至少一个中继簇首节点(例如一个中继簇首节点C)，则该数据请求从源节点A通过中继簇首节点C发送至目标节点B。

[0088] S103、若不存在与数据请求对应的中继簇首节点，则通过路由获得该数据请求对应的至少一个中继簇首节点。

[0089] 具体的，根据源节点信息、目标节点信息确定中继节点的范围，判断源节点与目标节点是否在同一道路上；

[0090] 若源节点与目标节点在同一道路上，则在中继节点范围的第一预设区域内判断当前节点是否属于第一预设区域，若当前节点属于第一预设区域，则当前节点向第一预设区域的中继簇首节点发送数据请求；若当前节点不属于第一预设区域，则丢弃当前节点；

[0091] 若源节点与目标节点不在同一道路上，则在中继节点范围的第二预设区域内判断当前节点是否属于第二预设区域，若当前节点属于第二预设区域，则当前节点向第二预设区域的中继簇首节点发送数据请求；若当前节点不属于第二预设区域，则丢弃当前节点。

[0092] 如图2所示，图2为本发明实施例一提供的路由查找的方法的部分流程图，当当前节点需要发送数据请求时，先将该数据请求交付给簇首节点，由簇首节点在路由信息表中查找是否存在与数据请求对应的至少一个中继簇首节点。若存在，则直接通过中继簇首节点向目标节点发送数据请求。若路由信息表中不存在数据请求对应的中继簇首节点，则通过路由获得数据请求对应的中继簇首节点。

[0093] 本实施例中，为了减少无用路由包在网络中的传输，根据源节点和目标节点的位置确定中继节点的范围；在一种可选的实施例中，例如源节点S、目标节点D的位置关系可以根据曼哈顿模型建立，例如利用节点在城市区域的移动来建模，节点在城区地图里沿着垂直和水平的街道移动，模拟在十字路口，节点可以左转、右转或者向前移动，且在同一街道上移动的概率为0.5，左转和右转的概率分别为0.25。故可以根据源节点和目标节点的位置确定中继节点的范围，寻找最佳的路由路径来将覆盖源节点S、目标节点D的有效活动区域和道路划分为中继节点的范围内。例如从源节点S开始到目标节点D所经过的所有街道划分为中继节点的范围，进而判断源节点与目标节点是否在同一道路上。

[0094] 为了充分限制无效泛洪，以及考虑道路、两节点的位置关系、方位等，将道路抽象为二维平面道路。例如当前节点I收到源节点S广播的RREQ(Route Request，路由请求；参见下表1，表1为RREQ报文内容)时,若源节点与目标节点在同一道路上，源节点与目标节点的位置关系可以为正北/正南/正西/正东，或者可以为西北/东南/东北/西南等等。若目标节点D在源节点S的正东/南/西/北方向上，此时无论源节点S和目标节点D方向关系如何，源节点S只需要朝着目标节点D所在的1/2区域洪泛即可有效的缩小洪泛区域，其中第一预设区域为目标节点D所在的1/2区域，判断该当前节点I是否属于该第一预设区域，若当前节点属于该第一预设区域，则当前节点向该第一预设区域的中继簇首节点发送该数据请求；若不当前节点不属于该第一预设区域，则丢弃当前节点。在一种可选的实施例中，当当前节点接收到RREQ分组时，只有簇首节点可以处理该分组RREQ，若簇首中包含有目标节点的信息，则直接向当前节点返回RREP(Route Reply，路由应答)。

[0095] 表1

[0096]

[0097] 若源节点S和目标节点D不在同一道路上，位置关系为东北/西北/东南/西南。此时双重位置关系将中继范围的二维平面分为4个区域(参考图3，图3为本发明实施例一提供的路由查找的方法中二维位置的效果示意图)，此时，无论源节点S和目标节点D方向关系如何，源节点S只需要朝着目标节点D所在的1/4区域洪泛即可。其中第二预设区域为目标节点D的1/4区域；若当前节点I判断自己处在源节点S和目标节点D之间的1/4区域内，则向该第二预设区域的中继簇首节点发送该数据请求，即转发RREQ；若当前节点I不属于该第二预设区域，否则丢弃当前节点I。

[0098] S104、将数据请求通过对应的至少一个中继簇首节点发送至目标节点。

[0099] 具体的，根据得到的至少一个中继簇首节点，将数据请求从源节点经过中继簇首节点发送至目标节点。

[0100] 在一种可选的实施例中，还包括：

[0101] 若在路由信息表中存在与数据请求对应的中继簇首节点，则通过中继簇首节点向目标节点发送数据请求。

[0102] 例如，根据数据请求对应的源节点信息、目标节点信息，在路由信息表中查找到存在与数据请求对应的一个或者多个中继簇首节点，则通过这些中继簇簇首节点向目标节点发送该数据请求。

[0103] 在一种可选的实施例中，还包括：建立路由信息表。

[0104] 具体的参考图4，图4为本发明实施例二提供的路由查找的方法的部分方法流程图，如图4所示，本实施例中建立路由信息表可以包括：

[0105] S201、确定当前道路交通流量，并判断当前道路交通流量是否大于预设门限流量；

[0106] 具体的，首先根据道路内车辆节点的车速和密度判断当前道路交通流量，其中交通流量为Q，是指在选定时间段内，通过道路某一个点、某一个断面或者某一个车道的交通实体数量，在一种可选的实施例中，车辆尤指机动车辆，故定义机动车流量为道路交通流量，计算方法如下公式一：

[0107]

[0108] 其中，t为观测点的时间，N为观察时间内通过的车辆数目，L是路段长度，k是车辆密度，v是车辆速度。

[0109] 根据格林息尔治提出的经典“速度-密度”现象关系的公式二：

[0110]

[0111] 其中，ν1表示自由流速度，k1表示阻塞流速度，车辆速度和车辆密度之间的线性关系如下，如图5(图5为本发明实施例二提供的车辆速度与车辆密度之间的线性关系示意图)可以看出：

[0112] limk→0v＝vf,limk→kjv=0    (公式三)

[0113]

[0114] 其中公式四中，Km表示临界密度，Vm表示临界速度，Qmax表示最大交通流量。格林息尔治描述了车辆速度随着车辆节点密度的增加呈直线下降的趋势，车辆速度是车辆密度的减函数。

[0115] 进而车辆密度与交通流量之间的关系是在格林息尔治的车辆速度和车辆密度线性模型基础上推导所得，根据公式一和公式二可推得：

[0116]

[0117] 参考图6，图6为本发明中二提供的车辆密度与交通流量之间的关系示意图，根据图5、图6可以看出，当Q小于Qmax，车辆速度随着交通流量的增加而减小，当Q大于Qmax之后，车辆速度随着交通流量的减小而减小。车辆速度达到临界值Vm的时候，交通流量Q达到Qmax。

[0118] S202、若当前道路交通流量大于门限流量，则按照道路路段进行簇划分，得到中继簇首节点。

[0119] 具体的，根据电子地图保存的多个路段信息，并按照预设路段间隔将路段划分为至少一个网格簇；

[0120] 根据车辆节点当前的位置和移动速度在网格簇中确定网格簇的中继簇首节点。

[0121] 本实施例中，根据电子地图保存的路段信息，将路段每间隔 米划分一个网格，每个网格代表一个簇，为每个簇分配一个簇ID号，最终将路段划分为多个网格簇，参考图7中的虚线部分。为了确保簇内和邻居簇之间可以直接进行通信，簇的大小不得超过最大通信距离的一半。这种基于路段的划分，节点运行方向相近，距离相近，可以使得节点在簇内的时间更长，维护方便。参考图7，图7为本发明实施例二提供的路由查找的方法中簇划分的效果示意图。基于划分好的簇的范围，根据车辆节点当前的位置(x,y)和移动速度v在网格簇中确定该网格簇的中继簇首节点。

[0122] 根据网格簇的边界范围参数(x1,x2,y1,y2)和车辆节点当前的运行方向，得到车辆节点和网格簇边界的距离，可以得到车辆节点在簇内停留时间。节点之间周期性传播hello包的时候，如果在同一个簇内的节点与当前节点进行HELLO通信，则将当前节点的Count+1，每次节点进入一个新簇Count清零。由次可以得到节点的稳定性Stabilization的计算公式六：

[0123] Stabilization＝|x-x1|/vx+Count   (公式六)

[0124] 可以选择簇内Stabilization值最大的作为簇首节点。

[0125] 在一种可选的实施例中，密度较大时，一个簇首节点可能承担过多转发任务，这些节点也更容易丢包或者产生路径断裂，所以为了均匀负载均衡，除了簇首节点还会选择备用簇首节点共同承担处理信息和转发信息的责任。备用簇首节点依据节点质量NodeQuality进行，如公式八。节点质量衡量标准主要分为两部分：节点拥塞状况+稳定性。稳定性可以按照公式六进行计算，节点的拥塞状况按照下面公式七进行计算：

[0126]

[0127] 其中公式七中Q代表该节点所有等待分组的长度总和，M表示节点缓存队列的长度。

[0128] NodeQuality＝αCro+(1-α)Stablization   (公式八)

[0129] 公式八中α为节点拥塞状况的权值系数。本实施例中，簇首选择的首要标准是“稳定性”，就是簇内停留时间最长，和簇内成员连通性最好的节点。节点之间周期性传输HELLO包，包里包含包类型、IP、网格簇ID、簇首IP、簇内连通数Count、位置、速度等有效信息。

[0130] 本实施例中，若当前道路交通流量大于门限流量，说明车辆节点拥挤程度较高，车速较慢，局部网络的信息密度较高，此时可能一个节点承担着多份信息的转发，信息丢失的可能也会上升，故按照道路路段进行簇首划分，得到中继簇首节点。

[0131] 本实施例中直接按照道路路段进行簇划分，然后将节点按照链路质量进行排序，即使链路断裂，仍然可以快速在簇内找到备用节点以进行信息转发，因为分担了每个节点的网络压力，提高路由查找的效率。

[0132] S203、若当前道路流量小于等于门限流量，则按照预设通信范围距离进行簇划分，得到中继簇首节点；

[0133] 具体的，将包括所有车辆节点的通信范围距离区域划分为一个网络簇；

[0134] 根据每个车辆节点的平均位置信息和平均速度信息，分别计算每个车辆节点的值数据；

[0135] 将值数据最小时对应的车辆节点作为中继簇首节点。

[0136] 本实施例中当前道路流量小于等于门限流量时，说明当前节点运动速度快密度相对小，需考虑通信范围R米内相对位置和相对速度接近的节点化为一簇，减少重新分簇的次数。假设该范围内一共有n个节点，先随机选择一个节点作为簇首，(x,y,v)分别是簇内节点的平均位置和平均速度信息，(xi,yi,vi)是簇内成员的位置和速度信息利用公式九计算该节点的Value(值数据)，找到最小Value的节点作为簇首：

[0137] Value＝Σ(x-xi)2+∑(y-yi)2+∑(v-vi)2   (公式九)

[0138] 若是一个节点在多个簇的范围内，选择Value最小的簇加入，即表示该节点与簇内成员的相对位置和速度更接近，若是Value值相同，随机选择一个簇进行加入。加入之后通知簇首节点。

[0139] S204、将中继簇首节点进行标识，生成路由信息表。

[0140] 具体的，参考图8，图8为本发明实施例二提供的路由查找的方法中簇生成的流程图，根据交通流量确定不同的簇生成方案，并对簇首节点进行标识。

[0141] 路由信息表中包含有至少一个簇首节点，路由信息表中可以包含簇首节点的类型标示(例如簇首设置为0)、簇ID、簇首ID、簇内成员数、簇内成员节点ID；路由信息表中还可以包括簇内成员维护信息，例如簇ID、簇首ID、簇节点类型标示(例如网关节点设置为1，普通节点设置为2)。在一种可选的实施例中，簇首节点会通知簇内成员该簇首节点的簇首ID。节点之间周期性传输HELLO包，包里包含包类型、IP、网格簇ID、簇首IP、簇内连通数Count、位置、速度等有效信息。

[0142] 在一种可选的实施例中，若一个节点收到两个或者两个以上节点的簇首发送的报文信息，首先查看是不是来自同一个簇首，如果是则丢弃前面的信息，若是来自不同的簇首，则说明当前节点是网关节点，将该当前节点标示为1。簇首一旦生成，就不会改变；除非脱离该簇的范围之后则需要按照之前步骤另行计算新的簇首，至此簇已经形成。参考图9，图9为本发明实施例三提供的路由查找的方法中簇形成的效果示意图。其中，黑色圆圈代表簇首节点、黑色实线的白色圆圈代表网关节点、黑色虚线的白色圆圈代表普通节点。

[0143] 在一种可选的实施例中，簇首会周期性检查簇内节点信息判断簇内交通流量和门限流量Q之间的关系，如果流量发生明显变化，从密集簇转化到稀疏簇，需要按照稀疏簇的方案重新建立；若是从稀疏簇转化到密集簇，也需要按照密集簇的方案重新建立簇。

[0144] 簇首也会周期刷新自己位置，如果发现自己离开了原簇，则在簇成员中按照上述过程进行重新选举，找到Value值最大的作为下一任簇首，并将自己的信息表转发给该节点，然后广播告诉原簇内节点，宣告自己不再是簇首，发送下一任簇首信息。若是一个节点在两个周期内没有收到簇首的分组信息，则将自己设置为簇首，因此在一个簇内可能会出现多个簇首，这种情况下，通过比较在簇内的有效时间确定簇首。

[0145] 在一种可选的实施例中，在路由信息表中查找是否存在与数据请求对应的至少一个中继簇首节点信息之前，还包括：

[0146] 若当前节点所在的网格簇中包括目标节点信息，则通过簇首节点发送数据请求至目标节点，且目的节点返回应答信息。

[0147] 在一种可选的实施例中，还包括：

[0148] 在预设时间段内未查找到数据请求对应的至少一个中继簇首节点，则结束数据请求的转发。

[0149] 例如在规定的时间内未查找到与数据请求对应的一个或者多个中继簇首节点，则此次数据请求的转发查找失败，至此全部查找过程均结束。

[0150] 图10为本发明实施例四提供的路由查找的装置的结构示意图，如图10所示，本实施例中路由查找的装置可以包括：

[0151] 接收模块31，用于接收车辆节点发送的数据请求；

[0152] 查找模块32，用于根据数据请求对应的源节点信息、目标节点信息，在路由信息表中查找是否存在与数据请求对应的中继簇首节点，其中路由信息表存储有多个中继簇首节点；

[0153] 判断模块33，用于若不存在与数据请求对应的中继簇首节点，则通过路由获得数据请求对应的至少一个中继簇首节点；

[0154] 发送模块34，用于将数据请求通过对应的至少一个中继簇首节点发送至目标节点。

[0155] 在一种可选的实施例中，还包括：建立路由信息表。

[0156] 在一种可选的实施例中，建立路由信息表，包括：

[0157] 确定当前道路交通流量，并判断当前道路交通流量是否大于预设门限流量；

[0158] 若当前道路交通流量大于门限流量，则按照道路路段进行簇划分，得到中继簇首节点；

[0159] 若当前道路流量小于等于门限流量，则按照预设通信范围距离进行簇划分，得到中继簇首节点；

[0160] 将中继簇首节点进行标识，生成路由信息表。

[0161] 在一种可选的实施例中，按照道路路段进行簇划分，得到中继簇首节点，包括：

[0162] 根据电子地图保存的多个路段信息，并按照预设路段间隔将路段划分为至少一个网格簇；

[0163] 根据车辆节点当前的位置和移动速度在网格簇中确定网格簇的中继簇首节点。

[0164] 在一种可选的实施例中，按照预设通信范围距离进行簇划分，得到中继簇首节点，包括：

[0165] 将包括所有车辆节点的通信范围距离区域划分为一个网络簇；

[0166] 根据每个车辆节点的平均位置信息和平均速度信息，分别计算每个车辆节点的值数据；

[0167] 将值数据最小时对应的车辆节点作为中继簇首节点。

[0168] 在一种可选的实施例中，在路由信息表中查找是否存在与数据请求对应的至少一个中继簇首节点信息之前，还包括：

[0169] 若当前节点所在的网格簇中包括目标节点信息，则通过簇首节点发送数据请求至目标节点，且目的节点返回应答信息。

[0170] 在一种可选的实施例中，还包括：

[0171] 若在路由信息表中存在与数据请求对应的中继簇首节点，则通过中继簇首节点向目标节点发送数据请求。

[0172] 在一种可选的实施例中，通过路由获得数据请求对应的至少一个中继簇首节点信息，包括：

[0173] 根据源节点信息、目标节点信息确定中继节点的范围，判断源节点与目标节点是否在同一道路上；

[0174] 若源节点与目标节点在同一道路上，则在中继节点范围的第一预设区域内判断当前节点是否属于第一预设区域，若当前节点属于第一预设区域，则当前节点向第一预设区域的中继簇首节点发送数据请求；若当前节点不属于第一预设区域，则丢弃当前节点；

[0175] 若源节点与目标节点不在同一道路上，则在中继节点范围的第二预设区域内判断当前节点是否属于第二预设区域，若当前节点属于第二预设区域，则当前节点向第二预设区域的中继簇首节点发送数据请求；若当前节点不属于第二预设区域，则丢弃当前节点。

[0176] 在一种可选的实施例中，还包括：

[0177] 在预设时间段内未查找到数据请求对应的至少一个中继簇首节点，则结束数据请求的转发。

[0178] 本实施例的路由查找的装置，可以执行图1所示方法中的技术方案，其具体实现过程和技术原理参见图1所示方法中的相关描述，此处不再赘述。

[0179] 图11为本发明实施例五提供的路由查找的系统的结构示意图，如图11所示，本实施例的路由查找的系统40可以包括：处理器41和存储器42。

[0180] 存储器42，用于存储计算机程序(如实现上述路由查找的方法的应用程序、功能模块等)、计算机指令等；

[0181] 上述的计算机程序、计算机指令等可以分区存储在一个或多个存储器42中。并且上述的计算机程序、计算机指令、数据等可以被处理器41调用。

[0182] 处理器41，用于执行存储器42存储的计算机程序，以实现上述实施例涉及的方法中的各个步骤。

[0183] 具体可以参见前面方法实施例中的相关描述。

[0184] 处理器41和存储器42可以是独立结构，也可以是集成在一起的集成结构。当处理器41和存储器42是独立结构时，存储器42、处理器41可以通过总线43耦合连接。

[0185] 本实施例的服务器可以执行图1所示方法中的技术方案，其具体实现过程和技术原理参见图1所示方法中的相关描述，此处不再赘述。

[0186] 本发明提供一种基于交通流量的分簇路由查找的方法、装置及系统，可以降低路由查找中的网络开销，增加网络的有效吞吐量，提升路由查找的效率。

[0187] 此外，本申请实施例还提供一种计算机可读存储介质，计算机可读存储介质中存储有计算机执行指令，当用户设备的至少一个处理器执行该计算机执行指令时，用户设备执行上述各种可能的方法。

[0188] 其中，计算机可读介质包括计算机存储介质和通信介质，其中通信介质包括便于从一个地方向另一个地方传送计算机程序的任何介质。存储介质可以是通用或专用计算机能够存取的任何可用介质。一种示例性的存储介质耦合至处理器，从而使处理器能够从该存储介质读取信息，且可向该存储介质写入信息。当然，存储介质也可以是处理器的组成部分。处理器和存储介质可以位于ASIC中。另外，该ASIC可以位于用户设备中。当然，处理器和存储介质也可以作为分立组件存在于通信设备中。

[0189] 本领域普通技术人员可以理解：实现上述各方法实施例的全部或部分步骤可以通过程序指令相关的硬件来完成。前述的程序可以存储于一计算机可读取存储介质中。该程序在执行时，执行包括上述各方法实施例的步骤；而前述的存储介质包括：ROM、RAM、磁碟或者光盘等各种可以存储程序代码的介质。

[0190] 最后应说明的是：以上各实施例仅用以说明本发明的技术方案，而非对其限制；尽管参照前述各实施例对本发明进行了详细的说明，本领域的普通技术人员应当理解：其依然可以对前述各实施例所记载的技术方案进行修改，或者对其中部分或者全部技术特征进行等同替换；而这些修改或者替换，并不使相应技术方案的本质脱离本发明各实施例技术方案的范围。