# Node Location Privacy Protection in Unattended Wireless Sensor Networks

Authors: ZhiGang Zhou; Yu Wang; PanPan Li; XinGong Chang; JiWei Luo
Journal: Mathematical Problems in Engineering
 (2021)

---

## Abstract

Node location protection is critical to the wireless sensor networks (WSN), especially for unattended environment. However, due to most of the static deployment and the limitations in energy, storage, and communication capabilities of the sensors, WSNs are vulnerable to various location (and derivative) attacks. In this work, we study the node location privacy protection issue from both aspects of attacks and defenses. First, we present a new two-phase location attack for two important types of nodes (including base station and source node). It can locate a base station node within few amounts of local wireless transmission monitoring and then reversely trace the location of the source node. Different from existing methods, the proposed attack determines the node location based on the transmission direction, which can break through existing defenses. Then, to defend against such attacks, we design a pseudospiral-based routing protocol for WSN. We analyze the performance of parameters such as routing probability, maximum detectable angle, hop count, and number of loops based on PU SBRF, MoRF, and PLAUDIT methods. The theory analysis and confrontation experiment of attack and defense show that the proposed scheme can protect the location privacy of the target node with moderate communication and computation overhead.


---

## Body

## 1. Introduction

As an important part of the Internet of things [1], unattended wireless sensor networks (UnWSNs) have been widely used in a variety of civilian and military applications (such as environmental monitoring, marine disaster warning, offshore oil, and gas exploration) [2]. However, due to the characteristics of static layout of sensors in unattended environment and the limitations in energy, storage, and communication capabilities of the sensors, UnWSNs are vulnerable to various location attacks [3]. Moreover, UnWSNs often involve the collection and transmission of large amounts of sensitive data, which concerns the national information security [4]. Once node location (including source node and base station) is leaked or captured by an attacker, it will result in a series of derivative attacks, such as sensitive data theft and military target intelligence collection. Therefore, privacy protection of node location becomes the top priority of UnWSNs security.In wireless sensor networks [5], node location privacy-preserving technology is to protect the location of some important nodes (such as source node and base station) in the network. Specifically, locating the source node means that an attacker can discover valuable information nearby the source node [6], while locating the SINK node (also called base station) means that an attacker can attack the SINK node and steal important information [7]. Anonymous communication technology protects the location of the source node or base station by hiding the identity of the nodes in the communication process [8]. Although much work has been done for protecting sensor location privacy (such as LPSS (phantom source nodes) [9, 10], flooding [11], and pseudoinformation injection [12]), these technologies are either computational intensive schemes (such as large-scale broadcasting-based protocols and public-key cryptosystems [13]) or linear growth in communication costs. They are not suitable for UnWSNs, since most of the sensor nodes consist of low-cost and low-power radio devices. In fact, many technologies have lost efficacy facing new challenges:First, unattended sensors are mostly statically deployed in the absence of shelter environment; compared to traditional IOTs, node location information is more easily positioned. It makes the source node location privacy expose to the risk of a steep.Second, the traditional single, fixed source node location privacy protection mode is difficult to resist the large sample of knowledge-related attacks. By the technique of data mining and analysis, such as area sampling monitor, association analysis, and neural network, adversaries can identify the relatively accurate location privacy protection pattern. It threatens the security of the location privacy of the node.Last but not the least, most of the existing node location privacy protection technologies require complex angle calculation and routing computation, which is difficult to implement on a large scale under the existing UnWSN environment.The objective of this paper is to provide a bidirectional location privacy protection mechanism for both source nodes and SINK nodes in an unattended wireless sensor network environment. Therefore, we first propose a new bidirectional node location attack(BDLA), including SINK attack and source node attack, which to the best of our knowledge, cannot be defended by existing node location protection schemes, especially in the case of multiple adversaries conspiring. Subsequently, in a targeted manner, we design a pseudospiral routing protocol based on Archimedes Curve for UnWSNs, in which we use Voronoi rule to partition the SINK nodes in the UnWSN. Through such data spiral routing, it not only improves the strength of SINK privacy protection but also balances the end-to-end communication quality. Furthermore, to cope with the data sampling attack, sensors generate and send pseudomessages to disturb the attackers on an irregular basis. It improves the ability of the source node location privacy resisted. The theory analysis and confrontation experiment of attack and defense show that the proposed scheme owns capable of protecting the location privacy of the target node with moderate communication and computation overhead. The contributions of the paper are summarized as follows:(1)
We first study a new bidirectional node location attack (BDLA) scheme in UnWSNs, and accordingly, we propose a pseudospiral-routing protocol based on the Archimedes curve to protect the location privacy of both source nodes and SINK nodes(2)
We construct a one-by-one mapping relationship between Vcell and SINK based on the Voronoi rule, aiming to minimize the communication overhead of sending information from a given source node to the nearest SINK(3)
To respond to data sampling attacks, we design a strategy in which the sensors generate and send false messages to disturb the attacker from time to time, making our mechanism more efficient(4)
Furthermore, our extensive experiments on a test bed demonstrate the effectiveness and practicality of the schemeThe rest of the paper is organized as follows. Section2 overviews related work in current decades. Section 3 introduces the network model, attack capability hypothesis, and attack strategy proposed for important sensor nodes. Section 4 provides the detailed description of the proposed mechanism designs for node location privacy protection in UnWSNs. Section 5 gives thorough analysis of privacy guarantee. Section 6 reports our experimental study that evaluates the performance of our solution, followed by the concluding remarks in Section 7. Symbols are summarized in Table 1.Table 1
List of symbols used in this work.
SymbolExplanationR,rRadiusL, lLine and tangentDDomainsN,nNode set and nodesCClassBSINKVVcellHIndex setki,BPairwise keyhfakeThe maximum number of times a pseudomessage is forwardedTTimerpRouting probabilities


## 2. Related Work

Over the past few decades, there has been a lot of interest in technologies related to WSN. Nayyar et al. [14] provide in-depth analysis of simulation tools available for simulating almost everything considering underwater sensor network and comparing the features provided by every simulation tool, and routing protocols for UWSN are presented. In addition, comparison of protocols is also mentioned by Nayyar et al. [15] on the basis of various characteristics such as routing technique, packet delivery ratio, energy efficiency, packet delay, and localization to give a clear picture of the benefits and shortcomings of each and every enlisted protocol for UWSN. Furthermore, John et al. [16] discussed the functioning of various location-based opportunistic routing protocols proposed for UWSNs and evaluated the performance of two major protocols and VBF and HH-VBF using simulations in Aqua-Sim, but the performance of these protocols comes down with communication voids in the network.In recent years, a series of inspiring techniques have sprung up. Current location privacy protection strategies are mainly classified into path camouflage technology, trap-inducing technology, and access control technology.In the research field of path camouflage technologies, Ozturk et al. [11] proposed a privacy protection method for source node location based on the random walk thought “phantom routing,” but the overhead is too large. In [9], authors made further improvements to “phantom routing” and proposed a directional walking technique based on sectors and skipping steps, and it is greatly reduced overhead. PUSBRF protocol [17] can generate phantom source nodes that are far away from the real source node and geographically diverse. It increases the cost of backtracking by attackers and can effectively resist local traffic attacks. SPENA protocol [18] makes it difficult for an attacker to trace the source node by modifying the packet and dynamically selecting a routing node. However, the implementation process of using the encryption technology to hide the source information is complex, similar methods include the EELP protocol [19]. The LPMS protocol [20] uses a random data receiving scheme to implement a dynamic SINK node, which has high privacy protection intensity, but has a greater impact on the end-to-end communication quality. Long et al. [21] propose a routing strategy based on tree structure, which is used to hide the location privacy of the source node, and this scheme is effective to improve the privacy protection while maximizing the network lifetime. The literature [22] hides the location information of the source node by randomly selecting intermediate nodes and a network mixing ring, but it consumes too much energy. The literature [23] also adopts the random walking strategy of camouflage packets and real packets. The real data packets would randomly walk in a certain stage to hide the transmission direction, while the camouflage data packets are injected into the intersecting nodes of two or more shortest paths so that the attacker cannot determine the real route.In the field of trap-inducing technologies, the PeCo protocol [24] protects the privacy of source node and base station by using camouflage routing path based on pseudobase station, but the use of flooding in backbone network leads to high energy consumption. In [25], authors propose a routing scheme based on the loop, where the network topology consists of multiple routing and routing paths. The data is sent to the receiving node via the nearest routing loop to protect the location privacy of the base station. The data in the SRCRR protocol [26] is stored randomly in the middle node in the routing process, and the SINK node periodically collects the data sent by the intermediate node in the semicircle circular movement, so as to prevent the attacker from predicting and tracking its position and moving mode. Similar to the SRCRR protocol, the literature [27] uses a receiving SINK toroidal region route, and the source node randomly selects nodes within the star region around the SINK node. If the star region is large enough, the attacker could not monitor the entire zone to protect the source node location information. The literature [28] protects the location privacy of the base station by introducing false data that balances the traffic density in the network. In addition to protecting the location of the source node privacy, the literature [29] adopts the strategy of random walking and bidirectional tree to protect the location privacy of the destination base station.In the research field of access control technology, the STAP protocol [30] uses the packet forwarding strategy of the joint layer to implement data forwarding and grouping under unknown node location, which can resist local and global attacks. However, it needs to lay out storage nodes, and the quality of communication is unstable. To improve the network energy consumption and its communication efficiency, the ADRing protocol [31] based on anonymous quantization dynamic obfuscation ring uses the dynamic obfuscation loop and the anonymous measure evaluation mechanism based on the location quadrant to protect the location privacy of source node. MQA Protocol [32] uses encryption technology to realize the anonymity of node IDs, but the frequent process of encryption and decryption leads to an inefficient system. The PPSNC protocol [8] based on GEVs (global encoding vectors) carries on the homomorphic encryption to the data stream. Because the ciphertext data flow is not detectable, it can effectively prevent the traffic analysis attack, but this method is computationally expensive.In summary, existing techniques have many shortcomings, such as reducing the communication quality while protecting the source node location privacy, or not enough to reduce the energy consumption while protecting the source node location privacy, so in this paper, we design a high-performance location privacy protection method, which improves the ability to protect the privacy of the source node location and ensures a moderate communication and computation overhead.


## 3. Network Model

The wireless sensor network consists of many sensor nodes and several SINK nodes deployed in the monitoring area. The sensor node forms a multihop and self-organizing network system by means of wireless communication, which aims to perceive, collect, and process the information of the objects in the network coverage area and send to the user. The network model is similar to the Panda_Hunter game [11] (as shown in Figure 1), where the sensor network is used to monitor panda activity and location. Once the panda is discovered, the nearest sensor, as the source node, will send the observations periodically or immediately to the SINK nodes in the form of messages. The SINK nodes send information to the user via the Internet or satellite.Figure 1
The Panda_Hunter game model.The goal of this work is to make it difficult for an attacker to locate the target object (such as a panda) by locating SINKs and stealing the message or reversely locating the source node. Without loss of generality, in this work, we make the following assumption for the entire UnWSNs:(1)
The sensor nodes are distributed uniformly across the network. Assume that each sensor node has a transmission rangers, which is the same with the distance of the nearest neighbor nodes, and any two nodes in the network can communicate by one hop or multihop mode.(2)
The whole network may have several SINKs, and the location of the base station is random.(3)
At the same time, the network may have multiple source nodes, and the mapping relationship between source nodes and SINKs is not fixed (i.e., given a source node, it can send messages to any SINK in the network).(4)
Sensor nodes and SINKs are indistinguishable from appearance, but the difference is that a sensor has limited computation and power, while the base station is not constrained in these aspects.


## 4. Attack Model

### 4.1. Attack Capability Hypothesis

In this work, we assume that the adversaries have strong hardware configurations and may be colluded in the network. Specifically, the adversaries have the following characteristics:(1)
Passive attack: each adversary can monitor the messages sent by nodes within its communication scope. Assume that each sensor has the same communication radiusrs, and the adversary’s monitoring radius is denoted by rdrd=k×rsk>1.(2)
Limited local attack capability: sensor nodes are deployed in a wide range of areas, making it difficult for attackers to monitor global traffic on such a large UnWSN. That is, we assume that the coverage of the whole UnWSN is a circle area with radiusruru=n×rsn≫k.(3)
Node locating: an attacker can locate nodes that are outside its monitoring scope through existing node-locating techniques (such as the sending signal strength [33]).(4)
Collusion attack: in order to locate the nodes (i.e., source nodes or SINKs) with high precision, several adversaries may collude with each other to share nodes’ location information they obtained. However, we assume that the monitoring scope of the adversaries cannot cover the entire network. In fact, if the adversaries could monitor the whole UnWSN, then they can monitor the target object’s activity directly without relying on the network.


### 4.2. Overview of Node Attack Strategy

Based on attack capability hypothesis, we propose a bidirectional node location attack (BDLA) scheme. BDLA first determines the location of the SINK by the direction of the message adversaries monitored. LetLni,nj be the line through the nodes ni and nj. For any two independent lines Li and Lj, if Li and Lj intersect, then the intersection is the candidate SINK. More generally, if there are mm>2 monitoring regions for conspirators who generate m fitted lines, then they compute all the intersections, and estimate the locations of the SINKs from these intersections. Based on this, BDLA reversely traces the location of the source nodes. Specifically, BDLA consists of five steps:(1)
Location sampling with multimonitoring regions: in the network, conspirators choosemm>1 regions as the monitoring domains DD1,…,Dm, where any Di∈D has a node set Ni, and each node ni∈Ni locates in the monitoring domain Di. As shown in Figure 2(a), four monitoring domains locate close to nodes n1,n2,n3,n4, respectively. The adversaries try to find several short forwarding paths ni,nj,…,nk,nt via passive attacks (such as eavesdropping) or compromising on some nodes.(2)
Candidate SINK location discovery based on multiparty coordination: according to the location sampling information of the nodes monitored, the attacker can use the least squares method to fit the position into a linel:y=ax+b, where a and b can be expressed as follows:(1)a=N∓∑n=1Nxn×yn−∑n=1Nxn∑n=1NynN∑n=1Nxn2−∑n=1Nxn2,b=∑n=1NynN−a∑n=1NxnN.(3)
SINK location estimation: by fitting the position sampling of the nodes monitored and removing noise, the attackers can locate the SINKs. Let the position set ofk estimate SINKs be LS. The attack can use a certain clustering method to clean the noise point in LS. The main steps of the denoising process are divided into 3 steps: (1) using agglomerative hierarchical clustering to LS, (2) finding the maximum class Cmax, and (3) locating the cluster means LocCmax, which are the location estimation of the SINKs after denoising, as shown in Figures 2(c) and 2(d).(4)
Based on SINKs’ location, the source node can be backtracked by data acquisition and fitting, as shown in Figure2(e).(5)
Based on the source node set with noise, in the same way, the attacks use cluster cleaning again to get the denoising location of the source nodes with high probability, as shown in Figure2(f).Figure 2
Bidirectional node location attack (BDLA) scheme procedure. (a) Location sampling. (b) Line fitting. (c) SINK estimation without denoising. (d) SINK estimation with denoising. (e) Source node estimation without denoising. (f) Source node estimation with denoising.
(a)(b)(c)(d)(e)(f)


## 4.1. Attack Capability Hypothesis

In this work, we assume that the adversaries have strong hardware configurations and may be colluded in the network. Specifically, the adversaries have the following characteristics:(1)
Passive attack: each adversary can monitor the messages sent by nodes within its communication scope. Assume that each sensor has the same communication radiusrs, and the adversary’s monitoring radius is denoted by rdrd=k×rsk>1.(2)
Limited local attack capability: sensor nodes are deployed in a wide range of areas, making it difficult for attackers to monitor global traffic on such a large UnWSN. That is, we assume that the coverage of the whole UnWSN is a circle area with radiusruru=n×rsn≫k.(3)
Node locating: an attacker can locate nodes that are outside its monitoring scope through existing node-locating techniques (such as the sending signal strength [33]).(4)
Collusion attack: in order to locate the nodes (i.e., source nodes or SINKs) with high precision, several adversaries may collude with each other to share nodes’ location information they obtained. However, we assume that the monitoring scope of the adversaries cannot cover the entire network. In fact, if the adversaries could monitor the whole UnWSN, then they can monitor the target object’s activity directly without relying on the network.


## 4.2. Overview of Node Attack Strategy

Based on attack capability hypothesis, we propose a bidirectional node location attack (BDLA) scheme. BDLA first determines the location of the SINK by the direction of the message adversaries monitored. LetLni,nj be the line through the nodes ni and nj. For any two independent lines Li and Lj, if Li and Lj intersect, then the intersection is the candidate SINK. More generally, if there are mm>2 monitoring regions for conspirators who generate m fitted lines, then they compute all the intersections, and estimate the locations of the SINKs from these intersections. Based on this, BDLA reversely traces the location of the source nodes. Specifically, BDLA consists of five steps:(1)
Location sampling with multimonitoring regions: in the network, conspirators choosemm>1 regions as the monitoring domains DD1,…,Dm, where any Di∈D has a node set Ni, and each node ni∈Ni locates in the monitoring domain Di. As shown in Figure 2(a), four monitoring domains locate close to nodes n1,n2,n3,n4, respectively. The adversaries try to find several short forwarding paths ni,nj,…,nk,nt via passive attacks (such as eavesdropping) or compromising on some nodes.(2)
Candidate SINK location discovery based on multiparty coordination: according to the location sampling information of the nodes monitored, the attacker can use the least squares method to fit the position into a linel:y=ax+b, where a and b can be expressed as follows:(1)a=N∓∑n=1Nxn×yn−∑n=1Nxn∑n=1NynN∑n=1Nxn2−∑n=1Nxn2,b=∑n=1NynN−a∑n=1NxnN.(3)
SINK location estimation: by fitting the position sampling of the nodes monitored and removing noise, the attackers can locate the SINKs. Let the position set ofk estimate SINKs be LS. The attack can use a certain clustering method to clean the noise point in LS. The main steps of the denoising process are divided into 3 steps: (1) using agglomerative hierarchical clustering to LS, (2) finding the maximum class Cmax, and (3) locating the cluster means LocCmax, which are the location estimation of the SINKs after denoising, as shown in Figures 2(c) and 2(d).(4)
Based on SINKs’ location, the source node can be backtracked by data acquisition and fitting, as shown in Figure2(e).(5)
Based on the source node set with noise, in the same way, the attacks use cluster cleaning again to get the denoising location of the source nodes with high probability, as shown in Figure2(f).Figure 2
Bidirectional node location attack (BDLA) scheme procedure. (a) Location sampling. (b) Line fitting. (c) SINK estimation without denoising. (d) SINK estimation with denoising. (e) Source node estimation without denoising. (f) Source node estimation with denoising.
(a)(b)(c)(d)(e)(f)


## 5. Node-Location Privacy Protection Protocol in UnWSNs

### 5.1. Observation

In the proposed attack model, the adversary can locate the location of the source nodes mainly by backtracking the transmission path of the information in the detection range. By observation, it has become the focus of contention between the two sides for the attacks and defenses of the information transmission directions and the traces. Therefore, how to find the balance between the communication cost and the privacy-aware transmission path in all the candidate paths from the source node to the SINK is a question.Intuitively, in all 2D graphics, the circle has the following two characteristics: (1) in the European rectangular coordinate system, for any two nodes on it, the tangent directions are different and (2) the integral of all angles between the adjacent nodes and the center of the circle is 360. Therefore, routing strategies with a (partial) ring in the path become the mainstream privacy protection solution for UnWSNs.As shown in Figure3, we denote by d the distance between the source node and SINK, by ϕx1+1−ϕx20<ϕ<1 the center of the circle and by R the radius of the circle. Let D be the possible monitoring domain of adversaries. Comparing Figures 3(a) and 3(b), the suspected range covering the source node depends on the value of the parameter ϕ and R. Make R a fixed value, and when ϕ⟶0, the center of the circle becomes closer to the SINK. According to the attack model, the larger the angle θ formed by the tangent l1 and l2, the wider the scope of the suspected range S=ϕπl2/360 (and vice versa). For ϕ to be fixed, when R increases, the angle θ will increase, and the scope of the suspected range S will increase as θ increases (and vice versa). However, in real scenarios, due to the limitation of the communication overhead, the size of the circle radius R is restricted correspondingly, and the value of ϕ is positively correlated with D. From the perspective of the actual effect of privacy protection, the value of ϕ is also restricted. Therefore, the existing location privacy protection scheme for WSNs cannot realize the theoretically optimal routing strategy that takes account of the node location privacy protection and communication overhead in ideal environment.Figure 3
The relationship between the proposed privacy protection policy and attacker’s monitoring domain.
(a)(b)Based on the above observation, focusing on multi-SINK scenario, we propose a pseudospiral-based node location privacy protection routing protocol for UnWSNs. As shown in Figure4, each node divides the other nodes within its perceived range into three subnode sets, including the loop-left node set (take the clockwise spiral as an example), the centripetal node set, and the centrifugal node set, where the loop-left node set is not required. In the hop-by-hop information routing, each relay selects a node in the corresponding loop-left node set or other node set to send the message with the given probability. It should be noted that the information is encrypted transmission, and the decision of which set would be chosen between the centripetal node set and centrifugal node set is set in the encrypted state bit of the information. Therefore, adversaries cannot infer the relative position among the relay and SINKs by the message forwarding relationship. Specifically, the proposed routing protocol includes two stages, namely, network initialization and message transmission.Figure 4
Schematic diagram of a pseudohelix-based node location privacy protection routing protocol.


### 5.2. Network Predeployment Initialization

We assume that the network is secure in the stage of predeployment and initialization. According to Voronoi rule [34], the whole network is divided into a set of Voronoi cells (Vcell), where each SINK Bi in the network is assigned to a Vcell. It makes the following:(1)
Each subspace Vcell has and only has a SINK(2)
Given aVcelli and the corresponding SINK Bi, for any node ni assigned to Vcelli, Bi is the nearest SINK compared with the others; if ni is at the boundary node between the two Vcells, the equation is establishedBased on the Voronoi rule, we build a one-by-one mapping relationship between a Vcell and a SINK, which aims at reducing the communication overhead of sending information from a given source node to the nearest SINK as much as possible. Figure5 shows a network space partitioning instance, and B1,B2,B3,B4 are four SINKs in the network which are divided into four Vcells V1,V2,V3,V4, respectively. Given the source node ni located in Vcell V1, B1 is the nearest SINK. However, it gives rise to the following problems: (1) due to the irregular shapes of the generated subspaces, it is difficult to be transformed by the coordinate representation; (2) as a result of the number of subspaces partitioned by the Voronoi rule is equal to the number of SINKs, it could not to be fine-grained refinements to regional division.Figure 5
An example of Voronoi-based domain division.To solve these problems, on top of the Voronoi diagram, we superimpose a regularM×M grid of arbitrary granularity, where each grid cell (Gcell) stores information about the Vcells intersecting it. The information recorded in each Gcell Gij can be viewed as a tuple B,N,H, where B is SINKs contained in this Gcell, N is the sensors contained in this Gcell, and H is an index set that records such Gcells: (1) when B=∅, H records such Gcells that contain SINKs in the Vcells intersecting of the target Gcell Gij; (2) B≠∅, and H records all Gcells in the Vcells covering B. For example, Figure 5 depicts a 4×4 grid, where G12 containing B1 stores B1,∅,G11,G12,G13,G14,G21,G22,G23,G24,G32,G33, G31 intersected by V2,V3 stores ∅,ni,G21,G43, etc. In practical, we use the Hilbert filling curve [10] to map the 2D regions into 1D values. The benefit of using Hilbert curve is that it describes the proximity relation among Gcells by using Hilbert ordering. 1-D values based on Hilbert ordering can be indexed by a B + -tree as well [35, 36]. Therefore, H of G12 (H2 corresponding with the Hilbert value of G12) records B1,∅,H1∼H3,H8,H9,H14∼H16.Figure6 depicts the data structure for the network. The core idea is to employ a grid-based B + -tree (gB + -tree) that hierarchically decomposes the spatial space into l levels tree structure, where the ith level has 4i Gcells. The root node of the gB + -tree is of height zero and covers the whole spatial space. The internal nodes located in the 1,l−1th level dynamically maintain a tuple B,N, respectively, where B records the number of SINKs within its subregion and N keeps the number of sensors within its subregion. The leaf nodes located in the lth level maintain a triple B,N,H, respectively. And, leaf nodes use Hilbert filling curve that maps the 2D space to 1D. The 1D values can be arranged in a B + tree. For example, in Figure 6, there are 8×8 grid, and the capacity of each node is 4. Each entry in a node has a key, a value domain, and a pointer to its child node. For the leaf level, the Hilbert values are the keys of the corresponding Gcells, while all the keys in a leaf node are less or equal to the key of the corresponding parent node. For the value domains in leaf nodes, each entry maintains a triple B,N,H (e.g., H7:∅,n3,n4,H3,H11), whereas the value domains in internal nodes, each entry maintains the statistics from its child node, e.g., in the level 1, the value of the entry with key=8 is 0,2 which means that, at the moment, there exists 0 SINK and 2 sensor nodes in the subregions H5,H6,H7,H8.Figure 6
An example of Grid-basedB + -tree.Obviously, the geographical location of the region with similar Hilbert line sequence is also neighboring. Combining the Voronoi rule and the Hilbert space filling curve, SINKs initialize the UnWSN with the following steps (as shown in Figure7).(1)
Each SINK in the deployment domain divides the network space into several subdomains and sorts by using the Voronoi rule and the Hilbert space fill curve. Each sensor records its Hilbert serial numberHi and the Voronoi partitioning domain number Vcelli, respectively, in the corresponding state code.(2)
Sensors in each Gcell boundary perceives the minimum upper Gcell sensor set and the maximum lower Gcell sensor set in its coverage range and marks them, respectively, as the centripetal node set and the centrifugal node set according to the relative position between sensors and the target SINK with the same Vcell.(3)
Each SINK calculates the sensor of the Archimedes Helix which is centered by itself and the radius ofR and broadcasts it, while each sensor only receives the information sent by the target SINK with the same Vcell and marks it in the corresponding SINK.(4)
Each sensor perceives whether there are left (or right) sensors labeled as loop nodes. If it exists, it is recorded in the loop-left (or -right) node set.Figure 7
An example of pseudohelix-based message routing.


### 5.3. Message Transmission

Each sensorni is preloaded with two pairwise keys ki,B and ki and a hashing function F, where ki,B is shared between the node ni and the SINK B; ki is ni’s broadcast key that is shared between ni and its neighbors. In addition, Wang et al. [37] proposed the concept of exposure domain, that is, the adversary is easy to trace the nodes nearby the source node to the location of the source node. To this end, massage transmission mainly includes the following three stages:(1)
Gh-hops finite flooding: Gh is a random function, which randomly transmits message; 0,h hops away from the source node. Different from literature [9] that aims at finding a phantom source node away from the source node for h-hops, the purpose of this step is to generate random location disturbances, which prevent the adversary from the reverse derivation of the proposed strategy.(2)
k,p-routing: we denote by k the maximum number of loops required for routing, which is designed to prevent information from being lost in the circle and to effectively reduce communication overhead, and by p the routing probability of choosing the node from the loop-left node set as the next relay. Correspondingly, 1−p is the routing probability of choosing the node from the centripetal node set or the centrifugal node set as the next relay. It is determined by the status bits of the information for the selection of the centripetal node set or the centrifugal node set. When the message has not been routed to the SINK, the corresponding state bit is set to 1 (representing the centripetal node set); when the SINK receives the message, it would change its corresponding state bit to 0 (representing the centrifugal node set). Noted that, in real scenarios, to prevent location leakage problem that the angle θ spanned by the circle tangents is too small, the value of the parameter p is often not a fixed value, but is determined by a function Qh with the reverse trend of the number of the message forwarding hops h.(3)
Gh-hops SINK camouflage: because SINKs are only responsible for receiving information in the process of message transmission, it shows the in-degree is much larger than the out-degree. Therefore, we need to disguise it as an ordinary relay node. When the message is received by the SINK, similar to step (1), the SINK would continue to forward the message with limited hops Gh.The details of the algorithm are shown in Algorithm1, and the algorithm flowchart is shown in Figure 8.Algorithm 1:Message security transmission algorithm.
INPUT:ni: start sensor node; k: the maximum number of loops passed;p: routing probability; Ux: the centripetal node set of ni;Ul: the centrifuge node set of ni; Uc: the loop-left (or -right) node set of ni;Vcelli, Gcelli: the corresponding Vcell and Gcell in which ni is located;W∗: random function;OUTPUT:nj target sensor node;PROCEDURE:(1)
whilek>0 do(2)
nj=ni;(3)
ifnj≠SINK then(4)
ifnj⋅Uc≠∅ & W∗≥p then(5)
randomly choose a nodenk from nj⋅Uc, let nj=nk(6)
else(7)
randomly choose a nodenk from nj⋅Ux, let nj=nk(8)
ifSINK⋅GcellSINK>ni⋅Gcelli then(9)
letni⋅Vcelli¯ be the subset that is bigger than Gcelli(10)
nj⋅Gcelli=minni⋅Vcelli¯(11)
else(12)
letni⋅Vcelli¯ be the subset that is smaller than Gcelli(13)
nj⋅Gcelli=maxni⋅Vcelli¯(14)
else(15)
letnj’s state be 0(16)
randomly choose a nodenk from nj⋅Ul, let nj=nk(17)
ifSINK⋅GcellSINK>ni⋅Gcelli then(18)
letni⋅Vcelli¯ be the subset that is smaller than Gcelli(19)
nj⋅Gcelli=maxni⋅Vcelli¯(20)
else(21)
letni⋅Vcelli¯ be the subset that is bigger than Gcelli(22)
nj⋅Gcelli=minni⋅Vcelli¯(23)
returnnjFigure 8
The flowchart of Algorithm1.


### 5.4. Pseudomessage Generation

In addition, to prevent adversaries from analyzing the message routing rules through big data monitoring and sampling technology, the sensors need to generate and send pseudomessages periodically to disturb the adversaries. To this end, each sensor nodeni preloads two random numbers during initialization: λ0<λ<1, hfake, where λ represents the probability of generating a pseudomessage and hfake represents the maximum number of times a pseudomessage is forwarded. However, it could cause message congestion in the network. Therefore, we introduce the trigger mechanism and the inhibition mechanism into the pseudomessage generation strategy:(i)
Trigger mechanism: each sensor contains a timerTi. When the sensor node does not forward message as the source node or relay node for a long time Ti>T, the pseudomessage generation mechanism will be triggered, and the corresponding state value of the pseudomessage and its own state are changed to Fake. The value of the timer set for each sensor node varies, and when the pseudomessage is sent, the sensor’s state value “Fake” will revert to True after m timer cycles.(ii)
Inhibition mechanism: when the node is forwarding message with the state value of “True” if receiving a message with the state value of “Fake” at the same time, the node will discard directly, regardless of the parameter settings (e.g.,hfake).


## 5.1. Observation

In the proposed attack model, the adversary can locate the location of the source nodes mainly by backtracking the transmission path of the information in the detection range. By observation, it has become the focus of contention between the two sides for the attacks and defenses of the information transmission directions and the traces. Therefore, how to find the balance between the communication cost and the privacy-aware transmission path in all the candidate paths from the source node to the SINK is a question.Intuitively, in all 2D graphics, the circle has the following two characteristics: (1) in the European rectangular coordinate system, for any two nodes on it, the tangent directions are different and (2) the integral of all angles between the adjacent nodes and the center of the circle is 360. Therefore, routing strategies with a (partial) ring in the path become the mainstream privacy protection solution for UnWSNs.As shown in Figure3, we denote by d the distance between the source node and SINK, by ϕx1+1−ϕx20<ϕ<1 the center of the circle and by R the radius of the circle. Let D be the possible monitoring domain of adversaries. Comparing Figures 3(a) and 3(b), the suspected range covering the source node depends on the value of the parameter ϕ and R. Make R a fixed value, and when ϕ⟶0, the center of the circle becomes closer to the SINK. According to the attack model, the larger the angle θ formed by the tangent l1 and l2, the wider the scope of the suspected range S=ϕπl2/360 (and vice versa). For ϕ to be fixed, when R increases, the angle θ will increase, and the scope of the suspected range S will increase as θ increases (and vice versa). However, in real scenarios, due to the limitation of the communication overhead, the size of the circle radius R is restricted correspondingly, and the value of ϕ is positively correlated with D. From the perspective of the actual effect of privacy protection, the value of ϕ is also restricted. Therefore, the existing location privacy protection scheme for WSNs cannot realize the theoretically optimal routing strategy that takes account of the node location privacy protection and communication overhead in ideal environment.Figure 3
The relationship between the proposed privacy protection policy and attacker’s monitoring domain.
(a)(b)Based on the above observation, focusing on multi-SINK scenario, we propose a pseudospiral-based node location privacy protection routing protocol for UnWSNs. As shown in Figure4, each node divides the other nodes within its perceived range into three subnode sets, including the loop-left node set (take the clockwise spiral as an example), the centripetal node set, and the centrifugal node set, where the loop-left node set is not required. In the hop-by-hop information routing, each relay selects a node in the corresponding loop-left node set or other node set to send the message with the given probability. It should be noted that the information is encrypted transmission, and the decision of which set would be chosen between the centripetal node set and centrifugal node set is set in the encrypted state bit of the information. Therefore, adversaries cannot infer the relative position among the relay and SINKs by the message forwarding relationship. Specifically, the proposed routing protocol includes two stages, namely, network initialization and message transmission.Figure 4
Schematic diagram of a pseudohelix-based node location privacy protection routing protocol.


## 5.2. Network Predeployment Initialization

We assume that the network is secure in the stage of predeployment and initialization. According to Voronoi rule [34], the whole network is divided into a set of Voronoi cells (Vcell), where each SINK Bi in the network is assigned to a Vcell. It makes the following:(1)
Each subspace Vcell has and only has a SINK(2)
Given aVcelli and the corresponding SINK Bi, for any node ni assigned to Vcelli, Bi is the nearest SINK compared with the others; if ni is at the boundary node between the two Vcells, the equation is establishedBased on the Voronoi rule, we build a one-by-one mapping relationship between a Vcell and a SINK, which aims at reducing the communication overhead of sending information from a given source node to the nearest SINK as much as possible. Figure5 shows a network space partitioning instance, and B1,B2,B3,B4 are four SINKs in the network which are divided into four Vcells V1,V2,V3,V4, respectively. Given the source node ni located in Vcell V1, B1 is the nearest SINK. However, it gives rise to the following problems: (1) due to the irregular shapes of the generated subspaces, it is difficult to be transformed by the coordinate representation; (2) as a result of the number of subspaces partitioned by the Voronoi rule is equal to the number of SINKs, it could not to be fine-grained refinements to regional division.Figure 5
An example of Voronoi-based domain division.To solve these problems, on top of the Voronoi diagram, we superimpose a regularM×M grid of arbitrary granularity, where each grid cell (Gcell) stores information about the Vcells intersecting it. The information recorded in each Gcell Gij can be viewed as a tuple B,N,H, where B is SINKs contained in this Gcell, N is the sensors contained in this Gcell, and H is an index set that records such Gcells: (1) when B=∅, H records such Gcells that contain SINKs in the Vcells intersecting of the target Gcell Gij; (2) B≠∅, and H records all Gcells in the Vcells covering B. For example, Figure 5 depicts a 4×4 grid, where G12 containing B1 stores B1,∅,G11,G12,G13,G14,G21,G22,G23,G24,G32,G33, G31 intersected by V2,V3 stores ∅,ni,G21,G43, etc. In practical, we use the Hilbert filling curve [10] to map the 2D regions into 1D values. The benefit of using Hilbert curve is that it describes the proximity relation among Gcells by using Hilbert ordering. 1-D values based on Hilbert ordering can be indexed by a B + -tree as well [35, 36]. Therefore, H of G12 (H2 corresponding with the Hilbert value of G12) records B1,∅,H1∼H3,H8,H9,H14∼H16.Figure6 depicts the data structure for the network. The core idea is to employ a grid-based B + -tree (gB + -tree) that hierarchically decomposes the spatial space into l levels tree structure, where the ith level has 4i Gcells. The root node of the gB + -tree is of height zero and covers the whole spatial space. The internal nodes located in the 1,l−1th level dynamically maintain a tuple B,N, respectively, where B records the number of SINKs within its subregion and N keeps the number of sensors within its subregion. The leaf nodes located in the lth level maintain a triple B,N,H, respectively. And, leaf nodes use Hilbert filling curve that maps the 2D space to 1D. The 1D values can be arranged in a B + tree. For example, in Figure 6, there are 8×8 grid, and the capacity of each node is 4. Each entry in a node has a key, a value domain, and a pointer to its child node. For the leaf level, the Hilbert values are the keys of the corresponding Gcells, while all the keys in a leaf node are less or equal to the key of the corresponding parent node. For the value domains in leaf nodes, each entry maintains a triple B,N,H (e.g., H7:∅,n3,n4,H3,H11), whereas the value domains in internal nodes, each entry maintains the statistics from its child node, e.g., in the level 1, the value of the entry with key=8 is 0,2 which means that, at the moment, there exists 0 SINK and 2 sensor nodes in the subregions H5,H6,H7,H8.Figure 6
An example of Grid-basedB + -tree.Obviously, the geographical location of the region with similar Hilbert line sequence is also neighboring. Combining the Voronoi rule and the Hilbert space filling curve, SINKs initialize the UnWSN with the following steps (as shown in Figure7).(1)
Each SINK in the deployment domain divides the network space into several subdomains and sorts by using the Voronoi rule and the Hilbert space fill curve. Each sensor records its Hilbert serial numberHi and the Voronoi partitioning domain number Vcelli, respectively, in the corresponding state code.(2)
Sensors in each Gcell boundary perceives the minimum upper Gcell sensor set and the maximum lower Gcell sensor set in its coverage range and marks them, respectively, as the centripetal node set and the centrifugal node set according to the relative position between sensors and the target SINK with the same Vcell.(3)
Each SINK calculates the sensor of the Archimedes Helix which is centered by itself and the radius ofR and broadcasts it, while each sensor only receives the information sent by the target SINK with the same Vcell and marks it in the corresponding SINK.(4)
Each sensor perceives whether there are left (or right) sensors labeled as loop nodes. If it exists, it is recorded in the loop-left (or -right) node set.Figure 7
An example of pseudohelix-based message routing.


## 5.3. Message Transmission

Each sensorni is preloaded with two pairwise keys ki,B and ki and a hashing function F, where ki,B is shared between the node ni and the SINK B; ki is ni’s broadcast key that is shared between ni and its neighbors. In addition, Wang et al. [37] proposed the concept of exposure domain, that is, the adversary is easy to trace the nodes nearby the source node to the location of the source node. To this end, massage transmission mainly includes the following three stages:(1)
Gh-hops finite flooding: Gh is a random function, which randomly transmits message; 0,h hops away from the source node. Different from literature [9] that aims at finding a phantom source node away from the source node for h-hops, the purpose of this step is to generate random location disturbances, which prevent the adversary from the reverse derivation of the proposed strategy.(2)
k,p-routing: we denote by k the maximum number of loops required for routing, which is designed to prevent information from being lost in the circle and to effectively reduce communication overhead, and by p the routing probability of choosing the node from the loop-left node set as the next relay. Correspondingly, 1−p is the routing probability of choosing the node from the centripetal node set or the centrifugal node set as the next relay. It is determined by the status bits of the information for the selection of the centripetal node set or the centrifugal node set. When the message has not been routed to the SINK, the corresponding state bit is set to 1 (representing the centripetal node set); when the SINK receives the message, it would change its corresponding state bit to 0 (representing the centrifugal node set). Noted that, in real scenarios, to prevent location leakage problem that the angle θ spanned by the circle tangents is too small, the value of the parameter p is often not a fixed value, but is determined by a function Qh with the reverse trend of the number of the message forwarding hops h.(3)
Gh-hops SINK camouflage: because SINKs are only responsible for receiving information in the process of message transmission, it shows the in-degree is much larger than the out-degree. Therefore, we need to disguise it as an ordinary relay node. When the message is received by the SINK, similar to step (1), the SINK would continue to forward the message with limited hops Gh.The details of the algorithm are shown in Algorithm1, and the algorithm flowchart is shown in Figure 8.Algorithm 1:Message security transmission algorithm.
INPUT:ni: start sensor node; k: the maximum number of loops passed;p: routing probability; Ux: the centripetal node set of ni;Ul: the centrifuge node set of ni; Uc: the loop-left (or -right) node set of ni;Vcelli, Gcelli: the corresponding Vcell and Gcell in which ni is located;W∗: random function;OUTPUT:nj target sensor node;PROCEDURE:(1)
whilek>0 do(2)
nj=ni;(3)
ifnj≠SINK then(4)
ifnj⋅Uc≠∅ & W∗≥p then(5)
randomly choose a nodenk from nj⋅Uc, let nj=nk(6)
else(7)
randomly choose a nodenk from nj⋅Ux, let nj=nk(8)
ifSINK⋅GcellSINK>ni⋅Gcelli then(9)
letni⋅Vcelli¯ be the subset that is bigger than Gcelli(10)
nj⋅Gcelli=minni⋅Vcelli¯(11)
else(12)
letni⋅Vcelli¯ be the subset that is smaller than Gcelli(13)
nj⋅Gcelli=maxni⋅Vcelli¯(14)
else(15)
letnj’s state be 0(16)
randomly choose a nodenk from nj⋅Ul, let nj=nk(17)
ifSINK⋅GcellSINK>ni⋅Gcelli then(18)
letni⋅Vcelli¯ be the subset that is smaller than Gcelli(19)
nj⋅Gcelli=maxni⋅Vcelli¯(20)
else(21)
letni⋅Vcelli¯ be the subset that is bigger than Gcelli(22)
nj⋅Gcelli=minni⋅Vcelli¯(23)
returnnjFigure 8
The flowchart of Algorithm1.


## 5.4. Pseudomessage Generation

In addition, to prevent adversaries from analyzing the message routing rules through big data monitoring and sampling technology, the sensors need to generate and send pseudomessages periodically to disturb the adversaries. To this end, each sensor nodeni preloads two random numbers during initialization: λ0<λ<1, hfake, where λ represents the probability of generating a pseudomessage and hfake represents the maximum number of times a pseudomessage is forwarded. However, it could cause message congestion in the network. Therefore, we introduce the trigger mechanism and the inhibition mechanism into the pseudomessage generation strategy:(i)
Trigger mechanism: each sensor contains a timerTi. When the sensor node does not forward message as the source node or relay node for a long time Ti>T, the pseudomessage generation mechanism will be triggered, and the corresponding state value of the pseudomessage and its own state are changed to Fake. The value of the timer set for each sensor node varies, and when the pseudomessage is sent, the sensor’s state value “Fake” will revert to True after m timer cycles.(ii)
Inhibition mechanism: when the node is forwarding message with the state value of “True” if receiving a message with the state value of “Fake” at the same time, the node will discard directly, regardless of the parameter settings (e.g.,hfake).


## 6. Experiments

We implemented experiments to evaluate our routing protocol (named MST for ease of description). The simulation experiments use Ubuntu 16.04LTS. We adopt simulation software NS2 to build UnWSN, where 10,000 sensors (including 10 SINKs) are randomly deployed in the region of 1000 m × 1000  m. The position coordinates of each node is added a random disturbanceε, which follows a Gaussian distribution, that is, ε∼Nμ,ε2. In addition, in order to compare and verify our proposed protocol MST with PU SBRF [17], MoRF [38], and PLAUDIT [28] in the simulation environment, all of experimental results are the average of three experiments. We analyze the performance of parameters such as routing probability, maximum detectable angle, and the number of loops passed on different methods in terms of communication overhead and security time.


### 6.1. Comparison and Analysis for Communication Overhead

The communication overhead is the basis for measuring the usability of the privacy protection method. In this work, the communication overhead is measured by the hops which messages passed from the source node to the SINK.In the case of given the minimum communication overheadd=50 (that is, it is 50 hops from source nodes to the SINK), Figure 9 shows the maximum number of loops passed by the MST algorithm under different routing probabilitiesp. As can be seen from Figure 9, the communication overhead of the MST protocol increases as the maximum number of loops required by the route increases. It indicates that the more the maximum number of loops passed by messages, the more hops is, due to the longer routing path. It is consistent with the theoretical analysis. In addition, when k>8, the number of hops remains basically constant. This is because in the experiment setting, the number of rings between the source node and the SINK remains around 8. According to the proposed node location protection routing algorithm, when the information is close to the SINK, the routing will no longer be limited to the set of k. It is designed to prevent the information from being lost in the rings and effectively reduce the communication overhead.Figure 9
The communication overhead of the MST method in different routing probabilities along rings (the specific experimental data are shown in Table2 in the Appendix).Table 2
The communication overhead of the MST method in different routing probabilities along rings.
KP/%0305070052.2354.8161.5470.01152.7456.1362.2472.13252.9156.7666.9375.84352.6757.8471.1479.93452.6462.1672.8582.59553.7366.1473.2684.95652.5267.5477.3386.14752.3270.1077.8387.96853.7372.8378.0188.32952.3873.9078.5290.121052.2774.3378.0190.161152.3373.8378.1890.071253.8373.8477.9290.13In conjunction with Figure10, it can be seen that when p = 70%, the superior performance was obtained, which comprehensively compares the three indexes: hop number, ring number passed, and amplitude of the detectable angle. Moreover, compared with the case of {p = 50%, k = 5} and the case of {p = 30%, k = 5}, the communication overhead of the case of {p = 70%, k = 5} increases slightly, but its detectable angle increases by 45%. Furthermore, we can reach the following conclusion that the size of the detectable angle is positively correlated with the number of hops along the rings in the early stage of routing. And, as the increase of the routing probability p that chooses the node from the loop-left node set, this positive correlation also tends to be significant. Furthermore, as the increase of hops, we found two kinds of interesting phenomena. (1) The detectable angle is suddenly enlarged. It is due to the fact that, in the multi-SINK network, message may leap from one helix formed by a certain SINK to another during the routing process (details in Algorithm 1: line 8–13), named the transition phenomenon of message routing between rings. (2) The detectable angle gradually expands to a certain maximum and then gradually shrinks. It mainly occurs in the events with high probability p. Due to the characteristics of helix, it is understandable that messages have higher chances of routing along the rings in a roundabout way. It is noted that, in this stage, the decrease of the detectable angle has no explicit relation with the change of detectable domain obtained by attackers. There are two main scenarios in our observations. (1) The distance between the focuses of routing paths and the source node is greater than the distance between the source node and the SINKs. In the multi-SINK network, it means that the source node and all the SINKs would be in the ipsilateral open sector, which results in the bidirectional node location attack failure. (2) The source node may be outside the detectable domain formed by attackers, due to the transition phenomenon. In short, under the MST protocol, along with the routing of the packets, the probability of the source node being traced back is reduced. Correspondingly, the risk of node location exposure is reduced. It is consistent with previous theoretical analyses.Figure 10
The communication overhead of the MST method at different detectable angles (the specific experimental data are shown in Table3 in the Appendix).Table 3
The communication overhead of the MST method at different detectable angles.
θP/%03050703075.0075.0240.0020.124082.3076.2840.8221.105085.0378.5448.9425.336086.1955.0730.057060.5233.158065.9841.289075.1345.7610044.3711047.2412050.26In addition to the maximum number of rings required that affects the communication overhead, the distance (the count of hops) between the source node to the SINK is also an index that uses to investigate the communication overhead of different routing protocols. Figure11 illustrates the impact of distance on the communication overhead, using the same experiment settings as before. The experiment shows that when p = 70%, MST algorithm has a lower hop count and communication overhead than other cases. Specifically, in the case of p = 90%, the routing path along the spiral ring is too long. It directly leads to a larger detectable angle but with more communication overhead. While in the case of p = 50%, the routing path along the spiral ring maybe too short, even causing the strategy probability to failure. Although communication overhead is low, in this case, the detectable domain formed by the detectable angle becomes smaller, and the risk of exposure of the resource node is greater.Figure 11
The communication overhead of the MST method in different distances from the source node to SINK (the specific experimental data are shown in Table4 in the Appendix).Table 4
The communication overhead of the MST method in different distances from the source node to SINK.
dP/%5070903032.2136.5440.124050.1055.1262.825057.3062.1570.906072.9282.8091.447085.3894.62112.818089.16121.32139.3190120.14132.32150.56100131.89148.64168.80110142.53158.56180.07120158.14173.65201.35130167.59183.27214.25140178.29195.71223.57In addition, givenp = 70%, we compared MST and the other three well-known algorithms in the communication overhead with different detectable angles. As shown in Figure 12, the communication overhead of four methods increases with the increase of the detectable angle. Specifically, the communication overhead of MoRF and PLAUDIT increases linearly with the increase of the detectable angle, while MST only presents sublinear growth. As PU SBRF adopts flooding protocol to generate multiple phantom source nodes that causes a large initial angle, the detectable angle formed by MST is smaller than that of PU SBRF in the early stage of routing; however, in this stage, the communication overhead of PU SBRF is a linear function of the parameter n (n represents the number of the phantom source nodes generated), which is much larger than the communication overhead of the other three algorithms. Moreover, under the same experimental settings, the maximum detectable angle that can be formed by MST is much larger than that of the other three algorithms. The experiment result shows that MST can reach a detectable angle of more than 120 degrees, while MoRF, PU SBRF, and PLAUDIT can only reach 60 degrees, 50 degrees, and 80 degrees, respectively. In general, the communication overhead of MST increases with the increase of the detectable angle, but the increasing trend is gentle, which is acceptable in the real environment.Figure 12
Compare the communication overhead of the four methods at different detectable angles (the specific experimental data are shown in Table5 in the Appendix).Table 5
Compare the communication overhead of the four methods at different detectable angles.
θMethodsPU SBRFMoRFPLAUDITMST1010.0318.8327.9314.542014.2626.0333.1520.023023.1235.4438.2325.294043.2240.0845.1431.685047.9242.9553.2338.446052.3455.2745.037062.1651.328065.3261.879047.2810051.7511057.4412063.00


### 6.2. Comparison and Analysis for Security Time

In this work, we use the security time to measure the security performance of protocols. The security time means the sum of hops that attackers need to trace from the SINK to the source node [17]. Similar to Section 5.1, given a certain distance (100 hops with 12 rings in the experiment setting), we verify the relationship between the number of rings passed and the detectable angle formed, as shown in Figure 13.Figure 13
The maximum detectable angle formed by the MST method in different routing probabilities along rings (the specific experimental data are shown in Table6 in the Appendix).Table 6
The maximum detectable angle formed by the MST method in different routing probabilities along rings.
kP/%507090010.0010.0010.00113.4018.2021.31221.2325.1431.94328.9032.6337.82432.2749.7852.33543.1958.8465.09652.9975.3682.30763.2283.5685.98863.9592.16107.63968.39112.33115.291070.38117.65126.891175.36126.89126.891281.33126.89126.89The experiment result shows that, with the increase of the maximum number of rings passed, the detectable angle increases gradually. The larger the detectable angle is, the smaller the detectable domain the attacker gets and the less the probability of the source node being exposed, and vice versa. A relatively small detectable domain would improve the nontraceability of the source node, guaranteeing the location privacy of the source node. When the detectable angleθ=75withp=70%and rings=8 or θ=110withp=70%and rings=9, MST obtains the superior comprehensive performance. It should be noted that a detectable angle that is too large or too small can cause the routing protocol to fail, as it is an art of balance between privacy protection and the communication overhead.Table 7
Compare the track-back error hop number (security time) of the four methods at different detectable angles.
θMethodsPU SBRFMoRFPLAUDITMST305.002.592.683.91407.585.767.456.925010.026.657.387.78607.507.7512.10707.6512.65808.1313.469013.4610016.3511018.2912018.94Theoretically, track-back hop number [18], average track-back time [26], and traffic confusion degree [8] can all be used as evaluation indexes to measure the security time. In order to unify, we take the track-back hop number as the evaluation indicator. The following experiment evaluated the security time of each algorithm with the track-back hop number for different detectable angle θ, as shown in Figure 14. The PU SBRF, in the initial routing stage, adopts flooding protocol, in which each hop is routed in a direction that deviates from the real source node. It makes the security time of the PUSBRF significantly improved in this stage. MoRF and PLAUDIT adopt the traffic balancing to hide the source node sending messages. It is noted that, in this experiment, we filter out the interference of the traffic-balancing strategy to the security time. We observed that MoRF and PLAUDIT have no dominant strategy for increasing the detectable angle. The MST method in this work uses the pseudohelix routing method to effectively expand the detectable angle in each stage of routing.Figure 14
Compare the track-back error hop number (security time) of the four methods at different detectable angles (the specific experimental data are shown in Table7 in the Appendix).


## 6.1. Comparison and Analysis for Communication Overhead

The communication overhead is the basis for measuring the usability of the privacy protection method. In this work, the communication overhead is measured by the hops which messages passed from the source node to the SINK.In the case of given the minimum communication overheadd=50 (that is, it is 50 hops from source nodes to the SINK), Figure 9 shows the maximum number of loops passed by the MST algorithm under different routing probabilitiesp. As can be seen from Figure 9, the communication overhead of the MST protocol increases as the maximum number of loops required by the route increases. It indicates that the more the maximum number of loops passed by messages, the more hops is, due to the longer routing path. It is consistent with the theoretical analysis. In addition, when k>8, the number of hops remains basically constant. This is because in the experiment setting, the number of rings between the source node and the SINK remains around 8. According to the proposed node location protection routing algorithm, when the information is close to the SINK, the routing will no longer be limited to the set of k. It is designed to prevent the information from being lost in the rings and effectively reduce the communication overhead.Figure 9
The communication overhead of the MST method in different routing probabilities along rings (the specific experimental data are shown in Table2 in the Appendix).Table 2
The communication overhead of the MST method in different routing probabilities along rings.
KP/%0305070052.2354.8161.5470.01152.7456.1362.2472.13252.9156.7666.9375.84352.6757.8471.1479.93452.6462.1672.8582.59553.7366.1473.2684.95652.5267.5477.3386.14752.3270.1077.8387.96853.7372.8378.0188.32952.3873.9078.5290.121052.2774.3378.0190.161152.3373.8378.1890.071253.8373.8477.9290.13In conjunction with Figure10, it can be seen that when p = 70%, the superior performance was obtained, which comprehensively compares the three indexes: hop number, ring number passed, and amplitude of the detectable angle. Moreover, compared with the case of {p = 50%, k = 5} and the case of {p = 30%, k = 5}, the communication overhead of the case of {p = 70%, k = 5} increases slightly, but its detectable angle increases by 45%. Furthermore, we can reach the following conclusion that the size of the detectable angle is positively correlated with the number of hops along the rings in the early stage of routing. And, as the increase of the routing probability p that chooses the node from the loop-left node set, this positive correlation also tends to be significant. Furthermore, as the increase of hops, we found two kinds of interesting phenomena. (1) The detectable angle is suddenly enlarged. It is due to the fact that, in the multi-SINK network, message may leap from one helix formed by a certain SINK to another during the routing process (details in Algorithm 1: line 8–13), named the transition phenomenon of message routing between rings. (2) The detectable angle gradually expands to a certain maximum and then gradually shrinks. It mainly occurs in the events with high probability p. Due to the characteristics of helix, it is understandable that messages have higher chances of routing along the rings in a roundabout way. It is noted that, in this stage, the decrease of the detectable angle has no explicit relation with the change of detectable domain obtained by attackers. There are two main scenarios in our observations. (1) The distance between the focuses of routing paths and the source node is greater than the distance between the source node and the SINKs. In the multi-SINK network, it means that the source node and all the SINKs would be in the ipsilateral open sector, which results in the bidirectional node location attack failure. (2) The source node may be outside the detectable domain formed by attackers, due to the transition phenomenon. In short, under the MST protocol, along with the routing of the packets, the probability of the source node being traced back is reduced. Correspondingly, the risk of node location exposure is reduced. It is consistent with previous theoretical analyses.Figure 10
The communication overhead of the MST method at different detectable angles (the specific experimental data are shown in Table3 in the Appendix).Table 3
The communication overhead of the MST method at different detectable angles.
θP/%03050703075.0075.0240.0020.124082.3076.2840.8221.105085.0378.5448.9425.336086.1955.0730.057060.5233.158065.9841.289075.1345.7610044.3711047.2412050.26In addition to the maximum number of rings required that affects the communication overhead, the distance (the count of hops) between the source node to the SINK is also an index that uses to investigate the communication overhead of different routing protocols. Figure11 illustrates the impact of distance on the communication overhead, using the same experiment settings as before. The experiment shows that when p = 70%, MST algorithm has a lower hop count and communication overhead than other cases. Specifically, in the case of p = 90%, the routing path along the spiral ring is too long. It directly leads to a larger detectable angle but with more communication overhead. While in the case of p = 50%, the routing path along the spiral ring maybe too short, even causing the strategy probability to failure. Although communication overhead is low, in this case, the detectable domain formed by the detectable angle becomes smaller, and the risk of exposure of the resource node is greater.Figure 11
The communication overhead of the MST method in different distances from the source node to SINK (the specific experimental data are shown in Table4 in the Appendix).Table 4
The communication overhead of the MST method in different distances from the source node to SINK.
dP/%5070903032.2136.5440.124050.1055.1262.825057.3062.1570.906072.9282.8091.447085.3894.62112.818089.16121.32139.3190120.14132.32150.56100131.89148.64168.80110142.53158.56180.07120158.14173.65201.35130167.59183.27214.25140178.29195.71223.57In addition, givenp = 70%, we compared MST and the other three well-known algorithms in the communication overhead with different detectable angles. As shown in Figure 12, the communication overhead of four methods increases with the increase of the detectable angle. Specifically, the communication overhead of MoRF and PLAUDIT increases linearly with the increase of the detectable angle, while MST only presents sublinear growth. As PU SBRF adopts flooding protocol to generate multiple phantom source nodes that causes a large initial angle, the detectable angle formed by MST is smaller than that of PU SBRF in the early stage of routing; however, in this stage, the communication overhead of PU SBRF is a linear function of the parameter n (n represents the number of the phantom source nodes generated), which is much larger than the communication overhead of the other three algorithms. Moreover, under the same experimental settings, the maximum detectable angle that can be formed by MST is much larger than that of the other three algorithms. The experiment result shows that MST can reach a detectable angle of more than 120 degrees, while MoRF, PU SBRF, and PLAUDIT can only reach 60 degrees, 50 degrees, and 80 degrees, respectively. In general, the communication overhead of MST increases with the increase of the detectable angle, but the increasing trend is gentle, which is acceptable in the real environment.Figure 12
Compare the communication overhead of the four methods at different detectable angles (the specific experimental data are shown in Table5 in the Appendix).Table 5
Compare the communication overhead of the four methods at different detectable angles.
θMethodsPU SBRFMoRFPLAUDITMST1010.0318.8327.9314.542014.2626.0333.1520.023023.1235.4438.2325.294043.2240.0845.1431.685047.9242.9553.2338.446052.3455.2745.037062.1651.328065.3261.879047.2810051.7511057.4412063.00


## 6.2. Comparison and Analysis for Security Time

In this work, we use the security time to measure the security performance of protocols. The security time means the sum of hops that attackers need to trace from the SINK to the source node [17]. Similar to Section 5.1, given a certain distance (100 hops with 12 rings in the experiment setting), we verify the relationship between the number of rings passed and the detectable angle formed, as shown in Figure 13.Figure 13
The maximum detectable angle formed by the MST method in different routing probabilities along rings (the specific experimental data are shown in Table6 in the Appendix).Table 6
The maximum detectable angle formed by the MST method in different routing probabilities along rings.
kP/%507090010.0010.0010.00113.4018.2021.31221.2325.1431.94328.9032.6337.82432.2749.7852.33543.1958.8465.09652.9975.3682.30763.2283.5685.98863.9592.16107.63968.39112.33115.291070.38117.65126.891175.36126.89126.891281.33126.89126.89The experiment result shows that, with the increase of the maximum number of rings passed, the detectable angle increases gradually. The larger the detectable angle is, the smaller the detectable domain the attacker gets and the less the probability of the source node being exposed, and vice versa. A relatively small detectable domain would improve the nontraceability of the source node, guaranteeing the location privacy of the source node. When the detectable angleθ=75withp=70%and rings=8 or θ=110withp=70%and rings=9, MST obtains the superior comprehensive performance. It should be noted that a detectable angle that is too large or too small can cause the routing protocol to fail, as it is an art of balance between privacy protection and the communication overhead.Table 7
Compare the track-back error hop number (security time) of the four methods at different detectable angles.
θMethodsPU SBRFMoRFPLAUDITMST305.002.592.683.91407.585.767.456.925010.026.657.387.78607.507.7512.10707.6512.65808.1313.469013.4610016.3511018.2912018.94Theoretically, track-back hop number [18], average track-back time [26], and traffic confusion degree [8] can all be used as evaluation indexes to measure the security time. In order to unify, we take the track-back hop number as the evaluation indicator. The following experiment evaluated the security time of each algorithm with the track-back hop number for different detectable angle θ, as shown in Figure 14. The PU SBRF, in the initial routing stage, adopts flooding protocol, in which each hop is routed in a direction that deviates from the real source node. It makes the security time of the PUSBRF significantly improved in this stage. MoRF and PLAUDIT adopt the traffic balancing to hide the source node sending messages. It is noted that, in this experiment, we filter out the interference of the traffic-balancing strategy to the security time. We observed that MoRF and PLAUDIT have no dominant strategy for increasing the detectable angle. The MST method in this work uses the pseudohelix routing method to effectively expand the detectable angle in each stage of routing.Figure 14
Compare the track-back error hop number (security time) of the four methods at different detectable angles (the specific experimental data are shown in Table7 in the Appendix).


## 7. Conclusion and Future Scope

In this paper, we presented a kind of bidirectional location privacy attack and defense mechanism for UnWSNs. Specifically, to prevent adversaries from reasoning or backtracking the source nodes and SINK nodes based on the message propagation path, we propose a pseudospiral routing protocol based on the Archimedes curve. In addition to this, the paper constructs a one-by-one mapping relationship between Vcell and SINK based on the Voronoi rule, aiming to optimally balance routing paths with privacy-preserving capabilities given the routing tolerance parameters.Till date, there is no proper secure routing mechanism for UnWSNs capable of dynamically adapting message routing to the evolution of the adversary’s attack capabilities. And, even very limited work (including the current version of this paper) implements pseudomessage obfuscation assuming only that adversary attack capabilities do not accumulate with observations.So, in the next version, we plan to dynamically evolve the adversary’s attack capability by incorporating the historical information distribution behavior of each sensor in the previous time window into the adversary’s observation knowledge and use Stackelberg game to guide the sensors in generating pseudomessage as a way to achieve an optimal balance of node location privacy protection and effectiveness in UnWSNs.



---

*Source: 5539382-2021-05-31.xml*