中文摘要：

针对无人飞行器Ad hoc网络的容错设计需求,采用增加中继节点的方法实现。在二维平面同构网络中,将容错问题转化为边长受限条件下最少数量Steiner点的Steiner树问题。提出了两种基于最小成本子图的中继节点配置算法,以求解最少数量的中继节点及其位置,使改变后的网络拓扑图为顶点2-连通,实现容错。第一种为多项式时间的8-近似算法;第二种为随机近似算法,采用文化基因算法,搜索需要新增加的最小成本强化边组合。仿真结果表明了所提算法的有效性,当网络规模较小和中等时,随机近似算法得到的中继节点数量较少,平均情况下性能较优。

英文摘要：

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.