Increasing the performance of a Mobile Ad-hoc Network using a game-theoretic approach to drone positioning

S. Blakeway ; D. V. Gromov ; E. V. Gromova ; A. S. Kirpichnikova ; T. M. Plekhanova

Vestnik Sankt-Peterburgskogo universiteta. Prikladnaâ matematika, informatika, processy upravleniâ, Tome 15 (2019) no. 1, pp. 22-38

Résumé

We describe a novel game-theoretic formulation of the optimal mobile agents' placement problem which arises in the context of Mobile Ad-hoc Networks (MANETs). This problem is modelled as a sequential multistage game. The definitions of both the Nash equilibrium and cooperative solution are given. A modification was proposed to ensure the existence of a Nash equilibrium. A modelling environment for the analysis of different strategies of the players was developed in MATLAB. The programme generates various game situations and determines each player move by solving respective optimisation problems. Using the developed environment, two specific game scenarios were considered in detail. The proposed novel algorithm was implemented and tested using Network Simulator 3 (NS-3). The results show that the proposed novel algorithm increases network performance by using game theory principles and techniques.

Détail

Keywords: dynamic games, multistage games, graphs, Nash equilibria
Mots-clés : MANET, drone placement, NS-3.

Bibliographie

[1] Chaubey N., Aggarwal A., Gandhi S., Jani K. A., “Performance analysis of TSDRP and AODV routing protocol under black hole attacks in MANETs by varying network size”, Advanced Computing $\$ Communication Technologies (ACCT), IEEE, 2015, 320–324

[2] Anjum S. S., Noor R. M., Anisi M. H., “Survey on MANET based communication scenarios for search and rescue operations”, IT Convergence and Security (ICITCS), IEEE, 2015, 1–5

[3] Erim O., Wright C., “Optimized mobility models for disaster recovery using UAVs”, 2017 IEEE 28th Annual Intern. Symposium on Personal, Indoor, and Mobile Radio Communications (PIMRC) (Montreal, QC, 2017), 1–5 | DOI | MR

[4] Benkaouha H., Abdelli A., Badache N., Ben-Othman J., Mokdad L., “Towards improving failure detection in mobile ad hoc networks”, IEEE Global Communications Conference (GLOBECOM), IEEE, 2015, 1–6

[5] Son T. T., Le Minh H., Sexton G., Aslam N., Boubezari R., “A new mobility, energy and congestion aware routing scheme for MANETs”, Communication Systems, Networks $\$ Digital Signal Processing (CSNDSP), IEEE, 2014, 771–77

[6] Blakeway S., Pullin A., “The effect of node density on routing protocol performance in mobile Ad-hoc Networks”, Proc. of the Convergence of Telecommunications, Networking and Broadcasting, 2007, 237–240

[7] Resende C., Almulla M., Boukerche A., “The use of Erasure Coding for video streaming unicast over Vehicular Ad-hoc Networks”, Local Computer Networks, 38 (2013), 715–718

[8] Sahingoz O. K., “Mobile networking with UAVs: Opportunities and challenges”, Intern. Conference on Unmanned Aircraft Systems (ICUAS), 2013, 933–941 | DOI

[9] Gupta L., Jain R., Vaszkun G., “Survey of important issues in UAV communication networks”, IEEE Communications Surveys $\$ Tutorials, 18:2 (2016), 1123–1152 | DOI | MR

[10] Zhu M., Cai Z., Zhao D., Wang J., Xu M., “Using multiple unmanned aerial vehicles to maintain connectivity of MANETs”, 23rd Intern. Conference on Computer Communication and Networks (ICCCN) (Shanghai, 2014), 1–7 | DOI

[11] Xuelin C., Zuxun S., “An overview of slot assignment (SA) for TDMA”, Signal Processing, Communications and Computing (ICSPCC), IEEE, 2015, 1–5

[12] McKinsey J. C. C., Introduction to the Theory of Games, Dover Publ., Dover, 2003, 384 pp. | MR | Zbl

[13] Fudenberg D., Tirole J., Game Theory, The MIT Press, Cambridge, 1991, 604 pp. | MR

[14] Poongothai T., Jayarajan K., “A noncooperative game approach for intrusion detection in Mobile Ad-hoc Networks”, Computing, Communication and Networking (ICCCn), IEEE, 2008, 1–4

[15] Wang F., Mo Y., Huang B., “Defending reputation system against false recommendation in Mobile Ad-hoc Network”, Networking, Sensing and Control, IEEE, 2008, 488–493

[16] Li F., Yang Y., Wu J., “Attack and flee: game-theory-based analysis on interactions among nodes in MANETs”, IEEE Transactions on Systems, Man, and Cybernetics. Pt B. Cybernetics, 40:3 (2010), 612–622 | DOI

[17] Wang X., Feng R., Wu Y., Che S., Ren Y., “A game theoretic malicious nodes detection model in MANETs”, Mobile Ad-hoc and Sensor Systems, IEEE, 2012, 1–6

[18] Wang K., Wu M., Ding C., Lu W., “Game-based modelling of node cooperation in Ad-hoc Networks”, Wireless and Optical Communications Conference (WOCC), 2010, 1–5

[19] Ermolin N. A., Mazalov V. V., Pechnikov A. A., “Game-theoretic methods for finding communities in the academic Web”, Trudy SPIIRAN, 55 (2017), 237–254 (In Russian)

[20] Gubanov D. A., Novikov D. A., Chkharteshvili A. G., Social networks: models of information influence, control and confrontation, Phizmatlit Publ., M., 2010, 228 pp. (In Russian)

[21] Jackson M. O., Social and Economic Networks, Princeton Univ. Press, Princeton, 2008, 520 pp. | MR | Zbl

[22] Petrosyan L. A., Sedakov A. A., “Multistage network games with complete information”, Autom. Remote Control, 75:8 (2014), 1532–1540 | DOI | MR

[23] Bulgakova M. A., Petrosyan L. A., “Cooperative network games with pairwise interactions”, Mathematical game theory and its applications, 7:38 (2015), 7–18 (In Russian) | MR | Zbl

[24] Parilina E. M., “Cooperative game on sending data in the wireless network”, UBS, 31:1 (2010), 191–209

[25] Novikov D. A., “Games and networks”, Automation and Remote Control, 75:6 (2014), 1145–1154 | DOI | MR

[26] Han Z., Niyato D., Saad W., Basar T., Hjorungnes A., Game Theory in Wireless and Communication Networks. Theory, Models, and Applications, Cambridge University Press, New York, 2012, 530 pp. | Zbl

[27] Bazenkov N. I., “Double best response dynamics in topology formation game for Ad-hoc Networks”, Autom. Remote Control, 76 (2015), 323–335 | DOI | MR | Zbl

[28] Gromova E., Gromov D., Timonin N., Kirpichnikova A., Blakeway S., “A dynamic game of Mobile Agent placement in a MANET”, Systems Informatics, Modelling and Simulation (SIMS), 2016, 153–158 | DOI

[29] Plekhanova T., Gromova E., Gromov D., Kirpichnikova A., Blakeway S., “The strategic placement of Mobile Agents on a hexagonal graph using game theory”, Proc. of the IEEE conference ICAT, 2017 | DOI

[30] Albert R., Jeong H., Barabasi A. L., “Diameter of the World-Wide Web”, Nature, 401 (1999), 130–131 | DOI

[31] Petrosyan L., Zenkevich N., Shevkoplyas E., Game Theory, BHV-Petersburg Publ., Saint Petersburg, 2012, 480 pp. (in Russian)

[32] Petrosyan L., Kuzyutin D., Consistent solutions of positional games, Izd. Dom Saint Petersburg University Press, Saint Petersburg, 2008, 326 pp. (in Russian)

[33] Kuhn H. W., “Extensive games and the problem of information”, Contributions to the Theory of Games, 2:28 (1953), 193–216 | MR

[34] Sanjab A., Saad W., Basar T., “Prospect theory for enhanced cyber-physical security of drone delivery systems: A network interdiction game”, IEEE Intern. conference on Communications (ICC) (Paris, 2017), 1–6

[35] Cormen T. H., Leiserson C. E., Rivest R. L., Stein C., Introduction to algorithms, 2nd ed., Cambridge MIT Press, Cambridge, 2001, 1314 pp. | MR | Zbl

[36] Wehrle K., Guneş M., Gross J. (eds.), Modeling and Tools for Network Simulation, Springer Verlag Publ., Berlin, 2010, 547 pp. | Zbl

[37] Gromova E. V., Plekhanova T. M., “On the regularization of a cooperative solution in a multi-stage game with random time horizon”, Discrete Applied Mathematics, 255 (2018), 40–55 | DOI | MR