Abstract: The vehicular networks become denser with the expanding of various services. Therefore, the interference poses a big challenge for the connectivity of network. In the existing works, the connectivity is determined by the signal strength and the distance between the pair of vehicular, where the interference induced by resource allocation has not been considered. Unlike the existing works, in this study, firstly, to represent the influence of the resource and interference on the connectivity, it uses the graph theory to model the connectivity of network, and it gives the definitions of connectivity indices related with resource allocation and interference. Secondly, it analyzes the minimum number of resources that can guarantee the network connectivity by coloring theory. At last, it proposes a resource allocation algorithm based on the minimum spanning tree, which can improve the connectivity in the limited resources. The simulations show that the proposed algorithm can improve the connectivity compared with the comparative algorithm.

Key words: connectivity, interference vehicular networks, resource allocation, graph theory

摘要： 随着车载网络中各种业务的飞速增长，网络密集程度不断增加，因此，愈发严重的干扰问题对网络的连通性构成了很大的挑战。已有研究中网络的连通性仅由信号强度或车辆之间的距离确定，而没有考虑资源分配引起的干扰对网络连通性的影响。针对这个问题，为了表征网络中资源与干扰对连通性的影响，使用图论对网络连通性进行了建模，定义了与资源分配相关的连通性度量指标；利用染色理论对能够保证网络连通性的所需资源数目的最小值进行了分析；提出了一种基于最小生成树的资源分配算法，以改善网络的连通性。仿真结果证实了相比其他算法，该算法能够提高车载网络的连通性。

关键词: 连通性, 干扰车载网络, 资源分配, 图论