CN105722091A - Directional charging base station deployment method of wireless rechargeable sensor network - Google Patents

Abstract

The invention discloses a directional charging base station deployment method of a wireless rechargeable sensor network. According to the wireless rechargeable sensor network adopted by the invention, N rechargeable sensors are randomly deployed in a two-dimensional plane; according to the adopted wireless charging model, a directional base station only can charge one sensor at a moment, through rotating the direction of a charging antenna, different sensors can be charged at different moments in a time period, and moreover, one sensor only can be charged by one directional base station. The specific steps are as follows: 1, solving a sensor set with feasible base stations; 2, solving a candidate base station set corresponding to the result set RFS of the sensor set; 3, calculating appearing frequencies of the sensors; and 4, selecting the base stations from the candidate base stations as few as possible. According to the method, through combination of the time divided charging models of the rotary directional charging base stations, the method conforms to the practical application scene well; and through adoption of two heuristic algorithms based on cupidity, the operation speeds of the algorithms are improved.

Description

Directional charging base station deployment method for wireless rechargeable sensor network

technical field

The invention relates to the field of wireless rechargeable sensor networks, in particular to a method for deploying a directional charging base station of a wireless rechargeable sensor network.

Background technique

With the development of society and the advancement of science and technology, wireless charging technology is more and more widely used in equipment such as RFID and sensors, as well as in fields such as smart grid and civil structure monitoring. In the application of wireless rechargeable sensor networks, charging base stations need to be deployed according to the characteristics of rechargeable sensors, charging base stations and charging models to meet the requirements for continuous operation of the entire sensor network. Therefore, the deployment of charging base stations is a very important issue in the application of wireless rechargeable sensor networks.

Regarding the solution to the base station deployment problem in wireless rechargeable sensor networks, researchers have proposed corresponding solutions for different charging models. Dai Haipeng et al. proposed an approximate greedy algorithm for the problem of maximizing the wireless charging benefit of the entire sensor network in the article "A Layout Algorithm for Efficient Directed Wireless Chargers". Based on the discretized charging efficiency function, it geometrically analyzes and transforms the charging range of a limited number of directional base stations, reconstructs the original problem into a submodular problem, and then obtains the directional base station deployment that maximizes the network charging benefit Program. In the patent "A Deployment Method for Non-Contact Charging Nodes Oriented to Sensor Networks" (Patent No.: CN201310276000.X), Wu Yifan and others proposed a method to minimize the number of charging nodes while ensuring the continuous operation of all sensor nodes. A deployment method for contactless charging nodes. Based on the distribution area of gridded sensor nodes, this method selects the optimal grid point as the location for deploying the next charging node until all sensor nodes are charged. These base station deployment methods are not directly applicable to the application scenarios of rotatable directional wireless charging base stations. Therefore, the present invention proposes a base station deployment method for a rotatable directional charging model.

Contents of the invention

The invention proposes a method for deploying a directional charging base station of a wireless rechargeable sensor network. First, a certain sensor is taken as the initial element of the sensor set, and other sensors are added to the set in turn from near to far according to the distance of other sensors to this sensor, until the set is large enough that when adding the next sensor, a The base station is unable to charge all the sensors in the set. Repeat the above process to calculate their sensor set for each sensor. Secondly, for several given sensor sets, according to the generalized Fermat point convergence algorithm, the deployment position information of candidate base stations corresponding to each set is calculated respectively. Then, according to the information of the candidate base stations, the frequency of occurrence of each sensor is calculated. Finally, the base station that can charge the most uncharged sensors is preferred. If there are multiple such base stations, the sensor with the least occurrence frequency is selected from all the sensors corresponding to these base stations, and the base station that charges the sensor is selected as the result. The process of selecting candidate base stations is repeated until all sensors can be charged.

The technical solution steps adopted by the present invention to solve its technical problems are as follows:

The directional charging base station deployment method of the wireless rechargeable sensor network adopts the wireless rechargeable sensor network as follows: on a two-dimensional plane, N rechargeable sensors are randomly deployed; the wireless charging model adopted is: the directional base station is in Only one sensor can be charged at a time, but by rotating the direction of the charging antenna, different sensors can be charged at different times within a period of time. At the same time, a sensor can only be charged by one directional base station; the specific steps are as follows:

Step 1: Find the sensor set with feasible base stations;

Step 2: Find the candidate base station set corresponding to the result set RFS of the sensor set;

Step 3: Calculate the occurrence frequency of the sensor;

Step 4: Select as few base stations as possible from the candidate base stations;

In Step 1, to obtain the sensor set with feasible base stations, firstly, N rechargeable sensors are randomly deployed on a two-dimensional plane, and a certain sensor is used as the initial element of the sensor set, using S={s ₁ , s ₂ ,…,s _N } represent N sensors in the sensor network; then take the following steps:

1-1. Initialize j=1, make the result set RFS of the sensor set of the feasible base station empty;

1-2. Calculate the distance between the jth sensor s _j and other N-1 sensors, and sort them from small to large as s ^j ₁ , s ^j ₂ ,…,s ^j _N-1 , so that the sensor Set SS={s _j }, the number of initial elements k in the sensor set SS=1;

1-3. Determine whether there is a feasible base station position in the sensor set SS, if it exists, proceed to step 1-4; if not, proceed to step 1-5;

1-4. If k=N, then go to step 1-6, otherwise, add sensor s ^j _k to the set SS, and make k=k+1, return to step 1-3;

1-5. Let k=k-1, and delete the last added sensor s ^j _k from the set SS;

1-6. Add the set SS to the result set RFS of the sensor set of the feasible base station, if j=N+1, the algorithm terminates, otherwise set j=j+1, return to step 1-2.

The set of candidate base stations corresponding to the result set RFS of the set of sensors obtained in step 2 is as follows:

Given a sensor set SS'={s' ₁ ,s' ₂ ,...,s' _k }, find the position c _i of the feasible base station of this set SS', that is, find the position that satisfies where, Pw _j represents the energy consumption rate of the _{jth sensor s' j ;} d( _ci , s' _j ) represents the distance between the feasible base station _{ci and sensor s' j ;} P(d) is The charging efficiency function is a strictly monotonically decreasing function, and its value is related to the distance d(c _i ,s' _j ), the function equation is α and β are parameter values determined by the charging hardware, D is the maximum charging distance of the charging device; the equation can be obtained after simplification, and the position of the candidate base station is solved, that is, it is required to obtain the minimum value;

The convergence algorithm for solving the Fermat problem is extended to solve the above problems: the iterative function of the horizontal and vertical coordinates is Where x _j , y _j represent the two-dimensional coordinates of the sensor s' _j , x, y represent the coordinates of the feasible base station c _i in the last iteration; when the distance d( _ci , s' _j ) is greater than D, the result of Target At the same time, select the initial position that does not cross the boundary, that is, d(c _i ,s' _j ) is less than or equal to D for iteration; when the algorithm iterates to a fixed number of times, or when the difference between the results of two iterations is less than a certain threshold, the algorithm End; at this point, the deployment position c _i of the candidate base station can be obtained.

The frequency of occurrence of the calculated sensor described in step 3 is as follows:

Each candidate base station corresponds to a set of sensors that need to be charged; according to the information of the current candidate base station, the frequency of occurrence of each sensor in the current candidate base station is calculated.

Select as few base stations as possible from the candidate base stations described in step 4, first obtain the frequency of occurrence of the sensor from step 3, and then specifically operate as follows:

4-1. Initialize the uncharged sensor set S'={s ₁ , s ₂ ,...,s _n }, define the base station set BS to be selected and the final base station set Res to be empty;

4-2. According to the method in step 3, calculate the occurrence frequency of all sensors, filter out all sensors with an occurrence frequency of 1, find out the base stations that charge these sensors, and record these base stations in the base station set BS to be selected ;

4-3. Add the information in the base station set BS to be selected to the final base station set Res, and recalculate the uncharged sensor set S' according to the information of the final base station set Res. If S' is empty, the algorithm ends, otherwise, According to the method in step 3, recalculate the frequency of occurrence of each sensor in the uncharged sensor set S';

4-4. Clear the base station set BS to be selected, select the base station with the largest number of sensors in the updated sensor set S' from the candidate base stations, and record these base stations into the set BS. If the BS contains only one base station, Then go to step 4-3;

4-5. Obtain all the sensors TempS={s' ₁ ,...,s' _k } corresponding to the base stations included in the set of base stations to be selected BS, filter out the sensor s' _min with the least frequency of occurrence from TempS, and obtain the sensor The base station charged by s' _min , let the set of base stations to be selected BS only include this base station, go to step 4-3.

Beneficial effects of the present invention:

1. For the application of the rotatable and directional charging base station, the present invention considers the time-sharing charging model in the wireless sensor network in detail, which is more in line with the actual application scene.

2. The present invention adopts two greedy-based heuristic algorithms to improve the running speed of the algorithm, so that it can be applied to application scenarios with a large number of rechargeable sensors.

Description of drawings

Fig. 1 is a schematic diagram of a wireless rechargeable sensor network and a charging model adopted by the present invention;

Fig. 2 is a specific flowchart of deploying a rotatable and directional base station according to the present invention;

Figure 3 (a) and (b) are schematic diagrams for solving the sensor set of the feasible base station;

Figure 4(a) and (b) are schematic diagrams of the frequency of sensor occurrence;

Figure 5 (a), (b), (c), (d), (e), (f) are schematic diagrams of the operation process of the base station selection algorithm.

detailed description

The present invention will be further described below in conjunction with accompanying drawing.

The present invention mainly proposes a method for deploying a directional charging base station of a wireless rechargeable sensor network. All rechargeable sensors have the same specifications except for their respective power consumption. A sensor can only be charged by a directional base station. The specifications of the directional charging base stations are also the same. The base stations can only charge one sensor at a time, but they can charge different sensors at different times within a period of time by rotating the direction of the charging antenna. On a H*W two-dimensional plane, N rechargeable sensors are randomly deployed. On the premise of ensuring that all sensors in the entire sensor network can continue to work, it is necessary to find a deployment strategy for directional base stations, and make the number of base stations in the deployment strategy as small as possible.

The present invention uses a rotatable directional charging base station model. Its charging area is a sector, and the angle of the sector is related to the physical parameters of the directional charging antenna, so it can only provide energy for a specific direction. However, when charging, it can time-share charging for multiple directions by rotating the charging direction. Therefore, we need to consider the charging time allocation of the base station. It is worth noting that when the wireless charging antenna rotates, it will inevitably cause the sensors in other directions to be unable to be charged. At this time, it is also necessary to consider that the remaining energy of the sensor may be exhausted.

According to the schematic diagram of the wireless rechargeable sensor network model in FIG. 1 , the wireless rechargeable sensor network adopted in the present invention is as follows: N rechargeable sensors are randomly deployed on a two-dimensional plane. On the premise of ensuring that all sensors in the entire sensor network can continue to work, the present invention needs to find a deployment strategy for directional base stations so that the number of required base stations is as small as possible.

According to the schematic diagram of the time-sharing charging model in Figure 1, the wireless charging model used in the present invention is: the directional base station can only charge one sensor at a time, but it can charge the sensor at different times within a time period by rotating the direction of the charging antenna. Charge different sensors. At the same time, a sensor can only be charged by a directional base station.

The specific embodiments of the present invention will be further described in detail below in conjunction with the accompanying drawings. Its specific steps are described in Figure 2.

Step 1: Find the set of sensors with feasible base stations

On a two-dimensional plane, N rechargeable sensors are randomly deployed, and a certain sensor is used as the initial element of the sensor set. According to the distance from other sensors to this sensor, other sensors are added to the set in turn from near to far. Until the set is large enough that when the next sensor is added, one base station cannot charge all the sensors in the set. Repeat the above process to calculate their sensor set for each sensor.

We use S={s ₁ ,s ₂ ,...,s _N } to represent N sensors in the sensor network. At this point, finding the sensor set with feasible base stations can be divided into the following six steps:

1-1. Initialize j=1, make the result set RFS of the sensor set of the feasible base station empty;

1-2. Calculate the distance between the jth sensor s _j and other N-1 sensors, and sort them from small to large as s ^j ₁ , s ^j ₂ ,…,s ^j _N-1 , so that the sensor Set SS={s _j }, the number of initial elements k in the sensor set SS=1;

1-3. Determine whether there is a feasible base station position in the sensor set SS, if it exists, proceed to step 1-4; if not, proceed to step 1-5;

1-4. If k=N, then go to step 1-6, otherwise, add sensor s ^j _k to the set SS, and make k=k+1, return to step 1-3;

1-5. Let k=k-1, and delete the last added sensor s ^j _k from the set SS;

1-6. Add the set SS to the result set RFS of the sensor set of the feasible base station, if j=N+1, the algorithm terminates, otherwise set j=j+1, return to step 1-2.

Figure 3 (a), (b) is a schematic diagram of solving the sensor set of the feasible base station.

Step 2: Calculate the candidate base station set corresponding to the result set RFS of the sensor set

Given a sensor set SS'={s' ₁ ,s' ₂ ,…,s' _k }, find the position c _i of the feasible base station of this set SS', that is, find the position that satisfies The position of _ci . where Pw _j represents the energy consumption rate of the _jth sensor s'j. d( _{ci, s' j )} represents the distance between the feasible base station _{ci and the sensor s' j .} P(d) is the charging efficiency function, which is a strictly monotonically decreasing function, and its value is related to the distance d(c _i ,s' _j ), the function equation is α and β are parameter values determined by the charging hardware, and D is the maximum charging distance of the charging device. After simplification of the equation, it can be obtained, and to solve the position of the candidate base station, it is required to obtain minimum value.

We extend the convergence algorithm for solving the Fermat problem to solve the above problems. That is, the iterative function of the horizontal and vertical coordinates is where x _j , y _j represent the two-dimensional coordinates of sensor s' _j , and x, y represent the coordinates of feasible base station c _i in the last iteration. When the distance d(c _i ,s' _j ) is greater than D, the resulting value of Target is penalized (plus positive infinity). At the same time, an initial position that does not cross the boundary (that is, d(c _i , s' _j ) is less than or equal to D) is selected for iteration. When the algorithm iterates to a fixed number of times, or when the difference between the results of two iterations is less than a certain threshold, the algorithm ends. At this point, the deployment position c _i of the candidate base station can be obtained.

For all the sensor sets in the result set RFS of the sensor sets obtained in step 1, the generalized Fermat point convergence algorithm is executed once, so as to obtain all candidate base station deployment positions corresponding to the sensor sets.

Step 3: Count the occurrence frequency of the sensor

Each candidate base station corresponds to a set of sensors that need to be charged. According to the information of the current candidate base station (obtained from step 2 or step 4), the frequency of occurrence of each sensor in the current candidate base station is calculated.

Figure 4(a), (b) is a schematic diagram of the frequency of sensor occurrence. As shown in FIG. 4 , according to the information of the current candidate base station, the frequency of occurrence of each sensor in the current candidate base station can be calculated. It can be seen from FIG. 4 that there are three candidate base station positions C1, C2, and C3 in the figure. Base station C1 charges sensors S1, S2, S3, C2 charges S1, S4, and C3 charges S2, S4. Therefore, the frequency of occurrence of each sensor can be calculated separately: the frequency of occurrence of the sensor S1 is 2, the frequency of S2 is 2, the frequency of S3 is 1, and the frequency of S4 is 2.

Step 4: Select as few base stations as possible from the candidate base stations

After obtaining the frequency of appearance of the sensor in step 3, the present invention uses a greedy base station selection algorithm to select as few base stations as possible from the candidate base stations.

The idea of the base station selection algorithm is as follows: Firstly, find all the sensors whose occurrence frequency is 1. Next, select the charging base station corresponding to them. Then, the base station that can charge the most uncharged sensors is prioritized. If there are multiple such base stations, the sensor with the least frequency of occurrence is selected from all the sensors corresponding to these base stations, and finally the base station that charges the sensor is selected as the result. Update the frequency of occurrence of the sensors, and repeat the above steps until all the sensors can be charged.

The implementation of the base station selection algorithm is divided into the following five steps:

4-1. Initialize the uncharged sensor set S'={s ₁ , s ₂ ,...,s _n }, define the base station set BS to be selected and the final base station set Res to be empty;

4-2. According to the method in step 3, calculate the occurrence frequency of all sensors, filter out all sensors with an occurrence frequency of 1, find out the base stations that charge these sensors, and record these base stations in the base station set BS to be selected ;

4-3. Add the information in the base station set BS to be selected to the final base station set Res, and recalculate the uncharged sensor set S' according to the information of the final base station set Res. If S' is empty, the algorithm ends, otherwise, According to the method in step 3, recalculate the frequency of occurrence of each sensor in the uncharged sensor set S';

4-4. Clear the base station set BS to be selected, select the base station with the largest number of sensors in the updated sensor set S' from the candidate base stations, and record these base stations into the set BS. If the BS contains only one base station, Then go to step 4-3;

4-5. Obtain all the sensors TempS={s' ₁ ,...,s' _k } corresponding to the base stations included in the base station set BS to be selected, filter out the sensor s' _min with the least frequency of occurrence from TempS, and obtain the sensor The base station charged by s' _min , let the set of base stations to be selected BS only include this base station, go to step 4-3.

5(a)-(f) are schematic diagrams of the operation process of the base station selection algorithm.

Claims (4)

1. The directional charging base station deployment method of the wireless rechargeable sensor network is characterized in that the wireless rechargeable sensor network adopted is as follows: on a two-dimensional plane, N rechargeable sensors are randomly deployed; the wireless charging model adopted It is: the directional base station can only charge one sensor at a time, but by rotating the direction of the charging antenna, it can charge different sensors at different times within a period of time, and at the same time, a sensor can only be charged by one directional base station; specifically includes Follow the steps below: Step 1: Find the sensor set with feasible base stations; Step 2: Find the candidate base station set corresponding to the result set RFS of the sensor set; Step 3: Calculate the occurrence frequency of the sensor; Step 4: Select as few base stations as possible from the candidate base stations; In Step 1, to obtain the sensor set with feasible base stations, firstly, N rechargeable sensors are randomly deployed on a two-dimensional plane, and a certain sensor is used as the initial element of the sensor set, using S={s ₁ , s ₂ ,…,s _N } represent N sensors in the sensor network; then take the following steps: 1-1. Initialize j=1, make the result set RFS of the sensor set of the feasible base station empty; 1-2. Calculate the distance between the jth sensor s _j and other N-1 sensors, and sort them from small to large as s ^j ₁ , s ^j ₂ ,…,s ^j _N-1 , so that the sensor Set SS={s _j }, the number of initial elements k in the sensor set SS=1; 1-3. Determine whether there is a feasible base station position in the sensor set SS, if it exists, proceed to step 1-4; if not, proceed to step 1-5; 1-4. If k=N, then go to step 1-6, otherwise, add sensor s ^j _k to the set SS, and make k=k+1, return to step 1-3; 1-5. Let k=k-1, and delete the last added sensor s ^j _k from the set SS; 1-6. Add the set SS to the result set RFS of the sensor set of the feasible base station, if j=N+1, the algorithm terminates, otherwise set j=j+1, return to step 1-2. 2. The directional charging base station deployment method of the wireless rechargeable sensor network according to claim 1, characterized in that the candidate base station set corresponding to the result set RFS of the sensor set obtained in step 2 is as follows: Given a sensor set SS'={s' ₁ ,s' ₂ ,...,s' _k }, find the position c _i of the feasible base station of this set SS', that is, find the position that satisfies where, Pw _j represents the energy consumption rate of the _{jth sensor s' j ;} d( _ci , s' _j ) represents the distance between the feasible base station _{ci and sensor s' j ;} P(d) is The charging efficiency function is a strictly monotonically decreasing function, and its value is related to the distance d(c _i ,s' _j ), the function equation is α and β are parameter values determined by the charging hardware, D is the maximum charging distance of the charging device; the equation can be obtained after simplification, and the position of the candidate base station is solved, that is, it is required to obtain the minimum value; The convergence algorithm for solving the Fermat problem is extended to solve the above problems: the iterative function of the horizontal and vertical coordinates is Where x _j , y _j represent the two-dimensional coordinates of the sensor s' _j , x, y represent the coordinates of the feasible base station c _i in the last iteration; when the distance d( _ci , s' _j ) is greater than D, the result of Target At the same time, select the initial position that does not cross the boundary, that is, d(c _i ,s' _j ) is less than or equal to D for iteration; when the algorithm iterates to a fixed number of times, or when the difference between the results of two iterations is less than a certain threshold, the algorithm End; at this point, the deployment position c _i of the candidate base station can be obtained. 3. The directional charging base station deployment method of the wireless rechargeable sensor network according to claim 1, characterized in that the frequency of occurrence of the calculation sensor described in step 3 is as follows: Each candidate base station corresponds to a set of sensors that need to be charged; according to the information of the current candidate base station, the frequency of occurrence of each sensor in the current candidate base station is calculated. 4. The directional charging base station deployment method for a wireless rechargeable sensor network according to claim 3, characterized in that in step 4, select as few base stations as possible from the candidate base stations, and first obtain the frequency of occurrence of the sensor from step 3 , and then proceed as follows: 4-1. Initialize the uncharged sensor set S'={s ₁ , s ₂ ,...,s _n }, define the base station set BS to be selected and the final base station set Res to be empty; 4-2. According to the method in step 3, calculate the occurrence frequency of all sensors, filter out all sensors with an occurrence frequency of 1, find out the base stations that charge these sensors, and record these base stations in the base station set BS to be selected ; 4-3. Add the information in the base station set BS to be selected to the final base station set Res, and recalculate the uncharged sensor set S' according to the information of the final base station set Res. If S' is empty, the algorithm ends, otherwise, According to the method in step 3, recalculate the frequency of occurrence of each sensor in the uncharged sensor set S'; 4-4. Clear the base station set BS to be selected, select the base station with the largest number of sensors in the updated sensor set S' from the candidate base stations, and record these base stations into the set BS. If the BS contains only one base station, Then go to step 4-3; 4-5. Obtain all the sensors TempS={s' ₁ ,...,s' _k } corresponding to the base stations included in the set of base stations to be selected BS, filter out the sensor s' _min with the least frequency of occurrence from TempS, and obtain the sensor The base station charged by s' _min , let the set of base stations to be selected BS only include this base station, go to step 4-3.