Solving Capacitated Data Storage Placement Problems in Sensor Networks

Data storage is an important issue in sensor networks as the large amount of data collected by the sensors in such networks needs to be archived for future processing. In this thesis we consider sensor networks in which the information produced by the sensors needs to be collected by storage nodes where the information is compressed and then sent to a central storage node called the sink. We study the problem of selecting k sensors to be used as storage nodes so as to minimize the total cost of sending information from the sensors to the storage nodes and from the storage nodes to the sink. We formulate this problem as a version of the capacitated k-median problem and design an approximation algorithm for it . We assume that each storage node has limited capacity so it can collect information from only a restricted number of sensors. Our algorithm is based on an algorithm by Guha for the capacitated k-median problem. We also study the version of the problem where a storage node has unlimited capacity, so it can collect information from any number of sensors. We show that a local search algorithm by Arya et al. can be used for this problem and it produces a solution of cost at most 5 times the cost of an optimum solution