A Knapsack Constrained Steiner Tree model for continuous coverage over urban VANETs

Time-sensitive mobile service with vehicular networks depend on continuous coverage on the road system. It is a challenge to meet a tight budget while maintaining coverage quality. In order to resolve the problem, we model the road system as an undirected graph and reduce it to a Knapsack Constrained Steiner Tree model. Since the reduced model is an NP-hard problem, we resolve it by using Lagrangian decomposition approach. The terminal nodes in the graph are hotspots, where most vehicles accumulate; and, the paths connecting these hotspots are measured by a new metric: coverage value. We evaluated the our scheme by comparing it with the Maximum Continuous Coverage protocol in terms of the packet drop rate in the NS2 simulation. The final result shows that our coverage is reliable, and suitable for urban vehicular networks.