李浩光， 胡玉鵬

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

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

李浩光1， 胡玉鵬2

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

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

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

0 引 言

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

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

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

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

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

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

圖1 DCAT算法和BSPT算法構建的匯集樹比較

算法1 DCAT輸入：G=V，E()，s：匯點輸出：圖G以s為根的生成樹，其中v．p表示v∈V的母節(jié)點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，是對文獻[9]中WIRES算法的一種改進：在WIRES算法中增加一個步驟，以便每個時隙期間調(diào)度更多個節(jié)點。每一輪次中，新添步驟需要為原來算法無法調(diào)度的合格節(jié)點匹配新的母節(jié)點。WIRES-G的具體內(nèi)容請見算法2(G表示貪婪)。工作流程如下。第5～9行表示原來WIRES算法每一輪次的步驟。第9行結束時，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ā)生干擾。

算法2 WIRES?G輸入：G=V，E()，s：匯點，v．p：樹中v∈V的母節(jié)點輸出：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é)點和接收節(jié)點集合開始時為空9．SCHEDULENODES(L；S；R)10．L=LS//將發(fā)送節(jié)點從合格節(jié)點中刪除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é)點28．foreachp∈Nu()do//尋找母節(jié)點29．ifp．t==0且p?NS()且(r=nil或Np()

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

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

算法3 DCAT?Greedy輸入：G=V，E()，s：匯點輸出：G以s為根的生成樹，及G的一個有效調(diào)度，其中v．t和v．p分別表示v∈V的傳輸時間和母節(jié)點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 仿真結果

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

5 結 語

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

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

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

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

TP 393

A

1006-7167(2017)01-0117-06