臧景才,王自力,鄭 鑫
(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的工作時隙
建立圖論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é)束。
假定節(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集示例
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ù)。