基于VCG拍卖机制的任务卸载策略

基于电力巡检机器人的变电站自动巡检技术能够快速找到故障区域,提升巡检效果。然而由于机器人终端的计算资源和能量有限,如何实时高效地处理巡检机器人采集的图像信息等以实现快速巡检是一个待解决的挑战。考虑到同时存在多个机器人终端将计算任务卸载给多个边缘计算供应商(edge computing provider,ECP),文章提出了基于VCG(Vickrey-Clarke-Groves)拍卖机制的计算任务卸载方案以降低任务处理时延并最大化ECP收益。首先,建立了多个终端向多个ECP进行任务卸载的异构网络模型。考虑到真实任务场景中任务可能是可以拆分的,将子任务以有向无环图(directed acyclic graph,DAG)的形式进行建模,并提出了考虑通信和计算资源时延的计算任务卸载算法。该算法考虑了每个ECP的收益,并通过VCG拍卖机制设计拍卖算法以保证该算法的真实性和有效性。最后,仿真证明该算法的性能能够迅速逼近最优卸载决策。

考虑源荷不确定性的多微电网鲁棒优化调度与VCG机制竞价策略

现代微电网集群新能源就地消纳的高效性和调度策略规避风险的能力日益受到关注,其与源荷不确定性和微电网之间的交互模式密切相关。为此,基于维克瑞–克拉克–格罗夫斯交易机制(Vickrey-Clarke-Groves,VCG)和鲁棒优化理论,提出了多微电网两阶段鲁棒优化调度模型,第1阶段:“新能源互补交易–净负荷波动平抑–余负荷功率平衡”优化调度模型,首先直接针对微电网间余缺新能源进行互补竞争性交易,引入VCG机制应对微电网谎报估值的行为,合理匹配余缺新能源,实现新能源高效就地消纳;再基于储能平抑拍卖之后的净负荷功率波动,综合考虑净负荷均方差和储能成本最小,优化储能充放电策略;最后通过可控机组以及与配电网交互实现余负荷功率平衡。第2阶段:不确定性决策校正模型,根据不确定性实际出现的情况对第1阶段的优化决策进行校正。采用列约束生成算法(columnand constraint generation algorithm,C&CG)求解优化模型,通过两阶段交互迭代以寻找恶劣场景,并得到该恶劣场景下微电网间的交易策略以及各设备功率调度计划。仿真结果验证了所提策略的有效性。

命令式动态规划类算法程序推导及机械化验证

动态规划是一种递归求解问题最优解的方法,主要通过求解子问题的解并组合这些解来求解原问题.由于其子问题之间存在大量依赖关系和约束条件,所以验证过程繁琐,尤其对命令式动态规划类算法程序正确性验证是一个难点.基于动态规划类算法Isabelle/HOL函数式建模与验证,通过证明命令式动态规划类算法程序与其的等价性,避免证明正确性时处理复杂的依赖关系和约束条件,提出命令式动态规划类算法程序设计框架及其机械化验证.首先,根据动态规划类算法的优化方法(备忘录方法)和性质(最优子结构性质和子问题重叠性质)描述问题规约、归纳递推关系式和形式化构造出循环不变式,并且基于递推关系式生成IMP(minimalistic imperative programming language)代码;其次,将问题规约、循环不变式和生成的IMP代码输入VCG(verification condition generator),自动生成正确性的验证条件;然后,在Isabelle/HOL定理证明器中对验证条件进行机械化验证.算法首先设计为命令式动态规划类算法的一般形式,并进一步实例化得到具体算法.最后,例证所提框架的有效性,为动态规划类算法的自动化推导和验证提供参考价值.

一种基于VCG拍卖的分布式网络资源分配机制

网络带宽资源分配的不合理是开放性网络环境中的一个突出问题.为抑制用户自私性行为,提出基于VCG(Vickrey-Clarke-Groves)机制的网络资源竞拍分配机制.该机制具有占优策略激励兼容特性,且仅需单维竞价信息.同时给出了指导用户进行策略选取的离散随机式学习算法,进一步分析了该算法的收敛性.仿真结果表明,本文所提出的分配机制通过有效的支付惩罚,使自私用户主动选择真实带宽需求策略,抑制说谎动机;离散随机式学习算法能够正确地引导用户选择出占优策略,合理分配带宽资源.

基于VCG机制的动态频谱分配算法

针对在Underlay频谱共享方式下的认知无线网络动态频谱分配问题,在满足主用户服务质量(QoS)的前提下,建立一种非合作博弈模型,并设计其效用函数。在借鉴VCG机制的基础上,设计相应的收益函数,提出一种可以最大化认知无线网络系统吞吐量且保证公平性的分布式动态频谱分配算法。仿真结果表明,该算法收敛速度快、公平性强。

具有计算复杂性的VCG机制投标策略研究

在组合拍卖的获胜者确定问题(WDP)具有计算复杂性的情况下,研究了相应的VCG机制中投标者的投标策略问题。通过提出2类重要概率,描述了投标者对于VCG机制WDP算法和其真实估价对于组合拍卖分配效率的信念。通过建模分析,揭示了在具有计算复杂性的VCG机制中,上述2类重要概率、投标者获胜后事后效用、跳投标增量与投标策略之间的确定性关系。

VCG机制在P2P存储系统副本放置中的应用

在点对点(P2P)存储系统副本放置简化模型下引入维克瑞—克拉克—格罗夫斯机制(VCG),建立副本放置模型到VCG机制的映射,设计适当的支付函数以达到副本预放置节点的激励相容,并分析占优战略均衡的存在性,证明了该均衡在多项式时间内可达到均衡。仿真实验表明该机制能达到预放置节点的激励相容。

含储能参与的日前市场价值公平分配机制

现有的节点边际电价机制中,由于传统发电商具有市场操控力,当储能独立参与市场出清时,各发电商采取策略性报价,打压并挤占储能电站的市场份额,阻碍了储能电站参与市场出清,间接导致市场出清总成本增大。为此,文中提出一种包含传统机组以及储能电站参与的市场竞争机制。首先,分析现有市场结算机制的弊端以及阻碍储能参与市场出清的原因;其次,建立含储能参与的市场出清模型,采用样本均值近似法求解二阶段随机规划模型;然后,基于Vickrey-Clarke-Groves(VCG)结算机制,提出适应储能参与的日前市场价值分配机制;最后,提出解决激励相容而造成的系统收支不平衡问题的策略。文中采用IEEE 30节点系统为例,证明该机制满足激励相容、收支平衡以及削弱传统发电商的市场操控力等要求,同时储能的参与将会减小系统出清总成本,降低市场价格剧烈波动的风险。

电碳联合市场下发电商激励性竞价策略

为在电力市场、碳市场和绿证市场下优化发电商的竞价策略,该文提出了一种电-碳联合市场下发电商竞价模型。首先,建立了发电商电-碳交易成本函数,实现对电-碳联合市场成本传导的量化分析。其次,以发电商自身综合收益最大化为目标函数,并考虑电量、碳配额和绿证3类交易产品的耦合约束,建立了电-碳联合市场下发电商竞价模型,并提出模型的线性化重构和求解方法。此外,引入Vickrey-Clarke-Groves(VCG)机制设计理论,提出适用于电-碳联合市场的发电商激励性竞价策略,抑制发电商恶意虚假报价。通过对上海某地区进行算例分析,验证了所提模型能提高发电商收益及促进碳减排,为电-碳联合市场下的发电商组合交易提供参考。

一种基于VCG机制的差分式隐私服务定价机制

大数据环境下,数据具有种类多、数量大、增长速度快及价值密度低等特点,若对所有的隐私数据都提供相同程度的保护必然会造成计算资源的浪费,因此必须对隐私数据施行分级保护。差分隐私是具有严格数学定义的隐私保护模型,其以概率为基础量化了隐私保护程度,可以利用隐私预算ε对隐私保护程度划分等级。假设存在隐私保护等级的前提下,提出了分级隐私保护服务模型,基于VCG机制与最优匹配相结合的方法,为各级隐私保护服务制定合理的价格以引导用户理性地选择隐私保护服务等级。运用该机制为6个等级的隐私保护服务制定了相应的价格。分析表明,该服务模型中的定价机制可以合理地制定每个等级之间的价格,实现了隐私数据分级保护,优化了社会资源的配置。

基于VCG机制的无线网络呼叫接入控制算法

提出一种基于VCG机制的无线网络呼叫接入控制(CAC)算法。该算法采用VCG机制调节用户需求,控制资源分配,以实现资源合理使用。CAC算法适合于无线接入网络中多业务服务、多优先级服务的情况。仿真结果表明,将VCG机制与CAC算法结合,能较好地改善无线网络性能,提高系统连接级的QoS。

基于VCG-Kelly机制的钢铁企业能源分配的研究

钢铁企业能源中心的主要目标是确保生产用能的稳定供应和动态调配。为了抑制二级厂自私性行为,提出了基于VCG-Kelly机制的能源分配机制。该机制具有占优策略激励兼容特性,且只需一维竞价信息。仿真结果表明,本文所提出的分配机制通过有效的价格惩罚,使自私二级厂主动地选择真实的能源需求策略,抑制其说谎的动机,进而使能源能得到合理的分配。

带预算约束的关键词拍卖研究——基于VCG机制的视角

文章研究了带有预算约束的基于VCG机制关键词拍卖问题。之前学者的研究一般不考虑预算约束的情况,但是广告主在参与广告位竞价时,通常都会提前分配每天的预算。当广告主的支付价格达到他的预算时,就会退出此次拍卖。在VCG机制中,广告主的支付是由排位在他之后的广告主的点击率和报价的线性组合决定,所以广告主会调增报价来提高竞争对手的支付价格。文章借助带有预算约束的全局无嫉妒纳什均衡条件,给出达到均衡时的预算阈值。结果表明合理设置预算对于广告主降低成本和提高收益都有一定影响。

基于VCG机制的移动Ad hoc网络路由改进策略

移动Ad hoc网是一种新兴的无线移动自组织网络,其路由机制与传统网络有很大差异。在分析VCG(Vickrey-Clark-Groves)路由机制的基础上,针对恶意节点的欺骗行为,提出了一种新兴的安全路由策略-YWCR。在保证数据包转发效率的前提下,杜绝了路由过程中恶意节点的欺骗行为。

价值发现视角下电网侧储能电站的定价机制研究

电网侧储能电站可以更好地发挥集群效应,促进新能源的消纳,但规模化应用又极易形成联盟产生市场力,不利于市场发展。节点边际电价在理论和实践中已经被证实无法同时满足市场出清时激励相容、个体理性和社会福利最大化对能源定价机制的要求。因此,基于维克里-克拉克-格罗夫斯(Vickrey-Clarke-Groves,VCG)机制设计理论,提出一种电网侧储能电站参与市场的能源定价机制,降低市场力的影响作用,发现储能电站最大价值。首先,以购电成本最小为目标建立综合考虑储能成本的日前市场出清模型;其次,提出基于VCG机制设计理论的电网侧储能电站定价机制,促进其理性报价、实现电力资源优化配置,并通过理论证明所提机制具有激励相容、个体理性和社会福利最大化的市场性质;最后,基于改进的IEEE 30节点系统进行实证分析,验证了该机制有效降低市场力,克服了节点边际电价能源定价机制下电网侧储能联盟的战略竞价行为,实现了市场社会福利最大化和有效的日前市场运作。

普适计算环境中防护策略的信任决策机制研究

普适计算信任模型中,存在自私用户为最大化自身利益而故意策略性谎报推荐信息的问题.文中提出了一种基于VCG(Vickrey-Clarke-Groves)机制的防护策略信任机制,用以获得用户的真实推荐.该机制实现了交互结果观测前的快速支付.一种基于连续多数加权算法的加权VCG防护策略机制被用于调整推荐权重.该文还给出了一般形式的信任决策机制并研究其激励相容特性以便可以构造更多的信任机制,这些信任机制结合已有的信任模型可以实现真实推荐.模拟结果显示,提出的信任机制有效,能保证自私用户提供诚实推荐.

基于机制设计理论的自组网节点合作协议

在移动自组网中,如何激励自私节点,使之参与网络合作,是当前研究的热点问题.文中提出了LMOCP协议,采用VCG机制计算转发节点的支付.通过引入邻居发现机制,并改进路由发现过程,使网络中控制消息的数量从O(n3)减少到O(n2).对协议的正确性进行了分析,并证明了LMOCP协议是事后纳什可实施的,在所有节点都是理性的这一共同知识的假定下,每个节点的最优策略是诚实地报告自己的转发价格.通过ns-2对协议进行了验证,仿真结果显示,与现有的几种重要协议相比,LMOCP协议具有更低的消息负载和网络延迟.

机制设计理论及其在计算机网络协议设计中的应用研究

计算机网络协议的设计一般假设参与者是完全服从的。对于域间路由、IP多播、P2P文件共享等问题,这个假设并不成立。这些问题中各参与者都是自治的主体,其行为是自利的,以追求自身的利益最大化为目标。这给网络协议的设计带来挑战。机制设计理论用于设计多主体之间的博弈规则,以获得期望的结果。该理论为计算机网络中出现的这类问题的协议设计提供了方向。本文首先介绍了机制设计的基本概念,并以路由为例说明了其在计算机网络中的具体应用。传统的机制设计理论是微观经济学和博弈论的分支,在具体应用到计算机网络中需要处理很多新的问题,例如计算复杂性、隐私、分布式计算等。文章对近年来该领域的研究成果做了总结,并指出了未来的研究方向。

组合拍卖与议价谈判机制设计研究

设计了一种先"组合拍卖"再"议价谈判"的多物品出售两阶段机制.论文分析表明,机制的组合拍卖阶段保持了VCG机制的激励相容性质,在机制的议价谈判阶段,存在4种不同类别的获胜投标者,就拍卖者将采取的不同价格策略,可将其区分为"第1类投标者"和"第2类投标者".据此,找到了拍卖者采取不同价格策略的相应条件.给出了该机制中拍卖者与任意获胜投标者之间的博弈均衡路径.就买卖双方的总估价而言,存在不同相对关系下的不同交易结果.对比该机制和经典VCG机制,该机制改进社会交易福利值为:第1类投标者在议价价格和VCG价格下带给拍卖者利润的变化值.此结果表明,该机制的社会交易福利优于经典VCG机制.

激励性含柔性负荷日前市场出清电价机制的建模

对于电力市场而言,发电竞争只是电力改革的初级阶段,进一步让柔性负荷参与市场竞价是电力市场化的必经之路。传统上采用节点边际电价的日前市场出清电价机制,理论与实践均证明,该机制难以同时实现个体理性、激励相容和社会福利最大化等要求。考虑到电力市场成员之间的信息不对称性,为克服电力市场中市场成员的策略性报价行为,实现市场的高效运行及社会福利最大化,基于VCG的机制设计理论,给出了一种考虑发电机组和柔性负荷参与日前市场出清的电价机制,该机制同时满足激励相容、个体理性以及社会福利最大化要求。最后,采用某2节点系统和修改的IEEE14节点系统为例说明了该日前市场出清电价机制的基本特征。