针对现有的基于物理干扰模型的数据聚集调度近似算法具有延时较高的问题，提出了一种改进的数据聚集调度近似算法。该算法首先构造一个连通支配集作为数据聚集树，使各节点根据数据聚集树分层进行数据调度；然后将整个网络划分为若干个边长相等的正方形区域，使每个区域中最多包含一个支配节点；最后对各个区域进行着色，并从颜色相同的每个正方形区域中任选一个普通节点，使它们能同时将数据汇聚到相应的支配节点。当数据从所有普通节点聚集到相应支配节点后，则将这些正方形区域构成一个大小相同的块，并采用四种颜色对这些块进行着色，使颜色相同的各个块中任选一条通信链路能够同时进行数据传输而不会发生通信冲突和干扰。理论分析表明，该算法的延时上界为K2Δ＋8K2R-3R；仿真模拟的结果表明，该算法产生的数据聚集延时低于现有算法。%This paper presented an improved data aggregation scheduling approximation algorithm,due to the existing data ag-gregation scheduling algorithms under the physical interference model had high time latency in wireless sensor networks.First-ly,this algorithm constructed a connected dominating set as a data aggregation tree so that every node’s data in network could be scheduled layer by layer.Secondly,it divided the whole network into square cells with the same side length so that each cell contained one dominator at most.Finally,it colored every square cell by using different colors.Therefore,some nodes from the cells with same color could be selected randomly to be scheduled simultaneously.After all dominatees’s data were ag-gregated to their corresponding dominators,the whole network was divided into large-blocks consisting of same number of square cells,and the four colors were used to color these blocks so that the adjacent blocks had different colors.And then, some communication links were selected randomly from these blocks with same color,which could be scheduled simultaneously without any communication collision and transmission interference.The theoretical analysis shows that the algorithm has a la-tency bound with K2Δ+8K2R-3R.Simulation results show that this algorithm has lower average latency than previous works.
展开▼
