9243746
Simulating the power consumption of large-scale sensor network applications
Developing sensor network applications demands a new set of tools to aid programmers. A number of simulation environments have been developed that provide varying degrees of scalability, realism, and detail for understanding the behavior of sensor networks. To date, however, none of these tools have addressed one of the most important aspects of sensor application design: that of power consumption. While simple approximations of overall power usage can be derived from estimates of node duty cycle and communication rates, these techniques often fail to capture the detailed, low-level energy requirements of the CPU, radio, sensors, and other peripherals.
 In this paper, we present, a scalable simulation environment for wireless sensor networks that provides an accurate, per-node estimate of power consumption. PowerTOSSIM is an extension to TOSSIM, an event-driven simulation environment for TinyOS applications. In PowerTOSSIM, TinyOS components corresponding to specific hardware peripherals (such as the radio, EEPROM, LEDs, and so forth) are instrumented to obtain a trace of each device's activity during the simulation runPowerTOSSIM employs a novel code-transformation technique to estimate the number of CPU cycles executed by each node, eliminating the need for expensive instruction-level simulation of sensor nodes. PowerTOSSIM includes a detailed model of hardware energy consumption based on the Mica2 sensor node platform. Through instrumentation of actual sensor nodes, we demonstrate that PowerTOSSIM provides accurate estimation of power consumption for a range of applications and scales to support very large simulations.
5122226
Sensor networks for medical care
Sensor networks have the potential to greatly impact many aspects of medical care. By outfitting patients with wireless, wearable vital sign sensors, collecting detailed real-time data on physiological status can be greatly simplified. However, there is a significant gap between existing sensor network systems and the needs of medical care. In particular, medical sensor networks must support multicast routing topologies, node mobility, a wide range of data rates and high degrees of reliability, and security. This paper describes our experiences with developing a combined hardware and software platform for medical sensor networks, called CodeBlue. CodeBlue provides protocols for device discovery and publish/subscribe multihop routing, as well as a simple query interface that is tailored for medical monitoring. We have developed several medical sensors based on the popular MicaZ and Telos mote designs, including a pulse oximeter, EKG and motion-activity sensor. We also describe a new, miniaturized sensor mote designed for medical use. We present initial results for the CodeBlue prototype demonstrating the integration of our medical sensors with the publish/subscribe routing substrate. We have experimentally validated the prototype on our 30-node sensor network testbed, demonstrating its scalability and robustness as the number of simultaneous queries, data rates, and transmitting sensors are varied. We also study the effect of node mobility, fairness across multiple simultaneous paths, and patterns of packet loss, confirming the system’s ability to maintain stable routes despite variations in node location and
1586078
Dual photography
We present a novel photographic technique called dual photography, which exploits Helmholtz reciprocity to interchange the lights and cameras in a scene. With a video projector providing structured illumination, reciprocity permits us to generate pictures from the viewpoint of the projector, even though no camera was present at that location. The technique is completely image-based, requiring no knowledge of scene geometry or surface properties, and by its nature automatically includes all transport paths, including shadows, inter-reflections and caustics. In its simplest form, the technique can be used to take photographs without a camera; we demonstrate this by capturing a photograph using a projector and a photo-resistor. If the photo-resistor is replaced by a camera, we can produce a 4D dataset that allows for relighting with 2D incident illumination. Using an array of cameras we can produce a 6D slice of the 8D reflectance field that allows for relighting with arbitrary light fields. Since an array of cameras can operate in parallel without interference, whereas an array of light sources cannot, dual photography is fundamentally a more efficient way to capture such a 6D dataset than a system based on multiple projectors and one camera. As an example, we show how dual photography can be used to capture and relight scenes.
10767971
The duality between information embedding and source coding with side information and some applications
Aspects of the duality between the information-embedding problem and the Wyner-Ziv (1976) problem of source coding with side information at the decoder are developed and used to establish a spectrum new results on these and related problems, with implications for a number of important applications. The single-letter characterization of the information-embedding problem is developed and related to the corresponding characterization of the Wyner-Ziv problem, both of which correspond to optimization of a common mutual information difference. Dual variables and dual Markov conditions are identified, along with the dual role of noise and distortion in the two problems. For a Gaussian context with quadratic distortion metric, a geometric interpretation of the duality is developed. From such insights, we develop a capacity-achieving information-embedding system based on nested lattices. We show the resulting encoder-decoder has precisely the same decoder-encoder structure as the corresponding Wyner-Ziv system based on nested lattices that achieves the rate-distortion limit. For a binary context with Hamming distortion metric, the information-embedding capacity is developed, along with its relationship to the corresponding Wyner-Ziv rate-distortion function. In turn, an information-embedding system for this case based on nested linear codes is constructed having an encoder-decoder that is identical to the decoder-encoder structure for the corresponding system that achieves the Wyner-Ziv rate-distortion limit. Finally, based on these results, a simple layered joint source-channel coding system is developed with a perfectly symmetric encoder-decoder structure. Its application and performance is discussed in a broadcast setting in which there is a need to control the fidelity experienced by different receivers. Among other results, we show that such systems and their multilayer extensions retain attractive optimality properties in the Gaussian-quadratic case, but not in the binary-Hamming case.
18808395
Stippling and silhouettes rendering in geometry-image space
We present a novel non-photorealistic rendering method that performs all operations in a geometry-image domain. We first apply global conformal parameterization to the input geometry model and generate corresponding geometry images. Strokes and silhouettes are then computed in the geometry-image domain. The geometry-image space provides combined benefits of the existing image space and object space approaches. It allows us to take advantage of the regularity of 2D images and yet still have full access to the object geometry information. A wide range of image processing tools can be leveraged to assist various operations involved in achieving non-photorealistic rendering with coherence.
4028543
On-Line Scheduling of Two-Machine Open Shops Where Jobs Arrive Over Time
We investigate the problem of on-line scheduling two-machine open shops with the objective of minimizing the makespan.Jobs arrive independently over time, and the existence of a job is not known until its arrival. In the clairvoyant on-line model, the processing requirement of every job becomes fully known at the arrival of the job, while inthe non-clairvoyant on-line model, this processing requirement is notknown until the job is processed and completed.In both models, scheduling of a job is irrevocable.We study the two-machine open shop problem for both models in the preemptive and in the non-preemptive version. For each of the four variants, we provide an algorithm that is best possible with respect to the worst-case performance. In the clairvoyant on-line model, the best worst-case performance ratios are 5/4 (preemptive) and 3/2 (non-preemptive), and in the non-clairvoyant on-line model, they are 3/2 (preemptive and non-preemptive).
12831347
Equitable Coloring and the Maximum Degree
Abstract Let Δ(G) denote the maximum degree of a graph G . The equitable Δ-coloring conjecture asserts that a connected graph G is equitably Δ( G )-colorable if it is different from K m , C 2 m + 1 and K 2 m + 1,2 m + 1 for all m ⩾ 1. This conjecture is established for graphs G satisfying Δ( G ) ⩾ | G |/2 or Δ( G ) ⩽ 3.