# ARNS: Adaptive Relay-Node Selection Method for Message Broadcasting in the Internet of Vehicles
## 2 Related Work  
Several methods are proposed for relay-node selection in IoV, as discussed in the following. Greedy perimeter stateless routing (GPSR) [19] obtains the location of neighbor nodes through periodic flood beacons, and selects the relay-node in each hop using the greedy algorithm. When the greedy algorithm fails, the relay-node is selected with the right-hand rule. The advantage of GPSR is that it can be applied in all road structures. However, the information update of neighbor nodes in GPSR is not real-time, and it limits the performance. What is more, GPSR mainly considers end-to-end message propagation and does not fully consider message broadcasting. In order to improve the performance of message broadcasting, a real-time adaptive dissemination system (RTAD) is proposed in [20], and it defines two metrics--informed vehicles and messages received--and selects the most suitable beacon-based method for different Rols based on the simulation results of the two metrics. Its advantage is that the message broadcasting in urban scenarios is achieved with better overall performance. However, it still has the problem of lacking real-time information, which is the same as GPSR and is only suitable in urban scenarios. Urban multi-hop broadcast protocol (UMB) [21] is a black-burst-based relay-node selection method, which solves the problem of lacking real-time information in the beacon-based method. It aims to maximize message progress by selecting the farthest vehicle as the relay-node. The sender broadcasts a Request-To-Broadcast (RTB) packet in its communication range. Upon the reception of RTB, nodes, i.e., vehicles, broadcast a channel jamming signal, i.e., black-burst, for a duration that is proportional to the node's distance from the sender. Then, the farthest node transmits the longest black-burst, and performs forwarding. The disadvantage of UMB is that it has a relatively high communication delay since it spends the longest black-burst to select the farthest node to perform forwarding. Binary-partition-assisted broadcast protocol (BPAB) [22] is a binary partitioning broadcast method based on the black-burst, and solves the problem of UMB. It deploys a binary partitioning scheme and a novel contention mechanism. The binary partitioning scheme iteratively divides the range, which is the communication range in the first iteration and the selected segment in other iterations, into multiple segments. In addition, the farthest segment which contains nodes is selected by the aid of the black-bursts. Then, through a novel contention mechanism, a node is randomly selected as the relay-node in the farthest segment. Compared with the previous methods, BPAB achieves a lower and more stable delay, but it only works on the straight road or the junction. Trinary partitioned black-burst-based broadcast protocol (3P3B) [23] is a trinary partitioning broadcast method. Improving on BPAB, 3P3B uses a trinary partitioning method instead of the binary partitioning, and introduces mini-DIFS in the channel access period before the start of relay-node selection to reduce the channel access delay. With these improvements, it achieves a lower delay than BPAB, but it only considers the relay-node selection in straight road scenarios. Exponent-based partitioning broadcast protocol (EPBP) [24] is an exponential partitioning broadcast method. Improving on 3P3B, it divides the communication range of sender into \(N_{\text{part}}\) segments for \(N_{\text{iter}}\) iterations. The width of segment increases exponentially with the increase of its distance from the relay-node's optimal position. Then, a non-empty segment closest to the optimal position is selected as the final segment. Finally, a node in the final segment is randomly selected as the relay-node through an exponential back-off method. The delay of the partitioning process is called partition delay, and the delay of the exponential back-off process is called contention delay. Due to the exponential partition, EPBP has a lower and more stable delay than 3P3B.