Title: Minimum Connected Dominating Set Algorithm Based on Learning Automata
Abstract: Connected Dominating Set(CDS) has a wide range of applications in wireless networks.For the Minimal Connected Dominating Set(MCDS) problem,an approximation algorithm is presented based on an improved Distributed Learning Automata(DLA).The proposed algorithm considers not only the deeper exploration with random selections,but also the strategy of backtracking.The dominating tree is constructed using only neighborhood information,and some properties of the dominating tree are analyzed on Unit Disk Graph(UDG) to model networks.Experimental results on those graphs show the superiority of the proposed algorithm over the existing algorithms in terms of the MCDS size.
Publication Year: 2011
Publication Date: 2011-01-01
Language: en
Type: article
Access and Citation
AI Researcher Chatbot
Get quick answers to your questions about the article from our AI researcher chatbot