Algebraic Computations in Anonymous VANET

In the area of development of AI/ML applications in Vehicular Adhoc Networks (VANET), a highly dynamic environment, efficient algebraic distributed computations are of utmost importance. On the other hand, there is a growing concern about privacy of users/drivers. One of the solutions is to perform computations assuming anonymity of the users. There is already a large amount of work on this topic in the general Anonymous Dynamic Network model, however the obtained theoretical guarantees are not suitable for very large-scale networks, such as VANET. In this work, we propose an anonymous algebraic computation framework tailored for VANET, called Anonymous Vehicular Adhoc Networks (A-VANET). We introduce heuristic changes to the Restricted Methodical Counting (RMC) protocol aiming to speed up performance in A-VANET with respect to the theoretical bounds in general Anonymous Dynamic Networks. We evaluate this protocol on traces of taxi trips in New York City extracted from publicly available data from 2013, and on a highway traffic environment modeled by a set of path graphs. Both inputs are highly dynamic including also recurrent disconnections. Our results show that, for the parameter combinations tested and for networks with good expansion, RMC is sub-quadratic and even linear under some conditions. Therefore, even the theoretical upper bound proved as a function of connectivity parameters is loose by a factor of more than n⁷. These results show the promise of further exploring the question of what is the optimal running time for algebraic computations in A-VANET and other practically-motivated Anonymous Dynamic Networks with limited messages, memory and disconnections.