Abstract
In this paper, we propose new formulations for the optimal connectivity of a tree backbone topology for mobile ad-hoc networks (MANETs). Applications of MANETs include military communications, emergency and disaster recovery, and e-commerce to name a few. Formally, given a graph \(G=(V \cup K,E)\) with set of wireless sensor nodes V, a set of connection links E, and a set of K users, the problem is to find a backbone spanning tree network topology with as many leaves as possible in order to maximize capacity at the lowest power costs for the users which are connected to the leaf nodes of the backbone network. For this purpose, we model a MANET by means of disk graphs where each disk represents the Euclidean distance transmission range of a node \(v \in V\). We propose an exponential and a compact polynomial formulation for the problem. The exponential model is characterized with constraints from the classical maximum leaf spanning tree polytope [18] whilst the compact formulation is characterized with constraints adapted from the classical minimum dominating tree problem [2]. The latter formulation is further strengthened with selected valid inequalities referred to as generalized sub-tour elimination constraints [9]. Our preliminary numerical results indicate that the compact model with additional valid inequalities allows to solve instances to optimality in significantly short CPU time for transmission distances ranging from 100 to 150 ms.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Adasme, P., Andrade, R., Letournel, M., Lisser, A.: Stochastic maximum weight forest problem. Networks 65(4), 289–305 (2015)
Adasme, P., Andrade, R., Lisser, A.: Minimum cost dominating tree sensor networks under probabilistic constraints. Comput. Netw. 112, 208–222 (2017)
Balasundaram, B., Butenko, S.: Graph domination, coloring and cliques in telecommunications. In: Resende, M.G.C., Pardalos, P.M. (eds.) Handbook of Optimization in Telecommunications, pp. 865–890. Springer, New York (2006)
Butenko, S., Cheng, X., Du, D.Z., Pardalos, P.M.: On the construction of virtual backbone for ad-hoc wireless networks. In: Butenko, S., Murphey, R., Pardalos, P.M. (eds.) Cooperative Control: Models, Applications and Algorithms, vol. 1, Dordrecht edn, pp. 43–54. Kluwer, Dordrecht (2002)
Cheng, B., Coyle, A., McGarry, S., Pedan, I., Veytser, L., Wheeler, J.: Characterizing routing with radio-to-router information in a heterogeneous airborne network. IEEE Trans. Wirel. Commun. 12(8), 4183–4195 (2013)
Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to Algorithms. MIT Press and McGraw-Hill, Cumberland (2009)
Ibm, ILOG, CPLEX High-performance mathematical programming engine .http://www.ibm.com/software/integration/optimization/cplex/
Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman, New York (1979)
Gendron, B., Lucena, A., de Cunha, A., Simonetti, L.: Benders decomposition, branch-and-cut, and hybrid algorithms for the minimum connected dominating set problem. Inform. J. Comput. 26(4), 645–657 (2014)
Guha, S., Khuller, S.: Approximation algorithms for connected dominating sets. Algorithmica 20(4), 374–387 (1998)
Ibrahim, H.M., Omar, N.M., William, E.K.: A secure technique for construction and maintenance of a trusted mobile backbone network in MANET. In: IEEE 12th International Conference on Networking, Sensing and Control, pp. 116–121 (2015)
Jia, R., Yang, F., Yao, S., Tian, X., Wang, X., Zhang, W., Xu, J.: Optimal CapacityDelayTradeoff in MANETs with correlation of node mobility. IEEE Trans. Veh. Technol 66(2), 1772–1785 (2017)
Jie, W., Fai, D.: Virtual backbone construction in MANETs using adjustable transmission ranges. IEEE Trans. Mob. Comput. 5(9), 1188–1200 (2006)
Keller, T., Hanzo, L.: Adaptive multicarrier modulation: a convenient framework for time frequency processing in wireless communications. Proc. IEEE 88, 611–640 (2000)
Kim, I., Lee, H.L., Kim, B., Lee, Y.H.: On the use of linear programming for dynamic subchannel and bit allocation in multiuser OFDM. In: IEEE GLOBECOM 2001, vol. 6, pp. 3648–3652 (2001)
Liu, J., Sheng, M., Xu, Y., Li, J., Jiang, X.: End-to-End delay modeling in buffer-limited MANETs: a general theoretical framework. IEEE Trans. Wirel. Commun. 15(1), 498–511 (2016)
Luo, Z., Gan, X., Wang, X., Luo, H.: Optimal ThroughputDelay tradeoff in MANETs with supportive infrastructure using random linear coding. IEEE Trans. Veh. Technol. 65(9), 7543–7558 (2016)
Lucena, A., Maculan, N., Simonetti, L.: Reformulations and solution algorithms for the maximum leaf spanning tree problem. Comput. Manag. Sci. 7, 289–311 (2010)
Selvi, P.F.A., Manikandan, M.S.K.: Ant based multipath backbone routing for load balancing in MANET. IET Commun. 11(1), 136–141 (2017)
Rajashekhar, B., Sunilkumar, M.: Multicast routing in MANET using multiple reliable rings backbone. In: 3rd International Conference on Advances in Recent Technologies in Communication and Computing (ARTCom 2011), pp. 56–61 (2011)
Sheikhan, M., Hemmati, E.: High reliable disjoint path set selection in mobile ad-hoc network using hopfield neural network. IET Commun. 5(11), 1566–1576 (2011)
Stankovic, J.: When sensor and actuator networks cover the world. ETRI J. 30, 627–633 (2008)
Vodnala, D., Aluvala, S., Phani, Kumar, S.: A backbone based multicast routing protocol for route recovery in MANETs. In: 2nd International Conference on Electronics and Communication Systems (ICECS), pp. 237–241 (2015)
Yang, S., Wu, J., Dai, F.: Efficient directional network backbone construction in mobile ad hoc networks. IEEE Trans. Parallel Distrib. Syst. 19(12), 1601–1613 (2008)
Acknowledgments
The authors acknowledge the financial support of Proyectos Dicyt Códigos 061413SG, 061513VC_DAS, 061713AS and CORFO 14IDL2-29919, and Vicerrectoría de Investigación, Desarrollo e Innovación.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2017 Springer International Publishing AG
About this paper
Cite this paper
Adasme, P., Soto, I., Seguel, F. (2017). New Formulations for an Optimal Connectivity Approach for Mobile Ad-hoc Networks. In: Younas, M., Awan, I., Holubova, I. (eds) Mobile Web and Intelligent Information Systems. MobiWIS 2017. Lecture Notes in Computer Science(), vol 10486. Springer, Cham. https://doi.org/10.1007/978-3-319-65515-4_21
Download citation
DOI: https://doi.org/10.1007/978-3-319-65515-4_21
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-65514-7
Online ISBN: 978-3-319-65515-4
eBook Packages: Computer ScienceComputer Science (R0)