面向海量物聯(lián)網(wǎng)的數(shù)據(jù)處理技術(shù)

1、 數(shù)據(jù)庫(kù)新技術(shù)課 程 報(bào) 告題 目： 面向物聯(lián)網(wǎng)的海量數(shù)據(jù)處理研究 學(xué) 院： 數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院 專 業(yè)： 計(jì)算機(jī)軟件與理論 年 級(jí)： 2012級(jí)1班 學(xué) 號(hào)： 120320042 姓 名： 賈福運(yùn) 成 績(jī)： 摘要 物聯(lián)網(wǎng)近年來(lái)受到人們的廣泛關(guān)注 伴隨各種感知技術(shù)的綜合應(yīng)用，物聯(lián)網(wǎng)所處理的數(shù)據(jù)量較之以往的任何網(wǎng)絡(luò)都巨大，呈現(xiàn)真正意義上的海量特征，如何高效 自動(dòng)智能化地處理這些數(shù)據(jù)是物聯(lián)網(wǎng)亟待解決的關(guān)鍵技術(shù)之一 提出一種基于多級(jí)數(shù)據(jù)處理的嵌入式中間件系統(tǒng)的體系結(jié)構(gòu)，采用數(shù)據(jù)分級(jí)和分布式處理技術(shù)，實(shí)現(xiàn)實(shí)時(shí)信息處理的負(fù)載均衡，并提出當(dāng)今流行的多種數(shù)據(jù)降維算法,從而盡可能多地保留原始信息的基礎(chǔ)上，減

2、少信息處理的數(shù)據(jù)量，從而提高物聯(lián)網(wǎng)應(yīng)用系統(tǒng)的整體效率.關(guān)鍵詞：物聯(lián)網(wǎng)；海量數(shù)據(jù)；分級(jí)處理；降維處理1 引言物聯(lián)網(wǎng)(The Internet of Things，IoT)的概念是1999年提出的。簡(jiǎn)單來(lái)講就是把各類物品通過(guò)射頻識(shí)別(RFID)、傳感器件與設(shè)備、全球定位系統(tǒng)等種種裝置與互聯(lián)網(wǎng)結(jié)合起來(lái)而形成一個(gè)巨大的網(wǎng)絡(luò)，實(shí)現(xiàn)智能化的識(shí)別與管理，進(jìn)而實(shí)現(xiàn)各類物品的遠(yuǎn)程感知和控制，由此生成一個(gè)更加智慧的生產(chǎn)和生活體系1根據(jù)丁明治,高需等人的分析, 物聯(lián)網(wǎng)的以下4個(gè)特點(diǎn)對(duì)數(shù)據(jù)處理技術(shù)形成了巨大的挑戰(zhàn)1：（1）首先物聯(lián)網(wǎng)數(shù)據(jù)的海量性物聯(lián)網(wǎng)系統(tǒng)通常包含著海量的傳感器結(jié)點(diǎn)。其中，大部分傳感器(如溫度傳感器、G

3、PS傳感器、壓力傳感器等)的采樣數(shù)據(jù)是數(shù)值型的，但也有許多傳感器的采樣值是多媒體數(shù)據(jù)(如交通攝像頭視頻數(shù)據(jù)、音頻傳感器采樣數(shù)據(jù)、遙感成像數(shù)據(jù)等)每一個(gè)傳感器均頻繁地產(chǎn)生新的采樣數(shù)據(jù)，系統(tǒng)不僅需要存儲(chǔ)這些采樣數(shù)據(jù)的最新版本，且在多數(shù)情況下，還需要存儲(chǔ)某個(gè)時(shí)間段(如1個(gè)月)內(nèi)所有的歷史采樣值，以滿足溯源處理和復(fù)雜數(shù)據(jù)分析的需要可以想象，上述數(shù)據(jù)是海量的，對(duì)它們的存儲(chǔ)、傳輸、查詢以及分析處理將是一個(gè)前所未有的挑戰(zhàn)(2)傳感器結(jié)點(diǎn)及采樣數(shù)據(jù)的異構(gòu)性在同一個(gè)物聯(lián)網(wǎng)系統(tǒng)中，可以包含形形色色的傳感器，如交通類傳感器、水文類傳感器、地質(zhì)類傳感器、氣象類傳感器、生物醫(yī)學(xué)類傳感器等，其中每一類傳感器又包括諸多具體

4、的傳感器如交通類傳感器可以細(xì)分為GPS傳感器、RFID傳感器、車牌識(shí)別傳感器、電子照相身份識(shí)別傳感器，交通流量傳感器(紅外、線圈、光學(xué)、視頻傳感器)、路況傳感器、車況傳感器等這些傳感器不僅結(jié)構(gòu)和功能不同，而且所采集的數(shù)據(jù)也是異構(gòu)的這種異構(gòu)性極大地提高了軟件開發(fā)和數(shù)據(jù)處理的難度(3)物聯(lián)網(wǎng)數(shù)據(jù)的時(shí)空相關(guān)性與普通互聯(lián)網(wǎng)結(jié)點(diǎn)不同，物聯(lián)網(wǎng)中的傳感器結(jié)點(diǎn)普遍存在著空間和時(shí)間屬性每個(gè)傳感器結(jié)點(diǎn)都有地理位置，個(gè)數(shù)據(jù)采樣值都有時(shí)間屬性，而且許多傳感器結(jié)點(diǎn)的地理位置還是隨著時(shí)間的變化而連續(xù)移動(dòng)的，如智能交通系統(tǒng)中，每個(gè)車輛安裝了高精度的GPS或RFID標(biāo)簽，在交通網(wǎng)絡(luò)中動(dòng)態(tài)地移動(dòng)與物聯(lián)網(wǎng)數(shù)據(jù)的時(shí)空相關(guān)性相對(duì)應(yīng)，

5、物聯(lián)網(wǎng)應(yīng)用中對(duì)傳感器數(shù)據(jù)的查詢也并不僅僅局限于關(guān)鍵字查詢很多時(shí)候，我們需要基于復(fù)雜的邏輯約束條件進(jìn)行查詢，如查詢某個(gè)指定地理區(qū)域中所有地質(zhì)類傳感器在規(guī)定時(shí)間段內(nèi)所采集的數(shù)據(jù)，并對(duì)它們進(jìn)行統(tǒng)計(jì)分析由此可見，對(duì)物聯(lián)網(wǎng)數(shù)據(jù)的空間與時(shí)間屬性進(jìn)行智能化的管理與分析處理是至關(guān)重要的(4)物聯(lián)網(wǎng)數(shù)據(jù)的序列性與動(dòng)態(tài)流式特性在物聯(lián)網(wǎng)系統(tǒng)中，要查詢某個(gè)監(jiān)控對(duì)象在某一時(shí)刻的物理狀態(tài)是不能簡(jiǎn)單地通過(guò)對(duì)時(shí)間點(diǎn)的關(guān)鍵字匹配來(lái)完成的，這是因?yàn)椴蓸舆^(guò)程是間斷進(jìn)行的，查詢時(shí)間與某個(gè)采樣時(shí)間正好匹配的概率極低為了有效地進(jìn)行查詢處理，需要將同一個(gè)監(jiān)控對(duì)象的歷次采樣數(shù)據(jù)組合成一個(gè)采樣數(shù)據(jù)序列，并通過(guò)插值計(jì)算的方式得到監(jiān)控對(duì)象在指定時(shí)

6、刻的物理狀態(tài)采樣數(shù)據(jù)序列反映了監(jiān)控對(duì)象的狀態(tài)隨時(shí)問(wèn)變化的完整過(guò)程，因此包含比單個(gè)采樣值豐富得多的信息此外，采樣數(shù)據(jù)序列表現(xiàn)出明顯的動(dòng)態(tài)流式特性隨著新采樣值的不斷到來(lái)和過(guò)時(shí)采樣值的不斷淘汰，采樣數(shù)據(jù)序列是不斷的動(dòng)態(tài)變化的針對(duì)物聯(lián)網(wǎng)海量數(shù)據(jù)管理所面臨的上述挑戰(zhàn)，目前尚沒(méi)有有效的解決方法.本文提出處理這些海量數(shù)據(jù)的兩種方法：(1)對(duì)這些數(shù)據(jù)進(jìn)行分級(jí)處理；（2）對(duì)這些數(shù)據(jù)進(jìn)行降維處理.分級(jí)處理可以有效的減輕系統(tǒng)的負(fù)荷；降維處理可以有效的壓縮數(shù)據(jù)量，并且降維處理是處理一些數(shù)據(jù)必須進(jìn)行的步驟，降維處理已經(jīng)在大規(guī)模的圖像處理算法中得到應(yīng)用.2 物聯(lián)網(wǎng)的海量數(shù)據(jù)分級(jí)處理策略2.1 海量數(shù)據(jù)分級(jí)的必要性2010

7、年JiKui Wang論證并提出了數(shù)據(jù)分級(jí)存儲(chǔ)的必要性4.他認(rèn)為：如左圖所示，通常40%或者更多的企業(yè)數(shù)據(jù)是非活躍的，但是這些非活躍的數(shù)據(jù)卻：（1） 消耗了昂貴的存儲(chǔ)空間（2） 不得不如同活躍數(shù)據(jù)一樣需要一些不必要管理，備份，復(fù)制等操作（3） 有嚴(yán)重的法律風(fēng)險(xiǎn)（4） 不得不在DR方案中進(jìn)行一些不必要的恢復(fù)操作 由此，我們可以把2000年的292TB的總數(shù)據(jù)可以分為：（1）115TB的活躍數(shù)據(jù)（2）77TB的非活躍數(shù)據(jù)截止到2010年，JiKui Wang得出如下圖所示的活躍數(shù)據(jù)與非活躍數(shù)據(jù)之間的關(guān)系：分級(jí)與具體的環(huán)境相關(guān)，比如說(shuō)，它與下面的幾個(gè)方面相關(guān)：（1） 服務(wù)屬性質(zhì)量，速率，可靠性（2）

8、 分級(jí)可以被專業(yè)化，比如合規(guī)存檔（3） 分級(jí)可以無(wú)硬盤存儲(chǔ)，比如用CDR,磁帶存儲(chǔ)等如下圖所示則很好地處理了數(shù)據(jù)分級(jí)處理問(wèn)題：2.2 海量物聯(lián)網(wǎng)數(shù)據(jù)分級(jí)處理海量物聯(lián)網(wǎng)數(shù)據(jù)分級(jí)模型海量物聯(lián)網(wǎng)分級(jí)存儲(chǔ)系統(tǒng)是針對(duì)基于服務(wù)需求和成本構(gòu)建的層次存儲(chǔ)系統(tǒng)。 它由具有不同性能、可用性和單位價(jià)格等指標(biāo)的存儲(chǔ)級(jí)別構(gòu)成, 數(shù)據(jù)存放在不同的存儲(chǔ)級(jí)別中(固態(tài)磁盤、光纖盤陣、IDE盤陣、SATA盤陣和磁帶庫(kù))。該系統(tǒng)可滿足海量數(shù)據(jù)存儲(chǔ)的高性能、大容量和低成本等要求。分級(jí)存儲(chǔ)系統(tǒng)的核心是數(shù)據(jù)遷移技術(shù)。該技術(shù)在不同存儲(chǔ)層次之間遷移數(shù)據(jù), 同時(shí)保證遷移過(guò)程中數(shù)據(jù)訪問(wèn)的一致性。數(shù)據(jù)遷移分為離線遷移和在線遷移兩種。 離線遷移需要

9、將應(yīng)用停止服務(wù)后再進(jìn)行遷移,它避免了遷移過(guò)程中對(duì)數(shù)據(jù)一致性的維護(hù)。由于目前企業(yè)級(jí)應(yīng)用都要求7*24h在線, 離線遷移已不適合大規(guī)模存儲(chǔ)系統(tǒng)的需要, 因此在線遷移成為遷移技術(shù)的研究熱點(diǎn). 目前, 已有的在線數(shù)據(jù)遷移技術(shù)都存在如下缺陷:（1）遷移條件缺乏自適應(yīng)機(jī)制。一些分級(jí)存儲(chǔ)系統(tǒng)的遷移策略是由管理員預(yù)先制定好的。如在生命周期管理的體系結(jié)構(gòu)STEPS中,具體遷移策略由管理員手工設(shè)定,文件在創(chuàng)建時(shí)就按照一定的放置策略放入不同的存儲(chǔ)池中, 在文件的生命周期內(nèi),由預(yù)先設(shè)定好的遷移策略將文件在不同存儲(chǔ)池之間遷移。 該遷移方法簡(jiǎn)單易操作, 但不能很好地適應(yīng)動(dòng)態(tài)變化的負(fù)載。（2）遷移代價(jià)高。如基于Lustre

10、的分級(jí)存儲(chǔ)管，理系統(tǒng)中,文件從離線設(shè)備遷移到在線設(shè)備都是由訪問(wèn)缺失觸發(fā)的, 因此造成一次訪問(wèn)缺失的代價(jià)很大,且不支持文件的在線遷移。 （3）傳統(tǒng)的文件遷移方法的升級(jí)策略都是on-demand類型。如果被訪問(wèn)的文件沒(méi)有在高端存儲(chǔ)系統(tǒng)中命中，則將其從低端存儲(chǔ)系統(tǒng)遷移到高端存儲(chǔ)系統(tǒng)中。 該方法的缺點(diǎn)是沒(méi)有考慮文件的其他信息,比如文件大小、訪問(wèn)間隔等,造成升級(jí)的文件過(guò)多。具有代表性的兩種文件遷移為:(1)LRU(least-recently-used), 優(yōu)先將最近最不常使用的文件進(jìn)行替換。LRU的缺陷在于平等地對(duì)待全部文件，沒(méi)有考慮到文件的大小而文件大小決定了文件的遷移代價(jià)。（2）GreedyDua

11、lSize,基于文件的recency,size和migrationcost對(duì)文件進(jìn)行替換。該方式升級(jí)遷移的數(shù)據(jù)量大，而且文件升級(jí)前需要通過(guò)降級(jí)來(lái)替換文件，增加了文件訪問(wèn)響應(yīng)時(shí)間。針對(duì)已有在線數(shù)據(jù)遷移技術(shù)存在的不足,清華大學(xué)敖莉，于得水等人提出了一種高效的數(shù)據(jù)遷移方法 CuteMig【2】,該方法采用基于升級(jí)成本和升級(jí)收益的文件分級(jí)策略, 動(dòng)態(tài)地考慮了文件大小和文件訪問(wèn)頻度,將升級(jí)成本與收益比值滿足條件的文件進(jìn)行遷移, 既保證了升級(jí)必要的熱點(diǎn)文件達(dá)到較高的命中率，也解決on-demand升級(jí)方式遷移數(shù)據(jù)量大的問(wèn)題。同時(shí)CuteMig采用基于剩余空間的文件自適應(yīng)降級(jí)選擇策略,根據(jù)高端存儲(chǔ)系統(tǒng)的剩余

12、空間情況主動(dòng)地選取文件來(lái)降級(jí),保證了高端存儲(chǔ)系統(tǒng)中始終有剩余空間, 解決了傳統(tǒng)替換策略在升級(jí)前必須先執(zhí)行DEMOTE操作進(jìn)行替換的問(wèn)題。在CuteMig遷移方法的基礎(chǔ)上,他們?yōu)橐环N物理數(shù)值模擬的海量數(shù)據(jù)存儲(chǔ), 設(shè)計(jì)并實(shí)現(xiàn)了一個(gè)分級(jí)存儲(chǔ)系統(tǒng)TH-TS, 該系統(tǒng)基于并行文件系統(tǒng)PVFS2, 采用增量掃描的方式獲取文件訪問(wèn)頻度信息,建立升級(jí)和降級(jí)隊(duì)列管理遷移任務(wù), 減少了遷移決策的開銷, 提高了系統(tǒng)的遷移效率. 評(píng)測(cè)結(jié)果表明, TH-TS可以根據(jù)文件訪問(wèn)頻度在不同數(shù)據(jù)服務(wù)器之間有效地遷移數(shù)據(jù),同時(shí)CuteMig遷移方法和傳統(tǒng)遷移方法LRU和GreedyDualSize相比, 升級(jí)遷移量下降了32%和

13、59%; 降級(jí)遷移量下降了47%和66%, 且CuteMig 的平均IPO響應(yīng)時(shí)間比LRU最多可降低10%, 比GreedyDualSize最多可降低39%。THTS體系結(jié)構(gòu)的硬件結(jié)構(gòu)按功能劃分，包括客戶端，元數(shù)據(jù)服務(wù)器和數(shù)據(jù)服務(wù)器3部分，如圖1所示：在圖1中, 元數(shù)據(jù)服務(wù)器和客戶端之間的通路稱為元數(shù)據(jù)路徑,數(shù)據(jù)服務(wù)器和客戶端之間的通路稱為數(shù)據(jù)路徑.元數(shù)據(jù)服務(wù)器負(fù)責(zé)把位于不同數(shù)據(jù)服器上的數(shù)據(jù)文件組織成統(tǒng)一的文件系統(tǒng)視圖,為客戶端軟件提供元數(shù)據(jù)操作服務(wù), 同時(shí)執(zhí)行文件掃描、數(shù)據(jù)分級(jí)、遷移決策和遷移速率控制等操作,實(shí)現(xiàn)對(duì)遷移操作的單點(diǎn)管理;數(shù)據(jù)服務(wù)器保存每個(gè)文件分片后的數(shù)據(jù)文件, 為客戶端軟件提供

14、文件IPO操作,同時(shí)執(zhí)行元數(shù)據(jù)服務(wù)器發(fā)來(lái)的文件遷移指令;文件系統(tǒng)客戶端軟件實(shí)現(xiàn)虛擬文件系統(tǒng)層和MPI-IO層的各種文件操作.THTS體系結(jié)構(gòu)的軟件體系結(jié)構(gòu)包括3部分客戶端軟件,元數(shù)據(jù)服務(wù)器軟件和數(shù)據(jù)服務(wù)器軟件?？蛻舳塑浖譃閼?yīng)用層、系統(tǒng)接口層、任務(wù)管理層和網(wǎng)絡(luò)通信層。元數(shù)據(jù)服務(wù)器是整個(gè)TH-TS系統(tǒng)中負(fù)責(zé)遷移和數(shù)據(jù)管理的主控節(jié)點(diǎn),其設(shè)計(jì)主要包括: 1)獲取數(shù)據(jù)服務(wù)器的文件訪問(wèn)頻度信息; 2)管理并調(diào)度遷移任務(wù);3)與數(shù)據(jù)服務(wù)器交互來(lái)控制遷移的執(zhí)行. 為了現(xiàn)以上功能, 元數(shù)據(jù)服務(wù)器軟件設(shè)計(jì)了文件遷移決策模塊,它包含了增量掃描器,文件訪問(wèn)表管理器以及遷移調(diào)度控制器3個(gè)子模塊.數(shù)據(jù)服務(wù)器負(fù)責(zé)向客戶端

15、軟件提供IPO服務(wù)記錄數(shù)據(jù)文件的訪問(wèn)頻度信息、執(zhí)行元數(shù)據(jù)服務(wù)器發(fā)來(lái)的遷移請(qǐng)求. 數(shù)據(jù)服務(wù)器軟件的設(shè)計(jì)主要包括:1) 數(shù)據(jù)分片. 為了提高IPO性能, 文件數(shù)據(jù)按照一定分片規(guī)則分布在不同數(shù)據(jù)服務(wù)器上. 數(shù)據(jù)服務(wù)器需要保證客戶端軟件和元數(shù)據(jù)服務(wù)器軟件按照分布信息可以獲取正確的數(shù)據(jù).2) 記錄數(shù)據(jù)文件的訪問(wèn)頻度信息. 數(shù)據(jù)服務(wù)器軟件需定時(shí)記錄數(shù)據(jù)文件的訪問(wèn)頻度信息, 并在收到元數(shù)據(jù)的掃描指令后把數(shù)據(jù)文件的訪問(wèn)頻度信息返回給元數(shù)據(jù)服務(wù)器.3) 數(shù)據(jù)服務(wù)器不僅在收到元數(shù)據(jù)服務(wù)器的遷移指令后開始執(zhí)行遷移, 而且還需把要遷移的數(shù)據(jù)文件寫入目標(biāo)數(shù)據(jù)服務(wù)器的數(shù)據(jù)文件中, 以完成遷移任務(wù).為了實(shí)現(xiàn)以上3個(gè)技術(shù)點(diǎn),

16、數(shù)據(jù)服務(wù)器軟件設(shè)計(jì)了數(shù)據(jù)分片策略、IPO記錄模塊和遷移執(zhí)行模塊來(lái)完成其功能 CuteMig數(shù)據(jù)遷移分級(jí)存儲(chǔ)系統(tǒng)中數(shù)據(jù)遷移是核心技術(shù). 為提高分級(jí)存儲(chǔ)系統(tǒng)的IPO性能,達(dá)到高的IPO命中率及少的數(shù)據(jù)遷移量, 我們?cè)O(shè)計(jì)了CuteMig數(shù)據(jù)遷移方法, 主要包括以下3種關(guān)鍵技術(shù)。.1基于升級(jí)成本和升級(jí)收益的文件分級(jí)策略基于升級(jí)成本和升級(jí)收益的文件分級(jí)策略是根據(jù)文件大小和文件訪問(wèn)頻度信息分別計(jì)算文件升級(jí)的成本和升級(jí)后的收益, 使用二者的比值對(duì)文件進(jìn)行分級(jí), 并根據(jù)文件分級(jí)結(jié)果決定是否對(duì)文件升級(jí),以提高系統(tǒng)的整體性能.1) 文件升級(jí)的成本定義為升級(jí)需要傳送的數(shù)據(jù)量:Cost = filesize (1)傳

17、送數(shù)據(jù)過(guò)程增大了高端和低端存儲(chǔ)系統(tǒng)的IPO負(fù)載, 也通過(guò)競(jìng)爭(zhēng)帶寬資源增大了前端應(yīng)用的響應(yīng)時(shí)間, 文件越大遷移過(guò)程對(duì)前端應(yīng)用的影響也越大.2) 文件升級(jí)后的收益定義為文件升級(jí)后被訪問(wèn)的吞吐率. 其計(jì)算過(guò)程包括如下兩個(gè)步驟:步驟1. 計(jì)算文件的平均訪問(wèn)時(shí)間間隔:其中文件的當(dāng)前訪問(wèn)間隔為current_interval = current _access_time- last_access_time. (3)式(2)中, 如果文件以前沒(méi)有被訪問(wèn)過(guò), 它的平均訪問(wèn)時(shí)間間隔INFINITE; 如果文件是第2次被訪問(wèn), 將它的平均訪問(wèn)間隔就是當(dāng)前訪問(wèn)間隔,否則按遺忘因子A將當(dāng)前訪問(wèn)間隔和舊的平均訪問(wèn)間隔加

18、權(quán)求和, 得到新的平均訪問(wèn)間隔. 該方法既考慮了文件當(dāng)前的訪問(wèn)間隔,也通過(guò)遺忘因子A把文件過(guò)去的訪問(wèn)間隔信息反映到平均訪問(wèn)間隔中.步驟2. 計(jì)算文件的升級(jí)收益. 設(shè)access_num,access_bytes,filesize, avg_interval分別表示文件的總訪問(wèn)次數(shù)、總訪問(wèn)字節(jié)數(shù)、文件大小和文件的平均訪問(wèn)間隔, 文件升級(jí)后經(jīng)過(guò)T時(shí)間的升級(jí)收益表示為（4）T/g_interval 表示文件在T 時(shí)間內(nèi)的預(yù)期訪問(wèn)次數(shù)cess_bytes/ccess_num表示文件每次訪問(wèn)的平均字節(jié)數(shù). 式(4)中升級(jí)收益是隨著時(shí)間T 不斷累積的, 因此平均收益為 由于access_num, acce

19、ss_bytes, avg_interval 都是文件的歷史訪問(wèn)特征, 可近似認(rèn)為文件的訪問(wèn)特征在短時(shí)間內(nèi)不會(huì)發(fā)生變化, 因此Benef it 是根據(jù)文件歷史訪問(wèn)特征預(yù)測(cè)的文件近期內(nèi)的平均收益.為保證升級(jí)熱點(diǎn)文件提高訪問(wèn)性能的同時(shí), 盡量降低遷移的數(shù)據(jù)量, 我們使用遷移成本和收益的比值表示文件的遷移優(yōu)先級(jí)MigLaziness, 即該優(yōu)先級(jí)越小文件被升級(jí)的概率越大. 每當(dāng)文件被訪問(wèn), 即更新平均訪問(wèn)間隔、總訪問(wèn)大小、總訪問(wèn)字節(jié)數(shù)等遷移相關(guān)信息, 計(jì)算升級(jí)遷移的優(yōu)先級(jí)值. 該值越小說(shuō)明升級(jí)的成本越小, 而且升級(jí)后的收益越大, 如果文件的遷移優(yōu)先級(jí)小于升級(jí)閾值, 即對(duì)該文件執(zhí)行升級(jí)操作.2.2.2

20、.2基于剩余空間的文件自適應(yīng)降級(jí)選擇策基于剩余空間的文件自適應(yīng)降級(jí)選擇策略根據(jù)文件的訪問(wèn)情況和高端存儲(chǔ)設(shè)備的剩余空間, 主動(dòng)地選擇需要降級(jí)的文件, 以保證高端存儲(chǔ)系統(tǒng)中始終有剩余空間. 該方法解決了傳統(tǒng)替換策略在升級(jí)前必須先執(zhí)行DEMOTE操作進(jìn)行替換的問(wèn)題.1) 維護(hù)一個(gè)LRU棧. 所有升級(jí)到高端存儲(chǔ)系統(tǒng)上的文件都放入該LRU棧中. 每當(dāng)高端存儲(chǔ)系統(tǒng)上的文件訪問(wèn)完成后, 則將其放入LRU棧的MRU端, 同時(shí)檢查L(zhǎng)RU棧中LRU端的文件, 根據(jù)該文件的上次訪問(wèn)時(shí)間和當(dāng)前時(shí)間來(lái)計(jì)算它的未訪問(wèn)時(shí)間2) 根據(jù)文件未訪問(wèn)時(shí)間與降級(jí)閾值的比值進(jìn)行降級(jí)判斷. 如果它的未訪問(wèn)時(shí)間大于降級(jí)閾值Demotion

21、_threshold, 那么將其放入降級(jí)候選隊(duì)列中, 由降級(jí)調(diào)度程序處理. 降級(jí)閾值在初始化時(shí)被賦值為初始值Init_demotion( 該值為可變參數(shù)) ,之后自適應(yīng)地變化: 每當(dāng)降級(jí)候選隊(duì)列中的文件被訪問(wèn), 把該文件重新放入LRU棧,同時(shí)把降級(jí)閾值設(shè)置為該文件的本次訪問(wèn)和上次訪問(wèn)的時(shí)間間隔, 作為對(duì)降級(jí)閾值的懲罰; 每當(dāng)降級(jí)線程從降級(jí)候選隊(duì)列中成功降級(jí)了一個(gè)文件, 把降級(jí)閾值設(shè)置為L(zhǎng)RU棧中LRU端文件的未訪問(wèn)時(shí)間,為對(duì)降級(jí)閾值的獎(jiǎng)勵(lì), 以使LRU棧中更多的文件進(jìn)入到降級(jí)候選隊(duì)列中來(lái)3) 降級(jí)頻率. 如圖5所示降級(jí)后候選隊(duì)列保存了LRU棧中大于降級(jí)閾值的文件. 每隔時(shí)間T, 調(diào)度程序從降級(jí)

22、候選隊(duì)列的隊(duì)首取出降級(jí)候選文件執(zhí)行降級(jí)操作. T 的計(jì)算公式如下:式(7)中K是可調(diào)參數(shù), f reeratio是高端存儲(chǔ)系統(tǒng)的剩余空間占其總空間的例, 取值范圍是 0, 1 ,因此T 的取值范圍是 0, Demotion_threshold . 降級(jí)的頻率根據(jù)Demotion_threshold和f reeratio 自適應(yīng)化。因此該策略是一個(gè)反饋過(guò)程, 最終降級(jí)閾值和高端存儲(chǔ)系統(tǒng)的剩余空間都會(huì)穩(wěn)定在一個(gè)范圍內(nèi)。.3 移調(diào)度控制為了避免遷移過(guò)程影響前端應(yīng)用, TH-TS采用了遷移調(diào)度控制, 按照遷移目標(biāo)的不同, 將遷移任務(wù)分為升級(jí)遷移和降級(jí)遷移, 并用雙候選隊(duì)列技術(shù), 使用升和降級(jí)隊(duì)列分別管

23、理調(diào)度這兩種遷移任務(wù).這種遷移任務(wù)區(qū)分的方法保證了緊迫的升級(jí)任務(wù)可以迅速執(zhí)行, 同時(shí)不緊迫的降級(jí)任務(wù)在負(fù)載較輕時(shí)才執(zhí)行。TH-TS把遷移任務(wù)分成兩類: 將數(shù)據(jù)從低端存儲(chǔ)系統(tǒng)遷移到高端存儲(chǔ)系統(tǒng)的過(guò)程稱為升級(jí)遷移;將數(shù)據(jù)從高端存儲(chǔ)系統(tǒng)遷移到低端存儲(chǔ)系統(tǒng)的過(guò)程稱為降級(jí)遷移. 這兩類遷移的目標(biāo)不同: 升級(jí)遷移是為了把熱點(diǎn)數(shù)據(jù)遷移到高端存儲(chǔ)系統(tǒng)中, 以提高系統(tǒng)的訪問(wèn)性能; 降級(jí)遷移是為了把非熱點(diǎn)數(shù)據(jù)遷移到低端存儲(chǔ)系統(tǒng)中, 以使高端存儲(chǔ)系統(tǒng)擁有足夠的剩余空間, 來(lái)保存后續(xù)可能升級(jí)的熱點(diǎn)文件.3 海量物聯(lián)網(wǎng)的降維處理隨著物聯(lián)網(wǎng)技術(shù)的應(yīng)用，人們將會(huì)不分時(shí)間和地點(diǎn)，可以方便的獲得大量的信息，人們獲得的數(shù)據(jù)量將以

24、指數(shù)形式快速增長(zhǎng)，這些數(shù)據(jù)具有快速更新，數(shù)據(jù)維數(shù)更高，非結(jié)構(gòu)化等特點(diǎn)。從大規(guī)模的海量數(shù)據(jù)發(fā)現(xiàn)和探索新的知識(shí)是人類獲取信息的主要目標(biāo)之一。 目前人們對(duì)這些數(shù)據(jù)的處理還沒(méi)有形成相應(yīng)的有效方法，傳統(tǒng)的數(shù)據(jù)分析方法在處理這些數(shù)據(jù)集合時(shí)，往往效果并不好，甚至在某些情況下失效，蘊(yùn)含在數(shù)據(jù)中的知識(shí)和規(guī)律我們無(wú)法得知，將會(huì)導(dǎo)致 數(shù)據(jù)災(zāi)難問(wèn)題。因此人們就迫切希望去認(rèn)識(shí)和探索這些數(shù)據(jù)之間的奧秘 如何能有效的利用這些高維數(shù)據(jù)是面臨的基本問(wèn)題。近年來(lái), 數(shù)據(jù)降維在物聯(lián)網(wǎng)海量數(shù)據(jù)領(lǐng)域起著越來(lái)越重要的作用。通過(guò)數(shù)據(jù)降維可以減輕維數(shù)災(zāi)難和高維空間中其他不相關(guān)屬性,從而促進(jìn)高維數(shù)據(jù)的分類、可視化及壓縮。所謂數(shù)據(jù)降維是指通過(guò)線

25、性或非線性映射將樣本從高維空間映射到低維空間,從而獲得高維數(shù)據(jù)的一個(gè)有意義的低維表示的過(guò)程。數(shù)據(jù)降維的數(shù)學(xué)描述如下: a)X= XiNi=1是D維空間中的一個(gè)樣本集,Y= YINi=1是d(d Y, x-y=M(x), 稱y為x的低維表示。目前，在很多情況下，首先將數(shù)據(jù)的維數(shù)將到一個(gè)合理的大小，同時(shí)盡可能多的保留原始的信息，然后再將降維處理后的數(shù)據(jù)送入信息處理系統(tǒng)，這樣的做法是非常有用的 同時(shí)降維算法也是一些機(jī)器學(xué)習(xí)，數(shù)據(jù)挖掘方法的組成部分 對(duì)數(shù)據(jù)降維處理，結(jié)合一些具體的業(yè)務(wù)需求，是一個(gè)行之有效對(duì)海量數(shù)據(jù)進(jìn)行處理的方法 降維算法主要分為線性降維算法和非線性降維算法 降維的實(shí)質(zhì)就是尋找投影變換：

26、從高維空間到低維空間變換 現(xiàn)在有一種最小量嵌入算法，在保持局部等距和角度不變的約束條件下，能很好的揭示數(shù)據(jù)內(nèi)在的流形結(jié)構(gòu).針對(duì)海量物聯(lián)網(wǎng)高維數(shù)據(jù)目前已經(jīng)提出了許多降維方法, 主要包括主成分分析( PCA)、多維尺度分析(multidimensional scaling, MDS)以及近年來(lái)提出的基于流形學(xué)習(xí)的算法, 如Isomap、局部線性嵌入( LLE)、拉普拉斯特征映射( LaplacianEigenmaps)等。對(duì)現(xiàn)有的降維方法, 可以從不同角度進(jìn)行分類。從待處理的數(shù)據(jù)的性質(zhì)角度考慮可分為線性和非線性的;從算法執(zhí)行的過(guò)程可分為基于特征值求解的方法和迭代方法;從幾何結(jié)構(gòu)的保留角度考慮可分為

27、全局方法和局部方法。本文依據(jù)降維方法間的主要區(qū)別, 將現(xiàn)有的降維方法進(jìn)行了系統(tǒng)的分類, 如圖1所示,并對(duì)幾種典型的線性和非線性降維方法進(jìn)行了詳細(xì)的闡述,最后對(duì)這些降維方法進(jìn)行了系統(tǒng)的分析比較。3.1典型的降維方法線性降維方法1) PCAPCA是通過(guò)對(duì)原始變量的相關(guān)矩陣或協(xié)方差矩陣內(nèi)部結(jié)構(gòu)的研究, 將多個(gè)變量轉(zhuǎn)換為少數(shù)幾個(gè)綜合變量即主成分,從而達(dá)到降維目的的一種線性降維方法。這些主成分能夠反映原始變量的絕大部分信息,它們通常表示為原始變量的線性組合。2)LDAFisher在1936年提出著名的Fisher準(zhǔn)則, 對(duì)于二類(分別稱為正類和負(fù)類)問(wèn)題,希望投影后得到的y=wTx能夠使得J(w)最大：

28、其中: m1、m2分別是正、負(fù)樣本在投影方向上的均值; ，是正、負(fù)樣本在投影方向上方差?？蓪⑵渫茝V到多類問(wèn)題, 此時(shí)希望找到的優(yōu)化方向是使得在低維空間中同類數(shù)據(jù)盡量靠近,而非同類數(shù)據(jù)盡量分離, 從而保留豐富的辨別信息, 使投影后的數(shù)據(jù)具有最大的可分性。非線性降維方法1)核主成分分析(KPCA)核方法是一系列非線性數(shù)據(jù)處理技術(shù)的總稱,它們的共同特征是這些數(shù)據(jù)處理方法均用到了核映射。近幾年,使用核函數(shù)對(duì)線性方法的重建提出一些成功方法如支持向量機(jī)回歸、核PCA、核Fisher分析等。核PCA是線性PCA的推廣, 主要思想是把輸入數(shù)據(jù)x經(jīng)由一個(gè)非線性映射A(x)映射到特征空間F,然后在特征空間F上執(zhí)行

29、線性PCA。2)MDSMDS是保留數(shù)據(jù)點(diǎn)間相似性或距離的一種非線性降維方法。MDS可分為度量性MDS和非度量性MDS。度量MDS利用數(shù)據(jù)點(diǎn)間的距離或相似性獲得數(shù)據(jù)的低維幾何表示,而非度量MDS僅利用原始數(shù)據(jù)點(diǎn)間的順序信息來(lái)獲得其低維表示。前者將距離平方陣轉(zhuǎn)換為內(nèi)積陣,通過(guò)求內(nèi)積陣的特征值和特征向量獲取低維表示;后者采用迭代方法。3) IsomapTenenbaum等人提出的Isomap算法是對(duì)經(jīng)典MDS的一種推廣。但MDS是基于歐式距離的且沒(méi)有考慮鄰近數(shù)據(jù)點(diǎn)的分布。假如高維數(shù)據(jù)點(diǎn)分布或近似分布于一個(gè)彎曲的流形上, 如Swiss-roll數(shù)據(jù)集, MDS可能將兩個(gè)數(shù)據(jù)點(diǎn)看做是近鄰點(diǎn), 然而它們沿著流形的距離要遠(yuǎn)遠(yuǎn)大于它們的輸入距離。Isomap的基本思想是首先使用最近鄰圖中的最短路徑得到近似的測(cè)地線距離(圖2),代替不能表示內(nèi)在流形結(jié)構(gòu)的Eucl-idean距離, 然后應(yīng)用MDS算法,進(jìn)而發(fā)現(xiàn)嵌入在高維空間的低維坐標(biāo)。測(cè)地線距離是兩點(diǎn)之間沿著流形的距離.4)LLE局部線性嵌入( LLE)是與Isomap相似的一種局部降維方法。但與Isomap不同的是, Isomap中建立了數(shù)據(jù)點(diǎn)的鄰接圖表示, 而LLE只試圖保留數(shù)據(jù)點(diǎn)的局部性質(zhì), 這使它對(duì)短環(huán)路問(wèn)題沒(méi)有Isomap敏感。此外, 局部性質(zhì)的保留允許非凸流形的成功嵌入。其基本思想是假設(shè)每個(gè)數(shù)據(jù)點(diǎn)與它的鄰