Hybrid Model for Location Privacy in Wireless Ad-Hoc Networks

Published Online January 2013 in MECS DOI: 10.5815/ijcnis.2013.01.02

Location Based Services is defined as the ability to locate a mobile user geographically and deliver services to the user based on his location. Schiller J. defines the location based services as “services that integrate a mobile device’s location or position with other information so as to provide added value to a user’. So knowing your location or how far you are from a specific location would not be valuable by itself. Only if it can be related to other location which gives it meaning and value? For example, knowing that you are 3 KM from University of Pune is good, but to obtain a travel path to the University of Pune would be considered as value. Retrieving information about restaurants and cafes along the path would enhance the value better. The ability to modify the route in case of possible delays on the selected path adds another level of the value. LBS has a variety of applications that can be offered to organizations such as government, emergency services, commercial and industrial organizations for example, breaking news, traffic information, tracking and way finding. As LBS has the ability to locate a mobile user geographically. It threatens the privacy and the security of the users.

Tanzima H. et. al. [1] introduces decentralized approach to location privacy and combines k-anonymity with obfuscation, which enable agents to act on the behalf of peers requiring a location-based service. As a result it does not requires to trust on any involved party, neither its peers not the LSP. There are no restrictions for the agents’ positions: they could be located in a street, an office building, a shopping mall, or public place. As per Mohamed F. et. al. [2] framework has two main components, the location anonymizer and the privacy-aware query processor. The location anonymizer acts as a third trusted party that blurs the exact location information of each user into a cloaked spatial area that matches the  user  privacy profile. The  location anonymizer spends its time wisely in maintaining the pyramid structure in order to provide very small cloaking time. The privacy-aware query processor is embedded into traditional location-based database servers to tune their functionalities to be privacy-aware by dealing with cloaked spatial areas rather than exact point information. Chi-Yin C et. al. [3] worked on k-anonymity concept in which a person cannot be distinguished among k-persons. System makes use of two in-network anonymization algorithms, resource aware algorithm and quality aware algorithm. System also uses a spatial histogram approach to enhance the location-monitoring quality. Instead of releasing exact information of the concerned person, proposed system aims to release information of a group of k persons, known as aggregate information. This approach helps to preserve location privacy of that concerned individual and at the same time, the released information is fruitful to the external agency to further research or investigates their tasks. Matt D. et. al. [4, 10], used obfuscation, anonymity, regulation and privacy policies to preserve individual privacy while releasing information. This approach helps to preserve the privacy of individuals concerned while the information released proves to be useful. Again Latanya S. et. al. [5] used k-anonymity concept within which a person cannot be distinguished among k-persons. This work relies on generalization concept within which a single entity data is released at a time. It also relies on suppression concept where data to be disclosed is suppressed/ hidden so that it can’t be released. Algorithms used in this work are Minimal Generalization Algorithm and Minimal Suppression Algorithm. However, best results are obtained only if both approaches are jointly applied. In the extended work of Latanya S. [6] a k-anonymity concept is used within which a person cannot be distinguished among k-persons. Algorithms used in this approach are Minimal Generalization Algorithm and Minimal Suppression Algorithm. This approach helps to preserve the privacy of individuals concerned while the information released proves to be useful. Lars K. et. al. [7]

introduces obfuscation, anonymity, regulation and privacy policies to preserve individual privacy while releasing information. This approach helps to preserve the privacy of individuals concerned while the information released proves to be useful. Ye Zhu et. al. [8] used Node Location Algorithm and Blind Source Separation (BSS) techniques to preserve the privacy of individuals concerned while releasing information. This approach helps to preserve the privacy of individuals concerned while the information released proves to be useful. However, BSS performs well only when data available is small. Ardagna, C. A. [9] propose a way to express user’s privacy preferences on location information in a straightforward and intuitive way.

Hence in this research work based on such location privacy preferences, a new solution, based on obfuscation techniques, which permits to achieve, and quantitatively estimate through a metric, different degrees of location privacy is proposed.

• II.    P roblem D efinition and F ormulation

In the present world, use of internet is a major source of data. User data and other vital data flows through the internet. This data is prone to be misused by external entities. Even though there are several policies to prevent data misuse, these aren’t foolproof. Hence this work aims to hide the data that is vital to preserve the privacy of any user. The proposed system uses k-anonymity and obfuscation concept to achieve this task. Hence based on extensive literature survey the problem is formulated as below:

Given a set of nodes n 1 , n 2 ,. . . , n n with LCA a 1 , a 2 , . . . , a n , respectively, a set of moving objects m 1 , m 2 , . . . , m m , and a required anonymity level k and obfuscation area O , we find LCA and GCA an aggregate location for each node n i in the form of R i = (A i , N i ), where A i is a rectangular area containing the GCA area of node A i and N i is the number of node residing in the GCA areas of the nodes in Ai, such that Ni ≥ k.

• iii .    K-A nonymity and O bfuscation S trategy

In wireless ad hoc network obfuscation make’s communication confusing by hiding node current position in minimum bounding box known as locally cloak area [LCA] at the same time k-anonymity make node position undistinguishable in group of [k-1] users using GCA algorithm.

• A.    Generating the LCA

Locally cloak area is computed to achieve obfuscation in which small bounding box is developed by forming that contains the LCA of the query initiator and (k – 1) LCAs of the (n – 1) agents. A mobile agent can specify its desired LCA via three constants;

• ■    The constant c determines the ratio between the width and the length of the LCA.

• ■    The constants c 1 and c₂ determine the minimum and maximum distance of the agent’s position from the boundary of its LCA.

If an agent A’ provides its LCA to an agent A and some part of its LCA lies outside the communication range of agent A, then agent A can easily render a more precise location of A’. Restricting the position of A’ via c 1 and c 2 to a smaller rectangle in the LCA ensures a larger obfuscated area for A’.

• B.    Generating the GCA

To compute the GCA for an agent ‘j’, assumed that ‘k’ is the desired anonymity level of ‘j’ and ‘n’ is the number of LCAs reported by its neighbors. For the computation of the GCA, we need to find the smallest rectangle ‘r’ that encloses a k-subset (including j’s LCA) from the ‘n’ reported LCAs. The LCA of an agent ‘i’ is described by (x mini , x maxi , y mini , y maxi ).

The algorithm removes at each iteration one rectangle of the ‘n’ rectangles excluding the agent’s rectangle rj. Each removal of a rectangle minimizes the size of the GCA. The algorithm continues until the number of remaining LCAs is equal to ‘k’.

I v . R esearch methodology

The Wireless ad-hoc networks are an emerging technology which finds variety of applications in military, movement tracking, industries and medical fields. Wireless ad-hoc networks are self configurable, self healing networks. Considering this need in this work two mobility models are used in the simulations as mentioned below:

• ■    Manhattan Model

• ■    Waypoint Model

The Manhattan mobility model uses a grid road topology. This model is mainly proposed for the movement in urban area, where the streets are in an organized manner and the mobile nodes are allowed to move only in horizontal or vertical direction. At each intersection of a horizontal and a vertical street, the mobile node can turn left, right or go straight with certain probability. The parameter setting for Manhattan mobility model is as shown below.

Simple waypoint [pathway] model is a way to integrate geographic constraints into the mobility model and the node movement to the pathways in the map. The map is predefined in the simulation field. This graph can be either randomly generated or carefully defined based on certain map of a real city. The vertices of the graph represent the buildings of the city and the edges model of the streets and freeways between those buildings. Initially, the nodes are placed randomly on the edge. Then for each node a destination is randomly chosen and the node moves towards this destination through the shortest path along the edges. Upon arrival, the node pauses for ‘T’ pause time and again chooses a new destination for the next movement. This procedure is repeated until the end of simulation. However, since the destination of each motion phase is randomly chosen, a certain level of randomness still exists for this model. So, in this graph based mobility model, the nodes are traveling in a pseudo-random fashion on the pathways.

• A.    Implementation and Performance Analysis

Our approach combines k-anonymity with obfuscation: In wireless adhoc network obfuscation make communication confusing by hiding node current position in minimum bounding box known as locally cloak area [LCA] at the same time k-anonymity make node position undistinguishable in group of [k - 1] users using GCA algorithm. Computation of the minimum bounding rectangle that includes node’s own rectangle and the rectangles of k - 1 other nodes in wireless ad hoc network, thus can achieve location privacy for secure communication. Our proposed approach reveals as little information as possible.

The system architecture design for the proposed system is as shown in the Fig.1. System architecture shown in Fig.1 is executed by using simulation environment NS-2.34. To run simulation; topology set up is done using tcl script. The tcl file intern called all the .cc files NS-2.34. The LCA Algorithm is implemented in NS2 core .cc files such as location. h, mobile node .cc, mobile node .h where as GCA algorithm is implemented using tcl script.

Figure 1: A System Architecture Design

• B.    Modifications to NS2.34

In wireless ad-hoc network obfuscation make communication confusing by hiding node current position in minimum bounding box known as locally cloak area [LCA], to perform this implementation, it is essential to add some important patches in NS-2.34 core files such as:

• ■    ns-allinone-2.34/ns- 34/common/mobilenode.cc, mobilenode.h

• ■    ns-allinone-2.34/ns-2.34/common/location.h

• ■    ns-allinone-2.34/ns-2.34/trace/ cmu-trace.cc , cmu-trace.h

• ■    ns-allinone-2.34/ns-2.34/tcl/lib/ns-default.tcl, ns-mobilenode.tcl.

• C.    Setup in NS-2.34 Simulation

The scenario to simulate and GCA algorithm computation are defined in simulation.

• 1.    Create the simulator object

• 2.  Setup the network nodes

• 3.  Setup the routing mechanism

• 4.    Create transport connections

• 5.    Setup user applications

• 6.    Schedule LCA request transmission for GCA computation.

• 7.    Stop the simulation

• D.    Experiment Setup

To setup experiment for LCA and GCA, two mobility models as Manhattan and Waypoint Models are used in the simulations of wireless ad-hoc network with AODV and Dump agent protocol.

Manhattan Model:

The parameter setting for Manhattan model is as shown in Table 1.

TABLE I.     NS2 Simulation Parameters
Parameter name	Value
Area of Sensor Field	500×500
Channel	Channel/Wireless Channel
Topology Used	Random
Number of Sensor Nodes for the simulation	70
IPQ length	64
Transmissions Range	0.1
Interface Range	0.1
MAC protocol	Mac/802_11Ext
Routing Protocol	AODV DumpAgent
Max Sensor node	5, 10 ,15, ……… 70
Sink Node	All
k- anonymity level	5 , 10 ,15, 20 , 25
LCA and Obfuscation Area	500 m2

Manhattan Mobility Model Scenario used for Simulation:

Manhattan Mobility model scenario implemented in NS2.34 simulation is as shown in Fig. 2.The Manhattan mobility model scenario as shown in Fig. 2 used for the simulation is created, which shows that the topology used for it is Random topology with 70 nodes deployed in the sensor field of 500×500 area. The different properties of the sensor node are as shown in Table1. Here we assume that there are 5 source nodes (max. up to 70) are randomly selected that generates the events at random time interval (0 to 120 sec). According to the parameter setting of source node (uniformly random node) will generate LCA request which will be broadcast at random time towards the Sink Nodes and these packets are forwarded by the cooperative nodes in the network as per routing table and path defined by AODV, Dumb Agent protocol and MAC 802_11EXT protocol . The source node that needs to find GCA will send LCA query request to the sink nodes. According to parameter setting source node can set different k- anonymity level as well as obfuscations area.

Results and Graphs of Manhattan Model:

Figure 3: Screen shot of LCA Computation Result for sender in Manhattan mobility model using Dump Agent Routing

Figure 4: Screen shot of LCA Computation Result for receiver node in Manhattan mobility model using Dump Agent Routing

Figure 5: Screen shot of GCA Computation Result for receiver in Manhattan mobility model using Dump Agent Routing

Figure 6 : Screen shot of GCA Computation Result for receiver in Manhattan mobility model using AODV Routing

Fig. 3 shows the screen s hot of LCA Computation result for sender node in Manhattan mobility model using Dump Agent Routing which generated by running tcl script using NS2.34. Fig. 4 shows the screen shot of LCA Computation result for receiver node in Manhattan mobility model using Dump Agent Routing generated by running tcl script using NS2.34.

Fig. 2 to Fig. 6 are obtained by running the tcl script (scenario) with NS2.34, by considering the effect of different parameters as shown in Table 1. Fig. 3 and Fig. 4 show the implementation of Location Privacy Algorithm [LCA].

GCA Computation Result:

Fig. 5 shows the screen shot of GCA Computation result for Sender Node ‘19’ in Manhattan mobility model using Dump Agent Routing. Fig.5 shows the result of GCA computation when node id ‘19’ request LCA to its neighbors. GCA of node id’19’ is shown in red color, whereas the result of LCA computation for node id ‘19’ is shown in bottle green color.

AODV Routing:

The similar results are obtained with AODV Routing protocol for LCA, whereas the GCA Computation varies for time required for the processing as shown in Fig. 6. Fig. 6 shows the result of GCA computation when node id ‘17’ request LCA to its neighbors. GCA of node id ‘17’ is shown in red color, where as the result of LCA computation for node id ‘17’ is shown in green color. From Fig. 5 and Fig. 6 it is observed that, when sender as well as sink used to communicate each other node in a wireless ad hoc network masks its current position by providing a rectangle instead of a point as its location.

Waypoint [Pathway] Model

The parameter setting for Way point (pathway) Model is as shown in Table 2.

TABLE II. NS2 Simulation Parameters

Parameter name	Value
Area of Sensor Field	500×500
Channel	Channel/Wireless Channel
Topology Used	Random
No. of Sensor Nodes for the simulation	76
Packet Length	50
IPQ length	64
Transmissions Range	0.1
Interface Range	0.1
MAC protocol	Mac/802_11Ext
Routing Protocol	AODV Dump Agent
Max Sensor node	5, 10 ,15, ……70
Sink Node	All
k- anonymity level	5 , 10 ,15, 20 , 25
LCA and Obfuscation Area	500 m2

Waypoint Mobility Model Simulation Scenario:

Waypoint Mobility model scenario implemented in NS2.34 simulation is as shown in Fig. 7.

The Waypoint mobility model scenario as shown in Fig. 7 used for the simulation is created, which shows that the topology used for it is Random topology with 76 nodes deployed in the sensor field of 500×500 area. The different properties of the sensor node are as shown in Table 2. Here we assume that there are 5 source nodes Here we assume that there are 5 source nodes (max. up to 76) are randomly selected that generates the events at random time interval (0 to 120 sec). According to the parameter setting of source node (uniformly random node)

will generate LCA request which will be broadcast at random time towards the Sink Nodes and these packets are forwarded by the cooperative nodes in the network as per routing table and path defined by AODV, Dumb Agent protocol and MAC 802_11EXT protocol . When source node need to find GCA, node will send LCA query request to the sink nodes. According to parameter setting source node can set different k- anonymity level as well as obfuscations area.

Fig. 8 shows the result of GCA computation when node id ‘26’ request LCA to its neighbors. GCA of node id ‘26’ is shown in red color, whereas the result of LCA computation for node id ‘26’ is shown in green color. Fig. 9 shows the result of GCA computation when node id ‘15’ request LCA to its neighbors. GCA of node id ’15’ is shown in red color, whereas the result of LCA computation for node id ‘15’ is shown in green color.

• E.    Effect of K & density on GCA Computation

Fig. 10 and Fig. 11 shows the effect GCA computation result and average GCA area for sender node in Manhattan mobility model for k- anonymity value 1, 5, 10, 15, 20. From the simulation result is seen that more the node density, the GCA algorithm maximizes the bounding box size, which results in maximum location privacy for secure communication.

From simulation results as shown in Fig. 12 and Fig. 13 it is seen that more the node density, the GCA algorithm maximizes the bounding box size, which results in maximum location privacy for secure communication. Again from Fig. 13 it is seen that as value of ‘k’ anonymity increases from 15 to 25, then GCA area also increases up to certain level for k =1 to 15 average GCA size is decreases to minimize overhung for large GCA.

• V. C onclusions

The primary objective of the present work is to develop a system which preserves the location privacy of the concerned individual. This objective is achieved by simulating locally cloak algorithm and globally cloak algorithm using NS-2.34 environment. An approach that combines obfuscation and anonymization to ensure both location and anonymity privacy for mobile agents is presented. This approach does not require any central trusted party for computation of obfuscation and anonymization method results which can be further used for LBS request. Form simulation is seen that the obfuscation and anonymization approach provides the best method of cloaking depending on the mobile user privacy need in decentralized manner. From simulation it is seen that when sender and receiver [sink node] communicate in a clique obfuscates (masks) its current position by providing a rectangle instead of a point as its location. During simulation it is seen that GCA algorithm generates minimum bounding box of size LCA. Again it is seen that more the node density, the GCA algorithm maximizes the bounding box size, which results in maximum location privacy for secure communication. The value of ‘k’ anonymity increases then GCA area also incases up to certain level.

Figure 7: Screen shot of Waypoint mobility model Scenario

Figure 8 : Screen shot of GCA Computation Result for receiver in Waypoint mobility model using Dump Agent Routing.

Figure 9 : Screen shot of GCA Computation Result for receiver in waypoint mobility model using AODV Routing z-axis Time 48,00010620375483176 - node id 73

^^,^..._..щ_^            ...............

He’er

z-axis ОСА49.00010633382709813- node id 15 z-axis GCA 43.00010633382709813 - node id 15 z-axis Time 43,00000000000000000 - node id 15 z-axis Time 43,0001060971 1718356 - node id 74 z-axis Time 43,0001060971 1718356 - node id 74 z-axis Time 43,00010619835568804- node id 22 z-axis Time 48,00010619835568804- node id 22

z-axis Time 48.00010620758487026 - node id 72 z:axis'Time"48ffl0W620758487026 :'n®^...............

z-axis Time 48.00010626165880809 - node id 88

T^HMiOOOIOKei™...............

z-axis Time 48.00010626263536285 - node id 1

z-axis Time 48.00010626263536285 - node id 1

z-axis Time 48.00010628507470045 - node id 37

z-"axis Time 48.000106285074700452 node id 37" "

z-axis Time 48.00010630503761000 - node id 8

z-"axis" Ттё"4"Э".00010630509761ООО"-"node" id’S ””

z-axis Time 48.00010630833622827 - node id 29

z-"axis" Ттё"4"8".00010630833622827"-"node" id" 2 9 ” ”

z-axis Time 48.00010630846087167 - node id 75

z-axis Time 48.00010630846087167 - node id 75

z-axis Time 48.00010631 1 13050863 -node"i"d"39"""

z:axisTime'48i000W^^..........

z-axis Time 48.00010631298885684- node id 34

z =_: s Tme -2 000"2:2129 j225z:24 -ode id 24

: a::s Тте T 000"2:217432Т:114 -'ode id 71

za:sTreT000"263l7432T2E4- -ode id 71

Figure 11 : GCA Computation Result of Average GCA Area for sender node in Manhattan mobility model

Figure 12: Effect of the ‘k’ anonymity and node density on GCA computation for Waypoint mobility Model.

Figure 13: GCA Computation Result of Average GCA Area for sender node in waypoint mobility model

without Compromising Privacy’, VLDB Endowment, ACM 159593385-9/06/09.

• [3]    C. Y. Chow, M. F. Mokbel and T. He, “A PrivacyPreserving Location Monitoring System for Wireless Sensor Networks”, IEEE Mobile Computing, vol.10, no.1, pp.1-14, January, 2011.

• [4]    M. Duckham and L. Kulik, “A Formal Model of Obfuscation and Negotiation for Location Privacy”, Proc. Of Pervasive Computing, 2005: pp.152–170, 2005.

• [5]    L. Sweeney and P. Samarati, “Protecting Privacy When Disclosing Information: k-anonymity & its enforcement through Generalization” , Proc. of MobiCom, 2002.

• [6]    L. Sweeney, “k- Anonymity: A Model for Protecting Privacy.” International Journal on Uncertainty, Fuzziness and Knowledge-based Systems, vol. 10, no.5, pp.557-570, 2002.

• [7]    M. Duckham and L. Kulik, “Location Privacy & Location Aware Computing” Proc. of HICSS, 2007.

• [8]    Y. Zhu and R. Bellati, “Compromising Location Privacy in WSN with limited information”, Proc. of ICDCS-2007, Pages 24, 2007.

• [9]    C. A. Ardagna, M. Cremonini, E. Damiani, S. De, C. Vimercati, and P. Samarati, “Location privacy protection through obfuscation-based techniques”, Lecture Notes in Computer Science, LNCS 4602, Springer, Berlin, pp.47–60, 2007.

• [10]    M. Duckham and L. Kulik., “Location Privacy & Location Aware Computing” Proceeding of HICSS, pp.213-220, 2007.

  R eferences

  • [1]    T. Hashem and L. Kulik , “Safeguarding Location Privacy in Wireless Ad-Hoc Networks” , UbiComp 2007, LNCS 4717, pp.372–390, Springer-Verlag

  Berlin Heidelberg 2007.

  • [2]    M. F. Mokbel, C. Y. Chow and W. G. Aref , “The New Casper: Query Processing for Location Services

  
  

  Balasaheb N. Jagdale received the B.E. and M.E. degrees in Computer engineering from University of Pune. Currently he is working as associate professor in Information Technology at MIT College of Engineering, Pune-38, Maharashtra, India. These days he is pursuing his doctoral degree at RTM Nagpur University, Nagpur,