A new phase for screening redundant broadcast nodes in source-independent broadcasting protocols

Abstract

Following the distributed approach, source-independent broadcasting protocols select a subset of nodes in a network as broadcasting nodes to cover the entire network. The selection of broadcasting nodes is performed prior to actual message transmission. These broadcasting nodes collectively form a connected dominating set or CDS. Aiming at finding a minimum CDS, existing source-independent broadcasting protocols consist of two phases. In this paper, we propose to add a third phase to eliminate unnecessary nodes in a CDS while ensuring all remaining nodes are still connected. We call it the redundant node screening phase. This paper shows that this new phase is a very important element that has been ignored by existing source-independent broadcasting protocols. When applying the new phase on existing broadcasting protocols, the savings in terms of number of nodes in the CDS could be as high as 21% in a 1000m x 1000m network of 20 nodes. © 2011 IEEE.