INFOCOM 2017 Papers

In a mobile crowdsensing (MCS) application, user diversity and social effect are two important phenomena that determine its profitability, where the former improves the sensing quality, while the latter incentives the users' participation. In this paper, we consider a reward mechanism design for the service provider to achieve diversity in the collected data by exploiting the users' social relationship. Specifically, we formulate a two-stage decision problem, where the service provider first optimizes its rewards for profit maximization. The users then decide their effort levels through social network interactions as a participation game. The analysis is particularly challenging due to the users' interplay in both the diversity and social graphs, which leads to a non-convex bilevel optimization problem. Surprisingly, we find that the service provider can focus on one superimposed graph that incorporates the diversity and social relationship and compute the optimal reward as the Katz centrality in closed-form. Simulation results, based on the random graph and a real Facebook trace, show that the availability of network information improves both the service provider's profit and the users' social surplus over the incomplete information cases.

Flash deal applications, which offer significant benefits (e.g., discount) to subscribers within a short period of time, are becoming increasingly prevalent. Motivated by such transient profit, flash crowds of subscribers request services simultaneously. Considering the unique business logic, a hybrid cloud with soft guarantee, i.e., bounding the response time of delay-tolerant requests, has great potential to handle flash crowds. In this paper, to cost-effectively withstand flash crowds with soft guarantee, we propose a solution that makes smart decisions on scheduling requests in the hybrid cloud and adjusting the capacity of the public cloud. In respect of scheduling requests, we apply Sequential Quadratic Programming (SQP) to achieve soft guarantee. Furthermore, for adjusting capacity, we design an online algorithm to tune the scale of the public cloud towards jointly minimizing cost and response time, yet without a priori knowledge of request arrival rate. We prove that the online algorithm can obtain a competitive ratio of 1-6ε against the optimal solution, where ε can be tuned close to 0. By conducting extensive trace-driven experiments in a website prototype deployed on OpenStack Mitaka and Amazon Web Service, our solution reduces response time by 15% compared with previous work under given budget.

A coflow is a collection of parallel flows belonging to the same job. It has the all-or-nothing property: a coflow is not complete until the completion of all its constituent flows. In this paper, we focus on optimizing coflow-level delay, i.e., the time to complete all the flows in a coflow, in the context of an N × N input-queued switch. In particular, we develop a throughput-optimal scheduling policy that achieves the best scaling of coflow-level delay as N → ∞. We first derive lower bounds on the coflow-level delay that can be achieved by any scheduling policy. It is observed that these lower bounds critically depend on the variability of flow sizes. Then we analyze the coflow-level performance of some existing coflow-agnostic scheduling policies and show that none of them achieves provably optimal performance with respect to coflow-level delay. Finally, we propose the Coflow-Aware Batching (CAB) policy which achieves the optimal scaling of coflow-level delay under some mild assumptions.

We consider a problem of how to effectively diffuse a new product over social networks by incentivizing selfish users. Traditionally, this problem has been studied in the form of influence maximization via seeding, where most prior work assumes that seeded users unconditionally and immediately start by adopting the new product and they stay at the new product throughout their lifetime. However, in practice, seeded users often adjust the degree of their willingness to diffuse, depending on how much incentive is given. To address such diffusion willingness, we propose a new incentive model and characterize the speed of diffusion as the value of a combinatorial optimization. Then, we apply the characterization to popular network graph topologies (Erdos-Renyi, planted partition and power law graphs) as well as general ones, for asymptotically computing the diffusion time for those graphs. Our analysis shows that the diffusion time undergoes two levels of order-wise reduction, where the first and second one are solely contributed by the number of seeded users, i.e., quantity, and the amount of incentives, i.e., quality, respectively. In other words, it implies that the best strategy given budget is (a) first identify the minimum seed set depending on the underlying graph topology, and (b) then assign largest possible incentives to users in the set. We believe that our theoretical results provide useful implications and guidelines for designing successful advertising strategies in various practical applications.

Industrial automation has emerged as an important application of wireless sensor-actuator networks (WSANs). To meet stringent reliability requirements of industrial applications, industrial standards such as WirelessHART adopt Time Slotted Channel Hopping (TSCH) as its MAC protocol. Since every link hops through all the channels used in TSCH, a straightforward policy to ensure reliability is to retain a link in the network topology only if it is reliable in all channels used. However, this policy has surprising side effects. While using more channels may enhance reliability due to channel diversity, more channels may also reduce the number of links and route diversity in the network topology. We empirically analyze the impact of channel selection on network topology, routing, and scheduling on a 52-node WSAN testbed. We observe inherent tradeoff between channel diversity and route diversity in channel selection, where using an excessive number of channels may negatively impact routing and scheduling. We propose novel channel and link selection strategies to improve route diversity and network schedulability. Experimental results on two different testbeds show that our algorithms can drastically improve routing and scheduling of industrial WSANs.

LTE evolved Multimedia Broadcast/Multicast Service (eMBMS) is an attractive solution for video delivery to very large groups in crowded venues. However, deployment and management of eMBMS systems is challenging, due to the lack of realtime feedback from the User Equipment (UEs). Therefore, we present the Dynamic Monitoring (DyMo) system for low-overhead feedback collection. DyMo leverages eMBMS for broadcasting Stochastic Group Instructions to all UEs. These instructions indicate the reporting rates as a function of the observed Quality of Service (QoS). This simple feedback mechanism collects very limited QoS reports from the UEs. The reports are used for network optimization, thereby ensuring high QoS to the UEs. We present the design aspects of DyMo and evaluate its performance analytically and via extensive simulations. Specifically, we show that DyMo infers the optimal eMBMS settings with extremely low overhead, while meeting strict QoS requirements under different UE mobility patterns and presence of network component failures. For instance, DyMo can detect the eMBMS Signal-to-Noise Ratio (SNR) experienced by the 0.1% percentile of the UEs with Root Mean Square Error (RMSE) of 0.05% with only 5 to 10 reports per second regardless of the number of UEs.

Communication costs dominate the energy consumption, and ultimately limit the utility, of low power devices and sensor nodes. Backscatter communication based on deliberate and ambient sources has the potential to radically alter this paradigm by offering two to three orders of magnitude better communication efficiency (in terms of nJ/Bit) then conventional radio architectures. Initial work on ambient backscatter shows promising results but has focused on narrow band operation in well controlled laboratory settings. The goal of this work is to enable the ubiquitous deployment of ultra-low power nodes that communicate via ambient backscatter to wired Universal Backscatter Readers, in real-world environments. This is accomplished through ultra-wideband backscatter techniques that leverage the breath of commercial broadcast signals in the 80 MHz to 900 MHz range from FM radios, digital TVs, and cellular networks. Additionally the use of powered Universal Backscatter Readers allows a network of ultra-low power nodes to operate on ambient carriers as low as -80 dBm, which is typical for indoor home and office environments. For the first time we demonstrate the simultaneous use of 17 ambient signal sources to achieve node-to-reader communication distances of 50 meters, with data rates up to 1 kbps.

In addition to providing substantial performance enhancements, future 5G networks will also change the mobile network ecosystem. Building on the network slicing concept, 5G allows to “slice” the network infrastructure into separate logical networks that may be operated independently and targeted at specific services. This opens the market to new players: the infrastructure provider, which is the owner of the infrastructure, and the tenants, which may acquire a network slice from the infrastructure provider to deliver a specific service to their customers. In this new context, we need new algorithms for the allocation of network resources that consider these new players. In this paper, we address this issue by designing an algorithm for the admission and allocation of network slices requests that (i) maximises the infrastructure provider's revenue and (ii) ensures that the service guarantees provided to tenants are satisfied. Our key contributions include: (i) an analytical model for the admissibility region of a network slicing-capable 5G Network, (ii) the analysis of the system (modelled as a Semi-Markov Decision Process) and the optimisation of the infrastructure provider's revenue, and (iii) the design of an adaptive algorithm (based on Q-learning) that achieves close to optimal performance.

Detecting anomalous traffic is a critical task for advanced Internet management. The traditional approaches based on Principal Component Analysis (PCA) are effective only when the corruption is caused by small additive i.i.d. Gaussian noise. The recent Direct Robust Matrix Factorization (DRMF) is proven to be more robust and accurate in anomaly detection, but it incurs a high computation cost due to its need of singular value decomposition (SVD) for low-rank matrix approximation and the iterative use of SVD execution to find the final solution. To enable the anomaly detection for large traffic matrix with the use of DRMF, we formulate the low-rank matrix approximation problem as a problem of searching for the subspace to project the traffic matrix with the minimum error. We propose a novel approach, LSH-subspace, for fast low-rank matrix approximation. To facilitate the matrix partition for the quick search of the subspace, we propose several novel techniques: a multi-layer locality sensitive hashing (LSH) table to reorder the OD pairs based on LSH function, a partition principle to guide the partition to minimize the projection error, and a lightweight algorithm to exploit the sparsity of the outlier matrix to update the LSH table at low overhead. Our extensive simulations based on real trace data demonstrate that our LSH-subspace is 3 times faster than DRMF with high anomaly detection accuracy.

The exponentially increasing number of IoT devices makes the unlicensed industrial, scientific, and medical (ISM) radio bands (e.g., 2.4 GHz) extremely crowded. Currently, there is no efficient solution to coordinate the large amount heterogeneous IoT devices that have different communication technologies (e.g., WiFi and ZigBee). To fill this gap, in this paper, we introduce embedded multiple flows (EMF) communication method, which (i) embeds different pieces of information in existing traffic and (ii)concurrently sends out these information from one IoT sender to multiple IoT receivers that have a different communication technology from the sender. By doing this, our EMF method (i) enables cross-technology communication among heterogeneous IoT devices, (ii) does not introduce any extra control traffic, and (iii) is transparent to the higher layer applications. Our approach is implemented on USRPs and commercial off-the-shelf (COTS) ZigBee devices. We also conducted extensive experiments to evaluate our approach in real-world settings. The evaluation results show that EMF's throughput is more than 14 times higher than the latest cross-technology communication technique (i.e. FreeBee[1]).