WSN中最小延時的數(shù)據(jù)匯集樹構(gòu)建與傳輸調(diào)度算法

李浩光， 胡玉鵬

(1. 廣東工程職業(yè)技術(shù)學(xué)院 信息工程學(xué)院， 廣州 510520; 2. 湖南大學(xué) 軟件學(xué)院， 長沙 410082)

WSN中最小延時的數(shù)據(jù)匯集樹構(gòu)建與傳輸調(diào)度算法

李浩光1， 胡玉鵬2

(1. 廣東工程職業(yè)技術(shù)學(xué)院 信息工程學(xué)院， 廣州 510520; 2. 湖南大學(xué) 軟件學(xué)院， 長沙 410082)

針對現(xiàn)有無線傳感器網(wǎng)絡(luò)數(shù)據(jù)匯集算法延時較大這一不足，對最小延時數(shù)據(jù)匯集樹和傳輸調(diào)度問題進(jìn)行了研究。提出一種基于度約束的匯集樹構(gòu)建算法(DCAT)。該算法按照BFS方式遍歷圖，當(dāng)遍歷到每個節(jié)點(diǎn)時，通過確定哪些節(jié)點(diǎn)與匯點(diǎn)更近來確定潛在母節(jié)點(diǎn)集合。然后，選擇圖中度數(shù)最小的潛在母節(jié)點(diǎn)作為當(dāng)前被遍歷節(jié)點(diǎn)的母節(jié)點(diǎn)。此外，為了在給定的匯集樹上進(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 引 言

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

針對以上方法的不足，提出一種新的匯集樹構(gòu)建算法，稱為度約束匯集樹(Degree-Constrained Aggregation Tree，DCAT)。此外，本文還提出兩種新的調(diào)度算法，稱為WIRES-G和DCAT-Greedy。通過全面的仿真實(shí)驗(yàn)評估了匯集樹構(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é)合起來，可實(shí)現(xiàn)進(jìn)一步的性能提升，將這種融合算法稱為DCAT-WIRES-G。此外，DCAT-Greedy的性能比BSPR-WIRES高出32%～40%，具體取決于網(wǎng)絡(luò)規(guī)模大小。

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

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

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

在圖1中，實(shí)線表示匯集樹的邊，虛線表示圖中未作為樹邊的邊。圖1(a)是BSPT算法構(gòu)建的匯集樹，可以看出，該樹的最優(yōu)調(diào)度需要4個時隙。圖1(b)是DCAT算法針對同一圖形構(gòu)建的匯集樹，此時，最優(yōu)調(diào)度只需要3個時隙。圖1表明為何DCAT中采用的方法可獲得優(yōu)于BSPT的性能。該圖中，子節(jié)點(diǎn)被均勻分布于潛在母節(jié)點(diǎn)之間，且與它們在圖中的度無關(guān)，于是調(diào)度算法受到的約束更多。由圖可以清晰看出，考慮圖中節(jié)點(diǎn)的度數(shù)，其性能要優(yōu)于使匯集樹的度最小化。這表明，DCAT更適合構(gòu)建高效的匯集樹，至少當(dāng)不同節(jié)點(diǎn)具有不同度數(shù)時如此。

圖1 DCAT算法和BSPT算法構(gòu)建的匯集樹比較

算法1 DCAT輸入：G=V，E()，s：匯點(diǎn)輸出：圖G以s為根的生成樹，其中v．p表示v∈V的母節(jié)點(diǎn)1．procedureDCATG，s()2．foreachu∈G．Vdo3．u．d=-14．u．p=nil5．endfor6．s．d=07．Q=?8．Enqueue(Q，s)9．whileQ≠?do

10．u=Dequeue(Q)11．foreachv∈Nu()do12．ifv．d<0then13．v．d=u．d+114．Enqueue(Q，v)15．endif16．ifv．d>u．dthen17．ifv．p==nilorNv．p()>Nu()then18．v．p=u19．endif20．endif21．endfor22．endwhile23．endprocedure

3 調(diào)度算法

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

算法2 WIRES?G輸入：G=V，E()，s：匯點(diǎn)，v．p：樹中v∈V的母節(jié)點(diǎn)輸出：G的一個有效調(diào)度，其中v．t表示v∈V的傳輸時間1．procedureWIRES?G(G；s)2．?v∈G．Vv．t=0//對時隙初始化3．j=14．whiles．t=0do5．L=GETELIGIBLENODES(G)6．COMPUTEWEIGHTS(L)7．SORTDECREASING(L)8．S=R=?//發(fā)送節(jié)點(diǎn)和接收節(jié)點(diǎn)集合開始時為空9．SCHEDULENODES(L；S；R)10．L=LS//將發(fā)送節(jié)點(diǎn)從合格節(jié)點(diǎn)中刪除11．GREEDY?SCHEDULING(L；S；R)12．j=j+113．endwhile14．endprocedure15．procedureSCHEDULENODES(L；S；R)16．foreachu∈Ldo17．ifu?NR()且u．p?NS()then//如果u在傳輸時不發(fā)生沖突18．u．t=j//通過調(diào)度使u在時間j傳輸

19．S=S∪u{}20．R=R∪u．p{}21．endif22．endfor23．endprocedure24．procedureGREEDY?SCHEDULING(L；S；R)25．foreachu∈Ldo26．ifu?R且u?NR()then27．r=nil//未發(fā)現(xiàn)母節(jié)點(diǎn)28．foreachp∈Nu()do//尋找母節(jié)點(diǎn)29．ifp．t==0且p?NS()且(r=nil或Np()

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

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

算法3 DCAT?Greedy輸入：G=V，E()，s：匯點(diǎn)輸出：G以s為根的生成樹，及G的一個有效調(diào)度，其中v．t和v．p分別表示v∈V的傳輸時間和母節(jié)點(diǎn)1．procedureDCAT?GREEDY(G)2．DCAT(G；s)3．?v∈G．Vv．t=0//時隙初始化4．j=15．whiles．t=0do6．L=GETELIGIBLENODES(G)7．COMPUTEWEIGHTS(L)8．SORTDECREASING(L)9．S=R=?10．GREEDY?SCHEDULING(L；S；R)11．j=j+112．endwhile13．endprocedure

4 仿真結(jié)果

結(jié)合小型、中型和大型無線傳感器網(wǎng)絡(luò)對匯集樹構(gòu)建算法DCAT及傳輸調(diào)度算法進(jìn)行性能評估，通過將節(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)連通。對每個被選密度值，共生成100個連通圖，對這100個圖求取平均作為最終結(jié)果。

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

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

圖3在一定程度上表明了DCAT算法性能優(yōu)于復(fù)雜性更高的BSPT算法的原因。該圖給出了圖中相鄰節(jié)點(diǎn)數(shù)量與匯集樹上子節(jié)點(diǎn)平均數(shù)量之間的關(guān)系?？梢钥闯?，與DCAT相比，BSPT分配給度數(shù)更高節(jié)點(diǎn)(高度節(jié)點(diǎn))的子節(jié)點(diǎn)更多，而DCAT傾向于為度數(shù)低于網(wǎng)絡(luò)密度的節(jié)點(diǎn)分配較多子節(jié)點(diǎn)。如果以度數(shù)較高的節(jié)點(diǎn)作為母節(jié)點(diǎn)，則調(diào)度算法可在同一時隙內(nèi)調(diào)度更多個節(jié)點(diǎn)，有助于降低調(diào)度的總體延時。

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

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

圖5給出了調(diào)度算法對大型傳感器網(wǎng)絡(luò)的性能。

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

結(jié)果特點(diǎn)與上文類似。然而，幾乎在所有密度設(shè)置下，DCAT-WIRES的性能均優(yōu)于BSPT-WIRES-G。實(shí)際上，對中等密度水平，DCATWIRES-G的性能比BSPT-WIRES-G高出15%。DCAT-Greedy和DCAT-WIRES-G的性能相近，但當(dāng)密度在15～75(含)時，DCAT-WIRES-G略優(yōu)于DCAT-Greedy。與BSPT-WIRES相比，DCAT-WIRES-G的性能提升了34.66 %，而DCAT-Greedy相對于BSPT-WIRES提升了32.25%。而DCAT-Greedy結(jié)果的標(biāo)準(zhǔn)差(4.48)低于DCAT-WIRES-G的標(biāo)準(zhǔn)差(5.35)。

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

為了更好理解性能特點(diǎn)，考察了圖中節(jié)點(diǎn)度與匯集樹中子節(jié)點(diǎn)平均數(shù)量之間的關(guān)系。圖6給出了密度為30時中等隨機(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)異的原因。對高密度設(shè)置具有類似特點(diǎn)。

另外，還考察了匯集樹中子節(jié)點(diǎn)數(shù)量最多的節(jié)點(diǎn)所處位置。圖7給出了中等規(guī)模網(wǎng)絡(luò)在密度為30時的運(yùn)行結(jié)果?？梢钥闯觯瑓R點(diǎn)(距離為0的節(jié)點(diǎn))在除了DCAT-Greedy的各種算法下，子節(jié)點(diǎn)數(shù)量均較高。這是因?yàn)殚_始時采用最短路徑樹。因此，所有與匯點(diǎn)相距一跳距離的節(jié)點(diǎn)將是匯點(diǎn)的子節(jié)點(diǎn)。DCAT-Greedy不存在這個問題，因?yàn)樗鼮榱送瑫r調(diào)度盡可能多的節(jié)點(diǎn)而修改了初始樹。

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

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

此外，發(fā)現(xiàn)如果使度較高的節(jié)點(diǎn)與樹頂較近，往往會導(dǎo)致延時上升。這是因?yàn)榕c匯點(diǎn)的距離近了，可供選擇的節(jié)點(diǎn)少了，并行化的概率便會降低。使度較高的節(jié)點(diǎn)位于樹的底層，也不利于性能提升，因?yàn)橹挥挟?dāng)所有節(jié)點(diǎn)傳輸完畢才能使數(shù)據(jù)向上傳輸，這解釋了為何對密度中等的大型網(wǎng)絡(luò)，DCATWIRES-G的性能要優(yōu)于DCAT-Greedy。為此，一種可能的思路是設(shè)計一種將上述兩種算法綜合起來的混合算法來提升面對大型傳感器網(wǎng)絡(luò)時的性能。例如，對樹的底層采用DCAT-WIRES-G算法，對樹的高層采用DCAT-Greedy算法。

5 結(jié) 語

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

[1] Bagaa M, Younis M, Djenouri D,etal. 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,etal. 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,etal. 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,etal. Nearly constant approximation for data aggregation scheduling in wireless sensor networks[C]// 26th IEEE International Conference on Computer Communications(INFOCOM). 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,etal. Semi-matchings for bipartite graphs and load balancing[J]. Journal of Algorithms, 2006, 59(1): 53-78.

[11] Incel ? D, Ghosh A, Krishnamachari B,etal. 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

LIHao-guang1,HUYu-peng2

(1. School of Information Engineering, Guangdong Engineering Polytechnic, Guangzhou 510520, China; 2. The Software College, Hunan University, Changsha 410082, China)

Aiming at shortcomings of the large delay at the existing data aggregation algorithms in wireless sensor networks, we study the problem of the minimum latency data aggregation tree and transmission scheduling, and an aggregation tree construction algorithm based on degree constraint (DCAT) is proposed. 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, we propose two new approaches based on greedy for building a TDMA transmission schedule to perform efficient aggregation on a given tree: WIRES-G and DCAT-Greedy. We evaluate the performance of our algorithms through extensive simulations on randomly generated sensor networks of different sizes and we compare them to the previous state of the art. 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-03-03

國家自然科學(xué)基金(61300218); 廣東省軟科學(xué)研究計劃項(xiàng)目(142400410179)

李浩光(1982-)，男，廣東云浮人，碩士，講師，研究方向：無線傳感網(wǎng)、網(wǎng)絡(luò)算法。E-mail:365073134@qq.com

TP 393

A

1006-7167(2017)01-0117-06