An efficient algorithm for scheduling sensor data collection through multi-path routing structures

Multi-path routing is essential to improve the robustness of sensor data collection in error-prone wireless communication environments. Besides the robustness against communication failures, both the energy efficiency and time efficiency are also of primary importance in sensor data collection due t...

Full description

Saved in:
Bibliographic Details
Main Authors: Luu, Hai Van, Tang, Xueyan
Other Authors: School of Computer Engineering
Format: Article
Language:English
Published: 2013
Subjects:
Online Access:https://hdl.handle.net/10356/98685
http://hdl.handle.net/10220/17430
Tags: Add Tag
No Tags, Be the first to tag this record!
Institution: Nanyang Technological University
Language: English
id sg-ntu-dr.10356-98685
record_format dspace
spelling sg-ntu-dr.10356-986852020-05-28T07:17:35Z An efficient algorithm for scheduling sensor data collection through multi-path routing structures Luu, Hai Van Tang, Xueyan School of Computer Engineering DRNTU::Engineering::Computer science and engineering Multi-path routing is essential to improve the robustness of sensor data collection in error-prone wireless communication environments. Besides the robustness against communication failures, both the energy efficiency and time efficiency are also of primary importance in sensor data collection due to the limited energy supplies of sensor nodes and the real-time nature of sensor network applications. Contention-free time division multiple access (TDMA) protocols have the potential to reduce the energy consumption and the latency of sensor data collection. To collect sensor data using a TDMA protocol, sensor nodes need to be assigned appropriate time slots for transmitting and receiving data prior to the data collection process. We note that the distributed TDMA scheduling process for sensor data collection incurs overhead costs of energy consumption and time latency. However, these overhead costs are usually overlooked, especially when multi-path routing is used to collect sensor data. In this paper, we propose an efficient scheduling algorithm for data collection through multi-path routing structures in wireless sensor networks. The objective of our scheduling algorithm is to reduce both the message complexity and running time of the scheduling process as much as possible. In addition, we also develop a method for deriving a lower bound on the shortest possible length of the data collection schedule that can be generated by any algorithm. The lower bound latency estimation offers a practical method to evaluate the efficiency of data collection schedules produced by scheduling algorithms. Extensive experimental results show that the proposed scheduling algorithm significantly reduces the number of messages transmitted during the scheduling process and the running time compared to an existing scheduling algorithm. The length of the data collection schedule produced by our algorithm is normally within 1.9 times of the lower bound estimate across a wide range of network settings. 2013-11-08T03:16:28Z 2019-12-06T19:58:28Z 2013-11-08T03:16:28Z 2019-12-06T19:58:28Z 2013 2013 Journal Article Luu, H. V., & Tang, X. (2013). An efficient algorithm for scheduling sensor data collection through multi-path routing structures. Journal of network and computer applications, in press. 1084-8045 https://hdl.handle.net/10356/98685 http://hdl.handle.net/10220/17430 10.1016/j.jnca.2013.03.013 en Journal of network and computer applications
institution Nanyang Technological University
building NTU Library
country Singapore
collection DR-NTU
language English
topic DRNTU::Engineering::Computer science and engineering
spellingShingle DRNTU::Engineering::Computer science and engineering
Luu, Hai Van
Tang, Xueyan
An efficient algorithm for scheduling sensor data collection through multi-path routing structures
description Multi-path routing is essential to improve the robustness of sensor data collection in error-prone wireless communication environments. Besides the robustness against communication failures, both the energy efficiency and time efficiency are also of primary importance in sensor data collection due to the limited energy supplies of sensor nodes and the real-time nature of sensor network applications. Contention-free time division multiple access (TDMA) protocols have the potential to reduce the energy consumption and the latency of sensor data collection. To collect sensor data using a TDMA protocol, sensor nodes need to be assigned appropriate time slots for transmitting and receiving data prior to the data collection process. We note that the distributed TDMA scheduling process for sensor data collection incurs overhead costs of energy consumption and time latency. However, these overhead costs are usually overlooked, especially when multi-path routing is used to collect sensor data. In this paper, we propose an efficient scheduling algorithm for data collection through multi-path routing structures in wireless sensor networks. The objective of our scheduling algorithm is to reduce both the message complexity and running time of the scheduling process as much as possible. In addition, we also develop a method for deriving a lower bound on the shortest possible length of the data collection schedule that can be generated by any algorithm. The lower bound latency estimation offers a practical method to evaluate the efficiency of data collection schedules produced by scheduling algorithms. Extensive experimental results show that the proposed scheduling algorithm significantly reduces the number of messages transmitted during the scheduling process and the running time compared to an existing scheduling algorithm. The length of the data collection schedule produced by our algorithm is normally within 1.9 times of the lower bound estimate across a wide range of network settings.
author2 School of Computer Engineering
author_facet School of Computer Engineering
Luu, Hai Van
Tang, Xueyan
format Article
author Luu, Hai Van
Tang, Xueyan
author_sort Luu, Hai Van
title An efficient algorithm for scheduling sensor data collection through multi-path routing structures
title_short An efficient algorithm for scheduling sensor data collection through multi-path routing structures
title_full An efficient algorithm for scheduling sensor data collection through multi-path routing structures
title_fullStr An efficient algorithm for scheduling sensor data collection through multi-path routing structures
title_full_unstemmed An efficient algorithm for scheduling sensor data collection through multi-path routing structures
title_sort efficient algorithm for scheduling sensor data collection through multi-path routing structures
publishDate 2013
url https://hdl.handle.net/10356/98685
http://hdl.handle.net/10220/17430
_version_ 1681056233103032320