MR-MC無線傳感器網絡基于森林的數據收集研究

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

?

MR-MC無線傳感器網絡基于森林的數據收集研究

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

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

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

無線傳感器網絡；路由樹；數據收集；延遲

1 引言

近年來，無線傳感器網絡因其巨大的潛力被廣泛應用于軍事領域、環境監測、醫療和工農業等領域中[1]。在這些應用中, 大量的傳感器節點監測周圍的環境，并將感知的數據通過多跳路由傳輸到匯聚節點。作為無線傳感器網絡的主要功能之一，數據收集問題受到眾多研究者的廣泛關注。

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

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

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

2 相關工作

對于不同的應用環境，無線傳感器網絡中數據收集協議的設計目標也不盡相同，下面分別從容量和延遲等方面介紹數據收集協議的研究現狀。

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

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

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

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

3 建立路由結構

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

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

3.1 準備工作

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

3.2 構造森林

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

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

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

算法1 構造森林

6) end for;

8) end for

end for

++;

end while

3.3 分配信道

4 數據收集策略和分析

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

4.1 劃分鏈路集合

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

(3)

算法2 劃分鏈路集合

1)1;

3)1;

9) end for

14) end for

15);

16) end while

17);

18)end while

4.2 理論分析

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

定理1 給定一個個節點組成的傳感器網絡，高度為，可以建立棵不相交的樹，設在一次數據收集中節點出現故障的平均概率是，那么sink平均可以收集到個數據。

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

5 模擬實驗與結果分析

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

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

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

5.1 數據收集量實驗

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

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

圖4是節點出現故障的概率對收集的快照次數的影響實驗。

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

5.2 數據收集延遲實驗

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

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

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

6 結束語

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

[1] 李鳳保, 李凌. 無線傳感器網絡技術綜述[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] 李楊, 郭龍江, 李金寶, 等.傳感器網絡基于小波分段常值壓縮的數據收集研究[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] 史久根, 胡小博.高效節能的無線傳感器網絡數據收集協議[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）；黑龍江省高校科技創新團隊建設計劃基金資助項目（No.2013TD012）；哈爾濱市優秀學科帶頭人基金資助項目（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-），女，黑龍江哈爾濱人，黑龍江大學工程師，主要研究方向為無線傳感器網絡。

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

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

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

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