基于FFT计算平稳过程概率密度的改进算法.doc

基于 FFT 计算 平稳过程概率密度的改进算法 白云 喻莉 朱光喜 李立 华中科技大学 武汉光电国家实验室 湖北 武汉 430074 摘 要 在网络流量建模和参数估计的过程中 平稳过程的概率密度计算是一项重要的基础工作 结合 平稳过 程特征函数的数学特性 在以往基于FFT 求解 平稳过程概率密度函数算法的基础上做出如下改进 通过计算自动 选择合适的采样区间和采样间隔 引入扩频进一步降低计算复杂度 实验表明 改进算法比传统算法计算复杂度 更低 并可以有效控制计算误差 关键词 网络建模 平稳过程 概率密度 误差控制 中图分类号 TN711 1 文献标识码 A文章编号 1000 436X 2007 07 0048 06 Improved FFT based alpha stable density approximation algorithm BAI Yun YU Li ZHU Guang xi LI Li Huazhong Science Technology University Wuhan National Laboratory for Optoelectronics Wuhan 430074 China Abstract Approximation of density of stable process is an elementary works in modeling network flow using stable process Combining the mathematical properties of characteristic function of stable process with the traditional approximating algorithm an improved FFT based algorithm was proposed The improved algorithm has 2 noticeable features automatically choosing the sampling space and sampling interval importing frequency expansion Experiments show that it can decrease calculation complexity and effectively control computation error Key words network modeling alpha stable process density approximation error control 1 引言 1 在 20 世纪末 网络业务流建模领域的一个重 大进展是发现并证实了网络业务流具有自相似特性 1 从而在理论上说明了为何传统的泊松模型在数 据通信网络中无法成功应用的原因 在针对网络流 量的自相似特性的研究 使用了基于 平稳过程的 模型 2 它能很好地描述业务流长呈相关性及重尾 特性 3 使用最大似然法对 平稳过程模型进行参 数估计需要计算概率密度函数 而 稳定分布的概 率密度没有解析结果 目前有2 种解决方法 一种 是直接数值积分方法DNI direct numerial integration 收稿日期 2006 07 18 修回日期 2007 05 29 基金项目 国家自然科学基金资助项目 60502023 另一种则是本文研究的基于快速傅立叶变换 FFT 加速计算的方法 直接数值积分 DNI 的理论依据是 Zolotarev 提 出的 M 参数化方法 4 这种方法提出一种分段近 似的数学理论 Nolan 将这种方法进一步发展 5 实现了以概率密度计算为基础的拟合 检验和参 数估计 基于 FFT 的数值计算方法是由 Mittnik 在 1999 年最早提出的 6 这种方法充分利用了 FFT 的加速性能 同时也不存在逼近问题 因而比 DNI 方法误差更小 运算速度更快 但 Mittnik 理 论证明过程复杂 2006 年 Christian Menn 7 使用了 更简单的 第 28 卷第 7 期通 信 学 报Vol 28 No 7 2007 年 7 月Journal on CommunicationsJuly 2007 Foundation Item The National Natural Science Foundation of China 60502023 第 7 期白云等 基于 FFT 计算 平稳过程概率密度的改进算法 49 证明方法 同时归纳了明确的算法 并与基于 DNI 的方法在速度和精度 2 方面进行了比较分析 但不足之处在对于计算的复杂度和精度 只列举 了一些特殊情况进行讨论 本文提出了一种改进的算法 重点对算法中 采样空间和采样精度 2 个自由变量进行讨论 并 给出一般情况下误差控制的解决方法 2 平稳过程 平稳过程的理论最早是由 Paul Levy 和 Aleksander Yankovlevich Khinchine 在 20 世纪二三 十年代发展起来的 目前正广泛应用于网络分析 信号处理 地球物理及金融分析等各个领域 平 稳过程有多种互相等价的定义 8 与本文关系密切 的是特征函数定义 定义 1 一个 平稳过程由 4 个参数确定 记为 各个参数的定义域分别为 XS 和 其特 0 2 1 1 0 R 征函数满足 exp1i signtani1 2 exp1i signlni 1 ttt t tttt 概率密度与特征函数之间的有如下关系 1 exp i d 2 f xttxt 理论上可以通过上面这个积分确定 平稳过程 的概率密度 然而这个积分没有解析结果 直接的 解决办法是用数值方法进行计算 然而这样运算 量大 复杂度高 利用 FFT 可以简化数值运算 3 基于 FFT 的概率密度计算 本节对基于 FFT 进行概率密度计算的方法进 行推导 在归纳总结现有成果的同时 本文提出 传统的积分算法的选取并不能在算法复杂度和计 算误差 2 个方面获得显著的改进 概率密度的数值计算首先要选择一个有限的 区间 称为采样区间 W0 W0 由于特征函数是 绝对可积的 这意味着其收敛性极好 采样区间 以外的部分可以忽略 忽略掉的这一部分称截断 误差 1 0 0 1 1 exp i d 2 W W f xttxt 接下来对上式中的积分进行离散化 1 在采样区间 W W0 W0 内均匀地选取 N 个采样点 采样间隔为 Ws 2W0 N 每个采样点的 位置为 tk kWs W0 其中 k 0 1 N 2 对时域区间 L L0 L0 同样选取 N 个采样 点 精度为 Ls 2L0 N 每个点的坐标为 xn nLs L0 其中 n 0 1 N 通过以上两步可以将概率密度函数的积分式 离散表示为式 1 并称离散化引入的误差为采样 误差 2 1 12s 1 s 12ss 1 0ss000 1 exp i 2 exp i 2 N nkkn k N k k f xtt x W W tknW L nW LkW LW L FFT 算法计算公式是Xn xkexp 2 i N nk 对比 式 1 若令关于 n k 两个变元的乘积项完全相等 由此可以得出对 W0 Ws L0 Ls这一系列变量选 取的一个限制条件 2 ss000s s0 2 2 W LNW LNW L W L 同时根据 FFT 优化算法的条件 假设 3 2 2 m Nm 将式 2 式 3 代入式 1 同时暂时忽略 2 个 误差项 得到 0 1 0 1 0 1 0 2 expii i i 2 exp i expi exp i 2 2 expi 2 1 1 exp i 1 FFT 1 N nk k N k k N nk k k nk k WN f xtnknk NN WN ntk N nk N W tnk NN W t N 这样便可以利用FFT 算法对概率密度函数进行 50 通 信 学 报第 28 卷 加速计算 可以总结出FFT 计算密度函数的一般过 程 是 1 选取截止频率 W0和采样精度 Ws 2 计算采样空间 W W0 W0 内均匀的 N 个 采样点序列 tk及相应的 tk 3 对特征函数进行前处理 1 k kk t 4 对前处理结果进行快速傅立叶变换 FFT nk f 5 对 FFT 结果进行后处理 0 1 n nn W ff N 由于非负 也可以表示成为 最后 n f 0 nn W ff N 注意每个的横坐标为 n f 00 2 n NN xn WW 传统的方法希望通过选取合适的积分算法来 提高精度 根据采样点的选取不同 文献 7 中总 结了左值积分 右值积分 中值积分和 Simpson 积分几种方法 表 1 给出了不同积分方法的对比 不考虑 Simpson 积分 各种算法只在 前处理 和 后处理 两步稍有差异 表 1 过程密度函数各种积分方法的计算过程 积分方法积分计算方法前处理公式后处理公式 左值积分 kk f tt 1 k kk t 0 nn W ff N 中值积分 1 2 kk k tt ft 1 1 2 kkk k tt 0 exp i nn W fn f NN 右值积分 1 kk f tt 1 1 k kk t 0 2 exp i nn W fn f NN 式 2 中互为等价的 4 个关系式是使用 FFT 方 法的限制条件 说明了 W0 Ws L0 Ls这 4 个变 量之间的相互制约关系 FFT 计算过程中 虽然有 W0 Ws L0 Ls N 这一系列变量 但由于频域 时域等分采样和式 2 的这 3 个限制条件 其实仅 有 2 个自由度 本文选定自由变量为 W0和 N 目 前 FFT 计算概率密度的问题主要表现为这 2 个自 由度没有较好的选取准则 因此通常采用确定值 或者增大了计算复杂度 或者降低了计算精度 4 算法改进 目前为止一个非常显著的问题是 上面推导 的基于 FFT 计算 稳定过程概率密度的算法实际上 与 稳定过程没有多少联系 如果将 过程换成其 他随机过程 对第 3 节中的推导没有任何影响 本文的基本想法是将计算过程结合 过程特征函数 的具体性质 使算法得到改进 前面提到截止频率W0和采样总数N 是2 个自由 变量 当W0越大 在采样区间W W0 W0 以外丢 弃的积分项越小 从而最终结果的截断误差 1也会越 小 另一方面 采样总数N 越大 则对采样区间的 离散化越接近于实际的连续函数积分 使得采样误差 2越小 在现有文献的实验数据中 W0 N 2 个自由 变量一般是预设的 如果预设值偏大 计算量将 呈 2n递增 如果预设值偏小 概率密度曲线可能 发生明显失真 通过反复实验可以发现 当 W0 N 达到某个临界值后 继续地加大对结果误 差影响不大 反而增加计算量 本文从确定误差 限的角度出发 针对不同的 平稳过程动态的确定 截止频率 W0和采样总数 N 从而最大限度地提高 算法效率 4 1 选择截止频率 首先定义 2 个引理 引理1 过程的概率密度函数 S 其中 1 d 2 f xH t xt exp H t xt cossigntan 2 txttt 这是因为 f x 必然为实数 而 H t x Re t exp itx 引理 2 exp 1H t xtB t 第一个不等号是因为 cos W0时 H t x B t 1 也就是说 特征函数在 W0 W0 的这一部分 其 H t x 的绝对值都是小于 1的 进一步的分析可 以看出 其1 000 1 1 1 d dd 2 t WWW t H t xtB ttt C 中 最后这个积分式具有第二类欧拉积 e1C 分的形式 因此积分式呈收敛于 0 1 n 注 稳定过程参数为 1 2 1 2 2 图 1 引理 2 示意图 B t 为 H t 的包络 通过以上分析 由 B W0 1来确定一个频率 如果 1足够小 则 W0这个频率以外的 H t x 将很 快由于 B t 的限制收敛到 0 W0 B 1 1 可以理想的 作为截至频率 即 4 1 1 0 lg 2 W 图 2 给出的实验数据用本文式 4 选取截止 频率的实际效果 图 2 中首先用虚线绘制出对于 参数为 1 2 0 1 0 的 稳定过程概率密度函数曲 线作为参照 而小圆圈则是使用 FFT 算法计算出 来的采样点 在图 2 中人为地选择不同的截止频 率 W0 在图 2 a 图 2 b 中可以观察到明显 的偏差 而图 2 c 是根据式 4 计算出的 W0 计算结果精确地落在了基准线上 而图 2 d 中进一步加大 W0时 计算结果没有明显改 进 注 图中稳定过程参数为 1 2 0 1 0 式 4 计算出的 W0 3 868 1 图 2 截止频率的选取示意图 4 2 选择采样精度 若将每个采样区间记为 Bk tk tk 1 这些 Bk 将 W0 W0 区间均匀的分割 总的采样误差 2是由 每一个区间的采样误差累积而成的 参照引理 1 知道实际上积分是对函数进行的 有如下 R t x 引理 引理 3 当采样区间 Ws足够小时 采样误差 s 21 2 W 引理 3 可简易证明如下 0 0 1 2 0 1 0 0 001 2 d d d k k N k B k N t B k W W H t xH txt Hxt t tH t xt H Wx HWxtB Wt 引理 3 说明 采样间隔 Ws与采样区间相比 相对次要 计算误差更大程度上是由 W0的选取 决定的 为了确定采样间隔的选取 进行了如下 实验 对于固定的模型参数 分别做出采样数量 N 2m与最大均方误差 MSE 为 和最大绝对误差 MLE 为 2 t f xfx 的关系图 其中 t x 表示采样空 t f xfx 52 通 信 学 报第 28 卷 间为 W0 采样数量为 N 2m的 FFT 计算结果 如 图 3 所示 图 3 中对比了 FFT 算法计算不同 平 稳过程时的误差 首先需要一个相对精确的标准 值 实验中是使用直接数值计算求解的 同时利 用第 4 1 节的结论 由 1 10 5计算截止频率 W0 并从 2W0 2W0 均匀采样 采样间隔 Ws为 10 3 在讨论的范围内 这个值可以认为是真实 值 为考察不同的 平稳过程 在图 3 d 还使 用了一个偏斜 0 参数模型 从图 3 中可以看出 当采样精度到 210左右时 继续加大采样点的数量对结果已经没有明显改善 因此可以将采样精度确定在 210 文献中这个值通 常被固定在 216 因此本文方法可以大大降低计算 复杂度 4 3 扩频 从图 3 中可以进一步看出 采样误差不会无 限制减小 这对于 FFT 算法的应用是一个坏消息 的 如何将计算误差减小 同时又不引入无谓的 计算量 本文使用类似扩频的技术 图 3 采样数量与结果误差关系图 因为在预设 1并根据截止频率选择公式计算出 W0以后 在 W0 W0 以外的 R t x 数值均小于 1 如果 1足够小 可以认为这些 R t x 就是 0 这样 在保证 W0 W0 区间上采样总数不变的情况下 可以不引入新的计算量的将采样区间从 W0 W0 扩展到 2W0 2W0 这种处理与一般信号处理中的 扩频非常类似 从图 4 描述的实验可以看出扩频的显著效果 这个实验中的标准数据仍然采用扩大截止频率 加大采样精度的直接数值计算获得 可以明显看 到 MSE 和 MLE 的计算误差均有显著减小 MLE 在扩频前后相差 2 个数量级 因此无法画出图形 第 7 期白云等 基于 FFT 计算 平稳过程概率密度的改进算法 53 只能列出实验数据 实验中使用的 平稳过程参数 为 1 5 1 1 0 可以验证扩频算法对其他 平稳过 程也可以起到显著地降低误差的效果 图 4 扩频后误差减小 需要说明的是 扩频算法并不增大计算复杂 度 也不会加大采样精度 恰恰相反 实验中对 于相同的 m 未扩频算法与扩频算法进行 FFT 计 算时样本数量均为 2m 这样对于截止频率内的区 间 W0 W0 扩频算法的采样精度只有 2m 1 因此 扩频算法反而降低了 前处理 的计算复杂度 图 4 描述的对比实验不仅证实了扩频确实可以提 高 FFT 算法的精度 同时也从另一个侧面证实了 引理 3 采样精度对最终误差效果的改进贡献不大 5 结束语 平稳过程正在越来越多地被应用到各领域学 术前沿 通过对已有基于 FFT 计算 平稳过程概率 密度函数的研究成果进行分析时发现 目前的方 法其实没有利用 平稳过程的性质 因此有进一步 改进的空间 本文结合 平稳过程特征函数的分析 通过理论推导和实验的方法提出确定截止频率和 选择采样精度 2 个问题的解决办法 并首次提出 通过扩频进一步改善计算结果误差的技术 大量 的实验结果验证了改进方法可降低复杂度 同时 有效减小误差 目前本文描述的方法已经应用到 对基于 平稳过程的多媒体网络流量模型的参数估 计中 取得了良好的效果 参考文献 1 LELAND W TAQQN M WILLINGER W et al On the self similar nature of ethernet traffic extended version J IEEE ACM Transactions on Networking 1994 2 1 1 15 2 GALLARDO J R MAKRAKIS D BARBOSA L O Use of alpha stable self similar stochastic processes for modeling traffic in broadband networks A Proceedings of 1998 SPIE Performance and Control Conference C Boston MA 1998 281 296 3 GE X H ZHU G X ZHU Y T An improved modeling for network traffic based on alpha stable self similar processes J Journal of Electronics 2003 12 4 494 498 4 ZOLOTARE