Date Added: Oct 2009
In wireless ad hoc networks, due to the dynamic topology changes, multi hop communications and strict resource limitations, routing becomes the most challenging issue, and broadcasting is a common approach which is used to alleviate the routing problem. Global flooding is a straightforward broadcasting method which is used in almost all existing topology-based routing protocols and suffers from the notorious broadcast storm problem. The Connected Dominating Set (CDS) formation is a promising approach for reducing the broadcast routing overhead in which the messages are forwarded along the virtual backbone induced by the CDS. In this paper, the authors propose an intelligent backbone formation algorithm based on Distributed Learning Automata (DLA) in which a near optimal solution to the minimum CDS problem is found.