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, doi: 10.3934/jimo.2018086
References:
[1]

R. Ahuja, T. Magnanti and J. Orlin, Network Flows: Theory, Algorithms, and Applications, PrenticeHall, Upper Saddle River, NJ, 1993. doi: 10.21236/ADA594171.

[2]

R. K. AhujaK. MehlhornJ. Orlin and R. E. Tarjan, Faster algorithms for the shortest path problem, Journal of the ACM (JACM), 37 (1990), 213-223. doi: 10.1145/77600.77615.

[3]

Y. Bachrach and E. Porat, Path disruption games, In Proceedings of the 9th International Conference on Autonomous Agents and Multiagent Systems, volume 1-Volume 1 (pp. 1123-1130). International Foundation for Autonomous Agents and Multiagent Systems, (2010, May).

[4]

Z. BarzilyZ. VolkovichB. Akteke-Öztürk and G. W. Weber, On a minimal spanning tree approach in the cluster validation problem, Informatica, 20 (2009), 187-202.

[5]

R. Bellman, On a Routing Problem (No. RAND-P-1000), Rand Corp Santa Monica Ca, 1956.

[6]

P. BormH. Hamers and R. Hendrickx, Operations research games: A survey, TOP, 9 (2001), 139-199. doi: 10.1007/BF02579075.

[7]

R. Branzei, D. Dimitrov and S. Tijs, Models in Cooperative Game Theory: Crisp, Fuzzy And Multi-Choice Games, In: Lecture notes in economics and mathematical systems, Springer, Berlin, vol 556, 2005.

[8]

T. S. Chandrashekar and Y. Narahari, Economic mechanisms for shortest path cooperative games with incomplete information, In Internet and Network Economics, Springer Berlin Heidelberg, (2005), 70-79.

[9]

J. H. Chang and L. Tassiulas, Energy conserving routing in wireless ad-hoc networks, In INFOCOM 2000, Nineteenth Annual Joint Conference of the IEEE Computer and Communications Societies, Proceedings, IEEE, 1 (2000), 22-31.

[10]

B. ChenK. JamiesonH. Balakrishnan and R. Morris, Span: An energy-efficient coordination algorithm for topology maintenance in ad hoc wireless networks, MobiCom '01 Proceedings of the 7th Annual International Conference on Mobile Computing and Networking, (2001), 85-96. doi: 10.1145/381677.381686.

[11]

S. M. ChoiX. Huang and W. K. Ching, Minimizing equilibrium expected sojourn time via performance-based mixed threshold demand allocation in a multiple-server queueing environment, Journal of Industrial and Management Optimization, 8 (2012), 299-323. doi: 10.3934/jimo.2012.8.299.

[12]

R. B. Dial, Algorithm 360: Shortest-path forest with topological ordering [H], Communications of the ACM, 12 (1969), 632-633. doi: 10.1145/363269.363610.

[13]

E. W. Dijkstra, A note on two problems in connection with graph, Numer. Math., 1 (1959), 269-271. doi: 10.1007/BF01386390.

[14]

T. S. Driessen, A survey of consistency properties in cooperative game theory, SIAM review, 33 (1991), 43-59. doi: 10.1137/1033003.

[15]

J. FeigenbaumC. PapadimitriouR. Sami and S. Shenker, A BGP-based mechanism for lowest-cost routing, PODC '02 Proceedings of the Twenty-First Annual Symposium on Principles of Distributed Computing, (2002), 173-182. doi: 10.1145/571825.571856.

[16]

L. R. Ford and D. R. Fulkerson, Flows in Networks, Princeton University Press, Princeton, N. J., 1962.

[17]

V. FragnelliI. García-Jurado and L. Méndez-Naya, On shortest path games, Mathematical Methods of Operations Research, 52 (2000), 251-264. doi: 10.1007/s001860000061.

[18]

M. L. Fredman and R. E. Tarjan, Fibonacci heaps and their uses in improved network optimization algorithms, Journal of the ACM (JACM), 34 (1987), 596-615. doi: 10.1145/28869.28874.

[19]

H. N. Gabow and R. E. Tarjan, Faster scaling algorithms for network problems, SIAM Journal on Computing, 18 (1989), 1013-1036. doi: 10.1137/0218069.

[20]

G. Gallo and S. Pallottino, Shortest path algorithms, Annals of Operations Research, 13 (1988), 1-79. doi: 10.1007/BF02288320.

[21]

J. Gebert, M. Lätsch, E. M. P. Quek and G. W. Weber, Analyzing and optimizing genetic network structure via path-finding Journal of Computational Technologies, 9 (2004).

[22]

A. V. Goldberg, Scaling algorithms for the shortest paths problem, SIAM Journal on Computing, 24 (1995), 494-504. doi: 10.1137/S0097539792231179.

[23]

J. Hershberger, J., S. Suri and V. Prices, Shortest Paths: What is an edge worth?, 42nd IEEE Symposium on Foundations of Computer Science (Las Vegas, NV, 2001), IEEE Computer Soc., Los Alamitos, CA, (2001), 252-259.

[24]

E. Kalai and E. Zemel, Generalized network problems yielding totally balanced games, Operations Research, 30 (1982), 998-1008. doi: 10.1287/opre.30.5.998.

[25]

E. Kalai and E. Zemel, Totally balanced games and games of flow, Mathematics of Operations Research, 7 (1982), 476-478. doi: 10.1287/moor.7.3.476.

[26]

J. Leino, Applications of Game Theory in Ad Hoc Networks, Master's Thesis, Department of Engineering Physics and Mathematics, Helsinki University of Technology, (2003).

[27]

W. Liang, Constructing minimum-energy broadcast trees in wireless ad hoc networks, Proceedings of the 3rd ACM international symposium on Mobile ad hoc networking & computing, (2002), 112-122. doi: 10.1145/513800.513815.

[28]

A. B. MacKenzie and L. A. DaSilva, Game theory for wireless engineers, Synthesis Lectures on Communications, 1 (2006), 1-86. doi: 10.2200/S00014ED1V01Y200508COM001.

[29]

N. Megiddo, Computational complexity of the game theory approach to cost allocation for a tree, Mathematics of Operations Research, 3 (1978), 189-196. doi: 10.1287/moor.3.3.189.

[30]

S. Mehta and K. S. Kwak, Application of Game Theory to Wireless Networks, Convergence and Hybrid Information Technologies: InTech, 2010. doi: 10.5772/9642.

[31]

S. MorettiS. Z. A. GökR. Branzei and S. Tijs, Connection situations under uncertainty and cost monotonic solutions, Computers & Operations Research, 38 (2011), 1638-1645. doi: 10.1016/j.cor.2011.02.004.

[32]

F. Nebel, Shortest Path Games: Computational Complexity of Solution Concepts, PhD Thesis, Universiteit van Amsterdam, 2010.

[33]

N. Nisan and A. Ronen, Algorithmic mechanism design, Annual ACM Symposium on Theory of Computing (Atlanta, GA, 1999), ACM, New York, (1999), 129-140. doi: 10.1145/301250.301287.

[34]

R. C. Prim, Shortest connection networks and some generalizations, Bell System Technical Journal, 36 (1957), 1389-1401.

[35]

H. ReijnierseM. MaschlerJ. Potters and S. Tijs, Simple flow games, Games and Economic Behavior, 16 (1996), 238-260. doi: 10.1006/game.1996.0085.

[36]

F. Schulz, D. Wagner and K. Weihe, Dijkstra's algorithm on-line: An empirical case study from public railroad transport, Journal of Experimental Algorithmics (JEA), 5 (2000), Special Issue 2, 23 pp. doi: 10.1145/351827.384254.

[37]

F. ShaD. Han and W. Zhong, Bounds on price of anarchy on linear cost functions, Journal of Industrial & Management Optimization, 11 (2015), 1165-1173. doi: 10.3934/jimo.2015.11.1165.

[38]

R. C. Shah and J. M. Rabaey, Energy aware routing for low energy ad hoc sensor networks, Wireless Communications and Networking Conference, 2002. WCNC2002. IEEE, 1 (2002), 350-355.

[39]

L. S. Shapley, A value for n-person games, Annals of Mathematics Studies, 28 (1953), 307-317.

[40]

J. C. Smith and C. Lim, Algorithms for network interdiction and fortification games, Pareto Optimality, Game Theory and Equilibria, 17 (2008), 609-644. doi: 10.1007/978-0-387-77247-9_24.

[41]

V. SrivastavaJ. NeelA. B. MacKenzieR. MenonL. A. DaSilvaE. H. HickJ. H. Reed and R. P. Gilles, Using game theory to analyze wireless ad hoc networks, IEEE Communications Surveys and Tutorials, 7 (2005), 46-56.

[42]

S. Tijs, Introduction to Game Theory, SIAM Hindustan Book Agency, India, 2003.

[43]

C. K. Toh, Maximum battery life routing to support ubiquitous mobile computing in wireless ad hoc networks, Communications Magazine, IEEE, 39 (2001), 138-147.

[44]

University of Waterloo, Combinatorics & Optimization. Discrete Optimization research group, https://math.uwaterloo.ca/combinatorics-and-optimization/research/areas/discrete-optimization.

[45]

M. Voorneveld and S. Grahn, Cost allocation in shortest path games, Mathematical methods of operations research, 56 (2002), 323-340. doi: 10.1007/s001860200222.

[46]

M. H. XuY. Q. LiuQ. L. HuangY. X. Zhang and G. F. Luan, An improved Dijkstra's shortest path algorithm for sparse network, Applied Mathematics and Computation, 185 (2007), 247-254. doi: 10.1016/j.amc.2006.06.094.

[47]

Y. ZhaoS. Jin and W. Yue, Adjustable admission control with threshold in centralized CR networks: Analysis and optimization, Journal of Industrial & Management Optimization, 11 (2015), 1393-1408. doi: 10.3934/jimo.2015.11.1393.

[48]

L. Zhou, A new bargaining set of an n-person game and endogenous coalition formation, Games and Economic Behavior, 6 (1994), 512-526. doi: 10.1006/game.1994.1030.

show all references

References:
[1]

R. Ahuja, T. Magnanti and J. Orlin, Network Flows: Theory, Algorithms, and Applications, PrenticeHall, Upper Saddle River, NJ, 1993. doi: 10.21236/ADA594171.

[2]

R. K. AhujaK. MehlhornJ. Orlin and R. E. Tarjan, Faster algorithms for the shortest path problem, Journal of the ACM (JACM), 37 (1990), 213-223. doi: 10.1145/77600.77615.

[3]

Y. Bachrach and E. Porat, Path disruption games, In Proceedings of the 9th International Conference on Autonomous Agents and Multiagent Systems, volume 1-Volume 1 (pp. 1123-1130). International Foundation for Autonomous Agents and Multiagent Systems, (2010, May).

[4]

Z. BarzilyZ. VolkovichB. Akteke-Öztürk and G. W. Weber, On a minimal spanning tree approach in the cluster validation problem, Informatica, 20 (2009), 187-202.

[5]

R. Bellman, On a Routing Problem (No. RAND-P-1000), Rand Corp Santa Monica Ca, 1956.

[6]

P. BormH. Hamers and R. Hendrickx, Operations research games: A survey, TOP, 9 (2001), 139-199. doi: 10.1007/BF02579075.

[7]

R. Branzei, D. Dimitrov and S. Tijs, Models in Cooperative Game Theory: Crisp, Fuzzy And Multi-Choice Games, In: Lecture notes in economics and mathematical systems, Springer, Berlin, vol 556, 2005.

[8]

T. S. Chandrashekar and Y. Narahari, Economic mechanisms for shortest path cooperative games with incomplete information, In Internet and Network Economics, Springer Berlin Heidelberg, (2005), 70-79.

[9]

J. H. Chang and L. Tassiulas, Energy conserving routing in wireless ad-hoc networks, In INFOCOM 2000, Nineteenth Annual Joint Conference of the IEEE Computer and Communications Societies, Proceedings, IEEE, 1 (2000), 22-31.

[10]

B. ChenK. JamiesonH. Balakrishnan and R. Morris, Span: An energy-efficient coordination algorithm for topology maintenance in ad hoc wireless networks, MobiCom '01 Proceedings of the 7th Annual International Conference on Mobile Computing and Networking, (2001), 85-96. doi: 10.1145/381677.381686.

[11]

S. M. ChoiX. Huang and W. K. Ching, Minimizing equilibrium expected sojourn time via performance-based mixed threshold demand allocation in a multiple-server queueing environment, Journal of Industrial and Management Optimization, 8 (2012), 299-323. doi: 10.3934/jimo.2012.8.299.

[12]

R. B. Dial, Algorithm 360: Shortest-path forest with topological ordering [H], Communications of the ACM, 12 (1969), 632-633. doi: 10.1145/363269.363610.

[13]

E. W. Dijkstra, A note on two problems in connection with graph, Numer. Math., 1 (1959), 269-271. doi: 10.1007/BF01386390.

[14]

T. S. Driessen, A survey of consistency properties in cooperative game theory, SIAM review, 33 (1991), 43-59. doi: 10.1137/1033003.

[15]

J. FeigenbaumC. PapadimitriouR. Sami and S. Shenker, A BGP-based mechanism for lowest-cost routing, PODC '02 Proceedings of the Twenty-First Annual Symposium on Principles of Distributed Computing, (2002), 173-182. doi: 10.1145/571825.571856.

[16]

L. R. Ford and D. R. Fulkerson, Flows in Networks, Princeton University Press, Princeton, N. J., 1962.

[17]

V. FragnelliI. García-Jurado and L. Méndez-Naya, On shortest path games, Mathematical Methods of Operations Research, 52 (2000), 251-264. doi: 10.1007/s001860000061.

[18]

M. L. Fredman and R. E. Tarjan, Fibonacci heaps and their uses in improved network optimization algorithms, Journal of the ACM (JACM), 34 (1987), 596-615. doi: 10.1145/28869.28874.

[19]

H. N. Gabow and R. E. Tarjan, Faster scaling algorithms for network problems, SIAM Journal on Computing, 18 (1989), 1013-1036. doi: 10.1137/0218069.

[20]

G. Gallo and S. Pallottino, Shortest path algorithms, Annals of Operations Research, 13 (1988), 1-79. doi: 10.1007/BF02288320.

[21]

J. Gebert, M. Lätsch, E. M. P. Quek and G. W. Weber, Analyzing and optimizing genetic network structure via path-finding Journal of Computational Technologies, 9 (2004).

[22]

A. V. Goldberg, Scaling algorithms for the shortest paths problem, SIAM Journal on Computing, 24 (1995), 494-504. doi: 10.1137/S0097539792231179.

[23]

J. Hershberger, J., S. Suri and V. Prices, Shortest Paths: What is an edge worth?, 42nd IEEE Symposium on Foundations of Computer Science (Las Vegas, NV, 2001), IEEE Computer Soc., Los Alamitos, CA, (2001), 252-259.

[24]

E. Kalai and E. Zemel, Generalized network problems yielding totally balanced games, Operations Research, 30 (1982), 998-1008. doi: 10.1287/opre.30.5.998.

[25]

E. Kalai and E. Zemel, Totally balanced games and games of flow, Mathematics of Operations Research, 7 (1982), 476-478. doi: 10.1287/moor.7.3.476.

[26]

J. Leino, Applications of Game Theory in Ad Hoc Networks, Master's Thesis, Department of Engineering Physics and Mathematics, Helsinki University of Technology, (2003).

[27]

W. Liang, Constructing minimum-energy broadcast trees in wireless ad hoc networks, Proceedings of the 3rd ACM international symposium on Mobile ad hoc networking & computing, (2002), 112-122. doi: 10.1145/513800.513815.

[28]

A. B. MacKenzie and L. A. DaSilva, Game theory for wireless engineers, Synthesis Lectures on Communications, 1 (2006), 1-86. doi: 10.2200/S00014ED1V01Y200508COM001.

[29]

N. Megiddo, Computational complexity of the game theory approach to cost allocation for a tree, Mathematics of Operations Research, 3 (1978), 189-196. doi: 10.1287/moor.3.3.189.

[30]

S. Mehta and K. S. Kwak, Application of Game Theory to Wireless Networks, Convergence and Hybrid Information Technologies: InTech, 2010. doi: 10.5772/9642.

[31]

S. MorettiS. Z. A. GökR. Branzei and S. Tijs, Connection situations under uncertainty and cost monotonic solutions, Computers & Operations Research, 38 (2011), 1638-1645. doi: 10.1016/j.cor.2011.02.004.

[32]

F. Nebel, Shortest Path Games: Computational Complexity of Solution Concepts, PhD Thesis, Universiteit van Amsterdam, 2010.

[33]

N. Nisan and A. Ronen, Algorithmic mechanism design, Annual ACM Symposium on Theory of Computing (Atlanta, GA, 1999), ACM, New York, (1999), 129-140. doi: 10.1145/301250.301287.

[34]

R. C. Prim, Shortest connection networks and some generalizations, Bell System Technical Journal, 36 (1957), 1389-1401.

[35]

H. ReijnierseM. MaschlerJ. Potters and S. Tijs, Simple flow games, Games and Economic Behavior, 16 (1996), 238-260. doi: 10.1006/game.1996.0085.

[36]

F. Schulz, D. Wagner and K. Weihe, Dijkstra's algorithm on-line: An empirical case study from public railroad transport, Journal of Experimental Algorithmics (JEA), 5 (2000), Special Issue 2, 23 pp. doi: 10.1145/351827.384254.

[37]

F. ShaD. Han and W. Zhong, Bounds on price of anarchy on linear cost functions, Journal of Industrial & Management Optimization, 11 (2015), 1165-1173. doi: 10.3934/jimo.2015.11.1165.

[38]

R. C. Shah and J. M. Rabaey, Energy aware routing for low energy ad hoc sensor networks, Wireless Communications and Networking Conference, 2002. WCNC2002. IEEE, 1 (2002), 350-355.

[39]

L. S. Shapley, A value for n-person games, Annals of Mathematics Studies, 28 (1953), 307-317.

[40]

J. C. Smith and C. Lim, Algorithms for network interdiction and fortification games, Pareto Optimality, Game Theory and Equilibria, 17 (2008), 609-644. doi: 10.1007/978-0-387-77247-9_24.

[41]

V. SrivastavaJ. NeelA. B. MacKenzieR. MenonL. A. DaSilvaE. H. HickJ. H. Reed and R. P. Gilles, Using game theory to analyze wireless ad hoc networks, IEEE Communications Surveys and Tutorials, 7 (2005), 46-56.

[42]

S. Tijs, Introduction to Game Theory, SIAM Hindustan Book Agency, India, 2003.

[43]

C. K. Toh, Maximum battery life routing to support ubiquitous mobile computing in wireless ad hoc networks, Communications Magazine, IEEE, 39 (2001), 138-147.

[44]

University of Waterloo, Combinatorics & Optimization. Discrete Optimization research group, https://math.uwaterloo.ca/combinatorics-and-optimization/research/areas/discrete-optimization.

[45]

M. Voorneveld and S. Grahn, Cost allocation in shortest path games, Mathematical methods of operations research, 56 (2002), 323-340. doi: 10.1007/s001860200222.

[46]

M. H. XuY. Q. LiuQ. L. HuangY. X. Zhang and G. F. Luan, An improved Dijkstra's shortest path algorithm for sparse network, Applied Mathematics and Computation, 185 (2007), 247-254. doi: 10.1016/j.amc.2006.06.094.

[47]

Y. ZhaoS. Jin and W. Yue, Adjustable admission control with threshold in centralized CR networks: Analysis and optimization, Journal of Industrial & Management Optimization, 11 (2015), 1393-1408. doi: 10.3934/jimo.2015.11.1393.

[48]

L. Zhou, A new bargaining set of an n-person game and endogenous coalition formation, Games and Economic Behavior, 6 (1994), 512-526. doi: 10.1006/game.1994.1030.

Figure 1.  An ad hoc network
Figure 2.  The network example
Figure 3.  Time Performances of three algorithms
Figure 4.  The lifetime of the nodes
Table 1.  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
Table 2.  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
Table 3.  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
Table 4.  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$
Table 5.  The comparision of three methods
Time performances * $CFGA\ <DA\ <DWBT$
Lifetime of nodes ** $CFGA\ >DWBT>DA$
Time performances * $CFGA\ <DA\ <DWBT$
Lifetime of nodes ** $CFGA\ >DWBT>DA$
[1]

Chia-Huang Wu, Kuo-Hsiung Wang, Jau-Chuan Ke, Jyh-Bin Ke. A heuristic algorithm for the optimization of M/M/$s$ queue with multiple working vacations. Journal of Industrial & Management Optimization, 2012, 8 (1) : 1-17. doi: 10.3934/jimo.2012.8.1

[2]

Gabriella Bretti, Maya Briani, Emiliano Cristiani. An easy-to-use algorithm for simulating traffic flow on networks: Numerical experiments. Discrete & Continuous Dynamical Systems - S, 2014, 7 (3) : 379-394. doi: 10.3934/dcdss.2014.7.379

[3]

Maya Briani, Emiliano Cristiani. An easy-to-use algorithm for simulating traffic flow on networks: Theoretical study. Networks & Heterogeneous Media, 2014, 9 (3) : 519-552. doi: 10.3934/nhm.2014.9.519

[4]

Jean-Paul Arnaout, Georges Arnaout, John El Khoury. Simulation and optimization of ant colony optimization algorithm for the stochastic uncapacitated location-allocation problem. Journal of Industrial & Management Optimization, 2016, 12 (4) : 1215-1225. doi: 10.3934/jimo.2016.12.1215

[5]

Xiangyu Gao, Yong Sun. A new heuristic algorithm for laser antimissile strategy optimization. Journal of Industrial & Management Optimization, 2012, 8 (2) : 457-468. doi: 10.3934/jimo.2012.8.457

[6]

Adil Bagirov, Sona Taheri, Soodabeh Asadi. A difference of convex optimization algorithm for piecewise linear regression. Journal of Industrial & Management Optimization, 2018, 13 (5) : 1-24. doi: 10.3934/jimo.2018077

[7]

Jianjun Liu, Min Zeng, Yifan Ge, Changzhi Wu, Xiangyu Wang. Improved Cuckoo Search algorithm for numerical function optimization. Journal of Industrial & Management Optimization, 2017, 13 (5) : 1-13. doi: 10.3934/jimo.2018142

[8]

Yong Wang, Wanquan Liu, Guanglu Zhou. An efficient algorithm for non-convex sparse optimization. Journal of Industrial & Management Optimization, 2017, 13 (5) : 1-13. doi: 10.3934/jimo.2018134

[9]

Pierre Frankel. Alternating proximal algorithm with costs-to-move, dual description and application to PDE's. Discrete & Continuous Dynamical Systems - S, 2012, 5 (3) : 545-557. doi: 10.3934/dcdss.2012.5.545

[10]

Leong-Kwan Li, Sally Shao. Convergence analysis of the weighted state space search algorithm for recurrent neural networks. Numerical Algebra, Control & Optimization, 2014, 4 (3) : 193-207. doi: 10.3934/naco.2014.4.193

[11]

Nguyen Van Thoai. Decomposition branch and bound algorithm for optimization problems over efficient sets. Journal of Industrial & Management Optimization, 2008, 4 (4) : 647-660. doi: 10.3934/jimo.2008.4.647

[12]

Tran Ngoc Thang, Nguyen Thi Bach Kim. Outcome space algorithm for generalized multiplicative problems and optimization over the efficient set. Journal of Industrial & Management Optimization, 2016, 12 (4) : 1417-1433. doi: 10.3934/jimo.2016.12.1417

[13]

Lianshuan Shi, Enmin Feng, Huanchun Sun, Zhaosheng Feng. A two-step algorithm for layout optimization of structures with discrete variables. Journal of Industrial & Management Optimization, 2007, 3 (3) : 543-552. doi: 10.3934/jimo.2007.3.543

[14]

M. Delgado Pineda, E. A. Galperin, P. Jiménez Guerra. MAPLE code of the cubic algorithm for multiobjective optimization with box constraints. Numerical Algebra, Control & Optimization, 2013, 3 (3) : 407-424. doi: 10.3934/naco.2013.3.407

[15]

Lipu Zhang, Yinghong Xu, Zhengjing Jin. An efficient algorithm for convex quadratic semi-definite optimization. Numerical Algebra, Control & Optimization, 2012, 2 (1) : 129-144. doi: 10.3934/naco.2012.2.129

[16]

Behrouz Kheirfam, Morteza Moslemi. On the extension of an arc-search interior-point algorithm for semidefinite optimization. Numerical Algebra, Control & Optimization, 2018, 8 (2) : 261-275. doi: 10.3934/naco.2018015

[17]

Paul B. Hermanns, Nguyen Van Thoai. Global optimization algorithm for solving bilevel programming problems with quadratic lower levels. Journal of Industrial & Management Optimization, 2010, 6 (1) : 177-196. doi: 10.3934/jimo.2010.6.177

[18]

Chunlin Hao, Xinwei Liu. Global convergence of an SQP algorithm for nonlinear optimization with overdetermined constraints. Numerical Algebra, Control & Optimization, 2012, 2 (1) : 19-29. doi: 10.3934/naco.2012.2.19

[19]

Xin Zhang, Jie Wen, Qin Ni. Subspace trust-region algorithm with conic model for unconstrained optimization. Numerical Algebra, Control & Optimization, 2013, 3 (2) : 223-234. doi: 10.3934/naco.2013.3.223

[20]

Soheil Dolatabadi. Weighted vertices optimizer (WVO): A novel metaheuristic optimization algorithm. Numerical Algebra, Control & Optimization, 2018, 8 (4) : 461-479. doi: 10.3934/naco.2018029

2017 Impact Factor: 0.994

Metrics

  • PDF downloads (16)
  • HTML views (317)
  • Cited by (0)

[Back to Top]