CN111263362B - Density distribution-based k-anonymous location privacy protection method and system - Google Patents

Abstract

The invention relates to a k-anonymous location privacy protection method and a system based on density distribution, which comprises the steps of constructing a polygonal k-anonymous area according to k-1 neighbor user location points found by the periphery of an inquiry user, and calculating a k-density value of the polygonal k-anonymous area; comparing the k-density value with a set maximum density threshold value and a set minimum density threshold value respectively; when the k-density value is between the maximum density threshold and the minimum density threshold, taking the geometric center of the anonymous area of the polygon k as an anchor point, and sending the anonymous area of the polygon k to a server for position query; expanding a polygon k-anonymous region when the k-density value is greater than the maximum density threshold; adding a number of false location points within the polygon k-anonymous region when the k-density value is less than the minimum density threshold. The invention can effectively improve the privacy protection effect and the query service quality of the k-anonymous location privacy protection method.

Description

K-anonymous location privacy protection method and system based on density distribution

technical field

The invention relates to the field of network and information security, in particular to a density distribution-based k-anonymous location privacy protection method and system.

Background technique

With the development of mobile positioning technology and wireless communication technology, more and more mobile devices on the market have GPS precise positioning function, making Location-Based Service (LBS) one of the most promising services for mobile users. . However, while LBS provides convenience to people and brings huge benefits to society, people also pay more attention to the problem of leakage of sensitive information when using LBS. Since the acquisition of services requires interworking between different Location Services Providers (LSPs), the user's location data must be shared among them. An untrustworthy third party can easily obtain some important personal information of users by analyzing and comparing the above location information. Once this private information falls into an illegal system, it will seriously threaten the safety of users.

Location privacy protection methods are mainly divided into spatial anonymity methods, fake location methods and encryption methods. Sweeney et al. ("Sweeney.k-Anonymity: A model for protecting privacy[J].International Journal of Uncertainty Fuzziness and Knowledge-Based Systems, 2012,10(05):557-570.") proposes the privacy protection method of spatial anonymity The effect is good, but this method not only consumes more time and reduces the accuracy of the query when the area of the anonymous area is too large, but also requires the assistance of the central anonymous server, which is likely to become a system bottleneck. Hwang R H et al. (“Hwang R H, HsuehY L, Wu J J, et al. Social Hide: A Distributed Framework for Location Privacy Protection [J]. Journal of Network & Computer Applications, 2016, 76:87-100.”) proposed based on The P2P spatial anonymity method realizes the k-anonymous privacy protection of the distributed system, but ignores the security issues of neighbor nodes, and greatly increases the various software and hardware resources and communication overheads of smartphones. The encryption method proposed by Kim H I et al. (“Kim H I, Kim H J, Chang J W.A secure kNN query processing algorithm using homomorphic encryption on outsourced database[J].Data&Knowledge Engineering, 2017.”) can protect location privacy very well , but the resource overhead is too large. The fake location method does not need to build an anonymous area, and does not need the assistance of TTP. The mobile client can achieve location anonymity by generating a fake location, which can well make up for the shortcomings of the spatial anonymity method and the encryption method.

Currently, k-anonymity is the preferred method for location privacy protection. The k-anonymous method was born in the relational database. It uses generalization and fuzzy technical means to process the key attribute values in the database, so that any one of the k records after generalization cannot be distinguished from it alone, so as to realize the location anonymized. Gruteser et al. (“Gruteser M, Grunwald D. Anonymous usage of location-based services through spatial and temporal cloaking[C]//International Conference on Mobile Systems, Applications.DBLP, 2003:31-42.”) put the k-anonymous method Introduced into location privacy protection. Gedik et al. ("Gedik B, Liu L. Protecting Location Privacy with Personalized k-Anonymity: Architecture and Algorithms[J]. IEEE Transactions on Mobile Computing, 2008, 7(1):1-18.") proposed to satisfy users The location k-anonymity method for personalized privacy requirements, users can define the k value and anonymity level to achieve personalized anonymity, but the actual effect of this method is poor when the k value is too large.

In the study of k-anonymous region construction method, Bamba et al. (“BambaB, Liu L, Pesti P, et al.Supporting Anonymous Location Queries in Mobile Environments with PrivacyGrid[C]//International Conference on World Wide Web.ACM, 2008 :237-246.") proposed a grid division method. In this method, for different privacy requirements, two algorithms, Top-Down Grid Cloaking and Bottom-Up Grid, are provided for optional use. Xu et al. (“Xu J, Tang X, Hu H, et al. Privacy-Conscious Location-Based Queries in Mobile Environments [J]. IEEE Transactions on Parallel & Distributed Systems, 2010, 21(3): 313-326.”) proved that The size of the k-anonymous region has a great influence on the accuracy of query results, which provides guidance for the research of anonymous region division methods. On this basis, Zhao et al. (“Zhao Z, Hu H, Zhang F, et al. A k-anonymous algorithm in location privacy protection based on circular zoning[J]. Journal of Beijing Jiaotong University, 2013, 37(5): 13-18.") proposed an anonymous method for circular region division, Yang et al. ("Yang Y, Wang R. Rectangular Region K-Anonymity Location Privacy Protection Based on LBS in Augmented Reality[J]. ), 2016,39(4):44-49.") proposed an anonymous method for rectangular area division in augmented reality. These methods improve the anonymity effect to a certain extent, but they do not fully consider the k-density distribution and terrain characteristics. Xie et al. ("XieP.A-anonymous Polygon Area Construction Method and Algorithm Based on LBSPrivacy Protecting[J].Journal of Information&Computational Science,2015,12(15):5713-5724.") proposed k- The anonymous algorithm reduces the effective area of the anonymous area by constructing an irregular polygonal anonymous area. However, the time complexity of the anonymous area generation algorithm used in this method is high, which affects the quality of service. Moreover, this method only considers the Euclidean space distance, but does not consider the user density distribution and the diversity of the environment.

Although the existing k-anonymous location privacy protection methods can protect location privacy well, they all have common shortcomings: (1) Most of them choose regular geometric shapes to construct anonymous regions, without considering the terrain and regional characteristics, the attacker may pass through Geographical features exclude invalid areas to infer the user's real location; (2) Most of the anonymity methods that do not consider the area fail due to insufficient k value, and need to re-use another location privacy protection method, which greatly increases the preprocessing time and reduces the query time. Quality of service; (3) Most of them do not consider the k-density distribution. If the value of k is too large or the value of k is too small, it will be easier to expose the location privacy of query users.

Contents of the invention

The purpose of the present invention is to provide a k-anonymous location privacy protection method and system based on density distribution, which solves the problem that the existing k-anonymous location privacy protection method does not fully consider the geographical characteristics of the query user's location and the k-density distribution , effectively improving the privacy protection effect and query service quality of the k-anonymous location privacy protection method.

To achieve the above object, the present invention provides the following scheme:

A k-anonymous location privacy protection method based on density distribution, comprising:

Obtain the k-1 nearest neighbor user location points found around the query user;

According to the k-1 neighbor user location points and the query user location point, a fast convex hull generation algorithm is used to construct a polygonal k-anonymous region;

Calculating the k-density value of the k-anonymous region of the polygon;

Comparing the k-density value with the set maximum density threshold and minimum density threshold respectively;

When the k-density value is between the maximum density threshold and the minimum density threshold, using the geometric center of the polygon k-anonymous area as an anchor point, the polygon k-anonymous area is sent to the server for location query;

When the k-density value is greater than the maximum density threshold, expand the polygon k-anonymous area, and use the geometric center of the expanded polygon k-anonymous area as an anchor point to send the expanded polygon k-anonymous area to the server for location queries;

When the k-density value is less than the minimum density threshold, add several false location points in the polygon k-anonymous area, and add the k-1 adjacent user location points, the query user location point, and all The fake location point is sent to the server for location query.

Optionally, the acquiring k-1 neighbor user location points found around the query user specifically includes:

A location point is set around the query user as a midpoint, and k-1 location points of neighboring users are obtained by scanning.

Optionally, according to the k-1 neighbor user location points and the query user location point, a fast convex hull generation algorithm is used to construct a polygonal k-anonymous region, which specifically includes:

Select a position point with the smallest abscissa among the k-1 adjacent user position points and query user position points, determine it as a special position point, and when there are multiple special position points, select a position point at the special position point Select a position point with the smallest ordinate in , and determine it as the final special position point;

Select a direction as the counterclockwise direction, and calculate the special vector formed between each remaining position point and the special position point except the special position point;

Calculate the angle between each of the special vectors and the negative direction of the y-axis;

Sort all the position points according to the included angle from small to large to obtain an ordered set;

According to the state of the double-ended queue at the set moment, each location point in the ordered set is traversed to construct a polygonal k-anonymous area.

Optionally, the calculation of the k-density value of the polygon k-anonymous region specifically includes:

Calculate the area value of the anonymous region of the polygon k in a recursive manner;

According to the area value, the k-density value of the k-anonymous area of the polygon is calculated.

A k-anonymous location privacy protection method based on density distribution, comprising:

Obtain the k-1 nearest neighbor user location points found around the query user;

According to the k-1 neighbor user location points and the query user location point, a fast convex hull generation algorithm is used to construct a polygonal k-anonymous region;

Calculate the area value of the anonymous region of the polygon k;

Comparing the area value with a set maximum area threshold and a minimum area threshold respectively;

When the area value is between the maximum area threshold and the minimum area threshold, using the geometric center of the polygon k anonymous area as an anchor point, the polygon k anonymous area is sent to the server for location query;

When the area value is less than the minimum area threshold, expand the polygon k anonymous area, and use the geometric center of the expanded polygon k anonymous area as an anchor point, and send the enlarged polygon k anonymous area to the server for location inquiries;

When the area value is greater than the maximum area threshold, add several false location points in the anonymous area of the polygon k, and add the k-1 adjacent user location points, the query user location point, and the fake The location point is sent to the server for location lookup.

A k-anonymous location privacy protection system based on density distribution, including:

The location point acquisition module is used to obtain the k-1 nearest neighbor user location points found around the query user;

A polygonal k anonymous area construction module is used to construct a polygonal k anonymous area by using a fast convex hull generation algorithm according to the k-1 neighbor user location points and query user location points;

k-density value calculation module, used to calculate the k-density value of the polygon k anonymous region;

A comparison module, for comparing the k-density value with a set maximum density threshold and a minimum density threshold respectively;

The first sending module is configured to use the geometric center of the polygon k-anonymous region as an anchor point to send the polygon k-anonymous region when the k-density value is between the maximum density threshold and the minimum density threshold to the server for location queries;

The second sending module is configured to expand the polygon k-anonymous area when the k-density value is greater than the maximum density threshold, and use the geometric center of the enlarged polygon k-anonymous area as an anchor point to expand the expanded The polygon k anonymous area after is sent to the server for location query;

The third sending module is used to add several false location points in the polygon k-anonymous area when the k-density value is less than the minimum density threshold, and add the k-1 neighboring user location points, all The query user location point and the false location point are sent to the server for location query.

Optionally, the location point acquisition module specifically includes:

The location point acquisition unit sets a location point around the query user as a midpoint, and scans to obtain k-1 adjacent user location points.

Optionally, the polygon k anonymous region construction module specifically includes:

The special location point determination unit is used to select a location point with the smallest abscissa among the k-1 adjacent user location points and the query user location point, and determine it as a special location point, and when the special location point is a plurality of , select a position point with the smallest ordinate among the special position points, and determine it as the final special position point;

A special vector calculation unit, configured to select a direction as the counterclockwise direction, and calculate a special vector formed between each remaining position point and the special position point except the special position point;

An included angle calculation unit, configured to calculate the included angle between each of the special vectors and the negative direction of the y-axis;

The ordered set determination unit is used to sort all the position points according to the included angle from small to large to obtain an ordered set;

The polygon k-anonymous area construction unit is used for traversing each location point in the ordered set according to the state of the double-ended queue at the set moment, and constructing the polygon k-anonymous area.

Optionally, the k-density value calculation module specifically includes:

an area value calculation unit, configured to recursively calculate the area value of the anonymous area of the polygon k;

The k-density value calculation unit is configured to calculate the k-density value of the k-anonymous area of the polygon according to the area value.

A k-anonymous location privacy protection system based on density distribution, including:

The location point acquisition module is used to obtain the k-1 nearest neighbor user location points found around the query user;

A polygonal k anonymous area construction module is used to construct a polygonal k anonymous area by using a fast convex hull generation algorithm according to the k-1 neighbor user location points and query user location points;

An area value calculation module, used to calculate the area value of the anonymous area of the polygon k;

A comparison module, configured to compare the area value with a set maximum area threshold and a minimum area threshold;

A first sending module, configured to use the geometric center of the polygon k anonymous area as an anchor point to send the polygon k anonymous area to the server when the area value is between the maximum area threshold and the minimum area threshold for location inquiries;

The second sending module is configured to expand the polygon k anonymous area when the area value is less than the minimum area threshold, and use the geometric center of the enlarged polygon k anonymous area as an anchor point to transfer the expanded polygon k to The polygon k anonymous area is sent to the server for location query;

The third sending module is configured to add several false location points in the anonymous area of the polygon k when the area value is greater than the maximum area threshold, and send the k-1 adjacent user location points, the query The user location point and the fake location point are sent to the server for location query.

According to the specific embodiments provided by the invention, the invention discloses the following technical effects:

(1) Construct a polygonal anonymous area according to the different terrain characteristics of the area where the query user is located.

(2) Applying a fast polygon generation algorithm further improves the efficiency of k-anonymous region generation.

(3) According to the k-density distribution, the effectiveness of k-anonymous location privacy protection is further improved by using the method of combining region anonymity and fake location.

The invention improves the k-anonymous area generation efficiency, improves the effectiveness of the k-anonymous location privacy protection, and further improves the location query service quality while ensuring the privacy protection effect.

Description of drawings

In order to more clearly illustrate the technical solutions in the embodiments of the present invention or the prior art, the following will briefly introduce the accompanying drawings required in the embodiments. Obviously, the accompanying drawings in the following description are only some of the present invention. Embodiments, for those of ordinary skill in the art, other drawings can also be obtained according to these drawings without paying creative labor.

Fig. 1 is a simple block diagram of the k-anonymous location privacy protection method based on density distribution in the present invention;

Fig. 2 is the flowchart of the k-anonymous location privacy protection method based on the density distribution of the present invention;

3 is a structural diagram of the k-anonymous location privacy protection system based on density distribution in the present invention;

Fig. 4 is a topographic feature map of the real region of the present invention;

Fig. 5 is the polygonal k-anonymous area that the present invention generates;

Fig. 6 is an invalid anonymous area diagram of the present invention;

Fig. 7 is a diagram of a privacy protection area combining area anonymity and fake location in the present invention.

Detailed ways

The following will clearly and completely describe the technical solutions in the embodiments of the present invention with reference to the accompanying drawings in the embodiments of the present invention. Obviously, the described embodiments are only some, not all, embodiments of the present invention. Based on the embodiments of the present invention, all other embodiments obtained by persons of ordinary skill in the art without making creative efforts belong to the protection scope of the present invention.

In view of the fact that the existing k-anonymous location privacy protection method does not fully consider the terrain characteristics and k-density distribution of the area where the query user is currently located, in order to improve the query service quality and privacy protection effect, the present invention proposes a density distribution-based Polygonal k-anonymous location privacy protection method and system. The polygonal anonymous region construction algorithm proposed by the present invention can quickly construct an anonymous region that matches the topographical features. According to the k-density threshold, the strategy of combining regional anonymity and false location is used to implement location privacy protection, effectively improving the location privacy protection effect and Query service quality.

In order to make the above objects, features and advantages of the present invention more comprehensible, the present invention will be further described in detail below in conjunction with the accompanying drawings and specific embodiments.

Embodiment one

The invention discloses a k-anonymity location privacy protection method based on density distribution, which mainly solves the problem that in the existing location privacy protection method based on k-anonymity, the terrain characteristics and k value of the user's area are not fully considered when generating an anonymous area The problem of density distribution. As shown in Figure 1, first find k-1 neighboring user locations around the current user, and generate an irregular polygonal area according to the convex hull calculation; then calculate the distribution density of k users in the polygonal area, according to the density parameter value Different strategies are applied to implement location privacy protection. When the k-density value meets the set density threshold, the polygonal area is sent to the LBS server for location query with the geometric center of the polygon as the anchor point; when the k-density value is greater than the set maximum density threshold, further expand Then use the expanded polygonal geometric center as the anchor point to send the polygonal area to the LBS server for location query; when the k-density value is less than the set minimum density threshold, add some fake location points, and k-1 neighboring user location points, query user location points and false location points are sent to the LBS server for query.

As shown in FIG. 2 , a density distribution-based k-anonymous location privacy protection method provided by the present invention specifically includes the following steps.

Step 101: Obtain k-1 nearby user location points found around the query user. Specifically:

A location point is set around the query user as a midpoint, and k-1 location points of neighboring users are obtained by scanning.

Step 102: Construct a polygonal k-anonymous region by using a fast convex hull generation algorithm according to the k-1 neighboring user location points and the query user location point. Specifically:

(1) Select a position point with the smallest abscissa among the k-1 adjacent user position points and query user position points, and determine it as a special position point, and when there are multiple special position points, in the Select a position point with the smallest ordinate among the special position points, and determine it as the final special position point P ₀ .

(2) Select a direction as the counterclockwise direction, and calculate the special vector formed by each remaining position point P _x and the special position point P ₀ except the special position point P ₀

与y轴负方向的夹角。(3) Calculate each of the special vectors

Angle with the negative direction of the y-axis.

(4) Sorting all the position points according to the included angle from small to large to obtain an ordered set S={P ₀ , P ₁ , P ₂ , . . . , P _k-1 }.

(5) According to the state P _t P _t-1 P ₀ ... P _b-1 P _b of the double-ended queue at the set time, traverse each position point in the ordered set to construct a polygonal k-anonymous area.

Step (5) further includes:

If it is P ₀ , first put P ₀ into the tail of the queue, if it is P ₁ , then enter the tail of the queue, if it is P ₂ , then enter the head of the queue and then enter the tail of the queue.

Assume traversing to the current node P _i : if P _b-1 P _b P _i can maintain the left-turn characteristic, continue, otherwise P _b will leave the end of the queue, and so on until P _bm-1 P _bm P _i can satisfy the left-turn characteristic, P _t enters the tail of the queue.

Assume traversing to the current node P _i : if P _i P _t P _t-1 can maintain the left-turn characteristic, continue, otherwise P _t will go out of the queue, and so on until P _i P _tn P _tn-1 can satisfy the left-turn characteristic, P _i enters the head of the team.

Return the double-ended queue D, and the construction of the polygon area is completed.

Step 103: Calculating the k-density value of the k-anonymous region of the polygon. Specifically:

The area value of the anonymous region of the polygon k is calculated in a recursive manner.

According to the area value, the k-density value of the k-anonymous area of the polygon is calculated.

Step 104: Compare the k-density value with the set maximum density threshold and minimum density threshold respectively.

Step 105: When the k-density value is between the maximum density threshold and the minimum density threshold, take the geometric center of the polygon k-anonymous area as the anchor point, and send the polygon k-anonymous area to the server for Location query.

Step 106: When the k-density value is greater than the maximum density threshold, expand the anonymous region of polygon k, and take the geometric center of the anonymous region of enlarged polygon k as the anchor point, and place the enlarged polygon k The anonymous zone is sent to the server for location queries. Specifically:

When the k-density value is greater than the maximum density threshold, expand the polygon k-anonymous region until the k-density value is between the maximum density threshold and the minimum density threshold and stop, and then expand The geometric center of the polygon k-anonymous area is used as an anchor point, and the enlarged polygon k-anonymous area is sent to the server for location query.

Step 107: When the k-density value is less than the minimum density threshold, add several false location points in the polygon k-anonymous area, and add the k-1 neighboring user location points, the query user location Points and the fake location point are sent to the server for location query. Specifically:

When the k-density value is less than the minimum density threshold, add several false position points in the polygon k-anonymous area until the k-density value is between the maximum density threshold and the minimum density threshold , and then send the k-1 neighboring user location points, the query user location point and the false location point to the server for location query.

A k-anonymous location privacy protection method based on density distribution proposed by the present invention has high efficiency, and the polygonal area generation method adopted can obtain anonymous areas that match the terrain features, and the location privacy protection is implemented by combining the area anonymity and false location strategy, While ensuring the query service quality, the privacy protection effect is further improved. Especially for the case where the regional anonymity method fails, the method combined with the fake location improves the effectiveness of k-anonymous location privacy protection.

Embodiment two

The present invention is a k-anonymous location privacy protection method based on density distribution. When a user needs location query, the current location and query request are first sent to TTP. With a certain location point as the center, k (including the current query location) neighboring user location points are queried, and the convex hull algorithm is used to construct a polygonal anonymous area. Then according to the set k-density parameters ρ _amx and ρ _min , calculate the minimum area threshold (S _min ) and maximum area threshold (S _max ) of the effective anonymous area, and apply the recursive method to calculate the area S(Rs) of the polygonal anonymous area, According to the size of the area, the location privacy protection is implemented by combining the method of expanding the anonymous area and adding fake locations. When S(Rs)>S _max , add several fake locations in this area, and TTP will send the found neighboring user locations, the added fake locations and the current query user location to the LBS server for location query.

Including the following steps:

Obtain the k-1 nearest neighbor user location points found around the query user.

According to the k-1 adjacent user location points and the query user location point, a fast convex hull generation algorithm is used to construct a polygonal k-anonymous region.

Calculate the area value of the anonymous region of the polygon k.

The area value is compared with the set maximum area threshold and minimum area threshold respectively.

When the area value is between the maximum area threshold and the minimum area threshold, the geometric center of the polygon k anonymous area is used as an anchor point, and the polygon k anonymous area is sent to the server for location query.

When the area value is less than the minimum area threshold, expand the polygon k anonymous area, and use the geometric center of the expanded polygon k anonymous area as an anchor point, and send the enlarged polygon k anonymous area to the server for location lookups.

When the area value is greater than the maximum area threshold, add several false location points in the anonymous area of the polygon k, and add the k-1 adjacent user location points, the query user location point, and the false location points The location point is sent to the server for location lookup.

Among them, the polygon k anonymous area construction process is as follows:

(1a) Set a location point around the query user as the center, and scan to obtain k (including the current query user location) neighboring user location points.

(1b) Select the point with the smallest abscissa value from the location point coordinates. If the smallest abscissa value is not unique, select the point with the smallest ordinate value at the same time, and record this location point as P ₀ .

与y轴负方向的夹角。(1c) Select a direction as the counterclockwise direction, and calculate the vector formed by each remaining point P _x and P ₀ except P ₀

Angle with the negative direction of the y-axis.

(1e) Sort all the points according to the included angle from small to large, and then get an ordered set S={P ₀ ,P ₁ ,P ₂ ,...,P _n-1 }; record the double-ended queue at a certain moment The state of D is: P _t P _t-1 P ₀ ... P _b-1 P _b , traversing each point in S.

(1f) If it is P ₀ , first put P ₀ into the tail of the queue, if it is P ₁ , then enter the tail of the queue, if it is P ₂ , then enter the head of the queue and then enter the tail of the queue.

(1g) Assume traversing to the current node P _i : if P _b-1 P _b P _i can maintain the left-turn characteristic, continue, otherwise P _b leaves the end of the queue, and so on until P _bm-1 P _bm P _i can satisfy the left-turn characteristic Features, P _t enters the tail of the queue.

(1h) Assume traversing to the current node P _i : if P _i P _t P _t-1 can maintain the left-turn characteristic, continue, otherwise P _t will go out of the queue, and so on until P _i P _tn P _tn-1 can satisfy the left-turn characteristic Features, P _i enters the head of the queue.

(1i) Return to the deque D, and the construction of the polygon area is completed.

The k-density value calculation and comparison process is as follows:

(2a) Set the maximum density threshold (ρ _amx ) and the minimum density threshold (ρ _min ) of the k-density in the polygon k-anonymous region.

(2b) Calculate the minimum area threshold (S _min ) and the maximum area threshold (S _max ) according to the density threshold. Calculated as follows:

(2c) Calculate the area value S(Rs) of the anonymous region of polygon k by recursive method, and compare them.

Calculated as follows:

(2d) When S(Rs)<S _min , further expand the area of the anonymous region of polygon k until the area threshold is met.

(2e) When S _min <S(Rs)<S _max , take the geometric center of the polygon k anonymous area as the anchor point, and send the polygon k anonymous area to the LBS server for location query.

(2f) When S(Rs)>S _max , add several false position points in the anonymous area of polygon k until the area threshold is met, and save the obtained false position points into the ordered set S to obtain the false position candidate set _S1 .

The implementation process of the false location privacy protection method is as follows:

(3a) When S(Rs)>S _max , add several false positions in the anonymous area of polygon k.

(3b) Send m locations (including the searched neighbor user location, the added false location, and the current query user location) to the LBS server for query.

(3c) After querying the location data, the LBS server sends k query results to the TTP.

(3d) After TTP refinement, the query result of the current location is returned to the query user.

The process of the privacy protection method for the anonymous location of the whole polygon k is very simple and easy to realize, and the addition of regional anonymity and false location is implemented through TTP in the polygonal region, which is easy to realize in mobile devices. The polygonal anonymous area construction algorithm proposed by the invention can quickly construct an anonymous area matching the terrain features, and improves the anonymous efficiency. According to the k-density parameter value, the area threshold is calculated, and the strategy of combining regional anonymity and fake location is applied according to the area threshold to implement location privacy protection, which effectively improves the location privacy protection effect and query service quality.

Embodiment three

For the above purpose, the present invention also provides a k-anonymous location privacy protection system based on density distribution, as shown in Figure 3, including:

The location point acquiring module 201 is configured to acquire k-1 nearby user location points found around the query user.

The polygonal k-anonymous region construction module 202 is configured to construct a polygonal k-anonymous region by using a fast convex hull generation algorithm according to the k-1 neighboring user location points and the query user location point.

The k-density value calculation module 203 is configured to calculate the k-density value of the k-anonymous area of the polygon.

A comparing module 204, configured to compare the k-density value with a set maximum density threshold and a minimum density threshold respectively.

The first sending module 205 is configured to, when the k-density value is between the maximum density threshold and the minimum density threshold, take the geometric center of the polygon k-anonymous region as an anchor point, and transfer the polygon k-anonymous region Sent to the server for location queries.

The second sending module 206 is configured to expand the polygon k-anonymous area when the k-density value is greater than the maximum density threshold, and take the geometric center of the expanded polygon k-anonymous area as an anchor point to the The enlarged anonymous region of polygon k is sent to the server for location query.

The third sending module 207 is configured to add several false location points in the polygon k-anonymous area when the k-density value is less than the minimum density threshold, and add the k-1 neighboring user location points, The location point of the inquiring user and the fake location point are sent to the server for location query.

The location point acquisition module 201 specifically includes: a location point acquisition unit, which sets a location point around the query user as a midpoint, and scans to obtain k-1 adjacent user location points.

The polygon k anonymous region construction module 202 specifically includes:

The special location point determination unit is used to select a location point with the smallest abscissa among the k-1 adjacent user location points and the query user location point, and determine it as a special location point, and when the special location point is a plurality of , select a position point with the smallest ordinate among the special position points, and determine it as the final special position point.

The special vector calculation unit is used to select a direction as the counterclockwise direction, and calculate the special vector formed by each remaining position point except the special position point and the special position point.

The included angle calculation unit is used to calculate the included angle between each of the special vectors and the negative direction of the y-axis.

The ordered set determination unit is used to sort all the position points according to the angles from small to large to obtain an ordered set.

The polygon k-anonymous area construction unit is used for traversing each location point in the ordered set according to the state of the double-ended queue at the set moment, and constructing the polygon k-anonymous area.

The k-density value calculation module 203 specifically includes:

The area value calculation unit is used to recursively calculate the area value of the polygon k-anonymous area; the k-density value calculation unit is used to calculate the k-density value of the polygon k-anonymous area according to the area value.

Embodiment four

In order to achieve the above object, the present invention also provides a k-anonymous location privacy protection system based on density distribution, including:

The location point obtaining module is used to obtain k-1 nearby user location points found around the query user.

The polygonal k-anonymous region construction module is used to construct a polygonal k-anonymous region by using a fast convex hull generation algorithm according to the k-1 neighboring user location points and the query user location point.

An area value calculation module, configured to calculate the area value of the anonymous area of the polygon k.

A comparing module, configured to compare the area value with a set maximum area threshold and a minimum area threshold respectively.

A first sending module, configured to use the geometric center of the polygon k anonymous area as an anchor point to send the polygon k anonymous area to the server when the area value is between the maximum area threshold and the minimum area threshold for location lookups.

The second sending module is configured to expand the polygon k anonymous area when the area value is less than the minimum area threshold, and use the geometric center of the enlarged polygon k anonymous area as an anchor point to transfer the expanded polygon k to The polygon k anonymous area is sent to the server for location lookup.

The third sending module is configured to add several false location points in the anonymous area of the polygon k when the area value is greater than the maximum area threshold, and send the k-1 adjacent user location points, the query The user location point and the fake location point are sent to the server for location query.

The above-mentioned embodiment will be described below through experiments.

1. Experimental conditions and performance evaluation criteria:

The experiment of the present invention selects Thomas Brinkhoff ("BrinkhoffT. Aframework for generating network-based moving objects [J]. Geoinformatica, 2002, 6 (2): 153-180.") Developed network-based mobile node generator, through as shown in Figure 4 The real map shown generates 1000 data nodes distributed throughout the region. The value of the main parameter k of the experiment is: 1≤k≤100, and the advantages can be further illustrated by the following simulation experiments.

The experimental environment is:

(1) The hardware environment is: Intel(R) Core(TM) i5-3337U CPU, 1.80GHz, memory 4G.

(2) The software environment is: Windows 7 operating system, using MyEclipse development platform, implemented with Java programming language.

2. Experimental content

Experiment 1: Efficiency Test and Analysis

Time Comparison of Different Algorithms to Generate Fake Locations

The polygonal anonymous area generation algorithm proposed by the present invention adopts the table form and the Xie method ("Xie P.A-anonymous Polygon Area Construction Method and Algorithm Based on LBS Privacy Protection [J]. Journal of Information & Computational Science, 2015, 12 (15): 5713-5724 ") to compare the efficiency of the irregular polygon anonymous region generation algorithm, and the comparison results are shown in Table 1.

Table 1 Anonymous area generation time comparison of different algorithms

It can be seen from Table 1 that k ranges from 10 to 100. With the increase of k value, the anonymous domain formation time of the method of the present invention and the polygon division method based on density distribution is increasing, and the growth rate and trend of the two are roughly the same . In the case of the same k value, comparing the time spent by the two algorithms in constructing the anonymous region, the method of the present invention takes much less time to generate the k-anonymous region than the Xie method. It can be seen that compared with the Xie method, the method of the present invention improves the efficiency of anonymity.

Experiment 2: Anonymous area comparison with other methods

A kind of k-anonymous position privacy protection method based on density distribution proposed by the present invention adopts table form and Xie method ("Xie P.A-anonymous Polygon Area Construction Method and Algorithm Basedon LBS Privacy Protecting[J].Journal of Information&Computational Science, 2015, 12(15):5713-5724."), Bamba method ("Bamba B, Liu L, Pesti P, et al.Supporting Anonymous Location Queries in Mobile Environments with Privacy Grid[C]//International Conference on World Wide Web.ACM ,2008:237-246."), Zhao method ("ZhaoZ, Hu H, Zhang F, et al.A k-anonymous algorithm in location privacy protection based on circular zoning[J].Journal of Beijing Jiaotong University, 2013,37 (5):13-18."), Yang method ("Yang Y, Wang R. Rectangular Region K-Anonymity Location Privacy Protection Based on LBS in Augmented Reality [J]. Journal of Nanjing Normal University (Natural science), 2016, 39 (4):44-49.") compared the anonymous region area, and the comparison results are shown in Table 2.

Table 2 Comparison of the anonymous area of different methods (×10 ⁴ m ² )

It can be seen from Table 2 that as the value of k increases, although the areas of several anonymous region division methods increase with the increase of the value of k, the growth speeds are different, which is determined by the geometry of the respective division methods of. In the case of the same k value, the method of the present invention and the Xie method are the smallest, which shows that the query accuracy of the polygonal area anonymous method is higher. As can be seen from Table 2: when the k value is between (0,20), the area of the inventive method is slightly larger than that of the Xie method; when k>20, the area growth trends of the two methods are exactly the same. This is because the method of the present invention sets a density threshold.

Experiment 3: Effectiveness Analysis

The polygonal k-anonymous area generated by the present invention is shown in FIG. 5 , and the polygonal anonymous area proposed by the present invention is compared with the invalid area of the circular and rectangular anonymous area, as shown in FIG. 6 . The area of invalid regions in polygonal anonymous regions is significantly smaller than that of rectangles and circles, proving that polygonal anonymous regions have better privacy and query accuracy.

Experiment 4: Comparison of Entropy

The privacy protection area diagram of the combination of regional anonymity and false location in the present invention is shown in Figure 7. The k-anonymous location privacy protection method based on the density distribution proposed by the present invention is combined with the Random method and the Lu method ("Lu H, Jensen C S,Man L Y.PAD: privacy-area aware,dummy-based location privacy inmobile services[C]//ACM International Workshop on Data Engineering for Wireless and Mobile Access,Mobide 2008,June 13,2008,Vancouver,British Columbia,Canada , Proceedings.DBLP, 2008:16-27.") Girdummy algorithm and Griddummy algorithm compare entropy, and the comparison results are shown in Table 3.

Table 3 Comparison of false position information entropy of different algorithms

As seen from Table 3, along with the increase of the k value, the entropy values of several methods are all increasing, but under the same k value situation, the inventive method entropy value is maximum, proves that the inventive method compares with other three kinds of methods, With the best privacy protection.

Through experimental comparison and analysis, the present invention satisfies better physical dispersion and semantic diversification among location points as much as possible, and at the same time, has higher generation efficiency of false locations, and can effectively improve location service quality.

Each embodiment in this specification is described in a progressive manner, each embodiment focuses on the difference from other embodiments, and the same and similar parts of each embodiment can be referred to each other. As for the system disclosed in the embodiment, since it corresponds to the method disclosed in the embodiment, the description is relatively simple, and for the related information, please refer to the description of the method part.

In this paper, specific examples have been used to illustrate the principle and implementation of the present invention. The description of the above embodiments is only used to help understand the method of the present invention and its core idea; meanwhile, for those of ordinary skill in the art, according to the present invention Thoughts, there will be changes in specific implementation methods and application ranges. In summary, the contents of this specification should not be construed as limiting the present invention.

Claims (8)

1. A privacy protection method for k-anonymous location based on density distribution is characterized by comprising the following steps:

acquiring k-1 neighbor user position points found by the periphery of the query user;

constructing a polygonal k anonymous area by adopting a rapid convex hull generation algorithm according to the k-1 neighbor user position points and the query user position points;

calculating a k-density value of the polygonal k anonymous region;

comparing the k-density values with a set maximum density threshold value and a set minimum density threshold value respectively;

when the k-density value is between the maximum density threshold and the minimum density threshold, taking the geometric center of the polygon k anonymous area as an anchor point, and sending the polygon k anonymous area to a server for position query;

when the k-density value is larger than the maximum density threshold value, expanding the polygon k anonymous area, and sending the expanded polygon k anonymous area to a server for position query by taking the geometric center of the expanded polygon k anonymous area as an anchor point;

when the k-density value is smaller than the minimum density threshold value, adding a plurality of false position points in the k anonymous area of the polygon, and sending the k-1 neighbor user position points, the inquiry user position points and the false position points to a server for position inquiry;

the calculating the k-density value of the k anonymous region of the polygon specifically includes:

calculating the area value of the anonymous region of the polygon k in a recursive mode;

and calculating a k-density value of the k anonymous region of the polygon according to the area value.

2. The method according to claim 1, wherein the obtaining of k-1 neighboring user location points found around a querying user specifically includes:

and setting a position point around the inquiry user as a midpoint, and scanning to obtain k-1 adjacent user position points.

3. The method according to claim 1, wherein the method for privacy protection of k-anonymous locations based on density distribution is configured by using a fast convex hull generation algorithm according to the k-1 neighboring user location points and query user location points, and specifically comprises:

selecting a position point with the smallest abscissa from the k-1 neighbor user position points and the inquiry user position points to be determined as a special position point, and selecting a position point with the smallest ordinate from the special position points to be determined as a final special position point when the special position points are multiple;

selecting a direction as a counterclockwise direction, and calculating a special vector formed by each remaining position point except the special position point and the special position point;

calculating the included angle between each special vector and the negative direction of the y axis;

sequencing all the position points according to the included angles from small to large to obtain an ordered set;

and traversing each position point in the ordered set according to the state of the double-end queue at the set moment to construct a polygon k anonymous region.

4. A privacy protection method for k-anonymous location based on density distribution is characterized by comprising the following steps:

acquiring k-1 neighbor user position points found by the periphery of the query user;

constructing a polygonal k anonymous area by adopting a rapid convex hull generation algorithm according to the k-1 neighbor user position points and the query user position points;

calculating the area value of the k anonymous region of the polygon;

comparing the area values with a set maximum area threshold value and a set minimum area threshold value respectively;

when the area value is between the maximum area threshold and the minimum area threshold, taking the geometric center of the anonymous region of the polygon k as an anchor point, and sending the anonymous region of the polygon k to a server for position query;

when the area value is smaller than the minimum area threshold value, the polygon k anonymous region is expanded, the geometric center of the expanded polygon k anonymous region is used as an anchor point, and the expanded polygon k anonymous region is sent to a server for position query;

when the area value is larger than the maximum area threshold value, adding a plurality of false position points in the anonymous area of the polygon k, and sending the k-1 neighbor user position points, the inquiry user position point and the false position points to a server for position inquiry;

the calculating the area value of the anonymous region of the polygon k specifically includes:

setting a maximum density threshold value and a minimum density threshold value of k-density in a k anonymous area of the polygon;

calculating a minimum area threshold value and a maximum area threshold value according to the density threshold value;

and calculating the area value of the anonymous region of the polygon k by applying a recursive method.

5. A density profile based k-anonymous location privacy preserving system, comprising:

the position point acquisition module is used for acquiring k-1 neighbor user position points found by the periphery of the inquiry user;

the polygon k anonymous region construction module is used for constructing a polygon k anonymous region by adopting a rapid convex hull generation algorithm according to the k-1 neighbor user position points and the query user position points;

a k-density value calculation module for calculating a k-density value of the k anonymous region of the polygon;

the comparison module is used for comparing the k-density value with a set maximum density threshold value and a set minimum density threshold value respectively;

a first sending module, configured to send the k-density anonymous area to a server for location query, with a geometric center of the k-density anonymous area as an anchor point, when the k-density value is between the maximum density threshold and the minimum density threshold;

the second sending module is used for expanding the polygonal k anonymous area when the k-density value is larger than the maximum density threshold value, taking the geometric center of the expanded polygonal k anonymous area as an anchor point, and sending the expanded polygonal k anonymous area to a server for position query;

a third sending module, configured to, when the k-density value is smaller than the minimum density threshold, add several false location points in the anonymous area of the polygon k, and send the k-1 neighboring user location points, the query user location point, and the false location points to a server for location query

The k-density value calculation module specifically comprises:

the area value calculating unit is used for calculating the area value of the anonymous region of the polygon k in a recursive mode;

and the k-density value calculation unit is used for calculating the k-density value of the k anonymous region of the polygon according to the area value.

6. The system according to claim 5, wherein the location point obtaining module specifically includes:

and the position point acquisition unit is used for setting a position point around the inquiry user as a midpoint and scanning to obtain k-1 adjacent user position points.

7. The privacy protection system for k-anonymous locations based on density distribution as claimed in claim 5, wherein the polygonal k-anonymous region construction module specifically comprises:

a special position point determining unit, configured to select a position point with the smallest abscissa from the k-1 neighboring user position points and the query user position points, and determine the position point as a special position point, and when there are multiple special position points, select a position point with the smallest ordinate from the special position points, and determine the position point as a final special position point;

the special vector calculation unit is used for selecting one direction as a counterclockwise direction and calculating a special vector formed by each remaining position point except the special position point and the special position point;

the included angle calculation unit is used for calculating the included angle between each special vector and the negative direction of the y axis;

the ordered set determining unit is used for sequencing all the position points from small to large according to the included angle to obtain an ordered set;

and the polygon k anonymous region construction unit is used for traversing each position point in the ordered set according to the state of the double-ended queue at the set moment to construct the polygon k anonymous region.

8. A density profile based k-anonymous location privacy preserving system, comprising:

the position point acquisition module is used for acquiring k-1 neighbor user position points found by the periphery of the inquiry user;

a polygon k anonymous region construction module, which is used for constructing a polygon k anonymous region by adopting a rapid convex hull generation algorithm according to the k-1 neighbor user position points and the query user position points;

the area value calculation module is used for calculating the area value of the anonymous region of the polygon k;

the comparison module is used for comparing the area value with a set maximum area threshold value and a set minimum area threshold value respectively;

a first sending module, configured to send the anonymous region of polygon k to a server for location query, with a geometric center of the anonymous region of polygon k as an anchor point, when the area value is located between the maximum area threshold and the minimum area threshold;

the second sending module is used for expanding the polygon k anonymous region when the area value is smaller than the minimum area threshold value, taking the geometric center of the expanded polygon k anonymous region as an anchor point, and sending the expanded polygon k anonymous region to a server for position query;

a third sending module, configured to, when the area value is greater than the maximum area threshold, add a plurality of false location points in the anonymous area of the polygon k, and send the k-1 neighboring user location points, the query user location point, and the false location points to a server for location query

The calculating the area value of the anonymous region of the polygon k specifically includes:

setting a maximum density threshold value and a minimum density threshold value of k-density in a k anonymous area of the polygon;

calculating a minimum area threshold value and a maximum area threshold value according to the density threshold value;

and calculating the area value of the anonymous region of the polygon k by applying a recursive method.

Images