A COMPARISON STUDY OF SIMULATED ANNEALING AND GENETIC ALGORITHM FOR NODE PLACEMENT PROBLEM IN WIRELESS MESH NETWORKS
Keywords:
Simulated Annealing, Genetic Algorithm, WMN, Node Placement ProblemAbstract
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
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.
