PaperlayerView exact revision on arXiv

Source-linked AI summary

Bus Trajectory-Based Street-Centric Routing for Message Delivery in Urban Vehicular Ad hoc Networks

Gang Sun, Yijing Zhang, Dan Liao, Hongfang Yu, Xiaojiang Du, Mohsen Guizani

arXiv:1804.02498v1cs.NIcs.CReess.SP

TL;DR

Urban VANET routing needs efficient message delivery despite limited RSU deployment and mobility-related connectivity challenges. The paper proposes BTSC, which uses bus trajectories, street-based routing metrics, and FACO forwarding, and reports better transmission ratio, delay, and adaptability across tested networks.

  • Problem

    Urban VANETs need efficient routing for communication between vehicles and places, while RSU-based routing is limited by deployment and existing bus schemes rely heavily on specified bus relays.

  • Method

    BTSC builds a bus-line routing graph using bus appearance probabilities on streets, selects paths with PSC and PPC, and uses FACO for forwarding between relay buses.

  • Results

    BTSC reports better packet transmission ratio and average end-to-end delay, better adaptability to different vehicle densities, and stable performance as transmission distance changes.

  • Takeaways & Limitations

    Bus trajectories can support street-centric routing, while combining bus main relays with ordinary-vehicle secondary relays provides the proposed forwarding architecture.

Abstract

from arXiv · show

This paper focuses on the routing algorithm for the communications between vehicles and places in urban VANET. As one of the basic transportation facilities in an urban setting, buses periodically run along their fixed routes and widely cover city streets. The trajectory of bus lines can be seen as a sub map of a city. Based on the characters of bus networks, we propose a bus trajectory-based street-centric routing algorithm (BTSC), which uses bus as main relay to deliver message. In BTSC, we build a routing graph based on the trajectories of bus lines by analyzing the probability of bus appearing on every street. We propose two novel concepts, i.e. the probability of street consistency (PSC) and the probability of path consistency (PPC) which is used as metrics to determine routing paths for message delivery. This aims to choose the best path with higher density of busses and lower probability of transmission direction deviating from the routing path. In order to improve the bus forwarding opportunity, we design a bus-based forwarding strategy with ant colony optimization (FACO) to find a reliable and steady multi-hop link between two relay buses in order to decrease end-to-end delay. BTSC makes the improvements in the selection of routing path and the strategy of message forwarding. Simulation results show that our proposed routing algorithm has a better performance in transmission ratio, transmission delay and adaptability to different networks.

I. INTRODUCTION

Urban VANET routing must deliver messages efficiently despite vehicle mobility, limited RSU deployment, and weaknesses in existing bus-based schemes. BTSC uses bus trajectories and street structure to select routes and improve forwarding.

  • Efficient routing is important for VANET communication between vehicles and places because vehicles must access networks across changing urban conditions.
  • RSU-based routing is constrained by RSU number, location, communication range, and deployment overhead, making intensive deployment necessary for stable service.
  • Buses offer wide coverage, relatively uniform node distribution, fixed trajectories, and regular service across city roads.
  • Existing bus-based routing specifies relay buses in sequence, so missing the next bus can delay forwarding until a later encounter.
  • BTSC builds a bus-line routing graph, selects streets with high bus density, and uses PSC and PPC to choose routing paths.
  • FACO uses ant colony optimization to select relay buses and stable multi-hop links, while simulations evaluate delay and packet transmission ratio.

B. Street-Centric Routing Protocol

Street-centric routing represents trajectories as sequences of streets rather than specified vehicles. The paper combines this perspective with a two-layer architecture in which buses provide primary relaying and common cars provide secondary forwarding.

  • Street-centric routing selects a sequence of streets as the routing trajectory, while node-centric routing selects moving vehicles as routing nodes.
  • Street-centric protocols comprise routing-path selection and forwarding strategies that deliver packets along the selected streets.
  • Existing street-centric studies use micro topologies, predicted link probabilities, QoS, and lane weight, but do not exploit relationships between streets and bus lines.
  • The proposed VANET architecture has upper and lower layers, and both buses and common cars can send, receive, and relay packets.
  • Buses act as main relays that plan routes, while common cars forward packets between relay buses that cannot directly communicate.
  • Vehicles exchange DSRC beacons containing identity, position, velocity, and direction, storing neighboring vehicle information in NeighborTable.

B. Link Life Time

The link-life-time model estimates how long two moving vehicles can remain connected under a communication-radius constraint. It uses relative distance and stochastic velocity assumptions to define link reliability and expected lifetime.

  • The model assumes communication radius R and represents each vehicle using position and velocity, together with inter-vehicle distance and velocity difference.
  • Vehicle distance changes over time according to the relative positions and velocities of the two vehicles.
  • A direct link exists when D(t)^2 ≤ R and the vehicles remain within communication range.
  • Link reliability is defined as the probability that direct communication remains available during a specified period.
  • Expected link lifetime combines link reliability with the duration of connection between the vehicles.

IV. ALGORITHM DESIGN

BTSC is a street-centric routing algorithm that uses buses as primary relays and common cars as secondary relays for multi-hop delivery. Its design comprises routing-graph construction, path selection, and forwarding along the selected street sequence.

  • Algorithm overview: BTSC builds a routing graph from bus trajectories, selects a routing path, and forwards packets along that path.The algorithm estimates bus density from fixed bus trajectories to address sparse-network routing failures.
  • Algorithm overview: Buses serve as the main relays, while common cars provide multi-hop links between main relays that cannot communicate directly.This division supports packet delivery between buses separated beyond direct communication range.
  • Link behavior: Vehicles can communicate indefinitely when they have equal velocity and direction, represented by T(l_i,j) = ∞.The stated condition is that communication lasts until one vehicle’s velocity changes.

A. Bus Lines-Based Routing graph

The bus lines-based routing graph maps real-road intersections and streets to vertices and edges, weighting streets according to bus presence. Bus appearance probability is derived from bus-line trajectories and street lengths.

  • Bus trajectory model: Bus-line trajectories are treated as a sub map of the city for analyzing their correlation with streets.The analysis defines the probability of a bus appearing on each street.
  • Bus trajectory model: For a bus serving street r, its appearance probability is based on the ratio of street length L_r to trajectory length L_b.The definition applies when the bus trajectory includes street r.
  • Graph construction: The routing graph G = (V, E, W) represents intersections as vertices, streets as edges, and edge weights as bus-density indicators.The graph is converted from the real road map and assigns weights using bus-appearance probabilities.
  • Graph construction: Higher edge weight represents lower bus density on the corresponding street, while streets without bus lines receive ω = ∞.Because buses move bidirectionally, ω_i,j is assumed equal to ω_j,i.
  • Figure context: Fig.2 analyzes the trajectories of bus lines used to construct the routing graph.Its caption identifies the figure as an analysis of bus-line trajectories.

B. Selection of Routing Path

BTSC selects street sequences using bus density and path consistency. PSC measures consistency between adjacent streets, while PPC helps choose a path whose bus movement is less likely to deviate from the route.

  • Path criteria: Higher vehicle density along a routing path is associated with better carry-and-forward routing performance.BTSC therefore favors paths containing streets with higher bus density.
  • Path criteria: PSC describes consistency between bus lines on two adjacent streets and addresses transmission-direction deviation during carry-and-forward routing.A relay bus that cannot find the next relay before deviating can cause packet loss or rerouting.
  • Path selection example: P1 and P2 have higher bus density than P3, making P1 and P2 preferable routing paths in the illustrated example.The example lists P1 as (E1, E5, E7, E8), P2 as (E4, E2, E7, E8), and P3 as (E4, E6, E3, E8).
  • Path criteria: PPC evaluates consistency across a sequence of adjoining streets and is used to compare candidate routing paths.The paper also redefines PPC because a zero PSC could otherwise make the entire path’s PPC zero.
  • Path selection example: P1 has a higher PPC value than P2, so P1 is selected as the routing path in the example.The passage reports the comparison without exposing the complete equation values.
  • Selection procedure: The algorithm first finds k shortest paths by weight, computes each path’s PPC, and selects the path with maximum PPC.This combines low edge-weight routing with a subsequent path-consistency criterion.

C. Bus-Based Forwarding Strategy with ACO (FACO)

The forwarding strategy restricts next relays to buses located along the remaining routing streets. It prefers the longest-lived direct link and uses multi-hop forwarding with ACO when direct qualified relays are unavailable.

  • Relay qualification: The next relay must be located between the carrier’s current street and the final street of the packet’s routing path.This qualification ensures forwarding remains along the selected street sequence.
  • Relay selection: When qualified buses are within communication range, the carrier selects the bus with maximum link lifetime.If none is directly reachable, the carrier searches for eligible buses through multi-hop links.
  • Multi-hop forwarding: Ant colony optimization is introduced because intermediate-vehicle movement can break the multi-hop link.The strategy uses ACO to address instability in links between relay buses.

1) ACO problem formulation

The ACO forwarding procedure seeks a qualified next relay bus by constructing and evaluating multi-hop links, then selecting the candidate with the highest objective value.

  • ACO problem formulation: ACO models the link between a packet carrier and a candidate relay bus as a multi-hop path through common vehicles.The path comprises single-hop links between adjacent nodes.
  • ACO problem formulation: Link quality is evaluated using multi-hop link lifetime and transmission delay, with longer lifetime and lower delay indicating greater reliability.The objective function combines these metrics using a weight parameter and a delay threshold.
  • ACO problem formulation: During the request and discovery phases, ask ants record candidate paths while vehicles forward them according to pheromone and heuristic values.Eligible vehicles generate response ants that return along the recorded path.
  • ACO problem formulation: Pheromone updates combine prior pheromone intensity with heuristic information, while evaporation returns stale links toward the initial pheromone state.When a link lifetime expires, its pheromone evaporates to the initial value.
  • ACO problem formulation: After the response timer expires, the source bus selects the endpoint of the recorded multi-hop link with the maximal objective function value.If qualified neighboring buses already exist, the forwarding algorithm can select the candidate with maximum link lifetime; otherwise it invokes ACO establishment.

V. PERFORMANCE EVALUATION AND ANALYSIS

This section describes the simulation environment and presents the routing simulation results.

  • V. PERFORMANCE EVALUATION AND ANALYSIS: The section describes the simulation environment and shows the simulation results.

A. Simulation Environment

The simulations use a Chengdu urban map with 20 bus lines and evaluate routing against existing algorithms under defined network and protocol settings.

  • A. Simulation Environment: The simulation map covers the area inside Chengdu’s First Ring Road, containing 58 intersections and 100 streets.The map was downloaded from OpenStreetMap and spans about 5.9 × 5.8km.
  • A. Simulation Environment: The simulated bus network contains 400 buses operating on 20 bus lines with trajectories generated by SUMO.The bus-line trajectories are shown as the simulation routes.
  • A. Simulation Environment: The evaluation compares BTSC with CBS and AQRV, representing node-centric and QoS-oriented routing approaches respectively.CBS selects frequently contacting buses, whereas AQRV uses ant colony optimization for routing-path selection.
  • A. Simulation Environment: The simulations use IEEE 802.11p, a 6Mbps transmission rate, 200~800m communication radii, and 10~40km/hr vehicle velocities.The simulation duration is 4000s.

B. Simulation Results

Simulations evaluate BTSC across sparse, common, and dense networks while varying packet transmission distance and communication radius. Across these scenarios, BTSC shows stronger stability and overall adaptability, while longer distances generally hurt performance and larger radiuses improve it.

  • Simulation setup: Simulations cover sparse, common, and dense networks with 2000, 4000, and 6000 vehicles, respectively.Each scenario tests packet transmission distances from 0 to 2500 meters and communication radiuses of 200, 400, 600, and 800 meters.
  • Comparative results: BTSC maintains more stable performance as transmission distance changes, with smaller delay increases and packet-ratio decreases than the other algorithms in sparse networks.The paper also reports good convergence and stability for BTSC across the three network densities.
  • Comparative results: When transmission distance is 0–500 meters, all three algorithms exceed 90% packet transmission ratio and remain below 25 seconds average end-to-end delay.When distance exceeds 1000 meters, BTSC has the best performance among the three algorithms in the common-network comparison.
  • Comparative results: In dense networks, AQRV performs better than BTSC and CBS at distances no more than 1000 meters, while BTSC has good convergence and stability as distance changes.BTSC’s two-relay design makes it inferior to AQRV at short distances despite both using ant colony optimization.
  • Parameter effects: Increasing transmission distance lowers packet transmission ratios and raises average end-to-end delays across the three network densities.This trend is reported for all four communication-radius groups in the sparse network and across the three networks overall.
  • Parameter effects: Increasing communication radius improves routing performance by increasing packet transmission ratio and decreasing average end-to-end delay.At the same transmission distance, a larger radius reduces forwarding hops, which raises routing success and lowers delay.
  • Overall findings: Overall, BTSC is reported to provide better packet transmission ratio, average end-to-end delay, adaptability to vehicle densities, and convergence for changing transmission distance.This conclusion compares the three algorithms under transmission distance, communication radius, and vehicle-node density.

VI. CONCLUSION

BTSC improves urban VANET routing by optimizing both route selection and message forwarding through bus trajectories. It uses PSC and PPC to select routes and FACO to establish reliable multi-hop links between relay buses.

  • VI. CONCLUSION: BTSC builds a bus line-based routing graph from the probability of buses appearing on each street.The graph exploits buses’ fixed routes to represent urban street connectivity.
  • VI. CONCLUSION: PSC and PPC select routes with higher bus density and lower transmission-direction deviation.
  • VI. CONCLUSION: FACO uses ant colony optimization to find reliable multi-hop links between relay buses that cannot directly communicate.The strategy aims to increase bus-forwarding opportunities and decrease end-to-end delay.
  • VI. CONCLUSION: BTSC optimizes routing-path selection and forwarding strategy to improve VANET quality of service.
Loading 1804.02498v1…