基于逆向拍卖的D2D边缘缓存网络编码内容定价与交易机制.pdf

第 卷第 期 年 月南 京 邮 电 大 学 学 报（自 然 科 学 版）（）：基于逆向拍卖的 边缘缓存网络编码内容定价与交易机制殷 俊，凌 仙南京邮电大学 物联网学院，江苏 南京()摘要：在 边缘缓存网络中引入网络编码技术具有缓存利用率高、数据块调度过程简单及系统鲁棒性高等优点。但是，由于对编码块分享所带来的设备能量消耗等顾虑，用户倾向于只从网络获取内容而进行内容分享，这种自私行为直接影响了系统的总体性能。针对该问题，提出了一种基于逆向拍卖的 编码网络内容分享激励机制 。以实现网络内容分享总效用最大化为目标，将内容请求者视作拍卖过程的买家，而将买家周围的潜在内容提供者视为拍卖过程的卖家；买、卖方的内容叫价过程可综合考虑其自身电量资源、用户之间传输距离以及传输内容的供需关系等影响因素；拍卖结果允许多个卖家中标，并采用虚拟代币结算，从而激励用户间相互分享缓存内容。理论分析证明 机制符合双边激励相容性、个人理性约束、物质及弱预算平衡特征，可有效约束买、卖方拍卖行为。仿真实验进一步表明，机制能够有效地激励网络内用户间编码内容分享过程，最大化边缘缓存网络效用。关键词：边缘缓存网络；网络编码；定价与交易机制；逆向拍卖中图分类号：文献标志码：文章编号：（），()收稿日期：；修回日期：本刊网址：基金项目：国防基础科研计划（，）、南邮创新基金（）和江苏省研究生科研与实践创新计划（）资助项目作者简介：殷俊，男，博士，讲师，引用本文：殷俊，凌仙基于逆向拍卖的 边缘缓存网络编码内容定价与交易机制南京邮电大学学报（自然科学版），（）：，：；随着智能手机的进一步普及，移动网络数据流量呈现出爆发性增长态势。在现有移动网络架构下，用户均是直接从核心网获取数据，这一过程越来越对回程链路（）的带宽带来挑战。为了缓解移动网络压力，边缘缓存和（）技术相结合成为业界研究热点。在边缘缓存网络中通过引入 通信技术，将热门内容提前缓存至用户设备上，实现用户间内容共享，可以达到减轻基站负载、降低核心网络负担的作用。然而，由于用户的频繁移动特性，边缘缓存网络也面临一个关键问题：即应该从哪些邻居处下载哪些内容的数据块调度问题。引入网络编码技术能够巧妙地解决该问题。网络编码的核心思想是将源文件块编码成若干编码块，用户间内容分享时均是传输这些各异的编码块。内容请求用户只需要获取一定数量编码块即可解码出源文件。由于各编码块对于用户文件解码价值是相同的，因此避免了复杂的数据块调度过程，且系统对于拥有“稀有”内容用户的离开具有更好的鲁棒性。尽管在 边缘缓存网络中引入网络编码可以带来上述优势，但是受到用户设备电池容量、计算能力等限制，用户倾向于只从邻居用户处下载内容而不愿向其分享自己拥有的内容。这种自私行为会严重削弱网络内容分享频率，从而导致系统性能退化。目前解决该问题的方法通常是设计基于虚拟代币的激励机制，通过将用户间的内容分享行为转化为一种可以定价的交易，并引入虚拟代币进行交易支付来激励用户间的内容分享。然而，不同用户对于不同的内容具有不同的估值，并且估值是一个动态行为，系统无法提前进行预定。因此，合理设定内容交易价格是困难的但又是必要的。拍卖是一种广泛应用的交易定价形式。例如经典的第一价格拍卖和第二价格拍卖。第一价格拍卖的内容由最高出价的买方竞得，并以其叫价进行交易，是一种卖方收益最大化的竞价策略；第二价格拍卖也称维克里拍卖，该拍卖将内容出售给竞价最高的买方，但支付的价格是所有买方竞价中的第二高价，是一种符合激励相容特征的交易机制。其他内容定价交易策略，例如 考虑移动场景下用户蜂窝流量卸载的激励问题，提出一种基于拍卖的中继用户选择算法和支付机制；为了降低系统功耗，等通过一种多轮次组合拍卖算法来决定资源包的定价与匹配策略；类似地，等考虑 辅助边缘计算系统中计算资源的分配，也提出一种拍卖方案 ，该方案首先根据身份确认将用户分为买方集合和卖方集合；然后，考虑延迟和资源条件对买卖用户集合进行排序，确定用户间交易的候选集合；最后，根据买卖用户的出价和叫价来确定交易的定价和分配。尽管 定价策略可以有效地激励 用户间进行分享内容行为，但并未考虑网络用户传输内容的代价和内容的供需关系对交易定价的影响。此外，考虑到交易过程中用户自私性问题（即通常买方用户想要以较低的价格买入交易商品，而卖方则期望以较高的价格卖出商品的问题），如何协调双方的效用分配矛盾亦是一个关键问题。因此，有必要设计一个更实际的激励策略，在激励用户间分享内容的同时，定价过程让所有的交易用户都能够披露自己的真实估价，从而提高整个边缘缓存网络的内容分享效率。本文以实现网络总效用最大化为目标，应用虚拟代币支付模式提出一种基于逆向拍卖的编码内容分享定价与交易机制（）。区别于经典单个中标人的拍卖方式，所采用的多个中标人的逆向竞价拍卖方式更契合 边缘缓存网络编码内容分享竞价问题。因为一个内容请求者想要获取一个完整的文件，那么他可以从一个或多个邻居处（多中标人）各获得这个文件的若干数量编码块，从而解码得到原始文件。此外，为了约束参与人的交易行为，使得拍卖市场的可持续发展，机制还需要符合双边激励相容、个人理性约束、弱预算平衡和物质平衡特征等必要性特征。综上，本文的主要贡献如下：南京邮电大学学报（自然科学版）年（）考虑到网络缓存压力和数据块调度问题，建立了基于网络编码的边缘缓存网络交易市场模型，并给出了符合编码内容交易的逆向拍卖机制框架来撮合用户间内容分享行为。（）提出边缘缓存网络交易商品的定价和分配机制。为了实现网络总效用最大化，买卖双方的报价或叫价可由其设备的当前状态（如剩余电量）和拍卖内容当前供需关系共同决定。在此基础上，结合商品交易价格、买卖方报价和叫价，给出了用户的效用函数和网络总效用函数。（）给出了 机制符合双边激励相容、个人理性约束、弱预算平衡及物质平衡等特征的理论证明。数值实验结果亦验证了该机制的有效性和有益性。系统模型考虑一个典型的 边缘缓存网络，由若干小基站和随机分布在小基站周围的用户设备组成。如图 所示，用户随机分布在小基站周围，包括可以直接进行 通信的用户对和直接与小基站通信的用户。假设网络中每个用户设备都采用电池供电，并记 来表示用户设备 在 时刻的设备电量，且每个用户设备都拥有一个缓存空间，受到主动行为的激励，用户会在设备上缓存自身感兴趣的内容。此外，小基站通过 网络连接互联网并具有缓存内容，用于存储满足用户需要的各种内容。为了减小网络缓存压力和解决数据块调度问题，考虑用户设备中的缓存内容是采用网络编码形式进行传输的，即传输的文件内容是编码块。图 边缘缓存网络内容分享系统模型用户在请求感兴趣的内容时，优先选择可以与其直接进行 通信的邻居用户（假设用户间可通信范围的最大半径为，即认为当用户间隔 时，可以相互传输内容）；只有当邻居用户无法满足请求时，用户才会选择从基站处下载内容。但无论用户从哪下载了多少编码块，都需要支付相应的虚拟代币。这种虚拟代币可以与现实世界的货币没有联系，但依然可以激励用户间内容分享行为，并且已经在商业 系统中提出。自然地，用户间的内容分享过程可以被视作为买卖方间的商品交易过程。其中，内容请求用户充当买方，内容提供用户充当卖方，交易的商品是用户设备缓存中的编码块。为了合理地进行商品的交易定价和买卖方的撮合匹配，本文将商品的定价和匹配过程建模为一个拍卖市场。不失一般性，考虑一个兴趣文件的编码块定价问题。假设每个买家周围的卖家数量服从密度为 的泊松分布，即在买方用户 距离内存在 个卖方用户的概率为（；）（）！（）边缘缓存网络编码内容交易拍卖市场 将拍卖市场建模为离散时间系统，由于用户设备的移动性会影响 传输，因此假设在一个 交易周期中的所有用户设备都保持相对静止的状态。拍卖交易机制采用密封报价形式进行拍卖，且在一个离散有限时间，上进行探讨。在一个拍卖交易市场中，参与者包括一个买方和多个卖方，记为 ，且有 、。定义 拍卖交易机制的分配规则 和支付规则 ：分配机制是指市场参与人在一个拍卖周期中交易的商品数量；支付规则是指在一个拍卖周期中商品交易的单位价格。在 开始时，买方 发布编码块需求信息 和。卖方用户 根据自身拥有的编码块数目、自身的手机电量给出竞拍商品数目 和叫价。假设用户是诚实的，即此时卖方发布的信息有两个前提条件：（）卖方用户参与拍卖的编码包数量不超过其拥有的线性无关编码包数量。（）卖方用户设备的剩余电量足够支持拍卖市场和内容传输交易结束。系统详细参数意义如表 所示。第 期殷 俊，等：基于逆向拍卖的 边缘缓存网络编码内容定价与交易机制表 系统参数符号物理意义用户集合申请编码块的用户（买方）提供编码块的用户（卖方）买方用户的需求编码包数量卖方 提供的线性无关的编码包用户 拥有的线性无关的编码包买方的报价卖方的叫价用户设备手机剩余电量比用户向基站请求一个编码包的费用用户 传输一个编码块的电量成本用户传输一个编码块的保留利润急迫程度因子（，），反映内容请求者获取文件的主观急迫程度。数值越高，表示越急迫。用户数量分布概率，买卖用户之间的通信距离 用户通信最大距离 基于逆向拍卖的编码内容定价和交易机制 买方（内容请求者）报价作为理性的用户，买方为了满足其主观商品需求紧急度，它会给出一个与需求紧急度成正比的报价来快速获取需求内容；当买方周围存在较多的卖方用户时，考虑到商品的供给量大于需求量，理性的买方更愿意给出一个相对较低的价格来支付交易。因此，买方的报价函数可以表示为（）（）式中，为买方需求编码包的主观紧急度，为周围存在若干卖方数量的概率；为用户向基站请求编码块的费用，该值由系统规定；和 为两者的权重值，表示买方对周围邻居数目和编码包需求紧急程度的偏好，且有 。卖方（内容提供者）叫价卖方内容分享意愿受到其设备电量影响，当设备电量变低时，其内容分享意愿也会相应变低，那么理性的卖方会给出较高的商品叫价来减少内容分享频率；商品的传输路径越长，卖方传输内容的成本越高，理性的卖方会给出较高的叫价来弥补传输成本损耗。因此卖方的叫价函数可以表示为（）（）（）式中，为卖方用户设备的电量剩余比；和 为两者的权重值，且有 ；为用户传输一个编码包的保留利润，为了简单起见，该值可由系统自定义；表示用户传输一个大小为 的编码块的成本费用，可以表示为（）式中，表示用户设备通信之间的一个常量系数，不同的通信设备产品具有不同的 值。表示通信距离，表示通信过程信号消减因子，其值满足 。考虑诸多因素，通常随着通信距离的增加，用户通信成本也会急剧增加。交易定价和分配机制 拍卖交易机制通过两个阶段来执行。结合相关假设和定义，下面给出了 机制的具体实施过程。在第一阶段，买方用户首先宣布其商品需求量 和密封报价，随后所有的卖方用户在规定时间内给出商品提供量 和密封叫价。在这个阶段所有卖方用户的叫价采取“升价”的方式进行排序。记所有参与拍卖的卖方用户叫价集合为（，），每个卖家参与投标的编码块数量为 （，）。不失一般性，假设 。为了确定最终的中标卖方用户，需要考虑其提供的编码块数量是否满足买方用户的商品需求量。因此，在这一阶段中计算 。如果 ，那 么 修 改 的 值 为，通 过 计 算 可以得出符合买方用户需求的前 个拍卖卖方用户。在第二阶段中，根据第一阶段得出的符合买方用户需求的前 个拍卖卖方用户信息，给出每个中标卖方用户的分配规则和支付规则。具体的分配规则和支付规则为：当 时，分配规则为 ，支付规则为（）。当 时，分配规则为 ，支付规则为 。此南京邮电大学学报（自然科学版）年时称 为最后一个成功的中标人，为第一个失败的竞标者。拍卖交易的最后将公布每个中标卖方用户的商品分配额及拍卖成交定价。定义 拍卖成功的买方效用函数与其报价和最终的商品成交价有关，效用函数可以表示为两者之差 （）定义 拍卖竞价成功的卖方效用函数与其叫价和最终的商品成交价有关，其效用函数表示为两者之差 （）机制的网络总效用分析在商品交易中，买卖双方的目的往往是冲突的，买方想要以较低的价格获得商品，而卖方的想法恰恰相反。为了解决双方交易的冲突，本文以实现网络总效用（包括买方效用和卖方效用）最大化为目标，设计基于逆向拍卖的定价与分配交易机制。在 中，当网络总效用最大化时达到有效的市场均衡，此时的买方报价和卖方叫价是最优的（所谓最优是指市场中买卖双方都诚实地汇报了自己的报价或叫价价格，并且可获得个人利益最大化）。因此，如果每个交易用户都诚实地报告自己的价格，并且第 个卖方成为最后一个成功的中标人时，网络总效用可表示为，（）（）（）（），（）其中，式（）代表卖方的提供量不能低于买方需求量；式（）表示每个卖方的提供量大于，且不超过每个卖方实际编码块的拥有量；式（）表示每个卖方的设备电量大于；式（）表示买卖双方的通信距离不超过 最大通信范围。一个合理的定价和分配交易方案需要满足拍卖机制中重要的经济特性，即激励相容性、个人理性约束、弱预算平衡和物质平衡特征。这些经济属性保证了拍卖机制的真实性，同时规范了交易拍卖市场的正向运转。下面将通过理论证明分析 拍卖机制的经济属性。机制的经济特性分析 激励相容特征分析激励相容性是指个体在追求个人利益最大化的同时，可以实现整个机制的利益最大化。在本文中，如果每个买方或卖方诚实地汇报自己真实的报价或叫价，其个人效用会达到最大化，进而整个网络总效用达到最大化，即称 拍卖机制满足双边激励相容。命题 机制符合激励相容特征。证明：卖方用户符合激励相容特征。当 为最后一个中标人时，卖方发布真实信息获得的效用函数为 ，且此时的支付规则为（）。因此卖方的效用函数可以简化为 （）。当卖方发布大于其真实信息的报价时，其虚假叫价表示为 （），卖方发布虚假叫价获得的效用函数简化为 （）（）。计算卖方用户 发布真实叫价和虚假叫价时的效用函数差值得出：，由于 ，可知 。因此在拍卖机制中，卖方在报告虚假叫价时的效用低于其报告真实叫价的效用。理性的卖方用户为了追求获取最大个人收益会选择诚实地报告自己真实叫价。买方用户符合激励相容特征。当 是最后一个中标人时，此时的支付规则为 （）。当买方汇报自己真实报价获得的效用函数为：。当汇报虚假价格 （）时，其收益函数表示为 。在买方汇报虚假价格同时，拍卖机制的支付规则变更为 （）。计算买方在两种情况下获得的效用函数差可得出 （），由于 ，得到 ，即买方用户只有在汇报自己真实报价时才可以获得最大的个人收益。由以上证明可知，在 机制中，参与拍卖的用户汇报自己真实价格的效用大于汇报虚假价格的效用，那么理性用户为了谋求最大的个人收益都会选择诚实地汇报自己的真实报价或叫价，因此整个网络的总效用也会达到最大化。个人理性约束特征分析个人理性约束是指用户参与交易获得的效用不第 期殷 俊，等：基于逆向拍卖的 边缘缓存网络编码内容定价与交易机制低于其不参与交易的最大期望效用。在这里，称不参与交易获得的最大期望效用为保留效用，将保留效用标准化为零。若 机制符合个人理性约束特征，即在 机制中任意理性的买方用户满足 ，任意理性的卖方用户满足 。命题 机制符合个人理性约束特征。证明：卖方用户满足个人理性约束。当 是最后一个中标人时，此时的支付规则为 （）。因 此 卖 方 的 效 用 函 数 （）可以简化为 （），由于 ，可知 。可知任意的卖方用户满足个人理性约束特征。买方用户满足个人理性约束。当 是最后一个中标人时，此时的支付规则为 （），买方 用 户 的 效 用 函 数 表 示 为 （）。由于 ，因此 。可知买方用户满足个人理性约束特征。通过上述证明可以得出，在 拍卖交易机制中任意理性的买方或卖方用户通过参与拍卖交易获得不低于保留效用的个人效用。因此，机制可以通过吸引用户参与拍卖交易，保证拍卖市场的持续正向发展。物质平衡及弱预算平衡特征分析在拍卖机制中，弱预算平衡是指用户的支付之和不小于零，即拍卖剩余满足 。物质平衡约束是指拍卖交易中不能出现任何空头交易，避免任何买方在拍卖结束后不能分配得到拍卖商品。命题 机制符合物质平衡和弱预算平衡特征。证明：简化公式 得到（），结 合 式（）和 式（）可 知 。因此，在 机制中任意理性的用户满足弱预算平衡特征。根据 机制的分配规则可知，对于任意的卖方用户 来说，只有当 时，该用户才会成为成功的中标人之一，其分配规则为 ，。当 时，该卖方用户竞标失败，其分配规则为 。上述分析可知，只有成功的中标人卖方才会向买方用户传输大于 数额的商品，这避免了拍卖过程中可能出现的空头交易。因此，机制是满足物质平衡特征的。结合上述特征分析可知，机制满足激励相容性、个体理性约束、弱预算平衡及物质平衡特征。机制通过约束买卖双方的交易行为，实现用户个人利益最大化，从而实现网络总效用最大化。因此可以有效地激励 边缘缓存网络中用户间共享资源。实验分析在这一节中，使用数值实验来模拟拍卖轮次、用户设备电量和用户密度对本机制的影响，并将实验结果与 机制、第一报价和第二报价机制结果进行对比分析。通过在校园地图上部署仿真程序来对所提拍卖交易机制进行实验验证，如图 所示，实验网络内 用户节点有两种类型，一种是行人节点，可以在道路上和建筑区域无障碍移动，另一种是自行车辆节点，只能在道路上移动。不同类型的节点会在各自的移动区域内遵循各自的移动准则。小基站节点均匀地部署在地图中，其覆盖范围的半径为 ，小基站在地图范围内全覆盖并独立分布，数量置为，用户设备间 通信最大范围是 。在每个拍卖轮次，本文按照节点数量的来设定拍卖请求者的数量，其他主要仿真参数如表 所示。图 校园地图模拟实验第 时的运行状态南京邮电大学学报（自然科学版）年表 仿真实验参数表符号取值网络规模（）用户设备数量 行人节点占比行人节点速度（）自行车节点速度（）文件块总数量（初始电量 每节点）初始代币 每节点，网络效用对比实验如图 所示，当、和 分别取值为 时，系统总效用值受到变量取值影响处于均衡水平。当 和、和 取值比为 时，网络总效用达到最大值。当 和、和 取值比为 时，网络总效用数值达到最小。因此，为了不受参数取值的影响，本实验中、和 分别取值为。图 变量取值对网络总效用的影响如图 所示，机制的网络总效用优于其他对比机制。在第一报价和第二报价机制中，尽管商品的交易价格较低，但每轮拍卖只能促成单个买卖方进行交易。这对于需求量大的买方来说，并不是最优的拍卖机制，因此其网络总效用相对较低。而在 机制中，由于买方用户需要进行延迟和资源条件的筛选，买方可能需要花费较高的费用从基站处获取资源。在移动用户的协助下，机制可以以较低的费用从邻居用户处通过 链路获取同样的资源。图 网络总效用对比 用户设备电量的影响如图 所 示，随 着 用 户 设 备 电 量 的 减 小，机制的网络总效用在逐渐变低。这是由于卖方分享意愿受到其设备电量剩余比变低的影响，商品叫价会相应地逐渐变高。因此，买方需要以较高的价格获取相对较少的编码块。更严重的是，急迫需要编码块的用户需要花费更高昂的费用从小基站处获取资源。图 电量对网络总效用的影响 用户密度的影响图 表明，随着用户密度的增大，第一报价机制、第二报价机制、机制和 机制的网络总效用数值都在提高。随着用户密度的提高，买方周围具有缓存内容的卖家变多，此时商品供大于求，买方可以较低的价格获取到需求编码块，从而使得 机制网络总效用提高更快。而在 机制中，尽管随着用户密度的提高，候选集合中可选择的卖方变多，使得匹配定价时买卖双方的交易概率变高，但仍然会面临匹配不成功时买方需要花费更高昂的费用从基站处获取内容。第 期殷 俊，等：基于逆向拍卖的 边缘缓存网络编码内容定价与交易机制图 用户密度对网络总效用的影响 用户参与率影响如图 所示，用户参与率是影响网络的总效用因素之一。图中显示随着参与率的提高，各个机制的网络总效用均在提高。随着用户参与意愿度的提高，参与拍卖交易的卖方用户数量增多，买方用户能够以较低的价格快速地获取到完整需求。在第一报价机制和第二报价机制中，尽管拍卖成交的价格相对较低，但是受到交易人数的限制，卖方可提供的交易商品量较低，整个网络的总效用也相应较低。受到资源和延迟条件的选择及匹配定价限制，机制网络总效用相对较低，但随着用户参与率的提高，机制中通过 交易的用户数量变多，其效用也随之提升。图 用户参与率对网络总效用的影响 结束语本文将 边缘缓存网络中用户间内容分享过程建模为一个逆向拍卖市场，并提出符合双边激励相容、个人理性约束、弱预算平衡及物质平衡等特征的拍卖定价与分配机制，仿真实验亦验证了该机制的有效性。下一步的研究是进一步拓展 机制，验证其在区块链等新型代币支付场景下智能合约、共识机制等对 机制的影响。参考文献：，（）：，（）：蔡艳，吴凡，陆音，等 协作的边缘缓存系统能耗分析 南京邮电大学学报（自然科学版），（）：，（），（）：（）岳雯雁，赵夙，朱琦 网络中 视频文件的缓存策略 南京邮电大学学报（自然科学版），（）：，（），（）：（），（）：，（）：，（）：，（）：，南京邮电大学学报（自然科学版）年，（）：，（）：刘浩，陈志刚，张连明 移动社交网络中基于拍卖模型的数 据 转 发 激 励 机 制 通 信 学 报，（）：，（）：（），（）：，（）：，：，（）：，：，（）：，（）：，（）：孙利民 无线传感器网络 北京：清华大学出版社，：（责任编辑：李小溪）第 期殷 俊，等：基于逆向拍卖的 边缘缓存网络编码内容定价与交易机制