Research Journal of Recent Sciences _________________________________________________ ISSN 2277-2502 Vol. 4(12), 106-109, December (2015) Res.J.Recent Sci. International Science Congress Association 106 Distributed Genetic Algorithm to Solve Coverage Problem in Wireless Camera-Based Sensor Networks Ahmad Habibizad Navin Department of Computer Engineering, Tabriz Branch, Islamic Azad University, Tabriz, IRANAvailable online at: www.isca.in , www.isca.me Received 27th January 2014, revised 15th June 2014, accepted 17th April 2015Abstract Wireless camera-based sensor networks have emerged as an important class of sensor-based distributed intelligent systems. These networks consist of large number of low-power camera nodes to monitor an environment such as airports, museums, traffic control, military applications etc. The most important problems in smart networks are camera coverage control that allows automatic tracking of targets and monitoring the environment. As this problem is NP-hard, so Meta heuristic methods such as genetic algorithm have been proposed to achieve near-optimal solution, which are with high time complexity. To overcome problem the distributed genetic algorithm is examined in this paper. Simulation results show that the distributed genetic algorithm results near-optimal solution faster than the genetic algorithm. Keywords:Genetic algorithm, coverage ratio, wireless camera based sensor network. Introduction Wireless Sensor Networks (WSNs) consist of a large number of low-cost and low-power sensor nodes. Recent technological developments in processing and imaging have led the development of smart camera nodes that can operate autonomously and collaboratively to meet the necessary requirements. There are a wide variety of camera nodes that can be used in camera networks deployments. Nowadays, low resolution cameras are embedded in sensor nodes being able to capture audio-visual information from the environment. Smart camera networks have a wide range of applications in areas such as security monitoring and surveillance, locating and tracking people, traffic management, health care and telemedicine12. Wireless camera networks can integrate with an existing fixed infrastructure to substantially improve the coverage and ability of these networks15,17. Moreover, they may enable ad hoc surveillance where a group of wireless cameras is deployed in situations where infrastructure is unavailable or expensive, or quick deployment is desired. For instance, such networks can be used by emergency recovery teams to monitor a disaster area to guide the search and rescue operation19. The cameras must be controlled (pan, and if available, tilt and zoom) to provide the best possible coverage of events happening within the area of interest. As the scale of cameras grows from tens to hundreds of cameras, it is impractical to rely on humans to control their setting to achieve the best combined coverage. Thus, supporting autonomous configuration of cameras to maximize coverage is a critical problem in smart camera networks. Wireless camera-based sensor networks coverage, determine how well an environment is monitored or tracked by the camera sensor nodes. Performance of directional sensing is much dependent on the presence of obstacles in the environment. As a result, finding the suitable orientation for camera sensors are noticeable problem. Therefore, orientation of multimedia sensors can be performed on the site once they have been deployed. However, such methods need an accurate field information database before being distributed in environment and are mostly applied to a small number of multi devices. Due to external effects or application-specific queries in WMSNs, multimedia nodes may need to change or re-orient their position in each time. In these networks, there have been several works on vision planning which take the geometric information as an input from database, as well as correction of the camera and the lens to adjust camera positions and settings. Currently, Genetic Algorithm (GA) is one of the most powerful Meta heuristic methods to solve optimization problems that are based on inherent selection, the process that drives biological evolution. It has been used to solve the coverage problem in multi-camera based sensor network3,7. It can reach near optimal solution but it has high time complexity to remove this complexity the distributed genetic algorithm is examined in this paper. Related Works Surveillance and maximizing the coverage of an area have been studied in great depth in wireless multimedia sensor networks. Theoretical analysis of the problem shown in10 has been used to maximize coverage of an area with less overlapping the camera fields of view. The papers7, 8 contain considerable works for the omnidirectional coverage problem to cover a plane by arranging circle on the plane. One of the classic coverage optimization problems, the Art Gallery Problem21, focuses on placing minimum number of security guards in an art gallery so that all points in the whole gallery will be under observation. In the context of Directional Sensor Networks (DSNs), Cheng et al14 Research Journal of Recent Sciences _____________________________________________________________ ISSN 2277-2502Vol. 4(12), 106-109, December (2015) Res.J.Recent Sci. International Science Congress Association 107 have proposed Maximum Directional Area Coverage (MDAC) problem to maximize the total area covered by a DSN, while minimizing the number of active sensors. In another instance, Erdem et al.16 consider the problem of determining automatic camera deployment layout to satisfy task-specific and floor plan-specific coverage requirements. Video sensors proposed in9 can only handle image with line sight between the event and the sensor. Note that method of coverage for traditional wireless sensor networks is not suitable for deployment planning of multimedia sensor networks. Some of the recent works in the context of directional sensor networks have provided optimization based solutions to address a basic instance of the problem of covering maximum targets11,13,14. Abouzeid et al11formulate the coverage optimization problem as a Maximum Coverage with Minimum Sensors (MCMS) problem, and show that MCMS is NP-complete. They formulate the MCMS problem as an Integer Linear Programming (ILP) problem to propose a centralized approach to solve the problem. Qureshi et al20 present a planning strategy to achieve a close-up biometric coverage of selected pedestrians till they are present in the coverage region. A method is proposed in to determine and increase multimedia coverage in individual sensor. Since this problem is NP-hard, even for static targets, so Meta heuristic method such as genetic algorithm, Particle Swarm Optimization have been proposed to reach near-optimal solution, But these method have high time complexity. To remove this complexity the distributed one GA is examined in this paper. Simulation result shows that the distributed GA reaches near-optimal solution in shorter time. This method is designed to adjust the position of the sensors automatically. By this method the coverage ratio of a number of nodes can be calculated and the efficiency of the method is decreased by increasing the number of nodes in this method. To overcome to this difficulty a method is proposed in next section. Basic Concepts A camera’s sensing model is mainly different from the sensing model of any other type of sensors. A traditional sensor collects data from its neighboring sensors situated in its sensing range but the camera nodes are characterized by a directional sensing model. Cameras capture images of distant obstacles from a certain direction. Some basic concepts are defined as follows: Definition 1: The area monitored by cameras is called Field of View (FOV) which is within [0, 360]. Triangular area in Fig. 1 shows the FOV of camera sensor node. Definition 2: Wireless camera-based sensor networks coverage determines how well an environment is monitored or tracked by the camera sensor nodes [5]. Coverage ratio (CR) is the percentage covered monitoring environment and is defined by (1). CR = (Monitored areas by cameras / Total area environment) * 100 (1) Definition 3: Fitness function is equal to CR for evaluation of the goodness of each solution; i.e. Particle. Some basic notations are defined as follows: j: denotes the number of nodes. R: denotes the maximum sensing range. : denotes the FoV vertex angle. : is current orientation, the vertical angle to the boundary edge of FoV. Fig. 1 shows two dimensional FoV of camera sensor nodes, , and . Figure-1 Two dimensional FOV of camera sensor nodesC: denotes the chromosome which is an array of genome with length j. C: denotes the i’th genome of chromosome C which is equal to the current orientation of i’th sensor. Ps: Population size is the number of chromosome in the iteration. Fitness function: is a function to evaluate the goodness of each particle. MF: Maximum Fitness functions in i’th iteration. Proposed Method GA: algorithm for Solving Coverage Problem in Wireless Camera-Based Sensor Networks by GA The steps of GA algorithm to find a better coverage ratio are as follows: Initialize population: Suppose the number of cameras is , and the number of chromosome is , then each chromosome is an array of genome with length j where g is the i-th camera orientation which is denoted by: C = (g, g, …) Generate chromosomes randomly. Obviously, the special position of each camera determine randomly. Calculate fitness value: Compute coverage ratio for each chromosome as Fitness value. Find maximum fitness value: Do For each chromosome Ci If the fitness value, F of chromosome C is better than the maximum fitness value then S = C and Mf =F EndDo: Select two chromosomes C and Cj randomly: Research Journal of Recent Sciences _____________________________________________________________ ISSN 2277-2502Vol. 4(12), 106-109, December (2015) Res.J.Recent Sci. International Science Congress Association 108 new1 = Crossover (C, C) new2 = mutation C Save Cnew1 and Cnew2 in new Population If (FMax - F ) then save C in new population Until (number of new population l). Update population: Population = new population Iteration: Go to step 2 while maximum iterations or minimum error criteria is not attained. DGA: proposed algorithm: the distributed Genetic algorithm for Solving Coverage Problem in Wireless Camera-Based Sensor Networks The steps in the proposed algorithm finding a better coverage ratio are as follows: Initialize population: Suppose the number of cameras is , and the number of chromosome is , then each chromosome is an array of genome with length j where g is the i-th camera orientation which is denoted by: C = (g, g, …) Generate chromosomes randomly. Divide population into Sub population. Do step 2 to step 8 in parallel for each sub population: Calculate fitness value: Compute coverage ratio for each chromosome as Fitness value. Find maximum fitness value: Do For each chromosome Ci If the fitness value, F of chromosome C is better than the maximum fitness value then S = C and Mf =F EndDo: Select two chromosomes C and Cj randomly: new1 = Crossover (C, C) new2 = mutation C Save Cnew1 and Cnew2 in new Population If (FMax - F ) then save C in new population Until (number of new population l/k). Update population: Population = new population Immigration: Select the 10% of the best chromosomes based on fitness value among the sub population and immigrate them to other sub population randomly. Receive and deletion: Delete the 10% the worst chromosomes based on fitness value among the sub population and receive the 10% of the best chromosomes from other sub population. Iteration: Go to step2 while maximum iterations or minimum error criteria is not attained. Performance Evaluation MATLAB simulator is used to simulate the proposed algorithm. All camera sensor nodes have been configured with R=30 m. In order to have better vision of cameras we set =60. Overlapping in the environment depends on the number of nodes and thus we set j=300 and K=4. A sensing field spanning area of 250*250 m has been used. Figure-2 shows the FoV of a single camera with real value. By the above assumption, genetic algorithm obtains 98.6 % coverage ratio but the proposed method obtains 98.4% coverage ratio. Also the running time of genetic algorithm is 43.66 but the running time of Parallel GA is 12.17. Table I shows the obtained results for coverage ratio and Table II shows the obtained results for time complexity. Figure-2 The FoV of a Single camera with real value Observations of presented algorithm are as follows: The proposed method can achieve the better coverage in the environment. Scalability of distributed genetic algorithm is better than genetic algorithm with camera based sensor networks can be used to cover the expanded environment such as jungles. Table-1 Coverage Ratio (%) Parallel Genetic Algorithm Genetic Algorithm Number of Camera 98.4% 98.6 % 300 Table-2 Running time of the algorithm (S) Parallel Genetic Algorithm Genetic Algorithm Number of Camera Research Journal of Recent Sciences _____________________________________________________________ ISSN 2277-2502Vol. 4(12), 106-109, December (2015) Res.J.Recent Sci. International Science Congress Association 109 12.17 43.66 300 Conclusion The main contribution of this paper is to show the ability of distributed genetic algorithm to solve coverage problem in wireless camera-based sensor networks in shorter time. A new modeling of coverage problem in wireless camera-based sensor networks is proposed to solve the coverage problem by distributed genetic algorithm. Simulation result of the presented method shows the better coverage ratio compared with the GA. The following area can be considered as future works: Solving the problem in the form of distributed or decentralized other evolutionary algorithm. References 1.Vikram P. Munishwar., et al., Scalable Target Coverage in Smart Camera Networks, in ICDSC, Atlanta, GA, USA, 2010)2.Akyildiz T. Melodia and Chowdhury K., A survey on wireless multimedia sensor networks. Computer Networks, 51(4), 921-960, (2007) 3.Collins R., Lipton A., Kanade T., Fujiyoshi H., Duggins D., Tsin Y., Tolliver D., Enomoto N., Hasegawa O., Burt P., et al. A System for Video Surveillance and Monitoring. Carnegie Mellon University, the Robotics Institute, (2000) 4.Hampapur L. Brown, J. Connell, A. Ekin, N. Haas, M. Lu, H. Merkl, S. Pankanti, I. Center and N. Hawthorne, Smart video surveillance: exploring the concept of multiscale spatiotemporal tracking. Signal Processing Magazine, IEEE, 22(2), 38-51, (2005) 5.Paxton L. and Yee J., The role of emerging technologies in imagery for disaster monitoring and disaster relief assistance, ActaAstronautica,52(2), 793-802, (2003) 6.Tezcan N. and Wang W., Self-orienting wireless multimedia sensor networks for occlusion-free viewpoints, department of electronic and computer engineering north Carolina state university, Raleigh, NC 27606, USA. Computer networks, 52(4), 2558-2567, (2008) 7.Navin A.H., et al., Solving Coverage Problem in Wireless Camera-Based Sensor Networks by Using Genetic Algorithm, in International Conference on Computational Intelligence and Communication Networks (CICN), 226229, (2010) 8.Tarabanis K.A., Tsai R.Y. and Kaul A., computing occlusion-free viewpoints, IEEE Transaction on Pattern Analysis and Machine Intelligence,2(3), 273-292 (1996)9.Krishna Reddy Konda and Nicola Conci, Global and local coverage maximization in multi-camera networks by stochastic optimization, Info-Communications Journal,2013)10.O’Rourke J., Art gallery Theorems and algorithms, Oxford University Press, New York, (1987) 11.Cardei M., Thai M. and Wu W., Energy-efficient target coverage in wireless sensor networks, in: Proc. IEEE InfoCom, Miami, Florida,USA, (2005) 12.Tian D. and Georganas N.D., A coverage-preserving node scheduling scheme for large wireless sensor networks and applications, Georgia, USA, (2002)13.Urrutia J., Art gallery and illumination problems. Handbook of Computational Geometry, 973-1027, (2000)14.Cheng W., Li S., Liao X., Changxiang S. and Chen H, Maximal Coverage Scheduling in Randomly Deployed Directional Sensor Networks. In Parallel Processing Workshops, ICPPW. International Conference on, 58-68, (2007) 15.Erdem U. and Sclaroff S., Automated camera layout to satisfy task-specific and floor plan-specific coverage requirements, Computer Vision and Image Understanding, 103(3), 156-169, (2006) 16.Akyildiz I.F, Melodia T. and Chowdhury K.R., A Survey on Wireless Multimedia Sensor Networks”, Computer Networks, 43(5), 54-67 (2006) 17.Ai J. and Abouzeid A.A., Coverage by directional sensors in randomly deployed wireless sensor networks, Journal of Combinatorial Optimization, 11(2), 21-41, (2006) 18.Cai Y., Lou W., Li M. and Li. X., Target-Oriented Scheduling in Directional Sensor Networks. IEEE Infocom, (2007) 19.Qureshi F. and Terzopoulos D., Planning Ahead for PTZ Camera Assignment and Hando_. In ACM/IEEE International Conference on Distributed Smart Cameras, 18, (2009) 20.Soro S. and Heinzelman W., A Survey of Visual Sensor Networks, (2009) 21.Akyildiz F., Su W., Sankarasubramaniam Y. and Cayirci E., Wireless Sensor Networks: a survey, Computer Networks,38(6), 393- 422, (2002) 22.Krahnstoever N., Yu T., Lim S., Patwardhan K. and Tu. P. Collaborative Real-Time Control of Active Cameras in Large Scale Surveillance Systems. In Workshop on Multi-camera and Multi-modal Sensor Fusion Algorithms and Applications, (2008)