EKR: An Efficient K-anycast Routing in UAV Networks

Abstract

K-anycast refers to a communication model where a message is transmitted from a source to k destinations. Compared to multicast and unicast, k-anycast offers significant advantages in terms of load balancing, redundancy, and improved reliability. As far as we know, there is currently no research on k-anycast for UAV networks. We propose an Efficient K-anycast Routing scheme called EKR. The high dynamism of UAV networks poses a challenge in formalizing and addressing the k-anycast problem. Therefore, this paper utilizes predetermined trajectory information to construct Encounter Record Tree (ER-Tree), which converts dynamically changing network topologies into a static graph. Based on ER-Tree, we formalize the k-anycast problem in UAV networks and transform it into a Group Steiner Tree problem, which is known to be NP-hard. Then an efficient search algorithm is proposed to solve it and find the transmission path. To evaluate the performance of EKR, we performed simulations with the One simulator. The results demonstrate that EKR outperforms existing protocols in terms of delivery rate, end-to-end delay, and network overhead.