车辆自组织网络中基于路段长度的交叉口路由方法

摘要

本发明公开一种车辆自组织网络中基于路段长度的交叉口路由方法，克服现有技术中不能保证转发路径连通以及没有考虑路段长度小于无线信号通信半径导致路由跳数增加的问题。本发明的具体思路是，首先交叉口节点计算相邻路段的连通度，然后根据相邻路段的连通度，将数据包转发给距离目的节点最近的交叉口节点或者邻居节点，最后重复上述过程直到将数据包转发给目的节点。本发明根据路段的长度利用不同的方法计算相邻路段的连通度，优先选择连通的且距离目的节点较近的交叉口节点，可有效的避免将数据包转发到易于中断的路段上，减少了网络延迟，提高了数据包的投递率。

说明书

技术领域

本发明属于通信技术领域，更进一步涉及一种车辆自组织网络(VANETs)中基于 路段长度的交叉口路由方法。本发明可用于城市场景的路由决策，根据路段的长度利 用不同的方法计算交叉口相邻路段的连通度，优先选择连通的且距离目的节点较近的 交叉口节点，可有效避免将数据包转发到易于中断的路段上，减少了网络延迟，提高 了车辆自组织网络的整体性能。

背景技术

车辆自组织网络是移动自组织网络一个极具应用价值的研究方向，并且为智能交 通系统的发展提供了一个有效的解决方案。车辆自组织网络以行驶的车辆和道路基础 设施为节点，实现车与车之间以及车与道路设施之间的信息交换，从而形成了由车辆 与道路基础设施组成的实时通信网络，不仅提高了道路交通的安全性与管理效率，而 且增加了驾驶舒适性。在城市环境中，网络拓扑变化频繁、节点移动受道路布局限制 以及路边障碍物对无线信号的阻挡，使车辆组织网络的路由协议设计比移动自组织网 络更加复杂。因此，如何结合城市环境下车辆自组织网络的特点设计出稳定、高效的 路由协议是车辆自组织网络研究的一个重点。

上海交通大学拥有的专利技术“一种动态自适应的车辆网络路由方法”(授权公 告号CN102595547B，申请号201210081277.2)公开了一种动态自适应的车辆网络路 由方法。该方法中车辆以及路边节点首先利用历史数据初始化整个网络系统，随后车 辆通过GPS以及路边节点获取其它车辆的轨迹信息、位置信息和当前道路的实时道路 信息，接下来各个车辆分别计算按道路来路由的路由策略和不考虑道路的路由策略在 当前情况下的传输成功率期望值及传输时延期望值，最后选择其中一种路由策略传输 数据包，并在需要的情况下对所选路由策略做出调整。该方法虽然根据不同的路况选 择不同的路由策略，但是该方法仍然存在的不足是，没有考虑到真实城市环境下障碍 物对无线信号传输的影响，造成丢包率的增加。

Lochert等人在“Geographic Routing in City Scenarios”(ACM SIGMOBILE Mobile  Computing and Communications Review，2005)中提出了一种基于交叉口的路由协 议GPCR(Greedy Perimeter Coordinator Routing)。该协议在每个交叉口设置协调 节点，在交叉口之间的路段上采用贪婪转发，在交叉口将数据包转发给协调节点，由 协调节点决定数据包的转发方向。该协议虽然解决了信号传输受障碍物阻碍的问题， 但是该方法仍然存在的不足是，过度依赖交叉口节点，将数据包转发给经过的每个交 叉口的协调节点，增加了跳数和延迟，降低了数据包的转发效率，此外交叉口节点的 判断算法增加了通信开销。

Lee等人在“Enhanced Perimeter Routing for Geographic Forwarding Protocols  in Urban Vehicular Scenarios”(Globecom Workshops，2007 IEEE)中提出了一 种基于预测的交叉口路由协议GpsrJ+(Greedy Perimeter Stateless Routing  Junction+)。该协议主要改进了交叉口处的路由策略，只有在数据包的转发方向发生 变化时，才将数据包转发给交叉口节点，否则数据包仍采用贪婪转发。若当前节点的 邻居节点中存在交叉口节点，就让当前节点做出如下预测：若该交叉口节点接收到数 据包，它将会选择哪个节点作为下一跳，如果预测所得的下一跳节点与当前节点的最 远邻居节点在同一路段上，则直接将数据包转发给最远的邻居节点；否则，转发给交 叉口节点。与基于交叉口的路由协议GPCR相比，该协议减少了数据包转发的跳数， 降低了对交叉口的依赖性，提高了数据包投递率。但是该协议仍然存在的不足是，基 于预测的交叉口路由协议GpsrJ+没有考虑路段的连通度，仅根据交叉口的一跳邻居 节点选择转发方向，有可能将数据包转发到不连通的路段上，造成网络中断，使得数 据包无法继续传输。

发明内容

本发明的目的在于克服上述现有技术的不足，提出一种车辆自组织网络中基于路 段长度的交叉口路由方法。本发明依据城市环境下车辆自组织网络中路段的长度，根 据交叉口节点计算得到的相邻路段连通度，选择连通的且距离目的节点最近的交叉口 节点或者邻居节点作为下一跳。

为实现上述目的，本发明提出的路由方法实现的具体思路是：首先交叉口节点计 算相邻路段的连通度；然后根据相邻路段的连通度，将数据包转发给距离目的节点最 近的交叉口节点或者邻居节点；重复上述过程直到到达目的节点。

本发明实现上述目的的具体步骤如下：

(1)节点获取节点信息：

(1a)车辆自组织网络中的每个节点，从全球定位系统GPS接收机和电子地图中， 获取自身节点信息和目的节点信息；

(1b)车辆自组织网络中的每个节点，周期性广播自身节点信息，并接收邻居节 点广播的节点信息，将邻居节点的节点信息保存到自身的邻居表中；

(2)当前节点查询自身的邻居节点中是否有目的节点，若是，执行步骤(7)； 否则，执行步骤(3)；

(3)当前节点查询自身的邻居节点中是否有交叉口节点，若是，执行步骤(4)； 否则，执行步骤(6)；

(4)计算交叉口节点的相邻路段连通度：

(4a)按照下式，计算交叉口节点所在交叉口的中心点和目的节点的连线与每个 相邻路段的角度差，

${\theta }_{i,j}=|{\theta }_{\mathrm{iD}}-{\theta }_{I_i{I}_j}|$

其中，θ_i,j表示交叉口节点所在的交叉口I_i的中心点和目的节点D的连线与相邻 路段I_i-I_j的角度差，I_j表示交叉口，I_i-I_j表示交叉口I_i和交叉口I_j所确定的路段， θ_iD表示交叉口节点所在的交叉口I_i的中心点和目的节点D连线与横坐标轴之间的夹 角，表示相邻路段I_i-I_j与横坐标轴之间的夹角，i和j分别表示两个不同的交叉 口的标号，其数值由实施场景中所涉及的交叉口的数目确定；

(4b)从相邻路段中，选取交叉口节点所在交叉口I_i的中心点和目的节点D的连 线与该相邻路段的角度差θ_i,j小于90°的相邻路段；

(4c)判断所选取的相邻路段的长度是否小于无线信号的通信半径，若是，执行 步骤(4d)；否则，执行步骤(4e)；

(4d)当交叉口节点位于所选取的相邻路段上的邻居节点中，存在比自身距离目 的节点更近的邻居节点时，所选取的相邻路段的连通度值为1；当交叉口节点位于所 选取的相邻路段上的邻居节点中，不存在比自身距离目的节点更近的邻居节点时，所 选取的相邻路段的连通度值为0；

(4e)交叉口节点利用实时的分布式连通度计算方法，计算所选取的相邻路段的 连通度；

(5)判断交叉口节点中相邻路段的连通度值是否为1，若是，当前节点向距离 目的节点最近的交叉口节点发送数据包，执行步骤(2)；否则，执行步骤(6)；

(6)当前节点向距离目的节点最近的邻居节点发送数据包，执行步骤(2)；

(7)当前节点向目的节点发送数据包：

当前节点的邻居节点中有目的节点时，将数据包直接转发给目的节点，目的节 点收到源节点转发的数据包后，路由结束。

与现有技术相比，本发明具有以下优点：

第一，本发明中计算了路段的连通度，优先选择连通的且距离目的节点更近的 交叉口节点，并且利用实时的分布式连通度计算方法获得路段的连通度，克服了现有 技术中不能保证转发路径连通的问题，可有效的避免将数据包转发到不连通的路段 上，减少了数据包的丢失率和延迟，提高了数据包投递率。

第二，本发明中通过路段长度和无线信号的通信半径的比较，针对长度大于无 线信号的通信半径和长度小于无线信号的通信半径的路段分别进行讨论，克服了现有 技术中没有考虑路段长度小于无线信号通信半径造成路由跳数增加的问题，使得该发 明更加适应于真实城市环境下的车辆自组织网中，将数据包跨路口转发给距离目的节 点最近的邻居节点，节省了路由跳数，提高了路由性能。

附图说明

图1为本发明的流程图；

图2为本发明实施例的应用场景示意图。

具体实施方式

下面结合附图1和附图2对本发明作进一步的描述。

参照附图2，本发明具体实施的应用场景示意图，图2中的直线所限定的条形区 域表示路段，虚线圆弧表示无线信号通信范围，无线信号通信范围的半径是无线信号 的通信半径，用R表示，白色圆表示节点，白色圆S₁和S₂表示两个不同的源节点， 白色圆D表示目的节点，I_i(i＝1,2,3,...,12)表示交叉口，I_i-I_j表示交叉口I_i和交叉 口I_j所确定的路段，A、B、C、E、F、G、H、J、K、L、M、N、O、P、Q和T表示节点。 源节点S₁和S₂都向目的节点D发送数据包，目的节点D位于交叉口I₉。

步骤1，节点获取节点信息。

车辆自组织网络中的每个节点，从全球定位系统GPS接收机和电子地图中，获取 自身节点信息和目的节点信息。节点信息包含节点标志号、速度、方向、地理坐标、 所在路段的标志号、所在路段长度和节点是否为交叉口节点的标志位。

本发明中的每个节点的地理坐标用下式表示：

(x_k,y_k)

其中，x_k表示节点k的横坐标，y_k表示节点k的纵坐标。

车辆自组织网络中的每个节点，周期性广播自身节点信息，并接收邻居节点广播 的节点信息，将邻居节点的节点信息保存到自身的邻居表中。邻居节点是指，任意两 个距离小于节点发出的无线信号的通信半径，且节点间没有被建筑物阻挡的两个互为 邻居的节点。源节点根据获得的节点信息，确定数据包的转发节点。

步骤2，当前节点查询自身的邻居节点中是否有目的节点，若是，执行步骤7； 否则，执行步骤3。

当前节点是指发送数据包的节点。

参照附图2，本发明的实施例中目的节点D不是源节点S₁和S₂的邻居节点。

步骤3，当前节点查询自身的邻居节点中是否有交叉口节点，若是，执行步骤4； 否则，执行步骤6。

如果当前节点是交叉口节点，这一步骤只考虑与当前节点位于不同的交叉口的邻 居节点，不考虑与当前节点位于同一个交叉口的邻居节点。

参照图2，本发明的实施例中交叉口节点A和B是源节点S₁的邻居节点，分别在 交叉口I₁和交叉口I₂处。交叉口节点H是源节点S₂的邻居节点，在交叉口I₁₁处。交 叉口节点F是源节点S₂的邻居节点，但却与源节点S₂在同一个交叉口I₁₀，因此不考 虑交叉口节点F。

步骤4，计算交叉口节点的相邻路段连通度。

路段是指任意两个相邻交叉口之间的道路，以相邻的交叉口为端点。交叉口节点 的相邻路段是指交叉口节点所在的交叉口的相邻路段。交叉口的相邻路段是指以该交 叉口为端点的路段。

如果相邻的交叉口节点都是当前节点的邻居节点，则这两个交叉口节点之间的路 段不作为交叉口节点的相邻路段考虑。源节点所在的路段也不作为交叉口节点的相邻 路段考虑。

(4a)按照下式，计算交叉口节点所在交叉口的中心点和目的节点的连线与每个 相邻路段的角度差，

${\theta }_{i,j}=|{\theta }_{\mathrm{iD}}-{\theta }_{I_i{I}_j}|$

其中，θ_i,j表示交叉口节点所在的交叉口I_i的中心点和目的节点D的连线与相邻 路段I_i-I_j的角度差，I_j表示交叉口，I_i-I_j表示交叉口I_i和交叉口I_j所确定的路段， θ_iD表示交叉口节点所在的交叉口I_i的中心点和目的节点D连线与横坐标轴之间的夹 角，表示相邻路段I_i-I_j与横坐标轴之间的夹角，i和j分别表示两个不同的交叉 口的标号，其数值由实施场景中所涉及的交叉口的数目确定。

按照下式，计算交叉口节点所在的交叉口I_i的中心点和目的节点D连线与横坐标 轴之间的夹角θ_iD和相邻路段I_i-I_j与横坐标轴之间的夹角

${\theta }_{\mathrm{iD}}=\arctan \frac{y_D-y_{I_i}}{x_D-x_{I_i}}$

${\theta }_{I_i{I}_j}=\arctan \frac{y_{I_j}-y_{I_i}}{x_{I_j}-x_{I_i}}$

其中，x_D和y_D分别表示目的节点的横坐标和纵坐标，和分别表示交叉口I_i的中心点的横坐标和纵坐标，和分别表示交叉口I_j的中心点的横坐标和纵坐 标。

参照图2，为描述方便，图2中没有标出的路段不予考虑。本发明的实施例是， 源节点S₁的邻居节点A所在的交叉口I₁的中心点坐标为(5,1)，邻居节点B所在的交叉 口I₂的中心点坐标为(19,1)，目的节点D的坐标为(66,24)，交叉口节点A所在交叉口 I₁的中心点和目的节点D的连线与横坐标轴的夹角交叉口节点A 的相邻路段I₁-I₄与横坐标轴之间的夹角则角度差交叉口节点B所在的交叉口I₂的中心点和目的节点D的连线与横坐标轴的夹角 交叉口节点B的相邻路段I₂-I₅与横坐标轴之间的夹角 交叉口节点B的相邻路段I₂-I₃与横坐标轴之间的夹角则角度 差和角度差源节点S₂的邻居节点H所在的 交叉口I₁₁的中心点坐标为(19,35)，交叉口节点H所在的交叉口I₁₁的中心点和目的节 点D的连线与横坐标轴的夹角交叉口节点H的相邻路段I₁₁-I₈与横坐标轴之间的夹角交叉口节点H的相邻路段I₁₁-I₁₂与横坐标轴之间 的夹角则角度差和角度差源 节点所在的路段和路段I₁-I₂不作为交叉口节点A和交叉口B的相邻路段考虑。

(4b)从相邻路段中，选取交叉口节点所在交叉口I_i的中心点和目的节点D的连 线与该相邻路段的角度差θ_i,j小于90°的相邻路段。

参照图2，本发明的实施例中交叉口节点A所在的交叉口I₁的中心点和目的节点 D的连线与相邻路段I₁-I₄的角度差则交叉口节点A选取 相邻路段I₁-I₄；交叉口节点B所在的交叉口I₂的中心点和目的节点D的连线与相邻 路段I₂-I₅的角度差交叉口节点B所在的交叉口I₂的中心 点和目的节点D的连线与相邻路段I₂-I₃的角度差则交叉 口节点B选取相邻路段I₂-I₅和I₂-I₃；交叉口节点H所在的交叉口I₁₁的中心点和目 的节点D的连线与相邻路段I₁₁-I₈的角度差交叉口节点 H所在的交叉口I₁₁的中心点和目的节点D的连线与相邻路段I₁₁-I₁₂的角度差 则交叉口节点H选取相邻路段I₁₁-I₈和I₁₁-I₁₂。

(4c)判断所选取的相邻路段的长度是否小于无线信号的通信半径，若是，执行 步骤(4d)；否则，执行步骤(4e)。

节点发出的无线信号的通信半径按照下式计算：

$R=\frac{\lambda }{4\pi }\sqrt{{10}^{\frac{P_s-P_r-L_o}{10}}{G}_s{G}_r}$

其中，R表示车辆自组织网络中节点发出的无线信号的通信半径，λ表示车辆自 组织网络中节点发出的无线信号的波长，P_r、P_s分别表示车辆自组织网络中节点的接 收功率和发送功率，L_o表示车辆自组织网络中的建筑物阻挡因子，G_s和G_r分别表示 车辆自组织网络中节点的发送天线增益和接收天线增益，s表示车辆自组织网络中发 出无线信号的节点，r表示车辆自组织网络中接收无线信号的节点，o表示车辆自组 织网络中的建筑物。

按照下式，计算建筑物阻挡因子：

L_o＝βn+γd

其中，L_o表示车辆自组织网络中的建筑物阻挡因子，β表示车辆自组织网络中节 点发出的无线信号穿过建筑物的一堵墙后的衰落值，该衰落值为9dB，n表示车辆自 组织网络中建筑物的墙与节点的通信路径相交的次数，γ表示车辆自组织网络中节点 发出的无线信号在建筑物内部传输时单位长度路径上的衰落值，该衰落值为0.4dB，d 表示车辆自组织网络中节点的通信路径与建筑物的墙相交的总长度，o表示车辆自组 织网络中的建筑物。

参照图2，本发明的实施例中交叉口节点A的相邻路段I₁-I₄的长度小于无线信 号的通信半径；交叉口节点B的相邻路段I₂-I₅的长度小于无线信号的通信半径，交 叉口节点B的相邻路段I₂-I₃的长度大于无线信号的通信半径；交叉口节点H的相邻 路段I₁₁-I₈的长度小于无线信号的通信半径，交叉口节点B的相邻路段I₁₁-I₁₂的长度 大于无线信号的通信半径。

(4d)当交叉口节点位于所选取的相邻路段上的邻居节点中，存在比自身距离目 的节点更近的邻居节点时，所选取的相邻路段的连通度值为1。当交叉口节点位于所 选取的相邻路段上的邻居节点中，不存在比自身距离目的节点更近的邻居节点时，所 选取的相邻路段的连通度值为0。

参照图2，本发明的实施例中相邻路段I₁-I₄上存在邻居节点C比交叉口节点A 距离目的节点D更近，则相邻路段I₁-I₄的连通度为1。相邻路段I₂-I₅的延伸线上存 在比交叉口节点B距离目的节点D更近的邻居节点E，则相邻路段I₂-I₅的连通度为1。 相邻路段I₁₁-I₈的延伸线上存在比交叉口节点H距离目的节点D更近的邻居节点O， 则相邻路段I₁₁-I₈的连通度为1。

(4e)交叉口节点利用实时的分布式连通度计算方法，计算所选取的相邻路段的 连通度。

本发明在实时的分布式连通度计算方法中定义了广播信息CAM，用来计算路段的 连通度。为了描述该方法，将路段两端的两个交叉口分别称为源交叉口和目的交叉口。 实施该方法的交叉口节点所在的交叉口就是源交叉口，路段另一端的交叉口为目的交 叉口。位于源交叉口的节点称为源交叉口节点，位于目的交叉口的节点称为目的交叉 口节点。广播信息CAM由源交叉口节点发出，向相邻路段进行广播。广播信息CAM包 含CAM标志号、广播路段标志号、源交叉口标志号、目的交叉口标志号、连通域值。 初始的广播信息CAM中的连通域值为空，广播信息CAM中的连通域值根据路段的连通 度进行更新。当返回源交叉口的连通域值等于0时，路段的连通度为1，当返回源交 叉口的连通域值大于0时，路段的连通度为0。

实时的分布式连通度计算方法按照下述步骤进行：

第一步，将相邻路段分成长度等于无线信号的通信半径的子部分，从距离目的交 叉口节点最近的子部分开始进行编号。

参照图2，本发明的实施例中相邻路段I₂-I₃的源交叉口为I₂，目的交叉口为I₃， 从I₃到I₂将路段分为子部分1、子部分2和子部分3；路段I₁₁I₁₂的源交叉口为I₁₁，目 的交叉口为I₁₂，从I₁₁到I₁₂将路段分为子部分1、子部分2和子部分3。

第二步，将相邻路段上每个节点的连通域值初始化为节点所在子部分的编号。

参照图2，本发明的实施例中在路段I₂-I₃上，节点J连通域值初始化为3，节点 K连通域值初始化为2，节点L初始值为1；在路段I₁₁-I₁₂上，节点M和节点N的连 通域值都初始化为2。

第三步，相邻路段上节点查询自身的邻居节点中是否有目的交叉口节点，如果有， 将节点自身的连通域值更新为0，将更新后节点的连通域值记入广播信息CAM进行广 播后，执行第六步；否则，执行第四步。

参照图2，本发明的实施例中目的交叉口节点G是节点L的邻居节点，则节点L 的连通域值更新为0，将更新的连通域值记入广播信息CAM，进行广播。

第四步，相邻路段上节点查询自身的邻居节点中是否有比自身节点距离目的交叉 口节点更近的节点，如果没有，节点将自身的连通域值记入广播信息CAM进行广播后， 执行第六步；否则，节点只广播广播信息CAM，执行第五步。

参照图2，本发明的实施例中节点J有比自身距离目的交叉口更近的节点K，则 节点J只广播广播信息CAM。节点K有比自身距离目的交叉口更近的节点L，则节点 K只广播广播信息CAM。节点M有比自身距离目的交叉口更近的节点N，则节点M只 广播广播信息CAM。节点N没有比自身距离目的交叉口更近的节点，则节点N将连通 域值2记入CAM，并进行广播。

第五步，当节点收到来自比自身距离目的交叉口节点更近的节点的广播信息CAM 时，根据广播信息CAM中记录的节点连通域值更新自身的连通域值，将更新后的连通 域值记入广播信息CAM进行广播。

参照图2，本发明的实施例中节点K收到节点L的广播信息CAM，将连通域值更 新为0，记入广播信息CAM进行广播。节点J收到节点K的广播信息CAM，将连通域 更新为0，记入广播信息CAM进行广播。节点M收到节点N的广播信息CAM，将连通 域更新为2，记入广播信息CAM进行广播。

第六步，相邻路段的源交叉口节点查询自身接收的广播信息CAM中是否有连通域 值，若有，将此相邻路段的标识号及其连通域值记入自身的节点信息中，执行第七步； 否则，执行第三步。

参照图2，本发明的实施例中源交叉口节点B收到节点J的广播信息CAM中有连 通域值，将路段标识号I₂-I₃和连通域值0记入自身的节点信息。源交叉口节点H收 到节点M的广播信息CAM中有连通域值，将路段标识号I₁₁-I₁₂和连通域值2记入自身 的节点信息。

第七步，当相邻路段的源交叉口节点的相邻路段的连通域值为0时，相邻路段的 连通度为1。当源交叉口节点的相邻路段的连通域值大于0时，相邻路段的连通度为 0。

参照图2，本发明的实施例中源交叉口节点B的相邻路段I₂-I₃的连通域为0，则 相邻路段I₂-I₃的连通度为1，源交叉口节点H的相邻路段I₁₁-I₁₂的连通域值为2， 则相邻路段I₁₁-I₁₂的连通度为0。

步骤5，判断交叉口节点中相邻路段的连通度值是否为1，若是，当前节点向距 离目的节点最近的交叉口节点发送数据包，执行步骤2；否则，执行步骤6。

参照图2，本发明的实施例中源节点S₁的邻居节点中的交叉口节点A的相邻路段 I₁-I₄的连通度是1，交叉口节点B的相邻路段I₂-I₃和相邻路段I₂-I₅的连通度是1， 且交叉口节点B比交叉口节点A距离目的节点D更近，则源节点S₁将数据包发送给交 叉口节点B；源节点S₂的邻居节点中的交叉口节点H的相邻路段I₁₁-I₈的连通度是1， 则源节点S₂将数据包发送给自身的距离目的节点D最近的邻居节点H。

步骤6，当前节点向距离目的节点最近的邻居节点发送数据包，执行步骤2。

步骤7，当前节点向目的节点发送数据包。

当前节点的邻居节点中有目的节点时，将数据包直接转发给目的节点，目的节点 收到源节点转发的数据包后，路由结束。

上述循环步骤中当前节点是发送数据包的节点，第一次循环中当前节点为源节 点，之后的每一次循环都会更新当前节点。当目的节点接收到数据包，路由结束。

参照图2，本发明的实施例中重复上述步骤2、步骤3、步骤4、步骤5和步骤6， 源节点S₁将数据包依次转发给交叉口节点B、节点K、节点L、交叉路口节点G和节 点T，最终转发到目的节点D。源节点S₂将数据包依次转发给交叉口节点H、交叉口 节点O、节点P和节点Q，最终转发到目的节点D，路由结束。