## 1 Introduction  
One of the most important variations of the dominating set (DS) problem is its connected version, which is a subset of connected nodes (vertices), where each node in the graph is in the connected dominating set, or adjacent to some nodes in the connected dominating set. Recently, the minimum connected dominating set (MCDS) problem has obtained wide popularity due to its applications in wireless sensor networks (WSN) and mobile ad hoc networks. Generally, in real-life problems that can be represented as a MCDS problem, it is not necessary to acquire the optimal solution, as near-optimal solutions are adequate in most applications [1]. Unlike traditional computer networks, there is no pre-defined fixed infrastructure as a hierarchical structure for WSNs. Consequently, it is difficult to achieve routing scalability and efficiency [2]. Using a connected dominating set (CDS) to form a virtual backbone (VB) in WSNs is a promising technique to enhance the performance and improve the efficiency of routing protocols. All network nodes are dominated by the set of nodes in CDS, and packets can be forwarded from the source to the destination node through the CDS. Thus, using CDSas VB reduces the average message load of a WSN and improves routing performance. In addition to that, the routing algorithm adapts quickly to any changes in network topology [3]. The improvement of routing performance in wireless networks results in energy saving and interference reduction as well as flooding restriction in the network. Such improvements require minimizing the size of CDS as possible. Finding a minimum CDS (MCDS) is usually an NP-hard problem and, in general, cannot be solved exactly in polynomial time [4]. Recently, meta-heuristics have become among the most successful computational methods to find good solutions for real-life optimization problems in many fields such as science, engineering, economics, and business, by exploring the solution search space of these large problems. Those algorithms reduce the effective size of the space and explore that space efficiently [5]. In fact, meta-heuristics are classified into three different categories. The first includes point-to-point techniques such as simulated annealing and tabu search, the second includes population-based techniques such as genetic algorithms and scatter search, and the third includes hybrid techniques that combine techniques from the first two categories such as memetic algorithms [6]. Scatter search (SS) is one of the most popular meta-heuristic algorithms based on the population-based technique that has effectively been applied to many hard optimization problems. The foundation, basic concepts, and principles of that technique were initially proposed in the 1970s [5]. The foundations of scatter search derive from previous strategies for combining decision rules and constraints. Usually, combining elements yields solutions better than one based only on original elements. Unlike genetic algorithms, scatter search is based on the hypothesis that systematic designs and methods create new solutions more than those derived from randomization. Furthermore, scatter search uses strategies for search diversification and intensification that have effectively been applied in varied optimization problems. Actually, the SS method is very effective and flexible as it is not restricted to a single uniform design and all SS elements can be implemented in many ways and varied degrees of sophistication [7]. In this paper, we propose an adaptive scatter search algorithm for finding the minimum connected dominating set, which is abbreviated to ASS-MCDS. It uses an on/off variable representation of solutions in searching for the MCDS and uses a composite fitness function to measure the quality of the solution. To measure the quality of each solution, the fitness function takes into account the size of the domination set as well as the connectivity between the nodes in the graph.