Search results for "Brooks"
showing 10 items of 11 documents
Reducing the observation error in a WSN through a consensus-based subspace projection
2013
An essential process in a Wireless Sensor Network is the noise mitigation of the measured data, by exploiting their spatial correlation. A widely used technique to achieve this reduction is to project the measured data into a proper subspace. We present a low complexity and distributed algorithm to perform this projection. Unlike other algorithms existing in the literature, which require the number of connections at every node to be larger than the dimension of the involved subspace, our algorithm does not require such dense network topologies for its applicability, making it suitable for a larger number of scenarios. Our proposed algorithm is based on the execution of several consensus pro…
Detecting faulty wireless sensor nodes through Stochastic classification
2011
In many distributed systems, the possibility to adapt the behavior of the involved resources in response to unforeseen failures is an important requirement in order to significantly reduce the costs of management. Autonomous detection of faulty entities, however, is often a challenging task, especially when no direct human intervention is possible, as is the case for many scenarios involving Wireless Sensor Networks (WSNs), which usually operate in inaccessible and hostile environments. This paper presents an unsupervised approach for identifying faulty sensor nodes within a WSN. The proposed algorithm uses a probabilistic approach based on Markov Random Fields, requiring exclusively an ana…
Grundy coloring for power graphs
2003
International audience
Chromatic Sums for Colorings Avoiding Monochromatic Subgraphs
2013
Abstract Given graphs G and H, a vertex coloring c : V ( G ) → N is an H-free coloring of G if no color class contains a subgraph isomorphic to H. The H-free chromatic number of G, χ ( H , G ) , is the minimum number of colors in an H-free coloring of G. The H-free chromatic sum of G , Σ ( H , G ) , is the minimum value achieved by summing the vertex colors of each H-free coloring of G. We provide a general bound for Σ ( H , G ) , discuss the computational complexity of finding this parameter for different choices of H, and prove an exact formulas for some graphs G. For every integer k and for every graph H, we construct families of graphs, G k with the property that k more colors than χ ( …
On Coloring Unit Disk Graphs
1998
In this paper the coloring problem for unit disk (UD) graphs is considered. UD graphs are the intersection graphs of equal-sized disks in the plane. Colorings of UD graphs arise in the study of channel assignment problems in broadcast networks. Improving on a result of Clark et al. [2] it is shown that the coloring problem for UD graphs remains NP-complete for any fixed number of colors k≥ 3 . Furthermore, a new 3-approximation algorithm for the problem is presented which is based on network flow and matching techniques.
A Novel Approach for Faulty Sensor Detection and Data Correction in Wireless Sensor Network
2013
he main Wireless Sensor Networks purpose is represented by areas of interest monitoring. Even if the Wireless sensor network is properly initialized, errors can occur during its monitoring tasks. The present work describes an approach for detecting faulty sensors in Wireless Sensor Network and for correcting their corrupted data. The approach is based on the assumption that exist a spatio-temporal cross- correlations among sensors. Two sequential mathematical tools are used. The first stage is a probabilistic tools, namely Markov Random Field, for a two-fold sensor classification (working or damaged). The last stage is represented by the Locally Weighted Regression model, a learning techniq…
A distributed genetic algorithm for restoration of vertical line scratches
2008
This paper reports a distributed algorithm for the restoration of still frames corrupted by vertical line scratches. The restoration is here approached as an optimisation problem, and is solved using an ad-hoc Genetic Algorithm. The distributed algorithm is designed following a pipeline logical structure. The front end is a network of standard workstations with heterogeneous operating systems. The quality of image is appreciable and the computational time is quite low with respect the sequential version.
Probabilistic Anomaly Detection for Wireless Sensor Networks
2011
Wireless Sensor Networks (WSN) are increasingly gaining popularity as a tool for environmental monitoring, however ensuring the reliability of their operation is not trivial, and faulty sensors are not uncommon; moreover, the deployment environment may influence the correct functioning of a sensor node, which might thus be mistakenly classified as damaged. In this paper we propose a probabilistic algorithm to detect a faulty node considering its sensed data, and the surrounding environmental conditions. The algorithm was tested with a real dataset acquired in a work environment, characterized by the presence of actuators that also affect the actual trend of the monitored physical quantities.
A distributed Bayesian approach to fault detection in sensor networks
2012
Sensor networks are widely used in industrial and academic applications as the pervasive sensing module of an intelligent system. Sensor nodes may occasionally produce incorrect measurements due to battery depletion, dust on the sensor, manumissions and other causes. The aim of this paper is to develop a distributed Bayesian fault detection algorithm that classifies measurements coming from the network as corrupted or not. The computational complexity is polynomial so the algorithm scales well with the size of the network. We tested the approach on a synthetic dataset and obtained significant results in terms of correctly labeled measurements.
The b-chromatic number of power graphs
2003
The b-chromatic number of a graph G is defined as the maximum number k of colors that can be used to color the vertices of G, such that we obtain a proper coloring and each color i, with 1 ≤ i≤ k, has at least one representant x_i adjacent to a vertex of every color j, 1 ≤ j ≠ i ≤ k. In this paper, we discuss the b-chromatic number of some power graphs. We give the exact value of the b-chromatic number of power paths and power complete binary trees, and we bound the b-chromatic number of power cycles.