Preserving Source Location Privacy inMonitoring-Based Wireless Sensor NetworksYong Xi, Loren Schwiebert, and Weisong ShiWayne State UniversityDepartment of Computer ScienceDetroit, MI 48202{yongxi, loren, weisong}@wayne.eduAbstractWhile a wireless sensor network is deployed to monitorcertain events and pinpoint their locations, the location in-formation is intended only for legitimate users. However, aneavesdropper can monitor the traffic and deduce the approx-imate location of monitored objects in certain situations. Wefirst describe a successful attack against the flooding-basedphantom routing, proposed in the seminal work by Celal Oz-turk, Yanyong Zhang, and Wade Trappe. Then, we proposeGROW (Greedy Random Walk), a two-way random walk, i.e.,from both source and sink, to reduce the chance an eaves-dropper can collect the location information. We improvethe delivery rate by using local broadcasting and greedy for-warding. Privacy protection is verified under a backtrackingattack model. The message delivery time is a little longerthan that of the broadcasting-based approach, but it is stillacceptable if we consider the enhanced privacy preservingcapability of this new approach. At the same time, the en-ergy consumption is less than half the energy consumptionof flooding-base phantom routing, which is preferred in alow duty cycle, environmental monitoring sensor network.1 IntroductionWireless communication had gained more popularity inrecent years. The application driven force behind the pop-ularity is easy deployment and mobility. Besides the wideapplications of wireless local network today, emerging appli-cations of wireless communication include wireless sensornetworks and Mesh Networks [4]. It can be easily seen thatwireless networking will gain more popularity and vast in-formation will be carried on wireless networks in the nearfuture.However, wireless communication media is a broadcastmedia, which poses a big challenge of how to protect infor-mation running on the network. Despite strong encryption ofthe data, wireless communication media still exposes someinformation about the traffic carried on the network. This isan inherent side effect of wireless communication. Mobilitymeans that the communication is expected everywhere in thedeployment area, which subsequently exposes the commu-nication to possible attackers. Easy deployment means thatthere is certain openness in the protocol, which subsequentlyexposes some protocol information to possible attackers.Location privacy is an important security issue. Loss oflocation privacy can enable subsequent exposure of identityinformation because location information enables bindingbetween cyberspace information and physical world entities.For example, web surfing packets coming out of a home in aMesh network enable an eavesdropper to analyze the surfinghabits of one family if the source location of those packetscan be determined.In a wireless sensor network, location information oftenmeans the physical location of the event, which is crucialgiven some applications of wireless sensor networks. Forexample, in a battlefield, the location of a soldier should notbe exposed if he initiates a broadcast query. In the panda-hunter problem, the location of the panda should not be ex-posed to hunters [8].A wireless sensor network can be a low duty cycle net-work. Often, traffic has a strong correlation with a certainevent at certain time. This gives big advantages to an eaves-dropper since he does not need sophisticated techniques todiscriminate traffic among different events. In this paper, westudy the source location privacy problem under the assump-tion of one single source during a specific period. However,we need to point out that such a scenario can happen in areal wireless sensor network.To preserve location privacy, we propose to use sourceand sink-based random walk for packet delivery. The sinkfirst sets up a path through random walk which serves asa receptor. Each packet from a source is then randomly1-4244-0054-6/06/$20.00 ©2006 IEEEforwarded until it reaches the receptor. At that point, thepacket is forwarded to the sink through the pre-establishedpath. A random walk greatly reduces the chance of packetsbeing detected. Even if an eavesdropper happens to detectone packet, the next packet is unlikely to follow the samepath, thus rendering the previous observation useless.The reminder of the paper is organized into 5 sections.In Section 2, related work is presented. In Section 3, weshow by an illustrated attack that randomness needs to beintroduced carefully into the routing protocol. In Section4, our implementation is described. In Section 5, simula-tion results are presented and discussed. In Section 6, weconclude our paper.2 Related WorkOur work is inspired by [8, 6]. An application scenarioof a wireless sensor network for monitoring a panda is pre-sented. Enabling outside monitoring of a panda withoutexposing the location of the panda to hunters is proposedas the Panda-Hunter problem. Phantom routing is used formessage delivery from the location of the panda to the sinkfor preserving its location privacy. The phantom routingalgorithm is composed of two phases. In the first phase,the source initiates a random walk. In the second phase,the packet is being delivered through flooding or single pathrouting. In this paper, we specifically address a possibleattack against the flooding-based delivery method.The idea of using intersecting paths to deliver packetshas been proposed in rumor routing [1]. In rumor routing,an event is known by some sensors in the small neighborhoodof the event location. A query is sent through random walk.A usable delivery ratio is achieved by a large number ofquery random walks intersecting with each other. This isdifferent from our approach. In our approach, both eventand query source use random walk to advertise themselves.Also, our concern is to provide privacy protection; thus amore dynamic structure than rumor routing is needed.In [10], asymptotics of three query strategies over a sen-sor network are discussed. Proofs are given that the prob-ability of unsuccessful delivery using source and receiverdriven ‘sticky’ Brownian motion decays much faster than us-ing a single Brownian motion with increasing random walklength. (t−5/8vs (log(t))−1where t is how long the Brown-ian motion has lasted) This result gives us a lower bound onthe performance for our approach. In a real sensor