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

李道清,張荊沙

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

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

李道清,張荊沙

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

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

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

0 引言

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

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

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

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

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

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

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

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

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

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

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

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

3 調(diào)度算法

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

算法1：WIRES-G

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

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

1：procedure WIRES-G(G;s)

2：?v∈G.Vvht= 0 //對時隙初始化

3：j=1

4：whiles.t= 0 do

5：L= GETELIGIBLENODES(G)

6： COMPUTEWEIGHTS(L)

7： SORTDECREASING(L)

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

9：SCHEDULENODES(L;S;R)

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

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在傳

輸時不發(fā)生沖突

18：u.t=j//通過調(diào)度使u在時間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é)點

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

30：r=p

31： end if

32： end for

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

34：p=u.p

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

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

算法 2：DCAT-Greedy

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

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

1：procedure DCAT-GREEDY(G)

2：DCAT(G;s)

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

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

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

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

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

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

圖1 DCAT 和 BSPT 樹的平均匯集延時性能比較

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

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

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

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

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

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

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

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

5 結(jié)束語

本文研究了WSN 中進(jìn)行TDMA 調(diào)度時的數(shù)據(jù)匯集問題，提出一種新的匯集樹構(gòu)建算法及兩種新的調(diào)度算法。與當(dāng)前最優(yōu)算法相比，如果將本文提出的匯集樹構(gòu)建算法與調(diào)試算法結(jié)合起來，可顯著降低延時。在下一步工作中，我們研究的重點主要包含兩個方面：1)在多種應(yīng)用場景下分析數(shù)據(jù)匯集可靠性與匯集樹構(gòu)建以及調(diào)度算法之間的關(guān)系，以進(jìn)一步提高數(shù)據(jù)匯集的質(zhì)量； 2)基于壓縮感知理論，分析數(shù)據(jù)匯集樹的構(gòu)建過程對于延長網(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ǎng)絡(luò)數(shù)據(jù)匯集樹生成算法[J]. 自動化學(xué)報, 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ī)學(xué)報, 2013, 36(1): 189-200.

[6] 邱立達(dá), 劉天鍵, 傅 平. 基于稀疏濾波的無線傳感器網(wǎng)絡(luò)數(shù)據(jù)融合[J]. 電子測量與儀器學(xué)報 , 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