用于车载Adhoc网络中的数据包贪婪转发的方法

暂无

用于车载Ad hoc网络中的数据包贪婪转发的方法\n技术领域\n[0001] 本发明涉及一种新型网络架构中的数据传输方法，确切地说，涉及一种用于城市道路环境的车载Ad hoc网络中数据包贪婪转发的方法，属于移动通信中移动自组织网络应用的技术领域。\n背景技术\n[0002] 车载Ad Hoc网络VANET(vehicle ad hoc networks)是一种特殊的自组织移动Ad Hoc网络，该网络的节点是由装备无线收发装置的机动车辆所组成。近年来，由于城市车辆的迅速增加造成交通堵塞的现象日趋严重，甚至交通事故频频发生。因此，使用车载网络进行车辆之间或控制台与各个车辆之间的通信，以疏通交通流量或提高物流企业的功效而对该车载Ad Hoc网络开展研究和应用已经逐渐成为一个研究热点。由于车辆的高速移动以及街道障碍物阻挡等多种原因，车载Ad hoc网络具有不同于普通Ad hoc网络的显著特点，其中之一是网络分割现象特别严重，在一个高速移动、且各个节点的趋向不确定的环境中，要想随时随地维持网络结构的拓扑信息势必导致网络负载显著增加，使得路由问题更加复杂。\n[0003] 但是，由于车载通信设备可以通过其发动机获得电力支持，能源供应比较充足，而且车辆的承载空间可以确保天线的尺寸和装载其他额外的通信设备不会受到限制，这样就能够确保车载Ad Hoc网络的节点具有强大的信息处理和海量存储等多种功能。再者，由于在城市环境中，车辆必须沿着既定的道路前进或后退，这就使得其运动轨迹具有一定的规律性和可预测性，即人们能够预测车载AdHoc网络节点的下一时刻位置。再者，发展迅速的全球定位服务GPS(globalpositioning system)系统能够为车载Ad Hoc网络节点提供精确定位和精准的时钟信息，有利于获取车载Ad Hoc网络各节点获取自身的位置信息和实现时钟同步。\n[0004] 目前，如何结合车载Ad Hoc网络的上述特点，找到一种适应于城市环境的车载Ad hoc网络中数据包转发的方法是一个需要解决的重要的技术问题。\n发明内容\n[0005] 有鉴于此，本发明的目的是提供一种适应于城市道路环境的车载Ad hoc网络中数据包贪婪转发的方法，该方法充分利用车载Ad Hoc网络节点的特性，在数据包的递交率、时延、平均跳数、物理层发送的总数据量等指标上都优于目前使用的其他算法，且操作步骤简单、易行，计算工作的复杂度低，能够满足实时传输的要求。\n[0006] 为了达到上述目的，本发明提供了一种适应于城市环境的车载Ad hoc网络中数据包贪婪转发的方法，其特征在于，包括下列操作步骤：\n[0007] (1)把城市的道路环境建模为具有权重值的无向图：在该无向图中，端点集是道路的岔路口的集合，边集是两个岔路口之间的街道的集合；车辆在该无向图中的移动是沿着边从一个端点移动到另一个端点，街道的权重值取决于街道交通流量信息和街道的物理长度；\n[0008] (2)对数据包转发路径中的岔路口进行动态选择和更新：根据目的节点的位置信息和城市道路环境的实时建模信息，对数据包转发路径中的岔路口进行动态选择和更新，持有数据包的节点在岔路口区域更新数据包中的岔路口序列；\n[0009] (3)每个节点维持一个邻居列表，并预测车辆节点位置和维护邻居列表：利用街道上移动的车辆所在地理位置具有可预测性的特点和预测车辆节点位置的方法，每个节点预测其邻居节点的当前位置，并及时更新其邻居列表，以便减少信息维护工作量，并提高邻居列表信息的有效性；\n[0010] (4)目的节点更新其位置消息：当目的节点移动到新的街道上后，向中间节点广播其位置更新消息；中间节点缓存该位置更新消息或用该位置更新消息更新原有记录后，转发该位置更新消息；当需要时，中间节点利用目的节点的最新位置信息和实时建模信息进行岔路口的动态选择和数据包的转发；\n[0011] (5)基于贪婪转发策略对数据包进行转发：中间节点在转发数据包而进行下一跳选择之前，先利用位置预测算法查看目的节点是否为其邻居节点，如果是，则直接把数据包发给目的节点；否则，根据中间节点位于岔路口区域还是两个岔路口之间的道路上，分别执行相应的贪婪转发策略转发数据包。\n[0012] 所述步骤(1)的无向图中，分别采用length(m，n)和traffic(m，n)表示岔路口m和n之间的街道物理长度及其交通流量信息，后者的量纲是单位时间内经过该街道的车辆α β\n数量；设置岔路口m和n之间的街道权值为weight(m，n)＝length (m，n)/traffic (m，n)，式中，两个调整系数α和β都大于或等于零，该两个数值分别决定街道的物理长度和交通流量信息在选择中间转发节点时所考虑的因素的份量大小，α＝0时表示街道的权值只取决于交通流量信息，β＝0时表示街道的权值仅取决于街道的物理长度。\n[0013] 所述步骤(2)中，由源节点到目的节点的转发数据包过程中，所经历的多个岔路口组成一个岔路口序列；且为适应城市道路环境的实时建模信息，对转发数据包路径中的每个岔路口都要逐个计算和动态选择；每个数据包的包头中含有两个岔路口标识：当前岔路口CJ和前一岔路口PJ，前者是数据包正在走向的岔路口标识，后者为该数据包刚刚离开的岔路口标识。\n[0014] 所述对数据包转发路径中的岔路口进行动态选择和更新的方法是：当产生数据包的源节点或持有数据包的中间节点走进某个岔路口区域时，要根据目的节点的位置信息，按照图论中的最小花费算法动态选择下一个岔路口作为其前进方向；优先选择的原则是距离短和车辆流量密度大的街道；完成选择后，持有数据包的节点要更新其岔路口序列：把刚刚选择的岔路口更新为当前岔路口CJ，而把该数据包刚经过的岔路口更新为前一岔路口PJ。\n[0015] 所述岔路口区域是指车载Ad Hoc网络中的节点到达某个岔路口的距离长度小于设定数值的地域范围。\n[0016] 所述邻居节点是指两个节点之间相互在对方的通信范围之内，且没有被建筑物阻挡时，则称该两个节点具有邻居关系，或者说其中一个节点是另外一个节点的邻居节点。\n[0017] 所述邻居列表的信息是通过相邻的节点间广播问候消息HELLO完成交互的，该HELLO消息包括节点标识ID、节点当前所在的地理位置、时间戳、节点的当前速度及其移动方向；收到邻居节点发送来的HELLO消息后，节点对邻居列表中的相关信息进行更新；为减少HELLO消息发送频率和提高邻居列表信息的有效性，节点利用位置预测方法对邻居列表中的各个邻居节点的当前位置进行预测，并从邻居列表中删除已经走出当前街道的节点；\n同时任何一个节点离开岔路口区域时，都要立即广播发送一个声明该节点的最新位置信息的HELLO消息，以便让其他节点更新其邻居列表中该离开岔路口的节点的信息；\n[0018] 所述车辆节点的位置预测方法是：假设当前时间为t，节点i的位置是(xi，yi)，其速度是vi，走向岔路口B的位置坐标是(xB，yB)，前一个岔路口A位置坐标是(xA，yA)；dis(A，B)是两个岔路口A到B的距离；则在t+Δt，其中Δt＜dis(i，B)/vi时刻，该节点仍然在该街道上移动的位置坐标是：(xi+Δt×vi×(xB-xA)/dis(B，A)，yi+Δt×vi×(yB-yA)/dis(B，A))，而在t+Δt，其中Δt＞dis(i，B)/vi时刻，该节点i可能已经走出当前街道而进入另一条街道上。\n[0019] 当中间节点位于岔路口区域时，所述贪婪转发策略转发数据包的方法是：根据中间节点的邻居列表进行位置预测，从走向当前岔路口的邻居节点中选择其中距离当前岔路口最近的节点作为下一跳节点；如果没有找到相应的节点，则把数据包暂存到缓存中，再使用探寻算法周期性地寻找是否有新的节点走进其通信范围；如果该中间节点离开岔路口区域但仍然没有找到一个合适的邻居节点转发数据时，则用该中间节点离开的岔路口和走向的岔路口分别替换数据包中的当前岔路口和前一岔路口；该方法的具体操作步骤如下：\n[0020] (5A)更新邻居列表：计算邻居列表中各个邻居节点的当前地理位置，并从邻居列表中删除与本节点不再具有邻居关系的节点；\n[0021] (5B)从邻居列表中走向当前岔路口的各邻居节点中，查找距离当前岔路口最近的节点作为下一跳节点，若能够找到，则跳转执行步骤(5D)，否则，顺序执行步骤(5C)；\n[0022] (5C)把数据包暂存于缓存，再循环执行探寻算法，寻找是否有新的节点走进其通信范围；若探寻成功，则返回执行步骤(5A)，否则，结束本跳操作；\n[0023] (5D)把数据包转发给该找到的下一跳节点，结束本跳操作。\n[0024] 当中间节点位于两个岔路口之间的道路上时，所述步骤(5)基于贪婪转发策略对数据包进行转发的方法是：根据中间节点的邻居列表选择距离当前岔路口最近的节点作为下一跳节点；如果没有找到相应的节点，就把数据包暂存到缓存中，使用探寻算法周期性地探寻是否有新的节点走进它的通信范围；该方法的具体操作步骤如下：\n[0025] (5a)更新邻居列表：计算邻居列表中各个邻居节点的当前地理位置，并从邻居列表中删除与本节点不再具有邻居关系的节点；\n[0026] (5b)从邻居列表中查找距离当前岔路口最近的节点作为下一跳节点，若能够找到，则跳转执行步骤(5d)，否则，顺序执行步骤(5c)；\n[0027] (5c)把数据包暂存于缓存，再循环执行探寻算法，寻找是否有新的节点走进其通信范围；若探寻成功，则返回执行步骤(5a)，否则，结束本跳操作；\n[0028] (5d)把数据包转发给该找到的下一跳节点，结束本跳操作。\n[0029] 所述探寻算法的具体操作内容是：\n[0030] A、持有数据包的节点广播一个探寻请求消息，该探寻请求消息中包含该节点的当前位置信息和当前岔路口，并设置一个定时器；\n[0031] B、在定时器超时之前，如果有节点接收到该探寻请求消息，并且其位置位于持有数据包的节点和当前岔路口之间，则该节点立即返回探寻响应消息，该响应消息中包含收到探寻请求节点的ID、该收到探寻请求节点的地理位置信息、当前速度及其移动方向；持有数据包的节点接收到探寻响应消息后，提取探寻响应消息中的相关数据并更新邻居列表；并在定时器到达设定时间后，结束本次探寻操作，探寻成功；\n[0032] C、在定时器超时之前，如果没有任何响应消息，这时持有数据包的节点可能走到一个网络的边缘，即出现网络分割现象；此时，该持有数据包的节点将延迟一段时间后重新返回执行步骤A的操作；若重复执行步骤A的操作达到设定的次数，仍未探寻成功，则该持有数据包的节点丢弃数据包，探寻失败。\n[0033] 本发明的优点和效果是：采用仿真工具NS2对本发明方法进行的大量仿真实施试验结果表明，本发明方法在递交率、时延、平均跳数、物理层发送的总数据量等指标上都优于目前使用的其他算法，且操作步骤简单、易行，计算工作复杂度低，能够满足实时传输的要求。\n附图说明\n[0034] 图1是本发明适应于城市环境的车载Ad hoc网络中数据包贪婪转发的方法操作步骤流程图。\n具体实施方式\n[0035] 为使本发明的目的、技术方案和优点更加清楚，下面结合附图对本发明作进一步的详细描述。\n[0036] 本发明是一种适应于城市环境的车载Ad hoc网络对数据包采用贪婪转发的路由实现方法，该方法包括下列操作步骤：\n[0037] 步骤1、把城市的道路环境建模为具有权重值的无向图：在该无向图中，端点集是道路的岔路口的集合，边集是两个岔路口之间的街道的集合。车辆在该无向图中的移动是沿着边从一个端点移动到另一个端点，街道的权重值取决于街道交通流量信息和街道的物理长度。\n[0038] 在该无向图中，分别采用length(m，n)和traffic(m，n)表示两个岔路口m和n之间的街道物理长度及其交通流量信息，前者的量纲是米和千米，后者的量纲是单位时间内经过该街道的车辆数量；再设置岔路口m和n之间的街道权值为weight(m，n)＝α β\nlength (m，n)/traffic (m，n)，式中，两个调整系数α和β都大于或等于零，该两个数值分别决定街道的物理长度和交通流量信息在进行转发节点选择时所考虑的因素的份量大小，α＝0时表示街道的权值只取决于交通流量信息，β＝0时表示街道的权值仅取决于街道的物理长度。\n[0039] 步骤2、对数据包转发路径中的岔路口进行动态选择和更新：根据目的节点的位置信息和城市道路环境的实时建模信息，对数据包转发路径中的岔路口进行动态选择和更新，持有数据包的节点在岔路口区域更新数据包中的岔路口序列。\n[0040] 在由源节点到目的节点的转发过程中，数据包要经历许多个岔路口；这些岔路口组成一个岔路口序列。而且，为了适应城市道路交通的实时建模信息，本发明对数据包转发路径中的每个岔路口都是逐个计算和动态选择的。被转发的每个数据包的包头中含有两个岔路口标识：一个是数据包正在走向的岔路口的标识，称为当前岔路口CJ；另一个是数据包刚刚离开的岔路口的标识，称为前一岔路口PJ。\n[0041] 本发明的数据包在转发路径中对岔路口进行动态选择和更新的方法是：当产生数据包的源节点或持有数据包的中间节点走进某个岔路口区域(即车载Ad Hoc网络中的节点到达某个岔路口的距离长度小于设定数值的地域范围)时，要根据目的节点的位置信息，按照图论中的Dijkstra最小花费算法动态选择下一个岔路口作为其前进方向；优先选择的原则是距离短和车辆流量密度大的街道。完成选择后，持有数据包的节点在岔路口区域要更新数据包中的岔路口序列：把刚刚选择的岔路口更新为当前岔路口CJ，而把该数据包刚经过的岔路口更新为前一岔路口PJ。\n[0042] 步骤3、每个节点维持一个邻居列表，并预测车辆节点位置和维护邻居列表：利用街道上移动的车辆所在地理位置具有可预测性的特点和预测车辆节点位置的方法，每个节点预测其邻居节点(邻居节点是指当两个节点之间相互都在对方的通信范围之内，且没有被建筑物阻挡时，该两个节点被称为有邻居关系，或者说其中一个节点是另一个节点的邻居节点)的当前位置，并及时更新其邻居列表，以便减少信息维护工作量，并提高邻居列表信息的有效性。\n[0043] 在车载Ad Hoc网络中，因为车辆是在城市设定的街道上移动，因此可以预测其地理位置。本发明使用的预测车辆节点的位置的计算方法如下：\n[0044] 假设当前时间为t，节点i的位置是(xi，yi)，其速度是vi，走向岔路口B的位置坐标是(xB，yB)，前一个岔路口A的位置坐标是(xA，yA)；dis(A，B)是两个岔路口A到B的距离；\n[0045] 则在t+Δt，其中Δt＜dis(i，B)/vi时刻，该节点仍然在该街道上移动的位置坐标是：(xi+Δt×vi×(xB-xA)/dis(B，A)，yi+Δt×vi×(yB-yA)/dis(B，A))；而在t+Δt，其中Δt＞dis(i，B)/vi时刻，该节点i可能已经走出当前街道而进入另一条街道上了。\n[0046] 本发明中，每个节点都维持的邻居列表的信息是通过相邻的节点间广播问候消息HELLO完成交互的。该HELLO消息包括节点标识ID、节点当前所在的地理位置、时间戳、节点的当前速度及其移动方向。节点收到邻居节点发送来的HELLO消息后，对邻居列表中的上述信息进行更新。\n[0047] 因为车辆通常处于高速移动中，导致网络拓扑结构变化迅速。在节点高速运动的情况下，邻居列表有时并不能真实、有效地反映网络的实际情况；但是，提高HELLO消息的发送频率又会增加网络负载。本发明是利用上述位置预测计算方法来提高邻居列表信息的有效性和降低HELLO消息发送的频率。节点i是利用位置预测方法对邻居列表中的邻居节点的当前位置进行预测，并从邻居列表中删除已经走出当前街道的节点；同时，任何一个节点离开岔路口区域时，都要立即广播发送一个声明该节点的最新位置信息的HELLO消息，以便让其他节点更新其邻居列表中该离开岔路口的节点的信息。\n[0048] 步骤4、目的节点更新其位置消息：当目的节点移动到新的街道上后，向中间节点广播其位置更新消息；该位置更新消息包括消息ID、目的节点的IP地址、当前速度、位置信息及其运动方向，即目的节点刚刚离开的岔路口ID和走向的岔路口ID。中间节点缓存该位置更新消息或用该位置更新消息更新原有记录后，转发该位置更新消息；当需要时，中间节点利用目的节点的最新位置信息和实时建模信息进行岔路口的动态选择和数据包的转发。\n[0049] 步骤5、基于贪婪转发策略对数据包进行转发：中间节点在转发数据包而选择下一跳节点之前，先利用位置预测算法查看目的节点是否为其邻居节点，如果是，则直接把数据包发给目的节点；否则，根据中间节点位于岔路口区域或两个岔路口之间的道路上的不同，分别执行相应的贪婪转发策略转发数据包。\n[0050] 下面分别介绍上述两种贪婪转发策略的具体操作过程：\n[0051] (一)当中间节点位于岔路口区域时，贪婪转发策略转发数据包的方法是：根据中间节点的邻居列表进行位置预测，从走向当前岔路口的邻居节点中选择其中距离当前岔路口最近的节点作为下一跳节点；如果没有找到相应的节点，则把数据包暂存到缓存中，再使用探寻算法周期性地寻找是否有新的节点走进其通信范围；如果该中间节点离开岔路口区域但仍然没有找到一个合适的邻居节点转发数据时，则用该中间节点离开的岔路口和走向的岔路口分别替换数据包中的当前岔路口和前一岔路口。该方法的具体操作步骤如下：\n[0052] (5A)更新邻居列表：计算邻居列表中各个邻居节点的当前地理位置，并从邻居列表中删除与本节点不再具有邻居关系的节点；\n[0053] (5B)从邻居列表中走向当前岔路口的各个邻居节点中，查找距离当前岔路口最近的节点作为下一跳节点，若能够找到，则跳转执行步骤(5D)，否则，顺序执行步骤(5C)；\n[0054] (5C)把数据包暂存于缓存，再循环执行探寻算法，寻找是否有新的节点走进其通信范围；若探寻成功，则返回执行步骤(5A)，否则，结束本跳操作；\n[0055] (5D)把数据包转发给该找到的下一跳节点，结束本跳操作。\n[0056] (二)当中间节点位于两个岔路口之间的道路上时，贪婪转发策略转发数据包的方法是：根据中间节点的邻居列表选择距离当前岔路口最近的节点作为下一跳节点；如果没有找到相应的节点，就把数据包暂存到缓存中，使用探寻算法周期性地探寻是否有新的节点走进它的通信范围。该方法的具体操作步骤如下：\n[0057] (5a)更新邻居列表：计算邻居列表中各个邻居节点的当前地理位置，并从邻居列表中删除与本节点不再具有邻居关系的节点；\n[0058] (5b)从邻居列表中查找距离当前岔路口最近的节点作为下一跳节点，若能够找到，则跳转执行步骤(5d)，否则，顺序执行步骤(5c)；\n[0059] (5c)把数据包暂存于缓存，再循环执行探寻算法，寻找是否有新的节点走进其通信范围；若探寻成功，则返回执行步骤(5a)，否则，结束本跳操作；\n[0060] (5d)把数据包转发给该找到的下一跳节点，结束本跳操作。\n[0061] 在步骤5中，探寻算法的具体操作内容如下：\n[0062] A、持有数据包的节点先广播一个探寻请求消息，该探寻请求消息中包含该节点的当前位置信息和当前岔路口，并设置一个定时器；\n[0063] B、在定时器超时之前，如果有节点接收到该探寻请求，并且其位置位于持有数据包的节点和当前岔路口之间，则该节点立即返回探寻响应消息，该响应消息中包含收到探寻请求节点的ID、该收到探寻请求节点的地理位置信息、当前速度及其移动方向；持有数据包的节点接收到探寻响应消息后，提取探寻响应消息中的相关数据并更新邻居列表；并在定时器到达设定时间后，结束本次探寻操作，探寻成功；\n[0064] C、在定时器超时之前，如果没有任何响应消息，这时持有数据包的节点可能走到一个网络的边缘，即出现网络分割现象；此时，该定时器将延迟一段时间后重新返回执行步骤A的操作；若重复执行步骤A的操作达到设定的次数后，仍未探寻成功，则持有数据包的节点丢弃数据包，探寻失败。\n[0065] 申请人对本发明方法进行了仿真实施试验，通过理论分析和仿真实施例的实验论证，证明本发明的方法是有效的，能够实现发明目的。