CN114567914A - Information transmission path planning method and device of wireless sensor network - Google Patents

Abstract

The invention discloses an information transmission path planning method and device of a wireless sensor network, which comprises the following steps: constructing a grid map of a signal transmission path according to a starting point and an end point of signal transmission in the wireless sensor network; based on the distance and the turning point number of the information transmission path, carrying out path search on the raster map by using an ant algorithm based on a bidirectional search strategy to obtain an initial optimal information transmission path; and constraining the linear velocity and the angular velocity of the signal transmitted along the initial optimal information transmission path, and checking the turning point of the initial optimal information transmission path by using a dynamic window method to obtain a final information transmission path. By adopting the embodiment of the invention, the obstacle avoidance capability of the signal to the unknown obstacle in the transmission process can be improved.

Description

Information transmission path planning method and device for wireless sensor network

technical field

The present invention relates to the technical field of wireless sensor networks, and in particular, to a method and device for planning an information transmission path of a wireless sensor network.

Background technique

With the rapid development of intelligent cities, wireless sensor networks are more and more widely used in all aspects of people's lives. In the wireless sensor network, the network information transmission process is realized in the process of mutual transmission among sensors, routers, and hosts through radio waves with data information. However, the transmission process of radio waves is network information transmission. During the process, radio waves will be blocked by static obstacles such as cement and walls, and at the same time, they will also be interfered by radio interference generated by moving electronic equipment, that is, dynamic obstacles. Therefore, how to plan the information transmission path of wireless sensor network? , in order to reduce the interference in the process of network information transmission, it is very important to speed up the transmission of information.

At present, an information transmission path from the starting point to the end point is found from the wireless sensor network through the ant colony algorithm. However, this scheme still has the following shortcomings: the signal has a weak ability to avoid unknown obstacles during the transmission process.

SUMMARY OF THE INVENTION

The purpose of the embodiments of the present invention is to provide an information transmission path planning method and device for a wireless sensor network, so as to solve the problem in the prior art that the obstacle avoidance ability for unknown obstacles during signal transmission is weak. The ant algorithm and the dynamic window method plan the information transmission path in the wireless network, which can improve the obstacle avoidance ability of the signal to unknown obstacles during the transmission process.

To achieve the above purpose, an embodiment of the present invention provides an information transmission path planning method for a wireless sensor network, including:

Build a grid map of the signal transmission path according to the starting point and end point of the signal transmission in the wireless sensor network;

Based on the distance of the information transmission path and the number of turning points, the ant algorithm based on the bidirectional search strategy is used to perform a path search on the grid map, and the initial optimal information transmission path is obtained;

The linear velocity and angular velocity of signal transmission along the initial optimal information transmission path are constrained, and the turning point of the initial optimal information transmission path is checked by the dynamic window method to obtain the final information transmission path.

As an improvement of the above solution, the information transmission path planning method of the wireless sensor network further includes:

obtaining the first turning point of the final information transmission path;

determining the theoretical value of the initial transmission heading angle of the final information transmission path according to the starting point and the first turning point;

Obtain the actual value of the initial transmission heading angle of the final information transmission path;

Based on the comparison result between the actual value of the initial transmission heading angle and the theoretical value of the initial transmission heading angle, the final optimal information transmission path is obtained.

Wherein, the theoretical value of the initial transmission heading angle of the final information transmission path is determined according to the following formula:

d=((X ₁ -X _s ) ² +(Y ₁ -Y _s ) ² ) ^1/2

θ=arcsin(c)

Among them, θ is the theoretical value of the initial transmission heading angle of the final information transmission path, (X _s , Y _s ) are the coordinates of the starting point of signal transmission, and (X ₁ , Y ₁ ) are the coordinates of the first turning point of the final information transmission path.

As an improvement of the above scheme, based on the distance of the information transmission path and the number of turning points, the ant algorithm based on the bidirectional search strategy is used to perform a path search on the grid map to obtain the initial optimal information transmission path, including:

Determine the initial pheromone concentration released by the ants during the path search process on the grid map;

Two groups of ants determine the next node according to the preset heuristic function and the preset probability selection formula;

When two groups of ants meet, several initial information transmission paths are obtained;

updating the pheromone concentrations of several of the initial information transmission paths;

Based on the distances and the number of turning points of several of the initial information transmission paths, the initial optimal information transmission paths are screened out.

As an improvement of the above scheme, the two groups of ants determine the next node according to the preset heuristic function and the preset probability selection formula include:

Using the preset heuristic function, it is determined whether the degree of expectation between any two adjacent nodes is greater than a preset threshold, and if so, the next node is determined using the preset probability selection formula.

As an improvement of the above scheme, the determination of the initial pheromone concentration released by the ants during the path search process on the grid map includes:

According to the following formula, determine the initial pheromone concentration released by the ants during the path search process on the grid map:

Among them, k is the slope of the straight line connecting the starting point (x _s , y _s ) and the end point (x _e , y _e ) of the signal transmission in the wireless sensor network, and L is the distance between the starting point and the end point of the signal transmission in the wireless sensor network , d is the distance from node i to DC L, q is the original pheromone concentration when the original pheromone concentration is uniformly distributed, and q _i is the initial pheromone concentration of node i.

As an improvement of the above scheme, the preset heuristic function is:

Among them, A is the magnification, and d _ijE is the sum of the Euclidean distance from node i to the next node j and the Euclidean distance from the next node j to the end point E;

The preset probability selection formula is:

n_ij为启发函数，n_x为原栅格转移到下一栅格内所有节点的总期望程度，τ_ij(t+1)为t+1时刻的信息素浓度。in,

n _ij is the heuristic function, n _x is the total expected degree of transfer from the original grid to all nodes in the next grid, and τ _ij (t+1) is the pheromone concentration at time t+1.

As an improvement of the above scheme, the pheromone concentrations of several of the initial information transmission paths are updated according to the following formula:

为初始最优信息传输路径上的的信息素浓度增量；L_m为起点到终点的直线距离，L_max为初始最优信息传输路径。Among them, τ _ij (t+1) is the pheromone concentration at time t+1, ρ is the pheromone concentration volatilization coefficient, 0≤ρ≤1; τ _ij represents the pheromone concentration at time t, Δτ _ij is the pheromone concentration increase The initial time Δτ _ij =0; Q is the total amount of pheromone concentration,

is the pheromone concentration increment on the initial optimal information transmission path; L _m is the straight-line distance from the starting point to the end point, and L _max is the initial optimal information transmission path.

As an improvement of the above solution, the dynamic window method is used to check the turning point of the initial optimal information transmission path to obtain the final information transmission path, including:

Check the turning point of the initial optimal information transmission path according to the preset evaluation function:

分别为方向角评价函数、速度评价函数的加权系数。Among them, v and ω represent the linear velocity and angular velocity of signal transmission respectively, angle(v, ω) is the direction angle evaluation function; vel(v, ω) is the velocity evaluation function; σ is the smoothing coefficient, γ and

are the weighting coefficients of the direction angle evaluation function and the velocity evaluation function, respectively.

As an improvement of the above scheme, the direction angle evaluation function is:

The speed evaluation function is:

Among them, V _m+1 is the propagation speed when the signal reaches the m+1th turning point, and Vm is the propagation speed of the _mth turning point.

The embodiment of the present invention also provides an information transmission path planning device for a wireless sensor network, including:

The grid map building module is used to construct a grid map of the signal transmission path according to the starting point and end point of the signal transmission in the wireless sensor network;

The initial optimal information transmission path acquisition module is used to perform a path search on the grid map based on the distance of the information transmission path and the number of turning points, using the ant algorithm based on the bidirectional search strategy to obtain the initial optimal information transmission path;

The final information transmission path acquisition module is used to constrain the linear velocity and angular velocity of the signal transmission along the initial optimal information transmission path, and use the dynamic window method to check the turning point of the initial optimal information transmission path, and obtain The final information transmission path.

Compared with the prior art, an information transmission path planning method and device for a wireless sensor network provided by the embodiment of the present invention constructs a grid map of the signal transmission path according to the starting point and the end point of the signal transmission in the wireless sensor network. ; Based on the distance of the information transmission path and the number of turning points, the ant algorithm based on the bidirectional search strategy is used to perform a path search on the grid map to obtain the initial optimal information transmission path; the signal is transmitted along the initial optimal information transmission path. The linear velocity and angular velocity are constrained, and the turning point of the initial optimal information transmission path is checked by the dynamic window method, and the final information transmission path is obtained. It can be seen that the embodiments of the present invention plan the information transmission path in the wireless network by combining the ant algorithm and the dynamic window method, which can improve the obstacle avoidance ability of the signal to unknown obstacles during the transmission process.

Description of drawings

1 is a flowchart of a method for planning an information transmission path of a wireless sensor network according to an embodiment of the present invention;

FIG. 2 is a structural block diagram of an apparatus for planning an information transmission path of a wireless sensor network according to an embodiment of the present invention.

Detailed ways

The technical solutions in the embodiments of the present invention will be clearly and completely described below with reference to the accompanying drawings in the embodiments of the present invention. Obviously, the described embodiments are only a part of the embodiments of the present invention, but not all of the embodiments. Based on the embodiments of the present invention, all other embodiments obtained by those of ordinary skill in the art without creative efforts shall fall within the protection scope of the present invention.

Referring to FIG. 1, FIG. 1 is a flowchart of an information transmission path planning method for a wireless sensor network provided by an embodiment of the present invention. The information transmission path planning method for a wireless sensor network includes:

S1. Build a grid map of the signal transmission path according to the starting point and the end point of the signal transmission in the wireless sensor network;

S2. Based on the distance of the information transmission path and the number of turning points, use the ant algorithm based on the bidirectional search strategy to perform a path search on the grid map to obtain the initial optimal information transmission path;

S3. Constrain the linear velocity and angular velocity of the signal transmission along the initial optimal information transmission path, and use the dynamic window method to check the turning point of the initial optimal information transmission path to obtain the final information transmission path.

Specifically, in step S1, connect the starting point and the end point of the signal transmission in the wireless sensor network, calculate the straight line distance between the starting point and the ending point, and then make a parallel to each other at the starting point and the ending point, and the length is equal to the straight line distance between the starting point and the ending point. The parallel lines connect the four end points of the parallel lines to form a parallelogram. Divide the parallelogram into grids with equal areas, that is, generate a grid map of the signal transmission path.

Specifically, in step S2, based on the distance of the information transmission path and the number of turning points, the ant algorithm based on the bidirectional search strategy is used to perform a path search on the grid map to obtain the initial optimal information transmission path, including:

S21, determine the initial pheromone concentration released by the ants during the path search process on the grid map;

S22, the two groups of ants determine the next node according to the preset heuristic function and the preset probability selection formula;

S23, when the two groups of ants meet, obtain several initial information transmission paths;

S24, updating the pheromone concentrations of several of the initial information transmission paths;

S25. Based on the distances and the number of turning points of several initial information transmission paths, screen out the initial optimal information transmission paths.

更新不为0，即该路径的浓度增加比其他路径高)；In the embodiment of the present invention, according to the probability selection function composed of the heuristic function and the initial information concentration of each grid, several initial information transmission paths are obtained by bidirectional search; then, the information concentration is updated for these several initial information transmission paths ( When the information concentration of the initial optimal information transmission path is updated, its

The update is not 0, i.e. the concentration increase of this path is higher than other paths);

Based on the distances and the number of turning points of several initial information transmission paths, the initial optimal information transmission paths are screened out. If the obtained initial optimal information transmission paths are not ideal, the heuristic function and the updated information concentration are again formed into a probability selection formula, perform a two-way search again, and repeat the above steps until a consistent optimal solution appears, that is, the initial optimal information transmission path is obtained.

Specifically, in step S21, the determination of the initial pheromone concentration released by the ants during the path search process on the grid map includes:

According to the following formula, determine the initial pheromone concentration released by the ants during the path search process on the grid map:

Among them, k is the slope of the straight line connecting the starting point (x _s , y _s ) and the end point (x _e , y _e ) of the signal transmission in the wireless sensor network, and L is the distance between the starting point and the end point of the signal transmission in the wireless sensor network , d is the distance from node i to DC L, q is the original pheromone concentration when the original pheromone concentration is uniformly distributed, and q _i is the initial pheromone concentration of node i.

It needs to be said that in the currently commonly used traditional information transmission planning algorithm, the original pheromone concentration adopts the method of uniform distribution, which is simple and easy to implement, but the same information concentration of each grid will lead to blind search and poor convergence in the initial stage of the algorithm. Since the two-way search strategy can greatly improve the global search capability of the algorithm, speed up the early search efficiency, and increase the effective solution in the early stage, the embodiment of the present invention proposes, based on the two-way search strategy, to make the original information concentration different and the two-way distributed distribution, which provides a better solution for the two-way search. The general direction is to avoid problems such as blind search and poor convergence in the initial stage of the algorithm, and to meet the application scenarios of arbitrary starting and ending points.

Specifically, in step S22, the two groups of ants determine the next node according to a preset heuristic function and a preset probability selection formula, including:

Using the preset heuristic function, it is determined whether the degree of expectation between any two adjacent nodes is greater than a preset threshold, and if so, the next node is determined using the preset probability selection formula.

It can be understood that the embodiment of the present invention uses a heuristic function to determine the degree of expectation between any two adjacent nodes. If the degree of expectation between two nodes is too low, the path formed by the two adjacent nodes is discarded. Otherwise, use The preset probability selection formula determines the next node.

Specifically, the preset heuristic function is:

Among them, A is the magnification, and d _ijE is the sum of the Euclidean distance from node i to the next node j and the Euclidean distance from the next node j to the end point E;

Specifically, d _ijE = μd _ij +(1-μ)d _jE , where d _ij is the Euclidean distance from node i to the next node j, d _jE is the Euclidean distance from the next node j to the end point E, and μ is a constant .

It should be noted that the heuristic function of the traditional planning algorithm is inversely proportional to the distance between grid i and grid j, but the distance difference between adjacent grids is very small, which has little guiding effect on path search. At present, the effective improvement is to use the weighted sum inverse of the distance from the next selectable grid to the end point of the signal and the distance from the current grid to the next selectable grid as the heuristic function. Although this method considers the transfer of the current grid to the next grid The price paid for one grid, but the distance difference between adjacent grids is small, and the overall heuristic information is not affected much. Therefore, the embodiment of the present invention introduces an amplification factor A to increase the heuristic information difference between adjacent grids, thereby increasing the probability of selecting a shorter node.

Specifically, the preset probability selection formula is:

n_ij为启发函数，n_x为原栅格转移到下一栅格内所有节点的总期望程度，τ_ij(t+1)为t+1时刻的信息素浓度。in,

n _ij is the heuristic function, n _x is the total expected degree of transfer from the original grid to all nodes in the next grid, and τ _ij (t+1) is the pheromone concentration at time t+1.

It should be noted that when transferring from one grid to the next grid, the number of nodes that may be transferred in the next grid is n;

Knowing from the heuristic function, the expected degree of transfer between two nodes is:

d _ijE = μd _ij +(1-μ)d _jE

Thus, the total expected degree of all nodes transferred from the original grid to the next grid can be obtained as:

Then, the probability that a node in the next grid is selected is:

In the formula, n _ij is the heuristic function, indicating the expected degree of signal transfer from node i to node j; d _ij is the Euclidean distance from node i to the next node j; d _jE is the Euclidean distance from the next node j to the end point E , A is the magnification, and μ is a constant.

Update the information density of all paths that may reach the end point, assuming that the information density of a node in the next grid is τ _ij (t+1);

Then, the probability of this node being transferred by the previous node is:

Among them, α is the probability that the node is selected by the heuristic function.

It can be understood that the greater the transition probability, the greater the probability of being selected for transition, which facilitates the selection of a more suitable and appropriate transition node.

Specifically, in step S23, when the two groups of ants meet, several initial information transmission paths are obtained.

Specifically, in step S24, the pheromone concentrations of several of the initial information transmission paths are updated according to the following formula:

为初始最优信息传输路径上的的信息素浓度增量；L_m为起点到终点的直线距离，L_max为初始最优信息传输路径。Among them, τ _ij (t+1) is the pheromone concentration at time t+1, ρ is the pheromone concentration volatilization coefficient, 0≤ρ≤1; τ _ij represents the pheromone concentration at time t, Δτ _ij is the pheromone concentration increase The initial time Δτ _ij =0; Q is the total amount of pheromone concentration,

is the pheromone concentration increment on the initial optimal information transmission path; L _m is the straight-line distance from the starting point to the end point, and L _max is the initial optimal information transmission path.

Specifically, ρ is the pheromone concentration volatilization coefficient, 0≤ρ≤1, and its value depends on the distance between two nodes. If the transmission distance between two points is long, the volatilization coefficient can be appropriately larger; Q is The total amount of pheromone concentration depends on the total area of the grid map. The larger the total area, the larger the Q value can be.

It should be noted that the traditional path planning algorithm adopts the global information concentration update method, and only the information concentration on the shortest path is updated. Although the optimal solution information can be used well, it will lead to premature concentration on the same path and reduce the algorithm. The global search ability is easy to fall into the local optimal solution. In addition, when updating the information density on the shortest path, it may not be considered that there may not be only one shortest path, so most of the information density on one of the shortest paths is updated, so that the optimal solution will be lost. Therefore, in the embodiment of the present invention, the information density of all paths reaching the end point is updated, and the shortest path is found among them, and then the influence factor of the number of turns is introduced when selecting the optimal path (the increase of the number of turns will greatly affect the propagation of the signal. Turning too frequently will also aggravate the attenuation of the signal and affect the propagation efficiency), select the shortest path with the least number of turns as the optimal path to update the information concentration, so as to obtain a path with higher smoothness and more in line with signal propagation. For example, when the optimal path 1 and the sub-optimal path 2 are obtained from the update, the propagation distance and the number of turns of the two need to be compared; if the propagation distance of path 1 is similar to that of path 2, but the number of turns is much larger than that of path 2, this When the path 1 should be discarded, the path 2 should be chosen as the best path instead.

In the embodiment of the present invention, since the information concentration is distributed in the route grid, the information concentration τ _ij (0) of the starting point needs to be obtained by bidirectional searching in the grid map.

Specifically, in step S25, based on the distances and the number of turning points of several initial information transmission paths, the initial optimal information transmission paths are screened out.

Specifically, in step S3, according to the characteristics of the signal itself and the factors of the surrounding environment, the linear velocity and the angular velocity of the signal transmission along the initial optimal information transmission path are constrained:

(1) Speed constraint

Suppose the initial propagation velocity of the signal is V _s , then V _s ={(v,ω)|v∈[v _max ,v _min ],ω∈[ω _max ,ω _min ]},

In the formula, v and ω represent the linear velocity and angular velocity of signal transmission, respectively; v _min , v _max and ω _min , ω _max represent the maximum and minimum values of the median linear velocity and angular velocity of signal transmission, respectively.

Due to the attenuation of the signal during the propagation process, v _max and ω _max are usually selected as the transmission linear and angular velocities of the previous node, and v _min and ω _min are half of the transmission linear and angular velocities of the previous node.

(2) Acceleration constraint

Although the signal is attenuated during transmission, it cannot be attenuated excessively, which will affect the quality of signal transmission and reception, or even not receive the signal at all; therefore, the following restrictions are imposed on the acceleration attenuation of linear and angular velocities between two nodes:

V _d ={(v,ω)|v∈[v _n ,v-at],ω∈[ω _n ,ω _n -bt]}

In the formula, v _n and ω _n represent the linear velocity and angular velocity of the signal at the turning point n, respectively; a and b represent the maximum attenuation acceleration of the signal transmission linear velocity and angular velocity, respectively. In general, the maximum attenuation acceleration is the signal propagation of the previous node. The decay acceleration when the velocity decays to two-thirds of the original speed.

Specifically, in step S3, the dynamic window method is used to check the turning point of the initial optimal information transmission path to obtain the final information transmission path, including:

Check the turning point of the initial optimal information transmission path according to the preset evaluation function:

分别为方向角评价函数、速度评价函数的加权系数。Among them, v and ω represent the linear velocity and angular velocity of signal transmission respectively, angle(v, ω) is the direction angle evaluation function; vel(v, ω) is the velocity evaluation function; σ is the smoothing coefficient, γ and

are the weighting coefficients of the direction angle evaluation function and the velocity evaluation function, respectively.

It can be understood that the function evaluation criterion is that the selected turning point can help the signal to avoid obstacles as much as possible during the transmission process and move towards the target quickly. In the embodiment of the present invention, if the score of a certain turning point is too low calculated by the evaluation function, the turning point can be deleted, and the previous turning point and the next turning point are used as the starting point and the end point, and the approximate middle of the turning point can be obtained by solving the above-mentioned embodiment. turning point.

Specifically, the direction angle evaluation function is:

The speed evaluation function is:

Among them, V _m+1 is the propagation speed when the signal reaches the m+1th turning point, and Vm is the propagation speed of the _mth turning point.

In the embodiment of the present invention, since the transmission speed attenuation cannot be too fast during the signal transmission process, and the turning angle of each turning node cannot be too high, the directional angle evaluation function and the speed evaluation function are as follows:

的取值取决于起点与终点连线的角度的偏差、距离的长短，正常两者的取值为1，但倘若偏差角度大，则γ可适当取小，若直线距离短，则

可适当取值偏大。In the formula, V _m+1 is the propagation speed of the signal when it reaches the m+1th turning point, and Vm is the propagation speed of the _mth turning point; γ and

The value of γ depends on the deviation of the angle between the starting point and the end point, and the length of the distance. Normally, the value of the two is 1, but if the deviation angle is large, γ can be appropriately small. If the straight line distance is short, then

It can be appropriately set to a larger value.

In the embodiment of the present invention, the selection of the turning point should fully consider the limitations of the characteristics of the signal itself and the constraints of the environment on the signal propagation speed. Therefore, the speed pair (linear speed and angular speed) in the two-dimensional space of the signal propagation speed is selected, and a certain and design a reasonable evaluation function to perform certain optimization screening on the selected nodes in the initial optimal transmission path, and finally complete the overall path optimization. It can be seen that by designing a reasonable and practical evaluation function, not only a reasonable evaluation of the propagation speed, but also a reasonable inspection of the turning angle is carried out, so that the designed route not only has the shortest distance, but also greatly reduces the turning angle and the number of times, and is subject to dynamic and static obstacles. The level of physical interference is low, and the signal transmission efficiency is high.

In yet another preferred embodiment, the information transmission path planning method for the wireless sensor network further includes:

obtaining the first turning point of the final information transmission path;

determining the theoretical value of the initial transmission heading angle of the final information transmission path according to the starting point and the first turning point;

Obtain the actual value of the initial transmission heading angle of the final information transmission path;

Based on the comparison result between the actual value of the initial transmission heading angle and the theoretical value of the initial transmission heading angle, the final optimal information transmission path is obtained.

Specifically, determining the theoretical value of the initial transmission heading angle of the final information transmission path according to the starting point and the first turning point includes:

According to the following formula, determine the theoretical value of the initial transmission heading angle of the final information transmission path:

d=((X ₁ -X _s ) ² +(Y ₁ -Y _s ) ² ) ^1/2

θ=arcsin(c)

Among them, θ is the theoretical value of the initial transmission heading angle of the final information transmission path, (X _s , Y _s ) are the coordinates of the starting point of signal transmission, and (X ₁ , Y ₁ ) are the coordinates of the first turning point of the final information transmission path.

It should be noted that in most planning algorithms, the initial transmission heading angle of the signal is a fixed angle set randomly, but when the angle deviation from the target point is large, the initial search route will detour, and the signal transmission path will be increased. Therefore, the embodiment of the present invention proposes to obtain the theoretical value of the initially transmitted heading angle based on the angle between the connection line between the starting point and the first turning point and the horizontal direction. When the deviation of the value is not greater than the preset deviation, it is determined that the final information transmission path is the final optimal information transmission path, otherwise, the iteration is continued until the deviation between the theoretical value of the initial transmission heading angle and the actual value of the initial transmission heading angle is not greater than the preset deviation, The final optimal information transmission path is obtained to avoid the circumstance of detour.

An information transmission path planning method for a wireless sensor network provided by an embodiment of the present invention constructs a grid map of the signal transmission path according to the starting point and end point of signal transmission in the wireless sensor network; The number of turning points, the ant algorithm based on the bidirectional search strategy is used to search the grid map, and the initial optimal information transmission path is obtained; the linear velocity and angular velocity of the signal transmission along the initial optimal information transmission path are constrained, And use the dynamic window method to test the turning point of the initial optimal information transmission path to obtain the final information transmission path. It can be seen that the embodiments of the present invention plan the information transmission path in the wireless network by combining the ant algorithm and the dynamic window method, which can improve the obstacle avoidance ability of the signal to unknown obstacles during the transmission process.

Referring to FIG. 2, FIG. 2 is a structural block diagram of an information transmission path planning apparatus 10 for a wireless sensor network provided by an embodiment of the present invention. The information transmission path planning apparatus 10 for a wireless sensor network includes:

The grid map construction module 11 is used for constructing a grid map of the signal transmission path according to the starting point and the end point of the signal transmission in the wireless sensor network;

The initial optimal information transmission path acquisition module 12 is used to perform a path search on the grid map based on the distance of the information transmission path and the number of turning points, using the ant algorithm based on the bidirectional search strategy to obtain the initial optimal information transmission path;

The final information transmission path acquisition module 13 is used to constrain the linear velocity and angular velocity of the signal transmission along the initial optimal information transmission path, and use the dynamic window method to check the turning point of the initial optimal information transmission path, Get the final information transmission path.

Preferably, the information transmission path planning device of the wireless sensor network further comprises:

The first turning point obtaining module is used to obtain the first turning point of the final information transmission path;

an initial transmission heading angle theoretical value calculation module, configured to determine the initial transmission heading angle theoretical value of the final information transmission path according to the starting point and the first turning point;

a module for obtaining the actual value of the initial transmission heading angle, which is used to obtain the actual value of the initial transmission heading angle of the final information transmission path;

The final optimal information transmission path acquisition module is configured to obtain the final optimal information transmission path based on the comparison result between the actual value of the initial transmission heading angle and the theoretical value of the initial transmission heading angle.

Preferably, determining the theoretical value of the initial transmission heading angle of the final information transmission path according to the starting point and the first turning point, including:

According to the following formula, determine the theoretical value of the initial transmission heading angle of the final information transmission path:

d=((X ₁ -X _s ) ² +(Y ₁ -Y _s ) ² ) ^1/2

θ=arcsin(c)

Among them, θ is the theoretical value of the initial transmission heading angle of the final information transmission path, (X _s , Y _s ) are the coordinates of the starting point of signal transmission, and (X ₁ , Y ₁ ) are the coordinates of the first turning point of the final information transmission path.

Preferably, based on the distance of the information transmission path and the number of turning points, the ant algorithm based on the bidirectional search strategy is used to perform a path search on the grid map to obtain the initial optimal information transmission path, including:

Determine the initial pheromone concentration released by the ants during the path search process on the grid map;

Two groups of ants determine the next node according to the preset heuristic function and the preset probability selection formula;

When two groups of ants meet, several initial information transmission paths are obtained;

updating the pheromone concentrations of several of the initial information transmission paths;

Based on the distances and the number of turning points of several of the initial information transmission paths, the initial optimal information transmission paths are screened out.

Preferably, the determination of the next node by the two groups of ants according to a preset heuristic function and a preset probability selection formula includes:

Using the preset heuristic function, it is determined whether the degree of expectation between any two adjacent nodes is greater than a preset threshold, and if so, the next node is determined using the preset probability selection formula.

Preferably, the determining the initial pheromone concentration released by the ants during the path search process on the grid map includes:

According to the following formula, determine the initial pheromone concentration released by the ants during the path search process on the grid map:

Among them, k is the slope of the straight line connecting the starting point (x _s , y _s ) and the end point (x _e , y _e ) of the signal transmission in the wireless sensor network, and L is the distance between the starting point and the end point of the signal transmission in the wireless sensor network , d is the distance from node i to DC L, q is the original pheromone concentration when the original pheromone concentration is uniformly distributed, and q _i is the initial pheromone concentration of node i.

Preferably, the preset heuristic function is:

Among them, A is the magnification, and d _ijE is the sum of the Euclidean distance from node i to the next node j and the Euclidean distance from the next node j to the end point E;

The preset probability selection formula is:

n_ij为启发函数，n_x为原栅格转移到下一栅格内所有节点的总期望程度，τ_ij(t+1)为t+1时刻的信息素浓度。in,

n _ij is the heuristic function, n _x is the total expected degree of transfer from the original grid to all nodes in the next grid, and τ _ij (t+1) is the pheromone concentration at time t+1.

Preferably, the pheromone concentrations of several of the initial information transmission paths are updated according to the following formula:

为初始最优信息传输路径上的的信息素浓度增量；L_m为起点到终点的直线距离，L_max为初始最优信息传输路径。Among them, τ _ij (t+1) is the pheromone concentration at time t+1, ρ is the pheromone concentration volatilization coefficient, 0≤ρ≤1; τ _ij represents the pheromone concentration at time t, Δτ _ij is the pheromone concentration increase The initial time Δτ _ij =0; Q is the total amount of pheromone concentration,

is the pheromone concentration increment on the initial optimal information transmission path; L _m is the straight-line distance from the starting point to the end point, and L _max is the initial optimal information transmission path.

Preferably, the dynamic window method is used to check the turning point of the initial optimal information transmission path to obtain the final information transmission path, including:

Check the turning point of the initial optimal information transmission path according to the preset evaluation function:

分别为方向角评价函数、速度评价函数的加权系数。Among them, v and ω represent the linear velocity and angular velocity of signal transmission respectively, angle(v, ω) is the direction angle evaluation function; vel(v, ω) is the velocity evaluation function; σ is the smoothing coefficient, γ and

are the weighting coefficients of the direction angle evaluation function and the velocity evaluation function, respectively.

Preferably, the direction angle evaluation function is:

The speed evaluation function is:

Among them, V _m+1 is the propagation speed when the signal reaches the m+1th turning point, and Vm is the propagation speed of the _mth turning point.

It should be noted that, for the working process of each module in the information transmission path planning apparatus 10 of the wireless sensor network according to the embodiment of the present invention, reference may be made to the working process of the information transmission path planning method for the wireless sensor network described in the above embodiment. , and will not be repeated here.

An information transmission path planning device 10 for a wireless sensor network provided by the embodiment of the present invention constructs a grid map of the signal transmission path according to the starting point and the end point of the signal transmission in the wireless sensor network; based on the distance of the information transmission path and the number of turning points, use the ant algorithm based on the bidirectional search strategy to search the grid map to obtain the initial optimal information transmission path; constrain the linear velocity and angular velocity of the signal transmission along the initial optimal information transmission path , and use the dynamic window method to check the turning point of the initial optimal information transmission path to obtain the final information transmission path. It can be seen that the embodiments of the present invention plan the information transmission path in the wireless network by combining the ant algorithm and the dynamic window method, which can improve the obstacle avoidance ability of the signal to unknown obstacles during the transmission process.

The above are the preferred embodiments of the present invention. It should be pointed out that for those skilled in the art, without departing from the principles of the present invention, several improvements and modifications can be made, and these improvements and modifications may also be regarded as It is the protection scope of the present invention.

Claims (10)

1. an information transmission path planning method for a wireless sensor network, characterized in that, comprising: Build a grid map of the signal transmission path according to the starting point and end point of the signal transmission in the wireless sensor network; Based on the distance of the information transmission path and the number of turning points, the ant algorithm based on the bidirectional search strategy is used to perform a path search on the grid map, and the initial optimal information transmission path is obtained; The linear velocity and angular velocity of signal transmission along the initial optimal information transmission path are constrained, and the turning point of the initial optimal information transmission path is checked by the dynamic window method to obtain the final information transmission path. 2. The information transmission path planning method of the wireless sensor network according to claim 1, wherein the information transmission path planning method of the wireless sensor network further comprises: obtaining the first turning point of the final information transmission path; determining the theoretical value of the initial transmission heading angle of the final information transmission path according to the starting point and the first turning point; Obtain the actual value of the initial transmission heading angle of the final information transmission path; Based on the comparison result between the actual value of the initial transmission heading angle and the theoretical value of the initial transmission heading angle, the final optimal information transmission path is obtained; Wherein, the theoretical value of the initial transmission heading angle of the final information transmission path is determined according to the following formula: d=((X ₁ -X _s ) ² +(Y ₁ -Y _s ) ² ) ^1/2

θ=arcsin(c) Among them, θ is the theoretical value of the initial transmission heading angle of the final information transmission path, (X _s , Y _s ) is the coordinate of the starting point of the signal transmission, and (X ₁ , Y ₁ ) is the coordinate of the first turning point of the final information transmission path. 3. the information transmission path planning method of wireless sensor network as claimed in claim 1 is characterized in that, described based on the distance of information transmission path and the number of turning points, utilize the ant algorithm based on two-way search strategy to described grid map. Perform path search to obtain the initial optimal information transmission path, including: Determine the initial pheromone concentration released by the ants during the path search process on the grid map; Two groups of ants determine the next node according to the preset heuristic function and the preset probability selection formula; When two groups of ants meet, several initial information transmission paths are obtained; updating the pheromone concentrations of several of the initial information transmission paths; Based on the distances and the number of turning points of several of the initial information transmission paths, the initial optimal information transmission paths are screened out. 4. The information transmission path planning method of the wireless sensor network according to claim 3, wherein the two groups of ants determine the next node according to a preset heuristic function and a preset probability selection formula, comprising: Using the preset heuristic function, it is determined whether the degree of expectation between any two adjacent nodes is greater than a preset threshold, and if so, the next node is determined using the preset probability selection formula. 5. The information transmission path planning method of the wireless sensor network according to claim 3, wherein the determining the initial pheromone concentration released by the ants during the path search process on the grid map comprises: According to the following formula, determine the initial pheromone concentration released by the ants during the path search process on the grid map:

Among them, k is the slope of the straight line connecting the starting point (x _s , y _s ) and the end point (x _e , y _e ) of the signal transmission in the wireless sensor network, and L is the distance between the starting point and the end point of the signal transmission in the wireless sensor network , d is the distance from node i to the straight line L, q is the original pheromone concentration when the original pheromone concentration is uniformly distributed, and q _i is the initial pheromone concentration of node i. 6. The information transmission path planning method of the wireless sensor network as claimed in claim 3, wherein the preset heuristic function is:

Wherein, A is the magnification, and d _ijE is the sum of the Euclidean distance from node i to the next node j and the Euclidean distance from the next node j to the end point E; The preset probability selection formula is:

in,

n _ij is the heuristic function, n _x is the total expected degree of transfer from the original grid to all nodes in the next grid, and τ _ij (t+1) is the pheromone concentration at time t+1. 7. The method for planning an information transmission path of a wireless sensor network according to claim 3, wherein the pheromone concentrations of several of the initial information transmission paths are updated according to the following formula:

Among them, τ _ij (t+1) is the pheromone concentration at time t+1, ρ is the pheromone concentration volatilization coefficient, 0≤ρ≤1; τ _ij represents the pheromone concentration at time t, Δτ _ij is the pheromone concentration increase The initial time Δτ _ij =0; Q is the total amount of pheromone concentration,

is the pheromone concentration increment on the initial optimal information transmission path; L _m is the straight-line distance from the starting point to the end point, and L _max is the initial optimal information transmission path. 8. The information transmission path planning method of the wireless sensor network according to claim 1, wherein the dynamic window method is used to check the turning point of the initial optimal information transmission path to obtain the final information transmission path, include: Check the turning point of the initial optimal information transmission path according to the preset evaluation function:

Among them, v and ω represent the linear velocity and angular velocity of signal transmission, respectively, angle(v, ω) is the direction angle evaluation function; vel(v, ω) is the velocity evaluation function; σ is the smoothing coefficient, γ and

are the weighting coefficients of the direction angle evaluation function and the velocity evaluation function, respectively. 9. The information transmission path planning method of the wireless sensor network according to claim 8, wherein the direction angle evaluation function is:

The speed evaluation function is:

Among them, V _m+1 is the propagation speed of the signal when it reaches the m+1th turning point, and V _m is the propagation speed of the mth turning point. 10. An information transmission path planning device for a wireless sensor network, comprising: The grid map building module is used to construct a grid map of the signal transmission path according to the starting point and end point of the signal transmission in the wireless sensor network; The initial optimal information transmission path acquisition module is used to perform a path search on the grid map based on the distance of the information transmission path and the number of turning points, using the ant algorithm based on the bidirectional search strategy to obtain the initial optimal information transmission path; The final information transmission path acquisition module is used to constrain the linear velocity and angular velocity of the signal transmission along the initial optimal information transmission path, and use the dynamic window method to check the turning point of the initial optimal information transmission path, and obtain The final information transmission path.

Images