陳 權(quán)， 高 宏, 金代亮

(1 哈爾濱工業(yè)大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院， 哈爾濱 150001; 2 哈爾濱工業(yè)大學(xué) 網(wǎng)絡(luò)與信息中心， 哈爾濱 150001)

引言

隨著信息技術(shù)的發(fā)展和日益成熟，特別是新一代無線通信技術(shù)、嵌入式計(jì)算技術(shù)、傳感器網(wǎng)絡(luò)技術(shù)和自動(dòng)控制技術(shù)等的飛速發(fā)展，一種能夠?qū)⑿畔⑹澜缗c物理世界友好集成的信息物理融合系統(tǒng)(CPS，Cyber-Physical System) 被提了出來[1-2]。由于該系統(tǒng)能夠協(xié)作地實(shí)時(shí)監(jiān)測(cè)、感知、采集目標(biāo)域內(nèi)的各種環(huán)境或監(jiān)測(cè)對(duì)象信息并及時(shí)提供反饋控制信息，目前CPS系統(tǒng)已經(jīng)廣泛地應(yīng)用于國(guó)防軍事、環(huán)境監(jiān)測(cè)與保護(hù)、空氣污染治理、工業(yè)制造、礦物開采等眾多領(lǐng)域[3-5]。

數(shù)據(jù)聚集操作是CPS系統(tǒng)中一個(gè)重要而基本的操作，可以方便sink節(jié)點(diǎn)以最少的數(shù)據(jù)傳輸獲取整個(gè)網(wǎng)絡(luò)的匯總信息(例如整個(gè)網(wǎng)絡(luò)的最大值、最小值、平均值等查詢)[6-7]。假設(shè)網(wǎng)絡(luò)中所有的節(jié)點(diǎn)都引入了時(shí)間同步，并且數(shù)據(jù)傳輸都在相同長(zhǎng)度的時(shí)間槽內(nèi)完成。數(shù)據(jù)聚集操作就是在一棵以sink節(jié)點(diǎn)為根節(jié)點(diǎn)的聚集樹中，為每個(gè)節(jié)點(diǎn)生成一個(gè)無沖突傳輸計(jì)劃。由于無線傳輸中的干擾問題，在每一輪調(diào)度中僅有部分節(jié)點(diǎn)能夠同時(shí)傳輸。聚集延遲就是指最后一個(gè)數(shù)據(jù)到達(dá)sink節(jié)點(diǎn)的延遲。如何構(gòu)造聚集樹和調(diào)度節(jié)點(diǎn)的傳輸計(jì)劃會(huì)嚴(yán)重影響聚集延遲的大小。

在CPS系統(tǒng)中，節(jié)點(diǎn)主要工作在2種模式；一直醒著(always-awake)模式[8-10]或者占空比(duty-cycle)模式[11-13]。在一直醒著模式下，節(jié)點(diǎn)一直保持著工作狀態(tài)。此時(shí)，可以隨時(shí)建立一條可用的骨干傳輸路徑。而在占空比模式下，節(jié)點(diǎn)是在工作狀態(tài)和睡眠狀態(tài)之間來回切換，并且在大部分時(shí)間保持睡眠狀態(tài)來節(jié)省能耗。在這種模式下，節(jié)點(diǎn)只能在工作狀態(tài)接受數(shù)據(jù)。針對(duì)這兩種模式，研究者們對(duì)最小延遲聚集調(diào)度問題進(jìn)行了大量研究和分析。本文將從這兩種模式對(duì)最小延遲聚集調(diào)度問題所取得的進(jìn)展給出研究論述，論述內(nèi)容如下。

1 問題形式化定義

給定一個(gè)網(wǎng)絡(luò)G=(V,E)，其中|V| =N表示所有傳感器節(jié)點(diǎn)的集合，E表示網(wǎng)絡(luò)中邊的集合。邊eij屬于E表示節(jié)點(diǎn)j可以與節(jié)點(diǎn)i直接進(jìn)行通信。另外為了表示方便，每個(gè)節(jié)點(diǎn)均進(jìn)行了時(shí)間同步，并且在一個(gè)調(diào)度周期T內(nèi)，時(shí)間被劃分為具有相同長(zhǎng)度的時(shí)間槽τ(根據(jù)CC2420的標(biāo)準(zhǔn)，τ的長(zhǎng)度通常都是非常受限的[14])。每個(gè)節(jié)點(diǎn)的一次傳輸均在一個(gè)時(shí)間槽內(nèi)完成。

例如，圖1給出了一個(gè)數(shù)據(jù)聚集的例子，其中實(shí)線表示生成的聚集樹，虛線表示網(wǎng)絡(luò)中的邊(即兩個(gè)節(jié)點(diǎn)可以直接通信)。首先，調(diào)度所有的葉子節(jié)點(diǎn)將自己的數(shù)據(jù)傳輸給自己的父親節(jié)點(diǎn)，之后再將該葉子節(jié)點(diǎn)從聚集樹中刪除。其次，當(dāng)父親節(jié)點(diǎn)收到其兒子節(jié)點(diǎn)的數(shù)據(jù)后，將收到的數(shù)據(jù)與自己的數(shù)據(jù)進(jìn)行聚集計(jì)算，其結(jié)果將作為新的數(shù)據(jù)傳輸給上一層的父親節(jié)點(diǎn)。當(dāng)該父親節(jié)點(diǎn)收到其所有兒子節(jié)點(diǎn)的數(shù)據(jù)后，由于其兒子節(jié)點(diǎn)都已從聚集樹中刪除，該父親節(jié)點(diǎn)也變成了一個(gè)葉子節(jié)點(diǎn)。然后重復(fù)上面的過程，等待被調(diào)度。整個(gè)過程一直持續(xù)到所有的聚集樹中只剩下sink節(jié)點(diǎn)。

下面，將根據(jù)上面的網(wǎng)絡(luò)模型提出最小延遲聚集調(diào)度問題的形式化定義：

輸入: 一個(gè)網(wǎng)絡(luò)G=(V,E), 其中V表示網(wǎng)絡(luò)中節(jié)點(diǎn)的集合，E表示網(wǎng)絡(luò)中邊的集合，s表示sink節(jié)點(diǎn);

輸出: 一個(gè)調(diào)度計(jì)劃S={ [u,p(u),t(u)] |?u∈V-{s}}, 讓Si={u| [u,p(u),t(u)]∈S&t(u)=i}, 則S1,S2,…,Sm滿足如下條件：

1)Si∩Sj= ?,?i≠j;

4)m的長(zhǎng)度最小。

其中，p(u)表示節(jié)點(diǎn)u的父親節(jié)點(diǎn)，而t(u)表示節(jié)點(diǎn)u的傳輸時(shí)間槽，Si表示在第i個(gè)時(shí)間槽內(nèi)的發(fā)送節(jié)點(diǎn)的集合，m的大小則表示聚集延遲。

圖1 一個(gè)數(shù)據(jù)聚集調(diào)度的例子Fig. 1 An example of data aggregation scheduling

需要注意的是，第一個(gè)條件表示一個(gè)節(jié)點(diǎn)不能夠傳輸多次；第二個(gè)條件是指除了sink節(jié)點(diǎn)外的節(jié)點(diǎn)都完成了調(diào)度；第三個(gè)條件表征為了滿足聚集過程是從無沖突的；第四個(gè)條件則是為了滿足聚集延遲的限制。

針對(duì)該問題，研究者分別從節(jié)點(diǎn)一直醒著網(wǎng)絡(luò)模型和占空比模型展開了研究。

2 節(jié)點(diǎn)一直醒著網(wǎng)絡(luò)中最小延遲聚集調(diào)度算法的研究

在節(jié)點(diǎn)一直醒著網(wǎng)絡(luò)中，可以隨時(shí)建立一條可用的骨干傳輸路徑。在這種網(wǎng)絡(luò)中，數(shù)據(jù)聚集涉及到生成一棵聚集樹以及一個(gè)無沖突的聚集調(diào)度計(jì)劃。聚集延遲則可定義為無沖突的聚集調(diào)度計(jì)劃所需要的時(shí)間槽的個(gè)數(shù)。為了最小化數(shù)據(jù)聚集延遲，文獻(xiàn)[15-24]等關(guān)于這種網(wǎng)絡(luò)已發(fā)表了眾多研究成果。內(nèi)容如下。

Chen等在文獻(xiàn)[15]中首次證明了在節(jié)點(diǎn)一直醒著的網(wǎng)絡(luò)中，最小延遲聚集調(diào)度問題是NP-hard問題，即很難在多項(xiàng)式時(shí)間內(nèi)找到該問題的精確解。因此，研究提出了一種啟發(fā)式的集中式算法。在文獻(xiàn)[15]中，首先在網(wǎng)絡(luò)中構(gòu)建了一顆最短路徑樹(SPT)。接著，開始迭代的是調(diào)度樹上的節(jié)點(diǎn)。最初調(diào)度的就是樹上的葉子節(jié)點(diǎn)。為了避免沖突，只有當(dāng)該葉子節(jié)點(diǎn)不會(huì)引起其它調(diào)度節(jié)點(diǎn)的沖突時(shí)才能得到調(diào)度。當(dāng)葉子節(jié)點(diǎn)的調(diào)度發(fā)生后，該節(jié)點(diǎn)將被從SPT 樹中移除。整個(gè)過程一直持續(xù)到SPT樹為空。為了解決SPT算法容易產(chǎn)生聚集樹的高度過長(zhǎng)的問題，Malhotra等在文獻(xiàn)[16]中就采用了一棵平衡的SPT樹作為聚集樹。另外，為了生成節(jié)點(diǎn)的無沖突調(diào)度計(jì)劃，研究將無沖突的調(diào)度問題抽象成一個(gè)混合圖著色的問題來避免節(jié)點(diǎn)之間的沖突。

與之前將CDS或者SPT等固定的結(jié)構(gòu)作為聚集樹不同，Bagaa 等在文獻(xiàn)[21]提出了一種不依賴固定結(jié)構(gòu)的調(diào)度算法。研究首次提出了將聚集樹的構(gòu)造與調(diào)度計(jì)劃的生成同時(shí)并行的思想。在文獻(xiàn)[21]中，為了避免將一棵固定結(jié)構(gòu)的聚集樹作為輸入，提出了一種基于半結(jié)構(gòu)化拓?fù)涞木奂{(diào)度算法和一個(gè)基于無結(jié)構(gòu)化拓?fù)涞木奂{(diào)度算法。采用這種方法，聚集延遲被直接降低到(ξ+4)*R+Δ-4, 其中ξ= ?2π/arccos(1 + 1/ε)」，0.05 <ε≤ 1。

除了集中式的算法，Yu等在文獻(xiàn)[22～24]中對(duì)節(jié)點(diǎn)一直醒著網(wǎng)絡(luò)中的分布式聚集調(diào)度算法也相繼取得了系列研究成果，具體如下。

在文獻(xiàn)[22]中，Yu等首次提出了一種分布式的聚集調(diào)度算法DAS，即每個(gè)節(jié)點(diǎn)根據(jù)自己的鄰居信息及鄰居的調(diào)度信息，通過節(jié)點(diǎn)之間的合作生成一棵聚集樹和一個(gè)無沖突的聚集調(diào)度樹。DAS算法首先利用文獻(xiàn)[25]中的分布式算法建立一棵基于CDS的聚集樹。然后再通過節(jié)點(diǎn)之間的合作生成一個(gè)無沖突的聚集調(diào)度。最后，研究證明提出的分布式算法的聚集延遲的上界為24D+6Δ+16，其中D表示網(wǎng)絡(luò)的直徑。

Xu等[23]則在文獻(xiàn)[22]的基礎(chǔ)上提出了一種分布式聚集調(diào)度算法來強(qiáng)勢(shì)優(yōu)化降低聚集延遲。研究發(fā)現(xiàn)當(dāng)網(wǎng)絡(luò)半徑過長(zhǎng)時(shí)，將會(huì)導(dǎo)致聚集樹的高度急劇增加，從而導(dǎo)致聚集延遲過大。因此，為了解決該問題，研究將網(wǎng)絡(luò)的中心節(jié)點(diǎn)作為根節(jié)點(diǎn)，然后再利用之前的分布式算法[25]以該節(jié)點(diǎn)生成一棵聚集樹。當(dāng)所有節(jié)點(diǎn)將數(shù)據(jù)聚集到根節(jié)點(diǎn)后，再由根節(jié)點(diǎn)將數(shù)據(jù)包采取多跳路由的方式傳送到sink節(jié)點(diǎn)。最后，研究證明該算法的聚集延遲的上界為16R+Δ-14，與文獻(xiàn)[22]中的上界相比，已更顯優(yōu)勢(shì)。

最近，文獻(xiàn)[24]提出了一種不依賴于任何結(jié)構(gòu)的分布式聚集調(diào)度算法DICA。與先前文獻(xiàn)[22]和文獻(xiàn)[23]中的分布式算法不同的是，DICA算法不需要預(yù)先根據(jù)連通支配集生成一棵聚集樹。DICA首先將網(wǎng)絡(luò)中所有的節(jié)點(diǎn)根據(jù)與sink節(jié)點(diǎn)的距離劃分為不同的層次。然后采取按層調(diào)度的思想逐層調(diào)度網(wǎng)絡(luò)中的節(jié)點(diǎn)。最后，研究通過實(shí)驗(yàn)證明提出的算法在聚集延遲上要優(yōu)勝于之前的所有算法。

3 占空比網(wǎng)絡(luò)中最小延遲聚集調(diào)度算法的研究

在占空比網(wǎng)絡(luò)中，節(jié)點(diǎn)有2種工作狀態(tài)，即睡眠狀態(tài)和工作狀態(tài)，并且在2種狀態(tài)之間周期性地轉(zhuǎn)換。當(dāng)節(jié)點(diǎn)處于睡眠狀態(tài)時(shí)，節(jié)點(diǎn)所有的功能模塊(包含感知模塊，接受和發(fā)送模塊等)都將關(guān)閉。這意味著節(jié)點(diǎn)只能在工作狀態(tài)時(shí)接受數(shù)據(jù)。由于每個(gè)節(jié)點(diǎn)都是異步醒來的，因此很難在這種網(wǎng)絡(luò)中維持一條隨時(shí)可用的骨干路徑，同時(shí)也將導(dǎo)致數(shù)據(jù)包的延遲常常是普通網(wǎng)絡(luò)的成百上千倍。這些均為聚集調(diào)度算法帶來了新的挑戰(zhàn)。在這種網(wǎng)絡(luò)中，文獻(xiàn)[26-30]等對(duì)最小延遲聚集調(diào)度問題展開了研究，詳情如下。

文獻(xiàn)[26]首先提出了占空比網(wǎng)絡(luò)中最小延遲聚集調(diào)度問題。在占空比網(wǎng)絡(luò)中，聚集延遲不再有一個(gè)無沖突聚集調(diào)度所需要的時(shí)間槽個(gè)數(shù)，而是最后一個(gè)數(shù)據(jù)包到達(dá)～sink～節(jié)點(diǎn)的延遲。研究通過節(jié)點(diǎn)一直醒著的網(wǎng)絡(luò)中的聚集調(diào)度問題證明了該問題是NP-hard問題。 接著，研究再次提出了一種集中式的聚集調(diào)度算法。該算法首先構(gòu)造一棵基于CDS的聚集樹，然后再生成一個(gè)考慮節(jié)點(diǎn)活動(dòng)時(shí)間槽的無沖突調(diào)度計(jì)劃。最后，研究對(duì)提出算法的聚集延遲的上界進(jìn)行了分析，證明其延遲上界為(15R+Δ-3)*|T|, 其中|T| 表示占空比網(wǎng)絡(luò)中一個(gè)工作周期的長(zhǎng)度。

文獻(xiàn)[27]和文獻(xiàn)[28]均假設(shè)占空比網(wǎng)絡(luò)中的每個(gè)節(jié)點(diǎn)在每個(gè)工作周期中只有一個(gè)醒來的時(shí)間槽，并在該假設(shè)下提出了不同的聚集調(diào)度算法。文獻(xiàn)[27]第一次在生成聚集樹的過程中考慮了節(jié)點(diǎn)之間的睡眠延遲。通過計(jì)算節(jié)點(diǎn)之間的睡眠延遲，研究生成了一棵最短延遲樹，并將其作為聚集操作的聚集樹。另外，為了防止父親節(jié)點(diǎn)的兒子節(jié)點(diǎn)的個(gè)數(shù)過多，導(dǎo)致父親節(jié)點(diǎn)的延遲陡然激增，從而影響整個(gè)網(wǎng)絡(luò)的聚集延遲，研究又隨即提出了一種有效的平衡算法來限制父親節(jié)點(diǎn)的兒子節(jié)點(diǎn)的個(gè)數(shù)。

在文獻(xiàn)[28]中，研究首先以sink為根節(jié)點(diǎn)構(gòu)造一棵廣度優(yōu)先樹，并將其作為聚集操作的聚集樹。為了得到最小化聚集延遲的無沖突調(diào)度，研究則將調(diào)度問題抽象為圖著色問題(即不在干擾半徑范圍內(nèi)的節(jié)點(diǎn)可以分配同樣一種顏色)，并且提出了一種基于圖劃分和圖著色的調(diào)度算法。在研究最后又通過理論分析，證明該算法的近似比為(R+Δ)。

與之前占空比網(wǎng)絡(luò)中的聚集調(diào)度算法[26-28]不同的是，文獻(xiàn)[29]考慮了在占空比網(wǎng)絡(luò)中，當(dāng)所有節(jié)點(diǎn)分布在一個(gè)2D平面中時(shí)，最小化延遲的聚集調(diào)度問題。通過假設(shè)每個(gè)節(jié)點(diǎn)的位置信息已知，繼而根據(jù)節(jié)點(diǎn)的位置信息將節(jié)點(diǎn)劃分為網(wǎng)格。而基于節(jié)點(diǎn)的網(wǎng)格信息，探討提出了一種集中式貪心調(diào)度算法(GAS)和一種分布式的近似算法(PAS)。其集中式算法和分布式算法的近似比均為(R+Δ)。

至此，除了協(xié)議干擾模型[26-29]外，另有文獻(xiàn)[30]還運(yùn)用獨(dú)家視角深度討論了物理干擾模型下的占空比網(wǎng)絡(luò)中最小化延遲的聚集調(diào)度算法。在物理干擾模型下，一個(gè)節(jié)點(diǎn)能夠成功地接收到數(shù)據(jù)包當(dāng)且僅當(dāng)該節(jié)點(diǎn)的信噪比值(SINR)小于一個(gè)給定的閾值。該模型能夠更好地刻畫網(wǎng)絡(luò)中無線傳輸。在該模型下，探討提出了兩種基于CDS結(jié)構(gòu)的集中式聚集調(diào)度算法。

4 結(jié)束語

數(shù)據(jù)聚集調(diào)度能夠幫助sink節(jié)點(diǎn)無沖突地獲取整個(gè)網(wǎng)絡(luò)的匯總信息，是信息物理融合系統(tǒng)中至關(guān)重要的一項(xiàng)服務(wù)。最小延遲聚集調(diào)度問題具有重要的理論，更具實(shí)際價(jià)值。本文則是以對(duì)信息物理融合系統(tǒng)中的最小延遲聚集調(diào)度問題的基礎(chǔ)描述作為開端，接著就從2個(gè)方面，即：節(jié)點(diǎn)一直醒著模式和占空比模式，對(duì)最小延遲聚集調(diào)度問題所取得的進(jìn)展進(jìn)行了系統(tǒng)闡述與分析。

[1] LEE E A. Cyber physical systems: Design challenges[C]//Proceedings of 11thIEEE International Symposium on Object Oriented Real-Time Distributed Computing. Orlando, FL: IEEE, 2008: 363-369.

[2] 孫利民, 李建中, 陳渝. 無線傳感器網(wǎng)絡(luò)[M]. 北京:清華大學(xué)出版社,2005.

[3] 陳權(quán), 高宏. RSPEED：無線傳感器網(wǎng)絡(luò)中基于不確定延遲的可靠實(shí)時(shí)路由[J]. 通信學(xué)報(bào),2013(8):110-119.

[4] GAO J, LI J, CAI Z, et al . Composite event coverage in Wireless Sensor Networks with heterogeneous sensors[C]//Proceedings of the 34thIEEE International Conference on Computer Communications (IEEE INFOCOM). Hong Kong, China:IEEE, 2015: 217-225.

[5] CHENG S, LI J, CAI Z. O(ε)-approximation to physical world by sensor networks[C]//Proceedings of IEEE INFOCOM. Turin, Italy:IEEE, 2013:3084-3092.

[6] YAN Mingyuan, HAN Meng, AI Chunyu, et al. Data aggregation scheduling in probabilistic Wireless Networks with cognitive radio capability[C]//Proceedings of the IEEE Global Communications Conference. Washington, DC,USA: IEEE, 2016:1-8.

[7] LI Ji, CHENG Siyao, CAI Zhipeng, et al. Approximate holistic aggregation in wireless sensor networks[J]. ACM Transactions on Sensor Networks (TOSN),2017,13(2):1-11.

[8] WANG Jiliang， LIU Yunhao, HE Yuan, et al. QoF: Towards comprehensive path quality measurement in wireless sensor networks[J]. IEEE Transactions on Parallel and Distributed Systems, 2014, 25(4):1003- 1013.

[9] CHEN Quan, GAO Hong. Link quality based path delay analysis in wireless sensor networks[J]. Journal on Communication, 2014, 35(6):100-109.

[10]WANG Yunbo, VURAN M C, GODDARD S. Cross-layer analysis of the end-to-end delay distribution in wireless sensor networks[J]. IEEE/ACM Transactions on Networking, 2012, 20(1):305-318.

[11]CHEN Quan, CHENG Siyao, GAO Hong, et al. Energy-efficient algorithm for multicasting in duty-cycled sensor networks[J]. Sensors, 2015, 15(12):31224-31243.

[12]GU Yu, HE Tian. Dynamic switching-based data forwarding for low-duty-cycle wireless sensor networks[J]. IEEE Transactions on Mobile Computing, 2011, 10(12): 1741-1754.

[13]CHEN Quan, GAO Hong. Towards reliable and real-time routing with active slot augmentation in low-duty-cycle WSNs[C]//Proceedings of the 9thInternational Conference on Wireless Algorithms, Systems, and Applications. Harbin, China: Springer,2014:672-681.

[14]Chipcon. CC2420 data sheet[EB/OL].[2017-03-02]. http://www.ti.com/.

[15]CHEN Xujin, HU Xiaodong, ZHU Jianming. Minimum data aggregation time problem in wireless sensor networks[C]//MSN'05 Proceedings of the First international conference on Mobile Ad-hoc and Sensor Network. Wuhan, China: IEEE, 2005:133-142.

[16]MALHOTRA B, NIKOLAIDIS I, NASCIMENTO M A. Aggregation convergecast scheduling in wireless sensor networks[J]. Springer Wireless Networks, 2010, 17(2):319-335.

[17]HUANG S C H, WAN P J, VU C T, et al. Nearly constant approximation for data aggregation scheduling in wireless sensor networks[C]//Proceedings of 26thIEEE International Conference on Computer Communications (INFOCOM). Alaska, USA: IEEE, 2007: 366-372.

[18]MATULA D W, BECK L L. Smallest-last ordering and clustering and graph coloring algorithms[J]. Journal of the Association of Computing Machinery,1983, 30(3):417-427.

[19]REN Meirui, GUO Longjiang, LI Jinbo. A new scheduling algorithm for reducing data aggregation latency in Wireless Sensor Networks[J]. International Journal of Communication, Network and System Sciences, 2010, 3(8): 679-688.

[20]WAN Pengjun, HUANG S C H, WANG Lixin, et al. Minimum-latency aggregation scheduling in multihop wireless networks[C]//Proceedings of the 10thACM International Symposium on Mobile Ad Hoc Networking and Computing (MobiHoc). New Orleans, LA, USA: IEEE, 2009:185-194.

[21]BAGAA M, DERHAB A, LASLA, N, et al. Semi-structured and unstructured data aggregation scheduling in wireless sensor networks[C]//Proceedings of IEEE Conference on Computer Communications (INFOCOM). Orlando, FL, USA: IEEE, 2012: 2671-2675.

[22]YU B, LI J Z, LI Y. Distributed data aggregation scheduling in Wireless Sensor Networks[C]//Proceedings of IEEE Conference on Computer Communications (INFOCOM). Rio, Brazil: IEEE,2009:2159-2167.

[23]XU Xiaohua, LI Xiangyang , MAO Xufei, et al A delay efficient algorithm for data aggregation in multi-hop Wireless Sensor Networks[J]. IEEE Transactions on Parallel and Distributed Systems, 2011, 22(1):163-175.

[24]BAGAA M, YOUNIS M, DJENOURI D, et al. Distributed low-latency data aggregation scheduling in Wireless Sensor Networks[J]. ACM Trans. Sen. Netw.,2015, 11(3):1-36.

[25]WAN P J, ALZOUBI K M, FRIEDER O. Distributed construction of connected dominating set in wireless ad hoc networks[C]//Proceedings of IEEE Conference on Computer Communications (INFOCOM). New York, NY, USA: IEEE, 2002:1597-1604.

[26]YU Bo, LI Jianzhong. Minimum-time aggregation scheduling in duty-cycled Wireless Sensor Networks[J]. Journal of Computer Science and Technology, 2011, 26(6): 962-970.

[27]HA N P K, ZALYUBOVSKIY V, CHOO H. Delay-efficient data aggregation scheduling in duty-cycled Wireless Sensor Networks[C]//Proceedings of RACS. San Antonio, TX, USA: IEEE,2012:203-208.

[28]JIAO Xianlong, LOU Wei, WANG Xiaodong, et al. Data aggregation scheduling in uncoordinated duty-cycled Wireless Sensor Networks under protocol interference model[J]. Journal of Ad Hoc & Sensor Wireless Networks, 2012, 15(2):315-338.

[29]XIAO Shiliang, HUANG Jingchang, PAN Lebing, et al. On centralized and distributed algorithms for minimizing data aggregation time in duty-cycled wireless sensor networks[J].Wireless Networks, 2014, 20(7):1729-1741.

[30]TANG Jiuyang, JIAO Xianlong, XIAO Wendong. Minimum-latency data aggregation in duty-cycled Wireless Sensor Networks under physical interference model[C]// 2013 22ndProceedings of IEEE Wireless and Optical Communication Conference. Chongqing, China: IEEE, 2013:309-314.