CN111836193B - Mobile charging method of wireless sensor network based on greedy algorithm - Google Patents

Abstract

The invention discloses a greedy algorithm-based mobile charging method for a wireless sensor network. The invention is as follows: firstly, determining a set M of stop points in a wireless sensor network. And secondly, acquiring line segments between every two points in the stop point set M to form a line set V. And thirdly, identifying and judging one by one in the line set V, and selecting m line segments forming the loop. Setting the position of a charging base station for charging the charging trolley; the charging trolley is driven out from the charging base station and runs along a charging path; when the charging trolley reaches a charging stop point, charging the wireless sensor in the effective charging area of the charging stop point; all wireless sensors are charged as the charging trolley travels and stops along the charging path. The invention combines the advantages of mobile charging and wireless omnidirectional charging equipment, so that the charging trolley can charge a plurality of wireless chargeable sensors at one stop point at the same time, and the energy radiated during charging can be utilized to the maximum extent.

Description

A mobile charging method for wireless sensor network based on greedy algorithm

technical field

The invention belongs to the technical field of energy supply for wireless rechargeable sensor networks, in particular to a mobile charging method for wireless rechargeable sensor networks based on a greedy algorithm.

Background technique

Nowadays, with the requirements of technology, Wireless Rechargeable Sensor Networks (WRSN) technology has become the focus of many research fields. , but the charging base station is expensive and time-consuming and labor-intensive. There are also cases where a mobile car is used to move to each node for charging, and the low energy utilization rate is the disadvantage of this method.

At present, regarding the deployment of charging base stations in wireless rechargeable sensor networks, there have been some studies based on the different characteristics of charging base stations. Wan Peng et al. put forward a fixed base station optimization scheme for the entire sensor network in the patent "A method of deploying a charging base station for a wireless rechargeable sensor network" (patent number: CN109246602A), but the calculation process is relatively complicated and it is difficult to apply to large-scale transmission. configuration of the sensor network. In the patent "A Charging Control Method for Wireless Sensor Network Nodes" (Patent No.: 201611042178.8), Wang Jun et al. divided different priority areas according to the remaining energy of sensor nodes, and then used a car to charge according to the urgency of node charging. , but the division method of this method cannot guarantee that each node is just distributed in different areas according to the different needs, so that the moving path of the charging car cannot be reasonably planned.

SUMMARY OF THE INVENTION

The purpose of the present invention is to provide a mobile charging method for a wireless rechargeable sensor network based on a greedy algorithm.

The concrete steps of the present invention are as follows:

Step 1: Determine the positions of multiple charging stop points in the wireless sensor network; all wireless sensors are within the effective charging area of at least one charging stop point. Each charging stop point constitutes a stop point set M.

条线段，m为停留点集合M内充电停留点的数量。该

条线段组成线集合V。Step 2: Obtain the line segment between two points in the stop point set M, and obtain a total of

line segment, m is the number of charging stop points in the stop point set M. Should

The line segments form the line set V.

Step 3: Take an initial empty line set T.

Step 4: Add the line segment with the shortest length in the line set V to the line set T and delete it from the line set V. Determine whether the line segment in the line set T has a branch; if there is a branch, delete the line segment just added to the line set T from the line set T; otherwise, go to step 5.

Step 5: Determine whether the line segments in the line set T form a loop, if no loop is formed, perform step 4 again; if a loop is formed, go to step 6.

Step 6. If the number of line segments in the line set T is less than m, delete the line segment recently added to the line set T from the line set T, and perform steps 4 and 5 again; if the number of line segments in the line set T is equal to m, Then the m line segments forming the loop in the line set T are the charging path.

Step 7: Set the location of the charging base station for charging the charging car; the charging car drives out of the charging base station and drives along the charging path; each time the charging car reaches a charging stop point, it is the effective charging area of the charging stop point Wireless sensor charging inside; charging all wireless sensors as the charging cart travels and stops along the charging path.

Preferably, the specific method for determining each charging stop point in step 1 is as follows:

Step 1. Establish a plane rectangular coordinate system, and place n common nodes corresponding to the positions of the n wireless rechargeable sensors into the first quadrant of the plane rectangular coordinate system. The set composed of n ordinary nodes is designated as the total node set U; the n ordinary nodes are all within a rectangular range. After that, take the geometric center of the rectangular range as the center point, sort and number the n common nodes according to the distance from the center point from small to large;

Step 2. Assign 1 to i.

Step 3. Take the common node with the smallest number in the total node set U as the ith central node O _i .

Step 4: Taking the i-th central node O _i as the center of the circle and 2R as the radius to make a circle, the i-th characteristic circle is obtained, and R is the radius of the effective charging area of the charging device on the charging trolley. All ordinary nodes located in the _i -th characteristic circle are added to the candidate set Si and removed from the total node set U.

Step 5: Determine the position of one or more charging stop points within the range of the i-th characteristic circle.

5-1. Make a circle with the i-th central node O _i as the center and R as the radius to obtain the i-th central circle.

5-2. Assign 1 to j.

5-3. Select a point on the contour of the i-th center circle as the center, and use R as the radius to make a circle to obtain a candidate circle; move the center of the candidate circle along the edge of the i-th center circle for a week, and determine The candidate circle position that can cover the largest number of common nodes in the candidate set Si is _obtained as the cover circle ○ _ij ; the common nodes in the cover circle ○ _ij are removed from the candidate set Si and added to the feature set _{Qi ij .}

5-4. If there is only one common node in the feature set Q _ij , the common node is taken as the charging stop point c _ij .

If there are only two common nodes in the feature set Q _ij , the midpoint of the line connecting the two common nodes is taken as the charging stop point c _ij .

If the number of common nodes in the feature set Q _ij is greater than or equal to three, the two common nodes with the farthest distance in the feature set Q _ij are selected as the first screening node p ₁ and the second screening node p ₂ . The midpoint of the line connecting the first screening node p ₁ and the second screening node p ₂ is taken as a candidate node. Find the common node in the candidate set Q _j that is farthest from the candidate node except the first screening node p ₁ and the second screening node p ₂ , and denote it as the third screening node p ₃ . If the distance between the third screening node p ₃ and the candidate node is greater than R, proceed to step 5-5; otherwise, take the candidate node as the charging stop point c _ij , and directly proceed to step 5-6.

5-5. Take the first screening node p ₁ , the second screening node p ₂ , and the third screening node p ₃ as the three vertices of the characteristic triangle, respectively, to establish a characteristic triangle. Take the outer center of the characteristic triangle as the charging stop point c _ij , and then proceed to step 5-6.

5-6. If there are common nodes in the candidate set Si, increase _j by 1, and repeat steps 5-3 to 5-5; otherwise, go to step 6.

Step 6: If there are common nodes in the total node set U, increase i by 1, and repeat steps 3 to 5. If there is no ordinary node in the total node set U, the determination of the positions of all the charging stop points c _ij is completed, and all the charging stop points c _ij form the stop point set M.

Preferably, in step 7, when the electric quantity in the charging trolley is lower than the preset value, the charging trolley returns to the charging base station to replenish the electric quantity for itself; after the electric quantity of the charging trolley itself is replenished, it continues to drive to the charging path to charge each wireless sensor .

Preferably, in step 4, the branch indicates that any three or more line segments in the line set T intersect at the same charging stop point. In step 5, forming a loop means that a plurality of line segments in the line set T form a ring that is connected end to end in sequence.

Preferably, the charging base station is located at any charging stop point.

Preferably, the charging base station is located at a charging intensive point. The charging intensive point is the charging stop point with the smallest sum of distances to two adjacent charging stop points among all the charging stop points.

The beneficial effects that the present invention has are:

1. The present invention gets rid of the disadvantages of the original wireless rechargeable sensor network charging method, and combines the advantages of mobile charging and wireless omnidirectional charging equipment, so that the charging trolley can simultaneously charge multiple wireless rechargeable sensors at one stop point, It can maximize the use of the energy radiated during charging, which improves the charging efficiency and charging range to a new level.

2. The present invention plans a charging path with a short length at each selected charging stop point, thereby reducing the time and energy loss of the charging trolley during the transfer process.

3. The present invention enables the charging device to cover as many wireless rechargeable sensors as possible by moving the candidate circle on the central circle.

4. The present invention is based on a greedy algorithm, the time complexity of the algorithm is low, and it can be adapted to an application scenario with a large number of rechargeable sensors.

Description of drawings

1 is a schematic diagram of a charging stop point and a wireless rechargeable sensor network in the present invention;

Fig. 2 is the schematic diagram of selecting the first characteristic circle in step 3 of the present invention;

3 is a schematic diagram of the candidate circle moving on the central circle in step 4 of the present invention;

FIG. 4 is a schematic diagram of three situations in step 5-3 of the present invention.

Fig. 5a is the schematic diagram of forming branch;

Figure 5b is a schematic diagram of forming a loop;

FIG. 6 is a schematic diagram of the charging trolley moving on the resulting charging path in the present invention.

FIG. 7 is a line graph comparing the paths of the algorithm of the present invention (DGA) and other algorithms.

Detailed ways

A charging method for a wireless sensor network based on energy consumption classification, all wireless rechargeable sensors in the targeted wireless sensor network are arranged on the same plane. Use the charging cart and charging base to charge each wireless rechargeable sensor. A wireless omnidirectional charging device is installed on the charging trolley, which can charge one or more wireless rechargeable sensors in its effective charging area. The effective charging area is a circle with itself as the center and radius R. By setting up multiple charging stop points in the wireless sensor network, all wireless rechargeable sensors are within the effective charging area of at least one charging stop point; and then the charging trolley moves to each charging stop point one by one along the charging path, as All wireless rechargeable sensors are charged.

As shown in Figure 1, n random and known wireless rechargeable sensors and a charging base station for replenishing the charging car are set on the deployment plane of the wireless sensor network. In Figure 1, the hollow circle is the wireless rechargeable sensor; point C is the location of the charging base station; the cross point is one of the charging stop points; the circular range is the effective charging area when the charging trolley moves to the charging stop point.

Example 1

The specific steps of a wireless sensor network charging method based on energy consumption classification are as follows:

Step 1. Establish a plane rectangular coordinate system, and place n common nodes corresponding to the positions of the n wireless rechargeable sensors into the first quadrant of the plane rectangular coordinate system. The set composed of n ordinary nodes is designated as the total node set U; the n ordinary nodes are all within a rectangular range of H×L; the lower left corner of the rectangular range is the coordinate origin of the plane coordinate system. H and L are the length and width of the rectangular range respectively, and their values are determined according to the positions of all common nodes, so that the rectangular range covers all common nodes; after that, the geometric center of the rectangular range is used as the center point (H/2, L/2 ), the n common nodes are sorted and numbered according to the distance to the center point, from small to large; if the distances are the same, the common nodes close to the coordinate origin are taken in front of the row.

Step 2. Assign 1 to i.

Step 3. Take the common node with the smallest number in the total node set U as the ith central node O _i .

Step 4. As shown in Fig. 2, take the i-th central node O _i as the center and 2R as the radius to make a circle to obtain the i-th characteristic circle, where R is the radius of the effective charging area of the charging device on the charging trolley. All ordinary nodes located in the _i -th characteristic circle are added to the candidate set Si and removed from the total node set U.

Step 5: Determine the position of one or more charging stop points within the range of the i-th characteristic circle.

5-1. Make a circle with the i-th central node O _i as the center and R as the radius to obtain the i-th central circle.

5-2. Assign 1 to j.

5-3. As shown in Figure 3, select a point on the contour of the i-th central circle as the center of the circle, and use R as the radius to make a circle to obtain a candidate circle; place the center of the candidate circle along the i-th central circle Move the edge of , and determine the candidate circle position that can cover the largest number of common nodes in the candidate set Si, as the cover circle ○ _ij ; _remove the common nodes in the cover circle ○ _ij from the candidate set Si _, and add Feature set Qi _ij .

5-4. As shown in Figure 4, if there is only one common node in the feature set Q _ij , the common node is taken as the charging stop point c _ij .

If there are only two common nodes in the feature set Q _ij , the midpoint of the line connecting the two common nodes is taken as the charging stop point c _ij .

If the number of common nodes in the feature set Q _ij is greater than or equal to three, the two common nodes with the farthest distance in the feature set Q _ij are selected as the first screening node p ₁ and the second screening node p ₂ . The midpoint of the line connecting the first screening node p ₁ and the second screening node p ₂ is taken as a candidate node. Find the common node in the candidate set Q _j that is farthest from the candidate node except the first screening node p ₁ and the second screening node p ₂ , and denote it as the third screening node p ₃ . If the distance between the third screening node p ₃ and the candidate node is greater than R, proceed to step 5-5; otherwise, take the candidate node as the charging stop point c _ij , and directly proceed to step 5-6.

5-5. Take the first screening node p ₁ , the second screening node p ₂ , and the third screening node p ₃ as the three vertices of the characteristic triangle, respectively, to establish a characteristic triangle. Take the outer center of the characteristic triangle as the charging stop point c _ij , and then proceed to step 5-6.

5-6. If there are common nodes in the candidate set Si, increase _j by 1, and repeat steps 5-3 to 5-5; otherwise, go to step 6.

Step 6: If there are common nodes in the total node set U, increase i by 1, and repeat steps 3 to 5. If there is no common node in the total node set U, the determination of the positions of all the charging stop points c _ij is completed, and all the charging stop points c _ij form the stop point set M, and the process goes to step 7 .

条线段，m为停留点集合M内充电停留点的数量。该

条线段组成线集合V。并将线集合V内的

条线段按照从短到长的顺序进行排序并编号。Step 7. Sort the charging stop points in the stop point set M according to the sequence of the determined positions, and obtain the connecting line segment and the distance value between two points in the stop point set M, and obtain a total of

line segment, m is the number of charging stop points in the stop point set M. Should

The line segments form the line set V. and put the lines within the set V

Line segments are sorted and numbered from shortest to longest.

Step 8. Take an initial empty line set T; assign 1 to i.

Step 9: The line segment li (ie, the line segment with the shortest length) numbered _i in the line set V is added to the line set T and deleted from the line set V. Determine whether the line segment in the line set T has a branch; if there is a branch, delete the line segment _li just added to the line set T from the line set T; otherwise, go to step 10. As shown in Fig. 5a, the branch indicates that any three or more line segments in the line set T intersect at the same charging stop point.

Step 10: Determine whether the line segments in the line set T form a loop, if no loop is formed, increase i by 1, and execute Step 9; if a loop is formed, go to Step 11. As shown in Fig. 5b, forming a loop means that a plurality of line segments in the line set T form a closed loop connected end to end in sequence.

Step 11. If the number of line segments in the line set T is less than m, delete the line segment l _i recently added to the line set T from the line set T, increase i by 1, and perform steps 9 and 10; if the line set T If the number of line segments is equal to m, the m line segments forming a loop in the line set T are the charging path, as shown in FIG. 6 .

Step 12: Set the location of the charging base station; the charging base station is used to charge the charging car. The charging trolley travels from the charging base station to the charging stop point closest to the charging base station, and drives along the charging path; the charging trolley stops every time it reaches a charging stop point, which is a circle with the charging stop point as the center and R as the radius The wireless sensors within the range are charged; until the wireless sensors within the circular range are fully charged, the charging trolley continues to drive to the next charging stop point.

When the power in the charging trolley is lower than the preset value, the charging trolley returns to the charging base station to replenish power for itself; after the charging trolley itself is replenished, it continues to drive to the charging path to charge each wireless sensor.

In order to verify the advantages of the present invention in the overall running path of the charging car, the algorithm in the present invention is compared with the two algorithms "GA" in the article "Joint Power Charging and Routing in WirelessRechargeable Sensor Networks" published in the foreign journal "sensors". The algorithm (ie, the genetic algorithm) is compared with the "APS" algorithm (ie, the anchor point selection algorithm); the results are shown in Figure 7.

In Figure 7, the abscissa is the number of sensor nodes, and the ordinate is the total moving path of the charging car; the triangle connection (GA), star connection (APS) and the article "Joint Power Charging and Routing in WirelessRechargeable Sensor Networks" ” corresponds to the algorithm in ”; the dotted line (DGA) corresponds to the present invention; it can be clearly seen that a certain number of sensor nodes are arranged in the same plane, and the total moving path lengths of the three algorithms are similar when the number of nodes is small; After the number of nodes increases to 200, the gap begins to manifest; the total moving path length required by the present invention is obviously less; and thereafter, as the number of nodes continues to increase, the growth trend of the path value is also slower. It can be seen from this that the present invention is more excellent in the realization of reducing the moving path of the trolley, and the charging efficiency of the entire wireless rechargeable sensor network can be further improved.

Example 2

The difference between this embodiment and Embodiment 1 is that the specific charging base station position is determined; the charging base station position is located at the center point of the rectangular range described in step 1.

Example 3

The difference between this embodiment and Embodiment 1 is that a specific charging base station location is determined; the charging base station location is located at any charging stop point.

Example 4

The difference between this embodiment and Embodiment 1 is that: the specific location of the charging base station is determined; the location of the charging base station is located at a charging intensive point. The charging intensive point is the charging stop point with the smallest sum of distances to two adjacent charging stop points among all the charging stop points.

Claims (6)

1. A mobile charging method of a wireless sensor network based on a greedy algorithm is characterized in that: step one, determining a plurality of charging stop point positions in a wireless sensor network; all wireless sensors are within an active charging region of at least one charging dwell point; each charging stop point forms a stop point set M;

step two, obtaining line segments between every two points in the stop point set M to obtain the line segments

A line segment, wherein M is the number of charging stop points in the stop point set M; the device is

The line segments form a line set V;

step three, taking an initial blank line set T;

adding the segment with the shortest length in the line set V into the line set T and deleting the segment from the line set V; judging whether the line segments in the line set T are branched or not; any three or more line segments in the branch indicating line set T are handed over to the same charging stop point; if the branch appears, deleting the line segment just added into the line set T from the line set T; otherwise, entering the step five;

step five, judging whether the line segments in the line set T form a loop, and if the line segments in the line set T do not form a loop, executing the step four again; if a loop is formed, entering a sixth step;

step six, if the number of the line segments in the line set T is less than m, deleting the line segments which are recently added into the line set T from the line set T, and executing the step four and the step five again; if the number of the line segments in the line set T is equal to m, the m line segments forming a loop in the line set T are charging paths;

step seven, setting the position of a charging base station for charging the charging trolley; the charging trolley is driven out from the charging base station and runs along a charging path; when the charging trolley reaches a charging stop point, charging the wireless sensor in the effective charging area of the charging stop point; all wireless sensors are charged as the charging trolley travels and stops along the charging path.

2. The mobile charging method of the wireless sensor network based on the greedy algorithm, according to claim 1, wherein: the specific method for determining each charging stop point in the first step is as follows:

step 1, establishing a planar rectangular coordinate system, and placing n common nodes corresponding to the positions of n wirelessly rechargeable sensors into a first quadrant of the planar rectangular coordinate system; a set formed by n common nodes is a total node set U; n common nodes are all in a rectangular range; then, taking the geometric center of the rectangular range as a central point, and sequencing and numbering the n common nodes from small to large according to the distances from the central point;

step 2, assigning 1 to i;

step 3, taking the common node with the minimum number in the total node set U as the ith central node O_i；

Step 4, using the ith central node O_iAs the center of circle, 2R is a circle with radius,obtaining an ith characteristic circle, wherein R is the effective charging area radius of charging equipment on the charging trolley; adding all common nodes positioned in the ith characteristic circle into a candidate set S_iAnd is removed from the total node set U;

step 5, determining the positions of one or more charging stop points in the range of the ith characteristic circle;

5-1, with the ith central node O_iTaking R as radius as circle center to obtain ith central circle;

5-2, assigning 1 to j;

5-3, optionally selecting a point on the outline of the ith central circle as the center of the circle, and making a circle by taking R as the radius to obtain a candidate circle; moving the circle center of the candidate circle for one circle along the edge of the ith central circle to determine a candidate set S capable of being covered_iThe candidate circle position with the largest number of normal nodes is used as the covered circle_ij(ii) a Will cover round o_ijFrom the candidate set S_iRemoving and adding a feature set Q_ij；

5-4. if feature set Q_ijOnly one common node is arranged in the charging device, and the common node is taken as a charging stop point c_ij；

If the feature set Q_ijIf there are two common nodes, the middle point of the connecting line of the two common nodes is taken as the charging stop point c_ij；

If the feature set Q_ijIf the number of the inner common nodes is more than or equal to three, taking a characteristic set Q_ijTwo common nodes with the farthest distance in the middle are marked as a first screening node p₁Second screening node p₂(ii) a Get the first screening node p₁And a second screening node p₂The midpoint of the connecting line is used as a candidate node; finding a feature set Q_ijRemoving the first screening node p₁A second screening node p₂The common node farthest from the candidate node is marked as a third screening node p₃(ii) a If the third screening node p₃If the distance between the candidate node and the candidate node is larger than R, entering the step 5-5; otherwise, taking the candidate node as a charging stop point c_ijAnd directly entering the step 5-6;

5-5, screening the node p by the first screening node₁Second screening node p₂A third screening node p₃Establishing a characteristic triangle for three vertexes of the characteristic triangle respectively; using the outer center of the characteristic triangle as a charging stop point c_ijThen entering step 5-6;

5-6. if the candidate set S_iIf the common node exists, increasing j by 1, and repeatedly executing the steps 5-3 to 5-5; otherwise, entering step 6;

step 6, if common nodes exist in the total node set U, increasing i by 1, and repeating the steps 3 to 5; if no common node exists in the total node set U, all charging stop points c are completed_ijDetermination of position, all charging stop points c_ijA set of stop points M is formed.

3. The mobile charging method of the wireless sensor network based on the greedy algorithm, according to claim 1, wherein: step seven, when the electric quantity in the charging trolley is lower than a preset value, the charging trolley returns to the charging base station to supplement the electric quantity for the charging trolley; and after the electric quantity of the charging trolley is supplemented, the charging trolley continuously runs to a charging path to charge each wireless sensor.

4. The mobile charging method of the wireless sensor network based on the greedy algorithm, according to claim 1, wherein: and step five, forming a plurality of line segments in the loop representation line set T to form a ring shape which is sequentially connected end to end.

5. The mobile charging method of the wireless sensor network based on the greedy algorithm, according to claim 1, wherein: the charging base station is positioned at any one charging stop point.

6. The mobile charging method of the wireless sensor network based on the greedy algorithm, according to claim 1, wherein: the charging base station is positioned at a charging dense point; the charging intensive point is the charging stop point with the minimum sum of the distances from the charging stop points to two adjacent charging stop points.

Images