信息物理融合系統中最小延遲數據聚集調度算法綜述

陳 權， 高 宏, 金代亮

(1 哈爾濱工業大學 計算機科學與技術學院， 哈爾濱 150001; 2 哈爾濱工業大學 網絡與信息中心， 哈爾濱 150001)

引言

隨著信息技術的發展和日益成熟，特別是新一代無線通信技術、嵌入式計算技術、傳感器網絡技術和自動控制技術等的飛速發展，一種能夠將信息世界與物理世界友好集成的信息物理融合系統(CPS，Cyber-Physical System) 被提了出來[1-2]。由于該系統能夠協作地實時監測、感知、采集目標域內的各種環境或監測對象信息并及時提供反饋控制信息，目前CPS系統已經廣泛地應用于國防軍事、環境監測與保護、空氣污染治理、工業制造、礦物開采等眾多領域[3-5]。

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

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

1 問題形式化定義

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

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

下面，將根據上面的網絡模型提出最小延遲聚集調度問題的形式化定義：

輸入: 一個網絡G=(V,E), 其中V表示網絡中節點的集合，E表示網絡中邊的集合，s表示sink節點;

輸出: 一個調度計劃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的長度最小。

其中，p(u)表示節點u的父親節點，而t(u)表示節點u的傳輸時間槽，Si表示在第i個時間槽內的發送節點的集合，m的大小則表示聚集延遲。

圖1 一個數據聚集調度的例子Fig. 1 An example of data aggregation scheduling

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

針對該問題，研究者分別從節點一直醒著網絡模型和占空比模型展開了研究。

2 節點一直醒著網絡中最小延遲聚集調度算法的研究

在節點一直醒著網絡中，可以隨時建立一條可用的骨干傳輸路徑。在這種網絡中，數據聚集涉及到生成一棵聚集樹以及一個無沖突的聚集調度計劃。聚集延遲則可定義為無沖突的聚集調度計劃所需要的時間槽的個數。為了最小化數據聚集延遲，文獻[15-24]等關于這種網絡已發表了眾多研究成果。內容如下。

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

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

除了集中式的算法，Yu等在文獻[22～24]中對節點一直醒著網絡中的分布式聚集調度算法也相繼取得了系列研究成果，具體如下。

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

Xu等[23]則在文獻[22]的基礎上提出了一種分布式聚集調度算法來強勢優化降低聚集延遲。研究發現當網絡半徑過長時，將會導致聚集樹的高度急劇增加，從而導致聚集延遲過大。因此，為了解決該問題，研究將網絡的中心節點作為根節點，然后再利用之前的分布式算法[25]以該節點生成一棵聚集樹。當所有節點將數據聚集到根節點后，再由根節點將數據包采取多跳路由的方式傳送到sink節點。最后，研究證明該算法的聚集延遲的上界為16R+Δ-14，與文獻[22]中的上界相比，已更顯優勢。

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

3 占空比網絡中最小延遲聚集調度算法的研究

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

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

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

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

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

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

4 結束語

數據聚集調度能夠幫助sink節點無沖突地獲取整個網絡的匯總信息，是信息物理融合系統中至關重要的一項服務。最小延遲聚集調度問題具有重要的理論，更具實際價值。本文則是以對信息物理融合系統中的最小延遲聚集調度問題的基礎描述作為開端，接著就從2個方面，即：節點一直醒著模式和占空比模式，對最小延遲聚集調度問題所取得的進展進行了系統闡述與分析。

[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] 孫利民, 李建中, 陳渝. 無線傳感器網絡[M]. 北京:清華大學出版社,2005.

[3] 陳權, 高宏. RSPEED：無線傳感器網絡中基于不確定延遲的可靠實時路由[J]. 通信學報,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.