An improved distributed data aggregation scheduling in wireless sensor networks
An improved distributed data aggregation scheduling in wireless sensor networks
复制标题
DOI：
10.1007/s10878-012-9504-9
复制
发表时间：
2012-05
影响因子：
1
通讯作者：
Deying Li;Qing-hua Zhu;Hongwei Du;Jianzhong Li
中科院分区：
文献类型：
--
作者：
Deying Li;Qing-hua Zhu;Hongwei Du;Jianzhong Li
本文主要研究无线传感器网络中的分布式数据汇聚无冲突调度问题。Bo等人（Proc. IEEE INFOCOM，2009）提出了用于该问题的近似分布式算法，并且Xu等人（Proc. ACM FOWANC，2009）提出了集中式算法及其分布式实现以生成用于该问题的无冲突调度，这是仅有的两种现有分布式算法。不幸的是，在Bo等人（Proc. IEEE INFOCOM，2009）的性能分析中存在一些错误，并且分布式算法不能获得与集中式算法相同的延迟，因为分布式实现不是集中式算法的准确实现（Xu等人，Proc. ACM FOWANC，2009）。在此基础上，提出了一种改进的分布式算法，用于生成无线传感器网络中的无冲突数据聚合调度。不是采用Bo等人（Proc. IEEE INFOCOM，2009）中的任意树，而是采用以sink节点为根的宽度优先搜索树（BFS），获得调度的有界延迟61 R +5Δ-67，其中R是网络相对于sink节点的半径，Δ是最大节点度。我们还将Bo等人（Proc. IEEE INFOCOM，2009）中调度的延迟界限校正为61 D +5Δ−67，其中D是网络的直径，并证明我们的算法比算法更有效（Bo等人在Proc. IEEE INFOCOM，2009）。我们还给出了Xu等人（Proc. ACM FOWANC，2009）中分布式实现的延迟范围。
This paper focuses on the distributed data aggregation collision-free scheduling problem, which is one of very important issues in wireless sensor networks. Bo et al. (Proc. IEEE INFOCOM, 2009) proposed an approximate distributed algorithm for the problem and Xu et al. (Proc. ACM FOWANC, 2009) proposed a centralized algorithm and its distributed implementation to generate a collision-free scheduling for the problem, which are the only two existing distributed algorithms. Unfortunately, there are a few mistakes in their performance analysis in Bo et al. (Proc. IEEE INFOCOM, 2009), and the distributed algorithm can not get the same latency as the centralized algorithm because the distributed implementation was not an accurate implementation of the centralized algorithm (Xu et al. in Proc. ACM FOWANC, 2009). According to those, we propose an improved distributed algorithm to generate a collision-free schedule for data aggregation in wireless sensor networks. Not an arbitrary tree in Bo et al. (Proc. IEEE INFOCOM, 2009) but a breadth first search tree (BFS) rooted at the sink node is adopted, the bounded latency 61R+5Δ−67 of the schedule is obtained, whereRis the radius of the network with respect to the sink node and Δ is the maximum node degree. We also correct the latency bound of the schedule in Bo et al. (Proc. IEEE INFOCOM, 2009) as 61D+5Δ−67, whereDis a diameter of the network and prove that our algorithm is more efficient than the algorithm (Bo et al. in Proc. IEEE INFOCOM, 2009). We also give a latency bound for the distributed implementation in Xu et al. (Proc. ACM FOWANC, 2009).