Algorithms for communication scheduling in data gathering network with data compression
Full Text: Luo2018_Article_AlgorithmsForCommunicationSche.pdf
We consider a communication scheduling problem that arises within wireless sensor networks, where data is accumulated by the sensors and transferred directly to a central base station. One may choose to compress the data collected by a sensor, to decrease the data size for transmission, but the cost of compression must be considered. The goal is to designate a subset of sensors to compress their collected data, and then to determine a data transmission order for all the sensors, such that the total compression cost is minimized subject to a bounded data transmission completion time (a.k.a. makespan). A recent result confirms the NP-hardness for this problem, even in the special case where data compression is free. Here we first design a pseudo-polynomial time exact algorithm, articulated within a dynamic programming scheme. This algorithm also solves a variant with the complementary optimization goalโto minimize the makespan while constraining the total compression cost within a given budget. Our second result consists of a bi-factor (1+๐,2) -approximation for the problem, where (1+๐) refers to the compression cost and 2 refers to the makespan, and a 2-approximation for the variant. Lastly, we apply a sparsing technique to the dynamic programming exact algorithm, to achieve a dual fully polynomial time approximation scheme for the problem and a usual fully polynomial time approximation scheme for the variant.
Citation
W. Luo, Y. Xu, B. Gu, W. Tong, R. Goebel, G. Lin. "Algorithms for communication scheduling in data gathering network with data compression". Algorithmica, 80(11), pp 3158-3176, November 2018.| Keywords: | Wireless sensor network, Data compression Scheduling, Approximation algorithm, FPTAS, Dual FPTAS |
| Category: | In Journal |
| Web Links: | DOI |
| Springer |
BibTeX
@article{Luo+al:18,
author = {Wenchang Luo and Yao Xu and Boyuan Gu and Weitian Tong and Randy
Goebel and Guohui Lin},
title = {Algorithms for communication scheduling in data gathering network
with data compression},
Volume = "80",
Number = "11",
Pages = {3158-3176},
journal = {Algorithmica},
year = 2018,
}Last Updated: February 13, 2020Submitted by Sabina P
