Forwarding Set Based Distributed Algorithm for Connected Dominating Set in WSN

作者：Tang, Yong^*; Zhang, Jun; Wang, Wenyong; Xiang, Yu; Zhang, Jun

来源：Sensor Letters, 2012, 10(8): 1918-1924.

DOI：10.1166/sl.2012.2646

• Forwarding Set
• Connected Dominating Set
• Distributed Algorithm

In wireless sensor networks, virtual backbone network is an important approach to reduce reduplicate data transmission, save energy and bandwidth. Constructing a virtual backbone is identical with calculating connected dominating set, which is a NP-complete problem in graph theory. An algorithm using only 1-hop neighbor's information to attain CDS, named FWCDS (Forwarding set based distributed algorithm for Connected Dominating Set), is proposed in this paper. FWCDS algorithm is an enhancement of OHDC algorithm. There are two stages in the calculating process of our algorithm. In the first stage each node calculates the forwarding set severally. In the second stage, each node in the forwarding set determines whether it is a dominating node. Simulation results show that less extra messages and less convergence time is achieved by the algorithm with smaller CDS size.

• 出版日期2012-12
• 单位电子科技大学