# A Distributed Token Passing Protocol for Time Constrained Data Gathering in VANETs
## 1 Introduction
In this paper, we propose a protocol inspired by WTRP seminal work [14], where significant differences have been introduced: (i) a token circulates in a network that is dynamically and _step-by-step_ formed, i.e, the initial unit (for example the traffic light) starts the process of the token packet sending it to only _one_ neighbor node (i.e., the one with higher information), which in turn selects in the next round only one vehicle and so on until the time deadline is reached, (ii) there is no a priori or proactive neighbors discovery, while it is _in-path_ performed, (iii) in every step, after possibly locally storing and processing, data are passed to the _best_ next hop in order to perform a distributed information gathering, thus this approach is close to a token passing, (iv) the number of visited devices can change dynamically according to the traffic conditions and mobility patterns, (v) the token is delivered to the initial unit creating a _virtual ring_ within a time deadline, and (vi) the token packet format, i.e, syntax and semantics of its fields, and the protocol phases are tailored to this specific use case. Specifically, we characterize a novel protocol, called _Tom Thumb_ (TT), suitable for information gathering and sharing within a VANET, by adopting D2D communications among vehicles in an urban environment. The proposed approach can be adopted to support typical _smart cities_ missions such as an improvement of traditional infrastructure through Information and Communications Technology (ICT), enhancing the quality of life for citizenship, companies and institutions [19]. In this context, each vehicle, which can be conveniently assumed to be paired with a smartphone used by drivers or passengers, shares its local context awareness with its neighbors belonging to a VANET group. In particular, our proposal resorts to a token passing protocol scheme initiated and terminated in the _same_ device (e.g., the traffic light) creation, which iteratively discovers the nearby vehicles and collects information for traffic monitoring and controlling applications, as expected in a typical smart city scenario. The selection of the best _closed_ path is a typical non polynomial (NP)-hard optimization problem, as it could analyse all the possible paths among vehicles, to select the one maximizing data gathering while matching a predefined time constraint; in particular, this problem is unaffordable at the increase of the number of vehicles [18]. In addition, in the presence of vehicles mobility, a centralized approach requires the instantaneous and ideal knowledge of vehicles' positions, which can be achieved at the expense of a prohibitive signaling overhead. To this purpose, the proposed TT adopts a sub-optimal approach by hop-by-hop selecting the best path and then concatenating local optima, instead of evaluating the global one. In particular, it does not visit all the nodes, but, driven by in path processing, it selects the path collecting an information quantity close to the optimum. However, TT is close to the optimum approach in terms of data gathering, as it has been validated by numerical results with different time constraints. The rest of this paper is structured as follows: Section 2 discusses some related works, in Section 3, the system model and the proposed protocol are described, Section 4 validates our method by means of numerical results, and, finally, in Section 5, the conclusions are drawn.