Abstract:

One approach to realize the fault tolerant unmanned aerial vehicle (UAV) Ad hoc network is to deploy the number of relay nodes. In the 2-dimensional plane homogeneous network, this problem is modeled by an NP hard network optimization problem named Steiner tree problem with minimum number of Steiner points and bounded edge length (STP-MSPBEL). Two relay node placement algorithms based on the minimum cost spanning subgraph of a complete graph are proposed to get the smallest number of additional relay nodes and their locations,then the induced topology graph is vertexbiconnected. The first one is a polynomial time 8-approximation algorithm. And the second one is a random approximation algorithm, in which the memetic algorithm  is developed to get a cheapest possible set of additional edges. Simulation results show that the proposed algorithms are effective and the average relay nodes required in the second algorithm is less than that in the first one when the network scale is small or middle.