アドホックネットワークにおける信頼性を考慮したトポロジ構築に関する検討

摘要

Several tree based algorithms to transmit information efficiently have been proposed. But in the case of a single link failure, a normal network based on a tree structure is split into two parts and the information is not reachable by some nodes. To avoid this problem, Tree-based Reliable Topology (TRT) has been proposed. It overcomes the reliability problem by using multiplex paths which conbines Minimum Spanning Trees (MSTs). But some modifications must be made to apply MST or TRT to an ad hoc network because it is difficult to know the global knowledge of the network. And so, an improved algorithm of MST, called Local MST (LMST), has been proposed. In this paper, we present the Local TRT(LTRT) algorithm that gurantees multiplex paths in ad hoc networks.%効率的な情報伝達のために，木構造に基づくネットワークを構築する手法がある．通常の木構造ではリンクが切断された時に，ネットワークの連結性が失われてしまう可能性がある．この間題を回避する手法として，TRT（Tree-based Reliable Topology）が提案されている．これは複数個のMST（Minimum Spanning Tree）の組合せにより，多重化された経路を保証して信頼性を確保する手法である．アドホックネットワークにおいては，各ノードが，ネットワーク全体にわたる他のノードの位置やリンク状況を把握するのが困難であり，MSTやTRTの適用には改良が必要である．現在，MSTの改良手法としてLMST（Local MST）が提案されている．そこで本稿では，アドホックネットワークで多重化された経路を保証する為に，LMSTを応用したLTRT（Local TRT）を提案する．