CN114567914A - Information transmission path planning method and device of wireless sensor network - Google Patents
Information transmission path planning method and device of wireless sensor network Download PDFInfo
- Publication number
- CN114567914A CN114567914A CN202210175770.4A CN202210175770A CN114567914A CN 114567914 A CN114567914 A CN 114567914A CN 202210175770 A CN202210175770 A CN 202210175770A CN 114567914 A CN114567914 A CN 114567914A
- Authority
- CN
- China
- Prior art keywords
- information transmission
- transmission path
- initial
- wireless sensor
- sensor network
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Pending
Links
- 230000005540 biological transmission Effects 0.000 title claims abstract description 243
- 238000000034 method Methods 0.000 title claims abstract description 57
- 230000008054 signal transmission Effects 0.000 claims abstract description 44
- 230000002457 bidirectional effect Effects 0.000 claims abstract description 20
- 239000003016 pheromone Substances 0.000 claims description 67
- 238000011156 evaluation Methods 0.000 claims description 34
- 241000257303 Hymenoptera Species 0.000 claims description 25
- 230000008569 process Effects 0.000 claims description 14
- 238000012216 screening Methods 0.000 claims description 6
- 238000012546 transfer Methods 0.000 claims description 5
- 238000009499 grossing Methods 0.000 claims description 4
- 230000006872 improvement Effects 0.000 description 9
- 230000001133 acceleration Effects 0.000 description 5
- 230000007704 transition Effects 0.000 description 4
- 230000002238 attenuated effect Effects 0.000 description 3
- 238000010586 diagram Methods 0.000 description 2
- 238000005457 optimization Methods 0.000 description 2
- 230000003068 static effect Effects 0.000 description 2
- 230000003321 amplification Effects 0.000 description 1
- 230000004888 barrier function Effects 0.000 description 1
- 239000004568 cement Substances 0.000 description 1
- 230000007547 defect Effects 0.000 description 1
- 238000013461 design Methods 0.000 description 1
- 238000011161 development Methods 0.000 description 1
- 238000009826 distribution Methods 0.000 description 1
- 238000012986 modification Methods 0.000 description 1
- 230000004048 modification Effects 0.000 description 1
- 238000003199 nucleic acid amplification method Methods 0.000 description 1
- 230000000644 propagated effect Effects 0.000 description 1
- 238000009827 uniform distribution Methods 0.000 description 1
Images
Classifications
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04W—WIRELESS COMMUNICATION NETWORKS
- H04W40/00—Communication routing or communication path finding
- H04W40/02—Communication route or path selection, e.g. power-based or shortest path routing
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04W—WIRELESS COMMUNICATION NETWORKS
- H04W40/00—Communication routing or communication path finding
- H04W40/24—Connectivity information management, e.g. connectivity discovery or connectivity update
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04W—WIRELESS COMMUNICATION NETWORKS
- H04W84/00—Network topologies
- H04W84/18—Self-organising networks, e.g. ad-hoc networks or sensor networks
-
- Y—GENERAL TAGGING OF NEW TECHNOLOGICAL DEVELOPMENTS; GENERAL TAGGING OF CROSS-SECTIONAL TECHNOLOGIES SPANNING OVER SEVERAL SECTIONS OF THE IPC; TECHNICAL SUBJECTS COVERED BY FORMER USPC CROSS-REFERENCE ART COLLECTIONS [XRACs] AND DIGESTS
- Y02—TECHNOLOGIES OR APPLICATIONS FOR MITIGATION OR ADAPTATION AGAINST CLIMATE CHANGE
- Y02D—CLIMATE CHANGE MITIGATION TECHNOLOGIES IN INFORMATION AND COMMUNICATION TECHNOLOGIES [ICT], I.E. INFORMATION AND COMMUNICATION TECHNOLOGIES AIMING AT THE REDUCTION OF THEIR OWN ENERGY USE
- Y02D30/00—Reducing energy consumption in communication networks
- Y02D30/70—Reducing energy consumption in communication networks in wireless communication networks
Landscapes
- Engineering & Computer Science (AREA)
- Computer Networks & Wireless Communication (AREA)
- Signal Processing (AREA)
- Mobile Radio Communication Systems (AREA)
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
Technical Field
The invention relates to the technical field of wireless sensor networks, in particular to an information transmission path planning method and device of a wireless sensor network.
Background
With the rapid advance and development of intelligent cities, wireless sensor networks are more and more widely applied to the aspects of people's life. In a wireless sensor network, a network information transmission process is realized in the mutual transmission process among a sensor, a router and a host through radio waves with data information, however, in the transmission process of the radio waves, namely the network information transmission process, the radio waves can be blocked by static obstacles such as cement, walls and the like, and can be interfered by radio interference generated by mobile electronic equipment, namely dynamic obstacles; therefore, how to plan the information transmission path of the wireless sensor network to reduce interference in the network information transmission process and speed up information transmission is very important.
At present, an information transmission path from a starting point to an end point is found from a wireless sensor network through an ant colony algorithm, however, the scheme still has the following defects: the obstacle avoidance capability of the signal to an unknown obstacle in the transmission process is weak.
Disclosure of Invention
The embodiment of the invention aims to provide an information transmission path planning method and an information transmission path planning device for a wireless sensor network, which aim to solve the problem that the obstacle avoidance capability of a signal on an unknown obstacle in the transmission process is weak in the prior art.
In order to achieve the above object, an embodiment of the present invention provides an information transmission path planning method for a wireless sensor network, including:
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.
As an improvement of the above scheme, the method for planning the information transmission path of the wireless sensor network further includes:
acquiring a first turning point of the final information transmission path;
determining an initial transmission course angle theoretical value of the final information transmission path according to the starting point and the first turning point;
acquiring an initial transmission course angle actual value of the final information transmission path;
and obtaining a final optimal information transmission path based on the comparison result of the initial transmission course angle actual value and the initial transmission course angle theoretical value.
Wherein the initial transmission course angle theoretical value of the final information transmission path is determined according to the following formula:
d＝((X1-Xs)2+(Y1-Ys)2)1/2
θ＝arcsin(c)
wherein, theta is the initial transmission course angle theoretical value of the final information transmission path, (X)s,Ys) As the coordinates of the start of signal transmission, (X)1,Y1) Is the first turning point coordinate of the final information transmission path.
As an improvement of the above scheme, the performing a path search on the grid map by using an ant algorithm based on a bidirectional search strategy based on the distance and the number of turning points of the information transmission path to obtain an initial optimal information transmission path includes:
determining the initial pheromone concentration released by ants in the process of searching the path of the grid map;
determining a next node by the two groups of ants according to a preset heuristic function and a preset probability selection formula;
when two groups of ants meet, a plurality of initial information transmission paths are obtained;
updating pheromone concentrations of a plurality of initial information transmission paths;
and screening out an initial optimal information transmission path based on the distances and the turning point numbers of the plurality of initial information transmission paths.
As an improvement of the above scheme, the determining, by the two groups of ants, a next node according to a preset heuristic function and a preset probability selection formula includes:
and judging whether the expected degree between any two adjacent nodes is greater than a preset threshold value or not by using the preset heuristic function, and if so, determining the next node by using the preset probability selection formula.
As an improvement of the above solution, the determining of the initial pheromone concentration released by the ants in the process of performing the route search on the grid map includes:
determining the initial pheromone concentration released by ants in the process of searching the path of the grid map according to the following formula:
wherein k is the starting point (x) of signal transmission in the wireless sensor networks,ys) And end point (x)e,ye) Is/are as followsThe slope of a straight line, L is the straight line between the starting point and the end point of signal transmission in the wireless sensor network, d is the distance from a node i to the direct current L, q is the original pheromone concentration when the original pheromone concentration is uniformly distributed, and q is the original pheromone concentrationiIs the initial pheromone concentration of node i.
As an improvement of the above scheme, the preset heuristic function is:
wherein A is the magnification factor, dijEThe sum of the Euclidean distance from the 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 as follows:
wherein,
nijfor heuristic functions, nxFor the total desired degree of transfer of the original grid to all nodes in the next grid, τij(t +1) is the pheromone concentration at time t + 1.
As an improvement of the above, pheromone concentrations of a plurality of the initial information transmission paths are updated according to the following formula:
wherein, tauij(t +1) is the pheromone concentration at the time of t +1, rho is the pheromone concentration volatilization coefficient, and rho is more than or equal to 0 and less than or equal to 1; tau isijIndicating the concentration of pheromone, Δ τ, at time tijFor pheromone concentration increase, the initial time delta tauij0; q is the total concentration of the pheromone,
the pheromone concentration increment on the initial optimal information transmission path; l is a radical of an alcoholmIs the straight-line distance from the starting point to the end point, LmaxIs the initial optimal information transmission path.
As an improvement of the above-mentioned scheme, the detecting the turning point of the initial optimal information transmission path by using a dynamic window method to obtain a final information transmission path includes:
and checking the turning point of the initial optimal information transmission path according to a preset evaluation function:
wherein v and ω respectively represent linear velocity and angular velocity of signal transmission, and angle (v, ω) is a direction angle evaluation function; vel (v, ω) is the velocity evaluation function; σ is the smoothing coefficient, γ and
the weighting coefficients are the direction angle evaluation function and the speed evaluation function.
As an improvement of the above solution, the direction angle evaluation function is:
the speed evaluation function is:
wherein, Vm+1Is the propagation velocity, V, of the signal at the m +1 th turning pointmThe propagation velocity at the mth turning point.
The embodiment of the invention also provides an information transmission path planning device of the wireless sensor network, which comprises the following components:
the grid map building module is used for building 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;
the initial optimal information transmission path acquisition module is used for carrying out path search on the raster map by using an ant algorithm based on a bidirectional search strategy based on the distance and the turning point number of the information transmission path to obtain an initial optimal information transmission path;
and the final information transmission path acquisition module is used for constraining the linear speed and the angular speed of the signal transmitted along the initial optimal information transmission path and detecting the turning point of the initial optimal information transmission path by using a dynamic window method to obtain a final information transmission path.
Compared with the prior art, the information transmission path planning method and the information transmission path planning device for the wireless sensor network provided by the embodiment of the invention construct the grid map of the signal transmission path according to the starting point and the 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. Therefore, the information transmission path in the wireless network is planned by combining the ant algorithm and the dynamic window method, and the obstacle avoidance capability of the signal on the unknown obstacle in the transmission process can be improved.
Drawings
Fig. 1 is a flowchart of an information transmission path planning method for a wireless sensor network according to an embodiment of the present invention;
fig. 2 is a block diagram of an information transmission path planning apparatus of a wireless sensor network according to an embodiment of the present invention.
Detailed Description
The technical solutions in the embodiments of the present invention will be clearly and completely described below with reference to the drawings in the embodiments of the present invention, and it is obvious that the described embodiments are only a part of the embodiments of the present invention, and not all of the embodiments. All other embodiments, which can be derived by a person skilled in the art from the embodiments given herein without making any creative effort, 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 according to an embodiment of the present invention, where the information transmission path planning method for the wireless sensor network includes:
s1, constructing a grid map of a signal transmission path according to the starting point and the end point of signal transmission in the wireless sensor network;
s2, 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 S3, 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.
Specifically, in step S1, connecting a start point and an end point of signal transmission in the wireless sensor network, calculating a linear distance between the start point and the end point, then making parallel lines parallel to each other at the start point and the end point, the length of the parallel lines being equal to the linear distance between the start point and the end point, and connecting four end points of the parallel lines parallel to each other to form a parallelogram; this parallelogram is divided into equal-area grids, i.e., grid maps of signal transmission paths are generated.
Specifically, in step S2, the performing a path search on the grid map by using an ant algorithm based on a bidirectional search strategy based on the distance and the number of turning points of the information transmission path to obtain an initial optimal information transmission path includes:
s21, determining the initial pheromone concentration released by ants in the process of searching the path of the grid map;
s22, determining a next node by the two groups of ants according to a preset heuristic function and a preset probability selection formula;
s23, when two groups of ants meet each other, a plurality of initial information transmission paths are obtained;
s24, updating pheromone concentrations of a plurality of initial information transmission paths;
and S25, screening out the initial optimal information transmission path based on the distance and the number of turning points of the plurality of initial information transmission paths.
In the embodiment of the invention, a plurality of initial information transmission paths are obtained by bidirectional searching according to probability selection functions consisting of heuristic functions and initial information concentrations of each grid; then, the information density is updated for each of the plurality of initial information transmission paths (when the information density of the initial optimum information transmission path is updated, it is updated
The update is not 0, i.e. the concentration increase of this path is higher than the other paths);
and screening out an initial optimal information transmission path from the initial optimal information transmission paths based on the distances and the turning point numbers of the plurality of initial information transmission paths, if the obtained initial optimal information transmission path is not ideal, enabling the heuristic function and the updated information concentration to form a probability selection formula again, performing two-way search again, and repeating the steps until a consistent optimal solution appears to obtain the initial optimal information transmission path.
Specifically, in step S21, the determining an initial pheromone concentration released by ants in the process of performing the route search on the grid map includes:
determining the initial pheromone concentration released by ants in the process of searching the path of the grid map according to the following formula:
wherein k is the starting point (x) of signal transmission in the wireless sensor networks,ys) And end point (x)e,ye) L is a straight line between a starting point and an end point of signal transmission in the wireless sensor network, d is the distance from a node i to the direct current L, q is the original pheromone concentration when the original pheromone concentration is uniformly distributed, q is the slope of the straight line in the wireless sensor network, L is the straight line between the starting point and the end point of the signal transmission in the wireless sensor network, d is the distance from the node i to the direct current L, q is the original pheromone concentration when the original pheromone concentration is uniformly distributed, and q is the slope of the straight line in the wireless sensor networkiIs the initial pheromone concentration of node i.
It should be noted that, in the conventional information transmission planning algorithm commonly used at present, the original pheromone concentration adopts a uniform distribution method, which is simple and easy to implement, but the same grid information concentration can cause the problems of blind search, poor convergence and the like at the initial stage of the algorithm. Because the bidirectional search strategy can greatly improve the global search capability of the algorithm, accelerate the early-stage search efficiency and increase the early-stage effective solution, the embodiment of the invention provides different original information concentrations and bidirectional distributed distribution based on the bidirectional search strategy, provides a general direction for bidirectional search, avoids the problems of blind search, poor convergence and the like at the early stage of the algorithm, and meets the application scenes of any starting point and destination point.
Specifically, in step S22, the determining, by the two groups of ants, a next node according to the preset heuristic function and the preset probability selection formula includes:
and judging whether the expected degree between any two adjacent nodes is greater than a preset threshold value or not by using the preset heuristic function, and if so, determining the next node by using the preset probability selection formula.
It can be understood that, in the embodiment of the present invention, the heuristic function is used to determine the expectation degree between any two adjacent nodes, if the expectation degree between two nodes is too low, the path formed by the two adjacent nodes is abandoned, otherwise, the preset probability selection formula is used to determine the next node.
Specifically, the preset heuristic function is:
wherein A is the magnification factor, dijEThe sum of the Euclidean distance from the node i to the next node j and the Euclidean distance from the next node j to the end point E;
in particular, dijE＝μdij+(1-μ)djEWherein d isijIs the Euclidean distance, d, from node i to the next node jjEμ is a constant, which is the euclidean distance from the next node j to the end point E.
It should be noted that the heuristic function of the conventional planning algorithm is inversely proportional to the distance between grid i and grid j, but the distance difference between adjacent grids is small, and the guiding function for path search is not large. At present, the effective improvement is to use the weighted sum reciprocal of the distance from the next selectable grid to the end point and the distance from the current grid to the next selectable grid as a heuristic function, and although the cost of transferring the current grid to the next grid is considered, the distance difference between adjacent grids is small, and the influence on the overall heuristic information is not large. Therefore, the embodiment of the invention introduces the amplification factor a to increase the difference of heuristic information of adjacent grids, thereby increasing the probability of selecting shorter nodes.
Specifically, the preset probability selection formula is as follows:
wherein,
nijas a heuristic function, nxFor the total desired degree of transfer of the original grid to all nodes in the next grid, τ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;
as known from the heuristic function, the expected degree of transition between two nodes is:
dijE＝μdij+(1-μ)djE
thus, the total expected degree of all nodes transferred from the original grid to the next grid can be:
then, the probability that a certain node in the next grid is selected can be obtained as follows:
in the formula, nijIs a heuristic function that represents the expected degree of signal transfer from node i to node j; d is a radical ofijThe Euclidean distance from the node i to the next node j; djEThe Euclidean distance from the next node j to the end point E, A is the magnification factor, and mu is a constant.
And updating the information concentration of all paths which can reach the end point, and assuming that the information concentration of a certain node in the next grid is tauij(t+1)；
Then, the probability that the node is transferred by the previous node is:
wherein, alpha is the probability of the node being selected by a heuristic function.
It can be understood that the greater the transition probability, the greater the probability of the selected transition, facilitating the selection of a more appropriate and appropriate transition node.
Specifically, in step S23, when two sets 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 equation:
wherein, tauij(t +1) is the pheromone concentration at the time of t +1, rho is the pheromone concentration volatilization coefficient, and rho is more than or equal to 0 and less than or equal to 1; tau.ijIndicating the concentration of pheromone, Δ τ, at time tijFor pheromone concentration increase, the initial time delta tauij0; q is the total concentration of the pheromone,
the pheromone concentration increment on the initial optimal information transmission path; l ismIs the linear distance from the starting point to the end point, LmaxIs the initial optimal information transmission path.
Specifically, rho is a pheromone concentration volatilization coefficient, rho is more than or equal to 0 and less than or equal to 1, the value of the rho depends on the distance between two nodes, and if the transmission distance between the two nodes is long, the volatilization coefficient can be properly larger; q is the total concentration of pheromones, the size of the total concentration of the pheromones depends on the total area of the grid map, and the larger the total area is, the larger the value of the Q value can be properly selected.
It should be noted that, the conventional path planning algorithm adopts a global information concentration updating mode, only the information concentration on the shortest path is updated, and although the optimal solution information can be well utilized, the information is prematurely concentrated on the same path, so that the global search capability of the algorithm is reduced, and the algorithm is easy to fall into a local optimal solution. In addition, when the information concentration on the shortest path is updated, it may be missed to consider that the shortest path may not be only one, so that the information concentration on one shortest path is mostly updated, so that the optimal solution is lost. Therefore, in the embodiment of the present invention, information concentration of all paths reaching the end point is updated, and the shortest path is found, then a turn number influence factor is introduced when selecting the optimal path (increase of the turn number greatly affects propagation efficiency when signals are propagated, too frequent turning also aggravates attenuation of the signals, affects propagation efficiency), and the shortest path with the least turn number is selected as the optimal path to update information concentration, so that a path with higher smoothness and better conformity to signal propagation is obtained. For example, when the optimal path one and the sub-optimal path two are obtained by updating, the propagation distance and the turning times of the two paths need to be compared; if the propagation distance of the first path is similar to that of the second path, but the number of turns is much greater than that of the second path, the first path should be discarded, and the second path is selected as the optimal path instead.
In the embodiment of the present invention, since the information concentration is distributed dispersedly in the course grid, the information concentration τ of the start pointij(0) The method needs to be obtained by bidirectional searching in a grid map.
Specifically, in step S25, an initial optimal information transmission path is screened out from a number of the initial information transmission paths based on their distances and the number of turning points.
Specifically, in step S3, the linear velocity and the angular velocity at which the signal is transmitted along the initial optimal information transmission path are constrained according to the characteristic limit of the signal itself and the factors of the surrounding environment:
(1) speed constraint
Let the initial propagation velocity of the signal be VsThen V iss＝{(v,ω)|v∈[vmax,vmin],ω∈[ωmax,ωmin]}，
In the formula, v and omega respectively represent linear velocity and angular velocity of signal transmission; v. ofmin、vmaxAnd ωmin、ωmaxRespectively representing the maximum and minimum values of the linear and angular velocities of the signal transmission.
V is usually chosen because of the attenuation of the signal during propagationmaxAnd ωmaxLinear and angular velocity, v, of the transmission line at the previous nodeminAnd ωminWhich is half the linear and angular velocity of the transmission at the previous node.
(2) Restraint of acceleration
Although the signal has attenuation property in the transmission process, the signal cannot be attenuated excessively, so that the quality of signal transmission and reception is affected, and even the signal cannot be received completely; therefore, the following restrictions are made on the acceleration attenuation of the linear velocity and the angular velocity between the two nodes:
Vd＝{(v,ω)|v∈[vn,v-at],ω∈[ωn,ωn-bt]}
in the formula, vnAnd ωnRespectively representing the linear velocity and the angular velocity of the signal at the turning point n; a and b respectively represent the maximum attenuation acceleration of the linear velocity and the angular velocity of signal transmission, and generally, the maximum attenuation acceleration is the attenuation acceleration when the signal propagation speed of the previous node is attenuated to two thirds of the original propagation speed.
Specifically, in step S3, the checking the turning point of the initial optimal information transmission path by using a dynamic window method to obtain a final information transmission path includes:
and checking the turning point of the initial optimal information transmission path according to a preset evaluation function:
wherein v and omega respectively represent linear velocity and angular velocity of signal transmission, and angle (v, omega) is a direction angle evaluation function; vel (v, ω) is the velocity evaluation function; σ is the smoothing coefficient, γ and
the weighting coefficients are the direction angle evaluation function and the speed evaluation function.
It is understood that the function evaluation criterion is that the turning point is selected to help the signal avoid the obstacle as much as possible during the transmission process and to advance toward the target quickly. In the embodiment of the invention, a turning point with too low score is calculated through an evaluation function, the turning point can be deleted, and the approximate middle turning point is obtained by solving through the above embodiment by taking the upper turning point and the lower turning point as the starting point and the end point.
Specifically, the direction angle evaluation function is:
the speed evaluation function is:
wherein, Vm+1Is the propagation velocity, V, of the signal at the m +1 th turning pointmThe propagation velocity at the mth turning point.
In the embodiment of the present invention, since the transmission speed cannot be attenuated too fast and the turning angle of each turning node cannot be too high in the transmission process of the signal, the direction angle evaluation function and the speed evaluation function are as follows:
in the formula, Vm+1Is the propagation velocity, V, of the signal at the m +1 th turning pointmThe propagation velocity of the mth turning point; γ and
the value of (a) is determined by the deviation of the angle of the connecting line of the starting point and the end point and the length of the distance, normally the values of the starting point and the end point are 1, but if the deviation angle is large, gamma can be properly small, and if the straight line distance is short, gamma can be properly small
Can be properly large.
In the embodiment of the invention, the selection of the turning point should fully consider the characteristic limit of the signal and the constraint of the environment on the signal propagation speed, so that the speed pairs (linear speed and angular speed) in the two-dimensional space of the signal propagation speed are selected and are subjected to certain constraint; and a reasonable evaluation function is designed, certain optimization screening is carried out on the selected nodes in the initial optimal transmission path, and finally the whole path optimization is completed. Therefore, through reasonable design and an actual evaluation function, the propagation speed is reasonably evaluated, and the turning angle is also reasonably checked, so that the designed route has the shortest distance, the turning angle and the turning times are greatly reduced, the interference degree by dynamic and static barriers is low, and the signal transmission efficiency is high.
In another preferred embodiment, the method for planning the information transmission path of the wireless sensor network further includes:
acquiring a first turning point of the final information transmission path;
determining an initial transmission course angle theoretical value of the final information transmission path according to the starting point and the first turning point;
acquiring an initial transmission course angle actual value of the final information transmission path;
and obtaining a final optimal information transmission path based on the comparison result of the initial transmission course angle actual value and the initial transmission course angle theoretical value.
Specifically, the determining the initial transmission heading angle theoretical value of the final information transmission path according to the starting point and the first turning point includes:
determining a starting transmission course angle theoretical value of the final information transmission path according to the following formula:
d＝((X1-Xs)2+(Y1-Ys)2)1/2
θ＝arcsin(c)
wherein, theta is the initial transmission course angle theoretical value of the final information transmission path, (X)s,Ys) As the coordinates of the start of signal transmission, (X)1,Y1) Is the first turning point coordinate of the final information transmission path.
It should be noted that, in most planning algorithms, the initial transmission course angle of a signal is a fixed angle set at random, but when the angle deviation from a target point is large, a phenomenon of route detour in the initial stage occurs, and the redundancy of a signal transmission path is increased; therefore, the embodiment of the invention provides that the initial transmission course angle theoretical value is obtained by the included angle between the connecting line of the starting point and the first turning point and the horizontal direction, when the deviation between the initial transmission course angle theoretical value and the initial transmission course angle actual value is not more than the preset deviation, the final information transmission path is judged to be the final optimal information transmission path, otherwise, the iteration is continued until the deviation between the initial transmission course angle theoretical value and the initial transmission course angle actual value is not more than the preset deviation, and the final optimal information transmission path is obtained, so as to avoid the circumambulation.
According to the information transmission path planning method of the wireless sensor network, provided by the embodiment of the invention, a grid map of a signal transmission path is constructed 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. Therefore, the information transmission path in the wireless network is planned by combining the ant algorithm and the dynamic window method, and the obstacle avoidance capability of the signal on the unknown obstacle in the transmission process can be improved.
Referring to fig. 2, fig. 2 is a block diagram of an information transmission path planning apparatus 10 of a wireless sensor network according to an embodiment of the present invention, where the information transmission path planning apparatus 10 of the wireless sensor network includes:
the grid map building module 11 is used for building 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;
an initial optimal information transmission path obtaining module 12, configured to perform path search on the grid map by using an ant algorithm based on a bidirectional search strategy based on a distance and a turning point number of an information transmission path, to obtain an initial optimal information transmission path;
and a final information transmission path obtaining module 13, configured to constrain a linear velocity and an angular velocity of a signal transmitted along the initial optimal information transmission path, and check a turning point of the initial optimal information transmission path by using a dynamic window method to obtain a final information transmission path.
Preferably, the information transmission path planning apparatus of the wireless sensor network further includes:
a first turning point acquisition module, configured to acquire a first turning point of the final information transmission path;
the starting transmission course angle theoretical value calculating module is used for determining the starting transmission course angle theoretical value of the final information transmission path according to the starting point and the first turning point;
an initial transmission course angle actual value acquisition module for acquiring an initial transmission course angle actual value of the final information transmission path;
and the final optimal information transmission path acquisition module is used for acquiring a final optimal information transmission path based on a comparison result of the initial transmission course angle actual value and the initial transmission course angle theoretical value.
Preferably, the determining the theoretical initial transmission heading angle value of the final information transmission path according to the starting point and the first turning point includes:
determining the theoretical value of the initial transmission course angle of the final information transmission path according to the following formula:
d＝((X1-Xs)2+(Y1-Ys)2)1/2
θ＝arcsin(c)
wherein, theta is the initial transmission course angle theoretical value of the final information transmission path, (X)s,Ys) As the coordinates of the start of signal transmission, (X)1,Y1) Is the first turning point coordinate of the final information transmission path.
Preferably, the performing a path search on the grid map by using an ant algorithm based on a bidirectional search strategy based on the distance and the number of turning points of the information transmission path to obtain an initial optimal information transmission path includes:
determining the initial pheromone concentration released by ants in the process of searching the path of the grid map;
determining a next node by the two groups of ants according to a preset heuristic function and a preset probability selection formula;
when two groups of ants meet, a plurality of initial information transmission paths are obtained;
updating pheromone concentrations of a plurality of initial information transmission paths;
and screening out an initial optimal information transmission path based on the distances and the turning point numbers of the plurality of initial information transmission paths.
Preferably, the determining, by the two groups of ants, a next node according to a preset heuristic function and a preset probability selection formula includes:
and judging whether the expected degree between any two adjacent nodes is greater than a preset threshold value or not by using the preset heuristic function, and if so, determining the next node by using the preset probability selection formula.
Preferably, the determining of the initial pheromone concentration released by the ants in the process of searching the path of the grid map includes:
determining the initial pheromone concentration released by ants in the process of searching the path of the grid map according to the following formula:
wherein k is the starting point (x) of signal transmission in the wireless sensor networks,ys) And end point (x)e,ye) L is a straight line between a start point and an end point of signal transmission in the wireless sensor network, d is a distance from a node i to the direct current L, q is an original pheromone concentration when the original pheromone concentration is uniformly distributed, q is a gradient of the straight lineiInitial pheromone concentration for node i。
Preferably, the preset heuristic function is:
wherein A is the magnification factor, dijEThe sum of the Euclidean distance from the 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 as follows:
wherein,
nijas a heuristic function, nxFor the total desired degree of transfer of the original grid to all nodes in the next grid, τij(t +1) is the pheromone concentration at time t + 1.
Preferably, the pheromone concentrations of several of said initial information transmission paths are updated according to the following formula:
wherein, tauij(t +1) is the pheromone concentration at the time of t +1, rho is the pheromone concentration volatilization coefficient, and rho is more than or equal to 0 and less than or equal to 1; tau.ijIndicating the concentration of pheromone, Δ τ, at time tijFor increasing pheromone concentration, the initial time delta tauij0; q is the total pheromone concentration，
The pheromone concentration increment on the initial optimal information transmission path; l is a radical of an alcoholmIs the straight-line distance from the starting point to the end point, LmaxIs the initial optimal information transmission path.
Preferably, the checking the turning point of the initial optimal information transmission path by using a dynamic window method to obtain a final information transmission path includes:
and checking the turning point of the initial optimal information transmission path according to a preset evaluation function:
wherein v and omega respectively represent linear velocity and angular velocity of signal transmission, and angle (v, omega) is a direction angle evaluation function; vel (v, ω) is the velocity evaluation function; σ is the smoothing coefficient, γ and
the weighting coefficients are the direction angle evaluation function and the speed evaluation function.
Preferably, the direction angle evaluation function is:
the speed evaluation function is:
wherein, Vm+1Is the propagation velocity, V, of the signal at the m +1 th turning pointmThe propagation velocity at 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 of the wireless sensor network according to the foregoing embodiment, and details are not repeated herein.
The information transmission path planning device 10 of the wireless sensor network provided by the embodiment of the invention constructs 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 of the information transmission path and the number of turning points, 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. Therefore, the embodiment of the invention plans the information transmission path in the wireless network by combining the ant algorithm and the dynamic window method, and can improve the obstacle avoidance capability of the signal on the unknown obstacle in the transmission process.
While the foregoing is directed to the preferred embodiment of the present invention, it will be understood by those skilled in the art that various changes and modifications may be made without departing from the spirit and scope of the invention.
Claims (10)
1. An information transmission path planning method for a wireless sensor network is characterized by comprising 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.
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 includes:
acquiring a first turning point of the final information transmission path;
determining an initial transmission course angle theoretical value of the final information transmission path according to the starting point and the first turning point;
acquiring an initial transmission course angle actual value of the final information transmission path;
obtaining a final optimal information transmission path based on a comparison result of the initial transmission course angle actual value and the initial transmission course angle theoretical value;
wherein the initial transmission course angle theoretical value of the final information transmission path is determined according to the following formula:
d＝((X1-Xs)2+(Y1-Ys)2)1/2
θ＝arcsin(c)
wherein, theta is the initial transmission course angle theoretical value of the final information transmission path, (X)s，Ys) As the coordinates of the start of signal transmission, (X)1，Y1) Is the first turning point coordinate of the final information transmission path.
3. The method for planning an information transmission path of a wireless sensor network according to claim 1, wherein the step of performing a path search on the grid map by using an ant algorithm based on a bidirectional search strategy based on the distance and the number of turning points of the information transmission path to obtain an initial optimal information transmission path comprises:
determining the initial pheromone concentration released by ants in the process of searching the path of the grid map;
determining a next node by the two groups of ants according to a preset heuristic function and a preset probability selection formula;
when two groups of ants meet, a plurality of initial information transmission paths are obtained;
updating pheromone concentrations of a plurality of initial information transmission paths;
and screening out an initial optimal information transmission path based on the distances and the turning point numbers of the plurality of initial information transmission paths.
4. The method for planning information transmission path of wireless sensor network according to claim 3, wherein the determining the next node by the two groups of ants according to the predetermined heuristic function and the predetermined probability selection formula comprises:
and judging whether the expected degree between any two adjacent nodes is greater than a preset threshold value or not by using the preset heuristic function, and if so, determining the next node by using the preset probability selection formula.
5. The method for planning the information transmission path of the wireless sensor network according to claim 3, wherein the determining of the initial pheromone concentration released by ants in the process of searching the path of the grid map comprises:
determining the initial pheromone concentration released by ants in the process of searching the path of the grid map according to the following formula:
wherein k is the starting point (x) of signal transmission in the wireless sensor networks,ys) And end point (x)e,ye) L is a straight line between the start point and the end point of signal transmission in the wireless sensor network, d is the distance from the node i to the straight line L, q is the original pheromone concentration when the original pheromone concentration is uniformly distributed, q is the slope of the straight lineiIs the initial pheromone concentration of node i.
6. The method for planning information transmission path of wireless sensor network according to claim 3, wherein the predetermined heuristic function is:
wherein A is the magnification, dijEThe sum of the Euclidean distance from the 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 as follows:
wherein,
nijfor heuristic functions, nxFor the total desired degree of transfer of the original grid to all nodes in the next grid, τij(t +1) is the pheromone concentration at time t + 1.
7. The method according to claim 3, wherein the pheromone concentrations of the plurality of initial information transmission paths are updated according to the following formula:
wherein, tauij(t +1) is the pheromone concentration at the time of t +1, rho is the pheromone concentration volatilization coefficient, and rho is more than or equal to 0 and less than or equal to 1; tau isijIndicating the concentration of pheromone, Δ τ, at time tijFor pheromone concentration increase, the initial time delta tauij0; q is the total concentration of the pheromone,
the pheromone concentration increment on the initial optimal information transmission path; l ismIs the linear distance from the starting point to the end point, LmaxIs the initial optimal information transmission path.
8. The method for planning information transmission path of wireless sensor network according to claim 1, wherein the step of checking the turning point of the initial optimal information transmission path by using a dynamic window method to obtain a final information transmission path comprises:
and checking the turning point of the initial optimal information transmission path according to a preset evaluation function:
wherein v and ω respectively represent linear speeds of signal transmissionAnd angular velocity, angle (v, ω) being an evaluation function of the azimuth; vel (v, ω) is the velocity evaluation function; σ is the smoothing coefficient, γ and
the weighting coefficients are the direction angle evaluation function and the speed evaluation function.
9. The method for planning information transmission path of wireless sensor network according to claim 8, wherein the direction angle evaluation function is:
the speed evaluation function is:
wherein, Vm+1Is the propagation velocity, V, of the signal at the m +1 th turning pointmThe propagation velocity at the mth turning point.
10. An information transmission path planning device of a wireless sensor network is characterized by comprising:
the grid map building module is used for building 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;
the initial optimal information transmission path acquisition module is used for carrying out path search on the raster map by using an ant algorithm based on a bidirectional search strategy based on the distance and the turning point number of the information transmission path to obtain an initial optimal information transmission path;
and the final information transmission path acquisition module is used for constraining the linear speed and the angular speed of the signal transmitted along the initial optimal information transmission path and detecting the turning point of the initial optimal information transmission path by using a dynamic window method to obtain a final information transmission path.
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN202210175770.4A CN114567914A (en) | 2022-02-24 | 2022-02-24 | Information transmission path planning method and device of wireless sensor network |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN202210175770.4A CN114567914A (en) | 2022-02-24 | 2022-02-24 | Information transmission path planning method and device of wireless sensor network |
Publications (1)
| Publication Number | Publication Date |
|---|---|
| CN114567914A true CN114567914A (en) | 2022-05-31 |
Family
ID=81716783
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| CN202210175770.4A Pending CN114567914A (en) | 2022-02-24 | 2022-02-24 | Information transmission path planning method and device of wireless sensor network |
Country Status (1)
| Country | Link |
|---|---|
| CN (1) | CN114567914A (en) |
Cited By (2)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN115396977A (en) * | 2022-08-12 | 2022-11-25 | 中国联合网络通信集团有限公司 | Method, device and equipment for determining signal transmission path and storage medium |
| CN117109622A (en) * | 2023-09-21 | 2023-11-24 | 哈尔滨理工大学 | UUV ant colony path planning method for bidirectional search under multiple obstacles |
Citations (4)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN109945881A (en) * | 2019-03-01 | 2019-06-28 | 北京航空航天大学 | A kind of method for planning path for mobile robot of ant group algorithm |
| CN112650242A (en) * | 2020-12-22 | 2021-04-13 | 天津理工大学 | Mobile robot path planning method based on hybrid algorithm |
| CN113703450A (en) * | 2021-08-23 | 2021-11-26 | 皖西学院 | Mobile robot path planning method for improving ant colony algorithm based on smooth factors |
| CN113985888A (en) * | 2021-11-08 | 2022-01-28 | 合肥工业大学 | Forklift path planning method and system based on improved ant colony algorithm |
-
2022
- 2022-02-24 CN CN202210175770.4A patent/CN114567914A/en active Pending
Patent Citations (4)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN109945881A (en) * | 2019-03-01 | 2019-06-28 | 北京航空航天大学 | A kind of method for planning path for mobile robot of ant group algorithm |
| CN112650242A (en) * | 2020-12-22 | 2021-04-13 | 天津理工大学 | Mobile robot path planning method based on hybrid algorithm |
| CN113703450A (en) * | 2021-08-23 | 2021-11-26 | 皖西学院 | Mobile robot path planning method for improving ant colony algorithm based on smooth factors |
| CN113985888A (en) * | 2021-11-08 | 2022-01-28 | 合肥工业大学 | Forklift path planning method and system based on improved ant colony algorithm |
Non-Patent Citations (1)
| Title |
|---|
| 黄辰: "《基于智能优化算法的移动机器人路径规划与定位方法研究》", 《中国优秀博硕士学位论文全文数据库(博士)》, 15 April 2019 (2019-04-15) * |
Cited By (4)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN115396977A (en) * | 2022-08-12 | 2022-11-25 | 中国联合网络通信集团有限公司 | Method, device and equipment for determining signal transmission path and storage medium |
| CN115396977B (en) * | 2022-08-12 | 2024-08-20 | 中国联合网络通信集团有限公司 | Method, device, equipment and storage medium for determining signal transmission path |
| CN117109622A (en) * | 2023-09-21 | 2023-11-24 | 哈尔滨理工大学 | UUV ant colony path planning method for bidirectional search under multiple obstacles |
| CN117109622B (en) * | 2023-09-21 | 2024-03-26 | 哈尔滨理工大学 | UUV ant colony path planning method for bidirectional search under multiple obstacles |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| CN114567914A (en) | Information transmission path planning method and device of wireless sensor network | |
| CN113821029B (en) | Path planning method, device, equipment and storage medium | |
| CN114675643A (en) | Information transmission path planning method and device of wireless sensor network | |
| CN1951027A (en) | Location determination and location tracking in wireless networks | |
| CN105372628A (en) | Wi-Fi-based indoor positioning navigation method | |
| CN108709562A (en) | A kind of mobile robot rolling grating map construction method | |
| CN105704652A (en) | Method for building and optimizing fingerprint database in WLAN/Bluetooth positioning processes | |
| CN103513229A (en) | Positioning method based on WIFI signal | |
| CN113382060B (en) | Unmanned aerial vehicle track optimization method and system in Internet of things data collection | |
| CN113485429A (en) | Route optimization method and device for air-ground cooperative traffic inspection | |
| CN111711923A (en) | Wireless sensor network node positioning method based on UAV | |
| Bharadwaj et al. | Determination of optimal location for setting up cell phone tower in city environment using lidar data | |
| CN109946673A (en) | Networking radar node method of selecting based on the search of Monte Carlo tree | |
| CN110366188B (en) | Interference measurement point deployment method, interference measurement path planning method and system | |
| CN109560972B (en) | Non-cooperative inference method for Ad Hoc network physical topology | |
| CN108990148B (en) | Reference point selection method for indoor cooperative positioning | |
| JP3854252B2 (en) | Reception characteristic estimation apparatus and reception characteristic estimation method | |
| CN114910072A (en) | Unmanned aerial vehicle navigation method, device, equipment and medium based on deep reinforcement learning | |
| CN113727278B (en) | Path planning method, access network equipment and flight control equipment | |
| Javed et al. | Position Vectors Based Efficient Indoor Positioning System. | |
| CN112887909B (en) | Indoor positioning method based on Wi-Fi signals | |
| JP7505569B2 (en) | Communication information prediction device, communication information prediction method, and communication information prediction program | |
| CN115426658A (en) | Underground and shielded space wireless sensor network deployment method based on multi-objective optimization algorithm | |
| CN110602635B (en) | Indoor map matching enhanced positioning method, device and storage device | |
| CN111896001A (en) | Three-dimensional ant colony track optimization method |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| PB01 | Publication | ||
| PB01 | Publication | ||
| SE01 | Entry into force of request for substantive examination | ||
| SE01 | Entry into force of request for substantive examination |