On k-coverage in a mostly sleeping sensor network
Sensor networks are often desired to last many times longer than the active lifetime of individual sensors. This is usually achieved by putting sensors to sleep for most of their lifetime. On the other hand, surveillance kind of applications require guaranteed k-coverage of the protected region at all times. As a result, determining the appropriate number of sensors to deploy that achieves both goals simultaneously becomes a challenging problem. In this paper, we consider three kinds of deployments for a sensor network on a unit square - a √n x √n grid, random uniform (for all n points), and Poisson (with density n). In all three deployments, each sensor is active with probability p, independently from the others. Then, we claim that the critical value of the function npπr2/log(np) is 1 for the event of k-coverage of every point. We also provide an upper bound on the window of this phase transition. Although the conditions for the three deployments are similar, we obtain sharper bounds for the random deployments than the grid deployment, which occurs due to the boundary condition. In this paper, we also provide corrections to previously published results for the grid deployment model. Finally, we use simulation to show the usefulness of our analysis in real deployment scenarios.

title: Barrier coverage with wireless sensors
abstract: In old times, castles were surrounded by moats (deep trenches filled with water, and even alligators) to thwart or discourage intrusion attempts. One can now replace such barriers with stealthy and wireless sensors. In this paper, we develop theoretical foundations for laying barriers of wireless sensors. We define the notion of k-barrier coverage of a belt region using wireless sensors. We propose efficient algorithms using which one can quickly determine, after deploying the sensors, whether a region is k-barrier covered. Next, we establish the optimal deployment pattern to achieve k-barrier coverage when deploying sensors deterministically. Finally, we consider barrier coverage with high probability when sensors are deployed randomly. We introduce two notions of probabilistic barrier coverage in a belt region -- weak and strong barrier coverage. While weak barrier-coverage with high probability guarantees the detection of intruders as they cross a barrier of stealthy sensors, a sensor network providing strong barrier-coverage with high probability (at the expense of more sensors) guarantees the detection of all intruders crossing a barrier of sensors, even when the sensors are not stealthy. Both types of barrier coverage require significantly less number of sensors than full-coverage, where every point in the region needs to be covered. We derive critical conditions for weak k-barrier coverage, using which one can compute the minimum number of sensors needed to provide weak k-barrier coverage with high probability in a given belt region. Deriving critical conditions for strong k-barrier coverage for a belt region is still an open problem.

title: Minimum Bayes-Risk Decoding for Statistical Machine Translation
abstract: We present Minimum Bayes-Risk (MBR) decoding for statistical machine translation. This statistical approach aims to minimize expected loss of translation errors under loss functions that measure translation performance. We describe a hierarchy of loss functions that incorporate different levels of linguistic information from word strings, word-to-word alignments from an MT system, and syntactic structure from parse-trees of source and target language sentences. We report the performance of the MBR decoders on a Chinese-to-English translation task. Our results show that MBR decoding can be used to tune statistical MT performance for specific loss functions.

title: Bounding blocking probabilities and throughput in queueing networks with buffer capacity constraints
abstract: We propose a new technique for upper and lower bounding of the throughput and blocking probabilities in queueing networks with buffer capacity constraints, i.e., some buffers in the network have finite capacity. By studying the evolution of multinomials of the state of the system in its assumed steady state, we obtain constraints on the possible behavior of the system. Using these constraints, we obtain linear programs whose values upper and lower bound the performance measures of interest, namely throughputs or blocking probabilities. The main advantages of this new technique are that the computational complexity does not increase with the size of the finite buffers and that the technique is applicable to systems in which some buffers have infinite capacity. The technique is demonstrated on examples taken from both manufacturing systems and communication networks. As a special case, for the M/M/s/s queue, we establish the asymptotic exactness of the bounds, i.e., that the bounds on the blocking probability asymptotically approach the exact value as the degree of the multinomials considered is increased to infinity.

title: Scheduling advertisements on a web page to maximize revenue
abstract: Many web sites (e.g. Hotmail, Yahoo) provide free services to the users while generating revenues from advertising. Advertising revenue is, therefore, critical for these sites. This in turn raises the question, how should advertisements at a web site be scheduled in a planning horizon to maximize revenue. Advertisements on the web are specified by geometry and display frequency and both of these factors need to be considered in developing a solution to the advertisement scheduling problem. Since this problem belongs to the class of NP-hard problems, we first develop a heuristic called LSMF to solve the problem. This heuristic is then combined with a genetic algorithm (GA) to develop a hybrid GA. The hybrid GA solution is first compared with the upper bound obtained by running CPLEX for the integer programming formulation of the problem. It is then also compared with an existing algorithm proposed in the literature. Our computational results show that the hybrid GA performs exceptionally well in the sense that it provides optimal or near optimal solution for a wide range of problem instances of realistic sizes and the improvements over existing algorithm are substantial. Finally we present a case study to illustrate how revenue could be significantly increased with a small improvement in the advertisement schedule. It is the first such study in this setup.

title: A hierarchical field framework for unified context-based classification
abstract: We present a two-layer hierarchical formulation to exploit different levels of contextual information in images for robust classification. Each layer is modeled as a conditional field that allows one to capture arbitrary observation-dependent label interactions. The proposed framework has two main advantages. First, it encodes both the short-range interactions (e.g., pixelwise label smoothing) as well as the long-range interactions (e.g., relative configurations of objects or regions) in a tractable manner. Second, the formulation is general enough to be applied to different domains ranging from pixelwise image labeling to contextual object detection. The parameters of the model are learned using a sequential maximum-likelihood approximation. The benefits of the proposed framework are demonstrated on four different datasets and comparison results are presented

title: Dynamic tracking of page miss ratio curve for memory management
abstract: Memory can be efficiently utilized if the dynamic memory demands of applications can be determined and analyzed at run-time. The page miss ratio curve(MRC), i.e. page miss rate vs. memory size curve, is a good performance-directed metric to serve this purpose. However, dynamically tracking MRC at run time is challenging in systems with virtual memory because not every memory reference passes through the operating system (OS).This paper proposes two methods to dynamically track MRC of applications at run time. The first method is using a hardware MRC monitor that can track MRC at fine time granularity. Our simulation results show that this monitor has negligible performance and energy overheads. The second method is an OS-only implementation that can track MRC at coarse time granularity. Our implementation results on Linux show that it adds only 7--10% overhead.We have also used the dynamic MRC to guide both memory allocation for multiprogramming systems and memory energy management. Our real system experiments on Linux with applications including Apache Web Server show that the MRC-directed memory allocation can speed up the applications' execution/response time by up to a factor of 5.86 and reduce the number of page faults by up to 63.1%. Our execution-driven simulation results with SPEC2000 benchmarks show that the MRC-directed memory energy management can improve the Energy * Delay metric by 27--58% over previously proposed static and dynamic schemes.