一種新的實時動態(tài)信息數(shù)據壓縮模型-科技論文

隨著多媒體數(shù)據技術及壓縮方法的改進，MPEG-4隨后也被提出來，MPEG-4的研究分為基于數(shù)據和基于模型兩種。基于數(shù)據的研究方法主要有：邊緣檢測、區(qū)域生長、聚類法、松弛法；基于模型的方法主要有：Kass提出的Snake模型、Bhandarkar提出的組合優(yōu)化模型、Klinker提出的物料模型和MRF統(tǒng)計模型。

針對數(shù)據庫存儲背景下的數(shù)據壓縮算法，基于小波理論的數(shù)據壓縮研究成為熱門的研究領域之一， 因為小波Mallat算法不僅可以把數(shù)據按多尺度的方式進行分解，形成較為簡單

的形式存儲，而且還可以減少空間的利用率。其主要思想是：把要存儲的原始數(shù)據按小波Mallat方法進行分解，把分解的結果按MainPart和Relationship進行存儲；然后再對第一次分解的結果MainPart再重復Mallat分解，直到滿足原先既定的要求為止。

小波Mallat分解首先定義數(shù)據源： ，數(shù)據關系函數(shù)： 以上 ；再定義數(shù)據源與Mallat分解方法的參數(shù)集的小波函數(shù) ， 為任意的整數(shù)。Mallat算法把數(shù)據源加在尺度方程和構造方程上，對于任意的數(shù)據源函數(shù)： ， ，變換成以下方程組的形式：

通過變換后的方程，利用小波的變換形成正交和分解關系，最后建立數(shù)據源與變換系數(shù)和小波系數(shù)的關系。

目前國內外對實時動態(tài)信息處理技術的研究工作主要集中在對處理的準確性、速度、復雜度等方面，目前粒子群優(yōu)化算法（PSO）[1]、蟻群算法、AR（p）模型[2]、數(shù)據倉庫等等技術[3][4][5]。Mark Palemer 總結了七種常用的對 RFID 實時動態(tài)數(shù)據處理的方法[6]，文獻[7]提出一種新的實時隊列理論模型，包括對象實時請求隊列，定時響應機制，這些方法經過模型分析，可以滿足對數(shù)據實時性管理的要求，該文還提出Heavy Traffic理論模型在實時數(shù)據中的應用，也取得了預期的效果；文獻[8]提出可變形模型對實時數(shù)據進行處理，對不確定性系統(tǒng)利用定義的FEM方法，把彈力系統(tǒng)理論應用到實時數(shù)據處理當中；時空結合的實時處理技術在文獻[9]中提到，使用緊度公式建立的模型，對多維時空性實時數(shù)據處理取得良好的實驗結果。實時動態(tài)信息處理技術是各國軍事部門、安全部門、航天部門等研究的熱點和重點，因此本課題研究的主要內容包括實時動態(tài)信息的表征，復雜場景下實時動態(tài)信息的視圖呈現(xiàn)結構，多維實時動態(tài)信息復雜度優(yōu)化等問題。

目前海量信息的處理技術主要包括從存儲體系結構方面著手研究，近年來，人們提出了一種“替代層次式”結構的分布式系統(tǒng)體系結構         – Peer-to-peer 結構，分布式文件系統(tǒng)下一步的一個重要發(fā)展方向就是建立基于 peer-to-peer 結構的系統(tǒng)，以克服傳統(tǒng)分布式文件系統(tǒng)的缺陷。文獻[12]提出一種最佳匹配最近鄰域的方法，對海量數(shù)據進行無監(jiān)督自主分類；NN Searching 也稱為相似匹配，或者相似查詢，在文獻[13]中提出，該方法適用在特殊領域內的海量數(shù)據挖掘。文獻[11]對隱性數(shù)據處理及數(shù)據編碼理論進行了深入的分析，Jaccard指數(shù)、標化因子和普性常數(shù)在海量數(shù)據處理中用來評估基類相似度， [12]對相關的隱性研究環(huán)境和背景進行了擴展，加入了適度因子參照，文獻[10]對離散海量數(shù)據集處理進行了研究，提出利用根標圖或者樹的方法來處理該類數(shù)據，空間結構理論和Hybrids維提出來處理相關的海量數(shù)據，取得了單元點匹對性。

事件驅動的可重構技術是目前一個較熱的研究領域，而基于RFID技術的復雜事件驅動實時信息管理系統(tǒng)更是近兩年各國科學家研究的重點，在國外事件驅動已經研究得非常深入，新理論的涌現(xiàn)為復雜事件處理提出了新的挑戰(zhàn)。[14]提出了一種基于復雜事件在 RFID 環(huán)境中應用的模式，描述了若干業(yè)務場景，并結合     EPCGlobal 提出的 ALE 架構描述了應用模型。在文章[16]中，提出了基于時間約束的RFID 事件模型，但是該文章缺少具體的實現(xiàn)框架。自從 90 年代起，對于主動數(shù)據庫的研究促進了復雜事件處理的發(fā)展。目前對于復雜事件查詢語言的研究，發(fā)布者/訂閱者模型主要關注的基于單個事件的主題和預設條件的事件過濾，數(shù)據流處理語言又缺少對于事件流中未發(fā)生事件的查詢處，而專門為主動數(shù)據庫研究開發(fā)的復雜事件處理語言又缺少對于事件屬性值的比較的支持。[15]提出了一種能夠彌補上述不足的針對 RFID 事件處理開發(fā)的 SASE 語言。

復雜事件數(shù)據自動檢測技術的關鍵是復雜事件處理器的設計，復雜事件處理器必須能支持對數(shù)據流的連續(xù)及長效操作，對引擎和查詢語言的要求較高，目前國外主要采用的方法有：對單一任務的實時監(jiān)控，數(shù)據傳輸規(guī)則及數(shù)據獲取技術的改善，集成數(shù)據流及數(shù)據庫查詢方法，參考文獻[10]介紹了一個系統(tǒng)的體系結構及與其它系統(tǒng)的集成方式，介紹了如何采用 Filter 和 smooth 對數(shù)據進行檢測，B．Yijian etc     用 ESL（Expressive Stream Language），UDA（User-defined Aggregates），DSMS（Data Stream Management）方法構成 SMA（Stream Mill Architecture）利用服務器來檢測數(shù)據流[14]。文獻[15]介紹了一種基于Wireless Sensor Network (WSN)的復雜事件處理機，通過過濾機制、聚類組合、復雜重組等對復雜事件中間件理論進行了研究。文獻[16]定義了事件處理語言，用來完成對復雜事件的定義；文獻[17]相關集用在定義復雜事件上，而且給出了相關集解析方式。文獻[18]將系統(tǒng)數(shù)據看作不同類型的事件，通過分析事件間的關系如：成員關系、時間關系以及因果關系等，建立不同的事件關系庫，利用事件間的關聯(lián)、事件提取以及事件分層等技術，從多個事件中提取有意義的復雜事件，使系統(tǒng)的不同使用者提取各自需要的信息，這些信息可是低層的處理數(shù)據，也可以是更高一級的管理數(shù)據。

小波分解算法對于處理實時動態(tài)數(shù)據還處于研究階段，對于促進以上制造業(yè)的數(shù)據存儲及以后的應用都有很大的引導及鋪墊作用。

2、問題模型

首先假設數(shù)據流函數(shù) ，先將數(shù)據流信號進行小波變換，按以下的形式把數(shù)據流函數(shù)進行分解：

根據多分辨分析思想，數(shù)據流的分解過程實際上是尺度變換 和小波變換 之間的關系，它們具有相互依賴的關系，具體的依賴關系如下所示（參數(shù) 為時間）： 。

第二步，對數(shù)據流進行空間的分解，所謂空間分解即是把數(shù)據流的復雜度從高階空間逐步分解到低維空間進行解析，這樣不僅可以把問題的空間復雜度降低，另一方面是把解決該問題的時間復雜度降低。按Mallat算法空間分解思想，可以得到分解過程和空間分解關系如下，其中Date Relation是數(shù)據流關系集，表示數(shù)據流中數(shù)據與數(shù)據之間各維關系，比如時間先后、因果、邏輯推理等等：

第三步進行系數(shù)的分解過程，系數(shù)的分解過程是其中最重要的一步，所有的數(shù)據通過實時動態(tài)的關系聯(lián)系在一起，系數(shù)一方面用來說明這些數(shù)據的內在聯(lián)系，另一方面，通過對系數(shù)的分解來壓縮存儲的數(shù)據量，最重要的是通過系數(shù)的分解后，數(shù)據的邏輯性更強，數(shù)據顯性更突出。具體的分解過程如下圖所示，圖中， 表示原始數(shù)據的系數(shù)關系， 表示須分解到的低級空間，H， G分別表示 和 ， 和 之間的關系信號圖 1：系數(shù)分解過程

這樣分解以后，我們可以得到分解算法的公式，如下，其中condition()是關系信號集，表示轉換之間的信號，當還原時須按此信息將數(shù)據進行還原：

        （1）

3、求解方法及分析結果

3.1模型求解

該模型的求解分為以下幾個步驟：（1）信號的重建；（2）空間的重建；（3）系數(shù)的重建；模型的求解過程其實是分解的逆向過程，即：用小波變換對原始數(shù)據流進行變換后，主要的信息通過分解后存放在不同的分解空間里，對這些分解空間的信息進行還原是該模型解的關鍵，因為小波分解后的存儲信息大大減少，其中數(shù)據與數(shù)據之間的關系另存在關鍵集中 ，因此模型求解的過程就是結合數(shù)據關系集，然后通過重建還原 ，變成原始的數(shù)據流 ，以達到數(shù)據壓縮存儲的目的。大數(shù)據量通過小波變換后可以存儲主要的信息及信息之間的關系 ，重建的過程也就是數(shù)據關系的重建及數(shù)據的釋放，基于該模型的求解如下所示：

（1）信號的重建過程：

（2）空間重建過程：

（3）系數(shù)重建過程， ：

在追求高壓縮比的基礎上，還應該兼顧其它的方面，例如小波分解次數(shù)，計算時間、重構時間、關系復雜性定義等，所以小波基的正則性階數(shù)應該取合適的值。該值決定了該模型的計算量及數(shù)據壓縮比，從一般意義上來說，正則性越大，則數(shù)據流的壓縮性越大，但針對實際問題來說不能一味追求階數(shù)的最大，因為輸出結果會隨著變換系統(tǒng)的增加出現(xiàn)不連續(xù)性。特別是針對實時動態(tài)數(shù)據的壓縮存儲，其中的數(shù)據量較大，計算機性能要求較高，因此本實驗的樣本數(shù)據實驗取于一大型制造業(yè)企業(yè)信息化系統(tǒng)的數(shù)據存儲作為測試數(shù)據，該系統(tǒng)的數(shù)據是實時從制造現(xiàn)場采集上來，該數(shù)據包括設備數(shù)據、設備加工數(shù)據、員人數(shù)據、物流數(shù)據、訂單數(shù)據等等，我們采用以上的模型進行數(shù)據的存儲測試，通過數(shù)據模型模擬將得到最合適的階數(shù)，用以達到最佳的壓縮存儲。

3.2實驗結果及分析

先對測試數(shù)據進行整理，對原數(shù)據流小波分解后的系數(shù)進行排序，其中發(fā)現(xiàn)，大多數(shù)的小波能量都集中在少數(shù)的小波系數(shù)上。因此分別采用取所有分解尺度和按多尺度的方法，按上面的模型進行壓縮和分解。

分析結果如下表所示：

由上表可知，對于大數(shù)據量的壓縮，通過多尺度的分解實驗表明，在相同的數(shù)據量下，通過多層的小波分解對于壓縮的結果是不同的，四層的小波分解后得到的壓縮比是最高的，但是隨著分解層次越來越大，壓縮比反而越小，因此最合適的分解層數(shù)是四層，按以上的數(shù)據模型可以得到最佳的壓縮比和最小的數(shù)據存儲容量。下圖1利用MABLAB仿真對測試數(shù)據進行分析，在實時動態(tài)數(shù)據傳輸量為1G的情況下，分別對數(shù)據進行一層，二層，四層，四層，五層，六層Mallat小波分解，分解后的數(shù)據存儲如圖1左圖所示，存儲量有一定的壓縮比。圖1右圖顯示存儲關系集所需要的空間增長，隨著分解次數(shù)的增加，關系集也越來越大，但是與算法壓縮后的數(shù)據存儲量比，存儲關系所花的空間開銷并不算特別大，因此，該算法具有一定的應用意義。

圖1：數(shù)據量及關系集

4、結束語

本文就制造業(yè)企業(yè)信息化系統(tǒng)數(shù)據存儲這一問題展開討論與研究，采用小波變換多層分解的形式，提出一種通用數(shù)據壓縮算法，該算法通過對數(shù)據流的多層分解、空間多層分解、參數(shù)多層分解后，形成按時間為線索的數(shù)據壓縮流，保存數(shù)據。通過實驗表明，該算法在有限的空間內分解結果良好。

但是本算法還存在一些不足，例如算法的健壯性、實際應用中參數(shù)的考慮問題及數(shù)據流形式的表示中參數(shù)的選擇問題，這些問題在實際的應用過程中可能更加復雜，因此，通過改進函數(shù)的參數(shù)及表達式，都可以把這類問題進行擴展，為后續(xù)的研究工作作基礎。

參考文獻：

【1】Zang,C.,& Fan, Y. Complex event processing in enterprise information systems based on               RFID. Enterprise Information Systems,2007, 1(1),Page 3-23.

【2】Roozbeh Derakhshan,Maria E. Orlowska and Xue Li, RFID Data Management: Challenges and Opportunities[J].IEEE International Conference on RFID Gaylord Texan Resort,Grapevine,TX,USA,2007,Page 175-182.

【3】H.Gonzalez, J.Han, X.Li, and D.Klabjan. Warehousing  and analyzing massive RFID  data sets. In   Proc of the international   conference on data engineering(ICDE06), 2006, Page 1-10.

【4】H.Wang and P.liu. Temporal management of RFID data. Proceeding of the VLDB05,2005, Page 1128-1139

【5】Y.C. Fung. Foundations of Solids Mechanics. Prentice-Hall, 1965.

【6】Gilles Debunne, Mathieu Desbrun, Marie-Paule Cani et al. Dynamic Real-time Deformations using Space & Time Adaptive Sampling, ACM SIGGRAPH, 2001, Page 12-17.

【7】Murtagh, F.; and Heck, A. Multivariate Data Analysis, Kluwer Academic, Dordrecht,1987.

【8】Arabie, P.; Hubert, L. J.; De Soete, G.; Eds.,Clustering and Classification, World Scientific, Singapore, 1996.

【9】Arabie, P.; Hubert, L. J. An Overview ofCombinatorial Data Analysis, in Arabie, P.; Hubert, L. J.; De Soete, G. Eds, Clustering and Classification, World Scientific,Singapore, 1996, 5.

【10】Bentley, J. L.; Friedman, J. H.IEEE Transactions on Computers, 1978, C-27, 97.

【11】Broder, A. J. Pattern Recognition, 1990, 23,171.

【12】Fionn Murtagh. Clustering in Massive Data Sets. Chemical Data Analysis in the Large, 2000, Bozen, Italy. Page 28-51.

【13】F.Wang and P.Liu, “Temporal Management of RFID Data”,In Proc.31st VLDB Conf., 2005,Page 1128–1139.

【14】Weixin Wang, Jongwoo Sung, Daeyoung Kim. Complex Event Processing in EPC Sensor Network Middleware for Both RFID and WSN. 11th IEEE Symposium on Object Oriented Real-time Distributed Computing (ISORC), 2008, Page 165-169.

【15】Liang Dong, Dong Wang, Huanye Sheng, “Design of RFID Middleware Based on Complex Event Processing”,IEEE conference on Cybernetics and Intelligent Systems,2006.

【16】Kaushik Dutta, Krithi Ramamritham, Kamlesh Laddhad,Karthik B. “Real-Time Event Handling in an RFID Middleware System” Workshop on Databases in Networked Information Systems (DNIS) 2007.

【17】Lars Brenna , Alan Demers , Johannes Gehrke , Mingsheng Hong , Joel Ossher , Biswanath Panda , Mirek Riedewald , Mohit Thatte , Walker White, Cayuga: a high-performance event processing engine, Proceedings of the 2007 ACM SIGMOD international conference on Management of data, June 11-14, 2007.

【18】Huang G.Q., Zhang, Y.F., Jiang, P.Y., 2007, RFID-Based Wireless Manufacturing for Walking-Worker Assembly Islands with Fixed-Position Layouts, International Journal of Robotics and Computer Integrated Manufacture, Vol 23/4 , Page 469-477.