# American Institute of Mathematical Sciences

• Previous Article
Analysis of a batch service multi-server polling system with dynamic service control
• JIMO Home
• This Issue
• Next Article
A modified scaled memoryless BFGS preconditioned conjugate gradient algorithm for nonsmooth convex optimization
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] Keisuke Minami, Takahiro Matsuda, Tetsuya Takine, Taku Noguchi. Asynchronous multiple source network coding for wireless broadcasting. Numerical Algebra, Control & Optimization, 2011, 1 (4) : 577-592. doi: 10.3934/naco.2011.1.577 [2] Sebastià Galmés. Markovian characterization of node lifetime in a time-driven wireless sensor network. Numerical Algebra, Control & Optimization, 2011, 1 (4) : 763-780. doi: 10.3934/naco.2011.1.763 [3] Li Gang. An optimization detection algorithm for complex intrusion interference signal in mobile wireless network. Discrete & Continuous Dynamical Systems - S, 2019, 12 (4&5) : 1371-1384. doi: 10.3934/dcdss.2019094 [4] Aiwan Fan, Qiming Wang, Joyati Debnath. A high precision data encryption algorithm in wireless network mobile communication. Discrete & Continuous Dynamical Systems - S, 2019, 12 (4&5) : 1327-1340. doi: 10.3934/dcdss.2019091 [5] Sangkyu Baek, Bong Dae Choi. Performance analysis of power save mode in IEEE 802.11 infrastructure wireless local area network. Journal of Industrial & Management Optimization, 2009, 5 (3) : 481-492. doi: 10.3934/jimo.2009.5.481 [6] Hong Il Cho, Myungwoo Lee, Ganguk Hwang. A cross-layer relay selection scheme of a wireless network with multiple relays under Rayleigh fading. Journal of Industrial & Management Optimization, 2014, 10 (1) : 1-19. doi: 10.3934/jimo.2014.10.1 [7] Yang Chen, Xiaoguang Xu, Yong Wang. Wireless sensor network energy efficient coverage method based on intelligent optimization algorithm. Discrete & Continuous Dynamical Systems - S, 2019, 12 (4&5) : 887-900. doi: 10.3934/dcdss.2019059 [8] Tomoya Tainaka, Hiroyuki Masuyama, Shoji Kasahara, Yutaka Takahashi. A Markovian approach to per-flow throughput unfairness in IEEE 802.11 multihop wireless networks. Journal of Industrial & Management Optimization, 2009, 5 (3) : 493-510. doi: 10.3934/jimo.2009.5.493 [9] Jin Soo Park, Kyung Jae Kim, Yun Han Bae, Bong Dae Choi. Admission control by dynamic bandwidth reservation using road layout and bidirectional navigator in wireless multimedia networks. Numerical Algebra, Control & Optimization, 2011, 1 (4) : 627-638. doi: 10.3934/naco.2011.1.627 [10] Miaohua Jiang, Qiang Zhang. A coupled map lattice model of tree dispersion. Discrete & Continuous Dynamical Systems - B, 2008, 9 (1) : 83-101. doi: 10.3934/dcdsb.2008.9.83 [11] Diego F. Aranha, Ricardo Dahab, Julio López, Leonardo B. Oliveira. Efficient implementation of elliptic curve cryptography in wireless sensors. Advances in Mathematics of Communications, 2010, 4 (2) : 169-187. doi: 10.3934/amc.2010.4.169 [12] Ruwu Xiao, Geng Li, Yuping Zhao. On the design of full duplex wireless system with chaotic sequences. Discrete & Continuous Dynamical Systems - S, 2019, 12 (4&5) : 783-793. doi: 10.3934/dcdss.2019052 [13] Tien-Fu Liang, Hung-Wen Cheng. Multi-objective aggregate production planning decisions using two-phase fuzzy goal programming method. Journal of Industrial & Management Optimization, 2011, 7 (2) : 365-383. doi: 10.3934/jimo.2011.7.365 [14] Hyukjin Lee, Cheng-Chew Lim, Jinho Choi. Joint backoff control in time and frequency for multichannel wireless systems and its Markov model for analysis. Discrete & Continuous Dynamical Systems - B, 2011, 16 (4) : 1083-1099. doi: 10.3934/dcdsb.2011.16.1083 [15] Shunfu Jin, Wuyi Yue, Xuena Yan. Performance evaluation of a power saving mechanism in IEEE 802.16 wireless MANs with bi-directional traffic. Journal of Industrial & Management Optimization, 2011, 7 (3) : 717-733. doi: 10.3934/jimo.2011.7.717 [16] Sung-Hwa Lim, Se Won Lee, Byoung-Hoon Lee, Seongil Lee, Ho Woo Lee. Stochastic method for power-aware checkpoint intervals in wireless environments: Theory and application. Journal of Industrial & Management Optimization, 2012, 8 (4) : 969-986. doi: 10.3934/jimo.2012.8.969 [17] Koen De Turck, Sabine Wittevrongel. Receiver buffer behavior for the selective repeat protocol over a wireless channel: An exact and large-deviations analysis. Journal of Industrial & Management Optimization, 2010, 6 (3) : 603-619. doi: 10.3934/jimo.2010.6.603 [18] Hanyu Cao, Meiying Zhang, Huanxi Cai, Wei Gong, Min Su, Bin Li. A zero-forcing beamforming based time switching protocol for wireless powered internet of things system. Journal of Industrial & Management Optimization, 2017, 13 (5) : 1-10. doi: 10.3934/jimo.2019086 [19] Ryan Loxton, Qun Lin. Optimal fleet composition via dynamic programming and golden section search. Journal of Industrial & Management Optimization, 2011, 7 (4) : 875-890. doi: 10.3934/jimo.2011.7.875 [20] Leong-Kwan Li, Sally Shao. Convergence analysis of the weighted state space search algorithm for recurrent neural networks. Numerical Algebra, Control & Optimization, 2014, 4 (3) : 193-207. doi: 10.3934/naco.2014.4.193

2018 Impact Factor: 1.025