Microsoft Word CX2.doc

Transcription

1 第 37 卷 第 4 期 通 信 学 报 Vol.37 No 年 4 月 Journal on Communications April 2016 doi: /j.issn x 基 于 可 信 拍 卖 机 制 的 视 频 移 植 定 价 策 略 丛 鑫, 訾 玲 玲, 孙 劲 光 ( 辽 宁 工 程 技 术 大 学 电 子 与 信 息 工 程 学 院, 辽 宁 葫 芦 岛 ) 摘 要 : 提 出 基 于 可 信 拍 卖 机 制 的 视 频 移 植 定 价 策 略 LBAS, 降 低 视 频 服 务 的 单 位 成 本 首 先, 依 据 市 场 经 济 价 格 规 律, 由 视 频 提 供 商 以 未 来 视 频 请 求 为 自 变 量 制 定 视 频 类 的 服 务 价 格, 有 利 于 降 低 视 频 提 供 商 费 用 支 出 ; 其 次, 设 计 了 距 离 函 数, 衡 量 视 频 服 务 单 位 成 本, 计 算 云 提 供 商 给 出 的 价 格 和 视 频 提 供 商 预 期 价 格 之 间 的 差 距, 确 定 能 赢 得 竞 拍 的 云 提 供 商 ; 再 次, 以 云 提 供 商 预 期 收 益 为 基 准, 提 出 可 替 换 视 频 集 的 视 频 分 配 算 法, 提 升 云 提 供 商 的 满 意 度 和 降 低 视 频 提 供 商 的 费 用 ; 最 后, 改 进 联 盟 抑 制 算 法 AEM, 使 其 适 应 低 价 格 拍 卖 机 制 并 加 入 了 视 频 数 量 检 测 机 制, 能 避 免 由 于 竞 拍 者 联 合 而 使 视 频 提 供 商 利 益 受 损 与 当 前 最 新 的 移 植 方 案 VMC 相 比, 实 验 结 果 表 明 LBAS 能 进 一 步 降 低 约 10% 的 费 用 关 键 词 : 可 信 拍 卖 ; 视 频 移 植 ; 定 价 策 略 中 图 分 类 号 :TP393 文 献 标 识 码 :A Pricing strategy for video migration based on truthful auction mechanism CONG Xin, ZI Ling-ling, SUN Jin-guang (School of Electronic and Information Engineering, Liaoning Technical University, Huludao , China) Abstract: In order to decrease the unit costs of video service, a pricing strategy LBAS for video migration based on truthful auction mechanism was proposed. Firstly, according to the principles of maret economy prices, service prices using the future video demand as independent variable were laid down by the VoD provider, so as to decrease the costs of the VoD provider. Secondly, a distance function was designed to measure the unit costs of video service. The proposed function computes the distance between the costs providing by cloud providers and expected prices offering by the VoD provider, and the obtained distance was used to determine who can win the auction. Thirdly, a replaceable video allocation algorithm based on the benefits of cloud providers was presented. The proposed algorithm increases the satisfaction of cloud providers and decreases the costs of the VoD provider. Finally, the AEM algorithm was improved through establishing the detection mechanism of video number, so as to adapt to the low-bid auction. The improved algorithm avoids the collusion among bidders and assurances the benefits of the VoD provider. The experiment results demonstrate that LBAS can decrease 10% of the costs compared to the VMC strategy. Key words: truthful auction, video migration, pricing strategy 收 稿 日 期 : ; 修 回 日 期 : 通 信 作 者 : 訾 玲 玲,lingling @126.com 基 金 项 目 : 国 家 科 技 支 撑 计 划 : 矿 业 组 合 服 务 支 撑 平 台 研 究 开 发 基 金 资 助 项 目 (No.2013BAH12F02); 辽 宁 工 程 技 术 大 学 博 士 启 动 基 金 资 助 项 目 (No , No ); 辽 宁 省 教 育 厅 科 学 研 究 一 般 基 金 资 助 项 目 (No.L ) Foundation Items: The National Key Technology Research and Development Program of the Ministry of Science and Technology of China:The Research on Platform of Mineral Service Composition (No.2013BAH12F02), The Ph.D Start-up Fund of Natural Science Foundation of LNTU(No , No ), The Foundation of Liaoning Education Committee (No.L )

2 54 通 信 学 报 第 37 卷 1 引 言 使 用 视 频 服 务 提 供 商 提 供 的 视 频 点 播 服 务 (VoD, video-on-demand) 在 线 观 看 视 频 已 成 为 当 前 人 们 流 行 的 娱 乐 方 式 之 一 随 着 用 户 数 量 的 增 加, 提 供 质 量 较 好 的 视 频 服 务 所 需 的 带 宽 也 日 益 增 大, 导 致 视 频 服 务 提 供 商 必 须 面 对 2 个 不 可 回 避 的 问 题 :1) 带 宽 费 用 占 视 频 服 务 商 每 个 月 费 用 支 出 比 重 达 到 一 半 以 上 [1] ;2) 一 天 之 中 大 部 分 时 间 带 宽 的 利 用 率 都 是 低 于 20% [2] 上 述 问 题 产 生 的 根 本 原 因 是 用 户 观 看 视 频 的 行 为 在 时 间 上 的 不 平 衡 性, 亦 即 一 天 之 中, 同 时 观 看 视 频 的 用 户 数 量 在 21:00 达 到 峰 值, 在 7:00 达 到 谷 值 [3], 这 就 使 视 频 服 务 提 供 商 必 须 申 请 大 量 的 带 宽 来 满 足 峰 值 时 用 户 流 畅 地 观 看 视 频 的 需 求, 而 这 大 量 的 带 宽 在 谷 值 是 不 可 能 被 用 到 的 在 现 有 的 ISP 运 营 模 式 下, 高 带 宽 费 用 支 出 和 低 带 宽 利 用 率 是 无 法 避 免 亦 是 无 法 解 决 的 矛 盾 P2P 技 术 为 缓 和 上 述 矛 盾 做 出 了 一 定 的 贡 献, 但 受 限 于 网 络 中 节 点 ( 用 户 ) 的 自 私 性 [4], 即 便 在 有 激 励 机 制 存 在 的 P2P 文 件 网 络 中, 服 务 器 完 全 不 参 与 数 据 的 分 发 和 传 输 过 程 也 是 不 可 能 的 事 情 [5,6], 更 无 论 VoD 这 种 每 个 节 点 都 需 要 一 定 下 载 速 率 来 保 证 视 频 能 平 滑 播 放, 激 励 机 制 又 不 能 对 网 络 系 统 太 严 格 系 统 近 年 来, 出 现 的 云 计 算 技 术 为 此 矛 盾 的 解 决 提 供 了 一 种 方 法 通 过 预 测 技 术 提 前 获 知 未 来 一 段 时 间 的 视 频 访 问 量 [7], 将 高 访 问 量 的 视 频 提 前 放 置 到 云 平 台 上, 在 访 问 高 峰 时 使 云 平 台 成 为 辅 助 的 视 频 服 务 器, 参 与 数 据 推 送 和 请 求 应 答, 降 低 本 地 视 频 服 务 器 的 负 载, 在 访 问 低 谷 时 释 放 占 用 的 云 平 台 资 源, 节 省 费 用 这 种 思 想 和 云 平 台 提 供 的 即 付 即 用 [8] 方 式 完 全 吻 合 采 用 云 平 台 作 为 辅 助 的 视 频 服 务 器 可 以 避 免 增 量 部 署 额 外 的 设 备 来 满 足 日 益 增 加 的 用 户 需 求, 同 时 也 减 少 了 设 备 运 行 开 销 [9] 和 维 护 所 带 来 的 人 工 开 销 VMC 算 法 在 对 Hulu 和 PPlive 真 实 数 据 分 析 ( 包 括 视 频 文 件 播 放 时 间 视 频 文 件 大 小 用 户 观 看 视 频 规 律 同 时 在 线 用 户 数 视 频 流 行 度 分 布 视 频 数 等 ) 的 基 础 上 重 点 关 注 视 频 移 植 过 程 中 的 费 用 开 销, 采 用 智 能 移 植 策 略, 即 在 一 天 内 只 移 植 一 次, 替 换 流 行 度 低 的 视 频, 保 证 云 平 台 上 的 视 频 都 是 最 受 欢 迎 的 相 比 于 当 前 以 P2P 技 术 为 核 心 的 VoD 视 频 服 务 方 案, 能 够 节 省 [10] 视 频 服 务 提 供 商 30% 的 运 营 费 用 OPT-ORS 方 案 设 计 了 Lyapunov 优 化 框 架, 依 据 用 户 请 求 数 来 计 算 需 要 云 平 台 预 留 的 资 源 数, 使 服 务 费 用 支 出 和 用 户 的 满 意 度 之 间 达 到 较 好 的 平 衡 性 该 方 案 以 Amazon 的 价 格 体 系 为 基 础, 与 在 营 的 VoD 视 频 服 务 方 案 在 费 用 和 请 求 服 务 时 间 2 个 方 面 进 行 了 比 较, 取 得 了 较 大 的 优 势 当 前 云 提 供 商, 如 Amazon, 利 用 固 定 的 价 格 模 型 收 取 服 务 费 用 按 需 实 例 [11], 允 许 用 户 以 小 时 为 周 期 支 付 固 定 的 费 用 ; 保 留 实 例 [11], 允 许 用 户 每 小 时 的 使 用 费 用 都 有 一 定 的 折 扣 价 格 这 种 价 格 模 型 不 能 反 映 用 户 请 求 的 变 化 趋 势, 也 不 能 时 刻 提 供 充 足 的 资 源, 导 致 了 价 格 敏 感 型 用 户 的 流 失 因 此 本 文 提 出 新 的 价 格 机 制, 以 进 一 步 降 低 视 频 服 务 提 供 商 的 费 用 支 出 考 虑 如 下 情 形 : 当 越 来 越 多 的 云 平 台 建 立 之 后, 由 于 基 础 设 施 规 模 和 架 构 的 不 同, 所 提 供 的 服 务 质 量 是 有 差 别 的, 所 收 取 的 服 务 费 用 亦 是 有 高 低 之 分 的 ; 当 视 频 服 务 提 供 商 的 规 模 极 大 时, 云 平 台 的 带 宽 大 小 可 能 成 为 提 升 视 频 服 务 质 量 的 瓶 颈 ; 当 云 平 台 发 生 灾 难 短 时 不 能 恢 复 时, 视 频 服 务 的 中 断 对 用 户 的 观 看 体 验 的 影 响 是 巨 大 的 因 此 租 用 多 个 云 平 台 取 代 租 用 单 个 云 平 台 作 为 辅 助 服 务 器 会 是 更 好 的 选 择 不 失 一 般 性, 假 设 云 辅 助 VoD 系 统 是 由 一 个 本 地 视 频 服 务 器 系 统 和 多 个 云 平 台 组 成, 节 点 以 P2P 方 式 相 结 合 互 换 部 分 数 据 并 向 本 地 视 频 服 务 器 或 云 平 台 发 送 连 接 应 答 请 求 和 使 用 数 据 推 送 服 务 在 此 种 情 形 下 新 的 价 格 机 制 也 能 很 容 易 地 扩 展 到 有 多 个 视 频 服 务 提 供 商 和 多 个 云 平 台 提 供 商 所 组 成 的 视 频 点 播 服 务 系 统 提 出 的 新 价 格 机 制 ( 命 名 为 LBAS) 以 拍 卖 机 制 为 基 础, 首 先, 建 立 了 符 合 市 场 经 济 模 型 的 视 频 集 定 价 算 法, 以 降 低 视 频 服 务 的 单 位 价 格, 定 价 算 法 保 证 了 视 频 服 务 提 供 商 能 以 视 频 的 请 求 数 为 基 准 将 视 频 集 打 包 并 得 到 合 理 的 定 价 ; 其 次, 构 建 新 的 基 于 低 价 格 的 拍 卖 模 型, 此 模 型 的 主 要 实 体 是 视 频 提 供 商 和 云 平 台 提 供 商, 竞 拍 的 物 品 时 视 频 集, 其 中, 视 频 提 供 商 是 货 物 的 销 售 方, 云 平 台 提 供 商 是 货 物 的 购 买 方, 采 用 最 低 价 格 竞 标 的 方 法 将 视 频 集 分 配 到 云 平 台 上 ; 再 次, 建 立 可 替 换 竞 拍 物 品 ( 视 频 集 ) 的 视 频 集 分 配 方 法, 这 是 本 文 拍 卖 算 法 的 独 特 之 处, 以 预 期 收 益 为 目 标, 将 不 同 收 益 的 视 频 集 进 行 组 合, 从 而 满 足 竞 拍 者 需 求, 降 低 货 物 的 剩 余 率 ; 最 后, 为 了 避 免 云 平 台 提 供 商 之 间 的 联 盟 对 拍 卖 过 程 造 成 的 负 面

3 第 4 期 丛 鑫 等 : 基 于 可 信 拍 卖 机 制 的 视 频 移 植 定 价 策 略 55 影 响, 引 入 并 改 进 了 AEM 算 法, 使 拍 卖 过 程 达 到 t 诚 信 在 构 建 了 模 拟 实 验 架 构 后, 对 提 出 的 价 格 机 制 进 行 了 详 细 的 评 估, 实 验 结 果 显 示 相 比 于 VMC 算 法, 提 出 的 机 制 能 够 进 一 步 降 低 视 频 服 务 提 供 商 10% 的 费 用 支 出 2 拍 卖 机 制 运 行 场 景 模 型 假 设 存 在 一 个 大 规 模 的 视 频 点 播 服 务 提 供 商 ( 视 频 提 供 商 ) 和 多 个 商 业 化 运 行 的 云 平 台 服 务 提 供 商 ( 云 提 供 商 ), 视 频 提 供 商 租 用 云 平 台 资 源 并 辅 以 本 地 视 频 点 播 服 务 器 提 供 视 频 点 播 服 务, 同 时 向 云 提 供 商 支 付 费 用 云 提 供 商 利 用 云 平 台 提 供 视 频 点 播 服 务 所 需 的 各 类 资 源 ( 如 视 频 文 件 存 储 服 务 器 视 频 数 据 分 发 服 务 器 用 户 请 求 应 答 服 务 器 等 ), 并 向 视 频 提 供 商 收 取 费 用 以 获 得 预 期 的 收 益 这 个 假 设 的 合 理 性 在 于 以 下 2 方 面 1) 对 于 视 频 点 播 服 务 所 需 的 一 个 重 要 的 资 源 即 带 宽, 不 同 于 存 储 能 力 和 计 算 能 力, 可 以 通 过 增 加 部 署 新 的 服 务 器 来 实 现, 带 宽 能 力 需 要 经 过 向 诸 如 ISP 申 请 才 能 得 到 提 升 云 平 台 的 带 宽 能 力 是 否 是 无 限 的, 是 视 频 点 播 服 务 架 构 设 计 时 需 要 考 虑 的 问 题 2) 已 有 的 案 例 表 明, 云 平 台 会 发 生 灾 难 事 件 从 而 导 致 在 云 上 运 行 的 服 务 发 生 中 断 如 2012 年 Amazon 云 平 台 的 服 务 中 断 导 致 Netflix 视 频 服 务 中 断 云 平 台 偶 发 的 灾 难 导 致 服 务 中 断 亦 是 架 构 设 计 时 需 要 考 虑 的 问 题 在 上 述 实 际 场 景 成 立 的 情 况 下, 设 计 如 下 虚 拟 场 景 以 利 于 拍 卖 算 法 的 运 行 视 频 提 供 商 拥 有 视 频 资 源, 将 作 为 拍 卖 资 源 的 提 供 者, 云 提 供 商 竞 争 拍 卖 资 源 并 提 供 服 务, 将 作 为 竞 拍 者, 即 视 频 提 供 商 收 取 资 源 拍 卖 的 费 用, 云 提 供 商 支 付 资 源 拍 卖 的 费 用 需 要 注 意 的 是, 实 际 的 情 况 是 视 频 提 供 商 支 付 费 用 而 云 提 供 商 收 取 费 用 [12] 视 频 按 照 未 来 一 段 时 间 的 用 户 请 求 数 进 行 分 类, 视 频 类 即 为 拍 卖 的 货 物 云 提 供 商 依 据 预 期 收 益 值 来 出 价 以 竞 拍 货 物, 而 后 视 频 提 供 商 将 云 提 供 商 竞 拍 得 到 的 视 频 类 移 植 到 云 平 台 上, 由 云 平 台 提 供 视 频 点 播 服 务 如 果 视 频 提 供 商 有 新 上 映 的 视 频, 则 重 复 拍 卖 过 程, 进 行 增 量 拍 卖 为 了 描 述 拍 卖 过 程, 设 定 参 数 如 下 视 频 提 供 商 将 视 频 按 照 某 种 原 则 进 行 分 类, 分 类 数 目 为 n 分 类 原 则 可 以 是 未 来 一 段 时 间 用 户 请 求 数, 如 未 来 一 天 内 低 用 户 请 求 数 的 视 频 为 一 类, 高 用 户 请 求 数 为 一 类, 或 者 视 频 服 务 单 位 带 宽 价 格, 如 服 务 高 用 户 请 求 数 的 视 频 所 需 的 单 位 带 宽 价 格 应 低, 服 务 低 用 户 请 求 数 视 频 所 需 相 反 每 个 视 频 类 内 的 视 频 为 有 限 的 数 目, 其 值 为 r i, R= r1, r2,, r n 服 务 可 形 成 拍 卖 的 视 频 集 矩 阵 为 [ ] 第 i 类 视 频 所 需 资 源 的 单 位 价 格 为 pvi, 可 形 成 服 务 价 格 集 矩 阵 pv = [ pv1, pv2,, pvn ] 视 频 提 供 商 希 望 云 提 供 商 能 以 等 于 或 低 于 pv i 的 价 格 购 买 视 频 i 云 提 供 商 购 买 的 视 频 集 可 表 达 为 S = {0,1,, r} {0,1,, r} {0,1,, } 1 2 云 提 供 商 参 与 拍 卖 的 云 提 供 商 数 目 为 m, 第 1 2 n 个 云 提 供 商 预 期 收 益 为 b, S = { r, r,, r } r n 是 为 了 实 现 b 而 希 望 竞 拍 成 功 的 视 频 集 矩 阵 r i 是 购 买 i 的 数 量 当 购 买 的 视 频 单 位 价 格 集 矩 阵 1 2 n 为 = { p, p,, p } P 时, b n i i = p i 1 r = 视 频 的 估 值 竞 拍 者 购 买 S 希 望 支 付 的 价 格 下 限 M, 当 最 后 的 价 格 低 于 此 值 时, 服 务 S 没 有 任 何 收 益, 还 可 能 有 所 损 失 也 可 以 通 过 非 诚 信 出 价 来 获 得 更 好 的 排 名 位 置, 如 给 出 低 于 M 的 价 格 n i i m 表 示 对 i 的 最 小 出 价, M = m r 按 照 i i= 1 拍 卖 原 则, 仅 仅 当 竞 拍 者 所 希 望 得 到 的 视 频 集 中 的 每 个 视 频 数 都 满 足, 才 支 付 M, 否 则 支 付 0 [13] ; M 仅 被 所 知, 且 独 立 于 其 他 竞 拍 者 的 出 价 [14] 视 频 的 支 付 T 代 表 需 要 支 付 视 频 集 的 实 际 价 格 T 是 拍 卖 者 的 总 收 入, T 3 拍 卖 算 法 3.1 视 频 定 价 算 法 m = T = 1 从 视 频 提 供 商 角 度 建 立 视 频 定 价 方 案, 以 降 低 本 地 服 务 器 费 用 支 出 在 现 行 带 宽 收 费 模 式 下, 视 频 提 供 商 支 付 给 ISP 的 每 单 位 视 频 服 务 费 用 是 固 定 的, 以 pv 标 记, 是 1 n 的 矩 阵, 矩 阵 中 每 个 元 素 都 有 相 同 的 数 值 将 每 类 视 频 的 平 均 用 户 请 求 数 d i 按 照 降 序 排 列, 可 以 得 每 类 视 频 用 户 请 求 数 集, 定 义 为 矩 阵 D = d1, d2,, d n 建 立 视 频 价 格 方 案, 满 足 以 下 条 件 :1) 相 比 于 现 行 的 视 频 服 务, 视 频 提 供 商 所 支 付 的 费 用 要 更 低 ;2) 云 提 供 商 必 须 有 收 益 视 频 定 价 算 法 的 设 计 满 足 条 件 1), 在 下 文 中 详 细 说 明 如 何 满 足 条 件 2)

4 56 通 信 学 报 第 37 卷 建 立 D 和 pv 之 间 的 关 系 pv = f( D ) (1) 满 足 用 户 请 求 所 需 支 付 的 资 源 数 和 价 格 之 间 要 满 足 经 济 学 法 则, 即 消 费 者 购 买 的 物 品 单 价 越 低, 其 销 售 量 越 高 ; 单 价 越 高, 销 售 量 会 降 低 因 此,f 是 减 函 数, 随 D 的 增 加,pv 降 低 利 用 pc 表 明 服 务 每 类 视 频 的 开 销, pc= [ pc1, pc2,, pcn ],pc i 是 服 务 i 的 单 位 费 用 开 销, 表 明 云 提 供 商 服 务 视 频 的 开 销 为 了 降 低 视 频 提 供 商 的 费 用 开 销,pv 满 足 T T pv D pv D (2) ( ) ( ) ( pv ) pv pc d pv pc d pc d n n n (3) 式 (2) 能 保 证 条 件 1) 得 到 满 足 构 建 式 (3) 的 原 因 在 于 : 为 了 使 高 请 求 数 的 视 频 被 云 提 供 商 选 择, 服 务 此 类 视 频 的 收 益 要 大 于 服 务 低 请 求 数 的 视 频 类 式 (3) 有 可 能 造 成 低 请 求 数 视 频 不 被 云 提 供 商 选 择, 但 此 类 视 频 完 全 可 以 由 视 频 提 供 商 服 务 器 应 答, 因 服 务 其 所 需 的 资 源 很 少 3.2 低 价 格 赢 标 的 视 频 分 配 算 法 已 有 的 多 单 位 联 合 拍 卖 优 化 算 法 的 复 杂 度 较 高 [15,16], 因 此 设 计 了 基 于 低 价 格 赢 标 的 视 频 分 配 算 法 视 频 提 供 商 按 给 定 原 则 将 视 频 聚 类 成 视 频 集, 形 成 D R 和 pv, 将 这 3 个 值 分 别 发 送 给 参 与 竞 拍 的 云 提 供 商 云 提 供 商 依 据 自 己 的 服 务 成 本 和 预 期 收 益 评 估 服 务 每 类 视 频 所 需 的 单 位 成 本, 形 成 P S 云 提 供 商 发 送 S 和 总 竞 拍 价 格 到 视 频 提 供 商 总 竞 拍 价 格 定 义 为 C, M C b 此 处 保 证 第 3.1 节 中 条 件 2) 成 立 由 于 云 提 供 商 为 不 同 类 型 视 频 集 提 供 视 频 点 播 服 务 需 要 占 用 不 同 的 资 源, 如 带 宽 内 存 等, 需 要 设 置 实 例 权 重 用 以 区 分 资 源 占 用 的 程 度 视 频 集 + 中 的 第 i 类 视 频 的 权 重 标 记 为 w R 定 义 距 离 参 数 dis, 表 明 哪 些 云 提 供 商 能 够 赢 得 拍 卖 dis pv S C = T n i wr i= 1 i i (4) dis 为 不 同 云 提 供 商 给 出 的 价 格 与 视 频 提 供 商 价 格 的 差 值, 即 服 务 视 频 的 平 均 价 格 差 值 此 值 小 于 0 时, 说 明 视 频 提 供 商 需 要 向 云 提 供 商 支 付 高 于 其 预 期 的 费 用 ; 此 值 大 于 0 时, 说 明 视 频 提 供 商 向 云 提 供 商 支 付 费 用 低 于 预 期, 对 于 视 频 提 供 商 来 讲, 这 是 有 益 的 事 情 为 了 将 视 频 集 尽 可 能 地 分 配 到 云 提 供 商, 设 计 了 基 于 迭 代 的 视 频 集 分 配 算 法, 如 算 法 1 例 1 说 明 算 法 1 是 诚 信 的 视 频 提 供 商 有 4 种 视 频 集, 标 记 为 {v 1,v 2,v 3,v 4 }, 每 种 视 频 的 数 量 为 {1,2,5,3} 3 个 云 提 供 商, 标 记 为 {c 1,c 2,c 3 }, 竞 拍 这 些 视 频 假 设 视 频 类 权 重 为 w i ={0.5,1.0,1.5,2.0} c 1 以 总 价 格 6 竞 拍 {1v 1,1v 2, 1v 3 },c 2 以 总 价 格 10 竞 拍 {1v 2,3v 3 },c 3 以 总 价 格 20 竞 拍 {2v 3,3v 4 } 经 过 算 法 1 的 计 算, 服 务 视 频 的 平 均 价 格 为 {2.0,1.8,2.2},c 1 c 2 被 满 足,c 3 被 拒 绝 那 么, 如 果 c 1 以 非 诚 实 的 出 价 7 竞 拍, 服 务 视 频 的 平 均 价 格 为 {2.3,1.8,2.2} 在 这 种 情 况 下,c 1 被 拒 绝 从 上 述 简 单 的 例 子 可 以 看 出, 对 于 竞 拍 者 来 说, 最 好 的 策 略 就 是 如 实 地 给 出 竞 拍 价 格 竞 拍 ){ 求 S ; 算 法 1 基 于 低 价 格 拍 卖 的 视 频 集 分 配 算 法 1) While( 视 频 集 为 空 没 有 云 提 供 商 再 参 与 2) 传 播 S D 到 云 提 供 商 处 ; 3) 传 播 S C 到 视 频 提 供 商 处 ; 4) 计 算 dis 并 按 降 序 排 列 ; 5) 选 择 dis 最 大 值 的 云 提 供 商, 满 足 其 要 6) If(S 中 的 每 个 视 频 类 的 数 量 都 小 于 r i ){ 7) 分 配 成 功 ; 8) 更 新 序 列 R; 9) 删 除 竞 拍 者 ; 10) }else{ 11) 分 配 失 败 ; 12) } 13) } 评 估 算 法 1 的 时 间 复 杂 度 : 排 序 dis 的 时 间 复 杂 度 是 O(mlogm) 低 价 格 视 频 集 分 配 算 法 的 时 间 复 杂 度 是 O(mn), 因 此 算 法 1 的 时 间 复 杂 度 是 O(mn) 3.3 视 频 ( 货 物 ) 替 换 算 法 已 有 的 拍 卖 模 式 是 建 立 在 竞 拍 者 竞 争 货 物 的 种 类 和 数 量 都 是 固 定 的 情 况 下, 而 以 预 期 收 益 为 基 准 的 视 频 类 是 可 替 换 的, 这 是 本 文 LBAS 在 拍 卖 机 制 上 区 别 于 其 他 文 献 的 创 新 之 处 例 2 竞 拍 者 a 需 要 3 单 位 的 CPU,4 单 位 的 内 存 来 完 成 一 项 工 作 但 此 时, 拍 卖 人 只 剩 余 2 单

5 第 4 期 丛 鑫 等 : 基 于 可 信 拍 卖 机 制 的 视 频 移 植 定 价 策 略 57 位 的 CPU 和 5 单 位 的 内 存, 那 么, 拍 卖 人 给 a 2 单 位 的 CPU 和 5 单 位 的 内 存 是 不 合 适 的 但 是, 在 LBAS 中, 货 物 可 以 替 换 的, 即 如 果 竞 拍 者 a 需 要 3 单 位 的 v 1 和 4 单 位 的 v 2 来 获 得 收 益 C, 但 是, 拍 卖 人 只 剩 余 2 单 位 的 v 1,4 单 位 的 v 2 和 5 单 位 的 v 3, 那 么 如 何 分 配 货 物 来 满 足 a 呢? 考 虑 到 1 单 位 v 1 所 获 得 的 收 益 等 于 2 单 位 v 3 所 获 得 的 收 益, 那 么 用 等 价 的 原 则 来 替 换 货 物 满 足 a 是 可 行 的 在 算 法 1 过 滤 出 能 初 步 赢 得 拍 卖 的 云 提 供 商 之 后, 按 降 序 排 列 形 成 [c 1,c 2, ] 在 此 序 列 中, 相 比 于 c 2, 竞 拍 者 c 1 分 配 到 视 频 类 对 于 视 频 提 供 商 来 讲 是 最 有 利 的, 但 如 果 c 1 所 需 视 频 类 数 量 不 能 得 到 满 足 时, 视 频 提 供 商 就 会 多 支 付 费 用, 因 此 存 在 如 下 问 题 问 题 1 在 运 行 算 法 1 之 后, 设 计 何 种 分 配 算 法, 使 视 频 提 供 商 本 地 服 务 器 上 预 留 的 视 频 总 体 开 销 尽 可 能 得 小 满 足 条 件 :1) 当 竞 拍 者 所 竞 拍 的 货 物 ( 亦 可 是 预 期 的 收 益 ) 完 全 被 满 足 后, 终 止 其 竞 拍 过 程 ;2) 视 频 类 以 收 益 为 基 准, 是 可 替 换 的 ;3) 竞 拍 者 请 求 的 视 频 类 数 量 足 够 时, 这 部 分 将 被 满 足, 形 成 固 定 视 频 集, 不 能 满 足 的 部 分 形 成 可 变 视 频 集 ;4) 固 定 视 频 集 和 可 变 视 频 集 的 收 益 之 和 不 等 于 ( 严 格 ) 或 不 接 近 于 ( 存 在 阈 值 ) 预 期 设 定 的 收 益, 则 视 频 类 分 配 失 败, 已 分 配 的 固 定 视 频 集 需 要 放 回 剩 余 视 频 集, 并 参 与 下 一 次 分 配 如 图 1 所 示 问 题 1 的 数 学 描 述 如 下 ( + ) (5) max Fix m wr i n i i (6) Fix + wr wr i n i i i n i i 其 中,m' 是 请 求 未 被 满 足 的 云 提 供 商 集,n' 是 剩 余 视 频 集 Fix 是 固 定 视 频 集, 是 可 替 换 视 wr ' ' i n i i 频 集 如 果 式 (6) 不 能 满 足, 则 Fix 需 要 返 回 n', 并 参 与 下 一 次 分 配 ( 详 见 算 法 2) 算 法 2 的 时 间 复 O mlog m + m n log n 杂 度 为 ( ( ) ( )) 3.4 费 用 支 付 算 法 -Vicrey 算 法 能 保 证 竞 拍 者 诚 信 出 价, 并 达 到 Pareto 有 效 性 [16], 使 竞 拍 者 只 关 注 如 何 更 好 地 估 计 视 频 集 的 价 格 而 不 用 考 虑 其 他 竞 拍 者 的 出 价, 亦 能 使 视 频 提 供 商 获 得 理 想 的 价 格 在 此 算 法 中, 需 要 找 到 一 个 最 小 值 mv, 定 义 为 竞 拍 过 程 中 在 竞 拍 者 不 参 与 的 情 况 下, 被 接 受 的 最 大 的 dis 值 而 竞 拍 者 需 要 支 付 的 价 格 为 C mv T C = (7) n i wr i= 1 i = (8) n i wr i 1 i mv = 是 在 竞 拍 者 不 参 与 竞 拍 的 情 况 下, 被 接 图 1 可 替 换 货 物 的 视 频 集 分 配

6 58 通 信 学 报 第 37 卷 受 的 竞 拍 者 总 的 价 格 值, r i 是 没 有 竞 拍 者 的 情 况 下, 被 接 受 的 竞 拍 者 竞 拍 i 的 数 量 竞 拍 成 功 支 付 T, 否 则 支 付 0 算 法 2 可 替 换 视 频 集 的 贪 婪 分 配 算 法 1) 按 dis 降 序 排 列 m 中 的 云 提 供 商, 形 成 m'; 2) While( 遍 历, m ){ 3) 按 w i 降 序 排 列 视 频 集, 形 成 n'; 4) b =0;num=0; 5) For(int l = 1; l <= n'.length; l ++){ i 6) 找 到 满 足 numw ' wr b ( num ) 1 wl + 的 num; 7) b += num w l ; 8) } 9) If( 式 (6) 成 立 ){ 10) 删 除 ; 11) 更 新 n'; 12) }else{ 13) Fix 返 回 n'; 14) } 15) } 3.5 联 盟 抑 制 算 法 l i n i 在 竞 拍 的 过 程 中, 可 能 会 遇 到 如 下 问 题 问 题 2 若 干 竞 拍 者 形 成 联 盟 后, 相 互 之 间 串 通 C 来 获 取 联 盟 利 益 的 最 大 化, 使 联 盟 成 员 都 能 获 得 较 高 的 收 益, 同 时 损 害 拍 卖 者 利 益 如 何 设 计 算 法 来 避 免 此 问 题 的 发 生, 同 时 适 应 低 价 格 竞 拍 机 制 [13] AEM 算 法 是 Andrew V. Goldberg 提 出 的 能 够 抑 制 拍 卖 过 程 中 竞 拍 者 联 盟 的 策 略, 其 核 心 思 想 1 是 以 概 率 进 行 竞 拍 者 集 选 择, 找 到 此 集 合 中 竞 拍 者 最 高 出 价 p, 而 后 以 [0,1] 之 间 的 某 个 随 机 数 为 基 准, 扩 大 此 集 合 并 找 到 第 一 个 大 于 该 集 合 元 素 个 数 的 数 值 n p, 评 估 n p 和 概 率 的 关 系, 当 n p 时, 可 保 证 此 次 拍 卖 过 程 中 不 会 有 个 竞 拍 者 联 盟 本 文 以 AEM 算 法 为 基 础, 提 出 改 进 的 AEM 算 法 AEM' 1) 设 定 集 合 S 评 估 第 低 价 格 拍 卖,S 中 的 元 1 素 以 概 率 进 行 选 择,S 中 元 素 最 低 出 价 标 记 为 p 2) 评 估 S 中 出 价 低 于 p 的 元 素 数 量, 设 置 变 量 为 y, 满 足 [0,1] 之 间 的 均 匀 随 机 分 布 计 算 n p, p ( ) {2 : i } n = b + Z # p i y 3) 如 果 n p, 则 所 有 竞 拍 者 价 格 均 为 p 4) 如 果 n p >, 竞 拍 者 i 的 价 格 以 概 率 为 p, n 2 p 满 足 其 他 概 率 时 为, 而 后 执 行 -Vicrey 在 AEM,# p (b) 定 义 为 集 合 b 中 竞 拍 者 的 数 量, 这 些 竞 拍 者 的 出 价 至 少 为 p x S 定 义 为 满 足 x S 且 x x 的 最 大 值, 即 x 是 小 于 且 最 接 近 于 x 的 值 设 计 迭 代 的 联 盟 抑 制 算 法 如 算 法 3 所 示 算 法 3 基 于 迭 代 过 程 的 AEM 联 盟 限 制 算 法 1) While( 所 有 的 视 频 集 都 被 分 配 完 毕 或 者 视 频 集 数 量 不 能 满 足 竞 拍 者 请 求 的 数 量 ){ 足 ){ 2) 输 入 S; 3) 输 入 S,C ; 4) 通 过 S 计 算 视 频 集 i 的 S i 值 ; 5) For(i=1;i 视 频 集 类 型 的 数 量 ; i++){ 6) 运 行 AEM 算 法 ; 7) 记 录 O i ; 8) } 9) For(j=1; j 竞 拍 者 数 量 ; j++){ 10) If( 竞 拍 者 j 所 希 望 的 视 频 集 数 量 被 满 11) 分 配 成 功 ; 12) 更 新 O i ;} 13) Else{ 14) 将 q i 加 回 到 每 个 视 频 集 }; 15) } 16) } 17) 输 出 O i ; 从 算 法 3 中 可 以 看 出,VoD 提 供 商 以 S 和 S 为 基 础 分 配 视 频 集 到 云 提 供 商, 利 用 AEM 算 法 能 够 达 到 规 模 大 小 为 t 的 联 盟 限 制, 即 结 盟 的 竞 拍 者 数 量 小 于 或 等 于 t 在 每 次 循 环 过 程 中,AEM 首 先 1 以 概 率 随 机 选 择 一 些 竞 拍 者, 同 时 决 定 最 低 的 出 价 值 p(,p 都 是 AEM 算 法 定 义 的 参 数 ) 然 后, 选 择 归 一 化 的 随 机 变 量 值 计 算 ( ) np = # p b i+ y {2 : i Z }, 随 机 变 量 值 的 取 值 为 [0, 1] 而 后,p 和 n p 用 于 发 布 价 格 : 当 np 时, 所 有 的 竞 拍 者 得 到 价 格 p; 否 则, 所 有 竞 拍 者 得 到 价 格 z i, 其 中,z i =p 的 概 率 为 n 2 p 最 后, 当 视 频 集 全 部 销 售 完 毕 时 运 行 -Vicrey 算 法

7 第 4 期 丛 鑫 等 : 基 于 可 信 拍 卖 机 制 的 视 频 移 植 定 价 策 略 59 需 要 注 意 的 是, 随 机 选 择 和 一 致 性 技 术 能 够 保 证 避 免 竞 拍 者 之 间 的 联 盟 但 是, 在 进 行 视 频 集 分 配 的 过 程 中, 必 须 要 考 虑 到 视 频 集 数 量 限 制, 同 时, 竞 拍 者 只 有 在 完 全 获 得 其 预 先 想 要 的 视 频 集 后 才 支 付 费 用, 因 此 必 须 将 检 测 算 法 加 入 到 AEM 算 法 中 设 计 的 检 测 算 法 如 下 : 在 第 i 次 循 环 过 程 中, 记 录 视 频 集 i 的 分 配 结 果 O i q i Q i 表 示 临 时 分 配 到 竞 拍 者 r 上 的 视 频 集 i 的 数 量, 这 个 值 等 于 竞 拍 者 r 预 先 希 望 得 到 的 视 频 集 i 数 量 当 所 有 的 视 频 集 都 计 算 完 毕 后, 需 要 检 测 S 来 决 定 是 否 所 有 竞 拍 者 希 望 的 视 频 集 数 都 满 足 如 果 都 被 满 足, 那 么 视 频 集 分 配 成 功, 否 则, 将 q i 回 到 视 频 集 i 的 剩 余 数 量 上, 并 参 与 下 次 循 环 过 程 如 果 所 有 剩 余 的 视 频 集 都 不 能 满 足 竞 拍 者, 那 么 这 些 视 频 集 需 要 VoD 提 供 商 服 务 器 完 成 请 求 应 答 过 程 下 面 通 过 定 理 证 明 算 法 3 是 诚 信 的 定 理 1 算 法 3 以 概 率 p 满 足 t 诚 信 的, 其 中, t p = 1 Θ 证 明 定 义 t 诚 信 如 下 : 对 于 任 何 竞 拍 者 数 量 小 于 或 等 于 t 的 联 盟, 联 盟 之 内 的 竞 拍 者 能 够 获 得 利 益 最 大 化 的 前 提 条 件 是, 所 有 的 竞 拍 者 都 能 如 实 地 给 出 自 己 的 价 格 AEM 算 法 已 经 被 证 实 以 概 率 t 1 Θ 符 合 t 诚 信 的 算 法 2 中, 每 个 视 频 集 都 是 利 用 AEM 算 法 独 立 计 算 的 因 此, 对 于 视 频 集 i, 假 设 联 盟 中 的 竞 拍 者 数 量 为 t i 那 么, 在 t i 中,AEM 算 法 能 够 保 证 每 个 竞 拍 者 都 能 如 实 地 出 价, 从 而 获 得 最 大 的 收 益 而 在 视 频 集 拍 卖 的 过 程 中, 视 频 集 彼 此 相 独 立, 因 此 竞 拍 者 不 能 通 过 非 诚 实 的 出 价 来 使 收 益 最 大 化 因 此 提 出 的 算 法 能 够 保 证 是 t i 诚 信 的 ti 视 频 集 i 是 以 概 率 pi = 1 Θ 达 到 t i 诚 信 的 所 有 视 频 集 都 是 t 诚 信 的 概 率 以 p 表 示 p 计 算 如 下 p = p = ( 1 p ) 1 p i i i, p = i 1 p i i S (9) i S i S 其 中, ti ti p i S i = Θ i S = Θ i S t t i S i,, 且 式 (9) 表 达 如 下 t p = 1 Θ 4 实 验 评 价 (10) 为 了 评 估 LBAS 的 性 能, 设 计 详 细 的 模 拟 实 验, 并 与 VMC [9] [10] 机 制 和 OPT-ORS 方 案 对 比 VMC 和 OPT-ORS 已 经 被 证 实 是 较 好 地 节 省 视 频 提 供 商 费 用 的 机 制 4.1 实 验 设 置 设 定 2 个 评 价 参 数 : 费 用 节 省 率 和 用 户 满 意 度 支 付 给 赢 得 竞 拍 的 云 提 供 商 费 用 之 和 费 用 开 销 率 = 传 统 架 构 下 费 用 开 销 之 和 费 用 节 省 率 =1 费 用 开 销 率 赢 得 竞 拍 的 云 提 供 商 数 量 用 户 满 意 度 = 参 与 竞 拍 的 云 提 供 商 数 量 需 要 注 意 的 是, 标 识 观 看 视 频 用 户 满 意 度 的 评 价 指 标 也 应 被 评 定, 但 由 于 视 频 点 播 服 务 是 由 云 提 供 商 提 供, 是 相 关 于 云 平 台 能 力 的 参 数, 因 此 这 个 参 数 对 LBAS 策 略 的 评 估 无 意 义 而 实 际 上, 视 频 点 播 提 供 商 有 权 与 云 提 供 商 交 涉 来 提 高 用 户 满 意 度 每 个 视 频 权 重 符 合 (0,1] 均 匀 分 布, 云 提 供 商 选 择 的 视 频 类 数 量 符 合 [0,r i ] 均 匀 分 布 使 用 Amazon EC2 的 价 格 模 式 为 实 验 价 格 基 准 为 了 区 分 云 平 台 能 力, 其 服 务 成 本 在 基 准 价 格 基 础 上 随 机 进 行 小 幅 增 减,pv 和 D 关 系 是 线 性 的 实 验 模 拟 运 行 环 境 在 本 地 云 中 典 型 的 服 务 器 配 置 为 2 个 4 核 CPU, 频 率 为 2.4 GHz,32 GB 内 存, 选 择 15 个 虚 拟 机 作 为 独 立 云, 配 置 为 4 GB 内 存,80 GB 存 储 空 间, 1 Mbit/s 4 Mbit/s 和 10 Mbit/s 带 宽 依 据 文 献 [9] 给 出 的 视 频 网 站 视 频 播 放 时 间 长 度, 服 务 各 类 视 频 所 需 的 单 位 费 用 开 销, 设 定 : 视 频 集 数 量 为 1 000~6 000, 视 频 播 放 时 间 为 10 min~1.5 h, 视 频 集 分 组 n 为 10~30,r i 取 值 从 0 到 视 频 类 数 最 大 值 4.2 实 验 结 果 图 2 显 示 的 是 在 云 提 供 商 数 不 同 的 情 况 下 的 费 用 节 省 率 随 云 提 供 商 数 的 增 加, 费 用 节 省 率 在 增 加, 这 归 因 于 基 于 dis 的 视 频 集 分 配 方 案 如 果 云 提 供 商 每 次 拍 卖 过 程 中 想 要 获 胜, 就 得 使 dis 尽 可 能 得 大, 从 而 导 致 服 务 视 频 请 求 的 单 位 价 格 在 降 低 另 一 个 因 素 在 于 分 配 到 云 提 供 商 处 的 视 频 数

8 60 通 信 学 报 第 37 卷 量 的 增 加 图 3 是 与 当 前 最 新 的 视 频 服 务 费 用 节 省 方 案 VMC 相 比 较 的 结 果 以 当 前 各 大 视 频 服 务 提 供 商 采 用 的 P2P-VoD 视 频 服 务 方 案 为 基 准,VMC 能 够 降 低 30% 的 费 用,LBAS 能 降 低 约 40% 的 费 用 这 归 功 于 云 提 供 商 之 间 的 竞 争, 同 时 视 频 服 务 的 定 价 权 从 云 提 供 商 转 移 到 视 频 提 供 商 处 与 基 于 云 资 源 预 留 的 视 频 服 务 方 案 OPT-ORS [10] 相 比 较, 由 于 OPT-ORS 以 预 留 资 源 的 开 销 来 换 取 请 求 应 答 时 间 的 缩 短 为 目 的, 造 成 其 费 用 支 出 要 稍 高 于 VMC 算 法, 但 用 户 满 意 度 确 高 于 VMC 算 法 LBAS 核 心 思 想 是 将 视 频 实 例 交 由 云 平 台 进 行 视 频 服 务, 通 过 云 提 供 商 间 的 竞 争 降 低 视 频 单 位 服 务 费 用, 但 用 户 满 意 度 依 云 平 台 的 基 础 设 施 和 平 台 设 置 的 不 同 而 不 同, 无 法 在 本 地 量 化 衡 量 用 户 满 意 度 的 衡 量 需 要 本 地 视 频 服 务 提 供 商 对 云 服 务 提 供 商 进 行 监 督, 如 果 用 户 满 意 度 低, 可 弃 之 不 用 图 4 显 示 了 视 频 集 数 不 同 时 的 用 户 满 意 度 随 着 视 频 类 数 量 的 增 加, 用 户 满 意 度 增 加, 值 可 以 达 到 1 这 是 由 于 所 有 的 云 提 供 商 预 期 的 收 入 都 由 于 有 足 够 的 视 频 类 而 得 到 满 足, 或 者 可 以 找 到 足 够 的 替 换 视 频 类 用 户 满 意 度 在 竞 争 固 定 数 量 的 视 频 类 时, 随 云 提 供 商 数 量 的 增 加 而 下 降 原 因 在 于 赢 得 竞 拍 的 云 提 供 商 占 据 了 大 量 的 视 频, 导 致 剩 余 的 数 图 2 云 提 供 商 数 和 视 频 集 数 不 同 时 费 用 节 省 率 的 变 化 图 3 LBAS VMC 和 OPT-ORS 在 费 用 节 省 率 参 数 上 的 对 比

9 第 4 期 丛 鑫 等 : 基 于 可 信 拍 卖 机 制 的 视 频 移 植 定 价 策 略 61 图 4 视 频 数 和 用 户 满 意 度 之 间 的 关 系 图 5 剩 余 视 频 率 和 云 提 供 商 数 之 间 的 关 系 量 不 能 满 足 其 余 的 云 提 供 商 需 求, 这 种 情 况 发 生 在 所 有 的 视 频 集 上, 因 此 可 替 换 的 视 频 集 也 不 充 足 图 5 是 剩 余 视 频 集 和 云 提 供 商 数 间 的 关 系 引 入 参 数 剩 余 视 频 率 没 有 被 分 配 到 云 平 台 的 视 频 数 剩 余 视 频 率 = 总 的 视 频 数 剩 余 视 频 必 须 被 视 频 服 务 提 供 商 服 务 器 应 答, 会 降 低 费 用 节 省 率 可 以 看 出, 随 云 提 供 商 数 的 增 加, 剩 余 视 频 率 在 降 低 但 当 云 提 供 商 数 固 定 时, 更 多 的 视 频 集 能 够 获 得 较 小 的 剩 余 视 频 率, 这 归 因 于 有 足 够 的 视 频 集 用 于 替 换 图 6 显 示 的 是 用 户 满 意 度 和 费 用 节 省 率 之 间 的 关 系 对 于 视 频 提 供 商 来 说, 当 用 户 满 意 度 等 于 1 时 对 其 是 有 害 处 的 此 时, 所 有 的 云 提 供 商 都 获 得 了 预 期 的 收 入, 并 且 都 不 参 与 竞 拍 过 程, 此 时 剩 余 的 视 频 集 不 得 不 通 过 VoD 提 供 商 本 地 的 服 务 器 来 应 答 评 估 分 配 算 法 的 视 频 集 可 替 换 程 度 对 剩 余 视 频 集 的 影 响, 设 置 参 数 δ δ 是 每 个 云 能 够 容 忍 的

10 62 通 信 学 报 第 37 卷 浮 动 收 益 例 如 : 竞 拍 者 i 的 所 申 请 的 w i r i 之 和 为 100, 且 δ=0.01, 那 么 之 和 值 就 可 以 是 99~101 的 任 何 数 图 7 显 示 了 当 δ=0.03 和 δ=0.05 时 的 剩 余 视 频 数 随 着 δ 值 的 增 加, 能 够 分 配 到 云 中 的 视 频 集 数 在 增 加, 但 是 增 加 幅 度 不 大 这 归 结 于 贪 婪 分 配 算 法 能 够 很 容 易 将 视 频 进 行 重 组 和 替 换 图 6 用 户 满 意 度 和 费 用 节 省 率 之 间 的 关 系 云 提 供 商 组 成 的 系 统 中, 仅 仅 需 要 增 加 一 个 中 间 商, 用 于 连 接 视 频 提 供 商 和 云 提 供 商 所 有 的 视 频 提 供 商 发 送 视 频 集 到 中 间 商 处, 并 且 由 中 间 商 利 用 提 出 的 策 略 来 分 配 视 频 集 但 是, 同 时 也 需 要 考 虑 到 中 间 商 的 收 益 5 结 束 语 当 视 频 提 供 商 规 模 较 大 时, 单 个 云 提 供 商 也 许 不 能 满 足 其 所 需 的 资 源 需 求, 如 带 宽, 同 时 为 了 避 免 由 于 云 灾 难 而 导 致 的 视 频 服 务 的 中 断, 选 择 多 个 云 提 供 商 参 与 视 频 服 务 是 个 很 好 的 解 决 方 案 基 于 上 述 问 题, 本 文 提 出 了 基 于 拍 卖 机 制 的 视 频 集 分 配 方 案 其 以 出 价 的 高 低 来 确 定 是 否 竞 拍 成 功, 价 格 越 低, 成 功 可 能 性 就 越 大 同 时, 为 了 避 免 由 于 竞 拍 者 之 间 的 联 盟 而 导 致 VoD 提 供 商 利 益 的 损 害, 设 计 了 AEM' 算 法, 使 竞 拍 过 程 能 够 达 到 t 诚 信 的 实 验 结 果 表 明,VMC 策 略 能 够 比 传 统 的 视 频 点 播 服 务 策 略 节 省 30% 的 费 用, 而 LBAS 能 够 进 一 步 节 省 10% 的 费 用, 因 此 可 以 认 为 提 出 的 策 略 是 有 效 的 参 考 文 献 : 图 7 云 提 供 商 数 和 δ 对 剩 余 视 频 率 的 影 响 4.3 讨 论 基 于 上 述 结 论, 视 频 提 供 商 必 须 通 过 视 频 集 的 数 量 来 评 估 参 与 竞 拍 的 云 提 供 商 数 量 相 比 VMC 机 制, 提 出 的 机 制 能 够 进 一 步 节 省 10% 的 费 用, 并 且 能 够 避 免 服 务 的 中 断 同 时,LBAS 能 够 以 较 小 的 价 格 处 理 突 发 流 量 更 重 要 的 是, LBAS 能 适 应 未 来 视 频 移 植 过 程, 即 当 视 频 提 供 商 规 模 很 大 且 云 提 供 商 可 选 时, 如 何 处 理 突 发 请 求 并 节 省 费 用 提 出 的 策 略 应 用 于 由 一 个 大 规 模 视 频 提 供 商 和 多 个 云 提 供 商 组 成 的 云 辅 助 VoD 系 统 中, 其 可 轻 易 地 扩 展 到 多 个 视 频 提 供 商 和 多 个 [1] HUANG C, LI J, BOSS K W. Can Internet video-on-demand be profitable?[j]. Proceedings of ACM SIGCOMM Computer Communication Review, 2007, 37(4): [2] HUANG G M. An upload bandwidth allocation algorithm in data scheduling of P2P VoD system[c]//the th IEEE International Conference on Software Engineering and Service Science. c2014: [3] ZHONG L J, XU C Q. DLCA: distributed load balancing and VCR-aware two-tier P2P VoD system[c]//the 2014 IEEE 11th Consumer Communications and Networing Conference. c2014: [4] DAVID H. From selfish nodes to cooperative networs-emergent lin-based incentives in peer-to-peer networs[c]// The Fourth International Conference on Peer-to-Peer Computing. c2004: [5] MEULPOLDER M, POUWELSE J A, EPEMA D H J. Bartercast: a practical approach to prevent lazy freeriding in P2P networs[c]// IEEE International Symposium on Parallel & Distributed. c2009:1-8. [6] SATSIOU A, TASSIULAS L. Trust-based exchange of services to motivate cooperation in P2P networs [J]. Peer-to-Peer Networing and Applications, 2011,4(2): [7] 丛 鑫, 双 锴, 苏 森, 等. 基 于 带 宽 请 求 预 测 和 云 资 源 预 留 的 视 频 移 植 策 略 [J]. 通 信 学 报, 2014,(5): CONG X, SHUANG K, SU S, et al. Video migration strategy based on bandwidth demand prediction and cloud resource reservation[j]. Journal on Communications, 2014,(5): [8] Amazon [EB/OL]:

11 第 4 期 丛 鑫 等 : 基 于 可 信 拍 卖 机 制 的 视 频 移 植 定 价 策 略 63 [9] LI H T, ZHONG L L, LIU J C, et al. Cost-effective partial migration of VoD services to content clouds[c]//ieee 4th International Conference on Cloud Computing. c2011: [10] HE J, WEN Y G, HUANG J W, et al. On the cost-qoe trade-off for cloud-based video streaming under amazon EC2 s pricing models[j]. IEEE Transactions on Circuits and Systems for Video Technology,2014,24(4): [11] HAJJAT M, SUN X, SUNG Y W E. Cloudward bound: planning for beneficial migration of enterprise applications to the cloud[j]. ACM SIGCOMM Computer Communication Review, 2010, 40(4): [12] DI N, LIU Z M, LI B C, et al. Demand forecast and performance prediction in peer-assisted on-demand streaming systems[c]//the 30th IEEE International Conference on Computer Communications. c2011: [13] GOLDBERG A V, HARTLINE J D. Collusion-resistant mechanisms for single-parameter agents[c]//the sixteenth annual ACM-SIAM symposium on Discrete algorithms. c2004: [14] CHEN Y J, LIN P, ZHANG Q. LOTUS: location-aware online truthful double auction for dynamic spectrum access[c]//the 2014 IEEE International Symposium on Dynamic Spectrum Access Networs. c2014: [15] TSAI Y H. The cloud streaming service migration in cloud video storage system[c]//the 27th International Conference on Advanced Information Networing and Applications Worshops. c2013: [16] LI W. An extensible and flexible truthful auction framewor for heterogeneous spectrum marets[c]//the 15th ACM International Symposium on Mobile Ad Hoc Networing and Computing. c2014: 作 者 简 介 : 丛 鑫 (1982-), 男, 辽 宁 阜 新 人, 博 士, 辽 宁 工 程 技 术 大 学 讲 师, 主 要 研 究 方 向 为 P2P 技 术 云 计 算 和 流 媒 体 訾 玲 玲 (1981-), 女, 辽 宁 阜 新 人, 博 士, 辽 宁 工 程 技 术 大 学 讲 师, 主 要 研 究 方 向 为 智 能 软 件 图 形 图 像 与 多 媒 体 孙 劲 光 (1962-), 女, 辽 宁 阜 新 人, 博 士, 辽 宁 工 程 技 术 大 学 教 授 博 士 生 导 师, 主 要 研 究 方 向 为 信 息 可 视 化 技 术 与 智 能 化 救 灾