CN102970652A - Query sensing position privacy protection system facing to road network - Google Patents

Abstract

Translated fromChinese

本发明公开了属于位置服务中的一种面向路网的查询感知的位置隐私保护系统，该系统通过移动用户提出匿名请求；匿名服务器中的匿名模块对请求进行匿名，产生匿名路段集合，然后把匿名路段集合以及与之对应的查询集合发送给位置服务器。位置服务器处理请求并把查询的候选结果集合发送给匿名服务器，匿名服务器的查询处理模块对收到的候选结果集合进行过滤，并且把过滤后最终结果发送给相应的用户。本发明系统结合路网拓扑结构和用户查询特征生成匿名区域，并允许用户个性化定制隐私保护参数。匿名模块运行在匿名服务器中；所述的匿名模块根据用户的隐私保护参数，利用本发明的匿名方法进行计算。该系统能保证匿名路段集合在查询有效期内被其包含的所有移动用户共享，对位置服务中提出查询用户的位置隐私进行有效的保护。

The invention discloses a road network-oriented query-aware location privacy protection system belonging to the location service. The system makes an anonymous request through a mobile user; the anonymous module in the anonymous server anonymizes the request, generates an anonymous road section set, and then The set of anonymous road segments and the set of queries corresponding thereto are sent to the location server. The location server processes the request and sends the query candidate result set to the anonymous server. The query processing module of the anonymous server filters the received candidate result set and sends the filtered final result to the corresponding user. The system of the invention generates an anonymous area in combination with the topological structure of the road network and user query features, and allows the user to personalize and customize privacy protection parameters. The anonymous module runs in the anonymous server; said anonymous module uses the anonymous method of the present invention to perform calculations according to the user's privacy protection parameters. The system can ensure that the collection of anonymous road sections is shared by all mobile users included within the validity period of the query, and effectively protects the location privacy of the querying user in the location service.

Description

Translated fromChinese

一种面向路网的查询感知的位置隐私保护系统A query-aware location privacy protection system for road network

技术领域technical field

本发明涉及位置服务隐私保护技术，更特别地说，是指一种对移动用户的位置和查询内容进行隐私保护的、基于路网的位置隐私保护系统。The present invention relates to location service privacy protection technology, more particularly, refers to a road network-based location privacy protection system for privacy protection of mobile user's location and query content.

背景技术Background technique

无线通信和移动数据库的快速发展,使得移动用户（mobilesubscriber）可以方便的享受基于位置的服务(LBS)。参见图1所示，移动用户10向位置服务提供商20（或者称为位置服务器）发出查询请求信息10A，位置服务提供商20收到所述查询请求信息10A后，会根据坐标位置(X,Y)和请求内容R_con进行结果查询，并将查询结果信息10B返回给移动用户10。查询请求信息10A中至少包括有移动用户的请求内容R_con和移动用户当前的坐标位置(X,Y)。坐标位置(X,Y)是基于移动终端定位的位置，一般可以是采用GPS、WIFI、AP等进行的位置定位；X表示经度、Y表示纬度。With the rapid development of wireless communication and mobile database, mobile subscribers can enjoy location-based services (LBS) conveniently. 1, themobile user 10 sends a query request message 10A to a location service provider 20 (or called a location server). Y) and the request content R_con carry out the result query, and return thequery result information 10B to themobile user 10 . The query request information 10A includes at least the request content R_con of the mobile user and the current coordinate position (X, Y) of the mobile user. The coordinate position (X, Y) is the position based on the positioning of the mobile terminal, and generally can be position positioning by using GPS, WIFI, AP, etc.; X indicates longitude and Y indicates latitude.

当多个移动用户10在公路上移动时，基于移动平台形成自组织无线通信网络。为了获得高质量的位置服务（即依据查询结果信息10B进行匹配位置指引），移动用户10需要向位置服务提供商20（也称为位置服务器）提供自身的准确位置（即X,Y）。但是，如果位置服务提供商20不可信，那么移动用户10发出的查询请求信息10A中的位置信息(X,Y)将会被泄露或者遭到非法使用。因此，基于位置的服务给移动用户10的位置信息(X,Y)隐私保护带来了极大的挑战。特别是当移动用户10沿着公路上的道路（Road）移动时，目前常用的基于欧式空间的位置匿名方法往往不能有效保护移动用户的位置信息(X,Y)的隐私（简称为位置隐私（Location Privacy））。这是因为这些方法仅把移动用户10的位置信息(X,Y)模糊化成一个区域（简称为模糊区域），并且把模糊区域作为衡量位置隐私保护程度的指标。而在路网拓扑中，一个很大的模糊区域可能只包含少量甚至一条路段，这会威胁到移动用户的位置隐私。When multiplemobile users 10 move on the road, an ad-hoc wireless communication network is formed based on the mobile platform. In order to obtain high-quality location services (that is, match location guidance based on thequery result information 10B), themobile user 10 needs to provide its own accurate location (ie, X, Y) to the location service provider 20 (also called a location server). However, if thelocation service provider 20 is untrustworthy, the location information (X, Y) in the query request information 10A sent by themobile user 10 will be leaked or used illegally. Therefore, the location-based service brings a great challenge to the privacy protection of the location information (X, Y) of themobile user 10 . Especially when themobile user 10 moves along the road (Road) on the road, the current location anonymity method based on Euclidean space often cannot effectively protect the privacy of the mobile user's location information (X, Y) (referred to as location privacy ( Location Privacy)). This is because these methods only blur the location information (X, Y) of themobile user 10 into an area (abbreviated as the blurred area), and use the blurred area as an index to measure the degree of location privacy protection. While in road network topology, a large ambiguous region may contain only a small number or even a single road segment, which threatens the location privacy of mobile users.

为了解决移动用户沿着公路上的道路移动时的位置隐私保护问题，广泛使用的匿名模型是星型匿名模型（2009.Proceeding of the VLDBEndowment.Ting Wang,Ling liu.Privacy-Aware Mobile Services overRoad Networks）。利用该星型匿名模型，移动用户的准确位置被模糊化成几条路段组成的星形拓扑图，但是该星型匿名模型存在以下几个缺陷：（1）该模型产生的匿名路段集合虽然包含了几条不同的路段，但是根据该模型的定义，即使分叉路口程度不是很高的路段也可以构成一个匿名路段集合，实质上并没有保证路段多样性。（2）该模型不能很好的满足互惠要求，这样会导致不同的匿名路段集合存在交叉重叠，恶意攻击者通过重放攻击可以推断出移动用户所在的路段。（3）该模型在匿名路段集合扩展过程中，并没有考虑移动用户的分布情况，是一种静态扩展，导致匿名路段集合产生具有一定的确定性而不是随机性。In order to solve the problem of location privacy protection when mobile users move along the road on the highway, the widely used anonymity model is the star anonymity model (2009.Proceeding of the VLDBEndowment.Ting Wang,Ling liu.Privacy-Aware Mobile Services overRoad Networks) . Using the star-shaped anonymous model, the exact location of the mobile user is blurred into a star-shaped topological graph composed of several road sections, but the star-shaped anonymous model has the following defects: (1) Although the anonymous road section set generated by the model contains Several different road segments, but according to the definition of the model, even road segments with a low fork degree can constitute an anonymous road segment set, which does not guarantee the diversity of road segments in essence. (2) This model cannot satisfy the requirement of reciprocity very well, which will lead to overlapping of different anonymous road segment sets, and malicious attackers can infer the road segment where the mobile user is located through replay attacks. (3) The model does not consider the distribution of mobile users during the expansion process of the anonymous road section set.

针对上述星型匿名模型存在的缺陷，本发明提出一种面向路网的查询感知的位置匿名系统，结合路网拓扑结构特征和移动用户的查询内容，使得每个匿名路段集合被其包含的所有移动用户共享，从而避免匿名路段集合的交叉重叠，更好的保护移动用户的位置隐私。Aiming at the defects of the above-mentioned star-shaped anonymous model, the present invention proposes a road network-oriented query-aware location anonymity system, which combines the characteristics of the road network topology and the query content of mobile users, so that each anonymous road section set is covered by all the Mobile users share, thereby avoiding the overlapping of anonymous road section sets, and better protecting the location privacy of mobile users.

发明内容Contents of the invention

针对上述星型匿名模型存在的缺陷，本发明提出一种面向路网的查询感知的位置隐私保护系统，结合路网拓扑结构特征和移动用户的查询特征，使得每个匿名路段集合被其包含的所有用户共享，从而避免匿名路段集合的交叉重叠，更好的保护移动用户的位置隐私。Aiming at the defects of the above-mentioned star-shaped anonymous model, the present invention proposes a query-aware location privacy protection system oriented to the road network, which combines the topological structure characteristics of the road network and the query characteristics of mobile users, so that each anonymous road section set is contained by it. All users share, thereby avoiding the intersection and overlapping of anonymous road section sets, and better protecting the location privacy of mobile users.

本发明是一种面向路网的查询感知的位置隐私保护系统，该位置隐私保护系统包括有移动用户（10）、匿名服务器（30）以及位置服务器（20）；其中，所述匿名服务器（30）包括有匿名请求模块（31）、路段匹配模块（32）、匿名赋值模块（33）和匿名映射模块（34）；The present invention is a road network-oriented query-aware location privacy protection system, the location privacy protection system includes a mobile user (10), an anonymous server (30) and a location server (20); wherein, the anonymous server (30 ) includes an anonymous request module (31), a link matching module (32), an anonymous assignment module (33) and an anonymous mapping module (34);

匿名请求模块（31）对接收到的查询请求信息（10C）一方面将位置-路段信息（31A）发送给路段匹配模块（32）；另一方面将匿名身份信息（31B）发送给匿名赋值模块（33）；The anonymous request module (31) sends the location-road section information (31A) to the road section matching module (32) on the one hand for the received query request information (10C); on the other hand, sends the anonymous identity information (31B) to the anonymous assignment module (33);

所述的位置-路段信息（31A）包括有查询内容集合D＝{d₁,d₂,d₃,…d_b}中的

、X_ID,Y_ID和t_ID，以及匿名路段集合S={s₁,s₂,s₃,…,s_a}；The position-road section information (31A) includes query content set D={d₁ ,d₂ ,d₃ ,...d_b }

, X_ID , Y_ID and t_ID , and the set of anonymous road segments S={s₁ ,s₂ ,s₃ ,…,s_a };

所述的匿名身份信息（31B）包括有查询内容集合D＝{d₁,d₂,d₃,…d_b}中的ID、X_ID,Y_ID、L_ID、I_ID和t_ID；The anonymous identity information (31B) includes ID, X_ID , Y_{ID, L ID,} I_ID and t_ID in the query content set D={d₁ , d₂ , d₃ ,...d_b };

所述任意一查询内容d_b的格式为：The format of any query content_db is:

$<span><span><</span><</span>\mathrm{<span><span>ID</span>ID</span>}<span><span>,</span>,</span>{\mathrm{<span><span>R</span>R</span>}}_{{\mathrm{<span><span>con</span>con</span>}}_{\mathrm{<span><span>ID</span>ID</span>}}}<span><span>,</span>,</span><span><span><</span><</span>{\mathrm{<span><span>X</span>x</span>}}_{\mathrm{<span><span>ID</span>ID</span>}}<span><span>,</span>,</span>{\mathrm{<span><span>Y</span>Y</span>}}_{\mathrm{<span><span>ID</span>ID</span>}}<span><span>></span>></span><span><span>,</span>,</span>{\mathrm{<span><span>t</span>t</span>}}_{\mathrm{<span><span>ID</span>ID</span>}}<span><span>,</span>,</span><span><span>\{</span>\{</span>{\mathrm{<span><span>L</span>L</span>}}_{\mathrm{<span><span>ID</span>ID</span>}}<span><span>,</span>,</span>{\mathrm{<span><span>I</span>I</span>}}_{\mathrm{<span><span>ID</span>ID</span>}}<span><span>\}</span>\}</span><span><span>></span>></span><span><span>;</span>;</span>$

路段匹配模块（32）首先对接收到的位置-路段信息（31A）通过任意一移动用户U_ID的位置坐标X_ID,Y_ID确定出，任意一移动用户U_ID所在路网中的路段然后对路段

进行匿名路段集合S={s₁,s₂,s₃,…,s_a}中的优先级第一队列AA＝(aa₁,aa₂,aa₃,…,aa_i)和优先级第二队列BB＝(bb₁,bb₂,bb₃,bb₄,bb₅,bb₆,…,bb_j,bb_(j+1),…)的更新，得到第二匿名路段集合SH={sh₁,sh₂,sh₃,…,sh_a}；然后对第二匿名路段集合SH={sh₁,sh₂,sh₃,…,sh_a}进行隐私要求{L_ID,I_ID}的判断，若满足r_NUM≥m_max同时r_NUM≥k_max，则为满足隐私要求{L_ID,I_ID}；在不满足隐私要求{L_ID,I_ID}的条件下，通过随机因子η在路段区间

范围内从侁先第一队列AA中随机选择一条候选路段r′，同时，把候选路段r′的两个端点添加到侁先第二队列BB中，并将该候选路段r′添加到第二匿名路段集合SH={sh₁,sh₂,sh₃,…,sh_a}中，得到第三匿名路段集合SHH={shh₁,shh₂,shh₃,…,shh_a}；最后把与候选路段r′相邻的所有路段插入到队列AA中，如果有匹配路段加入，继续进行匿名，直到找到满足移动用户隐私要求的匿名路段集合为止；如果没有匹配路段加入，则匿名失败，拒绝位置匿名服务；The road segment matching module (32) first determines the road segment in the road network where any mobile user U_ID is located by using the location coordinates X_ID and Y_ID of any mobile user_UID from the received position-road segment information (31A) Then for the section

Carry out_{the priority first queue AA=(aa 1 ,aa 2,aa 3,…,aa i)andthe} priority second Queue BB=(bb₁ , bb₂ , bb₃ , bb₄ , bb₅ , bb₆ ,..., bb_j , bb_(j+1) ,...) update to get the second anonymous segment set SH={sh₁ ,sh₂ ,sh₃ ,…,sh_a }; then judge the privacy requirement {L_ID ,I_ID } for the second anonymous road segment set SH={sh₁ ,sh₂ ,sh₃ ,…,sh_a }, If r_NUM ≥ m_max and r_NUM ≥ k_max , then the privacy requirement {L_ID , I_ID } is satisfied; if the privacy requirement {L_ID , I_ID } is not met, the random factor η is used to determine the

Randomly select a candidate road section r' from the first queue AA within the range, and at the same time, add the two endpoints of the candidate road section r' to the first second queue BB, and add the candidate road section r' to the second queue In the anonymous section set SH={sh₁ ,sh₂ ,sh₃ ,…,sh_a }, get the third anonymous section set SHH={shh₁ ,shh₂ ,shh₃ ,…,shh_a }; Insert all road segments adjacent to road segment r' into the queue AA. If there is a matching road segment added, continue to anonymize until an anonymous road segment set that meets the privacy requirements of mobile users is found; if no matching road segment is added, anonymization fails and location anonymization is rejected Serve;

匿名赋值模块（33）对收到的查询内容集合D＝{d₁,d₂,d₃,…d_b}中的任意移动用户U_ID的标识ID进行假名赋值处理，得到用户假名ID′；同时记录下移动用户的真实标识与用户假名之间的对应关系，即匿名对应关系A_ID→NA_ID；The anonymous assignment module (33) performs pseudonym assignment processing on the identification ID of any mobile user U_ID in the received query content set D={d₁ ,d₂ ,d₃ ,...d_b }, and obtains the user pseudonym ID′; At the same time, record the corresponding relationship between the real identity of the mobile user and the user's pseudonym, that is, the anonymous corresponding relationship A_ID → NA_ID ;

匿名映射模块（34）收到位置服务器返回的查询结果C＝{c₁,c₂,c₃,…,c_h}后，根据移动用户的准确位置对查询结果进行过滤，并且把准确的最终查询结果F_最终＝{f₁,f₂,f₃,…f_e}发送给相应的移动用户。After receiving the query result C={c₁ ,c₂ ,c₃ ,…,c_h } returned by the location server, the anonymous mapping module (34) filters the query result according to the exact location of the mobile user, and puts the accurate final The query result F={f₁ , f₂ , f₃ ,...f_e } is_finally sent to the corresponding mobile user.

本发明面向路网的查询感知的位置隐私保护系统的优点在于：The advantages of the road network-oriented query-aware location privacy protection system of the present invention are:

①使用本系统可以对路网中享受位置服务的移动用户的位置隐私进行保护，从而解决移动用户在使用位置服务的同时位置隐私遭到泄露的问题。本发明产生的匿名路段集合保证被其所包含的所有移动用户共享，避免了匿名路段集合的交叉重叠，很好的抵抗了重放攻击。①Using this system can protect the location privacy of mobile users who enjoy location-based services in the road network, thereby solving the problem that mobile users' location privacy is leaked while using location-based services. The anonymous road section set generated by the invention is guaranteed to be shared by all mobile users contained therein, avoids overlapping of the anonymous road section set, and well resists replay attacks.

②采用匿名路段替代准确的位置信息，从而很好的保护了移动用户的位置隐私，防止恶意攻击者获得移动用户的位置信息，从而推断出移动用户所处的位置。②Anonymous road sections are used to replace accurate location information, thereby protecting the location privacy of mobile users and preventing malicious attackers from obtaining the location information of mobile users, thereby inferring the location of mobile users.

附图说明Description of drawings

图1是传统位置服务的位置查询的结构框图。FIG. 1 is a structural block diagram of a location query of a traditional location service.

图2是本发明的位置服务中基于路网的位置隐私保护框图。Fig. 2 is a block diagram of road network-based location privacy protection in the location service of the present invention.

图3是位置服务中基于路网的位置隐私保护的流程图。Fig. 3 is a flowchart of location privacy protection based on road network in location services.

图4是匿名路段的拓朴结构图。Figure 4 is a topological structure diagram of an anonymous road segment.

  10.移动用户10.Mobile users  20.位置服务器20.Location server  31.匿名请求模块31.Anonymous request module  32.路段匹配模块32.Section matching module  33.匿名赋值模块33.Anonymous assignment module  34.匿名映射模块34. Anonymous mapping module

具体实施方式Detailed ways

下面将结合附图和实施例对本发明做进一步的详细说明。The present invention will be further described in detail below in conjunction with the accompanying drawings and embodiments.

在无线通信网络中，建立会话之后，匿名服务器30执行本发明的面向路网的查询感知的隐私保护系统。移动用户10向匿名服务器30发送查询请求信息10C时需要提前进行注册。In the wireless communication network, after the session is established, theanonymous server 30 executes the road network-oriented query-aware privacy protection system of the present invention. When themobile user 10 sends thequery request information 10C to theanonymous server 30, it needs to register in advance.

在本发明中，第一移动用户标记为U₁，第二移动用户标记为U₂，第三移动用户标记为U₃，任意一移动用户标记为U_ID（ID为移动用户的标识），则移动用户采用集合形式表示为MS＝{U₁,U₂,U₃,…,U_ID}。多个移动用户10向匿名服务器30发出查询请求信息10C，所述查询请求信息10C包括有查询内容集合D＝{d₁,d₂,d₃,…d_b}和匿名路段集合S={s₁,s₂,s₃,…,s_a}。In the present invention, the first mobile user is marked as U₁ , the second mobile user is marked as U₂ , the third mobile user is marked as U₃ , and any mobile user is marked as U_ID (ID is the identification of the mobile user), then The mobile users are represented as MS={U₁ , U₂ , U₃ ,..., U_ID } in a set form. Multiplemobile users 10 sendquery request information 10C to theanonymous server 30, thequery request information 10C includes query content set D={d₁ ,d₂ ,d₃ ,...d_b } and anonymous road section set S={s₁ ,s₂ ,s₃ ,...,s_a }.

在查询内容集合D＝{d₁,d₂,d₃,…d_b}中，d₁为第一个查询内容，d₂为第二个查询内容，d₃为第三个查询内容，d_b为任意一个查询内容，b为查询内容的种类标识号。所述任意一查询内容d_b的格式为$<\mathrm{ID},R_{{\mathrm{con}}_{\mathrm{ID}}},<X_{\mathrm{ID}},Y_{\mathrm{ID}}>,t_{\mathrm{ID}},\{L_{\mathrm{ID}},I_{\mathrm{ID}}\}>;$在本发明中，所述的查询内容集合D＝{d₁,d₂,d₃,…d_b}是移动用户的私有信息，是本发明要保护的对象。其中，ID表示移动用户的标识；X_ID,Y_ID表示移动用户的位置坐标；表示请求的查询内容；t_ID表示请求查询内容发出时的时刻（简称为查询时刻）；L_ID表示个性化位置k匿名参数；I_ID表示个性化路段m匿名参数。L_ID与I_ID统称为隐私要求。In the query content set D={d₁ ,d₂ ,d₃ ,…d_b }, d₁ is the first query content, d₂ is the second query content, d₃ is the third query content, d_b is any query content, and b is the type identification number of the query content. The format of any query content_db is$<\mathrm{ID},R_{{\mathrm{con}}_{\mathrm{ID}}},<x_{\mathrm{ID}},Y_{\mathrm{ID}}>,t_{\mathrm{ID}},\{L_{\mathrm{ID}},I_{\mathrm{ID}}\}>;$ In the present invention, the query content set D={d₁ , d₂ , d₃ ,...d_b } is the private information of the mobile user and is the object to be protected by the present invention. Wherein, ID represents the identification of mobile user; X_ID , Y_ID represents the location coordinate of mobile user; Indicates the query content of the request; t_ID indicates the time when the request query content is issued (referred to as the query time); L_ID indicates the personalized location k anonymous parameter; I_ID indicates the personalized road section m anonymous parameter. L_ID and I_ID are collectively referred to as privacy requirements.

在匿名路段集合S={s₁,s₂,s₃，…,s_a}中，s₁为第一个匿名路段，s₂为第二个匿名路段，s₃为第三个匿名路段，s_a为移动用户的任意一匿名路段，a为匿名路段标识号。In the set of anonymous road segments S={s₁ , s₂ , s₃ ,…,s_a }, s₁ is the first anonymous road segment, s₂ is the second anonymous road segment, s₃ is the third anonymous road segment, s_a is any anonymous section of the mobile user, and a is the identification number of the anonymous section.

参见图2所示，本发明的一种面向路网的查询感知的位置隐私保护系统的宗旨是匿名服务器30将匿名查询信息32A（即匿名查询集合Q＝{q₁,q₂,q₃,…,q_w}）转发给位置服务器20，位置服务器20再将候选查询结果信息20A（即候选查询结果集合C＝{c₁,c₂,c₃,…,c_h}）返回给匿名服务器30。这样只要任意一个移动用户U_ID在匿名路段集合S={s₁,s₂,s₃，…,s_a}中，并且查询请求信息在查询内容集合D＝{d₁,d₂,d₃,…d_b}中，便会得到匿名服务。匿名服务器30在收到候选查询结果集合C＝{c₁,c₂,c₃,…,c_h}之后，再将所述的候选查询结果集合C＝{c₁,c₂,c₃,…,c_h}经过身份过滤求精处理形成查询结果信息10B（即查询结果集合F_最终＝{f₁,f₂,f₃,…f₃}）返回给移动用户U_ID。Referring to Fig. 2, the purpose of the road network-oriented query-aware location privacy protection system of the present invention is that theanonymous server 30 will send theanonymous query information 32A (that is, the anonymous query set Q={q₁ ,q₂ ,q₃ , ...,q_w }) to thelocation server 20, and thelocation server 20 returns the candidatequery result information 20A (that is, the candidate query result set C={c₁ ,c₂ ,c₃ ,...,c_h }) to theanonymous server 30. In this way, as long as any mobile user U_ID is in the anonymous segment set S={s₁ ,s₂ ,s₃ ,…,s_a }, and the query request information is in the query content set D={d₁ ,d₂ ,d₃ ,...d_b }, anonymous service will be obtained. After receiving the candidate query result set C={c₁ ,c₂ ,c₃ ,...,c_h }, theanonymous server 30 then sends the candidate query result set C={c₁ ,c₂ ,c₃ , ..., c_h } are processed through identity filtering and refinement to formquery result information 10B (that is, the query result set F_finally ={f₁ , f₂ , f₃ ,...f₃ }) and return it to the mobile user U_ID .

参见图2所示，本发明的一种面向路网的查询感知的位置隐私保护系统，其包括有移动用户10、匿名服务器30以及位置服务器20；其中，匿名服务器30包括有匿名请求模块31、路段匹配模块32、匿名赋值模块33和匿名映射模块34。2, a road network-oriented query-aware location privacy protection system of the present invention includes amobile user 10, ananonymous server 30, and alocation server 20; wherein theanonymous server 30 includes ananonymous request module 31, Roadsection matching module 32 ,anonymous assignment module 33 andanonymous mapping module 34 .

（一）匿名请求模块31(1)Anonymous request module 31

匿名请求模块31对接收到的查询请求信息10C一方面将位置-路段信息31A发送给路段匹配模块32；另一方面将匿名身份信息31B发送给匿名赋值模块33；Theanonymous request module 31 sends the location-road section information 31A to the roadsection matching module 32 on the one hand for the receivedquery request information 10C; sends theanonymous identity information 31B to theanonymous assignment module 33 on the other hand;

所述的位置-路段信息31A包括有查询内容集合D＝{d₁,d₂,d₃,…d_b}中的

X_ID,Y_ID和t_ID，以及匿名路段集合S={s₁,s₂,s₃,…,s_a}；The position-road section information 31A includes query content set D={d₁ ,d₂ ,d₃ ,...d_b }

X_ID , Y_ID and t_ID , and the set of anonymous road segments S={s₁ , s₂ , s₃ ,…,s_a };

所述的匿名身份信息31B包括有查询内容集合D＝{d₁,d₂,d₃,…d_b}中的ID、X_ID,Y_ID、L_ID、I_ID和t_ID；Theanonymous identity information 31B includes ID, X_ID , Y_ID , L_ID , I_ID and t_ID in the query content set D={d₁ , d₂ , d₃ ,...d_b };

在本发明中，所述任意一查询内容d_b的格式为：In the present invention, the format of any query content_db is:

$<span><span><</span><</span>\mathrm{<span><span>ID</span>ID</span>}<span><span>,</span>,</span>{\mathrm{<span><span>R</span>R</span>}}_{{\mathrm{<span><span>con</span>con</span>}}_{\mathrm{<span><span>ID</span>ID</span>}}}<span><span>,</span>,</span><span><span><</span><</span>{\mathrm{<span><span>X</span>x</span>}}_{\mathrm{<span><span>ID</span>ID</span>}}<span><span>,</span>,</span>{\mathrm{<span><span>Y</span>Y</span>}}_{\mathrm{<span><span>ID</span>ID</span>}}<span><span>></span>></span><span><span>,</span>,</span>{\mathrm{<span><span>t</span>t</span>}}_{\mathrm{<span><span>ID</span>ID</span>}}<span><span>,</span>,</span><span><span>\{</span>\{</span>{\mathrm{<span><span>L</span>L</span>}}_{\mathrm{<span><span>ID</span>ID</span>}}<span><span>,</span>,</span>{\mathrm{<span><span>I</span>I</span>}}_{\mathrm{<span><span>ID</span>ID</span>}}<span><span>\}</span>\}</span><span><span>></span>></span><span><span>;</span>;</span>$

其中，ID表示移动用户的标识；X_ID,Y_ID表示移动用户的位置坐标；表示请求的查询内容；t_ID表示请求查询内容发出时的时刻（简称为查询时刻）；L_ID表示个性化位置k匿名参数；I_ID表示个性化路段m匿名参数。L_ID与I_ID统称为隐私要求。Wherein, ID represents the identification of mobile user; X_ID , Y_ID represents the location coordinate of mobile user; Indicates the query content of the request; t_ID indicates the time when the request query content is issued (referred to as the query time); L_ID indicates the personalized location k anonymous parameter; I_ID indicates the personalized road section m anonymous parameter. L_ID and I_ID are collectively referred to as privacy requirements.

在本发明中，对查询内容引入个性化k匿名参数和个性化m匿名参数有利于移动用户MS＝{U₁,U₂,U₃,…,U_ID}针对所处环境的不同，并根据自身需求灵活制定个性化的匿名参数。为保护自身的查询隐私提供更好的保障。In the present invention, the introduction of personalized k anonymous parameters and personalized m anonymous parameters to query content is beneficial to mobile users MS={U₁ , U₂ , U₃ ,..., U_ID } according to different environments, and according to Customize your own anonymous parameters flexibly according to your own needs. Provide better protection for protecting your own query privacy.

在本发明中，应用匿名请求模块31来对多个移动用户MS＝{U₁,U₂,U₃,…,U_ID}的各个信息进行分发，能够均衡无线通信网络的负载，实现对查询结果的分布处理。In the present invention, theanonymous request module 31 is used to distribute the various information of multiple mobile users MS={U₁ , U₂ , U₃ ,..., U_ID }, which can balance the load of the wireless communication network and realize the query Distributed processing of results.

（二）路段匹配模块32(2)Section matching module 32

路段匹配模块32首先对接收到的位置-路段信息31A通过任意一移动用户U_ID的位置坐标X_ID,Y_ID确定出，任意一移动用户U_ID所在路网中的路段

然后对路段

进行匿名路段集合S={s₁,s₂,s₃,…,s_a}中的优先级第一队列AA＝(aa₁,aa₂,aa₃,…,aa_i)和优先级第二队列BB＝(bb₁,bb₂,bb₃,bb₄,bb₅,bb₆,…,bb_j,bb_(j+1),…)的更新，得到第二匿名路段集合SH={sh₁,sh₂,sh₃,…,sh_a}；然后对第二匿名路段集合SH={sh₁,sh₂,sh₃,…,sh_a}进行隐私要求{L_ID,I_ID}的判断，若满足r_NUM≥m_max同时r_NUM≥k_max，则为满足隐私要求{L_ID,I_ID}；在不满足隐私要求{L_ID,I_ID}的条件下，通过随机因子η在路段区间

范围内从侁先第一队列AA中随机选择一条候选路段r′，同时，把候选路段r′的两个端点添加到侁先第二队列BB中，并将该候选路段r′添加到第二匿名路段集合SH={sh₁,sh₂,sh₃,…,sh_a}中，得到第三匿名路段集合SHH={shh₁,shh₂,shh₃,…,shh_a}；最后把与候选路段r′相邻的所有路段插入到队列AA中，如果有匹配路段加入，继续进行匿名，直到找到满足移动用户隐私要求的匿名路段集合为止；如果没有匹配路段加入，则匿名失败，拒绝位置匿名服务。The road section matching module 32 first determines the road section in the road network where any mobile user_UID is located through the position coordinates X_ID and Y_ID of any mobile user_UID to the received position-road section information 31A

Then for the section

Carry out_{the priority first queue AA=(aa 1 ,aa 2,aa 3,…,aa i)andthe} priority second Queue BB=(bb₁ , bb₂ , bb₃ , bb₄ , bb₅ , bb₆ ,..., bb_j , bb_(j+1) ,...) update to get the second anonymous segment set SH={sh₁ ,sh₂ ,sh₃ ,…,sh_a }; then judge the privacy requirement {L_ID ,I_ID } for the second anonymous road segment set SH={sh₁ ,sh₂ ,sh₃ ,…,sh_a }, If r_NUM ≥ m_max and r_NUM ≥ k_max , then the privacy requirement {L_ID , I_ID } is satisfied; if the privacy requirement {L_ID , I_ID } is not met, the random factor η is used to determine the

Randomly select a candidate road section r' from the first queue AA within the range, and at the same time, add the two endpoints of the candidate road section r' to the first second queue BB, and add the candidate road section r' to the second queue In the anonymous section set SH={sh₁ ,sh₂ ,sh₃ ,…,sh_a }, get the third anonymous section set SHH={shh₁ ,shh₂ ,shh₃ ,…,shh_a }; Insert all road segments adjacent to road segment r' into the queue AA. If there is a matching road segment added, continue to anonymize until an anonymous road segment set that meets the privacy requirements of mobile users is found; if no matching road segment is added, anonymization fails and location anonymization is rejected Serve.

在本发明中，路段匹配模块32的具体路段选取包括有下列步骤：In the present invention, the specific road section selection of the roadsection matching module 32 includes the following steps:

步骤32-1：路段匹配模块32对接收到的位置-路段信息31A通过任意一移动用户U_ID的位置坐标X_ID，Y_ID确定出，任意一移动用户U_ID所在路网中的路段Step 32-1: The roadsegment matching module 32 determines the road segment in the road network where any mobile user U_ID is located through the position coordinates X_ID and Y_ID of any mobile user U_ID on the received position-road segment information 31A

在本发明中，路段

是指移动用户所在的实际路段。路段

包含在匿名路段集合S={s₁,s₂,s₃,…,s_a}中。In the present invention, the section

It refers to the actual road section where the mobile user is located. road section

Included in the collection of anonymous road segments S={s₁ ,s₂ ,s₃ ,…,s_a }.

步骤32-2：（A）从匿名路段集合S={s₁,s₂,s₃,…,s_a}中选取出匿名候选路段，形成优先级第一队列AA＝(aa₁,aa₂,aa₃,…,aa_i)；（B）对优先级第一队列AA＝(aa₁,aa₂,aa₃,…,aa_i)进行路段的两个端点提取，得到优先级第二队列BB＝(bb₁,bb₂,bb₃,bb₄,bb₅,bb₆,…,bb_j,bb_(j+1),…)；（C）将步骤32-1中得到的路段添加至匿名路段集合S={s₁,s₂,s₃,…,s_a}中，并用优先级第一队列AA＝(aa₁,aa₂,aa₃,…,aa_i)和优先级第二队列BB＝(bb₁,bb₂,bb₃,bb₄,bb₅,bb₆,…,bb_j,bb_(j+1),…)来更新匿名路段集合S={s₁,s₂,s₃,…,s_a}，得到第二匿名路段集合SH={sh₁,sh₂,sh₃,…,sh_a}；Step 32-2: (A) Select anonymous road segments from the set of anonymous road segments S={s₁ , s₂ , s₃ ,…,s_a } to form the first priority queue AA=(aa₁ ,aa₂ ,aa₃ ,…,aa_i ); (B) Extract the two endpoints of the road segment from the first priority queue AA=(aa₁ ,aa₂ ,aa₃ ,…,aa_i ), and get the second priority queue BB＝(bb₁ ,bb₂ ,bb₃ ,bb₄ ,bb₅ ,bb₆ ,…,bb_j ,bb_(j+1) ,…); (C) The road section obtained in step 32-1 Add to the anonymous road section set S={s₁ ,s₂ ,s₃ ,…,s_a }, and use the priority first queue AA=(aa₁ ,aa₂ ,aa₃ ,…,aa_i ) and priority The second queue BB=(bb₁ ,bb₂ ,bb₃ ,bb₄ ,bb₅ ,bb₆ ,…,bb_j ,bb_(j+1) ,…) to update the anonymous road section set S={s₁ ,s₂ ,s₃ ,…,s_a }, get the second anonymous road section set SH={sh₁ ,sh₂ ,sh₃ ,…,sh_a };

在本发明中，路段

的一端端点记为r_头(X,Y)，路段

的另一端端点记为r_尾(X,Y)，在对优先级第二队列BB进行初始化时，存入r_头(X,Y)与r_尾(X,Y)的位置值。In the present invention, the section

The end point of one end is recorded as r_head (X, Y), and the road section

The other end point of is denoted as r_tail (X, Y), and when the second priority queue BB is initialized, the position values of r_head (X, Y) and r_tail (X, Y) are stored.

在本发明中，优先级第一队列AA＝(aa₁,aa₂,aa₃，…,aa_i)为匿名路段集合S={s₁,s₂,s₃，…,s_a}中的匿名候选路段集合。In the present invention, the first priority queue AA=(aa₁ ,aa₂ ,aa₃ ,...,aa_i ) is the anonymous section set S={s₁ ,s₂ ,s₃ ,...,s_a } A collection of anonymous road segments.

在本发明中，优先级第一队列AA＝(aa₁,aa₂,aa₃,…,aa_i)中的aa₁为第一个匿名候选路段，aa₂为第二个匿名候选路段，aa₃为第三个匿名候选路段，aa_i为任意一匿名候选路段，i为匿名候选路段的标识号。In the present invention,aa 1 in the priority first queue AA=(aa₁ , aa₂ , aa₃ ,..., aa_i ) is the first anonymous candidate road section,_{aa 2is} the second anonymous candidate road section, and aa₃ is the third anonymous candidate road section, aa_i is any anonymous candidate road section, and i is the identification number of the anonymous candidate road section.

在本发明中，优先级第二队列BB＝(bb₁,bb₂,bb₃,bb₄,bb₅,bb₆,…,bb_j,bb_(j+1),…)中的：In the present invention, in the second priority queue BB=(bb₁ , bb₂ , bb₃ , bb₄ , bb₅ , bb₆ ,..., bb_j , bb_(j+1) ,...):

bb₁为第一个匿名候选路段aa₁的一端端点，bb₂为第一个匿名候选路段aa₁的另一端端点；bb₁ is one endpoint of the first anonymous candidate road section aa₁ , and bb₂ is the other endpoint of the first anonymous candidate road section aa₁ ;

bb₃为第二个匿名候选路段aa₂的一端端点，bb₄为第二个匿名候选路段aa₂的另一端端点；bb₃ is one endpoint of the second anonymous candidate road section aa₂ , and bb₄ is the other endpoint of the second anonymous candidate road section aa₂ ;

bb₅为第三个匿名候选路段aa₃的一端端点，bb₆为第三个匿名候选路段aa₃的另一端端点；bb₅ is one endpoint of the third anonymous candidate road section aa₃ , and bb₆ is the other endpoint of the third anonymous candidate road section aa₃ ;

bb_j为任意一个匿名候选路段aa_i的一端端点，bb_(j+1)为任意一个匿名候选路段aa_i的另一端端点；j为与i对应的匿名候选路段端点标识号。bb_j is one endpoint of any anonymous candidate road section aa_i , bb_(j+1) is the other endpoint of any anonymous candidate road section aa_i ; j is the identification number of the anonymous candidate road section endpoint corresponding to i.

步骤32-3：判断第二匿名路段集合SH={sh₁,sh₂,sh₃,…,sh_a}是否满足任意一移动用户U_ID的隐私要求{L_ID,I_ID}；Step 32-3: Determine whether the second set of anonymous road segments SH={sh₁ ,sh₂ ,sh₃ ,...,sh_a } meets the privacy requirement {L_ID ,I_ID } of any mobile user U_ID ;

判断过程如下：若r_NUM≥m_max同时r_NUM≥k_max，则满足隐私要求{L_ID,I_ID}；反之为不满足，则进入步骤32-4；The judging process is as follows: if r_NUM ≥ m_max and r_NUM ≥ k_max , then the privacy requirement {L_ID , I_ID } is met; otherwise, it is not satisfied, then enter step 32-4;

r_NUM表示第二匿名路段集合SH={sh₁,sh₂,sh₃,…,sh_a}中包含的路段数量；m_max表示隐私要求{L_ID,I_ID}中的个性化路段m匿名参数I_ID中取的路段最大值（简称为路段匿名最大值，一般m_max=20）；k_max表示隐私要求{L_ID，I_ID}中的个性化位置k匿名参数L_ID中取的最大值（简称为位置匿名最大值，一般k_max=50）。r_NUM represents the number of road segments contained in the second anonymous road segment set SH={sh₁ ,sh₂ ,sh₃ ,…,sh_a }; m_max represents the personalized road segment m anonymous in the privacy requirement {L_ID ,I_ID } The maximum value of the road section taken in the parameter I_ID (abbreviated as the anonymous maximum value of the road section, generally m_max =20); k_max represents the personalized position k in the privacy requirement {L_ID , I_ID } The largest value in the anonymous parameter L_ID value (referred to as the positional anonymous maximum value, generally k_max =50).

在本发明中，如果第二匿名路段集合SH={sh₁,sh₂,sh₃,…,sh_a}中的路段数满足移动用户的隐私要求{L_ID，I_ID}，匿名完成，并把匿名查询信息32A发送给位置服务器20。In the present invention, if the number of road sections in the second anonymous road section set SH={sh₁ ,sh₂ ,sh₃ ,...,sh_a } meets the mobile user's privacy requirement {L_ID , I_ID }, anonymity is completed, and Theanonymous inquiry message 32A is sent to thelocation server 20 .

在本发明中，匿名查询信息32A也是匿名查询集合Q＝{q₁,q₂,q₃,…,q_w}。在匿名查询集合Q＝{q₁,q₂,q₃,…,q_w}中，q₁＝(s₁,d₁)，q₂＝(s₂,d₂)，q₃＝(s₃,d₃)，q_w＝(s_a,d_b)；q₁＝(s₁,d₁)为第一个匿名路段和第一个查询内容构成的有序对；q₂＝(s₂,d₂)为第二个匿名路段和第二个查询内容构成的有序对；q₃＝(s₃,d₃)为第三个匿名路段和第三个查询内容构成的有序对；q_w＝(s_a,d_b)为任意一个匿名路段和任意一个查询内容构成的有序对，w为匿名路段和查询内容构成的有序对的标识号。In the present invention, theanonymous query information 32A is also an anonymous query set Q={q₁ , q₂ , q₃ , . . . , q_w }. In the anonymous query set Q={q₁ ,q₂ ,q₃ ,…,q_w }, q₁ =(s₁ ,d₁ ), q₂ =(s₂ ,d₂ ), q₃ =(s₃ ,d₃ ), q_w ＝(s_a ,d_b ); q₁ ＝(s₁ ,d₁ ) is the ordered pair formed by the first anonymous road segment and the first query content; q₂ ＝(s₂ ,d₂ ) is the ordered pair formed by the second anonymous road segment and the second query content; q₃ =(s₃ ,d₃ ) is the ordered pair formed by the third anonymous road segment and the third query content ;q_w =(s_a ,d_b ) is an ordered pair formed by any anonymous road segment and any query content, and w is the identification number of the ordered pair formed by the anonymous road segment and the query content.

步骤32-4：（A）在第二匿名路段集合SH={sh₁,sh₂,sh₃,…,sh_a}不满足隐私要求{L_ID，I_ID}时，路段匹配模块32将产生随机因子η（一般地，η为0.1～0.5的一个数，单位为常量）；（B）在路段区间

范围内从侁先第一队列AA中随机选择一条候选路段r′，同时，把候选路段r′的两个端点添加到侁先第二队列BB中，并将该候选路段r′添加到第二匿名路段集合SH={sh₁,sh₂,sh₃,…,sh_a}中，得到第三匿名路段集合SHH={shh₁,shh₂,shh₃,…,shh_a}；（C）把与候选路段r′相邻的所有路段插入到队列AA中，如果有匹配路段加入，则返回至步骤32-2中进行继续匿名，直到找到满足移动用户隐私要求的匿名路段集合为止；如果没有匹配路段加入，则匿名失败，拒绝位置匿名服务。Step 32-4: (A) When the second set of anonymous road segments SH={sh₁ ,sh₂ ,sh₃ ,...,sh_a } does not meet the privacy requirement {L_ID , I_ID }, the roadsegment matching module 32 will generate Random factor η (generally, η is a number from 0.1 to 0.5, and the unit is a constant); (B) in the section interval

Randomly select a candidate road section r' from the first queue AA within the range, and at the same time, add the two endpoints of the candidate road section r' to the first second queue BB, and add the candidate road section r' to the second queue In the anonymous road section set SH={sh₁ ,sh₂ ,sh₃ ,…,sh_a }, the third anonymous road section set SHH={shh₁ ,shh₂ ,shh₃ ,…,shh_a } is obtained; (C) put All road segments adjacent to the candidate road segment r' are inserted into the queue AA. If there is a matching road segment added, return to step 32-2 to continue anonymizing until an anonymous road segment set that meets the privacy requirements of the mobile user is found; if there is no matching If a road segment is added, the anonymity fails, and the location anonymity service is rejected.

表示处于队列AA的队首路段（即aa₁）上的查询请求数量。 Indicates the number of query requests on the head section of queue AA (that is, aa₁ ).

（三）匿名赋值模块33(3)Anonymous assignment module 33

匿名赋值模块33对接收到的匿名身份信息31B进行假名赋值处理，得到用户假名ID′；同时记录下移动用户的真实标识与用户假名之间的对应关系，即匿名对应关系A_ID→NA_ID；Anonymous assignment module 33 carries out pseudonym assignment processing to theanonymous identity information 31B that receives, obtains user's pseudonym ID '; Record the corresponding relationship between the real identification of mobile user and user's pseudonym simultaneously, namely anonymous corresponding relationship A_ID →NA_ID ;

在本发明中，匿名身份信息31B也是查询内容集合D＝{d₁,d₂,d₃,…d_b}，查询内容d_b的格式为$<\mathrm{ID},R_{{\mathrm{con}}_{\mathrm{ID}}},<X_{\mathrm{ID}},Y_{\mathrm{ID}}>,t_{\mathrm{ID}},\{L_{\mathrm{ID}},I_{\mathrm{ID}}\}>.$对于任意一移动用户U_ID的标识ID进行假名赋值处理，得到用户假名ID′。In the present invention, theanonymous identity information 31B is also a set of query content D={d₁ , d₂ , d₃ ,...d_b }, the format of the query content_db is$<\mathrm{ID},R_{{\mathrm{con}}_{\mathrm{ID}}},<x_{\mathrm{ID}},Y_{\mathrm{ID}}>,t_{\mathrm{ID}},\{L_{\mathrm{ID}},I_{\mathrm{ID}}\}>.$ The pseudonym assignment process is performed on the identification ID of any mobile user_UID to obtain the user pseudonym ID'.

如第一移动用户U₁的身分标识为A₁，在匿名模块中所述身分标识A₁所对应的假名为NA₁，则查询内容d_b的格式$<\mathrm{ID},R_{{\mathrm{con}}_{\mathrm{ID}}},<X_{\mathrm{ID}},Y_{\mathrm{ID}}>,t_{\mathrm{ID}},\{L_{\mathrm{ID}},I_{\mathrm{ID}}\}>$变换为匿名对应查询内容Nd_b的格式为If the identity of the first mobile user U₁ is A₁ , and the pseudonym corresponding to the identity A₁ in the anonymous module is NA₁ , then the format of the query content_db$<\mathrm{ID},R_{{\mathrm{con}}_{\mathrm{ID}}},<x_{\mathrm{ID}},Y_{\mathrm{ID}}>,t_{\mathrm{ID}},\{L_{\mathrm{ID}},I_{\mathrm{ID}}\}>$ Transformed into anonymous corresponding query content Nd_b format is

$<span><span><</span><</span>{\mathrm{<span><span>NA</span><figure-callout\; label="NA"\; filenames="HDA00002261301000031.png"\; state="\{\{state\}\}">NA</figure-callout></span>}}_{\mathrm{<span><span>1</span>1</span>}}<span><span>,</span>,</span>{\mathrm{<span><span>R</span><figure-callout\; label="R\; con\; NA"\; filenames="HDA00002261301000031.png"\; state="\{\{state\}\}">R</figure-callout></span><figure-callout\; label="R\; con\; NA"\; filenames="HDA00002261301000031.png"\; state="\{\{state\}\}"></figure-callout>}}_{{\mathrm{<span><span>con</span>con</span>}}_{{}_{}}}<span><span>,</span>,</span><span><span><</span><</span>{\mathrm{<span><span>X</span>x</span>}}_{{\mathrm{<span><span>NA</span><figure-callout\; label="NA"\; filenames="HDA00002261301000031.png"\; state="\{\{state\}\}">NA</figure-callout></span>}}_{\mathrm{<span><span>1</span>1</span>}}}<span><span>,</span>,</span>{\mathrm{<span><span>Y</span><figure-callout\; label="Y\; NA"\; filenames="HDA00002261301000031.png"\; state="\{\{state\}\}">Y</figure-callout></span><figure-callout\; label="Y\; NA"\; filenames="HDA00002261301000031.png"\; state="\{\{state\}\}"></figure-callout>}}_{{\mathrm{<span><span></span></span>}}_{}}<span><span>></span>></span><span><span>,</span>,</span>{\mathrm{<span><span>t</span><figure-callout\; label="t\; NA"\; filenames="HDA00002261301000031.png"\; state="\{\{state\}\}">t</figure-callout></span><figure-callout\; label="t\; NA"\; filenames="HDA00002261301000031.png"\; state="\{\{state\}\}"></figure-callout>}}_{{\mathrm{<span><span></span></span>}}_{}}<span><span>,</span>,</span><span><span>\{</span>\{</span>{\mathrm{<span><span>L</span><figure-callout\; label="L\; NA"\; filenames="HDA00002261301000031.png"\; state="\{\{state\}\}">L</figure-callout></span><figure-callout\; label="L\; NA"\; filenames="HDA00002261301000031.png"\; state="\{\{state\}\}"></figure-callout>}}_{{\mathrm{<span><span></span></span>}}_{}}<span><span>,</span>,</span>{\mathrm{<span><span>I</span>I</span>}}_{{\mathrm{<span><span>NA</span>NA</span>}}_{\mathrm{<span><span>1</span>1</span>}}}<span><span>\}</span>\}</span><span><span>></span>></span><span><span>.</span>.</span>$

（四）匿名映射模块34(4)Anonymous mapping module 34

匿名映射模块34收到位置服务器20返回的候选查询结果信息20A后，根据移动用户的位置U_ID(X,Y)对候选查询结果信息20A进行过滤，得到查询结果信息10B发送给相应的移动用户。After receiving the candidate query resultinformation 20A returned by thelocation server 20, theanonymous mapping module 34 filters the candidate query resultinformation 20A according to the mobile user's location U_ID (X, Y), obtains the query resultinformation 10B and sends it to the corresponding mobile user .

在本发明中，候选查询结果信息20A也是候选查询结果C＝{c₁,c₂,c₃,…,c_h}，在候选查询结果C＝{c₁,c₂,c₃,…,c_h}中c₁为q₁所对应的位置服务器的查询候选结果，c₂为q₂所对应的位置服务器的查询候选结果，c₃为q₃所对应的位置服务器的查询候选结果，c_h为q_w所对应的位置服务器的查询候选结果，h为w对应的位置服务器的查询候选结果的标识号。In the present invention, candidate query resultinformation 20A is also candidate query result C={c₁ ,c₂ ,c₃ ,...,c_h }, where candidate query result C={c₁ ,c₂ ,c₃ ,..., In c_h }, c₁ is the query candidate result of the location server corresponding to q₁ , c₂ is the query candidate result of the location server corresponding to q₂ , c₃ is the query candidate result of the location server corresponding to q₃ , c_h is the query candidate result of the location server corresponding to q_w , and h is the identification number of the query candidate result of the location server corresponding to w.

在本发明中，查询结果信息10B也是最终查询结果F_最终＝{f₁,f₂,f₃,…f_e}，在最终查询结果F_最终＝{f₁,f₂,f₃,…f_e}中f₁为q₁所对应的匿名服务器的最终查询结果，f₂为q₂所对应的匿名服务器的最终查询结果，f₃为q₃所对应的匿名服务器的最终查询结果，f_e为q_w所对应的匿名服务器的最终查询结果，e为w对应的匿名服务器的最终查询结果的标识号。In the present invention, the query resultinformation 10B is also the final query result F_final ={f₁ , f₂ ,f₃ ,...f_e }, where the final query result F_final ={f₁ ,f₂ ,f₃ ,...f In_e }, f₁ is the final query result of the anonymous server corresponding to q₁ , f₂ is the final query result of the anonymous server corresponding to q₂ , f₃ is the final query result of the anonymous server corresponding to q₃ , f_e is the final query result of the anonymous server corresponding to q_w , and e is the identification number of the final query result of the anonymous server corresponding to w.

（五）位置服务器20(5)Location server 20

位置服务器20根据收到的匿名查询集合Q＝{q₁,q₂,q₃,…,q_w}进行查询处理，并把候选查询结果C＝{c₁,c₂,c₃,…,c_h}发送给匿名服务器30中的匿名映射模块34。Thelocation server 20 performs query processing according to the received anonymous query set Q={q₁ ,q₂ ,q₃ ,...,q_w }, and sends candidate query results C={c₁ ,c₂ ,c₃ ,..., c_h } to theanonymous mapping module 34 in theanonymous server 30.

在本发明中，任意一移动用户第一次请求位置服务时，需要在匿名服务器进行注册，并且匿名服务器为每次的连续查询建立一个会话(session)。在连续的查询会话中，若某个移动用户可以通过一些标识符与其他移动用户区分开来，因此，匿名服务器会与位置服务器保持着一些会话标识符。为了方便说明每一个移动用户在位置服务请求过程中的隐私保护，本发明下文将以任意一移动用户U_ID进行列举说明。In the present invention, when any mobile user requests location service for the first time, he needs to register with the anonymous server, and the anonymous server establishes a session (session) for each continuous query. In continuous query sessions, if a certain mobile user can be distinguished from other mobile users by some identifiers, therefore, the anonymous server will keep some session identifiers with the location server. In order to facilitate the description of the privacy protection of each mobile user in the location service request process, the present invention will be described below with any mobile user_UID .

本发明是在位置服务中提供一种面向路网的查询感知的位置隐私保护系统，对基于位置服务中的移动用户提出的查询请求进行匿名的步骤为（参见图3所示）：The present invention provides a road network-oriented query-aware location privacy protection system in location-based services. The steps for anonymizing the query requests made by mobile users in location-based services are as follows (see Figure 3):

步骤一：移动用户发出请求信息Step 1: The mobile user sends a request for information

移动用户MS＝{U₁,U₂,U₃,…,U_ID}中的任意一移动用户U_ID把查询内容d_b发送给匿名服务器30中的匿名请求模块31；查询内容d_b属于查询内容集合D＝{d₁,d₂,d₃,…d_b}中的内容。Any mobile user U ID in mobile user MS={U₁ , U₂ , U₃ ,..., U_ID} sends the query content d_b to theanonymous request module 31 in theanonymous server 30; the query content d_b belongs to the query Content set D=content in {d₁ , d₂ , d₃ , . . . d_b }.

所述任意一移动用户的查询内容d_b的格式为：The format of the query content_db of any one mobile user is:

$<span><span><</span><</span>\mathrm{<span><span>ID</span>ID</span>}<span><span>,</span>,</span>{\mathrm{<span><span>R</span>R</span>}}_{{\mathrm{<span><span>con</span>con</span>}}_{\mathrm{<span><span>ID</span>ID</span>}}}<span><span>,</span>,</span><span><span><</span><</span>{\mathrm{<span><span>X</span>x</span>}}_{\mathrm{<span><span>ID</span>ID</span>}}<span><span>,</span>,</span>{\mathrm{<span><span>Y</span>Y</span>}}_{\mathrm{<span><span>ID</span>ID</span>}}<span><span>></span>></span><span><span>,</span>,</span>{\mathrm{<span><span>t</span>t</span>}}_{\mathrm{<span><span>ID</span>ID</span>}}<span><span>,</span>,</span><span><span>\{</span>\{</span>{\mathrm{<span><span>L</span>L</span>}}_{\mathrm{<span><span>ID</span>ID</span>}}<span><span>,</span>,</span>{\mathrm{<span><span>I</span>I</span>}}_{\mathrm{<span><span>ID</span>ID</span>}}<span><span>\}</span>\}</span><span><span>></span>></span><span><span>;</span>;</span>$

步骤二：匿名赋值-映射处理Step 2: Anonymous assignment - mapping processing

步骤201：匿名请求模块31对接收到的查询请求信息10C一方面将位置-路段信息31A发送给路段匹配模块32；另一方面将匿名身份信息31B发送给匿名赋值模块33；Step 201: Theanonymous request module 31 sends the location-road section information 31A to the roadsection matching module 32 on the one hand for the receivedquery request information 10C; on the other hand, sends theanonymous identity information 31B to the anonymousvalue assignment module 33;

步骤202-1：路段匹配模块32根据发出请求的移动用户的位置坐标确定移动用户所在的路段

Step 202-1: The roadsegment matching module 32 determines the road segment where the mobile user is located according to the location coordinates of the requesting mobile user

步骤202-2：（A）从匿名路段集合S={s₁,s₂,s₃,…,s_a}中选取出匿名候选路段，形成优先级第一队列AA＝(aa₁,aa₂,aa₃,…,aa_i)；（B）对优先级第一队列AA＝(aa₁,aa₂,aa₃,…,aa_i)进行路段的两个端点提取，得到优先级第二队列BB＝(bb₁,bb₂,bb₃,bb₄,bb₅,bb₆,…,bb_j,bb_(j+1),…)；（C）将步骤32-1中得到的路段添加至匿名路段集合S={s₁,s₂,s₃,…,s_a}中，并用优先级第一队列AA＝(aa₁,aa₂,aa₃，…,aa_i)和优先级第二队列BB＝(bb₁,bb₂,bb₃,bb₄,bb₅,bb₆,…,bb_j,bb_(j+1),…)来更新匿名路段集合S={s₁,s₂,s₃,…,s_a}，得到第二匿名路段集合SH={sh₁,sh₂,sh₃,…,sh_a}；Step 202-2: (A) Select anonymous road segments from the set of anonymous road segments S={s₁ , s₂ , s₃ ,…,s_a } to form the first priority queue AA=(aa₁ ,aa₂ ,aa₃ ,…,aa_i ); (B) Extract the two endpoints of the road segment from the first priority queue AA=(aa₁ ,aa₂ ,aa₃ ,…,aa_i ), and get the second priority queue BB＝(bb₁ ,bb₂ ,bb₃ ,bb₄ ,bb₅ ,bb₆ ,…,bb_j ,bb_(j+1) ,…); (C) The road section obtained in step 32-1 Add to the anonymous road section set S={s₁ ,s₂ ,s₃ ,…,s_a }, and use the priority first queue AA=(aa₁ ,aa₂ ,aa₃ ,…,aa_i ) and priority The second queue BB=(bb₁ ,bb₂ ,bb₃ ,bb₄ ,bb₅ ,bb₆ ,…,bb_j ,bb_(j+1) ,…) to update the anonymous road section set S={s₁ ,s₂ ,s₃ ,…,s_a }, get the second anonymous road section set SH={sh₁ ,sh₂ ,sh₃ ,…,sh_a };

步骤202-3:判断第二匿名路段集合SH={sh₁,sh₂,sh₃,…,sh_a}是否满足任意一移动用户U_ID的隐私要求{L_ID,I_ID}；Step 202-3: Judging whether the second set of anonymous road segments SH={sh₁ ,sh₂ ,sh₃ ,...,sh_a } meets the privacy requirement {L_ID ,I_ID } of any mobile user U_ID ;

判断过程如下：若r_NUM≥m_max同时r_NUM≥k_max，则满足隐私要求{L_ID，I_ID}；反之为不满足，则进入步骤202-4；The judging process is as follows: if r_NUM ≥ m_max and r_NUM ≥ k_max , then the privacy requirement {L_ID , I_ID } is satisfied; otherwise, it is not satisfied, then enter step 202-4;

在本发明中，匿名路段集合S={s₁,s₂,s₃，…,s_a}中包含路段的数量大于等于其包含的所有移动隐私要求m的最大值（m_max=20），同时匿名路段集合S={s₁,s₂,s₃,…,s_a}包含查询的数量大于等于其所包含的所有移动用户隐私要求k的最大值（k_max=50），那么该匿名路段集合就可以满足其所包含的所有用户的隐私要求。In the present invention, the anonymous road section set S={s₁ , s₂ , s₃ , ..., s_a } contains the number of road sections greater than or equal to the maximum value of all mobile privacy requirements m (m_max =20), At the same time, the set of anonymous road segments S={s₁ , s₂ , s₃ ,…,s_a } contains queries that are greater than or equal to the maximum value of all mobile user privacy requirements k (k_max =50), then the anonymous The road section collection can meet the privacy requirements of all users included in it.

步骤202-4:（A）在第二匿名路段集合SH={sh₁,sh₂,sh₃,…,sh_a}不满足隐私要求{L_ID,I_ID}时，路段匹配模块32将产生随机因子η（一般地，η为0.1～0.5的一个数）；（B）在路段区间范围内从侁先第一队列AA中随机选择一条候选路段r′，同时，把候选路段r′的两个端点添加到侁先第二队列BB中，并将该候选路段r′添加到第二匿名路段集合SH={sh₁,sh₂,sh₃,…,sh_a}中，得到第三匿名路段集合SHH={shh₁,shh₂,shh₃,…,shh_a}；（C）把与候选路段r′相邻的所有路段插入到队列AA中，如果有匹配路段加入，则返回至步骤202-2中进行继续匿名，直到找到满足移动用户隐私要求的匿名路段集合为止；如果没有匹配路段加入，则匿名失败，拒绝位置匿名服务。Step 202-4: (A) When the second set of anonymous road segments SH={sh₁ ,sh₂ ,sh₃ ,...,sh_a } does not meet the privacy requirement {L_ID ,I_ID }, the roadsegment matching module 32 will generate Random factor η (generally, η is a number from 0.1 to 0.5); (B) in the section interval Randomly select a candidate road section r' from the first queue AA within the range, and at the same time, add the two endpoints of the candidate road section r' to the first second queue BB, and add the candidate road section r' to the second queue In the anonymous road section set SH={sh₁ ,sh₂ ,sh₃ ,…,sh_a }, the third anonymous road section set SHH={shh₁ ,shh₂ ,shh₃ ,…,shh_a } is obtained; (C) put All road segments adjacent to the candidate road segment r' are inserted into the queue AA. If there is a matching road segment added, return to step 202-2 to continue anonymizing until an anonymous road segment set that meets the privacy requirements of the mobile user is found; if there is no matching If a road segment is added, the anonymity fails, and the location anonymity service is rejected.

步骤203：匿名赋值模块33对收到的查询内容集合D＝{d₁,d₂,d₃,…d_b}中的任意移动用户U_ID的标识ID进行假名赋值处理，得到用户假名ID′；同时记录下移动用户的真实标识与用户假名之间的对应关系，即匿名对应关系A_ID→NA_ID；如第一移动用户U₁的身分标识为A₁，在匿名模块中所述身分标识A₁所对应的假名为NA₁，则查询内容d_b的格式$<\mathrm{ID},R_{{\mathrm{con}}_{\mathrm{ID}}},<X_{\mathrm{ID}},Y_{\mathrm{ID}}>,t_{\mathrm{ID}},\{L_{\mathrm{ID}},I_{\mathrm{ID}}\}>$变换为匿名对应查询内容Nd_b的格式为$<{\mathrm{NA}}_1,R_{{\mathrm{con}}_{{\mathrm{NA}}_1}},<X_{{\mathrm{NA}}_1},Y_{{\mathrm{NA}}_1}>,t_{{\mathrm{NA}}_1},\{L_{{\mathrm{NA}}_1},I_{{\mathrm{NA}}_1}\}>.$Step 203: The anonymousvalue assignment module 33 performs pseudonym assignment processing on the identification ID of any mobile user_UID in the received query content set D={d₁ ,d₂ ,d₃ ,...d_b }, and obtains the user pseudonym ID'; Simultaneously record the corresponding relationship between the real identification of the mobile user and the pseudonym of the user, that is, the anonymous corresponding relationship A_ID →NA_ID ; if the identity identification of the first mobile user U₁ is A₁ , the identity identification in the anonymous module The pseudonym corresponding to A₁ is NA₁ , then the format of the query content d_b$<\mathrm{ID},R_{{\mathrm{con}}_{\mathrm{ID}}},<x_{\mathrm{ID}},Y_{\mathrm{ID}}>,t_{\mathrm{ID}},\{L_{\mathrm{ID}},I_{\mathrm{ID}}\}>$ Transformed into anonymous corresponding query content Nd_b format is$<{\mathrm{<figure-callout\; label="NA"\; filenames="HDA00002261301000031.png"\; state="\{\{state\}\}">NA</figure-callout>}}_1,{\mathrm{<figure-callout\; label="R\; con\; NA"\; filenames="HDA00002261301000031.png"\; state="\{\{state\}\}">R</figure-callout>}}_{{\mathrm{con}}_{{\mathrm{NA}}_{}}},<x_{{\mathrm{<figure-callout\; label="NA"\; filenames="HDA00002261301000031.png"\; state="\{\{state\}\}">NA</figure-callout>}}_1},{\mathrm{<figure-callout\; label="Y\; NA"\; filenames="HDA00002261301000031.png"\; state="\{\{state\}\}">Y</figure-callout>}}_{{\mathrm{NA}}_{}}>,{\mathrm{<figure-callout\; label="t\; NA"\; filenames="HDA00002261301000031.png"\; state="\{\{state\}\}">t</figure-callout>}}_{{\mathrm{NA}}_{}},\{{\mathrm{<figure-callout\; label="L\; NA"\; filenames="HDA00002261301000031.png"\; state="\{\{state\}\}">L</figure-callout>}}_{{\mathrm{NA}}_{}},I_{{\mathrm{NA}}_1}\}>.$

步骤三：位置查询Step 3: Location query

位置服务器根据收到的请求进行查询处理，并把查询的结果发送给匿名服务器。The location server performs query processing according to the received request, and sends the result of the query to the anonymous server.

位置服务器根据收到的匿名查询集合Q＝{q₁,q₂,q₃,…,q_w}进行查询处理，并把候选查询结果C＝{c₁,c₂,c₃,…,c_h}发送给匿名服务器。The location server performs query processing according to the received anonymous query set Q={q₁ ,q₂ ,q₃ ,…,q_w }, and sends candidate query results C={c₁ ,c₂ ,c₃ ,…,c_h } to the anonymous server.

步骤四：匿名反映射处理Step 4: Anonymous anti-mapping processing

匿名映射模块34收到位置服务器返回的查询结果C＝{c₁,c₂,c₃,…,c_h}后，根据移动用户的准确位置对查询结果进行过滤，并且把准确的最终查询结果F_最终＝{f₁,f₂,f₃,…f_e}发送给相应的移动用户。After receiving the query result C={c₁ ,c₂ ,c₃ ,...,c_h } returned by the location server, theanonymous mapping module 34 filters the query result according to the exact location of the mobile user, and puts the accurate final query result_Ffinal ={f₁ , f₂ , f₃ ,...f_e } are sent to the corresponding mobile users.

在本发明中，匿名服务器中的查询处理模块根据移动用户位置x_ID，y_ID对位置服务器返回的候选查询结果C＝{c₁,c₂,c₃,…,c_h}进行身份过滤处理，找到精确结果，得到最终查询结果F_最终＝{f₁,f₂,f₃,…f_e}，f₁＝(d₁,s₁)；然后将最终查询结果F_最终＝{f₁,f₂,f₃,…f_e}发送给移动用户。In the present invention, the query processing module in the anonymous server performs identity filtering processing on the candidate query result C={c₁ ,c₂ ,c₃ ,...,c_h } returned by the location server according to the mobile user's location x_ID and y_ID , find the exact result, and get the final query result F_final = {f₁ , f₂ , f₃ ,...f_e }, f₁ = (d₁ , s₁ ); then the final query result F_final = {f₁ , f₂ , f₃ ,…f_e } are sent to mobile users.

在本发明中，所述身份过滤处理是指将已经存储的假名和移动用户真实的身份标识的对应寻找，找到精确结果。In the present invention, the identity filtering process refers to finding the correspondence between the stored pseudonym and the real identity of the mobile user, and finding an accurate result.

在本发明中匿名服务器的查询处理模块完成了对候选查询结果C＝{c₁,c₂,c₃,…,c_h}的过滤处理，保证了返回给移动用户的最终查询结果F_最终＝{f₁,f₂,f₃,…f_e}的准确性，很好的满足了用户对最终结果的准确性要求，极大的提升了服务质量。In the present invention, the query processing module of the anonymous server completes the filtering process of candidate query results C={c₁ , c₂ , c₃ ,..., c_h }, ensuring that the final query result F_final = The accuracy of {f₁ , f₂ , f₃ ,…f_e } satisfies the user's accuracy requirements for the final result and greatly improves the service quality.

实施例Example

参见图4所示，在一路段拓朴结构图（即一个路网区域）中，每一路段以路头和路尾进行标注，有7个路段，即第一路段记为r¹、第二路段记为r²、第三路段记为r³、第四路段记为r⁴、第五路段记为r⁵、第六路段记为r⁶、第七路段记为r⁷。As shown in Figure 4, in the topological structure diagram of a road section (that is, a road network area), each road section is marked with a road head and a road end, and there are 7 road sections, that is, the first road section is denoted as r¹ , the second road section The section is denoted as r² , the third section is denoted as r³ , the fourth section is denoted as r⁴ , the fifth section is denoted as r⁵ , the sixth section is denoted as r⁶ , and the seventh section is denoted as r⁷ .

r¹的两个端点分别为r¹_头、r¹_尾；The two endpoints of r¹ are r¹_head and r¹_tail respectively;

r²的两个端点分别为r²_头、r²_尾；The two endpoints of r² are r²_head and r²_tail respectively;

r³的两个端点分别为r³_头、r³_尾；The two endpoints of r³ are r³_head and r³_tail respectively;

r⁴的两个端点分别为r⁴_头、r⁴_尾；The two endpoints of r⁴ are r⁴_head and r⁴_tail respectively;

r⁵的两个端点分别为r⁵_头、r⁵_尾；The two endpoints of r⁵ are r⁵_head and r⁵_tail respectively;

r⁶的两个端点分别为r⁶_头、r⁶_尾；The two endpoints of r⁶ are r⁶_head and r⁶_tail respectively;

r⁷的两个端点分别为r⁷_头、r⁷_尾。The two endpoints of r⁷ are r⁷_head and r⁷_tail respectively.

在路网区域中，r¹_头、r⁴_尾、r⁵_头和r⁶_头为重叠交点；r¹_尾、r²_头和r³_头为重叠交点；r²_尾和r⁷_尾为重叠交点。由于存在重叠交点，则第一路段r¹的相邻路段是第二路段r²、第三路段r³、第四路段r⁴、第五路段r⁵和第六路段r⁶，即有5个相邻路段数值。In the road network area, r¹_head , r⁴_tail , r⁵_head and r⁶_head are overlapping intersection points; r¹_tail , r²_head and r³_head are overlapping intersection points; r²_tail and r⁷_tail are overlapping intersection points . Due to the existence of overlapping intersections, the adjacent road sections of the first road section r¹ are the second road section r² , the third road section r³ , the fourth road section r⁴ , the fifth road section r⁵ and the sixth road section r⁶ , that is, there are 5 Adjacent segment value.

假设第一移动用户U₁需要位置服务时，匿名服务器进行的匿名保护为：Assuming that when the first mobile user U₁ needs location services, the anonymous protection performed by the anonymous server is:

步骤1：第一移动用户U₁把查询内容集合D＝{d₁,d₂，d₃,…d_b}发送给匿名服务器30中的匿名请求模块31，请求信息的格式为$<U_1,R_{{\mathrm{con}}_{U_1}},<X_{U_1},Y_{U_1}>,t_{U_1},\{L_{U_1},I_{U_1}\}>;$

赋值为12，赋值为4；Step 1: The first mobile user U₁ sends the query content set D={d₁ ,d₂ ,d₃ ,...d_b } to theanonymous request module 31 in theanonymous server 30, and the format of the request information is$<{\mathrm{<figure-callout\; label="u"\; filenames="HDA00002261301000031.png"\; state="\{\{state\}\}">u</figure-callout>}}_1,{\mathrm{<figure-callout\; label="R\; con\; u"\; filenames="HDA00002261301000031.png"\; state="\{\{state\}\}">R</figure-callout>}}_{{\mathrm{con}}_{u_{}}},<{\mathrm{<figure-callout\; label="x\; u"\; filenames="HDA00002261301000031.png"\; state="\{\{state\}\}">x</figure-callout>}}_{u_{}},{\mathrm{<figure-callout\; label="Y\; u"\; filenames="HDA00002261301000031.png"\; state="\{\{state\}\}">Y</figure-callout>}}_{u_{}}>,{\mathrm{<figure-callout\; label="t\; u"\; filenames="HDA00002261301000031.png"\; state="\{\{state\}\}">t</figure-callout>}}_{u_{}},\{{\mathrm{<figure-callout\; label="L\; u"\; filenames="HDA00002261301000031.png"\; state="\{\{state\}\}">L</figure-callout>}}_{u_{}},I_{u_1}\}>;$

assigned a value of 12, The assignment is 4;

步骤2：匿名服务器中的匿名模块对收到的查询内容D＝{d₁,d₂,d₃,…d_b}中的移动用户U₁的标识ID进行假名赋值处理，得到用户假名ID′；同时记录移动用户的真实标识与用户假名之间的对应关系；如移动用户U₁的身分标识为U₁，在匿名模块中U₁对应的假名为NU₁，则查询内容的格式变换为$<{\mathrm{NU}}_1,R_{{\mathrm{con}}_{{\mathrm{NU}}_1}},<X_{{\mathrm{NU}}_1},Y_{{\mathrm{NU}}_1}>,t,\{L_{{\mathrm{NU}}_1},I_{{\mathrm{NU}}_1}\}>;$Step 2: The anonymous module in the anonymous server performs pseudonym assignment processing on the ID of the mobile user U₁ in the received query content D={d₁ ,d₂ ,d₃ ,...d_b }, and obtains the user pseudonym ID′ ; Simultaneously record the corresponding relationship between the real identity of the mobile user and the pseudonym of the user; if the identity of the mobile user U₁ is U₁ , and the pseudonym corresponding to U₁ in the anonymous module is NU₁ , then the format of the query content is transformed into$<{\mathrm{<figure-callout\; label="NU"\; filenames="HDA00002261301000031.png"\; state="\{\{state\}\}">NU</figure-callout>}}_1,{\mathrm{<figure-callout\; label="R\; con\; NU"\; filenames="HDA00002261301000031.png"\; state="\{\{state\}\}">R</figure-callout>}}_{{\mathrm{con}}_{{\mathrm{NU}}_{}}},<x_{{\mathrm{<figure-callout\; label="NU"\; filenames="HDA00002261301000031.png"\; state="\{\{state\}\}">NU</figure-callout>}}_1},{\mathrm{<figure-callout\; label="Y\; NU"\; filenames="HDA00002261301000031.png"\; state="\{\{state\}\}">Y</figure-callout>}}_{{\mathrm{NU}}_{}}>,t,\{{\mathrm{<figure-callout\; label="L\; NU"\; filenames="HDA00002261301000031.png"\; state="\{\{state\}\}">L</figure-callout>}}_{{\mathrm{NU}}_{}},I_{{\mathrm{NU}}_1}\}>;$

步骤3：匿名服务器根据发出请求的移动用户的位置坐标确定用户所在的路段

从图4中可以看到，用户U₁处于路段r¹中。Step 3: The anonymous server determines the road segment the user is on based on the location coordinates of the requesting mobile user

It can be seen from Fig. 4 that the user U₁ is in the road segment r¹ .

步骤4：匿名服务器把路段r¹加入到匿名路段集合S={s₁,s₂,s₃，…,s_a}中，同时维护两个优先级队列AA和BB；用路段r¹的两个端点r¹_头、r¹_尾来初始化BB，把路段r¹相邻的所有路段（第二路段r²、第三路段r³、第四路段r⁴、第五路段r⁵和第六路段r⁶）插入到队列AA中；从而得到更新后的匿名路段集合S={s₁,s₂,s₃,…,s_a}，即第二匿名路段集合SH={sh₁,sh₂,sh₃,…,sh_a}；Step 4: The anonymous server adds^the road segment r¹ to the anonymous road segment set S={s₁ , s₂ , s₃ ,…,s_a }, and maintains two priority queues AA and BB at the same time; BB is initialized with two endpoints r¹_head and r¹_tail , and all road sections adjacent to road section r¹ (the second road section r² , the third road section r³ , the fourth road section r⁴ , the fifth road section r⁵ and the sixth road section r⁶ ) is inserted into the queue AA; thus the updated anonymous road section set S={s₁ ,s₂ ,s₃ ,…,s_a }, that is, the second anonymous road section set SH={sh₁ ,sh₂ , sh₃ ,...,sh_a };

步骤5：判断SH={sh₁,sh₂,sh₃,…,sh_a}是否满足移动用户的隐私要求，Step 5: Determine whether SH={sh₁ ,sh₂ ,sh₃ ,…,sh_a } meets the privacy requirements of mobile users,

判断过程如下：SH={sh₁,sh₂,sh₃,…,sh_a}中包含路段的数量大于等于其包含的所有移动隐私要求m＝4的，同时SH={sh₁,sh₂,sh₃,…,sh_a}包含移动用户查询的数量大于等于其所包含的所有移动用户隐私要求k＝12的，那么该SH={sh₁,sh₂,sh₃,…,sh_a}就可以满足其所包含的所有用户的隐私要求。The judging process is as follows: SH={sh₁ ,sh₂ ,sh₃ ,…,sh_a } contains road sections greater than or equal to all mobile privacy requirements m=4, and SH={sh₁ ,sh₂ , sh₃ ,…,sh_a } contains mobile user queries whose number is greater than or equal to all mobile user privacy requirements k=12, then the SH={sh₁ ,sh₂ ,sh₃ ,…,sh_a } is Can meet the privacy requirements of all the users it contains.

如果满足移动用户的隐私要求，匿名完成，并把匿名后的请求发送给位置服务器。If the privacy requirements of the mobile user are met, the anonymization is completed, and the anonymized request is sent to the location server.

步骤6：如果SH={sh₁,sh₂,sh₃,…,sh_a}不满足上述隐私要求，则进入步骤7；从图4中可以看到，路段r¹上共有两个移动用户U₁、U₂，不满足用户U₁的隐私要求，所以进入步骤7。Step 6: If SH={sh₁ ,sh₂ ,sh₃ ,…,sh_a } does not meet the above privacy requirements, go to step 7; as can be seen from Figure 4, there are two mobile users U on the road section r¹_1. U₂ does not meet the privacy requirements of user U₁ , so go to step 7.

如果SH={sh₁,sh₂,sh₃,…,sh_a}同时满足r_NUM≥4同时r_NUM≥12移动用户的隐私要求，匿名完成，并向位置服务器输出匿名查询信息；If SH={sh₁ ,sh₂ ,sh₃ ,…,sh_a } simultaneously meet the privacy requirements of r_NUM ≥ 4 and r_NUM ≥ 12 mobile users, anonymity is completed, and anonymous query information is output to the location server;

步骤7：匿名服务器产生随机因子η,然后在

范围内从队列AA中随机选择一条路段r′添加到匿名路段集合S={s₁,s₂,s₃，…,s_a}中，同时，把路段r′的两个端点添加到队列BB中，把与路段r′相邻的所有路段以路段上查询请求数量插入到队列AA中，得到第三SHH={shh₁,shh₂,shh₃,…,shh_a}；如果没有路段与之匹配的路段加入，则匿名失败；Step 7: The anonymous server generates a random factor η, and then

Randomly select a road section r′ from the queue AA within the range and add it to the anonymous road section set S={s₁ ,s₂ ,s₃ ,…,s_a }, and at the same time, add the two endpoints of the road section r′ to the queue BB , insert all the road segments adjacent to the road segment r′ into the queue AA according to the number of query requests on the road segment, and get the third SHH={shh₁ ,shh₂ ,shh₃ ,…,shh_a }; if there is no road segment with it If the matching road segment is added, the anonymity fails;

如果有路段与之匹配的路段加入，否则回到步骤4继续匿名过程，直到找到满足移动用户隐私要求的匿名路段集合。If there is a road segment matching it, add it, otherwise go back to step 4 and continue the anonymization process until an anonymous road segment set that meets the privacy requirements of the mobile user is found.

假设图4中的随机因子η=0.5，由上所述可知，图4中路段r2,r3,r4,r5、r6均可以作为候选路段被添加到匿名路段集合S中。假设随机选择r2并把它加入到匿名路段集合S中，此时匿名路段集合S包括路段r1和r2，仍然没有满足用户U₁的隐私要求，所以进入步骤7继续该匿名过程，直到找到满足隐私要求的匿名路段集合。图4中的实线表示该例子最终的匿名路段集合。Assuming the random factor η=0.5 in Figure 4, it can be seen from the above that the road sections r2, r3, r4, r5, and r6 in Figure 4 can all be added to the anonymous road section set S as candidate road sections. Assume that r2 is randomly selected and added to the anonymous road section set S. At this time, the anonymous road section set S includes road sections r1 and r2, which still does not meet the privacy requirements of user U₁ , so go to step 7 and continue the anonymous process until a road that satisfies the privacy requirements is found. The collection of anonymous road segments requested. The solid line in Fig. 4 represents the final set of anonymous road segments in this example.

步骤8：位置服务器根据收到的匿名查询集合Q＝{q₁,q₂,q₃,…,q_w}进行查询处理，并把候选查询结果C＝{c₁,c₂,c₃,…,c_h}发送给匿名服务器。Step 8: The location server performs query processing according to the received anonymous query set Q={q₁ ,q₂ ,q₃ ,…,q_w }, and sends candidate query results C={c₁ ,c₂ ,c₃ , ...,c_h } to the anonymous server.

步骤9：匿名服务器收到位置服务器返回的查询结果C＝{c₁,c₂,c₃,…,c_h}后，根据移动用户的准确位置对查询结果进行过滤，并且把准确的最终查询结果F_最终＝{f₁,f₂,f₃,…f_e}发送给相应的移动用户U₁。Step 9: After receiving the query result C＝{c₁ ,c₂ ,c₃ ,…,c_h } returned by the location server, the anonymous server filters the query result according to the exact location of the mobile user, and puts the exact final query result The result F_finally ={f₁ , f₂ , f₃ ,...f_e } is sent to the corresponding mobile user U₁ .

Claims (4)

Translated fromChinese

1.一种面向路网的查询感知的位置隐私保护系统，该位置隐私保护系统包括有移动用户（10）、匿名服务器（30）以及位置服务器（20）；其特征在于：所述匿名服务器（30）包括有匿名请求模块（31）、路段匹配模块（32）、匿名赋值模块（33）和匿名映射模块（34）；1. A road network-oriented query-aware location privacy protection system, the location privacy protection system includes a mobile user (10), an anonymous server (30) and a location server (20); it is characterized in that: the anonymous server ( 30) Including anonymous request module (31), road section matching module (32), anonymous assignment module (33) and anonymous mapping module (34);匿名请求模块（31）对接收到的查询请求信息（10C）一方面将位置-路段信息（31A）发送给路段匹配模块（32）；另一方面将匿名身份信息（31B）发送给匿名赋值模块（33）；The anonymous request module (31) sends the location-road section information (31A) to the road section matching module (32) on the one hand for the received query request information (10C); on the other hand, sends the anonymous identity information (31B) to the anonymous assignment module (33);所述的位置-路段信息（31A）包括有查询内容集合D＝{d₁,d₂,d₃,…d_b}中的X_ID,Y_ID和t_ID，以及匿名路段集合S={s₁,s₂,s₃,…,s_a}；The position-road section information (31A) includes query content set D={d₁ ,d₂ ,d₃ ,...d_b } X_ID , Y_ID and t_ID , and the set of anonymous road segments S={s₁ , s₂ , s₃ ,…,s_a };所述的匿名身份信息（31B）包括有查询内容集合D＝{d₁,d₂,d₃,…d_b}中的ID、X_ID,Y_ID、L_ID、I_ID和t_ID；The anonymous identity information (31B) includes ID, X_ID , Y_ID , L_ID , I_ID and t_ID in the query content set D={d₁ , d₂ , d₃ ,...d_b };所述任意一查询内容d_b的格式为：The format of any query content_db is:$<span><span><</span><</span>\mathrm{<span><span>ID</span>ID</span>}<span><span>,</span>,</span>{\mathrm{<span><span>R</span>R</span>}}_{{\mathrm{<span><span>con</span>con</span>}}_{\mathrm{<span><span>ID</span>ID</span>}}}<span><span>,</span>,</span><span><span><</span><</span>{\mathrm{<span><span>X</span>x</span>}}_{\mathrm{<span><span>ID</span>ID</span>}}<span><span>,</span>,</span>{\mathrm{<span><span>Y</span>Y</span>}}_{\mathrm{<span><span>ID</span>ID</span>}}<span><span>></span>></span><span><span>,</span>,</span>{\mathrm{<span><span>t</span>t</span>}}_{\mathrm{<span><span>ID</span>ID</span>}}<span><span>,</span>,</span><span><span>\{</span>\{</span>{\mathrm{<span><span>L</span>L</span>}}_{\mathrm{<span><span>ID</span>ID</span>}}<span><span>,</span>,</span>{\mathrm{<span><span>I</span>I</span>}}_{\mathrm{<span><span>ID</span>ID</span>}}<span><span>\}</span>\}</span><span><span>></span>></span><span><span>;</span>;</span>$路段匹配模块（32）首先对接收到的位置-路段信息（31A）通过任意一移动用户U_ID的位置坐标X_ID,Y_ID确定出，任意一移动用户U_ID所在路网中的路段然后对路段进行匿名路段集合S={s₁,s₂,s₃,…,s_a}中的优先级第一队列AA＝(aa₁,aa₂,aa₃,…,aa_i)和优先级第二队列BB＝(bb₁,bb₂,bb₃,bb₄,bb₅,bb₆,…,bb_j,bb_(j+1),…)的更新，得到第二匿名路段集合SH={sh₁,sh₂,sh₃,…,sh_a}；然后对第二匿名路段集合SH={sh₁,sh₂,sh₃,…,sh_a}进行隐私要求{L_ID,I_ID}的判断，若满足r_NUM≥m_max同时r_NUM≥k_max，则为满足隐私要求{L_ID,I_ID}；在不满足隐私要求{L_ID,I_ID}的条件下，通过随机因子η在路段区间

范围内从侁先第一队列AA中随机选择一条候选路段r′，同时，把候选路段r′的两个端点添加到侁先第二队列BB中，并将该候选路段r′添加到第二匿名路段集合SH={sh₁,sh₂,sh₃,…,sh_a}中，得到第三匿名路段集合SHH={shh₁,shh₂,shh₃,…,shh_a}；最后把与候选路段r′相邻的所有路段插入到队列AA中，如果有匹配路段加入，继续进行匿名，直到找到满足移动用户隐私要求的匿名路段集合为止；如果没有匹配路段加入，则匿名失败，拒绝位置匿名服务；The road segment matching module (32) first determines the road segment in the road network where any mobile user U_ID is located by using the location coordinates X_ID and Y_ID of any mobile user_UID from the received position-road segment information (31A) Then for the section Carry out_{the priority first queue AA=(aa 1 ,aa 2,aa 3,…,aa i)andthe} priority second Queue BB=(bb₁ , bb₂ , bb₃ , bb₄ , bb₅ , bb₆ ,..., bb_j , bb_(j+1) ,...) update to get the second anonymous segment set SH={sh₁ ,sh₂ ,sh₃ ,…,sh_a }; then judge the privacy requirement {L_ID ,I_ID } for the second anonymous road segment set SH={sh₁ ,sh₂ ,sh₃ ,…,sh_a }, If r_NUM ≥ m_max and r_NUM ≥ k_max , then the privacy requirement {L_ID , I_ID } is satisfied; if the privacy requirement {L_ID , I_ID } is not met, the random factor η is used to determine the

Randomly select a candidate road section r' from the first queue AA within the range, and at the same time, add the two endpoints of the candidate road section r' to the first second queue BB, and add the candidate road section r' to the second queue In the anonymous section set SH={sh₁ ,sh₂ ,sh₃ ,…,sh_a }, get the third anonymous section set SHH={shh₁ ,shh₂ ,shh₃ ,…,shh_a }; Insert all road segments adjacent to road segment r' into the queue AA. If there is a matching road segment added, continue to anonymize until an anonymous road segment set that meets the privacy requirements of mobile users is found; if no matching road segment is added, anonymization fails and location anonymization is rejected Serve;匿名赋值模块（33）对收到的查询内容集合D＝{d₁,d₂,d₃,…d_b}中的任意移动用户U_ID的标识ID进行假名赋值处理，得到用户假名ID′；同时记录下移动用户的真实标识与用户假名之间的对应关系，即匿名对应关系A_ID→NA_ID；The anonymous assignment module (33) performs pseudonym assignment processing on the identification ID of any mobile user U_ID in the received query content set D={d₁ ,d₂ ,d₃ ,...d_b }, and obtains the user pseudonym ID'; At the same time, record the corresponding relationship between the real identity of the mobile user and the user's pseudonym, that is, the anonymous corresponding relationship A_ID → NA_ID ;匿名映射模块（34）收到位置服务器返回的查询结果C＝{c₁,c₂,c₃,…,c_h}后，根据移动用户的准确位置对查询结果进行过滤，并且把准确的最终查询结果F_最终＝{f₁,f₂,f₃,…f_e}发送给相应的移动用户。After receiving the query result C={c₁ ,c₂ ,c₃ ,…,c_h } returned by the location server, the anonymous mapping module (34) filters the query result according to the exact location of the mobile user, and puts the accurate final The query result F={f₁ , f₂ , f₃ ,...f_e } is_finally sent to the corresponding mobile user.2.根据权利要求1所述的面向路网的查询感知的位置隐私保护系统，其特征在于：所述路段匹配模块（32）进行路段选取的步骤为：2. The road network-oriented query-aware location privacy protection system according to claim 1, characterized in that: the road segment matching module (32) selects the road segment as follows:步骤32-1：路段匹配模块（32）对接收到的位置-路段信息（31A）通过任意一移动用户U_ID的位置坐标X_ID,Y_ID确定出，任意一移动用户U_ID所在路网中的路段

Step 32-1: The road section matching module (32) determines from the received position-road section information (31A) through the location coordinates X_ID and Y_ID of any mobile user U_ID , that any mobile user U_ID is located in the road network section of

步骤32-2：（A）从匿名路段集合S={s₁,s₂,s₃,…,s_a}中选取出匿名候选路段，形成优先级第一队列AA＝(aa₁,aa₂,aa₃,…,aa_i)；（B）对优先级第一队列AA＝(aa₁,aa₂,aa₃,…,aa_i)进行路段的两个端点提取，得到优先级第二队列BB＝(bb₁,bb₂,bb₃,bb₄,bb₅,bb₆,…,bb_j,bb_(j+1),…)；（C）将步骤32-1中得到的路段添加至匿名路段集合S={s₁,s₂,s₃,…,s_a}中，并用优先级第一队列AA＝(aa₁,aa₂,aa₃,…,aa_i)和优先级第二队列BB＝(bb₁,bb₂,bb₃,bb₄,bb₅,bb₆,…,bb_j,bb_(j+1)，…)来更新匿名路段集合S={s₁,s₂,s₃,…,s_a}，得到第二匿名路段集合SH={sh₁,sh₂,sh₃,…,sh_a}；Step 32-2: (A) Select anonymous road segments from the set of anonymous road segments S={s₁ , s₂ , s₃ ,…,s_a } to form the first priority queue AA=(aa₁ ,aa₂ ,aa₃ ,…,aa_i ); (B) Extract the two endpoints of the road segment from the first priority queue AA=(aa₁ ,aa₂ ,aa₃ ,…,aa_i ), and get the second priority queue BB＝(bb₁ ,bb₂ ,bb₃ ,bb₄ ,bb₅ ,bb₆ ,…,bb_j ,bb_(j+1) ,…); (C) The road section obtained in step 32-1 Add to the anonymous road section set S={s₁ ,s₂ ,s₃ ,…,s_a }, and use the priority first queue AA=(aa₁ ,aa₂ ,aa₃ ,…,aa_i ) and priority The second queue BB=(bb₁ ,bb₂ ,bb₃ ,bb₄ ,bb₅ ,bb₆ ,…,bb_j ,bb_(j+1) ,…) to update the anonymous road section set S={s₁ ,s₂ ,s₃ ,…,s_a }, get the second anonymous road section set SH={sh₁ ,sh₂ ,sh₃ ,…,sh_a };步骤32-3：判断第二匿名路段集合SH={sh₁,sh₂,sh₃,…,sh_a}是否满足任意一移动用户U_ID的隐私要求{L_ID,I_ID}；Step 32-3: Determine whether the second set of anonymous road segments SH={sh₁ ,sh₂ ,sh₃ ,...,sh_a } meets the privacy requirement {L_ID ,I_ID } of any mobile user U_ID ;判断过程如下：若r_NUM≥m_max同时r_NUM≥k_max，则满足隐私要求{L_ID,I_ID}；反之为不满足，则进入步骤32-4；The judging process is as follows: if r_NUM ≥ m_max and r_NUM ≥ k_max , then the privacy requirement {L_ID , I_ID } is met; otherwise, it is not satisfied, then enter step 32-4;步骤32-4：（A）在第二匿名路段集合SH={sh₁,sh₂,sh₃,…,sh_a}不满足隐私要求{L_ID,I_ID}时，路段匹配模块32将产生随机因子η（一般地，η为0.1～0.5的一个数）；（B）在路段区间范围内从侁先第一队列AA中随机选择一条候选路段r′，同时，把候选路段r′的两个端点添加到侁先第二队列BB中，并将该候选路段r′添加到第二匿名路段集合SH={sh₁,sh₂,sh₃,…,sh_a}中，得到第三匿名路段集合SHH={shh₁,shh₂,shh₃,…,shh_a}；（C）把与候选路段r′相邻的所有路段插入到队列AA中，如果有匹配路段加入，则返回至步骤32-2中进行继续匿名，直到找到满足移动用户隐私要求的匿名路段集合为止；如果没有匹配路段加入，则匿名失败，拒绝位置匿名服务。Step 32-4: (A) When the second set of anonymous road segments SH={sh₁ ,sh₂ ,sh₃ ,...,sh_a } does not meet the privacy requirement {L_ID ,I_ID }, the road segment matching module 32 will generate Random factor η (generally, η is a number from 0.1 to 0.5); (B) in the section interval Randomly select a candidate road section r' from the first queue AA within the range, and at the same time, add the two endpoints of the candidate road section r' to the first second queue BB, and add the candidate road section r' to the second queue In the anonymous road section set SH={sh₁ ,sh₂ ,sh₃ ,…,sh_a }, the third anonymous road section set SHH={shh₁ ,shh₂ ,shh₃ ,…,shh_a } is obtained; (C) put All road segments adjacent to the candidate road segment r' are inserted into the queue AA. If there is a matching road segment added, return to step 32-2 to continue anonymizing until an anonymous road segment set that meets the privacy requirements of the mobile user is found; if there is no matching If a road segment is added, the anonymity fails, and the location anonymity service is rejected.3.根据权利要求2所述的面向路网的查询感知的位置隐私保护系统，其特征在于：路段匹配模块（32）中随机因子η的取值为0.1～0.5，单位为常量。3. The road network-oriented query-aware location privacy protection system according to claim 2, characterized in that: the value of the random factor η in the road section matching module (32) is 0.1-0.5, and the unit is a constant.4.根据权利要求2所述的面向路网的查询感知的位置隐私保护系统，其特征在于：隐私要求{L_ID,I_ID}中的路段匿名最大值，一般m_max=20，位置匿名最大值，一般k_max=50。4. The location privacy protection system oriented to road network query perception according to claim 2, characterized in that: the anonymous maximum value of the road section in the privacy requirement {L_ID , I_ID }, generally m_max =20, and the largest anonymous location value, generally k_max =50.

Images