李道清,張荊沙

(武昌工學(xué)院 信息工程學(xué)院，武漢 430065)

無(wú)線(xiàn)傳感器網(wǎng)絡(luò)中基于最小延時(shí)的數(shù)據(jù)匯集樹(shù)構(gòu)建與傳輸調(diào)度算法

李道清,張荊沙

(武昌工學(xué)院 信息工程學(xué)院，武漢 430065)

無(wú)線(xiàn)傳感器網(wǎng)絡(luò)的數(shù)據(jù)通信模式問(wèn)題是目前的研究熱點(diǎn)，針對(duì)現(xiàn)有的無(wú)線(xiàn)傳感器網(wǎng)絡(luò)數(shù)據(jù)匯集算法延時(shí)較大這一不足，對(duì)最小延時(shí)數(shù)據(jù)匯集樹(shù)和傳輸調(diào)度問(wèn)題進(jìn)行了研究;提出一種基于度約束的匯集樹(shù)構(gòu)建算法(DCAT);該算法按照 BFS 方式遍歷圖，當(dāng)遍歷到每個(gè)節(jié)點(diǎn)時(shí)，通過(guò)確定哪些節(jié)點(diǎn)與匯點(diǎn)更近來(lái)確定潛在母節(jié)點(diǎn)集合;然后，選擇圖中度數(shù)最小的潛在母節(jié)點(diǎn)作為當(dāng)前被遍歷節(jié)點(diǎn)的母節(jié)點(diǎn);此外，為了在給定的匯集樹(shù)上進(jìn)行高效地?cái)?shù)據(jù)匯集，還提出兩種新的基于貪婪的TDMA傳輸調(diào)度算法：WIRES-G 和 DCAT-Greedy;利用隨機(jī)生成的不同規(guī)模的傳感器網(wǎng)絡(luò)，參照當(dāng)前最新算法，對(duì)文中方法的性能進(jìn)行了全面評(píng)估;結(jié)果表明，與當(dāng)前最優(yōu)算法相比，文中調(diào)度算法與文中匯集樹(shù)構(gòu)建算法結(jié)合起來(lái)，可顯著降低數(shù)據(jù)匯集的延時(shí)。

無(wú)線(xiàn)傳感器網(wǎng)絡(luò)；數(shù)據(jù)匯集；最小延時(shí)；度約束；傳輸調(diào)度

0 引言

在無(wú)線(xiàn)傳感器網(wǎng)絡(luò)的多種應(yīng)用中，數(shù)據(jù)由傳感器節(jié)點(diǎn)采集后發(fā)往匯點(diǎn)(即Sink)處，這種通信模式稱(chēng)為匯集模式[1-3]。該模式通過(guò)構(gòu)建以匯點(diǎn)為根并通往匯點(diǎn)的樹(shù)，然后沿著樹(shù)向匯點(diǎn)傳輸報(bào)文，進(jìn)而完成數(shù)據(jù)匯集。在部分應(yīng)用中，匯集樹(shù)上的部分節(jié)點(diǎn)接收到子節(jié)點(diǎn)的數(shù)據(jù)后，首先對(duì)數(shù)據(jù)進(jìn)行匯集，然后再發(fā)往母節(jié)點(diǎn)，以便降低需要傳輸?shù)膱?bào)文數(shù)量。數(shù)據(jù)匯集技術(shù)可將匯集操作時(shí)傳輸?shù)膱?bào)文數(shù)量從Ω(n2)下降到O(n)個(gè)，極大地節(jié)約了網(wǎng)絡(luò)能耗[4-6]。文獻(xiàn)[7]研究了用單位圓盤(pán)圖表示的傳感器網(wǎng)絡(luò)中的最小延時(shí)匯集調(diào)度問(wèn)題(minimum latency aggregation scheduling, MLAS)，提出了一種集中式(△-1)近似算法，稱(chēng)為最短數(shù)據(jù)匯集算法(shortest data aggregation, SDA)，其中△表示圖中節(jié)點(diǎn)的最大度。然而，該算法性能的優(yōu)劣依賴(lài)于網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，可擴(kuò)展性較差。Huang等人[8]提出一種基于MIS的集中式算法來(lái)求解MLAS問(wèn)題，延時(shí)為 23R+△-18 ，其中R表示匯點(diǎn)和其他任意節(jié)點(diǎn)的最大距離。然而，該算法在求解MIS的過(guò)程中需要節(jié)點(diǎn)多次交換信息，時(shí)間復(fù)雜度較高。

此外，文獻(xiàn)[9]提出了稱(chēng)為BSPT均衡式最短路徑樹(shù))的構(gòu)建算法和稱(chēng)為WIRES(基于加權(quán)增量排序的匯集調(diào)度)的算法來(lái)實(shí)現(xiàn)數(shù)據(jù)匯集。BSPT 算法給出了數(shù)據(jù)匯集延時(shí)的范圍為max{ζi+hi:i=1,2,…,n}的下界，其中ζi和hi分別為指定樹(shù)中節(jié)點(diǎn)i從根節(jié)點(diǎn)開(kāi)始的子節(jié)點(diǎn)數(shù)量和跳數(shù)。它采取寬度優(yōu)先搜索方式遍歷圖，然后采用雙枝半匹配算法[10]來(lái)構(gòu)建可使延時(shí)最小的最短路徑樹(shù)。而WIRES調(diào)度算法則將匯集樹(shù)作為輸入，并將樹(shù)中所有葉節(jié)點(diǎn)作為可在單位時(shí)間內(nèi)被調(diào)度的合格節(jié)點(diǎn)。為每個(gè)合格節(jié)點(diǎn)計(jì)算一個(gè)權(quán)重，權(quán)重越高，表明該節(jié)點(diǎn)在當(dāng)前時(shí)隙內(nèi)被調(diào)度的優(yōu)先級(jí)越高。然后挨個(gè)考察合格節(jié)點(diǎn)，對(duì)于在傳輸時(shí)不與先前節(jié)點(diǎn)發(fā)生干擾的所有節(jié)點(diǎn)進(jìn)行調(diào)度。所有節(jié)點(diǎn)考慮完畢后，一個(gè)輪次完畢，通過(guò)刪除已被調(diào)度的節(jié)點(diǎn)，增加從各個(gè)子節(jié)點(diǎn)接收到數(shù)據(jù)的母節(jié)點(diǎn)來(lái)更新合格節(jié)點(diǎn)集合。重復(fù)上述步驟，直到所有節(jié)點(diǎn)被調(diào)度一次。然而該方法使用匯集樹(shù)中非葉相鄰節(jié)點(diǎn)的數(shù)量來(lái)進(jìn)行權(quán)重計(jì)算，因?yàn)楣?jié)點(diǎn)被調(diào)度后從匯集樹(shù)中刪除，所以每一輪次均需重新計(jì)算權(quán)重，導(dǎo)致數(shù)據(jù)匯集延時(shí)增大，且額外耗費(fèi)了能量。

針對(duì)以上方法的不足，本文提出一種新的匯集樹(shù)構(gòu)建算法，稱(chēng)為度約束匯集樹(shù)(Degree-Constrained Aggregation Tree，DCAT)。此外，我們還提出兩種新的調(diào)度算法，稱(chēng)為WIRES-G和DCAT-Greedy。通過(guò)全面的仿真實(shí)驗(yàn)評(píng)估了本文匯集樹(shù)構(gòu)建算法和調(diào)度算法的性能，并與當(dāng)前最優(yōu)算法BSPT-WIRES[9]進(jìn)行了性能比較。結(jié)果表明，DCAT算法與WIRES調(diào)度算法結(jié)合起來(lái)可將延時(shí)性能提升21%。如果將本文調(diào)度算法WIRES-G與DCAT算法結(jié)合起來(lái)，可實(shí)現(xiàn)進(jìn)一步的性能提升，將這種融合算法稱(chēng)為DCAT-WIRES-G。此外，DCAT-Greedy的性能比BSPR-WIRES高出32%-40%，具體取決于網(wǎng)絡(luò)規(guī)模大小。

1 網(wǎng)絡(luò)模型和問(wèn)題描述

本文利用單位圓盤(pán)圖來(lái)模擬無(wú)線(xiàn)傳感器網(wǎng)絡(luò)中的數(shù)據(jù)匯集過(guò)程，然后對(duì)TDMA調(diào)度問(wèn)題進(jìn)行研究。如果兩個(gè)節(jié)點(diǎn)互相位于對(duì)方的傳輸范圍內(nèi)，則認(rèn)為這兩個(gè)節(jié)點(diǎn)連通。沿著圖的生成樹(shù)進(jìn)行數(shù)據(jù)匯集。在傳輸時(shí)隙期間必須對(duì)鏈路進(jìn)行調(diào)度，以便使可能發(fā)生干擾的鏈路在不同時(shí)隙內(nèi)傳輸數(shù)據(jù)，同時(shí)使每個(gè)節(jié)點(diǎn)在其所有子節(jié)點(diǎn)傳輸完畢后再傳輸數(shù)據(jù)，保證數(shù)據(jù)匯集的有效性。本文采用基于圖的干擾模型[11]：如果v1在u2傳輸范圍內(nèi)，則認(rèn)為鏈路 (u1,v1) 和(u2,v2)對(duì)接收器v1產(chǎn)生干擾。一次匯集操作的延時(shí)，定義為匯點(diǎn)接收到所有節(jié)點(diǎn)的數(shù)據(jù)所需要的時(shí)間。

假設(shè)節(jié)點(diǎn)同步，且共享相同的無(wú)線(xiàn)信道。假設(shè)所有節(jié)點(diǎn)固定布置，傳輸范圍相同且恒定。同時(shí)假設(shè)干擾半徑等于傳輸半徑[12]。時(shí)間經(jīng)過(guò)時(shí)隙處理，每個(gè)節(jié)點(diǎn)經(jīng)過(guò)調(diào)度后在指定時(shí)隙內(nèi)傳輸數(shù)據(jù)。如果在同一時(shí)隙內(nèi)傳輸數(shù)據(jù)時(shí)不會(huì)發(fā)生干擾，則兩個(gè)節(jié)點(diǎn)可在同一時(shí)隙內(nèi)傳輸數(shù)據(jù)。我們還假設(shè)節(jié)點(diǎn)具有求取最小值、最大值、求和和計(jì)數(shù)功能，將n個(gè)數(shù)據(jù)元素作為輸入，產(chǎn)生一個(gè)元素作為輸出。

已知一組傳感器節(jié)點(diǎn)S= {s0,s1,… ,sn-1} ，其中sn-1表示匯點(diǎn)，每個(gè)節(jié)點(diǎn)均有一個(gè)數(shù)據(jù)需要傳輸給匯點(diǎn)。我們希望找到一種傳輸調(diào)度策略，使所有節(jié)點(diǎn)在各自子節(jié)點(diǎn)傳輸完畢后自己只需傳輸一次，便可將所有融合數(shù)據(jù)發(fā)往匯點(diǎn)，同時(shí)不發(fā)生干擾。用圖G=(V,E)表示一個(gè)無(wú)線(xiàn)傳感器網(wǎng)絡(luò)，s∈V表示匯點(diǎn)，我們?yōu)閳DG定義一個(gè)生成樹(shù)T作為它的有效調(diào)度，該樹(shù)以匯點(diǎn)s為根并通往匯點(diǎn)，對(duì)于數(shù)據(jù)傳輸任務(wù)A:V→Z+，我們要求：

1)vchildren(u)A(u) >A(v) ；

2) (u,v)∈T且 (ω,v)GA(u)A(ω)。

第一個(gè)條件可保證每個(gè)節(jié)點(diǎn)在其子節(jié)點(diǎn)傳輸完畢后才開(kāi)始傳輸，保證數(shù)據(jù)經(jīng)過(guò)融合；第二個(gè)條件可保證傳輸過(guò)程未被干擾。圖G有效調(diào)度A的延時(shí)可表示為L(zhǎng)(G,A)，并定義L(G,A)=maxv∈V{A(v)}。于是，MLAS問(wèn)題可表示如下：已知圖G= (V,E)，為圖G尋找一種可使延時(shí)最小化的有效調(diào)度。很顯然，這一問(wèn)題可分為兩個(gè)階段：匯集樹(shù)構(gòu)建過(guò)程，和基于樹(shù)的調(diào)度策略搜索過(guò)程。下面對(duì)這兩個(gè)問(wèn)題進(jìn)行研究。

2 基于度約束的匯集樹(shù)(DCAT)

本節(jié)給出了基于度約束的匯集樹(shù)構(gòu)建算法。當(dāng)對(duì)節(jié)點(diǎn)的潛在母節(jié)點(diǎn)進(jìn)行選擇時(shí)，本文算法的主要思想就是選擇圖中度數(shù)最小的節(jié)點(diǎn)。原因是潛在母節(jié)點(diǎn)的度非常關(guān)鍵，只有對(duì)節(jié)點(diǎn)進(jìn)行調(diào)度，才能避免受到其母節(jié)點(diǎn)在圖中其他子節(jié)點(diǎn)的干擾，同時(shí)避免受到母節(jié)點(diǎn)在圖中其他相鄰節(jié)點(diǎn)的干擾。本文算法與 BSPT 算法不同，BSPT 算法通過(guò)將節(jié)點(diǎn)均勻分布于它們的潛在母節(jié)點(diǎn)之間來(lái)盡量提高并行化水平。也就是說(shuō)，該算法盡量降低樹(shù)中節(jié)點(diǎn)的度，并忽略潛在母節(jié)點(diǎn)在圖中的相鄰節(jié)點(diǎn)。 DCAT 的步驟為：首先，按照BFS 方式遍歷圖，當(dāng)遍歷到每個(gè)節(jié)點(diǎn)時(shí)，通過(guò)確定哪些節(jié)點(diǎn)與匯點(diǎn)更近(少一跳距離)來(lái)確定潛在母節(jié)點(diǎn)集合。然后，選擇圖中度數(shù)最小的潛在母節(jié)點(diǎn)作為當(dāng)前被遍歷節(jié)點(diǎn)的母節(jié)點(diǎn)。限于篇幅，該算法的具體內(nèi)容略。

3 調(diào)度算法

本節(jié)給出了兩種用于數(shù)據(jù)匯集的調(diào)度算法。第一種算法稱(chēng)為 WIRES-G，是對(duì)文獻(xiàn)[9]中 WIRES 算法的一種改進(jìn)：我們?cè)?WIRES 算法中增加一個(gè)步驟，以便每個(gè)時(shí)隙期間調(diào)度更多個(gè)節(jié)點(diǎn)。每一輪次中，新添步驟需要為原來(lái)算法無(wú)法調(diào)度的合格節(jié)點(diǎn)匹配新的母節(jié)點(diǎn)。WIRES-G 的具體內(nèi)容請(qǐng)見(jiàn)算法1(G表示貪婪)。工作流程如下。第 5-9 行表示原來(lái) WIRES 算法每一輪次的步驟。第 9 行結(jié)束時(shí)，S包含經(jīng)過(guò)調(diào)度將在時(shí)間j發(fā)送數(shù)據(jù)的節(jié)點(diǎn)，R包含從S中節(jié)點(diǎn)接收數(shù)據(jù)的節(jié)點(diǎn)集合。此時(shí)，如果我們繼續(xù)保持原來(lái)的樹(shù)，則其他所有節(jié)點(diǎn)經(jīng)過(guò)調(diào)度后傳輸數(shù)據(jù)總會(huì)與已被調(diào)度的節(jié)點(diǎn)發(fā)生干擾。

算法1：WIRES-G

輸入：G=(V,E)，s：匯點(diǎn)，v.p：樹(shù)中v∈V的母節(jié)點(diǎn)

輸出：G的一個(gè)有效調(diào)度，其中v.t表示v∈V的傳輸時(shí)間

1：procedure WIRES-G(G;s)

2：?v∈G.Vvht= 0 //對(duì)時(shí)隙初始化

3：j=1

4：whiles.t= 0 do

5：L= GETELIGIBLENODES(G)

6： COMPUTEWEIGHTS(L)

7： SORTDECREASING(L)

8：S=R=//發(fā)送節(jié)點(diǎn)和接收節(jié)點(diǎn)集合開(kāi)始為空

9：SCHEDULENODES(L;S;R)

10：L=LS//將發(fā)送節(jié)點(diǎn)從合格節(jié)點(diǎn)中刪除

11： GREEDY-SCHEDULING(L;S;R)

12：j=j+1

13：end while

14：end procedure

15：procedure SCHEDULENODES(L;S;R)

16：for eachu∈Ldo

17：ifu?N(R)且u.p?N(S) then //如果u在傳

輸時(shí)不發(fā)生沖突

18：u.t=j//通過(guò)調(diào)度使u在時(shí)間j傳輸

19：S=S∪{u}

20：R=R∪{u.p}

21：end if

22：end for

23：end procedure

24：procedure GREEDY-SCHEDULING(L;S;R)

25： for eachu∈Ldo

26： ifu?R且u?N(R) then

27：r= nil //未發(fā)現(xiàn)母節(jié)點(diǎn)

28： for eachp∈N(u) do //尋找母節(jié)點(diǎn)

30：r=p

31： end if

32： end for

33： ifr≠ nil then //如果找到新的母節(jié)點(diǎn)

34：p=u.p

35：u.p=r//分配新的母節(jié)點(diǎn)

36： if ISELIGIBLE(p) then

37：L=L∪{p}

38： end if

39：u.t=j

40：S=S∪{u}

41：R=R∪{u.p}

42： end if

43： end if

44： end for

45：end procedure

在算法1 的 GREEDY-SCHEDULING 中，我們對(duì)之前未被順利調(diào)度的所有合格節(jié)點(diǎn)進(jìn)行迭代。首先，我們考查當(dāng)前節(jié)點(diǎn)p是否已經(jīng)不再作為接收節(jié)點(diǎn)，同時(shí)考察該節(jié)點(diǎn)在傳輸數(shù)據(jù)時(shí)是否會(huì)對(duì)R中的接收節(jié)點(diǎn)造成干擾。如果如此，則為p選擇一個(gè)未被調(diào)度且可在時(shí)間j傳輸數(shù)據(jù)并不發(fā)生干擾的相鄰節(jié)點(diǎn)，同時(shí)該相鄰節(jié)點(diǎn)的度在圖中所有類(lèi)似相鄰節(jié)點(diǎn)間最小。找到相鄰節(jié)點(diǎn)后，便將其作為當(dāng)前節(jié)點(diǎn)在匯集樹(shù)中新的母節(jié)點(diǎn)。如果先前母節(jié)點(diǎn)未遺留下未被調(diào)度的子節(jié)點(diǎn)，并且在當(dāng)前輪次內(nèi)不作為接收節(jié)點(diǎn)，則將其添加到合格節(jié)點(diǎn)列表中，原因是它可在時(shí)間j被調(diào)度(第 36-38 行)。

算法 2：DCAT-Greedy

輸入：G= (V,E)，s：匯點(diǎn)

輸出：G以s為根的生成樹(shù)，及G的一個(gè)有效調(diào)度，其中v.t和v.p分別表示v∈V的傳輸時(shí)間和母節(jié)點(diǎn)

1：procedure DCAT-GREEDY(G)

2：DCAT(G;s)

3： ?v∈G.V v.t = 0 //時(shí)隙初始化

4：j=1

5： whiles.t= 0 do

6：L= GETELIGIBLENODES(G)

7： COMPUTEWEIGHTS(L)

8： SORTDECREASING(L)

9：S=R=

10： GREEDY-SCHEDULING(L;S;R)

11：j=j+1

12： end while

13：end procedure

本文提出的第二種調(diào)度算法稱(chēng)為DCAT-Greedy，具體內(nèi)容見(jiàn)算法 2。該算法融合了本文的匯集樹(shù)構(gòu)建算法DCAT及GREEDY-SCHEDULING 算法，目的是進(jìn)一步降低延時(shí)。DCAT-Greedy 算法首先采用 DCAT 構(gòu)建一個(gè)匯集樹(shù)。每次迭代時(shí)，我們確定哪些節(jié)點(diǎn)有資格在此輪接受調(diào)度。只有所有子節(jié)點(diǎn)均被分配了一個(gè)時(shí)隙的節(jié)點(diǎn)才是有資格被調(diào)度的節(jié)點(diǎn)(合格節(jié)點(diǎn))。DCAT-Greedy 采用與WIRES 相同的方法計(jì)算權(quán)重(非葉相鄰節(jié)點(diǎn)的數(shù)量)，并根據(jù)權(quán)重對(duì)節(jié)點(diǎn)降序排列。然后，GREEDY-SCHEDULING 對(duì)所有合格節(jié)點(diǎn)進(jìn)行迭代，在不發(fā)生干擾的前提下使盡可能多的節(jié)點(diǎn)被調(diào)度。

DCAT-Greedy算法與 WIRES-G 有兩點(diǎn)不同：(1)它利用DCAT 來(lái)構(gòu)建樹(shù)；(2)沒(méi)有調(diào)用 SCHEDULENODES。

4 仿真結(jié)果與分析

本文結(jié)合小型、中型和大型無(wú)線(xiàn)傳感器網(wǎng)絡(luò)對(duì)匯集樹(shù)構(gòu)建算法DCAT及傳輸調(diào)度算法進(jìn)行性能評(píng)估，通過(guò)將節(jié)點(diǎn)隨機(jī)均勻分布于5*5、10*10 和20*20 的地理區(qū)域上生成小型、中型和大型網(wǎng)絡(luò)。節(jié)點(diǎn)的傳輸范圍為1，節(jié)點(diǎn)的密度范圍為8-200，其中密度定義為圖中節(jié)點(diǎn)的平均度。如果節(jié)點(diǎn)間的歐氏距離小于等于傳輸范圍，則認(rèn)為節(jié)點(diǎn)連通。對(duì)每個(gè)被選密度值，共生成 100 個(gè)連通圖，對(duì)這 100 個(gè)圖求取平均作為最終結(jié)果。

首先，我們單獨(dú)評(píng)估匯集樹(shù)構(gòu)建算法。為此我們比較了DCAT-WIRES和BSPT-WIRES的性能，同時(shí)衡量了所生成調(diào)度方案的延時(shí)。如圖1所示，網(wǎng)絡(luò)尺寸20*20，采用WIRES 調(diào)度。DCAT 樹(shù)無(wú)論在哪種密度設(shè)置下，延時(shí)均較低。鑒于篇幅有限，我們?cè)谶@里只給出大型網(wǎng)絡(luò)的運(yùn)行結(jié)果，對(duì)小型和中型網(wǎng)絡(luò)具有相同結(jié)論。

圖1 DCAT 和 BSPT 樹(shù)的平均匯集延時(shí)性能比較

下面我們?cè)u(píng)估WIRES-G和DCAT-Greedy兩種調(diào)度算法的性能。圖2給出了WIRES-G、DCAT-Greedy和WIRES在小型傳感器網(wǎng)絡(luò)上的性能比較。很顯然，DCAT-Greedy對(duì)小型網(wǎng)絡(luò)的性能最優(yōu)?？梢钥闯?，DCAT-Greedy所生成的調(diào)度方案的平均延時(shí)，要遠(yuǎn)低于其他算法，當(dāng)密度設(shè)置較高時(shí)更是如此。DCAT-Greedy甚至遠(yuǎn)低于BSPT生成的匯集樹(shù)的下界。當(dāng)密度為 200 時(shí)，DCAT-Greedy 的性能比排名第二的算法DCAT-WIRES-G高出25% ，比先前最優(yōu)算法BSPTWIRES 高出近 40%。此外，用百分比表示的性能增益隨著密度穩(wěn)定上升。鑒于篇幅所限，對(duì)中型網(wǎng)絡(luò)的運(yùn)行結(jié)果類(lèi)似，此處略。我們可以看出，無(wú)論在哪種情況下，WIRES-G均可降低調(diào)度方案的延時(shí)，且與采用的樹(shù)構(gòu)建算法無(wú)關(guān)；WIRES 無(wú)法實(shí)現(xiàn)這一性能。BSPTWIRES-G 和 DCAT-WIRES的性能比較接近，前者略?xún)?yōu)于后者。因此，無(wú)論是采用本文新提出的調(diào)度算法IRES-G，還是新提出的樹(shù)構(gòu)建算法DCAT-Greedy，均可實(shí)現(xiàn)性能提升。DCAT-WIRES-G 的性能優(yōu)于其他算法，但低于DCAT-Greedy，且密度越大，性能增益越大。

圖2 網(wǎng)絡(luò)規(guī)模為 5*5 時(shí)平均匯集延時(shí)

圖3 網(wǎng)絡(luò)規(guī)模為 20*20 時(shí)平均匯集延時(shí)

圖3給出了調(diào)度算法對(duì)大型傳感器網(wǎng)絡(luò)的性能。結(jié)果特點(diǎn)與上文類(lèi)似。然而，幾乎在所有密度設(shè)置下，DCAT-WIRES 的性能均優(yōu)于BSPT-WIRES-G。實(shí)際上，對(duì)中等密度水平，DCATWIRES-G的性能比BSPT-WIRES-G高出15%。DCAT-reedy 和DCAT-WIRES-G的性能相近，但當(dāng)密度在15到75之間(含)時(shí)，DCAT-WIRES-G 略?xún)?yōu)于DCAT-Greedy。與BSPT-IRES相比，DCAT-WIRES-G的性能提升了34.66%，而DCAT-Greedy相對(duì)于BSPT-WIRES 提升了32.25%。請(qǐng)注意，DCAT-Greedy 結(jié)果的標(biāo)準(zhǔn)差低于DCAT-WIRES-G(4.48 vs 5.35)。

為了更好理解性能特點(diǎn)，我們考察了圖中節(jié)點(diǎn)度與匯集樹(shù)中子節(jié)點(diǎn)平均數(shù)量之間的關(guān)系。圖4給出了密度為30時(shí)中等隨機(jī)網(wǎng)絡(luò)下的關(guān)系?？梢钥闯觯鞣N基于DCAT的算法為度數(shù)較高的節(jié)點(diǎn)分配的子節(jié)點(diǎn)數(shù)量很少，這與我們預(yù)期相一致。DCAT-Greedy 算法為低度節(jié)點(diǎn)分配的子節(jié)點(diǎn)數(shù)量最多，為高度節(jié)點(diǎn)分配的子節(jié)點(diǎn)數(shù)量最少。這也是該算法在實(shí)驗(yàn)中表現(xiàn)優(yōu)異的原因。對(duì)高密度設(shè)置具有類(lèi)似特點(diǎn)。

圖4 圖的度數(shù)與匯集樹(shù)子節(jié)點(diǎn)平均數(shù)量間的關(guān)系

另外，我們還考察了匯集樹(shù)中子節(jié)點(diǎn)數(shù)量最多的節(jié)點(diǎn)所處位置。 圖 5 給出了中等規(guī)模網(wǎng)絡(luò)在密度為30 時(shí)的運(yùn)行結(jié)果 。可以看出，匯點(diǎn)(距 離為0 的節(jié)點(diǎn) )在除了DCAT-Greedy 的各種算法下，子節(jié)點(diǎn)數(shù)量均較高。這是因?yàn)槲覀冮_(kāi)始時(shí)采用最短路徑樹(shù)。因此，所有與匯點(diǎn)相距一跳距離的節(jié)點(diǎn)將是匯點(diǎn)的子節(jié)點(diǎn)。DCAT-Greedy不存在這個(gè)問(wèn)題，因?yàn)樗鼮榱送瑫r(shí)調(diào)度盡可能多的節(jié)點(diǎn)而修改了初始樹(shù)。此外，我們發(fā)現(xiàn)，如果使度較高的節(jié)點(diǎn)與樹(shù)頂較近，往往會(huì)導(dǎo)致延時(shí)上升。這是因?yàn)榕c匯點(diǎn)的距離近了，可供選擇的節(jié)點(diǎn)少了，并行化的概率便會(huì)降低。使度較高的節(jié)點(diǎn)位于樹(shù)的底層，也不利于性能提升， 因?yàn)橹挥挟?dāng)所有節(jié)點(diǎn)傳輸完畢才能使數(shù)據(jù)向上傳輸，這解釋了為何對(duì)密度中等的大型網(wǎng)絡(luò)，DCATWIRES-G 的性能要優(yōu)于DCAT-Greedy。為此，一種可能的思路是設(shè)計(jì)一種將上述兩種算法綜合起來(lái)的混合算法來(lái)提升面對(duì)大型傳感器網(wǎng)絡(luò)時(shí)的性能。例如，對(duì)樹(shù)的底層采用 DCAT-WIRES-G 算法，對(duì)樹(shù)的高層采用 DCAT-Greedy 算法。

圖5 匯集樹(shù)中度數(shù)較高節(jié)點(diǎn)的位置( 密度為 30)

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

本文研究了WSN 中進(jìn)行TDMA 調(diào)度時(shí)的數(shù)據(jù)匯集問(wèn)題，提出一種新的匯集樹(shù)構(gòu)建算法及兩種新的調(diào)度算法。與當(dāng)前最優(yōu)算法相比，如果將本文提出的匯集樹(shù)構(gòu)建算法與調(diào)試算法結(jié)合起來(lái)，可顯著降低延時(shí)。在下一步工作中，我們研究的重點(diǎn)主要包含兩個(gè)方面：1)在多種應(yīng)用場(chǎng)景下分析數(shù)據(jù)匯集可靠性與匯集樹(shù)構(gòu)建以及調(diào)度算法之間的關(guān)系，以進(jìn)一步提高數(shù)據(jù)匯集的質(zhì)量； 2)基于壓縮感知理論，分析數(shù)據(jù)匯集樹(shù)的構(gòu)建過(guò)程對(duì)于延長(zhǎng)網(wǎng)絡(luò)生命周期的影響，進(jìn)而提出一種可提高網(wǎng)絡(luò)生命周期的基于壓縮感知的數(shù)據(jù)匯集算法。

[1] Bagaa M, Younis M, Djenouri D, et al. Distributed low-latency data aggregation scheduling in wireless sensor networks [J]. ACM Transactions on Sensor Networks (TOSN), 2015, 11(3): 49-60.

[2] 石為人, 唐云建, 王燕霞. 基于擁塞控制的無(wú)線(xiàn)傳感器網(wǎng)絡(luò)數(shù)據(jù)匯集樹(shù)生成算法[J]. 自動(dòng)化學(xué)報(bào), 2010, 36(6): 823-828.

[3] Yousefi H, Malekimajd M, Ashouri M, et al. Fast aggregation scheduling in wireless sensor networks[J]. IEEE Transactions on Wireless Communications, 2015,14(6): 3402-3414.

[4] Liu X Y, Zhu Y, Kong L, et al. CDC: Compressive data collection for wireless sensor networks[J]. IEEE Transactions on Parallel and Distributed Systems, 2015, 26(8): 2188-2197.

[5] 楊 庚, 李 森, 陳正宇, 等. 傳感器網(wǎng)絡(luò)中面向隱私保護(hù)的高精確度數(shù)據(jù)融合算法 [J]. 計(jì)算機(jī)學(xué)報(bào), 2013, 36(1): 189-200.

[6] 邱立達(dá), 劉天鍵, 傅 平. 基于稀疏濾波的無(wú)線(xiàn)傳感器網(wǎng)絡(luò)數(shù)據(jù)融合[J]. 電子測(cè)量與儀器學(xué)報(bào) , 2015, 29(3): 352-357.

[7] Guo L, Li Y, Cai Z. Minimum-latency aggregation scheduling in wireless sensor network[J]. Journal of Combinatorial Optimization, 2016, 31(1): 279-310.

[8] Huang S C H, Wan P J, Vu C T, et al. Nearly constant approximation for data aggregation scheduling in wireless sensor networks[A].26th IEEE International Conference on Computer Communications(INFOCOM)[C]. Anchorage, Alaska, USA: IEEE Press, 2007: 366-372.

[9] Malhotra B, Nikolaidis I, Nascimento M A. Aggregation convergecast scheduling in wireless sensor networks[J]. Wireless Networks, 2011, 17(2): 319-335.

[10] Harvey N J A, Ladner R E, Lovász L, et al. Semi-matchings for bipartite graphs and load balancing[J]. Journal of Algorithms, 2006, 59(1): 53-78.

[11] Incel ? 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.

[12] Yao Y, Cao Q, Vasilakos A V. EDAL: An energy-efficient, delay-aware, and lifetime-balancing data collection protocol for heterogeneous wireless sensor networks[J]. IEEE/ACM Transactions on Networking, 2015, 23(3):810-823.

Data Aggregation Tree Construction and Transmission Scheduling Algorithm Based on Minimum Latency in Wireless Sensor Networks

Li Daoqing,Zhang Jingsha

(School of Information Engineering, Wuchang Institute of Technology, Wuhan 430065, China)

Data communication problem in wireless sensor networks is the research hotspot at now,aiming at the shortcomings of the larger delay at the existing data aggregation algorithms in wireless sensor networks, the problem of the minimum latency data aggregation tree and transmission scheduling is studied, and an aggregation tree construction algorithm based on degree constraint is proposed(DCAT). It works by traversing the graph in a BFS manner. As it traverses each node, the set of potential parents is determined by identifying the nodes that are one-hop closer to the sink. The potential parent with the lowest degree in the graph is selected as the parent for the currently traversed node. Furthermore, two new approaches based on greedy for building a TDMA transmission schedule WIRES-G and DCAT-Greedy is proposed to perform efficient aggregation on a given tree. the evaluation to the performance of our algorithms is given through extensive simulations on randomly generated sensor networks of different sizes and the comparison to the previous state of the art is given. the results show that both our new scheduling algorithms when combined with our new tree-building algorithm obtain significantly lower latencies than that of the previous best algorithm.

wireless sensor networks; data aggregation; minimum latency; degree constraint; transmission scheduling

2016-07-01；

2016-07-17。

李道清(1963-)，男，湖北京山人,碩士，副教授，主要從事傳感器網(wǎng)絡(luò)、數(shù)據(jù)采集與處理方向的研究。

1671-4598(2016)12-0147-04

10.16526/j.cnki.11-4762/tp.2016.12.042

TP393

A