The Ad Hoc On-Demand Distance Vector (AODV) routing protocol is a classical protocol in wireless ad hoc networks and is widely used in wireless communication scenarios such as Flying Ad-Hoc Networks (FANET). The traditional AODV routing protocol uses broadcasting to forward route control messages in the route discovery phase, which is prone to causing broadcast storms, thus affecting the network performance. To address this issue, this paper proposes an enhanced AODV routing protocol based on the K-means +  + algorithm, which adopts a probabilistic approach to select the initial clustering centers in a decentralized manner and uses three clustering features, namely, the distance between nodes, the idle length of the packet queue, and the number of nodes' neighbors to classify Unmanned Aerial Vehicle (UAV) nodes, so that the nodes will comprehensively select the best node class among their neighbors for route discovery, in order to reduce the number of unnecessary route request packet forwarding. Simulation results show that the proposed protocol is well-suitable for the FANET environment in terms of combined data delivery rate, end-to-end delay, delay jitter, and network energy consumption.