Approximation Bounds for the Minimum \(k\) -Storage Problem
Sensor networks are widely used to collect data that are required for future information retrieval. Data might be aggregated in a predefined number \(k\) of special nodes in the network, called storage nodes, which, for replying to external queries, compr
- PDF / 436,482 Bytes
- 16 Pages / 439.37 x 666.142 pts Page_size
- 35 Downloads / 194 Views
Abstract. Sensor networks are widely used to collect data that are required for future information retrieval. Data might be aggregated in a predefined number k of special nodes in the network, called storage nodes, which, for replying to external queries, compress the last received raw data and send them towards the sink. We consider the problem of locating such storage nodes in order to minimize the energy consumed for converging the raw data to the storage nodes as well as to converge the aggregated data to the sink. This is known as the minimum k-storage problem. We first prove that it is NP -hard to be approximated within a factor of 1+ 1e . We then propose a local search algorithm which guarantees a constant approximation factor. We conducted extended experiments to show that the algorithm performs very well in many different scenarios. Further, we prove that the problem is not in APX if we consider directed links, unless P = NP .
1
Introduction
Networks of sensor nodes are usually employed to monitor large areas, collecting data with regular frequency. This large volume of data has to be stored somewhere for answering to external user queries [8]. Source nodes, which are responsible for collecting data, can either locally store the data or transmit them to the sink, a powerful node connected to the external world. If data are locally stored, several problems may arise: (i) data cannot be accumulated for long periods because nodes are equipped with only limited memory space; (ii) stored data are lost once the energy of a source node – battery operated – is depleted; and (iii) searching data for serving query demand results in network-wide communications. Alternatively, source nodes can forward the collected data to the Research partially supported by the Research Grant 2010N5K7EB ‘PRIN 2010’ ARS TechnoMedia (Algoritmica per le Reti Sociali Tecno-mediate), from the Italian Ministry of University and Research, and by “Fondazione Cassa di Risparmio della Provincia dell’Aquila” within project ARISE. P. Flocchini et al. (Eds.): ALGOSENSORS 2013, LNCS 8243, pp. 123–138, 2014. c Springer-Verlag Berlin Heidelberg 2014 DOI: 10.1007/978-3-642-45346-5 10,
124
G. D’Angelo et al.
sink. However, communicating data from the source nodes up to the sink makes the network congested, especially if data are transmitted raw, that is, uncompressed. In general, source nodes may forward their raw data to some midway nodes, referred to as storage nodes. Here, raw data are stored and aggregated, i.e., reduced in size, to be transmitted to the sink at the time a query demand from external users is submitted. Such midway nodes must have extra permanent storage, more power battery and more computational capabilities. With this two-tier model, if the number of storage nodes is kept limited, the network becomes less congested at the price of a moderate increase of the network cost. This scheme has been pursued in [16,17] where the problem of selecting a subset of storage nodes so as the overall communication cost is minimized is called
Data Loading...
