Robust communication network formation: a decentralized approach

Springer Science and Business Media LLC - 2019
Christopher Diaz1, Alexander G. Nikolaev1, Abhinav Perla1, Alexander Veremyev2, Eduardo L. Pasiliao3
1Department of Industrial and Systems Engineering, University at Buffalo, Buffalo, USA
2Department of Industrial Engineering and Management Systems, University of Central Florida, Orlando, USA
3AFRL Munitions Directorate, Air Force Research Laboratory, Eglin, USA

Tóm tắt

AbstractThe formation of robust communication networks between independently acting agents is of practical interest in multiple domains, for example, in sensor placement and Unmanned Aerial Vehicle communication. These are the cases where it is only feasible to have the communicating actors modify the network locally, i.e., without relying on the knowledge of the entire network structure and the other actors’ decisions. This calls for approaches to optimizing network structure in a decentralized way. We present an actor-oriented modeling approach to design and parameterize models that enable the creation of networks that exhibit the properties desirable for efficient information sharing. Computational experiments show that the achieved network formation rules, specified in a calculated way, allow agents to maintain robust network structure by activating only a limited number of direct communication channels. The obtained results are promising, as evidenced by the reported comparisons to optimal network configuration solutions obtained in a centralized way.

Từ khóa


Tài liệu tham khảo

Akyildiz I, Kasimoglu I. Wireless sensor and actor networks: research challenges. Ad Hoc Netw J. 2004;2(4):351.

Beard RW, McLain TW, Nelson DB, Kingston D, Johanson D. Decentralized cooperative aerial surveillance using fixed-wing miniature UAVs. Proc IEEE. 2006;94(7):1306.

Bala V, Goyal S. Learning from neighbours. Rev Econ Stud. 1998;65(3):595.

Gale D, Kariv S. Bayesian learning in social networks. Games Econ Behav. 2003;45(2):329.

Villatoro D, Sabater-Mir J, Sen S. Robust convention emergence in social networks through self-reinforcing structures dissolution. ACM Trans Auton Adapt Syst. 2013;8(1):2:1. https://doi.org/10.1145/2451248.2451250.

Safar M, Mahdi K, Torabi S. Network robustness and irreversibility of information diffusion in Complex networks. J Comput Sci. 2011;2(3):198. https://doi.org/10.1016/j.jocs.2011.05.005.

Jiang C, Chen Y, Liu K. Evolutionary dynamics of information diffusion over social networks. IEEE Trans Signal Process. 2014;62(17):4573. https://doi.org/10.1109/TSP.2014.2339799.

Greenan CC. Diffusion of innovations in dynamic networks. J R Stat Soc Series A. 2015;178(1):147. https://doi.org/10.1111/rssa.12054/pdf.

Pandit S, Yang Y, Chawla N. Maximizing information spread through influence structures in social networks. In: 2012 IEEE 12th international conference on data mining workshops (ICDMW); 2012. p. 258–65. https://doi.org/10.1109/ICDMW.2012.140

Snijders TA, Van de Bunt GG, Steglich CE. Introduction to stochastic actor-based models for network dynamics. Social Netw. 2010;32(1):44.

Melodia T, Pompili D, Gungor VC, Akyildiz IF. A Distributed coordination framework for wireless sensor and actor networks. In: Proceedings of the 6th ACM international symposium on mobile Ad Hoc networking and computing. New York: ACM; 2005 MobiHoc ’05, p. 99–110. https://doi.org/10.1145/1062689.1062704.

Samadi M, Nikolaev A, Nagi R. A subjective evidence model for influence maximization in social networks. Omega. 2016;59:263.

Farasat A, Nikolaev AG. Social structure optimization in team formation. Comput Op Res. 2016;74:127.

Wu XM, Li Z, So AM, Wright J, Chang SF. Learning with partially absorbing random walks. In: Advances in neural information processing systems; 2012, p. 3077–85. http://papers.nips.cc/paper/4833-learning-with-partially-absorbing-random-walks.

De J, Zhang X, Cheng L. Transduction on directed graphs via absorbing random walks. arXiv preprint arXiv:1402.4566; 2014;1402:4566.

Kan Z, Yucelen T, Doucette E, Pasiliao E. A finite-time consensus framework over time-varying graph topologies with temporal constraints. J Dyn Syst Meas Control. 2017;139(7):071012.

Olfati-Saber R, Fax A, Murray RM. Consensus and cooperation in networked multi-agent systems. Proc IEEE. 2007;95(1):215.

Smith B, Egerstedt M, Howard A. Automatic deployment and formation control of decentralized multi-agent networks. In: IEEE international conference on robotics and automation, 2008. ICRA; 2008, p. 134–139. https://doi.org/10.1109/ROBOT.2008.4543198.

Lanham M, Morgan G, Carley K. Social network modeling and agent-based simulation in support of crisis de-escalation. IEEE Trans Syst Man Cyber Syst. 2014;44(1):103. https://doi.org/10.1109/TSMCC.2012.2230255.

Chinowsky P, Diekmann J, Galotti V. Social network model of construction. J Constr Eng Manag. 2008;134(10):804. https://doi.org/10.1061/(ASCE)0733-9364(2008)134:10(804).

Watts A. A dynamic model of network formation. Games Econ Behav. 2001;34(2):331. https://doi.org/10.1006/game.2000.0803.

Jackson MO, Watts A. The evolution of social and economic networks. J Econ Theory. 2002;106(2):265. https://doi.org/10.1006/jeth.2001.2903.

Snijders TA. The statistical evaluation of social network dynamics. Sociol Methodol. 2001;31(1):361.

Sabattini L, Secchi C, Chopra N. Decentralized control for maintenance of strong connectivity for directed graphs. In: 21st mediterranean conference on control and automation; 2013, p. 978–86. https://doi.org/10.1109/MED.2013.6608840

Diaz C, Nikolaev A, Pasiliao E. A Decentralized deterministic information propagation model for robust communication. In: International conference on computational social networks. Springer; 2018, p. 235–46.

Nikolaev AG, Razib R, Kucheriya A. On efficient use of entropy centrality for social network analysis and community detection. Soc Netw. 2015;40:154.

Kemeny JG, Snell JL. Others, Finite markov chains, vol. 356. Princeton: van Nostrand Princeton; 1960.

Latora V, Marchiori M. Efficient behavior of small-world networks. Phys Rev Lett. 2001;87(19):198701.

Nelder JA, Mead R. A simplex method for function minimization. Comput J. 1965;7(4):308. https://doi.org/10.1093/comjnl/7.4.308.

Snijders TAB. Markov chain monte Carlo estimation of exponential random graph models. J Soc Str. 2002;3(2):1.

Mukherjee T, Veremyev A, Kumar P, Pasiliao E Jr. The minimum edge compact spanner network design problem. 2017. arXiv preprint arXiv:1712.04010

Veremyev A, Prokopyev OA, Pasiliao EL. Critical nodes for distance-based connectivity and related problems in graphs. Networks. 2015;66(3):170.

L. Gurobi Optimization. Gurobi optimizer reference manual. 2018. http://www.gurobi.com

Thông tin
Thông tin xuất bản

Springer Science and Business Media LLC

Thông tin tác giả