CARA:一种采用组合拍卖的智能电视终端多资源分配机制  

CARA:A Multi-Resource Allocation Mechanism for Smart TV System Based on Combinatorial Auction

作　　者：徐超[1,2] 曾学文[1] 郭志川[1] 

机构地区：[1]中国科学院声学研究所国家网络新媒体工程技术研究中心,北京100190 [2]中国科学院大学,北京100049

出　　处：《西安交通大学学报》2013年第10期25-30,共6页Journal of Xi'an Jiaotong University

基　　金：国家"863计划"资助项目(2011AA01A102);中国科学院战略性先导科技专项子课题(XDA06010302);中国科学院声学所所长择优项目(Y154221601)

摘　　要：针对智能电视操作系统中在线分配资源时第三方应用程序虚报效用获取资源的问题,提出一种采用组合拍卖策略的多资源分配机制(CARA)及其竞胜标求解算法。首先,将系统资源表征为离散资源配置选项,以资源组为单位投标,用暗标第二价格组合拍卖策略进行拍卖;然后,将组合拍卖竞胜标问题转化为多维多选择背包问题,提出一种竞胜标求解算法,在投标集中用贪心法搜索最优投标,并利用共享型资源增加时边际效用递减的特征缩小搜索空间,降低算法复杂度。仿真实验表明,CARA的竞胜标问题求解算法在求得相同解的前提下,比M-HEU算法的时间复杂度低约40%,更适于在线多资源分配。A combinatorial auction based multi-resource allocation （CARA） mechanism and a solution approach of its winner determination problem are proposed to solve the problem that excessive resources are consumed by application＇s utility misreport in the online resource allocation in smart television operating system.Firstly,the resource requirements are expressed as discrete resource options,and the combinatorial auction for resource groups based on secondprice sealed-bid is held.Then the winner determination problem of the combinatorial auction is converted to a multidimensional multiple-choice knapsack problem,and a new solution algorithm with lower time complicity is presented.The greedy method is used to search the optimal bid in the bid set,and the characteristic of diminishing marginal utility is used to reduce the search space when the shared resources are increased.Simulation results show that the solution algorithm of CARA＇s winner determination problem gets the same solution as the M-HEU algorithm but with the time complexity about 40％ less than the latter,and hence it is more applicable for online multi-resource allocation.

关 键 词：智能电视 多资源分配机制 组合拍卖 效用 

分 类 号：TP316[自动化与计算机技术—计算机软件与理论]