Title
On optimal service directory selection in urban vehicular networks
Abstract
This paper studies the Delay Bounded Service Discovery Protocol (DB-SDP) problem in Urban Vehicular Ad-hoc Networks (VANETs). Services and resources on the vehicles must be discovered before they become available to the whole network. In distributed Service Discovery Protocols (SDPs), Service Directories (SDs) are selected to store the service description for other vehicles. Selecting SDs is difficult because VANETs has the disruptive nature which incurs a significant delay, whereas the users may have QoS requirements that the query for some certain service must be answered within some delay bound. We study the problem of optimal SD selection that minimizes the number of the SDs under such delay bound requirement. We theoretically prove that such SD selection problem is NP-complete even when the future positions of the vehicles are known as a priori. To solve the DB-SDP without the prior knowledge of future traces, we theoretically and empirically analyze the number of vehicles covered by the set of SDs within a delay bound. We find the number of covered vehicles exhibits some strong regularity. Regarding this regularity, we develop a heuristic iterative algorithm for the optimal SD selection. We conduct extensive trace driven simulations based on real vehicular GPS data and the results show that with high probability, our algorithm can select SD sets 50% smaller than those selected by alternative algorithms.
Year
DOI
Venue
2012
10.1145/2413236.2413241
Proceedings of the first workshop on Urban networking
Keywords
DocType
CitationsĀ 
sd set,certain service,selecting sds,service directories,sd selection problem,significant delay,alternative algorithm,service discovery protocols,optimal service directory selection,urban vehicular network,delay bounded service discovery,optimal sd selection,service discovery
Conference
1
PageRankĀ 
ReferencesĀ 
Authors
0.38
8
4
Name
Order
Citations
PageRank
Fenggang Wu1164.08
Hongzi Zhu265343.37
Jia-Liang Lu312116.62
Min-you Wu41600140.81