ExScal: elements of an extreme scale wireless sensor network
Project ExScal (for extreme scale) fielded a 1000+ node wireless sensor network and a 200+ node peer-to-peer ad hoc network of 802.11 devices in a 13km by 300m remote area in Florida, USA during December 2004. In comparison with previous deployments, the ExScal application is relatively complex and its networks are the largest ones of either type fielded to date. In this paper, we overview the key requirements of ExScal, the corresponding design of the hardware/software platform and application, and some results of our experiments.

title: On k-coverage in a mostly sleeping sensor network
abstract: 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: 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 P1500 compliant programmable BistShell for embedded memories
abstract: We describe the design and implementation of an IEEE P1500 compliant programmable BIST for embedded memories. The proposed design can be embedded in other cores or systems with minimum test generation or test application overhead. The programmability of our BIST is useful when the algorithm is being refined while the memory architecture is under production. A variety of test algorithms can be implemented with the programmability provided in our design with no change to the BIST hardware. As an example we demonstrate the implementation of an algorithm to detect open decoder faults. This example is shown for its didactic content as it brings out the programmable axis of our design. Our design also offers means to perform dedicated delay tests as well as scan tests for diagnosis. We show by synthesis experiments that the extra area cost for the BIST hardware is relatively small for medium to large memories.

title: A Weighted Finite State Transducer Implementation of the Alignment Template Model for Statistical Machine Translation
abstract: We present a derivation of the alignment template model for statistical machine translation and an implementation of the model using weighted finite state transducers. The approach we describe allows us to implement each constituent distribution of the model as a weighted finite state transducer or acceptor. We show that bitext word alignment and translation under the model can be performed with standard FSM operations involving these transducers. One of the benefits of using this framework is that it obviates the need to develop specialized search procedures, even for the generation of lattices or N-Best lists of bitext word alignments and translation hypotheses. We evaluate the implementation of the model on the French-to-English Hansards task and report alignment and translation performance.

title: ESP: a language for programmable devices
abstract: This paper presents the design and implementation of Event-driven State-machines Programming (ESP)—a language for programmable devices. In traditional languages, like C, using event-driven state-machine forces a tradeoff that requires giving up ease of development and reliability to achieve high performance. ESP is designed to provide all of these three properties simultaneously.
ESP provides a comprehensive set of features to support development of compact and modular programs. The ESP compiler compiles the programs into two targets—a C file that can be used to generate efficient firmware for the device; and a specification that can be used by a verifier like SPlN to extensively test the firmware.
As a case study, we reimplemented VMMC firmware that runs on Myrinet network interface cards using ESP. We found that ESP simplifies the task of programming with event-driven state machines. It required an order of magnitude fewer lines of code than the previous implementation. We also found that model-checking verifiers like SPIN can be used to effectively debug the firmware. Finally, our measurements indicate that the performance overhead of using ESP is relatively small.

title: MEGA2: molecular evolutionary genetics analysis software
abstract: We have developed a new software package, Molecular Evolutionary Genetics Analysis version 2 (MEGA2), for exploring and analyzing aligned DNA or protein sequences from an evolutionary perspective. MEGA2 vastly extends the capabilities of MEGA version 1 by: (1) facilitating analyses of large datasets; (2) enabling creation and analyses of groups of sequences; (3) enabling specification of domains and genes; (4) expanding the repertoire of statistical methods for molecular evolutionary studies; and (5) adding new modules for visual representation of input data and output results on the Microsoft Windows platform.


AVAILABILITY
http://www.megasoftware.net.