A Chemical Reaction Algorithm to Solve the Router Node Placement in Wireless Mesh Networks

  • PDF / 1,619,350 Bytes
  • 14 Pages / 595.224 x 790.955 pts Page_size
  • 96 Downloads / 190 Views

DOWNLOAD

REPORT


A Chemical Reaction Algorithm to Solve the Router Node Placement in Wireless Mesh Networks Lamri Sayad1,2

· Louiza Bouallouche-Medjkoune1 · Djamil Aissani1

© Springer Science+Business Media, LLC 2017

Abstract This paper considers the problem of router node placement (WMN-RNP) in wireless mesh networks (WMN). A wireless mesh network consists of three kinds of nodes: mesh clients, mesh routers and gateways interconnected via radio links. The problem considered in this paper is the following: given a set of mesh clients deployed in a rectangular area, determine the best placement of mesh routers so that both client coverage and network connectivity are maximized. This issue is known to be NP-hard since it can be modeled as a facility location problem. To solve this issue, we propose to use a metaheuristic technique inspired from the interactions between molecules in chemical reactions to reach a low stable energy state, namely Chemical Reaction Optimization algorithm (CRO). A simulation tool has been developed to compare the performance of our CRO algorithm to the existing Genetic Algorithm (GA) and Simulated Annealing (SA). Simulation results show that our proposed algorithm can improve client coverage by 4.5% to 18% (3% to 17% respectively) and network connectivity by 5% to 61% (4.5% to 41% respectively) when compared to GA algorithm (SA algorithm respectively). Keywords Wireless mesh network · Router node placement · Bio-inspired algorithm · Metaheuristic · Chemical reaction optimization

 Lamri Sayad

siad [email protected] 1

LAMOS Laboratory, Faculty of Exact Sciences, University of Bejaia, Bejaia 06000, Algeria

2

Computer Science Department, Msila University, Msila 28000, Algeria

1 Introduction In the last few years, the research in the area of Wireless Mesh Networks (WMN) has experienced a significant growth and an increasing interest among researchers in both industry and academia. The reasons behind this interest are the attractive qualities of this paradigm, which include: low cost and easy deployment, reliability, scalability, connectivity and self-organization. They are intended to play an increasingly essential role in next generation wireless and mobile networks. A Wireless Mesh Network is a communications network made up of self-organized radio nodes organized into a mesh topology. It is also a form of wireless ad hoc network where both ad hoc and infrastructure modes are used forming a hybrid network. WMN often consists of mesh clients, mesh routers (which are typically stationary devices) and gateways as illustrated in Fig. 1. The mesh clients are often laptops, cellphones and other wireless devices. Generally, mesh routers perform a typical ad hoc networking paradigm by forwarding data for other mesh routers in a multihop fashion. In the other hand, gateways are central points where traffic is relayed from/to public networks such as Internet. Hence, in addition to the radio interface, gateways are commonly connected to Internet over wired links. For comprehensive surveys related to WMNs, interes