# American Institute of Mathematical Sciences

• Previous Article
A modified scaled memoryless BFGS preconditioned conjugate gradient algorithm for nonsmooth convex optimization
• JIMO Home
• This Issue
• Next Article
Analysis of a batch service multi-server polling system with dynamic service control
April  2018, 14(2): 759-784. doi: 10.3934/jimo.2017074

## Dispersion with connectivity in wireless mesh networks

 1 R & D Center, Information Technologies Department, Migros T.A.Ş., 34758, Istanbul, Turkey 2 Faculty of Engineering and Natural Sciences, Sabanci University, 34956, Istanbul, Turkey

* Corresponding author: byuceoglu@migros.com.tr

Received  March 2016 Published  September 2017

We study a multi-objective access point dispersion problem, where the conflicting objectives of maximizing the distance and maximizing the connectivity between the agents are considered with explicit coverage (or Quality of Service) constraints. We model the problem first as a multi-objective model, and then, we consider the constrained single objective alternatives, which we propose to solve using three approaches: The first approach is an optimal tree search algorithm, where bounds are used to prune the search tree. The second approach is a beam search heuristic, which is also used to provide lower bound for the first approach. The third approach is a straightforward integer programming approach. We present an illustrative application of our solution approaches in a real wireless mesh network deployment problem.

Citation: Birol Yüceoǧlu, ş. ilker Birbil, özgür Gürbüz. Dispersion with connectivity in wireless mesh networks. Journal of Industrial & Management Optimization, 2018, 14 (2) : 759-784. doi: 10.3934/jimo.2017074
##### References:

show all references

##### References:
The Pareto curve with $n=5$ and with different values of $e_{min}$
An illustration of the TSWB approach
The candidate locations on the floor plan. The dashed lines in the middle of the building is a meshed glass and solid lines around the rooms (colored areas) are walls
The solution of problem 2 for $n=10$ with $c_{\min}=40$
The solutions of problem 2 for $n=5$
The solutions of problem 3 for $n=5$
The solutions of problem 3 for $n=10$
The performance of the tree search algorithm for the multi-objective problem ($n=10$, $e_{min}=0.8$). The cardinality of the set of all solutions is $\binom{70}{10} \approx 3.967\times 10^{11}$
The performance of the tree search algorithm for the problem in Figure 4. The cardinality of the set of all solutions is $\binom{70}{10} \approx 3.967\times 10^{11}$
The performance of the tree search algorithm for the problem in Figure 7(a)
 0 0.42 0.33 0.25 0.86 0.48 0.48 0.37 0.81 0.29 0.42 0 0.64 0.74 0.1 0.54 0.92 0.61 0.68 0.45 0.33 0.64 0 0.23 0.41 0.25 0.51 0.72 0.4 0.55 0.25 0.74 0.23 0 0.42 0.48 0.75 0.55 0.54 0.44 0.86 0.1 0.41 0.42 0 0.77 0.52 0.4 0.24 0.24 0.48 0.54 0.25 0.48 0.77 0 0.33 0.78 0.63 0.92 0.48 0.92 0.51 0.75 0.52 0.33 0 0.42 0.31 0.41 0.37 0.61 0.72 0.55 0.4 0.78 0.42 0 0.47 0.55 0.81 0.68 0.4 0.54 0.24 0.63 0.31 0.47 0 0.4 0.29 0.45 0.55 0.44 0.24 0.92 0.41 0.55 0.4 0
 0 0.42 0.33 0.25 0.86 0.48 0.48 0.37 0.81 0.29 0.42 0 0.64 0.74 0.1 0.54 0.92 0.61 0.68 0.45 0.33 0.64 0 0.23 0.41 0.25 0.51 0.72 0.4 0.55 0.25 0.74 0.23 0 0.42 0.48 0.75 0.55 0.54 0.44 0.86 0.1 0.41 0.42 0 0.77 0.52 0.4 0.24 0.24 0.48 0.54 0.25 0.48 0.77 0 0.33 0.78 0.63 0.92 0.48 0.92 0.51 0.75 0.52 0.33 0 0.42 0.31 0.41 0.37 0.61 0.72 0.55 0.4 0.78 0.42 0 0.47 0.55 0.81 0.68 0.4 0.54 0.24 0.63 0.31 0.47 0 0.4 0.29 0.45 0.55 0.44 0.24 0.92 0.41 0.55 0.4 0
 0.06 0.40 0.27 0.31 0.83 0.73 0.89 0.04 0.51 0.18 0.93 0.89 0.99 0.87 0.94 0.15 0.99 0.66 0.98 0.58 0.40 0.99 0.79 0.77 0.68 0.31 0.66 0.30 0.76 0.91 0.88 0.52 0.32 0.26 0.35 0.63 0.06 0.48 0.54 0.89 0.53 0.73 0.77 0.68 0.43 0.10 0.34 0.03 0.34 0.91 0.42 0.01 0.10 0.81 0.13 0.40 0.72 0.52 0.47 0.97 0.18 0.75 0.48 0.95 0.44 0.68 0.70 0.06 0.89 0.82 0.33 0.73 0.82 0.75 0.52 0.88 0.21 0.62 0.74 0.67 Bounds 0.99 0.66 0.98 0.58 0.83 0.99 0.89 0.77 0.99 0.91 0.98 0.97 0.89 0.99 0.89 0.95
 0.06 0.40 0.27 0.31 0.83 0.73 0.89 0.04 0.51 0.18 0.93 0.89 0.99 0.87 0.94 0.15 0.99 0.66 0.98 0.58 0.40 0.99 0.79 0.77 0.68 0.31 0.66 0.30 0.76 0.91 0.88 0.52 0.32 0.26 0.35 0.63 0.06 0.48 0.54 0.89 0.53 0.73 0.77 0.68 0.43 0.10 0.34 0.03 0.34 0.91 0.42 0.01 0.10 0.81 0.13 0.40 0.72 0.52 0.47 0.97 0.18 0.75 0.48 0.95 0.44 0.68 0.70 0.06 0.89 0.82 0.33 0.73 0.82 0.75 0.52 0.88 0.21 0.62 0.74 0.67 Bounds 0.99 0.66 0.98 0.58 0.83 0.99 0.89 0.77 0.99 0.91 0.98 0.97 0.89 0.99 0.89 0.95
The problem parameters
 $d_0 = 1$ meter $\lambda = (3\times 10^8)/(2.4 \times 10^9)$ $\alpha = 2$ $B= 20$ GHz $P_t = 4$ Watt $N_0=3.98\times10^{-17}$ $G_t = 1$ $t^{wall}=5.4$ dB, $t^{glass}=7.7$ dB
 $d_0 = 1$ meter $\lambda = (3\times 10^8)/(2.4 \times 10^9)$ $\alpha = 2$ $B= 20$ GHz $P_t = 4$ Watt $N_0=3.98\times10^{-17}$ $G_t = 1$ $t^{wall}=5.4$ dB, $t^{glass}=7.7$ dB
Results of the computational study for the single objective problems
 Instance Beam Search TSWB CPLEX Model $n$ Constraint Gap Time Time 2 5 $c(\mathbf{x}) \geq 8$ 0.00% 1 129 2 5 $c(\mathbf{x}) \geq 9$ 50.00% 1 561 2 10 $c(\mathbf{x}) \geq 35$ 0.00% 155 1566 2 10 $c(\mathbf{x}) \geq 40$ 50.00% 23 1695 3 5 $d(\mathbf{x}) \geq 15$ 0.10% 1 28 3 5 $d(\mathbf{x}) \geq 20$ 0.00% 1 7 3 10 $d(\mathbf{x}) \geq 10$ 0.18% 22 154 3 10 $d(\mathbf{x}) \geq 15$ 3.54% 79 12
 Instance Beam Search TSWB CPLEX Model $n$ Constraint Gap Time Time 2 5 $c(\mathbf{x}) \geq 8$ 0.00% 1 129 2 5 $c(\mathbf{x}) \geq 9$ 50.00% 1 561 2 10 $c(\mathbf{x}) \geq 35$ 0.00% 155 1566 2 10 $c(\mathbf{x}) \geq 40$ 50.00% 23 1695 3 5 $d(\mathbf{x}) \geq 15$ 0.10% 1 28 3 5 $d(\mathbf{x}) \geq 20$ 0.00% 1 7 3 10 $d(\mathbf{x}) \geq 10$ 0.18% 22 154 3 10 $d(\mathbf{x}) \geq 15$ 3.54% 79 12
 [1] Juan Manuel Pastor, Javier García-Algarra, José M. Iriondo, José J. Ramasco, Javier Galeano. Dragging in mutualistic networks. Networks & Heterogeneous Media, 2015, 10 (1) : 37-52. doi: 10.3934/nhm.2015.10.37 [2] Alba Málaga Sabogal, Serge Troubetzkoy. Minimality of the Ehrenfest wind-tree model. Journal of Modern Dynamics, 2016, 10: 209-228. doi: 10.3934/jmd.2016.10.209 [3] Rui Hu, Yuan Yuan. Stability, bifurcation analysis in a neural network model with delay and diffusion. Conference Publications, 2009, 2009 (Special) : 367-376. doi: 10.3934/proc.2009.2009.367 [4] Christina Surulescu, Nicolae Surulescu. Modeling and simulation of some cell dispersion problems by a nonparametric method. Mathematical Biosciences & Engineering, 2011, 8 (2) : 263-277. doi: 10.3934/mbe.2011.8.263 [5] Alessandro Gondolo, Fernando Guevara Vasquez. Characterization and synthesis of Rayleigh damped elastodynamic networks. Networks & Heterogeneous Media, 2014, 9 (2) : 299-314. doi: 10.3934/nhm.2014.9.299 [6] Juan Manuel Pastor, Javier García-Algarra, Javier Galeano, José María Iriondo, José J. Ramasco. A simple and bounded model of population dynamics for mutualistic networks. Networks & Heterogeneous Media, 2015, 10 (1) : 53-70. doi: 10.3934/nhm.2015.10.53 [7] Ardeshir Ahmadi, Hamed Davari-Ardakani. A multistage stochastic programming framework for cardinality constrained portfolio optimization. Numerical Algebra, Control & Optimization, 2017, 7 (3) : 359-377. doi: 10.3934/naco.2017023 [8] Luke Finlay, Vladimir Gaitsgory, Ivan Lebedev. Linear programming solutions of periodic optimization problems: approximation of the optimal control. Journal of Industrial & Management Optimization, 2007, 3 (2) : 399-413. doi: 10.3934/jimo.2007.3.399 [9] Alexandr Mikhaylov, Victor Mikhaylov. Dynamic inverse problem for Jacobi matrices. Inverse Problems & Imaging, 2019, 13 (3) : 431-447. doi: 10.3934/ipi.2019021 [10] Armin Lechleiter, Tobias Rienmüller. Factorization method for the inverse Stokes problem. Inverse Problems & Imaging, 2013, 7 (4) : 1271-1293. doi: 10.3934/ipi.2013.7.1271 [11] Hildeberto E. Cabral, Zhihong Xia. Subharmonic solutions in the restricted three-body problem. Discrete & Continuous Dynamical Systems - A, 1995, 1 (4) : 463-474. doi: 10.3934/dcds.1995.1.463 [12] Michel Chipot, Mingmin Zhang. On some model problem for the propagation of interacting species in a special environment. Discrete & Continuous Dynamical Systems - A, 2020  doi: 10.3934/dcds.2020401 [13] Fritz Gesztesy, Helge Holden, Johanna Michor, Gerald Teschl. The algebro-geometric initial value problem for the Ablowitz-Ladik hierarchy. Discrete & Continuous Dynamical Systems - A, 2010, 26 (1) : 151-196. doi: 10.3934/dcds.2010.26.151 [14] Gloria Paoli, Gianpaolo Piscitelli, Rossanno Sannipoli. A stability result for the Steklov Laplacian Eigenvalue Problem with a spherical obstacle. Communications on Pure & Applied Analysis, 2021, 20 (1) : 145-158. doi: 10.3934/cpaa.2020261 [15] Rongchang Liu, Jiangyuan Li, Duokui Yan. New periodic orbits in the planar equal-mass three-body problem. Discrete & Continuous Dynamical Systems - A, 2018, 38 (4) : 2187-2206. doi: 10.3934/dcds.2018090 [16] Marion Darbas, Jérémy Heleine, Stephanie Lohrengel. Numerical resolution by the quasi-reversibility method of a data completion problem for Maxwell's equations. Inverse Problems & Imaging, 2020, 14 (6) : 1107-1133. doi: 10.3934/ipi.2020056

2019 Impact Factor: 1.366

## Metrics

• HTML views (748)
• Cited by (0)

• on AIMS