哲也（Tetsuya Oda）

学位被授与者氏名

小田

学位の名称

博士（工学）

学位番号

博（一）第４６号

学位授与年月日

平成２８年３月２０日

論文題目
論文題目
（英訳または和訳）
論文審査委員

Implementation of Simulation Systems and Testbed for WMNs: Simulation andExperimental Results
無線メッシュネットワークのためのシミュレーションシステムとテストベッドの実装：
シミュレーションと実験結果
論文審査委員会
委員主査 ：福岡工業大学大学院知能情報システム工学専攻教授
同審査委員：福岡工業大学大学院知能情報システム工学専攻教授
同審査委員：福岡工業大学大学院知能情報システム工学専攻准教授
同審査委員：福岡工業大学大学院物質生産システム工学専攻教授

ﾊﾞﾛﾘﾚｵﾅﾙﾄﾞ
西田 茂人
池田誠
朱世杰

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

論文内容の要旨（和文）

無線メッシュネットワーク（WMN）はインフラレスでネットワークを構築する事が可能なアーキテクチャである。WMN は無線ノードのみでネットワークを形成するため、トポロジは刻々と変化する。そのため、フロー制御、ルーティング、キュー管理の性能向上に関する研究は重要である。これらの研究を行うに当たり、アルゴリズムやプロトコルの問題を検証するための手法は、大きく分けてシミュレータ、エミュレータ、テストベッドに分類される。
WMN における課題点は多く存在するが、中でも、スループット性能、ルーティング効率、エネルギー消費量は、アドホックネットワークでも頻繁に扱われる重要な問題である。加えて、将来の WMN 技術はセキュリティ及びスケーラビリティを確保し、分散協調コンピューティングのためのバックボーンを提供する必要がある。
そこで本論文では、WMN における通信性能改善のために、様々なメタヒューリスティクス手法、異なるアーキテクチャ、ルーティングプロトコル、キュー管理アルゴリズム、モビリティモデルを考慮した環境でのシミュレーションシステム及びテストベッドの実装を行った。シミュレーション及び実験結果より、ノードの移動が通信性能におけるデグラデーションや経路の不安定性をもたらすことを明らかにした。また、複数フローの通信時には、ネットワークの性能が低下した。
本研究は次のような特色と独創的な点を有しており科学技術の貢献が期待できる。１) 様々なメタヒューリスティクス手法を用いたメッシュルータ配置最適化手法の提案と評価、２）ns3 を用いた WMN のシミュレーションシステムの実装、３）Raspberry Pi に基づく WMN テストベッドの実装と評価、４）様々なシナリオを考慮したシミュレーション及び実験、５）WMN テストベッドにおける異なる OS の評
価、６）WMN テストベッドを用いた分散型並行処理の評価、７）本研究の結果から、今後の無線通信の技術の発展のための WMN の統合についての見識を与える。
以下に論文の構成を示す。第１章では、研究背景と目的を述べている。第2章では、無線ネットワークの一般的な技術を紹介する。無線ネットワークの構造とその長所と短所を示しながら無線技術を議論する。第3章では、WMNの問題点を議論し、ルーティングプロトコルとその詳細を述べる。第4章では、メタヒューリスティクス手法について述べ、遺伝的アルゴリズム（GAs）、禁錮探索法（TS）、山登り法（HC）及び焼き鈍し法（SA）について紹介する。第5章では、遺伝的アルゴリズムの詳細について述べる。第6章では、シミュレーションシステムの設計と実装について述べる。第7章では、我々のテストベッドの設計と実装について述べる。技術的な設定や環境の前提条件に関する詳細を提供する。また、テストベッドの実験シナリオについて説明する。第8章と第9章では、シミュレーションと実験の結果を議論する。第10章では、結論とこの分野における今後の課題の見識を与えて、論文をまとめる。
A Wireless Mesh Network (WMN) can be deﬁned as a collection of mobile nodes, which
form a highly resource constrained network and a dynamic topology. Because of the dynamictopology, routing procedures and protocols are a key field of testing and research. In a
research environment, research tools are required to test, verify and identify problems of analgorithm or protocol. These tools are classified in three major techniques: simulators,

論文内容の要旨（英文）論文審査結果

emulators and real-world testbeds.
In most of research in WMNs, their performance is evaluated in both quantitative andqualitative aspects. Throughput performance, routing efficiency, energy consumption aresome of the key issues that are addressed frequently on WMNs. The WMN technology has toensure a certain degree of security and scalability and provide the infrastructure for
distributed collaborative computing.
In this thesis, we design and implement simulation systems and a testbed in order toanalyse the performance of different routing protocols, architectures, OSs, queue
management algorithms and mobility models. From the evaluation results, we found that themobility of nodes brings oscillations in performance and route instabilities. We found thatmultiple flows traffic decreases the performance of the network.
The contributions of our work are: 1) implementation and evaluation of a different
meta-heuristics methods for mesh router node placement; 2) implementation of a simulation
tool for WMNs using NS3; 3) implementation and evaluation of a Raspberry Pi based WMN
testbed; 4) application of WMN testbed in real environments, considering different scenarios;5) evaluation of WMN testbed in different OSs; 6) evaluation of WMN testbed considering
distributed concurrent processing; 7) our research work give insights about future
developments and integration of WMNs as an important technology of wirelesscommunication.
The outline of the thesis is as follows. In Chapter 1 is shown the background and themotivation of the thesis. In Chapter 2, we introduce general aspects of wireless networks. We
discuss wireless architectures and wireless technologies giving advantages and disadvantages
for each of them. We present WMNs in Chapter 3. We discuss problems of WMNs anddescribe the routing protocols and their features. In Chapter 4, we introduce general aspectsof meta-heuristics methods. We present Genetic Algorithms (Gas), Tabu Search (TS), Hill
Climbing (HC) and Simulated Annealing (SA). We show in details the GA and its operators
in Chapter 5. The simulation systems are presented in Chapter 6. We give details of radio
propagation models, mobility models and other parameters. Then, we show different
scenarios and the traffic data that we used for simulations. In Chapter 7, we introduce theimplemented testbed. We give details of technical and environment settings. Then we show
the experimental scenarios. In Chapter 8 and Chapter 9, we discuss the results of thesimulations and experiments, respectively. Chapter 10 concludes the thesis. We present someconcluding remarks and future work.
博士後期課程知能情報システム工学専攻３年の「小田 哲也」氏が提出した学位論文を審査し、また最終試験を行ったのでその結果について報告する。
（学位論文審査の結果）
本論文では、無線メッシュネットワーク（WMN）のためのシミュレーションシステムとテストベッドを実装し、その評価を行っている。WMN はインフラレスでネットワークを構築する事が可能なアーキテクチャであり、無線ノードのみでネットワークを形成するため、トポロジは刻々と変化する。そのため、フロー制御、ルーティング、キュー管理の性能向上に関する研究は重要である。WMN における課題点は多く存在するが、中でも、スループット性能、ルーティング効率、エネルギー消費量は重要な問題である。WMN における通信性能改善のために、様々なメタヒューリスティクス手法、異なるアーキテクチャ、ルーティングプロトコル、キュー管理アルゴリズム、モビリティモデルを考慮した環境でのシミュレーションシステム及びテストベッドの実装と評価を行った。シミュレーション及び実験結果より、ノードの移動が通信性能におけるデグラデーションや経路の不安定性をもたらすことを明らかにした。
また、複数フローの通信時には、ネットワークの性能が低下することが示された。
このように本研究の内容は、他の研究者によって報告されていない結果を含み，学位論文としての十分な価値があると認められる。
本論文は次の特色と独創性を有しており高く評価できる。１) 様々なメタヒューリスティクス手法を用いたメッシュルータ配置最適化手法の提案と評価、２）

Network Simulator 3 (ns-3)を用いた WMN のシミュレーションシステムの実装、３）Raspberry Pi を用いた WMN テストベッドの実装と評価、４）様々なシナリオを考慮したシミュレーション及び実験、５）WMN テストベッドにおける異なる OS の評価、
６）WMN テストベッドを用いた分散型並行処理の評価 に取り組んでおり、今後の無線通信の技術の発展のための WMN の統合についての見識を与えることができる。
論文の構成は次のようになっている。第１章では、研究背景と目的を述べている。
第 2 章では、無線ネットワークの既存技術を説明している。第 3 章では WMN の問題点を議論し、ルーティングプロトコルについて考察している。第 4 章では、メタヒューリスティクス手法について述べ、遺伝的アルゴリズム、タブー探索法、山登り法及び焼きなまし法について紹介している。第 5 章では遺伝的アルゴリズムについて述べている。第 6 章ではシミュレーションシステムの設計と実装について紹介している。第 7 章ではテストベッドの設計と実装について述べている。第 8 章と第 9章では、シミュレーションと実験の結果を議論している。第 10 章では、結論と今後の課題の見識を与えて、論文をまとめている。
本研究の成果は、氏の博士後期課程在学期間において学術論文 5 編（第１著者 5編）、国際会議 18 編（第１著者 18 編）となっている。また、ITCS-2013 と BWCCA-2014
国際会議及び WAINA-2015 国際ワークショップでは“Best Paper”賞を受賞しており、本研究の新規性と有用性が認められるとともに、国際的にも高く評価できる研究であることが分かる。
以上の理由により、審査委員会は本論文が学位論文の内容として適合すると判定した。

主な研究業績

学位論文公聴会においては、論文内容に関連する種々の工学的及び技術的な質問があったが、いずれも適切な回答を行うことができた。また、公聴会後の最終試験においては、学位論文に関連する分野の学識を有し、今後研究を進めていくための研究能力を備えていることが判明した。
以上の結果から、学位審査委員会は本論文が博士（工学）の学位に適格であると判定した。
参考論文 ２３編１冊（学術論文）（査読付き学術論文：第一著者５編）
1. Tetsuya Oda, Yi Liu, Shinji Sakamoto, Donald Elmazi, Leonard Barolli, Fatos
Xhafa, "Analysis of Mesh Router Placement in Wireless Mesh Networks
Using Friedman Test Considering Different Meta-heuristics'', International
Journal of Communication Networks and Distributed Systems (IJCNDS),
Inderscience, Vol. 15, No. 1, pp. 84–106, July 2015, (DOI:10.1504/IJCNDS.2015.0702895).
2. Tetsuya Oda, Donald Elmazi, Admir Barolli, Shinji Sakamoto, Leonard
Barolli, Fatos Xhafa, "A Genetic Algorithm Based System for Wireless Mesh
Networks: Analysis of System Data Considering Different Routing Protocolsand Architectures'', Journal of Soft Computing (SOCO), Springer, pp. 1-14,
2015, (DOI: 10.1007/s00500-015-1663-z), (Published online: 31 March, 2015).
3. Tetsuya Oda, Shinji Sakamoto, Admir Barolli, Evjola Spaho, Leonard Barolli
and Fatos Xhafa, "Effect of Different Grid Shapes in Wireless Mesh Network
Genetic Algorithm System'', International Journal of Web and Grid Services(IJWGS), Inderscience, Vol. 10, No. 4, pp.371-395, September 2014, (DOI:10.1504/IJWGS.2014.064932).
4. Tetsuya Oda, Admir Barolli, Evjola Spaho, Leonard Barolli, Fatos Xhafa,Muhammad Younas, "Effects of population size for location-aware nodeplacement in WMNs: evaluation by a genetic algorithm based approach'',
Personal and Ubiquitous Computing (PUC), Springer, Vol. 18, No. 2, pp.
261-269, February 2014 (DOI 10.1007/s00779-013-0643-5).

5. Tetsuya Oda, Admir Barolli, Fatos Xhafa, Leonard Barolli, Makoto Ikeda,
Makoto Takizawa, "WMN-GA: A Simulation System for WMNs and Its
Evaluation Considering Selection Operators'', Journal of AmbientIntelligence and Humanized Computing (JAIHC), Springer, Vol. 4, No. 3, pp.
323-330, June 2013, (DOI 10.1007/s12652-011-0099-2).

（国際会議論文）（査読付き国際会議：第一著者１８編）
1. Tetsuya Oda, Donald Elmazi, Taro Ishitaki, Admir Barolli, Keita Matsuo,
Leonard Barolli, "Experimental Results of a Raspberry Pi Based WMN
Testbed for Multiple Flows and Distributed Concurrent Processing", The
10-th International Conference on Broadband and Wireless Computing,Communication and Applications (BWCCA-2015), Krakow, Poland, pp.
201-206, November 2015.
2. Tetsuya Oda, Donald Elmazi, Taro Ishitaki, Keita Matsuo, Makoto Ikeda,
Leonard Barolli, "Implementation and Experimental Results of a Raspberry
Pi and OLSR Based Wireless Content-Centric Network Testbed", The 10-th
International Conference on Broadband and Wireless Computing,Communication and Applications (BWCCA-2015), Krakow, Poland, pp.
263-268, November 2015
3. Tetsuya Oda, Makoto Ikeda, Leonard Barolli, Fatos Xhafa, Makoto Takizawa,“A GA-Based Simulation System for WMNs: Performance Analysis ofWMN-GA System for Different WMN Architectures Considering DCF andEDCA”, The 7-th International Conference on Intelligent Networking andCollaborative Systems (INCoS-2015), Taipei, Taiwan, pp. 232-238 ,September 2015.
4. Tetsuya Oda, Keita Matsuo, Leonard Barolli, Makoto Ikeda, Makoto
Takizawa, “Performance Evaluation of a WMN Testbed in Indoor
Environment Considering Mobile Mesh Node Scenario”, The 18-th
International Conference on Network-Based Information Systems(NBiS-2015), Taipei, Taiwan, pp. 93-98 , September 2015.
5. Tetsuya Oda, Donald Elmazi, Evjola Spaho, Vladi Kolici, Leonard Barolli, “ASimulation System Based on ONE and SUMO Simulators: Performance
Evaluation of Direct Delivery, Epidemic and Energy aware Epidemic DTN
Protocols”, The 18-th International Conference on Network-BasedInformation Systems (NBiS-2015), Taipei, Taiwan, pp. 418-423, September2015.
6. Tetsuya Oda, Keita Matsuo, Admir Barolli, Shinji Sakamoto, Makoto Ikeda,Leonard Barolli, "Implementation and Experimental Results of a Wireless
Mesh Network Testbed Considering NLoS Scenario", The 9-th International
Conference on Complex, Intelligent, and Software Intensive Systems(CISIS-2015), Blumenau, Brazil, pp.283-288, July 2015.
7. Tetsuya Oda, Yi Liu, Keita Matsuo, Shinji Sakamoto, Makoto Ikeda, Leonard
Barolli, "Experimental Results of a CentOS-based Ad-Hoc Network Testbed
Considering LoS Scenario", The 9-th International Conference on Innovative
Mobile and Internet Services in Ubiquitous Computing (IMIS-2015) ,Blumenau, Brazil, pp. 9-14, July 2015.
8. Tetsuya Oda, Donald Elmazi, Algenti Lala, Vladi Kolici, Leonard Barolli,Fatos Xhafa, " Analysis of Node Placement in Wireless Mesh Networks Using
Friedman Test: A Comparison Study for Tabu Search and Hill Climbing", The
9-th International Conference on Complex, Intelligent, and Software

Intensive Systems (CISIS-2015), Blumenau, Brazil, pp. 133-140, July 2015.
9. Tetsuya Oda, Admir Barolli, Shinji Sakamoto, Leonard Barolli, Makoto Ikeda
and K. Uchida, “Implementation and Experimental Results of a WMN
Testbed in Indoor Environment Considering LoS Scenario”, The 29-th IEEE
International Conference on Advanced Information Networking andApplications (IEEE AINA-2015), Gwangju, Korea, pp. 37-42, March 2015.
10. Tetsuya Oda, Shinji Sakamoto, Admir Barolli, Makoto Ikeda, Leonard Barolli
and Fatos Xhafa, “A GA-Based Simulation System for WMNs: Performance
Analysis for Different WMN Architecture Considering TCP”, The 9-th
International Conference on Broadband and Wireless Computing,Communication and Applications (BWCCA-2014), Guangzhou, China, pp.
120-126, November 2014.
11. Tetsuya Oda, Shinji Sakamoto, Admir Barolli, Makoto Ikeda, Fatos Xhafa
and Leonard Barolli, “Analysis of Mesh Router Node Placement Using
WMN-GA System Considering Different Architectures of WMNs”, The 17-th
International Conference on Network-Based Information Systems(NBiS-2014), Salerno, Italy, pp. 39-44, September 2014.
12. Tetsuya Oda, Shinji Sakamoto, Evjola Spaho, Admir Barolli, Leonard Barolli
and Fatos Xhafa, “Node Placement in WMNs using WMN-GA SystemConsidering Uniform and Normal Distribution of Mesh Clients”, The 8-th
International Conference on Complex, Intelligent and Software Intensive
Systems (CISIS 2014), Birmingham, UK, pp. 120-127, July 2014.
13. Tetsuya Oda, Admir Barolli, Evjola Spaho, Leonard Barolli, Fatos Xhafa,“Analysis of Mesh Router Placement in Wireless Mesh Networks Using
Friedman Test”, The 28-th IEEE International Conference on Advanced
Information Networking and Applications (IEEE AINA-2014), Victoria,
Canada, pp. 289-296, May 2014.
14. Tetsuya Oda, Evjola Spaho, Admir Barolli, Leonard Barolli, Fatos Xhafa,
Makoto Takizawa, ”Mesh Router Node Placement in Wireless Mesh Networks
Considering Different Initial Router Placement Methods”, The 8-th
International Conference on Broadband and Wireless Computing,Communication and Applications (BWCCA-2013), pp. 61-67, November 2013.
15. Tetsuya Oda, Evjola Spaho, Admir Barolli, Leonard Barolli, Fatos Xhafa,
Makoto Takizawa, ”Performance Evaluation of WMN-GA for Wireless Mesh
Networks Considering Mobile Mesh Clients”, The 5-th International
Conference on Intelligent Networking and Collaborative Systems(INCoS-2013), X’ian, China, pp. 77-84, September 2013.
16. Tetsuya Oda, Evjola Spaho, Admir Barolli, Leonard Barolli, Fatos Xhafa,
Makoto Takizawa,”A Comparison Study of GA and HC for Mesh Router NodePlacement in Wireless Mesh Networks”, The 16-th International Conference
on Network-Based Information Systems (NBiS-2013), Gwangju, Korea,
pp.206-213, September 2013.
17. Tetsuya Oda, Evjola Spaho, Admir Barolli, Leonard Barolli, Fatos Xhafa,
Makoto Takizawa, ”WMN-GA System for Node Placement in WMNs: Effect ofGrid Shape”, The 5-th International Conference on Information Technology
Convergence and Services (ITCS-13), Fukuoka, Japan, pp.150-156, July 2013.
18. Tetsuya Oda, Admir Barolli, Evjola Spaho, Leonard Barolli, Fatos
Xhafa, ”Performance Evaluation of WMN-GA system for Node Placement inWMNs for Normal and Uniform Distributions of Mesh Clients Considering
Different Grid Shapes”, The 7-th International Conference on Complex,Intelligent, and Software Intensive Systems (CISIS-2013), Taichung, Taiwan,
pp.150-156, July 2013.