WSNs中數(shù)據(jù)融合樹的時隙分配算法*

臧景才,王自力,鄭 鑫

(1.青海廣播電視大學(xué)繼續(xù)教育學(xué)院,青海 西寧 810000;2.駐馬店職業(yè)技術(shù)學(xué)院信息工程系,河南 駐馬店 463000;3.黃淮學(xué)院信息工程學(xué)院,河南 駐馬店 463000)

無線傳感網(wǎng)絡(luò)WSNs(Wireless Sensor Networks)由大量的微型傳感節(jié)點組成[1-2],這些傳感節(jié)點具有感測、通信能力,進而實現(xiàn)對環(huán)境的監(jiān)測目的。目前,WSNs已廣泛應(yīng)用于軍事勘測、環(huán)境管理以及健康醫(yī)療等領(lǐng)域。在多數(shù)的應(yīng)用中,數(shù)據(jù)融合是最基本的技術(shù)。通過數(shù)據(jù)融合,將從多個傳感節(jié)點所接收數(shù)據(jù)進行匯集,再經(jīng)處理后傳輸信宿。在數(shù)據(jù)融合過程中,中間節(jié)點將所收集的數(shù)據(jù)與自己的數(shù)據(jù)進行融合成一個數(shù)據(jù)包,然后再轉(zhuǎn)發(fā)。目前,融合技術(shù)有合并、最大求和,平均等策略[3-4]。

最小化數(shù)據(jù)融合時延是融合技術(shù)最重要性能指標。所謂融合時延是指數(shù)據(jù)融合數(shù)據(jù)傳輸至信宿的時間[5-6]。最小化數(shù)據(jù)融合時延就是最小時延的融合策略問題MLAS(Minimum-Latency Aggregation Scheduling)。MLAS問題就是最快找到無碰撞的數(shù)據(jù)融合時隙[7]。實際上,節(jié)點間的干擾是影響數(shù)據(jù)融合的主要因素。當節(jié)點在同一時刻監(jiān)聽兩個或兩個以上的信號時,就發(fā)生了信號干擾。一旦產(chǎn)生了干擾,節(jié)點就無法成功再接收任何數(shù)據(jù),這就使得發(fā)射節(jié)點需要重新傳輸數(shù)據(jù)。

文獻[8-9]通過分析證實,由于重傳數(shù)據(jù)消耗了大量的能量,碰撞是WSNs的挑戰(zhàn)之一。此外,在MAC層(硬件)解決碰撞問題比在應(yīng)用層(時隙分配策略)增加了大量的傳輸時延[10-12]。例如,文獻[11]提出二次獨立集的數(shù)據(jù)融合算法,該算法引用時分復(fù)用概念,并二次構(gòu)建最大獨立集,進而降低整合時延。因此,研究人員通過合理分配融合時隙可解決MLAS問題,進而減少傳輸時延,并降低碰撞概率。

此外,最小化能耗也是WSNs的研究熱點。近期,周期工作DC(Duty Cycling)[13-14]技術(shù)得到廣泛關(guān)注。在DC中,每個節(jié)點只工作一小段時間,而其余的時間進行休眠。DC技術(shù)能夠有效節(jié)省能量,降低能耗。然而,如何控制休眠時間是DC的關(guān)鍵,并且DC技術(shù)也增加了數(shù)據(jù)傳輸時延。

為此,針對基于DC技術(shù)的WSNs,研究如何解決MLAS問題,并提出免碰撞的數(shù)據(jù)融合樹的時隙分配算法CF-DGSS(Collision-Free Data Aggregation Slots Scheduling Algorithm for Duty-Cycled Wireless Sensor Networks)。CF-DGSS算法以融合樹為基礎(chǔ),給每個節(jié)點分配融合數(shù)據(jù)時隙,并保證無碰撞,進而最小化融合時延。仿真數(shù)據(jù)表明,提出的CF-DGSS算法能夠有效降低傳輸時延。因此,本文的主要工作可歸納以下3點:①為了減少碰撞,定義碰撞集;②通過節(jié)點秩定義數(shù)據(jù)融合樹,并據(jù)此分配時隙,進而降低時延;③構(gòu)建仿真平臺,通過數(shù)據(jù)分析了算法性能。

圖1 基于DC的WSNs的工作時隙

1 網(wǎng)絡(luò)模型

建立圖論G=(V,E)的無線傳感網(wǎng)絡(luò),其中V為傳感節(jié)點集,E為邊集。同時假定傳感節(jié)點的傳輸距離為R。如果兩個節(jié)點i、j間的歐式距離‖i-j‖小于R,則它們間存在一條邊(i,j)∈E。

在DC的無線傳感網(wǎng)絡(luò),將每個節(jié)點的整個壽命劃分多個工作時期,且每個時期時長相同。每個時期又劃分為T個工作時隙。每個節(jié)點i隨機在從T個時隙中選擇一個時隙用于傳輸數(shù)據(jù)包或接收數(shù)據(jù)包。假定節(jié)點i所選擇的工作時隙表示為A(i),且這個時隙稱為節(jié)點i的活動時隙,而其他T-1個時隙為休眠時隙,如圖1所示。T=5,節(jié)點i選擇的時隙為2。

假定每個節(jié)點僅有一個數(shù)據(jù)包要傳,且每個節(jié)點在它的活動時隙只能接收數(shù)據(jù)包,但是,它能夠在任何時隙發(fā)送數(shù)據(jù)。此外,假定節(jié)點能夠融合它的子節(jié)點的數(shù)據(jù),并通過數(shù)據(jù)融合樹向它的父節(jié)點傳輸。所謂數(shù)據(jù)融合就是指將兩個或多個數(shù)據(jù)轉(zhuǎn)換成一個數(shù)據(jù)包。

此外,一個信宿節(jié)點s∈V能夠接收其他所有節(jié)點的數(shù)據(jù),直到網(wǎng)絡(luò)內(nèi)所有數(shù)據(jù)傳輸至信宿后,數(shù)據(jù)融合過程才結(jié)束。

2 干擾模型

假定節(jié)點不能同時接收數(shù)據(jù)和發(fā)送時隙。令R和R′分別表示節(jié)點的傳輸距離和干擾距離,且令R=R′。對于任意節(jié)點(假定是節(jié)點i),如果滿足下列條件,則認為節(jié)點i能夠成功將數(shù)據(jù)發(fā)送至它的父節(jié)點p(i)。

‖i-p(i)‖≤R

(1)

?x,‖x-p(i)‖≤R,andA[p(x)]=A[p(i)]

(2)

為了解決碰撞問題,保證融合時隙安排策略的無碰撞,給每個傳感節(jié)點定義碰撞集CS(Conflicting Set)。且每個傳感節(jié)點在數(shù)據(jù)融合過程需保存CS。在安排時,傳感節(jié)點應(yīng)當保證被分配的傳輸時隙與CS中其他節(jié)點的傳輸時隙不產(chǎn)生沖突。

為此,接下來,對CS進行定義。節(jié)點i的碰撞集為CS(i),其由三部分組成:

①節(jié)點i的父節(jié)點p(i)的所有子節(jié)點,且除節(jié)點i外;

②節(jié)點i的鄰居節(jié)點的所有子節(jié)點(假定為節(jié)點υ)。如果A(υ)=A[p(i)],則節(jié)點υ為節(jié)點i的CS節(jié)點;

③假定p(i)的鄰居節(jié)點表示為x。如果A[p(x)]=A[p(i)],則節(jié)點x稱為節(jié)點i的CS節(jié)點。

如圖2所示,12個節(jié)點構(gòu)成了一個數(shù)據(jù)融合樹。以節(jié)點8為例,它的CS節(jié)點分別為節(jié)點υ7、υ9、υ4。即CS(υ8)={υ7,υ9,υ4},其中υ7、υ9、υ4分別滿足①、②、③3種情況。

圖2 CS集示例

3 CF-DGSS數(shù)據(jù)融合時隙安排算法

CF-DGSS算法就是依據(jù)數(shù)據(jù)融合樹DAT(Data Aggregation Tree),給每個節(jié)點分配一個傳輸或接收數(shù)據(jù)的時隙,同時保證與其他節(jié)點不發(fā)生沖突。為此,CF-DGSS算法中的每個節(jié)點應(yīng)當存取以下局部信息。

①節(jié)點的秩

假定節(jié)點i的秩為rank(i)。rank(i)包含了兩項信息,分別為level(i)和節(jié)點的ID(i),其中l(wèi)evel(i)表示在DAT中節(jié)點i離信宿的跳數(shù)。如果level(i)>level(j),則rank(i)>rank(j);如果level(i)=level(j),ID(i)>ID(j),則rank(i)>rank(j)。節(jié)點可以通過來自信宿s的廣播消息,獲取這些信息。

②融合時隙

假定tsch(i)表示給節(jié)點i分配的工作融合時隙。換而言之,節(jié)點i在tsch(i)時隙向它的父節(jié)點p(i)傳輸數(shù)據(jù)。

③最小的工作時隙tmin(i)

節(jié)點i的最小工作時隙就是節(jié)點i的子節(jié)點中的最大工作時隙。此外,tsch(i)≥tmin(i),?i∈{Vs}。

④節(jié)點i的未安排時隙的子節(jié)點數(shù),且表示為nuch(i)。

⑤節(jié)點的CS集,即CS(i)。

最后一個就是節(jié)點i的禁止工作時隙的集,且表示為FS(i)。換而言之,FS(i)表示節(jié)點i不應(yīng)該分配的工作時隙,進而避免碰撞。

CF-DGSS算法核心思想如下:當節(jié)點的后裔節(jié)點全部被分配了時隙,而該節(jié)點自己本身沒有安排時隙,此節(jié)點稱為未安排節(jié)點UE(Unscheduled Node),而已安排的節(jié)點稱為安排節(jié)點RE(Ready Node)。CF-DGSS算法就是優(yōu)先給秩值高的節(jié)點分配時隙。為了防止碰撞,給節(jié)點分配的時隙保持相互干擾。一旦分配了時隙,節(jié)點就向鄰居節(jié)點廣播通知消息。一旦接收了該消息,鄰居節(jié)點就更新自己局部變量。

圖3描述了CF-DGSS算法分配時隙的過程。首先,網(wǎng)絡(luò)內(nèi)每個節(jié)點先初始化局部變量。假定RN節(jié)點u的秩最大,因此首先給節(jié)點u分配工作時隙。如果u是DAT的一個子節(jié)點,給它分配的工作時隙tsch(u)設(shè)置為1,如Step 4所示。否則的話,節(jié)點u的所有子節(jié)點已經(jīng)完成了時隙分配過程。在這種情況下,就依據(jù)節(jié)點u、p(u)的活動時隙和tmin(u)給節(jié)點u分配時隙。

圖3 融合時隙分配算法的偽代碼

如果A(u)

一旦完成時隙安排,節(jié)點u就向它的兩跳鄰居節(jié)點傳輸MARK消息,其包含節(jié)點的ID和它的tsch(u)。如果與節(jié)點u沖突的一個UN接收了消息,它就從CS中將節(jié)點u移除,同時將tsch(u)加入至FS集,因為節(jié)點u已經(jīng)安排了時隙,如Step 17至 Step 19行。

當接收到來自節(jié)點u的消息,如果tsch(u)大于當前tmin[p(u)],p(u)就將nuch(u)減一,并更新它的最小工作時隙tmin[p(u)],如Step 20行至Step 24行所示。最后,當所有節(jié)點分配了時隙后,它們就依據(jù)這些時隙傳輸數(shù)據(jù)。

圖4描述了CF-DGSS算法的示例。圖4(a)表示了7個節(jié)點的活動時隙。而圖4(b)為CF-DGSS算法給每個節(jié)點分配的數(shù)據(jù)融合時隙。首先,因為節(jié)點υ5位于DCT的葉節(jié)點,所以tsch(υ5)=1。將節(jié)點υ5的工作時隙與FS(υ5)內(nèi)的沖突節(jié)點的工作時隙進行核對。由于FS(υ5)={tsch(υ4)}={2},節(jié)點υ5被安排在時隙1向節(jié)點υ2傳輸數(shù)據(jù)。

此外,如果A(u)

圖4 CF-DGSS算法的時隙安排示例

4 性能分析

4.1 仿真參數(shù)

利用MATLAB軟件建立仿真平臺,并分析CF-DGSS算法的性能。假定N個傳感節(jié)點分布于L×L的正方形區(qū)域,傳感節(jié)點傳輸距離R=30 m。在每個周期內(nèi),傳感節(jié)點從[0,T-1]內(nèi)選擇一個時隙作為工作時隙。

為了更好地比較CF-DGSS算法的性能,選擇文獻[15]的融合時隙分配算法IAS和文獻[16]的SA。主要考查算法的數(shù)據(jù)融合時延。數(shù)據(jù)融合時延是指在一個周期內(nèi)信宿s接收到所有節(jié)點數(shù)據(jù)的時間,在仿真過程中,選用工作時隙數(shù)表征數(shù)據(jù)融合時延,工作時隙數(shù)越多,數(shù)據(jù)融合時延越高,反之,亦然。

考查3個實驗場景:①改變節(jié)點數(shù)N;②改變網(wǎng)絡(luò)尺寸L;③改變總時隙數(shù)T。每次實驗,獨立重復(fù)50次,取平均值作為最終的仿真數(shù)據(jù)。

4.2 數(shù)據(jù)分析

4.2.1 改變節(jié)點數(shù)

在本次實驗中,假定節(jié)點數(shù)N從300至1 200變化,且考慮L=200,T=10和L=50,T=100兩種情況。實驗數(shù)據(jù)如圖5所示。

從圖5可知,提出的CF-DGSS算法具有低的工作時隙。以圖5(a)為例,CF-DGSS算法的工作時隙比SA算法降低了55.21%。隨著網(wǎng)絡(luò)尺寸的下降,CF-DGSS算法的優(yōu)勢減弱,在圖5(b)中,CF-DGSS算法的工作時隙比SA算法降低了44.50%。CF-DGSS 算法能夠獲取低的工作時隙數(shù)的原因在于:CF-DGSS算法允許多個節(jié)點在同一個時隙傳輸,這減少了所需的時隙數(shù)。

圖5 工作時隙數(shù)

圖6 工作時隙數(shù)

4.2.2 改變網(wǎng)絡(luò)尺寸L

在次實驗中,假定網(wǎng)絡(luò)尺寸L從30至300變化,且考慮N=400,T=2和N=400,T=100兩種情況。實驗數(shù)據(jù)如圖6所示。

對比圖6(a)和圖6(b)可知,T的增加極大地提高了CF-DGSS算法的性能。此外,隨著網(wǎng)絡(luò)尺寸L的增加,3個算法的工作時隙隨之下降。但是,當L大于100后,工作時隙數(shù)不再隨L變化,而是趨于平穩(wěn)。

從圖6可知,提出的CF-DGSS算法的工作時隙數(shù)比IAS和SA,分別平均下降了約65.04%和50.95%。

4.2.3 改變總時隙數(shù)T

在本次實驗中,假定節(jié)點數(shù)T從5至100變化,且考慮N=400,L=50 m和N=400,L=200 m兩種情況。實驗數(shù)據(jù)如圖7所示。

從圖7(a)可知,當L=50 m時,CF-DGSS算法比SA算法的工作時隙數(shù)平均下降了約14.23%。此外,T值越大,CF-DGSS算法的時隙性能越好。相反,從圖7(b)可知,當L=200 m時,CF-DGSS算法的工作時隙數(shù)下降。

圖7 工作時隙數(shù)

5 總結(jié)

針對無線傳感網(wǎng)絡(luò)的數(shù)據(jù)融合問題,提出免碰撞的數(shù)據(jù)融合樹的時隙分配算法CF-DGSS。CF-DGSS算法旨在降低融合時延,并減少節(jié)點間的相互干擾。CF-DGSS算法先依據(jù)DAT樹,計算節(jié)點秩,然后給每個節(jié)點分配融合時隙,并通過沖突集CS的設(shè)定,降低節(jié)點間的干擾。實驗數(shù)據(jù)表明,與SA和IAS算法相比,提出的CF-DGSS算法能夠有效地降低融合時延。