信息物理融合系统中最小延迟数据聚集调度算法综述

陈 权， 高 宏, 金代亮

(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.