Research On Spanner Based On Wireless Sensor Network

Sensor network is a system of monitoring, controlling and wireless communicating, by a large number of sensor nodes are randomly deployed in monitoring region within or nearby, which can through the self-organizing way constitute network. Generally speaking, once the sensor nodes was deployed, their positions will never change. Besides, each of the sensor nodes has very limited energy and the communications between the nodes must have a certain physical interference, these factors will affect the quality of the communications of the network. In this environment, the spanner has become a hot problem for researching.The main research of this thesis is to guarantee the connectivity of the wireless sensor network and make the communication link sparse as far as possible, so as to reduce the network overhead and the communication interference, finally makes the wireless sensor network more optimal, which is the key technology of the spanner. In fact, the spanner is a sparse graph, which make the wireless network transformed into the graph problem and the nodes of the network correspond to the vertices of the graph, the links correspond to the edges of the graph. In this way, the network optimization problem is transformed into how to make a relatively sparse graph. Firstly all the nodes in the network is defined as the vertices in the graph, for any two vertices of t-path; and then query link of other nodes by the signal source shortest path algorithm, according to the ratio t, marker the link to the new t-path; and so on, finally we can get a network of spanner, obviously, this involves the algorithm to construct spanner. This thesis is based on the classical greedy algorithm, and by using the data structure of WSPD and the weight matrix, which has shown that the TB-Greedy is an advanced algorithm, in addition, in the doubling metric space, by using properties of dumbbell theorem and WSPD has proved the validity and feasibility of the algorithm in practical operation. Finally, this thesis makes the theory into practice, taking into account of the physical interference of the nodes during the TB-Greedy implementation process, which makes our algorithm more close to the reality. The next work is to decrease the space complexity and make the TB-Greedy close to the optimal spanner algorithm.Through a large number of the research, we can draw the following conclusions: TB-Greedy algorithm ensures the connectivity of the network conditions and get the spanner is relatively sparse, and the time complexity is greatly improved; at the same time, it not only reduces the network overhead, but also reduces the physical interference between the nodes. We also use simulation to show the correctness and feasibility of the TB-Greedy algorithm, so this thesis has certain value for studying. The thesis mainly introduces the basic knowledge about spanner, involves the network model and interference model, the common spanner algorithms and the specific research ideas and feasibility analysis of the TB-Greedy algorithm,the future work and so on.