電子政務(wù)物聯(lián)網(wǎng)信息處理技術(shù)

1、<p>　　電子政務(wù)物聯(lián)網(wǎng)信息處理技術(shù)</p><p><b>　　摘要：</b></p><p>　　物聯(lián)網(wǎng)應(yīng)用在國(guó)內(nèi)外已廣泛興起。近年來，美國(guó)、歐盟、日韓和我國(guó)政府先后在多個(gè)領(lǐng)域啟動(dòng)大量物聯(lián)網(wǎng)應(yīng)用工程。本文在對(duì)國(guó)內(nèi)外電子政務(wù)物聯(lián)網(wǎng)應(yīng)用信息特點(diǎn)分析的基礎(chǔ)上，從不確定信息處理、海量信息處理和數(shù)據(jù)融合三個(gè)方面介紹了電子政務(wù)物聯(lián)網(wǎng)信息處理技術(shù)的國(guó)內(nèi)外發(fā)展現(xiàn)狀和研

2、究成果，并展望了未來發(fā)展趨勢(shì)。</p><p><b>　　關(guān)鍵詞：</b></p><p>　　電子政務(wù)物聯(lián)網(wǎng)、不確定信息處理、海量信息處理、數(shù)據(jù)融合</p><p>　　Abstract: the E-government Internet of things (IOT) has been widely arised in the wor

3、ld. In recent years, the United States of America, European Union, Japan ,South Korea and Chinese governments have started a lot of IOT application engineerings in many areas. Based on the analysis of the characteristics

4、 of the information in E-government IOT,this paper first introduces E-government IOT information processing technology development status and research results at home and abroad from three as</p><p>　　Key

5、words: E-government IOT, uncertain information processing, massive information processing, data fusion</p><p><b>　　1引言</b></p><p>　　電子政務(wù)物聯(lián)網(wǎng)，主要指政府部門主導(dǎo)建設(shè)的服務(wù)于政府管理、社會(huì)民生、經(jīng)濟(jì)發(fā)展的物聯(lián)網(wǎng)。</p&g

6、t;<p>　　1.1 國(guó)內(nèi)外電子政務(wù)物聯(lián)網(wǎng)應(yīng)用現(xiàn)狀</p><p>　　國(guó)內(nèi)外電子政務(wù)物聯(lián)網(wǎng)應(yīng)用正如火如荼開展。</p><p>　　2009年，美國(guó)總統(tǒng)奧巴馬簽署生效《2009年美國(guó)恢復(fù)和再投資法案》（即美國(guó)的經(jīng)濟(jì)刺激計(jì)劃），在智能電網(wǎng)和衛(wèi)生醫(yī)療信息技術(shù)應(yīng)用領(lǐng)域投資300億美元，大力推進(jìn)物聯(lián)網(wǎng)在這些領(lǐng)域的應(yīng)用。</p><p>　　歐盟許多國(guó)家在電

7、力、交通以及物流領(lǐng)域已經(jīng)形成了一定規(guī)模的物聯(lián)網(wǎng)應(yīng)用，進(jìn)行安全監(jiān)測(cè)、能源管理、公共交通管理等等。例如，德國(guó)電信公司推出了面向全球的M2M市場(chǎng)平臺(tái)，該平臺(tái)提供了9個(gè)業(yè)務(wù)分類，包括能源、醫(yī)療、交通物流、汽車、消費(fèi)電子、零售、工業(yè)自動(dòng)化、公共事業(yè)和安全等；英國(guó)通過普及智能儀表，為英國(guó)家庭提供個(gè)性化的能源效率咨詢服務(wù)；丹麥自2010年7月起推出個(gè)人數(shù)字簽名一體化系統(tǒng)NemID，用戶憑借NemID便可登陸網(wǎng)上銀行、稅局系統(tǒng)及公私機(jī)構(gòu)的網(wǎng)站，登錄后可

8、進(jìn)行個(gè)人稅務(wù)年報(bào)查詢、信息更新、補(bǔ)交稅款、簽證申請(qǐng)、發(fā)送探親訪友邀請(qǐng)、醫(yī)療咨詢等操作。NemID不僅提高了社會(huì)管理效率，也進(jìn)一步節(jié)省了人力和物力資源；瑞典國(guó)家運(yùn)輸部將RFID技術(shù)運(yùn)用到北環(huán)線(Norra Länken)隧道內(nèi)的空氣質(zhì)量監(jiān)控，還可以對(duì)人員進(jìn)行追蹤。</p><p>　　2009年7月，日本IT戰(zhàn)略本部頒布了日本新一代的信息化戰(zhàn)略——“i-Japan”戰(zhàn)略，首先將政策目標(biāo)聚焦在三大公共事業(yè)：

9、電子化政府治理、醫(yī)療健康信息服務(wù)、教育與人才培育，達(dá)到“新的行政改革”，使行政流程簡(jiǎn)化、效率化、標(biāo)準(zhǔn)化、透明化，同時(shí)推動(dòng)電子病歷、遠(yuǎn)程醫(yī)療、遠(yuǎn)程教育等應(yīng)用的發(fā)展。物聯(lián)網(wǎng)在日本已滲透到人們的衣食住行中。</p><p>　　2004年，韓國(guó)信息通信部提出“U-Korea”戰(zhàn)略?！癠-Korea”戰(zhàn)略是一種以無(wú)線傳感網(wǎng)絡(luò)為基礎(chǔ)，把韓國(guó)的所有資源數(shù)字化、網(wǎng)絡(luò)化、可視化、智能化，以此促進(jìn)韓國(guó)經(jīng)濟(jì)發(fā)展和社會(huì)變革的國(guó)家戰(zhàn)略。

10、2009年，韓國(guó)通過了U-City綜合計(jì)劃，在道路、橋梁、學(xué)校、醫(yī)院等城市基礎(chǔ)設(shè)施之中搭建融合信息通信技術(shù)的泛在網(wǎng)平臺(tái)，實(shí)現(xiàn)可隨時(shí)隨地提供交通、環(huán)境、福利等各種泛在網(wǎng)服務(wù)的城市。</p><p>　　2009年，溫家寶總理提出“感知中國(guó)”的戰(zhàn)略構(gòu)想，隨后，我國(guó)政府通過一系列政策、規(guī)劃和專項(xiàng)重點(diǎn)推動(dòng)物聯(lián)網(wǎng)在交通、公共安全、農(nóng)業(yè)、林業(yè)、環(huán)保、家居、醫(yī)療、工業(yè)生產(chǎn)、電力、物流等領(lǐng)域的應(yīng)用。例如，在交通領(lǐng)域，開展了“基于

11、物聯(lián)網(wǎng)的城市智能交通應(yīng)用示范”和“長(zhǎng)三角航道網(wǎng)及京杭運(yùn)河水系智能航運(yùn)信息服務(wù)物聯(lián)網(wǎng)應(yīng)用示范”工程?！盎谖锫?lián)網(wǎng)的城市智能交通應(yīng)用”著重構(gòu)建城市智能交通要素身份認(rèn)證、信息精準(zhǔn)獲取、交通綜合信息處理三大體系，在城市智能交通領(lǐng)域和橋隧監(jiān)控服務(wù)領(lǐng)域研發(fā)和改造相關(guān)感知設(shè)備，實(shí)現(xiàn)交通物理單元的全面感知和主動(dòng)管理?！伴L(zhǎng)三角航道網(wǎng)及京杭運(yùn)河水系智能航運(yùn)信息服務(wù)物聯(lián)網(wǎng)應(yīng)用”推進(jìn)長(zhǎng)三角航道網(wǎng)內(nèi)河航運(yùn)管理及信息服務(wù)的協(xié)同化和規(guī)范化，加速我國(guó)航運(yùn)物流一體化進(jìn)程

12、，提高航運(yùn)物流的安全和效率。在公共安全領(lǐng)域，開展城市社會(huì)公共安全物聯(lián)網(wǎng)應(yīng)用示范，主要應(yīng)用包括四個(gè)方面——智能安防、智能消防和智能交通。其中智能安防是以智能化的監(jiān)控系統(tǒng)為核心，實(shí)現(xiàn)重點(diǎn)區(qū)域的全天候監(jiān)控，對(duì)于危險(xiǎn)物品的管控等。智能消防主要內(nèi)容包括火災(zāi)、預(yù)警感知，火災(zāi)遠(yuǎn)程監(jiān)控，消防員生命特征的監(jiān)控。智能交通是車輛行蹤動(dòng)態(tài)感知，對(duì)車輛進(jìn)行管控。在環(huán)保</p><p>　　1.2電子政務(wù)物聯(lián)網(wǎng)信息特點(diǎn)</p>

13、<p>　　縱觀各類電子政務(wù)物聯(lián)網(wǎng)，其采集、處理和利用信息，具有如下幾個(gè)重要特點(diǎn)：</p><p>　　（1）多態(tài)性與異構(gòu)性</p><p>　　電子政務(wù)物聯(lián)網(wǎng)應(yīng)用中涉及各種各樣的傳感器，所采集的數(shù)據(jù)格式各不相同，有文本數(shù)據(jù)，也有圖像、音頻、視頻等多媒體數(shù)據(jù)。既有靜態(tài)數(shù)據(jù)，也有動(dòng)態(tài)數(shù)據(jù)。信息多態(tài)性和異構(gòu)性程度隨著應(yīng)用場(chǎng)景復(fù)雜度的增加而加大。</p><p&g

14、t;<b>　?。?）不確定性</b></p><p>　　信息的不確定性主要表現(xiàn)在 [3]：</p><p>　　①不一致性。由于時(shí)空映射失真造成的信息時(shí)空關(guān)系不一致；</p><p>　?、诓粶?zhǔn)確性。由于傳感器采樣和量化方式不同造成的信息精度差異；由于安全和隱私保護(hù)需要，對(duì)信息進(jìn)行變換加工，導(dǎo)致的信息不準(zhǔn)確；</p><

15、p>　?、鄄贿B續(xù)性。由于網(wǎng)絡(luò)傳輸不穩(wěn)定造成的信息斷續(xù)；</p><p>　?、懿蝗嫘?。由于傳感器感知域的局限性導(dǎo)致獲取的信息不全面。</p><p>　　⑤不完整性。由于網(wǎng)絡(luò)和環(huán)境的動(dòng)態(tài)變化造成的信息缺失。</p><p><b>　　（3）時(shí)效性</b></p><p>　　在狀態(tài)監(jiān)測(cè)、事件檢測(cè)等應(yīng)用中，被感知

16、的事物的狀態(tài)可能是瞬息萬(wàn)變的，只有新數(shù)據(jù)才能反映系統(tǒng)所感知的事物的現(xiàn)有狀態(tài)。</p><p><b>　?。?）海量性</b></p><p>　　主要由于兩個(gè)方面原因引起：</p><p>　　①在一些應(yīng)用中，往往涉及數(shù)量龐大的感知設(shè)備，這些設(shè)備產(chǎn)生了海量的數(shù)據(jù)集合。</p><p>　　②在一些系統(tǒng)中，例如視頻監(jiān)控，

17、數(shù)據(jù)以流的形式實(shí)時(shí)、高速、源源不斷地產(chǎn)生，隨著時(shí)間的推移，積累了龐大的數(shù)據(jù)量。</p><p>　　物聯(lián)網(wǎng)系統(tǒng)通常包含著海量的傳感器結(jié)點(diǎn)。其中，大部分傳感器（如溫度傳感器、ＧＰＳ傳感器、壓力傳感器等）的采樣數(shù)據(jù)是數(shù)值型的，但也有許多傳感器的采樣值是多媒體數(shù)據(jù)（如交通攝像頭視頻數(shù)據(jù)、音頻傳感器采樣數(shù)據(jù)、遙感成像數(shù)據(jù)等）。每一個(gè)傳感器均頻繁地產(chǎn)生新的采樣數(shù)據(jù)，系統(tǒng)不僅需要存儲(chǔ)這些采樣數(shù)據(jù)的最新版本，而且在多數(shù)情況下，

18、還需要存儲(chǔ)某個(gè)時(shí)間段（如１個(gè)月）內(nèi)所有的歷史采樣值，以滿足溯源處理和復(fù)雜數(shù)據(jù)分析的需要[18]。 </p><p>　?。?）時(shí)空相關(guān)性[18]</p><p>　　物聯(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è)車輛安裝了高精度的ＧＰＳ或ＲＦＩＤ標(biāo)簽，在交

19、通網(wǎng)絡(luò)中動(dòng)態(tài)地移動(dòng)。與物聯(lián)網(wǎng)數(shù)據(jù)的時(shí)空相關(guān)性相對(duì)應(yīng)，物聯(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ì)分析[18]。</p><p>　?。?）序列性與動(dòng)態(tài)流式性[18]</p><p>　　在電子政務(wù)物聯(lián)網(wǎng)系統(tǒng)中，要查詢某個(gè)監(jiān)控對(duì)象在某一時(shí)刻的物理

20、狀態(tài)往往不能簡(jiǎn)單地通過對(duì)時(shí)間點(diǎn)的關(guān)鍵字匹配來完成的，這是因?yàn)椴蓸舆^程是間斷進(jìn)行的，查詢時(shí)間與某個(gè)采樣時(shí)間正好匹配的概率極低。采樣數(shù)據(jù)序列反映了監(jiān)控對(duì)象的狀態(tài)隨時(shí)間變化的完整過程，因此包含比單個(gè)采樣值豐富得多的信息。此外，采樣數(shù)據(jù)序列表現(xiàn)出明顯的動(dòng)態(tài)流式特性—隨著新采樣值的不斷到來和過時(shí)采樣值的不斷淘汰，采樣數(shù)據(jù)序列是不斷動(dòng)態(tài)變化的[18]。</p><p>　　1.3本文內(nèi)容與安排</p><

21、p>　　電子政務(wù)物聯(lián)網(wǎng)的信息特點(diǎn)，決定了其信息處理的技術(shù)要求和技術(shù)方法。</p><p>　　目前，電子政務(wù)物聯(lián)網(wǎng)信息處理技術(shù)研究，可歸納為三大方向：不確定數(shù)據(jù)處理、海量信息處理和感知信息融合。</p><p>　　本文圍繞上述三大方向，首先介紹國(guó)際研究現(xiàn)狀，然后介紹國(guó)內(nèi)研究進(jìn)展，最后對(duì)該領(lǐng)域的發(fā)展趨勢(shì)進(jìn)行了展望。</p><p><b>　　2國(guó)際

22、研究現(xiàn)狀</b></p><p>　　2.1不確定數(shù)據(jù)處理</p><p>　　電子政務(wù)物聯(lián)網(wǎng)信息具有典型的不確定性。</p><p>　　不確定性數(shù)據(jù)由于其特點(diǎn)，在各種應(yīng)用情景下，傳統(tǒng)的確定性數(shù)據(jù)處理技術(shù)已不能有效適用。不確定信息處理技術(shù)主要包括不確定數(shù)據(jù)模型定義、存儲(chǔ)與索引，以及查詢分析和挖掘等[3]。近年來，概率統(tǒng)計(jì)的方法被逐步應(yīng)用于不確定性數(shù)據(jù)的

23、處理中。目前國(guó)際上的研究熱點(diǎn)主要集中在不確定數(shù)據(jù)模型、不確定數(shù)據(jù)查詢和不確定數(shù)據(jù)挖掘。</p><p>　?。?） 不確定數(shù)據(jù)模型[3] [15]</p><p>　　“可能世界模型”是最典型的和最常用的不確定數(shù)據(jù)模型建模思想[3] [15][66-67]?？赡苁澜缈臻g由一系列可能世界實(shí)例組成，可能世界實(shí)例對(duì)應(yīng)一個(gè)確定性數(shù)據(jù)庫(kù),其中,那些非確定性屬性是滿足約束條件的確定值[16]。目前研究

24、的主流不確定性數(shù)據(jù)庫(kù)為概率數(shù)據(jù)庫(kù)，它建立在可能世界模型的基礎(chǔ)上，可能世界語(yǔ)義是不確定性查詢處理技術(shù)的出發(fā)點(diǎn)和基礎(chǔ)。</p><p>　　不確定性數(shù)據(jù)的種類較多，例如關(guān)系型數(shù)據(jù)、半結(jié)構(gòu)化數(shù)據(jù)、流數(shù)據(jù)、移動(dòng)對(duì)象數(shù)據(jù)等，盡管存在許多與數(shù)據(jù)類型緊密相關(guān)的數(shù)據(jù)模型，但是這些模型最終都可以轉(zhuǎn)化為“可能世界模型”[3]。</p><p>　　在大多數(shù)應(yīng)用中，不確定性可細(xì)分為存在級(jí)不確定性（Existen

25、tial Uncertainty）和屬性級(jí)不確定性（Attribute Level Uncertainty）。存在級(jí)不確定性描述元組的存在與否，較為通用。屬性級(jí)不確定性并不涉及整個(gè)元組的不確定性，而是以概率密度函數(shù)或統(tǒng)計(jì)參數(shù)（例如方差等）來描述特定屬性的不確定性。作為不確定性數(shù)據(jù)庫(kù)建模的最核心思想，可能世界模型被廣泛采納于各種應(yīng)用之中，并衍生出多種應(yīng)用相關(guān)的模型，特別是針對(duì)關(guān)系型數(shù)據(jù)、半結(jié)構(gòu)化數(shù)據(jù)、流數(shù)據(jù)和多維數(shù)據(jù)的模型[3]。<

26、/p><p>　　最為常見的是針對(duì)關(guān)系模型的擴(kuò)展，包括Probabilistic-table、Probabilistic or-set table、Probabilistic or-set- table、Probabilistic c-table等[3] [68-70] 。Probabilistic -table以一個(gè)獨(dú)立的概率字段表示元組的概率，且各元組之間獨(dú)立。一個(gè)特定的數(shù)據(jù)庫(kù)實(shí)例（也即可能世界實(shí)例）的概率等于其

27、所包含的元組的概率乘積和其所不包含的元組的不發(fā)生概率的乘積。而Probabilistic or-set table則傾向于描述屬性級(jí)不確定性。在Probabilistic or-set table中，元組的屬性值被描述為多個(gè)候選值之間的“或”關(guān)系，可視為離散概率密度函數(shù)。也有的研究人員將probabilistic or-set- table命名為x-relation，它包含若干x-tuple（無(wú)存在級(jí)不確定性）或者maybe x-tu

28、ple（有存在級(jí)不確定性）[3] [68-70] 。</p><p>　　半結(jié)構(gòu)化數(shù)據(jù)模型（semistructed data model）能有效描述缺乏嚴(yán)格模式結(jié)構(gòu)的數(shù)據(jù)[3] [71]。半結(jié)構(gòu)化數(shù)據(jù)通?？梢杂梦臋n樹來描述。文獻(xiàn)[72]提出了一種管理概率半結(jié)構(gòu)化數(shù)據(jù)（probabilistic semistructed data）的方法，該方法以關(guān)系數(shù)據(jù)庫(kù)技術(shù)為基礎(chǔ)，支持豐富的代數(shù)查詢。目前，以文檔樹形式描述不

29、確定性半結(jié)構(gòu)化數(shù)據(jù)，例如p-文檔模型（p-document model）[72]、概率樹模型（Probabilistic Tree Model）[73-74]、PXDB模型[75]等獲得廣泛關(guān)注[3]。p-文檔模型[72]將概率值附加于文檔樹的邊上，各節(jié)點(diǎn)的概率依賴于其祖先的概率，節(jié)點(diǎn)之間可以是互斥關(guān)系（mux）或相互獨(dú)立（ind）。概率樹模型是一個(gè)事件驅(qū)動(dòng)的模型[3] [73-74]。它并不在各節(jié)點(diǎn)/邊上附加概率值來描述不確定性，而是

30、在各節(jié)點(diǎn)附加一系列事件變量，由外部事件的發(fā)生與否決定節(jié)點(diǎn)的存在性。PXDB模型[74]擴(kuò)展了p-文檔模型，增加外部約束條件。其他模型還包括PXML模型[77-78]、概率樹模型[79] 、PrXML模型[80]等[3]</p><p>　　在數(shù)據(jù)流模型中，數(shù)據(jù)到達(dá)的速度極快、數(shù)據(jù)規(guī)模極大，僅能夠開發(fā)一次掃描算法，使用有限內(nèi)存在線計(jì)算查詢結(jié)果。在不確定性數(shù)據(jù)流（Uncertain Data Stream, 或Pro

31、babilistic Data Stream）中，各元組具有不確定性。根據(jù)窗口定義不同，數(shù)據(jù)流模型可細(xì)分為界標(biāo)模型、滑動(dòng)窗口模型。界標(biāo)模型的范圍從某固定時(shí)間點(diǎn)至當(dāng)前時(shí)間為止，滑動(dòng)窗口模型僅考慮最新 的W個(gè)元組[81] [3]。在各模型中，新元組的到達(dá)與舊元組的消逝均引發(fā)可能世界實(shí)例的大變遷[3]。</p><p>　　在確定性多維數(shù)據(jù)模型中，各個(gè)事實(shí)（fact）必定屬于某一個(gè)立方體中。但對(duì)于處理不精確數(shù)據(jù)的應(yīng)用而

32、言，各事實(shí)可能無(wú)法被準(zhǔn)確地定位到立方體中[3]。文獻(xiàn)[82-83]提出了基于可能世界的多維數(shù)據(jù)模型，以處理這類不確定數(shù)據(jù)。在這種模型中，上述記錄能夠被存儲(chǔ)于不確定性數(shù)據(jù)庫(kù)中，可以基于可能世界語(yǔ)義做執(zhí)行OLAP操作（例如切塊、上卷等）[3]。</p><p>　　目前研究的主流不確定性數(shù)據(jù)庫(kù)為概率數(shù)據(jù)庫(kù)[15]。它建立在可能世界模型的基礎(chǔ)上，可能世界實(shí)例對(duì)應(yīng)一個(gè)確定性數(shù)據(jù)庫(kù)。其中,那些非確定性屬性是滿足約束條件的確

33、定值。可能世界語(yǔ)義是不確定性查詢處理技術(shù)的出發(fā)點(diǎn)和基礎(chǔ)[15]。一個(gè)不確定性數(shù)據(jù)庫(kù)可以分別或同時(shí)含有屬性級(jí)和記錄級(jí)不確定性;而對(duì)于不確定性屬性,其值可以離散或連續(xù);對(duì)于以一定概率存在的記錄之間,可以沒有生成規(guī)則也可以有生成規(guī)則,含有生成規(guī)則時(shí),生成規(guī)則可以是互斥、共存或其他規(guī)則 [15] [84]。不確定數(shù)據(jù)庫(kù)其組成如圖1。</p><p>　　圖1 不確定數(shù)據(jù)庫(kù)組成[15]</p><p&g

34、t;　　（2） 不確定數(shù)據(jù)查詢</p><p>　　不確定數(shù)據(jù)查詢已成為近年研究熱點(diǎn)。圍繞查詢算法、查詢優(yōu)化等技術(shù)國(guó)內(nèi)外取得了大量研究成與確定數(shù)據(jù)查詢相比，不確定數(shù)據(jù)查詢主要有三個(gè)特點(diǎn)[4]：</p><p>　?、俨樵冾愋蛷?fù)雜多樣。由于查詢?nèi)蝿?wù)種類較多，查詢目標(biāo)多樣，使得查詢類型更加復(fù)雜多樣；</p><p>　?、跀?shù)據(jù)類型多樣。目前不確定查詢面向的數(shù)據(jù)主要是多維

35、數(shù)據(jù)集、半結(jié)構(gòu)化數(shù)據(jù)、流數(shù)據(jù)、空間數(shù)據(jù)、模糊數(shù)據(jù)、世系數(shù)據(jù)和圖數(shù)據(jù)等，各種數(shù)據(jù)類型又可以進(jìn)一步細(xì)分，專門針對(duì)各種不確定數(shù)據(jù)類型的查詢技術(shù)研究在國(guó)內(nèi)外已廣泛開展；</p><p>　?、鄹怕示S度的特殊性。引入概率維度后，查詢類型需要重新定義，查詢返回結(jié)果也具有概率信息，概率特征增加了查詢的復(fù)雜性。</p><p>　　（3） 目前，國(guó)際上不確定數(shù)據(jù)查詢的研究主要集中在不確定Skyline查詢

36、、不確定Top -k 查詢、不確定NN查詢和不確定聚集查詢等方面。研究人員在這些方面開展了大量研究。</p><p>　?。?） 不確定Skyline查詢：主要分為針對(duì)不確定數(shù)據(jù)集和不確定數(shù)據(jù)流的Skyline查詢。</p><p>　?。?） 不確定數(shù)據(jù)集Skyline查詢目前主要分為集中式和分布式兩種[4]。</p><p>　　（6） 對(duì)集中式不確定數(shù)據(jù)集Sk

37、yline查詢，文獻(xiàn)[86]針對(duì)元組級(jí)不確定數(shù)據(jù)上的概率Skyline查詢，定義了計(jì)算q-Skyline的自底向上和自頂向下算法。自底向上算法用來計(jì)算選定的不確定數(shù)據(jù)對(duì)象實(shí)例的Skyline概率，使用這些實(shí)例剪枝其他實(shí)例和對(duì)象[85] [86][4]。自頂向下算法則遞歸地將不確定數(shù)據(jù)集合分割為子數(shù)據(jù)集，并對(duì)子集和對(duì)象漸進(jìn)剪枝。在概率Skyline模型中，不確定數(shù)據(jù)對(duì)象以某一概率加入Skyline中，而概率閥值q-Skyline查詢則要求

38、對(duì)象參與到Skyline的概率至少為q[4] [5]。然而某些場(chǎng)合設(shè)定閥值是不合適的，在此情形下需要計(jì)算全部數(shù)據(jù)的Skyline，Atallah M J.等研究了不確定數(shù)據(jù)集的全Skyline查詢，提出了一種有效結(jié)合加權(quán)支配計(jì)算方法和網(wǎng)格劃分算法。為提高剪枝效率，對(duì)象參數(shù)空間利用高斯樹索引，并通過限界-剪枝-精華方法計(jì)算出結(jié)果集合[4] [7]。</p><p>　　對(duì)分布式不確定數(shù)據(jù)集上概率Skyline查詢問

39、題，Ding等提出了基于元組級(jí)不確定數(shù)據(jù)一種4階段迭代處理算法DSUD及其擴(kuò)張算法e-DSUD,算法首先計(jì)算各個(gè)節(jié)點(diǎn)局部Skyline集合，然后選取部分元組進(jìn)行計(jì)算并利用一定反饋機(jī)制進(jìn)一步剪枝各個(gè)子節(jié)點(diǎn)中不可能成為全局Skyline的元組[4] [8]。</p><p>　　某些電子政務(wù)物聯(lián)網(wǎng)數(shù)據(jù)流的連續(xù)、無(wú)限、實(shí)時(shí)和只允許單遍掃描等特點(diǎn)，以及復(fù)雜的概率特性和計(jì)算表示，給不確定數(shù)據(jù)流上Skyline查詢提出了很多

40、挑戰(zhàn)。文獻(xiàn)[88]針對(duì)概率數(shù)據(jù)流上的Skyline計(jì)算問題，研究了基于滑動(dòng)窗口模型的建模和查詢定義，并提出SOPDS算法，算法應(yīng)用概率定界，逐步求精、提前淘汰與選擇補(bǔ)償?shù)葐l(fā)式規(guī)則對(duì)算法從時(shí)間和空間加以優(yōu)化，取得較好的整體性能[4] [9]。Zhang等基于滑動(dòng)窗口模型建立了概率Skyline算子，首先基于可能世界語(yǔ)義定義了Skyline概率和概率Skyline，然后定義候選集合，并證明候選集上計(jì)算概率Skyline等價(jià)于在整個(gè)滑動(dòng)窗口

41、上計(jì)算[4] [10]。</p><p>　　1） 不確定Top -k 查詢</p><p>　　Top –k查詢的目標(biāo)是返回k個(gè)排序函數(shù)值最大的元組。</p><p>　　在大規(guī)模的電子政務(wù)物聯(lián)網(wǎng)分布式環(huán)境中,Top-K查詢一直有著廣泛的應(yīng)用[16] [89]。分布式環(huán)境中,不確定性Top-K查詢處理面臨的核心問題是如何在降低計(jì)算開銷的同時(shí)最小化交互開銷[16]。

42、在傳感器數(shù)據(jù)流上,由于記錄到達(dá)的快速性、無(wú)序性以及數(shù)量的無(wú)限制性,要求查詢處理算法必須具有一遍掃描、時(shí)間開銷和空間開銷都比較低等特點(diǎn)[16]。不確定數(shù)據(jù)流上的Top-K查詢,目前主要有基于無(wú)限制數(shù)據(jù)流以及基于限定時(shí)間維數(shù)據(jù)流的研究[16]。</p><p>　　無(wú)限制的不確定性數(shù)據(jù)流環(huán)境中,不考慮記錄的消逝。隨著記錄不停到達(dá),所有記錄參與Top-K查詢處理[16]。文獻(xiàn)[93]中討論了如何在無(wú)限制的不確定性數(shù)據(jù)流

43、中進(jìn)行Expected Rank并根據(jù)Expected Rank值獲取前k記錄的ER-TopK查詢。根據(jù)每個(gè)記錄各不確定屬性值概率分布特點(diǎn),文獻(xiàn)[94]定義了記錄之間的支配關(guān)系。數(shù)據(jù)流對(duì)時(shí)間維的限定方式主要有兩種:一種是隨時(shí)間衰減的處理方式,一種是滑動(dòng)窗口的處理方式[16]。文獻(xiàn)[95]中分析了不確定數(shù)據(jù)流上連續(xù)滑動(dòng)窗口Top-K查詢的特點(diǎn),定義了滑動(dòng)窗口W內(nèi)一定包含Top-K記錄的最小子集——窗口的緊致集C(W).無(wú)限制不確定數(shù)據(jù)流上

44、Top-K查詢由于考慮所有記錄,因此更具有時(shí)間全局性;而考慮時(shí)間限制的不確定數(shù)據(jù)流上的Top-K查詢更具有現(xiàn)時(shí)性[16]。</p><p>　　文獻(xiàn)[96]研究了概率數(shù)據(jù)庫(kù)中Top –k查詢問題，闡述了通過SQL語(yǔ)句查詢概率數(shù)據(jù)庫(kù)中概率值最大的Top –k元組，其元組的排序即為排序函數(shù)值。文獻(xiàn)[97]提出了解決查詢的不確定數(shù)據(jù)模型以及U-Topk查詢和U-kRanks查詢的定義，將查詢問題轉(zhuǎn)化為狀態(tài)空間搜索問題，

45、并提出具有最優(yōu)性保證的查詢算法[4] [13]。針對(duì)文獻(xiàn)[13]等給出的概率Top-k查詢定義，文獻(xiàn)[11]采用x-relation不確定模型提出了更高效的U-Topk和U-kRanks多項(xiàng)式查詢算法[14]。</p><p>　　2） 不確定NN查詢[4]</p><p>　　最近鄰(NN)查詢通常定義為：給定查詢點(diǎn)和查詢對(duì)象集合，以及方向和范圍約束集合，檢索距離查詢對(duì)象的ｋ個(gè)最近的對(duì)象

46、[4]。概率最近鄰查詢（PNNQ）的概念在２００３年ACM SIGMOD會(huì)議上提出［98］，PNNQ定義為查詢返回對(duì)于某個(gè)查詢點(diǎn)ｑ在某一時(shí)刻的（Oi,Pi）形式的元組集合，其中pi為對(duì)象Oi在該時(shí)刻成為查詢ｑ的最近鄰的概率[98]。概率k-NN查詢（k-PNNQ）則要求返回一組列表｛（S,p(S)）｝，其中Ｓ為數(shù)據(jù)集Ｄ的基數(shù)為ｋ的子集，p(S)則為對(duì)于集合Ｓ中含有至查詢點(diǎn)ｑ的ｋ個(gè)最近鄰居的非零概率[14]。</p><

47、;p>　　根據(jù)計(jì)算過程的側(cè)重點(diǎn)不同，不確定ＮＮ查詢方法目前分為基于概率計(jì)算的方法和基于概率過濾的方法２類?；诟怕视?jì)算的方法強(qiáng)調(diào)通過概率形式特別是概率密度函數(shù)積分等形式的計(jì)算獲取對(duì)象與查詢點(diǎn)的ｋ近鄰的概率值；基于概率過濾的方法強(qiáng)調(diào)利用閾值或容忍值、上下界等各種約束條件來驗(yàn)證相應(yīng)的對(duì)象是否在查詢的結(jié)果中[14]。</p><p>　　Ljosa等人[99]將概率ＮＮ查詢問題簡(jiǎn)化為傳統(tǒng)的ＮＮ查詢，提出利用APL

48、A－tree索引結(jié)構(gòu)，并使用不確定性對(duì)象數(shù)據(jù)的概率密度函數(shù)期望的距離作為排序標(biāo)準(zhǔn)，但其k-NN查詢基于期望距離，查詢結(jié)果中并不包含概率信息。1-PNNQ僅返回對(duì)于給定查詢點(diǎn)ｑ最近的單個(gè)對(duì)象，是PNNQ研究的基礎(chǔ)。文獻(xiàn)［100］提出了基于R-tree索引的查詢方法，根據(jù)移動(dòng)對(duì)象不同的運(yùn)動(dòng)軌跡，提出了相應(yīng)的概率計(jì)算方法，其主要思想在于將每個(gè)對(duì)象的不確定性轉(zhuǎn)換成即距離查詢點(diǎn)的pdf (概率密度函數(shù)）和cdf（累積密度函數(shù)），并通過對(duì)此函數(shù)相關(guān)

49、的表達(dá)式的積分獲得條件概率。由于對(duì)概率pdf或cdf等的頻繁積分使得不確定ＮＮ查詢的計(jì)算代價(jià)過高，查詢反應(yīng)時(shí)間過長(zhǎng)。針對(duì)此問題，文獻(xiàn)[101]提出了一種蒙特卡羅采樣的高效計(jì)算PNNQ的方法，該方法中涉及的查詢和數(shù)據(jù)對(duì)象均可以是不確定的，方法的實(shí)用性較強(qiáng)[4]。</p><p>　　為了改進(jìn)1-PNNQ中概率計(jì)算所涉及的密集型積分計(jì)算開銷，文獻(xiàn)[102]提出了約束概率最近鄰查詢（C-PNNQ）的概念。C-PNNQ利

50、用基于Ｒ樹的方法過濾不可能成為最近鄰的對(duì)象，并根據(jù)ｃｄｆ函數(shù)粗粒度地求取概率邊界以避免復(fù)雜的嵌套積分過程。由于剪枝、驗(yàn)證過程的引入，極大地縮小了對(duì)象搜索的空間，從而減小了概率計(jì)算的開銷[4] [102]。針對(duì)屬性級(jí)不確定數(shù)據(jù)上的k-PNNQ問題，文獻(xiàn)[103]提 出了概率閾 值k-NN查詢 （T-k-PNNQ）的概念和定義，并研究了３種有效的查詢剪枝算法，而其中的閾值則由用戶設(shè)定，用于控制結(jié)果的數(shù)目。首先，采用k-bound過濾算法刪除

51、不可能成為查詢結(jié)果的對(duì)象；其次，采用概率候選選擇算法高效地檢測(cè)ｋ－子集，以快速剔除不滿足條件概率的對(duì)象集合．最后，通過概率上界和下界驗(yàn)證方法過濾返回結(jié)果以進(jìn)一步篩選查詢結(jié)果。目前多數(shù)不確定ＮＮ查詢研究不能同時(shí)支持元組級(jí)和屬性級(jí)不確定數(shù)據(jù)源。為解決此問題，文獻(xiàn)［23］中采用一種通用的不確定性模型，綜合平衡查詢中I/O操作和CPU操作（復(fù)雜的概率積分計(jì)算）等各種代價(jià)要素，并提出了Topk-PNN查詢定義。然而其排序標(biāo)準(zhǔn)僅基于每</p&

52、gt;<p>　　4）不確定數(shù)據(jù)集聚集查詢</p><p>　　文獻(xiàn)[107]針對(duì)概率數(shù)據(jù)庫(kù)上的聚集查詢問題，提出了一種基于分桶策略的概率聚集操作。通過將關(guān)系的可能世界分組成多個(gè)桶，每個(gè)桶對(duì)應(yīng)相同的聚集值，并對(duì)每個(gè)桶求線性規(guī)劃問題以獲得概率邊界，算法具有一般指數(shù)級(jí)的復(fù)雜性。早期傳統(tǒng)的聚集查詢算法主要關(guān)注于獲得精確的聚集統(tǒng)計(jì)值。然而在很多的現(xiàn)實(shí)應(yīng)用場(chǎng)景中，用戶只需獲得近似的聚集結(jié)果而非精確查詢結(jié)果。針

53、對(duì)不確定數(shù)據(jù)集的近似概率聚集查詢問題，文獻(xiàn)[108-109]中提出了基于草圖（sketch）的分布式數(shù)據(jù)集上的近似聚集查詢算法。其研究主要關(guān)注于傳感器網(wǎng)絡(luò)中的能量消耗，采用復(fù)制敏感的草圖方法以近似求取COUNT和SUM。與早期精確查詢算法不同，這些算法傳輸?shù)氖菈嚎s的數(shù)據(jù)而非原始數(shù)據(jù)，減少了通信的開銷；然而，由于算法中所有的傳感器數(shù)據(jù)均參與聚集查詢的計(jì)算過程，使得計(jì)算開銷較大。為了克服誤差界限固定的障礙，文獻(xiàn)[110]提出了一種基于抽樣的

54、(ε,δ)近似聚集算法以滿足不同程度精度要求的概率聚集查詢應(yīng)用。算法根據(jù)(ε,δ)值適應(yīng)性地確定抽樣的大小，對(duì)分布式的傳感器數(shù)據(jù)均勻抽樣，并采用數(shù)學(xué)方法估計(jì)各種聚集值。文獻(xiàn)[111]給出了針對(duì)不確定數(shù)據(jù)的分布式不確定最大值</p><p><b>　　2.2海量信息處理</b></p><p>　　大規(guī)模的電子政務(wù)物聯(lián)網(wǎng)應(yīng)用，涉及大量的不同類型的感知設(shè)備。這些感知設(shè)備

55、源源不斷地產(chǎn)生大量的數(shù)據(jù)。在很多應(yīng)用領(lǐng)域，短時(shí)間內(nèi)就能產(chǎn)生PB量的數(shù)據(jù)。如何存儲(chǔ)、管理和訪問海量的物聯(lián)網(wǎng)數(shù)據(jù)，是目前國(guó)際上最熱門的研究領(lǐng)域之一。國(guó)內(nèi)外研究機(jī)構(gòu)和研究人員，以及許多IT商業(yè)機(jī)構(gòu)取得了許多重要的研究成果。</p><p>　　電子政務(wù)物聯(lián)網(wǎng)領(lǐng)域的海量信息處理技術(shù)，主要包括數(shù)據(jù)存儲(chǔ)、管理和分析等。</p><p>　　（1）分布式存儲(chǔ)技術(shù)</p><p>

56、　　目前，廣泛采用分布式策略存儲(chǔ)海量數(shù)據(jù)。基本策略如下：所有數(shù)據(jù)被放置在多個(gè)存儲(chǔ)設(shè)備之中；存儲(chǔ)設(shè)備通過高速網(wǎng)絡(luò)相互連接；為各數(shù)據(jù)準(zhǔn)備多個(gè)副本，分別放置在不同存儲(chǔ)設(shè)備之中；僅當(dāng)數(shù)據(jù)塊的所有副本均無(wú)法被訪問時(shí)，該數(shù)據(jù)塊才無(wú)法被讀??；建立分布式索引，當(dāng)系統(tǒng)接收到數(shù)據(jù)訪問請(qǐng)求時(shí)，能夠快速?zèng)Q定從哪些存儲(chǔ)設(shè)備中讀取數(shù)據(jù)[17]．谷歌公司的ＧＦＳ和Ｈａｄｏｏｐ的ＨＤＦＳ是兩個(gè)最知名的分布式文件系統(tǒng)。</p><p>　?。?）

57、 noSQL技術(shù)</p><p>　　嚴(yán)格的關(guān)系數(shù)據(jù)模型不容易組織和管理復(fù)雜多樣的物聯(lián)網(wǎng)數(shù)據(jù)。noSQL技術(shù)解決了類型多樣的物聯(lián)網(wǎng)海量數(shù)據(jù)的管理、處理和分析問題。目前，noSQL技術(shù)可分為操作型noSQL技術(shù)和分析型noSQL技術(shù)[19]。</p><p>　　1）操作型noSQL技術(shù)</p><p>　　依據(jù)存儲(chǔ)模型,操作型noSQL技術(shù)可劃分成基于Key Val

58、ue存儲(chǔ)模型、基于Column Family(列分組)存儲(chǔ)模型、基于文檔模型和基于圖模型4類[19]。</p><p>　?、倩贙ey Value存儲(chǔ)技術(shù)</p><p>　　主要系統(tǒng)包括Tokyo Cabinet/Tyrant,Redis,Voldemort,OracleBerkeley DB，Amazon Dynamo/SimpleDB等[19] [112-116]。它們的共同特點(diǎn)是

59、,利用哈希表維護(hù)Key值到具體數(shù)據(jù)(value)的映射,通過Key值可以很方便地對(duì)數(shù)據(jù)進(jìn)行查找。由于Key Value存儲(chǔ)模型和查詢的簡(jiǎn)單性,有利于把數(shù)據(jù)進(jìn)行橫向分割,分布到大規(guī)模集群上進(jìn)行存儲(chǔ)和處理,從而獲得很高的操作性能(特別是寫入的性能) [19]。</p><p>　　②基于Column Family存儲(chǔ)技術(shù)</p><p>　　基于Column Family存儲(chǔ)的技術(shù)的主要 no

60、SQL系統(tǒng)包括 Cassandra,Big Table,HBase等[19][117-119]。Google的Big Table系統(tǒng)的存儲(chǔ)結(jié)構(gòu)是典型的Column Family存儲(chǔ)。在Column Family存儲(chǔ)中,同樣通過Key Value基礎(chǔ)模型對(duì)數(shù)據(jù)進(jìn)行建模,但是Value具有了更精巧的結(jié)構(gòu),即一個(gè)Value包含多個(gè)列,這些列還可以分組(column family),呈現(xiàn)出多層嵌套映射(map)的數(shù)據(jù)結(jié)構(gòu)特點(diǎn)[19]。 由于每列

61、數(shù)據(jù)是帶有時(shí)間戳(timestamp)的,可以在Column Family里維護(hù)多個(gè)Key Value 映射的版本。在需要對(duì)歷史數(shù)據(jù)的變動(dòng)情況進(jìn)行分析的場(chǎng)合,這樣的建模方法正好能夠提供有力的支持[19] 。 </p><p>　?、跠ocument(文檔)存儲(chǔ)技術(shù)</p><p>　　Document(文檔)存儲(chǔ)技術(shù)由來已久。這里介紹的基于Document存儲(chǔ)的noSQL技術(shù)是基于傳統(tǒng)文檔

62、存儲(chǔ)技術(shù)的新發(fā)展.Document存儲(chǔ)技術(shù)仍然以Key Value存儲(chǔ)模型作為基礎(chǔ)模型.這個(gè)模型可以對(duì)文檔的歷史版本進(jìn)行追蹤,每個(gè)文檔又是一個(gè)Key Value的列表,形成循環(huán)嵌套的結(jié)構(gòu),文檔格式一般采用JSON(Javascript object notation)或者類似于JSON的格式.對(duì)于特定的查詢來說,Document存儲(chǔ)的效率更高.目前Document(文檔)存儲(chǔ)主要的技術(shù)和產(chǎn)品包括CouchDB,MongoDB和Riak等

63、[19][121-123]. </p><p>　　④基于Graph存儲(chǔ)技術(shù)</p><p>　　基于Graph存儲(chǔ)的noSQL技術(shù)系統(tǒng)包括Neo4J,InfoGrid,Infinite Graph,Hyper Graph DB等[19][124-127]。有些圖數(shù)據(jù)庫(kù)基于面向?qū)ο髷?shù)據(jù)庫(kù)創(chuàng)建，比如Infinite Graph,在節(jié)點(diǎn)的遍歷等圖數(shù)據(jù)的操作中，表現(xiàn)出優(yōu)異的性能。在新的圖數(shù)據(jù)庫(kù)的

64、設(shè)計(jì)中，擴(kuò)展性作為重要的目標(biāo)被考慮,目的是對(duì)大規(guī)模的圖數(shù)據(jù)進(jìn)行有效的管理和分析。圖數(shù)據(jù)庫(kù)和上述3類noSQL技術(shù)在存儲(chǔ)模型、物理設(shè)計(jì)、數(shù)據(jù)分布、數(shù)據(jù)遍歷、查詢處理、事務(wù)的語(yǔ)義等方面都具有明顯的差異[19]。</p><p>　　行存儲(chǔ)（row store）和列存儲(chǔ)（column store）是兩種典型的數(shù)據(jù)庫(kù)物理存儲(chǔ)策略．由于數(shù)據(jù)分析任務(wù)往往僅使用較少字段，因此列存儲(chǔ)方式的效率更高[17]． 文獻(xiàn)[126]提出了

65、行列混合式數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)（RCFile）以解決海量數(shù)據(jù)快速加載、縮短查詢響應(yīng)時(shí)間、磁盤空間高效利用等問題。</p><p><b>　　⑤RCFile技術(shù)</b></p><p>　　RCFile融合了行存儲(chǔ)和列存儲(chǔ)的優(yōu)點(diǎn)，通過行組劃分降低數(shù)據(jù)加載開銷，通過列數(shù)據(jù)壓縮提高存儲(chǔ)空間利用率[19]。國(guó)際上應(yīng)用最廣泛的兩大分布式數(shù)據(jù)分析系統(tǒng)Hive和Pig均集成了RCFile

66、技術(shù)。RCFile已經(jīng)成為分布式離線數(shù)據(jù)分析系統(tǒng)中數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)的事實(shí)標(biāo)準(zhǔn)[15]。RC File技術(shù)是由Ohio州立大學(xué)、中國(guó)科學(xué)院、Facebook公司合作研發(fā)的面向Hadoop平臺(tái)的行列存儲(chǔ)模型。RCFile基于HDFS的塊結(jié)構(gòu),維持 Hadoop系統(tǒng)的擴(kuò)展性和容錯(cuò)性不變,但是賦予HDFS的數(shù)據(jù)塊更加精細(xì)的結(jié)構(gòu)[19]。這個(gè)工作借鑒了RDBMS的PAX存儲(chǔ)技術(shù),首先對(duì)大表進(jìn)行橫向劃分,以便放入HDFS約定大小的數(shù)據(jù)塊;然后在數(shù)據(jù)塊里

67、實(shí)現(xiàn)列存儲(chǔ),由于使用列存儲(chǔ),非常有利于對(duì)數(shù)據(jù)進(jìn)行壓縮,節(jié)省存儲(chǔ)空間。該技術(shù)已經(jīng)在Facebook得到了實(shí)際應(yīng)用[19]。Wisconsin Madison大學(xué)提出了基于MapReduce平臺(tái)的純列存儲(chǔ)模型,獲得了比RCFile更高的性能.Hadoop++則通過嵌入索引尋址機(jī)制加快數(shù)據(jù)訪問,從而提高數(shù)據(jù)處理的性能。在連接算法方面,著名數(shù)據(jù)庫(kù)技術(shù)專家Ullman研究了面向 </p><p>　　2）分析型noSQL技

68、術(shù)[19]</p><p>　　面向分析型應(yīng)用的noSQL技術(shù)主要包括MapReduce和Dryad(由于MapReduce技術(shù)的大流行,微軟已經(jīng)徹底關(guān)閉 Dryad項(xiàng)目,轉(zhuǎn)而全面支持 MapReduce技術(shù)(http://www.zdnet.com/blog/microsoft/microsoft-drops-dryad-puts-its-big-data-bets-on-hadoop/11226)).MapR

69、educe技術(shù)是由 Google公司提出來的,旨在解決大規(guī)模非結(jié)構(gòu)化數(shù)據(jù)快速批量處理的并行技術(shù)框架.MapReduce在設(shè)計(jì)之初,致力于通過大規(guī)模廉價(jià)服務(wù)器集群實(shí)現(xiàn)大數(shù)據(jù)的并行處理 .MapReduce技術(shù)框架包含 3個(gè)方面的內(nèi)容 :(1)高度容錯(cuò)的分布式文件系統(tǒng) ;(2) 并行編程模型 ; (3)并行執(zhí)行引擎.MapReduce并行編程模型,其計(jì)算過程分解為兩個(gè)主要階段,即 Map階段和Reduce階段。自從2004年Google首次

70、發(fā)布該技術(shù)以來,MapReduce技術(shù)表現(xiàn)出了強(qiáng)大的穿透力。隨著MapReduce技術(shù)的影響力不斷擴(kuò)大,傳統(tǒng)數(shù)據(jù)庫(kù)廠家,包括強(qiáng)烈反對(duì)noSQL/MapReduce技術(shù)的一些廠家</p><p>　　近幾年,MapReduce技術(shù)獲得了廣泛的關(guān)注，,研究人員圍繞MapReduce應(yīng)用領(lǐng)域擴(kuò)展、性能的提升、易用性的改進(jìn)等進(jìn)行了大量研究[19]。</p><p>　　在MapReduce應(yīng)用領(lǐng)域

71、擴(kuò)展方面，IBM公司的研究人員致力于對(duì)R和 Hadoop的集成.R是開源的統(tǒng)計(jì)分析軟件,通過R和 Hadoop的深度集成,把計(jì)算推向數(shù)據(jù)并且并行處理,使Hadoop獲得了強(qiáng)大的深度分析能力。Purdue大學(xué)的RHIPE項(xiàng)目(http://ml.stat.purdue.edu/rhipe/index.html)也致力于R和 Hadoop的集成,為大數(shù)據(jù)分析提供開發(fā)環(huán)境的支持[19]。</p><p>　　在性能提升

72、方面，主要圍繞如下幾個(gè)方面：</p><p>　?、俣嗪擞布cGPU上的性能改進(jìn)[19]</p><p>　　MIT和Manchester大學(xué)的研究人員研究了多核硬件上的MapReduce性能改進(jìn)。文獻(xiàn)[135-136]討論了Cell Broadband Engine上的MapReduce性能優(yōu)化技術(shù),其中,Wisconsin大學(xué)的研究人員利用Cell Sort算法,充分發(fā)揮硬件能力,極大

73、地提高了排序的性能。Texas大學(xué)Austin分校等科研機(jī)構(gòu)的研究人員,就如何利用GPU提高M(jìn)apReduce的執(zhí)行性能展開了研究[138，140],并且擴(kuò)展了MapReduce的應(yīng)用領(lǐng)域.清華大學(xué)和IBM實(shí)驗(yàn)室的研究人員提出了Map CG[141],在源代碼級(jí)提供CPU編程和GPU編程的可移植性,大大提高了MapReduce程序編寫的容易程度[19]。</p><p>　?、谒饕夹g(shù)與連接技術(shù)的優(yōu)化[19]&l

74、t;/p><p>　　文獻(xiàn)[112]研究了非侵入式的MapReduce性能提升技術(shù),包括特洛伊索引(Trojan index)和分區(qū)數(shù)據(jù)并置(co-partition,即把需要連接的數(shù)據(jù)分區(qū)保存到同一個(gè)節(jié)點(diǎn)或者在網(wǎng)絡(luò)拓?fù)渖辖咏墓?jié)點(diǎn),以加快數(shù)據(jù)分區(qū)之間的Join操作)技術(shù)等.文獻(xiàn)[113]則提出事實(shí)表上的虛擬視圖(virtual view over fact table)、事實(shí)表和維表連接的優(yōu)化、基于列存儲(chǔ)的壓縮(c

75、olumnar compression)等技術(shù),提高了MapReduce環(huán)境下星型模型上的OLAP類應(yīng)用的執(zhí)行性能.文獻(xiàn)[114]通過對(duì)MapReduce執(zhí)行函數(shù)的分析,對(duì)MapReduce查詢進(jìn)行改寫,充分利用SQL數(shù)據(jù)庫(kù)的索引、聚集函數(shù)等功能,提高M(jìn)apReduce函數(shù)的執(zhí)行效率。 </p><p>　?、壅{(diào)度技術(shù)優(yōu)化[19]</p><p>　　文獻(xiàn)[118]試圖利用基于優(yōu)先級(jí)的調(diào)度

76、策略提高M(jìn)apReduce的運(yùn)行效率.文獻(xiàn)[119]提出了基于MPI的MapReduce優(yōu)化實(shí)現(xiàn),利用MPI-3的新特性,比如MPI Reduce Local等,在127個(gè)節(jié)點(diǎn)的集群上獲得25%的性能提升.Toronto大學(xué)和Boston大學(xué)的研究人員[120]嘗試在多個(gè)MapReduce Job之間進(jìn)行查詢處理工作的共享,以此提高系統(tǒng)的總體吞吐能力。Barcelona超級(jí)計(jì)算中心和IBM Watson實(shí)驗(yàn)室的研究人員研究了任務(wù)聯(lián)合調(diào)度

77、[19]。</p><p>　?。?）高速數(shù)據(jù)流的大規(guī)模處理[19]</p><p>　　針對(duì)高速數(shù)據(jù)流的大規(guī)模處理，文獻(xiàn)[136] 提出一種支持高速數(shù)據(jù)流下大規(guī)模數(shù)據(jù)實(shí)時(shí)處理的方法RTMR（Real Time MapReduce）。RTMR的處理過程為預(yù)處理歷史數(shù)據(jù)并將中間結(jié)果分布緩存到各個(gè)節(jié)點(diǎn)上，在節(jié)點(diǎn)上基于SEDA構(gòu)造從Map階段到Reduce階段的本地階段化流水線，充分利用本地計(jì)算

78、和存儲(chǔ)資源實(shí)現(xiàn)數(shù)據(jù)流同歷史數(shù)據(jù)的實(shí)時(shí)計(jì)算。RTMR方法還包括了一種基于系統(tǒng)參數(shù)的本地階段化處理優(yōu)化方法和支持高并發(fā)讀寫的本地存儲(chǔ)方法[19][136]。</p><p>　　圖3 RTMR方法[19][136]</p><p><b>　　2.3數(shù)據(jù)融合</b></p><p>　　物聯(lián)網(wǎng)數(shù)據(jù)融合（Data Fusion）是對(duì)感知數(shù)據(jù)進(jìn)行綜合處

79、理獲取確定性信息的過程。</p><p>　　在物聯(lián)網(wǎng)中，目前國(guó)際上開展的數(shù)據(jù)融合研究主要分為兩方面：（1）基于去冗去噪目的的感知數(shù)據(jù)融合；（2）以多傳感器信息的關(guān)聯(lián)和綜合為基礎(chǔ)，以估計(jì)和預(yù)測(cè)實(shí)體狀態(tài)[163]。</p><p>　　（1） 基于去冗去噪目的的感知數(shù)據(jù)融合</p><p>　　在物聯(lián)網(wǎng)感知網(wǎng)絡(luò)中，對(duì)感知數(shù)據(jù)進(jìn)行融合處理，只將少量有意義的信息傳輸?shù)絽R聚

80、節(jié)點(diǎn)，可有效減少數(shù)據(jù)傳輸量。</p><p>　　目前，主要采用傳統(tǒng)的數(shù)據(jù)融合方法，例如概率統(tǒng)計(jì)方法、回歸分析和卡爾曼濾波等，消除冗余信息，去除噪聲和異常值。文獻(xiàn)[142]提出的分布式融合方法，采用極大似然估計(jì)實(shí)現(xiàn)了局部感知數(shù)據(jù)的估計(jì)，消除了數(shù)據(jù)異常，并解決了不同步數(shù)據(jù)的融合問題。Bayes方法也是數(shù)據(jù)融合常用的方法[20]。</p><p>　　文獻(xiàn)[143]在研究基于簇結(jié)構(gòu)的數(shù)據(jù)融合時(shí)

81、，為了解決數(shù)據(jù)收集中簇頭節(jié)點(diǎn)的數(shù)據(jù)沖突問題，采用Ｂａｙｅｓ 方法估計(jì)發(fā)送數(shù)據(jù)的節(jié)點(diǎn)數(shù)量。為了提高Bayes數(shù)據(jù)融合的計(jì)算效率，文獻(xiàn)[144]實(shí)現(xiàn)了后驗(yàn)概率的分布式計(jì)算?；谠紨?shù)據(jù)的回歸分析，可以通過少量數(shù)據(jù)獲得感知數(shù)據(jù)全局或局部的估計(jì)．例如，文獻(xiàn)[145-146]建立了感知數(shù)據(jù)的回歸模型，通過模型的回歸計(jì)算大幅減少了數(shù)據(jù)傳輸量。將傳統(tǒng)信號(hào)處理的各種濾波方法應(yīng)用于感知數(shù)據(jù)的融合，可以有效去除噪聲、消除數(shù)據(jù)冗余。常見的方法有漂移均值濾波、

82、卡爾曼濾波和粒子濾波等。文獻(xiàn)[147]將漂移均值濾波用于觀測(cè)值的數(shù)據(jù)處理以及事件和事件邊界的估計(jì)。卡爾曼濾波在觀測(cè)值預(yù)測(cè)[148] 、上下文信息預(yù)測(cè)[149]，甚至MAC層數(shù)據(jù)幀大小預(yù)測(cè)[150]等方面均有應(yīng)用。但卡爾曼濾波不能很好地處理非高斯噪聲和低采樣率的數(shù)據(jù)，因此粒子濾波方法被引入無(wú)線傳感器網(wǎng)絡(luò)的數(shù)據(jù)分析和處理中，特別是節(jié)點(diǎn)定位和跟蹤方面．例如，文獻(xiàn)[151]采用粒子濾波方法實(shí)現(xiàn)了基于網(wǎng)絡(luò)幾何屬性的目標(biāo)跟蹤[20]。</p&

83、gt;<p>　　物聯(lián)網(wǎng)數(shù)據(jù)融合還要考慮網(wǎng)絡(luò)的結(jié)構(gòu)和路由，因?yàn)榫W(wǎng)絡(luò)結(jié)構(gòu)和路由直接影響數(shù)據(jù)融合的實(shí)現(xiàn)。目前在無(wú)線感知網(wǎng)絡(luò)中經(jīng)常采用樹或分簇網(wǎng)絡(luò)結(jié)構(gòu)及路由策略。基于樹的數(shù)據(jù)融合一般是對(duì)近源匯集樹、最短路徑樹、貪婪增量樹等經(jīng)典算法的改進(jìn)。例如，文獻(xiàn)［159］提出的動(dòng)態(tài)生成樹構(gòu)造算法，通過目標(biāo)附近的節(jié)點(diǎn)構(gòu)建動(dòng)態(tài)生成樹，節(jié)點(diǎn)將觀測(cè)數(shù)據(jù)沿生成樹向根節(jié)點(diǎn)傳輸，并在傳輸過程中對(duì)其子生成樹節(jié)點(diǎn)的數(shù)據(jù)進(jìn)行融合。經(jīng)典的分簇協(xié)議LEACH[160

84、]支持簇頭節(jié)點(diǎn)的數(shù)據(jù)融合，但LEACH并未給出具體的融合方法。PEGASIS協(xié)議對(duì)LEACH的數(shù)據(jù)融合進(jìn)行了改進(jìn)，采用了鏈?zhǔn)浇Y(jié)構(gòu)獲得了更好的融合性能。但PEGASIS協(xié)議鏈的長(zhǎng)度與節(jié)點(diǎn)數(shù)量有關(guān)，對(duì)于規(guī)模較大的網(wǎng)絡(luò)會(huì)產(chǎn)生較大的延遲．PEDAP協(xié)議進(jìn)一步發(fā)展了PEGASIS協(xié)議，通過構(gòu)造最小匯集樹，將子節(jié)點(diǎn)的數(shù)據(jù)包融合為單個(gè)數(shù)據(jù)包，減少了網(wǎng)絡(luò)傳輸量。數(shù)據(jù)融合能有效減少數(shù)據(jù)傳輸量，降低數(shù)據(jù)傳輸沖突，減輕網(wǎng)絡(luò)擁塞，提高通信效率[20]。<

85、/p><p>　?。?）關(guān)聯(lián)和綜合多傳感器信息，估計(jì)和預(yù)測(cè)實(shí)體狀態(tài)</p><p>　　多傳感器數(shù)據(jù)融合國(guó)際上已開展多年的研究，最初主要應(yīng)用于軍事領(lǐng)域，目前，在民用領(lǐng)域也得到廣泛應(yīng)用。</p><p>　　多傳感器的信息之間關(guān)系為: 獨(dú)立、競(jìng)爭(zhēng)、互補(bǔ)和合作關(guān)系, 通過融合手段將有著各種關(guān)系的多源信息去偽、去粗和升華, 便可得到更加準(zhǔn)確、完備的信息, 并且這種融合還可以在

86、不同的信息層次上出現(xiàn)[164]。</p><p>　　1） 多傳感器數(shù)據(jù)融合特性[166]</p><p>　　目前，多傳感器數(shù)據(jù)融合成為一項(xiàng)非常具有挑戰(zhàn)性的任務(wù),呈現(xiàn)出不確定、多模態(tài)、高沖突、強(qiáng)相關(guān)、等諸多特性。 </p><p>　　①不確定:傳感器的觀測(cè)總會(huì)受到噪聲影響,使得其不準(zhǔn)確或者產(chǎn)生虛警等;同時(shí),雜波、多目標(biāo)的</p><p>

87、　　存在使得量測(cè)來源具有不確定性。信息融合算法需要利用冗余有效降低不確定性[166]; </p><p>　　②多模態(tài):在多傳感器系統(tǒng)中,針對(duì)同一待觀測(cè)現(xiàn)象,可能存在著聲音、視頻、文字等多模態(tài)量測(cè),</p><p>　　系統(tǒng)須具備融合這些量測(cè)的能力,給出一致理解和高品質(zhì)態(tài)勢(shì)[166]; </p><p>　　③高沖突:當(dāng)多個(gè)專家對(duì)同一現(xiàn)象給出不同意見時(shí),信息就產(chǎn)生了

88、沖突.在基于證據(jù)置信推理和Dempster組合規(guī)則的融合算法中,融合帶有沖突的數(shù)據(jù)易產(chǎn)生與直覺不一致的結(jié)果.因此,融合算法需要小心處理高沖突數(shù)據(jù)[166]; </p><p>　　④強(qiáng)相關(guān)：該問題在分布式融合中尤為重要和普遍,例如,在無(wú)線傳感器網(wǎng)絡(luò)中,一些傳感器節(jié)點(diǎn)很可能受相同噪聲的影響,產(chǎn)生有偏量測(cè).另外,在估計(jì)過程中使用近似濾波器也會(huì)造成局部節(jié)點(diǎn)估計(jì)之間相關(guān).如果不考慮數(shù)據(jù)相關(guān)性,會(huì)產(chǎn)生有偏估計(jì)[166];

89、</p><p>　?、莘蔷€性:目標(biāo)運(yùn)動(dòng)建模與量測(cè)建模坐標(biāo)系的非線性關(guān)系引起運(yùn)動(dòng)建模的非線性,分布式觀測(cè)的信息在空間變換配準(zhǔn)中引起非線性等.對(duì)非線性的處理不當(dāng)會(huì)損失有用信息[166]. </p><p>　　2）多傳感器數(shù)據(jù)融合系統(tǒng)和融合模型</p><p>　　多傳感器信息融合系統(tǒng)包含四個(gè)主要元素: 一是信息源元素, 它向系統(tǒng)提供原始的信息; 二是信息轉(zhuǎn)換、傳遞、

90、交換元素, 它完成信息的預(yù)處理; 三是信息互補(bǔ)、綜合處理元素,它完成信息的再生、升華; 四是信息融合處理報(bào)告元素, 即輸出融合處理結(jié)果[164-165]。 </p><p>　　多傳感器信息融合模型是建立系統(tǒng)模型是設(shè)計(jì)信息融合系統(tǒng)的第一步, 模型的優(yōu)劣直接決定了整個(gè)系統(tǒng)功能的好壞。目前，提出了很多的信息融合模型，可分為功能模型、結(jié)構(gòu)模型和數(shù)學(xué)模型。功能模型從融合過程出發(fā)描述信息融合, 包括主要功能、數(shù)據(jù)庫(kù), 以

91、及信息融合系統(tǒng)各組成部分之間的相互作用過程; 結(jié)構(gòu)模型從信息融合的組成出發(fā),說明信息融合系統(tǒng)的軟硬件組成、相關(guān)數(shù)據(jù)流、系統(tǒng)與外部環(huán)境的人機(jī)界面。數(shù)學(xué)模型是在一定結(jié)構(gòu)模型下信息融合算法的數(shù)學(xué)表達(dá)和綜合邏輯[163]。</p><p>　　功能模型根據(jù)融合的功能層次, 文獻(xiàn)[163]在JDL/DFS分級(jí)模型基礎(chǔ)上，按照信息抽象的不同層次，把信息融合分為五級(jí)，包括了從檢測(cè)到威脅估計(jì)的完整過程[163]。 第一級(jí)為檢測(cè)級(jí)

92、融合; 第二級(jí)為位置融合; 第三個(gè)級(jí)為目標(biāo)識(shí)別信息融合; 第四和第五分別為態(tài)勢(shì)估計(jì)和威脅估計(jì)。 在這種功能模型描述中, 前三個(gè)層次的信息融合適用于任意的多傳感器信息融合系統(tǒng), 而后兩個(gè)層次主要適用于軍事C4 ISR中的信息融合[163]。</p><p>　　從分布檢測(cè)的角度看, 檢測(cè)級(jí)融合結(jié)構(gòu)主要有5 種, 即分散式結(jié)構(gòu)、并行結(jié)構(gòu)、串行結(jié)構(gòu)、樹狀結(jié)構(gòu)和帶反饋并行結(jié)構(gòu)[163]。從多傳感器系統(tǒng)的信息流通形式和綜合

93、處理層次上看, 位置級(jí)融合結(jié)構(gòu)主要有4 種, 即集中式、分布式、混合式和多級(jí)式[163]。 屬性級(jí)數(shù)據(jù)融合結(jié)構(gòu)主要有3 種: 決策層屬性融合, 特征層屬性融合和數(shù)據(jù)層屬性融合[163] . </p><p>　　3）多傳感器數(shù)據(jù)融合算法</p><p>　　多傳感器信息融合技術(shù)發(fā)展到現(xiàn)在, 已產(chǎn)生了很多融合算法, 但是這些融合算法大都是根據(jù)具體的問題而提出的, 對(duì)特定領(lǐng)域的問題能獲得最優(yōu)效

94、果。 因此, 現(xiàn)有的融合算法都有其一定的適用范圍。根據(jù)不同的準(zhǔn)則, 常用的多傳感器信息融合有不同的分類方法. 一種分類法將常用的融合算法概括為兩大類: 經(jīng)典方法和現(xiàn)代方法. 經(jīng)典的融合算法是基于經(jīng)典數(shù)學(xué)方法的一類融合算法. 該類算法主要有: 貝葉斯估計(jì)( Bay esian Inference)、加權(quán)平均法( Weig hted A ver ag e Method) 、極大似然估計(jì)( Max imun Likelihoo d) 、D-

95、S 證據(jù)理論( Dempster- Shafer Inference)、卡爾曼濾波( Kalman Filter)等. 現(xiàn)代融合算法是根據(jù)人工智能理論、現(xiàn)代信息論等的發(fā)展而發(fā)展起來的一類融合算法. 該類算法常用的主要有: 聚類分析( Cluster A nalysis) 、模糊邏輯( Fuzzy Lo gic) 、神經(jīng)網(wǎng)絡(luò)( Neur al Netw orks) 、小波理論( Wavelet Theory) 、粗糙集理論(</p&

96、gt;<p>　　表1.. 融合算法[164]</p><p>　?、俨淮_定信息融合[166]</p><p>　　線性高斯條件下的估計(jì)融合理論已經(jīng)成熟,在這里主要介紹非線性非高斯條件下的濾波估計(jì)進(jìn)展以及隨機(jī)集理論[166].</p><p>　　針對(duì)非線性非高斯條件下的濾波問題,近年來人們提出了大量次優(yōu)的近似方法.這些次優(yōu)濾波器可以分為4大類[166

97、] [174]:解析近似、數(shù)值逼近、高斯和濾波以及采樣近似.解析近似方法包括擴(kuò)展卡爾曼濾波器(EKF)、高階EKF、迭代EKF等,其主要特征是通過線性化逼近狀態(tài)和量測(cè)方程.數(shù)值方法也稱為基于網(wǎng)格的逼近方法,通過沿離散變量求和代替積分.為了得到連續(xù)狀態(tài)空間比較好的逼近,網(wǎng)格必須足夠密集.隨著狀態(tài)空間維數(shù)的增加,計(jì)算量也急劇增加.高斯和逼近(Gaussian sum approximation)通過選擇適當(dāng)?shù)母咚够旌蟼€(gè)數(shù),得到要求的逼近精度

98、,當(dāng)后驗(yàn)分布是多峰值時(shí),這種逼近是很合理的,然而很難在線計(jì)算各個(gè)高斯分布權(quán)重,并且混合個(gè)數(shù)可能隨時(shí)間呈指數(shù)增加.由于近似非線性函數(shù)的概率密度分布比近似非線性函數(shù)更容易,使用采樣方法近似非線性分布來解決非線性問題的途徑在得到廣泛關(guān)注. UKF[166] [175]、高斯厄米特濾波器(GHF) [174]、中心差分濾波器(CDF) [176]、分離差分濾波器(DDF[176-177])、粒子濾波器(particle filter, PF)及

99、其各種變形等就</p><p>　　由于PF在理論上能夠近似任意的概率密度,適用于強(qiáng)非線性非高斯問題,在采樣型非線性濾波器</p><p>　　中最受關(guān)注. PF利用狀態(tài)空間的一組帶權(quán)隨機(jī)樣本(粒子)逼近狀態(tài)變量的后驗(yàn)概率分布,每個(gè)樣本代表</p><p>　　系統(tǒng)的一個(gè)可能狀態(tài),是基于蒙特卡羅(Monte Carlo, MC)仿真的方法.在實(shí)現(xiàn)過程中, PF一般包

100、括序貫</p><p>　　重要性采樣和重采樣兩個(gè)步驟.由于存在退化問題,在研究和發(fā)展過程中, PF算法得到許多改進(jìn),這些</p><p>　　改進(jìn)主要圍繞增加粒子的多樣性和重要性分布函數(shù)的選擇,包括馬爾可夫鏈蒙特卡洛(MCMC)改進(jìn)策</p><p>　　略、Unscented粒子濾波器、輔助粒子濾波器(APF)、 Rao-Blackwellised粒子濾波器(R

101、BPF)、正則化粒子濾波器(RPF)等[166] [177]。高維狀態(tài)空間時(shí)計(jì)算量過大是PF在應(yīng)用過程中面臨的一個(gè)難題.針對(duì)該問題, MCMC算法是一種可選擇的替代方法,其基本思想是通過構(gòu)造馬爾可夫鏈產(chǎn)生來自目標(biāo)分布的樣本.當(dāng)?shù)螖?shù)充分大時(shí),馬爾可夫鏈趨于一個(gè)平穩(wěn)密度. MCMC有許多方法,常用的有Metropolis-Hastings算法 [178]和Gibbs采樣器 [179]. Metropolis-Hastings算法對(duì)樣本的

102、初始化和切換分布較為敏感,如果選擇不適,則收斂過程緩慢.而Gibbs采樣器可以作為Metropolis-Hastings的一個(gè)特例.另外一個(gè)方法是Rao-Blackwellised化[180]也稱為邊緣化PF(marginalized particle filters),其思想(,) 是對(duì)某些狀態(tài)空間模型,狀態(tài)向量的一部分在其余部分條件下的后驗(yàn)分布可以用解析方法求得,例如某些狀態(tài)是條件線性高斯模型,可用卡爾曼濾波器得到條件后驗(yàn)分布,對(duì)另