Computer Science ›› 2017, Vol. 44 ›› Issue (Z6): 300-304.doi: 10.11896/j.issn.1002-137X.2017.6A.068

Previous Articles     Next Articles

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: 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

[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.

No related articles found!
Full text



No Suggested Reading articles found!