WSN中最小延時的數據匯集樹構建與傳輸調度算法

李浩光， 胡玉鵬

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

WSN中最小延時的數據匯集樹構建與傳輸調度算法

李浩光1， 胡玉鵬2

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

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

無線傳感器網絡； 數據匯集； 最小延時； 度約束； 傳輸調度

0 引 言

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

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

1 網絡模型和問題描述

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

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

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

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

算法1 DCAT輸入：G=V，E()，s：匯點輸出：圖G以s為根的生成樹，其中v．p表示v∈V的母節點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 調度算法

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

算法2 WIRES?G輸入：G=V，E()，s：匯點，v．p：樹中v∈V的母節點輸出：G的一個有效調度，其中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=?//發送節點和接收節點集合開始時為空9．SCHEDULENODES(L；S；R)10．L=LS//將發送節點從合格節點中刪除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在傳輸時不發生沖突18．u．t=j//通過調度使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//未發現母節點28．foreachp∈Nu()do//尋找母節點29．ifp．t==0且p?NS()且(r=nil或Np()

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

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

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

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

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

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

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

圖3 圖的度數與匯集樹子節點平均數量之間的關系

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

圖5給出了調度算法對大型傳感器網絡的性能。

圖4 網絡規模為5×5時平均匯集延時

結果特點與上文類似。然而，幾乎在所有密度設置下，DCAT-WIRES的性能均優于BSPT-WIRES-G。實際上，對中等密度水平，DCATWIRES-G的性能比BSPT-WIRES-G高出15%。DCAT-Greedy和DCAT-WIRES-G的性能相近，但當密度在15～75(含)時，DCAT-WIRES-G略優于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 網絡規模為20×20時平均匯集延時

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

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

圖6 圖的度數與匯集樹子節點平均數量之間的關系

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

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

5 結 語

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

[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] 石為人, 唐云建, 王燕霞. 基于擁塞控制的無線傳感器網絡數據匯集樹生成算法[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] 楊 庚, 李 森, 陳正宇, 等. 傳感器網絡中面向隱私保護的高精確度數據融合算法 [J]. 計算機學報, 2013, 36(1): 189-200.

[6] 邱立達, 劉天鍵, 傅 平. 基于稀疏濾波的無線傳感器網絡數據融合[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-)，男，廣東云浮人，碩士，講師，研究方向：無線傳感網、網絡算法。E-mail:365073134@qq.com

TP 393

A

1006-7167(2017)01-0117-06