MR-MC無線傳感器網(wǎng)絡基于森林的數(shù)據(jù)收集研究

張偉平，郭亞紅，王蒙,3，倪林雨,3，李金寶,3

?

MR-MC無線傳感器網(wǎng)絡基于森林的數(shù)據(jù)收集研究

張偉平1，郭亞紅2，王蒙1,3，倪林雨1,3，李金寶1,3

(1. 黑龍江大學計算機科學技術學院，黑龍江哈爾濱 150080； 2. 黑龍江大學信息科學與技術學院，黑龍江哈爾濱 150080； 3. 黑龍江省數(shù)據(jù)庫與并行計算重點實驗室，黑龍江哈爾濱 150080)

傳感器網(wǎng)絡的部署環(huán)境以及節(jié)點自身的限制，導致傳感器節(jié)點很容易出現(xiàn)故障并且難以維護。在基于樹的數(shù)據(jù)收集過程中，節(jié)點故障或者鏈路擁塞會造成較高的通信時延，甚至數(shù)據(jù)丟失。針對該問題提出以森林作為路由結構進行數(shù)據(jù)收集的策略。首先提出一個建立森林的算法，然后以多棵樹作為路由結構進行數(shù)據(jù)收集。理論分析和實驗結果表明，提出的方法可以有效減少數(shù)據(jù)收集過程中的數(shù)據(jù)丟失，在有25個故障節(jié)點的情況下，3棵樹的森林路由結構收集的數(shù)據(jù)量與基于連通支配集的路由樹收集的數(shù)據(jù)量相比多55%，并且能降低數(shù)據(jù)收集的延遲。

無線傳感器網(wǎng)絡；路由樹；數(shù)據(jù)收集；延遲

1 引言

近年來，無線傳感器網(wǎng)絡因其巨大的潛力被廣泛應用于軍事領域、環(huán)境監(jiān)測、醫(yī)療和工農(nóng)業(yè)等領域中[1]。在這些應用中, 大量的傳感器節(jié)點監(jiān)測周圍的環(huán)境，并將感知的數(shù)據(jù)通過多跳路由傳輸?shù)絽R聚節(jié)點。作為無線傳感器網(wǎng)絡的主要功能之一，數(shù)據(jù)收集問題受到眾多研究者的廣泛關注。

無線傳感器網(wǎng)絡通常部署在無人值守的野外環(huán)境中，網(wǎng)絡中的傳感器節(jié)點有可能因為出現(xiàn)故障而導致無法正常工作，例如節(jié)點的電池能量耗盡、動物踩踏以及大雨雷電的破壞等。由于在無線傳感器網(wǎng)絡中進行數(shù)據(jù)收集通常使用樹作為路由結構，因此，當網(wǎng)絡中的某個節(jié)點出現(xiàn)故障時，以該節(jié)點為根的子樹上的所有數(shù)據(jù)都將無法傳輸?shù)絽R聚節(jié)點。

傳感器節(jié)點使用無線信道進行通信，多條鏈路競爭通信資源有可能會導致傳輸失敗。鏈路調(diào)度即為每條鏈路分配指定的傳輸時槽進行通信，可以提高鏈路的并行性，有效降低數(shù)據(jù)收集延遲。目前的鏈路調(diào)度方案均假設在滿足特定的干擾模型(協(xié)議干擾模型、物理干擾模型、信噪比模型等)下，每次鏈路調(diào)度都是成功的。然而在現(xiàn)實情況中，鏈路通常需要多次傳輸才能夠成功，造成這種現(xiàn)象的原因有多種，例如鏈路可能會由比特誤碼率等原因擁塞。在以樹作為路由結構的鏈路調(diào)度中, 如果某條鏈路擁塞, 那么該鏈路不會被調(diào)度直到下一個周期的調(diào)度時槽到達。此外，如果2個節(jié)點使用某個信道進行通信時出現(xiàn)擁塞，那么該信道在最近一段時間內(nèi)都會處于擁塞狀態(tài)。因此，如果鏈路的性能不穩(wěn)定，那么數(shù)據(jù)收集的延遲將會受到很大影響。

綜合上述2個方面的分析，考慮節(jié)點出現(xiàn)故障以及鏈路擁塞等原因，本文提出了一個新穎的基于協(xié)議干擾模型的以森林作為路由結構的數(shù)據(jù)收集策略。

2 相關工作

對于不同的應用環(huán)境，無線傳感器網(wǎng)絡中數(shù)據(jù)收集協(xié)議的設計目標也不盡相同，下面分別從容量和延遲等方面介紹數(shù)據(jù)收集協(xié)議的研究現(xiàn)狀。

文獻[2~6]研究了在不同類型的網(wǎng)絡中數(shù)據(jù)收集容量的問題。其中，文獻[2]分析了在任意單radio、單信道無線傳感器網(wǎng)絡中的數(shù)據(jù)收集容量問題，該文獻分別討論了當通信模型采用磁盤圖模型和一般圖模型，干擾模型分別采用協(xié)議干擾模型以及物理干擾模型時數(shù)據(jù)收集容量的上下界。文獻[3]和文獻[4]分別研究了在DR-MC無線傳感器網(wǎng)絡和大規(guī)模概率無線傳感器網(wǎng)絡中的數(shù)據(jù)收集容量問題，并分別設計了快照數(shù)據(jù)收集算法以及連續(xù)數(shù)據(jù)收集算法。文獻[5]和文獻[6]分別研究了隨機網(wǎng)絡和異步網(wǎng)絡中的數(shù)據(jù)收集容量問題。

文獻[7~12]以縮短數(shù)據(jù)收集的延遲為目標設計數(shù)據(jù)收集協(xié)議。其中，文獻[7]考慮的是建立一個低延遲的數(shù)據(jù)收集結構，文獻[8]和文獻[9]以樹作為路由結構，通過調(diào)度鏈路節(jié)約數(shù)據(jù)收集時間。針對收集決策信息問題，當時間不足以收集來自網(wǎng)絡中的所有節(jié)點的決策時，文獻[10]考慮收集具有更高可靠性的決策。文獻[11]針對城市建筑中使用的無線傳感器網(wǎng)絡設計跨層數(shù)據(jù)收集機制，通過在路徑發(fā)現(xiàn)階段使用數(shù)據(jù)轉(zhuǎn)發(fā)提高數(shù)據(jù)傳輸速率、降低延遲。文獻[12]綜合考慮了數(shù)據(jù)收集的延遲和容量問題。

此外，文獻[13]首次研究如何盡可能傳輸較少的數(shù)據(jù)，同時傳輸?shù)臄?shù)據(jù)滿足所有應用的要求。文獻[14]首次提出在大規(guī)模無線傳感器網(wǎng)絡中，通過壓縮采樣理論收集數(shù)據(jù)，該方案能夠降低整體通信負載且不會引入額外的計算。文獻[15]分別研究了基于樹和簇的數(shù)據(jù)收集和聚集協(xié)議。文獻[16]分析了數(shù)據(jù)收集、聚集和選擇的復雜度。文獻[17]設計了一個自適應的數(shù)據(jù)收據(jù)近似算法。文獻[18]提出了基于小波分段常值壓縮的數(shù)據(jù)收集方法。文獻[19]提出了一種分布式的高效節(jié)能的無線傳感器網(wǎng)絡數(shù)據(jù)收集協(xié)議。

同上述工作不同，本文研究的問題是考慮網(wǎng)絡中節(jié)點出現(xiàn)故障以及擁塞等情況，如何收集網(wǎng)絡中盡可能多的數(shù)據(jù)，并且數(shù)據(jù)收集的延遲較低。針對該問題，本文提出以森林作為路由結構進行數(shù)據(jù)收集的策略，森林表示的是具有多棵路由樹的拓撲結構。

3 建立路由結構

在大多數(shù)的應用中，節(jié)點都是密集分布在監(jiān)測區(qū)域內(nèi)的，也即一個節(jié)點通常有多個鄰居節(jié)點可以通信。為了避免由于信道競爭、節(jié)點故障等導致的大規(guī)模數(shù)據(jù)擁塞，本節(jié)提出建立多棵不相交的樹形成森林進行數(shù)據(jù)收集。這里的不相交有2個方面的含義：1) 網(wǎng)絡中不存在某個節(jié)點在任意2棵路由樹上使用除sink以外的相同節(jié)點作為父親節(jié)點，即物理鏈路不相交；2) 不存在某個節(jié)點在任意2棵樹上使用相同的信道進行數(shù)據(jù)傳輸，也即邏輯鏈路不相交。

因此，對于一個待發(fā)送數(shù)據(jù)的節(jié)點，當一棵路由樹上的父親節(jié)點出現(xiàn)故障時，可以經(jīng)由其他路由樹上的父親節(jié)點將數(shù)據(jù)發(fā)送到sink。例如，給定拓撲結構如圖1(a)所示，圖中的虛線表示節(jié)點之間可以進行通信。圖1(b)和圖1(c)是對圖1(a)給出的網(wǎng)絡拓撲使用算法1建立的2棵不相交的路由樹。從圖1中可以看到，當節(jié)點1因為出現(xiàn)故障而無法通信時，節(jié)點6和7可以通過第2棵路由樹上的節(jié)點2進行數(shù)據(jù)傳輸，避免了節(jié)點6、7、11和12的數(shù)據(jù)的丟失。

3.1 準備工作

考慮一個由個傳感器節(jié)點和一個匯聚節(jié)點sink組成的無線傳感器網(wǎng)絡，記為=(,)，其中，是網(wǎng)絡中節(jié)點構成的集合，是網(wǎng)絡中所有可能的通信鏈路集合。假設sink具有相對強大的能力，不會出現(xiàn)故障或者擁塞。假設網(wǎng)絡中的每個節(jié)點配備個radio(無線收發(fā)器)，并且網(wǎng)絡有個可利用的正交信道，記為Channel={1,2,…,C}。設和分別表示節(jié)點配備radio的通信半徑和干擾半徑，在此假設所有radio具有相同的干擾半徑和通信半徑。設hop表示節(jié)點距離sink的最短跳數(shù)，表示網(wǎng)絡的高度，即網(wǎng)絡中的節(jié)點距離sink的最大跳數(shù)。假設網(wǎng)絡采用協(xié)議干擾模型，即2個節(jié)點可以成功通信當且僅當在接收節(jié)點的干擾范圍內(nèi)沒有其他節(jié)點在同一時槽使用相同信道進行通信。

3.2 構造森林

顯然，一個節(jié)點的候選父親節(jié)點集合越大，在選擇父親節(jié)點時具有更多的可選擇性，因此，按照節(jié)點的候選父親節(jié)點個數(shù)由低到高為節(jié)點分配每棵路由樹上的父親節(jié)點。

基于森林的數(shù)據(jù)收集不會造成數(shù)據(jù)冗余，之所以選擇這種多棵樹的路由結構，只是為了避免當某一個節(jié)點出現(xiàn)問題時導致經(jīng)過該節(jié)點的數(shù)據(jù)都無法傳輸成功，現(xiàn)在有多棵路由樹，一個節(jié)點通信失敗時，數(shù)據(jù)可以通過其他的路由樹傳輸，而不是同時使用多條路由傳輸，因此不會產(chǎn)生數(shù)據(jù)冗余，也不會增大通信開銷。

例如，給定網(wǎng)絡拓撲結構如圖1(a)所示，使用算法1在建立第一棵路由樹時，首先按照候選父親節(jié)點集合的大小考慮，節(jié)點6、10、11和15都有2個候選父親節(jié)點，是最少的，所以先考慮這4個節(jié)點，節(jié)點間的順序則是按照節(jié)點編號順序列出的，因此依次考慮節(jié)點6、10、11和15，選擇父親節(jié)點加入到樹中。考慮節(jié)點7有3個候選父親節(jié)點，分別是1、2和3。那么，如果節(jié)點7選擇節(jié)點1作為父親節(jié)點則與集合干擾，因為節(jié)點6也在節(jié)點1的干擾半徑內(nèi)。如果選擇2作為父親節(jié)點則與集合干擾。如果選擇3作為父親節(jié)點則與集合干擾。因此，節(jié)點7選擇節(jié)點1作為父親節(jié)點。重復執(zhí)行上述過程，直至所有節(jié)點都加入到樹中，如圖1(b)所示。然后按照上述過程繼續(xù)構建第2棵樹，如圖1(c)所示。

算法1 構造森林

6) end for;

8) end for

end for

++;

end while

3.3 分配信道

4 數(shù)據(jù)收集策略和分析

本節(jié)提出的數(shù)據(jù)收集策略是首先將森林中每棵路由樹上的鏈路集合劃分成個無沖突的子集合，然后將個時槽作為一個周期，在每個時槽調(diào)度棵路由樹上的固定鏈路子集合，直到所有節(jié)點的數(shù)據(jù)都收集到sink。因此，網(wǎng)絡中的數(shù)據(jù)收集過程可以描述為重復執(zhí)行下述步驟直到所有節(jié)點的數(shù)據(jù)都收集到sink：設是通信時槽，在時槽調(diào)度鏈路集合中的鏈路進行數(shù)據(jù)傳輸，其中，，即對于中的任意節(jié)點，使用信道向父親節(jié)點發(fā)送數(shù)據(jù)。對于節(jié)點，如果，則稱為節(jié)點在第棵路由樹上的一個調(diào)度時間。

4.1 劃分鏈路集合

在劃分鏈路集合之前首先介紹調(diào)度時間差的定義。

(3)

算法2 劃分鏈路集合

1)1;

3)1;

9) end for

14) end for

15);

16) end while

17);

18)end while

4.2 理論分析

下面對本文提出的基于森林的數(shù)據(jù)收集策略進行理論分析，并舉例子進行說明。

定理1 給定一個個節(jié)點組成的傳感器網(wǎng)絡，高度為，可以建立棵不相交的樹，設在一次數(shù)據(jù)收集中節(jié)點出現(xiàn)故障的平均概率是，那么sink平均可以收集到個數(shù)據(jù)。

以一個例子進行說明，假設網(wǎng)絡中有100個節(jié)點，網(wǎng)絡高度為12層，節(jié)點的平均故障概率為0.05, 每個節(jié)點傳送一個數(shù)據(jù)分組的時間為1個單位時間，節(jié)點傳輸數(shù)據(jù)失敗，重傳一個數(shù)據(jù)分組所需時間為1.2，并假設網(wǎng)絡拓撲可以構造出包含3棵樹的森林。那么，根據(jù)定理1中的公式，以3棵路由樹收集數(shù)據(jù)時sink可以收集到大約個數(shù)據(jù)分組，由于數(shù)據(jù)重傳所產(chǎn)生的延遲為51.2=6個單位時間。而在以一棵樹作為路由結構的數(shù)據(jù)收集中，sink可以成功接收到的數(shù)據(jù)分組個數(shù)為，由于數(shù)據(jù)重傳所產(chǎn)生的延遲為261.2=31.2個單位時間。

5 模擬實驗與結果分析

本文采用Microsoft Visual C++ 6.0編程環(huán)境模擬無線傳感器網(wǎng)絡，假設400個傳感器節(jié)點均勻隨機地分布在的監(jiān)測區(qū)域內(nèi)，sink位于網(wǎng)絡的中間位置，網(wǎng)絡高度為12層，節(jié)點的通信半徑和干擾半徑均設置為5 m。假設傳感器網(wǎng)絡的MAC層使用TDMA協(xié)議工作，即時間可以劃分成若干個時槽。節(jié)點每個可利用的信道都有相同的帶寬，設為1。假設每個節(jié)點使用的任意2個不同的信道都是正交的，即每個節(jié)點在任意2個信道上的通信不存在干擾。設網(wǎng)絡中節(jié)點出現(xiàn)故障的概率是5%，sink收集數(shù)據(jù)的成功率為95%，則根據(jù)定理1可以得到森林中需要構建的樹的棵數(shù)為3。

假設每個節(jié)點每次產(chǎn)生一個數(shù)據(jù)，該數(shù)據(jù)可以在一個時槽內(nèi)成功傳輸對于數(shù)據(jù)收集，所有節(jié)點在指定時間的所有感知數(shù)據(jù)集合稱為一個快照。收集一個快照的數(shù)據(jù)稱為快照數(shù)據(jù)收集，收集多個連續(xù)快照的問題稱為連續(xù)數(shù)據(jù)收集，數(shù)據(jù)收集延遲的單位是時槽。

下面分別進行節(jié)點的故障對收集到的數(shù)據(jù)量的影響實驗以及鏈路擁塞對數(shù)據(jù)收集的延遲影響的實驗。

5.1 數(shù)據(jù)收集量實驗

下面對快照數(shù)據(jù)的收集進行實驗，在該實驗中分別對比森林中包含2棵路由樹和3棵路由樹時整個網(wǎng)絡的分組丟失率，并且將其與基于連通支配集（CDS）的路由樹[3]進行對比。如圖2所示為出現(xiàn)故障的節(jié)點個數(shù)對收集到的數(shù)據(jù)量的影響情況，其中，橫坐標為出現(xiàn)故障的節(jié)點個數(shù)，在此設置為從0~25個，并且每隔5個做一次記錄，這里的故障節(jié)點個數(shù)表示在一次數(shù)據(jù)收集過程中出現(xiàn)故障的節(jié)點個數(shù)，縱坐標表示收集到的數(shù)據(jù)個數(shù)。

從圖2中可以看出，隨著出現(xiàn)故障的節(jié)點個數(shù)的不斷增多，基于連通支配集的路由樹收集到的數(shù)據(jù)量明顯減少，大約增加5個故障節(jié)點收集到的數(shù)據(jù)量降低60個左右。這是由于在一棵路由樹上一個節(jié)點的故障不僅會導致自身數(shù)據(jù)丟失，還會導致其所有子孫節(jié)點的數(shù)據(jù)丟失。而2棵路由樹和3棵路由樹丟失的數(shù)據(jù)量較低，這是由于在以森林做路由結構的情況下，一個節(jié)點出現(xiàn)故障，其孩子節(jié)點可以轉(zhuǎn)換到其他路由樹上進行數(shù)據(jù)傳輸，從而保證未出現(xiàn)故障的節(jié)點在很大程度上有到達sink的路徑。圖3是連續(xù)數(shù)據(jù)收集中隨著快照次數(shù)的增加sink收集到的數(shù)據(jù)量情況，也即收集到的數(shù)據(jù)個數(shù)隨著網(wǎng)絡使用時間的變化趨勢。如圖3所示，橫坐標表示在連續(xù)數(shù)據(jù)收集中執(zhí)行的快照次數(shù)，縱坐標表示sink收集到的數(shù)據(jù)個數(shù)。以森林作為路由結構收集到的數(shù)據(jù)量明顯高于基于CDS的路由樹收集到的數(shù)據(jù)量，并且隨著快照次數(shù)的增多，這種優(yōu)勢愈加明顯，在進行40次快照后包含3棵樹的森林仍舊可以收集一半的數(shù)據(jù)量。此外，在初始的快照收集中包含2棵樹的森林和包含3棵樹的森林收集到的數(shù)據(jù)量相差無幾，但隨著快照次數(shù)的增多，包含3棵樹的森林優(yōu)勢逐漸明顯，并且趨于穩(wěn)定。這是由于初始時出現(xiàn)故障的節(jié)點個數(shù)較少，這些故障節(jié)點的子孫節(jié)點數(shù)據(jù)可以經(jīng)由第2棵樹傳輸?shù)絪ink，而不必使用第3棵樹；當故障節(jié)點的個數(shù)隨著快照次數(shù)增加時，網(wǎng)絡中的一些節(jié)點必需使用第3棵樹才能夠傳輸數(shù)據(jù)。

圖4是節(jié)點出現(xiàn)故障的概率對收集的快照次數(shù)的影響實驗。

如圖4所示，橫坐標是在數(shù)據(jù)收集過程中節(jié)點出現(xiàn)故障的概率，縱坐標表示在連續(xù)數(shù)據(jù)收集中收集到200以上數(shù)據(jù)的快照次數(shù)，即收集到網(wǎng)絡中一半節(jié)點感知數(shù)據(jù)的快照次數(shù)。隨著節(jié)點故障概率的增加，收集200個以上數(shù)據(jù)的快照次數(shù)隨之減小，但是包含3棵樹森林的快照次數(shù)總是基于CDS路由樹的快照次數(shù)的2倍左右。

5.2 數(shù)據(jù)收集延遲實驗

在鏈路擁塞的實驗中，分別測試鏈路出現(xiàn)擁塞的概率以及擁塞的等待時間對數(shù)據(jù)收集的影響。擁塞的等待時間表示在一條鏈路出現(xiàn)擁塞后該鏈路在一段時間內(nèi)會一直處于擁塞狀態(tài)，這段時間稱為擁塞的等待時間。在實驗中分別對采用TAG算法[20]形成的單棵路由樹和包含3棵路由樹的森林數(shù)據(jù)收集的延遲進行了測試。為了實驗的公平性，在TAG路由樹數(shù)據(jù)收集過程中，令網(wǎng)絡中的每個節(jié)點仍有3個可以使用的正交信道進行通信。

圖5為鏈路出現(xiàn)擁塞的概率對數(shù)據(jù)收集延遲的影響。如圖5所示，橫坐標表示鏈路在每個調(diào)度時槽出現(xiàn)擁塞的平均概率為0~0.2，設置擁塞等待時間為3個時槽，縱坐標表示數(shù)據(jù)收集的延遲。即圖中可以看到隨著鏈路擁塞概率的增大，收集延遲也隨之增加，而以森林作路由結構的延遲要小于TAG的路由結構。這是由于在基于森林的數(shù)據(jù)收集過程中，在某一時槽一條鏈路出現(xiàn)擁塞后，該鏈路的發(fā)送節(jié)點在較短的時間內(nèi)會以其他節(jié)點作為父親節(jié)點重新傳輸失敗的數(shù)據(jù)，降低了數(shù)據(jù)的等待時間。

圖6所示為鏈路擁塞的等待時間對數(shù)據(jù)收集延遲的影響，在此設置每個時槽鏈路出現(xiàn)擁塞的概率為0.05。橫坐標為鏈路擁塞的等待時間，即0~8個時槽，縱坐標表示數(shù)據(jù)收集的延遲。從圖6中可以看到，TAG路由樹的數(shù)據(jù)收集延遲幾乎與等待時間成正比，而基于森林的數(shù)據(jù)收集延遲隨著擁塞等待時間的增加增長相對緩慢。在TAG路由樹的數(shù)據(jù)收集過程中，假設一條鏈路擁塞，如果在下一個調(diào)度時槽仍處于擁塞等待狀態(tài)，那么該鏈路的發(fā)送節(jié)點只能等待下一個調(diào)度時槽的到來。而以森林作為路由結構的數(shù)據(jù)收集過程中，該鏈路的發(fā)送節(jié)點可以使用其他路由樹的鏈路進行數(shù)據(jù)傳輸，而不必等待該鏈路恢復正常。

6 結束語

在無線傳感器網(wǎng)絡中，基于TAG路由樹的數(shù)據(jù)收集策略在節(jié)點出現(xiàn)故障時會造成較多的數(shù)據(jù)丟失，此外，節(jié)點的擁塞會造成較高的數(shù)據(jù)收集延遲。針對上述問題，本文提出建立森林作為收集網(wǎng)絡中數(shù)據(jù)的路由結構，并且設計了基于森林的數(shù)據(jù)收集算法。理論分析和實驗結果表明，在網(wǎng)絡中節(jié)點出現(xiàn)故障概率較高或者擁塞嚴重的情況下，本文提出的方法能以較低的延遲收集到網(wǎng)絡中的大部分數(shù)據(jù)。

[1] 李鳳保, 李凌. 無線傳感器網(wǎng)絡技術綜述[J]. 儀器儀表學報, 2005, 26(8): 559-561.

LI F B, LI L. Survey on wireless sensor network techniques[J]. Chinese Journal of Scientific Instrument, 2005, 26(8): 559-561.

[2] CHEN S, HUANG M, TANG S, et al. Capacity of data collection in arbitrary wireless sensor networks[J]. Parallel and Distributed Systems, 2012, 23(1): 52-60.

[3] JI S, LI Y, JIA X. Capacity of dual-radio multi-channel wireless sensor networks for continuous data collection[C]//INFOCOM, 2011 Proceedings IEEE. c2011: 1062-1070.

[4] JI S, BEYAH R, CAI Z. Snapshot/continuous data collection capacity for large-scale probabilistic wireless sensor networks[C]//INFOCOM, 2012 Proceedings IEEE. c2012: 1035-1043.

[5] CHEN S, WANG Y, LI M, et al. Data collection capacity of random- deployed wireless sensor networks[C] //Global Telecommunications Conference, 2009. IEEE. c2009: 1-6.

[6] JI S, CAI Z. Distributed data collection and its capacity in asynchronous wireless sensor networks[C] //INFOCOM, 2012 Proceedings IEEE. c2012: 2113-2121.

[7] CHENG C T, TSE C K, LAU F C M. A delay-aware data collection network structure for wireless sensor neworks[J]. Sensors Journal, 2011, 11(3): 699-710.

[8] INCEL O D, GHOSH A, KRISHNAMACHARI B, et al. Fast data collection in tree-based wireless sensor networks[J]. IEEE Transactions on Mobile Computing, 2012, 11(1): 86-99.

[9] INCEL O D, GHOSH A, KRISHNAMACHARI B. Scheduling algorithms for tree-based data collection in wireless sensor networks[M]//Theoretical Aspects of Distributed Computing in Sensor Networks. Springer Berlin Heidelberg, 2011: 407-445.

[10] SEKSAN L, EDWARD J, COYLE. Optimizing the collection of local decisions for time-constrained distributed detection in WSNs[C]// INFOCOM, 2013 Proceedings IEEE. c2013: 1923-1931.

[11] HUANG C, LIN T, CHEN L, et al. XD: a cross -layer designed data collection mechanism for mission-critical WSN in urban buildings[C]// International Conference on Mobile Data Management: Systems, Services and Middleware 2009.

[12] CHEN S, WANG Y, LI M, et al. Order-optimal data collection in wireless sensor networks: delay and capacity[C]//6th Annual IEEE Communications Society Conference on.Sensor, Mesh and Ad Hoc Communications and Networks, 2009. SECON'09. c2009: 1-9.

[13] FANG X, GAO H, LI J, et al. Application-aware data collection in Wireless Sensor Networks[C]//INFOCOM, 2013 Proceedings IEEE. c2013: 1645-1653.

[14] LUO C, WU F, SUN J, et al. Compressive data gathering for large- scale wireless sensor networks[C]//The 15th Annual International Conference on Mobile Computing and Networking. ACM, c2009: 145-156.

[15] WANG W, WANG B, LIU Z, et al. A cluster-based and tree-based power efficient data collection and aggregation protocol for wireless sensor networks[J]. Information Technology Journal, 2011, 10(3): 557-564.

[16] LI M, WANG Y, WANG Y. Complexity of data collection, aggregation, and selection for wireless sensor networks[J]. IEEE Transactions on, Computers, 2011, 60(3): 386-399.

[17] WANG C, MA H, HE Y, et al. Adaptive approximate data collection for wireless sensor networks[J]. IEEE Transactions on, Parallel and Distributed Systems, 2012, 23(6): 1004-1016.

[18] 李楊, 郭龍江, 李金寶, 等.傳感器網(wǎng)絡基于小波分段常值壓縮的數(shù)據(jù)收集研究[J]. 儀器儀表學報, 2013, 34(1):119-127.

LI Y, GUO L J, LI J B, et al. Data collection using wavelet-segment constant compression in wireless sensor networks[J]. Chinese Journal of Scientific Instrument, 2013, 34(1):119-127.

[19] 史久根, 胡小博.高效節(jié)能的無線傳感器網(wǎng)絡數(shù)據(jù)收集協(xié)議[J]. 電子測量與儀器學報, 2012, 26(5): 437-445.

SHI J G, HU X B. Energy-efficient data gathering protocol for wireless sensor networks[J]. Journal of Electronic Measurement and Instrument, 2012, 26(5): 437-445.

[20] MADDEN S, FRANKLIN M J, HELLERSTEIN J M, et al. Tag: a tiny aggregation service for ad hoc sensor networks[J]. OSDI Conf, 2002, 36(1): 1-28.

Forest based data collection in MR-MC wireless sensor networks

ZHANG Wei-ping1, GUO Ya-hong2, WANG Meng1,3, NI Lin-yu1,3, LI Jin-bao1,3

(1. School of Computer Science and Technology, Heilongjiang University, Harbin 150080, China; 2. School of Information Science and Technology, Heilongjiang University, Harbin 150080, China; 3. Key Laboratory of Database and Parallel Computing of Heilongjiang Province, Harbin 150080, China)

The limit of node itself and deployment environment of WSN result in the node was prone to failure and difficult to maintain. In the tree-based data collection process, the node failure or link congestion could result in higher communication delay, or even data loss. To solve this problem, a strategy for data collection was proposed which used forest as the routing structure. Firstly, an algorithm for the construction of forest was proposed, and then collect data through trees in the forest. Theoretical analysis and simulation results show that, the method could reduce the loss of data in the data collection process effectively, in the case of 25 fault nodes, the amount of data collected by forest routing structure of 3 trees compared to the amount of data collected from the connected dominating set is more than 55%, and reduce the latency of data collection.

WSN, routing tree, data collection, latency

TP212

A

10.11959/j.issn.1000-436x.2016051

2015-10-30；

2016-01-18

郭亞紅, jbli@hlju.edu.cn

國家自然科學基金資助項目（No.61370222, No.61300225）；黑龍江省自然科學基金資助項目（No.F201324）；黑龍江省高校科技創(chuàng)新團隊建設計劃基金資助項目（No.2013TD012）；哈爾濱市優(yōu)秀學科帶頭人基金資助項目（No.2015RAXXJ004）

The National Natural Science Foundation of China (No.61370222, No.61300225), The Natural Science Foundation of Heilongjiang Province (No.F201324), Technology Innovation of Helongjiang Educational Committee (No.2013TD012), The Program for Group of Science Harbin Technological Innovation Found (No.2015RAXXJ004)

張偉平（1964-），女，黑龍江哈爾濱人，黑龍江大學工程師，主要研究方向為無線傳感器網(wǎng)絡。

郭亞紅（1972-），女，黑龍江雙鴨山人，黑龍江大學副教授，主要研究方向為無線傳感器網(wǎng)絡。

王蒙（1989-），女，黑龍江牡丹江人，黑龍江大學碩士生，主要研究方向為無線傳感器網(wǎng)絡。

倪林雨（1990-），男，黑龍江慶安人，黑龍江大學碩士生，主要研究方向為無線傳感器網(wǎng)絡。

李金寶（1969-），男，黑龍江慶安人，博士，黑龍江大學教授，主要研究方向為無線傳感器網(wǎng)絡、數(shù)據(jù)庫原理、移動計算和并行計算。