無線傳感器網絡集成了微型計算機技術，分布式計算技術和現代網絡技術等，已經成為當今實具高效影響力的重要技術，本文主要研究無線傳感器網絡數據收集問題。

　　《電子科技大學學報》(雙月刊)創刊于1999年，是由電子科技大學主辦的刊物。本學報主要反映學校學科建設、教學科研成果以及管理水平的高級社會科學學術刊物，面向國內外公開發行。

　　數據收集是無線傳感器網絡中的重要研究問題之一。其基本原理是通過傳感器節點的自組織而形成網絡，將采集到的數據通過多跳的形式發送到基站進行相應處理的實現過程。

　　數據收集問題研究外界用戶如何通過無線傳感器網絡從監控區域收集感知數據。傳感器節點通過自組織方式構成網絡，數據收集問題就是尋找高效可靠的方式將感知數據通過多跳的方式傳輸給用戶進行分析和處理。近幾年對數據收集問題的研究非常廣泛，主要包含減少數據收集過程中的數據傳輸量、數據收集協議和大規模網絡數據收集調度等問題。從以上幾方面對數據收集問題進行綜述。

　　無線傳感器網絡，通常包括傳感器，匯聚節點和基站。傳感器節點數據經過多個節點后最終到達Sink節點，其后再通過Internet網絡或衛星網絡傳輸給用戶。用戶處理數據后，通過sink節點向網絡發送控制命令以及調度命令。傳感器節點由電池供電，其節點能量有限[4]。無線傳感器網絡具有動態性強、監測數據量大、但其通信能力、供電能力和計算能力均屬有限等特點。現實中的無線傳感器網絡主要應用在工業控制[5]、智能家居[6]、醫療護理[7]、農業和環境監測[8]以及目標跟蹤[9]和物流管理[10]等方面。

　　在傳感器網絡的很多應用中，數據收集需要傳輸大量的感知數據。大量感知數據在網絡中傳輸，會產生大量通信開銷。通信開銷是傳感器網絡最重要的能量消耗方式。據統計，數據傳輸消耗的能量占整個傳感器網絡能量消耗的80%。減少數據傳輸量，即能夠降低能量開銷，從而延長網絡生命周期。數據收集算法中，有多種方法可以減少數據傳輸量。例如，基于采樣的數據收集方法，基于數據壓縮的數據收集方法以及基于數據共享的數據收集方法。

　　傳感器網絡數據收集問題的覆蓋范圍非常廣泛，從數據收集協議、到多信道調度，從靜態網絡、到可移動網絡數據收集等，都存在著大量的研究問題。本文將從如何減少數據收集過程中的數據傳輸量、數據收集協議和大規模網絡數據收集調度等幾方面對數據收集問題進行系統分析和專題介紹。

　　1基于采樣的數據收集方法

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

　　2基于數據聚集的數據收集方法

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

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

　　3基于多任務數據共享的數據收集方法

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

　　無線傳感器網絡中數據共享問題的研究目標是在多任務共享的傳感器網絡中，采集最少的數據，從而滿足所有任務的需求。傳感器網絡中查詢優化問題也需要收集盡量最少的數據滿足各個查詢的要求[42-43]。但其中需要解決的問題通常是如何在網內進行分布式調度，再通過數據聚集來減少數據量。

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

　　4數據收集過程中路由協議問題的研究

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

　　5數據收集過程中調度問題的研究

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

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

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

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

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

　　文獻[66，71]針對UDG網絡和非UDG網絡提出兩種調度算法。算法中，針對UDG網絡所提出的算法上界為8μαΔ(T)。其中，μα是與方格大小有關的函數，Δ(T)是所構建路由樹的度。針對非UDG網絡所提出的算法上界為O(Δ(T)logn)。其中，(T)是所構建路由樹的度，n是網絡中的節點個數。這兩種算法都是集中式的。

　　多信道調度的研究工作還包括多電臺多信道調度的研究[75-77]。多電臺多信道網絡中每個節點包含多個收發裝置，每個收發裝置可以獨立地進行數據收發工作，如此即可進一步提高數據傳輸能力。

　　6結束語

　　用戶進行區域監測、事件發現、事件挖掘以及事件預測等操作，都需要將網絡中的傳感器數據收集到基站進行處理，因此數據收集問題成為傳感器網絡中的焦點研究內容之一。本文從如何減少數據收集過程的數據量、如何減少數據聚集過程的數據量以及數據收集過程中的路由協議和調度問題幾方面對數據收集問題進行了闡述，介紹了當前數據收集問題的研究工作，并針對相關研究工作分別進行了分析和介紹。參考文獻：

　　[1]李建中，李金寶，石勝飛.傳感器網絡及其數據管理的概念、問題與進展[J].軟件學報，2003，14(10)：1717–1727.

　　[2]孫利民，李建中，陳渝.無線傳感器網絡[M].北京：清華大學出版社，2005.