Research on relay node placement algorithm based on its capacity limitation in WSN Energy consumption problem is one of the key issues in Wireless Sensor Network (WSN). Usually sensor nodes are far from one or more sink nodes. In such a case, it calls for deploying some relay nodes as the interval nodes to transmit data from sensor nodes to sink nodes. A relay node placement algorithm in twotiered WSN model is proposed in this thesis. This algorithm first constructs an optimum spanning tree for unlimited number of relay nodes. Then, a greedy strategy was put forward to remove some relay nodes from the tree. Under the restriction that each relay node must satisfy its communication capacity limitation, the greedy strategy aims to minimize the total energy consumption to prolong the lifetime of whole network.

Adaptive Scatter Search to Solve the Minimum Connected Dominating Set Problem for Efficient Management of Wireless Networks An efficient routing using a virtual backbone (VB) network is one of the most significant improvements in the wireless sensor network (WSN). One promising method for selecting this subset of network nodes is by finding the minimum connected dominating set (MCDS), where the searching space for finding a route is restricted to nodes in this MCDS. Thus, finding MCDS in a WSN provides a flexible lowcost solution for the problem of event monitoring, particularly in places with limited or dangerous access to humans as is the case for most WSN deployments. In this paper, we proposed an adaptive scatter search (ASSMCDS) algorithm that finds the nearoptimal solution to this problem. The proposed method invokes a composite fitness function that aims to maximize the solution coverness and connectivity and minimize its cardinality. Moreover, the ASSMCDS methods modified the scatter search framework through new local search and solution update procedures that maintain the search objectives. We tested the performance of our proposed algorithm using different benchmarktestgraph sets available in the literature. Experiments results show that our proposed algorithm gave good results in terms of solution quality.