系统工程与电子技术
繫統工程與電子技術
계통공정여전자기술
SYSTEMS ENGINEERING AND ELECTRONICS
2012年
1期
179-184
,共6页
陈凌%梁加红%胡志伟%吴冰
陳凌%樑加紅%鬍誌偉%吳冰
진릉%량가홍%호지위%오빙
无人飞行器%Ad hoc网络%容错%Steiner树问题
無人飛行器%Ad hoc網絡%容錯%Steiner樹問題
무인비행기%Ad hoc망락%용착%Steiner수문제
针对无人飞行器Ad hoc网络的容错设计需求,采用增加中继节点的方法实现.在二维平面同构网络中,将容错问题转化为边长受限条件下最少数量Steiner点的Steiner树问题.提出了两种基于最小成本子图的中继节点配置算法,以求解最少数量的中继节点及其位置,使改变后的网络拓扑图为顶点2-连通,实现容错.第一种为多项式时间的8-近似算法；第二种为随机近似算法,采用文化基因算法,搜索需要新增加的最小成本强化边组合.仿真结果表明了所提算法的有效性,当网络规模较小和中等时,随机近似算法得到的中继节点数量较少,平均情况下性能较优.
針對無人飛行器Ad hoc網絡的容錯設計需求,採用增加中繼節點的方法實現.在二維平麵同構網絡中,將容錯問題轉化為邊長受限條件下最少數量Steiner點的Steiner樹問題.提齣瞭兩種基于最小成本子圖的中繼節點配置算法,以求解最少數量的中繼節點及其位置,使改變後的網絡拓撲圖為頂點2-連通,實現容錯.第一種為多項式時間的8-近似算法；第二種為隨機近似算法,採用文化基因算法,搜索需要新增加的最小成本彊化邊組閤.倣真結果錶明瞭所提算法的有效性,噹網絡規模較小和中等時,隨機近似算法得到的中繼節點數量較少,平均情況下性能較優.
침대무인비행기Ad hoc망락적용착설계수구,채용증가중계절점적방법실현.재이유평면동구망락중,장용착문제전화위변장수한조건하최소수량Steiner점적Steiner수문제.제출료량충기우최소성본자도적중계절점배치산법,이구해최소수량적중계절점급기위치,사개변후적망락탁복도위정점2-련통,실현용착.제일충위다항식시간적8-근사산법；제이충위수궤근사산법,채용문화기인산법,수색수요신증가적최소성본강화변조합.방진결과표명료소제산법적유효성,당망락규모교소화중등시,수궤근사산법득도적중계절점수량교소,평균정황하성능교우.
