WO2010108395A1 - Quantized, multithreaded and intelligent path selection method in network - Google Patents

Abstract

A quantized, multithreaded and intelligent path selection method in network, comprises the following steps: a. establishing a topological structure diagram for an electronic network according to the topological structure of the network, numbering each edge and each node of the structure diagram, each node connecting with a node register; b. defining two nodes for which the path will be selected on the structure diagram, inputting a signal from either node, the signal being transmitted along the network topological structure, when the signal passing through certain edge or edges firstly reaches a certain node, the node register of the node recording the numbers of the edge or edges; c. radially transmitting the signal to the next node along the direction in which the transmission is enabled, based on the network topological structure, until the other node obtains the signal; d. tracing the numbers of edges recorded by the node registers, thus obtaining the path with the shortest signal transmission time between the two nodes. For the selection of the path by means of this invention, the processing time is shorter, and the precision is higher.

Description

A Quantitative Multi-thread Network Intelligent Path Selection Method

Technical field

The invention relates to a quantitative multi-thread network intelligent path selection method.

Background technique

According to the patent application No. 200810021101.1, "A quotient space coverage model for network shortest path and its construction method" refers to the technical background and actual situation. For transportation networks, power networks, and information transmission networks (such as the Internet), the shortest path search method between the two points is still based on the Dijkstra algorithm. Although the shortest path is available through the Dijkstra algorithm, for a complex network, the computation time will increase in geometric progression or occupy a huge amount of memory. Generally, the complex network is a dynamic network, and its processing time determines the accuracy of its tracking. Therefore, the accuracy of the existing network selection method is poor.

 Summary of the invention

In view of the shortcomings of the prior art, an object of the present invention is to provide a quantized multi-thread network intelligent path selection method with short processing time and high precision.

To achieve the above objective, the technical solution of the present invention is: a quantitative multi-thread network intelligent path selection method, which includes the following steps:

a. Establish an electronic network topology structure according to the topology of the network, number each side of the structure diagram and each node, and each node is connected with a node register;

b. Definition Two points on the structure diagram that need to be path-finished. One of the input signals is transmitted along the network topology. When the signal passing through one side or some sides reaches the node first, the node register of the node records the side. Or the number of the sides;

c. The signal is then transmitted to the next node along the energy transmission direction according to the network topology until the other point obtains the signal;

d. Trace the number of the edge recorded by the node register to obtain the path with the shortest signal transmission time between the two points.

step In b, a pulse counting trigger for adjusting the signal transmission time of each side is connected at the end of each side, and the trigger output end of the pulse counting trigger is connected to the corresponding node register; when the signal reaches the end of the edge When the pulse counting trigger is triggered, the pulse counting trigger starts to calculate the number of pulses of the signal. When the number of pulses reaches the set number of triggers, the pulse counting trigger is triggered, and the signal is output to the next node, and the node register records the number of the corresponding side. .

By adjusting the pulse number of the corresponding edge end pulse counting trigger or the frequency of the input signal, the transmission time of the edge signal is adjusted; and the on/off switching of the edge is controlled by serially connecting the controllable switching elements on the side.

In step b, a certain amount of impedance is connected to each side Controllable electrical components with the same value, each controllable electrical component is connected to the power supply through the switching component, and the unidirectional voltage triggering unit is connected at the end; the signal is input from one point, and the signal passes through the controllable electrical component on the side to the end of the edge. The unidirectional voltage triggering unit, the unidirectional voltage triggering unit accumulates the charge, reaches the threshold, and triggers the trigger; respectively outputs the signal to the number of the recording edge of the node register, and continues to output the signal to the connected side.

step In b, a controllable electrical component with variable impedance value is connected to each side, and each controllable electrical component is connected to the power source through the switching component, and the unidirectional voltage triggering unit is connected to the end.

By setting the impedance of the controllable electrical component, adjusting the weight of the edge, or the trigger threshold of the unidirectional voltage triggering unit, the charging time of the triggering threshold voltage is adjusted to adjust the transmission time of the edge signal.

By controlling the switching elements in series on the side, the on and off of the sides is controlled.

Current limiting elements for limiting the direction of signal transmission are connected in series on each side such that the network forms a directed network.

The starting point has a plurality or one, and the ending point has one or more;

In a directed network, when there are multiple starting points and one end point, each node register records the number of each side between each starting point and the single end point, and traces the number of the side recorded by the node register, thereby obtaining each The path with the shortest signal transmission time between the point and the single end point;

When there is one starting point and there are multiple ending points, each node register records the number of each side from the single starting point to each end point, and traces the number of the edge recorded by the node register to obtain the signal between the single starting point and each end point. The shortest path for each transmission time.

After obtaining the shortest path from the starting point O to the ending point E, the amount of time taken from the starting point O to the ending point E on the shortest path is c; the amount of time taken from the starting point O to the other node D in the shortest path is d ; the backup node F adjacent to the other node D on the shortest path and not triggered, from the other node D to the backup node F The amount of time used is X, the backup node F is selected according to the range of X+d>c, and the state of each point on the shortest path is returned to the state before the trigger, and the pathfinding process is continued for the other points of X+d≤c The node in the range of X+b>a selects the signal by X+b, so that the short path is obtained. This is the shortest path of the first backup. Repeat the above steps in the directed network. Get multiple backup paths.

After obtaining the shortest path from the start point to the end point, set the amount of the shortest path end point to a; the amount of other nodes on the shortest path is b The backup node adjacent to the other nodes on the shortest path and not triggered, the amount corresponding to the edge formed by the other nodes on the shortest path is X According to the range of X-a+b>0, the node is selected, so that the state of each point on the shortest path is restored to the state before the triggering, and the other paths continue to track the path; the nodes in the selected range are X+b Amount release The signal, thus obtaining the second short path, which is the shortest path of the first backup. Repeat the above steps to obtain multiple backup paths in the directed network.

First from the starting point to the network topology Each point in the field obtains the shortest path and the corresponding quantity t1, and then obtains the shortest path and the corresponding quantity t2 from the end point to each point in the network, wherein the corresponding quantity refers to the start/end point to the network topology diagram The time used in each point, the two quantities t1 and t2 of each point are added together, the minimum total point set and their topological connections form the shortest path between the starting point and the end point, the point set of the next smallest total amount and their sum The topological connection of points of adjacent minimum totals constitutes the second short path between the starting point and the ending point.

Compared with the prior art, the present invention has the following beneficial effects:

The path-finding method of the present invention measures the path, that is, the advantages and disadvantages of the edge, and eliminates the non-shortest path. Since the path-finding process has no real-numbered operations and the path-finding method is performed simultaneously with multiple threads, it is not necessary to examine the path of all points, so it is faster than the Dijkstra path-finding method. And the weight-to-weight ratio (the ratio of the quantity to the weight on the same arc) can be used as a regulating valve. (In the case where the unit of quantity is constant), the processing speed can be increased at the expense of the accuracy of the extra large network, and the required precision and processing can be achieved. The dynamic balance of speed to adapt to a variety of different networks. In addition, the unit quantity can be replaced with different surveys of other networks to obtain an optimal solution for this network. This ratio The A* algorithm is more adaptable and faster.

DRAWINGS

1 is a schematic diagram of a network structure using a pulse triggering method according to the present invention;

2 is a schematic structural view of a pulse counting trigger of the present invention;

FIG. 3 is a schematic diagram of a network structure using an impedance adjustment method according to the present invention.

detailed description

The invention is described in detail below with reference to the accompanying drawings.

Example 1

As shown in FIG. 1, a quantized multi-thread network intelligent path selection method includes the following steps:

a. According to the topology structure of the network, an electronic network topology structure diagram is established, and each side of the structure diagram and each node are numbered, and each node is connected with a node register; the edge is a path without a transmission direction limitation, and the node is located at the edge and the edge. At the intersection of the two.

b. Define the starting point or end point of the structure drawing on which the path needs to be found. The signal is input from the starting point, and the signal is transmitted along the network topology. When the signal passing through an edge or some side reaches the node first, the node register record of the node is recorded. The number of the side or the sides.

c. The signal is then transmitted to the next node along the energy transmission direction according to the network topology until the end point obtains the signal.

d. Trace the number of the edge recorded by the node register to obtain the path with the shortest signal transmission time between the two points.

On each side, a current limiting element for limiting the direction of signal transmission can also be connected in series to form an arc, and the arc is a path having a transmission direction limitation, so that the network forms a directed network. The current limiting element can be a current limiting diode.

In step b, a pulse counting trigger for adjusting the signal transmission time of each side is connected at the end of each side, as shown in the figure. As shown in 2, the trigger output of the pulse count trigger is connected to the corresponding node register; when the signal reaches the end of the edge When the pulse counting trigger is triggered, the pulse counting trigger starts to calculate the number of pulses of the signal. When the number of pulses reaches the set number of triggers, the pulse counting trigger is triggered, and the signal is output to the next node, and the node register records the number of the corresponding side. .

By adjusting the pulse number of the corresponding edge end pulse counting trigger or the frequency of the input signal, the transmission time of the edge signal is adjusted; and the on/off switching of the edge is controlled by serially connecting the controllable switching elements on the side.

For dynamic networks with arc or edge weight changes, the number of pulse triggers or the frequency of the input pulse signal of the corresponding arc or edge end pulse counting trigger can be adjusted to achieve tracking of this dynamic network. For a dynamic network with an indeterminate network topology, switching elements such as a switching transistor can be connected in series on an arc or an edge to control the switching of the arc or the edge, thereby implementing tracking of such a network. Among them, the weight is the value on the defined edge, the distance between the nodes or the time taken to complete the path between the nodes.

As shown in Figure 3, in step b, each side can also be connected with a certain amount of impedance. Controllable electrical components of the same value, each controllable electrical component is connected to the power source through the switching component, and the unidirectional voltage triggering unit is connected at the end; The signal is input from one point, the signal passes through the controllable electrical component on the side, and reaches the unidirectional voltage triggering unit at the end of the edge. The unidirectional voltage triggering unit accumulates the charge, reaches the threshold, triggers the trigger, and outputs the signal to the node register respectively. Record the number of the edge and continue to output the signal to the connected edge. In this embodiment, the controllable electrical component is controllable The PN junction, the switching element is a switching PN junction, and the unidirectional voltage triggering unit is a unit composed of a unidirectional step diode and a thyristor connection or a Schmitt trigger.

 In step b, each side is connected with a variable impedance value The controllable electrical component, each controllable electrical component is connected to the power source through the switching component, and the unidirectional voltage triggering unit is connected at the end. The controllable electrical component is a controllable potentiometer.

By setting the impedance of the controllable electrical component, adjusting the weight of the edge, or the trigger threshold of the unidirectional voltage triggering unit, the charging time of the triggering threshold voltage is adjusted to adjust the transmission time of the edge signal.

By controlling the switching elements in series on the side, the on and off of the sides is controlled.

With one of the release signals, the signal immediately passes through the controllable electrical component on the arc or edge, and the unidirectional voltage triggering unit that reaches the end of the arc or edge in the transmittable direction is controlled by the controllable switching electrical component. After the accumulation of charge, the charge reaches the threshold, and the unidirectional voltage trigger unit triggers; the output signal to the node register respectively records the number of the arc or edge, and continues to output the same signal as the signal release point to the connected arc or edge. Repeat the above process until another point is obtained. Since the nodes through which the signal passes are registered with the path of the signal source, the path traced through the node register is traced to obtain the optimal path.

For a dynamic network with arc or edge weight variation, the total impedance value of the controllable electrical component on the corresponding arc or edge, or the trigger threshold of the unidirectional voltage triggering unit, can be adjusted to adjust the current collection time of the triggered threshold voltage. Achieve tracking of this dynamic network. For dynamic networks with uncertain network topologies, the controllable switching elements can be used to control the direction, arc or edge of the arc to achieve tracking of such networks.

The starting point has a plurality or one, and the ending point has one or more;

In a directed network, when there are multiple starting points and one end point, each node register records the number of each side between each starting point and the single end point, and traces the number of the side recorded by the node register, thereby obtaining each The path with the shortest signal transmission time between the point and the single end point;

When there is one starting point and there are multiple ending points, each node register records the number of each side from the single starting point to each end point, and traces the number of the edge recorded by the node register to obtain the signal between the single starting point and each end point. The shortest path for each transmission time.

Example 2

This embodiment is in the embodiment On the basis of 1, a method for further searching for a backup path in the quantized multi-thread network intelligent routing method is proposed. Based on the idea of the dual Dijkstra algorithm, in the undirected network, from the starting point to the network topology diagram Each point in the field obtains the shortest path and the corresponding quantity t1, and then obtains the shortest path and the corresponding quantity t2 from the end point to each point in the network, wherein the corresponding quantity refers to the point used from the start/end point to each point in the network topology map. Time, the sum of the two quantities t1 and t2 at each point, the minimum total point set and their topological connection, constitute the shortest path between the starting point and the end point, the point set of the next smallest total amount and the minimum total of them and the adjacent The topological connection of the points of the quantity constitutes the second short path between the start point and the end point.

Example 3

This embodiment further proposes a method of finding a backup path in a directed network based on the first embodiment. Directed network In the network, look for the backup path. After obtaining the shortest path from the starting point O to the ending point E, the amount of time taken from the starting point O to the ending point E on the shortest path is c; the amount of time taken from the starting point O to the other node D in the shortest path is d ; the backup node F adjacent to the other node D on the shortest path and not triggered, from the other node D to the backup node F The amount of time used is X, the backup node F is selected according to the range of X+d>c, and the state of each point on the shortest path is returned to the state before the trigger, and the pathfinding process is continued for the other points of X+d≤c ; nodes within the X+b>a selection range are released in X+b time The signal, thus obtaining the second short path, which is the shortest path of the first backup. Repeat the above steps to obtain multiple backup paths in the directed network.

The backup path can be applied to highly intelligent systems. Because in the ever-changing reality, changes in various external conditions may lead to differences in results, and the sampling of data is likely to be one-sided, so that the selected path is not the true optimal path in reality. Therefore, high-intelligence systems must also have the ability to select backup paths based on the results. After practice, the selected path is corrected according to the effect (self-learning ability), which is what we often call 'experience'.

This system can be used for power running networks (such as transportation networks, medical minimally invasive surgery routes), information transmission networks (such as the Internet, neural networks), pressure delivery networks (such as transmission, gas, liquid networks) and virtual networks (such as labor). Smart, etc.). They can be the intersection of the traffic network (road junction, port, station), the nodes of the information network (server, user, router), the control nodes of the pressure transmission network (distribution transformer, disconnect switch, throttle) as nodes; The lines connecting adjacent two nodes are arcs (edges), such as roads and routes of traffic networks, channels of information networks, pipes and waterways of pressure transmission networks; and the amount on the arc (edge) can be the mileage of the transportation network. Time-consuming, fuel consumption, road level, bandwidth, load, delay, interference of the information network, pressure, flow rate, length, and transmission power of the pressure transmission network. It enables a variety of network workloads to work in a balanced manner and find the optimal solution.

Claims (10)

A quantitative multi-thread network intelligent path selection method, comprising the following steps: a. According to the topology structure of the network, establish an electronic network topology structure diagram, number each side of the structure diagram and each node, and each node is connected with a node register; b. Definition The starting point and the end point of the path to be searched on the structure diagram, the signal is input from the starting point, and the signal is transmitted along the network topology. When the signal passing through one side or some sides first arrives and triggers a node, the node register of the node is recorded. The number of the side or the sides; c. The signal is then transmitted to the next node along the energy transmission direction according to the network topology until the end point obtains the signal; d. Trace the number of the edge recorded by the node register to obtain the path with the shortest signal transmission time between the two points. The quantized multi-thread network intelligent routing method according to claim 1, wherein the step In b, a pulse counting trigger for adjusting the signal transmission time of each side is connected to the end of each side, and the trigger output end of the pulse counting trigger is connected to the corresponding node register; When the signal reaches the end of the edge When the pulse counting trigger is triggered, the pulse counting trigger starts to calculate the number of pulses of the signal. When the number of pulses reaches the set number of triggers, the pulse counting trigger is triggered, and the signal is output to the next node, and the node register records the number of the corresponding side. . The quantized multi-thread network intelligent routing method according to claim 2, wherein: The transmission time of the edge signal is adjusted by adjusting the number of pulse triggers of the corresponding edge pulse count trigger or the frequency of the input signal. The quantized multi-thread network intelligent path selection method according to claim 3, wherein: By controlling the switching elements in series on the side, the on and off of the sides is controlled. The quantized multi-thread network intelligent routing method according to claim 1, wherein the step In b, a certain number of controllable electrical components having the same impedance value are connected to each side, and each controllable electrical component is connected to the power source through the switching component, and the unidirectional voltage triggering unit is connected at the end; The input signal is input from the starting point, and the signal passes through the controllable electrical component on the side, and reaches the unidirectional voltage triggering unit at the end of the edge. After the charge is accumulated, the threshold value is reached, and the unidirectional voltage triggering unit triggers; respectively, the signal is output to the node register recording side. Number, and continue to output signals to the connected side. The quantized multi-thread network intelligent routing method according to claim 1, wherein the step In b, a controllable electrical component with a variable impedance value is connected to each side, and a unidirectional voltage triggering unit is connected at the end, and the Setting the impedance of the controllable electrical component or the triggering threshold of the unidirectional voltage triggering unit to adjust the collecting time of the triggering threshold voltage to adjust the transmission time of the edge signal; by serially connecting the controllable switching component on the side, Control the on and off of the edge. The invention according to any one of claims 1 to 6 A quantized multi-thread network intelligent path selection method is characterized in that a current limiting element for limiting a signal transmission direction is connected in series on each side, so that the network forms a directed network. The quantized multi-thread network intelligent routing method according to claim 7, wherein the starting point has a plurality or a , the end point has one or more; When there are multiple starting points and one end point, each node register records the number of each side from each starting point to the single end point, and traces the number of the edge recorded by the node register to obtain the between each starting point and the single end point. The path with the shortest signal transmission time; When there is one starting point and there are multiple ending points, each node register records the number of each side from the single starting point to each end point, and traces the number of the edge recorded by the node register to obtain the signal between the single starting point and each end point. The shortest path for each transmission time. The quantized multi-thread network intelligent path selection method according to claim 7, wherein after obtaining the shortest path from the start point O to the end point E, setting the time amount from the start point O to the end point E on the shortest path is c The amount of time taken from the starting point O to the other node D on the shortest path is d; the backup section adjacent to other nodes D on the shortest path and not triggered Point F, from other node D to backup node F The amount of time used is X, the backup node F is selected according to the range of X+d>c, and the state of each point on the shortest path is returned to the state before the trigger, and the pathfinding process is continued for the other points of X+d≤c The node in the X+d>c selection range releases the signal by the amount of time of X+d, so that the second short path is obtained, which is the first backup path. Repeat the above steps to obtain more in the directed network. Strip backup path. The quantized multi-thread network intelligent path selection method according to claim 7, wherein: First, obtain the shortest path and the corresponding quantity t1 from the starting point to each point in the network topology diagram, and then obtain the shortest path and the corresponding quantity t2 from the end point to each point in the network, where the corresponding quantity refers to the starting point/end point to the network. The time used by each point in the topology diagram, the two quantities t1 and t2 of each point are added, the minimum total point set and their topological connections form the shortest path between the start point and the end point, and the point set of the next smallest total amount And their topological connection to the adjacent minimum total number of points constitutes the shortest path between the start and end points.

Images