Approximation Algorithms for Capacitated Minimum Forest Problems in Wireless Sensor Networks with a Mobile Sink

To deploy a wireless sensor network for the purpose of large-scale monitoring, in this paper, we propose a heterogeneous and hierarchical wireless sensor network architecture. The architecture consists of sensor nodes, gateway nodes, and mobile sinks. The sensors transmit their sensing data to the g...

Full description

Saved in:
Bibliographic Details
Published in:IEEE transactions on computers 2013-10, Vol.62 (10), p.1932-1944
Main Authors: Weifa Liang, Schweitzer, P., Zichuan Xu
Format: Article
Language:English
Subjects:
Approximation algorithms
Approximation methods
capacitated minimum forest problem
constrained optimization problem
data gathering
Logic gates
Mobile communication
Mobile computing
sink mobility
Vegetation
Wireless sensor networks
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:To deploy a wireless sensor network for the purpose of large-scale monitoring, in this paper, we propose a heterogeneous and hierarchical wireless sensor network architecture. The architecture consists of sensor nodes, gateway nodes, and mobile sinks. The sensors transmit their sensing data to the gateway nodes for temporary storage through multihop relays, while the mobile sinks travel along predetermined trajectories to collect data from nearby gateway nodes. Under this paradigm of data gathering, we formulate a novel constrained optimization problem, namely, the capacitated minimum forest (CMF) problem, for the decision version of which we first show NP-completeness. We then devise approximation algorithms and provide upper bounds for their approximation ratios. We finally evaluate the performance of the proposed algorithms through experimental simulation. In our experiments, the approximation ratio delivered by the proposed algorithms is always less than 2. In the case of arbitrary gateway capacities, this contrasts our theoretical results which show that the approximation ratio is at most linear in the number of gateways. Our experiments thus indicate that for realistic inputs, our worst case analysis of the approximation ratio is very conservative. The proposed algorithms are the first approximation algorithms for the CMF problem, and our techniques may be applicable to other constrained optimization problems beyond wireless sensor networks.
ISSN:0018-9340
1557-9956
DOI:10.1109/TC.2012.124