Applications Of GA To Solving Dynamic Coverage Problems In Wireless Sensor Networks

Wireless Sensor Networks (WSN) refer to the cheap sensor nodes deployed in large numbers within a certain scope, through which a self-organized multi-hop network system is formed by wireless communication to collect information in time, process by mutual contact, transfer information and send results to the observers. The application of WSN integrates sensor technology, embedded computing technology, distributed information processing and communication technology. WSN enables people to acquire a huge number of detailed and reliable information at any time, location and circumstance. WSN expands people's ability to acquire information, connects the objective physical information with transmission networks, and provides people with the most direct, effective and authentic information. Therefore, WSN can be widely applied to the national defense military, national security, navigation, environmental monitoring, traffic management, health care, manufacturing, anti-terrorism, disaster fighting and other fields. The potential practical value of WSN has already caused great attention in the academic and industrial field from many countries. WSN are recognized as one of the technologies which have a tremendous influence in the 21st Century.Due to the constraints of size and cost, we normally use the battery with limited capacity to provide energy to sensor nodes. In addition, due to the great number of sensor nodes which are usually deployed in the desert, the battlefield and other dangerous environment, the replacement and charge of the battery is not realistic. Therefore, how to make the efficient use of limited energy to maximize survival time of the networks is the key challenge for the design of WSN.In WSN, the large number of sensors and intensiveness of sensor nodes make it feasible for us to save energy. Since the number of actually-used sensors is often far greater than the minimum number of sensors needed in our target region, sensor networks usually have a great surplus of sensors. In order to achieve the purpose of detecting the target region effectively, we just need to activate part of sensors in the sensor networks, while the remaining sensors can be set to sleep. When the energy of activated sensors has been depleted, we can activate dormant sensors to ensure that WSN continues to detect the target region effectively. The rational planning of the activation order in WSN can effectively extend the life of WSN. How to plan the activation orders to achieve the goal of energy saving is known as the dynamic coverage problem of WSN, which is discussed in this thesis. Genetic Algorithm (GA) as a new type of optimization method, which owns the characteristic of parallel search and group optimization, has been widely applied to solving various problems with NP difficulty. The dynamic coverage problem of WSN is a typical problem of multi-objective combination and optimization, that is, it is not only necessary to guarantee the network to achieve a specific level of coverage, but also to extend the working hours of the network. Therefore, using genetic algorithms to solve the dynamic coverage problem of WSN is a feasible way.In the process of using genetic algorithms to solve the dynamic coverage problem of WSN, the author does the following work in this thesis:1) Analyze the previous studies of applying genetic algorithms to solving the dynamic coverage problem of WSN, and point out their advantages and disadvantages.0/1 encoding genetic algorithm is a very direct and simple encoding way and its decoding process is also very simple. However, a large number of infeasible solutions may appear in the process of implementation, which requires additional algorithm to correct. Although sub-integer sequence method can avoid the appearance of infeasible solutions, the decoding process is too complicated.The above two reasons lead to that these two algorithms are not satisfactory. In addition, the study of dynamic coverage problem is mainly intended to consider how to make use of redundant nodes to increase the efficiency of energy and prolong the survival time of networks, but the present study is mainly focused on how to use the least energy to achieve specific coverage in a given T period of time. This may lead to the excessive use of the nodes around the center of coverage region, while the nodes at the edge of network have low activation probability, which is unbeneficial both to the balance of network load and to the continuity of the survival time of network.2) Based on the above review of previous algorithms, the author puts forward the row encoding method based on the sensor's electricity. This effectively prevents the emergence of infeasible solutions beyond the time of the sensor's activation and also increases the average fitness of the initial group. On the basis of this encoding method, the author also designs the cross operator and genetic operator.This thesis adopts 0/1 encoding method, which can make use of the simplicity of the 0/1 encoding method. However, solutions educed by 0/1 encoding method can map the entire solution space. Due to the limitation of electricity carried by sensors, not all the solutions are feasible. Therefore, restrictions should be added in the process of the generation of the initial group and genetic manipulation. In this way, the solutions can satisfy the restriction of electricity carried by sensors, which can greatly improve the overall fitness of the group and speed up the convergence of algorithm.3) Apply the minimum number of sensors needed to reach the specific coverage of WSN to the algorithm, which further enhances the average fitness of the group. Suppose that the minimum number of sensor nodes needed to reach the specific coverage of WSN is M, then the individual solutions, whose activated sensors in a certain period are less than M, will not be the satisfactory feasible solution. In the process of the formation of the initial group, we aim to ensure that the number of activated sensors of each individual at any time is greater than M through the revised algorithm of each formed individual. In this way, we can further enhance the average fitness of the group, and ensure that this feature will not be destroyed in the process of crossover and mutation.4) Make an analysis of the reasons why sensor nodes need a phased activation.The main reason why sensors need a phased activation is to respond to the difference in the initial electric quantity of each sensor. If the initial electric quantity of each node in the network is different, then the sensors with more electric quantity can be activated several times.Finally, through the experiment, the optimum value of each parameter of the algorithm is given. And good results have been achieved in the experiment.