Clustering the nodes in a wireless sensor network is a fundamental step in many distributed self organization, re- source management, communication, and processing algorithms. Although in many system management tasks a purely network topology-based clustering may be sufficient, a more sensor-centric approach to clustering is required for many distributed sensing, control, and actuation applications. In this paper we investigate the sensing-driven node clustering problem by first formulating it as an instance of weighted bi-partite matching between sensors and phenomena of interest. In order to make the clustering algorithm implementation practical in a larger networks, we then present two distributed approaches: (i) a simple, low- cost, deterministic approach and (ii) a probabilistic balanced clustering approach. Depending on the number of sensors in the system and cluster capacities, our simulation studies indicate that switching from one approach to the other, under specific conditions, can achieve near optimal results while keeping the communication costs low.

There is a wide consensus that performance and power consumption of IC designs in deep submicron technologies is mainly dictated by interconnect requirements. Our goal is demonstrate how compilation and architectural techniques can be used to minimize and balance interconnect requirements. Specifically, we target the use of bypass units to reduce routing congestion and eliminate long interconnections while essentially preserving or even improving the throughput requirements. We formulate the bypassing problem, establish its complexity and develop an efficient integer-linear programming (ILP) formulation. In addition to satisfying user specified interconnect requirements, we simultaneously optimize the number of operations and, therefore runtime of the targeted application. The approach is prototyped and evaluated using a platform consisting of the Trimaran architecture and compilation tools and the CPLEX ILP solver.

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 large scale wireless networks, both in terms of energy consumption and latency costs. 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, hi order to make the data collection as efficient as possible, various proposed sampling and compression techniques have been, and are being investigated. As we demonstrate, in addition to the compression algorithm, the topology of the aggregation (e.g. the routes used) can play a significant role in the achievable compression rates, hi this paper, we propose a compression-centric data collection algorithm for use in wireless sensor networks. The algorithm relies on the construction of a Minimum Cost Tree (MCT), using neighbor data correlation as the optimization heuristic along the tree. By selecting routes that traverse nodes with higher degrees of data correlation, it is possible to achieve superior compression results when compared to more naive minimum spanning tree algorithm variations, hi addition to presenting the details of our distributed MCT algorithm, we use simulated data as well as actual data from a real sensor network to validate and demonstrate the performance of the new compression-centric routing scheme.

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

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

Deep submicrometer 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, an ultrahigh level of integration mandates design of systems-on-chip that encompass numerous design blocks of 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. 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 have been developed. 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; it also sends feedback about the most constrained parts of the network. The effectiveness of our bus-network design approach on a number of multicore designs is demonstrated

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.

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.

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.