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] Alberto Bressan, Sondre Tesdal Galtung. A 2-dimensional shape optimization problem for tree branches. Networks & Heterogeneous Media, 2020  doi: 10.3934/nhm.2020031 [2] Qiang Fu, Yanlong Zhang, Yushu Zhu, Ting Li. Network centralities, demographic disparities, and voluntary participation. Mathematical Foundations of Computing, 2020, 3 (4) : 249-262. doi: 10.3934/mfc.2020011 [3] Yahia Zare Mehrjerdi. A new methodology for solving bi-criterion fractional stochastic programming. Numerical Algebra, Control & Optimization, 2020  doi: 10.3934/naco.2020054 [4] Serge Dumont, Olivier Goubet, Youcef Mammeri. Decay of solutions to one dimensional nonlinear Schrödinger equations with white noise dispersion. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020456 [5] M. S. Lee, H. G. Harno, B. S. Goh, K. H. Lim. On the bang-bang control approach via a component-wise line search strategy for unconstrained optimization. Numerical Algebra, Control & Optimization, 2021, 11 (1) : 45-61. doi: 10.3934/naco.2020014 [6] Min Chen, Olivier Goubet, Shenghao Li. Mathematical analysis of bump to bucket problem. Communications on Pure & Applied Analysis, 2020, 19 (12) : 5567-5580. doi: 10.3934/cpaa.2020251 [7] Qingfang Wang, Hua Yang. Solutions of nonlocal problem with critical exponent. Communications on Pure & Applied Analysis, 2020, 19 (12) : 5591-5608. doi: 10.3934/cpaa.2020253 [8] Stefano Bianchini, Paolo Bonicatto. Forward untangling and applications to the uniqueness problem for the continuity equation. Discrete & Continuous Dynamical Systems - A, 2020  doi: 10.3934/dcds.2020384 [9] Marco Ghimenti, Anna Maria Micheletti. Compactness results for linearly perturbed Yamabe problem on manifolds with boundary. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020453 [10] Fioralba Cakoni, Pu-Zhao Kow, Jenn-Nan Wang. The interior transmission eigenvalue problem for elastic waves in media with obstacles. Inverse Problems & Imaging, , () : -. doi: 10.3934/ipi.2020075 [11] 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 [12] Shenglan Xie, Maoan Han, Peng Zhu. A posteriori error estimate of weak Galerkin fem for second order elliptic problem with mixed boundary condition. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020340 [13] Gang Bao, Mingming Zhang, Bin Hu, Peijun Li. An adaptive finite element DtN method for the three-dimensional acoustic scattering problem. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020351 [14] Zhilei Liang, Jiangyu Shuai. Existence of strong solution for the Cauchy problem of fully compressible Navier-Stokes equations in two dimensions. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020348 [15] Mehdi Badsi. Collisional sheath solutions of a bi-species Vlasov-Poisson-Boltzmann boundary value problem. Kinetic & Related Models, , () : -. doi: 10.3934/krm.2020052 [16] Lingfeng Li, Shousheng Luo, Xue-Cheng Tai, Jiang Yang. A new variational approach based on level-set function for convex hull problem with outliers. Inverse Problems & Imaging, , () : -. doi: 10.3934/ipi.2020070

2019 Impact Factor: 1.366