CN107426703B

CN107426703B - A mobility prediction method based on fuzzy clustering in outdoor crowded places

Info

Publication number: CN107426703B
Application number: CN201710733379.0A
Authority: CN
Inventors: 李曦; 杨鹏波; 纪红; 张鹤立
Original assignee: Beijing University of Posts and Telecommunications
Current assignee: Beijing University of Posts and Telecommunications
Priority date: 2017-08-24
Filing date: 2017-08-24
Publication date: 2020-04-03
Anticipated expiration: 2037-08-24
Also published as: CN107426703A

Abstract

The invention relates to a mobility prediction method based on fuzzy clustering in outdoor crowded places, and belongs to the technical field of mobile communication. Divide the scene into several prediction areas, and divide the prediction time into several time periods. In each prediction area, the user movement trajectories are divided into different groups according to the prediction time period, and the irregular trajectories are excluded by using sequential pattern mining to find frequent trajectories. The sequence of movement patterns predicts the next location information by matching with the user's historical movement trajectory, thereby improving the accuracy of the prediction. The present invention ensures continuous communication service for users in outdoor crowded areas, effectively reduces unnecessary switching times and increases the staying time of users. The present invention analyzes and models the movement trajectory of the user in the outdoor densely populated area, which is helpful to analyze and solve other related outdoor user behavior problems in the densely populated area.

Description

Mobility prediction method based on fuzzy clustering in outdoor crowded place

Technical Field

The invention belongs to the technical field of mobile communication, and particularly relates to a mobility prediction method based on fuzzy clustering in an outdoor crowded place.

Background

With the explosive increase of data traffic in outdoor crowded areas, the prediction of the movement track and behavior of users can ensure the service quality of the communication network in the areas, and the prediction result can be applied to network deployment planning, resource allocation and mobility management. In an outdoor place with dense people flow, frequent movement of a user can cause the user to switch among different cells, and in order to ensure continuous service, resource allocation of a network is optimized through accurate prediction of a user track and smooth switching is ensured.

In outdoor crowded places, due to the huge number of users and the complex and varied behavior characteristics of users, how to quickly predict the next position of the user must be considered. Meanwhile, the behavior characteristics of the user will present different characteristics in different time and space, and how to comprehensively consider the factors influencing the motion trajectory must also be solved.

In the prior art, the next position of a user is predicted according to the movement characteristics of a single user, and the prediction precision of a new user is reduced; in the prediction scheme according to the multi-user movement characteristics, the influence factor of irregular movement tracks and the influence of space-time two dimensions are not considered, and the prediction precision is also reduced.

In the prediction scheme for predicting the next position of the user according to the moving track of the single user, for example, reference [1] (reference [1 ]: x.zhu, m.li, w.xia, and h.zhu, "a novel handoff algorithm-m for handover networks," China Communications, vol.13, No.8, pp.136-147, and Aug 2016), a handover algorithm based on speed and service perception is proposed, and the speed of the user is predicted by using a markov prediction model, so as to determine the next position area of the user to select a handover base station. But this mechanism only considers the current speed and direction of a single user, which will result in a reduction in prediction accuracy for an irregularly moving user.

In The prediction scheme for predicting The next position of a single user according to The moving tracks of multiple users, such as reference [2] (reference [2 ]: j. jeong, m.leonte, and a. property, "Cluster-aided location predictions," in IEEE info com 2016-The 35th Annual international conference Computer Communications, April2016, pp.1-9.), a method for predicting The next position area of a new user by using The tracks of all The mobile users is proposed, and The moving tracks of all The users are classified by a clustering algorithm and then similar moving tracks are extracted to improve The prediction accuracy. However, in the multi-user movement trajectory, the irregular user movement trajectory will reduce the overall prediction accuracy.

Under the condition that switching frequently occurs, the switching process can be optimized by utilizing the mobility prediction technology, and unnecessary switching times are reduced. However, in an outdoor crowded environment, the huge number of users and the variable user behaviors make accurate prediction more difficult, and the existing prediction model is no longer suitable for the mobility prediction in the scene.

Disclosure of Invention

Aiming at mobility prediction in outdoor crowded places, the invention provides a mobility prediction method based on fuzzy clustering in the outdoor crowded places in order to solve the problem that the existing prediction model is not applicable. The method of the invention adopts a clustering algorithm to divide the prediction area, divides the prediction time according to the characteristics of the research scene, clusters the movement track mode of the user in each prediction area, eliminates irregular movement tracks and finds out frequent sequences based on a sequence mode mining technology, thereby improving the movement prediction precision.

The invention provides a mobility prediction method based on fuzzy clustering in an outdoor crowded place, which comprises the following steps:

step 1, an initialization phase, comprising: dividing the whole area into a plurality of prediction areas; dividing time into a plurality of prediction time slots according to the characteristics of a researched scene, grouping user tracks contained in each time slot segment in each prediction area, and dividing the user tracks into different movement mode groups; and mining a frequent movement pattern sequence in each divided group of user tracks by using the sequence pattern.

Step 2, a prediction stage, comprising: adding the current position of the user into a position observation sequence, and selecting a prediction area corresponding to the current time period of the user according to the historical moving position track of the user; and dividing the user into similar movement mode groups in corresponding prediction areas, and selecting a frequent movement mode sequence with the highest matching degree as a prediction sequence by matching the historical movement track of the user with the frequent movement mode sequence in the groups so as to predict the next position information of the user.

Step 3, a switching execution stage, comprising: and determining a Base Station (BS) connected with the next position according to the predicted position in the prediction stage, and switching the optimal target BS.

The invention has the advantages that:

1. the mobility prediction scheme can realize accurate prediction of the user movement track in the outdoor crowded area, ensures the continuous communication service of the users in the outdoor crowded area, and decides the optimal target switching base station by predicting the next position area of the users, thereby ensuring the good continuous communication service of the users. According to the simulation result, the switching optimization is carried out based on the proposed prediction scheme, so that unnecessary switching times are effectively reduced, and the residence time of a user is increased.

2. The invention comprehensively considers the factors of two dimensions of the prediction time and the prediction space, realizes the detailed division of the user movement characteristics of the predicted area, and can more accurately predict the next position area of the user. The invention analyzes and models the user movement track of the outdoor crowd-sourced region, and is beneficial to analyzing and solving the user behavior problem of other related outdoor crowd-sourced regions.

Drawings

FIG. 1 is a mobility prediction scenario for an outdoor crowded place of the present invention;

FIG. 2 is an algorithmic flow chart of the movement prediction scheme of the present invention;

FIG. 3 illustrates an average number of handovers per prediction period for a user in accordance with an embodiment of the present invention;

FIG. 4 is a diagram illustrating the number of times users switch between different prediction regions according to an embodiment of the present invention;

FIG. 5 is a diagram illustrating average user retention times in different prediction regions according to an embodiment of the present invention.

Detailed Description

The present invention will be described in further detail with reference to the accompanying drawings and examples.

The invention provides a prediction scheme aiming at outdoor crowded places for researching the application of mobility prediction in outdoor scenes, and the next position area of a user is predicted by fully considering the factors of two dimensions of time and space, so that the fluency of switching of user equipment between outdoor communication cells is optimized, and the continuous service of the user is ensured.

In the outdoor people flow dense area, the invention introduces the mobility prediction technology to optimize the switching process and ensure the continuous communication service of the user.

As shown in fig. 1, taking a campus scenario as an example, the present invention divides the whole campus into a plurality of prediction areas according to people flow aggregation, divides the prediction time into a plurality of time periods according to the class work and rest time, divides the user movement trajectories into different groups in each prediction area according to the prediction time periods, eliminates irregular trajectories by using sequence pattern mining, finds out frequent movement pattern sequences, and predicts next location information by matching with the user historical movement trajectories, thereby improving the prediction accuracy. The mobility prediction method based on fuzzy clustering in the outdoor crowded place has the overall flow as shown in FIG. 2, the method divides a new user into the belonged prediction region according to the predicted time and the position of the new user, matches the most suitable movement track and predicts the next position region, and decides the optimal switching target base station according to the prediction result. The steps are explained below.

Step 1, an initialization stage, which mainly comprises two parts, wherein the first part is used for carrying out prediction area division, and the second part is used for grouping user tracks in each prediction area.

Firstly, by analyzing a mobile user gathering area, dividing the whole area into a plurality of prediction areas, grouping user tracks contained in each area, dividing time into a plurality of prediction time slots according to the characteristics of a researched scene, and predicting according to the movement characteristics of users in each time slot.

The method classifies the researched area into a plurality of prediction areas according to the distribution of the people stream based on a Kmeans clustering algorithm. The process of prediction region division includes step 1.1 to step 1.4.

Step 1.1, selecting the central position of the dense people flow area as a clustering center, and extracting position coordinate information from historical movement tracks of all users as a clustering data set.

Setting initialized cluster centers

Wherein u is_j＝(x_j,y_j) And expressing the position coordinates of the jth clustering center, and expressing the number of the selected clustering centers by K. Let the extracted set of user position coordinates be expressed as

Wherein s is_i＝(x_i,y_i) The ith user position in the set is represented, and N represents the number of positions.

And the number K of the clustering centers is determined according to the research scene and is associated with the distribution of the user in the research scene. Since the number of clusters in the prediction region partition is small, traversal from 2 to 10 can be adopted to determine the optimal number of cluster centers. And initially selecting the center position of the crowd dense area as a clustering center.

And 1.2, dividing all the positions according to the distance from the position of each user to the clustering center. Each cluster center corresponds to a partition region. To the collection

The distances from the position to all the cluster centers are calculated, and the position is divided into the area corresponding to the cluster center with the minimum distance.

User location s_iDistance cluster center u_jIs d(s)_i,u_j) As follows:

finding the user position s_iThe minimum distance from each cluster center is set as the distance from the cluster center

More recently, the following:

c_ican represent the area c to which the user belongs_i。

Step 1.3: update the cluster centers as follows:

in the formula (3), the jth cluster center u_jUpdating according to the position divided into the jth area, wherein the numerator represents the sum of all position coordinates belonging to the jth area, and the denominator represents the number of the position coordinates in the jth area.

Step 1.4: the objective function is solved as follows:

wherein, J_(c,u)And the sum of the distances between each user position and the clustering center of each belonging area is represented. Wherein the distance is

Can be calculated according to the formula (1).

Step 1.5, judging whether the target function converges to the minimum value, if so, finishing iteration, finishing prediction region division, and outputting each clustering center and the position in each region; otherwise, the step 1.2 is returned to and executed.

And in each iteration, updating and recording the minimum value of the objective function, and when the objective function value is not changed during the iteration, representing that the minimum value is converged and ending the iteration.

And (3) grouping the user tracks in each prediction area by using an FCM (Fuzzy C-means) algorithm, wherein in each prediction position area, the user moving tracks contained in each time period are extracted and classified, and the mobile users with similar tracks are classified into corresponding groups. The specific steps comprise step 2.1-step 2.2.

Step 2.1: for a certain prediction region, extracting the track sequence of L users contained in a set time period in the prediction region

Wherein P is_l＝<p_l1，p_l2，…，…p_lw，…，p_lW>For the track of user l, W represents the total number of positions in the track of user l, and set

The number of the clustering centers of the tracks of the L users is T, and the total number of the clustering centers is T. The track of one user only belongs to one track cluster center in one time period. And (4) clustering the central position of the initial track, and selecting the central position of the crowd dense area.

Step 2.2: and solving the membership degree of each user and the track clustering center according to the target function.

The objective function J is:

wherein, | | | represents solving Euclidean distance, m represents membership factor, e_tlRepresenting the user l as belonging to the trajectory cluster center v_tDegree of membership.

Degree of membership e_tlCalculated according to the following formula:

step 2.3: updating the central position of each track cluster, wherein the formula is as follows:

step 2.4: judging whether the target function converges to the minimum value, if not, continuing to execute the step 2.2, calculating the target function according to the formulas (5) and (6), and updating the track clustering center according to the formula (7); if so, namely when the target function is continuously reduced and the final convergence is not changed, namely the target function converges to the minimum value, the iteration is stopped.

And after the iteration is finished, outputting T track clustering centers and the user tracks of all the track clustering centers. Thus, the study area is divided into several prediction areas and the user movement trajectories of each area are classified according to the prediction time.

And then mining the movement tracks of all groups of users in each prediction area by using a sequence mode to find out the frequent movement track mode of the users in the same group. And clustering the movement tracks of the users in each prediction area, and mining by using a sequence mode to find out frequent movement tracks so as to eliminate irregular movement tracks.

And 2, a prediction stage.

Firstly, adding the current position of a user into a position observation sequence, and selecting a prediction area corresponding to the current time period of the user according to the historical movement position track of the user. The user can be divided into corresponding prediction areas according to the position coordinates where the user is currently located.

The users are then classified into corresponding groups of similar movement patterns within the predicted area. And selecting the frequent movement pattern sequence with the highest matching degree as a prediction sequence by matching the historical movement track of the user with the frequent movement pattern sequence in the group.

Dividing users into corresponding similar moving mode groups in a time slot in a prediction area by calculating the membership e of the users to each track clustering center in the prediction area_tlTo determine the group to which the user belongs.

And finally, according to and predicting the next position information of the user. The next position information is predicted by matching with the historical movement track of the user, so that the accuracy of prediction is improved.

Step 3, switching execution stage.

And determining the base station BS connected with the next position according to the predicted position obtained in the prediction stage. As shown in FIG. 2, let the currently connected base station be labeled as BS_qAnd the decided base station to be connected is marked as BS_p. When the BS is decided_pAnd the current connection BS_qAre identical to each otherWhen the BS is decided, the switching operation is not performed, and the next position prediction is performed in the prediction stage, if the BS is decided_pAnd the current connection BS_qDifferent, handover to target BS_pAnd returning to the prediction stage to continue predicting the next position.

Examples

As shown in fig. 1, in a campus dense traffic field, a Small-cell Base Station (SBS) is deployed in the area, and the coverage area is 100 m. The mobile user trajectory is extracted from the user data in reference [3] (reference 3: i.rhee, m.shin, s.hong, k.lee, s.kim, and s.chong, "Crawdad dataset ncsu/mobilitymodels," downloaded from http:// Crawdad. org/Crawdad/ncsu/mobilitymodels/20090723/, Jul2009.) and the position coordinates of the user are recorded every 30 seconds. And dividing the user tracks in the scene into 6 groups according to the comparison of the simulation performances, and counting the switching times of the users in each area and the residence time of the users in each cell range.

To demonstrate the performance of the mobility prediction optimized handover scheme (MPSDM) proposed herein, two handover mechanisms were chosen for comparison.

Mechanism 1 (MP-IUM): the scheme is based on the single-user movement characteristics and carries out the prediction of the next position information of the user.

Mechanism 2 (MP-MUM): according to the scheme, the next position information of the user is predicted based on the multi-user movement characteristics, and the influence of the movement characteristics of the user changing along with time and the motion trail of an irregular moving user on the prediction precision is not considered.

As shown in fig. 3, is the average number of handovers per prediction period for all users. Wherein, the abscissa represents 9 the prediction time period, and the ordinate represents the switching times, it can be seen from the figure that the switching times of the method of the present invention in each time period are less than those of the other two comparison schemes. At a time period t₁，t₄And t₇It can be seen that the number of switching times is greater than those in other periods because the three periods are the time to go to class and eat, and the increase in the number of switching times is caused by the large movement of the stream of people. As shown in fig. 4, the number of times the user switches in different predicted areas is shown. WhereinThe abscissa represents the area region and the ordinate represents the average switching times as can be seen from the figure, the switching times of the method of the present invention in each region are all smaller than the comparison scheme. The MP-IUM handover frequency is the largest because the MP-IUM is based on the moving track of a single user, and when the irregular movement of the user is predicted to increase, the prediction accuracy will decrease, and the decided handover base station is not optimal, which will result in frequent handover. The MP-MUM classifies similar movement tracks through the movement tracks of multiple users, and carries out corresponding movement group matching on new users to predict the next position. The method divides the prediction area, more accurately predicts the concentrated area, and divides the prediction time according to the characteristics of the research scene, thereby integrating the movement characteristics of the user in each position area and time period, eliminating irregular movement tracks, improving the prediction precision and reducing unnecessary switching times.

As shown in fig. 5, the average residence time of the user in different prediction regions is shown. Where the abscissa represents the prediction region and the ordinate represents the mean residence time it can be seen from the figure that the residence time of the method of the invention is greater than for the other two comparison schemes. Because the prediction accuracy of the comparison scheme on the next position of the user is reduced, the corresponding switching times are increased, so that the residence time of the user in the same cell is reduced. The method improves the accuracy of prediction and decides the optimal target base station by comprehensively considering the influence factors of space-time two dimensions, thereby reducing unnecessary switching times and improving the residence time of users in the same cell.

Claims

1. a mobility prediction method based on fuzzy clustering in outdoor crowded places, is characterized in that, comprises:

Step 1, the initialization phase, including: dividing the entire area into multiple prediction areas; dividing the time into several prediction time slots according to the characteristics of the studied scene, grouping the user trajectories in each time slot in each prediction area, and dividing are different movement pattern groups; use sequential patterns to mine the frequent movement pattern sequences in each group of user trajectories;

In the described step 1, the prediction area is divided based on the Kmeans clustering algorithm, which specifically includes:

Step 1.1, select K cluster centers, and extract the position coordinates from the historical movement trajectories of all users as a cluster data set; K is a positive integer;

Step 1.2, for each position in the cluster data set, according to the distance from the position to each cluster center, divide the position into the area corresponding to the cluster center with the smallest distance;

Step 1.3, update the position of each cluster center according to the position divided into each area;

Step 1.4, obtain the objective function, and the objective function is the sum of the distances between each user's location and the cluster center of their respective area;

Step 1.5, determine whether the objective function has converged to the minimum value, if so, end the iteration, complete the division of the prediction area, and output each cluster center and the user position coordinates in each prediction area; otherwise, go to step 1.2 to execute;

In the step 1, the user trajectories in each time slot in each prediction region are grouped by using the fuzzy C-means algorithm, which specifically includes:

Step 2.1, for a prediction area, extract the trajectory sequence of L users contained in a certain time slot in the prediction area, and set a total of T trajectory cluster centers of the L users, which are expressed as {v ₁ ,v ₂ , …,v _t ,…,v _T }; L and T are positive integers;

Step 2.2, calculate the objective function J of each user about each trajectory clustering center, as follows:

Among them, P _l represents the trajectory of user l, ||.|| represents the Euclidean distance, m represents the membership factor; e _tl represents the membership degree of user l belonging to the trajectory clustering center v _t , and the calculation formula is as follows:

Step 2.3, update the center position of each trajectory clustering, the formula is as follows:

Step 2.4, determine whether the objective function has converged to the minimum value, if not, continue to step 2.2 to execute; otherwise, stop the iteration, and output the T trajectory cluster centers and the user trajectory of each trajectory cluster center to which they belong;

Step 2, the prediction stage, includes: adding the user's current position to the position observation sequence, selecting the prediction area corresponding to the user in the current time period according to the user's historical movement trajectory; dividing the user into similar movement pattern groups in the corresponding prediction area, and matching The user's historical movement trajectory and the frequent movement pattern sequence in the group are selected, and the frequent movement pattern sequence with the highest matching degree is selected as the prediction sequence to predict the user's next position;

Step 3, the handover execution stage, includes: according to the predicted position in the prediction stage, deciding the base station connected to the next position, and performing the handover of the optimal target base station.

2 . The method according to claim 1 , wherein the K value range is [2, 10], and the optimal number of cluster centers is determined by traversing the values within the range. 3 .

3. The method according to claim 1, wherein, in the described step 2, the user is divided into similar movement pattern groups in the corresponding prediction area, by calculating the user's cluster center of each trajectory in the prediction area. Membership to determine the group to which the user belongs.

4. The method according to claim 1, wherein, in the described step 3, performing the optimal target base station handover is specifically: when the base station decided by the decision is the same as the currently connected base station, do not perform the handover operation, and then return to In the prediction stage, the prediction of the next position is performed; when the determined base station is different from the currently connected base station, switch to the determined base station, and then return to the prediction stage to predict the next position.