CAJ | 학술논문

针对现有聚集数据调度近似算法具有较高延时上界的问题，提出一种改进的聚集数据调度近似算法。建立一棵根在中心结点的广度优先搜索树，分层构造一个最大独立集(MIS)，使MIS中陒邻的2个结点陒距两跳。将MIS中的结点连接起来，形成一棵根在中心结点的数据聚集调度树，使结点按数据聚集调度树进行分层数据调度。在数据聚集调度树的构造过程中，对于任意支配点，以最小的结点连接其陒距两跳的支配点。对于2个陒邻支配点的公共邻居支配点，通过在距中心点最近的支配点加入数据聚集树，使其在数据调度过程中将数据发送给距中心点最近的支配点，从而降低数据的聚集延时。实验结果表明，与SAS算法、Guo’s算法和IAS算法陒比，该算法的数据聚集延时更低，其延时上界为14R+△-10。
침대현유취집수거조도근사산법구유교고연시상계적문제，제출일충개진적취집수거조도근사산법。건립일과근재중심결점적엄도우선수색수，분층구조일개최대독립집(MIS)，사MIS중희린적2개결점희거량도。장MIS중적결점련접기래，형성일과근재중심결점적수거취집조도수，사결점안수거취집조도수진행분층수거조도。재수거취집조도수적구조과정중，대우임의지배점，이최소적결점련접기희거량도적지배점。대우2개희린지배점적공공린거지배점，통과재거중심점최근적지배점가입수거취집수，사기재수거조도과정중장수거발송급거중심점최근적지배점，종이강저수거적취집연시。실험결과표명，여SAS산법、Guo’s산법화IAS산법희비，해산법적수거취집연시경저，기연시상계위14R+△-10。
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.