# American Institute of Mathematical Sciences

• Previous Article
Unified optimality conditions for set-valued optimizations
• JIMO Home
• This Issue
• Next Article
Optimization of a condition-based duration-varying preventive maintenance policy for the stockless production system based on queueing model
July  2019, 15(3): 1085-1100. doi: 10.3934/jimo.2018086

## Performance analysis of a cooperative flow game algorithm in ad hoc networks and a comparison to Dijkstra's algorithm

 1 Süleyman Demirel University, Faculty of Technology, Department of Software Engineering, Isparta, Turkey 2 Süleyman Demirel University, Arts and Sciences Faculty, Department of Mathematics, Isparta, Turkey 3 Poznan University of Technology, Faculty of Engineering Management, Poznan, Poland

* Corresponding author: Serap Ergün

Received  May 2016 Revised  March 2018 Published  July 2018

The aim of this study is to provide a mathematical framework for studying node cooperation, and to define strategies leading to optimal node behaviour in ad hoc networks. In this study we show time performances of three different methods, namely, Dijkstra's algorithm, Dijkstra's algorithm with battery times and cooperative flow game algorithm constructed from a flow network model. There are two main outcomes of this study regarding the shortest path problem which is that of finding a path of minimum length between two distinct vertices in a network. The first one finds out which method gives better results in terms of time while finding the shortest path, the second one considers the battery life of wireless devices on the network to determine the remaining nodes on the network. Further, optimization performances of the methods are examined in finding the shortest path problem. The study shows that the battery times play an important role in network routing and more devices provided to keep the network. To view the time performance analysis of the methods MATLAB is used. Also, considering the cooperation between the nodes, it is envisaged that using cooperative game theory brings a new approach to network traffic engineering and routing methods.

Citation: Serap Ergün, Sirma Zeynep Alparslan Gök, Tuncay Aydoǧan, Gerhard Wilhelm Weber. Performance analysis of a cooperative flow game algorithm in ad hoc networks and a comparison to Dijkstra's algorithm. Journal of Industrial & Management Optimization, 2019, 15 (3) : 1085-1100. doi: 10.3934/jimo.2018086
##### References:

show all references

##### References:
The network example
Time Performances of three algorithms
The pseudo code of Dijkstra's Algorithm
 1 function Dijkstra(Graph, source): 2 dist[source] := 0 // Distance from source to source 3 for each vertex v in Graph: // Initializations 4 if v $\mathit{\boldsymbol{\neq}}$ source 5 dist[v] := infinity // Unknown distance function from source to v 6 previous[v] := undefined // Previous node in optimal path from source 7 end if 8 add v to Q // All nodes initially in Q (unvisited nodes) 9 end for 10 11 while Q is not empty: // The main loop 12 u := vertex in Q with min dist[u] // Source node in first case 13 remove u from Q 14 15 for each neighbor v of u: // where v has not yet been removed from Q. 16 alt := dist[u] + length(u, v) 17 if alt $<$ dist[v]: // A shorter path to v has been found 18 dist[v] := alt 19 previous[v] := u 20 end if 21 end for 22 end while 23 return dist[], previous[] 24 end function
 1 function Dijkstra(Graph, source): 2 dist[source] := 0 // Distance from source to source 3 for each vertex v in Graph: // Initializations 4 if v $\mathit{\boldsymbol{\neq}}$ source 5 dist[v] := infinity // Unknown distance function from source to v 6 previous[v] := undefined // Previous node in optimal path from source 7 end if 8 add v to Q // All nodes initially in Q (unvisited nodes) 9 end for 10 11 while Q is not empty: // The main loop 12 u := vertex in Q with min dist[u] // Source node in first case 13 remove u from Q 14 15 for each neighbor v of u: // where v has not yet been removed from Q. 16 alt := dist[u] + length(u, v) 17 if alt $<$ dist[v]: // A shorter path to v has been found 18 dist[v] := alt 19 previous[v] := u 20 end if 21 end for 22 end while 23 return dist[], previous[] 24 end function
The pseudo code of Dijkstra's Algorithm with Battery Times
 1 function DijkstraBatteryTime(Graph, source): 2 dist[source] := 0 // Distance from source to source 3 for each vertex v in Graph: // Initializations 4 if v $\mathit{\boldsymbol{\neq }}$ source 5 dist[v] := infinity // Unknown distance function from source to v 6 previous[v] := undefined // Previous node in optimal path from source 7 end if 8 add v to Q // All nodes initially in Q (unvisited nodes) 9 end for 10 while Q is not empty: // The main loop 11 u := vertex in Q with min dist[u] // Source node in first case 12 remove u from Q 13 for each neighbor v of u: // where v has not yet been removed from Q. 14 alt := dist[u] + length(u, v) 15 battime:=dist[u]+length(u, v) 16 if alt $<$ dist[v]: // A shorter path to v has been found 17 if battime$<$dist[v:] // A shorter path to v has been found 18 dist[v]:=battime 19 previous [v]:=u 20 dist[v] := alt 21 previous[v] := u 22 end if 23 end if 24 end for 25 end while 26 return dist[], previous[] 27 end function
 1 function DijkstraBatteryTime(Graph, source): 2 dist[source] := 0 // Distance from source to source 3 for each vertex v in Graph: // Initializations 4 if v $\mathit{\boldsymbol{\neq }}$ source 5 dist[v] := infinity // Unknown distance function from source to v 6 previous[v] := undefined // Previous node in optimal path from source 7 end if 8 add v to Q // All nodes initially in Q (unvisited nodes) 9 end for 10 while Q is not empty: // The main loop 11 u := vertex in Q with min dist[u] // Source node in first case 12 remove u from Q 13 for each neighbor v of u: // where v has not yet been removed from Q. 14 alt := dist[u] + length(u, v) 15 battime:=dist[u]+length(u, v) 16 if alt $<$ dist[v]: // A shorter path to v has been found 17 if battime$<$dist[v:] // A shorter path to v has been found 18 dist[v]:=battime 19 previous [v]:=u 20 dist[v] := alt 21 previous[v] := u 22 end if 23 end if 24 end for 25 end while 26 return dist[], previous[] 27 end function
The pseudo code of cooperative flow game algorithm
 1 function CooperativeFlowGame(Graph, source): 2 dist[source] := 0 // Distance from source to source 3 for each vertex v in Graph: // Initializations 4 if v $\mathit{\boldsymbol{\neq }}$ source 5 dist[v] := infinity // Unknown distance function from source to v 6 previous[v] := undefined // Previous node in optimal path from source 7 end if 8 add v to Q // All nodes initially in Q (unvisited nodes) 9 end for 10 subset[vs]; // Calculate all the subset's (coalitions) values 11 while Q is not empty: // The main loop 12 u := vertex in Q with min dist[u] // Source node in first case 13 remove u from Q 14 for each coalition vs of u: // where vs has not yet been removed from Q. 15 alt := dist[u] + length(u, vs) 16 if alt $<$ dist[vs]: // A shorter path to vs has been found 17 dist[vs] := alt // Choose this coalition 18 previous[vs] := u 19 end if 20 end for 21 end while 22 return dist[], previous[] 23 end function
 1 function CooperativeFlowGame(Graph, source): 2 dist[source] := 0 // Distance from source to source 3 for each vertex v in Graph: // Initializations 4 if v $\mathit{\boldsymbol{\neq }}$ source 5 dist[v] := infinity // Unknown distance function from source to v 6 previous[v] := undefined // Previous node in optimal path from source 7 end if 8 add v to Q // All nodes initially in Q (unvisited nodes) 9 end for 10 subset[vs]; // Calculate all the subset's (coalitions) values 11 while Q is not empty: // The main loop 12 u := vertex in Q with min dist[u] // Source node in first case 13 remove u from Q 14 for each coalition vs of u: // where vs has not yet been removed from Q. 15 alt := dist[u] + length(u, vs) 16 if alt $<$ dist[vs]: // A shorter path to vs has been found 17 dist[vs] := alt // Choose this coalition 18 previous[vs] := u 19 end if 20 end for 21 end while 22 return dist[], previous[] 23 end function
The marginal vectors of the cooperative flow game
 $\sigma$ $m_{1}^{\sigma }$ $m_{2}^{\sigma }$ $m_{3}^{\sigma }$ $m_{4}^{\sigma }$ $\sigma _{1}=(1, 2, 3, 4)$ $0$ $0$ $0$ $12$ $\sigma _{2}=(1, 2, 4, 3)$ $0$ $0$ $12$ $0$ $\sigma _{3}=(1, 3, 2, 4)$ $0$ $0$ $0$ $12$ $\sigma _{4}=(1, 3, 4, 2)$ $0$ $7$ $0$ $5$ $\sigma _{5}=(1, 4, 2, 3)$ $0$ $0$ $12$ $0$ $\sigma _{6}=(1, 4, 3, 2)$ $0$ $7$ $5$ $0$ $\sigma _{7}=(2, 1, 3, 4)$ $0$ $0$ $0$ $12$ $\sigma _{8}=(2, 1, 4, 3)$ $0$ $0$ $12$ $0$ $\sigma _{9}=(2, 3, 1, 4)$ $0$ $0$ $0$ $12$ $\sigma _{10}=(2, 3, 4, 1)$ $5$ $0$ $0$ $7$ $\sigma _{11}=(2, 4, 1, 3)$ $0$ $0$ $12$ $0$ $\sigma _{12}=(2, 4, 3, 1)$ $5$ $0$ $7$ $0$ $\sigma _{13}=(3, 1, 2, 4)$ $0$ $0$ $0$ $12$ $\sigma _{14}=(3, 1, 4, 2)$ $0$ $7$ $0$ $5$ $\sigma _{15}=(3, 2, 1, 4)$ $0$ $0$ $0$ $12$ $\sigma _{16}=(3, 2, 4, 1)$ $5$ $0$ $0$ $7$ $\sigma _{17}=(3, 4, 1, 2)$ $-1$ $7$ $0$ $6$ $\sigma _{18}=(3, 4, 2, 1)$ $5$ $1$ $0$ $6$ $\sigma _{19}=(4, 1, 2, 3)$ $0$ $0$ $12$ $0$ $\sigma _{20}=(4, 1, 3, 2)$ $0$ $7$ $5$ $0$ $\sigma _{21}=(4, 2, 1, 3)$ $0$ $0$ $12$ $0$ $\sigma _{22}=(4, 2, 3, 1)$ $5$ $0$ $7$ $0$ $\sigma _{23}=(4, 3, 1, 2)$ $-1$ $7$ $6$ $0$ $\sigma _{24}=(4, 3, 2, 1)$ $5$ $1$ $6$ $0$
 $\sigma$ $m_{1}^{\sigma }$ $m_{2}^{\sigma }$ $m_{3}^{\sigma }$ $m_{4}^{\sigma }$ $\sigma _{1}=(1, 2, 3, 4)$ $0$ $0$ $0$ $12$ $\sigma _{2}=(1, 2, 4, 3)$ $0$ $0$ $12$ $0$ $\sigma _{3}=(1, 3, 2, 4)$ $0$ $0$ $0$ $12$ $\sigma _{4}=(1, 3, 4, 2)$ $0$ $7$ $0$ $5$ $\sigma _{5}=(1, 4, 2, 3)$ $0$ $0$ $12$ $0$ $\sigma _{6}=(1, 4, 3, 2)$ $0$ $7$ $5$ $0$ $\sigma _{7}=(2, 1, 3, 4)$ $0$ $0$ $0$ $12$ $\sigma _{8}=(2, 1, 4, 3)$ $0$ $0$ $12$ $0$ $\sigma _{9}=(2, 3, 1, 4)$ $0$ $0$ $0$ $12$ $\sigma _{10}=(2, 3, 4, 1)$ $5$ $0$ $0$ $7$ $\sigma _{11}=(2, 4, 1, 3)$ $0$ $0$ $12$ $0$ $\sigma _{12}=(2, 4, 3, 1)$ $5$ $0$ $7$ $0$ $\sigma _{13}=(3, 1, 2, 4)$ $0$ $0$ $0$ $12$ $\sigma _{14}=(3, 1, 4, 2)$ $0$ $7$ $0$ $5$ $\sigma _{15}=(3, 2, 1, 4)$ $0$ $0$ $0$ $12$ $\sigma _{16}=(3, 2, 4, 1)$ $5$ $0$ $0$ $7$ $\sigma _{17}=(3, 4, 1, 2)$ $-1$ $7$ $0$ $6$ $\sigma _{18}=(3, 4, 2, 1)$ $5$ $1$ $0$ $6$ $\sigma _{19}=(4, 1, 2, 3)$ $0$ $0$ $12$ $0$ $\sigma _{20}=(4, 1, 3, 2)$ $0$ $7$ $5$ $0$ $\sigma _{21}=(4, 2, 1, 3)$ $0$ $0$ $12$ $0$ $\sigma _{22}=(4, 2, 3, 1)$ $5$ $0$ $7$ $0$ $\sigma _{23}=(4, 3, 1, 2)$ $-1$ $7$ $6$ $0$ $\sigma _{24}=(4, 3, 2, 1)$ $5$ $1$ $6$ $0$
The comparision of three methods
 Time performances * $CFGA\ DWBT>DA$
 Time performances * $CFGA\ DWBT>DA$
 [1] J. Frédéric Bonnans, Justina Gianatti, Francisco J. Silva. On the convergence of the Sakawa-Shindo algorithm in stochastic control. Mathematical Control & Related Fields, 2016, 6 (3) : 391-406. doi: 10.3934/mcrf.2016008 [2] Demetres D. Kouvatsos, Jumma S. Alanazi, Kevin Smith. A unified ME algorithm for arbitrary open QNMs with mixed blocking mechanisms. Numerical Algebra, Control & Optimization, 2011, 1 (4) : 781-816. doi: 10.3934/naco.2011.1.781 [3] Z. Reichstein and B. Youssin. Parusinski's "Key Lemma" via algebraic geometry. Electronic Research Announcements, 1999, 5: 136-145. [4] Ronald E. Mickens. Positivity preserving discrete model for the coupled ODE's modeling glycolysis. Conference Publications, 2003, 2003 (Special) : 623-629. doi: 10.3934/proc.2003.2003.623 [5] Bernold Fiedler, Carlos Rocha, Matthias Wolfrum. Sturm global attractors for $S^1$-equivariant parabolic equations. Networks & Heterogeneous Media, 2012, 7 (4) : 617-659. doi: 10.3934/nhm.2012.7.617 [6] Hakan Özadam, Ferruh Özbudak. A note on negacyclic and cyclic codes of length $p^s$ over a finite field of characteristic $p$. Advances in Mathematics of Communications, 2009, 3 (3) : 265-271. doi: 10.3934/amc.2009.3.265 [7] Marion Darbas, Jérémy Heleine, Stephanie Lohrengel. Numerical resolution by the quasi-reversibility method of a data completion problem for Maxwell's equations. Inverse Problems & Imaging, 2020, 14 (6) : 1107-1133. doi: 10.3934/ipi.2020056 [8] Karl-Peter Hadeler, Frithjof Lutscher. Quiescent phases with distributed exit times. Discrete & Continuous Dynamical Systems - B, 2012, 17 (3) : 849-869. doi: 10.3934/dcdsb.2012.17.849 [9] David Cantala, Juan Sebastián Pereyra. Endogenous budget constraints in the assignment game. Journal of Dynamics & Games, 2015, 2 (3&4) : 207-225. doi: 10.3934/jdg.2015002 [10] Juan Manuel Pastor, Javier García-Algarra, José M. Iriondo, José J. Ramasco, Javier Galeano. Dragging in mutualistic networks. Networks & Heterogeneous Media, 2015, 10 (1) : 37-52. doi: 10.3934/nhm.2015.10.37 [11] Alessandro Gondolo, Fernando Guevara Vasquez. Characterization and synthesis of Rayleigh damped elastodynamic networks. Networks & Heterogeneous Media, 2014, 9 (2) : 299-314. doi: 10.3934/nhm.2014.9.299 [12] Juan Manuel Pastor, Javier García-Algarra, Javier Galeano, José María Iriondo, José J. Ramasco. A simple and bounded model of population dynamics for mutualistic networks. Networks & Heterogeneous Media, 2015, 10 (1) : 53-70. doi: 10.3934/nhm.2015.10.53 [13] Christina Surulescu, Nicolae Surulescu. Modeling and simulation of some cell dispersion problems by a nonparametric method. Mathematical Biosciences & Engineering, 2011, 8 (2) : 263-277. doi: 10.3934/mbe.2011.8.263 [14] Shu-Yu Hsu. Existence and properties of ancient solutions of the Yamabe flow. Discrete & Continuous Dynamical Systems - A, 2018, 38 (1) : 91-129. doi: 10.3934/dcds.2018005 [15] Matthias Erbar, Jan Maas. Gradient flow structures for discrete porous medium equations. Discrete & Continuous Dynamical Systems - A, 2014, 34 (4) : 1355-1374. doi: 10.3934/dcds.2014.34.1355 [16] Ardeshir Ahmadi, Hamed Davari-Ardakani. A multistage stochastic programming framework for cardinality constrained portfolio optimization. Numerical Algebra, Control & Optimization, 2017, 7 (3) : 359-377. doi: 10.3934/naco.2017023 [17] Luke Finlay, Vladimir Gaitsgory, Ivan Lebedev. Linear programming solutions of periodic optimization problems: approximation of the optimal control. Journal of Industrial & Management Optimization, 2007, 3 (2) : 399-413. doi: 10.3934/jimo.2007.3.399 [18] Feng Luo. A combinatorial curvature flow for compact 3-manifolds with boundary. Electronic Research Announcements, 2005, 11: 12-20. [19] Yila Bai, Haiqing Zhao, Xu Zhang, Enmin Feng, Zhijun Li. The model of heat transfer of the arctic snow-ice layer in summer and numerical simulation. Journal of Industrial & Management Optimization, 2005, 1 (3) : 405-414. doi: 10.3934/jimo.2005.1.405 [20] Hong Seng Sim, Wah June Leong, Chuei Yee Chen, Siti Nur Iqmal Ibrahim. Multi-step spectral gradient methods with modified weak secant relation for large scale unconstrained optimization. Numerical Algebra, Control & Optimization, 2018, 8 (3) : 377-387. doi: 10.3934/naco.2018024

2019 Impact Factor: 1.366