Adaptive Distributed Data Stream Management System.pdf

1、傳感器網(wǎng)絡(luò)是一種無線網(wǎng)絡(luò)，它們廣泛應(yīng)用于環(huán)境監(jiān)控、目標(biāo)跟蹤、建筑物安全監(jiān)測、農(nóng)業(yè)精細(xì)化耕種、活火山監(jiān)測、運(yùn)輸業(yè)監(jiān)控、人類活動(dòng)監(jiān)控以及其他監(jiān)控領(lǐng)域。傳感器網(wǎng)絡(luò)的數(shù)據(jù)，其表現(xiàn)形式與傳統(tǒng)的數(shù)據(jù)源完全不同，它們成倍連續(xù)地傳送，是一種快速、時(shí)變、不確定、無限的數(shù)據(jù)流，而且跟歷史信息無關(guān)。
　　 在數(shù)據(jù)流模型中，某些或全部需要被操作的輸入數(shù)據(jù)并不是通過隨機(jī)訪問硬盤或內(nèi)存得到的，它們是以一個(gè)或多個(gè)連續(xù)的數(shù)據(jù)流形式達(dá)到的。數(shù)據(jù)流在幾個(gè)方面與常規(guī)

2、的存儲關(guān)系模型不同。對于數(shù)據(jù)流來說，隨機(jī)訪問特定數(shù)據(jù)是不允許的。數(shù)據(jù)流中的各數(shù)據(jù)元素是在線達(dá)到的，系統(tǒng)并不對來自于一個(gè)或幾個(gè)數(shù)據(jù)流源的各數(shù)據(jù)元素達(dá)到的順序進(jìn)行控制。數(shù)據(jù)流在規(guī)模上有可能是無限大的。當(dāng)數(shù)據(jù)流中一個(gè)數(shù)據(jù)元素被處理完畢，它就會被丟棄或存檔。除非被存放到存儲器中，否則被處理過的數(shù)據(jù)元素不容易被取回。相比于數(shù)據(jù)流的規(guī)模，顯然存儲器的容量是非常小的。
　　 傳統(tǒng)的數(shù)據(jù)庫管理系統(tǒng)及其改進(jìn)版本都無法適應(yīng)對傳感器網(wǎng)絡(luò)數(shù)據(jù)流的有效管

3、理。為此，需要建立一種全新的數(shù)據(jù)流管理系統(tǒng)(DataStreaming Management System-DSMS)，以便處理數(shù)據(jù)流并可對數(shù)據(jù)流進(jìn)行動(dòng)態(tài)、持續(xù)的查詢操作。
　　 傳統(tǒng)的數(shù)據(jù)庫系統(tǒng)并不是設(shè)計(jì)用來處理時(shí)間緊急的一類應(yīng)用問題，它們也缺乏支持實(shí)時(shí)處理或?qū)崟r(shí)交易所需要的特征。而且，傳統(tǒng)的數(shù)據(jù)庫管理系統(tǒng)也不是設(shè)計(jì)用來連續(xù)且快速地載入個(gè)體數(shù)據(jù)項(xiàng)，它們不能直接支持連續(xù)的數(shù)據(jù)查詢，而這恰好是數(shù)據(jù)流應(yīng)用的典型特征。此外，在對高速數(shù)

4、據(jù)流進(jìn)行查詢和其它處理(如數(shù)據(jù)分析和數(shù)據(jù)挖掘)時(shí)，重點(diǎn)關(guān)注的是查詢結(jié)果的近似準(zhǔn)確性和查詢過程的自適應(yīng)性；而傳統(tǒng)的數(shù)據(jù)庫管理系統(tǒng)關(guān)注的重點(diǎn)則是由穩(wěn)定的查詢計(jì)劃所計(jì)算出的精準(zhǔn)答案。如果用于對數(shù)據(jù)流進(jìn)行復(fù)雜且大量的持續(xù)查詢，傳統(tǒng)的數(shù)據(jù)庫系統(tǒng)及其數(shù)據(jù)處理算法在功能上是不能滿足要求的，面對這樣的應(yīng)用問題其數(shù)據(jù)管理和數(shù)據(jù)處理方法在很多方面都需要被重新考慮。
　　 在本文中，針對成倍、連續(xù)、高速以及時(shí)變的數(shù)據(jù)流，我們研究了數(shù)據(jù)管理及查詢處理的

5、相關(guān)問題，將研究重點(diǎn)集中在稱為數(shù)據(jù)流管理系統(tǒng)這種新出現(xiàn)的數(shù)據(jù)庫管理系統(tǒng)技術(shù)上。與傳統(tǒng)的數(shù)據(jù)庫管理系統(tǒng)相比，數(shù)據(jù)流管理系統(tǒng)能夠?qū)?shí)時(shí)進(jìn)入和實(shí)時(shí)離開系統(tǒng)的連續(xù)數(shù)據(jù)流進(jìn)行持續(xù)的查詢，數(shù)據(jù)僅存放在主存儲器上以便處理。這種數(shù)據(jù)流可以是傳感器數(shù)據(jù)、證券市場數(shù)據(jù)或網(wǎng)絡(luò)數(shù)據(jù)流等。
　　 在數(shù)據(jù)庫管理系統(tǒng)領(lǐng)域，一直以來一個(gè)重要的挑戰(zhàn)就是如何最優(yōu)地利用資源以使系統(tǒng)的性能達(dá)到最佳，同時(shí)兼顧、平衡其它因素，如數(shù)據(jù)的可恢復(fù)性和可靠性。數(shù)據(jù)流管理系統(tǒng)也具有

6、這些特征，但它們常常有著不同的側(cè)重點(diǎn)。數(shù)據(jù)流管理系統(tǒng)涉及的是推送式數(shù)據(jù)源(Push-based Sources)，這種數(shù)據(jù)源常常通過在系統(tǒng)中登記過的持續(xù)查詢輸入數(shù)據(jù)流。一般來說，查詢結(jié)果的有效性往往取決于結(jié)果產(chǎn)生的速度。這意味著極小化延時(shí)和極大化數(shù)據(jù)流通量是極為重要的，所以希望能夠?qū)PU執(zhí)行時(shí)間和內(nèi)存使用量降到最小。有很多相關(guān)技術(shù)可以用來達(dá)到這些目的，如刪除不重要的元組以降低系統(tǒng)的負(fù)載(負(fù)載剝離)，對算子的排序進(jìn)行最優(yōu)調(diào)度以減少系統(tǒng)所

7、需要的元組數(shù)量，等等。在這些技術(shù)中，有很多種(如負(fù)載剝離)會大大影響查詢的準(zhǔn)確度，從本質(zhì)上來說也就改變了查詢的原意。因此，有必要研究更準(zhǔn)確的查詢技術(shù)以及系統(tǒng)性能評價(jià)標(biāo)準(zhǔn)，兼顧性能和準(zhǔn)確度兩者之間的平衡，并確保查詢達(dá)到一定程度的準(zhǔn)確性。
　　 在本文中，我們提出了一個(gè)自適應(yīng)分布式數(shù)據(jù)流管理系統(tǒng)(Adaptive Distributed Data Streaming Management System-ADDSMS)的框架，該系統(tǒng)是

8、一個(gè)數(shù)據(jù)流控制接口，它運(yùn)行于分布式數(shù)據(jù)流資源陣列與需要訪問和分析這些數(shù)據(jù)流的終端客戶之間。整個(gè)框架提供了一種數(shù)據(jù)流管理和數(shù)據(jù)流查詢處理的機(jī)制，可為分布式傳感器網(wǎng)絡(luò)數(shù)據(jù)流的在線獲取、管理、處理、存儲以及融合提供支持。
　　 所提出的自適應(yīng)分布式數(shù)據(jù)流管理系統(tǒng)由三個(gè)主要模塊組成：系統(tǒng)管理模塊，數(shù)據(jù)封裝模塊以及查詢處理器模塊。這種系統(tǒng)結(jié)構(gòu)為數(shù)據(jù)流的處理提供了一種分布式方案。
　　 系統(tǒng)管理模塊由三部分組成，包括數(shù)據(jù)流與查詢登記

9、，查詢優(yōu)化器以及查詢分配管理器。其中，最重要的是查詢分配管理器，它采用優(yōu)化過的查詢和費(fèi)用模型作為圖形分配器的輸入。圖形分配器被用來聚類在已知數(shù)量聚類中的各圖形節(jié)點(diǎn)，這些聚類代表查詢執(zhí)行節(jié)點(diǎn)(即查詢處理器模塊)。以輸入數(shù)據(jù)流的特征和操作算子的費(fèi)用模型為基礎(chǔ)，可以計(jì)算出各操作算子的開銷。查詢分配器具有自適應(yīng)性，它可以每隔一定周期自動(dòng)執(zhí)行查詢分配指令。當(dāng)輸入數(shù)據(jù)流的特征改變時(shí)，查詢分配器也會即時(shí)執(zhí)行查詢分配指令，在這種情況下，費(fèi)用模型變得無效

10、。如果由于增加或刪除了某些查詢使得查詢計(jì)劃被修改，那么查詢分配必須重做。此外，當(dāng)某些處理器模塊出現(xiàn)故障時(shí)，在故障期，分配管理器可以在現(xiàn)有的無故障處理器模塊中重新分配查詢計(jì)劃；在故障模塊恢復(fù)正常后，它還可以再次將查詢計(jì)劃重新分配到所有查詢處理器模塊中。
　　 數(shù)據(jù)封裝模塊由兩部分組成。第一部分是數(shù)據(jù)流接口組件，它負(fù)責(zé)從數(shù)據(jù)源(即傳感器網(wǎng)絡(luò))讀入數(shù)據(jù)流。數(shù)據(jù)流接口使用的是一個(gè)網(wǎng)絡(luò)接口，該接口從傳感器網(wǎng)絡(luò)中挑選出數(shù)據(jù)并檢查它們的有效性

11、。如果是有效數(shù)據(jù)，那么該數(shù)據(jù)將從字節(jié)數(shù)組形式解碼成與其匹配的對象類型。然后，數(shù)據(jù)對象會被轉(zhuǎn)換成包含所有類型數(shù)據(jù)字段的記錄對象。對一個(gè)特定數(shù)據(jù)流源的封裝就是將其數(shù)據(jù)轉(zhuǎn)換成一個(gè)統(tǒng)一記錄，該記錄攜帶著數(shù)據(jù)流元素的所有數(shù)據(jù)字段。記錄對象含有數(shù)據(jù)字段的名稱、類型和數(shù)值，所以我們可以在來自于各類數(shù)據(jù)流源的所有各類數(shù)據(jù)流中使用相同的算子模型。數(shù)據(jù)封裝模塊的第二部分是流監(jiān)控組件。為了計(jì)算已登記查詢的費(fèi)用模型，必須獲得輸入流的特征。流監(jiān)控組件的任務(wù)就是為

12、系統(tǒng)收集有關(guān)輸入流的統(tǒng)計(jì)信息并將這些信息發(fā)送到查詢優(yōu)化器和分配管理器。數(shù)據(jù)封裝模塊的這兩個(gè)組件都使用所收集的元數(shù)據(jù)以生成自適應(yīng)分布式查詢。
　　 查詢處理器模塊包含九個(gè)組件：查詢計(jì)劃分析器、算子組態(tài)、算子調(diào)度程序、執(zhí)行引擎、執(zhí)行運(yùn)行監(jiān)控器、連接管理器、流接收器、流發(fā)送器以及存儲管理器。所有這些組件都被集成在查詢計(jì)劃的執(zhí)行之中。此外，非常重要的是這些組件都是按照使整個(gè)系統(tǒng)的性能達(dá)到最優(yōu)的方式來運(yùn)行的。所有這些組件都保持相互通信，這

13、就使得在這些組件之間進(jìn)行切換的開銷可以達(dá)到最小。查詢處理器模塊的核心是算子調(diào)度程序，它是一個(gè)線程，在一組基于查詢計(jì)劃的給定條件下，該程序決定著哪個(gè)算子被執(zhí)行。在內(nèi)核層，線程調(diào)度程序決定著運(yùn)行哪個(gè)算子以及如何在算子之間共享資源(如處理器的時(shí)間和內(nèi)存)。算子調(diào)度的目的是極小化內(nèi)存需求和元組延時(shí)。
　　 查詢分配管理器和算子調(diào)度程序是數(shù)據(jù)流管理系統(tǒng)的主要組件，它們與整個(gè)系統(tǒng)的自適應(yīng)特征密切相關(guān)。
　　 近年來，大規(guī)模監(jiān)控基礎(chǔ)設(shè)

14、施(如無線傳感器網(wǎng)絡(luò))的出現(xiàn)，帶來了如何采用分布式方法處理數(shù)據(jù)流的查詢這樣一個(gè)具有挑戰(zhàn)性的問題。在監(jiān)控網(wǎng)絡(luò)中，數(shù)據(jù)流的查詢必須在系統(tǒng)內(nèi)部采用分布式方法進(jìn)行處理，以便使網(wǎng)絡(luò)中資源受限的各查詢處理器節(jié)點(diǎn)的性能達(dá)到最優(yōu)。此外，在數(shù)據(jù)流高速傳輸?shù)沫h(huán)境下，為能實(shí)現(xiàn)數(shù)據(jù)的高流通量和低延時(shí)，查詢處理的操作算子必須能被自適應(yīng)地配置在查詢計(jì)劃中，以使數(shù)據(jù)移動(dòng)的代價(jià)最小。
　　 在本文中，針對無線傳感器網(wǎng)絡(luò)的數(shù)據(jù)流管理系統(tǒng)，我們提出了一種三級優(yōu)化策

15、略，包括傳感器定位優(yōu)化、查詢分配優(yōu)化以及查詢操作算子最優(yōu)調(diào)度，以最大限度地減少處理數(shù)據(jù)流所需要的資源。
　　 第一級優(yōu)化是針對傳感器部署(即傳感器節(jié)點(diǎn)定位)的優(yōu)化。在無線傳感器網(wǎng)絡(luò)中，傳感器的部署是一個(gè)至關(guān)重要的問題，它對網(wǎng)絡(luò)的建造成本、查詢操作需要處理的數(shù)據(jù)量以及網(wǎng)絡(luò)的監(jiān)測能力都會產(chǎn)生重要影響。在監(jiān)測區(qū)域?qū)Χ鄠€(gè)傳感器實(shí)施最優(yōu)部署，可以使傳感器節(jié)點(diǎn)的數(shù)量達(dá)到最少，而傳感器數(shù)量的減少又有利于減少數(shù)據(jù)流管理系統(tǒng)需要管理的數(shù)據(jù)量。過去

16、雖然有許多研究都曾涉及到這個(gè)問題，但它們大多都假設(shè)監(jiān)測區(qū)域是一個(gè)開放式空間，即傳感器可以部署在該區(qū)域內(nèi)的任何位置上。在本文中，我們考慮的監(jiān)測區(qū)域是一個(gè)有定位約束的區(qū)域，即在區(qū)域內(nèi)的某些位置點(diǎn)是不能部署傳感器的。傳感器定位問題(Sensor Location Problem-SLP)是一個(gè)非線性、非凸規(guī)劃問題，其目的是要確定所有傳感器的安裝位置，以對目標(biāo)區(qū)域?qū)嵤┯行ПO(jiān)控。對傳感器定位的要求是，使用最少的傳感器，而使監(jiān)控覆蓋的區(qū)域達(dá)到最大。

17、
　　 進(jìn)化算法是一類模仿生物世界選擇與進(jìn)化機(jī)制的通用隨機(jī)搜索方法。進(jìn)化算法與其它優(yōu)化算法不同(如爬山算法和模擬退火算法)，它不是依靠一個(gè)解而是通過一組有潛力的候選解組成一個(gè)群體去解決一個(gè)優(yōu)化問題。
　　 一般來說，各種進(jìn)化算法都是基于以下機(jī)制運(yùn)行的。由若干個(gè)體組成一個(gè)群體，然后將群體初始化。每個(gè)個(gè)體都對應(yīng)著優(yōu)化問題一個(gè)可能的解，解的質(zhì)量可以通過一個(gè)適應(yīng)度函數(shù)來評價(jià)。進(jìn)化算法在每一次迭代中，即在進(jìn)化過程的每一代中，都會執(zhí)

18、行選擇操作，該操作會將適應(yīng)度較好的個(gè)體挑選出來并讓它們進(jìn)入到下一代的群體中。使用變異、交叉或其它進(jìn)化操作可以改變個(gè)體。以上過程被不斷重復(fù)，直到算法產(chǎn)生的結(jié)果收斂為止。此時(shí)，可以認(rèn)為由算法找到的最終解就是優(yōu)化問題的最優(yōu)解。遺傳算法(Genetic Algorithm-GA)和粒子群算法(Particle Swarm Optimization-PSO)被認(rèn)為是最重要的兩種進(jìn)化算法。對于許多組合優(yōu)化問題來說，GA和PSO已被認(rèn)為在獲得最優(yōu)解或

19、近似最優(yōu)解方面是最有效的，但它們也存在一些缺陷。目前，已經(jīng)出現(xiàn)了一些混合算法，用來克服GA和PSO的缺陷。研究人員已經(jīng)提出了PSO算法一些改進(jìn)的版本，其中引入了其它進(jìn)化算法的優(yōu)異特性。最近幾年，已有很多學(xué)者研究過如何將選擇、變異、交叉以及各種不同的進(jìn)化機(jī)制結(jié)合進(jìn)PSO算法中。
　　 GA和PSO在它們固有的并行特征方面是非常相似的，然而實(shí)驗(yàn)結(jié)果表明，在求解不同的優(yōu)化問題時(shí)它們又有著各自獨(dú)有的優(yōu)點(diǎn)。我們希望將這兩種算法綜合在一起，

20、以期獲得兩者的優(yōu)異特征。在本文中，我們提出了一種自適應(yīng)混合優(yōu)化算法(Adaptive HybridOptimization-AHO)，該算法采用一個(gè)模糊邏輯控制器作為智能切換開關(guān)，它可以在不同類型的優(yōu)化算法之間按某種規(guī)則進(jìn)行自動(dòng)轉(zhuǎn)換。
　　 在本文中，我們采用了三種進(jìn)化算法來求解傳感器的定位問題，包括粒子群優(yōu)化算法PSO、遺傳算法GA以及我們提出的自適應(yīng)混合優(yōu)化算法AHO。AHO算法包含PSO算法和GA算法。在進(jìn)化過程中，AHO

21、算法通過一個(gè)模糊邏輯控制器(Fuzzy logic controller-FLC)可以自適應(yīng)地在PSO算法和GA算法之間進(jìn)行智能切換。通過改變感應(yīng)模式、傳感器數(shù)量以及監(jiān)控區(qū)域的定位約束，我們分別采用這三種進(jìn)化算法對傳感器部署問題進(jìn)行了多種仿真實(shí)驗(yàn)，對各種條件下由這三種算法所獲得的監(jiān)控區(qū)域覆蓋率和計(jì)算成本都進(jìn)行了比較，結(jié)果表明這三種算法在各種條件下都能獲得好的定位效果。但與PSO算法和GA算法相比，AHO算法由于能夠利用PSO和GA算法各

22、自的優(yōu)點(diǎn)并避開它們的缺點(diǎn)，在二元感應(yīng)模式、指數(shù)衰減感應(yīng)模式以及梯度衰減感應(yīng)模式下，采用AHO算法對傳感器進(jìn)行部署可以獲得最大的監(jiān)控區(qū)域覆蓋率，而且只需經(jīng)過較少代的進(jìn)化AHO算法就能獲得傳感器定位問題的全局最優(yōu)解。
　　 第二級優(yōu)化是針對查詢分配過程的優(yōu)化，其目的是要將多個(gè)持續(xù)查詢以負(fù)載均衡的方式分配到所有查詢執(zhí)行節(jié)點(diǎn)(即查詢處理器模塊)上，并極小化各處理節(jié)點(diǎn)之間的交互通信總量。對數(shù)據(jù)流進(jìn)行一次持續(xù)查詢可以形象地用一個(gè)數(shù)據(jù)流圖來表

23、示。為了在一個(gè)數(shù)據(jù)流管理系統(tǒng)中運(yùn)行多個(gè)持續(xù)查詢，通常的方法是將它們的數(shù)據(jù)流圖統(tǒng)一在一個(gè)查詢計(jì)劃上，然后由一個(gè)查詢執(zhí)行引擎依次執(zhí)行計(jì)劃中的各個(gè)步驟，產(chǎn)生出所需要的查詢結(jié)果。在查詢計(jì)劃中有“節(jié)點(diǎn)”和“邊”這兩個(gè)基本要素，節(jié)點(diǎn)有三類，分別是源節(jié)點(diǎn)(代表數(shù)據(jù)流源)、操作算子節(jié)點(diǎn)(包括選擇算子、連接算子、合并算子、聚合算子、時(shí)間尺度算子以及窗口算子等)以及匯點(diǎn)(代表用戶的應(yīng)用軟件)；而連接兩個(gè)節(jié)點(diǎn)的邊則代表節(jié)點(diǎn)之間的數(shù)據(jù)流。查詢計(jì)劃的這種特征使它

24、可以用一個(gè)有向非循環(huán)圖(稱為查詢圖)來表示，圖中的每個(gè)頂點(diǎn)都代表一個(gè)操作算子，而每條邊則代表數(shù)據(jù)流；在頂點(diǎn)和操作算子之間、邊與數(shù)據(jù)流之間分別構(gòu)成一對一的映射關(guān)系。自適應(yīng)分布式數(shù)據(jù)流管理系統(tǒng)(ADDSMS)的性能完全取決于能否將多個(gè)查詢在可用的各查詢處理器之間實(shí)現(xiàn)均衡的負(fù)載分配以及能否極小化各查詢處理器之間相互通信的影響。在本文中，我們采用了一個(gè)合適的費(fèi)用模型用于查詢計(jì)劃與查詢圖(有向非循環(huán)圖)之間的映射，并根據(jù)“數(shù)據(jù)流處理與監(jiān)測公用系統(tǒng)

25、”(Public Infrastructure for Processing and ExploringStreams-PIPES)中連續(xù)滑窗查詢的語義學(xué)規(guī)則和實(shí)現(xiàn)機(jī)制建立了該模型。PIPES是一種基礎(chǔ)資源，它可以提供構(gòu)建一個(gè)分布式數(shù)據(jù)流管理系統(tǒng)所需的各種基本要素或組件。費(fèi)用模型為每個(gè)操作算子提供了費(fèi)用計(jì)算公式。將一個(gè)操作算子的費(fèi)用計(jì)算公式應(yīng)用到它的輸入數(shù)據(jù)流，就可以計(jì)算出它的輸出數(shù)據(jù)流的特征。對任一數(shù)據(jù)流進(jìn)行查詢，該費(fèi)用模型都會從查詢

26、計(jì)劃圖的數(shù)據(jù)流源開始自底向上依次運(yùn)用費(fèi)用計(jì)算公式計(jì)算出所有中間數(shù)據(jù)流的特征。所產(chǎn)生的查詢圖可以反映出每個(gè)算子的費(fèi)用以及前后算子之間的通信開銷。
　　 為了將多個(gè)持續(xù)查詢以負(fù)載均衡的方式分配到相關(guān)查詢處理器節(jié)點(diǎn)上，可以采用圖形分割算法對查詢計(jì)劃圖中的操作算子群按負(fù)載均衡以及節(jié)點(diǎn)間交互通信量最少的原則進(jìn)行分割。在本文中，我們提出了一種新的蟻群算法，稱為載物相似度螞蟻模型(Similarity CarryingAnt Model，SC

27、AM-ant)，用于求解數(shù)據(jù)流查詢計(jì)劃圖的分割問題。第一個(gè)蟻群聚類算法是由J.L.Deneubourg等人提出的。后來，P.Kuntz、P.Layzell和D.Snyers提出了一種用于圖形分割的蟻群聚類算法，稱為KLS算法，該算法將圖形分割問題嵌入到一個(gè)歐幾里德空間或歐幾里德平面中去考慮。基于蟻群的聚類模型本質(zhì)上是一個(gè)動(dòng)力學(xué)系統(tǒng)，螞蟻可以移動(dòng)查詢圖中的頂點(diǎn)(即操作算子)以完成算子的聚類。各頂點(diǎn)(操作算子)究竟被哪些類吸引、被哪些類拒絕

28、是由頂點(diǎn)與類之間的距離決定的。蟻群聚類算法的提出以及對它所做的改進(jìn)都受到了自然界螞蟻行為的啟發(fā)。關(guān)于螞蟻，人們已經(jīng)發(fā)現(xiàn)的特征之一是，一只螞蟻能夠提起自身重量20～50倍的重物。這種特征已經(jīng)被用來增強(qiáng)蟻群聚類的性能。在我們所提出的螞蟻模型中，一只螞蟻在移動(dòng)過程中具有同時(shí)攜帶多個(gè)物品的能力。這種成組抓一放物品的行為可以減少螞蟻移動(dòng)的次數(shù)，從而達(dá)到減少完成聚類過程所需時(shí)間的目的。在SCAM-ant模型中，每只螞蟻在移動(dòng)過程可以同時(shí)搬運(yùn)多個(gè)對象

29、(頂點(diǎn)，即算子)，數(shù)量由搬運(yùn)對象和候選對象的相似度決定。SCAM-ant算法利用了物群移動(dòng)特性，可以有效減少完成聚類過程所需的時(shí)間，這是對現(xiàn)有的單物搬運(yùn)蟻群聚類算法的改進(jìn)。
　　 為了提供一種適用于數(shù)據(jù)流查詢圖頂點(diǎn)(算子)之間相似度測量的方法，我們提出了一種改進(jìn)的SimRank算法。SimRank原為一種只能確定結(jié)構(gòu)相似性的普通算法。在本文中，我們將SimRank算法與查詢圖中各條邊的權(quán)值相結(jié)合(邊的權(quán)值通過費(fèi)用模型計(jì)算)，得到

30、一種新的相似度測量方法，這種方法可以基于查詢結(jié)構(gòu)和算子之間的內(nèi)部數(shù)據(jù)流反映出算子之間是否具有相似關(guān)系。
　　 為了有效使用SCAM-ant算法完成算子的聚類，我們提出了一種融合SCAM-ant算法的通用模板。采用該模板，算子聚類的最終結(jié)構(gòu)將緊密遵循由這個(gè)模板所定義的構(gòu)型。模板上所有聚類的質(zhì)心是基于用戶需求定義的，并不依賴于被聚類的操作算子的特征空間。
　　 為了測試我們所提出的持續(xù)查詢分配算法的性能，我們使用了兩個(gè)指標(biāo)，

31、即通信開銷和負(fù)載不均衡性。在不同的算子聚類之間總的通信開銷以及在不同查詢處理器節(jié)點(diǎn)之間的負(fù)載不均衡性可以反映出分配策略的優(yōu)劣。
　　 從本文的實(shí)驗(yàn)結(jié)果可以清楚地看出，與KLS算法相比，SCAM-ant算法的性能更好。通信開銷和負(fù)載不均衡性這兩個(gè)指標(biāo)證實(shí)，采用我們提出的SCAM-ant算法，可以在更少的時(shí)間內(nèi)實(shí)現(xiàn)更好的算子聚類。SCAM-ant模型是非常有效的，它能減少螞蟻搬運(yùn)算子所需要的旅行次數(shù)。
　　 我們的實(shí)驗(yàn)結(jié)果也

32、顯示出SCAM-ant算法可以生成負(fù)載均衡性很好的分布式查詢計(jì)劃，具有最小的通信開銷。與光普、線性、散射和多級KL分割算法相比，在分區(qū)數(shù)量不斷增長的情況下，SCAM-ant算法保持負(fù)載均衡的能力更穩(wěn)定。
　　 第三級優(yōu)化是針對查詢操作算子調(diào)度的優(yōu)化，其目的是自適應(yīng)地調(diào)度在查詢處理中將要使用的多個(gè)操作算子。算子的最優(yōu)調(diào)度可以極小化計(jì)算機(jī)內(nèi)存需求以及查詢結(jié)果輸出的延時(shí)。以前，用于調(diào)度數(shù)據(jù)流查詢及其操作算子的方法都假設(shè)每個(gè)算子是以一個(gè)

33、單獨(dú)的線程運(yùn)行，或者所有的算子結(jié)合在同一個(gè)查詢計(jì)劃中像Chain算法[124]一樣用單線程運(yùn)行。這兩種方法都存在線程開銷過大以及因操作費(fèi)時(shí)引起延時(shí)兩個(gè)嚴(yán)重缺陷。以前在某些數(shù)據(jù)流管理系統(tǒng)的調(diào)度中所建立的Chain算法只關(guān)注極小化最大內(nèi)存使用量，而忽視了輸出延時(shí)這一重要方面。當(dāng)輸入的數(shù)據(jù)流激增時(shí)，Chin算法將遭受到元祖匱乏，從而引起高延時(shí)。為了克服這些缺陷，在本文中我們提出了一種新的聚類算子調(diào)度算法(Clustered Operators

34、 Scheduling-COS)。該算法基于各算子的選擇性和計(jì)算開銷自適應(yīng)地將查詢計(jì)劃中的所有算子聚類到不同的組中，并使用S-均值(S-mean)聚類方法計(jì)算開銷。S-均值聚類是基于相似度驅(qū)動(dòng)的聚類方法，它與K-均值方法相似，但兩者存在一些差別。S-均值聚類會將所有的算子組合到一個(gè)新的聚類中，如果這些算子對現(xiàn)有各個(gè)聚類質(zhì)心的相似度的最大值小于給定的閾值。但在K-均值聚類方法中，所有節(jié)點(diǎn)都必須歸到現(xiàn)有的K個(gè)聚類中的一個(gè)，這對那些與其最靠近

35、聚類的相似度非常低的節(jié)點(diǎn)是不公平的。不規(guī)定聚類數(shù)目K的值可以為聚類過程提供高度的自適應(yīng)性。
　　 為了比較不同算子調(diào)度算法的性能，我們采用離散事件仿真系統(tǒng)(Discrete Event Simulation-DES)建立了數(shù)據(jù)處理單元仿真模型。實(shí)驗(yàn)結(jié)果表明，將COS聚類算子調(diào)度算法與傳統(tǒng)的FIFO算法、Chain算法以及多線程算法進(jìn)行比較，在所有仿真條件下COS算法都表現(xiàn)出了更好的性能。此外，在可擴(kuò)展性和魯棒性方面，COS算法也

36、表現(xiàn)得非常好。COS算法還能用高效率的方式使用內(nèi)存和計(jì)算資源，這使得它可以在資源受限的情況下連續(xù)工作，而其它調(diào)度算法此時(shí)卻失去了它們的穩(wěn)定性。實(shí)驗(yàn)評估證實(shí)了COS算法作為持續(xù)查詢處理器具備自適應(yīng)性、靈活性、可靠性、可擴(kuò)展性以及魯棒性。
　　 總體來說，ADDSMS自適應(yīng)分布式數(shù)據(jù)流管理系統(tǒng)是一個(gè)數(shù)據(jù)管理器，它具有自適應(yīng)能力，可被用來處理數(shù)據(jù)流。系統(tǒng)中的每一級優(yōu)化都可以基于數(shù)據(jù)流的特征和用戶的查詢提供一定程度的靈活性。