BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

Minghua Chen

Minghua Chen appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
math.NAInformation Theorymath.ITNetworking and Internet ArchitectureNumerical AnalysisSystems and Controleess.SYPerformanceMachine LearningData Structures and Algorithmseess.SPmath.OCphysics.opticsApplicationsComputational ComplexityComputer Science and Game TheoryComputer VisionDatabasesDistributed, Parallel, and Cluster ComputingOther Computer Sciencephysics.comp-ph

Catalog footprint

What is connected

52works
21topics
4close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

52 published item(s)

preprint2026arXiv

Implicit and implicit--explicit high-order BDF methods for coupled elliptic--parabolic systems

First-order fully implicit as well as implicit--explicit schemes for coupled elliptic-parabolic systems are discussed in [Ern and Meunier, ESAIM: M2AN, 2009] and [Altmann et al., Math.\ Comp., 2021], respectively. The extension of the analysis to higher-order (third-, fourth-, fifth-, and sixth-order) schemes is not straightforward since explicitly constructing $G$ matrices (G-stability) is often tricky. In this article, we develop fully implicit as well as implicit--explicit backward difference formula (BDF) schemes of order up to six. The implicit--explicit variants are decoupled, thereby enhancing computational efficiency; their convergence analysis requires a weak coupling condition on the poroelastic parameters. In contrast, no coupling conditions are needed for the fully implicit, coupled schemes. We determine novel and suitable multipliers for the two proposed classes and establish error estimates via the energy technique. A prominent advantage of these higher-order schemes is that, with almost the computational cost of first-order schemes, they greatly improve the accuracy.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Competitive Online Optimization with Multiple Inventories: A Divide-and-Conquer Approach

We study a competitive online optimization problem with multiple inventories. In the problem, an online decision maker seeks to optimize the allocation of multiple capacity-limited inventories over a slotted horizon, while the allocation constraints and revenue function come online at each slot. The problem is challenging as we need to allocate limited inventories under adversarial revenue functions and allocation constraints, while our decisions are coupled among multiple inventories and different slots. We propose a divide-and-conquer approach that allows us to decompose the problem into several single inventory problems and solve it in a two-step manner with almost no optimality loss in terms of competitive ratio (CR). Our approach provides new angles, insights and results to the problem, which differs from the widely-adopted primal-and-dual framework. Specifically, when the gradients of the revenue functions are bounded in a positive range, we show that our approach can achieve a tight CR that is optimal when the number of inventories is small, which is better than all existing ones. For an arbitrary number of inventories, the CR we achieve is within an additive constant of one to a lower bound of the best possible CR among all online algorithms for the problem. We further characterize a general condition for generalizing our approach to different applications. For example, for a generalized one-way trading problem with price elasticity, where no previous results are available, our approach obtains an online algorithm that achieves the optimal CR up to a constant factor.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

DeepOPF-AL: Augmented Learning for Solving AC-OPF Problems with Multiple Load-Solution Mappings

The existence of multiple load-solution mappings of non-convex AC-OPF problems poses a fundamental challenge to deep neural network (DNN) schemes. As the training dataset may contain a mixture of data points corresponding to different load-solution mappings, the DNN can fail to learn a legitimate mapping and generate inferior solutions. We propose DeepOPF-AL as an augmented-learning approach to tackle this issue. The idea is to train a DNN to learn a unique mapping from an augmented input, i.e., (load, initial point), to the solution generated by an iterative OPF solver with the load and initial point as intake. We then apply the learned augmented mapping to solve AC-OPF problems much faster than conventional solvers. Simulation results over IEEE test cases show that DeepOPF-AL achieves noticeably better optimality and similar feasibility and speedup performance, as compared to a recent DNN scheme, with the same DNN size yet elevated training complexity.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

DeepOPF: A Feasibility-Optimized Deep Neural Network Approach for AC Optimal Power Flow Problems

High percentage penetrations of renewable energy generations introduce significant uncertainty into power systems. It requires grid operators to solve alternative current optimal power flow (AC-OPF) problems more frequently for economical and reliable operation in both transmission and distribution grids. In this paper, we develop a Deep Neural Network (DNN) approach, called DeepOPF, for solving AC-OPF problems in a fraction of the time used by conventional solvers. A key difficulty for applying machine learning techniques for solving AC-OPF problems lies in ensuring that the obtained solutions respect the equality and inequality physical and operational constraints. Generalized the 2-stage procedure in [1], [2], DeepOPF first trains a DNN model to predict a set of independent operating variables and then directly compute the remaining dependable ones by solving power flow equations. Such an approach not only preserves the power-flow balance equality constraints but also reduces the number of variables to predict by the DNN, cutting down the number of neurons and training data needed. DeepOPF then employs a penalty approach with a zero-order gradient estimation technique in the training process to preserve the remaining inequality constraints. As another contribution, we drive a condition for tuning the size of the DNN according to the desired approximation accuracy, which measures the DNN generalization capability. It provides theoretical justification for using DNN to solve the AC-OPF problem. Simulation results of IEEE 30/118/300-bus and a synthetic 2000-bus test cases show that DeepOPF speeds up the computing time by up to two orders of magnitude as compared to a state-of-the-art solver, at the expense of $<$0.1% cost difference.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Fast algebraic multigrid for block-structured dense and Toeplitz-like-plus-Cross systems arising from nonlocal diffusion problems

Algebraic multigrid (AMG) is one of the most efficient iterative methods for solving large sparse system of equations. However, how to build/check restriction and prolongation operators in practical of AMG methods for nonsymmetric {\em sparse} systems is still an interesting open question [Brezina, Manteuffel, McCormick, Runge, and Sanders, SIAM J. Sci. Comput. (2010); Manteuffel and Southworth, SIAM J. Sci. Comput. (2019)]. This paper deals with the block-structured dense and Toeplitz-like-plus-Cross systems, including {\em nonsymmetric} indefinite, symmetric positive definite (SPD), arising from nonlocal diffusion problem and peridynamic problem. The simple (traditional) restriction operator and prolongation operator are employed in order to handle such block-structured dense and Toeplitz-like-plus-Cross systems, which is convenient and efficient when employing a fast AMG. We focus our efforts on providing the detailed proof of the convergence of the two-grid method for such SPD situations. The numerical experiments are performed in order to verify the convergence with a computational cost of only $\mathcal{O}(N \mbox{log} N)$ arithmetic operations, by using few fast Fourier transforms, where $N$ is the number of the grid points. To the best of our knowledge, this is the first contribution regarding Toeplitz-like-plus-Cross linear systems solved by means of a fast AMG.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Learning-based AC-OPF Solvers on Realistic Network and Realistic Loads

Deep learning approaches for the Alternating Current-Optimal Power Flow (AC-OPF) problem are under active research in recent years. A common shortcoming in this area of research is the lack of a dataset that includes both a realistic power network topology and the corresponding realistic loads. To address this issue, we construct an AC-OPF formulation-ready dataset called TAS-97 that contains realistic network information and realistic bus loads from Tasmania's electricity network. We found that the realistic loads in Tasmania are correlated between buses and they show signs of an underlying multivariate normal distribution. Feasibility-optimized end-to-end deep neural network models are trained and tested on the constructed dataset. Trained on samples with bus loads generated from a fitted multivariate normal distribution, our learning-based AC-OPF solver achieves 0.13% cost optimality gap, 99.73% feasibility rate, and 38.62 times of speedup on realistic testing samples when compared to PYPOWER.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Modified BDF2 schemes for subdiffusion models with a singular source term

The aim of this paper is to study the time stepping scheme for approximately solving the subdiffusion equation with a weakly singular source term. In this case, many popular time stepping schemes, including the correction of high-order BDF methods, may lose their high-order accuracy. To fill in this gap, in this paper, we develop a novel time stepping scheme, where the source term is regularized by using a $k$-fold integral-derivative and the equation is discretized by using a modified BDF2 convolution quadrature. We prove that the proposed time stepping scheme is second-order, even if the source term is nonsmooth in time and incompatible with the initial data. Numerical results are presented to support the theoretical results.

0 citations0 reviewsNo code linkedOpen access
preprint2021arXiv

Principle-driven Fiber Transmission Model based on PINN Neural Network

In this paper, a novel principle-driven fiber transmission model based on physical induced neural network (PINN) is proposed. Unlike data-driven models which regard fiber transmission problem as data regression tasks, this model views it as an equation solving problem. Instead of adopting input signals and output signals which are calculated by SSFM algorithm in advance before training, this principle-driven PINN based fiber model adopts frames of time and distance as its inputs and the corresponding real and imaginary parts of NLSE solutions as its outputs. By taking into account of pulses and signals before transmission as initial conditions and fiber physical principles as NLSE in the design of loss functions, this model will progressively learn the transmission rules. Therefore, it can be effectively trained without the data labels, referred as the pre-calculated signals after transmission in data-driven models. Due to this advantage, SSFM algorithm is no longer needed before the training of principle-driven fiber model which can save considerable time consumption. Through numerical demonstration, the results show that this principle-driven PINN based fiber model can handle the prediction tasks of pulse evolution, signal transmission and fiber birefringence for different transmission parameters of fiber telecommunications.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

DeepOPF: A Deep Neural Network Approach for Security-Constrained DC Optimal Power Flow

We develop DeepOPF as a Deep Neural Network (DNN) approach for solving security-constrained direct current optimal power flow (SC-DCOPF) problems, which are critical for reliable and cost-effective power system operation.DeepOPF is inspired by the observation that solving SC-DCOPF problems for a given power network is equivalent to depicting a high-dimensional mapping from the load inputs to the generation and phase angle outputs. We first train a DNN to learn the mapping and predict the generations from the load inputs. We then directly reconstruct the phase angles from the generations and loads by using the power flow equations. Such a predict-and-reconstruct approach reduces the dimension of the mapping to learn, subsequently cutting down the size of the DNN and the amount of training data needed. We further derive a condition for tuning the size of the DNN according to the desired approximation accuracy of the load-generation mapping. We develop a post-processing procedure based on $\ell_1$-projection to ensure the feasibility of the obtained solution, which can be of independent interest. Simulation results for IEEE test cases show that DeepOPF generates feasible solutions with less than 0.2% optimality loss, while speeding up the computation time by up to two orders of magnitude as compared to a state-of-the-art solver.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

DeepOPF+: A Deep Neural Network Approach for DC Optimal Power Flow for Ensuring Feasibility

Deep Neural Networks (DNNs) approaches for the Optimal Power Flow (OPF) problem received considerable attention recently. A key challenge of these approaches lies in ensuring the feasibility of the predicted solutions to physical system constraints. Due to the inherent approximation errors, the solutions predicted by DNNs may violate the operating constraints, e.g., the transmission line capacities, limiting their applicability in practice. To address this challenge, we develop DeepOPF+ as a DNN approach based on the so-called "preventive" framework. Specifically, we calibrate the generation and transmission line limits used in the DNN training, thereby anticipating approximation errors and ensuring that the resulting predicted solutions remain feasible. We theoretically characterize the calibration magnitude necessary for ensuring universal feasibility. Our DeepOPF+ approach improves over existing DNN-based schemes in that it ensures feasibility and achieves a consistent speed up performance in both light-load and heavy-load regimes. Detailed simulation results on a range of test instances show that the proposed DeepOPF+ generates 100% feasible solutions with minor optimality loss. Meanwhile, it achieves a computational speedup of two orders of magnitude compared to state-of-the-art solvers.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Fast and High-order Accuracy Numerical Methods for Time-Dependent Nonlocal Problems in $\mathbb{R}^2

In this paper, we study the Crank-Nicolson method for temporal dimension and the piecewise quadratic polynomial collocation method for spatial dimensions of time-dependent nonlocal problems. The new theoretical results of such discretization are that the proposed numerical method is unconditionally stable and its global truncation error is of $\mathcal{O}\left(τ^2+h^{4-γ}\right)$ with $0<γ<1$, where $τ$ and $h$ are the discretization sizes in the temporal and spatial dimensions respectively. Also we develop the conjugate gradient squared method to solving the resulting discretized nonsymmetric and indefinite systems arising from time-dependent nonlocal problems including two-dimensional cases. By using additive and multiplicative Cauchy kernels in non-local problems, structured coefficient matrix-vector multiplication can be performed efficiently in the conjugate gradient squared iteration. Numerical examples are given to illustrate our theoretical results and demonstrate that the computational cost of the proposed method is of $O(M \log M)$ operations where $M$ is the number of collocation points.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Finite difference/spectral approximations for the two-dimensional time Caputo-Fabrizio fractional diffusion equation

The main contribution of this work is to construct and analyze stable and high order schemes to efficiently solve the two-dimensional time Caputo-Fabrizio fractional diffusion equation. Based on a third-order finite difference method in time and spectral methods in space, the proposed scheme is unconditionally stable and has the global truncation error $\mathcal{O}(τ^3+N^{-m})$, where $τ$, $N$ and $m$ are the time step size, polynomial degree and regularity in the space variable of the exact solution, respectively. It should be noted that the global truncation error $\mathcal{O}(τ^2+N^{-m})$ is well established in [ Li, Lv and Xu, {\em Numer. Methods Partial Differ. Equ}. (2019)]. Finally, some numerical experiments are carried out to verify the theoretical analysis. To the best of our knowledge, this is the first proof for the stability of the third-order scheme for the Caputo-Fabrizio fractional operator.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Fourier temporal ghost imaging

Ghost imaging is a fascinating framework which constructs the image of an object by correlating measurements between received beams and reference beams, none of which carries the structure information of the object independently. Recently, by taking into account space-time duality in optics, computational temporal ghost imaging has attracted attentions. Here, we propose a novel Fourier temporal ghost imaging (FTGI) scheme to achieve single-shot non-reproducible temporal signals. By sinusoidal coded modulation, ghost images are obtained and recovered by applying Fourier transformation. For demonstration, non-repeating events are detected with single-shot exposure architecture. It's shown in results that the peak signal-to-noise ratio (PSNR) of FTGI is significantly better (13dB increase) than traditional temporal ghost imaging in the same condition. In addition, by using the obvious physical meaning of Fourier spectrum, we show some potential applications of FTGI, such as frequency division multiplexing demodulation in the visible light communications.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

High order algorithms for Fokker-Planck equation with Caputo-Fabrizio fractional derivative

Based on the continuous time random walk, we derive the Fokker-Planck equations with Caputo-Fabrizio fractional derivative, which can effectively model a variety of physical phenomena, especially, the material heterogeneities and structures with different scales. Extending the discretizations for fractional substantial calculus [Chen and Deng, \emph{ ESAIM: M2AN.} \textbf{49}, (2015), 373--394], we first provide the numerical discretizations of the Caputo-Fabrizio fractional derivative with the global truncation error $\mathcal{O}(τ^ν)$ $ (ν=1,2,3,4)$. Then we use the derived schemes to solve the Caputo-Fabrizio fractional diffusion equation. By analysing the positive definiteness of the stiffness matrices of the discretized Caputo-Fabrizio operator, the unconditional stability and the convergence with the global truncation error $\mathcal{O}(τ^2+h^2)$ are theoretically proved and numerical verified.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

The energy technique for the six-step BDF method

In combination with the Grenander--Szegö theorem, we observe that a relaxed positivity condition on multipliers, milder than the basic %fundamental requirement of the Nevanlinna--Odeh multipliers that the sum of the absolute values of their components is strictly less than $1$, makes the energy technique applicable to the stability analysis of BDF methods for parabolic equations with selfadjoint elliptic part. This is particularly useful for the six-step BDF method for which no Nevanlinna--Odeh multiplier exists. We introduce multipliers satisfying the positivity property for the six-step BDF method and establish stability of the method for parabolic equations.

0 citations0 reviewsNo code linkedOpen access
preprint2019arXiv

A second-order accurate scheme for two-dimensional space fractional diffusion equations with time Caputo-Fabrizio fractional derivative

We provide and analyze a second order scheme for the model describing the functional distributions of particles performing anomalous motion with exponential Debye pattern and no-time-taking jumps eliminated, and power-law jump length. The model is derived in [M. Chen, J. Shi, W. Deng, arXiv:1809.03263], being called the space fractional diffusion equation with the time Caputo-Fabrizio fractional derivative. The designed schemes are unconditionally stable and have the second order global truncation error with the nonzero initial condition, being theoretically proved and numerically verified by two methods (a prior estimate with $L^2$-norm and mathematical induction with $l_\infty$ norm). Moreover, the optimal estimates are obtained.

0 citations0 reviewsNo code linkedOpen access
preprint2019arXiv

A sharp error estimate of piecewise polynomial collocation for nonlocal problems with weakly singular kernels

As is well known, using piecewise linear polynomial collocation (PLC) and piecewise quadratic polynomial collocation (PQC), respectively, to approximate the weakly singular integral $$I(a,b,x) =\int^b_a \frac{u(y)}{|x-y|^γ}dy, \quad x \in (a,b) ,\quad 0< γ<1,$$ have the local truncation error $\mathcal{O}\left(h^2\right)$ and $\mathcal{O}\left(h^{4-γ}\right)$. Moreover, for Fredholm weakly singular integral equations of the second kind, i.e., $λu(x)- I(a,b,x) =f(x)$ with $ λ\neq 0$, also have global convergence rate $\mathcal{O}\left(h^2\right)$ and $\mathcal{O}\left(h^{4-γ}\right)$ in [Atkinson and Han, Theoretical Numerical Analysis, Springer, 2009]. Formally, following nonlocal models can be viewed as Fredholm weakly singular integral equations $$\int^b_a \frac{u(x)-u(y)}{|x-y|^γ}dy =f(x), \quad x \in (a,b) ,\quad 0< γ<1.$$ However, there are still some significant differences for the models in these two fields. In the first part of this paper we prove that the weakly singular integral by PQC have an optimal local truncation error $\mathcal{O}\left(h^4η_i^{-γ}\right)$, where $η_i=\min\left\{x_i-a,b-x_i\right\}$ and $x_i$ coincides with an element junction point. Then a sharp global convergence estimate with $\mathcal{O}\left(h\right)$ and $\mathcal{O}\left(h^3\right)$ by PLC and PQC, respectively, are established for nonlocal problems. Finally, the numerical experiments including two-dimensional case are given to illustrate the effectiveness of the presented method.

0 citations0 reviewsNo code linkedOpen access
preprint2017arXiv

Energy estimates for two-dimensional space-Riesz fractional wave equation

The fractional wave equation governs the propagation of mechanical diffusive waves in viscoelastic media which exhibits a power-law creep, and consequently provided a physical interpretation of this equation in the framework of dynamic viscoelasticity. In this paper, we first develop the energy method to estimate the one-dimensional space-Riesz fractional wave equation. For two-dimensional cases with the variable coefficients, the discretized matrices are proved to be commutative, which ensures to carry out of the priori error estimates. The unconditional stability and convergence with the global truncation error $\mathcal{O}(τ^2+h^2)$ are theoretically proved and numerically verified. In particulary, the framework of the priori error estimates and convergence analysis are still valid for the compact finite difference scheme and the nonlocal wave equation.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

High-speed real-time single-pixel microscopy based on Fourier sampling

Single-pixel cameras based on the concepts of compressed sensing (CS) leverage the inherent structure of images to retrieve them with far fewer measurements and operate efficiently over a significantly broader spectral range than conventional silicon-based cameras. Recently, photonic time-stretch (PTS) technique facilitates the emergence of high-speed single-pixel cameras. A significant breakthrough in imaging speed of single-pixel cameras enables observation of fast dynamic phenomena. However, according to CS theory, image reconstruction is an iterative process that consumes enormous amounts of computational time and cannot be performed in real time. To address this challenge, we propose a novel single-pixel imaging technique that can produce high-quality images through rapid acquisition of their effective spatial Fourier spectrum. We employ phase-shifting sinusoidal structured illumination instead of random illumination for spectrum acquisition and apply inverse Fourier transform to the obtained spectrum for image restoration. We evaluate the performance of our prototype system by recognizing quick response (QR) codes and flow cytometric screening of cells. A frame rate of 625 kHz and a compression ratio of 10% are experimentally demonstrated in accordance with the recognition rate of the QR code. An imaging flow cytometer enabling high-content screening with an unprecedented throughput of 100,000 cells/s is also demonstrated. For real-time imaging applications, the proposed single-pixel microscope can significantly reduce the time required for image reconstruction by two orders of magnitude, which can be widely applied in industrial quality control and label-free biomedical imaging.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

On Stability and Sojourn Time of Peer-to-Peer Queuing Systems

Recent development of peer-to-peer (P2P) services (e.g. streaming, file sharing, and storage) systems introduces a new type of queue systems that receive little attention before, where both job and server arrive and depart randomly. Current study on these models focuses on the stability condition, under exponential workload assumption. This paper extends existing result in two aspects. In the first part of the paper we relax the exponential workload assumption, and study the stability of systems with general workload distribution. The second part of the paper focuses on the job sojourn time. An upper bound and a lower bound for job sojourn time are investigated. We evaluate tightness of the bounds by numerical analysis.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Online Offering Strategies for Storage-Assisted Renewable Power Producer in Hour-Ahead Market

A promising approach to hedge against the inherent uncertainty of renewable generation is to equip the renewable plants with energy storage systems. This paper focuses on designing profit maximization offering strategies, i.e., the strategies that determine the offering price and volume, for a storage-assisted renewable power producer that participates in hour-ahead electricity market. Designing the strategies is challenging since (i) the underlying problem is coupled across time due to the evolution of the storage level, and (ii) inputs to the problem including the renewable output and market clearing price are unknown when submitting offers. Following the competitive online algorithm design approach, we first study a basic setting where the renewable output and the clearing price are known for the next hour. We propose sOffer, a simple online offering strategy that achieves the best possible competitive ratio of O(log θ), where $θ$ is the ratio between the maximum and the minimum clearing prices. Then, we consider the case where the clearing price is unknown. By exploiting the idea of submitting multiple offers to combat price uncertainty, we propose mOffer, and demonstrate that the competitive ratio of mOffer converges to that of sOffer as the number of offers grows. Finally, we extend our approach to the scenario where the renewable output has forecasting error. We propose gOffer as the generalized offering strategy and characterize its competitive ratio as a function of the forecasting error. Our trace-driven experiments demonstrate that our algorithms achieve performance close to the offline optimal and outperform a baseline alternative significantly.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Peak-Aware Online Economic Dispatching for Microgrids

By employing local renewable energy sources and power generation units while connected to the central grid, microgrid can usher in great benefits in terms of cost efficiency, power reliability, and environmental awareness. Economic dispatching is a central problem in microgrid operation, which aims at effectively scheduling various energy sources to minimize the operating cost while satisfying the electricity demand. Designing intelligent economic dispatching strategies for microgrids, however, is drastically different from that for conventional central grids, due to two unique challenges. First, the erratic renewable energy emphasizes the need for online algorithms. Second, the widely-adopted peak-based pricing scheme brings out the need for new peak-aware strategy design. In this paper, we tackle these critical challenges and devise peak-aware online economic dispatching algorithms. For microgrids with fast-responding generators, we prove that our deterministic and randomized algorithms achieve the best possible competitive ratios $2-β$ and $e/(e-1+β)$, respectively, where $β\in[0,1]$ is the ratio between the minimum grid spot price and the local-generation price. Our results characterize the fundamental \emph{price of uncertainty} of the problem. For microgrids with slow-responding generators, we first show that a large competitive ratio is inevitable. Then we leverage limited prediction of electricity demand and renewable generation to improve the competitiveness of the algorithms. By extensive empirical evaluations using real-world traces, we show that our online algorithms achieve near offline-optimal performance. In a representative scenario, our algorithm achieves $17.5\%$ and $9.24\%$ cost reduction as compared to the case without local generation units and the case using peak-oblivious algorithms, respectively.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

High order algorithms for the fractional substantial diffusion equation with truncated Lévy flights

The equation with the time fractional substantial derivative and space fractional derivative describes the distribution of the functionals of the Lévy flights; and the equation is derived as the macroscopic limit of the continuous time random walk in unbounded domain and the Lévy flights have divergent second order moments. However, in more practical problems, the physical domain is bounded and the involved observables have finite moments. Then the modified equation can be derived by tempering the probability of large jump length of the Lévy flights and the corresponding tempered space fractional derivative is introduced. This paper focuses on providing the high order algorithms for the modified equation, i.e., the equation with the time fractional substantial derivative and space tempered fractional derivative. More concretely, the contributions of this paper are as follows: 1. the detailed numerical stability analysis and error estimates of the schemes with first order accuracy in time and second order in space are given in {\textsl{complex}} space, which is necessary since the inverse Fourier transform needs to be made for getting the distribution of the functionals after solving the equation; 2. we further propose the schemes with high order accuracy in both time and space, and the techniques of treating the issue of keeping the high order accuracy of the schemes for {\textsl{nonhomogeneous}} boundary/initial conditions are introduced; 3. the multigrid methods are effectively used to solve the obtained algebraic equations which still have the Toeplitz structure; 4. we perform extensive numerical experiments, including verifying the high convergence orders, simulating the physical system which needs to numerically make the inverse Fourier transform to the numerical solutions of the equation.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Numerical algorithms for the forward and backward fractional Feynman-Kac equations

The Feynman-Kac equations are a type of partial differential equations describing the distribution of functionals of diffusive motion. The probability density function (PDF) of Brownian functionals satisfies the Feynman-Kac formula, being a Schrödinger equation in imaginary time. The functionals of no-Brownian motion, or anomalous diffusion, follow the fractional Feynman-Kac equation [J. Stat. Phys. 141, 1071-1092, 2010], where the fractional substantial derivative is involved. Based on recently developed discretized schemes for fractional substantial derivatives [arXiv:1310.3086], this paper focuses on providing algorithms for numerically solving the forward and backward fractional Feynman-Kac equations; since the fractional substantial derivative is non-local time-space coupled operator, new challenges are introduced comparing with the general fractional derivative. Two ways (finite difference and finite element) of discretizing the space derivative are considered. For the backward fractional Feynman-Kac equation, the numerical stability and convergence of the algorithms with first order accuracy are theoretically discussed; and the optimal estimates are obtained. For all the provided schemes, including the first order and high order ones, of both forward and backward Feynman-Kac equations, extensive numerical experiments are performed to show their effectiveness.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

On Routing-Optimal Network for Multiple Unicasts

In this paper, we consider networks with multiple unicast sessions. Generally, non-linear network coding is needed to achieve the whole rate region of network coding. Yet, there exist networks for which routing is sufficient to achieve the whole rate region, and we refer to them as routing-optimal networks. We identify a class of routing-optimal networks, which we refer to as information-distributive networks, defined by three topological features. Due to these features, for each rate vector achieved by network coding, there is always a routing scheme such that it achieves the same rate vector, and the traffic transmitted through the network is exactly the information transmitted over the cut-sets between the sources and the sinks in the corresponding network coding scheme. We present more examples of information-distributive networks, including some examples from index coding and single unicast with hard deadline constraint.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

SUPER: Sparse signals with Unknown Phases Efficiently Recovered

Suppose ${\bf x}$ is any exactly $k$-sparse vector in $\mathbb{C}^{n}$. We present a class of phase measurement matrix $A$ in $\mathbb{C}^{m\times n}$, and a corresponding algorithm, called SUPER, that can resolve ${\bf x}$ up to a global phase from intensity measurements $|A{\bf x}|$ with high probability over $A$. Here $|A{\bf x}|$ is a vector of component-wise magnitudes of $A{\bf x}$. The SUPER algorithm is the first to simultaneously have the following properties: (a) it requires only ${\cal O}(k)$ (order-optimal) measurements, (b) the computational complexity of decoding is ${\cal O}(k\log k)$ (near order-optimal) arithmetic operations.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

A second-order numerical method for two-dimensional two-sided space fractional convection diffusion equation

Space fractional convection diffusion equation describes physical phenomena where particles or energy (or other physical quantities) are transferred inside a physical system due to two processes: convection and superdiffusion. In this paper, we discuss the practical alternating directions implicit method to solve the two-dimensional two-sided space fractional convection diffusion equation on a finite domain. We theoretically prove and numerically verify that the presented finite difference scheme is unconditionally von Neumann stable and second order convergent in both space and time directions.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Discretized fractional substantial calculus

This paper discusses the properties and the numerical discretizations of the fractional substantial integral $$I_s^νf(x)=\frac{1}{Γ(ν)} \int_{a}^x{\left(x-τ\right)^{ν-1}}e^{-σ(x-τ)}{f(τ)}dτ,ν>0, $$ and the fractional substantial derivative $$D_s^μf(x)=D_s^m[I_s^νf(x)], ν=m-μ,$$ where $D_s=\frac{\partial}{\partial x}+σ=D+σ$, $σ$ can be a constant or a function without related to $x$, say $σ(y)$; and $m$ is the smallest integer that exceeds $μ$. The Fourier transform method and fractional linear multistep method are used to analyze the properties or derive the discretized schemes. And the convergences of the presented discretized schemes with the global truncation error $\mathcal{O}(h^p)$$ (p=1,2,3,4,5)$ are theoretically proved and numerically verified.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Dynamic Provisioning in Next-Generation Data Centers with On-site Power Production

The critical need for clean and economical sources of energy is transforming data centers that are primarily energy consumers to also energy producers. We focus on minimizing the operating costs of next-generation data centers that can jointly optimize the energy supply from on-site generators and the power grid, and the energy demand from servers as well as power conditioning and cooling systems. We formulate the cost minimization problem and present an offline optimal algorithm. For "on-grid" data centers that use only the grid, we devise a deterministic online algorithm that achieves the best possible competitive ratio of $2-α_{s}$, where $α_{s}$ is a normalized look-ahead window size. For "hybrid" data centers that have on-site power generation in addition to the grid, we develop an online algorithm that achieves a competitive ratio of at most \textmd{\normalsize {\small $\frac{P_{\max} (2-α_{s})}{c_{o}+c_{m}/L} [1+2\frac{P_{\max}-c_{o}}{P_{\max}(1+α_{g})}]$}}, where $α_{s}$ and $α_{g}$ are normalized look-ahead window sizes, $P_{\max}$ is the maximum grid power price, and $L$, $c_{o}$, and $c_{m}$ are parameters of an on-site generator. Using extensive workload traces from Akamai with the corresponding grid power prices, we simulate our offline and online algorithms in a realistic setting. Our offline (resp., online) algorithm achieves a cost reduction of 25.8% (resp., 20.7%) for a hybrid data center and 12.3% (resp., 7.3%) for an on-grid data center. The cost reductions are quite significant and make a strong case for a joint optimization of energy supply and energy demand in a data center. A hybrid data center provides about 13% additional cost reduction over an on-grid data center representing the additional cost benefits that on-site power generation provides over using the grid alone.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Efficient numerical algorithms for three-dimensional fractional partial differential equations

This paper detailedly discusses the locally one-dimensional numerical methods for efficiently solving the three-dimensional fractional partial differential equations, including fractional advection diffusion equation and Riesz fractional diffusion equation. The second order finite difference scheme is used to discretize the space fractional derivative and the Crank-Nicolson procedure to the time derivative. We theoretically prove and numerically verify that the presented numerical methods are unconditionally stable and second order convergent in both space and time directions. In particular, for the Riesz fractional diffusion equation, the idea of reducing the splitting error is used to further improve the algorithm, and the unconditional stability and convergency are also strictly proved and numerically verified for the improved scheme.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

FRANTIC: A Fast Reference-based Algorithm for Network Tomography via Compressive Sensing

We study the problem of link and node delay estimation in undirected networks when at most k out of n links or nodes in the network are congested. Our approach relies on end-to-end measurements of path delays across pre-specified paths in the network. We present a class of algorithms that we call FRANTIC. The FRANTIC algorithms are motivated by compressive sensing; however, unlike traditional compressive sensing, the measurement design here is constrained by the network topology and the matrix entries are constrained to be positive integers. A key component of our design is a new compressive sensing algorithm SHO-FA-INT that is related to the prior SHO-FA algorithm for compressive sensing, but unlike SHO-FA, the matrix entries here are drawn from the set of integers {0, 1, ..., M}. We show that O(k log n /log M) measurements suffice both for SHO-FA-INT and FRANTIC. Further, we show that the computational complexity of decoding is also O(k log n/log M) for each of these algorithms. Finally, we look at efficient constructions of the measurement operations through Steiner Trees.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Online Energy Generation Scheduling for Microgrids with Intermittent Energy Sources and Co-Generation

Microgrids represent an emerging paradigm of future electric power systems that can utilize both distributed and centralized generations. Two recent trends in microgrids are the integration of local renewable energy sources (such as wind farms) and the use of co-generation (i.e., to supply both electricity and heat). However, these trends also bring unprecedented challenges to the design of intelligent control strategies for microgrids. Traditional generation scheduling paradigms rely on perfect prediction of future electricity supply and demand. They are no longer applicable to microgrids with unpredictable renewable energy supply and with co-generation (that needs to consider both electricity and heat demand). In this paper, we study online algorithms for the microgrid generation scheduling problem with intermittent renewable energy sources and co-generation, with the goal of maximizing the cost-savings with local generation. Based on the insights from the structure of the offline optimal solution, we propose a class of competitive online algorithms, called CHASE (Competitive Heuristic Algorithm for Scheduling Energy-generation), that track the offline optimal in an online fashion. Under typical settings, we show that CHASE achieves the best competitive ratio among all deterministic online algorithms, and the ratio is no larger than a small constant 3.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Routing for Security in Networks with Adversarial Nodes

We consider the problem of secure unicast transmission between two nodes in a directed graph, where an adversary eavesdrops/jams a subset of nodes. This adversarial setting is in contrast to traditional ones where the adversary controls a subset of links. In particular, we study, in the main, the class of routing-only schemes (as opposed to those allowing coding inside the network). Routing-only schemes usually have low implementation complexity, yet a characterization of the rates achievable by such schemes was open prior to this work. We first propose an LP based solution for secure communication against eavesdropping, and show that it is information-theoretically rate-optimal among all routing-only schemes. The idea behind our design is to balance information flow in the network so that no subset of nodes observe "too much" information. Interestingly, we show that the rates achieved by our routing-only scheme are always at least as good as, and sometimes better, than those achieved by "naïve" network coding schemes (i.e. the rate-optimal scheme designed for the traditional scenario where the adversary controls links in a network rather than nodes.) We also demonstrate non-trivial network coding schemes that achieve rates at least as high as (and again sometimes better than) those achieved by our routing schemes, but leave open the question of characterizing the optimal rate-region of the problem under all possible coding schemes. We then extend these routing-only schemes to the adversarial node-jamming scenarios and show similar results. During the journey of our investigation, we also develop a new technique that has the potential to derive non-trivial bounds for general secure-communication schemes.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Second-order LOD multigrid method for multidimensional Riesz fractional diffusion equation

We propose a locally one dimensional (LOD) finite difference method for multidimensional Riesz fractional diffusion equation with variable coefficients on a finite domain. The numerical method is second-order convergent in both space and time directions, and its unconditional stability is strictly proved. Comparing with the popular first-order finite difference method for fractional operator, the form of obtained matrix algebraic equation is changed from $(I-A)u^{k+1}=u^k+b^{k+1}$ to $(I-{\widetilde A})u^{k+1}=(I+{\widetilde B})u^k+{\tilde b}^{k+1/2}$; the three matrices $A$, ${\widetilde A}$ and ${\widetilde B}$ are all Toeplitz-like, i.e., they have completely same structure and the computational count for matrix vector multiplication is $\mathcal{O}(N {log} N)$; and the computational costs for solving the two matrix algebraic equations are almost the same. The LOD-multigrid method is used to solve the resulting matrix algebraic equation, and the computational count is $\mathcal{O}(N {log} N)$ and the required storage is $\mathcal{O}(N)$, where $N$ is the number of grid points. Finally, the extensive numerical experiments are performed to show the powerfulness of the second-order scheme and the LOD-multigrid method.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

When Backpressure Meets Predictive Scheduling

Motivated by the increasing popularity of learning and predicting human user behavior in communication and computing systems, in this paper, we investigate the fundamental benefit of predictive scheduling, i.e., predicting and pre-serving arrivals, in controlled queueing systems. Based on a lookahead window prediction model, we first establish a novel equivalence between the predictive queueing system with a \emph{fully-efficient} scheduling scheme and an equivalent queueing system without prediction. This connection allows us to analytically demonstrate that predictive scheduling necessarily improves system delay performance and can drive it to zero with increasing prediction power. We then propose the \textsf{Predictive Backpressure (PBP)} algorithm for achieving optimal utility performance in such predictive systems. \textsf{PBP} efficiently incorporates prediction into stochastic system control and avoids the great complication due to the exponential state space growth in the prediction window size. We show that \textsf{PBP} can achieve a utility performance that is within $O(ε)$ of the optimal, for any $ε>0$, while guaranteeing that the system delay distribution is a \emph{shifted-to-the-left} version of that under the original Backpressure algorithm. Hence, the average packet delay under \textsf{PBP} is strictly better than that under Backpressure, and vanishes with increasing prediction window size. This implies that the resulting utility-delay tradeoff with predictive scheduling beats the known optimal $[O(ε), O(\log(1/ε))]$ tradeoff for systems without prediction.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

WSLD operators II: the new fourth order difference approximations for space Riemann-Liouville derivative

High order discretization schemes play more important role in fractional operators than classical ones. This is because usually for classical derivatives the stencil for high order discretization schemes is wider than low order ones; but for fractional operators the stencils for high order schemes and low order ones are the same. Then using high order schemes to solve fractional equations leads to almost the same computational cost with first order schemes but the accuracy is greatly improved. Using the fractional linear multistep methods, Lubich obtains the $ν$-th order ($ν\leq 6$) approximations of the $α$-th derivative ($α>0$) or integral ($α<0) [Lubich, SIAM J. Math. Anal., 17, 704-719, 1986], because of the stability issue the obtained scheme can not be directly applied to the space fractional operator with $α\in(1,2)$ for time dependent problem. By weighting and shifting Lubich's 2nd order discretization scheme, in [Chen & Deng, arXiv:1304.7425] we derive a series of effective high order discretizations for space fractional derivative, called WSLD opeartors there. As the sequel of the previous work, we further provide new high order schemes for space fractional derivatives by weighting and shifting Lubich's 3rd and 4th order discretizations. In particular, we prove that the obtained 4th order approximations are effective for space fractional derivatives. And the corresponding schemes are used to solve the space fractional diffusion equation with variable coefficients.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

WSLD operators: A class of fourth order difference approximations for space Riemann-Liouville derivative

Because of the nonlocal properties of fractional operators, higher order schemes play more important role in discretizing fractional derivatives than classical ones. The striking feature is that higher order schemes of fractional derivatives can keep the same computation cost with first-order schemes but greatly improve the accuracy. Nowadays, there are already two types of second order discretization schemes for space fractional derivatives: the first type is given and discussed in [Sousa & Li, arXiv:1109.2345; Chen & Deng, arXiv:1304.3788; Chen et al., Appl. Numer. Math., 70, 22-41]; and the second type is a class of schemes presented in [Tian et al., arXiv:1201.5949]. The core object of this paper is to derive a class of fourth order approximations, called the weighted and shifted Lubich difference (WSLD) operators, for space fractional derivatives. Then we use the derived schemes to solve the space fractional diffusion equation with variable coefficients in one-dimensional and two-dimensional cases. And the unconditional stability and the convergence with the global truncation error $\mathcal{O}(τ^2+h^4)$ are theoretically proved and numerically verified.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Analog Network Coding in General SNR Regime

The problem of maximum rate achievable with analog network coding for a unicast communication over a layered wireless relay network with directed links is considered. A relay node performing analog network coding scales and forwards the signals received at its input. Recently this problem has been considered under two assumptions: (A) each relay node scales its received signal to the upper bound of its transmit power constraint, (B) the relay nodes in specific subsets of the network operate in the high-SNR regime. We establish that assumption (A), in general, leads to suboptimal end-to-end rate. We also characterize the performance of analog network coding in class of symmetric layered networks without assumption (B). The key contribution of this work is a lemma that states that a globally optimal set of scaling factors for the nodes in a layered relay network that maximizes the end-to-end rate can be computed layer-by-layer. Specifically, a rate-optimal set of scaling factors for the nodes in a layer is the one that maximizes the sum-rate of the nodes in the next layer. This critical insight allows us to characterize analog network coding performance in network scenarios beyond those that can be analyzed using the existing approaches. We illustrate this by computing the maximum rate achievable with analog network coding in one particular layered network, in various communication scenarios.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Analog network coding in general SNR regime: Performance of a greedy scheme

The problem of maximum rate achievable with analog network coding for a unicast communication over a layered relay network with directed links is considered. A relay node performing analog network coding scales and forwards the signals received at its input. Recently this problem has been considered under certain assumptions on per node scaling factor and received SNR. Previously, we established a result that allows us to characterize the optimal performance of analog network coding in network scenarios beyond those that can be analyzed using the approaches based on such assumptions. The key contribution of this work is a scheme to greedily compute a lower bound to the optimal rate achievable with analog network coding in the general layered networks. This scheme allows for exact computation of the optimal achievable rates in a wider class of layered networks than those that can be addressed using existing approaches. For the specific case of Gaussian N-relay diamond network, to the best of our knowledge, the proposed scheme provides the first exact characterization of the optimal rate achievable with analog network coding. Further, for general layered networks, our scheme allows us to compute optimal rates within a constant gap from the cut-set upper bound asymptotically in the source power.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Analog Network Coding in General SNR Regime: Performance of Network Simplification

We consider a communication scenario where a source communicates with a destination over a directed layered relay network. Each relay performs analog network coding where it scales and forwards the signals received at its input. In this scenario, we address the question: What portion of the maximum end-to-end achievable rate can be maintained if only a fraction of relay nodes available at each layer are used? We consider, in particular, the Gaussian diamond network (layered network with a single layer of relay nodes) and a class of symmetric layered networks. For these networks we show that each relay layer increases the additive gap between the optimal analog network coding performance with and without network simplification (using k instead of N relays in each layer, k < N) by no more than log(N/k)^2 bits and the corresponding multiplicative gap by no more than a factor of (N/k)^2, asymptotically (in source power). To the best of our knowledge, this work offers the first characterization of the performance of network simplification in general layered amplify-and-forward relay networks. Further, unlike most of the current approximation results that attempt to bound optimal rates either within an additive gap or a multiplicative gap, our results suggest a new rate approximation scheme that allows for the simultaneous computation of additive and multiplicative gaps.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Optimal Distributed P2P Streaming under Node Degree Bounds

We study the problem of maximizing the broadcast rate in peer-to-peer (P2P) systems under \emph{node degree bounds}, i.e., the number of neighbors a node can simultaneously connect to is upper-bounded. The problem is critical for supporting high-quality video streaming in P2P systems, and is challenging due to its combinatorial nature. In this paper, we address this problem by providing the first distributed solution that achieves near-optimal broadcast rate under arbitrary node degree bounds, and over arbitrary overlay graph. It runs on individual nodes and utilizes only the measurement from their one-hop neighbors, making the solution easy to implement and adaptable to peer churn and network dynamics. Our solution consists of two distributed algorithms proposed in this paper that can be of independent interests: a network-coding based broadcasting algorithm that optimizes the broadcast rate given a topology, and a Markov-chain guided topology hopping algorithm that optimizes the topology. Our distributed broadcasting algorithm achieves the optimal broadcast rate over arbitrary P2P topology, while previously proposed distributed algorithms obtain optimality only for P2P complete graphs. We prove the optimality of our solution and its convergence to a neighborhood around the optimal equilibrium under noisy measurements or without time-scale separation assumptions. We demonstrate the effectiveness of our solution in simulations using uplink bandwidth statistics of Internet hosts.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Second order finite difference approximations for the two-dimensional time-space Caputo-Riesz fractional diffusion equation

In this paper, we discuss the time-space Caputo-Riesz fractional diffusion equation with variable coefficients on a finite domain. The finite difference schemes for this equation are provided. We theoretically prove and numerically verify that the implicit finite difference scheme is unconditionally stable (the explicit scheme is conditionally stable with the stability condition $\frac{τ^γ}{(Δx)^α}+\frac{τ^γ}{(Δy)^β} <C$) and 2nd order convergent in space direction, and $(2-γ)$-th order convergent in time direction, where $γ\in(0,1]$.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Secure Compressed Reading in Smart Grids

Smart Grids measure energy usage in real-time and tailor supply and delivery accordingly, in order to improve power transmission and distribution. For the grids to operate effectively, it is critical to collect readings from massively-installed smart meters to control centers in an efficient and secure manner. In this paper, we propose a secure compressed reading scheme to address this critical issue. We observe that our collected real-world meter data express strong temporal correlations, indicating they are sparse in certain domains. We adopt Compressed Sensing technique to exploit this sparsity and design an efficient meter data transmission scheme. Our scheme achieves substantial efficiency offered by compressed sensing, without the need to know beforehand in which domain the meter data are sparse. This is in contrast to traditional compressed-sensing based scheme where such sparse-domain information is required a priori. We then design specific dependable scheme to work with our compressed sensing based data transmission scheme to make our meter reading reliable and secure. We provide performance guarantee for the correctness, efficiency, and security of our proposed scheme. Through analysis and simulations, we demonstrate the effectiveness of our schemes and compare their performance to prior arts.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

SHO-FA: Robust compressive sensing with order-optimal complexity, measurements, and bits

Suppose x is any exactly k-sparse vector in R^n. We present a class of sparse matrices A, and a corresponding algorithm that we call SHO-FA (for Short and Fast) that, with high probability over A, can reconstruct x from Ax. The SHO-FA algorithm is related to the Invertible Bloom Lookup Tables recently introduced by Goodrich et al., with two important distinctions - SHO-FA relies on linear measurements, and is robust to noise. The SHO-FA algorithm is the first to simultaneously have the following properties: (a) it requires only O(k) measurements, (b) the bit-precision of each measurement and each arithmetic operation is O (log(n) + P) (here 2^{-P} is the desired relative error in the reconstruction of x), (c) the decoding complexity is O(k) arithmetic operations and encoding complexity is O(n) arithmetic operations, and (d) if the reconstruction goal is simply to recover a single component of x instead of all of x, with significant probability over A this can be done in constant time. All constants above are independent of all problem parameters other than the desired success probability. For a wide range of parameters these properties are information-theoretically order-optimal. In addition, our SHO-FA algorithm works over fairly general ensembles of "sparse random matrices", is robust to random noise, and (random) approximate sparsity for a large range of k. In particular, suppose the measured vector equals A(x+z)+e, where z and e correspond respectively to the source tail and measurement noise. Under reasonable statistical assumptions on z and e our decoding algorithm reconstructs x with an estimation error of O(||z||_2 +||e||_2). The SHO-FA algorithm works with high probability over A, z, and e, and still requires only O(k) steps and O(k) measurements over O(log n)-bit numbers. This is in contrast to the worst-case z model, where it is known O(k log n/k) measurements are necessary.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Simple and Effective Dynamic Provisioning for Power-Proportional Data Centers

Energy consumption represents a significant cost in data center operation. A large fraction of the energy, however, is used to power idle servers when the workload is low. Dynamic provisioning techniques aim at saving this portion of the energy, by turning off unnecessary servers. In this paper, we explore how much performance gain can knowing future workload information brings to dynamic provisioning. In particular, we study the dynamic provisioning problem under the cost model that a running server consumes a fixed amount energy per unit time, and develop online solutions with and without future workload information available. We first reveal an elegant structure of the off-line dynamic provisioning problem, which allows us to characterize and achieve the optimal solution in a {}"divide-and-conquer" manner. We then exploit this insight to design three online algorithms with competitive ratios $2-α$, $(e-α)/(e-1)\approx1.58-α/(e-1)$ and $e/(e-1+α)$, respectively, where $0\leqα\leq1$ is the fraction of a critical window in which future workload information is available. A fundamental observation is that \emph{future workload information beyond the critical window will not} \emph{improve dynamic provisioning performance}. Our algorithms are decentralized and are simple to implement. We demonstrate their effectiveness in simulations using real-world traces. We also compare their performance with state-of-the-art solutions.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Amplify-and-Forward in Wireless Relay Networks

A general class of wireless relay networks with a single source-destination pair is considered. Intermediate nodes in the network employ an amplify-and-forward scheme to relay their input signals. In this case the overall input-output channel from the source via the relays to the destination effectively behaves as an intersymbol interference channel with colored noise. Unlike previous work we formulate the problem of the maximum achievable rate in this setting as an optimization problem with no assumption on the network size, topology, and received signal-to-noise ratio. Previous work considered only scenarios wherein relays use all their power to amplify their received signals. We demonstrate that this may not always maximize the maximal achievable rate in amplify-and-forward relay networks. The proposed formulation allows us to not only recover known results on the performance of the amplify-and-forward schemes for some simple relay networks but also characterize the performance of more complex amplify-and-forward relay networks which cannot be addressed in a straightforward manner using existing approaches. Using cut-set arguments, we derive simple upper bounds on the capacity of general wireless relay networks. Through various examples, we show that a large class of amplify-and-forward relay networks can achieve rates within a constant factor of these upper bounds asymptotically in network parameters.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Enabling Multi-level Trust in Privacy Preserving Data Mining

Privacy Preserving Data Mining (PPDM) addresses the problem of developing accurate models about aggregated data without access to precise information in individual data record. A widely studied \emph{perturbation-based PPDM} approach introduces random perturbation to individual values to preserve privacy before data is published. Previous solutions of this approach are limited in their tacit assumption of single-level trust on data miners. In this work, we relax this assumption and expand the scope of perturbation-based PPDM to Multi-Level Trust (MLT-PPDM). In our setting, the more trusted a data miner is, the less perturbed copy of the data it can access. Under this setting, a malicious data miner may have access to differently perturbed copies of the same data through various means, and may combine these diverse copies to jointly infer additional information about the original data that the data owner does not intend to release. Preventing such \emph{diversity attacks} is the key challenge of providing MLT-PPDM services. We address this challenge by properly correlating perturbation across copies at different trust levels. We prove that our solution is robust against diversity attacks with respect to our privacy goal. That is, for data miners who have access to an arbitrary collection of the perturbed copies, our solution prevent them from jointly reconstructing the original data more accurately than the best effort using any individual copy in the collection. Our solution allows a data owner to generate perturbed copies of its data for arbitrary trust levels on-demand. This feature offers data owners maximum flexibility.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

An Adaptive Multi-channel P2P Video-on-Demand System using Plug-and-Play Helpers

We present a multi-channel P2P Video-on-Demand (VoD) system using "plug-and-play" helpers. Helpers are heterogenous "micro-servers" with limited storage, bandwidth and number of users they can serve simultaneously. Our proposed system has the following salient features: (1) it minimizes the server load; (2) it is distributed, and requires little or no maintenance overhead and which can easily adapt to system dynamics; and (3) it is adaptable to varying supply and demand patterns across multiple video channels irrespective of video popularity. Our proposed solution jointly optimizes over helper-user topology, video storage allocation and bandwidth allocation. The combinatorial nature of the problem and the system demand for distributed algorithms makes the problem uniquely challenging. By utilizing Lagrangian decomposition and Markov chain approximation based arguments, we address this challenge by designing two distributed algorithms running in tandem: a primal-dual storage and bandwidth allocation algorithm and a "soft-worst-neighbor-choking" topology-building algorithm. Our scheme provably converges to a near-optimal solution, and is easy to implement in practice. Simulation results validate that the proposed scheme achieves minimum sever load under highly heterogeneous combinations of supply and demand patterns, and is robust to system dynamics of user/helper churn, user/helper asynchrony, and random delays in the network.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Analysis of Frequency-Agile CSMA Wireless Networks

This paper proposes and analyzes the performance of a simple frequency-agile CSMA MAC protocol. In this MAC, a node carrier-senses multiple frequency channels simultaneously, and it takes the first opportunity to transmit on any one of the channels when allowed by the CSMA backoff mechanism. We show that the frequency-agile MAC can effectively 1) boost throughput and 2) remove temporal starvation. Furthermore, the MAC can be implemented on the existing multiple-frequency setup in Wi-Fi using multi-radio technology, and it can co-exist with the legacy MAC using single radio. This paper provides exact stationary throughput analysis for regular 1D and thin-strip 2D CSMA networks using a "transfer-matrix" approach. In addition, accurate approximations are given for 2D grid networks. Our closed-form formulas accurately quantify the throughput gain of frequency-agile CSMA. To characterize temporal starvation, we use the metric of "mean residual access time" (MRAT). Our simulations and closed-form approximations indicate that the frequency-agile MAC can totally eliminate temporal starvation in 2D grid networks, reducing its MRAT by orders of magnitude. Finally, this paper presents a "coloring theorem" to justify the use of the frequency-agile MAC in general network topologies. Our analysis and theorem suggest that with enough frequency channels, the frequency-agile MAC can effectively decouple the detrimental interactions between neighboring links responsible for low throughput and starvation.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Distributed and Optimal Reduced Primal-Dual Algorithm for Uplink OFDM Resource Allocation

Orthogonal Frequency Division Multiplexing (OFDM) is the key component of many emerging broadband wireless access standards. The resource allocation in OFDM uplink, however, is challenging due to heterogeneity of users' Quality of Service requirements, channel conditions, and individual resource constraints. We formulate the resource allocation problem as a non-strictly convex optimization problem, which typically has multiple global optimal solutions. We then propose a reduced primal-dual algorithm, which is distributed, low in computational complexity, and probably globally convergent to a global optimal solution. The performance of the algorithm is studied through a realistic OFDM simulator. Compared with the previously proposed centralized optimal algorithm, our algorithm not only significantly reduces the message overhead but also requires less iterations to converge.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Passive network tomography for erroneous networks: A network coding approach

Passive network tomography uses end-to-end observations of network communication to characterize the network, for instance to estimate the network topology and to localize random or adversarial glitches. Under the setting of linear network coding this work provides a comprehensive study of passive network tomography in the presence of network (random or adversarial) glitches. To be concrete, this work is developed along two directions: 1. Tomographic upper and lower bounds (i.e., the most adverse conditions in each problem setting under which network tomography is possible, and corresponding schemes (computationally efficient, if possible) that achieve this performance) are presented for random linear network coding (RLNC). We consider RLNC designed with common randomness, i.e., the receiver knows the random code-books all nodes. (To justify this, we show an upper bound for the problem of topology estimation in networks using RLNC without common randomness.) In this setting we present the first set of algorithms that characterize the network topology exactly. Our algorithm for topology estimation with random network errors has time complexity that is polynomial in network parameters. For the problem of network error localization given the topology information, we present the first computationally tractable algorithm to localize random errors, and prove it is computationally intractable to localize adversarial errors. 2. New network coding schemes are designed that improve the tomographic performance of RLNC while maintaining the desirable low-complexity, throughput-optimal, distributed linear network coding properties of RLNC. In particular, we design network codes based on Reed-Solomon codes so that a maximal number of adversarial errors can be localized in a computationally efficient manner even without the information of network topology.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

TCP Reno over Adaptive CSMA

An interesting distributed adaptive CSMA MAC protocol, called adaptive CSMA, was proposed recently to schedule any strictly feasible achievable rates inside the capacity region. Of particular interest is the fact that the adaptive CSMA can achieve a system utility arbitrarily close to that is achievable under a central scheduler. However, a specially designed transport-layer rate controller is needed for this result. An outstanding question is whether the widely-installed TCP Reno is compatible with adaptive CSMA and can achieve the same result. The answer to this question will determine how close to practical deployment adaptive CSMA is. Our answer is yes and no. First, we observe that running TCP Reno directly over adaptive CSMA results in severe starvation problems. Effectively, its performance is no better than that of TCP Reno over legacy CSMA (IEEE 802.11), and the potentials of adaptive CSMA cannot be realized. Fortunately, we find that multi-connection TCP Reno over adaptive CSMA with active queue management can materialize the advantages of adaptive CSMA. NS-2 simulations demonstrate that our solution can alleviate starvation and achieve fair and efficient rate allocation. Multi-connection TCP can be implemented at either application or transport layer. Application-layer implementation requires no kernel modification, making the solution readily deployable in networks running adaptive CSMA.

0 citations0 reviewsNo code linkedOpen access