基于时隙ALOHA协议的数据传输二人随机博弈模型

doi:10.15960/j.cnki.issn.1007-6093.2019.04.004

运筹学学报 ›› 2019, Vol. 23 ›› Issue (4): 45-58.doi: 10.15960/j.cnki.issn.1007-6093.2019.04.004

基于时隙ALOHA协议的数据传输二人随机博弈模型

薛娟¹, 高红伟^1,2,*, 姜辉³, 周允旭⁴

1. 青岛大学数学与统计学院, 山东青岛 266071;
2. 山东省应用数学研究所, 山东青岛 266071;
3. 青岛大学研究生院, 山东青岛 266071;
4. 青岛大学国际交流合作处, 山东青岛 266071

收稿日期:2019-02-19 发布日期:2019-12-04
通讯作者: 高红伟 E-mail:gaohongwei@qdu.edu.cn
基金资助:
国家自然科学基金面上项目（No.71571108），国家自然科学基金国际（地区）合作交流项目（Nos.71611530712，61661136002），山东省“外专双百计划”项目（No.WST2017009）

Two-person stochastic game model of data transmission based on slotted ALOHA protocol

XUE Juan¹, GAO Hongwei^1,2,*, JIANG Hui³, ZHOU Yunxun⁴

1. School of Mathematics and Statistics, Qingdao University, Qingdao, 266071, Shandong, China;
2. Institute of Applied Mathematics of Shandong, Qingdao 266071, Shandong, China;
3. Graduate school of Qingdao university, Qingdao, 266071, Shandong, China;
4. International Office of Qingdao University, Qingdao, 266071, Shandong, China

Received:2019-02-19 Published:2019-12-04

摘要/Abstract

摘要： 在一个给定的拓扑网络中研究关于数据传输的二人随机博弈模型.两个局中人（源节点）试图通过一个公共节点向目的节点传输随机数据包，这些数据包被分为重要的数据包和不重要的数据包两类，假设每个局中人都有一个用于存储数据包的有限容量的缓冲器.通过构造数据传输的成本分摊和奖励体系，把这种动态的冲突控制过程建模为具有有限状态集合的随机博弈，研究局中人在这种随机博弈模型下的非合作以及合作行为.在非合作情形下，给出纳什均衡的求解算法；在合作情形下，选择Shapley值作为局中人支付总和的分配方案，并讨论其子博弈一致性，提出使得Shapley值为子博弈一致的分配补偿程序.

关键词: 数据传输随机博弈, Nash均衡, Shapley值, 子博弈一致性, 分配补偿程序

Abstract: Considering a stochastic game model of data transmission in a network of a given topology. Two players (source nodes) try to transmit packages to the destination node through a common node. These packages are divided into important packages and not important packages. Each player has a buffer of limited capacity to store packages. We define a system of cost and reward, and this dynamic conflict control process is modeled as stochastic game with a finite set of states. We study the non-cooperative and cooperative behaviors of players. We calculate the Nash equilibrium under the noncooperative situation. Shapley value is chosen as the solution of the cooperation game. We discuss the subgame consistency of Shapley value and propose a imputation distribution procedure.

Key words: stochastic game of data transmission, Nash equilibrium, Shapley value, subgame consistency, imputation distribution procedure

中图分类号:

O225

薛娟, 高红伟, 姜辉, 周允旭. 基于时隙ALOHA协议的数据传输二人随机博弈模型[J]. 运筹学学报, 2019, 23(4): 45-58.

XUE Juan, GAO Hongwei, JIANG Hui, ZHOU Yunxun. Two-person stochastic game model of data transmission based on slotted ALOHA protocol[J]. Operations Research Transactions, 2019, 23(4): 45-58.

参考文献

[1] Roberts L G. ALOHA packet system with and without slots and capture[J]. ACM SIGCOMM Computer Communication Review, 1975, 5(2):28-42.
[2] Altman E, Barman D, Azouzi R E, et al. A game theoretic approach for delay minimization in slotted ALOHA[C]//2004 IEEE International Conference on Communications. Paris:IEEE, 2004, 3999-4003.
[3] Marban S, Van de ven P, Borm P, et al. ALOHA networks:a game-theoretic approach[J]. Mathematical Methods of Operations Research, 2013, 78(2):221-242.
[4] Sagduyu Y E, Ephremides A. A game-theoretic look at simple relay channel[J]. Wireless Networks, 2006, 12(5):545-560.
[5] Afghah F, Razi A, Abedi A. Stochastic game theoretical model for packet forwarding in relay network[J]. Telecommunication Systems, 2013, 52(4):1877-1893.
[6] Herings P J-J, Peeters R J A P. Stationary equilibria in stochastic games:structure, selection, and computation[J]. Journal of Economic Theory, 2004, 118(1):32-60.
[7] Jaskiewicz A, Nowak A. On pure stationary almost Markov Nash equilibria in nonzero-sum ARAT stochastic games[J]. Mathematical Methods of Operations Research, 2015, 81(2):169-179.
[8] Rosenberg D, Solan E, Vieille N. The max-min value of stochastic games with imperfect monitoring[J]. International Journal of Game Theory, 2003, 32(1):133-150.
[9] Petrosyan L A. Cooperative stochastic games[M]//Advances in Dynamic Games, Annals of the International Society of Dynamic Games. Boston:Birkhäuser, 2006, 139-146.
[10] Petrosyan L A, Baranova E V. Cooperative stochastic games in stationary strategies[M]//Game Theory and Applications. New York:Nova Science Publishers, 2006, 7-17.
[11] Petrosyan L A. Stable solutions of differential games with many participants[J]. Viestnik of Leningrad University, 1977, 19:46-52.
[12] Petrosyan L A, Danilov N N. Stability of solutions in non-zero sum differential games with transferable payoffs[J]. Vestnik of Leningrad University, 1979, 1:52-59.
[13] Parilina E M. Strategic support of the Shapley value in stochastic games[J]. Contributions to Game Theory and Management, 2016, 9:246-265.
[14] Lemke C E, Howson J T. Equilibrium points of bimatrix games[J]. Journal of the Society for Industrial and Applied Mathematics, 1964, 12(2):413-423.
[15] Fink A M. Equilibrium in a stochastic n-person game[J]. Journal of Science of the Hiroshima University, Series A-I (Mathematics), 1964, 28(1):89-93.
[16] 高红伟, 彼得罗相(俄). 动态合作博弈[M]. 北京:科学出版社, 2009.
[17] Dockner E J, Jorgensen S, Long N V, et al. Differential games in economics and management science[M]. Cambridge:Cambridge University Press, 2000.
[18] Aumann R J, Peleg B. Von Neumann-Morgenstern solutions to cooperative games without side payments[J]. Bulletin of the American Mathematical Society, 1960, 66(3):173-180.
[19] Gao H W, Petrosyan L A, Qiao H, et al. Cooperation in two-stage games on undirected networks[J]. Journal of Systems Science and Complexity, 2017, 30(3):680-693.
[20] Wang L, Gao H W, Petrosyan L A, et al. Strategically supported cooperation in dynamic games with coalition structures[J]. Science China-Mathematics, 2016, 59(5):1015-1028.

基于时隙ALOHA协议的数据传输二人随机博弈模型

Two-person stochastic game model of data transmission based on slotted ALOHA protocol

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 5

编辑推荐

Metrics

本文评价

[1]	于晓辉, 杜志平, 张强, 逄金辉. 基于T-联盟Shapley值的分配策略[J]. 运筹学学报, 2020, 24(4): 113-127.
[2]	王磊, 林崇, 谷岩, 刘翠, 高红伟. 无限阶段网络博弈中合作解的策略稳定性[J]. 运筹学学报, 2018, 22(1): 77-86.
[3]	胡勋锋, 李登峰. Shapley值与Winter值的解析关系[J]. 运筹学学报, 2015, 19(4): 114-120.
[4]	聂翠平, 张强. 模糊联盟合作对策的平均树解[J]. 运筹学学报, 2012, 16(4): 77-85.
[5]	彼得罗相. 微分对策中的联盟解[J]. 运筹学学报, 2012, 16(4): 86-94.