Communication scheduling in data gathering networks of heterogeneous sensors with data compression: Algorithms and empirical experiments

Wenchang Luo, Boyuan Gu and Guohui Lin

European Journal of Operational Research, 2018, vol. 271, issue 2, 462-473

Abstract: We consider a communication scheduling problem to address data compression and data communication together, arising from the data gathering wireless sensor networks with data compression. In the problem, the deployed sensors are heterogeneous, in that the data compression ratios, in terms of size reduction, the compression time, and the compression costs, in terms of energy consumption, on different sensors are different. The bi-objective is to minimize the total compression cost and to minimize the total time to transfer all the data to the base station. The problem reduces to two mono-objective optimization problems in two separate ways: in the original problem a time bound is given and the mono-objective is to minimize the total compression cost, and in the complementary problem a global compression budget is given and the mono-objective is to minimize the makespan. We present a unified exact algorithm for both of them based on dynamic programming; this exact algorithm is then developed into a fully polynomial time approximation scheme for the complementary problem, and a dual fully polynomial time approximation scheme for the original problem. All these approximation algorithms have been implemented and extensive computational experiments show that they run fast and return the optimal solutions almost all the time.

Keywords: Scheduling; Wireless sensor network; Data compression; Algorithm; Performance analysis (search for similar items in EconPapers)
Date: 2018
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (3)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221718304582
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:ejores:v:271:y:2018:i:2:p:462-473

DOI: 10.1016/j.ejor.2018.05.047

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().