摘要： 针对现有聚集数据调度近似算法具有较高延时上界的问题，提出一种改进的聚集数据调度近似算法。建立一棵根在中心结点的广度优先搜索树，分层构造一个最大独立集(MIS)，使MIS中相邻的2个结点相距两跳。将MIS中的结点连接起来，形成一棵根在中心结点的数据聚集调度树，使结点按数据聚集调度树进行分层数据调度。在数据聚集调度树的构造过程中，对于任意支配点，以最小的结点连接其相距两跳的支配点。对于2个相邻支配点的公共邻居支配点，通过在距中心点最近的支配点加入数据聚集树，使其在数据调度过程中将数据发送给距中心点最近的支配点，从而降低数据的聚集延时。实验结果表明，与SAS算法、Guo’s算法和IAS算法相比，该算法的数据聚集延时更低，其延时上界为14R+△?10。

关键词: 数据聚集, 最小延时, 无线传感器网络, 数据调度算法, 圆盘图, 传输冲突

Abstract: An improved approximation data aggregation scheduling algorithm for Minimum Data Aggregation Latency(MDAL) is presented due to the existing algorithms have a high time latency bound. A Breadth First Search(BFS) tree rooted at the center node is constructed in this algorithm. And then, a Maximal Independent Set(MIS) is found layer by layer and the adjacent dominators have only 2-hop away from each other. A data aggregation scheduling tree rooted at the center node is formed by using some nodes to connect the nodes in MIS. Thus, the node’s data can be scheduled layer by layer according to the data aggregation scheduling tree. For every dominator, it always connects its 2-hop neighboring dominators using minimal connectors. For the common neighboring dominators of two adjacent dominators, they select a dominator which is close to the center node to join the data aggregation scheduling tree so as to send their data to it. Using this method, the latency for the sink collecting all sensors’ data is reduced greatly. Simulation results show that compared with SAS algorithm, Guo’s algorithm and IAS algorithm, this algorithm has lower average latency than previous works and it has a latency bound of 14R+△?10.

Key words: data aggregation, minimum latency, Wireless Sensor Networks(WSNs), data scheduling algorithm, disk graph, transmitting collision

中图分类号: 

• TP393