计算机科学
計算機科學
계산궤과학
COMPUTER SCIENCE
2012年
3期
83-87
,共5页
贺毅朝%田海燕%张新禄%高锁刚
賀毅朝%田海燕%張新祿%高鎖剛
하의조%전해연%장신록%고쇄강
Ad-hoc网络%极大独立集%相邻矩阵%贪心策略%连通支配集
Ad-hoc網絡%極大獨立集%相鄰矩陣%貪心策略%連通支配集
Ad-hoc망락%겁대독립집%상린구진%탐심책략%련통지배집
在无线Ad-hoc网络中,基于极小连通支配集的虚拟主干网技术对资源分配和路由优化具有重要的作用.首先证明了相邻矩阵理论的一个有关结论,然后利用此结论以及极大独立集和极小支配集的关系,提出了一种基于相邻矩阵快速构建无线Ad-hoc网络最小连通支配集的近似算法,并给出了算法的正确性证明、复杂性分析和近似比分析.仿真试验结果表明,利用该算法可以快速高效地构建Ad-hoc网络的虚拟主干网.
在無線Ad-hoc網絡中,基于極小連通支配集的虛擬主榦網技術對資源分配和路由優化具有重要的作用.首先證明瞭相鄰矩陣理論的一箇有關結論,然後利用此結論以及極大獨立集和極小支配集的關繫,提齣瞭一種基于相鄰矩陣快速構建無線Ad-hoc網絡最小連通支配集的近似算法,併給齣瞭算法的正確性證明、複雜性分析和近似比分析.倣真試驗結果錶明,利用該算法可以快速高效地構建Ad-hoc網絡的虛擬主榦網.
재무선Ad-hoc망락중,기우겁소련통지배집적허의주간망기술대자원분배화로유우화구유중요적작용.수선증명료상린구진이론적일개유관결론,연후이용차결론이급겁대독립집화겁소지배집적관계,제출료일충기우상린구진쾌속구건무선Ad-hoc망락최소련통지배집적근사산법,병급출료산법적정학성증명、복잡성분석화근사비분석.방진시험결과표명,이용해산법가이쾌속고효지구건Ad-hoc망락적허의주간망.
