Sensor coverage is a fundamental sensor networking design and use issue that in general tries to answer the questions about the quality of sensing (surveillance) that a particular sensor network provides. Although isotropic sensor models and coverage formulations have been studied and analyzed in great depth recently, the obtained results do not easily extend to, and address the coverage of directional and field-of-view sensors such as imagers and video cameras. In this paper, we present an optimal polynomial time algorithm for computing the worst-case breach coverage in sensor networks that are comprised of directional ``field-of-view'' (FOV) sensors. Given a region covered by video cameras, a direct application of the presented algorithm is to compute ``breach'', which is defined as the maximal distance that any hostile target can maintain from the sensors while traversing through the region. Breach translates to ``worst-case coverage'' by assuming that in general, targets are more likely to be detected and observed when they are closer to the sensors (while in the field of view). The approach is amenable to the inclusion of any sensor detection model that is either independent of, or inversely proportional to distance from the targets. Although for the sake of discussion we mainly focus on square fields and model the sensor FOV as an isosceles triangle, we also discuss how the algorithm can trivially be extended to deal with arbitrary polygonal field boundaries and sensor FOVs, even in the presence of rigid obstacles. We also present several simulation-based studies of the scaling issues in such coverage problems and analyze the statistical properties of breach and its sensitivity to node density, locations, and orientations. A simple grid-based approximation approach is also analyzed for comparison and validation of the implementation.

Inter-sensor data modeling and prediction have recently proven to be very promising techniques in drastically reducing the number of active sensors and thus the overall energy consumption in wireless sensor networks. Using existing and recently proposed inter-sensor data modeling techniques as the enablers, we propose an on-line distributed active prediction algorithm to use the available prediction models to put redundant sensor nodes to sleep. We first start by a more general eligible redundant set representation of the problem with an integer linear programming formulation that does not take network connectivity into account. We then discuss an efficient centralized heuristic to deal with the connectivity issue. The proposed distributed algorithm selects a subset of the sensors that form a connected network. After completion, each sensor is either in the active set or its measurements can be directly predicted by a designated predictor sensor in the active set, within specified tolerance levels. The elected predictor sensor performs the prediction and disseminates it along with its own measurements when necessary. We also show that performing the prediction modeling locally, as opposed to at a fusion center, is better suited for dynamic sensor networks. We evaluate the proposed algorithm using simulated data as well as real experimental data collected from 16 indoor temperature sensors from a large office building. The experimental results from the indoor temperature sensors show that the algorithm can reduce the number of active nodes in this case by 60% to 80% with only a 0.5F average tolerance level in the predicted measurements.

Efficient sensor data fusion is one of the more critical and challenging tasks in building practical sensor networks. It is widely understood that transmitting raw sensor data to a central location for processing is severely hampered by scaling, in terms of energy consumption and latency costs, in large scale wireless networks. However, many detection, classification, estimation, and phenomena modeling algorithms rely heavily on the individual data from each sensor and thus require raw data collection, if not from the entire network, then at least among localized node clusters of varying sizes. In order to make the data collection as efficient as possible, various compression and fusion techniques have been proposed and are currently being investigated. In addition to the compression and fusion algorithms, the topology of the aggregation, e.g. the clusters and routes used, can play a significant role in the achievable compression rates.

In this paper, we investigate the problem of cluster formation for data fusion by focusing on two aspects of the problem: (i) how does one estimate the number of clusters needed to efficiently utilize data correlation of sensors for a general sensor network, and (ii), given the number of clusters, how does one pick the cluster-heads (sinks of information) to cover the sensor network more efficiently. We start by first analytically deriving and analyzing the number of required cluster heads. We then propose an algorithm for the head selection. Simulation results are used to investigate the performance of the algorithm compared to exhaustively found optimal solutions which show that significant improvements in energy efficiency of the fusion algorithms can be obtained through minimal efforts spent on optimizing the cluster head-selection process.

Distributed actuation is a major application of sensor networks that relies on the information provided by the sensors and the ability of the actuators to change the environment, to try to achieve a set of desired conditions. In large scale ad hoc distributed sensor-actuator networks, traditional centralized control algorithms are undesirable due to limiting factors such as scaling, delays associated with collecting information, and energy consumption. To tackle distributed actuation problems in wireless sensor networks, groups of sensors and actuators can first be matched (clustered) efficiently and then the problem posed and solved in localized manners.

In this paper, given a set of sensors and controllable sources of superposable phenomena (e.g. light and heat), we first formulate and optimally solve the distributed sensor-actuator problem as an instance of centralized quadratic programming. We then investigate localized heuristics that can achieve near optimal results while trading off message exchanges and energy consumption for accuracy and latency in obtaining the results. We also briefly discuss the clustering algorithm used as a heuristic for solving the matching problem associated with matching the sensors to the proper actuators. Light sensors and sources are used throughout the paper as an illustrating application

Calibration is the process of mapping raw sensor readings into corrected values by identifying and correcting systematic bias. Calibration is important from both off-line and on-line perspectives. Major objectives of calibration procedure include accuracy, resiliency against random errors, ability to be applied in various scenarios, and to address a variety of error models. In addition, a compact mapping function is attractive in terms of both storage and robustness. We start by introducing the nonparametric statistical approach for conducting off-line calibration. After that, we present the non-parametric statistical percentile method for establishing the confidence interval for a particular mapping function.

We propose the first systematic, sensor-centric approach for quantitative design of sensor network appliances. We demonstrate its use by designing light appliance devices and the associated middleware. We have developed five models which are required to make this problem tractable and to undertake the challenging task of designing light sensor appliances: (i) physical world, (ii) light sensor, (iii) physical phenomenon, (iv) appliance design, and (v) computational model. With these models in place, we present the new design methodology that consists of two mains steps: (1) a procedure for placement of individual sensors of the appliance, and (2) error minimization-based sensor data interpretation middleware. We have developed new optimization techniques for both tasks. A portable light sensor system was designed using the optimization intensive procedure, and its effectiveness demonstrated.

Numerous factors contribute to errors in sensor measurements. In order to be useful, any sensor device must be calibrated to adjust its accuracy against the expected measurement scale. In large-scale sensor networks, calibration will be an exceptionally difficult task since sensor nodes are often not easily accessible and manual device-by-device calibration is quite intractable. In this paper, we present a two-phase post-deployment calibration technique for large-scale, dense sensor deployments. In its first phase, the algorithm derives relative calibration relationships between pairs of co-located sensors, while in the second phase, it maximizes the consistency of the pair-wise calibration functions among groups of sensor nodes. The key idea in the first phase is to use temporal correlation of signals received at neighboring sensors when the signals are highly correlated (i.e. sensors are observing the same phenomenon) to derive the function relating their bias in amplitude. We formulate the second phase as an optimization problem and explore potential trade-offs in the size of the input, quality of solution, and complexity. We evaluate the performance of both phases of the algorithm using empirical and simulated data.

Linear programming (LP) in its many forms has proven to be an indispensable tool for expressing and solving optimization problems in numerous domains. We propose the first set of generic watermarking techniques for integer-LP (ILP). The proof of authorship by watermarking is achieved by introducing additional constraints to limit the solution space and can be used as effective means of intellectual property protection (IPP) and authentication. We classify and analyze the types of constraints in the ILP watermarking domain and show how ILP formulations provide more degrees of freedom for embedding signatures than other existing approaches. To demonstrate the effectiveness of the proposed ILP watermarking techniques, the generic discussion is further concretized using two examples, namely Satisfiability and Scheduling.

The effectiveness of traditional CAD optimization algorithms is proportional to the accuracy of the targeted objective functions. However, behavioral synthesis tools are not used in isolation; they form a strongly connected design flow where each tool optimizes its own objective function without considering the consequences on the optimization goals of the subsequently applied tools. Therefore, efforts to optimize one aspect of a design often have unforeseen negative impacts on other phases of the design process.
Our objective is to establish a systematic way of developing and validating new types of objective functions that consider the effects on subsequently applied synthesis steps. We demonstrate the generic forward-looking objective function (FLOF) strategy on three main steps in behavioral synthesis: (i) Transformation, (ii) Scheduling, and (iii) Register Assignment. We show how the FLOF can be used in the first two phases to reduce the total number of registers required in the third phase.

In the last several years, system and integrated circuits (IC) semiconductor industry and research has started refocusing from the general purpose computing platform toward application specific devices and appliances. This shift, compounded with the exponentially growing gap between IC potential and design productivity imposes an urgent need for new design methodologies and technologies. There are four main phases in development of application specific systems (ASS): algorithm, architecture, implementation, and semiconductor realization. The last phase is mainly related to the technology CAD field and is out of main scope of the research presented in this paper.
The effectiveness of the first three phases is mainly dictated by employed optimization and search techniques. For this purpose, we have developed a new probabilistic iterative improvement generic technique. The technique has a number of noble properties including high quality of solution, low run-time, flexibility and ease of application. We have demonstrated the effectiveness of the new technique on two tasks: architectural design space for Infinite Impulse Response (IIR) filter and for the widely used Graph Coloring problem.

We propose a new optimization paradigm for solving intractable combinatorial problems. The technique, named probabilistic constructive, combines the advantages of constructive and probabilistic algorithms. Since it is constructive, it has a relatively short run time and is amenable for inclusion of insights through heuristic rules. The probabilistic nature facilitates a flexible trade-off between run-time and the quality of solution, and super imposition of a variety of control strategies and solution selection mechanisms.

In addition to presenting the generic technique, we apply it to two generic NP-complete problems (maximal independent set, graph coloring) and two synthesis and compilation problems (sequential code covering, scheduling). The extensive experimentation indicates that the new approach provides very attractive trade-offs between the quality of the solution and run time, often outperforming the best previously published approaches.

The development of practical, localized algorithms is probably the most needed and most challenging task in wireless ad-hoc sensor networks (WASNs). Localized algorithms are a special type of distributed algorithms where only a subset of nodes in the WASN participate in sensing, communication, and computation. We have developed a generic localized algorithm for solving optimization problems in wireless ad-hoc networks that has five components: (i) data acquisition mechanism, (ii) optimization mechanism, (iii) search expansion rules, (iv) bounding conditions, and (v) termination rules. The main idea is to request and process data only locally and only from nodes who are likely to contribute to rapid formation of the final solution.
The approach enables two types of optimization: The first, guarantees the fraction of nodes that are contacted while optimizing for solution quality. The second, provides guarantees on solution quality while minimizing the number of nodes that are contacted and/or amount of communication. This localized optimization approach is applied to two fundamental problems in sensor networks: location discovery and exposure-based coverage. We demonstrate its effectiveness on a number of benchmark examples.

Wireless ad-hoc sensor networks will provide one of the missing connections between the Internet and the physical world. One of the fundamental problems in sensor networks is the calculation of coverage. Exposure is directly related to coverage in that it is a measure of how well an object, moving on an arbitrary path, can be observed by the sensor network over a period of time.

In addition to the informal definition, we formally define exposure and study its properties. We have developed an efficient and effective algorithm for exposure calculation in sensor networks, specifically for finding minimal exposure paths. The minimal exposure path provides valuable information about the worst case exposure-based coverage in sensor networks. The algorithm works for any given distribution of sensors, sensor and intensity models, and characteristics of the network. It provides an unbounded level of accuracy as a function of run time and storage. We provide an extensive collection of experimental results and study the scaling behavior of exposure and the proposed algorithm for its calculation.

Deep submicron technology has two major ramifications on the design process: (i) critical paths are being dominated by global interconnect rather than gate delays and (ii) ultra high levels of integration mandate designs that encompass numerous intra-synchronous blocks with decreased functional granularity and increased communication demands. These factors emphasize the importance of the on-chip bus network as the crucial high-performance enabler for future systems-on-chip. By using independent functional blocks with programmable connectivity, designers are able to build systems-on-chip capable of supporting different applications with exceptional level of resource sharing. To address challenges in this design paradigm, we have developed a methodology that enables efficient bus network design with approximate timing verification and floorplanning of multi-purpose systems-on-chip in early design stages. The design platform iterates system synthesis and floorplanning to build min-area floorplans that satisfy statistical time constraints of applications. We demonstrate the effectiveness of our bus network design approach using examples from a multimedia benchmark suite.

Currently, hardware intellectual property (IP) is delivered at three levels of abstraction: hard, firm, and soft. In order to further enhance performance, efficiency, and flexibility of IP design, we have developed a new approach for designing hardware and software IP called MetaCores. The new design approach starts at the algorithm level and leverages on the algorithm's intrinsic optimization degrees of freedom. The approach has four main components: (i) Problem formulation and identification of optimization degrees of freedom; (ii) Objective functions and constraints; (iii) Cost evaluation engine; (iv) Multiresolution design space search. From the algorithmic viewpoint, the main contribution is the introduction of multiresolution search in the optimization and synthesis process. We have applied the approach to the development of Viterbi and IIR MetaCores. Experimental results demonstrate the effectiveness of the new approach.

Wireless ad-hoc sensor networks have recently emerged as a premier research topic. They have great long-term economic potential, ability to transform our lives, and pose many new system-building challenges. Sensor networks also pose a number of new conceptual and optimization problems. Some, such as location, deployment, and tracking, are fundamental issues, in that many applications rely on them for needed information.
In this paper, we address one of the fundamental problems, namely coverage. Coverage in general, answers the questions about quality of service (surveillance) that can be provided by a particular sensor network. We first define the coverage problem from several points of view including deterministic, statistical, worst and best case, and present examples in each domain. By combining computational geometry and graph theoretic techniques, specifically the Voronoi diagram and graph search algorithms, we establish the main highlight of the paper - optimal polynomial time worst and average case algorithm for coverage calculation. We also present comprehensive experimental results and discuss future research directions related to coverage in sensor networks.

Deep submicron technology scaling has two major ramifications on the design process. First, reduced feature size significantly increases wire delay, thus resulting in critical paths being dominated by global interconnect rather than gate delays. Second, ultra high level of integration mandates design of systems-on-chip that encompass numerous intra-synchronous blocks with decreased functional granularity and increased communication demands. The convergence of these two factors emphasizes the importance of the on-chip bus network as one of the crucial high-performance enablers for future systems-on-chip. We have developed an on-chip bus network design methodology and corresponding set of tools which, for the first time, close the synthesis loop between system and physical design. The approach has three components: a communication profiler, a bus network designer, and a fast approximate floorplanner. The communication profiler collects run-time information about the traffic between system cores. The bus network design component optimizes the bus network structure by coordinating information from the other two components. The floorplanner aims at creating a feasible floorplan and to communicate information about the most constrained parts of the network. We have demonstrated the effectiveness of our bus network design approach on a number of multi-core designs.

In many modern designs, timing is either a key optimization goal and/or a mandatory constraint. We propose the first intellectual property protection (IPP) technique using watermarking which guarantees preservation of timing constraints. This is accomplished by judiciously selecting parts of the design specification on which watermarking constraints can be imposed. The technique is applied during the mapping of logical elements to instances of realization elements in a physical library. The generic technique is applied to two steps in the design process: combinational logic mapping in logic synthesis and template matching in behavioral synthesis. The technique is fully transparent to the synthesis process, and can be used in conjunction with arbitrary synthesis tools. Several optimization problems associated with the application of the technique have been solved. The effectiveness of the technique is demonstrated on a number of designs at both the logic synthesis and behavioral synthesis designs.

Abstract

Wireless ad hoc sensor networks have recently emerged as a premier research topic. They have great long-term economic potential, ability to transform our lives, and pose many new system-building challenges. Sensor networks also pose a number of new conceptual and optimization problems. Here, we address one of the fundamental problems, namely, coverage. Sensor coverage, in general, answers the questions about the quality of service (surveillance) that can be provided by a particular sensor network. We briefly discuss the definition of the coverage problem from several points of view and formally define the worst and best-case coverage in a sensor network. By combining computational geometry and graph theoretic techniques, specifically the Voronoi diagram and graph search algorithms, we establish the main highlight of the paper-an optimal polynomial time worst and average case algorithm for coverage calculation for homogeneous isotropic sensors. We also present several experimental results and analyze potential applications, such as using best and worst-case coverage information as heuristics to deploy sensors to improve coverage.

We have developed a new optimization paradigm for solving computationally intractable combinatorial optimization and synthesis problems. The technique, named probabilistic constructive, combines the advantages of both constructive and probabilistic optimization mechanisms. Since it is a constructive approach, it has a relatively short runtime and is amenable for the inclusion of insights through heuristic rules. The probabilistic nature facilitates a flexible tradeoff between runtime and the quality of solution, suitability for the superimposition of a variety of control strategies, and simplicity of implementation. After presenting the generic technique, we apply it to a generic NP-complete problem (maximum independent set) and a synthesis and compilation problem (sequential code covering). Extensive experimentation indicates that the new approach provides very attractive tradeoffs between the quality of solution and runtime, often outperforming the best previously published approaches.

Wireless ad-hoc sensor networks have the potential to provide the missing interface between the physical world and the Internet, thus impacting a large number of users. This connection will enable computational treatments of the physical world in ways never before possible. In this far reaching scenario, quality of service can be expressed in terms of accuracy and/or latency of observing events and overall state of the physical world. Consequently, one of the fundamental problems in sensor networks is the calculation of coverage, which can be defined as a measure of the ability to detect objects within a sensor filed. Exposure is directly related to coverage in that it is an integral measure of how well the sensor network can observe an object, moving on an arbitrary path, over a period of time. After elucidating the importance of exposure, we formally define exposure and study its properties. We have developed an efficient and effective algorithm for exposure calculation in sensor networks, specifically for finding minimal exposure paths. The minimal exposure path provides valuable information about the worst case exposurebased coverage in sensor networks. The algorithm can be applied to any given distribution of sensors, sensor and sensitivity models, and characteristics of the network. Furthermore, It provides an unbounded level of accuracy as a function of run time and storage. Finally, we provide an extensive collection of experimental results and study the scaling behavior of exposure and the proposed algorithm for its calculation.

Wireless sensor networks monitor the physical world by taking measurements of physical phenomena. Those measurements, and consequently the results computed from the measurements, may be significantly inaccurate. Therefore, in order to properly design and use wireless sensor networks, one must develop methods that take error sources, error propagation through optimization software, and ultimately their impact on applications, into consideration. In this paper, we focus on location discovery induced errors. We have selected location discovery as the object of our case study since essentially all sensor network computation and communication tasks are dependent on geographical node location data. First, we model the error in input parameters of the location discovery process. Then, we study the impact of errors on three selected applications: exposure, best- and worst-case coverage, and shortest path routing. Furthermore, we examine how the choice of a specific objective function optimized during the location discovery process impacts the errors in results of different applications.

Sensor networks consist of a set of sensor nodes, each equipped with one or more sensors, communication subsystems, storage and processing resources, and in some cases actuators. The sensors in a node observe phenomena such as thermal, optic, acoustic, seismic, and acceleration events, while the processing and other components analyze the raw data and formulate answers to specific user requests. Recent advances in technology have paved the way for the design and implementation of new generations of sensor network nodes, packaged in very small and inexpensive form factors with sophisticated computation and wireless communication abilities. Although still at infancy, these new classes of sensor networks, generally referred to as wireless sensor networks (WSN), show great promise and potential with applications ranging in areas that have already been addressed, to domains never before imagined. In this article we provide an overview of this new and exciting field and a brief discussion on the factors pushing the recent flurry of sensor network related research and commercial undertakings. We also provide overview discussions on architectural design characteristics of such networks including physical components, software layers, and higher level services. At each step, we highlight special characteristics of WSNs and discuss why existing approaches and results from wireless communication networks are not necessarily suitable in WSN domains. We conclude by briefly summarizing the state of the art and the future research directions.

A method for developing a circuit is disclosed. The method generally comprises the steps of (A) generating a solution space having a dimension for each of a plurality of parameters for the circuit, (B) evaluating a plurality of instances of the circuit in the solution space through a software simulation, (C) evaluating the instances through a hardware simulation, and (D) updating the instances in response to the software simulation and the hardware simulation to approach an optimum instance of the instances for the circuit.

A method for decoding an encoded signal. A first step generates a plurality of first precision state metrics for a decoder trellis in response to a plurality of first precision branch metrics. A second step generates a plurality of second precision state metrics for a selected subset of the first precision state metrics in response to a plurality of second precision branch metrics. A third step replaces the selected subset of first precision state metrics with the second precision state metrics. A fourth step stores the first precision state metrics and the second precision state metrics.

A method for optimizing an algorithm specified for implementation on an integrated circuit for a specified application. The algorithm is analyzed with respect to its performance, and estimates of implementation area and speed are calculated. Specifically, the degrees of freedom for the algorithm alternations under specific targeted implementation objective functions and constraints are identified. The algorithm solution space is then searched to identify the algorithm structure that is best suited for the specified design goals and constraints. Algorithm parameters which satisfy performance metrics and can be implemented with minimum silicon area are identified.

Sensor data middleware design is an essential step in building functional and reusable sensor networks. The middleware layer processes the raw data collected from sensors and provides meaningful information to the application layers that utilize it for a variety of tasks. We first formulate sensor data middleware as a nonlinear programming problem with a special structure. As our driver example, we focus on a middleware for light sensing that determines the number, positions, and intensities of different light sources in the environment based on sensor measurements. We demonstrate that even under idealized assumptions, the problem is difficult to solve in presence of errors. The errors are unavoidable and can appear in the forms of position and orientation errors of sensors, as well as calibration and noise in measurements. The backbone of the paper is an algorithm for solving the nonlinear programming problem that leverages on knowledge about light properties, and combining combinatorial and existing numerical optimization techniques. Finally, we present an in depth discussion on our validation techniques and extensive experimental studies on the behaviors and prediction capabilities of our models and algorithms.

Recently, a large number of sensor equipped wireless mobile systems have been developed and deployed. The general common denominators in all of them have been the emphasis on the communication and computation components and the placements of single sensors of each type. However, in order to enable a meaningful interaction between the user and the physical world, it is necessary to equip the system with a proper number of judiciously placed sensors, as well as to develop the corresponding sensor data processing middleware.
We propose the first sensor-centric, generic, systematic approach for quantitative design of sensor network appliances. We demonstrate its use by designing light appliance devices and middleware. We have developed five models required to make this problem tractable and to undertake the challenging task of designing light sensor appliances. These five models are: (i) physical world, (ii) light sensor, (iii) physical phenomenon, (iv) appliance design, and (v) computational model. Having these models in place, we present the new design methodology that consists of two mains steps: (1) a procedure for placement of individual sensors of the appliance, and (2) error minimization-based sensor data interpretation middleware. We have developed new optimization techniques for both tasks. The portable light sensor system has been designed using the optimization intensive procedure, and its effectiveness has been demonstrated and validated.

Distributed embedded systems have recently emerged as an economically attractive and technically challenging research direction. Among such systems, wireless ad-hoc sensor networks have a special place due to their numerous applications and potential to fill the interface gap between the Internet and the physical world. Wireless sensor networks are intrinsically energy constrained and therefore necessitate the design of new low power protocols. Coverage, in its many forms, is a fundamental task in sensor networks. Our focus here is energy efficient operation strategies for sensor networks with sensor coverage as the primary objective. We present several ILP (Integer Linear Program) formulations and strategies to reduce overall energy consumption while maintaining guaranteed coverage levels. We also demonstrate the practicality and effectiveness of these formulations using several examples and provide comparisons with alternative strategies.