A comparison study of Hill Climbing, Simulated Annealing and Genetic Algorithm for node placement problem in WMNs

被引：62

作者：

Sakamoto, Shinji ^{[1
]}

Kulla, Elis ^{[1
]}

Oda, Tetsuya ^{[1
]}

Ikeda, Makoto ^{[2
]}

Barolli, Leonard ^{[2
]}

Xhafa, Fatos ^{[3
]}

机构：

[1] Fukuoka Inst Technol, Grad Sch Engn, Fukuoka, Japan

[2] Fukuoka Inst Technol, Dept Informat & Commun Engn, Fukuoka, Japan

[3] Tech Univ Catalonia, Dept Languages & Informat, Barcelona, Spain

来源：

JOURNAL OF HIGH SPEED NETWORKS | 2014年 / 20卷 / 01期

关键词：

Comparison study; simulation; Hill Climbing; HC; Simulated Annealing; SA; Genetic Algorithm; GA; WMN; node placement problem;

D O I：

10.3233/JHS-140487

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

One of the key advantages of Wireless Mesh Networks (WMNs) is their importance for providing cost-efficient broadband connectivity. There are issues for achieving the network connectivity and user coverage, which are related with the node placement problem. In this work, we compare Hill Climbing (HC), Simulated Annealing (SA) and Genetic Algorithm (GA) by simulations for node placement problem. We want to find the optimal distribution of router nodes in order to provide the best network connectivity and provide the best coverage in a set of randomly distributed clients. From the simulation results, all algorithms converge to the maximum size of Giant Component (GC). However, according to the number of covered mesh clients, HC and SA converge faster.

引用

页码：55 / 66

页数：12

共 15 条

[1] Wireless mesh networks: a survey [J].

Akyildiz, IF ;

Wang, XD ;

Wang, WL .

COMPUTER NETWORKS, 2005, 47 (04) :445-487

[2] Optimization models and methods for planning wireless mesh networks [J].

Amaldi, E. ;

Capone, A. ;

Cesana, M. ;

Filippini, I. ;

Malucelli, F. .

COMPUTER NETWORKS, 2008, 52 (11) :2159-2171

[3]

Chen C., 2007, UIUCDCSR20072874

[4]

Franklin AA, 2007, GLOB TELECOMM CONF, P4823

[5]

Holland J. H., 1975, ADAPTATION NATURAL A

[6] OPTIMIZATION BY SIMULATED ANNEALING [J].

KIRKPATRICK, S ;

GELATT, CD ;

VECCHI, MP .

SCIENCE, 1983, 220 (4598) :671-680

[7] k-Center problems with minimum coverage [J].

Lim, A ;

Rodrigues, B ;

Wang, F ;

Xu, Z .

THEORETICAL COMPUTER SCIENCE, 2005, 332 (1-3) :1-17

[8]

Muthaiah SN, 2008, PROC 8 INT IEEE S CO, P4754

[9] Wireless Mesh Networks: Current challenges and future directions of Web-in-the-sky [J].

Nandiraju, Nagesh ;

Nandiraju, Deepti ;

Santhanam, Lakshmi ;

He, Bing ;

Wang, Junfang ;

Agrawal, Dharma P. .

IEEE WIRELESS COMMUNICATIONS, 2007, 14 (04) :79-89

[10] Scalable service discovery in ubiquitous and pervasive computing architectures: A percolation-driven approach [J].

Palmieri, Francesco .

FUTURE GENERATION COMPUTER SYSTEMS-THE INTERNATIONAL JOURNAL OF ESCIENCE, 2013, 29 (03) :693-703

← 1 2 →