SCIENCE CHINA Information Sciences, Volume 60, Issue 11: 110205(2017) https://doi.org/10.1007/s11432-017-9165-7

## Cooperation and distributed optimization for the unreliable wireless game with indirect reciprocity

Xiang LI2,3,*,
• AcceptedJul 10, 2017
• PublishedSep 22, 2017
Share
Rating

### Abstract

Cooperation in packet forwarding among users and operators of a distributed wireless network has been widely studied.However, because of the limited computational resources, users in wireless communication do not prefer to cooperate with others unless cooperation may improve their own performance.Therefore, the key problem in cooperation enforcement must be solved first to enable a wireless network to be efficient.Yet, most of the existing game-theoretic cooperation stimulation approaches assume that the interactions between any pair of players (users) are long-lasting.In this paper, we apply game theory to optimize the communication efficiency of a distributed wireless network with finite number of interactions between any pair of players.Based on the mechanism of indirect reciprocity, we theoretically analyze the optimal action rule with the method of dynamic programming,and derive the approximate threshold of benefit-to-cost ratio to achieve the optimal action rule.Furthermore, we adopt the replicator dynamics to assess the evolutionary stability of the optimal action rule against the perturbation effect.Numerical illustrations verify the performance of the proposed method on wireless cooperation.

### Acknowledgment

This work was supported by National Science Fund for Distinguished Young Scholar of China (Grant No. 61425019), Key Projects of National Natural Science Foundation of China (Grant No. 71731004), National Natural Science Foundation of China (Grant Nos. 61403059, 61503342, 11572288, 61672468), and Zhejiang Provincial Natural Science Foundation of China (Grant Nos. LY15F020013, LY16F030002).

### References

[1] Song L, Niyato D, Han Z, et al. Wireless Device-to-Device Communications and Networks. Cambridge: Cambridge University Press, 2015. 1--32. Google Scholar

[2] Liu K J R, Sadek A K, Su W F, et al. Cooperative Communications and Networking. Cambridge: Cambridge University Press, 2009. 1--45. Google Scholar

[3] Xu Q, Zheng R, Saad W. Device Fingerprinting in Wireless Networks: Challenges and Opportunities. IEEE Commun Surv Tutorials, 2016, 18: 94-104 CrossRef Google Scholar

[4] Ku M L, Li W, Chen Y. On Energy Harvesting Gain and Diversity Analysis in Cooperative Communications. IEEE J Select Areas Commun, 2015, 33: 2641-2657 CrossRef Google Scholar

[5] Jaramillo J J, Srikant R. DARWIN: distributed and adaptive reputation mechanism for wireless ad-hoc networks. In: Proceedings of 13th Annual ACM International Conference on Mobile Computing and Networking, Montreal, 2007. 87--97. Google Scholar

[6] Buttyán L, Hubaux J P. Stimulating cooperation in self-organizing ad hoc networks. Mobile Networks Appl, 2003, 8: 579-592 CrossRef Google Scholar

[7] Crowcroft J, Gibbens R, Kelly F. Modelling incentives for collaboration in mobile ad hoc networks. Performance Evaluation, 2004, 57: 427-439 CrossRef Google Scholar

[8] Zhong S, Chen J, Yang Y R. Sprite: a simple, cheat-proof, credit-based system for mobile ad-hoc networks. In: Proceedings of the 22nd Annual Joint Conference of the IEEE Computer and Communications, San Francisco, 2003. 1987--1997. Google Scholar

[9] Janzadeh H, Fayazbakhsh K, Dehghan M. A secure credit-based cooperation stimulating mechanism for MANETs using hash chains. Future Generation Comp Syst, 2009, 25: 926-934 CrossRef Google Scholar

[10] Wang L, Liao X K, Xue J L, et al. Enhancement of cooperation between file systems and applications-VFS extensions for optimized performance. Sci China Inf Sci, 2015, 58: 092104. Google Scholar

[11] Michiardi P, Molva R. CORE: a collaborative reputation mechanism to enforce node cooperation in mobile ad hoc networks. In: Advanced Communications and Multimedia Security. Boston: Springer, 2002. 107--121. Google Scholar

[12] He Q, Wu D, Khosla P. SORI: a secure and objective reputation-based incentive scheme for ad-hoc networks. In: Proceedings of IEEE Wireless Communications and Networking Conference, Atlanta, 2004. 825--830. Google Scholar

[13] Balakrishnan K, Deng J, Varshney V K. TWOACK: preventing selfishness in mobile ad hoc netwotks. In: Proceedings of IEEE Wireless Communications and Networking Conference, New orleans, 2005. 2137--2142. Google Scholar

[14] Refaei M T, DaSilva L A, Eltoweissy M. Adaptation of reputation management systems to dynamic network conditions in ad hoc networks. IEEE Trans Comput, 2010, 59: 707-719 CrossRef Google Scholar

[15] Mejia M, Pe?a N, Mu?oz J L. DECADE: Distributed Emergent Cooperation through ADaptive Evolution in mobile ad hoc networks. Ad Hoc Networks, 2012, 10: 1379-1398 CrossRef Google Scholar

[16] Akkarajitsakul K, Hossain E, Niyato D. Coalition-based cooperative packet delivery under uncertainty: a dynamic Bayesian coalitional game. IEEE Trans Mobile Comput, 2013, 12: 371-385 CrossRef Google Scholar

[17] Duarte P B F, Fadlullah Z M, Vasilakos A V. On the partially overlapped channel assignment on wireless mesh network backbone: a game theoretic approach. IEEE J Select Areas Commun, 2012, 30: 119-127 CrossRef Google Scholar

[18] Yang Y H, Chen Y, Jiang C. Wireless Network Association Game With Data-Driven Statistical Modeling. IEEE Trans Wireless Commun, 2016, 15: 512-524 CrossRef Google Scholar

[19] Xiao Y, Niyato D, Chen K C. Enhance device-to-device communication with social awareness: a belief-based stable marriage game framework. IEEE Wireless Commun, 2016, 23: 36-44 CrossRef Google Scholar

[20] Xu C, Zhao Y, Zhang J F. Decision-implementation complexity of cooperative game systems. Sci China Inf Sci, 2017, 60: 112201 CrossRef Google Scholar

[21] Srinivasan V, Nuggehalli P, Chiasserini C F, et al. Cooperation in wireless ad hoc networks. In: Proceedings of the 22nd Annual Joint Conference of the IEEE Computer and Communications, San Francisco, 2003. 808--817. Google Scholar

[22] Felegyhazi M, Hubaux J P, Buttyan L. Nash equilibria of packet forwarding strategies in wireless ad hoc networks. IEEE Trans Mobile Comput, 2006, 5: 463-476 CrossRef Google Scholar

[23] Yu W, Liu K J R. Game Theoretic Analysis of Cooperation Stimulation and Security in Autonomous Mobile Ad Hoc Networks. IEEE Trans Mobile Comput, 2007, 6: 507-521 CrossRef Google Scholar

[24] Akkarajitsakul K, Hossain E, Niyato D. Cooperative packet delivery in hybrid wireless mobile networks: a coalitional game approach. IEEE Trans Mobile Comput, 2013, 12: 840-854 CrossRef Google Scholar

[25] Zhang H, Niyato D, Song L. Zero-Determinant Strategy for Resource Sharing in Wireless Cooperations. IEEE Trans Wireless Commun, 2016, 15: 2179-2192 CrossRef Google Scholar

[26] Li Z, Shen H. Game-theoretic analysis of cooperation incentive strategies in mobile ad hoc networks. IEEE Trans Mobile Comput, 2012, 11: 1287-1303 CrossRef Google Scholar

[27] Seredynski M, Bouvry P. Evolutionary game theoretical analysis of reputation-based packet forwarding in civilian mobile ad hoc networks. In: Proceedings of IEEE International Symposium on Parallel & Distributed Processing, Rome, 2009. 1--8. Google Scholar

[28] Song L, Niyato D, Han Z, et al. Game-theoretic resource allocation methods for device-to-device (D2D) communication. IEEE Wirel Commun, 2014, 21: 136--144. Google Scholar

[29] Jiang C, Chen Y, Liu K J R. Multi-Channel Sensing and Access Game: Bayesian Social Learning with Negative Network Externality. IEEE Trans Wireless Commun, 2014, 13: 2176-2188 CrossRef Google Scholar

[30] Xiao Y, Niyato D, Han Z. Dynamic Energy Trading for Energy Harvesting Communication Networks: A Stochastic Energy Trading Game. IEEE J Select Areas Commun, 2015, 33: 2718-2734 CrossRef Google Scholar

[31] Akkarajitsakul K, Hossain E, Niyato D. Game theoretic approaches for multiple access in wireless networks: a survey. IEEE Commun Surv Tutorials, 2011, 13: 372-395 CrossRef Google Scholar

[32] Khan M, Tembine H, Vasilakos A. Evolutionary coalitional games: design and challenges in wireless networks. IEEE Wireless Commun, 2012, 19: 50-56 CrossRef Google Scholar

[33] Hoang D T, Lu X, Niyato D. Applications of Repeated Games in Wireless Networks: A Survey. IEEE Commun Surv Tutorials, 2015, 17: 2102-2135 CrossRef Google Scholar

[34] Zhu Ji , Wei Yu , Liu K J R. A belief evaluation framework in autonomous MANETs under noisy and imperfect observation: vulnerability analysis and cooperation enforcement. IEEE Trans Mobile Comput, 2010, 9: 1242-1254 CrossRef Google Scholar

[35] Wang W, Chatterjee M, Kwiat K. Cooperation in wireless networks with unreliable channels. IEEE Trans Commun, 2011, 59: 2808-2817 CrossRef Google Scholar

[36] Nowak M A, Sigmund K. Evolution of indirect reciprocity. Nature, 2005, 437: 1291-1298 CrossRef PubMed ADS Google Scholar

[37] Yan Chen , Liu K J R. Indirect reciprocity game modelling for cooperation stimulation in cognitive networks. IEEE Trans Commun, 2011, 59: 159-168 CrossRef Google Scholar

[38] Tang C, Li A, Li X. When Reputation Enforces Evolutionary Cooperation in Unreliable MANETs.. IEEE Trans Cybern, 2015, 45: 2190-2201 CrossRef PubMed Google Scholar

[39] Tanabe S, Suzuki H, Masuda N. Indirect reciprocity with trinary reputations.. J Theor Biol, 2013, 317: 338-347 CrossRef PubMed Google Scholar

[40] Pacheco J M, Santos F C, Chalub F A C C. Stern-Judging: a simple, successful norm which promotes cooperation under indirect reciprocity. PLoS Comput Biol, 2006, 2: 1634--1638. Google Scholar

[41] Hofbauer J, Sigmund K. Evolutionary Games and Population Dynamics. Cambridge: Cambridge University Press, 1998. 92--95. Google Scholar

[42] Ohtsuki H, Iwasa Y, Nowak M A. Indirect reciprocity provides only a narrow margin of efficiency for costly punishment. Nature, 2009, 457: 79-82 CrossRef ADS Google Scholar

• Figure 1

(Color online) The illustration of the packet forwarding on distributed wireless network. At each time slot, the packets of the provider will be forwarded or dropped by the relay to the receiver depending on the provider’s reputation under channel loss probability $p_{e}$. Afterwards, reputation of the relay will get updated with the observed receiver signal under reputation updating error $\mu$. Then, the relay’s reputation is spread through a channel of noisy gossip from the receiver and the observers to the whole network. After the interaction, each participant returns to the network with probability $\omega$, or leaves the network with probability $1-\omega$ without return.

• Figure 2

The illustration of dynamic programming.

• Figure 3

The illustration of expected payoffs' calculation to the actions $FF$.

• Figure 4

(Color online) The evolutionary stability of the action $FD$ with $b=2.4$ and $c=1$. (a) The initial frequency of the action $FD$ is setting to $0.6$; (b) the initial frequency of the action $FD$ is setting to $0.35$.

• Figure 5

(Color online) The evolutionary stability of the action $FD$ with $b=1.6$ and $c=1$. (a) The initial frequency of the action $FD$ is setting to $0.85$; (b) the initial frequency of the action $FD$ is setting to $0.35$.

• Figure 6

(Color online) The average node payoffs of the full cooperation action and the optimal action with different channel loss probability when $\mu=0.01$.

• Figure 7

(Color online) The normalized data session throughput of the full cooperation action and optimal action with different channel loss probability when $\mu=0.01$.

• Figure 8

(Color online) The normalized data session throughput of hop count with different channel loss probability when $\mu=0.01$.

• Table 1   Notations in the paper
 Notation Physical meaning $\mathbf{S}$ The strategy set of packet forwarding $F$ The strategy forwarding $D$ The strategy dropping $\Theta$ The set of observed signal $f$ The observations of packet forwarding $d$ The observations of packet dropping $b$ Gain of a player as a provider $c$ Cost of a player as a relay $i(j)$ The index of player $I(J)$ The reputation of player $G (B)$ The player with good (bad) reputation $p_{e}$ The channel loss probability $\mu$ The reputation updating error $\omega$ The discounting factor of the furture $\mathbb{A}$ The action rule of relay $s_{G} (s_{B})$ The strategy for a relay towards a good (bad) provider $Q$ The social norm $q_{iJ}$ The reputation assigned to a relay who has taken the strategy $i$ towards a provider whose reputation is $J$ $q$ The social resolution of players $R'(R,X)$ The new reputation of a relay who takes the strategy $X$ towards a provider with reputation $R$ $N$ The set of all game players $x_{g}$ The frequency of good players $W_{I,J}$ Maximum payoff of a player can gain from this interaction to future, $I$ is currently reputation and $J$ is a reputation of opponent $\lambda$ Advantage of being a good player $m$ Index of action rule ($m$=1,2,3) $x_{m}$ Frequency of strategy $m$ $\eta$ Scale factor of dynamical evolution $P_m$ Expected payoff of action rule $m$ $\bar{P}$ Average payoff of three action rules

Citations

• #### 0

Altmetric

Copyright 2020 Science China Press Co., Ltd. 《中国科学》杂志社有限责任公司 版权所有