دانلود رایگان ترجمه مقاله پوشش منطقه صرفه جویی انرژی با الگوریتم های زمانبندی گره دوربین تکاملی (نشریه اسپرینگر 2015)

پوشش منطقه صرفه جویی انرژی با استفاده از الگوریتم های زمانبندی گره دوربین تکاملی در شبکه های حسگر بصری

Energy efficient area coverage by evolutionary camera node scheduling algorithms in visual sensor networks

Abstract

Area coverage is an important research issue in the field of visual sensor networks (VSNs) because of the inherent constraints of VSNs, such as non-rechargeable energy resources and directionality of the sensing range of camera nodes. The dense deployment of camera nodes makes it possible to provide a satisfactory area coverage for a longer duration. At the same time the rest of camera nodes can be turned off and be scheduled to alternate the active nodes when it is necessary. In this paper, we define area coverage problem in VSNs aiming to minimize blind and redundantly covered grid cells of a desired area and energy distortion of camera nodes. Then we propose two scheduling algorithms for camera nodes which are randomly deployed to k-cover the desired area. In the first algorithm named evolutionary camera node scheduling (ECNS), we aim to achieve maximal area coverage by putting the smallest number of camera nodes into active mode and to minimize blind and redundantly grid cells. Since the objectives considered in ECNS conflict each other, we employ adaptive weighted sum method to formulate our objectives into a linear equation and then we propose a genetic algorithm to find the minimum value of the integrated linear equation. In the second algorithm named energy aware evolutionary camera node scheduling (EAECNS), we propose a method to strike a balance between the energy consumption of all camera nodes while it is providing satisfactory coverage of the target area and keeping the number of redundantly covered grid cells down. We evaluate the performance of both algorithms in terms of coverage, number of live nodes and redundancy by subsequent simulations. Also, we show that EAECNS has superior performance in comparison with ECNS and other state-of-the-art algorithms.

1 Introduction

Visual sensor networks (VSNs) consist of a large number of camera nodes each of which integrate capabilities of an image sensor, an embedded processor, and a wireless transceiver. Camera nodes in a VSN form a distributed multihop wireless network, where each node can capture image, process data locally and collaborate with other nodes to provide the system user application-specific information about intended targets. The powerful collaboration between nodes and the low cost of VSNs are some of the clear advantages that make these networks suitable for a variety of applications. Today, VSNs are widely used in different areas ranging from surveillance, monitoring and traffic controlling to advanced health care delivery and automated assistance for elderly people (Akyildiz et al. 2007, 2008; Soro and Heinzelman 2009; Hu and Kumar 2003; Reeves et al. 2005; Charfi et al. 2009).

In many typical VSN applications to successfully accomplish sensing tasks, camera nodes should cover the entire desired area. Therefore, area coverage problem is considered an important research issue especially when it comes to inherent characteristics of VSNs such as non-rechargeable energy resources and directionality of the sensing range of camera nodes (Guvensan and Yavuz 2011; Costa and Guedes 2010; Ai and Abouzeid 2006). According to the literature, many solutions have been proposed so far based on greedy, genetic and particle swarm optimization algorithms and binary integer programming methods to solve the problem of area coverage in VSNs (Cheng et al. 2007; Liang et al. 2011; Tezcan and Wang 2008a, b; Jiang et al. 2010; Kandoth and Chellappan 2009; Li et al. 2009; Morsly et al. 2012; Pham et al. 2011; Alaei and Barcelo-Ordinas 2010; Aghdasi et al. 2009; Hooshmand et al. 2013). Although the existing solutions provide suitable coverage of desired area, in majority of them it is assumed that camera nodes have the ability of rotation. This assumption needs special infrastructure and invokes high cost which is not satisfying for existing low-cost camera nodes (Tavli et al. 2012; Seema and Reisslein 2011; Newell et al. 2010; Kulkarni et al. 2005). However, there are a few number of solutions which employ high density of fixed camera nodes in a desired area and solve the area coverage problem in VSNs (Aghdasi et al. 2009; Hooshmand et al. 2013). Since these solutions do not consider the direct influence of remaining energy of camera nodes in their scheduling algorithms, they cannot induce a lot of camera nodes to be alive simultaneously and cannot prolong network lifetime while providing an acceptable coverage of the desired area.

Thus, in this paper we define area coverage problem in VSNs while minimizing blind and redundantly covered grid cells of desired area and minimizing camera nodes energy distortion as our objectives. We traverse the solution space with these three conflicting objectives. Then we rely on evolutionary methods and propose two new camera nodes scheduling algorithms to the defined area coverage problem in VSNs. We also simulate these algorithms with two different VSN scenarios to show effectiveness of proposed methods and fitness functions. The important part of our methods is emphasizing on prolonging network life time considering network power consumption distribution. Our defined fitness function is trying to schedule node in a fair way to achieve uniform power consumption in entire network. We also compared proposed methods with two other proposed methods to show effectiveness of them.

In our first scheduling algorithm for area coverage problem, we aim to provide maximal coverage by putting the least number of camera nodes into the active mode. First we apply geographical information to put the desired area into grid cells, and then we specify the grid cells covered by each camera node. We consider the objectives of minimizing blind and redundantly covered grid cells in the first scheduling algorithm. Second to obtain an acceptable compromise between the objectives which are conflicting each other, we utilize adaptive weighted sum method (Kim and De Weck 2006) to integrate them in a linear equation. Finally, we solve the area coverage problem using genetic algorithm to find the minimum value of the integrated linear equation which serves as a fitness function. Our proposed scheduling algorithm is named evolutionary camera node scheduling (ECNS).