Task Allocation Model And Algorithm For Sensor Networks Based On Multi-objective Optimization

Task allocation is the most important optimization problem in Wireless sensor networks (Wireless Sensor Networks, WSN), because task allocation scheme directly determines the energy consumption, which eventually determines the network lifetime. There have been multiple algorithms to solve task allocation problem, three-phase heuristic algorithm (3-PH) is one better algorithm because this algorithm took the impact of multiple factors into account it the task allocation. However, the three-stage heuristic algorithm still suffers from some limitations: (1) it is divided into three stages to solve multi-objective optimization problem, this method can not effectively coordinate the relationship of multi-objectives; (2) the random iteration algorithm’s "no memory" character makes it difficult to obtain the best individual; (3) algorithm assumes that there have not been communication conflictions between nodes, but there have been serious conflictions among nodes.To cope with the shortcomings of the Three-phase heuristic, this paper has proposed two kinds of algorithms: the improved three-stage heuristic algorithm (G3-PH) and genetic algorithm (GA) based on the critical path of nested. G3-PH algorithm proposed in this thesis coordinates the target and converts the multi-objective optimization to a single target, so as to solve the problem of coordination of multiple targets. Meanwhile, G3-PH algorithm assumes that there have been communication conflictions among sensor nodes. As long as the voltage of sensor nodes meets the requirements on the industry, the multiple communication tasks of network nodes can be executed simultaneously. However, the G3-PH algorithm is character with "no memory". Therefore, the thesis proposed GA to solve the task allocation problem, because the algorithm can deal with the problem of "no memory", so the iterative process can effective obtains the best individual generated during the evolutionary process. Meanwhile, this thesis also introduced critical path optimization algorithms and target coordinate algorithms into the traditional GA, respectively, to solve the routing problem and the multi-objective optimization problem.Finally, we compare three algorithms of 3-PH, G3-PH, GA. The simulation results show that GA is the best one to solve the task allocation problem; the network energy consumption is the smallest one. Further, the optimal network latency and the total degree of the largest network equilibrium are also achieved, which shows that GA is effective to solve the task allocation problem.