FORM 2
The Patent Act 1970
(39 of 1970)
&
The Patent Rules, 2005

COMPLETE SPECIFICATION
(SEE SECTION 10 AND RULE 13)

TITLE OF THE INVENTION

“Design of a Decentralized Matching Service for User Privacy in Location Based Services”

APPLICANTS:

Name Nationality Address
Alcatel Lucent France 54, rue La Boétie, 75008 PARIS, FRANCE

The following specification particularly describes and ascertains the nature of this invention and the manner in which it is to be performed:-

TECHNICAL FIELD
[001] The present invention relates to service offerings to users and, more particularly, to location based service offerings to users.

BACKGROUND
[002] Location Based Services (LBS), wherein services are offered to a user depending on the location of the user and the profile (interests of the user and social network of the user) of the user, are becoming popular. As the location based service provider has access to both the locations of the user and the profile of the user, concerns of the privacy of the user become important.
[003] Currently, an intermediate entity is used to cloak the location of the user from the LBS provider. The location of the user may be cloaked by some form of K-anonymity, i.e. the user''s location is not distinguishable from K other users by assigning a large location zone corresponding to a user, or creating and occasionally "mixing" the pseudonyms of users, or generating confusion about the user path by combining with queries of other users. However, it is not clear as to who should be the intermediate entity, as the intermediate entity will also have access both the location of the user and the profile of the user. Also, there may be a loss of quality of service to the user, as the location of the user is cloaked from the LBS provider.
[004] Also, in current use is creation of a region comprising of a large number of users, where the region depends on the number of users and communicating this region in lieu of the exact location of the user to the LBS provider. However, there is a computational delay at the user device end caused by computing the region. Also, there is a communication overhead as the computed region for a user is greater than required. This results in a loss of quality of service available to the user.
[005] Also, in current use are cryptography based techniques, where the location of the user is coded, when the user sends the location to the LBS provider requests for a service. However, in addition to increasing computational and communication overhead, due to the encoding, cryptography based techniques can only be used, when the user wants to make a request and cannot be used when the LBS provider wants to push a service to the user.
[006] In one of the current approaches available, the device of the user generates multiple locations and queries the LBS provider for services related to all the locations. On receiving the responses, the device filters the responses to choose the correct responses based on the correct location.

SUMMARY
[007] In view of the foregoing, an embodiment herein provides a method for providing location based services to a user using a pseudonymized location given the network operator of the user and at least one pseudonymized identifier provided by the location based service provider or the user, wherein the pseudonymized location represents location of the user; which may be of equal sizes or unequal sizes; and the pseudonymized identifiers represents services of interest to the user, the method further comprising steps of matching the pseudonymized location to a node in a distributed matching service, wherein the node contains the pseudonymized location and may be a mobile device; a virtual network server; or a computing device; matching at least one pseudonymized location to a list of pseudonymized identifiers present in the node; sending at least one matching pseudonymized identifier to a device used by the user, if a match of the pseudonymized identifier is present in the node; mapping the pseudonymized identifier to a physical address; and presenting the physical address to the user. The mapping of the pseudonymized identifier to the physical address comprises the step of the device contacting a yellow pages service. The mapping of the pseudonymized identifier to the physical address comprises steps of the device contacting the location based service provider to ask for the physical addresses corresponding to the pseudonymized identifier for a region, wherein the region is larger than the pseudonymized location; and the device filtering physical addresses received from the location based service provider to select the physical address closest to the pseudonymized location.
[008] Embodiments herein further disclose a communication network providing coverage over a region for at least one user, the network comprising of at least one means configured for dividing the region into a plurality of pseudonymized locations; assigning the user to one of the pseudonymized locations; and providing the user with the pseudonymized location. The network is configured for providing the pseudonymized location to the user, on receiving a request from the user or automatically. The network is configured for providing a location based matching service with the pseudonymized location.
[009] Also, disclosed herein is a location based service provider comprising at least one means configured for assigning a pseudonymized identifier to a registered service provider; and providing the pseudonymized identifier to a user of the location based service. The location based service provider is configured for enabling the user to register for the location based service; enabling the user to provide at least one service of interest to the user; and assigning pseudonymized identifiers to the service. The location based service provider also provides the pseudonymized identifier to a matching service.
[0010] Disclosed herein is a device for enabling a user to access location based services, the device comprising at least one means configured for obtaining a pseudonymized location from a communication network; obtaining at least one pseudonymized identifier from a location based service provider; enabling the user to request for the location based services to a decentralized matching service using the pseudonymized location and at least one of the pseudonymized identifier; and providing response of the request to the user. The device further comprises at least one means configured for enabling the user to register for location based services with the location based service provider. The device further comprises at least one means configured for sending the pseudonymized location to the matching service, on detecting a change in the pseudonymized location or at periodic intervals.
[0011] Embodiments herein disclose a matching service for providing location based services to a user, the matching service comprising of a plurality of nodes, wherein each of the node corresponds to at least one area and comprises of at least one service available in the area, further the matching service comprising at least one means configured for searching for a service available in a location by traversing the nodes in a hopping manner; and providing results of the search to the user.
[0012] These and other aspects of the embodiments herein will be better appreciated and understood when considered in conjunction with the following description and the accompanying drawings.

BRIEF DESCRIPTION OF THE FIGURES
[0013] The embodiments herein will be better understood from the following detailed description with reference to the drawings, in which:
[0014] FIG. 1 depicts a Location Based Service (LBS) system, according to embodiments as disclosed herein;
[0015] FIG. 2 depicts a matching service, according to embodiments as disclosed herein;
[0016] FIG. 3 illustrates a network operator, according to embodiment as disclosed herein; and
[0017] FIG. 4 depicts a flowchart where a user requests for information about a service, according to embodiments as disclosed herein.

DETAILED DESCRIPTION OF EMBODIMENTS
[0018] The embodiments herein and the various features and advantageous details thereof are explained more fully with reference to the non-limiting embodiments that are illustrated in the accompanying drawings and detailed in the following description. Descriptions of well-known components and processing techniques are omitted so as to not unnecessarily obscure the embodiments herein. The examples used herein are intended merely to facilitate an understanding of ways in which the embodiments herein may be practiced and to further enable those of skill in the art to practice the embodiments herein. Accordingly, the examples should not be construed as limiting the scope of the embodiments herein.
[0019] The embodiments herein enable a user to access LBS without any single entity being able to know both the location of the user and the interests of the user. Referring now to the drawings, and more particularly to FIGS. 1 through 4, where similar reference characters denote corresponding features consistently throughout the figures, there are shown embodiments.
[0020] FIG. 1 depicts a Location Based Service (LBS) system, according to embodiments as disclosed herein. The system, as depicted, comprises of at least one user 101, a LBS provider 102, a matching service 103, a network operator 104 and at least one service provider 105. The user 101 may be using a device capable of communicating with a communication network, belonging to a network operator 104. The device may be a mobile phone, a Personal Digital Assistant (PDA), a computing device or any other suitable device. The network operator 104 may be a mobile network operator, an internet service provider or an operator of any communication network. The network operator 104 is aware of the current location of the user 101. The LBS provider 102 is a service provider who provides information regarding services to user 101, based on the location of the user. The LBS provider 102 enables service providers 105 to register themselves, so that the LBS provider 102 may inform its users in the vicinity of the registered service providers 105 of the services. The users 101 may also register with the LBS provider 102, by providing a list of services of interest to the user 101. The matching network 103 is a distributed network with a plurality of nodes and is responsible for matching the location of the user 101 received from the network operator 104 with services of interest to the user 101 received from the LBS provider 102.
[0021] The user 101, who desires to avail of the LBS, registers with the LBS provider 102 using an application present on the device being used by the user 101. During registration, the user 101 creates an account with a user name with the LBS provider 102, wherein the user 101 provides information about the services that the user 101 is interested in. For example, a user 101 may enter his interests as movies, books and eating pizzas. The LBS provider 102 has a Pseudonymized Identifiers (PI) associated with each service. For example, services related to movies may have M0123 as PI; services related to books may have B1234 as PI and services related to pizzas may have ME5678 as PI. Once the user 101 has entered the services that are of interest to him, the device receives the corresponding PIs from the LBS provider 102 and stores them for future reference. Service providers 105 may also register themselves with the LBS provider 102 by providing their name and an accurate description of the services offered by them. The service providers 105 are assigned PIs, according to services offered by the service providers 105. For example, a restaurant A offering pizzas is assigned ME5678 as PI, while a movie theater is assigned M0123. In some cases, the service provider 105 may be assigned more than one PI. For example, if restaurant A offers both pizzas and pastries, the restaurant will be assigned two PIs, one PI belonging to the class of pizzas, while the second PI belongs to the class of pastries/sweets.
[0022] At the operators end, the operator divides the region served by it into logical sectors, where each sector is called a Pseudonymized location (PL). The size of the PL may be varied according to the preferences of the operator 104. The size of the PL may be a square shaped sector having dimensions of 50m x 50m. The size of the PL may be any suitable shape, which depends on the preferences of the network operator 104. The location of each user 101 registered for LBS is mapped by the network operator to the respective PL. In another embodiment, the locations for all users served by the network operator 104 are mapped onto the respective PLs.
[0023] When the user 101 wants a service of interest located close to his location, he sends a query to the matching service 103. The query sent by the user 101 may specify the PI of the service of interest. In another embodiment herein, the query as written by the user 101 may comprise of at least one keyword, which describes the service and the device may translate the keyword into the PI. In another embodiment, the user 101 may request the LBS provider 102 to provide the PI for the service of interest, before sending the query. The query may also comprise of the user name, which serves as an identification means. The query may also contain a distance, where the distance is the radius around the current PL of the user 101 that the user 101 wants to search.
[0024] The matching service 102 has a distributed architecture comprising of a plurality of nodes, wherein each node is responsible for at least one PL and the list of PIs present in that PL. In an embodiment, each node may be responsible for handling a plurality of PLs, along with the list of corresponding PIs for each PL. In another embodiment, one PL may be spread over a plurality of nodes, with the list of PIs associated with that PL distributed across the nodes. The matching service 103 may obtain the current PL of the user 101 from the user. The device may also be configured for sending the PLs to the matching service 103 at periodic intervals. The device 103 may also send the PLs to matching service 103, when the device detects that the PL has changed. The query from the user 101 hops across the nodes of the matching service, till the node corresponding to the current PL of the user 101 is reached. If there is a match of the PI specified by the user 101 in the node matching the PL, then the PI along with the PL is sent to the user 101. If there are multiple nodes for a single PL, then a search has to be performed at each of the nodes till the matching PI is obtained.
[0025] The matching service 103 may also provide a list of PIs to the user 101, without the user 101 sending a query to the matching service 103. Here, the LBS provider 102 and the user 101 provide the PIs of interest to the user 101 and the PL of the user 101 respectively to the matching service. A hopping search is done across the nodes of the matching service 103, till the node corresponding to the current PL of the user 101 is reached. If there is a match of the PIs of interest in the node matching the PL, then the PI is sent to the user 101. If there are multiple nodes for a single PL, then a search has to be performed at each of the nodes till the matching PI is obtained. In an embodiment herein, multiple PIs of interest may be found in a PL.
[0026] The device of the user 101, on receiving the PIs, obtains the physical address and displays the address to the user 101. In an embodiment herein, the device contacts a directory services like Yellow Pages to get the physical address of the service provider. In another embodiment herein, the device contacts the LBS provider 102 for the physical address corresponding to the PI. The device may contact the LBS provider 102 to get all the locations in a larger region around the current user''s location, effectively cloaking the location of the user 101 from the LBS provider 102. Comparing this list of locations with the current location of the user 101, the application on the device can highlight the nearest location. The application present on the device may be a mashup application. In another embodiment, the device may download all the addresses of services of interest to the user 101, after the user 101 completes registration with the LBS provider 102.
[0027] FIG. 2 depicts a matching service, according to embodiments as disclosed herein. The matching service 103 may be a Distributed Hash Table (DHT) based distributed architecture, with the matching service being done using a Key Based Routing (KBR) primitive provided by structured overlays. Here, all nodes in the matching service 103 are assigned an identification means, which is chosen from a large number of possible values. The KBR primitive permits general access to the node that is currently responsible for a given key or identification means. Also, a structured overlay with a circular identifier space (here [0,1000]) is assumed like Pastry, as being the implementation substrate of the matching service 103. The matching service 103 comprises of a proxy 201 and a plurality of non-colluding nodes 202, 203, 204, 205 and 206. The nodes may be a suitable computing device such as a computer, mobile device, mobile phone and so on. Each node stores its identifier, which comprises of PLs and at least one corresponding PI. In an embodiment, each node may be responsible for handling a plurality of PLs, along with the list of corresponding PIs for each PL. In another embodiment, one PL may be spread over a plurality of nodes, with the list of PIs associated with that PL distributed across the nodes. The proxy 201 is responsible for receiving the queries from the user 101 and initiating the search for the response to the query across the nodes. The proxy 201 may be a node, which acts as a proxy for a user 101. For a different user, a different node may act as the proxy.
[0028] FIG. 3 illustrates the network operator, according to embodiments as disclosed herein. The network operator 104 comprises of a Mobile Switching Center (MSC) 301, a Home Location Register (HLR) 302, a Visitor Location Register (VLR) 303, an Authentication center (AUC) 304, A Base Station Controller (BSC) 305 and a Mobile Location Center (MLC) 306.
[0029] The MSC 301 is the primary service delivery node for the network. The MSC 301 is responsible for routing voice calls and SMS as well as other services (such as conference calls, FAX and circuit switched data). The MSC 301 sets up and releases the end-to-end connection, handles mobility and hand-over requirements during the call and takes care of charging and real time pre-paid account monitoring.
[0030] The HLR 302 is a database which stores data about subscribers, including the Individual Subscriber Authentication Key (Ki) for each Subscriber Identity Module (SIM). In an embodiment, details of the users registered for the LBS may also be stored in the HLR 302.
[0031] The VLR 303 is a database which stores temporary information about roaming subscribers. The VLR 303 may track the user and store his current location details. The location based details may be provided to the user 101 by the VLR 303, when the user 101 makes a request for the same.
[0032] The AUC 304 is a database which contains the International Mobile Subscriber Identity (IMSI) the Subscriber Authentication key (Ki), and the defined algorithms for encryption. The AUC 304 may authenticate the user 101 for the LSB based service.
[0033] The BSC 305 is an element which provides all the control functions and physical links between the MSC 301 and base transceiver station. The BSC 305 provides functions such as handover, cell configuration data, and control of radio frequency (RF) power levels in Base Transceiver Stations.
[0034] The MLC 306 maintains a track of the current location of every subscriber, who is registered with the network operator 104 for the service. On request from the user 101, the MLC 306 may provide location details (PL) to the user 101. In an embodiment, the MLC 306 may also provide updates of the PL to the user 101 after specified time intervals.
[0035] FIG. 4 depicts a flowchart where a user requests for information about a service, according to embodiments as disclosed herein. Consider a particular user 101 is interested in obtaining information about services available in a location from the LBS provider 102. For example, the user 101 may be interested in obtaining information regarding pizza eateries present in his current PL. The user 101 enters a query regarding the available pizza outlets and sends (401) the query to the matching service 103. The query sent by the user 101 may specify the PI of the service of interest. In another embodiment herein, the query as written by the user 101 may comprise of at least one keyword, which describes the service and the device may translate the keyword into the PI. In another embodiment, the user 101 may request the LBS provider 102 to provide the PI for the service of interest, before sending the query. The query may also comprise of the user name, which serves as an identification means. The query may also contain a distance, where the distance is the radius around the current PL of the user 101 that the user 101 wants to search. In an embodiment, the user 101 may also provide information on the current PL of the user 101. The information on current PL of the user 101 may be obtained from the network operator 104 by the user 101 himself by sending a request for the same. The PL based information may be obtained by tracking the user’s location based on Global Positioning System (GPS), triangulation techniques or the like. On receiving the current PL of the user 101, a proxy routes (402) the request in the matching service 103, where the proxy corresponding to the mobile user. The proxy routes the request in O (log N) hops (N being the size of the structured overlay) to the node that is currently responsible for the current PL of the user (here node `A’). The matching service 103 then checks (403) if the queried PI for pizza outlets is present in the PIs present in node A. In case, there is no match in node A, the matching service 103 informs (404) the user 101 of the lack of the requested service, in this case pizza outlets in his current PL. If there is a match found in node A, the matching service 103 sends (405) the results to the device of the user 101. The result may be in the form of a list of PIs corresponding to the current PL. The device of the user 101, on receiving the results, obtains (406) the physical address and displays (407) the address to the user 101. In an embodiment herein, the device contacts a directory services like Yellow Pages to get the physical address of the service provider. In another embodiment herein, the device contacts the LBS provider 102 for the physical address corresponding to the PI and the PL. The device may contact the LBS provider 102 to get all the locations in a larger region around the current user''s location, effectively cloaking the location of the user 101 from the LBS provider 102. Comparing this list of locations with the current location of the user 101, the application on the device can highlight the nearest location. The application present on the device may be a mashup application. In another embodiment, the device may download all the addresses of services of interest to the user 101, after the user 101 completes registration with the LBS provider 102. In another embodiment herein, the matching service 103 may search for other nodes who are also handling the same PL. The various actions in method 400 may be performed in the order presented, in a different order or simultaneously. Further, in some embodiments, some actions listed in FIG. 4 may be omitted.
[0036] In an embodiment herein, the PL may be provided to the matching service 103 by the network operator 104. In such a case, the matching service 103 may send a request to the network operator 104 for the current location of the user 101.
[0037] In another embodiment herein, the user 101 may search for services present in a PL, which is not his present location. The user 101, when sending the query to the matching service 103 may specify the PL of interest to him. The user 101 may type the PL number. The user 101 may also specify the name of the location and the device inserts the corresponding PL in the query, before sending the query to the matching service 103.
[0038] In another embodiment herein, the user 101 may receive information about services in his current PL without the user 101 querying for the services. Here, the matching service 103 obtains the PIs of interest to the user from the LBS provider 102. The matching service 103 then searches for PIs of interest to the user 101 in the node corresponding to the current PL of the user 101. If there are any matches, the matching service 103 sends the corresponding PIs to the device of the user 101, which displays the results to the user 101. In a further embodiment, the user 101 may receive updates about services in his current PL on changing his location or on updating the PLs of interest to him.
[0039] In an embodiment herein, the user 101 may specify a radial distance from a PL to search for services. The user 101 may specify the distance in the query sent by him. The user 101 may also specify a default distance at the LBS provider 102 at the time of registration or at any point of time by using his user name. One approach to enable a search to be done in an area larger than a PL is to have a business insert multiple entries corresponding to the location-grids within an advertising zone of desired radius centered at its location. The overlay node responsible for a location-grid, can trivially sort the businesses based on the distance parameter.
[0040] A second approach to enable this is a hierarchical approach of partitioning the location space. Every location is associated with multiple PLs of different levels. The first PL has the smallest grid-size (say 100m). A business then inserts entries corresponding to each successive PL level, with the number of entries equal to the number of levels of the PL. The number of levels can be selected as the log of the size of the maximum distance supported by the matching service 103. The overlay nodes responsible for each PL will store information about businesses in an exponentially larger area as compared to its previous level. Given a query with a desired radial distance, issuing multiple DHT lookups to retrieve the state corresponding to different PLs, and taking a set difference from returned results at each successive level, enables returning an approximately sorted list of businesses.
[0041] In another embodiment herein, the PLs may be of unequal size, such that the expected demand for services based in each PL would be approximately equal.
[0042] In another embodiment herein, one-hop DHT lookups are used to reduce the query latency routing latency.
[0043] Embodiments disclosed herein provide a mechanism to ensure user privacy while accessing LBS without requiring a single trusted entity that has access to all the information, without any reduction in accuracy in terms of the spatial granularity of the query responses, or an increase in the time of response. Embodiments disclosed herein also do not impose any substantial communication or computational overheads at the end-nodes.
[0044] The embodiments disclosed herein can be implemented through at least one software program running on at least one hardware device and performing network management functions to control the network elements. The network elements shown in Figs. 1, 2 and 3 include blocks which can be at least one of a hardware device, or a combination of hardware device and software module.
[0045] The foregoing description of the specific embodiments will so fully reveal the general nature of the embodiments herein that others can, by applying current knowledge, readily modify and/or adapt for various applications such specific embodiments without departing from the generic concept, and, therefore, such adaptations and modifications should and are intended to be comprehended within the meaning and range of equivalents of the disclosed embodiments. It is to be understood that the phraseology or terminology employed herein is for the purpose of description and not of limitation. Therefore, while the embodiments herein have been described in terms of preferred embodiments, those skilled in the art will recognize that the embodiments herein can be practiced with modification within the spirit and scope of the claims as described herein.

CLAIMS

What is claimed is:
1. A method for providing location based services to a user using a pseudonymized location and at least one pseudonymized identifier, wherein said pseudonymized location represents location of said user and said pseudonymized identifiers represents services of interest to said user, said method further comprising steps of
matching said pseudonymized location to a node in a distributed matching service (103), wherein said node contains said pseudonymized location;
matching at least one pseudonymized identifier to a list of pseudonymized identifiers present in said node;
sending at least one matching pseudonymized identifier to a device used by said user, if a match of said pseudonymized identifier is present in said node;
mapping said pseudonymized identifier to a physical address; and
presenting said physical address to said user.
2. The method, as claimed in claim 1, wherein said pseudonymized location comprises of sectors of
Equal sizes; or
Unequal sizes.

3. The method, as claimed in claim 1, wherein network operator (104) of said user provides said pseudonymized location to said matching service (103).
4. The method, as claimed in claim 1, wherein a location based service provider (102) provides at least one pseudonymized identifier to said matching service (103) for matching with a list of pseudonymized identifiers present in said node.
5. The method, as claimed in claim 1, wherein said user provides at least one pseudonymized identifier to said matching service (103) for matching with a list of pseudonymized identifiers present in said node.
6. The method, as claimed in claim 1, wherein said node may be one of
a mobile device;
a virtual network server;
a computing device.
7. The method, as claimed in claim 1, wherein said node is reached in (logN) hops, wherein N is the size of said matching service (103).
8. The method, as claimed in claim 1, wherein mapping of said pseudonymized identifier to said physical address comprises the step of said device contacting a yellow pages service.

9. The method, as claimed in claim 1, wherein mapping of said pseudonymized identifier to said physical address comprises steps of
said device contacting said location based service provider (102) to ask for said physical addresses corresponding to said pseudonymized identifier for a region, wherein said region is larger than said pseudonymized location;
said device filtering physical addresses received from said location based service provider (102) to select said physical address closest to said pseudonymized location.
10. A communication network (104) providing coverage over a region for at least one user, said network comprising of at least one means configured for
dividing said region into a plurality of pseudonymized locations;
assigning said user to one of said pseudonymized locations; and
providing said user with said pseudonymized location.
11. The communication network, as claimed in claim 10, wherein said network (104) is configured for providing said pseudonymized location to said user, on receiving a request from said user.
12. The communication network, as claimed in claim 10, wherein said network (104) is configured for providing said pseudonymized location to said user automatically.

13. The communication network, as claimed in claim 10, wherein said network (104) is configured for providing a location based matching service (103) with said pseudonymized location.

14. A location based service provider (102) comprising at least one means configured for
assigning a pseudonymized identifier to a registered service provider; and
providing said pseudonymized identifier to a user of said location based service.

15. The location based service provider (102), as claimed in claim 14, wherein said location based service provider (102) is configured for
enabling said user to register for said location based service;
enabling said user to provide at least one service of interest to said user; and
assigning pseudonymized identifiers to said service.

16. The location based service provider (102), as claimed in claim 14, wherein said location based service provider (102) provides said pseudonymized identifier to a matching service (103).

17. A device for enabling a user to access location based services, said device comprising at least one means configured for
obtaining a pseudonymized location from a communication network (104);
obtaining at least one pseudonymized identifier from a location based service provider (102);
enabling said user to request for said location based services to a decentralized matching service (103) using said pseudonymized location and at least one of said pseudonymized identifier; and
providing response of said request to said user.

18. The device, as claimed in claim 17, wherein said device further comprises at least one means configured for enabling said user to register for location based services with said location based service provider (102).
19. The device, as claimed in claim 17, wherein said device further comprises at least one means configured for sending said pseudonymized location to said matching service (103) at periodic intervals.

20. The device, as claimed in claim 17, wherein said device further comprises at least one means configured for sending said pseudonymized location to said matching service (103), on detecting a change in said pseudonymized location.

21. A matching service (103) for providing location based services to a user, said matching service (103) comprising of a plurality of nodes, wherein each of said node corresponds to at least one area and comprises of at least one service available in said area, further said matching service (103) comprising at least one means configured for
searching for a service available in a location by traversing said nodes in a hopping manner; and
providing results of said search to said user.

Dated this 29th March 2010

Dr. Kalyan Chakravarthy
Patent Agent