INFOCOM 2017 Papers

Event-based Social Networks (EBSNs) which bridge the gap between online and offline interactions among users have received increasing popularity. The unique cold-start nature makes event recommendation more challenging than traditional recommendation problems, since even for two events with the same content, they may not happen at the same time, the same location, or be organized by the same host. Existing event recommendation algorithms mainly exploit the basic context information (e.g., location, time and content), while the social influence of event hosts and group members have been ignored. In this paper, we propose a Social Information Augmented Recommender System (SIARS), which fully exploits the social influence of event hosts and group members together with basic context information for event recommendation. In particular, we combine the information of EBSNs and other social networks to characterize the social influence of event hosts, and take interactions between group members into consideration for event recommendation. In addition, we propose a new content-aware recommendation model using the topic model to find the most similar topic the event belongs to, and a new location-aware recommendation model integrating location popularity with location distribution for event recommendation. Extensive experiments on real-world datasets demonstrate that SIARS outperforms other recommendation algorithms.

One of the most central problems in viral marketing is Influence Maximization (IM), which finds a set of k seed users who can influence the maximum number of users in online social networks. Unfortunately, all existing algorithms to IM, including the state of the art SSA and IMM, have an approximation ratio of (1 - 1/e - ϵ). Recently, a generalization of IM, Cost-aware Target Viral Marketing (CTVM), asks for the most cost-effective users to influence the most relevant users, has been introduced. The current best algorithm for CTVM has an approximation ratio of (1 - 1/√e - ϵ). In this paper, we study the CTVM problem, aiming to optimally solve the problem. We first highlight that using a traditional two stage stochastic programming to exactly solve CTVM is not possible because of scalability. We then propose an almost exact algorithm TIPTOP, which has an approximation ratio of (1 - ϵ). This result significantly improves the current best solutions to both IM and CTVM. At the heart of TIPTOP lies an innovative technique that reduces the number of samples as much as possible. This allows us to exactly solve CTVM on a much smaller space of generated samples using Integer Programming. While obtaining an almost exact solution, TIPTOP is very scalable, running on billion-scale networks such as Twitter under three hours. Furthermore, TIPTOP lends a tool for researchers to benchmark their solutions against the optimal one in large-scale networks, which is currently not available.

In today's always-connected world, we receive a large number of notifications on our mobile devices. These notifications cause interruptions, stress, and even impact users' lifestyle. To understand how users respond to notifications, we develop an application that monitors various features (e.g., importance) of the notifications, users' actions, and the level of users' engagement with the notifications. We recruit 30 users to use the application and monitor over 30 days, and subsequently find that 20% to 50% of the notifications generally get ignored by the users. In addition, we also solicit explicit feedback about the importance of notifications from 12 users over 14 days and identify the relation between perceived importance and users' engagement level. Based on this study, we identify the key characteristics of notifications and users' engagement, which is further substantiated by an onfine survey of 400+ users. In addition, we develop a notification manager that includes a machine learning based prediction model and that shows only the important notifications and delays the unimportant notifications. Our experimental results show that our notification manager automatically assesses the importance of notifications with more than 87% accuracy. We believe this work is a promising step toward intelligent personal assistant that manages notifications.

We study how the so-called Rao-Blackwellization, which is a variance reduction technique via “conditioning” for Monte Carlo methods, can be judiciously applied for graph sampling through neighborhood exploration. Despite its popularity for Monte Carlo methods, it is little known for Markov chain Monte Carlo methods and has never been discussed for random walk-based graph sampling. We first propose two forms of Rao-Blackwellization that can be used as a swap-in replacement for virtually all (reversible) random-walk graph sampling methods, and prove that the ‘Rao-Blackwellized’ estimators reduce the (asymptotic) variances of their original estimators yet maintain their inherent unbiasedness. The variance reduction can translate into lowering the number of samples required to achieve a desired sampling accuracy. However, the sampling cost for neighborhood exploration, if required, may outweigh such improvement, even leading to higher total amortized cost. Considering this, we provide a generalization of Rao-Blackwellization, which allows one to choose a suitable extent of obtaining Rao-Blackwellized samples in order to achieve a right balance between sampling cost and accuracy. We finally provide simulation results via real-world datasets that confirm our theoretical findings.

The proliferation of loT applications drives the need of ubiquitous connections among heterogeneous wireless devices. Cross-Technology Communication (CTC) is a significant technique to directly exchange information among heterogeneous devices that follow different standards. By exploiting a side-channel like frequency, amplitude or temporal modulation, the existing works enable CTC but have limited performance under channel noise. In this paper, we propose WiZig, a novel CTC technique that employs modulation techniques in both the amplitude and temporal dimensions to optimize the throughput over a noisy channel. We establish a theoretical model of the energy communication channel to clearly understand the channel capacity. We then devise an online rate adaptation algorithm to adjust the modulation strategy according to the channel condition. Based on the theoretical model, WiZig can accurately control the number of encoded energy amplitudes and the length of a receiving window, so as to optimize the CTC throughput. We implement a prototype of WiZig on a software radio platform and a commercial ZigBee device. The evaluation show that WiZig achieves a throughput of 153.85 bps with less than 1 % symbol error rate in a real environment. The results demonstrate that WiZig realizes efficient and reliable CTC under varied channel conditions.

We study the problem of scheduling n tasks on m + m' parallel processors, where the processing times on m processors are known while those on the remaining m' processors are not known a priori. This semi-online model is an abstraction of certain heterogeneous computing systems, e.g., with the m known processors representing local CPU cores and the unknown processors representing remote servers with uncertain availability of computing cycles. Our objective is to minimize the makespan of all tasks. We initially focus on the case m' = 1 and propose a semi-online algorithm termed Single Restart with Time Stamps (SRTS), which has time complexity O(n log n). We derive its competitive ratio in comparison with the optimal offline solution. If the unknown processing times are deterministic, the competitive ratio of SRTS is shown to be either always constant or asymptotically constant in practice, respectively in cases where the processing times are independent and dependent on m. A similar result is obtained when the unknown processing times are random. Furthermore, extending the ideas of SRTS, we propose a heuristic algorithm termed SRTS-Multiple (SRTS-M) for the case m' > 1. Besides the proven competitive ratios, simulation results further suggest that SRTS and SRTS-M give superior performance on average over randomly generated task processing times, substantially reducing the makespan over the best known alternatives. Interestingly, the performance gain is more significant for task processing times sampled from heavy-tailed distributions.

The power flow model for DC power grids has been used theoretically to launch false data injection attacks (FDIAs) against state estimation. We recognize FDIAs are just one possible attack using the power flow model and that the grid topology information within the model implies its discovery may also facilitate topology-based attacks. We show attackers can derive the power flow model, and thus the topology also. Indeed, with incomplete data, attackers can accurately reconstruct regions of the model, or topology, all that is necessary to launch an attack. We also illustrate how to cause such attackers to derive instead a convincing fake model by camouflaging the real model. Consequently, no sensitive information will leak, so attacks based on this fake model will be ineffective, rather alerting grid administrators to the attacker's efforts. Using five test cases included in the MATLAB power flow analysis tool MATPOWER, ranging from 9 to 300 buses, an average 67.0% of the topology may be derived with a 69.1% model accuracy. Lastly, we find reconstructions of small portions of the model sufficient for performing FDIAs with 75% success, and that camouflage prevents 93% of them in all but the 9-bus case.

Caching decisions by default seek to maximize some notion of social welfare: the content to be cached is determined so that the maximum possible aggregate demand over all users served by the cache is satisfied. Recommendation systems, on the contrary, are oriented towards user individual preferences: the recommended content should be most appealing to the user so as to elicit further content consumption. In our paper we explore how these, phenomenically conflicting, objectives can be jointly addressed. To this end, we depart radically from current practice with recommender systems, and we approach them as network traffic engineering tools that can actively shape content demand towards optimizing user- and network-centric performance objectives. We formulate the resulting joint theoretical optimization problem of deciding on the cached content and the recommendations to each user so that the cache hit ratio is maximized subject to a maximum tolerable distortion that the recommendation should undergo. We conclude on its complexity, and we propose a practical algorithm for its solution. The algorithm is essentially a form of lightweight control over the user recommendations so that the recommended content is both appealing to the end user and more friendly to the caching system and the network resources.

User location is of critical importance to cellular network operators. It is often used for network capacity planning and to aid in the analysis of service and network diagnostics. However, existing localization techniques rely on user-provided information (e.g., Angle-of-Arrival), which are not available to the operator, and often require a significant effort to collect training data. Our main contribution is the design and evaluation of the Network-Based Localization (NBL) System for localizing a user in a 4G LTE network. The NBL System consists of 2 stages. In an offline stage, we develop RF coverage maps based on a large-scale crowd-sourced channel measurement campaign. Then, in an online stage, we present a localization algorithm to quickly match RF measurements (which are already collected as part of normal network operation) to coverage map locations. The system is more practical than related works, as it does not make any assumptions about user mobility, nor does it require expensive manual training measurements. Despite the realistic assumptions, our extensive evaluations in a national 4G LTE network show that the NBL System achieves a localization accuracy which is comparable to related works (i.e., a median accuracy of 5% of the cell's coverage region).

Conserving the energy consumption of large data centers is of critical significance, where a few percent in consumption reduction translates into millions-dollar savings. This work studies energy conservation on emerging CPU-GPU hybrid clusters through dynamic voltage and frequency scaling (DVFS). We aim at minimizing the total energy consumption of processing a sequence of real-time tasks under deadline constraints. We compute the appropriate voltage/frequency setting for each task through mathematical optimization, and assign multiple tasks to the cluster with heuristic scheduling algorithms. In performance evaluation driven by real-world power measurement traces, our scheduling algorithm shows comparable energy savings to the theoretical upper bound. With a GPU scaling interval where analytically at most 38% of energy can be saved, we record 30-36% of energy savings. Our results are applicable to energy management on modern heterogeneous clusters. In particular, our model stresses the nonlinear relationship between task execution time and processor speed for GPU-accelerated applications, for more accurately capturing real-world GPU energy consumption.

In this paper, we propose to leverage the emerging deep learning techniques for spatiotemporal modeling and prediction in cellular networks, based on big system data. First, we perform a preliminary analysis for a big dataset from China Mobile, and use traffic load as an example to show non-zero temporal autocorrelation and non-zero spatial correlation among neighboring Base Stations (BSs), which motivate us to discover both temporal and spatial dependencies in our study. Then we present a hybrid deep learning model for spatiotemporal prediction, which includes a novel autoencoder-based deep model for spatial modeling and Long Short-Term Memory units (LSTMs) for temporal modeling. The autoencoder-based model consists of a Global Stacked AutoEncoder (GSAE) and multiple Local SAEs (LSAEs), which can offer good representations for input data, reduced model size, and support for parallel and application-aware training. Moreover, we present a new algorithm for training the proposed spatial model. We conducted extensive experiments to evaluate the performance of the proposed model using the China Mobile dataset. The results show that the proposed deep model significantly improves prediction accuracy compared to two commonly used baseline methods, ARIMA and SVR. We also present some results to justify effectiveness of the autoencoder-based spatial model.

The design trade-offs of transceiver hardware are crucial to the performance of wireless systems. In this paper, we present an in-depth study to characterize the surprisingly notable systemic impacts of low-pass filter (LPF) design, which is a small yet indispensable component used for shaping spectrum and rejecting interference. Using a bottom-up approach, we examine how signal-level distortions caused by the trade-off of LPF design propagate to the upper-layers of wireless communication, reshaping bit error patterns and degrading link performance of today's 802.11 systems. Moreover, we propose a novel algorithm that harnesses LPF defects for improving video streaming, which substantially enhances video quality in mobile environments.

Fork-Join (FJ) queueing models capture the dynamics of system parallelization under synchronization constraints, for example, for applications such as MapReduce, multipath transmission and RAID systems. Arriving jobs are first split into tasks and mapped to servers for execution, such that a job can only leave the system when all of its tasks are executed. In this paper, we provide computable stochastic bounds for the waiting and response time distributions for heterogeneous FJ systems under general parallelization benefit. Our main contribution is a generalized mathematical framework for probabilistic server scheduling strategies that are essentially characterized by a probability distribution over the number of utilized servers, and the optimization thereof. We highlight the trade-off between the scaling benefit due to parallelization and the FJ inherent synchronization penalty. Further, we provide optimal scheduling strategies for arbitrary scaling regimes that map to different levels of parallelization benefit. One notable insight obtained from our results is that different applications with varying parallelization benefits result in different optimal strategies. Finally, we complement our analytical results by applying them to various applications showing the optimality of the proposed scheduling strategies.

In small-cell wireless networks where users are connected to multiple base stations (BSs), it is often advantageous to opportunistically switch off a subset of BSs to minimize energy costs. We consider two types of energy cost: (i) the cost of maintaining a BS in the active state, and (ii) the cost of switching a BS from the active state to inactive state. The problem is to operate the network at the lowest possible energy cost (sum of activation and switching costs) subject to queue stability. In this setting, the traditional approach - a Max-Weight algorithm along with a Lyapunov-based stability argument - does not suffice to show queue stability, essentially due to the temporal co-evolution between channel scheduling and the BS activation decisions induced by the switching cost. Instead, we develop a learning and BS activation algorithm with slow temporal dynamics, and a Max-Weight based channel scheduler that has fast temporal dynamics. We show using convergence of time-inhomogeneous Markov chains, that the co-evolving dynamics of learning, BS activation and queue lengths lead to near optimal average energy costs along with queue stability.

The accuracy of measurement-driven mobile coverage maps depends on the quality, density and pattern of the signal strength observations. Thus, identifying an efficient measurement data collection methodology is essential, especially when considering the cost associated with the measurement collection approaches (e.g., drive tests, crowd approaches). We propose ZipWeave, a novel measurement data collection and fusion framework for building efficient and reliable measurement-based mobile coverage maps. ZipWeave incorporates a novel nonuniform sampling strategy to achieve reliable coverage maps with reduced sample size. Assuming prior knowledge of the propagation characteristics of the region of interest, we first examine the potential gains of this non-uniform sampling strategy in different cases via a measurement-based statistical analysis methodology; this involves irregular spatial tessellation of the region of interest into sub-regions with internally similar radio propagation characteristics and sampling based on these sub-regions. We then present a practical form of ZipWeave nonuniform sampling strategy that can be used even without any prior information. In all our evaluations, we show that the ZipWeave non-uniform sampling approach reduces the samples by half compared to the common systematic-random sampling, while maintaining similar accuracy. Moreover, we show that the other key feature of ZipWeave to combine high-quality controlled measurements (that present limited geographic footprint similar to drive tests) with crowdsourced measurements (that cover a wider footprint) leads to more reliable mobile coverage maps overall.

In this paper, we consider a surveillance scenario where a team of sensing robots survey a sensitive area and transmit the monitored data to a remote base station through a mobile relay. In this scenario, it is challenging to autonomously adjust the position of the mobile relay for the sake of minimizing the total communication-motion energy consumption of the system, while maintaining the communication quality of the mobile sensing robots. We first derive the asymptotically optimal transmit powers of the mobile relay and of the sensing robots according to the predefined end-to-end packet error rate (PER) requirement. Then, we propose a joint communication-motion planning (JCMP) method for minimizing the total communication-motion energy consumption in both: single- and multi-sensing-robot scenarios, where the trajectories of the sensing robots are rigorously defined. We further consider the scenario where the sensing robots' trajectories are not fixed but can be optimized in restrained areas. The effectiveness of the proposed JCMP is verified by analysis and numerical results for different system configurations, showing that a substantial energy-efficiency improvement may be achieved in comparison with the benchmark that only optimizes the communication energy consumption.

An important category of mobile crowdsensing applications involve collecting sensor measurements from mobile devices and querying mobile users for annotations to build machine learning models for inference and prediction. Trade-offs between inference performance and the costs of data acquisition (both unlabeled and labeled) are not yet well understood. In this paper, we develop, ALSense, a distributed active learning framework for mobile crowdsensing. The goal is to minimize prediction errors for classification-based mobile crowdsensing tasks subject to upload and query cost constraints. Novel stream-based active learning strategies are developed to orchestrate queries of annotation data and the upload of unlabeled data from mobile devices. We evaluate the effectiveness of ALSense through two applications that can benefit from mobile crowdsensing, namely, WiFi fingerprint-based indoor localization and IMU-based human activity recognition. Extensive experiments demonstrate that ALSense can indeed achieve higher classification accuracy given fixed data acquisition budgets for both applications.

We study learning outcome prediction for online courses. Whereas prior work has focused on semester-long courses with frequent student assessments, we focus on short-courses that have single outcomes assigned by instructors at the end. The lack of performance data makes the behavior of learners, captured as they interact with course content and with one another in Social Learning Networks (SLN), essential for prediction. Our method defines several (machine) learning features based on behaviors collected on the modes of (human) learning in a course, and uses them in appropriate classifiers. Through evaluation on data captured from three two-week courses hosted through our delivery platforms, we make three key observations: (i) behavioral data is predictive of learning outcomes in short-courses (our classifiers achieving AUCs ≥ 0.8 after the two weeks), (ii) it has an early detection capability (AUCs ≥ 0.7 with the first week of data), and (iii) the content features have an “earliest” detection capability (with higher AUC in the first few days), while the SLN features become the more predictive set over time, as the network matures. We also discuss how our method can generate behavioral analytics for instructors.