On the Convergence and Optimality of Reweighted Message Passing for Channel Assignment Problems

Author

Moretti, M. ; Abrardo, A. ; Belleschi, Marco

Author_Institution

Dipt. di Ing. dell´Inf., Univ. di Pisa, Pisa, Italy

Volume

21

Issue

11

fYear

2014

fDate

Nov. 2014

Firstpage

1428

Lastpage

1432

Abstract

Many assignment problems, and channel allocation in OFDMA networks is a typical example, can be formulated as bipartite weighted b-matching (BWBM) problems. In this letter we provide a proof of the convergence and the optimality of the reweighted message passing (ReMP) algorithm when applied to solve BWBM problems in a distributed fashion. To this aim, we first show that the ReMP rule is a contraction mapping under a maximum mapping norm. Then, we show that the fixed convergence point is an optimal solution for the original assignment problem.

Keywords

OFDM modulation; channel allocation; frequency division multiple access; message passing; BWBM problem; OFDMA networks; ReMP algorithm; bipartite weighted b-matching problem; channel allocation; channel assignment problem; contraction mapping; fixed convergence point; maximum mapping norm; reweighted message passing; reweighted message passing algorithm; Ad hoc networks; Algorithm design and analysis; Channel allocation; Convergence; Message passing; Resource management; Signal processing algorithms; Distributed optimization; message passing; resource allocation;

fLanguage

English

Journal_Title

Signal Processing Letters, IEEE

Publisher

ieee

ISSN

1070-9908

Type

jour

DOI

10.1109/LSP.2014.2337951

Filename

6851895