Improvement of Dependable Access Point Allocation Algorithm and Introduction of Route Availability for Wireless Mesh Networks

摘要

As a scalable, flexible, and inexpensive network, we have studied the wireless Internet-access mesh net­work (WIMNET) that is composed of multiple access points (APs) connected by the wireless distribution system (WDS). Previously, we have proposed the AP allocation algorithm, and its dependability extensions such that one link fault or one AP fault does not impair the connectivity of the network. In this paper, we improve this heuristic algorithm by adding the improvement stage using the local search method. Besides, we introduce the route avail­ability (RA) index to estimate the certainty of connections between hosts and the Internet gateway. We verify the effectiveness of our proposal through simulations in two instances.%本グループでは，低コストで柔軟なインターネットアクセス通信路として，WDSによる無線通信で接続された複数のアクセスポイント（AP：Access Point）で構成される無線メッシュネットワークWIMNET（Wireless Internet-access Mesh NETwork）の研究を進めている．これまで，WIMNETのAP配置アルゴリズムと，1リンクまたは1APの故障時にもネットワーク接続性を保証するためのアルゴリズム拡張を提案してきた．本論文では，まず，局所探索法を用いた解改善段階の追加による拡張AP配置アルゴリズムの改善を行う．次に，ネットワーク接続性の確からしさを評価する経路可用度（RA）の概念を導入する．2種類の例題車用いたシミュレーションにより，本提案の有効性を示す．