一种基于Ad Hoc的城市车联网广播算法

引言

近年来，作为物联网的一个热门应用领域,车联网已经在全世界范围内得到广泛关注。车载通信也成为一个热门的研究领域。美国专门划分了一个频段用于无线车载网络(VehicularAdHocNetwork，VANET)领域的研究。VANET是移动AdHoc网络的一种特殊形式，以配备了特殊电子装置的车辆为网络节点，通过无线局域网技术实现车辆间的通信。VANET的广泛应用对于城市交通的管理和改善有着重要的意义。

AdHoc网络中的移动节点相互传递信息主要靠数据广播。广播是从源节点发送消息到网络中其他节点的路由过程。传统的广播算法为了解决广播风暴的问题，提出了基于概率的算法、基于面积的算法和基于邻居信息的算法等。这些算法都能很好地解决报文的重复传送和竞争碰撞问题。但是在VANET中，车辆作为节点有着不同于传统AdHoc网络节点的一些特性，如计算能力强、存储能力强、高速移动和不会耗尽能量等特点，这就要求数据的快速处理和有效投递。同时，车载网络用于改善城市的交通状况，其广播的信息类型是不同的，如提醒用户路面的信息：车辆的速度和密度等。这些信息只对附近车辆有用，而远距离车辆则无需给予关注,所以数据的广播具有选择性。谢珊珊等人根据消息的类型提出了一种在高速公路场景下的VANET路由协议MTAODV，查询前方的道路信息和提醒后方车辆注意路况。但是在更为复杂的城市场景下，如岔路口和环形立交桥，道路信息复杂多样，方向性不再明显，所以单纯地根据车辆的正向反向可能会造成信息的广播覆盖不完全，导致一些车辆无法得知。周伯生口等人提出了一种基于竞争机制的广播协议，定义了转发优先权和等待时间，但是并未对各参数的性能影响进行分析说明。李元振等人提出了一种基于竞争转发的城市场景车载AdHoc网络路由算法，针对网络分割现象提出了“暂存转发机制”，假设每辆车都安装有导航系统和GPS定位系统，且每个导航系统中都存在一个电子地图，但是在实际驾驶中却并不能达到假设的标准。

基于此，在充分考虑现实环境的复杂性的情况下，本文提出了一种在城市场景下的基于节点相对距离与消息类型的广播算法(theBroadcastingAlgorithmBasedonRelativelyDistanceandMessageType,RDMT-BA)。该算法应用节点相对移动速度和消息类型的不同，限制转发的节点数，使信息高效广播，促使车辆及时作出反应，缓解交通压力。通过改变转发的参数，分析其对算法性能的影响。RDMT-BA算法计算简便，易于实现，无需周期广播Hello消息、获取全网信息,无需配备导航系统，增加额外设备。

1算法的有关参数确定

在城市场景下，车辆较为密集，若所有车辆均装有GPS，但相当一部分的车辆由于短距离行驶而没有开启GPS，这样则会对实际车辆的分布密度和广播转发估计造成较为明显的偏差。因此，本模型假设车辆装有全向天线，不使用GPS导航装置。所有车辆节点共享同一信道，MAC协议采用IEEE802.11。所有节点均属于无向集合，节点i发送广播报文,节点j接收。

定义1:节点之间的相对距离S，可以通过检测收到的信号强度计算发送和接收节点间的距离此为发送节点i信号强度,Pj为接收节点j信号强度。本模型所采用的全向天线发射频率为2400~2485MHz，增益为9dBi。则已知发射信号强度，接收节点信号强度为：

Pj=Pi+9(dBi)－自由空间损耗(1)

自由空间传播是指天线周围为无限大真空时的电波传播，是理想的传播条件。自由空间传输的损耗为：

[Lfs](dB)=32.44+20lgS(km)+20lgf(MHz)(2)

式中，Lfs是传输损耗，S为传输距离，频率的单位以MHz计算。

通过上述可得，节点的相对距离S为：

定义2：相对移动速度v，即判断节点是否接听广播的依据。公式为：

式中,&和S2是节点j先后两次从广播节点i收听到信号，根据定义1计算出的相对距离，相隔时间为很小)。分析可知,当v>0时,有三种情况:一是两车相向行驶并且距离越来越短;二是两车同向行驶且距离越来越短；三是无论正向还是反向，两车擦身而过，距离在缩短。因此，若v>0,则接收节点j可/58物联网技术2013年/第5期判断At时间内两车在靠近，或者已经很接近;同样，当v<0时,也有三种情况：一是两车相向行驶且距离越来越远；二是两车同向行驶且距离越来越远；三是无论正向还是反向，两车擦身而过，距离在拉远。因此，若v<0,则接收节点j可判断At时间内两车正在远离，或者已经远离。当v=0时，有两种情况：一种是两车同向行驶且速度一样;另一种是两车相错而过。这两种情况都可以归为At时间内两车在靠近。

定义3：转发阈值D,即判断接收节点是否转发广播的依据。假设所有节点呈圆形向外卜广播，且通信半径相同。现以源节点A为坐标原点，接收节点B离节点A的距离为d,如图1所示。

图1  转发阈值的计算模型

图1中,A、B的通信半径均为R,可以得到圆A和圆B的表达式如下：

进而得到，交点C的坐标为，则额外覆盖面积是圆B减去圆A、B的交集部分。假设源节点i的通信圆为A，接收节点j的通信圆为B，则：

可以得到额外覆盖面积EAC为：

由式(8)可见，额外覆盖面积EAC与圆心距d成正比例关系。额外覆盖率定义为：

若规定当节点的额外覆盖率EAR大于转发阈值D(i,j)时,才能转发广播报文。

由定义3可知，转发阈值D(i,j)即为节点可以广播报文的最小额外覆盖率，即：

D(i,j)=(EAR)m,n(10)

其中，(EAR)mm表示的是人为规定的最小额外覆盖率。综合考虑实际的情况和理论的推算，阈值大小一般在50%~90%之间。

定义4:等待时间T是一个变量，根据接收节点j距离源节点i的位置远近而不同。当接收节点决定转发广播时，会计算出一个等待时间。在该等待时间内，如果该节点重复收听到此消息，则认为该广播已被转发，放弃对其的转发；如果没有接听到，则转发该广播。

在考虑函数变化率对参数的影响下，等待时间T［7］可表示为：

式中，C为设定的最长等待时间，D为转发阈值。

由式(11)可知,D在［0,1］的变化范围内，三个函数在［0,1］内单调递增。若接收节点与源节点的在某一时刻下的距离s越远(s<R),则额外覆盖面积越大，转发阈值D越容易被满足，且T越小。同时，由于正弦函数在接近0时的变化率比正切函数和比例函数大，这就保证了在靠近源节点通信半径边缘的不同转发节点的等待时间差量，减少了竞争转发在信道中的冲突，提高了报文转发的投递率。

2RDMT-BA算法与网络模型

2.1算法的建立过程

RDMT-BA算法是根据节点的相对距离与消息类型来决定接收信息的节点和进行广播转发的节点消息类型根据需要得知的群体分为邻近型和远离型。邻近型即为邻近节点需知的消息，如车辆的速度和密度、是否转弯等，该类型尤其适合于大雾天气等能见度很低的情况；远离型即为远距离的节点所需的信息，如修路、堵车等，该类型可促使车辆更改路线,缓解交通。实现的具体步骤如下：

Step1:源节点i发现路况后，先广播Hello消息给通信范围内的邻居节点，邻居节点j接收到相关信息后，根据定义1计算出相对距离S1(i,)。

Step2:源节点在相隔圍之后，再次向外广播路况信息,并将消息类型放入邻居节点信息列表中。

Step3：邻居节点监听信息，判断是否接收过该消息。若有,则放弃；若没有，则转至Step4。

Step4:根据监听到的第二次消息，再根据定义1计算出相对距离S2(i,,),同时调出该广播的消息类型。

Step5:根据定义2计算出相对移动速度V。若消息类型为邻近型，则vN0的节点收听广播；若消息类型为远离型,则v<0的节点收听广播。

Step6:收听广播的邻居节点，同时根据S2是否大于转发阈值D(i,j)来判断是否进行转发。若小于D,则放弃转发；若大于等于D,则转至Step7。

Step7:计算等待时间T(i,j)。在T时间内,继续监听该广播。若重复收到，则认为该报文已经转发，放弃对其的转发;若没有,则进行转发。转发的步骤重复Step1至Step7。

2.2网络模型

假设城市街道为双行道，且车辆处于移动中。当路面发生车祸或者修路、堵车等现象时，移动的车辆在做出调头或者停车的动作前广播信息，并且该车的附近车辆继续行驶，不存在临时超车、调头等因素。城市场景道路的复杂性很高,如三岔口、立交桥、环岛等。本算法的网络模型采用典型的直路和十字路口，图2所示是其网络模型。

图2  网络模型

下面来讨论情景1,即直路的情形。当车辆在街道上行驶时，发现前方出现道路状况，则向外发送广播信息，其模型如图3所示。

图3  直路模型

图3中，车辆节点A1向外广播Hello消息和路况信息,相邻节点A,、A3、幼和B3都监听到该消息。现假设』2、A3和A,的速度均大于A1，所以A?、A3和B节点在靠近A1节点,而节点A,、幼在远离，计算出的相对移动速度v(A2,A1)>0，v(』3,A)>0,3(83,A)>0,v(&,&)<0,v(B2,A1)<0。因此，若&节点向外广播的消息为邻近型，则A?、A3和83节点收听广播；若为远离型，则A、收听广播。

当消息为邻近型时，节点』2、A3和83分别计算额外覆盖率EAR(A2,Aj)、EAR(A3,A)EAR(B3，A).现根据定义3假设得出：

EAR(&,A1)>EAR(&,Ai)>D2EAR(务Ai)(⑵

所以,』2、』3决定转发广播,83放弃。再根据定义4,计算等待时间T(A2,A1)和T(A3,Aj),且T(A2,A1)<T(A3,Aj)。所以,A,先转发广播,A3在等待时间内重复接听到了转发的广播，则放弃转发。同样车辆节点Bj的广播也如此，这样就减少了转发广播的节点数，保证了路况信息快速有效地向外广播，而不会引起冲突导致信息的丢失。其流程图如图4所示。

对于情景2，也就是岔路口的情形。如果车辆行驶在一个十字路口，发现前方出现路况，车辆将向外广播消息。其模型如图5所示。

在图5中，A1、A2、A4和A5驶向路口且向外广播，A3、A6、B1、B3、B4、B5监听到该广播。现假设A3的速度大于A2，A6的速度大于A5，所以A3、A6、B5在靠近A2、A5，而B1、B3、B4在远离A1、A4。若该信息为邻近型，则接近点A3、A6、B5收听；若消息为远离型，则B1、B3、B4接听。B2和B5由于已远离十字路口，所以不在接听范围内。接听广播的节点再根据转发阈值和等待时间决定转发的节点，流程图与直路模型一致。

由上述两种情景可以看出，广播邻近型消息可以保证接近源节点的所有节点都收听到，提醒用户注意当前路况；广播远离型消息可以使此段路况信息高效地向外传送，使远距离的用户也可提前得知并做出反应，缓解交通压力。

如果城市场景更加复杂，如环绕立交桥，当桥上发生堵车或施工等状况时,RDMT-BA算法能够根据不同的消息类型,运用不同的处理方式，告知附近的车辆减速慢行，或者警示各路口接近立交桥的车辆转向。城市场景越复杂，对于城市交通管理的改善就越明显。

3性能比较

在基于不同的场景、不同的节点数和不同移动速度的情况下，对RDMT-BA算法和洪泛广播算法进行了分析比较。可从覆盖率(EAR)、转发节省数(节点总数-转发节点数)和延迟等性能方面进行评估。

3.1直路场景

国家一级公路双向四车道宽为26m，在城市中车速一般为0~60km/h。假设在直路模型下，无线带宽为2Mb/s，环境为600m×50m，节点的无线通信半径均为100m，节点数由30增加到200，其中正反向车道的车辆均为总数的一半。针对不同的节点数，分别在速度0~20km/h、20~40km/h和40~60km/h的情况下，两种算法的性能比较如图6所示。

图6(a)中，随着节点数的增多，洪泛算法的覆盖率一直在90%~100%间波动而且越来越趋近100%，RDMT-BA算法在节点数少于70之前覆盖率大幅度增长，在节点数到达80之后，基本在90%和100%之间波动，其覆盖率与洪泛算法的覆盖率相接近。同时随着节点速度的增大，覆盖率略有下降且波动幅度加大，但是在总体趋势上性能相似，甚至在车速很低的情况下，覆盖率的性能要优于洪泛算法。图6(b)中，由于洪泛算法所有的节点均转发广播，所以转发节省数为零。而本算法随着节点数的增多，转发节省数也呈稳步增长，且随着速度的增大，转发节省数也随之增多。图6(c)中，随着节点数的增多，洪泛算法的延迟时间呈递增趋势，且远远高于RDMT-BA算法的延迟时间。而RDMT-BA算法的延迟时间却随着节点数的增加而降低，且速度越快，延迟越少。由此可见，在直路模型下本算法的性能要优于洪泛算法，而且节点数越多，算法的性能越好。

对于RDMT-BA算法，节点的转发阈值D和等待时间T是判断节点是否转发和影响算法性能优劣的重要参数。

针对不同的转发阈值D,分别在速度0~20km/h、20~40km/h和40~60km/h的情况下，RDMT-BA算法的性能比较如图7所示(假设节点数为120)。

图7(a)中，当转发阈值固定时，速度越大，覆盖率越差。当转发阈值增大时，覆盖率呈下降趋势，其中低速时覆盖率的波动最平稳，但是均保持在90%以上，基本满足实际场景中的覆盖要求。图7(b)中，当转发阈值固定时，速度越大，转发的节省数越多。当转发阈值增大时，速度越大，节省数的波动越大，但是总体上呈上升趋势，其中低速时转发节省数稳步上升。这就减少了转发的冲突和提高了消息的投递率。图7(c)中，当转发阈值固定时，速度越大，延迟的时间越少。当转发阈值增大时，速度越大，延迟的波动性越明显，但是从总体上呈下降趋势，其中低速时延迟稳步下降。这就保证了消息的快速传播。由此可见，低速的性能要优于高速，保持低速行驶可以保证信息广播的稳定，也可以保证车辆行驶的安全。

针对不同的速度(0~20km/h、20~40km/h和40~60km/h)，等待时间T的函数分别为正弦函数、比例函数和正切函数的情况下，RDMT-BA算法的性能比较如图8所示。

图8(a)中，随着速度的增大，覆盖率下降，且正弦函数、比例函数和正切函数相比，正切函数的波动性最明显，比例函数次之，正弦函数最稳定。虽然正弦函数的覆盖率比正切函数和比例函数小，但是在总体上保持在95%以上，满足实际场景中的覆盖条件。图8(b)中，当速度固定时，正弦函数的转发节省数最多，比例函数次之，正切函数最少。当速度增大时，三个函数都呈上升趋势，其中正弦函数平稳性最优。图8(c)中，当速度固定时，正弦函数的延迟时间最少，比例函数次之，正切函数最多。当速度增大时，三个函数都呈下降趋势，其中正弦函数波动性最小。由此可见，正弦函数的性能要优于比例函数和正切函数。

3.2岔路场景

一般在十字路口车辆的运动速度都比较慢，可以假设在十字路口模型下，无线带宽为2Mb/s，环境为350mX350m，节点的无线通信半径为50m，节点数由30增加到200,其中驶向路口的车辆和驶离路口的车辆均为总数的一半。针对不同的节点数，当车辆驶向路口的速度和驶离路口的速度分别为0~20km/h和18~36km/h的情况时，记为V1；当驶向路口的速度和驶离路口的速度分别为20~40km/h和36~54km/h的情况时，记为0两种算法的性能比较如图9所示。

图9(a)中，随着节点数的增大，洪泛算法的覆盖率一直在90%~100%之间稳步上升，RDMT-BA算法的覆盖率在节点数到达140之前呈明显的上升趋势，在140之后跟洪泛算法的覆盖率相接近，同时随着速度的提高，覆盖率略有下降,但在总体趋势上性能仍然良好，甚至在低速的情况下，RDMT-BA算法的覆盖率要优于洪泛算法。图9(b)中，由于洪泛算法所有的节点均转发广播，所以转发节省数为零。而本算法当节点数固定时，低速比高速转发的节省数稍小。但当节点数增加时，低速的上升趋势更平稳。图9(c)中，随着节点数的增多,洪泛算法的延迟时间呈递增趋势，且远远高于RDMT-BA算法的延迟时间。而本算法的延迟时间却随着节点数的增加而降低，低速比高速延迟稍长，但是并无明显差异。由此可见,在岔路模型下本算法的性能要优于洪泛算法，而且节点数越多,算法的性能越好。

针对不同的转发阈值D,分别在兀、兀两种情况下,RDMT-BA算法的性能比较如图10所示(假设节点数为120)。

图10(a)中，当转发阈值固定时，速度越大，覆盖率越差。当转发阈值增大时，覆盖率有明显的下降趋势，其中低速时覆盖率的波动较平稳，且均保持在80%以上，基本满足实际场景中的覆盖要求。图10(b)中，当转发阈值固定时，速度越大,转发的节省数越多。当转发阈值增大时，速度越大，转发节省数的波动越大，但是总体上呈上升趋势，其中低速时转发节省数上升的趋势更稳定。这就减少了信道中转发的竞争和冲突。图10(c)中，当转发阈值固定时，速度越大，延迟的时间越少。当转发阈值增大时，速度越大，延迟的波动性越明显，但是从总体上呈下降趋势，其中低速时延迟下降的趋势更平稳。这就减少了消息传播的滞后性。由此可见，岔路模型的结论与直路模型一致，低速的性能要优于高速，可以保证信道的平稳和车辆行驶的安全。

针对不同的速度(0~60km/h)的情况下，等待时间T的函数分别为正弦函数、比例函数和正切函数时，RDMT-BA算法的性能比较如图11所示(假设节点数为120)。

图11(a)中，随着速度的增大，覆盖率下降，且正弦函数、比例函数和正切函数相比，正切函数的波动性最明显，比例函数次之，正弦函数最稳定。其中正弦函数的覆盖率比正切函数和比例函数小，但是在总体上保持在84%以上，基本满足实际场景中的覆盖要求。图11(b)中，当速度固定时，正弦函数的转发节省数最多，比例函数次之，正切函数最少。当速度增大时，其中正弦函数上升的平稳性最优。图11(c)中，当速度固定时，正弦函数的延迟时间最小，比例函数次之，正切函数最大。当速度增大时，三个函数都呈下降趋势，其中正弦函数波动性最小。由此可见，岔路模型的结论与直路模型一致,正弦函数的性能要优于比例函数和正切函数。

根据上述一系列的分析比较可以看出，无论是直路模型还是岔路模型，均可得到如下结果：

洪泛算法因为每个节点都转发广播，所以覆盖率达到90%以上；RDMT-BA算法随着车辆数目的增多，覆盖率达到80%左右，基本可以满足车辆之间通信的要求。

由于RDMT-BA算法要求节点在达到一定的要求后才转发广播，所以当车辆数目增多，趋于密集时，转发节点覆盖范围内的节点越多，越多的节点无需转发，进而转发节省的节点数目就会增多。

洪泛算法的每个节点在接听到广播后，都会向外转发,所以广播的延迟较大，而RDMT-BA算法则随着节点数目的增多，延迟比洪泛算法的减少50%甚至更多。

当转发阈值D增大时，即在相同节点数目的条件下,满足转发条件的节点减少，所以转发节省数增加、覆盖率下降、延迟增加。

当等待时间T因为函数改变时，可以看出正切函数覆盖率高但波动性较大，而正弦函数转发节省数多和延迟时间少，且平稳性很好，所以综合性能上正弦函数要优于正切函数和比例函数。

综上所述，RDMT-BA算法在覆盖率、转发节省数和延迟三个性能上较之洪泛算法有着显著的改善。在城市复杂的环境下，能够在保证绝大多数车辆收听广播信息的前提下，将广播信息高效快速地向外发送，通过车、路、人的合一，真正意义上实现城市的智能交通。

4结语

针对城市场景下道路的复杂性，提出了一种基于节点相对距离与消息类型的广播算法。该算法应用节点的相对移动速度和消息类型决定接听广播的节点之后，再依据转发阈值和等待时间的判断决定对广播进行转发的节点。但是，考虑到实际场景的复杂性，该算法尚有不足。首先计算节点相对距离的公式可能会受到环境因素的影响而准确性降低，进而在求取相对速度时，即使在很短的时间和相同的环境下，也不能完全消除环境的影响，所以在下一步继续深入研究和实现论文方法的同时，会实际采用硬件电路进行模拟，将实际数据与仿真数据进行比较，根据实际情况对算法进行完善。其次算法的安全性不高，虽然通过判断是否重复收听广播可以减少重复收听的次数，及时将正确的道路信息转达给车主，但是无法完全防止恶意节点的消息。所以，拟定的下一步工作主要是在实际场景中改善算法的准确性、可靠性和安全性。

20211021_61715b9b12598__一种基于AdHoc的城市车联网广播算法