1,355 research outputs found
Optimal Skewed Allocation on Multiple Channels for Broadcast in Smart Cities
No full textWe 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
Online Knapsack of Unknown Capacity: Energy Optimization for Smartphone Communications
No full textWe propose a new variant of the more standard online knapsack problem where the only information missing to the provided instances is the capacity B of the knapsack. We refer to this problem as the online Knapsack of Unknown Capacity problem. Any algorithm must provide a strategy for ordering the items that are inserted in the knapsack in an online fashion, until the actual capacity of the knapsack is revealed and the last inserted item might not fit in. Apart from the interest in a new version of the fundamental knapsack problem, the motivations that lead to define this new variant come from energy consumption constraints in smartphone communications. We do provide lower and upper bounds to the problem for various cases. In general, we design an optimal algorithm admitting a 1/2 -competitive ratio. When all items admit uniform ratio of profit over size, our algorithm provides a 49/86 =.569... competitive ratio that leaves some gap with the provided bound of 1/φ =.618... , the inverse of the golden number. We then conduct experimental analysis for the competitive ratio guaranteed algorithms compared to the optimum and to various heuristics
Optimal Solutions for Pairing Services on Smartphones: a Strategy to Minimize Energy Consumption
No full textEnergy consumption is one of the main concerns that refrain users from fully exploiting their smartphone capabilities.
Guided by energy measurements on smartphones, which show that some services performed in parallel require less energy than their
stand-alone executions, we investigate the possibility to delay some services to the time when other services have
already been scheduled in such a way the total energy consumption is minimized once all services are accomplished.
We define two new energy optimization problems, called {\em Single Overlapping Pair (SOP)} and {\em Multiple Overlapping Pairs (MOP)}.
The former assumes that a delay-tolerant service must be paired with a single pre-scheduled service,
the latter that a delay-tolerant service may be paired with multiple pre-scheduled services.
We propose new algorithms to solve both SOP and MOP optimally in polynomial time, when the set of services to be executed is known in advance.
Finally, we evaluate the benefits of the energy-efficient pairing strategy via simulations on synthetic traces.
The results of our preliminary experiments show a neat energy gain achievable by pairing executions, if compared to stand-alone executions.
Indeed, the solution for SOP shows a 30\% decrease in energy consumption, while the one for MOP shows a 70\% decrease in energy demanding
The Minimum κ-Storage Problem: Complexity, Approximation, and Experimental Analysis
No full textIn 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
The minimum k-storage problem on directed graphs
No full textIn standard sensor network applications, sensors generate raw data that have to be sent to a sink node. In order to save energy, special intermediate storage nodes can be exploited in order to compress data before forwarding them to the sink. We consider the problem of locating k storage nodes in order to minimize the energy consumed for converging data to the sink. This is known as the minimum k-storage problem. We show that in directed graphs (and in particular in Directed Acyclic Graphs) the problem does not admit an algorithm with a constant approximation ratio, unless P=NP. If the topology is restricted to trees where the arcs are directed towards the sink (typical scenario in sensor networks), the problem is solvable in polynomial time. We give a dynamic programming algorithm that requires O(min{kn^2,k^2P}) time, where n and P are the number of nodes and the path length of the tree, respectively. We improve over a previous algorithm which requires O(kn^2(max{k,d})^(d−1)) time, where d is the maximum out-degree of the tree
Storage Placement in Path Networks
No full textNew 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
Approximation Bounds for the Minimum k-Storage Problem
No full textSensor 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+1/e . 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
Optimal Solutions for Pairing Services on Smartphones: a Strategy to Minimize Energy Consumption
No full text
- …
