基于FFT計算平穩(wěn)過程概率密度的改進算法.doc

基于 FFT 計算 平穩(wěn)過程概率密度的改進算法 白云 喻莉 朱光喜 李立 華中科技大學 武漢光電國家實驗室 湖北 武漢 430074 摘 要 在網(wǎng)絡(luò)流量建模和參數(shù)估計的過程中 平穩(wěn)過程的概率密度計算是一項重要的基礎(chǔ)工作 結(jié)合 平穩(wěn)過 程特征函數(shù)的數(shù)學特性 在以往基于FFT 求解 平穩(wěn)過程概率密度函數(shù)算法的基礎(chǔ)上做出如下改進 通過計算自動 選擇合適的采樣區(qū)間和采樣間隔 引入擴頻進一步降低計算復(fù)雜度 實驗表明 改進算法比傳統(tǒng)算法計算復(fù)雜度 更低 并可以有效控制計算誤差 關(guān)鍵詞 網(wǎng)絡(luò)建模 平穩(wěn)過程 概率密度 誤差控制 中圖分類號 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 世紀末 網(wǎng)絡(luò)業(yè)務(wù)流建模領(lǐng)域的一個重 大進展是發(fā)現(xiàn)并證實了網(wǎng)絡(luò)業(yè)務(wù)流具有自相似特性 1 從而在理論上說明了為何傳統(tǒng)的泊松模型在數(shù) 據(jù)通信網(wǎng)絡(luò)中無法成功應(yīng)用的原因 在針對網(wǎng)絡(luò)流 量的自相似特性的研究 使用了基于 平穩(wěn)過程的 模型 2 它能很好地描述業(yè)務(wù)流長呈相關(guān)性及重尾 特性 3 使用最大似然法對 平穩(wěn)過程模型進行參 數(shù)估計需要計算概率密度函數(shù) 而 穩(wěn)定分布的概 率密度沒有解析結(jié)果 目前有2 種解決方法 一種 是直接數(shù)值積分方法DNI direct numerial integration 收稿日期 2006 07 18 修回日期 2007 05 29 基金項目 國家自然科學基金資助項目 60502023 另一種則是本文研究的基于快速傅立葉變換 FFT 加速計算的方法 直接數(shù)值積分 DNI 的理論依據(jù)是 Zolotarev 提 出的 M 參數(shù)化方法 4 這種方法提出一種分段近 似的數(shù)學理論 Nolan 將這種方法進一步發(fā)展 5 實現(xiàn)了以概率密度計算為基礎(chǔ)的擬合 檢驗和參 數(shù)估計 基于 FFT 的數(shù)值計算方法是由 Mittnik 在 1999 年最早提出的 6 這種方法充分利用了 FFT 的加速性能 同時也不存在逼近問題 因而比 DNI 方法誤差更小 運算速度更快 但 Mittnik 理 論證明過程復(fù)雜 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 計算 平穩(wěn)過程概率密度的改進算法 49 證明方法 同時歸納了明確的算法 并與基于 DNI 的方法在速度和精度 2 方面進行了比較分析 但不足之處在對于計算的復(fù)雜度和精度 只列舉 了一些特殊情況進行討論 本文提出了一種改進的算法 重點對算法中 采樣空間和采樣精度 2 個自由變量進行討論 并 給出一般情況下誤差控制的解決方法 2 平穩(wěn)過程 平穩(wěn)過程的理論最早是由 Paul Levy 和 Aleksander Yankovlevich Khinchine 在 20 世紀二三 十年代發(fā)展起來的 目前正廣泛應(yīng)用于網(wǎng)絡(luò)分析 信號處理 地球物理及金融分析等各個領(lǐng)域 平 穩(wěn)過程有多種互相等價的定義 8 與本文關(guān)系密切 的是特征函數(shù)定義 定義 1 一個 平穩(wěn)過程由 4 個參數(shù)確定 記為 各個參數(shù)的定義域分別為 XS 和 其特 0 2 1 1 0 R 征函數(shù)滿足 exp1i signtani1 2 exp1i signlni 1 ttt t tttt 概率密度與特征函數(shù)之間的有如下關(guān)系 1 exp i d 2 f xttxt 理論上可以通過上面這個積分確定 平穩(wěn)過程 的概率密度 然而這個積分沒有解析結(jié)果 直接的 解決辦法是用數(shù)值方法進行計算 然而這樣運算 量大 復(fù)雜度高 利用 FFT 可以簡化數(shù)值運算 3 基于 FFT 的概率密度計算 本節(jié)對基于 FFT 進行概率密度計算的方法進 行推導 在歸納總結(jié)現(xiàn)有成果的同時 本文提出 傳統(tǒng)的積分算法的選取并不能在算法復(fù)雜度和計 算誤差 2 個方面獲得顯著的改進 概率密度的數(shù)值計算首先要選擇一個有限的 區(qū)間 稱為采樣區(qū)間 W0 W0 由于特征函數(shù)是 絕對可積的 這意味著其收斂性極好 采樣區(qū)間 以外的部分可以忽略 忽略掉的這一部分稱截斷 誤差 1 0 0 1 1 exp i d 2 W W f xttxt 接下來對上式中的積分進行離散化 1 在采樣區(qū)間 W W0 W0 內(nèi)均勻地選取 N 個采樣點 采樣間隔為 Ws 2W0 N 每個采樣點的 位置為 tk kWs W0 其中 k 0 1 N 2 對時域區(qū)間 L L0 L0 同樣選取 N 個采樣 點 精度為 Ls 2L0 N 每個點的坐標為 xn nLs L0 其中 n 0 1 N 通過以上兩步可以將概率密度函數(shù)的積分式 離散表示為式 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 若令關(guān)于 n k 兩個變元的乘積項完全相等 由此可以得出對 W0 Ws L0 Ls這一系列變量選 取的一個限制條件 2 ss000s s0 2 2 W LNW LNW L W L 同時根據(jù) FFT 優(yōu)化算法的條件 假設(shè) 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 算法對概率密度函數(shù)進行 50 通 信 學 報第 28 卷 加速計算 可以總結(jié)出FFT 計算密度函數(shù)的一般過 程 是 1 選取截止頻率 W0和采樣精度 Ws 2 計算采樣空間 W W0 W0 內(nèi)均勻的 N 個 采樣點序列 tk及相應(yīng)的 tk 3 對特征函數(shù)進行前處理 1 k kk t 4 對前處理結(jié)果進行快速傅立葉變換 FFT nk f 5 對 FFT 結(jié)果進行后處理 0 1 n nn W ff N 由于非負 也可以表示成為 最后 n f 0 nn W ff N 注意每個的橫坐標為 n f 00 2 n NN xn WW 傳統(tǒng)的方法希望通過選取合適的積分算法來 提高精度 根據(jù)采樣點的選取不同 文獻 7 中總 結(jié)了左值積分 右值積分 中值積分和 Simpson 積分幾種方法 表 1 給出了不同積分方法的對比 不考慮 Simpson 積分 各種算法只在 前處理 和 后處理 兩步稍有差異 表 1 過程密度函數(shù)各種積分方法的計算過程 積分方法積分計算方法前處理公式后處理公式 左值積分 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 個關(guān)系式是使用 FFT 方 法的限制條件 說明了 W0 Ws L0 Ls這 4 個變 量之間的相互制約關(guān)系 FFT 計算過程中 雖然有 W0 Ws L0 Ls N 這一系列變量 但由于頻域 時域等分采樣和式 2 的這 3 個限制條件 其實僅 有 2 個自由度 本文選定自由變量為 W0和 N 目 前 FFT 計算概率密度的問題主要表現(xiàn)為這 2 個自 由度沒有較好的選取準則 因此通常采用確定值 或者增大了計算復(fù)雜度 或者降低了計算精度 4 算法改進 目前為止一個非常顯著的問題是 上面推導 的基于 FFT 計算 穩(wěn)定過程概率密度的算法實際上 與 穩(wěn)定過程沒有多少聯(lián)系 如果將 過程換成其 他隨機過程 對第 3 節(jié)中的推導沒有任何影響 本文的基本想法是將計算過程結(jié)合 過程特征函數(shù) 的具體性質(zhì) 使算法得到改進 前面提到截止頻率W0和采樣總數(shù)N 是2 個自由 變量 當W0越大 在采樣區(qū)間W W0 W0 以外丟 棄的積分項越小 從而最終結(jié)果的截斷誤差 1也會越 小 另一方面 采樣總數(shù)N 越大 則對采樣區(qū)間的 離散化越接近于實際的連續(xù)函數(shù)積分 使得采樣誤差 2越小 在現(xiàn)有文獻的實驗數(shù)據(jù)中 W0 N 2 個自由 變量一般是預(yù)設(shè)的 如果預(yù)設(shè)值偏大 計算量將 呈 2n遞增 如果預(yù)設(shè)值偏小 概率密度曲線可能 發(fā)生明顯失真 通過反復(fù)實驗可以發(fā)現(xiàn) 當 W0 N 達到某個臨界值后 繼續(xù)地加大對結(jié)果誤 差影響不大 反而增加計算量 本文從確定誤差 限的角度出發(fā) 針對不同的 平穩(wěn)過程動態(tài)的確定 截止頻率 W0和采樣總數(shù) N 從而最大限度地提高 算法效率 4 1 選擇截止頻率 首先定義 2 個引理 引理1 過程的概率密度函數(shù) S 其中 1 d 2 f xH t xt exp H t xt cossigntan 2 txttt 這是因為 f x 必然為實數(shù) 而 H t x Re t exp itx 引理 2 exp 1H t xtB t 第一個不等號是因為 cos W0時 H t x B t 1 也就是說 特征函數(shù)在 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 注 穩(wěn)定過程參數(shù)為 1 2 1 2 2 圖 1 引理 2 示意圖 B t 為 H t 的包絡(luò) 通過以上分析 由 B W0 1來確定一個頻率 如果 1足夠小 則 W0這個頻率以外的 H t x 將很 快由于 B t 的限制收斂到 0 W0 B 1 1 可以理想的 作為截至頻率 即 4 1 1 0 lg 2 W 圖 2 給出的實驗數(shù)據(jù)用本文式 4 選取截止 頻率的實際效果 圖 2 中首先用虛線繪制出對于 參數(shù)為 1 2 0 1 0 的 穩(wěn)定過程概率密度函數(shù)曲 線作為參照 而小圓圈則是使用 FFT 算法計算出 來的采樣點 在圖 2 中人為地選擇不同的截止頻 率 W0 在圖 2 a 圖 2 b 中可以觀察到明顯 的偏差 而圖 2 c 是根據(jù)式 4 計算出的 W0 計算結(jié)果精確地落在了基準線上 而圖 2 d 中進一步加大 W0時 計算結(jié)果沒有明顯改 進 注 圖中穩(wěn)定過程參數(shù)為 1 2 0 1 0 式 4 計算出的 W0 3 868 1 圖 2 截止頻率的選取示意圖 4 2 選擇采樣精度 若將每個采樣區(qū)間記為 Bk tk tk 1 這些 Bk 將 W0 W0 區(qū)間均勻的分割 總的采樣誤差 2是由 每一個區(qū)間的采樣誤差累積而成的 參照引理 1 知道實際上積分是對函數(shù)進行的 有如下 R t x 引理 引理 3 當采樣區(qū)間 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與采樣區(qū)間相比 相對次要 計算誤差更大程度上是由 W0的選取 決定的 為了確定采樣間隔的選取 進行了如下 實驗 對于固定的模型參數(shù) 分別做出采樣數(shù)量 N 2m與最大均方誤差 MSE 為 和最大絕對誤差 MLE 為 2 t f xfx 的關(guān)系圖 其中 t x 表示采樣空 t f xfx 52 通 信 學 報第 28 卷 間為 W0 采樣數(shù)量為 N 2m的 FFT 計算結(jié)果 如 圖 3 所示 圖 3 中對比了 FFT 算法計算不同 平 穩(wěn)過程時的誤差 首先需要一個相對精確的標準 值 實驗中是使用直接數(shù)值計算求解的 同時利 用第 4 1 節(jié)的結(jié)論 由 1 10 5計算截止頻率 W0 并從 2W0 2W0 均勻采樣 采樣間隔 Ws為 10 3 在討論的范圍內(nèi) 這個值可以認為是真實 值 為考察不同的 平穩(wěn)過程 在圖 3 d 還使 用了一個偏斜 0 參數(shù)模型 從圖 3 中可以看出 當采樣精度到 210左右時 繼續(xù)加大采樣點的數(shù)量對結(jié)果已經(jīng)沒有明顯改善 因此可以將采樣精度確定在 210 文獻中這個值通 常被固定在 216 因此本文方法可以大大降低計算 復(fù)雜度 4 3 擴頻 從圖 3 中可以進一步看出 采樣誤差不會無 限制減小 這對于 FFT 算法的應(yīng)用是一個壞消息 的 如何將計算誤差減小 同時又不引入無謂的 計算量 本文使用類似擴頻的技術(shù) 圖 3 采樣數(shù)量與結(jié)果誤差關(guān)系圖 因為在預(yù)設(shè) 1并根據(jù)截止頻率選擇公式計算出 W0以后 在 W0 W0 以外的 R t x 數(shù)值均小于 1 如果 1足夠小 可以認為這些 R t x 就是 0 這樣 在保證 W0 W0 區(qū)間上采樣總數(shù)不變的情況下 可以不引入新的計算量的將采樣區(qū)間從 W0 W0 擴展到 2W0 2W0 這種處理與一般信號處理中的 擴頻非常類似 從圖 4 描述的實驗可以看出擴頻的顯著效果 這個實驗中的標準數(shù)據(jù)仍然采用擴大截止頻率 加大采樣精度的直接數(shù)值計算獲得 可以明顯看 到 MSE 和 MLE 的計算誤差均有顯著減小 MLE 在擴頻前后相差 2 個數(shù)量級 因此無法畫出圖形 第 7 期白云等 基于 FFT 計算 平穩(wěn)過程概率密度的改進算法 53 只能列出實驗數(shù)據(jù) 實驗中使用的 平穩(wěn)過程參數(shù) 為 1 5 1 1 0 可以驗證擴頻算法對其他 平穩(wěn)過 程也可以起到顯著地降低誤差的效果 圖 4 擴頻后誤差減小 需要說明的是 擴頻算法并不增大計算復(fù)雜 度 也不會加大采樣精度 恰恰相反 實驗中對 于相同的 m 未擴頻算法與擴頻算法進行 FFT 計 算時樣本數(shù)量均為 2m 這樣對于截止頻率內(nèi)的區(qū) 間 W0 W0 擴頻算法的采樣精度只有 2m 1 因此 擴頻算法反而降低了 前處理 的計算復(fù)雜度 圖 4 描述的對比實驗不僅證實了擴頻確實可以提 高 FFT 算法的精度 同時也從另一個側(cè)面證實了 引理 3 采樣精度對最終誤差效果的改進貢獻不大 5 結(jié)束語 平穩(wěn)過程正在越來越多地被應(yīng)用到各領(lǐng)域?qū)W 術(shù)前沿 通過對已有基于 FFT 計算 平穩(wěn)過程概率 密度函數(shù)的研究成果進行分析時發(fā)現(xiàn) 目前的方 法其實沒有利用 平穩(wěn)過程的性質(zhì) 因此有進一步 改進的空間 本文結(jié)合 平穩(wěn)過程特征函數(shù)的分析 通過理論推導和實驗的方法提出確定截止頻率和 選擇采樣精度 2 個問題的解決辦法 并首次提出 通過擴頻進一步改善計算結(jié)果誤差的技術(shù) 大量 的實驗結(jié)果驗證了改進方法可降低復(fù)雜度 同時 有效減小誤差 目前本文描述的方法已經(jīng)應(yīng)用到 對基于 平穩(wěn)過程的多媒體網(wǎng)絡(luò)流量模型的參數(shù)估 計中 取得了良好的效果 參考文獻 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