真仁（Shinji Sakamoto）

学位被授与者氏名

坂本

学位の名称

博士（工学）

学位番号

博（一）第４９号

学位授与年月日

平成３０年３月２０日

論文題目

Implementation of Intelligent and Hybrid Systems for Wireless Mesh Networks: AComparison Study

論文題目（英訳または和訳）

無線メッシュネットワークのための知的およびハイブリッドシステムの実装：比較研究

論文審査委員

論文審査委員会
委員主査 ：福岡工業大学大学院知能情報システム工学専攻教授
同審査委員：福岡工業大学大学院知能情報システム工学専攻教授
同審査委員：福岡工業大学大学院知能情報システム工学専攻准教授
同審査委員：福岡工業大学大学院物質生産システム工学専攻教授

ﾊﾞﾛﾘﾚｵﾅﾙﾄﾞ
前田洋
池田誠
大山 和宏

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

論文内容の要旨（和文）

無線メッシュネットワーク（WMN）は，低コストで無線インターネット接続を提供する魅力的な性質を有するため，多くの注目を集めている．WMN は動的に自己組織化・自己構成され，ネットワーク内のメッシュノードは自動的に接続を確立し，その状態を維持する．メッシュルータの配置は，WMN にとって非常に重要な問題である．しかし，この問題は NP 困難であることが知られており，対処するためには，新しい方法，アルゴリズムおよびシステムが必要である．
本論文では，WMN におけるメッシュルータ配置問題を解決するため，インテリジェントおよびハイブリッドシステムの設計と実装を行う．実装システムでは，Sizeof Giant Component（SGC）を最大化し，次に Number of Covered Mesh Clients（NCMC）を最大化する二目的最適化を考慮する．実装したシステムを多くのシミュレーションで評価する．評価結果から，ハイブリッドシステムが，WMN におけるメッシュルータ配置最適化に対して，非常に良好な性能を有することがわかった．
本研究は，次のような特色と独創的な点を有しており，科学技術の貢献が期待できる．1）様々な知的アルゴリズムを用いたメッシュルータ配置最適化システムの実装，2）様々なシミュレーションシナリオによる知的アルゴリズムを用いたメッシュルータ配置最適化システムの評価，3）ハイブリッド型知的アルゴリズムを含む様々な知的アルゴリズムに基づいたシステムの比較，4）Network Simulator 3 を用いたWMN のシミュレーションシステムの実装，5）実環境を考慮したシナリオのためのWMN のメッシュルータ配置最適化システムの応用，6）本研究の結果から，今後の無線通信の技術の発展のための WMN の統合についての見識を与える．
以下に論文の構成を示す．第1章では，研究背景と目的，論文構成を述べている．
第2章では，無線ネットワークの一般的な技術を紹介し，WMNの関連研究として，無線センサアクタネットワーク（WSAN）とモバイルアドホックネットワーク（MANET）について述べる．第3章では，WMNにおけるノードの分類や，ルーティングプロトコルについて説明する．加えて，WMNにおけるメッシュルータ配置問題を定義する．第4章では，山登り法（HC），焼き鈍し法（SA），禁錮探索法（TS），遺伝的アルゴリズム（GA），アントコロニー最適化（ACO），粒子群最適化（PSO）といった知的アルゴリズムについて紹介する．第5章では，PSOの詳細について述べる．
第6章では，シミュレーションシステムの設計と実装について述べる．第7章では，シミュレーション結果を議論する．第8章では，結論とこの分野における今後の課題の見識を与えて，論文をまとめる．
Wireless Mesh Networks (WMNs) are gaining a lot of attention because of their low cost
nature that makes them attractive for providing wireless Internet connectivity. A WMN isdynamically self-organized and self-configured, with the nodes in the network automaticallyestablishing and maintaining mesh connectivity among themselves. In WMNs, the meshnode placement is a very important problem. However, this problem is known to be NP-hard.
To deal with this problem, new methods, algorithms and systems are needed.
In this thesis, we design and implement intelligent and hybrid systems in order to solve thenode placement problem in WMNs. We consider a bi-objective optimization in which we

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

first maximize the network connectivity through the maximization of Size of GiantComponent (SGC) and then the maximization of the Number of Covered Mesh Clients(NCMC). We evaluate the implemented systems by many simulations. From the evaluation
results, we found that the hybrid systems have very good performance for optimizing thenode placement in WMNs.
This thesis contributes in the research field as following: 1) Implementation of intelligent
systems for solving node placement problem in WMNs. 2) Evaluation of various intelligent
algorithms based systems for different scenarios. 3) Comparison of implemented intelligent
and hybrid systems. 4) Implementation of WMN simulation system using Network Simulator
3. 5) Application of implemented system for WMN node placement problem in a realistic
scenario. 6) Give insights about future developments and integration of WMNs as animportant technology in wireless communications.
This thesis is constructed by 8 Chapters. Chapter 1 presents the background, the motivationand thesis structure. Chapter 2 introduces general aspects of wireless networks. Also,
Wireless Sensor and Actor Networks (WSANs) and Mobile Ad-hoc Networks (MANETs) areexplained as a related work to this thesis. In Chapter 3, we explain about the nodeclassification in WMNs and routing protocols for WMNs. In addition, we define the Node
Placement Problem in WMNs. In Chapter 4 are discussed intelligent algorithms such as Hill
Climbing (HC), Simulated Annealing (SA), Tabu Search (TS), Genetic Algorithm (GA), Ant
Colony Optimization (ACO) and Particle Swarm Optimization (PSO). We present in details
the PSO algorithm in Chapter 5. The implemented intelligent and hybrid systems arepresented in Chapter 6. Chapter 7 shows the evaluation and comparison of implemented
systems by conducting simulations and application for a realistic scenario. In Chapter 8, wegive some concluding remarks and future work.
博士後期課程知能情報システム工学専攻３年の「坂本 真仁」氏が提出した学位論文を審査し、また最終試験を行ったのでその結果について報告する。
（学位論文審査の結果）
近年、無線メッシュネットワーク（Wireless Mesh Network: WMN）の研究が注目されている。WMN は動的に自己組織化・自己構成され、ネットワーク内のメッシュノードは自動的に接続を確立し、その状態を維持する。メッシュルータの配置は、WMNにとって非常に重要な問題である。しかし、この問題は NP 困難であることが知られており、対処するためには新しい方法およびシステムが必要である。本論文では、WMN におけるメッシュルータ配置問題を解決するため、インテリジェントおよびハイブリッドシステムの設計と実装を行っている。実装システムでは Size of GiantComponent（SGC）を最大化し、次に Number of Covered Mesh Clients（NCMC）を最大化する二目的最適化を考慮している。実装したシステムを多くのシミュレーションで評価している。評価の結果から、ハイブリッドシステムが WMN におけるメッシュルータ配置最適化に対して、非常に良好な性能を有することが示された。このように本研究の内容は、他の研究者によって報告されていない結果を含み，学位論文としての十分な価値があると認められる。
本論文は次の特色と独創性を有しており高く評価できる。1）様々な知的アルゴリズ
ムを用いたメッシュルータ配置最適化システムの実装、2）様々なシミュレーションシナリオによる知的アルゴリズムを用いたメッシュルータ配置最適化システムの評価、3）ハイブリッド型知的アルゴリズムを含む様々な知的アルゴリズムに基づいたシステムの比較、4）Network Simulator 3 (ns-3)を用いた WMN のシミュレーションシステムの実装、5）実環境を考慮したシナリオのための WMN のメッシュルータ配置最適化システムの応用、6）本研究の結果から、今後の無線通信の技術の発展のための WMN の統合についての見識を与える。
論文の構成は次のようになっている。第 1 章では、研究背景と目的、論文構成を述べている。第 2 章では、無線ネットワークの一般的な技術を紹介し、WMN の関連研究として、無線センサアクタネットワーク（Wireless Sensor and Actor Networks: WSAN）とモバイルアドホックネットワーク（Mobile Ad-hoc Networks: MANET）について述べている。第 3 章では、WMN におけるノードの分類や、ルーティングプロトコルについて説明している。
第 4 章では、山登り法（Hill Climbing: HC），焼き鈍し法（SimulatedAnnealing: SA），禁錮探索法（Tabu Search: TS），遺伝的アルゴリズム（GeneticAlgorithm: GA），アントコロニー最適化（Ant Colony Optimization: ACO），粒子群最適化（Particle Swarm Optimization: PSO）といった知的アルゴリズムについて紹介している。第 5 章では、PSO の詳細について述べている。第 6 章では、シミュレーションシステムの設計と実装について述べている。第 7 章では、シミュレーション結果を議論している。第 8 章では、結論とこの分野における今後の課題の見識を与えて、論文をまとめている。
本研究の成果は、氏の博士後期課程在学期間において学術論文 4 編（第１著者 4 編）、国際会議 12 編（第１著者 12 編）となっている。また、BWCCA-2016 国際会議では“BestPaper”賞を受賞しており、本研究の新規性と有用性が認められるとともに、国際的にも高く評価できる研究であることが分かる。
以上の理由により、審査委員会は本論文が学位論文の内容として適合すると判定した。

学位論文公聴会においては、論文内容に関連する種々の工学的及び技術的な質問があったが、いずれも適切な回答を行うことができた。また、公聴会後の最終試験においては、学位論文に関連する分野の学識を有し、今後研究を進めていくための研究能力を備えていることが判明した。
以上の結果から、学位審査委員会は本論文が博士（工学）の学位に適格であると判定した。
主な研究業績

参考論文 16 編１冊（学術論文）（査読付き学術論文：第一著者4編）
1. Shinji Sakamoto, Tetsuya Oda, Makoto Ikeda, Leonard Barolli and Fatos
Xhafa, “Implementation and Evaluation of a Simulation System Based onParticle Swarm Optimisation for Node Placement Problem in Wireless MeshNetworks”, International Journal of Communication Networks andDistributed Systems, Inderscience, Vol. 17, No. 1, pp. 1–13, DOI:
10.1504/IJCNDS.2016.077935, 2016.
2. Shinji Sakamoto, Ryoichiro Obukata, Tetsuya Oda, Leonald Barolli, MakotoIkeda and Admir Barolli, “Performance Analysis of Two Wireless Mesh
Network Architectures by WMN-SA and WMN-TS Simulation Systems”,
Journal of High Speed Networks, IOS Press, Vol. 24, No 4, pp. 311-322, DOI
10.3233/JHS-170573, 2017.
3. Shinji Sakamoto, Kosuke Ozera, Makoto Ikeda and Leonard Barolli,“Implementation of Intelligent Hybrid Systems for Node Placement Problemin WMNs Considering Particle Swarm Optimization, Hill Climbing andSimulated Annealing”, International Journal of Mobile Networks andApplications, Springer, Published online: 06 September 2017, DOI:
10.1007/s11036-017-0897-7, 2017.
4. Shinji Sakamoto, Kosuke Ozera, Admir Barolli, Makoto Ikeda, Leonald
Barolli and Makoto Takizawa, “Implementation of an Intelligent Hybrid
Simulation Systems for WMNs based on Particle Swarm Optimization andSimulated Annealing: Performance Evaluation for Different Replacement
Methods”, Journal of Soft Computing, Springer, Published online: 11December 2017, DOI: 10.1007/s00500-017-2948-1, 2017.
（国際会議論文）（査読付き国際会議：第一著者12編）
1. Shinji Sakamoto, Algenti Lala, Tetsuya Oda, Vladi Kolici, Leonard Barolliand Fatos Xhafa, “Analysis of WMN-HC Simulation System Data Using
Friedman Test”, The 9th International Conference on Complex, Intelligent,and Software Intensive Systems (CISIS-2015), pp. 254-259, Blumenau,Brazil, July 8-10, 2015.
2. Shinji Sakamoto, Tetsuya Oda, Makoto Ikeda and Leonard Barolli, “Designand Implementation of a Simulation System Based on Particle Swarm
Optimization for Node Placement Problem in Wireless Mesh Networks”, The
7th International Conference on Intelligent Networking and CollaborativeSystems (INCoS-2015), pp. 164-168, Taipei, Taiwan, September 2-4, 2015.
3. Shinji Sakamoto, Tetsuya Oda, Makoto Ikeda, Leonard Barolli and Fatos
Xhafa, “A PSO-based Simulation System for Node Placement in Wireless
Mesh Networks: Evaluation Results for Different Replacement Methods”,
The 10th International Conference on Broadband and Wireless Computing,Communication and Applications (BWCCA-2015), pp. 213-219, Krakow,Poland, November 4-6, 2015.
4. Shinji Sakamoto, Tetsuya Oda, Makoto Ikeda, Leonard Barolli and Fatos
Xhafa “Implementation of a New Replacement Method in WMN-PSO
Simulation System and Its Performance Evaluation”, The 30th IEEE
International Conference on Advanced Information Networking andApplications (AINA-2016), pp. 206-211, Le Régent Congress Centre,Crans-Montana, Switzerland, March 23-25, 2016.
5. Shinji Sakamoto, Tetsuya Oda, Makoto Ikeda, Leonard Barolli, Fatos Xhafa
and Isaac Woungang, “Investigation of Fitness Function Weight-Coefficientsfor Optimization in WMN-PSO Simulation System”, The 10th International
Conference on Complex, Intelligent, and Software Intensive Systems(CISIS-2016), pp. 224-229, Fukuoka Institute of Technology, Fukuoka, Japan,July 6-8, 2016.
6. Shinji Sakamoto, Tetsuya Oda, Makoto Ikeda, Leonard Barolli, Fatos Xhafa
and Isaac Woungang, “Node Placement in Wireless Mesh Networks: A
Comparison Study of WMN-SA and WMN-PSO Simulation Systems”, The
19th International Conference on Network-Based Information Systems(NBiS-2016), pp. 1-8, VSB - Technical University of Ostrava, Czech Republic,
September 7-9, 2016.
7. Shinji Sakamoto, Tetsuya Oda, Makoto Ikeda, Leonard Barolli and Fatos
Xhafa, “An Integrated Simulation System Considering WMN-PSO
Simulation System and Network Simulator 3”, The 11th InternationalConference on Broad-Band Wireless Computing, Communication andApplications (BWCCA-2016), pp. 187-198, Soonchunhyang (SCH) University,Asan, Korea, November 5-7, 2016.
8. Shinji Sakamoto, Ryoichiro Obukata, Tetsuya Oda, Leonard Barolli andMakoto Ikeda, “Implementation of an Intelligent Hybrid Simulation System
for Node Placement Problem in WMNs Considering Particle Swarm
Optimization and Simulated Annealing”, The 31st IEEE International
Conference on Advanced Information Networking and Applications(AINA-2017), pp. 697-703, Tamkang University, Taipei, Taiwan, March 27-29,
2017.
9. Shinji Sakamoto, Kosuke Ozera, Tetsuya Oda, Makoto Ikeda and Leonard
Barolli, “Performance Evaluation of WMN-PSOHC and WMN-PSO
Simulation Systems for Node Placement in Wireless Mesh Networks: AComparison Study”, The 5th International Conference on Emerging
Internetworking, Data & Web Technologies (EIDWT-2017), pp. 64-74, Hubei
University, Wuhan, China, June 10-11, 2017.
10. Shinji Sakamoto, Kosuke Ozera, Tetsuya Oda, Makoto Ikeda and Leonard

Barolli, “Performance Evaluation of Intelligent Hybrid Systems for Node
Placement in Wireless Mesh Networks: A Comparison Study ofWMN-PSOHC and WMN-PSOSA”, The 11th International Conference onInnovative Mobile and Internet Services in Ubiquitous Computing(IMIS-2017), pp. 16-26, Istituto Superiore Mario Boella (ISMB), Torino, Italy,
July 10-12, 2017.
11. Shinji Sakamoto, Kosuke Ozera, Makoto Ikeda and Leonard Barolli,“Performance Evaluation of WMNs by WMN-PSOSA Simulation SystemConsidering Constriction and Linearly Decreasing Inertia Weight Methods”,
The 20th International Conference on Network-Based Information Systems(NBiS-2017), pp. 3-13, Ryerson University, Toronto, Canada, August 24-26,
2017.
12. Shinji Sakamoto, Kosuke Ozera, Admir Barolli, Makoto Ikeda, LeonardBarolli and Makoto Takizawa, “Performance Evaluation of WMNs byWMN-PSOSA Simulation System Considering Random Inertia WeightMethod and Linearly Decreasing Vmax Method”, The 12th International
Conference on Broad-Band Wireless Computing, Communication andApplications (BWCCA-2017), pp. 114-124, Palau Macaya, Barcelona, Spain,
November 8-10, 2017.