车联网中一种面向路侧单元的自组网路由协议

林晓辉

(1．广东交通职业技术学院，广州510650;2．华南理工大学土木与交通学院，广州510641)

车载自组网(Vehicular Ad hoc Networks，VANETs)是车联网(未来智能交通发展方向)的重要组成部分，它通过车车通信、车路通信，高效地实现事故预警、辅助驾驶、道路交通信息查询以及 Internet接入服务等多种应用［1-3］．车联网是智能交通的未来发展方向．借助于路侧单元并结合车辆上的车载单元所提供可靠的数据传输路线，可解决车联网中车载自组网连通性问题，而路侧单元的网络构建是其关键技术．路由协议作为VANETs研究的关键技术之一，国内外学者提出了很多VANETs路由方案，如基于拓扑结构的路由协议(AODV［4］、OLSR、DSR、TORA、DSDV 等)、基于位置信息的路由协议(GPSR、GPCR)、基于地图信息的路由协议(GSR、SAR)、基于交通信息的路由协议(A-STAR)、基于行驶路线信息的路由协议(VADD［5］、Geopps)和混合路由(GeoDTN+NAV)等．尽管如此，现有的路由协议仍面临诸多挑战，其中，网络频繁分割问题，导致VANETs连通的不稳定，极大限制了网络中数据发布的速度与准确性，成为VANETs投入实际应用中的最大的挑战［3］．借助路侧单元RSU(Road Site U-nit)并结合车辆上的车载单元OBU(On board Unit)所提供可靠的数据传输路线，可以解决VANETs连通性问题［3］，而RSU的网络构建是基于RSU车载自组网的关键技术．He等［6］提出一种分化可靠路由方案，有利于降低阻塞概率和保持较低的控制，同时提供区分服务的开销;Kim等［7］设计了一种基于街道的SARC路由协议，提供了有效的路径发现和隐私保护路由发现和数据转发阶段;Kitani等［8］提出基于消息摆渡技术，借助公交上路由设备，采集、保留和传播普通车辆间的交通信息;葛明珠等［9］提出基于静态节点辅助的路由方法，将数据包存储在交叉路口的静态节点中，直到最优路径是有效的，提高数据包的传输效率．尽管上述算法数据传输可靠，但其均存在一定的局限性，很难准确地建立空间模型，而且没有综合考虑车辆网络社会行为的规律性特征．鉴于此，本文提出一种面向RSU的自组网路由协议．

1 面向RSU的自组网路由协议

1．1 基本思路

RSU用作固定可靠的路由节点，独立地部署于道路两侧，用于大面积传感与通信(图1)．采用树形拓扑结构，路网分为若干交通控制子区，各子区设有交通控制中心，网络采用无线或有线方式与控制总中心相连，各子区内以交通控制子中心(Traffic Control Center，TCC)作为根节点，RSU作为路由子节点，新增的RSU加入网络时，根据信号强度，选择已入网的RSU节点作为父节点，通过本文自组网路由协议，构建RSU自组网络．车辆通信设备以广播模式向周边RSU节点请求应答，控制中心根据应答的RSU位置，确定车辆位置，借助RSU节点，实现相互车路通信和车车通信．

图1 路侧单元RSU部署分布Figure 1 The RSU deployment distribution

1．2 RSU节点网络结构和网络地址码

网络由一个TCC和若干个RSU节点组成，TCC个数必须为1，并作为网络树的根节点(图2)．新RSU节点加入网络后，网络都会为其分配一个64位的网络地址．TCC的网络地址均为全0，且固定不变，其他节点网络地址根据本节点在网络拓扑的位置和结构不同而不同．

RSU节点网络结构由2个参数决定:网络层数number(n)和各层占用网络地址的比特数BitsPer-Lever(bpl_1，bpl_2，…，bpl_n)，而且 8＜=n＜=64，bpl_1+bpl_2+… +bpl_n=64．n值根据路网情况的需要而定，当n=64时，每层的比特数为1，其检测距离最长，可应用于城市主干道或高速路上的车载数据传输．

图2 交通控制子区网络树形拓扑结构Figure 2 The network topological structure of traffic control sub area

设bn为前n层比特数的总和，即bn=bpl_1+bpl_2+bpl_n，则:

1)TCC网络地址为64位二进制，均为0，且固定不变．

2)可设定TCC的第1个子节点和第2个子节点的网络地址如图3所示，以此类推，可确定最后1个子节点的网络地址．

图3 TCC子节点网络地址Figure 3 The network address of the child nodes of TCC

3)若节点处于第n层，则其网络地址如图4A所示，其子节点的网络地址如图4B所示，其中XX…XXXXX为一个00…01到11…111的数，该值取决于该节点是其父节点的第几个子节点．

图4 处于第n层的节点及其子节点网络地址Figure 4 The network address of node and child node on the n layer

1．3 RSU 网络维护

1．3．1 RSU节点地址分配 TCC地址分配:TCC自动分配全0的网络地址．RSU节点地址分配:当RSU节点上电时，首先检查本节点是否保存有原网络地址信息，若没有保存，则进入RSU节点地址分配流程，否则进入RSU节点地址快速分配流程．

(1)RSU节点地址分配流程如图5所示，具体步骤如下:

①New RSU节点上电后，读取Flash中的网络配置数据，若Flash中没有网络配置数据，则广播消息Network_Init，向附近的RSU节点/TCC通知本节点进行网络初始化．由于New RSU节点未分配到地址，消息中的广播原地址码为全F，同时启动定时器T1和T2(T1＞T2)．

②RSU节点/TCC收到New RSU节点的Network_Init消息后，随机延迟一段时间，然后广播发送Network_Init_Ack消息通知New RSU节点，消息中的原地址为本节点的地址码，消息中带有 gtAddrStruct消息、本节点的地址码、节点的层数以及可分配的节点数．如RSU节点可加入的节点数为0，则RSU节点进入子节点检测状态流程．New RSU节点收到Network_Init_Ack消息后，检测该消息的信号强度RssiVal，并保存收集到的Network_Init_Ack消息，等待定时器T2超时．若定时器T2超时，且New RSU节点未收到任何 Network_Init_Ack消息，则New RSU节点需要启用定时器T3．等待定时器T3超时后，切换到其他频点发送Network_Init消息．

③同Step②．

④New RSU节点根据保存的各个Network_Init_Ack消息的信号强度RssiVal、原地址节点的层数以及可分配的节点数，选择最优的TCC/RSU节点作为父节点．然后发送Addr_Alloc_req消息给该节点，

图5 RSU节点地址分配流程Figure 5 The assignment process of routing node addresses of RSU

目的地址为父节点地址码，消息中带有本节点的MAC地址以及New RSU节点收到的响应次数．RSU节点/TCC收到Addr_Alloc_req消息后，检测本节点是否有可分配的子节点．若有，则跳到Step⑥;若没有，则跳到Step⑤．选择算法:

1)若同时出现RssiVal＞临界值和RssiVal＜临界值的情况，则优选RssiVal＜=临界值的RSU．

2)若只出现RssiVal＞临界值的情况，则以10为最小因子优选RssiVal较小的RSU．

3)对于RssiVal＜=临界值的，根据父节点的层数和该父节点可以继续加入的子节点个数进行优选．

⑤若Addr_Alloc_req消息中带的节点个数为1，则RSU节点/TCC可检查出父节点最多的子节点，并将其删除，同时发送Addr_alloc_Fail消息给New RSU节点;否则只需要发送Addr_alloc_Fail消息给NewRSU节点．Addr_alloc_Fail消息的类型为广播消息，消息中还有Addr_alloc_req消息带给New_RSU节点的MAC地址．New RSU节点收到 Addr_alloc_Fail后进入Step④．

⑥RSU节点/TCC收到Addr_Alloc_req消息后，检查New RSU节点是否已经在本RSU节点中存在．若存在，则跳到Step⑧;否则向TCC发送Addr_bind_req消息，请求将分配给New RSU节点的地址码和MAC地址进行绑定．

⑦TCC收到Addr_Bind_Req后，对New RSU节点的MAC地址和地址码进行绑定，并回复Addr_Bind_Resp消息．TCC检查New RSU节点是否可以被绑定．若可以，则绑定成功;否则绑定失败．

⑧RSU节点/TCC收到Addr_Bind_Resp后，发送Addr_Alloc_Complete消息给New RSU节点，消息中带有RSU节点重新分配地址的次数以及地址分配是否成功的标志，New RSU节点取消定时器T1，分配地址完成．若地址分配失败，则New RSU节点需要启用定时器T3，等待定时器T3超时后，再切换到其他频点发送 Network_Init消息．定时器超时处理:

1)当定时器T1超时，启用定时器T3．

2)当定时器T2超时，进入Step④．

3)当定时器T3超时，New RSU节点切换到其他频点，并跳到Step①．T3时间随着失败次数增加而增加．

(2)RSU节点地址快速分配流程如图6所示，具体步骤如下:

①New RSU节点读取Flash中的配置信息，发送Addr_Alloc_Quickly_Req消息给原来的父节点，消息的原地址为全F，目的地址为准备加入的父节点的地址码，消息中带有本节点编号、New RSU节点的原地址码和MAC地址．RSU节点收到Addr_Alloc_Quickly_Req后，检测是否可以接受New RSU节点的请求．若不接受，则跳到Step②，否则判断本New RSU节点的地址在本节点是否存在．若存在，则跳到Step⑤，否则跳到Step③．

②RSU节点发送Addr_Alloc_Quickly_Fail消息给New RSU节点，若通知地址加入失败，则需要进入RSU节点地址分配流程．

③RSU节点向TCC发送Addr_Bind_Req消息，请求New RSU节点的MAC地址和地址码进行绑定．

④TCC收到Addr_Bind_Req消息后，向其回复Addr_Bind_Resp消息．

⑤RSU节点收到Addr_Bind_Resp消息后，向New RSU节点发送Addr_Alloc_Complete消息，消息中带有RSU节点重新分配地址的次数，接着通知New RSU节点分配地址完成．New RSU节点收到Addr_Alloc_Complete消息后，检测收到该消息的信号强度，若信号强度值大于预设阈值，则重新执行地址分配流程;否则表明快速地址分配成功．

图6 RSU节点快速分配流程Figure 6 The fast assignment process of routing node addresses of RSU

1．3．2 RSU节点切换 RSU_Router地址重新分配流程如图7所示，具体步骤如下:

(1)RSU节点入网成功后，若半个小时内未收到来自其父节点的消息，则向其父节点发送Network_HandShake消息．

(2)其父节点收到Network_HandShake消息后，回复Network_HandShake_Ack消息．RSU节点收到该消息后，不作处理．若RSU节点未收到Network_HandShake_Ack消息，则RSU节点重复发Network_HandShake消息．若重复3次消息，RSU节点均未收到父节点的Network_HandShake_Ack消息，则进入切换流程．

(3)执行RSU地址快速分配流程，若RSU地址快速分配成功，则RSU用原来的网络地址，此时不需要切换．若RSU快速上电失败(可能是与其父节点通讯失败，或检测到父节点的信号强度过弱)，则跳到Step(4)．

(4)重新执行地址分配流程，若此时有信号更强的RSU可以加入，则切换到新的RSU上，作为该RSU的子节点．

图7 Router地址重新分配流程Figure 7 The re-assignment process of router address

1．3．3 RSU 节点删除

(1)RSU节点子节点状态检测流程如图8所示，具体步骤如下:

①RSU_0发送Network_Status_Test消息给其子节点同时启动定时器T1．

②若在定时器T1超时前，RSU_0收到其子节点发出的Network_Status_Test_Ack消息，则RSU_0停止定时器T1．

③同Step①．

图8 RSU节点子节点状态检测流程Figure 8 The state detection process of child nodes of RSU routing node

④当RSU_0发送Network_Status_Test消息给RSU_2时，等定时器T1超时后，若RSU_2未响应，则RSU需要重新启动定时器T1，并再次发送Network_Status_Test消息给RSU_2．若RSU_2连续3次未响应，则RSU_0将RSU_2在本节点删除并跳到Step⑤;否则停止定时器T1，并检查其他节点．

⑤RSU_0发送Cancle_Addr_Req消息给TCC，通知TCC删除RSU_2及其子孙节点地址．

⑥TCC对RSU_0回复Cancle_Addr_Resp消息，节点删除完成，RSU_0继续检测其他子节点(若多次检查不到RSU_2，说明RSU_2和RSU_0已经无法通讯，此时不需要再通知RSU_2)．

(2)RSU节点删除子节点流程如图9所示，具体步骤如下:

①进行删除节点操作时，OMS向TCC发送Del_Node消息，消息中带有需要删除的节点MAC地址．

②TCC根据MAC地址找到需要删除的节点的网络地址，计算出他的父节点网络地址．TCC向需要删除的节点的父节点发送Del_Child_Node消息，消息中带有需要删除的节点MAC地址．

③Father_RSU节点发送NetWork_Invailid消息后，RSU节点通知删除该节点，同时将RSU节点中的信息在本节点中删除．

④RSU节点收到NetWork_Invailid消息后，检测本节点是否有子节点．若有，则发送NetWork_Invailid消息广播通知子节点，并复位网络;若没有，则只需复位网络．

⑤同Step②．

⑥Father_RSU节点发送Cancle_Addr_Req消息，通知TCC删除RSU节点及其后代子节点的地址信息．

⑦TCC对OMS回复Del_Node_OK消息，通知节点删除成功．

图9 RSU节点子节点删除流程Figure 9 The deleted process of child nodes of RSU routing node

1．3．4 信号强度检测 网络中各个RSU节点可以对收到消息进行信号强度的检测，信号强度用RssiVal表示，依据RSU路由设备的DB值公式，可计算RssiVal．信号强度的作用:

(1)快速地址分配时，若父节点向子节点发送Addr_Alloc_Complete消息，子节点会对该消息进行信号值的检测．若RssiVal＞预设阈值，则子节点认为快速地址分配失败．

(2)地址分配时，若有多个父节点向RSU节点应答，则由RSU节点根据信号强度去选择其父节点．

2 仿真实验分析

采用NS2作为仿真平台，仿真区域为4 000 m×3 000 m，每条道路随机设定若干节点，各节点速度约7～14 m/s，信号容量:2mb/s．分别采用本文路由协议、VADD［5］和 AODV［4］等3 种不同路由协议进行数据传输，同时随机选择数据包产生节点和目标节点，最后比较3种不同路由协议的数据传输延时、传输率、路由负载和报文交付率．

结果表明:在数据传输延时方面，如图10所示，AODV的数据传输延时最低，因为该方法没有区分车辆节点和静态节点，数据包在节点处理时间减少，但这种方法数据包丢失较严重．VADD和本文路由协议随着节点数量增加，延时有所降低，当节点数＜50个时，VADD传输延时明显高于本文路由协议;在数据传输率方面，如图11所示，本文路由协议传输率比VADD高约11%，数据包的传送率随之节点的增加而提升，但对于AODV方法而言，当节点数目＞=250时，节点间的干扰和碰撞急剧增加，降低了数据包的传送率，本文算法的传输率明显优于AODV方法;在归一化路由负载方面，如图12所示，3种协议的路由负载随着车流密度的增加而增加，本文路由协议最高，VADD和AODV次之，因为随着车流密度增多，产生大量的路由更新和控制分组数据，路由节点负荷会增加，尤其是本文路由协议，借助RSU进行通讯，RSU会周期性向周边广播网络地址，增量了控制分组数据，因而路由负载增加明显;在报文交付率方面，如图13所示，3种协议的报文交付率随着车辆数量的增加而增加，当车辆较少时，行车速度较快，网络切换频繁，报文交付率较低，当车辆较多时，行车速度降低，报文交付率较高，总体上，本文路由协议的报文交付率均优于其他2种方法．

图10 数据传输平均延时Figure 10 The average delay of data transmission

图11 数据传输率Figure 11 The data rates

图12 归一化路由负载变化情况Figure 12 The change of normalized routing load

图13 不同车流密度下的报文交付率Figure 13 The delivery rate under the differentmessage traffic density

3 结束语

借助RSU自组网络，实现车载自组网是最为可靠的，避免网络频繁分割问题，有利于数据传输的稳定性和效率，很大程度改善了车载自组网的信息发布与数据聚合．但是在实际应用前应当考虑的问题有:(1)RSU的布设密度优化问题;(2)一旦发生重大灾难，RSU必然遭到损坏，有无其他辅助的手段，来保证网络的正常使用．我们将围绕这2个问题继续开展研究．

［1］刘永广，张剑，陈瑞昭，等．一种基于网络编码的ad hoc网络多路径源选路由算法［J］．华南师范大学学报:自然科学版，2010(3):42-46．Liu Y G，Zhang J，Chen R Z，et al．A multi-path source routing algorithm for ad hoc networks based on network coding［J］．Journal of South China Normal University:Natural Science Edition，2010(3):42-46．

［2］刘峥，向勇，孙卫真．车载自组网单播路由协议对比分析［J］．计算机工程与设计，2011，32(11):3622-3628．Liu Z，Xiang Y，Sun W Z．Analysis and comparison of unicast routing protocols in VANET ［J］．Computer Engineering and Design，2011，32(11):3622-3628．

［3］徐会彬，夏超．VANETs路由综述［J］．计算机应用研究，2012，29(1):1-6．Xu H B，Xia C．Survey on routing in vehicular ad hoc networks ［J］． Application Research of Computers，2012，29(1):1-6．

［4］IETF RFC 3561，Ad hoc on-demand distance vector(AODV)routing［S］．2003．

［5］Zhao J，Cao G．VADD:Vehicle-assisted data delivery in vehicular Ad Hoc networks［C］∥Proceedings of the 25th IEEE international conference on computer communications．New York:IEEE Communications Society，2006，57(3):1-12．

［6］He R，Rutagemwa H，Shen X．Differentiated reliable routing in hybrid vehicular ad-hoc networks［C］∥Proceeding of the IEEE international conference on communications(ICC)．New York:IEEE Communications Society，2008:2353-2358．

［7］Kim H，Paik J，Lee B，etal．Sarc:A street-based anonymous vehicular ad hoc routing protocol for city environment［C］∥Proceedings of the 2008 IEEE/IFIP international conference on embedded and ubiquitous computing．Washington，DC，USA，2008:324-329．

［8］Kitani T，Shinkawa T，Shibata N，et al．Efficient vanetbased traffic information sharing using buses on regular routes［C］∥Proceeding of the vehicular technology conference．New York:IEEE Communications Society，2008:3031-3036．

［9］葛明珠，徐利亚，雷淑君．车载网中一种利用静态节点辅助的路由方法［J］．信息安全与技术，2012，30(8):65-68．Ge M Z，Xu L Y，Lei S J．A static-nade assisted routing in VANET［J］．Information Security and Technology，2012，30(8):65-68．