We consider the problem of allocating N uniform data to K transmission channels so as the average Expected Delay (AED) is minimized. This problem arises in designing efficient data-diffusion broadcast algorithms in a smart environment. We show that the basic dynamic rogramming algorithm for solving the uniform pallocation problem can be speedup up to O(NK) time by applying an optimal algorithm to find the row-minima of totally monotone matrices. Such a new algorithm is always faster than the best previously known algorithm for the uniform allocation problem that runs in O(NKlogN). Moreover, it is computationally optimal for the uniform allocation of up to N data and K channels. We then reduce the largest allocation problem, i.e., the subproblem with exactly N data and K channels, to the problem of finding a minimum weight K-link path in a particular directed acyclic graph. We also present two heuristics and we show by extended simulations their effectiveness in practical scenarios. Both the K-link path algorithm and the heuristics are much faster than O(NK). We then compare the behaviours of our algorithms on the online version of the allocation problem in which new single items are inserted for broadcast.

In a sensor network, data might be stored in so-called storage nodes, which receive raw data from other nodes, compress them, and send them toward a sink. We consider the problem of locating k storage nodes in order to minimize the energy consumed for converging the raw data to the storage nodes as well as to converge the compressed data to the sink. This is known as the minimum k-storage problem. In general, the problem is NP-hard. However, we are able to devise a polynomial-time algorithm that optimally solves the problem in bounded-tree width graphs. We then characterize the minimum k-storage problem from the approximation viewpoint. We first prove that it is NP-hard to be approximated within a factor smaller than 1 + 1/e. We then propose a local search algorithm that guarantees a constant approximation factor. We conducted extended experiments to show that the algorithm performs very well, exhibiting very small deviation from the optimum and computational time. It is worth to note that our problem is a generalization to the well-known metric k-median problem and then the obtained results also hold for this case.

New algorithms are presented to optimally place storage nodes in a sensor network consisting of a path so as to minimize the communication cost of convergecasting towards the sink the data gathered into storage nodes in reply to queries. Such algorithms are faster than previously known algorithms and require optimal running time for finding the optimal storage placement.

Recent energy measurements on smartphones have shown that parallel communications (e.g., data transfer and voice call) require less energy than their stand-alone execution. Guided by these results, we investigate the possibility of scheduling communications in pairs for minimizing the energy consumption. We define two energy optimization problems to postpone delay-tolerant services and perform them in parallel with real-time services in order to save energy. The first problem, called single delay-tolerant assignment (SDA), allows at most one delay-tolerant service to be paired with each real-time service, whereas the second problem, called multiple delay-tolerant assignment (MDA), allows multiple delay-tolerant services to be paired (in different times) with the same real-time service. For the SDA problem, we propose an optimal algorithm. For the MDA problem, which is computationally intractable, we give an approximation algorithm. We evaluate the benefits of the energy-efficient pairing strategy via simulations on synthetic traces. The MDA algorithm can save up to the 60 percent of the energy consumption using 4G network assuming an intensive smartphone usage, while the SDA algorithm saves up to the 20 percent.