Joint Sensor Selection and Multihop Routing for Distributed Estimation in Ad-hoc Wireless Sensor Networks
IEEE Transactions on Signal ProcessingPublished 4 October 2013
Santosh Shah, Baltasar Beferull‐Lozano
Citations26
SJR quartileQ1
SJR score2.05
SNIP2.36
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
This paper designs two algorithms: a Fixed-Tree Relaxation-Based Algorithm (FTRA) and a very efficient Iterative Distributed Al algorithm (IDA) to optimize the sensor selection and routing structure in a Wireless Sensor Network.
Abstract
This paper considers the problem of power-efficient distributed estimation of vector parameters related to localized phenomena so that both sensor selection and routing structure in a Wireless Sensor Network (WSN) are jointly optimized to obtain the best possible estimation performance at a given querying node, for a given total power budget. First, we formulate our problem as an optimization problem and show that it is an NP-Hard problem. Then, we design two algorithms: a Fixed-Tree Relaxation-Based Algorithm (FTRA) and a very efficient Iterative Distributed Algorithm (IDA) to optimize the sensor selection and routing structure. We also provide a lower bound for our optimization problem and show that our IDA provides a performance that is close to this bound, and it is substantially superior to the previous approaches presented in the literature. An important result from our work is the fact that because of the interplay between communication cost and estimation gain when fusing measurements from different sensors, the traditional Shortest Path Tree (SPT) routing structure, widely used in practice, is no longer optimal. To be specific, our routing structure provides a better trade-off between the overall power efficiency and estimation accuracy. Comparing to more conventional sensor selection and fixed routing algorithms, our proposed algorithms yield a significant amount of energy saving for the same estimation accuracy.
Keywords
Computer ScienceEngineering
Reducibility among Combinatorial Problems
10,823 Citations1972Richard M. Karp
American Mathematical MonthlyCombinatorial Optimization: Algorithms and Complexity.
6,028 Citations1984David Johnson, Christos H. Papadimitriou +1 more
IEEE Transactions on Signal ProcessingSensor Selection via Convex Optimization
1,325 Citations2008Shashank V. Joshi, Stephen Boyd
This paper describes a heuristic, based on convex optimization, that gives a subset selection as well as a bound on the best performance that can be achieved by any selection of k sensor measurements.
NetworksA survey of gossiping and broadcasting in communication networks
1,245 Citations1988Sandra M. Hedetniemi, Stephen T. Hedetniemi +1 more
Gossiping and broadcasting are two problems of information dissemination described for a group of individuals connected by a communication network that one individual has an item of information which needs to be communicated to everyone else.
IEEE Signal Processing MagazineDetection, classification, and tracking of targets
933 Citations2002Dan Li, Kerry D. Wong +2 more
The key ideas behind the CSP algorithms for distributed sensor networks being developed at the University of Wisconsin (UW) are described and the approach to tracking multiple targets that necessarily requires classification techniques becomes a reality.
Computer NetworksA line in the sand: a wireless sensor network for target detection, classification, and tracking
894 Citations2004Anish Arora, Prabal Dutta +15 more
This paper studies the application of sensor networks to the intrusion detection problem and the related problems of classifying and tracking targets using a dense, distributed, wireless network of multi-modal resource-poor sensors combined into loosely coherent sensor arrays that perform in situ detection, estimation, compression, and exfiltration.
IEEE Transactions on Signal ProcessingBandwidth-constrained distributed estimation for wireless sensor networks-part II: unknown probability density function
277 Citations2006Alejandro Ribeiro, Georgios B. Giannakis
Algorithms and studied interesting tradeoffs that emerge even in the simplest distributed setup of estimating a scalar location parameter in the presence of zero-mean additive white Gaussian noise of known variance, derive distributed estimators based on binary observations along with their fundamental error-variance limits for more pragmatic signal models.
IEEE Transactions on Information TheoryDecentralized Estimation in an Inhomogeneous Sensing Environment
237 Citations2005J.-J. Xiao, Zhongqiang Luo
A decentralized estimation scheme (DES) where each sensor compresses its observation to a small number of bits with length proportional to the logarithm of its local signal-to-noise ratio (SNR) and the MSE is within a constant factor of 25/8 of that achieved by the classical centralized BLUE estimator.
IEEE Transactions on Signal ProcessingRate-Constrained Distributed Estimation in Wireless Sensor Networks
166 Citations2007Junlin Li, Ghassan AlRegib
A theoretical nonachievable lower bound of the estimation MSE under the total bit rate constraint is stated and it is shown that the proposed algorithm is quasi-optimal within a factor 2.2872 of the theoretical lower bound.
IEEE Transactions on Signal ProcessingDistributed Estimation in Energy-Constrained Wireless Sensor Networks
142 Citations2009Junlin Li, Ghassan AlRegib
The theoretical energy-distortion performance bound for distributed estimation of a noise-corrupted deterministic parameter in energy-constrained wireless sensor networks is addressed and it is shown that the proposed algorithm is quasi-optimal within a factor 2 of the theoretical lower bound.
Path loss exponent estimation in large wireless networks
79 Citations2009Sunil Srinivasa, Martin Haenggi
This paper proposes and studies three distributed algorithms for estimating the path loss exponent at each node in a large ad hoc network where nodes are distributed as a homogeneous planar Poisson point process and the channels are subject to Nakagami-m fading.
IEEE Transactions on Signal ProcessingSensor Selection and Power Allocation for Distributed Estimation in Sensor Networks: Beyond the Star Topology
72 Citations2008Gautam Thatte, Urbashi Mitra
Optimal power allocation for distributed parameter estimation in a wireless sensor network with a fusion center under a total network power constraint is considered and asymptotically optimal solutions are derived.
Landmark Selection and Greedy Landmark-Descent Routing for Sensor Networks
61 Citations2007An Nguyen, Nikola Milosavljević +3 more
This work presents a distributed landmark selection algorithm that does not rely on global clock synchronization, and a companion local greedy landmark-based routing scheme that guarantees packet delivery in the continuous domain and works with asymmetric links.
Ad Hoc NetworksExtended message passing algorithm for inference in loopy Gaussian graphical models
44 Citations2003Kurt Plarre, Praveen Kumar
It is shown that for singly connected graphs, message passing yields an algorithm that is equivalent to the application of Gaussian elimination to the solution of a particular system of equations.
IEEE Signal Processing LettersMultihop Progressive Decentralized Estimation in Wireless Sensor Networks
42 Citations2007Yi Huang, Yingbo Hua
A multihop progressive decentralized estimation scheme is presented for 1- D, 2-D, or 3-D sensor networks where routing trees are available and is shown to be much more efficient in energy consumption than the nonprogressive decentralized estimation schemes available in the literature.
IEEE Transactions on Signal ProcessingEnergy Planning for Progressive Estimation in Multihop Sensor Networks
36 Citations2009Yi Huang, Yingbo Hua
It is shown that digital transmission is more efficient in transmission energy than analog transmission if the available transmission time-bandwidth product for each link and each observation sample is not too limited.
IEEE Transactions on Signal ProcessingOn Energy for Progressive and Consensus Estimation in Multihop Sensor Networks
22 Citations2011Yi Huang, Yingbo Hua
A generalized energy planning algorithm is developed for a progressive estimation method which exploits routing tree and channel state information and the energy cost for a consensus estimation method used in broadcast multihop WSN is analyzed.
Bandwidth-Constrained MAP Estimation for Wireless Sensor Networks
18 Citations2006Saud Al Faisal, Abdul Hakim Shah +2 more
The main goal of the paper is to design efficient estimators when the parameter can be modelled as random with a priori information and develop maximum a posteriori (MAP) estimators for distributed parameter estimation.
IEEE Transactions on Signal ProcessingInnovations Diffusion: A Spatial Sampling Scheme for Distributed Estimation and Detection
16 Citations2008Zhi Quan, William J. Kaiser +1 more
A distributed sampling scheme based on the concept of innovations diffusion to select the sensor nodes in a wireless network with distributed processing capabilities for estimation or detection applications is presented.
Quantizer design and distributed encoding algorithm for source localization in sensor networks
15 Citations2005Yoon Hak Kim, Antonio Ortega
This paper proposes a quantizer design algorithm that is optimized for source localization in sensor networks and introduces the equally distance-divided quantizer (EDQ), designed so that quantizer partitions correspond to a uniform partitioning in terms of distance.
In-Network Iterative Distributed Estimation for Power-Constrained Wireless Sensor Networks
9 Citations2012Santosh Shah, Baltasar Beferull‐Lozano
This work develops a joint optimization problem that involves both selecting a subset of active sensors and the routing structure so that the quality of estimation at a given querying node is the best possible subject to a total imposed communication cost.
Power-Aware Joint Sensor Selection and Routing for Distributed Estimation: A Convex Optimization Approach
6 Citations2012Santosh Shah, Baltasar Beferull‐Lozano
The traditional shortest-path-tree routing structure, widely used in practice, is no longer optimal, that is, the routing structures provide a better trade-off between the overall power efficiency and the final estimation accuracy obtained at the querying node.
Quantizer design and distributed encoding algorithm for source localization in sensor networks
6 Citations2005Yoon Hak Kim, Andres Gonzálo Hernández Ortega
Maximizing Network Lifetime for Estimation in Multi-Hop Wireless Sensor Networks
6 Citations2008Junlin Li, Ghassan AlRegib
This paper considers distributed estimation in energy-limited wireless sensor networks from lifetime-distortion perspective and shows that this NLP problem can be decoupled without loss of optimality and reformulated as a linear programming (LP) problem.
Joint sensor selection and routing for distributed estimation in wireless sensor networks
6 Citations2009Eduardo Portu-Repolles, Baltasar Beferull‐Lozano
This work considers a wireless sensor network deployed over a large geographical area, where a querying node wishes to perform a estimation of a localized phenomenon and proposes two approximation algorithms that jointly optimizes the sensor selection and routing structure.
IEEE Transactions on Signal ProcessingDistributed Estimation and Coding: A Sequential Framework Based on a Side-Informed Decomposition
5 Citations2010Chao Yu, Gaurav Sharma
The achievable bound for the proposed sequential framework is shown to be close to a general nonconstructive distributed bound that does not impose the sequential constraint indicating that the sequential approach may not cause a significant performance compromise.
Journal of Electrical EngineeringA Localized Recursive Estimation Algorithm for Vector Parameter Estimation in AD HOC Wireless Sensor Networks
5 Citations2010Amir Rastegarnia, Mohammad Ali Tinati +2 more
The mathematical analysis shows that the proposed recursive algorithm is an unbiased estimator of the unknown parameter and asymptotically approaches to the estimate that would be obtained if each sensor had access to the information across the entire network.
Lecture notes in computer scienceJoint Sensor Selection and Data Routing in Sensor Networks
3 Citations2005Özgür Erçetin, Özgür Gürbüz +2 more
A new joint sensor selection and routing algorithm, which selects a set of sensor nodes (sensing nodes) in a sensor network to take measurements, and determines aset of paths connecting the sensing nodes to the sink node, and designs a low complexity heuristic called SP-RE.