WSN中基于最小延时的数据汇集树构建与传输调度算法

doi:10.11896/j.issn.1002-137X.2017.6A.068

计算机科学 ›› 2017, Vol. 44 ›› Issue (Z6): 300-304.doi: 10.11896/j.issn.1002-137X.2017.6A.068

WSN中基于最小延时的数据汇集树构建与传输调度算法

高蕾,胡玉鹏

惠州学院计算机科学系惠州516007,湖南大学软件学院长沙410082

出版日期:2017-12-01 发布日期:2018-12-01
基金资助:
本文受国家自然科学基金(61300218)资助

Data Aggregation Tree Construction and Transmission Scheduling Algorithm Based on Minimum Latency in Wireless Sensor Networks

GAO Lei and HU Yu-peng

Online:2017-12-01 Published:2018-12-01

摘要/Abstract

摘要： 针对现有的无线传感器网络数据汇集算法延时较大的不足,对最小延时数据汇集树和传输调度问题进行了研究。提出一种基于度约束的汇集树构建算法(DCAT)。该算法按照BFS方式遍历图,当遍历到每个节点时,通过确定哪些节点与汇点更近来确定潜在母节点集合。然后,选择图中度数最小的潜在母节点作为当前被遍历节点的母节点。此外,为了在给定的汇集树上进行高效的数据汇集,还提出两种新的基于贪婪的TDMA传输调度算法:WIRES-G和DCAT-Greedy。利用随机生成的不同规模的传感器网络,参照当前最新算法,对所提方法的性能进行了全面评估。结果表明,与当前最优算法相比,将所提调度算法与所提汇集树构建算法结合起来,可显著降低数据汇集的延时。

关键词: 无线传感器网络,数据汇集,最小延时,度约束,传输调度

Abstract: Aiming at the shortcomings of the larger delay at the existing data aggregation algorithms in wireless sensor networks,we studied the problem of the minimum latency data aggregation tree and transmission scheduling.An aggregation tree construction algorithm based on degree constraint(DCAT) was proposed.It works by traversing the graph in a BFS manner.As it traverses each node,the set of potential parents is determined by identifying the nodes that are one-hop closer to the sink.The potential parent with the lowest degree in the graph is selected as the parent for the currently traversed node.Furthermore,we proposed two new approaches based on greedy for building a TDMA transmission schedule to perform efficient aggregation on a given tree:WIRES-G and DCAT-Greedy.We evaluated the perfor-mance of our algorithms through extensive simulations on randomly generated sensor networks of different sizes and we compared them to the previous state of the art.The results show that new scheduling algorithms combining with our new tree-building algorithm obtain significantly lower latencies than that of the previous best algorithm.

Key words: Wireless sensor networks,Data aggregation,Minimum latency,Degree constraint,Transmission scheduling

高蕾,胡玉鹏. WSN中基于最小延时的数据汇集树构建与传输调度算法[J]. 计算机科学, 2017, 44(Z6): 300-304. https://doi.org/10.11896/j.issn.1002-137X.2017.6A.068

GAO Lei and HU Yu-peng. Data Aggregation Tree Construction and Transmission Scheduling Algorithm Based on Minimum Latency in Wireless Sensor Networks[J]. Computer Science, 2017, 44(Z6): 300-304. https://doi.org/10.11896/j.issn.1002-137X.2017.6A.068

参考文献

[1] BGAAA M,YOUNIS M,DJENOUI D,et al.Distributed low-latency data aggregation scheduling in wireless sensor networks [J].ACM Transactions on Sensor Networks (TOSN),2015,11(3):49-60.
[2] 石为人,唐云建,王燕霞.基于拥塞控制的无线传感器网络数据汇集树生成算法[J].自动化学报,2010,36(6):823-828.
[3] YOUSEFI H,MALEKIMAJD M,ASHOURI M,et al.Fast aggregation scheduling in wireless sensor networks [J].IEEE Transactions on Wireless Communications,2015,14(6):3402-3414.
[4] LIU X Y,ZHU Y,KONG L,et al.CDC:Compressive data collection for wireless sensor networks [J].IEEE Transactions on Parallel and Distributed Systems,2015,26(8):2188-2197.
[5] 杨庚,李森,陈正宇,等.传感器网络中面向隐私保护的高精确度数据融合算法 [J].计算机学报,2013,36(1):189-200.
[6] 邱立达,刘天键,傅平.基于稀疏滤波的无线传感器网络数据融合[J].电子测量与仪器学报,2015,29(3):352-357.
[7] GUO L,LI Y,CAI Z.Minimum-latency aggregation scheduling in wireless sensor network [J].Journal of Combinatorial Optimization,2016,31(1):279-310.
[8] HUANG S C H,WAN P J,VU C T,et al.Nearly constant approximation for data aggregation scheduling in wireless sensor networks[C]∥26th IEEE International Conference on Compu-ter Communications(INFOCOM).Anchorage,Alaska,USA:IEEE Press,2007:366-372.
[9] MALHOTRA B,NIKOLAIDIS I,NASCIMENTO M A.Aggregation convergecast scheduling in wireless sensor networks [J].Wireless Networks,2011,17(2):319-335.
[10] HARVEY N J A,LADNER R E,LOVSZ L,et al.Semi-matchings for bipartite graphs and load balancing[J].Journal of Algorithms,2006,59(1):53-78.
[11] INCEL  D,GHOSH A,KRISHNAMACHARI B,et al.Fast data collection in tree-based wireless sensor networks [J].IEEE Transactions on Mobile Computing,2012,11(1):86-99.
[12] YAO Y,CAO Q,VASILAKOS A V.EDAL:An energy-efficient,delay-aware,and lifetime-balancing data collection protocol for heterogeneous wireless sensor networks [J].IEEE/ACM Transactions on Networking,2015,23(3):810-823.

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed

WSN中基于最小延时的数据汇集树构建与传输调度算法

Data Aggregation Tree Construction and Transmission Scheduling Algorithm Based on Minimum Latency in Wireless Sensor Networks

PDF (PC)

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 0

Metrics

本文评价

推荐阅读 0