In Vehicular Ad hoc NETworks (VANETs), essentially the information of one-hop neighbors is important for data delivery. In a general way, each node broadcasts short packets, i.e., hello packets, to indicate its appearance and establishes a neighbor table for storing neighbor information through receiving others' hello packets. As a popular approach, it is named as a hello scheme. Determining the validity of the neighbor table, a hello scheme is vital to routing protocols in VANETs. However, a hello scheme with high accuracy and low overhead is severely challenged due to the highly dynamic topology and restricted vehicle mobility in VANETs.