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.


    Zugriff

    Zugriff prüfen

    Verfügbarkeit in meiner Bibliothek prüfen

    Bestellung bei Subito €


    Exportieren, teilen und zitieren



    Titel :

    Decentralized Message Passing Algorithm for Distributed Minimum Sensor Cover


    Beteiligte:
    Jang, Dae-Sung (Autor:in) / Choi, Han-Lim (Autor:in)

    Erschienen in:

    Erscheinungsdatum :

    2017-05-18


    Format / Umfang :

    18 pages




    Medientyp :

    Aufsatz (Zeitschrift)


    Format :

    Elektronische Ressource


    Sprache :

    Englisch





    Decentralized Message Passing for Minimum Sensor Cover Based on Belief Propagation (AIAA 2015-0358)

    Jang, Dae-Sung / Choi, Han-Lim | British Library Conference Proceedings | 2015


    Decentralized Economic Dispatch via Proximal Message Passing

    Greenough, Ryan / McClone, Graham / Alvarez, Melvin Lugo et al. | IEEE | 2022


    Iterative Message Alignment for Quantized Message Passing between Distributed Sensor Nodes

    Stark, Maximilian / Lewandowsky, Jan / Bauch, Gerhard | IEEE | 2018


    Message-Passing Strategy for Decentralized Connectivity Maintenance in Multiagent Surveillance

    Aksaray, Derya / Yasin Yazıcıoğlu, A. / Feron, Eric et al. | AIAA | 2015