A COMPARISON STUDY OF SIMULATED ANNEALING AND GENETIC ALGORITHM FOR NODE PLACEMENT PROBLEM IN WIRELESS MESH NETWORKS

Authors

  • SHINJI SAKAMOTO Graduate School of Engineering, Fukuoka Institute of Technology (FIT) 3-30-1 Wajiro-Higashi, Higashi-Ku, Fukuoka 811-0295, Japan
  • ELIS KULLA Graduate School of Engineering, Fukuoka Institute of Technology (FIT) 3-30-1 Wajiro-Higashi, Higashi-Ku, Fukuoka 811-0295, Japan
  • TETSUYA ODA Graduate School of Engineering, Fukuoka Institute of Technology (FIT) 3-30-1 Wajiro-Higashi, Higashi-Ku, Fukuoka 811-0295, Japan
  • MAKOTO IKEDA Department of Information and Communication Engineering Fukuoka Institute of Technology (FIT) 3-30-1 Wajiro-Higashi, Higashi-Ku, Fukuoka 811-0295, Japan
  • LEONARD BAROLLI Department of Information and Communication Engineering Fukuoka Institute of Technology (FIT) 3-30-1 Wajiro-Higashi, Higashi-Ku, Fukuoka 811-0295, Japan
  • FATOS XHAFA Technical University of Catalonia Department of Languages and Informatics Systems C/Jordi Girona 1-3, 08034 Barcelona, Spain

Keywords:

Simulated Annealing, Genetic Algorithm, WMN, Node Placement Problem

Abstract

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 net- work connectivity and user coverage, which are related with the node placement problem. In this work, we compare 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 user coverage in a set of randomly distributed clients. From the simulation results, both algorithms converge to the maximum size of GC. However, according to the number of covered mesh clients SA converges faster.

 

Downloads

Download data is not yet available.

References

I. F. Akyildiz, X. Wang, and W. Wang, “Wireless Mesh Networks: A Survey”, Computer Networks,

Vol. 47, No. 4, pp. 445-487, 2005.

N. Nandiraju, D. Nandiraju, L. Santhanama, B. He, J. Wang, and D. Agrawal, “ Wireless Mesh

Networks: Current Challenges and Future Direction of Web-in-the-Sky”, IEEE Wireless Communications,

pp. 79-89, 2007.

Ch. Chen and Ch. Chekuri. “Urban Wireless Mesh Network Planning: The Case of Directional

Antennas”, Tech Report No. UIUCDCS-R-2007-2874, Department of Computer Science, University

of Illinois at Urbana-Champaign, 2007.

M.R. Garey and D.S. Johnson, “Computers and Intractability -A Guide to the Theory of NPCompleteness”,

Freeman, San Francisco, 1979.

A. Lim, B. Rodrigues, F. Wang and Zh. Xua, “k−Center Problems with Minimum Coverage”,

Theoretical Computer Science, Vol. 332, No. 1-3, pp. 1-17, 2005.

E. Amaldi, A. Capone, M. Cesana, I. Filippini, F. Malucelli. “Optimization Models and Methods

for Planning Wireless Mesh Networks”, Computer Networks, Vol. 52, pp. 2159-2171, 2008.

J. Wang, B. Xie, K. Cai and D.P. Agrawal, “Efficient Mesh Router Placement in Wireless Mesh

Networks”, MASS-2007, Pisa, Italy, pp. 9-11, 2007.

S. N. Muthaiah and C. Rosenberg, “Single Gateway Placement in Wireless Mesh Networks”, In

Proc. of 8th International IEEE Symposium on Computer Networks, Turkey, pp. 4754-4759, 2008.

P. Zhou, B.S. Manoj and R. Rao, "A Gateway Placement Algorithm in Wireless Mesh Networks",

Proc. of the Third Annual International Wireless Internet Conference (WICON-2007), pp. 1-9,

October 2007.

M. Tang, “Gateways Placement in Backbone Wireless Mesh Networks”, International Journal of

Communications, Network and System Sciences, Vol. 2, No.1, pp. 45-50, 2009.

A. Antony Franklin and C. Siva Ram Murthy, “Node Placement Algorithm for Deployment of

Two-Tier Wireless Mesh Networks”, In Proc. of IEEE GLOBECOM-2007, Washington, USA, pp.

-4827, 2007.

T. Vanhatupa, M. Hännikäinen and T.D. Hämäläinen, “Genetic Algorithm to Optimize Node

Placement and Configuration for WLAN Planning”, In Proc. of 4th International Symposium on

Wireless Communication Systems, pp. 612-616, 2007.

S. Kirkpatrick, C. D. Gelatt and M. P. Vecchi, “Optimization by Simulated Annealing”, Journal

of Science, Vol. 220, pp. 671-680, 1983.

F. Xhafa, C. Sanchez, L. Barolli, R. Miho, “An Annealing Approach to Router Nodes Placement

Problem in Wireless Mesh Networks”, In Proc. of CISIS-2010, pp. 245-252, 2010.

J. Holland, “Adaptation in Natural and Artificial Systems”, University of Michigan Press, Ann

Arbor, 1975.

F. Xhafa, C. Sanchez, L. Barolli, “Genetic Algorithms for Efficient Placement of Router Nodes in

Wireless Mesh Networks”, Proc. of AINA-2010, pp. 465-472, 2010.

Downloads

Published

2013-07-14

Issue

Section

Articles

Most read articles by the same author(s)

1 2 > >>