基于自适应的车载网信息交换算法.doc

《基于自适应的车载网信息交换算法.doc》由会员分享，可在线阅读，更多相关《基于自适应的车载网信息交换算法.doc（7页珍藏版）》请在三一办公上搜索。

1、精品论文基于自适应的车载网信息交换算法戴其进，孙咏梅（北京邮电大学信息与通信工程学院，北京 100876）5摘要：路由技术是车载网络中的重大挑战之一。建立路由时，节点寻找下一跳需要知道邻居 节点的信息，即节点需要与邻居节点交换信息。而邻居节点较少或者较多时采用相同的策 略会导致信息交换耗时较长，降低了网络吞吐量，增加了端到端时延，网络性能下降。因 此，本文结合邻居节点的数量，参考 802.11DCF 机制，设计出一种自适应的信息交换方式， 采用自适应信息交换方式选择最佳下一跳，优化路由协议的总体性能。10关键词：车载网；路由协议；信息交换；自适应算法中图分类号：TN929An adaptive

2、ly exchange-of-information algorithm inVANETs15Dai Qijin, Sun Yongmei(School of Information and Communication Engineering,Beijing University of Posts andTelecommunications, Beijing 100876)Abstract: Routing protocol is one of the key research techniques in Vehicular ad hoc networks. Anode needs to kn

3、ow its neighbors information when it looks for the next hop. Whenever the20number of neighbor nodes is different, using the same strategy to exchange information wastesmore time. Combined with the number of neighbor nodes and 802.11 DCF, it puts forward an adaptive algorithm. It means that a node wh

4、ose number of neighbors is great will choose a distributed next-hop election method, while a node whose number of neighbors is low will choose a centralized next-hop election method. The improved scheme optimizes the overall performance25of routing protocol.Keywords: Vehicular Ad-hoc Networks; Routi

5、ng Protocol; exchange information; an adaptive algorithm0引言30车载网与传统的移动自组织无线网络相比，节点所处的环境受实际的道路场景限制以及 节点行驶的目的性较强，而且随着 GPS 和电子地图的广泛使用，节点可以获得自己位置信 息以及周围道路布局信息，因此基于地理位置的路由协议更加接近车载网路由协议的设计需 求。现有的路由协议一般分为:基于贪婪算法和基于十字路口。贪婪算法地理路由有：基于 地理和能量的路由1、贪婪周边无状态路由2、地理源路由协议3、贪婪周边协同路由协议435等。基于十字路口的地理路由有：IBRP5协议等。 不管是哪一种协

6、议，研究人员运用到一个很重要的前提条件是节点根据其邻居的信息选择最佳的邻居节点作为其数据传输的下一跳，即节点需要知道其邻居节点的信息或者将自己 的信息告诉给邻居节点，因此节点与邻居的信息交换方式将会影响路由协议的性能。节点间 信息交换受到邻居数量的直接影响，而在实际的车辆运行环境中，车辆的邻居数量可能随着40车辆所处的地理位置、时间而出现很大的差异，因此本文将从 802.11 协议出发，结合邻居 的数量，设计出一种自适应的信息交换策略，进而对地理路由协议进行优化。作者简介：戴其进，（1987-），男，硕士研究生，通信与信息系统。通信联系人：孙咏梅，（1971-），女，副教授，物联网。E-mai

7、l: ymsun- 3 -1802.11 协议 DCF 介绍802.11MAC 层的主要协议是分布式协调功能(distributed coordination function，简称 DCF)协议。DCF 是基于 CSMA/CA(Carrier Sense Multiple Access with Collision Avoidance)的随机45访问机制67。下面简要介绍 DCF 协议的请求发送(Request to Send，RTS)信号和清空传送区 域的清除发送(Clear to Send，CTS)访问方法。为了防止通信冲突发生，802.11 标准允许通信节点使用 RTS 和 CTS 信

8、号。增加 RTS 和 CTS 的原子通信过程包含了：RTS 帧、CTS 帧、数据帧以及最后的响应帧。具体过程为： 假设节点 1 有数据帧发送给节点 2，那么节点 1 首先送出一个 RTS 帧开启数据传送过程。50RTS 帧的目标有两个：与接收数据帧的节点 2 进行预约，占有节点 1 和节点 2 之间无线链 路的使用权；其他节点接收到 RTS 帧后，保持沉默。节点 2 收到来自节点 1 的 RTS 帧后， 节点 2 将给节点 1 发送 CTS 帧，作为应答。CTS 也可令其他节点保持沉默。等节点 1 和 2 之间的 RTS/CTS 完成交换过程，即节点 1 和 2 释放与其他节点之间的无线链路的

9、使用权， 完全占有了两者之间的通信链路，无需担心来自其他隐藏节点的干扰。55802.11 协议的 DCF 通信模式成为无线通信中的一种基本通信模式，而车载网中车辆基 本上都安装了能够发送、接收的无线通信装置，可以将车辆作为无线通信网络的基本节点。 车辆间的通信模式与上面的通信模式一致。车载网中节点选择下一跳时需要与其邻居节点交 换信息，例如位置、速度。根据邻居节点的信息，最终从邻居中选择出最佳下一跳作为转发 节点。如何在较短时间内以及通信数据没有冲突的前提下，当前节点准确的选出最佳下一跳，60是车载网中需要优化的地方。如何在 DCF 机制的基础上，较短时间内正确的选择出下一跳 将在路由算法优化

10、思路中论述。2邻居数量预测节点与邻居通信的数据量与其邻居数量成正比例的关系，如何准确的获得邻居节点的数 量是一个首先要解决的问题。由于节点在不同的时间、不同的位置，其邻居数量肯定是不一65样的。但是根据其历史的运行轨迹，可以估计出节点在某一时间某一区域邻居的数量。下面 介绍其估计算法。2.1理解车辆的移动特性郑宇博士的城市计算研究提到车辆的移动体现了人类的一种行为，并推断用户交通方式 的方法分为三步：采用一个基于改变点的分割方法，改变推理模型和基于图的后处理算法。70首先，采用基于改变点的分割方法将每个 GPS 轨迹划分为属于独立的交通模式的不同部分。 第二，从每个部分中识别出一组复杂的特性,

11、该特性不受交通条件的影响。接着，这些特性 用来生成一般的推理模型,从而能够区分该区域的不同交通模式。第三，进行基于图的后处 理，进一步提高了推理的性能。经过上面三步，可以获得车辆在不同的区域的移动特性。2.2根据出租车数据，估计其邻居数量75T-drive 项目8利用 2009 年至 2010 年取自北京 33000 辆出租车的 GPS 信息，将 GPS 数 据与电子地图对应，得到车辆分布热点图，如图 1。从热点图可以看到，不同的路段上车辆 的密度差距较大，颜色越亮表示密度越高。图 1 反映北京出租车轨迹数据分布的热度图80Fig. 1 Heat map of the partitioned

12、regions in Beijing上图可以看到不同的道路上车辆的数量由较大的差距，而不同的时间，同一道路上车辆数量的差距也是比较大的。就城市的交通状况而言，本文进一步将每天的时间分割成一些时 间段。具体的时间划分如表 1：85表 1 具体时间划分Tab. 1 Time division参数 工作日 休息日Slot1 7:00am-10:30am 9:00am-12:30pmSlot2Slot3Slot410:30am-4:00pm4:00pm-7:30pm7:30pm-7:00am12:30pm-7:30pm7:30pm-9:00am9095100时间分割让本文能够从历史数据集中找到车辆位置

13、的时间相关性，这能够更好的估计车辆在某一时刻其邻居的数量。3自适应信息交换算法通过对节点邻居数量估计的介绍，本文可以使用其算法估计出节点的邻居数量。同时结 合 DCF 机制，本文提出一种自适应信息交换算法。3.1算法思路信息交换的目的是中心节点（即当前发送信息的节点）在下一跳选择时提供邻居节点的 信息，所以需要保证中心节点能够完全准确的获得邻居节点的信息。除了准确性，中心节点 需要尽量在较短时间内选择出下一跳。本文首先对集中式和分布信息交换方式进行说明，然 后提出自适应信息交换方式算法。3.1.1集中式信息交换方式 中心节点要知道其邻居节点的信息，中心节点先发出广播，其邻居节点都会接收到广播消

14、息。此时邻居节点都需要将自己的信息告诉给中心节点，那么邻居节点开始竞争与中心节点通信的信道，没有竞争到信道的节点将处于退避阶段，等待信道的使用权。假设节点 1 首先获得无线信道的使用权，如图 2 所示，节点 1 将发送 RTS 消息给中心节点，中心节点 收到来自节点 1 的 RTS 消息后，将发出 CTS 消息，保证节点 1 与中心节点原子通信过程的- 7 -105110完整性。当节点将自己的信息告诉给中心节点后，将释放信道。其他节点开始重新竞争信道，获得信道使用权的节点将自己的信息发送给中心节点，直至所有邻居节点都将自己的信息发 送给中心节点。中心节点根据收集到的邻居节点信息，将根据下一跳选

15、择计算函数来选择出 最佳下一跳。邻居节点 i （如图 2 中示例， i 的取值范围为 1 到 6）与中心节点所花的时间为：iT = DIFS + RTS + SIFS + CTS + DATA + ACK(1) 其中 DIFS 是分布式帧间间隔，SIFS 是最短的时序间隔，DATA 为邻居节点发送信息给 中心节点所花的时间，ACK 为中心节点回复消息所花时间，CTS 和 RTS 为发送 CTS 和 RTS消息所花的时间。所有邻居节点将信息发送给中心节点所需要的时间为：115T = i Ti(2)可以看到当邻居节点数量不断增大时，为了避免碰撞，中心节点需要花更长的时间才能 完全正确的获得邻居节点

16、的信息。所以该种信息交换方式在邻居数量较少时，信息交换所花 的时间较少；而随着邻居数量的增加，信息交换所花的时间将成正比例增长。120125130135图 2 集中式信息交换方式Fig. 2 Centrally exchange-of-information approach3.1.2分布式信息交换方式 前面已经介绍了集中式信息交换方式，并且知道了当邻居数量增加时，其性能将不断下降。而当邻居节点数量增加时，本文将采用分布式信息交换方式。具体方法为：假设中心节点与邻居节点都处于空闲状态， 首先，中心节点广播消息给邻居节点，告诉邻居自己即将广播自己的信息，使其邻居节点都处于接收状态。 其次，邻居节

17、点接收到消息后，将准备接收中心节点发送数据的消息。中心节点将自己的信息广播给自己的所有邻居。 再次，邻居节点接收到中心节点的信息后，将结合自己的信息进行计算，获得一个权值，并将权值映射为等待函数。例如，邻居节点接收到中心节点的位置、速度信息后，将根据下 一跳选择目标函数的计算公式，获得计算的值。当下一跳选择的标准为目标函数值最大的邻 居时，可以将计算值映射为等待函数，例如直接取倒数，从而保证计算值越大时，其等待时 间越短。这样确保目标函数值最大的邻居能够当选为最佳下一跳。接着，等待时间较短的节点在等待时间结束后将发送当选为最佳下一跳的消息给中心节 点。如图 3 所示，当节点 1 的等待时间与其

18、他邻居节点相比，时间最短，那么节点 1 的等待140时间结束后，将发送当选为下一跳消息给中心节点。最后，中心节点收到当选下一跳消息后，将广播等待结束消息给邻居，处于等待时间的 邻居接收到等待结束消息后，结束等待。信息交换过程结束。 经过这一过程，中心节点即可选择出最佳下一跳。同样用整个过程花费的时间作为评价该种 信息交换方式性能的标准。其整个过程的所花费的时间为：T = DATA + ACK + WAIT + Message *2 (3)145150其中 DATA 时间为中心节点广播信息给邻居所花的时间，ACK 为最佳下一跳发送给中 心节点的确定时间，WAIT 为最佳下一跳的等待时间，Mess

19、age 为广播一个消息所花的时间。可以看到，分布式信息交换过程与节点的数量基本无关，很大程度上是由等待时间映射 函数来决定整个信息交换过程所需要的时间，因此当邻居节点数量过多时，该种信息交换方 式等待的时间较短；而当邻居节点数量较少时，例如即使中心节点只有一个邻居节点，该邻 居节点仍然需要等待一段时间，才能将当选为最佳下一跳的消息发送给中心节点，导致时间 浪费，性能下降。该策略还有一个明显的缺陷是，由于邻居节点不会将自己的信息发送给中 心节点，中心节点将无法获得其邻居节点的信息，因此当中心节点需要邻居节点的信息时， 仍然需要经过集中式信息交换的过程。155160图 3 分布式信息交换方式Fig

20、. 3 Distributionally exchange-of-information approach3.1.3自适应信息交换方式 前面分别介绍了集中式和分布式信息交换方式，分析了节点的邻居数量对信息交换过程所花费的时间的影响。而且在本章的节点邻居数量的预测分析中，已经讨论了对于节点邻居数量的预测是可行的。根据邻居数量的多少，本文将采用自适应的策略来选择信息交换方式， 引入邻居数量的门限值，即当邻居数量较少时，低于门限值，采用集中式信息交换方式；而 当邻居数量较多时，高于门限值，采用分布式信息交换方式。3.2 算法流程图结合基本的路由算法和自适应信息交换方式，下一跳选择算法的流程图如图 4

21、 所示：165图 4 下一跳选择算法的流程图Fig. 4 Flow chart of next-hop election method其中集中式信息交换方式的流程图，如下图 5(a)，分布式信息交换方式的流程图如下图5(b)：170175180185图 5 (a)和(b)分别为集中式和分布式信息交换方式流程图Fig. 5 (a) is flow chart of centrally exchange-of-information approach, (b) is flow chart of distributionally exchange-of-information approach优化的

22、路由协议在基本的路由协议的基础上增加自适应信息交换方式，因此节点不需要 改变路由协议下一跳的选择策略，能够根据邻居节点的数量选择信息交换方式，最终在降低 信息传输带来的时延的基础上，选择出最佳下一跳，从而满足不同的网络密度下，提高路由 协议性能。3.3 仿真结果本部分使用网络仿真软件 NS2 对自适应信息交换方式进行仿真以验证算法的性能。下 面将自适应信息交换方式与最基本的贪婪周边无状态路由(GPSR)协议进行结合，即优化的 GPSR，在不同的节点密度条件下进行仿真，并与基本的 GPSR 的结果进行对比，对比的指 标为数据传输到达率与端到端时延。3.3.1仿真结果通过对不同的网络节点数量进行仿

23、真，得到如表 2 的仿真数据。其中第一行为网络中节 点的数量，第一列为协议类型。其他的数据为仿真得出的端到端时延，其单位为毫秒(ms)。表 2 仿真结果Tab. 2 Simulation result50100150200GPSR134.174475.138292.419309.089优化的 GPSR63.05664.63562.29662.7351901952002052102152203.3.2仿真分析表 2 是通过改变网络中节点的密度来定量比较不同路由协议的端到端时延的结果。从仿 真结果可以看到，在只改变节点数量的条件下，不管节点数量如何变化，采用了自适应信息 交换方式的 GPSR 协议

24、的端到端时延与 GPSR 相比，至少降低一半。随着网络规模的扩大， 优化的 GPSR 协议的时延不会有太大变化，并且会进一步降低时延，这是由于采用等待函数 能够在较短的时间内选择出下一跳。同时，优化的路由协议不会随着网络规模的变化而变化。 总之，采用自适应信息交换方式能够较大程度上提高路由协议的性能。4结论由于不同的区域不同的时间，网络中节点的数量差异较大，节点的邻居数量差别也较大。 针对这种情况，本文给出了一种自适应信息交换方式：结合 IEEE 802.11 无线局域网中分布 式协调功能 DCF 的优点；对车辆的历史运行轨迹数据进行学习，进而估计出邻居节点数量； 参考节点数量，采用自适应的方

25、法进行信息交换方式，挑选出最佳下一跳。最后，我们对提 出的算法采用 NS2 软件仿真。仿真数据显示，采用了自适应信息交换方式的路由协议在端 到端时延的性能指标上不会随着网络中节点数量的改变而发生较大改变，并且要大大优于基 本的路由协议。总之，自适应信息交换方式节省了信息交换所花费的时间，为节点准确的选 择下一跳以及最终路由路径的建立提高了实时性，降低了端到端时延，提高了路由协议的综 合性能。参考文献 (References)1 Yan Yu, Ramesh Govindan, Deborah Estrin. Geographical and Energy Aware Routing: a re

26、cursive data dissemination Protocol for wireless sensor networksR. USA: Technical University of California at Los Angeles,Report UCLACSDTR-01-0023,2001.2 Lochert C, Hartenstein H, Tian J, et al. A Routing Strategy for Vehicular Ad-Hoc Networks in CityEnvironmentsJ. Proc of Intelligent Vehicles Sympo

27、sium. 2003, 9(8): 156-161.3 Christian Lochert, Martin Mauve, Holger Fuler, Hannes Hartenstein. Geographic routing in city scenariosJ.ACM SIGMOBILE Mobile Computing and Communications Review, 2005, 9(1): 69-72.4 Brad Karp, H T Kung. GPSR:Greedy Perimeter Stateless Routing for Wireless NetworksJ. Proc

28、.Of the ACM Mobicom, 2000, 7(11): 243-254.5 Li-Der Chou, Jyun-Yan Yang, Ying-Cheng Hsieh, DerChyn Chang and Chi-Feng Tung. Intersection-BasedRouting ProtocolJ. VANETs: Wireless Personal Communications, 2011, 60(1):105-124.6 张亮，舒炎泰. IEEE802.11 无线局域网中分布式协调功能的改进J. 计算机应用，2005，06（11）： 7-11.7 Mattbew S Gast. 802.11 无线网络权威指南M，江苏：东南大学出版社，2007.8 Y Zheng, Y Chen, Q Li, X Xie, W Ma. Understanding transportation modes based on GPS data for Web applicationsJ. ACM Transactions on the Web, 2010, 4(1):136.