学位の名称

Admir Barolli
博士（工学）

学位番号

博（二）第２号

学位授与年月日

平成２４年３月２０日

学位被授与者氏名

論文題目
論文題目（英訳または和訳）
論文審査委員Application of Genetic Algorithms for Mobile Ad-hoc Networks and Wireless Mesh
Networks
無線アドホック・ネットワークと無線メッシュ・ネットワークのための遺伝的アルゴリ
ズムの応用
論文審査委員会
委員主査 ：福岡工業大学大学院知能情報システム工学専攻教授
同審査委員：福岡工業大学大学院知能情報システム工学専攻教授
同審査委員：福岡工業大学大学院知能情報システム工学専攻教授
同審査委員：福岡工業大学大学院物質生産システム工学専攻教授

内田一徳
松永利明
西田茂人
ｽｳｰﾁｭ･ｸﾗｳﾃﾞﾕ･ｳﾞｧﾚﾝﾃｨﾝ

論文審査機関福岡工業大学大学院工学研究科

論文内容の要旨（和文）

本論文では，無線アドホック・ネットワークの QoS 経路制御と無線メッシュ・ネットワークにおけるメッシュノード配置のための遺伝的アルゴリズムの応用について議論している．一般に，無線アドホック・ネットワークの多くの経路制御手法は，ベストエフォート・トラフィックにおける解決策となっている．しかし接続におけるサービス品質（QoS）要件として，音声チャネルで用いられるような遅延時間と帯域幅の制約は考慮されていない．QoS を考慮した経路制御はますます注目されてきているが，多くの評価指標を考慮した最短経路の探索は NP 完全問題となるので，マルチパス制約の QoS 経路制御には，近似解とヒューリスティック・アルゴリズムを採用する必要がある．また経路制御手法は適応力に富み，かつ柔軟で知的でなければならない．そこで本論文では，無線アドホック・ネットワークの QoS ルーティングに対して，遺伝的アルゴリズム（GA）と多目的最適化の手法を用いている．
無線メッシュ・ネットワークでは，いくつかの最適化問題が提案されている．これらはネットワークの接続性，範囲及び安定性の最適化に関連している．この問題を解決しておくことは，ネットワーク性能の最適化にとって極めて重要である．無線メッシュ・ネットワークの場合，この問題にはネットワーク性能の最適化に必要なメッシュ・ルータ・ノード配置の計算が含まれる．しかし，これらの最適化問題を解決するのは困難である．そこで最近では，効果的な解決方法として GA を用いることが検討されている．
この論文では，GAMAN と呼ぶ GA を用いた無線アドホック・ネットワークのためのシミュレーション・システムを実装すると共に，無線メッシュ・ネットワークのためのWMN-GA と呼ばれるシミュレーション・システムも実装した．そこで実装したシミュレーションによって，提案したヒューリスティック手法の性能評価を行った．その結果，従来の GAMNA-1 と GLBR アルゴリズムとの比較によって，提案する GAMAN が無線アドホック・ネットワークにおける QoS 経路制御に対して有望なアルゴリズムであることを明らかにした．また，異なったクライアントとメッシュ・ルータの分布及び異なった GA 操作を用いることによって，提案した WMN-GA システムの評価を行った．その結果，提案システムは無線メッシュ・ネットワークに対して非常に良いパフォーマンスを示すことが分かった．
本研究で実現できた主要な結果は，無線アドホック・ネットワークのための GAMANアルゴリズムの設計と実装，多目的最適化のための提案されたアプローチの拡張，無線メッシュ・ネットワークのメッシュ・ルータ配置問題のための WMN-GA システムの設計と実装，GAMAN のための遺伝子コーディング手法の提案，WMN-GA のための新しい GA 操作の提案，QoS 経路制御のための GAMAN の評価及びノード配置問題のためのWMN-GA 手法の評価である．
論文の構成は次のようになる．第1章では、論文の背景、目的、および概要を紹介する．第2章では，遺伝的アルゴリズムについて説明する．第3章では，無線ネットワークについて紹介する．第4章では，遺伝的アルゴリズムに基づいたGAMANアルゴリズムについて述べる． 第5章では、提案したWMN-GAシステムについて説明する．第6章では、GAMANアルゴリズムの評価について議論する．第7章では、WMN-GAシステムの評価

論文内容の要旨（英文）

論文審査結果について議論する．第8章では、本研究の結論と今後の研究について述べる．
In this thesis, we consider application of Genetic Algorithms (GAs) for QoS Routingin Mobile Ad-hoc Networks (MANETs) and node placement in Wireless Mesh
Networks (WMNs). In general, most of routing solutions in MANETs deal with thebest effort data traffic. Connections with Quality of Service (QoS) requirements, suchas voice channels with delay and bandwidth constraints, are not supported. The QoS
routing has been receiving increasingly intensive attention, but searching for theshortest path with many metrics is an NP-complete problem. For this reason,
approximated solutions and heuristic algorithms should be developed for multi-path
constraints QoS routing. Also, the routing methods should be adaptive, flexible, andintelligent. For this reason, we use Genetic Algorithms (GAs) and Multi-objective
Optimization for QoS routing in MANETs.
In WMNs, several optimization problems are appearing. Such problems are related
to optimizing network connectivity, coverage and stability. The solution of theseproblems turns out to be crucial for optimized network performance. In the case ofWMNs, such problems include computing placement of mesh router nodes so that
network performance is optimized. However, as these optimization problems areknown to be computationally hard to solve, GAs have been recently investigated aseffective resolution methods.
We have implemented a simulation system for ad-hoc networks using GA called
GAMAN and another simulator for mesh networks called WMN-GA. We evaluate theperformance of proposed heuristic methods by computer simulations. We evaluatedGAMAN and we have shown that the GAMAN algorithm has better behavior thanprevious GAMAN-1 and GLBR algorithms and is a promising algorithm for QoS
routing in MANETs. We also evaluate the performance of the proposed WMN-GA
system by using different distributions of client and mesh routers and different GAoperators. We found that the proposed system has a very good behavior.
Our work has the following contributions: design and implementation of GAMAN
algorithm for ad-hoc networks; extension of proposed approach for multi-objectiveoptimization; design and implementation of WMN-GA system for mesh routerplacement problem in WMNs, propose a ne gene coding method for GAMAN;
proposed new GA operators for WMN-GA; evaluation of GAMAN for QoS Routing;and evaluation of WMN GA-based method for node placement problem.
The thesis is organized as follows. In Chapter 1, we introduce the background, thepurpose and the outline of this thesis. In Chapter 2, we present an overview of GAs.
In Chapter 3, we provide an introduction for wireless networks. Chapter 4 introduces
our proposed QoS routing method for MANETs. Chapter 5 presents application of GAfor WMNs. In Chapter 6, we give evaluation results for MANETs. In Chapter 7, wepresent the evaluation results for WMNs. Chapter 8 concludes this thesis. We givethe conclusions and future work.
本論文では，無線アドホック・ネットワークのサービス品質（QoS）経路制御と無線メッシュ・ネットワークにおけるメッシュノード配置のための遺伝的アルゴリズムの応用について研究を行っている．これまで無線アドホック・ネットワークの経路制御については，ベストエフォート・トラフィック手法に基づいて解決策を論じる場合がほとんどで，接続の要件としてQoSを考慮することはなかった．QoSを考慮した場合，多くの評価指標に基づいて最短経路を探索しなければならず，この問題はNP完全問題となる．その結果，近似解とヒューリスティック・アルゴリズムが重要となるが，経路制御手法には適応力，柔軟性と知的処理能力が必要とされる．そこで本研究では，無線アドホック・ネットワークのQoSルーティングに対して，遺伝的アルゴリズム（GA）と多目的最適化を用いている．また無線メッシュ・ネットワークに対しては，ネットワークの接続性と範囲及びその安定性について多くの研究報告がなされ，またいくつかの最適化問題も提案されている．特に無線メッシュ・ネットワークの場合，ネットワークの性能向上のための最適化を行うためには，メッシュ・ルータ・ノードの最適配置が重要となる．しかし，

これらの最適化問題を解決するのは一般に困難であるため，効果的な解決方法として，本研究ではGAを用いて検討している．
本研究では，GAMANとWMA-GAシステムを提案し，実装も行っている．シミュレーションによって，提案したヒューリスティック手法の性能評価を行った．従来のGAMNA-1とGLBRアルゴリズムとの比較によって，GAMANが無線アドホック・ネットワークにおけるQoS経路制御のための有望なアルゴリズムであることを明らかにした．また，異なったクライアントとメッシュ・ルータの分布や異なったGA操作を用いることによって，提案した
WMN-GAシステムの評価も行った．その結果，提案システムが非常に良いパフォーマンスを示すことができた．このように本研究の成果は，次のように多岐に亘っている．すな
わち，無線アドホック・ネットワークのためのGAMANアルゴリズムの設計と実装，多目的最適化のための提案されたアプローチの拡張，無線メッシュ・ネットワークのメッシュ・ルータ配置問題のためのWMN-GAシステムの設計と実装，GAMANのための遺伝子コーディング手法の提案，WMN-GAのための新しいGA操作の提案，QoS経路制御のためのGAMANの評
価，さらにはノード配置問題のためのWMN-GA手法の評価である．このように本研究の内容は、他の研究者によって報告されていない多くの研究結果を含んでおり，学位論文として十分な価値があると認められる．
論文の構成は次のようになる．第1章では，論文の背景，目的及び概要を紹介する． 第2章では，遺伝的アルゴリズムについて説明する．第3章では，無線ネットワークについて紹介する．第4章では，遺伝的アルゴリズムに基づいたGAMANアルゴリズムについて述べる．第5章では，提案したWMN-GAシステムについて説明する． 第6章では，GAMANアルゴリズムの評価について議論する．第7章では，WMN-GAシステムの評価について紹介する．第8章では，本研究の結論と今後の課題について述べる．
本研究の成果として，学術論文が１１編（第１著者６編），国際会議が１７編（第１著者６編）となっている．また，国際会議BWCCA-2011ではBest Paper賞を受賞しており，本研究の新規性と有用性及び国際性が認められる．以上の理由により，審査委員会は論文提出が学位論文の内容として適合すると判定した．
学位論文公聴会においては、論文内容に関連する種々の工学的及び技術的な質問があったが，いずれも適切に回答を行うことができた．また公聴会後の最終試験においては，学位論文に関連する分野の学識を有し，今後研究を進めていくための研究能力を備えていることが判明した．
以上の結果から，学位審査委員会はこの論文が博士（工学）の学位に適格であると判主な研究業績定した．
参考論文

２８編１冊

（学術論文）
1. A. Barolli, M. Takizawa, F. Xhafa, L. Barolli, “Application of Genetic Algorithms
for QoS Routing in Mobile Ad-Hoc Networks: Approaches and Solutions”,
International Journal of Business Intelligence and DataMining (IJBIDM), Vol. 6,
No. 3, pp. 215-236, 2011.
2. F. Xhafa, A.Barolli, C. S`anchez, L. Barolli, “Simulated Annealing Algorithm for
Router Nodes Placement Problem in Wireless Mesh Networks”, Simulation
Modelling Practice and Theory (SIMPAT), Elsevier, Vol Vol. 19. pp. 2276-2284,
2011.
3. S. Sawamura, A. Barolli, A. Aikebaier, T. Enokido, M. Takizawa, “Design andEvaluation of Algorithms for Obtaining Objective Trustworthiness on
Acquaintances in Peer-to-Peer (P2P) Overlay Networks”, International Journal ofGrid and Utility Computing (IJGUC), Inderscience, Vol. 2. No. 3, pp. 196-203,

2011.
4. A. Barolli, E. Spaho, L. Barolli, F. Xhafa, M. Takizawa, “QoS Routing in Ad-Hoc
Networks Using GA and Multi-Objective Optimization“, Mobile Information
Systems(MIS), IOS Press, Vol. 7, No. 3, pp. 169-188, 2011.
5. A. Barolli, F. Xhafa, C. S`anchez, M. Takizawa, “A Study on the Performance ofLocal Search vs. Population-based Methods for Mesh Router PlacementProblem”, In Press, Journal of Intelligent Manufacturing, Journal of Intelligent,Manufacturing, DOI: 10.1007/s10845-011-0507-7, 2011.
6. A. Barolli, F. Xhafa, Ch. S`anchez, M. Takizawa, “A Study on the Effect ofMutation in Genetic Algorithms for Mesh Router Placement Problem in Wireless
Mesh Networks”, Accepted, To appear in International Journal of Computer
Systems Science and Engineering (IJCSSE), 2012.
7. A. Barolli, M. Takizawa, T. Oda, E. Spaho, L. Barolli, K. Uchida, F. Xhafa,“Performance Evaluation of WMN-GA Simulation System for Different Settingsof Genetic Operators Considering Giant Component and Number of CoveredUsers”, Accepted, To Appear in International Journal of Distributed Systems andTechnologies (IJDST), 2012.
8. T. Oda, A. Barolli, F. Xhafa, L. Barolli, M. Ikeda, M. Takizawa, “WMN-GA: A
Simulation System for WMNs and Its Evaluation Considering Selection
Operators“, Accepted, To Appear in Journal of Ambient Intelligence andHumanized Computing (JAIHC), Springer, 2012.
9. T. Oda, A. Barolli, E. Spaho, F. Xhafa, L. Barolli, M. Takizawa, “Evaluation ofWMN-GA for Different Mutation Operators”, Accepted, To Appear inInternational Journal of Space-Based and Situated Computing (IJSSC),
Inderscience, 2012.
10. T. Oda, A. Barolli, F. Xhafa, L. Barolli, M. Ikeda, M. Takizawa, “Performance
Evaluation of WMN-GA for Different Mutation and Crossover Rates Considering
Number of Covered Users Parameter”, Accepted, To Appear in Mobile
Information Systems (MIS), IOS Press, 2012.
11. A. Barolli, T. Oda, F. Xhafa, L. Barolli, M. Takizawa, K. Uchida, “Evaluation ofWMN-GA for Different Mutation and Crossover Rates Considering GiantComponent Parameter”, Accepted, To Appear in Journal of Interconnection
Networks, World Scientific Publishing, 2012.
（国際会議論文）
1. F. Xhafa, C. Sanchez, A. Barolli, R. Miho, L. Barolli, M. Takizawa, “TuningOperators of Genetic Algorithms for Mesh Routers Placement Problem inWireless Mesh Networks”, Proc. of BWCCA-2010, Fukuoka, Japan, pp. 80-87,November 2010.
2. A. Barolli, M. Takizawa, F. Xhafa, L. Barolli, “Application of Genetic Algorithms
for QoS Routing in Mobile Ad Hoc Networks: A Survey”, Proc. of BWCCA-2010,Fukuoka, Japan, pp. 250-259, November 2010.

3. S. Sawamura, A. Barolli, A. Aikebaier, V. Barolli, M. Takizawa, “Two Types ofTrustworthiness of Acquaintances in Peer-to-Peer (P2P) Overlay Networks”,
Proc. of BWCCA-2010, Fukuoka, Japan, pp. 320-327, November 2010.
4. L. Barolli, Gj. Mino, T. Ikebata, A. Barolli, F. Xhafa, M. Takizawa, “PerformanceEvaluation and Comparison of Fuzzy-based Intelligent CAC Systems for Wireless
Cellular Networks”, Proc. of IEEE INCoS-2010, Thessaloniki, Greece, pp.
177-184, November 2010.
5. S. Sawamura, A. Barolli, A. Aikebaier, M. Ikeda, M. Takizawa, “ObjectiveTrustworthiness of Acquaintances in Peer-to-Peer (P2P) Overlay Networks”,
Proc. of IEEE AINA-2011, Singapore, pp. 167-174, March 2011.
6. A. Barolli, F. Xhafa, C. S`anchez, M. Takizawa, “A Study on the Performance ofSearch Methods for Mesh Router Nodes Placement Problem”, Proc. of IEEE
AINA-2011, Singapore, pp. 756-763, March 2011.
7. A. Barolli, F. Xhafa, C. S`anchez, M. Takizawa, “A Study on the Effect of Mutationin Genetic Algorithms for Mesh Router Placement Problem in Wireless MeshNetworks”, Proc. of CISIS-2011, Seoul, Korea, pp. 32-39, June-July 2011.
8. T. Oda, A. Barolli, E. Spaho, F. Xhafa, L. Barolli, M. Takizawa, “A GA-based
System for WMN and Its Performance Evaluation for Different Scenarios”, Proc.
of CISIS-2011, Seoul, Korea, pp.402-408, June-July 2011.
9. A. Barolli, E. Spaho, L. Barolli, F. Xhafa, M. Takizawa, “Application of GA andMulti-Objective Optimization for QoS Routing in Ad-hoc Networks”, Proc. ofNBiS-2011, Tirana, Albania, pp. 50-59, September 2011.
10. A. Barolli, F. Xhafa, M. Takizawa, “Optimization Problems and ResolutionMethods for Node Placement in Wireless Mesh Networks”, Proc. of NBiS-2011,Tirana, Albania, pp. 126-134, September 2011.
11. T. Oda, A. Barolli, E. Spaho, F. Xhafa, L. Barolli, M. Takizawa, “PerformanceEvaluation of WMN Using WMN-GA System for Different Mutation Operators”,
Proc. of NBiS-2011, Tirana, Albania, pp. 400-406, September 2011.
12. A. Barolli, T. Oda, E. Spaho, F. Xhafa, L. Barolli, M. Takizawa, “Effects ofMutation and Crossover in Genetic Algorithms for Node Placement in WMNConsidering Giant Component Parameter”, Proc. of BWCCA-2011, Barcelona,
Spain, pp.18-25, October 2011.
13. F. Xhafa, C. Christian Sanchez, A. Barolli, M. Takizawa, "A Tabu SearchAlgorithm for Efficient Node Placement in Wireless Mesh Networks", Proc. ofIEEE INCoS-2011, Fukuoka, Japan, pp. 53-59, November-December 2011.
14. T. Oda, A. Barolli, E. Spaho, F. Xhafa, L. Barolli, "Effects of Mutation andCrossover in Genetic Algorithms for Node Placement in WMNs Considering
Number of Covered Users Parameter", Proc. of IEEE INCoS-2011, Fukuoka,
Japan, pp. 188-195, November-December 2011.
15. L. Barolli, E. Spaho, T. Oda, A. Barolli, F. Xhafa, M. Takizawa, “PerformanceEvaluation for Different Settings of Crossover and Mutation Rates ConsideringNumber of Covered Users: A Case Study”, accepted in Proc. of MoMM-2011, Ho
Chin Minh City, Vietnam, pp. 110-115, December 2011.
16. T. Oda, A. Barolli, E. Spaho, F. Xhafa, L. Barolli, M. Takizawa, K. Uchida, “Effectof Population Size for Node Placement in WMNs Considering Giant Component
and Number of Covered Users Parameters”, Accepted, To appear in Proc. of IEEE
AINA-2012, Fukuoka, Japan, March 2012.
17. F. Xhafa, J. Sun, A. Barolli, M. Takizawa, K. Uchida, “Evaluation of GeneticOperators of a GA for Ground Station Scheduling”, Accepted, To appear in Proc. ofIEEE AINA-2012, Fukuoka, Japan, March 2012.