State-of-the-art covert routing in heterogeneous networks (HetNets) focuses on balancing covertness and throughput, but often overlooks explicit energy optimization. While covert communication inherently limits transmit power, meeting throughput demands without coordinated design can still lead to high energy consumption. To this end, we propose DECOR, Decentralized Energy-efficient COvert Routing framework that jointly optimizes covertness, throughput, and energy efficiency. Unlike traditional methods that use a single wireless technology, DECOR leverages the diversity of available wireless communication technologies in HetNet to enable simultaneous multi-modal routing. The core idea behind DECOR is that optimal simultaneous utilization of multiple modalities improves throughput and overall energy efficiency. It minimizes the end-to-end energy consumption while satisfying stringent constraints on throughput and covertness through two core steps: (1)link-level optimizationusing sequential least squares programming (SLSQP), and (2)network-level optimizationthrough a custom cluster-based routing strategy. DECOR introduces a novel clustering-based strategy that aggregates intra-cluster link information and delegates routing decisions to cluster heads, significantly reducing control overhead and enabling scalable, energy-efficient covert communication. Extensive numerical analysis demonstrates that DECOR significantly outperforms existing approaches in terms of energy-efficiency and data overhead.

The past decade has witnessed significant progress in next-generation wireless networks. Resilient routing is essential for maintaining reliability in mission-critical network services, particularly in dynamic and adversarial environments. Traditional traffic engineering (TE) approaches rely on pre-computed paths. Still, they face performance limitations when the number of pre-computed paths is small and scalability challenges when the number is large. This study seeks to answer the fundamental question:“How can we achieve throughput-guaranteed resilient routing under network failures without pre-computing routing paths?”We propose AEGIS, a novel throughput-guaranteed resilient routing scheme leveraging a conditional value-at-risk (CVaR) approach, which proactively guarantees the required throughput under normal conditions and enables recovery during network failures. Specifically, we propose an optimization problem that minimizes the CVaR of total throughput loss across all the failure situations while respecting user budget and network constraints. The above optimization problem is non-differentiable and non-linear; we then reformulate it as an equivalent linear program (LP) and develop an optimal solution. However, the above solution will induce cyclic flows due to resource reservation behaviors. To achieve a more resource-efficient routing, we propose a bisection approach to obtain a CVaR upper bound so that the corresponding routing is acyclic. Extensive numerical evaluations demonstrate the trade-offs among various approaches and highlight the advantages of AEGIS.

A significant challenge for computation offloading in wireless multi-hop networks is the complex interactions among traffic flows in the presence of interference. Existing approaches often ignore these key effects and/or rely on outdated queueing and channel state information. To fill these gaps, we reformulate joint offloading and routing as a routing problem on an extended graph with physical and virtual links. We adopt the state-of-the-art shortest path-biased Backpressure routing algorithm, which allows the destination and the route of a job to be dynamically adjusted at every time step based on network-wide long-term information and real-time states of local neighborhoods. In large networks, our approach achieves smaller makespan than existing approaches, such as separated Backpressure offloading, and joint offloading and routing based on linear programming.

This paper proposes an efficient approach to joint task offloading and routing for real-time sensor data analytics at the network edge, enabling applications such as video surveillance and environmental monitoring. This problem can be formulated as a mixed-integer program (MIP) with the objective of utility maximization subject to the constraints of network topology, limited link capacity, and diverse task profiles. To efficiently approximate this NP-hard problem, we propose SeLR, a combination of primal-dual optimization and reweighted L1-norm regularization, which iteratively solves the convex relaxation while penalizing constraint violations and encouraging sparsity. Compared to greedy heuristics, SeLR provides a better accuracy—latency trade-off and better scalability to larger problems. Moreover, it reduces scheduling runtime by up to 9.17× over optimal solvers in networks with 300 nodes and 100 tasks.

Markov Decision Processes (MDPs) serve as the mathematical foundation of Reinforcement learning (RL), where a Markov process with defined states is used to model the system and the actions to be taken affect the state transitions and the corresponding rewards. The RL and deep RL (DRL) can produce the high-performing action policy to maximize the long-term reward. Although RL/DRL have been widely applied to communication and computer systems, a key limitation is that the system under consideration often does not satisfy the required mathematical properties, thus making the MDP inexact and the derived policy flawed. Therefore, we consider the periodic Markov Decision Process (pMDP), where the evolution of the underlying process and model parameters for the pMDP demonstrate some forms of periodic characteristics (e.g., periodic job arrivals and available resources) which violate the Markov property. To obtain the optimal policies for the pMDP, a policy gradient method with a multi-policy solution framework is proposed, and a deep-learning method is developed to improve the effectiveness and stability of the proposed solution. Furthermore, a layer-sharing strategy is proposed to reduce the storage complexity by reducing the number of parameters in the neural networks. The deep-learning method is applied to achieve the near-optimal allocation of resources to arriving computational tasks in a network setting corresponding to the software-defined network (SDN). Evaluation results reveal that the proposed technique is valid and capable of outperforming a baseline method that employs a single policy by 31% on average.

Federated learning (FL) is a useful tool that enables the training of machine learning models over distributed data without having to collect data centrally. When deploying FL in constrained wireless environments, however, intermittent connectivity of devices, heterogeneous connection quality, and non-i.i.d. data can severely slow convergence. In this paper, we consider FL with arbitrary device participation probabilities for each round and show that by weighing each device’s update by the reciprocal of their per-round participation probability, we can guarantee convergence to a stationary point. Our bound applies to non-convex loss functions and non-i.i.d. datasets and recovers state-of-the-art convergence rates for both full and uniform partial participation, including linear speedup, with only a single-sided learning rate. Then, using the derived convergence bound, we develop a new online client selection and power allocation algorithm that utilizes the Lyapunov drift-plus-penalty framework to opportunistically minimize a function of the convergence bound and the average communication time under a transmit power constraint. We use optimization over manifold techniques to obtain a solution to the minimization problem. Thanks to the Lyapunov framework, one key feature of the algorithm is that knowledge of the channel distribution is not required and only the instantaneous channel state information needs to be known. Using the CIFAR-10 dataset with varying levels of data heterogeneity, we show through simulations that the communication time can be significantly decreased using our algorithm compared to uniformly random participation, especially for heterogeneous channel conditions.

Today, DNS exfiltration attacks are detected by checking for anomalies present in the traffic, such as unusu-ally high transmission rates to a single domain and/or DNS query patterns that are very different from those in benign queries. While such approaches are seemingly robust, we show in this paper that our carefully designed and novel DNS exfiltration attack, Dolos, that uses a generative adversarial network (GAN), can guide the encoding of sensitive data in a manner that both evades these detectors and significantly speeds up the exfiltration rate compared to prior methods. At its core, Dolos divides the exfiltration data into smaller chunks, and projects each chunk into a representation that is very similar to benign queries. In addition, Dolosadaptively tunes its exfiltration rate to conform with benign DNS traffic from the compromised host, and introduces proper levels of spurious traffic to reduce entropy. Importantly, Dolos evades machine learning (ML) based detectors with no prior knowledge of their architectures or training sets (i.e., it is a blackbox exfiltration). We perform extensive evaluations using multiple datasets and also have a real im-plementation of DOLOS. Our evaluations show that DOLOS has a 12% detection probability even if 6 out of the 9 state-of-the-art defenses that we consider, are jointly used to detect exfiltration; if any of today's baseline exfiltration techniques try to achieve the same rate as Dolos in this setting, they are almost surely detected. If we reduce the rates of the baselines to achieve even a low albeit slightly higher detection probability than Dolos (0.15), we see that they take 25 x longer to achieve the exfiltration. With the other three defenses, we find that baselines are almost surely detected while Dolos remains relatively unaffected regardless of the rate of exfiltration.

When making decisions in a network, it is important to have up-to-date knowledge of the current state of the system. Obtaining this information, however, comes at a cost. In this paper, we determine the optimal finite-time update policy for monitoring the binary states of remote sources with a reporting rate constraint. We first prove an upper and lower bound of the minimal probability of error before solving the problem analytically. The error probability is defined as the probability that the system performs differently than it would with full system knowledge. More specifically, an error occurs when the destination node incorrectly determines which top- K priority sources are in the “free” state. We find that the optimal policy follows a specific ordered 3-stage update pattern. We then provide the optimal transition points for each stage for each source.

Abstract In this work, we explore multiplex graph (networks with different types of edges) generation with deep generative models. We discuss some of the challenges associated with multiplex graph generation that make it a more difficult problem than traditional graph generation. We propose TenGAN, the first neural network for multiplex graph generation, which greatly reduces the number of parameters required for multiplex graph generation. We also propose 3 different criteria for evaluating the quality of generated graphs: a graph-attribute-based, a classifier-based, and a tensor-based method. We evaluate its performance on 4 datasets and show that it generally performs better than other existing statistical multiplex graph generative models. We also adapt HGEN, an existing deep generative model for heterogeneous information networks, to work for multiplex graphs and show that our method generally performs better.

Federated learning (FL) enables distributed model training from local data collected by users. In distributed systems with constrained resources and potentially high dynamics, e.g., mobile edge networks, the efficiency of FL is an important problem. Existing works have separately considered different configurations to make FL more efficient, such as infrequent transmission of model updates, client subsampling, and compression of update vectors. However, an important open problem is how to jointly apply and tune these control knobs in a single FL algorithm, to achieve the best performance by allowing a high degree of freedom in control decisions. In this paper, we address this problem and propose FlexFL – an FL algorithm with multiple options that can be adjusted flexibly. Our FlexFL algorithm allows both arbitrary rates of local computation at clients and arbitrary amounts of communication between clients and the server, making both the computation and communication resource consumption adjustable. We prove a convergence upper bound of this algorithm. Based on this result, we further propose a stochastic optimization formulation and algorithm to determine the control decisions that (approximately) minimize the convergence bound, while conforming to constraints related to resource consumption. The advantage of our approach is also verified using experiments.

Given a tensor that captures temporal data, such as (user, item, time), the way that we set the granularity of the “time” mode can make or break our analysis of the data. If we set the granularity to be extremely fine, we end up with a very sparse and high-rank tensor which is essentially incompatible with what virtually all tensor decomposition models expect, i.e., tensors with low-rank structure, which can be expressed in some form of factorization. Traditionally, this problem has been avoided by setting the granularity of the “time” to a “reasonable” aggregation (say hourly or daily intervals), an approach which has certainly served tensor analysis of temporal methods well so far. However, such an approach requires tedious trial- and-error experimentation across a number of such fixed aggregations, where typically the one that provides the most sensible results is retained, and furthermore it is arbitrary, since the optimal aggregation over time need not necessarily be uniform. In our work, we directly tackle this problem. We introduce Harvester, the first principled factorization-based approach which seeks to identify the best temporal granularity of a given tensor. Unlike existing methods which follow a greedy approach, Harvester leverages multiple aggregated views of the tensor, and a carefully-designed optimization problem, in order to uncover an aggregation of a tensor which has a “good” structure for factor analysis or a downstream task. We extensively evaluate Harvester on synthetic and real data, and demonstrate that it consistently produces tensors of very high quality, compared to the state-of-the-art, across the board for a number of different popular quality measures that have been used by the community.

While most networks have long lifetimes, temporary network infrastructure is often useful for special events, pop-up retail, or disaster response. Aninstant IoTnetwork is one that is rapidly constructed, used for a few days, then dismantled. We consider the synthesis of instant IoT networks in urban settings. This synthesis problem must satisfy complex and competing constraints: sensor coverage, line-of-sight visibility, and network connectivity. The central challenge in our synthesis problem is quicklyscalingto large regions while producing cost-effective solutions. We explore two qualitatively different representations of the synthesis problems using satisfiability modulo convex optimization (SMC), and mixed-integer linear programming (MILP). The former is more expressive, for our problem, than the latter, but is less well-suited for solving optimization problems like ours. We show how to express our network synthesis in these frameworks. To scale to problem sizes beyond what these frameworks are capable of, we develop ahierarchical synthesistechnique that independently synthesizes networks in sub-regions of the deployment area, then combines these. We find that, while MILP outperforms SMC in some settings for smaller problem sizes, the fact that SMC's expressivity matches our problem ensures that it uniformly generates better quality solutions at larger problem sizes.

Crowdsourced image processing has the potential to vastly impact response timeliness in various emergency situations. Because images can provide extremely important information regarding an event of interest (hits), sending the right images to an analyzer as soon as possible is of crucial importance. In this paper, we consider the problem of optimally assigning resources, both local (CPUs in phones) and remote (network-based GPUs) to mobile devices for processing images, ultimately sending those of interest to a centralized entity while also accounting for the energy consumption at the distributed nodes. To that end, we use the dual-path Network Utility Maximization (NUM) framework, coupled with a hit-ratio estimator and energy costs, to enable a distributed implementation of the system. We include analysis of different hit-ratio estimators using realistic trace data, first considering immediate and then delayed feedback. We address accuracy concerns when estimating the likelihood of future imagehitsand provide a window-based heuristic for scenarios when hit-ratio feedback is severely delayed. Our TCP-inspired window-method predicts both imagehitlikelihood and current wireless network congestion with great effectiveness. Results are validated using both synthetic simulations and real-life traces.

Federated learning (FL) is a useful tool in distributed machine learning that utilizes users’ local datasets in a privacy-preserving manner. When deploying FL in a constrained wireless environment; however, training models in a time-efficient manner can be a challenging task due to intermittent connectivity of devices, heterogeneous connection quality, and non-i.i.d. data. In this paper, we provide a novel convergence analysis of non-convex loss functions using FL on both i.i.d. and non-i.i.d. datasets with arbitrary device selection probabilities for each round. Then, using the derived convergence bound, we use stochastic optimization to develop a new client selection and power allocation algorithm that minimizes a function of the convergence bound and the average communication time under a transmit power constraint. We find an analytical solution to the minimization problem. One key feature of the algorithm is that knowledge of the channel statistics is not required and only the instantaneous channel state information needs to be known. Using the FEMNIST and CIFAR-10 datasets, we show through simulations that the communication time can be significantly decreased using our algorithm, compared to uniformly random participation.

We consider the problem of computing the$k$k-means centers for a large high-dimensional dataset in the context of edge-based machine learning, where data sources offload machine learning computation to nearby edge servers.$k$k-Means computation is fundamental to many data analytics, and the capability of computing provably accurate$k$k-means centers by leveraging the computation power of the edge servers, at a low communication and computation cost to the data sources, will greatly improve the performance of these analytics. We propose to let the data sources send small summaries, generated by joint dimensionality reduction (DR), cardinality reduction (CR), and quantization (QT), to support approximate$k$k-means computation at reduced complexity and communication cost. By analyzing the complexity, the communication cost, and the approximation error of$k$k-means algorithms based on carefully designed composition of DR/CR/QT methods, we show that: (i) it is possible to compute near-optimal$k$k-means centers at a near-linear complexity and a constant or logarithmic communication cost, (ii) the order of applying DR and CR significantly affects the complexity and the communication cost, and (iii) combining DR/CR methods with a properly configured quantizer can further reduce the communication cost without compromising the other performance metrics. Our theoretical analysis has been validated through experiments based on real datasets.

Online advertisers have been quite successful in circumventing traditional adblockers that rely on manually curated rules to detect ads. As a result, adblockers have started to use machine learning (ML) classifiers for more robust detection and blocking of ads. Among these, AdGraph which leverages rich contextual information to classify ads, is arguably, the state of the art ML-based adblocker. In this paper, we present a4, a tool that intelligently crafts adversarial ads to evade AdGraph. Unlike traditional adversarial examples in the computer vision domain that can perturb any pixels (i.e., unconstrained), adversarial ads generated by a4 are actionable in the sense that they preserve the application semantics of the web page. Through a series of experiments we show that a4 can bypass AdGraph about 81% of the time, which surpasses the state-of-the-art attack by a significant margin of 145.5%, with an overhead of <20% and perturbations that are visually imperceptible in the rendered webpage. We envision that a4’s framework can be used to potentially launch adversarial attacks against other ML-based web applications.

Generative adversarial networks (GANs) are often billed as "universal distribution learners", but precisely what distributions they can represent and learn is still an open question. Heavy-tailed distributions are prevalent in many different domains such as financial risk-assessment, physics, and epidemiology. We observe that existing GAN architectures do a poor job of matching the asymptotic behavior of heavy-tailed distributions, a problem that we show stems from their construction. Additionally, common loss functions produce unstable or near-zero gradients when faced with the infinite moments and large distances between outlier points characteristic of heavy-tailed distributions. We address these problems with the Pareto GAN. A Pareto GAN leverages extreme value theory and the functional properties of neural networks to learn a distribution that matches the asymptotic behavior of the marginal distributions of the features. We identify issues with standard loss functions and propose the use of alternative metric spaces that enable stable and efficient learning. Finally, we evaluate our proposed approach on a variety of heavy-tailed datasets.

Mobile devices collect a large amount of visual data that are useful for many applications. Searching for an object of interest over a network of mobile devices can aid human analysts in a variety of situations. However, processing the information on these devices is a challenge owing to the high computational complexity of the state-of-the-art computer vision algorithms that primarily rely on Convolutional Neural Networks (CNNs). Thus, this paper builds PicSys, a system that enables answering visual search queries on a mobile network. The objective of the system is to minimize the maximum completion time over all devices while taking into account the energy consumption of mobile devices as well. First, PicSys carefully divides the computation into multiple filtering stages, such that only a small percentage of images need to run the entire CNN pipeline. Splitting such CNN computation into multiple stages requires understanding the intermediate CNN features and systematically trading off accuracy for the computation speed. Second, PicSys determines where to run each of the stages of the multi-stage pipeline to fully utilize the available resources. Finally, through extensive experimentation, system implementation, and simulation, we show that PicSys performance is close to optimal and significantly outperforms other standard algorithms.

Convolutional Neural Networks (ConvNets/CNNs) have revolutionized the research in computer vision, due to their ability to capture complex patterns, resulting in high inference accuracies. However, the increasingly complex nature of these neural networks means that they are particularly suited for server computers with powerful GPUs. We envision that deep learning applications will be eventually widely deployed on mobile devices, e.g., smartphones, self-driving cars, and drones. Therefore, in this paper, we aim to understand the resource requirements of CNNs on mobile devices in terms of compute time, memory, and power. First, by deploying several popular CNNs on different mobile CPUs and GPUs, we measure and analyze the performance and resource usage for the CNNs on a layerwise granularity. Our findings point out the potential ways of optimizing the CNN pipelines on mobile devices. Second, we model resource requirements of core computations of CNNs. Finally, based on the measurement and modeling, we build and evaluate our modeling tool, Augur, which takes a CNN configuration (descriptor) as the input and estimates the compute time, memory, and power requirements of the CNN, to give insights about whether and how efficiently a CNN can be run on a given mobile platform.

Mobile edge computing provides the opportunity for wireless users to exploit the power of cloud computing without a large communication delay. To serve data-intensive applications (e.g., video analytics, machine learning tasks) from the edge, we need, in addition to computation resources, storage resources for storing server code and data as well as network bandwidth for receiving user-provided data. Moreover, due to time-varying demands, the code and data placement needs to be adjusted over time, which raises concerns of system stability and operation cost. In this paper, we address these issues by proposing a two-time-scale framework that jointly optimizes service (code and data) placement and request scheduling, while considering storage, communication, computation, and budget constraints. First, by analyzing the hardness of various cases, we completely characterize the complexity of our problem. Next, we develop a polynomial-time service placement algorithm by formulating our problem as a set function optimization, which attains a constant-factor approximation under certain conditions. Furthermore, we develop a polynomial-time request scheduling algorithm by computing the maximum flow in a carefully constructed auxiliary graph, which satisfies hard resource constraints and is provably optimal in the special case where requests have homogeneous resource demands. Extensive synthetic and trace-driven simulations show that the proposed algorithms achieve 90% of the optimal performance.

As Deep Packet Inspection (DPI) middleboxes become increasingly popular, a spectrum of adversarial attacks have emerged with the goal of evading such middleboxes. Many of these attacks exploit discrepancies between the middlebox network protocol implementations, and the more rigorous/complete versions implemented at end hosts. These evasion attacks largely involve subtle manipulations of packets to cause different behaviours at DPI and end hosts, to cloak malicious network traffic that is otherwise detectable. With recent automated discovery, it has become prohibitively challenging to manually curate rules for detecting these manipulations. In this work, we propose CLAP, the first fully-automated, unsupervised ML solution to accurately detect and localize DPI evasion attacks. By learning what we call the packet context, which essentially captures inter-relationships across both (1) different packets in a connection; and (2) different header fields within each packet, from benign traffic traces only, CLAP can detect and pinpoint packets that violate the benign packet contexts (which are the ones that are specially crafted for evasion purposes). Our evaluations with 73 state-of-the-art DPI evasion attacks show that CLAP achieves an Area Under the Receiver Operating Characteristic Curve (AUCROC) of 0.963, an Equal Error Rate (EER) of only 0.061 in detection, and an accuracy of 94.6% in localization. These results suggest that CLAP can be a promising tool for thwarting DPI evasion attacks.

Traditional network topology inference aims at reconstructing the routing trees rooted at each probing source from end-to-end measurements. However, due to emerging technologies such as network function virtualization, software defined networking, and segment routing, many modern networks are capable of supporting generalized forwarding that can create complex routing topologies different from routing trees. In this work, we take a first step towards closing this gap by proposing methods to infer the routing topology (referred to as 1-1-N topology) from a single source to multiple destinations, where routes may be required to traverse a given waypoint. We first thoroughly study the special case of 1-1-2 topologies, showing that even this seemingly simple case is highly nontrivial with 36 possibilities. We then demonstrate how the solution to the special case can be used as building blocks to infer 1-1-N topologies. The inferred topology is proved to be equivalent to the ground truth up to splitting/combining edges in the same category.

Advances in optimization and constraint satisfaction techniques, together with the availability of elastic computing resources, have spurred interest in large-scale network verification and synthesis. Motivated by this, we consider the top-down synthesis of ad-hoc IoT networks for disaster response and search and rescue operations. This synthesis problem must satisfy complex and competing constraints: sensor coverage, line-of-sight visibility, and network connectivity. The central challenge in our synthesis problem is quickly scaling to large regions while producing cost-effective solutions. We explore a representation of the synthesis problems using a novel constraint satisfaction paradigm, satisfiability modulo convex optimization (SMC). We choose SMC because it matches the expressivity needs for our network synthesis. To scale to large problem sizes, we develop a hierarchical synthesis technique that independently synthesizes networks in sub-regions of the deployment area, then combines these. Our experiments show that SMC consistently generates better quality solutions than a baseline synthesis approach based on Mixed Integer Linear Programming (MILP).

We consider the problem of computing the k-means centers for a large high-dimensional dataset in the context of edge-based machine learning, where data sources offload machine learning computation to nearby edge servers. k-Means computation is fundamental to many data analytics, and the capability of computing provably accurate k-means centers by leveraging the computation power of the edge servers, at a low communication and computation cost to the data sources, will greatly improve the performance of these analytics. We propose to let the data sources send small summaries, generated by joint dimensionality reduction (DR) and cardinality reduction (CR), to support approximate k-means computation at reduced complexity and communication cost. By analyzing the complexity, the communication cost, and the approximation error of k-means algorithms based on state-of-the-art DR/CR methods, we show that: (i) in the single-source case, it is possible to achieve a near-optimal approximation at a near-linear complexity and a constant communication cost, (ii) in the multiple-source case, it is possible to achieve similar performance at a logarithmic communication cost, and (iii) the order of applying DR and CR significantly affects the complexity and the communication cost. Our findings are validated through experiments based on real datasets.

Contested and dynamic environments such as those of military operations and crisis situations have poor and unreliable network conditions and participants usually only have an incomplete, local, and quickly changing view of the system. In such systems, optimizing how nodes communicate such that important messages arrive in a timely manner without degrading network performance is critical. SMARTNet is a middleware that prioritizes and controls the messages sent by each node, with the aim of preserving network bandwidth, while at the same time achieving timely delivery of messages within a contested and dynamic environment. In this industry experience report, we propose the integration of evolutionary algorithms with the SMARTNet middleware allowing it to learn the best bandwidth ratio for each different message type. We propose a centralized integration, where a single node performs the evolutionary algorithm (EA) and determines a communication strategy that is subsequently followed by all SMARTNet nodes. Our results show an improvement of nearly 50% over the baseline, at a cost of significant pre-run preparation for the EA to converge on a potential solution. Our analysis also shows the benefits of using an application-specific metric as an objective of the EA, and our discussion identifies new research avenues.

We address energy-efficient placement of data and analytics components of composite analytics services on a wireless network to minimize execution-time energy consumption (computation and communication) subject to compute, storage and network resource constraints. We introduce an expressive analytics service hypergraph model for representing k-ary composability relationships (k ≥ 2) between various analytics and data components and leverage binary quadratic programming (BQP) to minimize the total energy consumption of a given placement of the analytics hypergraph nodes on the network subject to resource availability constraints. Then, after defining a potential energy functional Φ(·) to model the affinities of analytics components and network resources using analogs of attractive and repulsive forces in physics, we propose a decentralized Metropolis Monte Carlo (MMC) sampling method which seeks to minimize Φ by moving analytics and data on the network. Although Φ is non-convex, using a potential game formulation, we identify conditions under which the algorithm provably converges to a local minimum energy equilibrium placement configuration. Trace-based simulations of the placement of a deep-neural-network analytics service on a realistic wireless network show that for smaller problem instances our MMC algorithm yields placements with total energy within a small factor of BQP and more balanced workload distributions; for larger problems, it yields low-energy configurations while the BQP approach fails.

Crowdsourced image processing has the potential to vastly impact response timeliness in various emergency situations. Because images can provide extremely important information regarding an event of interest, sending the right images to an analyzer as soon as possible is of crucial importance. In this paper, we consider the problem of optimally assigning resources, both local (CPUs in phones) and remote (network-based GPUs) to mobile devices for processing images, ultimately sending those of interest to a centralized entity while also accounting for the energy consumption. To that end, we use the Network Utility Maximization (NUM) framework, coupled with a hit-ratio estimator and energy costs, to enable a distributed implementation of the system. Our results are validated using both synthetic simulations and real-life traces.

Coreset, which is a summary of the original dataset in the form of a small weighted set in the same sample space, provides a promising approach to enable machine learning over distributed data. Although viewed as a proxy of the original dataset, each coreset is only designed to approximate the cost function of a specific machine learning problem, and thus different coresets are often required to solve different machine learning problems, increasing the communication overhead. We resolve this dilemma by developing robust coreset construction algorithms that can support a variety of machine learning problems. Motivated by empirical evidence that suitably-weighted k -clustering centers provide a robust coreset, we harden the observation by establishing theoretical conditions under which the coreset provides a guaranteed approximation for a broad range of machine learning problems, and developing both centralized and distributed algorithms to generate coresets satisfying the conditions. The robustness of the proposed algorithms is verified through extensive experiments on diverse datasets with respect to both supervised and unsupervised learning problems.

The rapid development of network function virtualization (NFV) enables a communication network to provide in-network services using virtual network functions (VNFs) deployed on general IT hardware. While existing studies on NFV focused on how to provision VNFs from the provider's perspective, little is done about how to validate the provisioned resources from the user's perspective. In this work, we take a first step towards this problem by developing an inference framework designed to “look into” the NFV network. Our framework infers the structure and state of the overlay formed by VNF instances, ingress/egress points of measurement flows, and critical points on their paths (branching/joining points). Our solution only uses external observations such as the required service chains and the end-to-end performance measurements. Besides the novel application scenario, our work also fundamentally advances the state of the art on topology inference by considering (i) general topologies with general measurement paths, and (ii) information of service chains. Our evaluations show that the proposed solution significantly improves both the reconstruction accuracy and the inference accuracy over existing solutions, and service chain information is critical in revealing the structure of the underlying topology.

The vast adoption of mobile devices with cameras has greatly contributed to the proliferation of the creation and distribution of videos. For a variety of purposes, valuable information may be extracted from these videos. While the computational capability of mobile devices has greatly improved recently, video processing is still a demanding task for mobile devices. We design an on-demand video processing system, NetVision, that performs distributed video processing using deep learning across a wireless network of mobile and edge devices to answer queries while minimizing the query response time. However, the problem of minimal query response time for processing videos stored across a network is a strongly NP-hard problem. To deal with this, we design a greedy algorithm with bounded performance. To further deal with the dynamics of the transmission rate between mobile and edge devices, we design an adaptive algorithm. We built NetVision and deployed it on a small testbed. Based on the measurements of the testbed and by extensive simulations, we show that the greedy algorithm is close to the optimum and the adaptive algorithm performs better with more dynamic transmission rates. We then perform experiments on the small testbed to examine the realized system performance in both stationary networks and mobile networks.

We introduce a new online learning framework where, at each trial, the learner is required to select a subset of actions from a given known action set. Each action is associated with an energy value, a reward and a cost. The sum of the energies of the actions selected cannot exceed a given energy budget. The goal is to maximise the cumulative profit, where the profit obtained on a single trial is defined as the difference between the maximum reward among the selected actions and the sum of their costs. Action energy values and the budget are known and fixed. All rewards and costs associated with each action change over time and are revealed at each trial only after the learner’s selection of actions. Our framework encompasses several online learning problems where the environment changes over time; and the solution trades-off between minimising the costs and maximising the maximum reward of the selected subset of actions, while being constrained to an action energy budget. The algorithm that we propose is efficient and general that may be specialised to multiple natural online combinatorial problems.

Motivated by the need of solving machine learning problems over distributed datasets, we explore the use of \emph{coreset} to reduce the communication overhead. Coreset is a summary of the original dataset in the form of a small weighted set in the same sample space. Compared to other data summaries, coreset has the advantage that it can be used as a proxy of the original dataset. However, existing coreset construction algorithms are each tailor-made for a specific machine learning problem. Thus, to solve different machine learning problems, one has to collect coresets of different types, defeating the purpose of saving communication overhead. We resolve this dilemma by developing robust coreset construction algorithms based on k-means/median clustering, that give a provably good approximation for a broad range of machine learning problems with sufficiently continuous cost functions. Through evaluations on diverse datasets and machine learning problems, we verify the robust performance of the proposed algorithms.

Network topology plays an important role in many network operations. However, it is very difficult to obtain the topology of public networks due to the lack of internal cooperation. Network tomography provides a powerful solution that can infer the network routing topology from end-to-end measurements. Existing solutions all assume that routes from a single source form a tree. However, with the rapid deployment of Software Defined Networking (SDN) and Network Function Virtualization (NFV), the routing paths in modern networks are becoming more complex. To address this problem, we propose a novel inference problem, called the weight inference problem, which infers the finest-granularity information from end-to-end measurements on general routing paths in general topologies. Our measurements are based on emulated multicast probes with a controllable “width”. We show that the problem has a unique solution when the multicast width is unconstrained; otherwise, we show that the problem can be treated as a sparse approximation problem, which allows us to apply variations of the pursuit algorithms. Simulations based on real network topologies show that our solution significantly outperforms a state-of-the-art network tomography algorithm, and increasing the width of multicast substantially improves the inference accuracy.

We study how emotions influence norm outcomes in decision-making contexts. Following the literature, we provide baseline Dynamic Bayesian models to capture an agent's two perspectives on a directed norm. Unlike the literature, these models are holistic in that they incorporate not only norm outcomes and emotions but also trust and goals. We obtain data from an empirical study involving game play with respect to the above variables. We provide a step-wise process to discover two new Dynamic Bayesian models based on maximizing log-likelihood scores with respect to the data. We compare the new models with the baseline models to discover new insights into the relevant relationships. Our empirically supported models are thus holistic and characterize how emotions influence norm outcomes better than previous approaches.

Mobile edge computing allows wireless users to exploit the power of cloud computing without the large communication delay. To serve data-intensive applications (e.g., augmented reality, video analytics) from the edge, we need, in addition to CPU cycles and memory for computation, storage resource for storing server data and network bandwidth for receiving user-provided data. Moreover, the data placement needs to be adapted over time to serve time-varying demands, while considering system stability and operation cost. We address this problem by proposing a two-time-scale framework that jointly optimizes service (data & code) placement and request scheduling, under storage, communication, computation, and budget constraints. We fully characterize the complexity of our problem by analyzing the hardness of various cases. By casting our problem as a set function optimization, we develop a polynomial-time algorithm that achieves a constant-factor approximation under certain conditions. Extensive synthetic and trace-driven simulations show that the proposed algorithm achieves 90% of the optimal performance.

The rapid development of network function virtualization (NFV) enables a communication network to provide in-network services using virtual network functions (VNFs) deployed on general IT hardware. While existing studies on NFV focused on how to provision VNFs from the provider's perspective, little is known about how to validate the provisioned resources from the user's perspective. In this work, we take a first step towards this problem by developing an inference framework designed to “look into” the NFV network. Our framework infers the structure and state of the overlay formed by VNF instances, ingress/egress points of measurement flows, and critical points on their paths (branching/joining points). Our solution only uses external observations such as the required service chains and the end-to-end performance measurements. Besides the novel application scenario, our work also fundamentally advances the state of the art on topology discovery by considering (i) general topologies with general measurement paths, and (ii) information of service chains. Evaluations based on real network topologies show that the proposed solution significantly improves the accuracy over existing solutions, and service chaining information is critical in revealing the structure of the underlying topology.

We consider assignment policies that allocate resources to users, where both resources and users are located on a one-dimensional line (0, ∞). First, we consider unidirectional assignment policies that allocate resources only to users located to their left. We propose the Move to Right (MTR) policy, which scans from left to right assigning the nearest available resource located to the right of a user, and contrast it to the Unidirectional Gale-Shapley (UGS) matching policy. While both policies among all unidirectional policies, minimize the expected distance traveled by a request, MTR is fairer. Moreover, we show that when user and resource locations are modeled by statistical point processes, and resources are allowed to satisfy more than one user, the spatial system under unidirectional policies can be mapped into bulk service queueing systems, thus allowing the application of many queueing theory results that yield closed form expressions. As we consider a case where different resources can satisfy different numbers of users, we also generate new results for bulk service queues. We also consider bidirectional policies where there are no directional restrictions on resource allocation and develop an algorithm for computing the optimal assignment which is more efficient than known algorithms in the literature when there are more resources than users. Finally, numerical evaluation of performance of unidirectional and bidirectional allocation schemes yields design guidelines beneficial for resource placement.

Detecting activities from video taken with a single camera is an active research area for ML-based machine vision. In this paper, we examine the next research frontier: near real-time detection of complex activities spanning multiple (possibly wireless) cameras, a capability applicable to surveillance tasks. We argue that a system for such complex activity detection must employ a hybrid design: one in which rule-based activity detection must complement neural network based detection. Moreover, to be practical, such a system must scale well to multiple cameras and have low end-to-end latency. Caesar, our edge computing based system for complex activity detection, provides an extensible vocabulary of activities to allow users to specify complex actions in terms of spatial and temporal relationships between actors, objects, and activities. Caesar converts these specifications to graphs, efficiently monitors camera feeds, partitions processing between cameras and the edge cluster, retrieves minimal information from cameras, carefully schedules neural network invocation, and efficiently matches specification graphs to the underlying data in order to detect complex activities. Our evaluations show that Caesar can reduce wireless bandwidth, on-board camera memory, and detection latency by an order of magnitude while achieving good precision and recall for all complex activities on a public multi-camera dataset.

Software defined networking (SDN) can be beneficial in mobile ad hoc networks (MANETs) to increase flexibility, provide programmability and simplify management. The high dynamics in mobile networks, however, raise new reliability challenges to the conventional centralized control plane of SDN. To increase reliability, methods such as placing multiple controllers in the network have been considered that add redundancy in the control plane in a brute force manner. However, these methods cannot by themselves fundamentally solve the reliability problem. To address this issue, this paper complements the controller placement methods with a new architecture that has a hybrid structure splitting the routing decision logic between the controllers and the data plane nodes. Specifically, the controllers can break the routing path into segments, similar to the segment routing technique, and broadcast the list of segment labels to the data plane nodes. The latter are able to make the actual forwarding decisions for each segment in a distributed manner, e.g., by running an existing MANET protocol like OLSR. Experiments on a testbed built from commercial mobile devices with integrated SDN functionality highlight the feasibility and benefits of the proposed architecture.

Emerging technologies and applications including Internet of Things, social networking, and crowd-sourcing generate large amounts of data at the network edge. Machine learning models are often built from the collected data, to enable the detection, classification, and prediction of future events. Due to bandwidth, storage, and privacy concerns, it is often impractical to send all the data to a centralized location. In this paper, we consider the problem of learning model parameters from data distributed across multiple edge nodes, without sending raw data to a centralized place. Our focus is on a generic class of machine learning models that are trained using gradient-descent-based approaches. We analyze the convergence bound of distributed gradient descent from a theoretical point of view, based on which we propose a control algorithm that determines the best tradeoff between local update and global parameter aggregation to minimize the loss function under a given resource budget. The performance of the proposed algorithm is evaluated via extensive experiments with real datasets, both on a networked prototype system and in a larger-scale simulated environment. The experimentation results show that our proposed approach performs near to the optimum with various machine learning models and different data distributions.

Mobile devices such as smartphones are enabling users to generate and share videos with increasing rates. In some cases, these videos may contain valuable information, which can be exploited for a variety of purposes. However, instead of centrally collecting and processing videos for information retrieval, we consider crowdprocessing videos, where each mobile device locally processes stored videos. While the computational capability of mobile devices continues to improve, processing videos using deep learning, i.e., convolutional neural networks, is still a demanding task for mobile devices. To this end, we design and build CrowdVision, a computing platform that enables mobile devices to crowdprocess videos using deep learning in a distributed and energy-efficient manner leveraging cloud offload. CrowdVision can quickly and efficiently process videos with offload under various settings and different network connections and greatly outperform the existing computation offload framework (e.g., with a 2× speed-up). In doing so, CrowdVision tackles several challenges: (i) how to exploit the characteristics of the computing of deep learning for video processing; (ii) how to parallelize processing and offloading for acceleration; and (iii) how to optimize both time and energy at runtime by just determining the right moments to offload.

In mobile edge computing, local edge servers can host cloud-based services, which reduces network overhead and latency but requires service migrations as users move to new locations. It is challenging to make migration decisions optimally because of the uncertainty in such a dynamic cloud environment. In this paper, we formulate the service migration problem as a Markov decision process (MDP). Our formulation captures general cost models and provides a mathematical framework to design optimal service migration policies. In order to overcome the complexity associated with computing the optimal policy, we approximate the underlying state space by the distance between the user and service locations. We show that the resulting MDP is exact for the uniform 1-D user mobility, while it provides a close approximation for uniform 2-D mobility with a constant additive error. We also propose a new algorithm and a numerical technique for computing the optimal solution, which is significantly faster than traditional methods based on the standard value or policy iteration. We illustrate the application of our solution in practical scenarios where many theoretical assumptions are relaxed. Our evaluations based on real-world mobility traces of San Francisco taxis show the superior performance of the proposed solution compared to baseline solutions.

Previous work has shown that selectivity based on opinions and values of attributes is an important tie-formation mechanism in human social networks. Less well-known is how selectivity influences the formation and composition of whole groups in which interactions extend beyond the dyads. To address this question, we use data from the NetSense study consisting of a multi-layer (nomination, communication, co-location) network of university students. We examine how group formation differs from tie-formation in terms of the role of selectivity based on opinions and attributes. In addition, we show how levels of such selectivity varies between groups formed to meet different needs.

Many modern applications generate a significant amount of data in dispersed geographical areas. To analyze and make use of the data, data fusion and machine learning techniques are usually applied, which has the potential to greatly enhance the amount of information extracted from the data. These algorithms traditionally run in data center environments where all the data are available at a central location. It is challenging to run them in distributed coalition environments, where it is impractical to send all the raw data to a single place due to bandwidth and security constraints. This problem has gained notable attention recently. In this paper, we provide an overview of available techniques and recent results of performing data fusion and machine learning in a distributed coalition environment, without sharing the raw data among local processing nodes. We discuss techniques for distributed model training, scoring, and outline some applications where these techniques are applicable and beneficial.

This work considers performance analysis of chaff-based traffic obfuscation against a passive adversary aiming to obtain contextual information, e.g. such as the protocol being used. The obfuscation could be either in terms of chaff bytes which are dummy bytes appended to packets of the intended traffic stream, or chaff packets which are dummy packets again inserted in specific intervals of the original packet stream. Despite consisting of dummy bytes, chaff deployment still results in additional resource consumption and potential drawbacks, and hence has to be deployed in a controlled manner. We first define notions of vulnerability of traffic patterns in terms of contextual privacy. Next, we fix the adversary and focus on optimal allocation of the chaff resources among the traffic to be obfuscated. For adversaries which perform statistical characterization based on packet sizes and interarrival times, we derive chaff placement algorithms based on the waterfilling algorithm commonly used in the field of information theory. We apply our derived algorithms to representative real-world scenarios to obfuscate certain applications vulnerable to contextual privacy leakage.

Mobile devices such as smartphones are enabling users to generate and share videos with increasing rates. In some cases, these videos may contain valuable information, which can be exploited for a variety of purposes. However, instead of centrally collecting and processing videos for information retrieval, we consider crowdprocessing videos, where each mobile device locally processes stored videos. While the computational capability of mobile devices continues to improve, processing videos using deep learning, i.e., convolutional neural networks, is still a demanding task for mobile devices. To this end, we design and build CrowdVision, a computing platform that enables mobile devices to crowdprocess videos using deep learning in a distributed and energy-efficient manner leveraging cloud offload. CrowdVision can quickly and efficiently process videos with offload under various settings and different network connections and greatly outperform the existing computation offload framework (e.g., with a 2× speed-up). In doing so CrowdVision tackles several challenges: (i) how to exploit the characteristics of the computing of deep learning for video processing; (ii) how to parallelize processing and offloading for acceleration; and (iii) how to optimize both time and energy at runtime by just determining the right moments to offload.

Emerging technologies and applications including Internet of Things (IoT), social networking, and crowd-sourcing generate large amounts of data at the network edge. Machine learning models are often built from the collected data, to enable the detection, classification, and prediction of future events. Due to bandwidth, storage, and privacy concerns, it is often impractical to send all the data to a centralized location. In this paper, we consider the problem of learning model parameters from data distributed across multiple edge nodes, without sending raw data to a centralized place. Our focus is on a generic class of machine learning models that are trained using gradient-descent based approaches. We analyze the convergence rate of distributed gradient descent from a theoretical point of view, based on which we propose a control algorithm that determines the best trade-off between local update and global parameter aggregation to minimize the loss function under a given resource budget. The performance of the proposed algorithm is evaluated via extensive experiments with real datasets, both on a networked prototype system and in a larger-scale simulated environment. The experimentation results show that our proposed approach performs near to the optimum with various machine learning models and different data distributions.

Edge servers, which are small servers located close to mobile users, have the potential to greatly reduce delay and backhaul traffic of mobile Internet applications by moving cloud services to the edge of the network. Due to limited capacity of edge servers and dynamic request arrival, proper service caching at the edge is essential to guarantee good performance. This paper proposes a tractable online algorithm called retrospective download with least-requested deletion that caches services dynamically without any assumptions on the arrival patterns of mobile applications. We evaluate the competitive ratio of our policy, which quantifies the worst case performance in comparison to an optimal offline policy. We prove that the competitive ratio of our policy is linear with the capacity of the edge server. We also show that no deterministic online policy can achieve a competitive ratio that is asymptotically better than ours. Moreover, we prove that our policy is scalable, in the sense that it only needs doubled capacity to achieve a constant competitive ratio. The utility of our online policy is further evaluated on real-world traces. These trace-based simulations demonstrate that our policy has better, or similar, performance compared with many intelligent offline policies.

In this paper, we consider user location privacy in mobile edge clouds (MECs). MECs are small clouds deployed at the network edge to offer cloud services close to mobile users, and many solutions have been proposed to maximize service locality by migrating services to follow their users. Co-location of a user and his service, however, implies that a cyber eavesdropper observing service migrations between MECs can localize the user up to one MEC coverage area, which can be fairly small (e.g., a femtocell). We consider using chaff services to defend against such an eavesdropper, with focus on strategies to control the chaffs. Assuming the eavesdropper performs maximum likelihood (ML) detection, we consider both heuristic strategies that mimic the user's mobility and optimized strategies designed to minimize the detection or tracking accuracy. We show that a single chaff controlled by the optimal strategy can drive the eavesdropper's tracking accuracy to zero when the user's mobility is sufficiently random. The efficacy of our solutions is verified through extensive simulations.

Convolutional Neural Networks (CNNs) have revolutionized the research in computer vision, due to their ability to capture complex patterns, resulting in high inference accuracies. However, the increasingly complex nature of these neural networks means that they are particularly suited for server computers with powerful GPUs. We envision that deep learning applications will be eventually and widely deployed on mobile devices, e.g., smartphones, self-driving cars, and drones. Therefore, in this paper, we aim to understand the resource requirements (time, memory) of CNNs on mobile devices. First, by deploying several popular CNNs on mobile CPUs and GPUs, we measure and analyze the performance and resource usage for every layer of the CNNs. Our findings point out the potential ways of optimizing the performance on mobile devices. Second, we model the resource requirements of the different CNN computations. Finally, based on the measurement, profiling, and modeling, we build and evaluate our modeling tool, Augur, which takes a CNN configuration (descriptor) as the input and estimates the compute time and resource usage of the CNN, to give insights about whether and how efficiently a CNN can be run on a given mobile platform. In doing so Augur tackles several challenges: (i) how to overcome profiling and measurement overhead; (ii) how to capture the variance in different mobile platforms with different processors, memory, and cache sizes; and (iii) how to account for the variance in the number, type and size of layers of the different CNN configurations.

We study the problem of network topology design within a set of policy-compliant topologies as a game between a designer and an adversary. At any time instant, the designer aims to operate the network in an optimal topology within the set of policy compliant topologies with respect to a desired network property. Simultaneously, the adversary counters the designer trying to force operation in a suboptimal topology. Specifically, if the designer and the attacker choose the same link in the current topology to defend/grow and attack, respectively, then the latter is thwarted. However, if the defender does not correctly guess where the attacker is going to attack, and, hence, acts elsewhere, the topology reverts to the best policy-compliant configuration after a successful attack. We show the existence of various mixed strategy equilibria in this game and systematically study its structural properties. We study the effect of parameters, such as probability of a successful attack, and characterize the steady state behavior of the underlying Markov chain. While the intuitive adversarial strategy here is to attack the most important links, the Nash equilibrium strategy is for the designer to defend the most crucial links and for the adversary to focus attack on the lesser crucial links. We validate these properties through two use cases with example sets of network topologies. Next, we consider a multi-stage framework where the designer is not only interested in the instantaneous network property costs but a discounted sum of costs over many time instances. We establish structural properties of the equilibrium strategies in the multi-stage setting, and also demonstrate that applying algorithms based on the Q-Learning and Rollout methods can result in significant benefits for the designer compared with strategies resulting from a one-shot based game.

In this paper, we consider user location privacy in mobile edge clouds (MECs). MECs are small clouds deployed at the network edge to offer cloud services close to mobile users, and many solutions have been proposed to maximize service locality by migrating services to follow their users. Co-location of a user and his service, however, implies that a cyber eavesdropper observing service migrations between MECs can localize the user up to one MEC coverage area, which can be fairly small (e.g., a femtocell). We consider using chaff services to defend against such an eavesdropper, with a focus on strategies to control the chaffs. Assuming the eavesdropper performs maximum likelihood detection, we consider both heuristic strategies that mimic the user's mobility and optimized strategies designed to minimize the detection or tracking accuracy. We show that a single chaff controlled by the optimal strategy or its online variation can drive the eavesdropper's tracking accuracy to zero when the user's mobility is sufficiently random. We further propose extended strategies that utilize randomization to defend against an advanced eavesdropper aware of the strategy. The efficacy of our solutions is verified through both synthetic and trace-driven simulations.

Mobile micro-clouds are promising for enabling performance-critical cloud applications. However, one challenge therein is the dynamics at the network edge. In this paper, we study how to place service instances to cope with these dynamics, where multiple users and service instances coexist in the system. Our goal is to find the optimal placement (configuration) of instances to minimize the average cost overtime, leveraging the ability of predicting future cost parameters with known accuracy. We first propose an offline algorithm that solves for the optimal configuration in a specific look-ahead time-window. Then, we propose an online approximation algorithm with polynomial time-complexity to find the placement in real-time whenever an instance arrives. We analytically show that the online algorithm is 0(1)-competitive for a broad family of cost functions. Afterwards, the impact of prediction errors is considered and a method for finding the optimal look-ahead window size is proposed, which minimizes an upper bound of the average actual cost. The effectiveness of the proposed approach is evaluated by simulations with both synthetic and real-world (San Francisco taxi) usermobility traces. The theoretical methodology used in this paper can potentially be applied to a larger class of dynamic resource allocation problems.

With the proliferation of fairly powerful mobile devices and ubiquitous wireless technology, we see a transformation from traditional mobile ad hoc networks (MANETs) into a new era of service-oriented MANETs wherein a node can provide and receive services. Requested services must be decomposed into more abstract services and then bound; we formulate this as a multi-objective optimization (MOO) problem to minimize the service cost, while maximizing the quality of service and quality of information in the service a user receives. The MOO problem is an SP-to-service assignment problem. We propose a multidimensional trust based algorithm to solve the problem. We carry out an extensive suite of simulations to test the relative performance of the proposed trust-based algorithm against a non-trust-based counterpart and an existing single-trust-based beta reputation scheme. Our proposed algorithm effectively filters out malicious nodes exhibiting various attack behaviors by penalizing them with loss of reputation, which ultimately leads to high user satisfaction. Further, our proposed algorithm is efficient with linear runtime complexity while achieving a close-to-optimal solution.

In social networks, individuals and systems work side by side. While individuals make decisions to filter or forward information, systems also prioritize and sort information to manage and assist individual information processing. It has long been argued that system level manipulations can reduce access of individuals to novel information. In this paper, we study how sorting of messages in one's inbox can help or hinder access of diverse information in the network through simulation of cognitively bounded actors. We show that first-in-first-out (FIFO) method of message sorting is ideal in bursty information arrival rates and in networks with lower diameter. Last-in-first-out (LIFO) method of message sorting is ideal for streaming information arrival, but leads to information overload in bursty scenarios by creating too many redundant copies of some of the information in the network. In short, the ideal message sorting method that enhances access to diverse information depends on the network type and information access patterns.

The vast adoption of mobile devices with cameras has greatly assisted in the proliferation of the creation and distribution of videos. For a variety of purposes, valuable information may be extracted from these videos. While the computational capability of mobile devices has greatly improved recently, video processing is still a demanding task for mobile devices. Given a network consisting of mobile devices and video-clouds, mobile devices may be able to upload videos to video-clouds, which are more computationally capable for these processing tasks. However, due to networking constraints, when a video processing task is initiated through a query, most videos will not likely have been uploaded to the video-clouds, especially when the query is about a recent event. We investigate the problem of minimal query response time for processing videos stored across a network; however, this problem is a strongly NP-hard problem. To deal with this, we first propose a greedy algorithm with bounded performance. To further deal with the dynamics of the transmission rate between mobile devices and video-clouds, we propose an adaptive algorithm. To evaluate these algorithms, we built an on-demand video processing system. Based on the measurements of the system, we perform simulations to extensively evaluate the proposed algorithms. We also perform experiments on a small testbed to examine the realized system performance. Results show the performance of the greedy algorithm is close to the optimal and much better than other approaches, and the adaptive algorithm performs better with more dynamic transmission rates.

"Edge-clouds," which are small servers located close to mobile users, have the potential to greatly reduce delay and backhaul traffic of mobile applications by moving cloud services closer to users at the edge. Due to their limited storage capacity, proper configurations of edge-clouds have a significant impact on their performance. This paper proposes a tractable online algorithm that configures edge-clouds dynamically solely based on past system history without any assumptions on the arrival patterns of mobile applications. We evaluate the competitive ratio, which quantifies the worst-case performance in comparison to an optimal offline policy, of our policy. We prove that the competitive ratio of our policy is linear with the capacity of the edge-cloud. Moreover, we also prove that no deterministic online policy can achieve a competitive ratio that is asymptotically better than ours. The utility of our online policy is further evaluated by traces from real-world data centers. These trace-based simulations demonstrate that our policy has better, or similar, performance compared to many intelligent offline policies that have complete knowledge of all future arrivals.

We study the problem of network topology design within a sequence of policy-compliant topologies as a game between a designer and an adversary. At any time instant, the designer aims to operate the network in an optimal topology within this policy compliant sequence with respect to a desired network property. Simultaneously, the adversary counters the designer trying to force operation in a suboptimal topology. We show the existence of various mixed strategy equilibria in this game and systematically study its structural properties. We study the effect of parameters, and characterize the steady state behavior of the underlying Markov chain. While the intuitive adversarial strategy here is to attack links appearing early in the topology sequence, the Nash Equilibrium strategy is for the designer to defend the earlier links and for the adversary to attack the later links. We validate these properties through two use cases with example sets of network topologies.

Seamless computing and data access is enabled by the emerging technology of mobile micro-clouds (MMCs). Different from traditional centralized clouds, an MMC is typically connected directly to a wireless base-station and provides services to a small group of users, which allows users to have instantaneous access to cloud services. Due to the limited coverage area of base-stations and the dynamic nature of mobile users, network background traffic, etc., the question of where to place the services to cope with these dynamics arises. In this paper, we focus on dynamic service placement for MMCs. We consider the case where there is an underlying mechanism to predict the future costs of service hosting and migration, and the prediction error is assumed to be bounded. Our goal is to find the optimal service placement sequence which minimizes the average cost over a given time. To solve this problem, we first propose a method which solves for the optimal placement sequence for a specific look-ahead time-window, based on the predicted costs in this time-window. We show that this problem is equivalent to a shortest-path problem and propose an algorithm with polynomial time-complexity to find its solution. Then, we propose a method to find the optimal look-ahead window size, which minimizes an upper bound of the average cost. Finally, we evaluate the effectiveness of the proposed approach by simulations with realworld user-mobility traces.

We study the dynamic service migration problem in mobile edge-clouds that host cloud-based services at the network edge. This offers the benefits of reduction in network overhead and latency but requires service migrations as user locations change over time. It is challenging to make these decisions in an optimal manner because of the uncertainty in node mobility as well as possible non-linearity of the migration and transmission costs. In this paper, we formulate a sequential decision making problem for service migration using the framework of Markov Decision Process (MDP). Our formulation captures general cost models and provides a mathematical framework to design optimal service migration policies. In order to overcome the complexity associated with computing the optimal policy, we approximate the underlying state space by the distance between the user and service locations. We show that the resulting MDP is exact for uniform one-dimensional mobility while it provides a close approximation for uniform two-dimensional mobility with a constant additive error term. We also propose a new algorithm and a numerical technique for computing the optimal solution which is significantly faster in computation than traditional methods based on value or policy iteration. We illustrate the effectiveness of our approach by simulation using real-world mobility traces of taxis in San Francisco.

A temporary coalition is often formed to pursue a common goal based on the collaboration of multiple partners who may have their own objectives. The coalition network must attain multiple objectives, under resource constraints and time deadlines. We propose a task assignment algorithm for a scenario where tasks are dynamic, with different arrival times and deadlines. We propose a heuristic coalition formation technique that uses multiple dimensions of trust (i.e., integrity, competence, social connectedness, and reciprocity) to assess trust of each entity. The proposed scheme enables task leaders to make critical assignment decisions based on assessed trustworthiness of entities. We consider three different objectives, namely, maximizing resilience and resource utilization while minimizing delay to task completion. We devise a ranking-based heuristic with linear runtime complexity to select members based on risk derived from trust assessment of nodes. We validate the performance of our proposed scheme by comparing our scheme with a non-trust-based baseline scheme as well as a global optimal solution implemented with the Integer Linear Programming technique.

The task of providing security services for wireless sensor networks is not trivial due to the resource constraints of the sensor nodes. An adversary may launch a wide range of attacks including eavesdropping, message forgery, packet dropping, and noise injection. In this paper, we propose random coding security (RCS) that provides protection against all the aforementioned attacks. For this purpose, the proposed protocol makes extensive use of node collaboration and data redundancy. Moreover, using location information, we both localize adversarial activities to the area under attack and enhance routing the data toward the sink. The objectives of using the novel idea of sparse random coding in RCS are twofold. First, every node generates correlated data by calculating random linear combinations of the received packets. Hence, the availability of the data at the receiver is guaranteed with a high probability. The second advantage is the feasibility of implementing the RCS in the real case scenario in which the communication media between the sensors is usually modeled as the erasure channel. The existing protocols cannot be trivially modified to suit this realistic situation. In the overall, RCS provides many security services with computation and communication overheads comparable with other schemes

Hierarchical routing protocols are studied in terms of energy usage, packet latency, and security in the presence of node compromise attacks. We analyze clustering and tree-based structures of hierarchical algorithms to establish a method by which to design wireless sensor networks with particular energy, latency and security demands. Networks of homogeneous nodes and random deployment over a field are considered. We present analysis of the distribution of the distances between nodes of the sensor network and also provide simulations to validate and expound on these ideas.

In this paper, we study connectivity properties of large-scale wireless sensor networks and discuss their effect on routing algorithms. In our model, n sensors are distributed randomly over a field based on a given distribution function. Two sensor nodes are connected with probability p/sub e/(n) if they are within the communication range of each other. The sensor nodes may also be unreliable. We find the necessary and sufficient conditions for the network to be k-connected, where k is a positive integer. We also find the distribution of isolated vertices. While connectivity (i.e, k = 1) insures that all nodes can communicate with each other, k-connectivity for k > 1 is required for multi-path routing. Additionally, it was found that the lengths of these multiple paths in a k-connected network are all close to the shortest path.