The Study Of Target Coverage Problems In Directional Sensor Networks

Wireless sensor network is the product of development of micro electromechan-ical system,wireless communication and low power embedded technology,which is regarded as the second largest network after Internet in the world.It is a distribut-ed wireless network,composed of a large number of sensors in self-organizing and multi-hop mode,which can sense,collect and process the information of sensed ob-jects in the sensing region and then transmit the information to terminals.Wireless sensor networks have a variety of applications,like intrusion detection,environment monitoring,intelligent traffic,industrial control and disaster management,et al.In wireless sensor networks,coverage problem reflects the monitoring capability and information acquire ability of sensors,and it is an important indicator to judge the quality of network service.Directional sensor networks are generalization of sensor networks,therefore we study target coverage problems in directional sensor networks and investigate how to schedule sensors to maximize the coverage performance.The main work of this dissertation is summarized as follows.1.Fairness based target coverage maximization problem in directional sensor networks:When directional sensors have P working directions,the working direc-tions of sensors can vary from one sensing region to another.Since every time at most one working direction of each sensor can be activated,it induces coverage con-flict among the targets covered by different working directions of the same sensor.In this context,we study the fairness based target coverage maximization problem in directional sensor networks,that is,how to activate the minimum number of sensors and schedule the working directions of them to maximize the minimum accumulated coverage time of targets.To solve the problem,firstly,we select the minimum num-ber of sensors ensuring that all targets are located in the sensing circles of selected sensors,which is NP-hard,and propose a polynomial time(1 +ln?)-approximation algorithm,where ? is the maximum number of targets in the sensing circles of sen-sors.Then we represent the coverage relation between sensors and targets in the form of matrix and vector.Based on the largest demand first serve principle,the single working direction constraint and the coverage relationship of sensors and tar-gets,we design an algorithm to compute the maximum number set of conflict free targets at every slot to solve the problem.Finally,simulation results are presented to demonstrate the performance of our algorithm.2.The directional sensor network lifetime maximization problem:In direction-al sensor networks,compared with the sensors with finite separate and fixed working directions,the sensors with continuous rotation capacity have chance to cover more targets.Based on the targets with differentiated coverage quality requirements,we study the directional sensor network lifetime maximization problem,where sensors can rotate continuously round their centers.Our goal is to maximize the lifetime of sensor network satisfying the coverage quality requirements of all targets.Since sen-sors have infinite working directions by rotating continuously,we study the intrinsic relationship between sensors and targets,then propose sensing direction partition algorithm to find all non-redundant working directions for each sensor,which leads to significant dimension reduction.Based on that,we propose an efficient heuristic algorithm to solve the target coverage problem by analyzing the characteristics of sensors and the coverage requirements of targets.Besides,we get an upper bound of the optimal solution for the problem.Finally,simulation results are presented to demonstrate the performance of our algorithm.3.Maximum full-view target coverage problem in camera sensor networks:Camera sensor networks are one kind of directional sensor networks,which consider facing directions of targets on the base of working directions of sensors.Full-view coverage is,for any facing direction of a target,there is at least one camera sensor can capture its positive information.Compared with traditional coverage,full-view coverage can improve coverage quality and achieve target recognition.However it needs a large number of camera sensors to achieve full-view coverage of all targets,which requires high cost.On this background,we investigate the maximum full-view target coverage problem in camera sensor networks,where camera sensors have P working directions,aiming at maximizing the number of full-view covered targets by scheduling the working directions of camera sensors.We prove the problem is NP-hard and propose an approximation algorithm with(1-1/e)performance ratio and an efficient heuristic algorithm to address the problem.Finally,simulation results are presented to demonstrate the performance of our algorithms.