车载自组网无标度特性与小世界特性分析
2022-06-29周贝贝周鹏
周贝贝，周鹏
（湖北汽车工业学院 电气与信息工程学院，湖北 十堰 442002）
车载自组网（vehicle ad-hoc network, VANET）是作用在车辆间自组织、结构开放的通信网络，是特殊的移动ad-hoc网络［1］。在已有关于VANET的研究成果中，对其拓扑特性的研究是提升网络整体性能的关键技术之一。网络拓扑结构的分析是优化路由策略的基础［2-3］，路由策略在不同的网络结构上会产生不同的运行效果；而运行在网络上的路由策略也会反映出网络的拓扑结构特性，两者相辅相成。通过研究分析网络的拓扑结构特征和路由策略在网络上的运行效果，深入理解网络结构特性，进而优化路由策略，是提高网络的容量和性能的重要手段。在已有的关于车载自组网网络特性的研究中，关于VANET 网到底具有什么特性的结论并不一致。蔡虹等［4］结合复杂网络理论，从全局视角出发，对南京地铁网络的拓扑结构进行分析，发现网络具有无标度特性，不具有小世界特性。高天智［5］基于图论和复杂网络理论，得到城市轨道网络具有无标度及小世界特性的结论。高佩等［6］基于复杂网络理论，通过分析综合运输网络的拓扑特性，得到其同时具有显著的“无标度”特性和“小世界”特性的结论。孟玉如［7］分析了VANET 的动态拓扑特性，发现其不具有无标度特性。分析网络拓扑结构是设计路由策略的基础。路由表的建立依赖于具体的网络模型，是衡量网络路由性能的关键参数之一。在基于网络拓扑特性设计路由协议的研究中，蔡蓉［8］提出了基于车辆密度的可靠性路由协议，韩定定［9］基于无标度网络提出了动态路由算法。文中基于实际数据集和仿真数据集，将2种连接方式下的车载自组网的网络特性进行了对比，探究了网络具有无标度特性和小世界特性的条件。
1 无标度特性和小世界特性
1.1 无标度特性
研究者们发现，无标度特性在很多复杂网络如Internet、WWW、社会网络、生物网络等中都有不同程度的体现。网络中，在大部分节点只有少数几个链接的同时，某些节点却拥有与其他节点的大量链接。具体地说，网络具有幂律形式的度分布［10］：
1.2 小世界特性
网络是将现实世界中的事物及其关系进行适当的抽象，由节点和边按照一定规则组成；小世界特性反映网络各节点之间联系的紧密程度。研究发现，许多节点数巨大的复杂网络却有着较小的平均路径长度。具体地说，在网络节点平均度k固定的前提下，如果网络平均路径长度L的增长速度与网络节点数N的对数成正比，即
式中：
2 组网方式
全连接构造算法：1）给网中所有节点集合V中的节点编号；2）根据节点的位置，得出距离矩阵；3）根据预设的通信半径，若距离矩阵中的值大于通信半径的值，则将此值置为1；若距离矩阵中的值小于通信半径的值，则将此值置为0；由此得到节点的邻接矩阵；4）根据邻接矩阵连边。
在BA 无标度网络演化模型中，通过增长和择优连接2个演化机制的引入，构造出了节点度服从幂律分布的生长型网络。BA连接构造算法表示如下［12］：1）增长。从1个由m0个节点构成的初始网络开始，每次引入1 个新的节点，依次连到m个已存在的节点上，m不大于m0。2）优先连接。1个新节点与1个已经存在的节点vi相连接的概率和节点vi的度ki有如下关系：
实际车载自组网中，节点位置及通信距离的限制会影响节点间的连接，所以择优连接演化机制受到限制。基于上述分析，对BA 连接加以改进，提出了受节点位置约束的BA1 度优先连接方法，构造算法如下：1）从网中所有节点集合V中随机选择n0个节点作为初始节点，记为V0，并将初始节点添加到网络中；2）找出V0中每个节点通信半径范围内的节点的并集，记为V1；3）依次找出V1中的节点vi，记vi的通信半径范围内的节点集与V0的交集为Mi；4）将vi与Mi中节点连边，最大连边数ni不大于n0：若Mi中的节点个数小于ni，则将节点vi与Mi中的节点连接；若Mi中的节点个数大于ni，则按度优先的原则从Mi中的节点中选出ni个，与节点vi相连接：
5）转步骤2），直到V0等于V。
3 实验方案
为探究连接方式对车载自组网网络特性的影响，基于实际数据集和仿真数据集，在全连接和BA1连接的组网方式下，分别对车载自组网的无标度特性与小世界特性进行验证。采用成都滴滴数据集作为实际数据集，每条记录包括车辆ID、订单ID、时间戳、经度和纬度。首先对GPS 数据进行预处理，如表1所示，以时间戳和经纬度为条件，筛选8：00和18：00区域直径为5592 m、8360 m、12 270 m的GPS数据，并将经纬度转换到高斯坐标系。
表1 实际数据集内容
为探究没有道路约束条件下改变连接方式对车载自组网网络特性的影响，在一定节点坐标范围内，按照随机均匀分布取点生成了10 个仿真数据集文件，节点数从100开始，每个数据集增加100个节点，节点坐标范围为3000×3000。
实际场景和仿真场景分别由实际数据集和仿真数据集组成。采用全连接和BA1 连接，通信半径R分别取300 m、500 m、1000 m，在BA1连接方式下，n0为10，ni为5。
4 仿真结果分析
4.1 实际场景网络特性分析
图1a 是实际数据集4～6 的GPS 数据在BA1 连接方式下组成的VANET度分布图，R为300 m。在双对数坐标下，由图1a 中数据所组成网络的累计度分布如图1b所示，尾部分布近似于直线，符合具有无标度特性的网络度分布在双对数坐标下的变化趋势，但VANET 是否具有无标度特性还需进一步分析。由实际数据集1～3 的GPS 数据在BA1 连接方式下所组成的VANET，在相同通信半径下，可得到与图1类似的度分布图与累计度分布图。
图1 R为300 m时BA1连接方式下实际数据集的度分布图
为了研究实际场景在全连接和BA1 连接方式下是否具有无标度特性，根据式（2）～（3）计算R分别为300 m、500 m、1000 m 时的缩放参数α，如图2所示。在全连接方式下，α均大于3，网络不具有无标度特性。在BA1 连接方式下，α更小，网络更贴近于无标度网络，但α均大于3，此时网络不具有无标度特性。相比于全连接，BA1连接方式下α要小得多，此时网络更贴近于无标度网络。
图2 实际数据集的缩放参数
为了研究实际场景在全连接和BA1 连接方式下是否具有小世界特性，分别计算L、C和
表2 不同组网方式下实际场景小世界特性分析表
4.2 仿真场景网络特性分析
图3a是仿真数据集6～10的GPS数据在BA1连接方式下组成VANET的度分布图，其中R为300 m。在双对数坐标下，由图3a 中数据所组成网络的累计度分布见图3b，可以看到，尾部分布近似于直线，符合具有无标度特性网络的度分布在双对数坐标下的变化趋势，但VANET 是否具有无标度特性还需进一步分析。由仿真数据集1～5 的GPS 数据在BA1 连接方式下所组成的VANET，在相同通信半径下，可得到与图3分布及走势类似的度分布图与累计度分布图。
图3 R为300时BA1连接方式下仿真数据集的度分布示意图
根据式（2）～（3）计算R分别为300 m、500 m、1000 m时的α，如图4所示。在全连接方式下，α均大于3，网络不具有无标度特性。在BA1连接方式下，α更小，网络更贴近于无标度网络，且当R增长到1000 m时，α为2～3，此时网络具有无标度特性。
图4 仿真数据集的缩放参数
分别计算L、C和
表3 不同组网方式下仿真场景小世界特性分析表
5 结论
以复杂网络为工具，基于实际场景和仿真场景，在全连接和BA1连接方式下，对VANET的无标度特性与小世界特性进行了分析，结果表明：实际场景VANET 都不具有无标度特性和小世界特性；仿真场景全连接方式下组成的VANET不具有无标度特性和小世界特性，BA1 连接方式下组成的VANET，当通信半径增长到一定值时，具有无标度特性和小世界特性。全连接方式下计算的缩放参数远大于BA1 连接方式下计算的缩放参数，因为BA1连接采用了度优先原则，构成的网络更贴近于无标度网络。当网络具有无标度特性时，节点度的大小可作为设计路由协议的依据；当网络具有小世界特性时，可按照节点的聚类系数来设计路由协议。后续将根据网络特性设计路由协议。
