Collaborative computing, leveraging resource on multiple wireless-connected devices, enables complex applications that a single device cannot support individually. However, the problem of assigning tasks over devices becomes challenging in the dynamic environments encountered in real-world settings, considering that the resource availability and channel conditions change over time in unpredictable ways due to mobility and other factors. In this paper, we formulate the task assignment problem as an online learning problem using an adversarial multi-armed bandit framework. We propose MABSTA, a novel algorithm that learns the performance of unknown devices and channel qualities continually through exploratory probing and makes task assignment decisions by exploiting the gained knowledge. The implementation of MABSTA, based on Gibbs Sampling approach, is computational-light and offers competitive performance in different scenarios on the trace-data obtained from a wireless IoT testbed. Furthermore, we prove that MABSTA is 1-competitive compared to the best offline assignment for any dynamic environment without stationarity assumptions, and demonstrate the polynomial-time algorithm for the exact implementation of the sampling process. To the best of our knowledge, MABSTA is the first online learning algorithm tailored to this class of problems.

With mobile devices increasingly able to connect to cloud servers from anywhere, resource-constrained devices can potentially perform offloading of computational tasks to either save local resource usage or improve performance. It is of interest to find optimal assignments of tasks to local and remote devices that can take into account the application-specific profile, availability of computational resources, and link connectivity, and find a balance between energy consumption costs of mobile devices and latency for delay-sensitive applications. We formulate an NP-hard problem to minimize the application latency while meeting prescribed resource utilization constraints. Different from most of existing works that either rely on the integer programming solver, or on heuristics that offer no theoretical performance guarantees, we propose Hermes, a novel fully polynomial time approximation scheme (FPTAS). We identify for a subset of problem instances, where the application task graphs can be described as serial trees, Hermes provides a solution with latency no more than (1 + ε) times of the minimum while incurring complexity that is polynomial in problem size and 1/ε. We further propose an online algorithm to learn the unknown dynamic environment and guarantee that the performance gap compared to the optimal strategy is bounded by a logarithmic function with time. Evaluation is done by using real data set collected from several benchmarks, and is shown that Hermes improves the latency by 16 percent compared to a previously published heuristic and increases CPU computing time by only 0.4 percent of overall latency.

With mobile devices increasingly able to connect to cloud servers from anywhere, resource-constrained devices can potentially perform offloading of computational tasks to either improve resource usage or improve performance. It is of interest to find optimal assignments of tasks to local and remote devices that can take into account the application-specific profile, availability of computational resources, and link connectivity, and find a balance between energy consumption costs of mobile devices and latency for delay-sensitive applications. Given an application described by a task dependency graph, we formulate an optimization problem to minimize the latency while meeting prescribed resource utilization constraints. Different from most of existing works that either rely on an integer linear programming formulation, which is NP-hard and not applicable to general task dependency graph for latency metrics, or on intuitively derived heuristics that offer no theoretical performance guarantees, we propose Hermes, a novel fully polynomial time problem approximation scheme (FPTAS) algorithm to solve this problem. Hermes pros vides a solution with latency no more than (1 + ε) times of the minimum while incurring complexity that is an polynomial in problem size and //ε We evaluate the performance by using real data set collected from several benchmarks, and show that Hermes improves the latency by 16% (36% for larger scale application) compared to a previously published heuristic and increases CPU computing time by only 0.4% of overall latency.

Computation Offloading, sending computational tasks to more resourceful servers, is becoming a widely-used approach to save limited resources on mobile devices like battery life, storage, processor, etc. Given an application that is partitioned into multiple tasks, the offloading decisions can be made on each of them. However, considering the delay constraint and the extra costs on data transmission and remote computation, it is not trivial to make optimized decisions. Existing works have formulated offloading decision problems as either graph-partitioning or binary integer programming problems. The first approach can solve the problem in polynomial time but is not applicable to delay constraints. The second approach relies on an integer programming solver without a polynomial time guarantee. We provide an algorithm, DTP (Deterministic delay constrained Task Partitioning), to solve the offloading decision problem with delay constraints. DTP gives near-optimal solution and runs in polynomial time in the number of tasks. Going beyond prior work on linear delay constraints that apply only to serial tasks, we generalize the delay constraints to settings where the dependency between tasks can be described by a tree. Furthermore, we provide another algorithm, PTP (Probabilistic delay constrained Task Partitioning), which gives stronger QoS guarantees. Simulation results show that our algorithms are accurate and robust, and scale well with the number of tasks.

We study two variations of the distributed storage allocation problem. The goal is to allocate a given storage budget in a distributed storage system for maximum reliability. It was recently discovered that this problem is related to an old conjecture in extremal combinatorics, on the maximum number of edges in a hypergraph subject to a constraint on its maximum matching number. The conjecture was recently verified in some regimes. In this paper we assume that the conjecture is true and establish new results for the optimal allocation for a variety of parameter values. We also derive new performance bounds that are independent of the conjecture, and compare them to the best previously known bounds.

In this paper, an accurate performance analysis is proposed for type-II hybrid ARQ scheme. As opposed to the existing type-II hybrid ARQ analysis work in the literature, the analysis proposed in this paper takes the dependency of the successive decoding attempts into account. The proposed analysis is applicable for type-II hybrid ARQ schemes with known weight spectrum of the error-correcting codes used. The channel models considered include AWGN and Rayleigh fading. Numerical experiments show that the proposed analysis is accurate in capturing the performance of type-II hybrid ARQ systems at mid-to-high SNR region.

Dynamic-susceptibility-contrast MR imaging is a widely used perfusion imaging technique that records signal changes on images caused by the passage of contrast-agent particles in the human brain after a bolus injection of contrast agent. The signal changes over time on different brain tissues represent distinct blood supply patterns and are crucial for studying cerebral hemodynamics. By assuming the spatial independence among these patterns, independent component analysis (ICA) was applied to classify different tissues, i.e., artery, gray matter, white matter, vein and sinus and choroid plexus, so that the spatio-temporal hemodynamics of these tissues were decomposed and analyzed. An arterial input function was modeled using the concentration-time curve of the arterial area for the deconvolution calculation of relative cerebral blood flow. The cerebral blood volume (CBV), relative cerebral blood flow (CBF), and relative mean transit time (MTT), were computed and their averaged ratios between gray matter and white matter were in good agreement with those in the literature.

Magnetic resonance images are reconstructed from digitized raw data, which are collected in the spatial-frequency domain (also called kappa-space). Occasionally, single or multiple data points in the k-space data are corrupted by spike noise, causing striation artifacts in images. Thresholding methods for detecting corrupted data points can fail because of small alterations, especially for data points in the low spatial frequency area where the k-space variation is large. Restoration of corrupted data points using interpolations of neighboring pixels can give incorrect results. We propose a Fourier transform method for detecting and restoring corrupted data points using a window filter derived from the striation-artifact structure in an image or an intermediate domain. The method provides an analytical solution for the alteration at each corrupted data point. It can effectively restore corrupted kappa-space data, removing striation artifacts in images, provided that the following three conditions are satisfied. First, a region of known signal distribution (for example, air background) is visible in either the image or the intermediate domain so that it can be selected using a window filter. Second, multiple spikes are separated by the full-width at half-maximum of the point spread function for the window filter. Third, the magnitude of a spike is larger than the minimum detectable value determined by the window filter and the standard deviation of kappa-space random noise.