Mobile edge computing (MEC) is a promising solution for enhancing user experience, minimizing content delivery expenses, and reducing backhaul traffic. This paper presents a game-theoretic framework to address the edge resource crowdsourcing problem, where mobile edge devices (MEDs) provide idle storage for content caching in exchange for rewards from a content provider (CP). We model the interaction between the CP and MEDs as a Stackelberg game, with the CP as the leader setting the reward structure and the MEDs as followers competing in a non-cooperative game for these rewards. We propose a novel privacy-preserving method to derive the Stackelberg equilibrium of the game. Notably, our algorithm is designed to operate effectively in time-varying communication networks, addressing the high mobility inherent in MEC environments. This contrasts with state-of-the-art algorithms, which assume a static communication network among MEDs–an impractical condition that does not account for the mobility of MEDs during algorithm execution. Specifically, our approach employs consensus-based algorithms to compute the Nash equilibrium (NE) for MEDs, with MEDs exchanging NE profile estimates with neighbors via row-stochastic mixing matrices and performing gradient steps to optimize their utility in a fully decentralized manner. Based on the computed NE strategies, we propose a zeroth-order reward search algorithm for the CP to determine the optimal strategy for profit maximization. Our comprehensive analysis details the properties of the equilibrium and establishes the geometric convergence of the proposed algorithms to the NE. We also derive explicit bounds for the stepsizes based on the game's properties and the graphs' connectivity structure. Extensive numerical results validate the efficacy of our proposed approach.

DNA edit distance (ED) measures the minimum number of single nucleotide insertions, substitutions, or deletions required to convert a DNA sequence into another. ED has broad applications in healthcare such as sequence alignment, genome assembly, functional annotation, and drug discovery. Privacy-preserving computation is essential in this context to protect sensitive genomic data. Nonetheless, the existing secure DNA edit distance solutions lack efficiency when handling large data sequences or resort to approximations and fail to accurately compute the metric. In this work, we introduce ScureED, a protocol that tackles these limitations, resulting in a significant performance enhancement of approximately 2-24 times compared to existing methods. Our protocol computes a secure ED between two genomes, each comprising 1,000 letters, in just a few seconds. The underlying technique of our protocol is a novel approach that transforms the established approximate matching technique (i.e., the Ukkonen algorithm) into exact matching, exploiting the inherent similarity in human DNA to achieve cost-effectiveness. Furthermore, we introduce various optimizations tailored for secure computation in scenarios with a limited input domain, such as DNA sequences composed solely of the four nucleotide letters.

This paper studies the joint optimization of edge node activation and resource pricing in edge computing, where an edge computing platform provides heterogeneous resources to accommodate multiple services with diverse pReferences. We cast this problem as a bi-level program, with the platform acting as the leader and the services as the followers. The platform aims to maximize net profit by optimizing edge resource prices and edge node activation, with the services’ optimization problems acting as constraints. Based on the platform’s decisions, each service aims to minimize its costs and enhance user experience through optimal service placement and resource procurement decisions. The presence of integer variables in both the upper and lower-level problems renders this problem particularly challenging. Traditional techniques for transforming bi-level problems into single-level formulations are inappropriate owing to the non-convex nature of the follower problems. Drawing inspiration from the column-and-constraint generation method in robust optimization, we develop an efficient decomposition-based iterative algorithm to compute an exact optimal solution to the formulated bi-level problem. Extensive numerical results are presented to demonstrate the efficacy of the proposed model and technique.

Edge computing enables Service Providers (SPs) to enhance user experience by placing services closer to the network edge. However, cost-effectively provisioning edge resources to meet uncertain and varying demand is a critical challenge. This paper introduces a novel two-stage, multi-period robust optimization model for edge service placement and workload allocation, aiming to minimize SPs' operating costs while ensuring service quality. The salient feature of this model is its ability to leverage dynamic service placement and spatio-temporal correlations in demand uncertainties to mitigate the conservatism of traditional robust approaches optimized for worst-case scenarios. In our model, resource reservation is determined preemptively in the first stage, while dynamic service placement and workload allocation are adaptively optimized in the second stage after uncertainties are revealed. To address the computational challenges posed by integer recourse variables in the resulting tri-level adjustable robust optimization problem, we develop a novel iterative decomposition-based approach with guaranteed finite convergence to an exact optimal solution. Extensive numerical results validate the efficacy of the proposed model and approach.

Edge computing (EC) promises to deliver low-latency and ubiquitous computation to numerous devices at the network edge. This paper aims to jointly optimize edge node (EN) placement and resource allocation for an EC platform, considering demand uncertainty. Diverging from existing approaches treating uncertainties as exogenous, we propose a novel two-stage decision-dependent distributionally robust optimization (DRO) framework to effectively capture the interdependence between EN placement decisions and uncertain demands. The first stage involves making EN placement decisions, while the second stage optimizes resource allocation after uncertainty revelation. We present an exact mixed-integer linear program reformulation for solving the underlying "min-max-min" two-stage model. We further introduce a valid inequality method to enhance computational efficiency, especially for large-scale networks. Extensive numerical experiments demonstrate the benefits of considering endogenous uncertainties and the advantages of the proposed model and approach.

Resiliency plays a critical role in designing future communication networks. How to make edge computing systems resilient against unpredictable failures and fluctuating demand is an important and challenging problem. To this end, this paper investigates a resilient service placement and workload allocation problem for a service provider (SP) who can procure resources from numerous edge nodes to serve its users, considering both resource demand and node failure uncertainties. We introduce a novel two-stage adaptive robust model to capture this problem. The service placement and resource procurement decisions are optimized in the first stage, while the workload allocation decision is determined in the second stage after the uncertainty realization. By exploiting the special structure of the uncertainty set, we develop an efficient iterative algorithm that can converge to an exact optimal solution within a finite number of iterations. However, the running time of this iterative algorithm heavily depends on the uncertainty set. Therefore, we further present an affine decisions rule approximation approach, which exhibits greater insensitivity to the uncertainty set, to tackle the underlying problem. Extensive numerical results demonstrate the advantages of the proposed model and approaches, which can help the SP make proactive decisions to mitigate the impacts of the uncertainties.

Edge Computing (EC) offers a superior user experience by positioning cloud resources in close proximity to end users. The challenge of allocating edge resources efficiently while maximizing profit for the EC platform remains a sophisticated problem, especially with the added complexity of the online arrival of resource requests. To address this challenge, we propose to cast the problem as a multi-armed bandit problem and develop two novel online pricing mechanisms, the Kullback-Leibler Upper Confidence Bound (KL-UCB) algorithm and the Min-Max Optimal algorithm, for heterogeneous edge resource allocation. These mechanisms operate in real-time and do not require prior knowledge of demand distribution, which can be difficult to obtain in practice. The proposed posted pricing schemes allow users to select and pay for their preferred resources, with the platform dynamically adjusting resource prices based on observed historical data. Numerical results show the advantages of the proposed mechanisms compared to several benchmark schemes derived from traditional bandit algorithms, including the Epsilon-Greedy, basic UCB, and Thompson Sampling algorithms.

Mobile edge computing (MEC) is a promising solution for enhancing the user experience, minimizing content delivery expenses, and reducing backhaul traffic. In this paper, we propose a novel privacy-preserving decentralized game-theoretic framework for resource crowdsourcing in MEC. Our framework models the interactions between a content provider (CP) and multiple mobile edge device users (MEDs) as a non-cooperative game, in which MEDs offer idle storage resources for content caching in exchange for rewards. We introduce efficient decentralized gradient play algorithms for Nash equilibrium (NE) computation by exchanging local information among neighboring MEDs only, thus preventing attackers from learning users' private information. The key challenge in designing such algorithms is that communication among MEDs is not fixed and is facilitated by a sequence of undirected time-varying graphs. Our approach achieves linear convergence to the NE without imposing any assumptions on the values of parameters in the local objective functions, such as requiring strong monotonicity to be stronger than its dependence on other MEDs' actions, which is commonly required in existing literature when the graph is directed time-varying. Extensive simulations demonstrate the effectiveness of our approach in achieving efficient resource outsourcing decisions while preserving the privacy of the edge devices.

Edge computing has emerged as a key technology to reduce network traffic, improve user experience, and enable numerous Internet of Things applications. In this article, we study an optimal resource procurement problem for a service provider (SP), who can purchase resources from various edge nodes in the edge computing market to serve its users’ requests. How to jointly optimize the service placement, resource sizing, and workload allocation decisions is a challenging problem, which becomes even more complicated when considering demand uncertainty. To this end, we propose a novel two-stage adaptive robust optimization framework to help the SP optimally determine the locations for installing its service (i.e., placement) and the amount of computing resource to purchase from each location (i.e., sizing). The proposed placement and sizing solution can hedge against any possible realization within a predefined demand uncertainty set. Given the first-stage robust solution, the optimal resource and workload allocation decisions are computed in the second stage after the uncertainty is revealed. To solve the two-stage model, this article presents an iterative solution approach by employing the column-and-constraint generation method that decomposes the underlying problem into a master problem and a max–min subproblem associated with the second stage. Extensive numerical results are shown to illustrate the efficacy of the proposed model.

The emerging edge computing (EC) paradigm promises to provide low latency and ubiquitous computation to numerous mobile and Internet of Things (IoT) devices at the network edge. How to efficiently allocate geographically distributed heterogeneous edge resources to a variety of services is a challenging task. While this problem has been studied extensively in recent years, most of the previous work has largely ignored the preferences of the services when making edge resource allocation decisions. To this end, this article introduces a novel bilevel optimization model, which explicitly takes the service preferences into consideration, to study the interaction between an EC platform and multiple services. The platform manages a set of edge nodes (ENs) and acts as the leader while the services are the followers. Given the service placement and resource pricing decisions of the leader, each service decides how to optimally divide its workload to different ENs. The proposed framework not only maximizes the profit of the platform but also minimizes the cost of every service. When there is a single EN, we derive a simple analytic solution for the underlying problem. For the general case with multiple ENs and multiple services, we present a Karush–Kuhn–Tucker-based solution and a duality-based solution, combining with a series of linearizations, to solve the bilevel problem. Extensive numerical results are shown to illustrate the efficacy of the proposed model.

The emerging edge computing paradigm promises to deliver superior user experience and enable a wide range of Internet of Things (IoT) applications. In this paper, we propose a new market-based framework for efficiently allocating resources of heterogeneous capacity-limited edge nodes (EN) to multiple competing services at the network edge. By properly pricing the geographically distributed ENs, the proposed framework generates a market equilibrium (ME) solution that not only maximizes the edge computing resource utilization but also allocates optimal resource bundles to the services given their budget constraints. When the utility of a service is defined as the maximum revenue that the service can achieve from its resource allotment, the equilibrium can be computed centrally by solving the Eisenberg-Gale (EG) convex program. We further show that the equilibrium allocation is Pareto-optimal and satisfies desired fairness properties including sharing incentive, proportionality, and envy-freeness. Also, two distributed algorithms, which efficiently converge to an ME, are introduced. When each service aims to maximize its net profit (i.e., revenue minus cost) instead of the revenue, we derive a novel convex optimization problem and rigorously prove that its solution is exactly an ME. Extensive numerical results are presented to validate the effectiveness of the proposed techniques.

Fog computing is transforming the network edge into an intelligent platform by bringing storage, computing, control, and networking functions closer to end users, things, and sensors. How to allocate multiple resource types (e.g., CPU, memory, bandwidth) of capacity-limited heterogeneous fog nodes to competing services with diverse requirements and preferences in a fair and efficient manner is a challenging task. To this end, we propose a novel market-based resource allocation framework in which the services act as buyers and fog resources act as divisible goods in the market. The proposed framework aims to compute a market equilibrium (ME) solution at which every service obtains its favorite resource bundle under the budget constraint, while the system achieves high resource utilization. This paper extends the general equilibrium literature by considering a practical case of satiated utility functions. In addition, we introduce the notions of non-wastefulness and frugality for equilibrium selection and rigorously demonstrate that all the non-wasteful and frugal ME are the optimal solutions to a convex program. Furthermore, the proposed equilibrium is shown to possess salient fairness properties, including envy-freeness, sharing-incentive, and proportionality. Another major contribution of this paper is to develop a privacy-preserving distributed algorithm, which is of independent interest, for computing an ME while allowing market participants to obfuscate their private information. Finally, extensive performance evaluation is conducted to verify our theoretical analyses.