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

针对智能电视操作系统中在线分配资源时第三方应用程序虚报效用获取资源的问题,提出一种采用组合拍卖策略的多资源分配机制(CARA)及其竞胜标求解算法。首先,将系统资源表征为离散资源配置选项,以资源组为单位投标,用暗标第二价格组合拍卖策略进行拍卖;然后,将组合拍卖竞胜标问题转化为多维多选择背包问题,提出一种竞胜标求解算法,在投标集中用贪心法搜索最优投标,并利用共享型资源增加时边际效用递减的特征缩小搜索空间,降低算法复杂度。仿真实验表明,CARA的竞胜标问题求解算法在求得相同解的前提下,比M-HEU算法的时间复杂度低约40%,更适于在线多资源分配。     

一种基于多标拍卖的资源分配算法

针对有限资源开放式系统多任务多资源分配问题,提出了一种基于多标拍卖的资源分配算法. 算法首先基于资源效用曲线为每个任务建立投标集合. 其次,任务向系统递交投标,系统收集所有任务投标并定义市场出清价, 确定资源分配的规则. 最后算法通过启发式方法调整每个任务的最大投标值,以获得接近最优的系统总效用. 实验结果表明算法在资源有限的情况下优先分配资源给投标价格高的任务,与0-1整数规划资源分配算法相比时间复杂度低,最优值偏差不大.      

基于用户行为模型的TVOS资源分配算法

现有的智能电视操作系统(TVOS)资源分配多依赖于操作系统本身对任务的资源分配方案,而系统对任务的调度是尽力而为(best-effort)的,以最大化系统的吞吐量为目的,这种资源调度分配方案在实时或多媒体应用系统存在不能保障应用的服务质量(QoS).为此,在研究TVOS用户行为模型的基础上,量化了用户对应用的偏好,并结合应用QoS模型提出了两种资源分配算法RA_DP和RA_PLSH.实验结果表明,基于动态规划的RA_DP算法能够求出问题的最优解,可作为算法间比较的参考,但算法时间复杂度很高;基于资源定价的局部搜索启发式RA_PLSH算法可在短时间内求出问题的近似最优解,与其他启发式算法相比更适合于智能电视资源的实时分配.     

采用定价机制的多媒体系统多资源分配算法

针对多媒体系统多资源分配问题,提出了一种基于定价机制的多资源分配算法.假设资消耗函数是凸函数,从而推导出资源分配问题是凸规划问题,可以通过拉格朗日对偶分解理论求解,确定资源的价格并得到最优的资源分配.对于单资源分配问题,使用多标拍卖算法确定最优的资源分配.仿真实验结果表明:对于单资源分配问题,当任务的投标数大于15时,系统总的服务质量水平达到近似最优;对于多资源分配问题,基于定价机制的多资源分配算法性能优于现有算法,且算法复杂度更低.     

基于贪心算法的离散单位圆盘覆盖问题研究

提出了一种基于贪心启发式的计算方法,可以在多项式时间复杂度内获得DUDC问题的近似最优解.首先生成了可替代二维平面的离散单元格,在每一单元格中心建立能够覆盖一定数量目标点的替代集,使用贪心算法确定替代集的最小组合方式,实现了对目标点的全覆盖.基于每个子集内所包含的点的具体位置,计算了其最小覆盖圆.最小覆盖圆的中心视为选址位置.基于具体案例证明了算法的有效性.讨论了该算法的影响因素,分析了时间复杂度以及近似度比率.     

无线传感器网络中覆盖度和连通度问题的研究

对无线传感器网络中的覆盖度和连通度问题进行了研究。传统的求解覆盖度和连通度问题的整数规划算 法对于大型的无线传感器网络,其整数规划算法的求解时间复杂度过高,导致算法效率偏低,CCP-WSN通过对的 研究,提出了一种新型的求解CCP-WSN的盲覆盖区增强算法,该算法采用启发式的策略,大大降低了求解的时间 复杂度,并且能够求出网络的近似最优解,非常适合于分布式应用。     

无线传感器网络中覆盖度和连通度问题的研究

对无线传感器网络中的覆盖度和连通度问题进行了研究。传统的求解覆盖度和连通度问题的整数规划算法对于大型的无线传感器网络，其整数规划算法的求解时间复杂度过高，导致算法效率偏低，通过对CCP—WSN的研究，提出了一种新型的求解CCP-WSN的盲覆盖区增强算法，该算法采用启发式的策略，大大降低了求解的时间复杂度，并且能够求出网络的近似最优解，非常适合于分布式应用。     

决策表最优特征子集的选择--基于粗集理论的启发式算法

特征子集选择问题是机器学习的重要问题。而最优特征子集的选择是NP困难问题,因此需要启发式搜索指导求解。基于粗集理论,本文提出了一种新的决策表最优特征子集选择的启发式算法。和以往的方法相比,这种算法简单实用,在一定条件下能够以较高的效率得到最优特征子集。     

基于离散灰狼算法的资源分配问题求解

针对标准灰狼优化算法(GWO)只适合求解连续优化问题,无法直接求解离散域上的资源分配问题,提出一种基于马太效应的离散灰狼优化算法(DGWO)来求解资源分配问题.首先,根据数学映射思想给出一种将连续空间转化为离散空间、实数变换为整数的编码转换方法;然后,对其中的不可行解采用基于马太效应的修复与优化方法处理;最后,将DGWO计算结果与遗传算法结果进行对比发现不论是收敛速度,还是求解质量,DGWO算法均优于遗传算法.实验结果表明了DGWO算法求解资源分配问题的可行性、正确性和优越性.     

正交频分多址接入系统中接收能耗优化的二维时频资源分配算法

正交频分多址接入系统资源分配的结果会直接影响资源分配效率以及各个接收站点的能耗.系统中的多用户系统资源分配问题在一定的标准(例如IEEE 802.16标准)约束下可证明为一个NP完全问题.以IEEE802.16标准为例,由一定的分配准则定义的一种启发式算法(能耗优化的低边数分配算法)可以对资源分配问题进行近似求解.仿真结果表明,和文献中典型的启发式算法相比,该算法可以获得较高的资源分配效率以及较低的接收站点能耗.