A Method for Distributed Computaion of Semi-optimal Multicast Tree for Efficient Video Distribution in MANET

モバイルアドホックネットワーク（MANET）上でビデオなどのマルチメディアデータをストリーミング配信するため，遅延や帯域幅などの複数のQoS に関する制約を満たすマルチキャスト木を動的に構築する手法が研究されている．MANET 上のマルチキャスト木構築は，QoS の制約だけでなく，経路の安定性，省電力など，様々な目的に対する最適性を同時に考慮できることが望ましい．最適なマルチキャスト木を求める問題はNP 困難であるため，近似解法として遺伝的アルゴリズム（GA）を用いる方法が提案されている．しかし，既存手法は，集中制御方式に基づいており，移動ノードの計算資源および通信資源の点で，大規模なMANET に適用するのは困難であった．本論文では，省電力性や通信の安定性など任意に指定した目的に対し，準最適なマルチキャスト木をMANET 上の複数のノードで分散して計算し構築するGA ベースの手法を提案する．提案手法では，MANET を複数のクラスタに分割し，各クラスタ内およびクラスタ間の2 階層でそれぞれ配送経路を算出し，それらを組み合わせてマルチキャスト木とすることにより，スケーラビィリティを高める工夫を行っている．提案手法をネットワークシミュレータ上に実装し，既存手法の1 つであるAQM（Ad Hoc Quality of Service Multicast Routing）と比較し，提案手法の優位性を示す．In order to realize multi-media streaming in mobile ad hoc network (MANET), a number of studies on dynamically constructing a multicast tree which satisfies multiple QoS restrictions such as bandwidth and delay, have been proposed. For construction of a multicast tree on MANET, it is desirable to take into account optimality of the tree in terms of communication stability, power consumption and so on. The problem to calculate an optimal multicast tree is known to be NP-hard. So, some existing studies propose algorithms based on genetic algorithms (GAs) to find a semi-optimal tree in practical time. However, since these existing methods adopt centralized mechanisms, they cannot be applied to large MANETs due to both communication and computation costs. In this paper, we propose a new method for MANET to dynamically construct a semi-optimal multicast tree which satisfies given QoS restrictions, for a given objective (e.g., communication stability and power consumption), by utilizing distributed computation of the tree based on GAs. In order to increase scalability, our proposed method constructs multiple clusters in MANET, and calculates a tree spanning all clusters and paths spanning nodes in each cluster by executing GA in some nodes selected in MANET. A multicast tree is constructed by grafting paths of all clusters on inter-cluster tree. Through experiments using network simulator, we confirmed that our method outperforms AQM (Ad Hoc Quality of Service Multicast Routing) in some objectives