A novel broadcast scheduling strategy using factor graphs and the sum-product algorithm

This paper presents a novel self-organizing distributed algorithm for finding a broadcasting schedule in a packet radio network via only local collaborative interactions among neighboring network stations. Inspired by the huge success of the low density parity check (LDPC) codes in the field of error control coding, we transform the broadcast scheduling problem (BSP) into an LDPC-like problem through a factor graph. In the proposed algorithm, the constraint rules of the BSP are divided into many simple local rules, each of which is enforced by a local processing unit in the factor graph. The soft-information, describing the probability that each station will transmit a data packet, is then efficiently exchanged among the local processing units by using the sum-product algorithm to iteratively optimize the broadcasting schedule. Simulation results indicate that the proposed algorithm performs better than the other existing central-processing algorithms in terms of the channel utilization and the average packet delay. This is true especially when the network scenario is very complex. Furthermore, the proposed algorithm is both low in complexity and completely distributed, which makes it suitable for implementation in practical network applications.