Max-Util: A Utility-Based Routing Algorithm for a Vehicular Delay Tolerant Network Using Historical Information
Milind R. Penurkar and Umesh A. Deshpande
Abstract A vehicular delay tolerant network (VDTN) has emerged as special type of delay tolerant network (DTN), characterized by the non-existence of end-to-end connectivity between different source nodes and destination nodes thereby dimin- ishing the possibility of delivering messages to the destination node. Hence, routing becomes a vital issue in VDTN. In this paper, a utility-based routing algorithm (Max-Util) for a VDTN has been proposed. This algorithm exploits the historical information of a node for computing the utility of a node to take a decision to forward a message among nodes. This history comprises the past encounters of a node with destination and relay nodes, the contact duration between nodes and the remaining buffer size of a node in contact. Our evaluations show that, Max-Util performs better in terms of message delivery ratio, overhead ratio and average delivery latency as compared to some existing DTN routing approaches like PRoPHET and Spray-and-Wait.
Keywords Vehicular delay tolerant networks Intermittent connectivity Routing · Utility · Forwarding · Flooding
· ·
Introduction
Delay tolerant networks (DTN) are mobile ad hoc networks where end-to-end connectivity does not exist most of the time because of short radio transmission range, limited power of evolving wireless communication devices, disruptions caused in the networks and network partitioning. VDTN is an example of DTN where vehicles act as moving nodes to carry devices to transmit messages in the network. VDTNs seize help of DTN capabilities to support disruptions for pro- viding the network connectivity. VDTNs are more useful in rural or mountainous areas because of the existence of intermittent connectivity.
Traditional routing protocols such as DSDV [1], DSR [2], AODV [3], etc. in the MANET/VANET establish an end-to-end path between a source and a destination node before sending any packets. Routing in such a network is all about finding the shortest path in the network and to forward packets on this path. These protocols naturally fail when applied to a VDTN because an instantaneous end-to-end path would be lacking to route the packets. To make communication possible in such a network, one must facilitate the routing of messages without establishing an end-to-end path in advance. Thus, routing becomes a challenging issue in this class of a network. Routing in these networks is not to devise the shortest path among the nodes but to ensure that messages reach the destination in one way or another. VDTNs employ store-carry-forward mechanism to route messages to the destination.
Among the number of routing algorithms discussed in the literature, an impor- tant type of routing algorithms discussed in a DTN literature focuses on the utility of nodes. Utility of a node can be defined as its fitness to forward a message to the destination. A utility based algorithm brings into play the utility of nodes for taking a decision in the routing process. In this paper, we propose Max-Util, a hybrid utility based routing algorithm that exploits both destination dependent as well as destination independent utility functions to route messages in a VDTN.
We show that Max-Util performs better by increased delivery ratio, reduced overhead ratio and decreased average delivery latency as compared to PRoPHET
[4] (the utility based algorithm), except Spray-and-Wait [5] (a controlled flooding algorithm) that succeeds Max-Util in terms of reducing the overhead ratio.
The remainder of this paper is organized as follows. Section 2 describes the related work and contributions in this area. Section 3 presents the Max-Util algo- rithm in detail. Section 4 shows simulation scenarios and analyzes the obtained results, Sect. 5 concludes the paper and Sect. 6 provides guidelines for future work.
Related Work
A number of routing approaches are designed, developed and simulated in a VDTN. In the following section, we discuss basic approaches for routing algo- rithms followed by the utility based routing algorithms.
2.1 Basic Approaches
-
-
- Forwarding Based Routing Algorithms
-
In these types of based First is the forwarding technique, in that only one copy of a message exists at any time in the network. First Contact [6], Spray-and-Focus [7] and FRESH [8] are some examples of the forwarding approach.
-
-
- Flooding and Controlled Flooding Based Routing Algorithms
-
In the flooding routing technique, every node floods messages to every other node that it meets and therefore a number of copies of a message exist at any time in the network. Most familiar form of flooding is Epidemic [9].
To prevail over the operating cost of a fully flooding approach, researchers have arrived at a number of approaches [6–8]. Controlled flooding algorithms have moderate message delivery ratio compared to their fully flooding based counterparts with less overhead ratio.
Utility-Based Routing Algorithms
In this kind of algorithms, a forwarding decision depends on the context of the current node that holds messages and the node that is encountered. A set of parameters associated with the nodes in contact are obtained for estimating the nodesrsquo; utility for a given message targeted t
全文共20107字，剩余内容已隐藏，支付完成后下载完整资料
Max-Util：一种基于实用程序的使用历史信息的车载延迟容错网络路由算法
Milind R. Penurkar和Umesh A. Deshpande
摘要：车辆延迟容忍网络（VDTN）已经成为特殊类型的延迟容忍网络（DTN），其特征是不存在在不同源节点和目的节点之间的端到端连接，从而减少向目的地传递消息的可能性。节点。因此，路由成为VDTN中的一个重要问题。本文提出了一种基于效用的VDTN路由算法（Max-Util）。该算法利用节点的历史信息来计算节点的效用，以决定在节点之间转发消息。该历史包括节点与目的地和中继节点的过去相遇、节点之间的接触持续时间和接触节点的剩余缓冲器大小。我们的评估表明，与一些现有的DTN路由方法（如PRoPHET和Spray-and-Wait）相比，Max-Util在消息传递率、开销比和平均传输延迟方面表现得更好。
关键词：车辆延迟容忍网络间歇连通路由 效用 转发 洪泛
1简介
延迟容忍网络（DTN）是移动自组织网络，由于无线电传输距离短，演进中的无线通信设备的功率有限，网络中断造成的网络和网络划分，大多数情况下不存在端到端连接。VDTN是DTN的一个例子，其中车辆充当移动节点以携带设备在网络中传输消息。VDTN抓住DTN功能的帮助来支持提供网络连接的中断。由于存在间歇连通性，VDTN在农村或山区更加有用。
传统路由协议如MANET / VANET中的DSDV [1]，DSR [2]，AODV [3]等在发送任何数据包之前在源节点和目的节点之间建立端到端路径。这种网络中的路由都是寻找网络中的最短路径，并在这条路径上转发数据包。这些协议在应用于VDTN时自然会失败，因为缺少路由数据包的瞬时端到端路径。为了在这样的网络中实现通信，必须提前实现消息路由而不必事先建立端到端路径。因此，路由在这类网络中成为一个具有挑战性的问题。这些网络中的路由不是设计节点间的最短路径，而是确保消息以某种方式到达目的地。VDTN采用存储转发机制将消息路由到目的地。
在文献中讨论的多种路由算法中，DTN文献中讨论的一种重要类型的路由算法着重于节点的效用。节点的效用可以被定义为将消息转发到目的地的合适性。基于效用的算法发挥节点在路由选择过程中作出决定的效用。在本文中，我们提出Max-Util，一种基于混合效用的路由算法，它利用目的地相关和目的地独立效用函数在VDTN中路由消息。
我们可以证明，与PRoPHET[4]（基于效用的算法）相比，Max-Util通过提高交付率，降低开销率和降低平均交付延迟来实现更好的性能，除了Spray-and-Wait [5]（一种受控洪泛算法），在降低开销比率方面继承了Max-Util。
本文的其余部分安排如下，第2节介绍了这方面的相关工作和贡献，第3节详细介绍了Max-Util算法，第4部分显示了模拟场景并分析了所得结果，第5部分总结了本文，第6部分提供了未来工作的指导原则。
2相关工作
许多路由方法是在VDTN中设计，开发和模拟的。在下一节中，我们将讨论路由算法的基本方法，然后讨论基于效用的路由算法。
2.1基本方法
2.1.1基于转发的路由算法
在这些类型的基础上，首先是转发技术，因为网络中随时只存在一个消息副本。 First Contact [6]，Spray-and-Focus [7]和FRESH [8]是转发方法的一些例子。
2.1.2洪泛和受控洪泛的路由算法
在泛洪路由技术中，每个节点都会将消息泛洪到每个遇到的其他节点，因此网络中随时都会存在多个消息副本。最常见的洪水形式是Epidemic [9]。
为了胜过完全淹没方法的运营成本，研究人员已经采取了许多方法[6-8]。控制洪泛算法具有中等的信息传递比率，与其开销比率较低的基于全面洪泛的对应方法相比。
2.2基于实用程序的路由算法
在这种算法中，转发决策取决于保存消息的当前节点的上下文和遇到的节点。获得与接触节点相关联的一组参数，用于估计针对特定目的地的给定消息的节点的效用。此实用程序基于效用函数进行评估，该函数在文献中分为两种类型，分别为目标相关（DD）效用函数和目标无关（DI）效用函数[6]。用于构建DD效用函数的参数示例包括过去遇到的历史，访问过的位置模式和社交网络，而构建DI效用函数的参数示例包括移动量，节点资源和合作行为[6]。有两种类型的基于工具的复制：如[3]中讨论的非受控和受控的基于工具的复制。受控的基于实用程序的复制的一个例子是SMART复制[6]，而不受控制的基于实用程序的复制则是PRoPHET [4]。
SMART复制集成了DD和DI实用程序功能，用于计算实用程序，
即它本质上是混合的（它利用“过去遭遇的历史”作为目的地依赖效用函数，而“移动性和节点资源”是使用的目的地独立效用函数）。基于接口的路由（EBR）[10]是受控实用程序复制的另一个示例。在这个算法中，节点遇到的未来速率是使用经过的节点来预测的。 EBR利用DD效用函数（历史遭遇）来计算效用。
PRoPHET中提供了不受控制的基于实用程序的复制功能。在这个算法中，每个节点使用历史遭遇的历史来维护一个概率向量，该向量保存节点未来遇到的概率。基于这个概率，只有当该节点很有可能在将来遇到目的地时才将消息副本转发给新节点。 PRoPHET利用DD效用函数（过去的历史记录）来计算效用。
3 Max-Util：基于效用的算法
3.1背景
在VDTN中，以下问题尚未完全解决。
1.由于节点的行驶速度，节点在短时间内保持接触。在文献[11]中，研究人员表明，使用IEEE802.11g时速20km / h的汽车之间的接触持续时间约为40s，时速40km / h约为15s，时速60km / h约为11s。当传输控制协议（TCP）以60公里/小时的速度使用时，平均可以传输80Kb的数据，并且在大多数情况下根本不传输数据。 UDP产生了更好的结果，以60km / h的速度在接触中传输了大约2Mb。因此，在联系机会期间可以发送的消息的数量取决于联系持续时间。
2.由于移动节点的存储空间有限，因此可能无法容纳所有收到的消息。因此，接触节点的剩余缓冲区存储对消息传输有很大影响。
3.Node与目的节点或不同路边单元（RSU）相遇的历史也被称为中继节点，对决定是否将消息转发到有问题的节点起着决定性的作用。这似乎是现实的，因为如果一个节点在过去遇到过目的节点或RSU，那么它很可能在将来再次遇到它们。
考虑到所有这些概述我们历史信息的参数，我们提出了Max-Util一种基于混合效用的路由算法，它使用节点的历史信息在VDTN中路由消息。它通过在历史信息中应用手头参数的加权平均值计算总体效用，然后将消息转发给具有最大效用的候选节点。 Max-Util是一种不受控制的基于效用的算法，它本质上是混合的，因为它结合了目标相关以及目标独立功能。考虑的目标相关函数是目标会议计数和中继会议计数，其中接触持续时间和剩余缓冲区大小已被包括为目标独立功能。
3.2 假设
以下是Max-Util算法的假设。
3.2.1 General
网络中的所有节点都有唯一的标识（ID）。网络中存在两种类型的终端节点：源终端节点和目的地终端节点。它们作为固定节点并被部署在车辆网络的两端（例如，具有存储和互联网连接的一些设备）。移动节点是携带同质或异构设备（例如手机，PDA，具有蓝牙或Wi-Fi的笔记本电脑）传输消息的交通工具。这里考虑的移动节点是遵循基于地图的运动的汽车，即它们在每次从一个位置到另一个位置时都遵循不同的路径，而不是使用基于地图路线的运动遵循预定路径的公共汽车，因此这看起来是现实的假设。路边单位（例如，一些设备具有存储和无线连接）不同，并且它们被放置在不同的交叉点处以提高交付比率。根据VDTN术语，它们也被称为中继节点。
3.2.2消息创建和复制策略
只有源节点创建消息。除目的节点以外的所有节点（源节点，中继节点和移动节点）都使用消息复制。
3.2.3调整和放弃政策
消息的调度基于随机策略，因为任何来自队列的随机消息都将被选择用于调度。丢弃消息是基于网络的生存时间（TTL），即当消息的TTL达到时，它将从队列中丢弃。
3.2.4转发/泛滥政策
源节点，中继节点和移动节点采用选择性泛洪（这将基于3.4节中描述的算法）。
4实验和结果
4.1Experimentation
试验已经在机会网络环境（ONE）[12]模拟器中进行。以下假设已针对所有情况制定。被称为世界大小的网络规模设置为4000times;3500平方米。终端节点放置在车辆网络的最末端，而中继节点放置在网络上的道路交叉点上。网络中的许多源和目的地终端节点被固定为五个。所有源节点彼此靠近放置，但不在彼此的范围内。目标节点标记了相同的类比。网络中的中继节点数量固定为10。这些被放置在网络中不同的道路交叉点上，以增加算法的情况2中提到的消息传送比率。网络中移动节点的数量在20到140之间变化，导致节点密度的变化。
ONE仿真器没有MAC层和物理层，接口规范已经完成了这些层的抽象[12]。蓝牙接口假设所有节点的传输范围为100米，传输速度为3 Mbps。随机路点模型被用于节点移动性。消息的大小从512 KB到1 MB随机选择。消息创建间隔在40到50秒之间随机设置。消息的TTL设置为300分钟。每次模拟运行时间为43秒（即12小时）。
以下场景已经过实验。在这种情况下，移动节点的数量从20到140不等，所有节点的缓冲区大小固定为50 MB。经过实验后，我们得出结论，alpha;的典型值应该是0.7，所以beta;和gamma;的值为0.15。
以下性能测量用于比较结果。
1.交付比率：这定义为传递到目的地的消息数量与创建的所有消息数量之比。
2.平均交付延迟：这被定义为交付消息到目的地的总延迟与交付消息总数的比率。请注意，传送延迟仅针对已传送的消息计算，并非针对所有已创建的消息计算。
3.Overhead比率：这被定义为中继消息的数量与延迟消息的数量与延迟消息的数量之差的比率。
4.2Results
我们将Max-Util算法与PRoPHET（基于非受控复制的实用算法），Spray-and-Wait（受控洪泛算法）进行了比较。对于Spray-and-Wait方案，我们将最大份数设置为6（以确保较高的交货率）。
如图1所示，当移动节点的数量从20增加到160时，几乎在所有情况下，所有算法的传输率都会增加。 Max-Util算法在传输率方面优于所有其他算法。这可以解释如下。当节点密度增加时，具有目的地节点和中继节点的节点的接触数量增加，由此增加目的地会议计数（DMC）以及中继节点会议计数（RMC）。根据Max-Util算法，DMC和RMC对整体效用的贡献更高，并且将消息转发给总效用值最高的节点。
如图2所示，随着节点数量的增加，消息传递等待时间有时会减小并且有时会增加。等待时间的减少是因为在消息转发中涉及更多节点，传送比率也增加，从而消息到达目的地节点所需的时间量减少。传输延迟的增加是由于底层路由算法和移动性的结合。对于所有的算法来说这一般是正确的。对于Max-Util算法，也应用相同的类比。对于Max-Util，由于节点存储有关其他节点的历史记录，因此决策制定变得更快，从而缩短了传递消息的时间，因此尽管邮件传递比率很高，但传输延迟较低。
图3显示了所有路由器对节点密度的开销比。据观察，与PRoPHET算法相比，Max-Util具有较少的开销比，但与Spray-and-Wait算法相比具有较高的开销比。
这是因为与PRoPHET算法相比，Max-Util不仅传递更少的消息，而且具有良好的传输率。在Spray-and-Wait算法中，节点将非常有限数量的消息喷到节点上（在我们的例子中，Spray-and-Wait假定有6个副本），直到它们直接与目的地节点相遇。另外，如图3所示，随着节点密度从20增加到160，除初始阶段之外，几乎所有密度变化的情况下，Max-Util的开销比都下降。最初（从20到80的节点密度）随着节点密度的增加，开销比率是波动的，因为与中继消息相比，所传送的消息非常少。开销率的下降是因为节点数量增加以及中继消息数量的增加。对于高于80的节点密度，开销比率增加并且随着传送比率和中继消息的相对增加而不断增加。
5结论
在本文中，我们为VDTN设计了一个选择性的基于实用程序的转发策略，称为Max-Util。 Max-Util不是在不应用任何智能的情况下使用转发消息，而是将消息转发给那些有更多机会传递消息的节点。 该选择基于存储在节点中的历史信息。 仿真结果表明，与PRoPHET算法相比，Max-Util在传输率和开销率两个性能指标上表现得更好。 它的传输比率优于Spray-and-Wait算法，但开销率更高。 因此，公平地说，Max-Util成功实现了在间歇性连接的网络中提供高效路由并且路由开销较低的目标。
6未来工作
在我们的算法中，我们假定节点以随机方式管理它们的队列，即每当新消息到达完整队列时，就从队列中随机选择的消息被丢弃。在这里使用其他策略可能会更好。例如，我们可以为消息分配优先级，并根据其传送的可能性。最后，为了减少节点上的缓冲区需求以进一步提高性能，目标节点向移动节点注入确认消息（表示收到某些消息）可能会有所帮助。在我们未来的工作中，我们建议将这些改进包括在所提出的算法中，并对性能评估进行广泛的实验。
References
-
Johnson, D., Maltz, d.: Dynamic source
全文共7683字，剩余内容已隐藏，支付完成后下载完整资料
资料编号：[10781]，资料为PDF文档或Word文档，PDF文档可免费转换为Word
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
