Sensor networks: from dependence analysis via matroid bases to online synthesis

DOI10.1016/J.TCS.2014.07.014zbMATH Open1360.68145arXiv1201.4054OpenAlexW2501575578MaRDI QIDQ742408FDOQ742408

Authors: Asaf Cohen, Shlomi Dolev, Guy Leshem 

Publication date: 18 September 2014

Published in: Theoretical Computer Science (Search for Journal in Brave)

Abstract: Consider the two related problems of sensor selection and sensor fusion. In the first, given a set of sensors, one wishes to identify a subset of the sensors, which while small in size, captures the essence of the data gathered by the sensors. In the second, one wishes to construct a fused sensor, which utilizes the data from the sensors (possibly after discarding dependent ones) in order to create a single sensor which is more reliable than each of the individual ones. In this work, we rigorously define the dependence among sensors in terms of joint empirical measures and incremental parsing. We show that these measures adhere to a polymatroid structure, which in turn facilitates the application of efficient algorithms for sensor selection. We suggest both a random and a greedy algorithm for sensor selection. Given an independent set, we then turn to the fusion problem, and suggest a novel variant of the exponential weighting algorithm. In the suggested algorithm, one competes against an augmented set of sensors, which allows it to converge to the best fused sensor in a family of sensors, without having any prior data on the sensors' performance.

Full work available at URL: https://arxiv.org/abs/1201.4054

Recommendations

• Sensor selection for random field estimation in wireless sensor networks
• Sensor fusion using entropic measures of dependence
• Sensor selection for Kalman filtering of linear dynamical systems: complexity, limitations and greedy algorithms
• Some progress in sensor network decision fusion
• On a stochastic sensor selection algorithm with applications in sensor scheduling and sensor coverage

zbMATH Keywords

randomized algorithmssensor networksempirical measuresLempel-Zivincremental parsingpolymatroidsmatroid optimizationgreedy selectiondependence analysisonline fusion

Mathematics Subject Classification ID

Randomized algorithms (68W20) Combinatorial optimization (90C27) Combinatorial aspects of matroids and geometric lattices (05B35) Network design and communication in computer systems (68M10)

Cites Work

• Elements of Information Theory
• Best Algorithms for Approximating the Maximum of a Submodular Set Function
• Sequential prediction of individual sequences under general loss functions
• Title not available (Why is that?)
• The weighted majority algorithm
• Compression of individual sequences via variable-rate coding
• On prediction of individual sequences
• How to use expert advice
• Title not available (Why is that?)
• Minimum cycle bases for network graphs
• Noiseless coding of correlated information sources
• On a stochastic sensor selection algorithm with applications in sensor scheduling and sensor coverage
• Chernoff-type bound for finite Markov chains
• A game of prediction with expert advice
• A simple randomized algorithm for sequential prediction of ergodic time series
• The on-line shortest path problem under partial monitoring
• Learning with stochastic inputs and adversarial outputs
• Universal prediction
• Dualities Between Entropy Functions and Network Codes
• Two Constructions on Limits of Entropy Functions
• On the (co)girth of a connected matroid
• Scanning and Sequential Decision Making for Multidimensional Data–Part I: The Noiseless Case
• Scanning and Sequential Decision Making for Multidimensional Data—Part II: The Noisy Case
• Title not available (Why is that?)
• Optimal sequential probability assignment for individual sequences
• Redundancy of the Lempel-Ziv incremental parsing rule
• A zero-delay sequential scheme for lossy coding of individual sequences
• On limited-delay lossy coding and filtering of individual sequences
• On sequential strategies for loss functions with memory
• Efficient Adaptive Algorithms and Minimax Bounds for Zero-Delay Lossy Source Coding

Cited In (2)

• Graph-Theoretic Analysis and Synthesis of Relative Sensing Networks
• Sensor fusion using entropic measures of dependence

Uses Software

• ITIP

This page was built for publication: Sensor networks: from dependence analysis via matroid bases to online synthesis

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q742408)