多媒体无线网中QoS降级的公平性研究.doc

多媒体无线网中 QoS 降级的公平性研究 张雪 东南大学 计算机网络和信息集成教育部重点实验室 江苏 南京 210096 摘 要 对无线 移动多媒体网中多服务类 多优先级的适应多媒体应用 QoS 降级的公平性问题进行了研究 提 出降级因子加权平方和最小的降级原则 不但考虑了类间和类内优先级 而且考虑了用户的 QoS 降级深度 接 着 证明对离散型适应多媒体应用 降级因子加权平方和最小的降级原则满足广义的按比例公平性 而对连续 型适应多媒体应用 满足按比例公平性 最后 用量子遗传算法对所给问题进行了求解 结果进一步验证了所 提算法的有效性 关键词 无线 移动网络 QoS 降级 公平性 降级因子 量子遗传算法 中图分类号 TN91文献标识码 B文章编号 1000 436X 2007 05 0102 07 Research on the fairness of QoS degradation in multimedia wireless networks ZHANG Xue Key Laboratory of Computer Network and Information Integration Ministry of Education Southeast University Nanjing 210096 China Abstract The fairness of QoS degradation of multi class and multi priority adaptive multimedia applications in wireless mobile multimedia networks was studied A degradation principle minimizing the weighted sum of degradation factor s square MWSDFS was proposed considering not only inter class and intra class priority but also user s QoS degradation degree Then the degradation principle of MWSDFS is proved satisfying the generalized proportional fairness for discrete multimedia applications and proportional fairness for continuous adaptive multimedia applications At last quantum genetic algorithm is used to solve the given problem and the results further validate the effectiveness of the proposed algorithm Key words wireless mobile networks QoS degradation fairness degradation factor quantum genetic algorithm 1 引言 1 随着因特网服务与无线移动通信网服务的集 成 要求无线移动通信网能够提供更多的带宽资 源来满足具有不同流量特征 不同 QoS 需求的多 媒体应用的带宽需求 无线网带宽资源固有的贫 乏性难以满足这种日益增长的需要 成为提供多 媒体服务的 QoS 性能瓶颈 连接级呼叫接纳控制 1 是 提供 QoS 保证的重要技术手段 目标是保证切换 收稿日期 2006 10 17 修回日期 2007 04 06 基金项目 国家自然科学基金资助项目 90604003 呼叫丢弃率满足系统 QoS 要求的前提下尽量降低 新发起呼叫阻塞率 适应多媒体应用已成功运行 于有线网 针对无线链路带宽资源缺乏以及快速 波动的特点 将有线网中的适应多媒体应用引入 到无线网中 可以对当前应用连接的带宽动态调 整 以适应不断变化的网络环境 从而缓解由于 移动和衰减引起的资源波动 利用适应多媒体应 用带宽可动态调 第 28 卷第 5 期通 信 学 报Vol 28 No 5 2007 年 5 月Journal on CommunicationsMay 2007 Foundation Item The National Natural Science Foundation of China 90604003 第 5 期张雪 多媒体无线网中 QoS 降级的公平性研究 103 整的特点 能够有效地降低切换丢弃率 并能使 系统接纳足够多的用户 从而潜在地增加服务提 供商的收入 但在适应多媒体应用中增加了新的 需要考虑的因素 如带宽适应算法 带宽降级 或 QoS 降级 及其公平性问题 降级频率 降 级深度 降级时间等对用户满意度的影响等 适应多媒体应用可分为离散型和连续型 在 离散适应多媒体中 带宽是一组离散值 可通过 分层编码 2 或滤波技术 3 实现 在连续适应多媒体 4 中 带宽是连续值 随着无线网中适应多媒体应 用的引入 在 QoS 呼叫接纳控制以及带宽降级 和适应问题方面已经有大量的研究 另外 公平 的无线带宽调度问题也已经有大量的研究 但带 宽降级的公平性问题却很少有研究 文献 5 将降 级周期率 DPR degradation period ratio 作为 QoS 参数研究带宽降级问题 但 DPR 未能反映带宽降 级的程度 文献 6 用降级率和升级 降级频率对带 宽适应问题进行了研究 但并没有考虑公平性问 题 文献 7 研究了带宽分配的公平性问题 但是 公平的带宽分配算法并不能保证公平的带宽降级 8 文献 8 对无线网中离散型适应多媒体应用的带宽 降级公平性问题进行了研究 并提出 3 种按比例 公平的降级方法分 2 个场景进行了研究 场景 1 研究降级率 DR degradation ratio 之比和降级深度 DD degradation degree 之比 场景 2 研究降级面 积 DA degradation area 之比 场景 1 结果表明对 于按比例降级 DR 之比优于 DD 之比 而场景 2 表明 DA 之比能够很好的达到 并能有效地利用带 宽资源且使 DA 最小 本文针对多服务类 多优先级的离散型适应 多媒体应用 研究其降级的公平性问题 为了更 好地描述适应多媒体应用 QoS 降级的公平性 本 文引入降级因子的概念并对其进行了定义 由它 的定义可知 它实际上反映了适应多媒体应用的 带宽 或速率 降级深度 即随着降级深度的增 加 降级因子增大 然后提出了降级因子加权平 方和最小的降级原则 其中权值定义为类间和类 内优先级的函数 而类内优先级定义为该用户为 此应用所付价格的单调增的凹函数 降级因子加 权平方和最小的降级原则不但考虑了类间和类内 优先级 而且考虑了用户的降级深度 因此它区 别于文献中严格按优先级降级的方法 它保证了 降级首先从低优先级类的低优先级用户开始 然 后逐渐向高优先级类的高优先级用户扩展 即它 总是试图保护高优先级的用户 不像严格按优先 级降级的方法 它同样考虑用户 QoS 降级的公平 性问题 随着降级深度的增加 低优先级用户的 QoS 降级对系统性能的影响将会超过高优先级用 户的 QoS 降级对系统性能的影响 即用户 QoS 降 级的公平性既依赖于用户的优先级 又依赖于用 户 QoS 的降级深度 它实际上避免了严格按优先 级降级方法中出现的低优先级用户长期处于饥饿 状态的情况 接着 进一步证明 对离散型适应 多媒体应用 降级因子加权平方和最小的降级原 则满足广义的按比例公平性 而对连续型适应多 媒体应用 满足按比例公平性 最后 主要针对 离散型适应多媒体应用 给出基于量子遗传算法 的问题求解方法 本文其余章节安排如下 第 2 节给出无线移 动多媒体网络的系统模型 第 3 节首先给出降级 因子的定义 然后提出降级因子加权平方和最小 的降级原则 第 4 节证明降级因子加权平方和最 小的降级原则满足广义的按比例公平性 第 5 节 用量子遗传算法对所给问题进行求解 第 6 节为 性能分析 第 7 节为结束语 2 系统模型 在适应多媒体网络中 多媒体呼叫可在自己 的生命周期内根据网络的负载状况动态地调整传 输速率 假设系统能提供 m 类服务 第 i 类适应 多媒体服务的速率需求可表示为 且 2 1 i qiiii rrrR 为 i 类1 2 1 2 1 1 ijiji qjmirr i q 服务的 QoS 等级 用和分别表示 i 类服务的 k i b k i r 第 k 个用户分配到的带宽及相应的传输速率 在有 线网中 而在无线网中 传输速率与信道 k i b k i r 状态有关 用表示该用户 k 的信道状 k i k i br k i k i br k i s 态 且 0 1 则有 事实上 信道10 k i s k i k i k i sbr 的动态与否 对本文的结论影响甚微 所以本文 不考虑信道的动态特性 即传输速率就等于带宽 用户为某一服务所付单位价格由基本价格和附加 价格两部分组成 假设各类服务具有不同的优先 级 用表示第 i 类服务的优先级 称为类间优先 i c 级 它与基本价格相关 在每一类服务中 依据 用户所付总价格的高低 将其分为不同的优先级 104 通 信 学 报第 28 卷 用表示 i 类服务的第 k 个用户的优先级 称为 k i u 类内优先级 且有 0 1 优先级越高 10 k i u 越大 定义为价格的单调增的凹函数 即 k i u k i u 是该用户为该类服务所付的总 k i k i pfu k i p 单位价格 为了反映用户在整个系统中的优先程 度 本文引入全局优先级的概念 定义为类间优 先级和类内优先级的函数 即 i 类服务的第 k 个用 户的全局优先级表示为 k ii k i ucfg 当 qi 1 且 ri 1 0 时 有 Ri ri 1 它可用来描 述 CBR 服务流 CBR 服务保证了所需的传输速率 可用于非适应多媒体应用或速率不可调的非多媒 体应用 当 qi 1 且 ri 1 0 时 有 它可用来描述 ABR 服务流 2 1 i qiiii rrrR ABR 服务只能保证最小的速率需求 可用于适应 多媒体应用 当 qi 1 且 ri 1 0 时 有 它可用来描述 UBR 服务流 0 2 i qiii rrR UBR 服务与尽力而为服务类似 所以 上述定义 的适应多媒体流量模型可表示多种服务流 3 降级因子加权平方和最小的降级原则 为了更好地描述适应多媒体应用 QoS 降级的 公平性 本文引入降级因子的概念 定义 1 对于速率需求范围为 rmin rmax 的适应 多媒体应用 r 为实际分配到的速率 其降级因子 定义为 1 max D maxmin 0 rr Fr rr 由降级因子的定义可以看出 当实际分配到 的速率小于应用的最小速率需求时 降级因子为 无穷大 它实际上保证了速率分配的有效性 因 为当小于最小速率需求时 该应用将不能正常运 行 因此应对系统目标进行比较大的惩罚 使其 不可能成为目标解 而当分配到的速率大于应用 的最大速率需求时 降级因子为 0 因为此时不存 在降级 但事实上 这种情况是不可能发生的 因为在接纳新应用时 最多只会分配给它所需的 最大速率 当系统资源难以满足用户的需求 而系统又 希望接纳足够多的用户时 就需要对弹性流进行 QoS 降级 为了公平地对用户的 QoS 进行降级 本文提出一种降级因子加权平方和最小的降级原 则 既考虑用户的优先级 又考虑了用户的降级 深度 假设系统中当前有 N 个用户 ri和 wi分别是 第 i 个用户分配到的带宽和全局优先级 则系统的 优化目标是 满足约束式 3 的条件下 式 2 取最 小值 其中 r r1 r2 rN 为带宽 或速率 分配向 量 rtotal是系统的总带宽 2 2 D 1 ii N f rwFr i total 1 rr N i i rtotal 3 从上面的定义可知 系统总是力图保护高优 先级的用户 在不得不对用户的 QoS 进行降级时 总是先从低优先级的用户开始降级 另一方面 它同样考虑了降级深度对用户满意度的影响 因 为随着降级深度的加深 用户的满意度也随之降 低 降级因子增大 使其加权平方和也增大 4 广义的按比例公平性 对于离散型适应多媒体应用 本文提出的降级 因子加权平方和最小的降级原则满足广义的按比例 公平性 而对于连续型适应多媒体应用 它满足按 比例公平性 下面通过引理和定理进行阐述 引理 1 设 0 且 a b 之和为常 0a bR 数 则 a2 b2取最小值的充要条件是 a b 推论 1 设 0 1 2 i aRiN N 为大于等于 2 的正整数 且为常数 则 N i i a 1 取最小值的充要条件是 a1 a2 aN N i i a 1 2 定理 1 对于传输速率可连续变化的弹性流 minf r 在区间 rmin rmax 内满足严格意义上的按比 例公平性 其中 r r1 r2 rN 为带宽 或速率 分 配向量 证明 分 2 种情况 1 当 时 即系统带宽还有剩余的情 total 1 rr N i i 况 这种情况下 系统中没有用户的 QoS 遭到 降级 每一用户都拥有各自最大的传输速率 所 以其相应的降级率均为零 minf r 0 此时不用 考虑降级的公平性问题 2 当时 即系统满载或者过载 total 1 rr N i i r rmax 第 5 期张雪 多媒体无线网中 QoS 降级的公平性研究 105 的情况 事实上 当系统带宽正好可以满足所有 用户的最大需要 即满载的情况 与 1 一样不存 在降级事件 也不用考虑降级的公平性问题 我 们所关心的是系统过载的情况 即系统带宽资源 已经完全被占用 但仍有新的用户请求加入 此 时为了接纳更多的用户 系统不得不对现有的用 户 主要针对弹性流 进行 QoS 降级 根据前 面的定义知 根据一定的接 0 1 2 iDi w FrRiN 纳原则 接纳新用户所需的带宽资源是定值 再 利用 带宽和降级率之间的关系 对于每一确定的速率 分配向量 都有是定值 我们的目 D 1 N ii i w Fr 标是找到使最小的速率分配向量 根 2 D 1 N ii i w Fr 据引理 1 及其推论可知 此时有 11 iiii rDFwrDFw 4 D1D1 iii FrwFr 对于传输速率可连续变化的弹性流 例如 FTP 应用 一旦系统内存在降级 由式 4 可知 所以可重写式 4 得式 D 0 1 2 ii w FriN 5 由式 5 可看出 降级率之比等于优先级的平 方根的倒数之比 而降级率与用户 QoS 的降级深 度成正比 所以定理 1 的结论成立 证毕 5 D D1 1 1 1 2 1 1 i i i i wFr iN Frw 定理 2 对于传输速率为阶梯变化的弹性流 minf r 在区间 rmin rmax 内满足广义的按比例公平 性 其中 r r1 r2 rN 为带宽 或速率 分配向量 证明 定理 2 的证明与定理1 类似 类似的分 析部分从略 只给出不同的地方 当系统过载时 为了接纳更多的用户 系统不得不对现有的用户 主要针对弹性流 进行QoS 降级 根据前面的定 义知 要使式 D 0 1 2 ii w FrRiN 2 取最小值 系统总是从低优先级的用户开始降级 逐渐向高优先级的用户扩展 对于传输速率为阶 梯变化的弹性流 降级是逐级进行的 所以很可 能只对前面 N1 小于 N 个用户的 QoS 进行降级就 能满足新用户的速率需求 所剩下的 N2 N N1 个用户不再需要降级 所以难以满足 0 i 1 2 N 的条件 当然 即使需 D 0 1 2 ii w FriN 要对系统内的所有用户的 QoS 都进行降级 由于 速率变化的阶梯特性 也很难使式 4 和式 5 成立 所以对于此种弹性流 降级因子加权平方和最小 的降级原则 难以满足严格意义上的按比例公平 性 但是总存在一组数 0 1 2 i RiN 使得式 6 成立 6 D11D1 iiiiii w FrwFr 当成立时 必有 0 1 2 iDi w FriN 可重写式 6 为式 7 定理 2Ni i 2 1 0 的结论成立 证毕 D D1 11 1 1 ii i i ii wFr Frw 7 定理 3 对于系统中所有的弹性流 minf r 在 区间 rmin rmax 内满足广义的按比例公平性 证明 由定理 1 和定理 2 的结论可知 定理 3 成立 证毕 5 基于量子遗传算法的求解方法 量子计算利用量子理论中量子态的叠加 纠缠 和干涉等特性 通过量子并行计算有可能解决经典 计算中的NP 问题 量子遗传算法将量子计算与遗传 算法相结合 具有迭代次数少 收敛速度快 搜索 效率高和全局寻优能力强等优点 本文用量子遗传 算法对上述问题进行求解 关于量子遗传算法在无 线网资源分配中的应用请参考文献 9 在此不再对 其做详细介绍 设共有 m 类服务 qi和 xi分别是 i 类服务的 QoS 等级数和当前状态的用户数 则对于我们的 问题可用式 8 表示量子位染色体 其中 ki lbqi i 1 2 m 为复数对 用来表示一个 T ijij 量子位 且有和 1 0 ijijij 是该量子位的状态 这里 1 22 ijij ij i 1 2 m j 1 2 ki 量子遗传算法的适应度函 数定义为式 9 其中 r r1 r2 rN 为速率分配向 量 8 1111 1 1111 1 112 11 11112 m m m m x kkxxx k kxxx kx k Fitness func minf r 9 采用量子旋转门更新量子位 量子染色体第 i 106 通 信 学 报第 28 卷 位的值用式 10 进行更新 其中是 T ii i 旋转角 定义为 和 i ii s i ii s 分别表示旋转方向和旋转角的大小 i i i i i i i i i cos sin sin cos 10 用量子遗传算法进行优化求解 可根据实际 问题预先制定收敛策略 本文用表 1 作为收敛策 略 f 代表适应度值 bi和 ri分别为最优解 b 和 当前的二值解 r 的第 i 位 算法描述如下 QGA QDA 基于 QGA 的 QoS 降级算法 1 t 0 2 初始化 Q t 3 由 Q t 状态得出 P t 4 修正 P t 5 计算 P t 的适应度值 6 保存最好的 P t 7 while t0 i i 0 i 0 i 0 0 0 0 0 1 1 1 1 0 0 1 1 0 0 1 1 false true false true false true false true 0 0 0 0 05 0 01 0 025 0 005 0 025 0 0 0 1 1 1 1 1 0 0 0 1 1 1 1 1 0 0 0 1 1 0 0 0 0 0 0 0 0 1 1 1 6 性能分析 假设系统中有两类应用 每一类应用的呼叫 随机到达 实验参数见表 2 表 2实验参数 应用 类 类间 优先级 基本 价格 带宽需求总带宽 种群 数 最大 代数 变异率 I0 30 4 1 2 3 4 II0 91 0 2 4 6 8 5015 0000 001 呼叫接纳控制 呼叫到达时 如果系统中不 存在降级且有足够的带宽资源供其使用 就接纳 该呼叫并分配给其最大所需 如果系统没有足够 的带宽资源满足其最大所需 但通过对系统中现 有应用的 QoS 实施降级后能挤出满足其最小速率 需求的带宽资源 就接纳该呼叫并调用量子遗传 算法寻找系统当前的最优分配方案 否则 就拒 绝该呼叫 所要测试的性能指标包括资源利用率 服务提 供商的利润 降级因子 按比例公平性 i 类应用的 用户k 的单位支付价格随机产生并归一化为 0 1 k i p 之间 并利用求出该用户的类 exp 1 k i k i pu 内优先级 然后利用求出其全局优先 k i u k ii k i ucg 级 资源利用率 11 U 1 j N Tr j 服务提供商的利润 12 S 2 11 j kk ii x RP r ik 因为量子遗传算法本身是一种随机操作 为 了更好地验证本文思想 运行 QGA QDA 算法 10 次 而且每次采用相同的用户类型和相同的全局 优先级 如图 1 所示 用户类型和全局优先级 图 1 用户类型及其全局优先级 图 2 是降级因子的平均值与系统中用户个数 间的关系 从图 2 可以看出 随着系统中用户数 的增加 降级因子增大 且低优先级用户 类 的 第 5 期张雪 多媒体无线网中 QoS 降级的公平性研究 107 降级因子几乎总是大于高优先级用户 类 的 DF 这与前面的理论分析部分相符 降级因子的平均值 图 2 降级因子的平均值 图 3 和图4 分别是当系统中有15 和 25 个用户 时 各个用户的降级因子之比与其全局优先级的平 方根倒数之比 从中可以看出 降级因子之比与其 相应的全局优先级的平方根倒数之比2 条曲线并没 有完全吻合 即对于离散型适应多媒体 降级因子 加权平方和最小的降级原则不满足严格的按比例公 平性 但同时也可看出 这2 条曲线几乎总是有相 同的变化趋势 正如前面的理论分析 它满足广义 的按比例公平性 另外还应注意 本文给出的并不 是最优结果 对于最优结果 图3 和图4 中的2 条 曲线应该更吻合一些 图 5 是系统吞吐量与系统中用户数之间的关 系 给出该图的目的主要是为了说明量子遗传算 法的搜索能力 当系列满载或过载时 搜索结果 所对应的系统吞吐量与理论带宽容量越接近 说 明算法的搜索能力越强 从图 5 中可看出 量子 遗传算法有非常好的搜索能力 比值 图 3 降级因子之比和优先级平方根倒数之比 比值 图 4 降级因子之比和优先级平方根倒数之比 图 5 系统吞吐量与系统中用户数之间的关系 图 6 是服务提供商的利润 随着系统中用户 数的增加 利润值一开始随之增大 但当系统处 于严重过载状态时 利润值又开始略有下降 造 成这种结果的原因主要是 不同用户的单位价格 是不同的 当出高价的用户让出部分资源供接纳 的低优先级用户使用时 总的利润就会下降 图 6 服务提供商的利润 7 结束语 本文针对多服务类 多优先级的适应多媒体 应用 研究其降级的公平性问题 将降级因子和 用户的全局优先级作为公平指标 提出了降级因 108 通 信 学 报第 28 卷 子加权平方和最小的降级原则 该原则不但考虑 了类间和类内优先级 而且考虑了用户的降级深 度 因此它区别于文献中严格按优先级降级的方 法 它保证了降级首先从低优先级类的低优先级 用户开始 然后逐渐向高优先级类的高优先级用 户扩展 即它总是试图保护高优先级的用户 如 图 2 所示 不像严格按优先级降级的方法 用户 QoS 降级的公平性既依赖于用户的优先级 又依 赖于用户 QoS 的降级深度 它实际上避免了严格 按优先级降级方法中出现的低优先级用户长期处 于饥饿状态的情况 接着 进一步证明 对离散 型适应多媒体应用 降级因子加权平方和最小的 降级原则满足广义的按比例公平性 而对连续型 适应多媒体应用 满足严格意义上的按比例公平 性 最后 主要针对离散型适应多媒体应用 给 出基于量子遗传算法的问题求解方法 结果与理 论分析部分相符 且有非常好的系统吞吐量 但 当系统处于严重过载状态时 服务提供商的利润 略有下降 这与接纳控制策略有关 因为本文重 点不在接纳控制部分 所以只假设只要能 挤出 满足其最小带宽需求的带宽资源就接纳之 有几 种方案可改变这一状况 其一是在接纳新用户时 将系统利润作为约束条件之一 其二是采用动态 价格 在系统处于过载状态时 根据用户所付价 格的高低为其提供相应的确保服务 当然 也可 在接纳时 就根据用户所付价格的高低为其定位 最低的确保服务 不管采用何种策略 资源一定 时 系统提供确保服务的能力总是与其所能接纳 的总用户数成反比 所以 制定策略时要根据实 际需要 做综合考虑 本文给出的量子遗传算法属于集中式求解方 法 对于有基础设施的无线网络是适用的 例如 蜂窝网 本算法可以运行在每一个基站 对于无 基础设施的无线网络 应该采用分布式的求解方 法 另外 由于篇幅所限 本文没有给出连续型 适应多媒体应用的 QoS 降级问题的求解方法 对 于连续型适应多媒体应用 求式 2 的最小值问题 实际上属于多约束条件下的连续函数优化问题 这类问题的求解方法很多 当然也可用量子遗传 算法对其进行求解 只是其编解码方式和更新策 略不同 文献 11 提出一种用于多峰值连续函数优 化的量子遗传算法 可作参考 参考文献 1 张雪 无线移动网中呼叫接纳控制模型分析 J 通信学报 2005 26 8 99 106 ZHANG X A survey on call admission control models in wireless mobile networks J Journal on Communications 2005 26 8 99 106 2 HARTUNG J JACQUIN A PAWLYK J et al A real time scalable video codec for collaborative applications over packet networks A Proceedings of ACM Multimedia C 1998 419 426 3 YEADON N Filters QoS support mechanisms for multipeer communi cations J IEEE Journal on Selected Areas in Communications 1996 14 7 1245 1262 4 DUFFIELD N RAMAKRISHNAN K REIBMAN A Save an algorithm for smoothed adaptive video over explicit rate networks J IEEE ACM Transaction on Networking 1998 6 6 717 728 5 KWON T CHOI Y BISDIKIAN C et al Q