Decentralized Message Passing Algorithm for Distributed Minimum Sensor Cover

Cited 0 time in webofscience Cited 0 time in scopus
  • Hit : 257
  • Download : 0
This paper addresses a decentralized message passing approach for a sensor placement problem in a continuous plane, named minimum sensor cover problem: given pointwise tasks and omnidirectional coverage of sensors deployable by distributed local planners, find the minimum set of sensors that cover all the tasks. Because the solution is required to be derived in the local planners' network, a decentralized message passing algorithm is proposed with a problem conversion process into a discrete domain for applying the algorithm. By using discretization of the solution space, the minimum sensor cover problem can be converted to a combinatorial optimization (i.e., the geometric set cover), and then it is formulated as a maximum a posteriori state assignment problem. Belief propagation is a decentralized algorithm based on local iterative message passing to solve the maximum a posteriori state assignment problem, but it has convergence and feasibility issues. Therefore, the proposed algorithm is modified from the belief propagation to obtain stable and guaranteed feasible solutions, and its time complexity in a decentralized computation is analyzed. Numerical simulations validate the convergence, feasibility, and preferable solution quality of the proposed algorithm against existing variants of belief propagation and the centralized greedy algorithm for the set cover.
Publisher
AMER INST AERONAUTICS ASTRONAUTICS
Issue Date
2017-07
Language
English
Article Type
Article
Keywords

BELIEF-PROPAGATION ALGORITHM; PLACEMENT OPTIMIZATION; DOMINATING SET; MAX-PRODUCT; NETWORKS; CONVERGENCE; CORRECTNESS; DEPLOYMENT; SELECTION; IDENTIFICATION

Citation

JOURNAL OF AEROSPACE INFORMATION SYSTEMS, v.14, no.7, pp.373 - 390

ISSN
1940-3151
DOI
10.2514/1.I010512
URI
http://hdl.handle.net/10203/225148
Appears in Collection
AE-Journal Papers(저널논문)
Files in This Item
There are no files associated with this item.

qr_code

  • mendeley

    citeulike


rss_1.0 rss_2.0 atom_1.0