一种基于车载网的树形多播路由协议

庞国彬,谭 龙,李瀚博,秦琦冰

(黑龙江大学 计算机科学技术学院，哈尔滨 150080)



一种基于车载网的树形多播路由协议

庞国彬,谭 龙*,李瀚博,秦琦冰

(黑龙江大学 计算机科学技术学院，哈尔滨 150080)

车载网中车辆的高速移动导致链路的生命期短，为了提高数据包的投递率，设计了一种基于分簇和多播树的地理多播路由协议。该协议将整个车载网中的车辆进行分簇，以多个车辆组成的簇为数据包中转站，簇内车辆协同转发一个数据包，数据包再由一个簇转发到另一个簇，最后到达目的区域。由于簇的稳定性，这个数据包投递成功的概率将显著增加。通过仿真实验与现有协议进行比较，验证了该协议具有更高的数据包投递率。

车载网；地理多播；分簇；多播树

车载网(vehicular ad-hoc networks，VANETs)被认为是很有发展前景的一项新技术，特别是在交通安全、车辆调度和商业应用上[1]。作为智能交通系统(Intelligent Transportation Systems，ITS)的重要组成部分，车载网不仅用来向司机提供潜在的交通拥堵信息以增加出行的便利性，还用来向后边的车辆传播紧急的信息以避免连环相撞事故的发生。为了实现这个前景，美国联邦通信委员会(Federal Communications Commission，FCC)为专用短程通信技术(dedicated short range communications，DSRC)分配了75 MHz的无线频段。并且，IEEE正在制定车辆间通信的标准[2]。车载网中的通信分为汽车到汽车 (vehicle-to-vehicle，V2V)，或者称为汽车之间(inter-vehicle communication，IVC)，以及汽车与基础设施之间(vehicle-to-infrastructure，V2I)[3]。由于越来越多的车辆具备了车与车之间的通信能力，大规模的车载网将在不久的将来成为可能。

虽然以上这些应用可以通过现有的许多无线设施(例如3 G或者4 G)来实现，但它们的花费较高，并且当有自然灾害发生时，一旦基础设施被摧毁，它们将不可用。因此，车载网的存在是有价值的，对车载网的研究是必要的[4]。

当有交通事故发生时，事故地点所在的路段可能发生拥堵，交通调度中心有必要向事故地点周围的车辆发送事故信息以及可能即将到来的拥堵警告。这就牵涉到一个节点向特定区域内的多个目的节点发送信息，也就是所谓的地理多播[5]。

车载网的很多路由协议是从移动自组网络(mobile ad hoc networks，MANETs)的路由协议演变过来的。文献[6]提出的AODV协议是传统的基于拓扑的MANET路由协议，考虑到有限的带宽和拓扑的频繁变化，该协议采用反应式的路由策略，当有数据需要发送时才启动路由发现过程。文献[7]提出的AODV-PNT协议是在AODV协议的基础上做了改进而应用于车载网，主要的改进有两点：①路由判据的改进并计算路由的总权值;②预测节点将来的路由总权值并计算出一个稳定阈值以选择适合的中继节点。由于车辆普遍都配备有GPS，这意味着车辆可以获取自己的位置信息，将位置信息融入路由策略，将极大地方便数据的转发。文献[8]提出的GPSR协议就是通过目的节点和路由节点的位置比较来做出转发决定，该协议只使用当前节点的邻居节点的位置信息就可以实现数据的贪心转发，数据转发前不需要建立从源节点到目的节点的完整的路径，所需的信息少，因此可以称为无状态的。文献[9]对GPSR进行了修改，通过挖掘相对运动信息来改进转发决策。文献[10]提出了一种分簇算法，它考虑到了车辆的移动速度快但移动受道路限制的情况，极大地改善了簇的稳定性。文献[11]提出了一种地理多播路由策略，通过建立多播树而使数据可靠地传输。

基于拓扑的路由虽然增加了反应式，但控制开销仍然大。基于位置的路由，在采用贪心策略的情况下容易出现局部最优而不是全局最优的情况。通过建立多播树来实现地理多播也存在控制开销大的问题。

本文在前人的基础上提出了一种基于分簇和多播树的地理多播路由协议。该协议在对网络进行分簇的情况下首先建立邻居簇，再以簇为单位构建整棵多播树，使得数据包可沿着多播树转发到目的区域，并且控制开销相对较小。

1 树形多播路由协议

在车载网中，车辆的高速移动，导致链路的生命期短。如果以单个车辆做为数据的中转站，数据包是否能够投递成功将令人担忧。换一种思路，如果以多个车辆组成的簇为中转站，簇内车辆协同转发一个数据包，数据包再由一个簇转发到另一个簇，最后到达目的车辆。由于簇的稳定性，这个数据包投递成功的概率将显著增加。基于以上的想法，笔者设计了下面的路由协议。

1.1 网络模型

本文涉及的车载网由多个移动车辆作为节点构成，每一辆车配备有GPS定位及电子地图，网络模型可以用图G(V，E)表示，图中的节点是车辆，如果两个节点u和v之间的距离小于或等于直接通信距离，那么两个节点之间就有一条边(u，v)。

节点的邻居节点指的是该节点一跳范围内的所有节点。邻居节点之间定期交换信息，建立邻居信息表，交换的信息包括节点标识VID，节点的位置，节点所在的簇的标识CID和节点的权值W(也就是节点成为簇头的适合性)。

一个簇指的是以簇头为中心，簇头一跳范围内的所有节点，簇头是簇内W值最大的节点。簇的组建过程如下：一个节点新加入网络时，通过与邻居节点交换信息，这个节点会得到所有邻居节点的W值，同时自己也会计算出一个W值。如果自己的W值比其他所有W值都大，节点就会选择自己为簇头。如果存在某个W值比自己和其他的都大，节点就会加入这个W 值对应节点为簇头的簇。同时，在簇的移动过程中，如果两个簇头节点之间的最小距离ICmin小于直接通信距离，其中W值较小的簇头就会放弃成为簇头节点，也就是说两个簇会进行合并。如果簇头离开了自己所在的簇，剩下的节点会重新确定一个簇头。新选出的簇头原先就是簇内成员的话，CID不需要改变。但新选出的簇头如若不是原簇内成员，CID就需要更改。簇的边缘节点很不稳定，一个时刻可能有节点离开这个簇，也有可能有新的节点加入这个簇，但整个簇作为数据的中转站具有较好的稳定性。本文的网络模型见图1。

图1 网络模型图Fig.1 Network model graph

1.2 邻居簇的建立

邻居簇的概念与邻居节点的概念类似，一个簇的邻居簇指的是能与这个簇直接通信的所有簇。如图1所示，假如A和B、C、S都可以直接通信，则B、C、S就是A的邻居簇。

为了建立邻居簇表，簇头广播跳数限制为2的邻居簇请求NCREQ(neighbor clusters request)信息。簇内节点在收到这个信息后，继续进行广播。簇内的边缘节点在收到簇头的广播后，能将这个信息广播到离簇最远的地方。广播得越远就越有可能获得更多的邻居簇，这对路由的建立和数据的转发都是有好处的。如果某个邻居簇的簇头收到了这个NCREQ，它会立即发送一个邻居簇应答NCREP(neighbor clusters reply)，并将发送NCREQ簇的CID和簇头位置加入自己的邻居簇表。同时，这个簇头会在簇内广播新获得的邻居簇，目的是为了使整个簇的邻居簇表同步。如果不是簇头收到NCREQ，而是非簇头节点收到NCREQ，收到NCREQ的节点会立即发送一个NCREP，并单播一个信息给簇头节点，告诉簇头自己收到了NCREQ。簇头在收到这个消息以后所做的处理与自己收到NCREQ的过程类似，只是不再发送NCREP，因为已经有簇内节点进行了应答。

节点在收到NCREP以后，会将这个NCREP发送给簇头。簇头发送的NCREQ得到了回应，簇头就把发送NCREP簇的CID和簇头位置加入自己的邻居簇表。同时，这个簇头也在簇内广播新获得的邻居簇，使整个簇的邻居簇表同步。

经过上述过程，一个簇与它的邻居簇建立了联系，它的邻居簇表增加了一项。当然，在这个过程中如果这个簇有多个邻居簇，那它将与所有的邻居簇取得联系，使自己的邻居簇表条目增加若干。而且，这个过程在簇与簇之间是周期进行的，以保证各自的邻居表都是最新的。

1.3 多播树的建立

地理多播的方式有两种：①基于洪泛的方式;②基于多播树的方式。洪泛的方式通信的数据量大，多播树的方式由于节点高速的移动性，使树的构建和维护较困难。由于本文对节点进行了分簇，并建立了邻居簇表，这使多播树的构建和维护变得简单。因此，采用基于多播树的方式进行地理多播。

当源节点需要向一个确定地理区域内的所有节点多播一个消息时，这个区域为多播区域MR(multicast region)，这个区域内的所有节点构成一个多播组。多播区域可被指定为圆形或多边形，这里指定为圆形。源节点向多播区域发送消息的时候，还会指定一个转发区域FZ(forwarding zone)。转发区域包含了源节点和多播区域，以及参与数据转发的中间节点。只有位于转发区域内的节点收到源节点发来的消息才会转发，而位于转发区域外的节点收到源节点发来的消息将会把这个消息丢弃。转发区域也可指定为多种形状，这里指定为长方形，即指定长方形的4个顶点坐标。多播区域和转发区域见图2。

图2 树形多播路由示意图Fig.2 Sketch map of the tree multicast routing protocol graph

当源节点需要向一个多播区域发送数据时，路由发现过程便会启动。源节点向自己所在簇的簇头发送一个多播区域路由请求MRREQ(multicast region request)信息，这个信息包含了源节点的节点标识VID、当前节点VID(对于源节点而言，当前节点VID和源节点VID是一样的。)、下一跳节点VID、源节点所在簇的标识CID、当前节点所在簇的CID、下一簇的CID(此时为NULL)、多播树路由序列号SS、多播区域的圆心和半径、转发区域的4个顶点坐标。簇头节点在收到这个MRREQ以后，修改当前节点VID，准备将它发送给自己所有的邻居簇。簇头节点从自己的簇内节点中选择几个节点，有多少个邻居簇就选择几个节点，每一个节点分别是到达对应邻居簇最近的节点。簇头将MRREQ进行复制，并把对应邻居簇的CID填入为NULL的下一簇的CID，再发送给刚选出的节点。节点一旦收到MRREQ，就会把它转发到对应的邻居簇。邻居簇内的节点在收到MRREQ后，先判断自己是否处于转发区域内，如果不是则丢弃该MRREQ，如果是则将它转发给自己所在簇的簇头节点。接下来，簇头节点在收到这个MRREQ后会重复上一个簇的簇头所做的工作，从而使MRREQ以簇间洪泛的方式向前转发，直到到达多播区域为止。多播区域内的某个节点在收到一个MRREQ后会立即发送一个多播区域路由应答MRREP(multicast region reply)信息，MRREP会沿着MRREQ来时经过的簇逆向到达源节点。MRREP经过的簇的簇头在簇内广播路由序列号SS，也就是使簇内的所有节点都加入这棵多播树。同时，MRREQ会在多播区域内继续洪泛，与在转发区域内不同的是收到MRREQ的节点会立刻进行应答，应答的目的节点不再是源节点而是发送MRREQ的上一跳节点。如果一个簇第二次收到相同的MRREQ，将不予理睬。这样，在转发区域和多播区域内就形成了一棵多播树，见图2红色线条。

1.4 数据的转发过程

源节点在收到MRREQ后，认为整棵多播树已经建好，就开始发送数据。数据将沿着整棵多播树传播，具体的过程如下：源节点把数据包发送给自己所在簇的簇头，簇头收到数据包以后从簇内成员中选择一个离多播树的下一个簇最近的节点，把数据包转发给它。这个节点收到数据包以后，将它发送到多播树的下一个簇。下一个簇的节点在收到数据以后，再把它发送给自己所在簇的簇头。经过这样的循环往复，数据包会到达多播区域。数据包在多播区域内的传播与在转发区域内的传播大体类似，只有3点不同：①多播区域内的簇会将数据包缓存一段时间再转发，这是为了避免先收到数据包而后收到MRREQ的情况，也是为了避免收到数据包时多播树还没建完;②每个簇收到几个MRREP，就会向几个簇发送数据包，这对应树分枝的情况;③簇头会在簇内广播收到的数据包，使簇内每个成员都可收到。通过上述步骤，数据先转发到多播区域，再转发到区域内的每个节点，整个多播任务得以完成。

根据以上描述，车载网中节点v运行下面的算法：

树形多播路由算法：Tree-Multicast-Routing

1 call Clustering //调用分簇算法

2 if(v is cluster head)

3 call Neighbor-Clusters-Build

4 if(v wants to send multicast message)

5 call Multicast-Tree-Build

6 call Data-Transfer

分簇算法：Clustering

1 compute a W

2 exchange W with neighbors

3 if(v is not cluster head)

4 if(W of v is the largest )

5 resign(u)//请求原来的簇头u放弃簇头地位

6 elect(v)//选自己为簇头

7 else join(u)//节点v加入簇头为u的簇

8 else if(distance to another cluster head<=ICmin and W of v is the largest )

9 resign(u)

邻居表的建立算法：Neighbor-Clusters-Build

1 broadcast NCREQ

2 if(receive a NCREP)

3 add CID of sender of NCREP and its cluster head position into neighbor-clusters-table

4 else if(receive a NCREQ)

5 add CID of sender of NCREQ and its cluster head position into neighbor-clusters-table

6 send a NCREP

多播树的建立算法：Multicast-Tree-Build

1 if(v is source node)

2 send MRREQ to cluster head

3 if(receive a MRREP)

4 return ok

5 if(v is a cluster head and within FZ)

6 send the MRREQ to nodes which are the nearest to its neighbor clusters

7 if(v is a ordinary node and within FZ)

8 if(receive a MRREQ from its cluster head)

9 transfer MRREQ to neighbor cluster

10 else transfer MRREQ to its cluster head

11 if(v is a ordinary node and within MR)

12 if(receive a MRREQ from the cluster within FZ)

13 send a MRREP to the source

14 else send a MRREP to the node from which receive the MRREQ

15 if(receive a MRREP)

16 transfer MRREP to the last hop of MRREQ

数据转发算法：Data-Transfer

1 if(v is source node)

2 send data packet to cluster head

3 if(v is a cluster head)

4 send the data packet to the node which is the nearest to the next cluster

5 if(v is within MR)

6 broadcast the data packet to its member

5 if(v is a ordinary node)

6 transfer the data packet to the next cluster

2 仿真实验与分析

本文在带有STRAW模块的Jist/SWANS上进行仿真，Jist/SWANS和ns-2一样也是专门用于移动自组网络的仿真，并且采用Java来实现。在某些方面增强了仿真设置，把路由协议做成一个新的路由模块。同时，为了使Jist/SWANS/STRAW能满足仿真要求，同时对它做了很多修改。

2.1 仿真设置

STRAW默认使用真实的道路地图，公路的长度为10 km，每个方向有3个车道，车辆允许的最大速度为120 km/h，如果车辆前方的车流速度慢，车辆会改变车道。在仿真开始之前，把n个车辆按照一定的间隔放置到公路上。在跟车模型下，所有的车辆都试图以最大的速度行驶。仿真参数的设置见表1，其中括号内的是默认值，一次只改变一个值，而其他的保持默认值。

表1 仿真参数

Table 1 Simulation parameters

参数值车辆密度/(辆·km-1)10,45,(272),545通信范围/m100,150,(200),250多播区域半径/km0.5,(1.5),2.5,3.5

2.2 仿真结果与分析

此部分主要呈现改变车流密度和多播区域大小后的实验结果，主要的评估标准是时延和数据包投递率，所有的实验数据都取的是15次仿真结果的平均值。

2.2.1 不同车流密度

实验结果表明，路由协议在所有的场景下的数据包投递率几乎为100%，只有在车辆密度极其低的情况下(低于10辆车/km)，数据包有时到不了多播区域，见图3。在此情况下，车辆间的平均距离大于100 m，这意味着一旦MRREQ和MRREP信息丢失，一部分多播树就建立不起来。但这种情况不是只有在路由协议里才会出现，其他所有的路由协议在如此低的车辆密度中都会出现这个问题。而且由于信号衰减的存在，短距离的多跳比长距离的一跳要好。

数据包传输的时延因场景而不同，但都会随着车辆密度的增大而出现不同程度的增大。车辆密度大，在簇的形成过程和邻居表的建立过程中，MAC层数据包的碰撞概率会增加，退避时间会增大，最后表现出来就是传输时延的增大。

2.2.2 不同多播区域大小

传输时延会随着多播区域的增大而增大，原因是更大的区域意味着需要更多的跳数，见图4。但值得庆幸的是多播区域的半径大到3.5 km，传输时延≤600 ms，而且数据包投递率也几乎是100%。

图3 基于车辆密度的时延对比图Fig.3 Time dalay comparison diagram based on vehicle density

图4 基于不同多播区域大小的时延对比图Fig.4 Time delay comparison diagram based on different multicast areas

4 结 论

本文提出了一种基于分簇和多播树的地理多播路由协议，主要是利用簇的稳定性来实现数据的可靠转发。虽然分簇和建树需要花费一定的时间，但为后续数据包的转发减少了开销。仿真实验表明该协议具有更高的数据包投递率和较低的时延。

如何实现车辆密度较低时数据包的可靠转发和在更真实的条件下验证协议有待研究。

[1] Vahdat-Nejad H,Ramazani A,Mohammadi T,et al.A survey on context-aware vehicular network applications[J].Vehicular Communications,2016,3:43-57.

[2] Zhao J,Cao G.VADD: Vehicle-Assisted Data Delivery in Vehicular Ad Hoc Networks[C]// INFOCOM 2006.25th IEEE International Conference on Computer Communications.Proceedings.IEEE,2010:1-12.

[3] 沈虎,王晓东,周兴铭,等.一种基于链路感知的VANET路由协议[J].软件学报,2011(22):157-164.

[4] 陈贵海,龚海刚,王晓敏,等.基于分布式实时信息的车载网络路由协议[J].软件学报,2011,22(3):466-480.

[5] Ko Y B,Vaidya N F.Geocasting in mobile ad hoc networks: location-based multicast algorithms[C]// IEEE Workshop on Mobile Computer Systems and Applications.IEEE Computer Society,1999:101.

[6] Perkins C,Belding-Royer E,Das S.Ad hoc On-Demand Distance Vector (AODV)Routing[M].RFC Editor,2000.

[7] Shen X,Wu Y,Xu Z,et al.AODV-PNT: An improved version of AODV routing protocol with predicting node trend in VANET[C]// Advanced Infocomm Technology (ICAIT),2014 IEEE 7th International Conference on.IEEE,2015:91-97.

[8] Karp B,Kung H T.GPSR: greedy perimeter stateless routing for wireless networks[C]// International Conference on Mobile Computing and NETWORKING.ACM,2005:243-254.

[9] Granelli F,Boato G,Kliazovich D,et al.Enhanced GPSR Routing in Multi-Hop Vehicular Communications through Movement Awareness[J].IEEE Communications Letters,2007,11(10):781-783.

[10] Blum J,Eskandarian A,Hoffman L.Mobility management in IVC networks[C]// Intelligent Vehicles Symposium,2003.Proceedings.IEEE.IEEE,2003:150-155.

[11] Kihl M,Sichitiu M,Ekeroth T,et al.Reliable Geographical Multicast Routing in Vehicular Ad-Hoc Networks[C]// International Conference on Wired/wireless Internet Communications.2007:315-325.

A tree multicast routing protocol in VANET

PANG Guo-Bin,TAN Long*,LI Han-Bo,QIN Qi-Bing

(CollegeofComputerScienceandTechnology,HeilongjiangUniversity,Harbin150080)

The high speed of mobile vehicles in vehicular ad-hoc networks leads to a short life span link between two vehicles.In order to improve the packet delivery rate,a geocast routing protocol is proposed based on cluster and tree.This protocol divides vehicles in vehicular ad-hoc networks into clusters.A cluster which consists of several vehicles becomes a data packet transfer station.Vehicles in a cluster coordinate with each other to forward a packet.Then packets are forwarded from one cluster to another cluster and finally reach the destination region.Due to the stability of the cluster,the packet delivery rate will be increased significantly.Compared with existing agreements now through simulation experiment,this protocol shows a higher packet delivery ratio.

VANET (vehicular ad-hoc network); geocast; cluster; multicast tree

10.13524/j.2095-008x.2016.04.061

2016-08-01

国家自然科学基金面上项目(81273649);黑龙江省自然科学基金面上项目(F201434);黑龙江大学研究生创新科研项目重点项目(YJSCX2016-018HLJU)

庞国彬(1989-)，男，四川泸州人，硕士研究生，研究方向：车载网,E-mail:767035979@qq.com；*通讯作者：谭 龙(1971-)，男，黑龙江哈尔滨人，副教授，硕士研究生导师，研究方向：传感器网络、数据挖掘，E-mail:tanlong@hlju.edu.cn。

TN929.5

A

2095-008X(2016)04-0075-07