# Design and Evaluation of Flooding-Based Location Service in Vehicular Ad Hoc Networks+
## 1 Introduction  
Research in the field of intelligent transport systems (ITSs) [1] is very active. Numerous advances have been made to increase user safety and comfort. Vehicular ad hoc networks (VANETs) are part of ITS, and developing them to obtain completely autonomous vehicles is a necessity. One of the most important characteristics of VANETs is their dynamic topology [2], which is a consequence of the network being made up of mobile nodes: nodes can change their position quite frequently. This means that there is a need for routing protocols that are capable of quickly adapting to changes in network topology. The geographical location of nodes (i.e., node co-ordinates) has been suggested as a means to address this issue. Location-based (geographic) routing protocols base their routing decisions on location information using the location of the destination node to forward packets to this node [3; 4; 5]. Establishing the destination's location is the first step towards communicating with the destination. Different means are available for a node to identify its own position, and the GPS is certainly the best-known and most used [6; 7]. Determining its own position is usually locally done by the node, even though other solutions exist. However, identifying the location of the destination node when sending a message cannot be done locally without the use of external data or services. In geographicrouting protocols, this is achieved by means of a location service. This service is used by the sender of a packet to determine the location of the destination. As a result, the performance of a geographic routing protocol mainly depends on the performance of the location service. A location service provides the location information for a specific node in a VANET by implementing a mechanism that tracks the location of nodes in the network. Figure 1 shows the general structure of a location-service management protocol. The scheme essentially consists of three different entities (a location service, a source node, and a destination node), and two main operations (a location query and a location update). Every node updates the location service responsible for handling the location information. When a node needs to send a packet, it queries the location service and retrieves the destination's location. The location service of a node may be situated on the source node itself or on another node. When the location service is present on the source node, the query is locally resolved by the source node, as is the case for location-information dissemination methods. A location-service protocol has to exhibit the following properties:  
* Efficiency: induced overhead by control packets (e.g., location updates and location queries) should be kept to a minimum. * Robustness: the location service should not be disrupted by node mobility or failure (especially for location servers if they are separate nodes), or disconnection from the network. * Load balancing: the protocol should apply traffic-balancing schemes to avoid bottleneck problems. * Scalability: the protocol should maintain all of the above properties when the network scales to a large number of nodes. * Locality awareness: the distance of the location server from the querying source should not be greater than the distance between the source and the destination nodes. In other words, location queries for nearby nodes should not travel unnecessarily over the network. However, the benefits of this feature rely on the presence of local data-traffic patterns. This article provides the following contributions:  
* A new location-service protocol that limits the amount of control information exchanged between nodes while maintaining accurate location information. Two versions of the protocol are proposed, a deterministic and a probabilistic version. * An analytical model to evaluate the number of messages sent by the protocol is provided. Models were developed for 1D, 2D, and 3D networks. * Simulations to confirm the validity of the analytical model are presented.