Hard Constrained Vertex-Cover Communication Algorithm for WSN

The communication problem is to select a minimal set of placed sensor devices in a service area so that the entire service area is accessible by the minimal set of sensors. Finding the minimal set of sensors is modeled as a vertex-cover problem, where the

  • PDF / 391,832 Bytes
  • 15 Pages / 430 x 660 pts Page_size
  • 91 Downloads / 199 Views

DOWNLOAD

REPORT


Abstract. The communication problem is to select a minimal set of placed sensor devices in a service area so that the entire service area is accessible by the minimal set of sensors. Finding the minimal set of sensors is modeled as a vertex-cover problem, where the vertex-cover set facilitates the communications between the sensors in a multi-hop fashion keeping in mind the limited communication range and battery lifespan of all sensors. The vertexcover is a subset of the coverage set of sensors; therefore, we transform the search space from a continuous domain into a discrete domain. We encoded the vertex-cover problem into the evolutionary domain, where the objective function is to select a minimal set of sensors out of the coverage sensors to act as the vertex-cover set so that its communication range covers all the coverage sensors. The experimental results demonstrate the feasibility of our evolutionary approach in finding minimal vertex cover set, which is less than 37% of total sensors used as communication sensors, in under 14 seconds with 100% coverage of the sensor nodes in wireless sensor network. Keywords: Wireless sensor network, communication, vertex cover, discrete space, optimization, evolutionary approach.

1 Introduction The wireless sensor network (WSN) has emerged as a promising platform to monitor an area with minimal human interventions. Advancements in low-power micro-electronic circuits, wireless communications, and operating systems have made WSN into feasible platforms that are used in many applications. Initially, the WSN applications were dominated and funded by the military applications, such as monitoring the activity in a battle field. Now, many civilian applications, such as environmental and habitat monitoring have emerged to benefit from the usage of WSN. There are two core problems that should be considered by deployment of any wireless sensor networks. These problems are the coverage and communication problems. The coverage problem is to place sensor devices in a service area so that the entire service area is covered. In a previous work [17], we proposed a heuristic model that maps the coverage problem into two sub-problems: floorplan and placement, which are mimicking the placement and integration modules of integrated T.-W. Kuo et al. (Eds.): EUC 2007, LNCS 4808, pp. 635–649, 2007. © IFIP International Federation for Information Processing 2007

636

M. Safar and S. Habib

circuit (IC) into a circuit board. The floorplan problem is to divide the circuit board into well-defined geometric cells, and then the placement problem determines the best cells to place the IC modules into them with minimal total wire connections. A combined optimization of floorplan and placement was coded in an evolutionary approach and found good coverage solutions as defined by the measure of quality of coverage [18]. In this work we focus on the communication problem, which will assume that sensor networks consist of two types of sensor devices. The first type of sensors (coverage sensors) is respon