移动互联网中博弈模型与机制设计研究

发布时间：2020-05-27 08:44

【摘要】：移动互联网的快速发展和丰富的移动应用极大地改变了现代人类的生活方式:微信改变了人们交流沟通的方式,移动支付正取代现金支付成为主流支付方式,共享单车填补出行最后一公里空白。移动互联网的高效稳定运行有赖于各组网节点的协同合作。然而,由于网络节点大都来自于具有不同利益目标的组织或个人,网络节点的个体优化目标与网络系统整体优化目标不一致,甚至存在冲突。网络节点的理性自私行为将会使网络系统进入无政府状态,降低系统整体性能。因此,需要有效的机制来保证网络节点的协同合作,杜绝策略操纵行为,以使移动互联网能够有序、高效、稳定的运转。本论文运用博弈论与机制设计基本原理,来分析移动互联网中自私网络节点的相互作用关系,以及节点的策略行为对网络系统性能的影响。我们以“互联——节流——开源——传输——实证”为主线,为移动互联网中的四大典型应用:频谱资源分配(互联)、群智感知计算(节流)、网络数据市场(开源)和云带宽资源管理(传输),设计高效激励机制来达到协同合作与互利共赢的目的,并采用大规模仿真实验来验证提出机制的性能。具体来说,本论文的主要研究内容和创新成果包括:首先,研究动态频谱资源管理,以提高频谱资源使用率,从而保证移动互联网稳定无线互联。我们提炼出设计合理、贴近实际的频谱分配方案的技术挑战:理性用户策略行为、频谱空间重用性、频谱异质性、资源需求多样性和最优社会福利求解复杂性。综合考虑以上五点设计挑战,基于组合拍卖理论基本原理,本论文设计了一系列适应不同场景的异质频谱拍卖机制。具体地说,我们考虑两种不同的策略博弈模型:单维度博弈模型(买家只能操纵单一维度私有信息)和多维度博弈模型(买家能操纵多维度私有信息)。针对单维度博弈模型,提出了防策略性和近似最优的异质频谱拍卖机制(SMASHER)。在多维度博弈模型中,我们进一步考虑单需求买家和多需求买家两种情况。对于前者,设计了满足防策略性的直接揭示组合频谱拍卖机制(AEGIS-SG)。对于后者,提出了一套迭代上升组合频谱拍卖机制(AEGIS-MP),实现未占优策略均衡。AEGIS-SG和AEGIS-MP机制都能达到近似最优社会福利。基于真实数据集,我们进行了大规模仿真模拟实验。实验结果表明SMASHER和AEGIS机制在社会福利、拍卖收益、买家满意度和信道利用率等指标上优于现有机制,并接近最优值。其次,研究群智感知中的酬劳机制,以激励移动用户参与到感知数据采集中,从而保证群智感知系统的持续高效运行。我们提炼出设计高效酬劳分配机制的技术挑战:理性用户自私性、酬劳预算限制性、任务完成不确定性和最优目标求解复杂性。综合这些设计挑战,重点考虑两个互补的优化问题:在酬劳预算限制条件下,最大化采集数据覆盖范围;在满足任务完成概率要求下,最小化数据采集成本。对于第一个优化问题,提出BEACON机制,包含数据采集任务分发算法和酬劳计算方法。可以证明BEACON机制满足防策略性和预算限制性,并能够在多项式时间内实现常数倍近似比。在第二个优化问题中,考虑到任务完成的不确定性,我们提出了具有容错性的酬劳分配机制TORCH,并证明该机制能够达到近似最优采集成本,且能防止用户在任务完成概率上的策略行为。我们在上海交通大学闵行校区部署了群智感知系统用于绘制校园噪声图谱,基于采集数据,进行大规模实验仿真来衡量机制BEACON和TORCH的性能。再次,研究网络数据交易市场中的数据定价机制,鼓励数据拥有者分享数据,从而打破数据壁垒,促进数据共享流通,进一步释放数据价值。重点关注感知数据交易市场中的数据采集和数据定价两方面内容。在数据采集机制设计中,需要考虑理性数据贡献者的策略行为、感知数据不确定性和最大化利润求解复杂性。我们提出以数据市场交易利润为导向的众包数据采集机制VENUS。为确定每个数据采集点的期望支付报酬,设计了数据采购逆向拍卖机制,既能保证防策略性,又能达到最优支付报酬。对于数据定价模块,需要考虑感知数据不确定性、定价机制灵活性与鲁棒性和非完全信息利益最大化的复杂性这三点设计挑战,并设计了基于在线学习的数据定价机制,称为ARETE。ARETE机制包括两部分内容:版本划分和在线定价。版本划分算法为数据商品生成不同精度版本,在线定价算法逐步学习数据消费者的数据估值,动态决定数据价格。我们证明了ARETE机制能够防止数据消费者的套利行为,并在数据交易收益上能达到常数倍竞争比。最后,研究云带宽资源管理,以提高云带宽网络资源的使用率,从而保证移动互联网可靠的大数据传输。我们重点研究了云带宽市场中两个基本优化问题:社会福利最大化和交易收益最大化。在社会福利最大化问题中,我们认为云带宽市场的设计需要克服三大挑战:多维度策略行为、多样化带宽需求和最优社会福利求解的计算复杂度。本论文提出首个防策略性云带宽拍卖机制(SOAR)。对于区间带宽需求模型、严格带宽需求模型和灵活带宽需求模型,分别设计了机制SOAR-VCG,SOAR-APX和SOAR-GDY。我们随后考虑交易收益最大化问题,并提出满足无嫉妒性和无套利性的云带宽定价机制。考虑到收益最大化问题的非凸优化特性和用户效益函数信息缺失,我们提出一系列近似最优云带宽定价机制来解决不同网络拓扑结构下的云带宽资源定价。对于单链路网络拓扑,我们的云带宽定价机制能够在多项式计算复杂度内取得(1+?)近似比。基于动态规划思想,将该定价机制拓展到树型网拓扑结构。对于普适网络拓扑结构,当用户具有相似效益函数时,均一定价策略能够达到较好近似比。我们还将定价策略拓展到多时间槽情况,以实现动态带宽定价机制。
【图文】：

频谱,拍卖机制,频谱,动态

图 1 2 动态频谱拍卖机制设计挑战Figure 1 2 Design Challenges of Dynamic Spectrum Auctions估值总和。最大化社会效益意味着我们希望把频谱资源分买家，保证稀缺频谱资源的有效利用。在复杂的频谱交易

框架图,网络市场,框架,互联网时代

图 1 3 群智感知网络市场框架Figure 1 3 The Market Framework for Mobile Crowdsensing群智的概念诞生于互联网时代，是一种分布式计算模式，即通过互联网分配工作任务，借助群体的智慧来发现创意或解决技术问题。近年来，
【学位授予单位】：上海交通大学
【学位级别】：博士
【学位授予年份】：2018
【分类号】：O225;TP393.09;TN929.5

【参考文献】