數(shù)據(jù)收集問題一直是計(jì)算機(jī)技術(shù)領(lǐng)域研究的熱點(diǎn)，近些年，無線傳感器網(wǎng)絡(luò)數(shù)據(jù)技術(shù)日漸成熟，本文主要研究無線傳感器網(wǎng)絡(luò)數(shù)據(jù)的工作原理。

　　《電子科技》創(chuàng)刊于1987年，國(guó)家新聞出版總署出版規(guī)范首批A類期刊，陜西省優(yōu)秀期刊。主要刊登高等院校、科研院所、電子行業(yè)企事業(yè)單位等科研機(jī)構(gòu)在電子技術(shù)應(yīng)用、通信工程、計(jì)算機(jī)科學(xué)技術(shù)與應(yīng)用、網(wǎng)絡(luò)安全及信息、光電子材料等領(lǐng)域最新的學(xué)術(shù)、技術(shù)論文、工程技術(shù)應(yīng)用研究、教學(xué)實(shí)踐總結(jié)、行業(yè)綜述等稿件。

　　無線傳感器網(wǎng)絡(luò)集成了微型計(jì)算機(jī)技術(shù)，分布式計(jì)算技術(shù)和現(xiàn)代網(wǎng)絡(luò)技術(shù)等[1-3]，已經(jīng)成為當(dāng)今實(shí)具高效影響力的重要技術(shù)。數(shù)據(jù)收集是無線傳感器網(wǎng)絡(luò)中的重要研究問題之一。其基本原理是通過傳感器節(jié)點(diǎn)的自組織而形成網(wǎng)絡(luò)，將采集到的數(shù)據(jù)通過多跳的形式發(fā)送到基站進(jìn)行相應(yīng)處理的實(shí)現(xiàn)過程。

　　數(shù)據(jù)收集問題研究外界用戶如何通過無線傳感器網(wǎng)絡(luò)從監(jiān)控區(qū)域收集感知數(shù)據(jù)。傳感器節(jié)點(diǎn)通過自組織方式構(gòu)成網(wǎng)絡(luò)，數(shù)據(jù)收集問題就是尋找高效可靠的方式將感知數(shù)據(jù)通過多跳的方式傳輸給用戶進(jìn)行分析和處理。近幾年對(duì)數(shù)據(jù)收集問題的研究非常廣泛，主要包含減少數(shù)據(jù)收集過程中的數(shù)據(jù)傳輸量、數(shù)據(jù)收集協(xié)議和大規(guī)模網(wǎng)絡(luò)數(shù)據(jù)收集調(diào)度等問題。從以上幾方面對(duì)數(shù)據(jù)收集問題進(jìn)行綜述。

　　0引言

　　無線傳感器網(wǎng)絡(luò)，通常包括傳感器，匯聚節(jié)點(diǎn)和基站。傳感器節(jié)點(diǎn)數(shù)據(jù)經(jīng)過多個(gè)節(jié)點(diǎn)后最終到達(dá)Sink節(jié)點(diǎn)，其后再通過Internet網(wǎng)絡(luò)或衛(wèi)星網(wǎng)絡(luò)傳輸給用戶。用戶處理數(shù)據(jù)后，通過sink節(jié)點(diǎn)向網(wǎng)絡(luò)發(fā)送控制命令以及調(diào)度命令。傳感器節(jié)點(diǎn)由電池供電，其節(jié)點(diǎn)能量有限[4]。無線傳感器網(wǎng)絡(luò)具有動(dòng)態(tài)性強(qiáng)、監(jiān)測(cè)數(shù)據(jù)量大、但其通信能力、供電能力和計(jì)算能力均屬有限等特點(diǎn)�，F(xiàn)實(shí)中的無線傳感器網(wǎng)絡(luò)主要應(yīng)用在工業(yè)控制[5]、智能家居[6]、醫(yī)療護(hù)理[7]、農(nóng)業(yè)和環(huán)境監(jiān)測(cè)[8]以及目標(biāo)跟蹤[9]和物流管理[10]等方面。

　　在傳感器網(wǎng)絡(luò)的很多應(yīng)用中，數(shù)據(jù)收集需要傳輸大量的感知數(shù)據(jù)。大量感知數(shù)據(jù)在網(wǎng)絡(luò)中傳輸，會(huì)產(chǎn)生大量通信開銷。通信開銷是傳感器網(wǎng)絡(luò)最重要的能量消耗方式。據(jù)統(tǒng)計(jì)，數(shù)據(jù)傳輸消耗的能量占整個(gè)傳感器網(wǎng)絡(luò)能量消耗的80%。減少數(shù)據(jù)傳輸量，即能夠降低能量開銷，從而延長(zhǎng)網(wǎng)絡(luò)生命周期。數(shù)據(jù)收集算法中，有多種方法可以減少數(shù)據(jù)傳輸量。例如，基于采樣的數(shù)據(jù)收集方法，基于數(shù)據(jù)壓縮的數(shù)據(jù)收集方法以及基于數(shù)據(jù)共享的數(shù)據(jù)收集方法。

　　傳感器網(wǎng)絡(luò)數(shù)據(jù)收集問題的覆蓋范圍非常廣泛，從數(shù)據(jù)收集協(xié)議、到多信道調(diào)度，從靜態(tài)網(wǎng)絡(luò)、到可移動(dòng)網(wǎng)絡(luò)數(shù)據(jù)收集等，都存在著大量的研究問題。本文將從如何減少數(shù)據(jù)收集過程中的數(shù)據(jù)傳輸量、數(shù)據(jù)收集協(xié)議和大規(guī)模網(wǎng)絡(luò)數(shù)據(jù)收集調(diào)度等幾方面對(duì)數(shù)據(jù)收集問題進(jìn)行系統(tǒng)分析和專題介紹。

　　1基于采樣的數(shù)據(jù)收集方法

　　文獻(xiàn)[11]提出一種大規(guī)模傳感器網(wǎng)絡(luò)中近似K-中位數(shù)計(jì)算方法。K-中位數(shù)是指，給定一個(gè)集合S，在集合S中找出第K小的值，n為S集合的大小。文獻(xiàn)[12]提出基于采樣的(ε，δ)-近似聚集算法。通過采樣，可使得到的結(jié)果誤差在ε界限內(nèi)的概率不大于δ。文獻(xiàn)[13]則在對(duì)一小部分傳感器節(jié)點(diǎn)數(shù)據(jù)采樣至融合中心后，再估計(jì)感知環(huán)境，并指導(dǎo)網(wǎng)絡(luò)資源分配。具體地講，融合中心根據(jù)估計(jì)的感知環(huán)境情況，有選擇地激活某些節(jié)點(diǎn)，從而滿足一定的誤差界限。這種動(dòng)態(tài)采樣方法可以有效節(jié)省能量開銷。文獻(xiàn)[14]提出一種在線算法，在給定能量開銷上界的情況下最小化近似比誤差。該種算法是基于區(qū)域采樣，將網(wǎng)絡(luò)劃分為多個(gè)不重疊的區(qū)域，并通過計(jì)算近似聚集結(jié)果來滿足事先設(shè)定的能量預(yù)算。文獻(xiàn)[15]采用基于卡爾曼濾波的估計(jì)方法來自動(dòng)動(dòng)態(tài)地調(diào)整采樣速率，從而降低傳輸量，提高估計(jì)精度。文獻(xiàn)[16]提出一種近似隨機(jī)的采樣方法。這種方法只采樣與網(wǎng)絡(luò)規(guī)模成比例的部分節(jié)點(diǎn)，由此而達(dá)到接近隨機(jī)采樣方法的效果及精度。

　　2基于數(shù)據(jù)聚集的數(shù)據(jù)收集方法

　　文獻(xiàn)[17]研究了數(shù)據(jù)聚集操作對(duì)于網(wǎng)絡(luò)性能的影響。文獻(xiàn)[18]總結(jié)了數(shù)據(jù)壓縮的幾種方式。其中，最為常見的是通過聚集的方式盡量更少地傳輸數(shù)據(jù)。聚集操作只是在根據(jù)特定查詢的應(yīng)用中較為有效，在一般的數(shù)據(jù)收集方法中卻并不適用。文獻(xiàn)[19]研究了傳感器網(wǎng)絡(luò)數(shù)據(jù)空間相關(guān)性對(duì)數(shù)據(jù)壓縮的影響。文獻(xiàn)[20]又提出一種分布式的基于數(shù)據(jù)空間相關(guān)性的數(shù)據(jù)壓縮方法。文獻(xiàn)[21]則研究了無結(jié)構(gòu)的數(shù)據(jù)聚集方法。通常，數(shù)據(jù)聚集方法都基于樹狀或其它固定結(jié)構(gòu)，該文提出了兩種無結(jié)構(gòu)的數(shù)據(jù)聚集方法。此外，文獻(xiàn)[22]研究稀疏網(wǎng)絡(luò)中的數(shù)據(jù)聚集方法，而文獻(xiàn)[23]研究了傳感器網(wǎng)絡(luò)數(shù)據(jù)聚集方法中的安全問題。

　　無線傳感器網(wǎng)絡(luò)中，有關(guān)數(shù)據(jù)聚集操作已經(jīng)產(chǎn)生了許多的研究成果[24-29]。聚集操作一般包括求最大值、最小值、和、均值、中值以及計(jì)數(shù)等。計(jì)數(shù)操作的方法包括基于采樣的方法[30-31]、基于壓縮感知的方法[32]、基于蒙特卡羅的方法[33]以及基于統(tǒng)計(jì)分析的方法[34-35]等。而根據(jù)不同的應(yīng)用場(chǎng)景，對(duì)象檢測(cè)技術(shù)也將有所不同。聚集算法則可分為集中式算法和分布式算法。集中式算法多是需要得到全網(wǎng)的信息，其通信開銷量一般并不適于傳感器網(wǎng)絡(luò)應(yīng)用中。人們更大程度上用的是分布式聚集算法。分布式聚集算法包括基于分簇的算法、基于多路徑的算法以及基于聚集樹的算法[36]。第1期方效林，等：無線傳感器網(wǎng)絡(luò)數(shù)據(jù)收集問題綜述智能計(jì)算機(jī)與應(yīng)用第4卷

　　3基于多任務(wù)數(shù)據(jù)共享的數(shù)據(jù)收集方法

　　多應(yīng)用共享傳感器網(wǎng)絡(luò)可以提高網(wǎng)絡(luò)的利用率[37-40]。但是多任務(wù)共享一個(gè)傳感器網(wǎng)絡(luò)卻會(huì)增加網(wǎng)絡(luò)的計(jì)算和通信開銷，從而降低網(wǎng)絡(luò)的生命周期。傳輸盡量最少的數(shù)據(jù)滿足多應(yīng)用的查詢要求是一種降低通信開銷的有效方法。文獻(xiàn)[41]研究多任務(wù)數(shù)據(jù)共享問題。但在其所研究的問題中，每個(gè)任務(wù)只是需要在各自的周期內(nèi)采集一個(gè)數(shù)據(jù)。

　　無線傳感器網(wǎng)絡(luò)中數(shù)據(jù)共享問題的研究目標(biāo)是在多任務(wù)共享的傳感器網(wǎng)絡(luò)中，采集最少的數(shù)據(jù)，從而滿足所有任務(wù)的需求。傳感器網(wǎng)絡(luò)中查詢優(yōu)化問題也需要收集盡量最少的數(shù)據(jù)滿足各個(gè)查詢的要求[42-43]。但其中需要解決的問題通常是如何在網(wǎng)內(nèi)進(jìn)行分布式調(diào)度，再通過數(shù)據(jù)聚集來減少數(shù)據(jù)量。

　　數(shù)據(jù)庫(kù)系統(tǒng)中涉及到的多查詢優(yōu)化問題也有需要減少數(shù)據(jù)量的情況[44-45]。但是這類問題更多的是強(qiáng)調(diào)如何最大化公共表達(dá)式，再通過限制查詢量來減少數(shù)據(jù)量。多查詢優(yōu)化問題可通過尋找SQL公共表達(dá)式減少不必要的重復(fù)子查詢。Krishnamurthy等人研究數(shù)據(jù)流系統(tǒng)中聚集查詢的數(shù)據(jù)共享問題[46]。研究者們主要解決處理諸如min、max、sum以及count等聚集查詢。在其所研究的問題中，數(shù)據(jù)流至少需要被掃描一次，并分成多個(gè)碎片。只有被多個(gè)查詢重疊覆蓋的碎片才可以得到共享。

　　4數(shù)據(jù)收集過程中路由協(xié)議問題的研究

　　無線傳感器網(wǎng)絡(luò)(WirelessSensorNetworks)通過大量部署在監(jiān)測(cè)區(qū)域內(nèi)的傳感器節(jié)點(diǎn)采集網(wǎng)絡(luò)覆蓋區(qū)域內(nèi)感知對(duì)象的信息，并通過多跳的無線通信方式將收集處理后的信息提供給終端用戶。路由算法是數(shù)據(jù)收集的基本問題，所有數(shù)據(jù)都需要通過路由方法發(fā)送至基站進(jìn)行相關(guān)處理。傳感器網(wǎng)絡(luò)中具有多種路由協(xié)議，包括Gossiping協(xié)議[47]、SPIN協(xié)議[48]、DirectedDiusion協(xié)議[49]、Rumor協(xié)議[50]、LEACH協(xié)議[51]等等。在數(shù)據(jù)收集過程中，使用較多的路由協(xié)議作為樹狀路由和地理路由等。而在無線傳感器網(wǎng)絡(luò)中，地理路由協(xié)議則使得數(shù)據(jù)包可以通過多跳無線傳輸?shù)竭_(dá)指定地理位置附近的節(jié)點(diǎn)，因而具備了廣泛的應(yīng)用前景。目前，已經(jīng)實(shí)現(xiàn)了很多關(guān)于地理路由算法的研究工作，其基本過程大體一致，都是在貪心模式失敗時(shí)轉(zhuǎn)入周邊模式。

　　5數(shù)據(jù)收集過程中調(diào)度問題的研究

　　在傳感器網(wǎng)絡(luò)的眾多應(yīng)用中，數(shù)據(jù)收集需要傳輸大量的感知數(shù)據(jù)。大量感知數(shù)據(jù)通過路由方法轉(zhuǎn)發(fā)給sink節(jié)點(diǎn)，必然引起數(shù)據(jù)沖突。數(shù)據(jù)沖突不但會(huì)導(dǎo)致重傳，從而降低吞吐量，而且還會(huì)導(dǎo)致數(shù)據(jù)丟失。TDMA方法是一種能夠在高負(fù)載網(wǎng)絡(luò)中避免沖突，提高吞吐量的有效方法[52-54]�，F(xiàn)今已經(jīng)涌現(xiàn)了許多關(guān)于TDMA的工作，這些工作的目的都在于如何減少TDMA時(shí)間槽數(shù)或者設(shè)計(jì)分布式TDMA算法[55-57]。但是這些研究工作卻都是針對(duì)一般數(shù)據(jù)通信而設(shè)計(jì)的TDMA算法。文獻(xiàn)[58]研究基于TDMA的數(shù)據(jù)收集問題。給定一棵路由樹及其對(duì)應(yīng)的干擾圖，每個(gè)節(jié)點(diǎn)都要向基站發(fā)送數(shù)據(jù)，目標(biāo)是找到最小的時(shí)間槽數(shù)，使得所有節(jié)點(diǎn)數(shù)據(jù)都能發(fā)送到基站。文獻(xiàn)[58]證明了這個(gè)問題的復(fù)雜性，并給出兩個(gè)算法。一個(gè)是基于節(jié)點(diǎn)的調(diào)度算法，另一個(gè)是基于分層的調(diào)度算法。該文獻(xiàn)還對(duì)提出的算法進(jìn)行了分析，但并未給出近似比。此外，減少數(shù)據(jù)沖突，提高網(wǎng)絡(luò)吞吐量的另一個(gè)有效方法則是采用多信道技術(shù)。多信道通信中，不同的信道將互不干擾。通過多信道機(jī)制，盡可能地使得多個(gè)鏈路在同一時(shí)間進(jìn)行通信，從而提高網(wǎng)絡(luò)的吞吐量�，F(xiàn)在已經(jīng)獲得了大量多信道調(diào)度問題的研究工作成果。文獻(xiàn)[59-61]研究聚集操作的多信道調(diào)度問題。文獻(xiàn)[62-64]探討了多信道MAC協(xié)議。文獻(xiàn)[65]實(shí)現(xiàn)了在網(wǎng)絡(luò)中建立多棵樹，每棵樹使用不同的信道，以此來提高網(wǎng)絡(luò)的吞吐量。文獻(xiàn)[66]則研究了多信道快速數(shù)據(jù)收集過程的吞吐量與延時(shí)的權(quán)衡問題。

　　已有的多信道研究中都選擇信道間頻距足夠大的信道，以保證信道間正交無干擾。但是這種選擇卻會(huì)導(dǎo)致可利用的信道數(shù)減少。有研究表明，適當(dāng)減小頻距，增加可用的信道數(shù)，能夠提高網(wǎng)絡(luò)的吞吐量。在數(shù)據(jù)收集過程中，一般均以樹狀路由進(jìn)行數(shù)據(jù)傳輸。研究中需要考慮如何進(jìn)行TDMA以及多信道調(diào)度，使得網(wǎng)絡(luò)中所有節(jié)點(diǎn)的數(shù)據(jù)能夠以最短的時(shí)間到達(dá)樹根的問題。同時(shí)，還需考慮信道間發(fā)生干擾時(shí)，如何使得因信道間干擾而造成的數(shù)據(jù)丟失最少的問題。

　　已有大量的工作表明多信道復(fù)用可以極大提高網(wǎng)絡(luò)的吞吐量[67-69]。近年來已開發(fā)了很多的多信道傳輸協(xié)議，例如MCMAC[70]，TMMAC[71]，MMSN[63]等。然而，這些工作使得為網(wǎng)絡(luò)中每一條鏈路分配時(shí)間槽，實(shí)現(xiàn)彼此之間互不干擾成為可能。其實(shí)針對(duì)數(shù)據(jù)聚集網(wǎng)絡(luò)中的多信道調(diào)度問題，只需要對(duì)所構(gòu)建路由樹上的鏈路，而不是網(wǎng)內(nèi)所有鏈路進(jìn)行時(shí)間槽分配即可實(shí)現(xiàn)與完成。

　　全網(wǎng)數(shù)據(jù)收集與數(shù)據(jù)聚集問題表現(xiàn)了一定的相關(guān)性[72]，但是并不完全相同。全網(wǎng)數(shù)據(jù)收集算法的目標(biāo)是收集網(wǎng)內(nèi)所有節(jié)點(diǎn)的原始數(shù)據(jù)，而數(shù)據(jù)聚集算法卻是收集聚集結(jié)果。最小化延時(shí)是數(shù)據(jù)收集問題的一個(gè)研究?jī)?nèi)容[102-103]。Gandham等人提出一調(diào)度算法[73]，算法實(shí)現(xiàn)需要3N個(gè)時(shí)間槽。其中，N為節(jié)點(diǎn)個(gè)數(shù)。Yu等人提出另一調(diào)度算法[74]，實(shí)現(xiàn)需要24D+6Δ+16個(gè)時(shí)間槽。其中，D是網(wǎng)絡(luò)的直徑，Δ是最大節(jié)點(diǎn)度數(shù)。這些工作的目標(biāo)都是減少延時(shí)，使得數(shù)據(jù)最早發(fā)送到基站。Wu等人又提出一多信道數(shù)據(jù)收集協(xié)議TMCP(Tree-basedMulti-ChannelProtocol)[65]。該協(xié)議將網(wǎng)絡(luò)劃分成多個(gè)子樹，樹間使用不同的信道，而樹內(nèi)使用相同的信道。其目標(biāo)是減少樹內(nèi)的干擾。

　　文獻(xiàn)[60]中，算法首先建立一棵路由樹;其次為每個(gè)節(jié)點(diǎn)分配信道，使其下的所有孩子節(jié)點(diǎn)都以這個(gè)信道發(fā)送數(shù)據(jù);為樹內(nèi)鏈路分配時(shí)間槽，使得彼此之間互不干擾。在分配信道過程中，算法優(yōu)先分配信道給那些干擾最嚴(yán)重的節(jié)點(diǎn)，這一分配方式是集中式的，并不適合在傳感器網(wǎng)絡(luò)中應(yīng)用。文獻(xiàn)[60]中，算法的上界為maxΔ2+1，其中Δ2是網(wǎng)絡(luò)形成的圖中2跳內(nèi)鄰居節(jié)點(diǎn)的個(gè)數(shù)。令Δ(G)為圖的度，則文獻(xiàn)[60]中的算法上界為O(Δ(G)2)。

　　文獻(xiàn)[66，71]針對(duì)UDG網(wǎng)絡(luò)和非UDG網(wǎng)絡(luò)提出兩種調(diào)度算法。算法中，針對(duì)UDG網(wǎng)絡(luò)所提出的算法上界為8μαΔ(T)。其中，μα是與方格大小有關(guān)的函數(shù)，Δ(T)是所構(gòu)建路由樹的度。針對(duì)非UDG網(wǎng)絡(luò)所提出的算法上界為O(Δ(T)logn)。其中，(T)是所構(gòu)建路由樹的度，n是網(wǎng)絡(luò)中的節(jié)點(diǎn)個(gè)數(shù)。這兩種算法都是集中式的。

　　多信道調(diào)度的研究工作還包括多電臺(tái)多信道調(diào)度的研究[75-77]。多電臺(tái)多信道網(wǎng)絡(luò)中每個(gè)節(jié)點(diǎn)包含多個(gè)收發(fā)裝置，每個(gè)收發(fā)裝置可以獨(dú)立地進(jìn)行數(shù)據(jù)收發(fā)工作，如此即可進(jìn)一步提高數(shù)據(jù)傳輸能力。

　　6結(jié)束語

　　用戶進(jìn)行區(qū)域監(jiān)測(cè)、事件發(fā)現(xiàn)、事件挖掘以及事件預(yù)測(cè)等操作，都需要將網(wǎng)絡(luò)中的傳感器數(shù)據(jù)收集到基站進(jìn)行處理，因此數(shù)據(jù)收集問題成為傳感器網(wǎng)絡(luò)中的焦點(diǎn)研究?jī)?nèi)容之一。本文從如何減少數(shù)據(jù)收集過程的數(shù)據(jù)量、如何減少數(shù)據(jù)聚集過程的數(shù)據(jù)量以及數(shù)據(jù)收集過程中的路由協(xié)議和調(diào)度問題幾方面對(duì)數(shù)據(jù)收集問題進(jìn)行了闡述，介紹了當(dāng)前數(shù)據(jù)收集問題的研究工作，并針對(duì)相關(guān)研究工作分別進(jìn)行了分析和介紹。參考文獻(xiàn)：

　　[1]李建中，李金寶，石勝飛.傳感器網(wǎng)絡(luò)及其數(shù)據(jù)管理的概念、問題與進(jìn)展[J].軟件學(xué)報(bào)，2003，14(10)：1717–1727.

　　[2]孫利民，李建中，陳渝.無線傳感器網(wǎng)絡(luò)[M].北京：清華大學(xué)出版社，2005.