Journal of Systems Engineering and Electronics ›› 2012, Vol. 34 ›› Issue (1): 179-184.doi: 10.3969/j.issn.1001-506X.2012.01.33
陈凌1, 梁加红1, 胡志伟1, 吴冰2
CHEN Ling1, LIANG Jiahong1, HU Zhiwei1, WU Bing2
摘要:
针对无人飞行器Ad hoc网络的容错设计需求,采用增加中继节点的方法实现。在二维平面同构网络中,将容错问题转化为边长受限条件下最少数量Steiner点的Steiner树问题。提出了两种基于最小成本子图的中继节点配置算法,以求解最少数量的中继节点及其位置,使改变后的网络拓扑图为顶点2-连通,实现容错。第一种为多项式时间的8-近似算法;第二种为随机近似算法,采用文化基因算法,搜索需要新增加的最小成本强化边组合。仿真结果表明了所提算法的有效性,当网络规模较小和中等时,随机近似算法得到的中继节点数量较少,平均情况下性能较优。