Multi-Objective Particle Swarm Optimization for Facility
Location Problem in Wireless Mesh Networks
Tarik Mountassir1, Bouchaib Nassereddine 1,3 , Abdelkrim Haqiq1,2 and S amir Bennani 3
1

IR2M Laboratory, FS T, Hassan 1st University, Settat, Morocco
2

3

e-NGN research group, Africa and Middle East

RIME Laboratory, Mohammedia Engineering S chool Agdal, Rabat Morocco

Abstract
Wireless mesh networks have seen a real progress due of their
implementation at a low cost. They present one of Next
Generation Networks technologies and can serve as home,
companies and universities networks. In this paper, we propose
and discuss a new multi-objective model for nodes deployment
optimization in M ulti-Radio M ulti-Channel Wireless M esh
Networks. We exploit the trade-off between network cost and the
overall network performance. This optimization problem is
solved simultaneously by using a meta-heuristic method that
returns a non-dominated set of near optimal solutions. A
comparative study was driven to evaluate the efficiency of the
proposed model.
Keywords: Wireless M esh Networks, Planning, Facility
Location, Improvement, M ulti-objective Optimization.

1. Introduction

wireless interfaces. Furthermore, the use of Multiple-Radio
Multiple-Channel techniques improves the capacity of
mesh networking but it result mo re interferences. Thus the
planning of such networks presents many challenges for
network operators.
Several applications for broadband wireless services have
been deployed based on WMNs. They include community
and neighborhood networks, public safety and security,
building and electric utility automation and transportation
systems. However, these applications continue to confront
the problem of connectivity and performance by poo r
planning of wireless networks. Recently, considerable
interest has been given to WMNs design problem. Most of
these studies have focused on routing [2], interference
measurement and capacity analysis [3], power control [4],
topology control [5], link scheduling [6], channel/radio
assignment [7] and nodes placement [8].

Wireless mesh networks (WMN) have emerged as a
reliable and cost efficient for providing large coverage area
through mutli-hop wireless communications and for
improving wireless ad-hoc Networks, Local Area Networks
(LA N), Personal Area Networks (WPAN) and
Metropolitan Area Networks (WMAN). Thus, the mesh
networking concept can be implemented by IEEE 802.11,
802.15 and 802.16 technologies. In WMNs, Wireless
connection between a sender and a receiver can be ensured
by redundant paths. This increase the network reliability
and robustness.
Such networks consist of Mesh Clients (MCs) and three
types of interconnected wireless routers; Fig.1 illustrates a
relatively static infrastructure of a WMN co mposed by:
Access Points (APs) which provide coverage to MCs,
Mesh relays (MR) which route traffic to other MRs/APs
and Mesh Gateways (MGs) which have an Internet
connection [1]. These routers are organized as the wireless
network backbone and can be equipped by multiple

Fig. 1 Architecture of a WMN

However, few studies have addressed the nodes placement
and the existing contributions have not considered all the
parameters that influence the quality of results.
WMNs planning can be divided into two stages which are
conducted either simultaneously or separately. First, nodes
deployment is a central problem which consists in
positioning MRs in an area in order to provide a network
access with the desired coverage and Qos requirements
while minimizing deployment cost. This issue corresponds
to the Facility Location Problem and the Set Covering
Problem [2] which is NP-hard problem [3]. Second, the
channel assignment is also a NP-hard problem that aims to
assign frequencies to each radio interface in order de
minimize interference. This problem is known as
Automatic Frequency Planning.
The network cost, namely the number of routers, and the
overall network performance present a trade-off that make
WMN planning a sensitive task. This is an open research
issues that need to be investigated.
Many algorithms have been proposed for WMN planning.
The authors of [10], [11], [12] optimized the placement of
MRs (i.e. the backbone WMNs) to provide large coverage
to clients at a min imu m cost while guarantying good
performances and a min imu m level of interference.
Other contributions (eg [13], [14], [15]) have introduced
different methods to select a minimu m number of M Rs to
become gateways while satisfying the throughput,
interference and congestion constraints. In [16], the authors
define a generalized form of a linear program that takes
into account interference and transmission power to
minimize the cost function. The study of [17] presents an
optimization model for WMNs planning that aims to
minimize the network deployment cost while providing
complete clients coverage. Most studies proposed models
with one objective which is to minimize the cost and opted
for exact optimization techniques (CPLEX for example) to
find optimal p lanning solution. However, the planning
problem invokes mult iple conflicting performance
measurements or objectives to be simultaneously
optimized. In this context, a mu lti-objective formu lation of
this problem has been proposed in [18] where the authors
simultaneously optimized the cost, the level of interference
on all network links and minimized gateways neighborhood
congestion.
In recent paper [19], we considered the Multi-Radio MultiChannel WMNs planning where we proposed a multi
objective model for nodes deployment problem that were
based on maximizing total clients coverage and lin ks load
balancing while minimizing deployment cost.

We also proposed, in [20], a relays placement algorithm
that provide newtork connectivity and robustness while in
[21], we proposed and disscussed tow new models for
nodes deployment that, beside minimizing cost and
maximizing total clients coverage, attempted to balance
both links and gateways loads as the common objective
functions subject to the same group of constraints. This
permited us to evoke a comparative study of the three
models. The optimization problems was solved by using
meta-heuristic method that return non-dominated set of
near optimal solutions.
In this contribution,in the one hand, we propose a new and
powerful model that combines four conflictuel objectives
for the facility location problem in wireless mesh networks
including: Cost min imization, maximizat ion coverage,
links, congestion minimization and gateways -congestion
minimization. On the other hand, we use a meta-heuristic
method to resolve this problem, being NP-hard, and we
propose an efficient algorithm for nodes deployment
problem. A co mparative study, between different other
model, will be conducted to show the efficiency of our
complex model.
To the best of out knowledge, this is the first contribution
that proposes a model associating all these conflictuel
objectives functions and that proceed to a simu ltanous
mu lti-objective approach to resolve this problem known as
the facility location problem.
The rest of the paper is organized as follow: Network
model and problem formu lation are presented in Section II.
In Section III, we propose a mult i-objective optimization of
the proposed models and we present numerical results and
analysis. We conclude our work and give directions for
future research in Section IV.

2. Network Model and Formulation
2.1 Network Model
We consider a Multi-Channel Multi-Radio WMN
represented by a graph G = (V, E) where V is the set of
wireless routers and E describes the set of links between
each pair of MRs. We assume the MRs have the same
number of radio interfaces R. Each one is equipped with K
channels (K > R). A link can be established between two
MRs when one of their interfaces use the same channel and
the distance between them is less than the transmission
range of each MR. To consider interference between the
links of WMNs, we adopt the Protocol Interference Model
[3] where a transmission on channel k is successful when
all interferes in the neighborhood of the transmitter and
receiver are silent during the transmission time. Let N = {1,

..., n} be the set of traffic Demand Points (Mesh Clients)
and S = {1, ..., s} be the set of Candidate Sites to host a
node (AP, MR, M G) . Table 1 shows the notations used to
describe the model.
n
s
Ti
Ck jl
Cmax
R

Table 1: List of parameters and variables
Number of Demand Points (DP)
Number of Candidate Sites (CS)
Traffic Demand of DP i
Capacity of link (j,l) using channel k
Maximum capacity of the radio interface of a router
Number of radio interfaces per node

K

Number of channels per radio interface

a ij
b jl
zj
nj
rj

Coverage of a DP i by CS j
Radio connectivity between two candidate sites j and l
Installation of a nodes on CS j
Installation of an Access Point at CS j
Installation of a Router at CS j

gj
x ij
wjk

Selection of a Gateway to CS j
Assignment of DP i to CS j
Installation of a router at CS j using the channel k
Establishing radio communication between CSs j and l
using the channel k
Flow on channel k between CSs j and l
Flow between the gateway and the ISP
All frequency channels Q = {1, ..., K}
Constant

Ljlk
fjlk
Fj
Q
A

1 𝑖𝑓 𝑎 𝑤𝑖𝑟𝑒𝑙𝑒𝑠𝑠 𝑙𝑖𝑛𝑘 𝑖𝑠 𝑒𝑠𝑡𝑎𝑏𝑙𝑖𝑠 𝑕𝑒𝑑
𝐿𝑗𝑙𝑘 = 𝑏𝑒𝑡𝑤𝑒𝑒𝑛 𝐶𝑆𝑠 𝑗 𝑎𝑛𝑑 𝑙 𝑢𝑠𝑖𝑛𝑔 𝑐𝑕𝑎𝑛𝑛𝑒𝑙 𝑘
0
𝑜𝑡𝑕𝑒𝑟𝑤𝑖𝑠𝑒

(9)

In this paper we consider all the parameters that influence
the quality of the solution. Thus, we have formulated our
model through a multitude of criteria that have a significant
impact on the result and we use Integer Linear
Programming to express the Facility Location Problem.
These criteria include constraints to be satisfied and four
objective functions to optimize.

2.2 Objective Functions
Most of the proposed networks planning solutions consider
the cost as the only function to optimize. Ho wever, the
problem invokes many performance measurements and
objectives to be simu ltaneously optimized. This approach
exp loits the trade-off between conflictual functions and
provides more realistic solution.
In this contribution, we propose an integrated model that
we call Link -Gateways Load Balancing (LGLB) that
contains four objective functions to be simultaneously
optimized namely :

We consider the following binary parameters namely:
Cost function:

1 𝑖𝑓 𝐷𝑃 𝑖 𝑖𝑠 𝑐𝑜𝑣𝑒𝑟𝑒𝑑 𝑏𝑦 𝐶𝑆 𝑗
𝑎𝑖𝑗 =
0 𝑜𝑡𝑕𝑒𝑟𝑤𝑖𝑠𝑒

(1)

1 𝑖𝑓 𝑡𝑤𝑜 𝐶𝑆 𝑗, 𝑙 𝑎𝑟𝑒 𝑤𝑖𝑟𝑒𝑠𝑠𝑒𝑙𝑦
𝑏𝑖𝑗 =
𝑐𝑜𝑛𝑛𝑒𝑐𝑡𝑒𝑑
0 𝑜𝑡𝑕𝑒𝑟𝑤𝑖𝑠𝑒

(2)

1 𝑖𝑓 𝑎 𝑛𝑜𝑑𝑒 𝑖𝑠 𝑖𝑛𝑠𝑡𝑎𝑙𝑙𝑒𝑑 𝑜𝑛 𝐶𝑆 𝑗
𝑧𝑗 =
0 𝑜𝑡𝑕𝑒𝑟𝑤𝑖𝑠𝑒

(3)

𝑴𝒊𝒏

𝒏𝒋 + 𝒓𝒋 + 𝒈𝒋
𝒋∈𝑺

(10)

This function minimizes the total deployment cost by
positioning a minimu m nu mber of APs, MRs and M Gs.
Coverage function:

1 𝑖𝑓 𝑎𝑛 𝐴𝑃 𝑖𝑠 𝑖𝑛𝑠𝑡𝑎𝑙𝑙𝑒𝑑 𝑜𝑛 𝐶𝑆 𝑗
𝑛𝑗 =
0 𝑜𝑡𝑕𝑒𝑟𝑤𝑖𝑠𝑒

(4)
𝑴𝒂𝒙

1 𝑖𝑓 𝑎 𝑀𝑒𝑠𝑕 𝑅𝑒𝑙𝑎𝑦 𝑖𝑠 𝑖𝑛𝑠𝑡𝑎𝑙𝑙𝑒𝑑 𝑜𝑛 𝐶𝑆 𝑗
𝑟𝑗 =
0 𝑜𝑡𝑕𝑒𝑟𝑤𝑖𝑠𝑒

(5)

1 𝑖𝑓 𝑎 𝑀𝐺 𝑖𝑠 𝑖𝑛𝑠𝑡𝑎𝑙𝑙𝑒𝑑 𝑜𝑛 𝐶𝑆 𝑗
𝑔𝑗 =
0 𝑜𝑡𝑕𝑒𝑟𝑤𝑖𝑠𝑒

(6)

𝑥 𝑖𝑗 =
𝑤𝑗𝑘 =

1 𝑖𝑓 𝑎 𝐷𝑃 𝑖 𝑖𝑠 𝑎𝑠𝑠𝑖𝑔𝑛𝑒𝑑 𝐶𝑆 𝑗
0 𝑜𝑡𝑕𝑒𝑟𝑤𝑖𝑠𝑒
1 𝑖𝑓 𝑑𝑒𝑣𝑖𝑐𝑒 𝑜𝑛 𝐶𝑆 𝑗 𝑢𝑠𝑖𝑛𝑔 𝑐𝑕𝑎𝑛𝑛𝑒𝑙 𝑘
0 𝑜𝑡𝑕𝑒𝑟𝑤𝑖𝑠𝑒

(7)

(8)

𝒂𝒊𝒋 𝒓𝒋
𝒊∈𝑵 𝒋∈𝑺

(11)

The objective is to maximize the number of clients to be
covered by installed routers.
Links load balancing:
As the flow on a link approaches to its capacity, the link
becomes more prone to congestion. The objective is to
maximize the number of links that has minimu m
congestion by balancing the traffic load among different
links. Thus, We put:

𝑴𝒂𝒙 ( 𝑴𝒊𝒏 𝒋,𝒍∈𝑺, 𝑳𝒌𝒋𝒍 𝑪𝒌𝒋𝒍 − 𝒇𝒌𝒋𝒍

)

𝒌∈𝑸

(12)

𝑳𝒌𝒋𝒍 ≤ 𝟏

∀ 𝒋 ∈ 𝑺, ∀ 𝒌 ∈ 𝑸

(15)

𝒍∈𝑺

Gateways load balancing:

To avoid simultaneous transmission or reception using the
same channel, we have:

The objective is to minimize congestion around gateways
by min imizing the unfair use of MG measured by the
standard deviation of flows entering network through
gateways. This function was used in [18]:
𝒍∈𝑺 𝑭𝒍

𝑴𝒊𝒏

𝟐

(13)

𝒍∈𝑺 𝑭𝒍

𝑳𝒌𝒋𝒍 +
𝒋∈𝑺

𝑳𝒌𝒋𝒍 ≤ 𝟏 ∀ 𝒌 ∈ 𝑸

A link between CS j and CS l can exist only when the two
devices are installed, wirelessly connected and tuned to the
same channel k. thus:
𝟐 𝑳𝒌𝒋𝒍 ≤ 𝒃𝒋𝒍 𝒘𝒌𝒋 + 𝒘𝒌𝒍

2.3 Problem Constraints

(16)

𝒍∈𝑺

∀ 𝒋, 𝒍 ∈ 𝑺, ∀ 𝒌 ∈ 𝑸

(17)

We state that the number of lin ks fro m a mesh node is
limited by the number of radio interfaces. Thus:

The problem constraints are formu lated as follow:
Coverage constraint:

𝒘𝒌𝒋 ≤ 𝑹 𝒛𝒋
The problem must make sure that a given DP i is assigned
to at most one CS j. Thus:
𝒙 𝒊𝒋 ≤ 𝟏

∀𝒊∈ 𝑵

𝒋∈𝑺

(11)

A given DP i must be affected and covered by an installed
node in CS j. Thus:
𝒙 𝒊𝒋 ≤ 𝒂𝒊𝒋 𝒛𝒋

∀ 𝒊 ∈ 𝑵, ∀ 𝒋 ∈ 𝑺

Links - Interference constraints:

∀𝒍 ∈ 𝑺

𝒋∈𝑺 𝒌∈𝑸

(13)

The maximu m nu mber of channel that can be used on link
(j,l) is equal to K. Thus:
𝑳𝒌𝒋𝒍 ≤ 𝑲
𝒌∈𝑸

∀ 𝒋, 𝒍 ∈ 𝑺

The sum of requested service by node on CS j must not
exceed the capacity of radio interface. Thus:
∀𝒋∈ 𝑺

(19)

𝒊∈𝑵

The flow on a link cannot exceed the capacity of this link.
This can be expressed by:

A node can use at most R radio interfaces for transmission
or reception or both. Thus:
𝑳𝒌𝒋𝒍 ≤ 𝑹

(18)

Flow – Capacity constraints:

𝑻𝒊 𝒙 𝒊𝒋 ≤ 𝑪𝒎𝒂𝒙
(12)

∀𝒋∈ 𝑺

𝒌∈𝑸

(14)

To prevent a mesh node from selecting the same channel k
more than once to assign it to its interfaces, we put:

𝒇𝒌𝒋𝒍 ≤ 𝑳𝒌𝒋𝒍 𝑪𝒌𝒋𝒍

∀ 𝒋, 𝒍 ∈ 𝑺, ∀ 𝒌 ∈ 𝑸

(20)

To define the network flow balance, we put:
𝒇𝒌𝒋𝒍 + 𝒇𝒌𝒍𝒋

𝑻𝒊 𝒙 𝒊𝒋 +
𝒊∈𝑵

𝒋∈𝑺 𝒍∈𝑺

= 𝑭𝒋

∀𝒋 ∈ 𝑺

(21)

If a mesh node is installed on CS j as a gateway and AP is
installed in CS l, then the path length (hops number)
between j and l cannot exceed A hops:
𝟐𝒉𝒋𝒍 ≤ 𝑨 (𝒛𝒋 + 𝒛𝒍 )

(22)

A node installed on CS j can route the flow to the Internet
only if it is a gateway. This flow is limited by a large
number M. Thus:
𝑭𝒋 ≤ 𝑴𝒈𝒋

∀𝒋∈ 𝑺

(23)

Robustness constraint:
Once node is deployed at a CS j, it is required that there are
at least two nodes in disjoint paths connecting it to the
network. This ensures any single failure does not
disconnect the network. We put:
𝑳𝒌𝒋𝒍 ≥ 𝟐

∀𝒍∈ 𝑺

𝒋∈𝑺 𝒌∈𝑸

We considered the planning of a network with a grid
topology and we proceeded to the placement of nodes in
three steps:
1.

Access Points Placement: We placed rando mly
the nodes in CSs to cover all the DPs that are not
yet assigned to an access point.

2.

Relays Placement: We added new routers to
connect the graph G (V, E) by requiring all nodes
to have at least two neighbors which ensure
robustness to the network ( eg. Algorith m 2).

3.

Gateways Placement: We choose randomly
among the nodes deployed in steps 1 and 2, who
will act as a gateway.

(24)

All parameters considered in the formulat ion must respect
the following conditions:

Algorithm 1: Topology Auto Planning

𝒓𝒋 , 𝒏𝒋 , 𝒛𝒋 , 𝒈𝒋 , 𝒙 𝒊𝒋 , 𝑳𝒌𝒋𝒍 , 𝒘𝒌𝒋 ∈ 𝟎, 𝟏
∀ 𝒊 ∈ 𝑵, ∀ 𝒋 ∈ 𝑺

(25)

𝒇𝒌𝒋𝒍 , 𝑭𝒋 , 𝑴 ∈ 𝑹 +

(26)

∀ 𝒋, 𝒍 ∈ 𝑺

particle represents the set of binary variables representing
the solution of the problem namely: n j , rj, gj, Ljl k and fjl k..

3. Results and Analysis
In this section, we propose and analyze solutions for nodes
placement models presented in previous section.

3.1Problem Resolution
We use the evolutionary technique called Multi-Ob jective
Particle Swarm Optimization (MOPSO) proposed in [20]
where authors introduced the mechanism of Cro wding
Distance to maintain diversity in the Pareto frontier. This
method is based on the PSO of Kennedy and Eberhart [21]
which is built on the social behavior of flocks of birds that
tend to imitate successful actions they s ee around them,
while there bringing their personal variations. A swarm
(population) consists of several particles (individuals).
In this method, the building of an init ial solution that meets
the constraints is a sensitive task that should be done
carefully. This leads us to propose the algorithm 1 where
we first randomly generate a coverage matrix that
expresses the allocation of every DPi to a CSj and another
connectivity matrix between each CSs j and l. Both
matrixes contribute to the construction of initial feasible
solutions, representing the placement of Mesh APs, Mesh
Relays and M Gs, which will be stored in the archive. A

Input: mut: mutation factor, gmax
Output: Archive
Begin
Initialize swarm
//Construct initial feasible
solutions
Evaluate all particles in swarm // Compute
Objectives
Store all non-dominated solutions into the Archive
Repeat (g < g max)
For each particle in the archive
Co mpute Crowding Distance (CD) value,
So rt the Archive in a descending order of CD
values
Mutation (mut)
Access Points Placement
Relays Placement // invoke Algorithm 2
Gateways Selection
EndFor
Check for constraints satisfaction
Evaluation // Compute Objective functions
Update Archive
g++
Until ( g >= g max )
End

Furthermore, we check for constraints satisfaction and
evaluate the objective functions at every generation of the
swarm in order to provide different non-dominated
solutions.

For each AP j in A
If (AP j is placed on a corner)
Add 2 nodes in the neighborhood / / r = r + 2
End if
If (AP j is placed on an edge)
Add 3 nodes in the neighborhood // r = r + 3
End if
If (AP j is placed on an internal)
Add 4 nodes in the neighborhood // r = r + 4
End if

with minimu m nu mber of nodes. Fig. 4 and show that when
R = 2, the coverage and the throughput are maximized.
While the cost is min imized when R= 3.

6
4
2

0
s=36

s=64

AP

Relays

MG

Devices number

30
25
20

15
10
5

0
Ti=1

Ti=2

Ti=3

Ti=4

Fig. 3 Number of nodes when T i varies

Devices number

AP

Relays

MG

16
14
12
10
8
6
4
2
0
R=2

R=3

Fig. 4 Number of nodes when R varies

Finally, an optimal nu mber of rad io interfaces permits the
maximization of throughput and the demand satisfaction

s=100

35

It is clear that one of the most important goals of WMNs
planning is cost minimization (represented by mesh nodes
numbers in our model). Thus, we run our algorithm and we
selected only the cheapest solutions which are located in
the Pareto frontiers.

We also studied the effect of changing Ti on deployment
cost showed in Fig. 3 while maintaining standard
parameters fixed. When Ti increases, we see the number of
APs and gateways increases highly to satisfy this service
demand to cover more clients. However, it result a low
fairness on links so the throughput decreases.

s=49

Fig. 2 Number of nodes when S varies

End

By varying the number of CSs, we observe in Fig. 2 that
the number of nodes increases when the number of CSs
increases. This is caused by the need of connecting the
network and providing more bandwidth respectively.

MG

8

Until ( all APs are visited )

To show the quality of the proposed solution, we study
the performance of the models and we consider 6×6, 7×7,
8×8and 10×10 grid topologies as CSs where mesh nodes
can be installed. We define standard settings by 200
demand points (groups of clients), the traffic demand Ti =
2Mb/s, Cjl k=Cmax =54Mb/s, A = R = 3 and number of
channel k = 11. The algorith m was coded in JAVA
language and all experiments were carried out on a Core i3
machine.

Relays

10

End For

3.2 Numerical Results and Analysis

AP

12

Devices number

Algorithm 2: Relays Placement
Input: Set of APs
Output Set of M esh Relays
Begin
Initialize r //MRs number r = 0
Repeat

R=4

3.3 Comparative study

The comparison between the four models is made by
analyzing the cost function represented by the number of
APs (Plotted in Fig 5), Relays (Plotted in Fig 6), and M Gs
(Plotted in Fig 7).
Fig.5 shows that the number of APs provided by the
Coverage Model (COV) is greater than that given by the
other three models. This can be exp lained by the fact that
function (11) maintains client coverage as maximal as
possible while satisfying function (10).

APs number

20

COV

LLB

GLB

LGLB

15

LLB

GLB

LGLB

8

6
4

2
0

S=36

S=49

S=64

S=100

Fig. 7 MGs number

Adding function (12) LLB model showed that the
algorithm generates less relays. Thus, in Fig.6, LLB and
LGLB models seem to be better than other models.
When we add a gateway throughput improvement function
in GLB model, we observe that a maximu m throughput
exp loited by all users while satisfying the economic criteria
(Fig.7).
Finally, we note that the model proposed by this article
namely LGLB model, which contains four functions
optimized simultaneously provides a complete and
effective solution for Facility Location problem in WMNs.

10
5

4. Conclusions

0
S=36

S=49

S=64

S=100

Fig. 5 APs Number

30
Relays number

COV

10
MGs number

In the following, we p roceed to a co mparative study of our
integral LGLB model with other models already proposed
and studied by the authors of [21] ie Coverage model
(COV), Lin k Load Balancing model (LLB) and Gateways
Load Balancing model (GLB). We run our algorithm for
the four models and we selected only the cheapest
solutions which are located in the Pareto frontiers. Thus,
we plotted for each model nodes number when CSs
number varies and all other parameters are fixed. The
planning solution will be provided for 200 Demand Points
for all models.

12

COV

LLB

GLB

LGLB

25
20
15

10

In this paper, we proposed a new integrated mutliobjective model for wireless mesh networks planning by
optimizing four objective functions simultaneously subject
to a set of constraints to take into account namely
interference, robustness and load balancing. The use of the
Multi-Objective Particle Swarm Optimization method to
resolve our models provides very interesting results and
lets the network planner decide wh ich solution responds to
his requirements. Additionally, we co mpared the
performance of our proposed model with other previous
models by co mparing the algorithm solutions in term of
deployment cost expressed as access Points, Relays and
gateways number.
As further research topic, we intend to propose a hybrid
algorith m for WMNs Planning that aims to simu ltaneously
place wireless nodes and allocate channels/links.

5
0
S=36

S=49

S=64

Fig. 6 Relays number

S=100

References
[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

I. F. Akyildiz, X. Wang, and W. Wang, "Wireless mesh
networks: a survey", Comput. Netw. ISDN Syst., 2005, Vol.
47, No.4, pp.445-487.
S. Bosio, A. Capone, and M . Cesana, “Radio planning of
wireless area networks”, IEEE/ACM Transactions on
Networking, Vol. 15, No.6, pp. 1414-1427.
O., Kariv, and S.L., Hakimi, “an algorithmic approach to
network location problem IIthe p -medians”, SIAM Journal
on Applied M athematics, Volume .37, Issue. 3, pp.539-560.
S. Biswas and R. M orris, “ExOR: opportunistic multi-hop
routing for wireless network ,” SIGCOMM Comput.
Commun. Rev., vol. 35, no.4,pp. 133-144, 2005.
P. Gupta, P. R. Kumar, The capacity of wireless networks,
IEEE Transactions on Information Theory, Vol. 46, pp.
388–404, 2000.
S. Narayanaswamy, V. Kawadia, R. S. Sreenivas, and P. R.
Kumar, “The COMPOW protocol for power control in ad
hoc
networks:
Theory,
architecture,
algorithm,
implementation, and experimentation,” European Wireless
Conference, 2002.
M . Burkhart, P. von Rickenbach, R. Wattenhofer, and A.
Zollinger, “Does topology control reduce interference?” in
proc. of the 5th ACM international symposium on M obile
ad hoc networking and computing. New York, USA: ACM ,
pp. 9–19, 2004.
G. Brar, D. M . Blough, and P. Santi, “Computationally
efficient scheduling with the physical interference model for
throughput improvement in wireless mesh networks,” in
M obiCom ’06: Proc. 12th annual international conference
on M obile computing and networking. New York, NY, U SA:
ACM , pp. 2–13, 2006.
A. Subramanian, H. Gupta, and S. Das, “M inimum
interference channel assignment in multi-radio wireless
mesh networks,” SECON ’07. 4th Annual IEEE
Communications Society Conference, pp. 481–490, 2007.
S. Nahle and N. M alouch,” Placement algorithms for
WiM AX M esh Network”, Next Generation Teletraffic and
Wired/Wireless Advanced Networking Lecture Notes in
Computer Science, Vol. 5174/2008, pp.37-48, 2008.
F. M artignon and S.Paris and A.Capone,” Optimal Node
Placement in Distributed Wireless Security Architectures”,
Proc. of the 10th international IFIP TC 6 conference on
Networking – Vol. Part I, Valencia, Spain, 2011.
F. Xhafa, C. Sanchez, L. Barolli and E. Spaho, “ Evaluation
of genetic algorithms for mesh router nodes placement in
wireless mesh networks”, J. Ambient Intell Human Comput ,
pp.271–282, 2010.
V. Targon, B. Sans, and A. Capone, “The joint gateway
placement and spatial reuse problem in wireless mesh
networks,” The International Journal of Computer and
Telecommunications Networking, Vol. 54, No.2, February,
2010.
P.Zhou, X.Wang, B.S.M anoj and R.Rao, “On Optimizing
Gateway Placement for Throughput in WirelessM esh
Networks“,Hindawi Publishing Corporation EURASIP
Journal onWireless Communications and Networking, Vol.
2010, Article ID 368423, 12 pages.

[15] Y. Drabu and H. Peyravi,“Planning with Joint Clustering in

[16]

[17]

[18]

[19]

[20]

[21]

[22]

[23]

M ulti-hop Wireless M esh and Sensor Networks”, The Tenth
International Conference on Networks, ICN 2011.
A. Beljadid, A. Hafid, M . Gendreau, “Optimal Design of
Broadband Wireless M esh Networks”, IEEE CLOBECOM ,
pp. 4840 – 4845, 2007.
E. Amaldi, A. Capone, M . Cesana, I. Filippini and F.
M alucelli, “Optimization models and methods for planning
wireless mesh networks”, Computer Networks, Vol. 52,
No.11, 2008.
D. Benyamina, A. Hafid and M . Gendreau,”Throughput
Gateways-Congestion Trade-Off in Designing M ulti-Radio
Wireless Networks”, Journal M obile Networks and
Applications Volume 16 Issue 1, PP. 109-121, 2011.
T. M ountassir, B. Nassereddine, A. Haqiq and S.Bennani, «
Wireless M esh Networks Topology Auto Planning »,
International Journal of Computer Applications, Vol. 52, No.
2, 2012, pp.27-33.
T. M ountassir, B. Nassereddine, A. Haqiq and
S.Bennani« Relays Placement in Wireless M esh Networks
Using a M ulti-Objective Optimization Approach », IEEE
International Conference on Complex System, November 56 Agadir M orocco, in press.
T. M ountassir, B. Nassereddine, A. Haqiq and J.
M ountassir, , « On Optimizing Nodes Deployment in M ultiRadio M ulti-Channel Wireless M esh Networks », 13th IEEE
International Symposium on Computational Intelligence and
Informatics November 20-22, 2012 in Budapest, Hungary,
in press.
C. Raquel , P. Naval, “An effective use of crowding distance
in multi-objective particle swarm optimization”, In Proc. of
Genetic and and Evolutionary Conference (GECCO
2005),257–64, ACM .
J. Kennedy and R. C. Eberhart, “Particle Swarm
Optimization”, In Proc. of the IEEE International
Conference on Neural Networks.1995.

Tarik MOUNTASSIR obtained the Master of Science and
Technology in electronics and the Higher Depth Studies Diploma
in computer sciences from CADY AYYAD University, Morocco, in
2005 and 2007 respectively where he was major his class. He
worked as project manager engineer for the central popular bank
in morocco from 2008 to 2010 and today he is an IT manager at
the Ministry of Interior of Morocco. Mr Mountassir Is now a PhD
student in computer science at HASSAN 1st University, Morocco.
Bouchaib Nassereddine is a Professor in Faculty of sciences and
Techniques, Hassan 1rst University, SETTAT Morocco. He is an
active member of research team RIME in Ecole Mohammadia
d’Ingénieurs - Rabat and Computer, Netw orks, Mobility, and
Modeling Laboratory, Hassan 1st University SETTAT.
Abdelkrim Haqiq is a member of the IEEE and the IEEE
Computer Society.
Sam ir Bennani is a Professor and Computer Science department
Head in Ecole Mohammadia d’Ingénieurs - Rabat. He is the
research team RIME (Netw orking, Modeling and eLearning)
director.

