一種新的實(shí)時(shí)動(dòng)態(tài)信息數(shù)據(jù)壓縮模型

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

針對(duì)數(shù)據(jù)庫(kù)存儲(chǔ)背景下的數(shù)據(jù)壓縮算法，基于小波理論的數(shù)據(jù)壓縮研究成為熱門(mén)的研究領(lǐng)域之一， 因?yàn)樾〔∕allat算法不僅可以把數(shù)據(jù)按多尺度的方式進(jìn)行分解，形成較為簡(jiǎn)單

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

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

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

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

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

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

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

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

2、問(wèn)題模型

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

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

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

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

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

        （1）

3、求解方法及分析結(jié)果

3.1模型求解

該模型的求解分為以下幾個(gè)步驟：（1）信號(hào)的重建；（2）空間的重建；（3）系數(shù)的重建；模型的求解過(guò)程其實(shí)是分解的逆向過(guò)程，即：用小波變換對(duì)原始數(shù)據(jù)流進(jìn)行變換后，主要的信息通過(guò)分解后存放在不同的分解空間里，對(duì)這些分解空間的信息進(jìn)行還原是該模型解的關(guān)鍵，因?yàn)樾〔ǚ纸夂蟮拇鎯?chǔ)信息大大減少，其中數(shù)據(jù)與數(shù)據(jù)之間的關(guān)系另存在關(guān)鍵集中 ，因此模型求解的過(guò)程就是結(jié)合數(shù)據(jù)關(guān)系集，然后通過(guò)重建還原 ，變成原始的數(shù)據(jù)流 ，以達(dá)到數(shù)據(jù)壓縮存儲(chǔ)的目的。大數(shù)據(jù)量通過(guò)小波變換后可以存儲(chǔ)主要的信息及信息之間的關(guān)系 ，重建的過(guò)程也就是數(shù)據(jù)關(guān)系的重建及數(shù)據(jù)的釋放，基于該模型的求解如下所示：

（1）信號(hào)的重建過(guò)程：

（2）空間重建過(guò)程：

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

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

3.2實(shí)驗(yàn)結(jié)果及分析

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

分析結(jié)果如下表所示：

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

圖1：數(shù)據(jù)量及關(guān)系集

4、結(jié)束語(yǔ)

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

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

參考文獻(xiàn)：

【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.