# A Distributed Token Passing Protocol for Time Constrained Data Gathering in VANETs
## 3 Proposed Approach
### Phase I: Token Processing
```
1:if\(L\) is 0 then
2:ifHop Counter is not Max Hop then
3:repeat
4:finds(max(\(\epsilon_{i}\)))
5:if\(i\) not in VNIsID then
6:\(\textit{NextTO}\leftarrow\textit{ i}\)
7:\(\textit{NextTO}_{\textit{Information}}\leftarrow\epsilon_{i}\)
8:exit
9:else
10: remove \(i\) from Neighbors
11:until len(Neighbors) is not 0
12:if len(Neighbor) is 0 then
13:\(\textit{NextTO}\leftarrow\textit{last arrived}\)
14:\(\textit{NextTO}_{\textit{Information}}\gets 0\)
15: adds its ID in VNIsID
16:\(HC\gets HC\) + 1
17:else
18:\(L\gets 1\)
19: create return path
20: changes VNIsID and Hop Counter
21:\(\textit{NextTO}_{\textit{information}}\gets 0\)
22:\(\textit{NextTO}\leftarrow\textit{VNIsID[0]}\)
23:else
24:\(\textit{NextTO}_{\textit{information}}\gets 0\)
25: Remove ID from VNIsID
26:\(\textit{NextTO}\leftarrow\textit{VNIsID[0]}\)
27:\(HC\gets HC\) - 1
```

**Algorithm 2** [PERSON] algorithm. If the token is in discovery mode (_L_ field sets to 0), after waiting for timer expiration, the actual TO checks all the received NDR packets and, if it still has some time remaining (i.e., the _Hop Counter_ lower than _Max Available Hop_), it searches for the next TO. It basically selects the neighbor that carries more information and, if it is not yet visited, it becomes the next TO. If the best neighbor has already been visited, it is discarded. This process repeats until a next TO. is found or there are no available neighbors (i.e., all the neighbors have been discarded). In the latter case, the next TO becomes the last vehicle coming in the queue, while, in the former case, the next TO is a previously visited device and the added information is 0. If a TO verifies that the _Hop Counter_ becomes equal to the _Max Available Hop_, it triggers the Return Mode (changes to 1 the \(L\) field) and it becomes responsible for evaluating the return path. It analyses the _Visiting Nodes ID_ field and performs an optimisation: if loops are present (i.e., nodes are visited more than one time), they are deleted. Furthermore, it appends all the visiting nodes in a FIFO queue (the first ID becomes the next TO) and it changes the _Hop Counter_ (equal to the length of the modified _Visiting Nodes ID_). It can be noticed that henceforth the added information is 0. If a node receives the token in return mode, it removes its ID in the _Visiting Nodes ID_ field, sets the following ID as the next TO, decreases the _Hop Counter_ field, and sends the token. ## 4 Numerical Results

The proposed TT protocol has been validated by performing numerical simulations on PythonTM based framework integrating both networkx and numpy to set up and analyse the network features. We investigate the performance in terms of the amount of collected information within a predefined time constraint, as expressed in Equation (2); in addition, the probability of token recovering has also been derived. Specifically, the following algorithms are compared:

1. Drunkard Random Walk (_DrkRdnWilk_), i.e., a special case of the well-known _random walk_ with a finite time horizon, where TO randomly forwards the token packet to one of its neighbours. As a consequence, it is a lower bound for the performance. 2. Heuristic 1 (_Heu1_). In this approach, the next TO is selected as in Algorithm 2. The main difference with respect to the proposed TT scheme is that _Heu1_ does not save the path and, when the return to the TL is triggered, the neighbours' discovery procedure is still performed and the token packet is forwarded the best neighbour, which becomes TO. The trigger is based on a time value \(\tau\) which represents the amount of available time to explore the network normalised to the deadline. As soon as this threshold is exceeded, the token is triggered back. In performing our simulations, we selected \(\tau\) as equal to 3/5, since it represents a good trade-off. This parameter is a priori set by the TL within the PADDING field of the token packet (Figure 3).