The Research Of Broadcast Problem For Wireless Sensor Networks

Since the 1990s, the micro sensors have appeared in the world with capabilities of perception, computing and communication. The wireless sensor networks, which generally consist of miniature and low-cost sensors, have a great prospect and receive great attention by government and scholars.Broadcasting is a widely-used operation in wireless sensor networks, which can be used to transfer control information, important data, alarm signal, information sharing, etc. It is also an important method to build routing. Generally, the wireless sensor node is budgeted with battery, which has limited energy, and replenishment/ recharge of the battery might be impossible. Achieving energy-efficient broadcasting has important theoretical significance and application value on improving the network performance and prolonging the network lifetime. The existing works on broadcast problem have made great achievements, but further researches are needed for energy-efficient broadcast issue. In addition, most of related works are based on reliable communication environment, rarely concern the unreliable communication environment, which show great gap between the practical application and theoretic works. Aiming at these shortages, we analyze the characteristics of broadcasting in wireless sensor networks and summarize the current broadcast algorithms. Focusing on achieving the energy-efficient broadcasting, we carry out the research on three different angles.(1) In case that the transmitting power of nodes can not be adjusted, the problem of finding a broadcast tree with the number of non-leaf nodes minimized is equivalent to the problem of find the minimum connected dominating set in graph, which is proved to be NP-complete. In this paper, we introduce an efficient heuristic algorithm to build the minimum connected dominating set, and propose a minimum energy-consumption broadcast scheme. Experimental results have shown that the proposed algorithm can find fewer forwarding nodes and balance the energy distribution of the nodes, which prolongs the network lifetime.(2) In case that the transmitting power of nodes can be adjusted, the problem of seeking a broadcast scheme with minimum energy-consumption has been proved to be NP-hard. The particle swarm optimization algorithm has a good performance on solving the NP-hard combinatorial optimization problems. In this paper, we apply it to the problem of minimum energy-consumption broadcast, and propose a local optimization algorithm to improve the feasible solution searched by particles. Experiment results have shown that the proposed algorithm can find optimal and near optimal solutions.(3) In the realistic communication environment, due to the noise interference, signal attenuation and other factors, the wireless communication link is unreliable. Firstly, we analyze the minimum energy consumption of communication between adjacent nodes.Then we discuss the relationship between the multi-hop relay strategy and the location information of nodes. On the basis of above works, we finally present a PSO-based broadcast algorithm for minimum broadcast tree, which can guarantees all the nodes receive the packet with the probability no less than P* and minimize the energy consumption.