Topology control technology is one of the most important technologies in wireless sensor networks. In a network topology generated by a wireless sensor network, there is a topological edge between two nodes that can communicate directly. If there is no topology control, all nodes will work with maximum wireless transmission power. In this case, on the one hand, the limited energy of the nodes will be quickly consumed by the communication components, reducing the life cycle of the network. At the same time, the wireless signal of each node in the network will cover a large number of other nodes, resulting in frequent wireless signal conflicts, affecting the wireless communication quality of the node and reducing the throughput rate of the network. On the other hand, there will be a large number of edges in the generated network topology, resulting in a large amount of network topology information, complicated route calculation, and a waste of precious computing resources. Therefore, it is necessary to study the topology control problem in wireless sensor networks. On the premise of maintaining certain global properties of the topology, by adjusting the transmission power of nodes to extend the network life cycle, improve network throughput, reduce network interference, and save nodes Resources.
The nature to be satisfied
The goal of the topology control algorithm is to make the generated network topology satisfy certain properties by controlling the transmission range of the nodes, so as to extend the network life cycle, reduce network interference, and increase throughput.
It is generally assumed that the nodes are distributed on a two-dimensional plane, and all the nodes are isomorphic and use undirectional antennas. Using a directed graph to model a wireless sensor network, if the transmission power Pi of node i is greater than the transmission power Pij required from node i to node j, then there is a directional edge from node i to node j. The topology generated when all nodes work at maximum power is called UDG graph (Unit Disk Graph).
Topology control should make the network topology satisfy one or more of the following properties:
Connectivity—In order to achieve mutual communication between nodes, the generated topology must ensure connectivity, that is, any node can send messages to another node. Connectivity is a property that any topology control algorithm must guarantee. It can be known from the definition of UDG graph that the connectivity of UDG graph is the maximum connectivity that the network can provide, so it is generally assumed that UDG graph is connected. Therefore, the topology generated by any topology control algorithm is a subgraph of the UDG graph.
Symmetry—If there is an edge from node i to node j, then there must be an edge from node j to node i. Since the asymmetric link is not well supported in the current MAC protocol, and the communication overhead of the asymmetric link is very large, it is generally required that the link in the generated topology is symmetric.
Sparseness—The number of edges in the generated topology is O (n), where n is the number of nodes. Reducing the number of edges in the topology can effectively reduce the interference in the network and improve the throughput of the network. Sparseness can also simplify route calculation.
Flatness—Indicates that no two edges intersect in the generated topology. It can be seen from graph theory that meeting flatness must satisfy sparseness. Geographic routing protocol is a routing protocol that is very suitable for wireless sensor nodes with limited computing and storage capabilities. It does not need to maintain routing tables and perform complex routing calculations. It only needs to forward messages according to certain rules. But when the underlying topology is not a floor plan, geographic routing protocols cannot guarantee the reachability of message forwarding. Therefore, when a node runs a geographic routing protocol, the generated topology must meet flatness.
Node degree bounded—means that the number of node neighbors in the generated topology is less than a constant d. Reducing the number of nodes can reduce the number of messages forwarded by nodes and the complexity of routing calculations.
Spanner property-refers to the distance between any two nodes in the generated topology is less than a constant multiple of their distance in the UDG graph.
Research methods
The current research on topology control can be divided into two categories. One type is the computational geometry method, which builds the topology of the network based on certain geometric structures to satisfy certain properties. The other is the probabilistic analysis method. In the case that the nodes are distributed according to a certain probability density, the minimum transmission power and the minimum number of neighbors required by the node when the topology meets certain properties with a high probability are calculated.
1. Computational geometry
The geometric structures commonly used in this method are as follows:
The minimum spanning tree (MST) network topology is the minimum spanning tree measured by the Euclidean distance between nodes. The transmission radius of a node is set to the length of the longest side adjacent to the node. A network with MST topology can ensure network connectivity. Due to the huge cost of constructing MST in a distributed environment, a compromise method is to use local MST to set the transmission range of the node.
GG graph (Gabriel Graph) When the transmission power is proportional to the square of the transmission distance, the GG graph is the most energy-efficient topology. MST is a subgraph of GG graph, and GG graph also satisfies connectivity.
The RNG graph (RelaTIve Neighbor Graph) is sparse between MST and GG graphs, and the connectivity is also between MST and GG graphs. It is better than MST and conflict interference is better than GG graphs, which is a compromise between the two. RNG diagrams are easy to construct with distributed algorithms.
DT diagram (Delaunay TriangulaTIon) The intersection of UDG and DT diagram is called UDel diagram (Unit Delaunay TriangulaTIon). UDel diagram is a sparse plan view, suitable for geographic routing protocols, energy saving, simplified route calculation, and interference reduction, so it is very suitable as a wireless underlying topology.
Yao Graph researchers have proposed many variations of Yao Graph, such as using Yao Graph on GG graphs and GG graphs on Yao Graph to reduce the number of edges in Yao Graph while maintaining the Spanner property.
θ-Graph is very similar to Yao Graph. The difference is that Yao Graph selects the closest node in each sector to establish the link, while θ-Graph selects the node with the shortest axis projection in the sector to establish the link.
2. Probabilistic analysis method
The developed random graph theory is not suitable for wireless sensor networks. In fact, the random graph assumes that the existence of edges between any two nodes is independent of each other. This assumption does not conform to the characteristics of wireless sensor networks. To solve this problem, the researchers proposed the theory of geometric random graphs. In this theory, nodes are distributed in the d-dimensional region R according to a certain probability density. The researchers studied certain properties of this node distribution, such as: the longest link to the nearest neighbor, the length of the longest side in the European minimum spanning tree, and the total cost of MST. Recently, researchers have used geometric random graph theory to study some basic properties of wireless ad hoc networks, such as connectivity.
The other two theories are continuum percolation and occupancy theory. In the continuous seepage theory, the nodes are distributed in a two-dimensional plane with a Poisson density λ. If the distance between the nodes is less than r, the two nodes are connected. It has been proved that for λ> 0, there is at most an infinite order of components (the set of connected nodes is called a component, and the order of the component is the number of nodes in the node set). However, the existence of only one infinite order component cannot guarantee the connectivity of the network. In fact, there may be many (infinitely many) nodes that do not belong to this large component, which leads to a disconnected network communication graph. Therefore, connectivity is related to the proportion of nodes belonging to large components to all nodes, and this proportion is related to the probability of seepage. However, there is currently no explicit expression for seepage probability. Because the model of continuous seepage theory is consistent with the ad hoc network model, the continuous seepage theory is used to analyze the connectivity of ad hoc networks.
In space-occupancy theory, it is assumed that n balls are put into C lattices independently. The method of putting the ball into the grid is determined by random variables that describe certain properties of the grid. The goal of occupancy theory is to determine the probability distribution (limit probability distribution) of these variables when n and C approach infinity. Occupancy theory can be used to analyze the connectivity of ad hoc networks. It can be abstracted as dividing the region R into rd small regions (grids) of the same size. In this case, it is determined that at least one node (ball )The probability.
The most important problem studied by the probabilistic method is the critical transmission range (CTR) problem, that is, the nodes are all isomorphic and the transmission range is the same, what is the minimum transmission range that connects the network. The reason for studying this problem is that in wireless sensor networks, inexpensive wireless communication components cannot dynamically adjust the transmission range. In wireless sensor networks, the transmission range of all nodes can only be set to the same value. The only way to reduce power consumption and increase network capacity is to set the transmission range to the minimum value to maintain network connectivity. The probability theory most suitable for solving the CTR problem is the geometric random graph theory. Because the critical transmission range is the longest side in the MST, the probability solution of the CTR can be derived from the probability distribution of the longest MST side. But the theory of geometric random graph is only applicable to dense ad hoc networks. Because the theory assumes that the space for placing nodes is fixed, when the number of nodes tends to infinity, the density of nodes also tends to infinity. But in reality, the density of the network cannot be great. In fact, when a node transmits, other nodes within its communication range must remain silent. If the node density is very large, when a node transmits, many nodes must remain silent, which will reduce the capacity of the entire network.
The researchers also used space-occupancy theory to analyze the critical transmission range problem in sparse ad hoc networks to ensure connectivity.
In recent years, topology control technology has become a research hotspot, and there are still many problems in this research field. First, the model used to model wireless sensor networks is too ideal. In order to obtain more realistic quantitative results, a more realistic model needs to be used. Second, the distribution assumptions of the nodes are too idealistic. General research assumes that the nodes are evenly distributed. Although this assumption is reasonable in some cases, in most cases it is too idealistic. Finally, the area where wireless sensors are placed is assumed to be too ideal. It is generally assumed that the area where the wireless sensor is placed is a flat two-dimensional plane, without considering the terrain.
High Voltage Module,High Voltage Power Module,High Voltage Booster Module,High Voltage Power Supply Module
Yangzhou IdealTek Electronics Co., Ltd. , https://www.idealtekpower.com