With the increasing popularity of Cloud computing and Mobile computing, individuals, enterprises and research centers have started outsourcing their IT and computational needs to on-demand cloud services. Recently geographical load balancing techniques have been suggested for data centers hosting cloud computation in order to reduce energy cost by exploiting the electricity price differences across regions. However, these algorithms do not draw distinction among diverse requirements for responsiveness across various workloads. In this paper, we use the flexibility from the Service Level Agreements (SLAs) to differentiate among workloads under bounded latency requirements and propose a novel approach for cost savings for geographical load balancing. We investigate how much workload to be executed in each data center and how much workload to be delayed and migrated to other data centers for energy saving while meeting deadlines. We present an offline formulation for geographical load balancing problem with dynamic deferral and give online algorithms to determine the assignment of workload to the data centers and the migration of workload between data centers in order to adapt with dynamic electricity price changes. We compare our algorithms with the greedy approach and show that significant cost savings can be achieved by migration of workload and dynamic deferral with future electricity price prediction. We validate our algorithms on MapReduce traces and show that geographic load balancing with dynamic deferral can provide 20-30% cost-savings.

Localizability of network or node is an important subproblem in sensor localization. While rigidity theory plays an important role in identifying several localizability conditions, major limitations are that the results are only applicable to generic frameworks and that the distance measurements need to be error-free. These limitations, in addition to the hardness of finding the node locations for a uniquely localizable graph, miss large portions of practical application scenarios that require sensor localization. In this paper, we describe a novel SDP-based formulation for analyzing node localizability and providing a deterministic upper bound of localization error. Unlike other optimization-based formulations for solving localization problem for the whole network, our formulation allows fine-grained evaluation on the localization accuracy per each node. Our formulation gives a sufficient condition for unique node localizability for any frameworks, i.e., not only for generic frameworks. Furthermore, we extend it for the case with measurement errors and for computing directional error bounds. We also design an iterative algorithm for large-scale networks and demonstrate the effectiveness by simulation experiments.

We study the problem of planning the motion of “data mules” for collecting the data from stationary sensor nodes in wireless sensor networks. Use of data mules significantly reduces energy consumption at sensor nodes compared to commonly used multihop forwarding approaches, but has a drawback in that it increases the latency of data delivery. Optimizing the motion of data mules, including path and speed, is critical for improving the data delivery latency and making the data mule approach more useful in practice. In this article, we focus on the path selection problem: finding the optimal path of data mules so that the data delivery latency can be minimized. We formulate the path selection problem as a graph problem that is capable of expressing the benefit from larger communication range. The problem is NP-hard and we present approximation algorithms for both single-data mule case and multiple-data mules case. We further consider the case in which we have only partial knowledge of communication range, where we design semionline algorithms that improve the offline plan using online knowledge at runtime. Simulation experiments on Matlab and ns2 demonstrate that our offline and semionline algorithms produce significantly shorter path lengths and data delivery latency compared to previously proposed methods, suggesting that controlled mobility can be exploited much more effectively.

A data mule represents a mobile device that collects data in a sensor field by physically visiting the nodes in a sensor network. The data mule collects data when it is in the proximity of a sensor node. This can be an alternative to multihop forwarding of data when we can utilize node mobility in a sensor network. To be useful, a data mule approach needs to minimize data delivery latency. In this paper, we first formulate the problem of minimizing the latency in the data mule approach. The data mule scheduling (DMS) problem is a scheduling problem that has both location and time constraints. Then, for the 1D case of the DMS problem, we design an efficient heuristic algorithm that incorporates constraints on the data mule motion dynamics. We provide lower bounds of solutions to evaluate the quality of heuristic solutions. Through numerical experiments, we show that the heuristic algorithm runs fast and yields good solutions that are within 10 percent of the optimal solutions.

Unlike traditional multihop forwarding among stationary sensor nodes, use of mobile devices for data collection in wireless sensor networks has recently been gathering more attention. The use of mobility significantly reduces the energy consumption at sensor nodes, elongating the functional lifetime of the network. However, a drawback is an increased data delivery latency. Reducing the latency through optimizing the motion of data mules is critical for this approach to thrive. In this article, we focus on the problem of motion planning, specifically, determination of the speed of the data mule and the scheduling of the communication tasks with the sensors. We consider three models of mobility capability of the data mule to accommodate different types of vehicles. Under each mobility model, we design optimal and heuristic algorithms for different problems: single data mule case, single data mule with periodic data generation case, and multiple data mules case. We compare the performance of the heuristic algorithm with a naive algorithm and also with the multihop forwarding approach by numerical experiments. We also compare one of the optimal algorithms with a previously proposed method to see how our algorithm improves the performance and is also useful in practice. As far as we know, this study is the first of a kind that provides a systematic understanding of the motion planning problem of data mules.

We consider the problem of planning path and speed of a "data mule" in a sensor network. This problem is encountered in various situations, such as modeling the motion of a data-collecting UAV (unmanned aerial vehicle) in a field of sensors for structural health monitoring. Our specific context here is use of a data mule as an alternative or supplement to multihop forwarding in a sensor network. While a data mule can reduce the energy consumption at each sensor node, it increases the latency from the time the data is generated at a node to the time the base station receives it. In this paper, we introduce the "data mule scheduling" or DMS framework that enables data mule motion planning to minimize the data delivery latency. The DMS framework is general; it can express many previously proposed problem formulations and problem settings related to data mules. We design algorithms for DMS and extend to the more general case of combined data mule and multihop forwarding to enable a flexible trade-off between energy consumption and data delivery latency. Using DMS, we can calculate the optimal way for node-to-node forwarding and data mule motion plan. Our implementation and simulation results using ns2 show nearly monotonic decrease of data delivery latency when each node can use more energy, thus vastly increasing the flexibility in the energy-latency trade-off for sensor network communications.

Sensor networks have a significant potential in diverse applications some of which are already beginning to be deployed in areas such as environmental monitoring. As the application logic becomes more complex, programming difficulties are becoming a barrier to adoption of these networks. The difficulty in programming sensor networks is not only due to their inherently distributed nature but also the need for mechanisms to address their harsh operating conditions such as unreliable communications, faulty nodes, and extremely constrained resources. Researchers have proposed different programming models to overcome these difficulties with the ultimate goal of making programming easy while making full use of available resources. In this article, we first explore the requirements for programming models for sensor networks. Then we present a taxonomy of the programming models, classified according to the level of abstractions they provide. We present an evaluation of various programming models for their responsiveness to the requirements. Our results point to promising efforts in the area and a discussion of the future directions of research in this area.

No abstract available.