一种基于拓扑演化的车载自组织网络路由选择方法

摘要

本发明涉及无线通信领域，特别涉及一种基于拓扑演化的车载自组织网络路由选择方法，该方法包括：获取车载自组织网络参数；根据网络参数构建动态键渗透模型，通过该模型预测链路变化；根据链路变化结果构建动态拓扑演化模型，并采用网络拓扑状态转移矩阵描述网络拓扑动态变化过程；根据动态拓扑演化模型的平稳分布性质预测稳态网络拓扑结构；根据稳态网络拓扑结构获取源目节点的所有可能传输路径作为候选路径集合，并筛选出最优传输路径；本发明考虑VANET中的网络特性以及链路间的相互影响关系，在路由选择过程中能够基于预测的网络拓扑选择稳定可靠路径进行数据传输，能够有效提升路由过程的数据包传输率，降低端到端传输时延。

说明书

技术领域

本发明涉及无线通信领域，特别涉及一种基于拓扑演化的车载自组织网络路由选择方法。

背景技术

智能交通系统在城市交通的发展过程中发挥着不可或缺的作用，车载自组织网络(Vehicular Ad-Hoc Network,VANET)作为智能交通系统的重要组成部分，通过建立车辆间、车辆与路边单元的无线通信解决交通信息传播以及道路安全等问题。路由算法是保障通信质量的核心问题，因此设计适用于VANET场景的高效路由算法具有重要意义。然而，VANET场景中高速移动的车辆节点，复杂的网络环境都将增加车辆间的无线链路的中断概率，导致网络拓扑结构频繁变化。时变的拓扑结构使得数据传输不连续，这将会启用重路由机制，导致网络数据包传输率以及端到端时延性能急剧恶化。因此需要针对VANET场景开发可靠路由协议，提升网络通信性能。

将软件定义网络(Software Defined Network,SDN)引入车联网中能够基于采集的网络信息从全局视图来决定最佳路由。然而，控制器基于当前网络信息进行路由选择，而后将决策指令下发到数据面，当数据平面的车辆节点收到指令后由于拓扑结构的时变性，该指令容易发生失效，因此刻画网络拓扑演化成为可靠路由选择方案设计的关键，对于决策者根据网络变化提前做出有效路由决策具有重要意义。现有拓扑时间演化分析方法对网络拓扑变化进行描述，通过建立时变图和时空图模型将时间维度加入网络演进刻画过程。然而，现有拓扑演化相关研究主要关注在构建时变图模型来刻画拓扑时变性，以支撑路由决策，并未从导致网络拓扑的微观变化出发分析网络拓扑的动态变化。现有图模型中拓扑变化表征精度较低，影响路由计算的精确度，无法得到最优的可靠路径。因此，需要从节点及链路变化切入对网络拓扑结构演化的分析，提升对时变拓扑结构刻画的精确度。

为表征网络动态特性，现有研究通过提取节点和节点间的特征建立链路预测模型。现有大量研究利用节点的位置信息和移动性预测链路连接状态变化情况。然而，实际VANET场景中除了节点的高速移动，复杂的信道环境，时变的节点资源，链路间的相互影响也会造成链路连接状态频繁变化的关键因素，导致了路由路径不精确。

发明内容

为解决以上现有技术存在的问题，本发明提出了一种基于拓扑演化的车载自组织网络路由选择方法，该方法包括：

S1：构建车载自组织网络，获取该网络参数，根据获取的网络参数确定网络无线链路状态变化图；

S2：构建动态键渗透模型，通过该模型计算网络无线链路状态变化图中每条链路间的相互影响关系，根据链路间的相互影响关系预测链路变化结果；

S3：根据链路变化结果构建动态拓扑演化模型，并采用动态拓扑演化模型的网络拓扑状态转移矩阵描述网络拓扑动态变化过程；

S4：采用动态拓扑演化模型预测稳态网络拓扑结构；

S5：根据预测的稳态网络拓扑结构获取源目节点的所有可能传输路径，并将所有的可能传输路径作为候选路径集合；

S6：对候选路径集合中的路径进行筛选，将其中具有最少跳数的路径即为最优传输路径。

优选的，网络参数包括信号与干扰加噪声比、节点缓存队列长度以及链路可用性。

优选的，根据网络参数确定网络无线链路状态变化图包括：设置信号与干扰加噪声比阈值，根据设置的阈值计算当前链路信号与干扰加噪声比的状态和下一时刻链路信号与干扰加噪声比的状态，根据当前链路信号与干扰加噪声比的状态和下一时链路信号与干扰加噪声比的状态构建信号与干扰加噪声比状态转移矩阵；采用概率质量函数计算当前车辆节点的缓存队列长度状态和下一时刻当前车辆的缓存队列长度状态，根据当前车辆节点的缓存队列长度状态和下一时刻当前车辆的缓存队列长度状态构建节点缓存队列长度状态转移矩阵；设置时间间隔，计算当前时间段两个车辆节点之间可持续通信的概率，根据设置的时间间隔计算下一个时间间隔内两个车辆节点之间可持续通信的概率，根据当前时间段的可持续通信的概率和下一个时间间隔的可持续通信的概率构建链路可用性状态转移矩阵；根据信号与干扰加噪声比状态转移矩阵、节点缓存队列长度状态转移矩阵以及链路可用性状态转移矩阵构建链路状态转移矩阵。

进一步的，链路状态转移矩阵为：

其中，

优选的，计算网络无线链路状态变化图中每条链路间的相互影响关系包括：计算链路l

进一步的，增加链路间相互影响的链路连接状态变化矩阵的表达式为：

其中，

优选的，构建动态拓扑演化模型的过程包括：获取增加链路间相互影响的链路连接状态变化矩阵F

进一步的，网络拓扑状态转移矩阵中的元素计算表达式为：

其中，集合Λ表示所有的网络拓扑状态集合，并且网络拓扑状态利用邻接矩阵表示，A

优选的，根据动态拓扑演化模型的平稳分布性质预测稳态网络拓扑结构的过程包括：构建稳态网络拓扑预测模型，通过该预测模型预测具有稳定状态的网络结构；预测模型的表达式为：

s.t.C1:πQ＝π

通过马尔可夫过程平稳性质计算得到的网络状态平稳概率中，概率最大的网络状态为所预测的最大稳定网络拓扑状态：

其中，π

优选的，对候选路径集合中的路径进行筛选的过程包括：计算候选路径集合中每条路径的跳数，将跳数最小的路径作为最优传输路径，其表达为：p_opt＝arg min h(p

本发明的有益效果：

本发明基于对VANET场景的动态特性分析，将车辆的移动性和复杂的网络环境的变化融入不同时间维度的节点和链路状态建模过程，并建立动态键渗透模型量化链路间相互影响关系，从而实现链路连接状态变化的精确预测；随后以链路模型为基础构建网络拓扑状态转移觉镇，完成网络拓扑动态演化过程的刻画；最后基于网络拓扑演化过程的稳态分析，预测稳态网络拓扑以支撑可靠路由决策，提高数据传输效率。

附图说明

图1为本发明的软件定义车载自组织网络场景图；

图2为本发明的基于拓扑演化的车载自组织网络的路由选择方法流程图。

具体实施方式

下面将结合本发明实施例中的附图，对本发明实施例中的技术方案进行清楚、完整地描述，显然，所描述的实施例仅仅是本发明一部分实施例，而不是全部的实施例。基于本发明中的实施例，本领域普通技术人员在没有做出创造性劳动前提下所获得的所有其他实施例，都属于本发明保护的范围。

VANET场景中无线链路的建立必须要满足以下条件：首先，恶劣的信道环境以及阴影衰落等影响使得信号传输质量较差，因此接收节点的SINR需要大于接收阈值以保障接收节点能够成功接收数据；其次，车辆节点需要有足够的缓存空间对接收到的数据进行存储和处理；然后，为保障无线链路的稳定性，车辆节点间的链路在指定时间内需要保持持续可用；最后，由于时变的业务流和网络资源，当节点或者链路上的流量超过阈值时，通过该节点或链路传输的数据将会选择相邻的链路进行传递，将会加剧相邻节点的缓存压力以及链路负载，导致相邻链路因节点或者链路过载而发生链路中断，从而引发级联故障，因此还需要考虑链路间的相互影响。

一种软件定义车载自组织网络结构如图1所示，此架构中包括了数据平面和控制平面，其中数据平面由车辆节点配备的车载单元(On Board Unit,OBU)、路边单元(RoadSide Unit,RSU)和基站(Base Station,BS)组成，执行由控制平面下发的操作指令。RSU通过监听车辆广播的基本安全信息(Basic Safety Messages,BSM)获得其覆盖区域内的车辆节点的状态信息，包括车辆的位置、速度以及行驶方向等，RSU覆盖范围外的车向BS更新其状态信息。RSU和BS将向SDN控制器发送BSM信息，而控制器通过聚合底层网络状态信息，将形成网络拓扑映射并进行网络拓扑预测，从而进行可靠路由决策。

一种基于拓扑演化的车载自组织网络路由选择方法，如图2所示，该方法包括：

S1：构建车载自组织网络，获取该网络参数，根据获取的网络参数确定网络无线链路状态变化图；

S2：构建动态键渗透模型，通过该模型计算网络无线链路状态变化图中每条链路间的相互影响关系，根据链路间的相互影响关系预测链路变化结果；

S3：根据链路变化结果构建动态拓扑演化模型，并采用动态拓扑演化模型的网络拓扑状态转移矩阵描述网络拓扑动态变化过程；

S4：采用动态拓扑演化模型预测稳态网络拓扑结构；

S5：根据预测的稳态网络拓扑结构获取源目节点的所有可能传输路径，并将所有的可能传输路径作为候选路径集合；

S6：对候选路径集合中的路径进行筛选，将其中具有最少跳数的路径即为最优传输路径。

一种基于拓扑演化的车载自组织网络路由选择方法的具体实施方式，VANET场景下无线链路建立需要满足以下条件：首先，接收节点的SINR需要大于接收阈值，保证接收节点能够成功接收到数据；其次，接收节点需要有足够的缓存队列长度对接收到的数据进行存储和处理；最后，为保持链路的稳定性，在一定时间内链路需要保持持续可用。针对以上关键条件，本发明选择网络参数SINR、BQL和链路可用性共同量化链路状态。

101、根据VANET场景的网络动态特性，选择参数SINR、BQL以及链路可用性共同量化链路状态；

在本发明实例中，VANET场景下无线链路建立需要满足以下条件：首先，接收节点的SINR需要大于接收阈值，保证接收节点能够成功接收到数据；其次，接收节点需要有足够的缓存队列长度对接收到的数据进行存储和处理；最后，为保持链路的稳定性，在一定时间内链路需要保持持续可用。针对以上关键条件，本发明选择网络参数SINR、BQL和链路可用性共同量化链路状态。

102、根据SINR、BQL和链路可用性的含义进行网络参数建模，并将VANET的动态特征，如节点移动性，信道环境，阴影衰落等整合到网络参数推导过程中，并基于网络参数的建模建立链路连接状态变化模型从而描述链路状态变化过程。

在本发明实例中，首先根据节点的状态信息对参数进行建模。针对参数SINR，节点的高速移动会导致节点间的距离和干扰频繁变化。因此当节点i在t

其中P

链路的SINR状态独立于链路前一SINR状态，并且独立于链路可用性状态L和缓存队列长度B。链路SINR状态转换概率为：

其中，P

网络参数SINR的状态转移矩阵表示为S，具体表达如下：

针对参数BQL，网络中节点具有相同的最大缓存队列长度为F，在时刻t

VANET中车辆的数据包达到过程近似服从泊松分布，平均到达概率为λ包/秒。节点的数据处理速度为h包/秒，数据包成功发送概率服从二项分布，车辆发送数据包的错误概率为p

其中，f

基于对车辆节点的缓存队列长度状态转移概率的分析，可以得到BQL状态转移矩阵如下：

其中，B表示BQL状态转移矩阵，P

矩阵B的元素计算如下：

其中，h表示节点对数据包的处理速度，Δt表示参数SINR当前状态和预测状态的时间差，b表示节点的剩余缓存空间长度。

为保证无线链路的稳定性，需要选择具有链路可用性的链路，其中链路可用性定义为两车之间的链路在指定时间内保持持续可用的概率。

当前无线链路具有可用性，表明链路的两端节点经过Δt后仍在彼此的通信范围内。预测链路在下一状态保持持续可用的概率，即链路具有可用性的概率计算如下：

其中，L表示当前链路可用性状态，L′表示预测的链路可用性状态，f(T)为持续时间T的概率密度函数。持续时间T的概率密度函数的表达式为：

其中，R表示车辆间可通信范围，

当前无线链路不具有可用性时，预测下一状态无线链路是否具有可靠性，首先计算下一状态链路两端节点是否在彼此的通信范围内，其表达式为：

根据下一状态链路两端节点是否在彼此的通信范围内计算下一状态链路具有可用性的概率，其表达式为：

链路可用性状态转移概率矩阵表示为L，具体表达为：

根据网络参数SINR、BQL和链路可用性的建模分析，可以量化链路连接状态，并推导链路状态变化转移矩阵；链路l

其中，

103、根据对链路间的相互影响关系分析，在步骤102的基础上构建动态键渗透模型量化链路的相邻链路连通性对链路状态变化的影响。

该模型中第i条链路的失效概率，即链路连接状态由“连接”转变为“故障”的概率，与网络中相邻链路中故障链路数目有关；链路的恢复概率，即链路连接状态由“故障”转变为“连接”的概率，与相邻链路中的连接链路数量有关。

链路l

其中，F

链路l

其中，参数μ>0为网络拓扑对链路恢复连接的影响强度，当μ＝1时，链路连接恢复不具有拓扑依赖性，当μ≠1时，网络拓扑结构将通过级联函数影响链路连接恢复情况。

增加链路间相互影响关系后的链路连接状态转移矩阵表示为F

其中，

104、根据全网链路变化，采用马尔可夫理论构建动态拓扑演化模型(DynamicTopology Evolution,DTE)，并利用网络拓扑状态转移矩阵Q描述网络拓扑动态变化过程，其中矩阵元素具体计算如下：

其中，A与A′分别为两种不同网络拓扑状态的邻接矩阵，a

105、DTE模型采用马尔可夫链，用状态转移矩阵来表示拓扑演化。根据该模型的平稳分布特性计算出每个网络拓扑状态的平稳概率，从而使平稳概率最大的拓扑状态成为稳定的网络拓扑。因此，将拓扑状态预测问题表述为平稳分布概率求解问题，并设计了稳定的拓扑预测模型如下：

s.t.C1:πQ＝π

其中，π

106、基于DTE模型预测得到的稳态网络拓扑结构进行路由选择，其所选的路径更具稳定性，在数据传输过程中不易发生中断。因此预测得到的稳态网络拓扑结构A

以上所举实施例，对本发明的目的、技术方案和优点进行了进一步的详细说明，所应理解的是，以上所举实施例仅为本发明的优选实施方式而已，并不用以限制本发明，凡在本发明的精神和原则之内对本发明所作的任何修改、等同替换、改进等，均应包含在本发明的保护范围之内。