Abstract
Proximity discovery is a very interesting and useful technique which helps a user to find out his proximities who have the same or similar location with him during a certain period of time. However, current methods of discovering proximities are difficult to adopt and vulnerable when wrong location tags are provided. This paper proposes Produre, a novel proximity discovery mechanism in location tagging system based on users’ credibility degrees and online social network. The introduction of online social network helps to maintain the relationship and location exposure policies between friends. The users’ credibilities help to diminish the bad influence of malicious users who always annotate wrong location tags because the credibility scores change based on users’ performance. The experimental results by our prototype illustrate Produre can effectively discover proximities of a user in an efficient and accurate way with high quality and fewer mistakes.
Keywords: Proximity discovery, location tagging system, credibility degree, online social network.
Introduction
With the development of online social networks(OSN), such as Facebook [1] in U.S. and Renren [2] in China, more and more applications have emerged to provide personalized and useful services. Among all these services, proximity discovery has attracted so many people and is being discussed almost everywhere. Here we define the term "proximity discovery" as "finding out the persons who have the same or similar geographical location with a certain user". In other words, according to proximity discovery, we can find out the geographical neighbors with respect to a certain user. In practice, we usually refer to the proximity of a user u as a user p the distance between whom and u is no more than a threshold Dt. In this paper, we would like to use "online social network" as an information pool which can provide useful information (e.g., friend relationship, location tags, maps…) to support proximity discovery. We define "user" as a real person behind an individual account in an online social network.
An example of proximity discovery. Alice and Bob are friends. Now Alice is shopping in a shopping mall. Her mobile is turned on and so is the bluetooth in the mobile. Bob has just stepped into that mall, then Alice is being noticed by her mobile that Bob is in the same hall too. Therefore, they will meet and have a pleasant time together.
Typical proximity discovery. In typical proximity discovery systems, users repeatedly annotate location tags according to the information given by their handheld devices (e.g., mobile phone and PDA), send the location tags to the server, and then the server will find out proximities of each user based on doing comparisons between those tags. For example, if the server discovers that the location in a location tag M1 sent by user U1 is the same as or similar with the location in another location tag M2 sent by user U2. Then the server may notice U\ and U2 that they are proximities of each other. However, there may be tag spam in the location tags. Here we define "tag spam" as a location tag whose content doesn’t match the location where the user resides. Obviously, if there are tag spam, then the server will do wrong comparisons and therefore return wrong results (i.e., wrong proximities) to the users. For example, Bob sends a location tag, which indicates that he is shopping however he is at home actually, to the server. One friend of Bob (say Alice) also sends a location tag, which indicates that she is shopping which is true, to the server. The server will tell Alice that Bob is nearby based on comparison between location tags, however, Alice will find herself be cheated.
Our goal. This paper aims to answer the following questions: Is it possible to design an approach that helps the users to discover their proximities with fewer mistakes which are caused by wrong location tags? To answer the question, we aim for effective mechanism that helps users to discover their proximities with high efficiency and fewer wrong results.
Our approach and contributions. In this paper we present Produre, a novel proximity discovery mechanism based on users’ credibilities in location tagging system and online social network. The introduction of online social network helps to maintain the relationship and location exposure policies between friends. The users’ credibilities help to diminish the bad influence of malicious users who always annotate wrong location tags because the credibility scores change based on users’ performance. The experimental results by our prototype illustrate Produre can effectively discover proximities of a user in an efficient and accurate way with high quality and fewer mistakes.
To the best of our knowledge, there is not any study, using the method similar with Produre. The contributions of this paper are as follows:
- We propose Produre, a novel proximity discovery mechanism in location tagging system based on users’ credibilities.
- We introduce online social network to maintain the relationship and location exposure policies between users in Produre.
- We are the first to introduce approach to overcome the proximity discovery problem in current social-network services.
Outline. The rest of this paper is organized as follows. Section 2 describes the design rationale of Produe. Then, the evaluation results are discussed in Section 3. We present the related work in Section 4. Finally, we present conclusion and future work in Section 5.
Produre
In this section, first, we introduce our model oflocation tagging system in Section 2.1 which also includes model of location tags and location exposure policy. In Section 2.2, we mainly describe the working process of Produre. In Section 2.3 and Section 2.4, we describe algorithm for users’ credibilities and issues about key management to supplement Section 2.2.
Location Tagging System
Location Tag Model. In traditional tagging system, users annotate tags to resources in the system to show their subjective feelings about the resources. In this paper, we define a location tag [3] as an ephemeral, unpredictable nonce associated with a location and can be derived from various electromagnetic signals available in the environment, such as WiFi and Bluetooth. It can be thought of as a shared pool of entropy between all users at a given location at a given time. A location tag It can be represented as follows:
where
- u: the user who sends the location tag It, i.e., the annotator of the location tag.
- I: the location of user u when he is sending the location tag It, which is the main content of the location tag. Apparently, there may be more information in a location tag due to different kinds of location services and in this paper we just extract several main items to design Produre.
- t: the time when the location tag It is sent, which means at the time of t, user u is in the location of I.
System Model. We define a location tagging system (say St) as a system which provides location services according to location tags. We also define the user who raises a proximity discovery request as a "client". The system model which meets the design requirement of Produre is given as follows:
where
- U: the set of users in the tagging system, among whom there are friendship relations because of introducing online social network.
- C: the processing center of the whole system, which is in charge of communication, computation, and storage of friendship relations between users and their location exposure policies.
- LT: the set of location tags in the system. Users in the system repeatedly send location tags to the processing center.
- K: the key management center. It is responsible for generating public and private key pairs for the processing center and each user in the location tagging system, maintaining and destroying the public and private key pairs when necessary.
Location Exposure Policy. Produre combines traditional location tagging system and online social network. Therefore, the friend relationship in ONS can be used to make location exposure policy in location tagging system. In other words, a user u in the system can decide which users are allowed to know his location so that these users will be notified when u is one of their proximities (i.e., is near them) . A location exposure policy of u’s can be represented as Pui = {F, A, ST, ET}, where F is the set of target users of this policy, i.e., the users who are covered in this policy item. A is the set of action of this policy. An action can be allowing or not allowing users in F to know the location information of u.
Steps of Produre
The working process of Produre which is shown in Fig. 1 is described as follows.
- Step 1 - Request Generation: A client c raises a request of proximity discovery, and the processing center receives the request.
- Step 2 - Policy Checking: The processing center C checks c’s location exposure policy to determine the set of users who are allowed to exist in the returning results to c.
- Step 3 - Proximity Calculation: For each user ui obtained in Step 2, the processing center C makes comparison of the set of ui’s location tags with the set of c’s location tags, and calculates the size (say Nci) of the intersection of those two sets. If Nci > Nm, then the processing center C will regard user ui as a proximity of the client c and put ui into a proximity set Sp of c.
- Step 4 - Proximity Ranking: The processing center C ranks each element upi (i.e., a user) in Sp according to c’s credibility degree with respect to upi. At last, the processing center C returns the first 6 elements in Sp to c and the value of 6 can be adjusted according to the system requirement.
- Step 5 - Credibility Adjustment: The client c views some of the results (users) who possibly are his proximities, and contacts some proximities to do something (e.g., going shopping together, or sharing the fee of a taxi…). After that, the client will adjust his credibility degrees with respect to those users according to his own evaluation on them.
After Step 5, the working process of a single proximity request is done. The changed credibility degrees are stored in the system for later use, i.e., dealing with the following proximity requests.
Algorithm for Users’ Credibilities
In Produre, when a client issues a proximity discovery request, the system will present the result page. Then he may view some of the results (users) who possibly are his proximities, and contact some proximities to do something (e.g., going shopping together, or sharing the fee of a taxi…). After that, the client will have his own evaluation with respect to the proximities who the client has contacted with. According to the evaluation, if the client regards a proximity as a true proximity, the credibility of the client with respect to that proximity will increase. In contrast, if the client regards that proximity as a false one, the credibility will decrease faster than it increase.
Fig. 1. Steps of Produre
Considering the client c and a proximity p in the results, the credibility of c with respect to p, Rcp), is as follows (the initial value to an unknown proximity is always 0):
where
- ai(ad): the reward (penalty) given to p for each good (bad) proximity feedback. The relation ad > ai assures that Rc(u) decreases faster than it increases. The selections of ai and ad are based on the specific requirement of application.
- n: the number of consecutive wrong proximity results which means Rc(p) decreases exponentially when n increases.
In Equation 3, the credibility of c with respect to p decreases faster than it increases. The advantage is obvious: malicious users who always try to pretend to be proximities of others will be severely penalized because of the weight which is ad by the square of the number of consecutive wrong proximity results.
Key Management
The key management center K mentioned in Equation 2 is in charge of generating public and private key pairs for the processing center and each user in the location tagging system, maintaining and destroying the public and private key pairs when necessary.
In Produre, all the users and the processing center have their own public and private key pair. During the transmission of location tags, the content is encrypted by the receiver’s public key and the sender’s private key for confidentiality and authentication. The sending content when considering encryption from the client’s perspective is 
where uid is the identity of the sender (i.e., user).
Fig. 2. Experimental area of evaluation on Produre
are respectively the receiver’s public key and the sender’s private key.
is the sending timestamp while Cont is the sending content.
Evaluation
In this section, we describe the evaluation of performance of Produre. First, we introduce the experimental environment and the evaluation metric. Then, we describe the result of evaluation.
Experiment Setup
To evaluate our approach, we develop a prototype location tagging system where the whole mechanism of Produre is implemented. We recruit several volunteers who behave as users in the tagging system. They are required to generate the location tags based on their handheld wireless devices (e.g., mobile phones, GPS, or RFID tags). In other words, users first check the position information given by handheld devices and then give their subjective location tags. The experimental area is shown in Fig. 2. It is a square whose length and width are both 1 kilometer. It is divided into many little 5m x 5m squares. Ideally, there should be location tag receivers at each red point in Fig. 2 to assure high accuracy of transmission. However, lacking of so many receivers, we only put some receivers at several red pints ( one at one ) in the area. We assume that the accuracy of transmission has been affected quite a little. The users randomly walk in the experimental area and repeatedly send location tags to the receivers and then to the processing center. However, some devices are malicious by providing wrong information about locations.
To discover the proximity set of a user, it is necessary to define a distance threshold of Dt two users who can be viewed as each other’s proximities. In the experiment, we set Dt to 5,10, 50 meters to see how the performance of the whole location tagging system is. We use the ratio of successful detection (SDR) as the evaluation metric which is defined as the ratio of the number of successful detection of wrong tags to the number of all the wrong tags.
Fig. 3. Evaluation result
Evaluation Result
From Fig. 3 we can see that without Produre, the SDR values fluctuate heavily as the number of experimental rounds increase. However, the adopting of Produre makes the SDR values increase as the number of rounds increase. Different Dt values get different results. Generally speaking, SDR values with Dt of a higher value are easily high. However, the accuracy is very low because Dt of a higher value cannot reveal more detail of users’ proximities’ locations. Therefore, in practice, there is always a trade-off between the SDR value and the accuracy of Produre.
Related Work
Tagging systems (e.g., Flickr [4], Del.icio.us [5] and YouTube [6]) have grown in significance on the global Internet. In tagging systems, users search their wanted resources with related tags and annotate their resources (e.g., photos in Flickr and URLs in Del.icio.us) with their interested tags. Location tagging system is one kind of tagging system which provide location services, among which proximity discovery is the most useful and practical to most of the users.
As to proximity discovery, it has been provided by many websites, such as Google [7] and Netease Bang [8]. Users of these sites now and then obtain their locations according to GPS and post location tags on sites. They can change the policy which defines whether their locations can be exposed to their friends or other strangers.
There have been several studies which focus on location privacy protection by now. Obviously, it is based on the assumption that the processing center may be compromised by malicious users or hackers, which is different from the assumption in this paper. A privacy-aware friend locator was studied in [9]. Unfortunately the technique used therein has many flaws including the fact that the server always learns the result of proximity testing. Many papers have taken the anonymization approach to location privacy. The work of Gruteser and Grunwald [10] kicked off a long line of papers in this area. This approach has several limitations including the highly identifying nature of location information [11] and the limited location resolution resulting from the ob-fuscation or quantization needed for anonymization. At any rate, this approach is not suitable for proximity detection because identity is important in a social network context. There is a body of work on location-based encryption. Some of it assumes the existence of tamper-proof ("anti-spoof") hardware [12]. Other work such as [13] is more rigorous and involves securely verifying the location of the receiver based on timing or strength of electromagnetic signals.
Conclusion and Future Work
Proximity discovery is very practical and interesting in location tagging systems. We have proposed Produre, a novel proximity discovery mechanism based on users’ credibilities. Our experiments based on real environment show that Produre can effectively discover proximities of a user in an efficient and accurate way with high quality and fewer mistakes.
In the future, we plan to apply Produre mechanism with more secure cryptographic features. Some improvements may be added, such as the use of attribute-based encryption (ABE) and identity-based encryption (IBE).
