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

?

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

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

(1. 黑龍江大學(xué)計(jì)算機(jī)科學(xué)技術(shù)學(xué)院，黑龍江哈爾濱 150080； 2. 黑龍江大學(xué)信息科學(xué)與技術(shù)學(xué)院，黑龍江哈爾濱 150080； 3. 黑龍江省數(shù)據(jù)庫(kù)與并行計(jì)算重點(diǎn)實(shí)驗(yàn)室，黑龍江哈爾濱 150080)

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

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

1 引言

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

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

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

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

2 相關(guān)工作

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

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

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

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

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

3 建立路由結(jié)構(gòu)

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

因此，對(duì)于一個(gè)待發(fā)送數(shù)據(jù)的節(jié)點(diǎn)，當(dāng)一棵路由樹(shù)上的父親節(jié)點(diǎn)出現(xiàn)故障時(shí)，可以經(jīng)由其他路由樹(shù)上的父親節(jié)點(diǎn)將數(shù)據(jù)發(fā)送到sink。例如，給定拓?fù)浣Y(jié)構(gòu)如圖1(a)所示，圖中的虛線表示節(jié)點(diǎn)之間可以進(jìn)行通信。圖1(b)和圖1(c)是對(duì)圖1(a)給出的網(wǎng)絡(luò)拓?fù)涫褂盟惴?建立的2棵不相交的路由樹(shù)。從圖1中可以看到，當(dāng)節(jié)點(diǎn)1因?yàn)槌霈F(xiàn)故障而無(wú)法通信時(shí)，節(jié)點(diǎn)6和7可以通過(guò)第2棵路由樹(shù)上的節(jié)點(diǎn)2進(jìn)行數(shù)據(jù)傳輸，避免了節(jié)點(diǎn)6、7、11和12的數(shù)據(jù)的丟失。

3.1 準(zhǔn)備工作

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

3.2 構(gòu)造森林

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

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

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

算法1 構(gòu)造森林

6) end for;

8) end for

end for

++;

end while

3.3 分配信道

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

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

4.1 劃分鏈路集合

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

(3)

算法2 劃分鏈路集合

1)1;

3)1;

9) end for

14) end for

15);

16) end while

17);

18)end while

4.2 理論分析

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

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

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

5 模擬實(shí)驗(yàn)與結(jié)果分析

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

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

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

5.1 數(shù)據(jù)收集量實(shí)驗(yàn)

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

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

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

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

5.2 數(shù)據(jù)收集延遲實(shí)驗(yàn)

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

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

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

6 結(jié)束語(yǔ)

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

[1] 李鳳保, 李凌. 無(wú)線傳感器網(wǎng)絡(luò)技術(shù)綜述[J]. 儀器儀表學(xué)報(bào), 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)絡(luò)基于小波分段常值壓縮的數(shù)據(jù)收集研究[J]. 儀器儀表學(xué)報(bào), 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ú)線傳感器網(wǎng)絡(luò)數(shù)據(jù)收集協(xié)議[J]. 電子測(cè)量與儀器學(xué)報(bào), 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

國(guó)家自然科學(xué)基金資助項(xiàng)目（No.61370222, No.61300225）；黑龍江省自然科學(xué)基金資助項(xiàng)目（No.F201324）；黑龍江省高?？萍紕?chuàng)新團(tuán)隊(duì)建設(shè)計(jì)劃基金資助項(xiàng)目（No.2013TD012）；哈爾濱市優(yōu)秀學(xué)科帶頭人基金資助項(xiàng)目（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-），女，黑龍江哈爾濱人，黑龍江大學(xué)工程師，主要研究方向?yàn)闊o(wú)線傳感器網(wǎng)絡(luò)。

郭亞紅（1972-），女，黑龍江雙鴨山人，黑龍江大學(xué)副教授，主要研究方向?yàn)闊o(wú)線傳感器網(wǎng)絡(luò)。

王蒙（1989-），女，黑龍江牡丹江人，黑龍江大學(xué)碩士生，主要研究方向?yàn)闊o(wú)線傳感器網(wǎng)絡(luò)。

倪林雨（1990-），男，黑龍江慶安人，黑龍江大學(xué)碩士生，主要研究方向?yàn)闊o(wú)線傳感器網(wǎng)絡(luò)。

李金寶（1969-），男，黑龍江慶安人，博士，黑龍江大學(xué)教授，主要研究方向?yàn)闊o(wú)線傳感器網(wǎng)絡(luò)、數(shù)據(jù)庫(kù)原理、移動(dòng)計(jì)算和并行計(jì)算。