# Location Privacy Protection Research Based on Querying Anonymous Region Construction for Smart Campus

Authors: Ruxia Sun; Jinwen Xi; Chunyong Yin; Jin Wang; Gwang-jun Kim
Journal: Mobile Information Systems
 (2018)

---

## Abstract

Along with the rapid development of smart campus, the deployment of novel learning applications for smart campus requires full consideration of information security issues. Location privacy protection is one of the most important issues, which considers the privacy protection and guarantees the quality of service. The existing schemes did not consider the area of the querying regions for location-based service provider (LSP) during the construction of the anonymous regions, which led to the low quality of service. To deal with this problem, the user’s query range was introduced to present a novel anonymous region construction scheme. In the proposal, the anonymous server first generated the original anonymous subregions according to the user’s privacy requirements, and then merged these subregions to construct the anonymity regions submitted to LSP based on the size of corresponding querying regions. The security and experiment analysis show that the proposed scheme not only protects the user’s privacy effectively but also decreases the area of LSP querying regions and the region-constructing time, improving the quality of service for smart campus.


---

## Body

## 1. Introduction

With the development and construction of novel learning applications for smart campus, smart devices and services, smart meters, smart terminals, and the like are widely applied to offer real-time learning feedback to students through continuously monitoring and analyzing the status and activities of students with various devices and platforms. As a large number of smart meters and intelligence appliances are accessed, incorporating various technologies and enabling world-changing learning, the network border further extends to the user side. Security risks on the user side for smart campus will become more and more prominent. Data privacy issues, especially location privacy protection and the quality of service, must be considered [1].Users’ location privacy threats refer to the risks that an attacker can obtain unauthorized access to raw location data by locating a transmitting device and identifying the subject (person) using it. Examples of such risks include spamming users with unwanted advertisements, drawing sensitive inferences from victims’ visits to various locations (e.g., students and teachers’ offices), and learning sensitive information about them (identity, religious and political affiliations, etc.). Hence, location privacy protection for smart campus is becoming a critical issue [2].However, location information is consistently sent to service providers without protection when users query LBSs, allowing location providers to collect location information from all users. The collected location information may expose users to customized advertisement or even be sold to third parties. A worse scenario is location information may be leaked to adversaries with criminal intents. Therefore, many researchers focus on creating location protection algorithms to protect the location privacy of users [3].The European Union’s Information Protection Supervision Organization recently said that high-tech equipment such as smart meters that monitor household energy consumption will pose a huge threat to personal privacy. Smart meters may track personal information, and the vast amounts of information collected can have serious consequences for consumers.With the popularization of mobile devices and location technology, location-based services (LBSs) are widely used in real life, which refers to the user accesses to its designated location information query and entertainment services through the mobile device [4]. However, the location-based service provider (LSP) may also collect and abuse user’s service information while providing the convenient LBS for the user, to illegally obtain the user’s confidential information. The location privacy protection in LBS has attracted the extensive attention of researchers [5–8].In view of the popularization of mobile positioning devices, if these novel learning applications are used in smart campus, the combination of location information and services at different moments in personal privacy may reveal sensitive information such as the user’s behavior habits and work nature. For example, if a mobile user is collected near a hospital, the user may be presumed to have any disease or health condition. If the user’s starting location and ending location are analyzed since the last few days, the user’s home address or work unit, the nature of work, and so on can be speculated. Therefore, the location data of mobile object brings convenience to people and brings about the threat of revealing privacy, which may contain other sensitive information such as home address, personal preference, personality habit, health status, working property, personal income, etc. If this information falls into the hands of normal institutions, it is a tool for information protection, if it falls into the hands of illegal institutions, it will be the weapon of innocent destruction. What we can do is to seek transparency in the use of personal information and to protect user’s location privacy not to be exploited by unscrupulous businesses and illegal agencies.As the most commonly used LBS privacy protection method, the basic idea ofk-anonymity [9] is that when a user sends a LBS query, he will send his real location and querying content to a trusted anonymous server, then the anonymous server will remove the user’s identification information and generate anonymity regions containing other k−1 users for the real location, finally sending them (all the generated anonymity regions and the real location) along with the querying content to the LSP. Compared with other LBS privacy protection methods (such as pseudo location [10], fuzzification [11], differential privacy [12], and cryptography-based methods [13, 14]), k-anonymity has the following advantages: (1) users can get accurate querying results; (2) the user’s cost of computing and communication is small; and (3) this method can confuse the relevance between users and LBS queries. So, k-anonymity is widely used in LBS privacy protection [15, 16].In smart campus, we can query the nearby points of interest. There are many sensors to be addressed for enabling such novel learning applications and services, which aims to enhance the service quality of novel learning applications. Whenk-anonymity method is used to protect the privacy of users in the above query, if the anonymous region generated by the anonymous server is too large, the querying cost of the location-based service provider (LSP) will increase and the service quality deteriorates [17–19]. To solve this problem, the existing methods [20–26] obtain n disjoint anonymous subregions by removing the part that does not contain the users in the regions, to reduce the area of anonymous regions and improve the service quality as shown in Figure 1. However, the quality of service in LBS queries based on k-anonymity is not only related to the size of the anonymous regions but also to the user’s query range. If we use the existing methods to construct the anonymous regions, the quality of service cannot be effectively improved. As shown in Figure 2, when using the existing division methods to divide the initial anonymous region, LSP will repeatedly search the points of interest in some regions, reducing the quality of service, and r is the query radius. This paper also proves this point through experiments.Figure 1
The existing anonymous regions division method. (a) Initial anonymity regions. (b) Anonymity regions after division.
(a)
(b)Figure 2
The querying regions of nearby points of interest. (a) Initial query regions. (b) Query regions after division.
(a)
(b)This paper proposes the LBS privacy protection scheme based on querying anonymous region construction. In which, firstly, the anonymous server generatesk initial anonymous subregions according to the privacy protection requirements of users and merges the anonymous regions according to the corresponding querying regions so that the anonymous regions finally submitted to the LSP can reduce the querying cost of LSP and improve the service quality without reducing the user’s privacy protection level. This is the first k-anonymity privacy protection scheme based on constructing the user querying anonymous regions. The main contributions of this paper are as follows:(1)
Based on the theoretical analysis, it is concluded that the existing anonymous region demarcation method cannot reduce the LSP querying cost and improve the service quality, and we prove it through experiments.(2)
We think that the area of querying regions is the judgment criterion to merge the anonymous subregions and propose an anonymous region construction scheme based on the user’s query range. Security analysis shows that the proposed scheme can effectively protect the users’ location privacy.(3)
A large number of experiments show that this scheme can effectively reduce the querying cost of LSP and improve the service quality, without causing a large computational cost for anonymous servers.


## 2. Related Work

At present, the international research on the privacy protection for smart campus is still in the initial stage. The discussion on the privacy protection focuses more on the risk analysis of exposing personal privacy for the wireless applications and devices. Research in the United States is the leader, which publishes relevant documents on this issue.Privacy laws in the United States do not explicitly address the smart campus and its related data, which is same as the regulations of the existing national Internet of Energy and power transmission [27]. The existing laws and regulations need to be revised to appeal to the smart campus. At the same time, new data items in the Internet of Energy, as well as new ways of using existing data, require more research and public opinion to adapt to current laws or shape new laws.US Internet of Energy Information Security is very concerned about privacy issues. NIST (National Institute of Standards and Technology) released “Guidelines for Smart Grid Cyber Security: Vol. 2, Privacy and Smart Grid” [28] in August 2010 and preliminarily analyzed the privacy issues of smart campus. For location privacy protection, many researchers have done a great deal of work.Grutese appliedk-anonymity to the field of location privacy protection for the first time [4]. The anonymous server divides the area with a quadtree structure and stores the users in the corresponding region in the node. When the user requests a service, a quadtree is retrieved upward from a leaf node corresponding to the user’s location. If the current leaf node does not satisfy the k-anonymity, the parent node will be retrieved until no less than other k−1 users to obtain the anonymous region. However, if the number of users in a leaf node does not satisfy the privacy requirements, it needs to retrieve its parent node, which will result in a four-fold increase in the anonymity area, thereby degrading the user’s service quality. To deal with the above problem, Mokbel et al. [29] improved the anonymous region construction method in [4]. In their scheme, if the current leaf node does not satisfy k-anonymity, firstly its sibling nodes will be retrieved, if it still does not satisfy the user’s privacy requirements, then it retrieves the parent node. To further solve the problem of low quality of service due to the large anonymous region based on the quadtree structure, Li et al. [30] proposed to reduce the area of anonymous regions and improve the service quality by suppressing part of users’ requests and deleting the most distant trails.Subsequently, the researchers proposed Clique Cloak [31] and Hilbert Cloak [32], respectively, to construct the anonymous regions by searching for the nearest users who meet the privacy requirements. In [31], users can customize the privacy protection requirements, but the scheme uses an undirected graph to construct an anonymous region and the cost of the solution is too large. It may happen that the anonymous region has not been successfully constructed but beyond the anonymous period. In [32], the anonymous server maps all users in two-dimensional space to a one-dimensional array according to the Hilbert curve and divides the users into several sets according to the value of k. When a user makes a service request, the anonymous region is constructed by using the user set to which the user belongs.Recently, Jin et al. [2] thought the anonymization server could lead to a new class of attacks called location injection attacks which can successfully violate users’ in-distinguishability (guaranteed by k-anonymity) among a set of users. Therefore, they propose and characterize location injection attacks by presenting a set of attack models and quantify the costs associated with them. Then, they propose and evaluate k-Trustee, which is resilient to location injection attacks and guarantees a low bound on the user’s in-distinguishability. The experimental results show that the proposed cloaking algorithm guaranteeing k-Trustee is effective against various location injection attacks, but the quality of location services is poor and cannot be guaranteed.In all the above solutions, if thek users used to construct the anonymous regions are far away from each other, the anonymous regions may still be too large, and the service quality may be low. Tan et al. [33] were the first ones to apply the idea of regionalization to the construction of anonymous regions, which divided the users in the anonymous regions into separate groups through the Hilbert space filling curve. When a user makes a server request, the anonymous server will use the locations of other users in the group to which it belongs to construct the anonymous region. Subsequently, Li and Zhu [34] also used the method of regionalization to research on reducing the area of anonymous regions and improving the quality of service. The anonymous server firstly constructs an anonymous region containing k users and then removes the anonymous regions that do not contain the users according to relationship among the users’ locations to form multiple anonymous subregions that do not intersect each other.However, the existing anonymous region construction schemes [35–37] ignore the impact of the users’ query range on LBS querying service quality. When using these methods to construct the anonymous regions, the LSP will repeatedly search the points of interest in the partial regions, reducing the service quality.


## 3. Improvedk-Value Location Privacy Protection Method

### 3.1. System Structure

This paper uses the centralized system architecture [38], composed of three parts: user, anonymous server, and LSP. When the user requests a service, the anonymous server blurs the real location of the user into an anonymous region and sends it to the LSP, which contains not only the real user but also other at least k−1 users. In this case, the correct rate that LSP correlates the service query with the right user will be not more than 1/k, which achieves k-anonymity. The system structure is shown in Figure 3.Figure 3
System structure.Assume that there is a secure communication channel between the user and the anonymous server. When the user queries the point of interest nearby, the secure channel is used to send the query requestq=ID,Lx,y,r,POI,p to the trusted anonymous server. In which, ID represents the identity of the user; Lx,y represents the location coordinates of the user; r represents the radius of the user query; POI represents the point of interest of the user query; p represents the privacy protection requirement of the user current query; k represents the anonymous region generated by the anonymous server contains at least other k−1 users; and Amin represents the minimum area of anonymous regions generated by anonymous server.After receiving the user’s request, the trusted anonymous server will determine the identity through authentication and find otherk−1 users to generate anonymous regions that the area is not less than Amin according to the user’s privacy protection requirements p=k,Amin and then send the query request Q=CR,r,POI obtained from the anonymization to the semitrusted LSP. CR represents the anonymous region generated by the anonymous server for the current user making the service query.After receiving the anonymous query request sent by the anonymous server, the LSP will search in the database and return all the query candidate results to the anonymous server. After the anonymous server receives the query result from the LSP, it selects the query result according to the locationLx,y of the user, and finally returns the accurate query result to the user.In this system model, we treat the LSP directly as an attacker. The attacking purposes are as follows: (1) the real location of the user could be identified in the anonymous region sent from the anonymous server and (2) the real user will be speculated from the query request.In addition, in the above model, LBS query quality of service is mainly affected by the following four factors: (1) the time required by the anonymous server to generate anonymous regions; (2) the time that the anonymous server sends the anonymous query request to LSP; (3) the time required by the LSP to retrieve the database for the anonymous query request sent by the anonymous server; and (4) the time it takes for the LSP to send the retrieval result to the anonymous server, and the time required by the anonymous server to finalize the query result. Because the time taken for the LSP to send search results to the anonymous server and the time required for the anonymous server to finalize the query results is affected by the distribution of points of interest, the time required for the anonymous server to send the anonymous query request to the LSP is affected by the transmission bandwidth. Therefore, this paper evaluates the quality of service based onk-anonymous LBS queries only by the time it takes the anonymous server to generate the anonymous regions and the LSP to retrieve the database.


### 3.2. Querying Region of LSP

After receiving the anonymous query requestQ=CR,r,POI sent by the anonymous server, the LSP first calculates the querying region QAR according to the anonymous region CR and the query radius r and then searches the interest point of the user query in the region QAR. The querying regions corresponding to the anonymous regions are as shown in Figure 4.Figure 4
Querying region of LSP.When the anonymous region is a circle, the areaSc of the querying region is (1)Sc=πr˜+r2,where r˜ represents the radius of the circular anonymous region and πr2 is the area of the anonymous region.When the anonymous region is a rectangle, the areaSr of the querying region is (2)Sr=ab+2a+br+πr2,where a, b is the side length of the rectangular anonymous region and ab is the area of the anonymous region CR.It can be learned from the above analysis that after receiving the anonymous query request sent by the anonymous server, the time required by the LSP to retrieve the database is not only related to the size of the anonymous regionCR generated by the anonymous server but also to the radius of the user’s query, in other words, it is determined by the querying region. However, the existing anonymous region partitioning schemes only take the size of the anonymous regions into account, which makes these solutions not effectively improve the LBS query service quality and even further reduces the service quality.


## 3.1. System Structure

This paper uses the centralized system architecture [38], composed of three parts: user, anonymous server, and LSP. When the user requests a service, the anonymous server blurs the real location of the user into an anonymous region and sends it to the LSP, which contains not only the real user but also other at least k−1 users. In this case, the correct rate that LSP correlates the service query with the right user will be not more than 1/k, which achieves k-anonymity. The system structure is shown in Figure 3.Figure 3
System structure.Assume that there is a secure communication channel between the user and the anonymous server. When the user queries the point of interest nearby, the secure channel is used to send the query requestq=ID,Lx,y,r,POI,p to the trusted anonymous server. In which, ID represents the identity of the user; Lx,y represents the location coordinates of the user; r represents the radius of the user query; POI represents the point of interest of the user query; p represents the privacy protection requirement of the user current query; k represents the anonymous region generated by the anonymous server contains at least other k−1 users; and Amin represents the minimum area of anonymous regions generated by anonymous server.After receiving the user’s request, the trusted anonymous server will determine the identity through authentication and find otherk−1 users to generate anonymous regions that the area is not less than Amin according to the user’s privacy protection requirements p=k,Amin and then send the query request Q=CR,r,POI obtained from the anonymization to the semitrusted LSP. CR represents the anonymous region generated by the anonymous server for the current user making the service query.After receiving the anonymous query request sent by the anonymous server, the LSP will search in the database and return all the query candidate results to the anonymous server. After the anonymous server receives the query result from the LSP, it selects the query result according to the locationLx,y of the user, and finally returns the accurate query result to the user.In this system model, we treat the LSP directly as an attacker. The attacking purposes are as follows: (1) the real location of the user could be identified in the anonymous region sent from the anonymous server and (2) the real user will be speculated from the query request.In addition, in the above model, LBS query quality of service is mainly affected by the following four factors: (1) the time required by the anonymous server to generate anonymous regions; (2) the time that the anonymous server sends the anonymous query request to LSP; (3) the time required by the LSP to retrieve the database for the anonymous query request sent by the anonymous server; and (4) the time it takes for the LSP to send the retrieval result to the anonymous server, and the time required by the anonymous server to finalize the query result. Because the time taken for the LSP to send search results to the anonymous server and the time required for the anonymous server to finalize the query results is affected by the distribution of points of interest, the time required for the anonymous server to send the anonymous query request to the LSP is affected by the transmission bandwidth. Therefore, this paper evaluates the quality of service based onk-anonymous LBS queries only by the time it takes the anonymous server to generate the anonymous regions and the LSP to retrieve the database.


## 3.2. Querying Region of LSP

After receiving the anonymous query requestQ=CR,r,POI sent by the anonymous server, the LSP first calculates the querying region QAR according to the anonymous region CR and the query radius r and then searches the interest point of the user query in the region QAR. The querying regions corresponding to the anonymous regions are as shown in Figure 4.Figure 4
Querying region of LSP.When the anonymous region is a circle, the areaSc of the querying region is (1)Sc=πr˜+r2,where r˜ represents the radius of the circular anonymous region and πr2 is the area of the anonymous region.When the anonymous region is a rectangle, the areaSr of the querying region is (2)Sr=ab+2a+br+πr2,where a, b is the side length of the rectangular anonymous region and ab is the area of the anonymous region CR.It can be learned from the above analysis that after receiving the anonymous query request sent by the anonymous server, the time required by the LSP to retrieve the database is not only related to the size of the anonymous regionCR generated by the anonymous server but also to the radius of the user’s query, in other words, it is determined by the querying region. However, the existing anonymous region partitioning schemes only take the size of the anonymous regions into account, which makes these solutions not effectively improve the LBS query service quality and even further reduces the service quality.


## 4. Anonymous Region Construction Scheme Based on Query Range

In this paper, the anonymous server first generatesk initial anonymous subregions according to the privacy protection requirements of the users and constructs the corresponding querying regions by calculating and then merges the anonymous subregions to finally obtain the anonymous subregion set. The solution can reduce the LSP query cost and improve the service quality without lowering the user privacy protection level.


### 4.1. Generation of Initial Anonymous Subregions

After receiving the service request sent by the users, the anonymous server will start to search the otherk−1 users according to the user’s privacy protection requirement p=k,Amin and obtain their location information L1x1,y1,…,Lk−1xk−1,yk−1. Then, the server will generate k disjoint initial anonymous subregions AR0,AR1,…,ARk−1 to satisfy(3)centreARi≠Lixi,yi,areaARi≠Amin,where ARi represents the initial anonymous subregion containing the i-th location Lixi,yi, 0≤i≤k−1; L0x0,y0 represents the location of the user who sent the query request; centreARi represents the central location of initial anonymous subregion ARi; and areaARi represents the area of initial subanonymous region ARi.


### 4.2. Merger of Anonymous Subregions

After generating thek initial anonymous subregions AR0,AR1,…,ARk−1, the anonymous server will calculate the area areaQAR0,areaQAR1,…,areaQARk−1 of the corresponding querying regions QAR0,QAR1,…,QARk−1, respectively, according to the query radius of the user and judge whether the anonymous subregions need to be merged on the basis of the area of the querying regions. In order to effectively reduce the cost, LSP retrieves the points of interest, and after the merger of anonymous subregions, it should ensure(4)Smin=min∑i=0lareaQARi′.That is to say, the sum of the area of each querying regionQARi′ corresponding to each anonymous subregion ARi′ in the anonymous regions CS is the smallest. ARi′ represents the i-th anonymous subregion after the merger of anonymous subregions, 0≤i≤l, 0≤l≤k−1.The merger process of anonymous subregions in the anonymous server is as follows:(1)
Filtering the anonymous subregions that require region consolidationTo ensure that the querying area of the anonymous region is minimized, the anonymous server chooses the anonymous subregionsARi and ARj to merge if the area of querying region is the smallest after the merger of them. The selected anonymous subregions ARi and ARj are needed to satisfy(5)∀i,j∈0,k−1,QARi,j=argminareaQARi,ji≠j,centreQARi,j≠Lixi,yi,centreQARi,j≠Ljxj,yj.(2)
Selecting anonymous subregions to mergeFor the two anonymous subregionsARi and ARj, ARi,j=genARi,ARj represents the new anonymous subregion formed by merging the anonymous subregion ARi with ARj and the corresponding querying region is QARi,j. If areaQARi+areaQARj≤areaQARi,j, it does not merge ARi with ARj. Else it merges ARi with ARj to make the new anonymous subregion ARi,j.(3)
Repeating the process until there is no need to merge anonymous subregions. In this case, the anonymous server will obtain the anonymous set(6)CS=AR0′,AR1′,…,ARl′.In this scheme, when the anonymous server merges the anonymous subregions, it chooses the anonymous regionsARi and ARj to make the area of the querying region the smallest after merging. Therefore, after every merger of the anonymous subregions, the area of the new querying region ARi,j is the smallest, which ensures that the querying area of the final anonymous region set CS is the smallest.In this paper, the locations ofk users are used as the input to generate the corresponding anonymous subregions AR0,AR1,…,ARk−1 and merge them to obtain the final anonymous subregion set CS, which is submitted to the LSP (Algorithm 1).Algorithm 1:Anonymous subregion generation algorithm based on querying region division.
Input:k pieces of locations L0x0,y0,L1x1,y1,…,Lk−1xk−1,yk−1; the query radius r; the privacy requirement Amin;
Output: anonymous region setCS;
(1)
fori=0 to k−1 do
(2)
ARi←GenLixi,yi;
(3)
centreARi≠Lixi,yi,AreaARi=Amin;
(4)
CS←ARi;
(5)
QARi←GenARi,r, calculating AreaQARi;
(6)
end for
(7)
fori,j=0 to ij and i≠j do
(8)
ARi,j←GenARi,ARj;
(9)
CR←ARi,j;
(10)
QARi,j←GenARi,j,r, calculating AreaQARi,j;
(11)
ifAreaQARi+AreaQARj≤AreaQARi,j then
(12)
CS←CS\ARi,j;
(13)
end if
(14)
ifAreaQARi+AreaQARj>AreaQARi,j,QARi,j=argminAreaQARi,ji≠j, centreQARi,j≠Lixi,yiandcentreQARi,j≠Ljxj,yj then
(15)
CS←CS\ARi,ARj;
(16)
end if
(17)
end for
(18)
returnCS


## 4.1. Generation of Initial Anonymous Subregions

After receiving the service request sent by the users, the anonymous server will start to search the otherk−1 users according to the user’s privacy protection requirement p=k,Amin and obtain their location information L1x1,y1,…,Lk−1xk−1,yk−1. Then, the server will generate k disjoint initial anonymous subregions AR0,AR1,…,ARk−1 to satisfy(3)centreARi≠Lixi,yi,areaARi≠Amin,where ARi represents the initial anonymous subregion containing the i-th location Lixi,yi, 0≤i≤k−1; L0x0,y0 represents the location of the user who sent the query request; centreARi represents the central location of initial anonymous subregion ARi; and areaARi represents the area of initial subanonymous region ARi.


## 4.2. Merger of Anonymous Subregions

After generating thek initial anonymous subregions AR0,AR1,…,ARk−1, the anonymous server will calculate the area areaQAR0,areaQAR1,…,areaQARk−1 of the corresponding querying regions QAR0,QAR1,…,QARk−1, respectively, according to the query radius of the user and judge whether the anonymous subregions need to be merged on the basis of the area of the querying regions. In order to effectively reduce the cost, LSP retrieves the points of interest, and after the merger of anonymous subregions, it should ensure(4)Smin=min∑i=0lareaQARi′.That is to say, the sum of the area of each querying regionQARi′ corresponding to each anonymous subregion ARi′ in the anonymous regions CS is the smallest. ARi′ represents the i-th anonymous subregion after the merger of anonymous subregions, 0≤i≤l, 0≤l≤k−1.The merger process of anonymous subregions in the anonymous server is as follows:(1)
Filtering the anonymous subregions that require region consolidationTo ensure that the querying area of the anonymous region is minimized, the anonymous server chooses the anonymous subregionsARi and ARj to merge if the area of querying region is the smallest after the merger of them. The selected anonymous subregions ARi and ARj are needed to satisfy(5)∀i,j∈0,k−1,QARi,j=argminareaQARi,ji≠j,centreQARi,j≠Lixi,yi,centreQARi,j≠Ljxj,yj.(2)
Selecting anonymous subregions to mergeFor the two anonymous subregionsARi and ARj, ARi,j=genARi,ARj represents the new anonymous subregion formed by merging the anonymous subregion ARi with ARj and the corresponding querying region is QARi,j. If areaQARi+areaQARj≤areaQARi,j, it does not merge ARi with ARj. Else it merges ARi with ARj to make the new anonymous subregion ARi,j.(3)
Repeating the process until there is no need to merge anonymous subregions. In this case, the anonymous server will obtain the anonymous set(6)CS=AR0′,AR1′,…,ARl′.In this scheme, when the anonymous server merges the anonymous subregions, it chooses the anonymous regionsARi and ARj to make the area of the querying region the smallest after merging. Therefore, after every merger of the anonymous subregions, the area of the new querying region ARi,j is the smallest, which ensures that the querying area of the final anonymous region set CS is the smallest.In this paper, the locations ofk users are used as the input to generate the corresponding anonymous subregions AR0,AR1,…,ARk−1 and merge them to obtain the final anonymous subregion set CS, which is submitted to the LSP (Algorithm 1).Algorithm 1:Anonymous subregion generation algorithm based on querying region division.
Input:k pieces of locations L0x0,y0,L1x1,y1,…,Lk−1xk−1,yk−1; the query radius r; the privacy requirement Amin;
Output: anonymous region setCS;
(1)
fori=0 to k−1 do
(2)
ARi←GenLixi,yi;
(3)
centreARi≠Lixi,yi,AreaARi=Amin;
(4)
CS←ARi;
(5)
QARi←GenARi,r, calculating AreaQARi;
(6)
end for
(7)
fori,j=0 to ij and i≠j do
(8)
ARi,j←GenARi,ARj;
(9)
CR←ARi,j;
(10)
QARi,j←GenARi,j,r, calculating AreaQARi,j;
(11)
ifAreaQARi+AreaQARj≤AreaQARi,j then
(12)
CS←CS\ARi,j;
(13)
end if
(14)
ifAreaQARi+AreaQARj>AreaQARi,j,QARi,j=argminAreaQARi,ji≠j, centreQARi,j≠Lixi,yiandcentreQARi,j≠Ljxj,yj then
(15)
CS←CS\ARi,ARj;
(16)
end if
(17)
end for
(18)
returnCS


## 5. Scheme Analysis and Experimental Results

### 5.1. Analysis of Security

In our scheme, we construct the disjoint initial anonymous subregionsAR0,AR1,…,ARk−1 that the area of each initial anonymous subregion is less than Amin according to k real locations L0x0,y0,L1x1,y1,…,Lk−1xk−1,yk−1 and ensure every real location is not located in the center of the initial anonymous sub-region for smart campus, that is, centreARi≠Lixi,yi. If the anonymous server directly sends the k initial anonymous subregions to the LSP, which cannot correctly identify the real location Lixi,yi of the user from the anonymous region ARi. If the anonymous server uses the proposed scheme to merge the anonymous subregions and sends the final anonymous region set CS to the LSP, the area of every anonymous subregion ARi satisfies areaARi=Amin, so the area of every merged anonymous subregion ARi′ will satisfy no less than Amin and for any location Lixi,yi∈ARi′, and it satisfies that the center of ARi′ is not Lixi,yi. In addition, the user’s identity has been removed from the anonymous query request sent by the anonymous server. Though the LSP received the anonymous query request Q=CR,r,POI, it is unable to know the user who made the service request. Therefore, this scheme proposed in this paper can effectively protect the privacy of users.


### 5.2. Analysis of Computational Complexity

When the anonymous server receives the service query request sent by the user and uses this solution proposed in this paper to generate an anonymous region for it, it firstly generatesk initial anonymous subregions according to the privacy protection requirement of the user. The computational complexity of generating the initial anonymous subregions is Ok. When the anonymous server determines whether any two anonymous subregions ARi and ARj need to be merged, it first needs to use the anonymous subregions ARi and ARj to generate a new anonymous region ARi,j. In this case, the number of new anonymous regions that need to be generated is Ck2=kk−1/2, and the computational complexity is Ok2. Subsequently, the anonymous server will calculate the area of the querying region corresponding to each newly generated anonymous region ARi,j, which requires kk−1/2 times of computation, and the computational complexity is Ok2. Finally, comparing the area of the querying region ARi and ARj with that of the newly generated anonymous region ARi,j to determine whether the both initial anonymous subregions are needed to merge, which requires kk−1/2 times of computation, and the computational complexity is Ok2. So the computational complexity of merging all the initial anonymous subregions is Ok2+Ok2+Ok2=Ok2. After obtaining the new anonymous region ARi,j merged from the initial anonymous subregions ARi and ARj, it also needs to judge whether the new anonymous subregions need to be merged again with other anonymous subregions. During the merging process of the anonymous subregions, the best case is that any one of k initial anonymous subregions does not need to be merged with others. In this case, the computational complexity required to implement this solution is(7)Obest=Ok+Ok2=Ok2.In contrast, the worst case is that any one ofk initial anonymous subregions needs to be merged with others and finally merged to an anonymous region. In this case, it needs to repeat the above anonymous region merger and judge k−1 time, and the computational complexity required to implement this solution is(8)Oworst=Ok+Ok−1k2=Ok3.


### 5.3. Experimental Results and Analysis

In this paper, a network-based generator of moving objects (NGMO) [39] is used to generate the experimental data. This generator is often used in the existing research of LBS privacy protection, which is based on the Oldenburg map of German city and simulates the location information of users by setting parameters such as the number of moving objects. We set the privacy requirement as k, the generated initial anonymous subregion is rectangular, and its area satisfies Amin=160000m2. At the same time, to assess the LSP query cost, this paper simulates 500000 points of interest, such as restaurants, hotels, hospitals, parking lots, and so on. In addition, R-tree structure is used to access these points of interest because R-tree is the best-balanced tree for storing high-dimensional data, which can effectively improve the searching efficiency in high-dimensional space [40]. The experimental environment is Intel (R) Core(TM) i7-6700HQ CPU @ 2.60 GHz, 20.0 GB RAM. The algorithms are programmed by Python and the programs run in the Windows 10 Enterprise. The experimental data sets are shown in Table 1.Table 1
Experimental data sets.
Status
Id
Reward number
Type id
Time stamp
X-axis
Y-axis
Speed
New point
105
1
0
0
4229.0
16335.0
298.0
New point
106
1
0
0
19065.0
9922.0
132.0
New point
107
1
0
0
3670.0
20230.0
298.0
New point
108
1
1
0
5565.0
18047.0
298.0
New point
109
1
0
0
10567.0
17947.0
298.0
Point
109
2
0
1
10275.4
17638.7
672.0
Point
108
2
1
1
5487.7
17812.9
504.5


#### 5.3.1. Problems Existing in Real Anonymity Region Constructions Schemes

To prove that the existing anonymous region construction scheme cannot effectively improve the service quality of LBS query, this paper selects Casper scheme [29] and Fragment scheme [34], respectively, to search nearby points of interest. As the most commonly used anonymous region construction method, the Casper method generates at least an anonymous region that contains all k users. Fragment is to deal with the anonymous region generated by the Casper scheme to reduce the area of the anonymous regions by removing the part that does not contain the user’s location according to the location of the user in the anonymous region.This paper compares the time required to generate the anonymous region, the area of the anonymous region, and the area of the querying region of LSP in the above two schemes to prove that the existing anonymous region division methods will further reduce the quality of service when there is an overlap querying region between both anonymous regions. In this part of the experiment, this paper sets the user’s query radiusr = 500 m. The experimental results are shown in Figures 5 and 6.Figure 5
Computational cost of anonymity server. (a) The area of anonymous regions. (b) The query cost of LSP.
(a)
(b)Figure 6
The area of querying regions and query cost of LSP. (a) The area of querying regions. (b) The query cost of LSP.
(a)
(b)As is shown in Figure5, compared with the Casper scheme, the Fragment scheme uses a region division method to reduce the area of anonymous regions, for example, when k=25, the area of anonymous regions generated by the Casper scheme is 5.71×107m2, and the time of generating the anonymous regions is 180.275ms. The area of anonymous regions generated by the Fragment scheme is 3.41×107m2, and the time of generating the anonymous regions is 175.331ms. However, in the Casper and Fragment schemes, the time required for the LSP to query the points of interest is, respectively, 9.940s (the corresponding area of querying regions is 7.234×107m2) and 10.501s (the corresponding area of querying regions is 7.329×107m2). Therefore, when the anonymous server adopts the Casper and Fragment schemes to generate the anonymous regions, the cost time when the user obtains the accurate query results (without considering the transmission delay) is 9.940+0.180=10.120s and 10.501+0.175=10.676s, respectively. When the anonymous server adopts the existing region division schemes to construct the anonymous regions, the time for the user to obtain the query result increases instead.


#### 5.3.2. Analysis of Our Scheme’s Effectiveness

In this section, we compare our proposed scheme with Casper scheme and prove that the proposed scheme can effectively reduce the query cost of the LSP and improve the query service quality in the smart campus. The experimental results are shown in Figures5 and 6.As is shown in Figures5 and 6, compared with the existing scheme, the anonymous regions and querying regions generated by our proposed scheme significantly reduced and the same as the time required for LSP to query the points of interest. For example, when k=25, the area of anonymous regions generated by our scheme is 5.89×106m2, which decreases by 2.80×107m2 compared to the Casper scheme, and the time to generate the anonymous regions increases from 180.275ms to 221.034ms, increasing by 40.759ms. The area of querying regions generated by our scheme is 2.493×107m2, which decreases by 4.741×107m2 compared to the Casper scheme, and the time for query processing increases from 9.940s to 1.961s. Therefore, compared with the Casper scheme, our scheme can effectively improve LBS query service quality.As can been seen from Figures5(b) and 6(b), compared with the Casper scheme, as the value of k increases, our scheme needs more extra time to construct the anonymous regions (the time difference between our scheme and the Casper scheme), but less time for query processing. At the same time, the time that the anonymous server generates the anonymous regions is in the milliseconds level, which has little impact on the user delay. The time of query processing is in the second level, which greatly affects the user delay. The query processing time of the LSP determines the user’s service quality to a great extent.The paper also has made a brief analysis about the influence of the user-specified query radius on the scheme. The experimental results are shown in Figures7(a) and 7(b). As the user query radius r increases, the number of anonymous subregions that need to be merged also increases, increasing the computational cost of the anonymous server. As a result, the area of querying regions and the time of LSP query processing also increase, which obviously influences the LBS query service quality.Figure 7
The impact of user query radius on the scheme of this paper. (a) The time of generating anonymous regions. (b) The time of LSP query processing.
(a)
(b)In summary, the proposed scheme not only reduces the computational cost of the anonymous server but also significantly reduces the area of the LSP querying regions and its query time, which effectively improves the LSB query service quality for smart campus.


## 5.1. Analysis of Security

In our scheme, we construct the disjoint initial anonymous subregionsAR0,AR1,…,ARk−1 that the area of each initial anonymous subregion is less than Amin according to k real locations L0x0,y0,L1x1,y1,…,Lk−1xk−1,yk−1 and ensure every real location is not located in the center of the initial anonymous sub-region for smart campus, that is, centreARi≠Lixi,yi. If the anonymous server directly sends the k initial anonymous subregions to the LSP, which cannot correctly identify the real location Lixi,yi of the user from the anonymous region ARi. If the anonymous server uses the proposed scheme to merge the anonymous subregions and sends the final anonymous region set CS to the LSP, the area of every anonymous subregion ARi satisfies areaARi=Amin, so the area of every merged anonymous subregion ARi′ will satisfy no less than Amin and for any location Lixi,yi∈ARi′, and it satisfies that the center of ARi′ is not Lixi,yi. In addition, the user’s identity has been removed from the anonymous query request sent by the anonymous server. Though the LSP received the anonymous query request Q=CR,r,POI, it is unable to know the user who made the service request. Therefore, this scheme proposed in this paper can effectively protect the privacy of users.


## 5.2. Analysis of Computational Complexity

When the anonymous server receives the service query request sent by the user and uses this solution proposed in this paper to generate an anonymous region for it, it firstly generatesk initial anonymous subregions according to the privacy protection requirement of the user. The computational complexity of generating the initial anonymous subregions is Ok. When the anonymous server determines whether any two anonymous subregions ARi and ARj need to be merged, it first needs to use the anonymous subregions ARi and ARj to generate a new anonymous region ARi,j. In this case, the number of new anonymous regions that need to be generated is Ck2=kk−1/2, and the computational complexity is Ok2. Subsequently, the anonymous server will calculate the area of the querying region corresponding to each newly generated anonymous region ARi,j, which requires kk−1/2 times of computation, and the computational complexity is Ok2. Finally, comparing the area of the querying region ARi and ARj with that of the newly generated anonymous region ARi,j to determine whether the both initial anonymous subregions are needed to merge, which requires kk−1/2 times of computation, and the computational complexity is Ok2. So the computational complexity of merging all the initial anonymous subregions is Ok2+Ok2+Ok2=Ok2. After obtaining the new anonymous region ARi,j merged from the initial anonymous subregions ARi and ARj, it also needs to judge whether the new anonymous subregions need to be merged again with other anonymous subregions. During the merging process of the anonymous subregions, the best case is that any one of k initial anonymous subregions does not need to be merged with others. In this case, the computational complexity required to implement this solution is(7)Obest=Ok+Ok2=Ok2.In contrast, the worst case is that any one ofk initial anonymous subregions needs to be merged with others and finally merged to an anonymous region. In this case, it needs to repeat the above anonymous region merger and judge k−1 time, and the computational complexity required to implement this solution is(8)Oworst=Ok+Ok−1k2=Ok3.


## 5.3. Experimental Results and Analysis

In this paper, a network-based generator of moving objects (NGMO) [39] is used to generate the experimental data. This generator is often used in the existing research of LBS privacy protection, which is based on the Oldenburg map of German city and simulates the location information of users by setting parameters such as the number of moving objects. We set the privacy requirement as k, the generated initial anonymous subregion is rectangular, and its area satisfies Amin=160000m2. At the same time, to assess the LSP query cost, this paper simulates 500000 points of interest, such as restaurants, hotels, hospitals, parking lots, and so on. In addition, R-tree structure is used to access these points of interest because R-tree is the best-balanced tree for storing high-dimensional data, which can effectively improve the searching efficiency in high-dimensional space [40]. The experimental environment is Intel (R) Core(TM) i7-6700HQ CPU @ 2.60 GHz, 20.0 GB RAM. The algorithms are programmed by Python and the programs run in the Windows 10 Enterprise. The experimental data sets are shown in Table 1.Table 1
Experimental data sets.
Status
Id
Reward number
Type id
Time stamp
X-axis
Y-axis
Speed
New point
105
1
0
0
4229.0
16335.0
298.0
New point
106
1
0
0
19065.0
9922.0
132.0
New point
107
1
0
0
3670.0
20230.0
298.0
New point
108
1
1
0
5565.0
18047.0
298.0
New point
109
1
0
0
10567.0
17947.0
298.0
Point
109
2
0
1
10275.4
17638.7
672.0
Point
108
2
1
1
5487.7
17812.9
504.5


### 5.3.1. Problems Existing in Real Anonymity Region Constructions Schemes

To prove that the existing anonymous region construction scheme cannot effectively improve the service quality of LBS query, this paper selects Casper scheme [29] and Fragment scheme [34], respectively, to search nearby points of interest. As the most commonly used anonymous region construction method, the Casper method generates at least an anonymous region that contains all k users. Fragment is to deal with the anonymous region generated by the Casper scheme to reduce the area of the anonymous regions by removing the part that does not contain the user’s location according to the location of the user in the anonymous region.This paper compares the time required to generate the anonymous region, the area of the anonymous region, and the area of the querying region of LSP in the above two schemes to prove that the existing anonymous region division methods will further reduce the quality of service when there is an overlap querying region between both anonymous regions. In this part of the experiment, this paper sets the user’s query radiusr = 500 m. The experimental results are shown in Figures 5 and 6.Figure 5
Computational cost of anonymity server. (a) The area of anonymous regions. (b) The query cost of LSP.
(a)
(b)Figure 6
The area of querying regions and query cost of LSP. (a) The area of querying regions. (b) The query cost of LSP.
(a)
(b)As is shown in Figure5, compared with the Casper scheme, the Fragment scheme uses a region division method to reduce the area of anonymous regions, for example, when k=25, the area of anonymous regions generated by the Casper scheme is 5.71×107m2, and the time of generating the anonymous regions is 180.275ms. The area of anonymous regions generated by the Fragment scheme is 3.41×107m2, and the time of generating the anonymous regions is 175.331ms. However, in the Casper and Fragment schemes, the time required for the LSP to query the points of interest is, respectively, 9.940s (the corresponding area of querying regions is 7.234×107m2) and 10.501s (the corresponding area of querying regions is 7.329×107m2). Therefore, when the anonymous server adopts the Casper and Fragment schemes to generate the anonymous regions, the cost time when the user obtains the accurate query results (without considering the transmission delay) is 9.940+0.180=10.120s and 10.501+0.175=10.676s, respectively. When the anonymous server adopts the existing region division schemes to construct the anonymous regions, the time for the user to obtain the query result increases instead.


### 5.3.2. Analysis of Our Scheme’s Effectiveness

In this section, we compare our proposed scheme with Casper scheme and prove that the proposed scheme can effectively reduce the query cost of the LSP and improve the query service quality in the smart campus. The experimental results are shown in Figures5 and 6.As is shown in Figures5 and 6, compared with the existing scheme, the anonymous regions and querying regions generated by our proposed scheme significantly reduced and the same as the time required for LSP to query the points of interest. For example, when k=25, the area of anonymous regions generated by our scheme is 5.89×106m2, which decreases by 2.80×107m2 compared to the Casper scheme, and the time to generate the anonymous regions increases from 180.275ms to 221.034ms, increasing by 40.759ms. The area of querying regions generated by our scheme is 2.493×107m2, which decreases by 4.741×107m2 compared to the Casper scheme, and the time for query processing increases from 9.940s to 1.961s. Therefore, compared with the Casper scheme, our scheme can effectively improve LBS query service quality.As can been seen from Figures5(b) and 6(b), compared with the Casper scheme, as the value of k increases, our scheme needs more extra time to construct the anonymous regions (the time difference between our scheme and the Casper scheme), but less time for query processing. At the same time, the time that the anonymous server generates the anonymous regions is in the milliseconds level, which has little impact on the user delay. The time of query processing is in the second level, which greatly affects the user delay. The query processing time of the LSP determines the user’s service quality to a great extent.The paper also has made a brief analysis about the influence of the user-specified query radius on the scheme. The experimental results are shown in Figures7(a) and 7(b). As the user query radius r increases, the number of anonymous subregions that need to be merged also increases, increasing the computational cost of the anonymous server. As a result, the area of querying regions and the time of LSP query processing also increase, which obviously influences the LBS query service quality.Figure 7
The impact of user query radius on the scheme of this paper. (a) The time of generating anonymous regions. (b) The time of LSP query processing.
(a)
(b)In summary, the proposed scheme not only reduces the computational cost of the anonymous server but also significantly reduces the area of the LSP querying regions and its query time, which effectively improves the LSB query service quality for smart campus.


## 5.3.1. Problems Existing in Real Anonymity Region Constructions Schemes

To prove that the existing anonymous region construction scheme cannot effectively improve the service quality of LBS query, this paper selects Casper scheme [29] and Fragment scheme [34], respectively, to search nearby points of interest. As the most commonly used anonymous region construction method, the Casper method generates at least an anonymous region that contains all k users. Fragment is to deal with the anonymous region generated by the Casper scheme to reduce the area of the anonymous regions by removing the part that does not contain the user’s location according to the location of the user in the anonymous region.This paper compares the time required to generate the anonymous region, the area of the anonymous region, and the area of the querying region of LSP in the above two schemes to prove that the existing anonymous region division methods will further reduce the quality of service when there is an overlap querying region between both anonymous regions. In this part of the experiment, this paper sets the user’s query radiusr = 500 m. The experimental results are shown in Figures 5 and 6.Figure 5
Computational cost of anonymity server. (a) The area of anonymous regions. (b) The query cost of LSP.
(a)
(b)Figure 6
The area of querying regions and query cost of LSP. (a) The area of querying regions. (b) The query cost of LSP.
(a)
(b)As is shown in Figure5, compared with the Casper scheme, the Fragment scheme uses a region division method to reduce the area of anonymous regions, for example, when k=25, the area of anonymous regions generated by the Casper scheme is 5.71×107m2, and the time of generating the anonymous regions is 180.275ms. The area of anonymous regions generated by the Fragment scheme is 3.41×107m2, and the time of generating the anonymous regions is 175.331ms. However, in the Casper and Fragment schemes, the time required for the LSP to query the points of interest is, respectively, 9.940s (the corresponding area of querying regions is 7.234×107m2) and 10.501s (the corresponding area of querying regions is 7.329×107m2). Therefore, when the anonymous server adopts the Casper and Fragment schemes to generate the anonymous regions, the cost time when the user obtains the accurate query results (without considering the transmission delay) is 9.940+0.180=10.120s and 10.501+0.175=10.676s, respectively. When the anonymous server adopts the existing region division schemes to construct the anonymous regions, the time for the user to obtain the query result increases instead.


## 5.3.2. Analysis of Our Scheme’s Effectiveness

In this section, we compare our proposed scheme with Casper scheme and prove that the proposed scheme can effectively reduce the query cost of the LSP and improve the query service quality in the smart campus. The experimental results are shown in Figures5 and 6.As is shown in Figures5 and 6, compared with the existing scheme, the anonymous regions and querying regions generated by our proposed scheme significantly reduced and the same as the time required for LSP to query the points of interest. For example, when k=25, the area of anonymous regions generated by our scheme is 5.89×106m2, which decreases by 2.80×107m2 compared to the Casper scheme, and the time to generate the anonymous regions increases from 180.275ms to 221.034ms, increasing by 40.759ms. The area of querying regions generated by our scheme is 2.493×107m2, which decreases by 4.741×107m2 compared to the Casper scheme, and the time for query processing increases from 9.940s to 1.961s. Therefore, compared with the Casper scheme, our scheme can effectively improve LBS query service quality.As can been seen from Figures5(b) and 6(b), compared with the Casper scheme, as the value of k increases, our scheme needs more extra time to construct the anonymous regions (the time difference between our scheme and the Casper scheme), but less time for query processing. At the same time, the time that the anonymous server generates the anonymous regions is in the milliseconds level, which has little impact on the user delay. The time of query processing is in the second level, which greatly affects the user delay. The query processing time of the LSP determines the user’s service quality to a great extent.The paper also has made a brief analysis about the influence of the user-specified query radius on the scheme. The experimental results are shown in Figures7(a) and 7(b). As the user query radius r increases, the number of anonymous subregions that need to be merged also increases, increasing the computational cost of the anonymous server. As a result, the area of querying regions and the time of LSP query processing also increase, which obviously influences the LBS query service quality.Figure 7
The impact of user query radius on the scheme of this paper. (a) The time of generating anonymous regions. (b) The time of LSP query processing.
(a)
(b)In summary, the proposed scheme not only reduces the computational cost of the anonymous server but also significantly reduces the area of the LSP querying regions and its query time, which effectively improves the LSB query service quality for smart campus.


## 6. Conclusions

In this paper, we merged novel learning applications technology with mobile technology to research on the location privacy protection technology for smart campus and proposed a new location privacy protection scheme based on querying anonymous region construction which faces the challenges to achieve the higher quality of smart campus services. Through theoretical analysis and experimental results in the location privacy protection based onk-anonymity, this paper proves that the existing anonymous region construction schemes based on the idea of region division cannot effectively improve the LBS query service quality. The root cause of this problem is that the service quality of sensors in the smart campus is not only related to the anonymous area size constructed by the anonymous server but also to the range of the LSP query. To deal with the above problem, this paper introduces the user’s query range into the construction process of the anonymous region. The anonymous server first generates k initial anonymous subregions based on the user’s privacy protection requirement, and then the anonymous subregions will be judged if it needs to be merged based on the size of the querying region. The scheme analysis shows that our proposed scheme can effectively reduce the query cost of LSP and improve the service quality while protecting user’s location privacy for smart campus.



---

*Source: 3682382-2018-09-16.xml*