In this paper, we propose an offline counterfactual policy estimation framework called Genie to optimize Sponsored Search Marketplace. Genie employs an open box simulation engine with click calibration model to compute the KPI impact of any modification to the system. From the experimental results on Bing traffic, we showed that Genie performs better than existing observational approaches that employs randomized experiments for traffic slices that have frequent policy updates. We also show that Genie can be used to tune completely new policies efficiently without creating risky randomized experiments due to cold start problem. As time of today, Genie hosts more than $10000$ optimization jobs yearly which runs more than $30$ Million processing node hours of big data jobs for Bing Ads. For the last 3 years, Genie has been proven to be the one of the major platforms to optimize Bing Ads Marketplace due to its reliability under frequent policy changes and its efficiency to minimize risks in real experiments.

Sensor networks have particularly important applications in challenging environments. However, those challenging environments also pose significant challenges to network sustainability and reliability. In such environments, the network often becomes disruptive and even unavailable during downtime. This results in undesired loss of valuable spatial-temporal sensor data. Data persistence can be achieved by using in-situ encoding and caching of data through distributed mechanisms. However, the existing methods in the literature are mainly based on network random walks, which not only incur significant communication overhead, but also are prone to network or node failures. In this article, we presentECPC, a distributedErasureCoding with randomizedPowerControl protocol for preserving data in disruptive sensor networks.ECPConly requires each sensor node to perform several rounds of broadcast in its neighborhood at some randomly chosen radio transmission power levels, and thus it incurs low communication overhead. We proved thatECPCachieves the expected code degree distribution and pseudo-global randomness of erasure coding principles. We have also evaluated the performance ofECPCby comparing it with several key related approaches in the literature (such as EDFC and RCDS). The performance comparisons validate that our proposedECPCprotocol can reach higher data reliability under varying node failure probabilities. In addition,ECPCprotocol is also shown to be scalable with different network sizes.

Tomography imaging, applied to seismology, requires a new, decentralized approach if high resolution calculations are to be performed in a sensor network configuration. The real-time data retrieval from a network of large-amount wireless seismic nodes to a central server is virtually impossible due to the sheer data amount and resource limitations. In this paper, we present a distributed multi-resolution evolving tomography algorithm for processing data and inverting volcano tomography in the network, while avoiding costly data collections and centralized computations. The new algorithm distributes the computational burden to sensor nodes and performs real-time tomography inversion under the constraints of network resources. We implemented and evaluated the system design in the CORE emulator. The experiment results validate that our proposed algorithm not only balances the computation load, but also achieves low communication cost and high data loss-tolerance.

In challenging environments, sensor networks may become disruptive even unavailable (downtime), resulting in data losses. In-situ encoding and caching data in a distributed fashion can preserve data persistence during downtime. However, the existing approaches are mainly based on random walks, which incurs significant communication overhead and may itself fail due to network disruptions. In this paper, we present a distributed Erasure Coding with randomized Power Control (ECPC) mechanism to preserve downtime data persistence in disruptive sensor networks. ECPC only requires each node to perform a single broadcast at each of its several randomly selected power levels. Thus it incurs low communication overhead. Moreover the storage space requirement is lower and uniform across the network. It applies randomized power control in localized data broadcast to achieve expected code degree distribution and ensure pseudo-global randomness for erasure coding. Performance comparisons between ECPC and other existing approaches show that ECPC mechanism can reach higher data reliability under varying node failure probabilities. In addition, our ECPC approach is scalable with network sizes.

Tomography imaging, applied to seismology, requires a new, decentralized approach if high resolution calculations are to be performed in a sensor network configuration. The real-time data retrieval from a network of large-amount wireless seismic nodes to a central server is virtually impossible due to the sheer data amount and resource limitations. In this paper, we present a distributed multi-resolution evolving tomography algorithm for processing data and inverting volcano tomography in the network, while avoiding costly data collections and centralized computations. The new algorithm distributes the computational burden to sensor nodes and performs real-time tomography inversion under the constraints of network resources. We implemented and evaluated the system design in the CORE emulator. The experiment results validate that our proposed algorithm not only balances the computation load, but also achieves low communication cost and high data loss tolerance.1

Opportunistic network coding has been developed and applied in disruptive networks to provide optimal data delivery. Though network coding system utilizes coding opportunities among multiple paths, its application in data collection suffers from a disconnected sink node and the limited storage space available for data cache. The state-of-the-art approach has studied preserving data persistence as an optimization problem under storage and energy constraints, without considering disruptive network dynamics during data redistribution. In this paper, we propose Ravine Streams (RS) to maximize data preservation under the constraints of limited storage and probabilistic node failure throughout data redistribution. Our RS approach leverages adaptive power control to achieve ensured storage of each redistribution data. Meanwhile, in the course of data redistribution, distributed coding-based rebroadcast strategy not only reduces the data duplication, but also improves the statistical property of symbol randomness. We show that the performance of preserving data persistence of proposed RS is approximately bounded by the optimal solutions. The experimental evaluations demonstrate that RS increases data delivery ratio, consumes even less communication energy with only comparable storage cost, when compared with existing data preserving algorithms.

Disruptive network communication entails transient network connectivity, asymmetric links, and unstable nodes, which pose severe challenges to data collection in sensor networks. Erasure coding can be applied to mitigate the dependency of feedback in such a disruptive network condition, improving data collection. However, the collaborative data collection through an in-network erasure coding approach has been underexplored. In this paper, we present an Opportunistic Network Erasure Coding protocol (ONEC) to collaboratively collect data in dynamic disruptive networks. ONEC derives the probability distribution of coding degree in each node and enables opportunistic in-network recoding, and guarantees that the recovery of original sensor data can be achieved with high probability upon receiving any sufficient amount of encoded packets. First, it develops a recursive decomposition structure to conduct probability distribution deconvolution, supporting heterogeneous data rates. Second, every node conducts selective in-network recoding of its own sensing data and received packets, including those opportunistic overheard packets. Last, ONEC can efficiently recover raw data from received encoded packets, taking advantages of low decoding complexity of erasure codes. We evaluate and show that our ONEC can achieve efficient data collection in various disruptive network settings. Moreover, ONEC outperforms other epidemic network coding approaches in terms of network goodput, communication cost, and energy consumption.

Data collection, redistribution and retrieval are essential components of wireless sensor networks (WSNs). In dense WSN deployments, the sensor data are usually sent to a sink that can be reached through one or multiple hops. In the case where communications with the sink are disrupted due to various reasons, the data must be stored in the network for later retrieval. When considering in-network storage, we must redistribute the data among an energy-constrained network with sensors that have a low storage capacity. In previous works, the data redistribution problem has been studied, but the focus was only on the redistribution costs while the data retrieval costs (which have been analyzed in other works as an independent problem) were ignored. We recognize that these two problems should be studied in concert and therefore, in this paper, we combine both data redistribution and retrieval into a single problem. We propose a graph transformation, formulate the problem as a minimum cost flow optimization problem and use linear programming to find the optimal solution. Moreover, we introduce an algorithm named EDR2: energy-efficient data redistribution and retrieval. EDR2is a distributed energy-efficient algorithm for in-network storage and later retrieval in WSNs. To evaluate our solution on a large scale, we modeled different scenarios in a 400-node network, used the GNU Linear Programming Kit (GLPK) to obtain the optimal solutions, and ran simulations to find the solutions using our algorithm. Finally, we implemented EDR2using real sensors to demonstrate the feasibility of our algorithm. We compared EDR2with two heuristic algorithm and show that our approach is an energy-efficient solution for node selection when redistributing data in a WSN for eventual retrieval.

In this paper we have proposed and designed FindingHuMo (Finding Human Motion), a real-time user tracking system for Smart Environments. FindingHuMo can perform device-free tracking of multiple (unknown and variable number of) users in the Hallway Environments, just from non-invasive and anonymous (not user specific) binary motion sensor data stream. The significance of our designed system are as follows: (a) fast tracking of individual targets from binary motion data stream from a static wireless sensor network in the infrastructure. This needs to resolve unreliable node sequences, system noise and path ambiguity, (b) Scaling for multi-user tracking where user motion trajectories may crossover with each other in all possible ways. This needs to resolve path ambiguity to isolate overlapping trajectories, FindingHumo applies the following techniques on the collected motion data stream: (i) a proposed motion data driven adaptive order Hidden Markov Model with Viterbi decoding (called Adaptive-HMM), and then (ii) an innovative path disambiguation algorithm (called CPDA). Using this methodology the system accurately detects and isolates motion trajectories of individual users. The system performance is illustrated with results from real-time system deployment experience in a Smart Environment.

This paper presents the design, deployment, and evaluation of a real-world sensor network system in an active volcano - Mount St. Helens. In volcano monitoring, the maintenance is extremely hard and system robustness is one of the biggest concerns. However, most system research to date has focused more on performance improvement and less on system robustness. In our system design, to address this challenge, automatic fault detection and recovery mechanisms were designed to autonomously roll the system back to the initial state if exceptions occur. To enable remote management, we designed a configurable sensing and flexible remote command and control mechanism with the support of a reliable dissemination protocol. To maximize data quality, we designed event detection algorithms to identify volcanic events and prioritize the data, and then deliver higher priority data with higher delivery ratio with an adaptive data transmission protocol. Also, a light-weight adaptive linear predictive compression algorithm and localized TDMA MAC protocol were designed to improve network throughput. With these techniques and other improvements on intelligence and robustness based on a previous trial deployment, we air-dropped 13 stations into the crater and around the flanks of Mount St. Helens in July 2009. During the deployment, the nodes autonomously discovered each other even in-the-sky and formed a smart mesh network for data delivery immediately. We conducted rigorous system evaluations and discovered many interesting findings on data quality, radio connectivity, network performance, as well as the influence of environmental factors.

Sensor network has found critical applications in extreme environments. However, in the extreme environments, a predictable and stable path may never exist, since the transient network connectivity, asymmetric links and unstable nodes are prevalent. Thus, the extreme environments severely challenge its basic function of data collection. Particularly, those disruptive conditions make traditional data collection protocols inefficient. In this paper, we design Opportunistic Network Erasure Coding (ONEC) protocol for collaborative data collection in disruptive sensor networks. The idea behind ONEC protocol is to study how each node determines code degree distribution and receding strategies in a distributed fashion, so that all data of network can be recovered with high probability upon receiving any sufficient amount of encoded packets. First, each node derives code degree distribution through recursive discrete deconvolution. Second, every node conducts selective receding of its own sensing data and opportunistically received data. Last, the ONEC ensures decoder can recover all data from any sufficient amount of encoded packets with high probability. The performance evaluations through extensive simulation validate that ONEC can truly achieve efficient data collection with high reliability in disruptive sensor networks and outperform other existing approaches in terms of network goodput, message complexity and buffer space.

In a data collection sensor network, how to maximize the network lifetime through topology control remains an open research problem. Previous work has studied this problem by aiming to build a max-lifetime data collection tree, however, tree-based data collection does not necessarily yield maximum network lifetime. In this paper, we consider collaborative multipath data delivery and formulate the lifetime maximization problem as a max-fair-flow problem, then study how to collaboratively adjust the transmission power of sensor nodes to achieve the maxfair-flow, thus maximizing the network lifetime. We give both theoretical proofs and simulations to validate its correctness and performance.

We present a lightweight lossless compression algorithm for realtime sensor networks. Our proposed adaptive linear filtering compression (ALFC) algorithm performs predictive compression using adaptive linear filtering to predict sample values followed by entropy coding of prediction residuals, encoding a variable number of samples into fixed-length packets. Adaptive prediction eliminates the need to determine prediction coefficients a priori and, more importantly, allows compression to dynamically adjust to a changing source. The algorithm requires only integer arithmetic operations and thus is compatible with sensor platforms that do not support floating-point operations. Significant robustness to packets losses is provided by including small but sufficient overhead data to allow each packet to be independently decoded. Real-world evaluations on seismic data from a wireless sensor network testbed show that ALFC provides more effective compression and uses less resources than an alternative recent work of lossless compression, S-LZW. Experiments in a multi-hop sensor network also show that ALFC can significantly improve raw data throughput and energy efficiency. We also implement the algorithm in our real sensor network, and show that our linear prediction based compression algorithm significantly improves data reliability and network efficiency.

This paper presents the design and deployment experience of an air-dropped wireless sensor network for volcano hazard monitoring. The deployment of five self-contained stations into the rugged crater of Mount St. Helens only took one hour with a helicopter. The stations communicate with each other through an amplified 802.15.4 radio and establish a self-forming and self-healing multihop wireless network. The transmit distance between stations was up to 8 km with favorable topography. Each sensor station collects and delivers real-time continuous seismic, infrasonic, lightning, GPS raw data to a gateway. The main contribution of this paper is the design of a robust sensor network optimized for rapid deployment during periods of volcanic unrest and provide real-time long-term volcano monitoring. The system supports UTC-time-synchronized data acquisition with 1 ms accuracy, and is remotely configurable. It has been tested in the lab environment, the outdoor campus, and the volcano crater. Despite the heavy rain, snow, and ice as well as gusts exceeding 160 km per hour, the sensor network has achieved a remarkable packet delivery ratio above 99 percent with an overall system uptime of about 93.8 percent over the 1.5 months evaluation period after deployment. Our initial deployment experiences with the system demonstrated to discipline scientists that a low-cost sensor network system can support real-time monitoring in extremely harsh environments.

This paper presents the design and deployment experience of an air-dropped wireless sensor network for volcano hazard monitoring. The deployment of five stations into the rugged crater of Mount St. Helens only took one hour with a helicopter. The stations communicate with each other through an amplified 802.15.4 radio and establish a self-forming and self-healing multi-hop wireless network. The distance between stations is up to 2 km. Each sensor station collects and delivers real-time continuous seismic, infrasonic, lightning, GPS raw data to a gateway. The main contribution of this paper is the design and evaluation of a robust sensor network to replace data loggers and provide real-time long-term volcano monitoring. The system supports UTCtime synchronized data acquisition with 1ms accuracy, and is online configurable. It has been tested in the lab environment, the outdoor campus and the volcano crater. Despite the heavy rain, snow, and ice as well as gusts exceeding 120 miles per hour, the sensor network has achieved a remarkable packet delivery ratio above 99 % with an overall system uptime of about 93.8 % over the 1.5 months evaluation period after deployment. Our initial deployment experiences with the system have alleviated the doubts of domain scientists and prove to them that a low-cost sensor network system can support real-time monitoring in extremely harsh environments.

We present a lightweight lossless compression algorithm for realtime sensor networks. Our proposed adaptive linear filtering compression (ALFC) algorithm performs predictive compression, using adaptive linear filtering to predict sample values followed by entropy coding of prediction residuals, encoding a variable number of samples into fixed-length packets. Adaptive prediction eliminates the need to determine prediction coefficients a priori and, more importantly, allows compression to dynamically adjust to a changing source. The algorithm requires only integer arithmetic operations and thus is compatible with sensor platforms that do not support floating-point operations. Significant robustness to packets losses is provided by including small but sufficient overhead data to allow samples in each packet to be independently decoded. Real-world evaluations on seismic data from a wireless sensor network testbed show that ALFC provides more effective compression and uses less resources than some other lossless compression approaches such as S-LZW. Experiments in a multi-hop sensor network also show that ALFC can significantly improve raw data throughput and energy efficiency.

This paper present a wake-on sensor network formed with the wake-on motes, TelosW. Our wake-on hardware and software design enable lower power operations and longer network lifetime.