Research On Optimation Problem Of Wireless Sensor Networks Using Differential Evolution Algorithms

The Internet of things, big data and cloud computing are the development tendencyin the future and the hot spot of research. Wireless sensor network (WSN) is the infras-tructure of the Internet of things and big data, which is also known as the prototype ofthe Internet of things. WSN consists of a large number of wireless sensor nodes withwireless communication and computation ability, which has the ability of informationcollection, information transmission and information processing, and has the flexibility,self-organization, dynamic, data-centric for a characteristic. These characteristics of WS-N are very similar to the characteristics of the large data and Internet of things, hence, theresearch on WSN has strong practical significance and broad prospects.The deployment of wireless sensor network need to consider the energy saving andcoverage, these requirements caused many complex optimization problems in WSN, suchas the longest survival time problems, the maximum coverage problem and the optimalpath problem.To tackle the above NP-hard problems, the researchers found that based on the ideaof nature, using evolutionary algorithm with the Darwin’s evolution theory show the bet-ter performance. Diferential Evolution(DE) is a kind of evolutionary algorithms, whichhas received wide attention with advantages of simple structure, fast convergence, androbustness. There are three main control parameters of the DE algorithm: the mutationscale factor, the crossover constant and the population size. DE algorithm has been suc-cessfully applied in diverse fields such as pattern recognition, bioinformatics, engineeringoptimization and combinatorial optimization problems. However, the standard difer-ential evolution has the defect of premature and stagnation when applied in optimizingproblems. Consequently, we should research and improve present algorithms in order tomake them be applied efectively.This dissertation main content is using diferential evolution to research some opti-mization problems in wireless sensor network (WSN). Firstly to solve the optimal pathproblem in WSN, the crossover problem of single objective is studied, and the superior-inferior (SI) crossover scheme is introduced to improve the original algorithm. Then, forsolving the two-objective coverage optimization problem of WSN, non-dominated sort-ing and crowding distance calculation in multi-objective diferential evolution algorithm are studied. The fast multi-objective diferential evolution is proposed to enhance the per-formance of the original algorithm. In addition, using the diferential evolution to solveseveral optimization problems in wireless sensor network. Including the use of single ob-jective diferential evolution to solve the largest survival time problem. Using the singleobjective diferential evolution with SI scheme to solve the optimal path problem. Usingfast multi-objective diferential evolution to solve the problem of two-objective coverageproblem.In this dissertation, the main research work is as follows:（（1））Researched on superior-inferior (SI) crossover scheme for DETo solve the optimal path problem in WSN, the crossover problem of single ob-jective is studied. The population diversity and search space decrease severely in thelater stage of the evolution, through mutation and crossover operations cannot reproducenew individuals based on excessive aggregation of individuals. In order to improve thepopulation diversity of DE, this chapter aims to present a superior-inferior (SI) crossoverscheme based on DE. Specifically, when population diversity degree is small, the superior-inferior crossover is performed to improve the search space of population. Otherwise,the superior-superior crossover is used to enhance its exploitation ability. Our schemeis implemented before crossover operation, which only adjusts the position of some in-dividuals in target and mutant vector In addition, the theoretical analysis of SI schemeis provided to show how the population’s diversity can be improved. In order to makethe selection of parameters in our scheme more intelligently, a self-adaptive SI crossoverscheme is proposed. Finally, comparative comprehensive experiments are given to illus-trate the advantages of our proposed method over various DEs on a suite of24numericaloptimization problems.（（2））Research on non-dominated solutions sorting and crowding distance formulti-objective diferential evolution algorithmFor solving the two-objective coverage optimization problem of WSN, non-dominatedsorting and crowding distance calculation in multi-objective diferential evolution algo-rithm are researched. The most famous multi-objective diferential evolution algorithmNSGAII is studied, and we found that there are some redundant operation during thenon-dominated solutions sorting.To solve high time-complexity of multi-objective evolutionary algorithm based Pare-to non-dominated solutions sorting. Based on the non-dominated solution sorted and its potential features, a sorting method which only handles the highest rank individuals incurrent population is introduced. The individuals can be chosen into the next genera-tion during the sorting operation. When the population of next generation is selectedenough, the algorithm is terminated. The method reduces the number of individuals forsorting process and the time complexity. In addition, a method of uniform crowding dis-tance calculation is given. Finally, a fast multi-objective diferential evolution algorithm(FMODE) is proposed which incorporates the introduced sorting method and uniformcrowding distance into diferential evolution (DE). Using the standard two-objective opti-mization problem ZDTl-ZDT4and ZDT6for simulation experiment. The parameters ofFMODE were obtained by experiment. Overall, simulation results show that the proposedalgorithm has greatly improved in terms of time complexity and performance.（（3））Based on diferential evolution to research lifetime maximization of wire-less sensor networksMaximizing the lifetime of wireless sensor networks (WSN) is researched with sin-gle diferential evolution (DE). This section proposes a DE-based approach that can max-imize the lifetime of WSN through finding the largest number of disjoint sets of sensors,with every set being able to completely cover the target. Diferent from other method-s in the literature, firstly we introduce a common method to generate test data set, andthen propose an algorithm using diferential evolution to solve disjoint set covers prob-lems. The proposed algorithm includes a recombining operation, which performs afterinitialization and guarantees at least one critical target’s sensors are divided into difer-ent disjoint sets. Moreover, the fitness computation in proposed method contains boththe number of complete cover subset and the coverage percent of incomplete cover sub-set. Applications for sensing a number of target points, named point-coverage, have beenused for evaluating the efectiveness of algorithm. Results show that the proposed algo-rithm is promising and simple, its performance outperforms or same with others existingexcellent approaches by both optimization speed and solution quality.（（4））Using Single objective diferential evolution to study the optimal path ofwireless sensor networksThis section studies using single objective diferential evolution with SI shceme tosolve the optimal path problem in wireless sensor networks. Firstly, the wireless sensornetwork path optimization problems are analyzed and the optimization model is estab-lished. Then use the diferential evolution algorithm as a tool to solve the model of minimum energy consumption, namely the optimal path problem. Chromosome usingthe decimal encoding, because the information transmission path is not a unified length,hence the length of each chromosome is variable. In mutation, using the diference setand union set of chromosome substitute diferential and summation of classical algorith-m. After mutation and crossover an amend operation is executed, which repair the loopand illegal path into legal chromosome. This operation ensure that all individuals in apopulation are legal path that from source node to destination node. Finally, in contrast tothe classical algorithm GA and PSO, the proposed method performs better than or equalto the two contrast algorithms. The experimentation result shows the validity of proposedalgorithm.（（5））Based on Multi-objective diferential evolution to solve the two-objectivecoverage problem of wireless sensor networksThe two-objective coverage problem of wireless sensor networks is studied by usingthe proposed fast multi-objective diferential evolution algorithm. Firstly the backgroundof the two-objective coverage problem and established mathematical model are intro-duced. Then, using the multi-objective diferential evolution algorithm to solve this prob-lem. Meanwhile this section provided the chromosome encoding for the two-objectiveproblem, the design of fitness function, non dominated sorting, the overall framework ofalgorithm. In solving this problem, the use of restructuring operation to ensure the at leastone of the key goals of the sensor was assigned to diferent subset, so as to improve theprobability of finding the maximum of full coverage subset. To verify the validity of theproposed method, the comparative experiment is performed on six test set. According tothe optimal solution set numbers and quality of solutions of the highest level, the proposedalgorithm is superior to the contrast algorithm. In addition, from diferent parameter com-binations, mutation method to carry out the simulation test, which obtain the appropriateparameter for the algorithm. So as to verify the efectiveness of the proposed method.