Article Contents
Article Contents

# Dispersion with connectivity in wireless mesh networks

• 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.

Mathematics Subject Classification: Primary: 90B80; Secondary: 90B18, 90C90.

 Citation:

• Figure 3.  The Pareto curve with $n=5$ and with different values of $e_{min}$

Figure 1.  An illustration of the TSWB approach

Figure 2.  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

Figure 4.  The solution of problem 2 for $n=10$ with $c_{\min}=40$

Figure 5.  The solutions of problem 2 for $n=5$

Figure 6.  The solutions of problem 3 for $n=5$

Figure 7.  The solutions of problem 3 for $n=10$

Figure 8.  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}$

Figure 9.  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}$

Figure 10.  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.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

Table 1.  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

Table 2.  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
•  I. F. Akyildiz , X. Wang  and  W. Wang , Wireless mesh networks: A survey, Computer Networks, 47 (2005) , 445-487. C. R. Anderson  and  T. S. Rappaport , In-building wideband partition loss measurements at 2.5 and 60 GHz, IEEE Transactions on Wireless Communications, 3 (2004) , 922-928. F. Birlik , Ö. Gürbüz  and  Ö. Erçetin , Iptv home networking via 802.11 wireless mesh networks: An implementation experience, IEEE Transactions on Consumer Electronics, 55 (2009) , 1192-1199. V. E. Brimkov , A. Leach , J. Wu  and  M. Mastroianni , Approximation algorithms for a geometric set cover problem, Discrete Applied Mathematics, 160 (2012) , 1039-1052.  doi: 10.1016/j.dam.2011.11.023. P. Cappanera, A survey on obnoxious facility location problems, Tech. Rep. TR-99-11, University of Pisa, 1999. R. L. Carraway  and  R. L. Schmidt , An improved discrete dynamic programming algorithm for allocating resources among interdependent projects, Management Science, 37 (1991) , 1195-1200.  doi: 10.1287/mnsc.37.9.1195. F. D. Croce , A. Grosso  and  M. Locatelli , A heuristic approach for the max-min diversity problem based on max-clique, Computers & Operations Research, 36 (2009) , 2429-2433.  doi: 10.1016/j.cor.2008.09.007. Z. Drezner and H. W. Hamacher, Facility Location. Applications and Theory Berlin: Springer, 2002. doi: 10.1007/978-3-642-56082-8. E. Erkut  and  S. Neuman , A multiobjective model for locating undesirable facilities, Annals of Operations Research, 40 (1992) , 209-227. S. Fekete  and  H. Meijer , Maximum dispersion and geometric maximum weight cliques, in APPROX '00: Proceedings of the Third International Workshop on Approximation Algorithms for Combinatorial Optimization, (London, UK), Springer-Verlag, (2000) , 132-143.  doi: 10.1007/3-540-44436-X_14. Ö. Gürbüz  and  H. Owen , Power control based QoS provisioning for multimedia in W-CDMA, ACM Wireless Networks (WINET), 8 (2002) , 37-44. R. Heydari  and  E. Melachrinoudis , Location of a semi-obnoxious facility with elliptic maximin and network minisum objectives, European Journal of Operational Research, 223 (2012) , 452-460.  doi: 10.1016/j.ejor.2012.06.039. P. T. Kabamba , S. M. Meerkov  and  C. Y. Tang , Optimal, suboptimal, and adaptive threshold policies for power efficiency of wireless networks, IEEE Transactions on Information Theory, 51 (2005) , 1359-1376.  doi: 10.1109/TIT.2005.844074. R. L. Keeney and H. Raiffa, Decisions with Multiple Objectives New York: John Wiley, 1976. A. M. Khedr  and  W. Osamy , Mobility-assisted minimum connected cover in a wireless sensor network, Journal of Parallel and Distributed Computing, 72 (2012) , 827-837.  doi: 10.1016/j.jpdc.2012.03.009. A. H. Land  and  A. G. Doig , An automatic method of solving discrete programming problems, Econometrica, 28 (1960) , 497-520.  doi: 10.2307/1910129. E. Macambira , An application of tabu search heuristic for the maximum edge-weighted subgraph problem, Annals of Operations Research, 117 (2002) , 175-190.  doi: 10.1023/A:1021525624027. C. Malandraki  and  R. B. Dial , A restricted dynamic programming heuristic algorithm for the time dependent traveling salesman problem, European Journal of Operational, 90 (1996) , 45-55. R. E. Marsten  and  T. L. Morin , A hybrid approach to discrete mathematical programming, Mathematical Programming, 14 (1978) , 21-40.  doi: 10.1007/BF01588949. E. Melachrinoudis  and  Z. Xanthopulos , Semi-obnoxious single facility location in euclidean space, Computers, 30 (2003) , 2191-2209.  doi: 10.1016/S0305-0548(02)00140-5. E. Melachrinoudis , Bicriteria location of a semi-obnoxious facility, Computers, 37 (1999) , 581-593.  doi: 10.1016/S0360-8352(00)00022-X. A. T. Murray  and  R. L. Church , Solving the anti-covering location problem using lagrangian relaxation, Computers, 24 (1997) , 127-140.  doi: 10.1016/S0305-0548(96)00048-2. Y. Ohsawa , Bicriteria euclidean location associated with maximin and minimax criteria, Naval Research Logistics (NRL), 47 (2000) , 581-592.  doi: 10.1002/1520-6750(200010)47:7<581::AID-NAV3>3.0.CO;2-R. Y. Ohsawa  and  K. Tamura , Efficient location for a semi-obnoxious facility, Annals of Operations Research, 123 (2003) , 173-188.  doi: 10.1023/A:1026127430341. J. Rakas , D. Teodorovic  and  T. Kim , Multi-objective modeling for determining location of undesirable facilities, Transportation Research Part D: Transport and Environment, 9 (2004) , 125-138.  doi: 10.1016/j.trd.2003.09.002. M. Rebai , M. L. berre , H. Snoussi , F. Hnaien  and  L. Khoukhi , Sensor deployment optimization methods to achieve both coverage and connectivity in wireless sensor networks, Computers, 59 (2015) , 11-21.  doi: 10.1016/j.cor.2014.11.002. O. Simeone , A. Maeder , M. Peng , O. Sahin  and  W. Yu , Cloud radio access network: Virtualizing wireless access for dense heterogeneous systems, Journal of Communications and Networks, 18 (2016) , 135-149.  doi: 10.1109/JCN.2016.000023. A. J. V. Skriver  and  K. A. Andersen , The bicriterion semi-obnoxious location (bsl) problem solved by an [epsilon]-approximation, European Journal of Operational Research, 146 (2003) , 517-528.  doi: 10.1016/S0377-2217(02)00271-0. J. L. Williams , J. W. Fisher  and  A. S. Willsky , Approximate dynamic programming for communication-constrained sensor network management, IEEE Transactions on Signal Processing, 55 (2007) , 4300-4311.  doi: 10.1109/TSP.2007.896099. D. Wood , An algorithm for finding a maximum clique in a graph, Operation Research Letters, 21 (1997) , 211-217.  doi: 10.1016/S0167-6377(97)00054-0. IBM, IBM ILOG CPLEX Optimizer, www.ibm.com/software/commerce/optimization/cplex-optimizer/, Last retrieved April 2015. The 5G Infrastructure Public Private Partnership, https://5g-ppp.eu/.

Figures(10)

Tables(4)