Abstract
Factor graphs, together with soft-information-passing sum-product algorithms, are known to be able to elegantly solve complex multi-dimensional optimization problems in a distributed low-complexity manner and are likely to reach an optimal solution. One famous recent application of the factor graph is on the LDPC (Low Density Parity Check) code, which virtually pushes the channel capacity to the Shannon limit. In this thesis, we propose to apply the factor graph ideas to solve network problems in wireless scenarios. We believe this approach is revolutionary and its impact is significant. Position location, dynamic channel assignment, and broadcast scheduling problem are all wireless network problems with various degrees of complexity. Up to now, people always go for sub-optimal solutions in solving these problems due to (part of) the following reasons: 1) There are way too many parameters to optimize in a wireless network. 2) The network parameters interact among themselves jointly in a very complicated way and difficult to optimize. 3) Collecting all the network parameters from all the network nodes to have a centralized joint process is unpractical. 4) Most distributed approaches proposed in the literature are only locally optimal, sometimes far worse than the globally optimal solution. Since network problems are by nature distributed, which happens to perfectly suit the characteristics of the factor-graph-based algorithms. Quite a few brand new factor-graph-based algorithms are proposed in this thesis to solve the wireless network problems described above. These algorithms are expected to reach the globally optimal solution while remaining distributed and very low complexity. In addition, these algorithms can be applied to TDMA/CDMA/OFDMA systems, i.e. systems with respectively 2G/3G/4G multiple access schemes. The advantages of these algorithms are especially obvious when dealing with wireless networks with multi-layer irregularly-shaped wireless network cells and with multi-rate data transmission, since these algorithms are naturally adaptive and can dynamically adjust themselves to the variation of the network scenario. Various performance bounds, robustness, stability, optimality and complexity of the proposed factor-graph-based algorithms are also systematically analyzed in this thesis.