Complex Network Theoretical Analysis on Information Dissemination over Vehicular Networks

Jingjing Wang, Chunxiao Jiang, Longxiang Gao, Shui Yu, Zhu Han, Yong RenICC 2016 · DOI · OpenReview

Abstract

Enhancing communication efficiency and quality in vehicular networks is a critical challenge as urban density increases. Real-world datasets suggest that large-scale vehicular networks align with complex network models. This paper analyzes a taxi GPS dataset from Beijing to establish communication models (V2I, V2V, and hybrid) and proposes optimization algorithms for station selection, traffic allocation, and information source selection based on complex network theory.

Introduction: The Scaling Crisis in Vehicular Networks

As urban environments become increasingly dense, vehicular networks (V2X) face a significant scaling crisis. Traditional research often focuses on isolated components, such as specific radio channel models or vehicle mobility patterns, frequently overlooking the "big picture" topological properties of massive, city-wide networks.

In these environments, communication performance is dictated by network structure as much as signal strength. Factors like frequent cellular handovers in ultra-dense 5G cells and the "bottleneck" effect of highly connected vehicles create complex webs of interference and delay. This research bridges the gap between abstract graph theory and practical telecommunications engineering to optimize network management.

Methodology

The researchers model the vehicular network as a weighted, undirected graph where nodes represent individual vehicles and edges represent communication links (V2V or V2I). A central contribution is the concept of Communication Impedance ($R$), which serves as the edge weight.

Unlike simple distance-based metrics, Communication Impedance factors in:

  • Path Loss: Calculated using the COST 231-Bertoni-Ikegami model.
  • Handover Costs: The number of cellular handovers ($n_s$) required.
  • Topological Metrics: Node degree (connectivity) and betweenness centrality (the frequency a node appears on shortest paths).

Dataset and Network Topology

The study is grounded in empirical data from a Taxi GPS dataset in Beijing (the "T-drive" dataset from Microsoft Research Asia). By tracking taxis within a specific longitude/latitude bounding box, the authors create a realistic snapshot of urban mobility.

Taxi GPS data points in Beijing used for network modeling.

Analysis of this data reveals that vehicular networks are "Small Worlds". Despite having thousands of nodes, the average path length remains low (approximately 6.7 hops), while the clustering coefficient is high. Furthermore, the network is "scale-free", meaning a small number of "hub" vehicles possess a disproportionately high number of connections.

Optimization Models

Based on the complex network framework, three optimization models were developed:

  1. V2I Clustering: A generalized distance-based algorithm to group vehicles for optimized base station selection.
  2. V2V Traffic Allocation: A convex optimization model designed to distribute data tasks across the network while minimizing total communication impedance.
  3. Hybrid Source Selection: A min-max linear programming approach to identify "information anchors"—specific vehicles that, when used as sources, maximize the network's overall capacity.

Key Results and Discussion

The topological verification for a 500-meter communication range yielded an average clustering coefficient of 0.7225 and an average path length of 6.7337.

Topological properties of the vehicular network, including node degree and clustering coefficients.

Several critical insights emerged from the simulations:

  • Frequency vs. Impedance: As carrier frequencies move toward 5G/6G bands, communication impedance rises due to increased path loss, necessitating a trade-off between bandwidth and range.
  • Optimal Cell Size: Handover dynamics stabilize when the cellular radius exceeds 700m, suggesting an optimal size for balancing infrastructure costs against switching delays.
  • Centrality Paradox: High centrality can be a disadvantage; vehicles that are highly connected often face higher impedance because they are overwhelmed with data-forwarding tasks, leading to congestion.

Conclusion and Future Directions

This paper provides a robust theoretical framework for managing dense urban vehicular networks. However, the current analysis primarily utilizes "snapshots" of the network. Because vehicular networks are inherently dynamic, future work will focus on dynamic evolutionary topology, transitioning from static graphs to temporal ones. Additionally, integrating more complex environmental factors, such as urban "canyons" (buildings and trees), into the impedance formula will further refine the model's real-world accuracy.

Summary updated

Abstract

How to enhance the communication efficiency and quality on vehicular networks is one critical important issue. While with the larger and larger scale of vehicular networks in dense cities, the real-world datasets show that the vehicular networks essentially belong to the complex network model. Meanwhile, the extensive research on complex networks has shown that the complex network theory can both provide an accurate network illustration model and further make great contributions to the network design, optimization and management. In this paper, we start with analyzing characteristics of a taxi GPS dataset and then establishing the vehicular-to-infrastructure, vehicle-to-vehicle and the hybrid communication model, respectively. Moreover, we propose a clustering algorithm for station selection, a traffic allocation optimization model and an information source selection model based on the communication performances and complex network theory.
BibTeX
@inproceedings{wang2016complex,
  author = {Jingjing Wang and Chunxiao Jiang and Longxiang Gao and Shui Yu and Zhu Han and Yong Ren},
  title = {{Complex Network Theoretical Analysis on Information Dissemination over Vehicular Networks}},
  booktitle = {ICC},
  year = {2016},
  doi = {10.1109/icc.2016.7511133},
}
Figure