Spokesmen Election Problem Revisited

The spokesmen election (SE) problem was first proposed in the wave expansion broadcast (WEB) protocol for minimizing broadcast latency in wireless multihop networks. It refers to how to select a set of transmitters from all informed nodes so that the number of uninformed nodes having correct reception is maximal. In this paper, the authors formulate the SE problem into posiform maximization problem, which is a special case of pseudo-Boolean optimization problems. Since maximizing posiform f is equivalent to finding the stability number of f´s conflict graph, existing approximate algorithms for computing stability number could be utilized to find a near- optimal solution of SE problem; and new lower bound of the number of uninformed nodes with correct receptions is derived. Numerical results show that our proposed solution outperforms previous spokesmen election algorithm (SEA) in terms of both broadcast latency and broadcast redundancy.