计算机技术与发展
計算機技術與髮展
계산궤기술여발전
COMPUTER TECHNOLOGY AND DEVELOPMENT
2007年
7期
17-20
,共4页
自组网%极小连通支配集%独立集
自組網%極小連通支配集%獨立集
자조망%겁소련통지배집%독립집
自组网通过节点的自组织,构造成一种不需要任何基础设施的新型无线网络,基于连通支配集算法的虚拟主干网技术对于自组网的路由优化、能量保护和资源分配具有重要的作用.针对现有的连通支配集法存在的不足,基于图着色思想提出一种新的极小连通支配集构造算法CB-MCDS(Coloring Based-Minimum Connected Dominating Set).CB-MCDS算法仅需要一跳邻居节点的拓扑信息,就能快速地构造出虚拟主干网,理论分析表明整个算法的时间和消息复杂度分别为O(△)和O(n△),该性能明显优于已有的算法.
自組網通過節點的自組織,構造成一種不需要任何基礎設施的新型無線網絡,基于連通支配集算法的虛擬主榦網技術對于自組網的路由優化、能量保護和資源分配具有重要的作用.針對現有的連通支配集法存在的不足,基于圖著色思想提齣一種新的極小連通支配集構造算法CB-MCDS(Coloring Based-Minimum Connected Dominating Set).CB-MCDS算法僅需要一跳鄰居節點的拓撲信息,就能快速地構造齣虛擬主榦網,理論分析錶明整箇算法的時間和消息複雜度分彆為O(△)和O(n△),該性能明顯優于已有的算法.
자조망통과절점적자조직,구조성일충불수요임하기출설시적신형무선망락,기우련통지배집산법적허의주간망기술대우자조망적로유우화、능량보호화자원분배구유중요적작용.침대현유적련통지배집법존재적불족,기우도착색사상제출일충신적겁소련통지배집구조산법CB-MCDS(Coloring Based-Minimum Connected Dominating Set).CB-MCDS산법부수요일도린거절점적탁복신식,취능쾌속지구조출허의주간망,이론분석표명정개산법적시간화소식복잡도분별위O(△)화O(n△),해성능명현우우이유적산법.
