一种城市车辆网络中的数据缓存算法

开篇：润墨网以专业的文秘视角，为您筛选了一篇一种城市车辆网络中的数据缓存算法范文，如需获取更多写作素材，在线客服老师一对一协助。欢迎您的阅读与分享！

摘 要:数据缓存在城市车辆网络中有着重要的应用。移动车辆通过缓存数据不仅可以减少自身访问数据的延迟,同时可以为整个网络节省带宽。所以,如何更有效地利用节点有限的存储是目前数据缓存研究的主要内容。重点分析了节点利用收益函数决定如何缓存数据,提出了利用本地访问频率和邻居节点访问频率构建收益函数的方法。最后,通过建立城市车辆网络场景并模拟验证了该收益函数下的数据缓存的优越性。

关键词:城市车辆网络;数据缓存算法;数据访问频率

中图分类号: TP393.02

文献标志码:A

Data caching algorithm in metropolitan vehicle network

SONG Hongbin, XIAO Xiaoqiang, XU Ming, LIN Lei

College of Computer, National University of Defense Technology, Changsha Hunan 410073,China)

Abstract: Data caching is an important technique in metropolitan vehicle networks. It can increase data availability and significantly improve the efficiency of information access by reducing the access latency and bandwidth usage. However, designing efficient caching algorithms is nontrivial when network nodes have limited memory. This paper analyzed how to cache with the help of benefit function, and proposed a way of using local access frequency and neighboring node access frequency to construct the benefit function. The authors simulated the algorithm using a network simulator (NS2), and its advantage was demonstrated in city scenarios.

Key words: metropolitan vehicle network; data caching algorithm; data access frequency

0 引言

随着车辆的普及和移动Ad Hoc网络(Mobile Ad Hoc Network,MANET)技术的不断发展,车辆网络(Vehicular Ad Hoc Network,VANET)逐渐成为新兴的研究领域。车辆网络是一个特殊的移动自组网,是自组织的、分布式的无线网络,在任何时刻移动的车辆通过无线信道组网,车辆间通过实时的交换交通信息,提供紧急报警消息的通告和各种分布式应用。在车辆网络中,数据始终是各类应用的中心,所以如何增加数据的可用性并减少数据传输延迟和带宽利用率是车辆网络研究的热点。

缓存技术是缓解数据访问的压力、减少网络通信流量、缩短用户访问延迟的经典方法,在计算机体系结构和分布式网络中,缓存技术被深入研究和广泛应用。同样,在车辆网络中,利用缓存技术,不仅可以减少节点自身访问数据的时间,周围节点也可以共享数据,从而从整体上减少网络带宽消耗,缩短访问延迟,大幅度提升车辆网络中数据获取的效率。

1 城市车辆网络

1.1 城市车辆网络的特点

城市车辆网络的实质是移动Ad Hoc网络(MANET)的一种特殊形式,因此它具有MANET的特点:1)节点地位平等、无中心网络的自组织性;2)网络拓扑结构动态变化的不可预测性;3)单跳、多跳共存的组网方式;4)无线传输带宽的有限性和无线信道的脆弱性。

同时,由于城市道路特殊性,使得城市车辆网络还具有如下特点:1)可预测移动;2)由于车辆高速移动性,导致动态的、快速变化的拓扑结构以及网络的分割特性;3)车辆节点不能保证可靠性;4)没有明显的电源限制。

由于以上特点,城市车辆网络中的数据缓存有了不同的意义。由于车辆移动性以及网络的分割性,之前的缓存算法只适用于普通的Ad Hoc网络,当应用在城市车辆网络时,就必须考虑城市车辆网络自身的特点。

1.2 城市车辆网络的应用实例

如图1所示,城市场景中,有固定的基站为周围车辆提供地图、旅游景点、饮食住宿等信息。当一辆在基站覆盖范围之外的车辆A通过多跳的方式向基站请求数据时,在这条路由路径上的节点B如果已经缓存了该数据,则由B向A发送数据,可以节省时间和带宽。オ

2 缓存算法具体描述

缓存算法的核心思想是节点如何利用有限的存储空间缓存数据,从而为自身服务,同时为邻居节点服务。

节点缓存任何一个数据都会得到一定的收益,节点根据收益的大小来决定在自身有限的存储空间里缓存哪些数据。文献[1]中提出的DGA算法定义的收益函数如下:

Bij=(Nj×Hj)/Sj

其中:Bij为节点i缓存数据j的收益;Nj为数据j的被访问频率;Hj为在没有本地缓存的情况下,节点i访问到数据j需要的跳数(在Ad Hoc网络中,数据传递的方式是hopbyhop,所以以跳数为单位计量数据传递的消耗);Sj为数据j的大小。节点计算每个数据的收益,收益越大越值得缓存,当缓存满了时,就用收益大的数据项替换掉收益小的数据项。

由于城市车辆网络的特性,车辆可以看作是以簇的方式运动,节点间合作就显得更加突出。为了最大化利用节点的存储空间,本文在文献[1]的研究基础上研究了一种新的收益函数,提出了利用本地访问频率和邻居节点访问频率来构造收益函数的方法。本地访问频率即自身节点对某一数据的访问频率。邻居节点访问频率是指节点转发的来自邻居节点的对某一数据的访问频率。д饫锝这两种访问频率分别记为Nj_access_myself和Nj_access_neighbors。显然,这两种访问频率对节点的缓存决策的影响是不同的,也就意味着有不同的权重,修改后的收益函数可以表示为:

Bij=[Nj_access_myself*weight+

Nj_access_neighbors*(1-weight)]×Hj/Sj

图片

图1 城市车辆网络中缓存应用实例

3 模拟工作

模拟使用NS2模拟工具,通信协议选择AODV。

基础场景如图2所示,是带有两个十字路口的城市道路。车辆在道路上按交通规则前进,速度服从(5km,20km)上的均匀分布,车辆到达十字路口时,以1/2的概率继续按原方向前进,以1/4的概率分别左转和右转。场景中,车辆数目维持在100。

图片

图2 模拟场景图

数据访问模型 场景需要的数据共有1B000个,每个数据的大小服从(150k,750k)上的均匀分布。1号节点存有所有奇数号数据,2号节点存有所有偶数号数据。本文的模拟中不考虑数据的有效期,假设数据在模拟时间内一直是有效的。这样的假设,将重点放在收益函数上,而不用再去关心数据更新带来的各种消耗。节点访问数据时,采取文献[2]中的所用的biasedZipflike访问模型。Zipflike模型常被用于模拟非均匀分布的访问频率。biasedZipflike访问模型,在此基础上加入了节点所处地理位置的因素,更符合真实移动场景,更能体现出在某一位置周围的节点容易访问相同的数据。

客户端请求模型 每一个节点有单独的数据访问流。该数据访问流服从Tquery时间的指数分布。如果节点在发送一个数据访问后,在Tquery时间内没有接收到应答,则认为本次数据访问不可达。节点只有在数据不可达或在Tquery时间内接收到应答才会发送下一次数据访问。根据实际情况以及文献[2]中的模拟结果,本文模拟中设置Tquery为40s。

┑1期 ┧魏瓯蟮:一种城市车辆网络中的数据缓存算法

┆扑慊应用 ┑30卷

4 模拟结果

图3,图4展示了Nj_access_myself权重分别为0.1、0.3、0.5、0.7、0.9以及DGA算法的模拟结果。

图片

图3 本文算法与DGA算法的平均延迟比较

图片

图4 本文算法与DGA算法的数据可达率比较

从模拟结果可以看出,随着Nj_access_myself权重的增大,网络的平均访问延迟在逐渐减小,访问可达率逐渐增大。在Nj_access_myself0.5时,网络的平均延迟、数据可达率都比DGA算法好。这说明在城市车辆网络里,节点的大部分存储空间用来缓存自己需要的数据比较好。

图5,图6展示了Nj_access_myself权重分别为0.5、0.6、0.7、0.8、0.9、1.0以及DGA算法的模拟结果。

图片

图5 权重≥0.5时与DGA算法的平均延迟比较

图片

图6 权重≥0.5时与DGA算法的数据可达率比较

Т幽D饨峁可以看出,Nj_access_myself的权重取0.8或0.9都是可行的,Т耸钡钠骄延迟和数据可达率都达到了较优值。

5 结语

本文重点研究了城市车辆网络的特点,在此基础上,提出了一种适用于城市车辆网络的数据缓存算法。与DGA算法相比,本文提出的数据缓存算法更适合城市车辆网络,可以到达更低的数据延迟和更高的数据可达率。最后,通过NS2建立模型,模拟验证了以上结论的正确性。

参考文献:[1] TANG BIN, GUPTA H, DAS S. Benefitbased data caching in Ad Hoc networks[C]// Proceedings of the 2006 IEEE International Conference on Network Protocols. Washington, DC: IEEE Computer Society, 2006:208-217.

[2] YIN LIANGZHONG, CAO GUOHONG. Supporting cooperative caching in Ad Hoc networks[J]. IEEE Transactions on Mobile Computing, 2006:10(5):77-89.

[3] MUSTAFA M D, NATHRAH B. Improving data availability using hybrid replication technique in peertopeer environments[C]// Proceedings of the 18th International Conference on Advanced Information Networking and Applications. Washington, DC: IEEE Computer Society, 2004:593.

[4] ZIPF G. Human behavior and the principle of least effort[M]. Cambridge, MA: AddisonWesley Press, 1994.

[5] BRESLAU L, CAO P, FAN L, et al. Web caching and Zipflike distributions: Evidence and implications[EB/OL].[2009-05-10]./wli/zipf/breslau99.pdf.