Neighbor Discovery for VANET with Gossip Mechanism and Multi-packet Reception

Neighbor discovery (ND) is a key initial step of network configuration and prerequisite of vehicular ad hoc network (VANET). However, the convergence efficiency of ND is facing the requirements of multi-vehicle fast networking of VANET with frequent topology changes. This paper proposes gossip-based information dissemination and sensing information assisted ND with multi-packet reception (GSIM-ND) algorithm for VANET. GSIM-ND algorithm leverages efficient gossip-based information dissemination in the case of multi-packet reception (MPR). Besides, through multi-target detection function of multiple sensors installed in roadside unit (RSU), RSU can sense the distribution of vehicles and help vehicles to obtain the distribution of their neighbors. Thus, GSIM-ND algorithm leverages the dissemination of sensing information as well. The expected number of discovered neighbors within a given period is theoretically derived and used as the critical metric to evaluate the performance of GSIM-ND algorithm. The expected bounds of the number of time slots when a given number of neighbors needs to be discovered is derived as well. The simulation results verify the correctness of theoretical derivation. It is discovered that GSIM-ND algorithm proposed in this paper can always reach the short-term convergence quickly. Moreover, GSIM-ND algorithm is more efficient and stable compared with completely random algorithm (CRA), scan-based algorithm (SBA) and gossip-based algorithm. The convergence time of GSIM-ND algorithm is 40%-90% lower than that of these existing algorithms for both low density and high density networks. Thus, GSIM-ND can improve the efficiency of ND algorithm.