基于物理干扰模型的无通信冲突的数据聚集调度算法

Data aggregation scheduling algorithm without communication collision under physical interference model

针对基于物理干扰模型的最小延时数据聚集调度问题,提出一种改进的无通信冲突的数据聚集调度算法。该算法采用簇与局部聚集树相结合的调度机制,首先在小区域范围内形成簇,当头节点聚集簇内成员节点的数据后,这些头节点再在一个较大的区域内形成新的簇。与现有算法相比,该算法不是将簇内各成员节点的数据直接传输给头节点,而是先构造一棵根在头节点的局部数据聚集树,然后将整个网络划分为若干个边长相等且只包含一个节点的正方形区域,最后对节点所在区域进行着色,使颜色相同、其孩子节点为空或已完成数据调度的簇内成员节点根据局部聚集树进行数据调度。实验结果表明,与现有算法相比,该算法的数据聚集延时更低,其延时上界为(5+logK+1Δ)(K+1)2。

This paper presented an improved data aggregation scheduling algorithm without communication collision aimed to solve the minimum latency data aggregation scheduling problem under the physical interference model. The algorithm applied cluster-based aggregation mechanism integrating with local aggregation tree-based aggregation mechanism. At the beginning, sensor moted in each small area-form a cluster. After the cluster head in each cluster had aggregation data from all the members, these cluster heads formed a new cluster in a larger area. Comparing with the existing algorithms, this algorithm didn＇t transmit data from member node to cluster head in each cluster directly. However, it constructed a local data aggregation tree root at the head using a certain method for each cluster. And then, it partitioned the whole network into square ceils with the same side length and each cell contains only one node. Lastly, it colored these square ceils in order to let the member node with the same color, having been aggregated data from its children or having no child, to transmit data according to the local aggregation tree. Simulation results show that this algorithm has lower average latencies than previous works and it has a laten- cy bound with （5 ＋ logK＋1Δ）（K＋1）^2.