Privacy Preserving Solution for the Asynchronous Localization of Underwater Sensor Networks

I. Introduction

INTERNET of underwater things (IoUTs) is defined as a world-wide network that incorporates underwater physical process, ubiquitous computation, efficient communication and reliable control [1]. In IoUTs, one of the most promising technologies is to utilize underwater sensor networks (USNs) to monitor the sea area. The USNs can support applications in various areas such as marine resource protection, gas and oil spill monitoring, data collection, disaster warning and mine reconnaissance (see [2]–[6] and references therein). For the applications of USNs, the precise localization of sensor nodes has become one of the primary prerequisites. This critical importance arises from its fundamental role in the sensing, communication and control of vast unexplored ocean volume, because these commands are valid only when the location information of sensor nodes is accurate.

In general, the localization schemes developed for sensor networks that can achieve high-accuracy localization are based on time. The time-based schemes employ various mechanisms such as time of arrival (TOA), time of flight (TOF), or time difference of arrival (TDOA) to measure distances. Since the distance measurement is derived from the time (or time difference), the time-based schemes rely heavily on the clock synchronization assumption of sensor nodes. For terrestrial sensor networks, the clock synchronization assumption can be easily founded through the assistance of global positioning system (GPS). However, the unique characteristics of USNs make underwater localization more [7]. For instance, radio waves are strongly absorbed in water, and GPS technology is not available for USNs. Moreover, the propagation delay of acoustic speed ($\approx 1500$ m/s) is five orders of magnitude higher than in radio frequency terrestrial channels ($\approx 3\times 10^{8}$ m/s). As a result, the time clocks in USNs are usually asynchronous, which make it difficult to acquire the accurate distance measurement. Although the received signal strength (RSS) technology [2] does not require the clock synchronization assumption, RSS signals are usually inaccurate in water. On the other hand, the nodes in water often have passive motions driven by water current, which results in the differences of round-trip propagation delays between any two nodes. Therefore, the localization schemes developed for terrestrial sensor networks [8]–[11] cannot be directly applied to USNs.

In order to achieve effective localization for IoUTs, some asynchronous localization algorithms have been developed, e.g., [12]–[15]. These algorithms mainly involve the following process. 1) Anchor discovery: several non-collinear anchor nodes are deployed in the network to provide localization reference for sensor nodes; 2) Distance measurement: the distance measurements are derived by multiplying the time (or time difference) with the transmission speed; 3) Location estimation: with the positions of anchor nodes and the measured distances, optimal or suboptimal estimators are designed to calculate the locations of sensor nodes. In such a process, the privacy preservation is not taken into consideration, since the positions of anchor nodes are directly revealed to the networks. However, the USNs are usually deployed in harsh or even insecure environment, and security threats cannot be avoided. Ignoring the effect of privacy preservation can lead to privacy leakage or even failure of the localization [16]. For example, malicious nodes can easily attack the anchor nodes and destroy the whole localization system if they harvest the locations of anchor nodes. Inspired by this, many privacy-preserving localization schemes have been proposed. For instance, the encryption technique was adopted in [17] and [18], through which privacy-preserving schemes were designed for indoor localization. In [19] and [20], the privacy preserving summation (PPS) strategy was employed to hide private location information of anchor nodes. Nevertheless, the localization schemes in [17]–[20] relied on the assumption of synchronous clock, i.e., the transmitter-receiver synchronization was assumed to be ensured. Meanwhile, the mobility characteristic of nodes was not considered in [17]–[20], i.e., the nodes were assumed to be static. As mentioned above, the clocks in USNs are always asynchronous, wherein the nodes often have passive motions. Ignoring the above characteristics can increase ranging errors and reduce localization accuracy. Per knowledge of the authors, how to design a localization algorithm that jointly considers the asynchronous clock, mobility and privacy preservation is not well studied.

This paper develops a privacy preserving solution for the asynchronous localization of USNs. We first present a hybrid network architecture, which includes four types of nodes, i.e., surface buoys, anchors, active sensors and ordinary sensors. In order to eliminate the effects of asynchronous clock and mobility, an asynchronous localization protocol is developed, through which PPS and privacy-preserving diagonal product (PPDP) based localization algorithms are designed to hide privacy information. Main contributions lie in two aspects:

1) Asynchronous Localization Protocol With the Consideration of Asynchronous Clock and Mobility: An asynchronous localization protocol is provided to eliminate the effect of asynchronous clock and mobility, through which the relationship between propagation delay and location is constructed. Different from the existing works [17]–[20], the clocks between anchors and sensors are not required to be synchronized. Meanwhile, the proposed localization protocol in this paper can compensate both the influences of clock skew and offset as compared with the works [12], [13], [21].

2) Asynchronous Localization Algorithm With the Consideration of Privacy Preservation: Without adopting any homomorphic encryption technique, PPS and PPDP based asynchronous localization algorithms are designed for USNs to hide the private location information. Compared to the existing works [14], [15], the position information of anchor nodes in this paper does not require to be revealed. Per knowledge of the authors, this is the first work that employs privacy preservation strategy into the asynchronous localization of USNs.

II. Related Works

Recently, the localization of terrestrial sensor networks has been extensively investigated. For instance, a divide-and-conquer strategy that enabled sparse localization of sensor nodes was developed in [22]. In [23], a viable kernel-based algorithm was presented to solve the localization problem. Also of relevance, some other localization algorithms were proposed for terrestrial sensor networks (see [24] and the references therein). However, these algorithms cannot be directly applied to USNs due to the unique characteristics of underwater environment. In the following, we review literatures on the topic of asynchronous localization of USNs.

In [21], a silent localization scheme was developed, where the underwater sensor nodes did not actively transmit any message. Based on this, an on-demand asynchronous localization (ODAL) scheme was provided in [12]. It can be seen that the mobility characteristic of USNs in [12], [21] was not considered. To handle this issue, Tsai et al. [25] developed a hybrid mobile localization algorithm for USNs. In [26], a prediction-based localization algorithm called scalable localization with mobility prediction (SLMP) was designed to predict the locations of sensor nodes. More recently, a mobility prediction based asynchronous localization algorithm was given in [13]. Nevertheless, the clock model in [12], [13], [21], [25], [26] ignored the clock skew, and this assumption can increase the synchronization error when the localization window was not small. With this consideration, some joint localization and synchronization algorithms have been proposed. For instance, a multi-phase solution to localization and synchronization was presented in [14], where the clock skew and offset were both considered. Different from [14], a unified framework was presented in [27], where the localization and synchronization tasks can be achieved simultaneously. In [28], an autonomous underwater vehicle (AUV) was employed as the anchor node, through which an AUV-aided asynchronous localization strategy was presented. Reference [29] studied a joint localization and tracking issue for AUV. In order to reduce the linearization errors, a follow-up work [30] was given to present an unscented transform-based asynchronous localization algorithm. Also of relevance, some underwater asynchronous localization algorithms were proposed in [31]–[33]. However, the major focus in the above studies is the design of communication protocol to localize sensor nodes, where the privacy preservation issue is not considered. It is worth mentioning that, the privacy preservation is critical for the success of localization process. With consideration of the mobility, how to incorporate the privacy preservation into the asynchronous localization of USNs is largely unexplored.

To avoid information leakage, some privacy-preserving localization [17], [18] adopted homomorphic encryption technique to hide the position information of indoor sensor nodes. Other encryption technique-based privacy preservations were developed in [16], [34]–[36]. Although the encryption technique can provide strong privacy preservation performance, its communication and computational overheads are high. Thereby, the encryption technique is not suitable for underwater localization [16], due to the limited bandwidth and energy of USNs. Inspired by this, some researchers attempt to use the signal processing solutions to preserve privacy data, whose main idea is to add noises to the privacy data. For instance, the authors in [19], [20] adopted PPS into TDOA-based localization, through which two privacy-preserving least squares estimators were designed. In [37], a privacy preserving mechanism was presented for the position estimation, and a differential privacy based privacy-preserving indoor localization scheme was designed in [38]. Nevertheless, these studies rely on the synchronous assumption, and they cannot be directly applied to the asynchronous localization. This paper gives a privacy-preserving localization solution for USNs, and more importantly, we consider more complex but realistic underwater environment, i.e., asynchronous clock and mobility characteristics.

III. Network Architecture and the Asynchronous Localization Protocol

A Network Architecture

In order to realize privacy-preserving asynchronous localization for USNs, we provide a network architecture that includes four different types of nodes, as depicted in Fig. 1.

Figure  1.  Network architecture of USNs.

DownLoad: Full-Size Img PowerPoint

1) Surface Buoys: Surface buoys are installed with GPS to acquire their accurate time references and positions through electromagnetic communication. The role of surface buoys is to provide self-localization and clock synchronization services for anchor nodes.

2) Anchor Nodes: Anchor nodes are powerful fixed nodes, and they make direct communication with surface buoys. Similar to the assumption in [26], [39], it is assumed that the time clocks of anchor nodes are synchronized and the locations are pre-known by using some existing technologies, e.g., the localization approach in [40].

3) Active Sensor Node: Active sensor nodes initiate the whole localization process by broadcasting timestamps to the networks. Due to the effect of water current, active sensor nodes can move passively, whose velocities can be accurately measured by Doppler velocity log (DVL) or fiber optic gyroscope (FOG). Particularly, the locations of active sensor nodes are required to be estimated and protected. It is emphasized that the clocks of active sensor nodes are not well synchronized with the real time.

4) Ordinary Sensor Nodes: Ordinary sensor nodes are low-complexity nodes, and they cannot initiatively start the whole localization process, i.e., they just passively listen to the networks and then send state noises to anchor nodes. The locations of ordinary sensor nodes are required to be estimated and protected. Similar to active sensor nodes, ordinary sensor nodes can move passively, whose velocities can be accurately measured. Besides, the clocks of ordinary sensor nodes are asynchronous.

B Asynchronous Localization Protocol

With the above network architecture, the localization process is divided into two subprocesses: a) active sensor localization; b) ordinary sensor localization. Without loss of generality, one active sensor node and one ordinary sensor node are considered here, while the method for single node can be easily extended to the other nodes. Besides, each node can hear message only from its neighboring nodes, i.e., each node cannot hear everybody else due to its limited sensing range. Thus, it is assumed that $m$ anchor nodes are deployed in the sensing range of active and ordinary nodes, where $m\geq 4.$ Meanwhile, the IDs of neighboring anchor nodes are pre-known to active and ordinary sensor nodes.

At the beginning, active sensor node sends out an initiator message to its neighboring nodes. Upon receiving the initiator message, anchor nodes record and reply the initiator message. Meanwhile, ordinary sensor node passively listens to the messages from active sensor node and anchor nodes. Since the exchange process can be quickly completed, it assumed that the positions of active and ordinary sensor nodes are fixed during the timestamp exchange process. The timestamp transmission process can be illustrated by Fig. 2, and some important notations are listed in Table I. Accordingly, the asynchronous localization protocol is detailed as follows.

Table  I.  Notation Definitions

Notation		Description
$T_{\rm{a,a}}$		Time when active sensor sends initiator message
$t_{{\rm{a}},i}$		Time when anchor $i$ receives initiator message
$t_{i,i}$		Time when anchor $i$ sends message
$t_{j,i}$		Time when anchor $i$ receives message from anchor $j$
$T_{i,{\rm{a}}}$		Time when active sensor receives message from anchor $i$
$T_{\rm{a,p}}$		Time when ordinary sensor receives message from active sensor
$T_{i,{\rm{p}}}$		Time when ordinary sensor receives message from anchor $i$
$\varpi _{i,1}$		Time measurement noise between anchor $i$ and anchor $1$
$\varpi _{i,{\rm{p}}}$		Time measurement noise between anchor $i$ and ordinary sensor

 | Show Table

DownLoad: CSV

Figure  2.  Description of the timestamp transmission process.

DownLoad: Full-Size Img PowerPoint

1) At time $T_{\rm{a,a}}$, active sensor node sends out an initiator packet to the networks, whose local length is $t_{\rm{r}}$. The packet includes $t_{\rm{r}}$ and the sending order of anchor nodes, i.e., $i\in \{1,\ldots,m\}$. Subsequently, active sensor node switches into waiting mode for the replies from the other nodes.

2) At time $t_{{\rm{a}},i},$ anchor node $i$ receives the initiator packet, and then it switches into waiting mode. At time $t_{j,i},$ anchor node $i$ receives message from anchor node $j\in \{1,\ldots,i-1\}$. After the message from anchor node $i-1$ has been received, anchor node $i$ sends out its message at time $t_{i,i}$. The length of this message is $t_{{\rm{r}},i},$ while this message includes $t_{{\rm{a}},i}$, $\{t_{j,i}\}_{\forall j}$ for $j<i$, $t_{i,i}$, $t_{{\rm{r}},i},$ and the disguised states of anchor node $i$. Of note, the disguised states can be acquired by adding noises to the real states, as presented in Section IV.

3) At time $T_{i,{\rm{a}}},$ active sensor node receives the reply from anchor node $i$. After receiving replies from all anchor nodes, active sensor node ends its waiting mode. Accordingly, active sensor node collects the following measurements

4) Ordinary sensor node passively listens to the networks, and it sends out state noises to anchor nodes as required. Accordingly, ordinary sensor node has the following timestamp measurements from anchor nodes

5) With the collected timestamps in (1) and (2), two asynchronous localization algorithms are given to estimate the positions of active and ordinary sensor nodes at timestamps $T_{\rm{a,a}}$ and $T_{\rm{a,p}}$, as provided in Section IV.

Different from the simplified model in [12], [13], [21], a clock model including time skew and offset is considered

where $T_{{\rm{a}}}$ and $T_{{\rm{p}}}$ are the local clocks of active and ordinary sensor nodes, respectively. In addition, $\alpha _{{\rm{a}}}$ denotes the clock skew between active sensor node and real time $t$, while $\alpha _{{\rm{p}}}$ denotes the clock skew between ordinary sensor node and real time $t$. Moreover, $\beta _{{\rm{a}}}$ and $\beta _{{\rm{p}}}$ represent the clock offsets of active sensor node and ordinary sensor node, respectively. Referring to [28], one knows $\alpha _{{\rm{a}}}$ and $\alpha _{{\rm{p}}}$ lie in [1 − 2 × 10⁻⁴, 1 + 2 × 10⁻⁴].

Remark 1: It is noted that, the asynchronous localization protocol in this paper is similar to the ones in [12], [13], [30]. Nevertheless, the asynchronous localization protocol in this paper is essentially different from the ones in [12], [13], [30]. Two reasons are associated with this judgement: 1) The clock model in [12], [13] ignores the clock skew (i.e., $\alpha _{{\rm{a}}} = 1$), and thus the localization protocol in [12], [13] cannot remove the effect of clock skew. Different from the above simplified clock model, the clock skew and the clock offset are both considered in this paper. 2) By revealing disguised positions to the networks, the localization protocol in this paper can hide the private location information of anchor nodes, however the protocols in [12], [13], [30] cannot solve this issue.

Due to the mobility characteristic, the above localization protocol should be periodically enforced to update the position information. However, this implementation can result in a waste of communication costs. In order to handle this issue, we develop a mobility compensation strategy, whose aim is to balance the tradeoff between communication cost and localization accuracy. Then, the time axis is divided into multiple measurement windows with length set to $T_{\rm{w}}$ (see Fig. 3). The position vectors of active sensor node at timestamps $T_{\rm{a,a}}$ and $T_{\rm{a,a}}^{{\#}}$ are denoted as ${{p}}_{{\rm{a}}}$ and ${{p}}_{{\rm{a}}}^{{\#}},$ respectively. To be specific, the position at timestamps $T_{{\rm{a,a}}}$ and $T_{\rm{a,a}}^{{\#}}$ is updated through the proposed localization protocol. At timestamp $T_{\rm{a,a}}^*\in$ $(T_{\rm{a,a}}$, $T_{\rm{a,a}}^{{\#}}],\ $the position can be updated as

where $\delta \in {\mathbb{R}}^{+}$ is the actual sampling interval. ${\vec{T}}_{\rm{a,a}} = T_{\rm{a,a}}+ m_{{\rm{a}}}\delta \alpha _{{\rm{a}}},$ where $m_{{\rm{a}}} = 0,\ldots ,n_{{\rm{a}}}$ and $n_{{\rm{a}}} = \left\lfloor (T_{{\rm{a,a}}}^{\ast }-T_{\rm{a,a}})/(\delta \alpha _{{\rm{a}}})\right\rfloor .$ Besides, ${{v}}_{{\rm{a}}}({\vec{T}}_{\rm{a,a}})$ represents the velocity vector of active sensor node at timestamp ${\vec{T}}_{\rm{a,a}},$ which can be measured by DVL or FOG. Note that the position information at timestamps $T_{\rm{a,a}}$ and $T_{\rm{a,a}}^{{\#}}$ can be estimated with the algorithm in Section IV-A. Thereby, the clock skew $\alpha _{{\rm{a}}}$ can be deduced by an exhaustive search with relationship of ${{p}}_{{\rm{a}}}^{{\#}}-{{p}}_{{\rm{a}}} = \delta \alpha _{{\rm{a}}}\sum\nolimits_{m_{{\rm{a}}} = 0}^{n_{{\rm{a}}}^{{\#}}} {{v}}_{{\rm{a}}}({\vec{T}}_{\rm{a,a}})$ where $n_{{\rm{a}}}^{{\#}} = \left\lfloor (T_{\rm{a,a}}^{{\#}}-T_{\rm{a,a}})/(\delta \alpha _{{\rm{a}}})\right\rfloor .$ Of note, $\left\lfloor \cdot \right\rfloor$ is the floor function.

Figure  3.  Example for the structure of measurement window.

DownLoad: Full-Size Img PowerPoint

Similar to the active sensor node, the position vectors of ordinary sensor node at timestamps $T_{\rm{a,p}}$ and $T_{\rm{a,p}}^{{\#}}$ are expressed as ${{p}}_{{\rm{p}}}$ and ${{p}}_{{\rm{p}}}^{{\#}},$ respectively. The position at timestamps $T_{\rm{a,p}}$ and $T_{\rm{a,p}}^{{\#}}$ is updated by the localization protocol in Section IV-B. At timestamp $T_{\rm{a,p}}^*\in$ $(T_{\rm{a,p}}$, $T_{\rm{a,p}}^{{\#}}],\ $the position is updated as

where ${\vec{T}}_{\rm{a,p}} = T_{\rm{a,p}}+m_{{\rm{p}}}\delta \alpha _{\rm{p}}$ for $m_{{\rm{p}}} = 0,\ldots ,n_{{\rm{p}}}$ and $n_{{\rm{p}}} = \lfloor (T_{\rm{a,p}}^*- T_{\rm{a,p}})/(\delta \alpha _{{\rm{p}}})\rfloor .$ In addition, ${{v}}_{{\rm{p}}}({\vec{T}}_{\rm{a,p}})$ denotes the velocity vector of ordinary sensor node at timestamp ${\vec{T}}_{\rm{a,p}},$ and $\alpha _{{\rm{p}}}$ can be deduced by the relationship of ${{p}}_{{\rm{p}}}^{{\#}}-{{p}}_{{\rm{p}}} = \delta \alpha _{{\rm{p}}}\sum\nolimits_{m_{{\rm{p}}} = 0}^{n_{{\rm{p}}}^{{\#}}}{{v}}_{{\rm{p}}}({\vec{T}}_{\rm{a,p}})$ where $n_{{\rm{p}}}^{{\#}} = \lfloor (T_{\rm{a,p}}^{{\#}}-T_{\rm{a,p}})/(\delta \alpha _{{\rm{p}}})\rfloor .$

With the above localization protocol, the following two problems require to be solved for the localization algorithms.

Problem 1 (Privacy-Preserving Asynchronous Localization for Active Sensor Node): In USNs, the clocks are asynchronous and the position information is required to be protected. Inspired by this, we attempt to design a privacy-preserving asynchronous localization algorithm for active sensor node, where active sensor node initiates the localization process by broadcasting message to the networks. This problem is reduced to the estimation of ${{p}}_{ {\rm{a}} }$ with the collected timestamps in (1).

Problem 2 (Privacy-Preserving Asynchronous Localization for Ordinary Sensor Node): Different from the active sensor node, the ordinary sensor node cannot initiatively broadcast timestamps to the networks. Thereby, the localization algorithm designed for active sensor node is not suitable for ordinary sensor node. Inspired by this, we aim to design a privacy-preserving asynchronous localization algorithm for ordinary sensor node. This problem can be reduced to the estimation of ${{p}}_{ \rm{{\rm{p}}} }$ with the collected timestamps in (2).

IV. Asynchronous Localization Algorithms

We first present a PPS-based asynchronous localization algorithm for active sensor node. Note that the PPS-based localization is not suitable for ordinary sensor node. Then, a PPS and PPDP based asynchronous localization algorithm is designed for ordinary sensor node. Finally, we present the consequence when there exist dishonest nodes.

A PPS-Based Localization for Active Sensor

In order to remove the effect of asynchronous clock, we define the following time difference, i.e.,

Without loss of generality, we assume that all nodes including anchor nodes, active and ordinary sensor nodes have the same measurement quality. Particularly, the measurement noise of each local measurement is a random variable with zero mean and variance $\sigma _{\rm{mea}}^{2}$, which is decided by the underlying signal processing in the presence of multipath propagation and ambient noise. Thereby, the relationship between time differences and propagation delays is constructed as

where $\tau _{{\rm{a}},i}$ is the one-way propagation delay between active sensor node and anchor node $i$, $\tau _{{\rm{a}},1}$ is the one-way propagation delay between active sensor node and anchor node $1$, $t_{\rm{a,a}}$ is the real time when the initiator message is sent to the network. Besides, $\varpi _{{\rm{a}},i}$ and $\varpi _{{\rm{a}},1}$ represent the measurement noises, which satisfy the distributions of $\varpi _{{\rm{a}},i}\sim {\cal{N}}(0,$ $\sigma _{\rm{mea}}^{2})$ and $\varpi _{{\rm{a}},1}\sim {\cal{N}}(0,$ $\sigma _{\rm{mea}}^{2})$, respectively. Based on this, the noise $\varpi _{i,1}$ satisfies the distribution of $\varpi _{i,1}\sim {\cal{N}}(0,$ $2\sigma _{\rm{mea}}^{2}).$

With (7), we have the following distance difference

where $\Upsilon _{i,1} = c \Delta {\cal{T}}_{i,1}$ is the measured distance difference for anchor node $i$, $d_{{\rm{a}},i} = c \tau _{{\rm{a}},i}$ is the relative distance between active sensor node and anchor node $i$, while $d_{{\rm{a}},1} =c \tau _{{\rm{a}},1}$ is the relative distance between active sensor node and anchor node $1$. Moreover, $e_{i,1} = c \varpi _{i,1}$ is the noise of distance measurement, satisfying the distribution of $e_{i,1}\sim {\cal{N}}(0,2 c ^{2}\sigma _{\rm{mea}}^{2})$.

It is denfined that ${{x}}_{{\rm{a}}} = [{{p}}_{{\rm{a}}}^{T},$ $d_{{\rm{a}},1}]^{T}.$ Based on (8), we formulate the following least squares (LS) problem, i.e.,

Denote the position vector of anchor node $i\in \{1,\ldots,m\}$ as ${{p}}_{i}\in {\mathbb{R}}^{3\times 1}$. Then, the nonlinear equation (9) can be transformed into the following linear LS problem

where ${{A}} =[{{a}}_{1},\ldots,{{a}}_{m-1}]^{T}$ and ${{B}}$ $=$ $[{{b}}_{1},\ldots,{{b}}_{m-1}]^{T}$. Particularly, the $j$-th element of ${{A}}$ is defined as ${{a}}_{j} =$ $[({{p}}_{j+1}-{{p}}_{1})^{T}$, $\Upsilon _{j+1,1}]$ for $j\in \{1,\ldots,m-1\}.$ Similarly, the $j$th element of ${{B}}$ is given by ${{b}}_{j} = {{p}}_{j+1}^{T}{{p}}_{j+1}-{{p}}_{1}^{T}{{p}}_{1}-\Upsilon _{j+1,1}^{2}.$

By employing the traditional LS estimator, the direct estimation of ${{x}}_{{\rm{a}}}$ can be given as ${\hat{{x}}}_{\rm{a,direct}}$, i.e.,

However, the direct calculation of $\dfrac{1}{2}({{A}}^{T}{{A}})^{-1}{{A}}^{T}{{B}}$ can lead to privacy leakage, since matrices ${{A}}$ and ${{B}}$ contain the position information of anchor nodes. In order to prevent privacy leakage, a PPS strategy is given to calculate ${{A}}^{T}{{A}}$ and ${{A}}^{T}{{B}}$, through which $\dfrac{1}{2}({{A}}^{T}{{A}})^{-1}{{A}}^{T}{{B}}$ can be indirectly calculated. Particularly, the indirect estimation of ${{x}}_{{\rm{a}}}$ is expressed as ${\hat{{x}}}_{\rm{a,indirect}},$ which can be divided into two parts, i.e., ${\tilde{{A}}} = {{A}}^{T}{{A}}$ and ${\tilde{{B}}} = {{A}}^{T}{{B}}.$ Based on this, ${\hat{{x}}}_{\rm{a,indirect}}$ can be defined as

With regard to (12), the main process of PPS-based asynchronous localization algorithm is detailed as follows.

Step 1: Matrix Construction

For the convenience of computation, it is defined that ${\tilde{{A}}} = [{{A}}_{11}$, ${{A}}_{12}$; ${{A}}_{21}$, $A_{22}]$ and ${\tilde{{B}}} = [{{B}}_{11}+{{B}}_{12}$; $B_{21}+B_{22}]$. Referring to the definitions of ${{A}}\ $and ${{B}},$ the elements of ${\tilde{{A}}}$ and ${\tilde{{B}}}$ can be described as

Therefore, the estimation of ${{x}}_{{\rm{a}}}$ in (12) can be rewritten as

Step 2: PPS-Based State Calculation

As mentioned in Section III-B, anchor nodes send disguised states to the networks. In this section, the real states of anchor node 1 are given as ${{Y}}_{1}= [(m-1){{p}}_{1}{{p}}_{1}^{T}-(\sum\nolimits_{i = 2}^{m}{{p}}_{i}){{p}}_{1}^{T}- {{p}}_{1}(\sum\nolimits_{i = 2}^{m} {{p}}_{i}^{T}),$ $(m-1){{p}}_{1}{{p}}_{1}^{T}{{p}}_{1}-(\sum\nolimits_{i = 2}^{m}{{p}}_{i}){{p}}_{1}^{T}{{p}}_{1}-{{p}}_{1}(\sum\nolimits_{i = 2}^{m}{{p}}_{i}^{T}{{p}}_{i})]$ and ${{Z}}_{1} = [-{{p}}_{1},$ ${{p}}_{1},$ $(0; -{{p}}_{1}^{T}{{p}}_{1};0)].$ The real states of anchor node $i\in \{2,\ldots,m\}$ are detailed as ${{X}}_{i} = [{{p}}_{i},$ $(0;{{p}}_{i}^{T}{{p}}_{i};0)]$, ${{Y}}_{i} = [{{p}}_{i}{{p}}_{i}^{T}, {{p}}_{i}{{p}}_{i}^{T}{{p}}_{i}]$ and ${{Z}}_{i}$ $=$ $[{{p}}_{i}$, $-{{p}}_{i}$, $(0;{{p}}_{i}^{T}{{p}}_{i};0)].$ In order to calculate ${\tilde{{A}}}$ and ${\tilde{{B}}},$ the summations of these states, i.e., $\sum\nolimits_{i = 2}^{m}{{X}}_{i},$ $\sum\nolimits_{i = 1}^{m}{{Y}}_{i},$ ${{Z}}_{1}\sum\nolimits_{i = 2}^{m}$ diag $(\Upsilon _{i,1},\Upsilon _{i,1}^{2},\Upsilon _{i,1})+\sum\nolimits_{i = 2}^{m}{{Z}}_{i}$diag$(\Upsilon _{i,1},\Upsilon _{i,1}^{2},\Upsilon _{i,1}),$ are required to be known. In the following, we give a PPS-based strategy [19], [20] to calculate these summations.

Anchor node $i\in \{1,\ldots,m\}$ randomly generates matrices ${{S}}_{2,ij}$ and ${{S}}_{3,ij},$ where $\sum\nolimits_{j = 1}^{m}{{S}}_{2,ij} = {{0}}$ and $\sum\nolimits_{j = 1}^{m}{{S}}_{3,ij} = {{0}}.$ Then, anchor node $i$ keeps ${{S}}_{2,ii}$ and ${{S}}_{3,ii}$ in memory, and sends the rest to the other $m-1$ anchor nodes. Meanwhile, anchor node $i$ receives the matrices from the other $m-1$ anchor nodes. By adding the received matrices to ${{S}}_{2,ii}$ and ${{S}}_{3,ii},$ two random matrices ${{\delta }}_{2i}$ and ${{\delta }}_{3i}$ can be obtained. According, the disguised state of ${{Y}}_{i}$ can be represented as ${\tilde{{Y}}}_{i} = {{Y}}_{i}+{{\delta }}_{2i}$ for $i\in \{1,\ldots,m\}.$ Denote the kth column of ${{\delta }}_{3i}$ as ${{\delta }}_{3i,k}$ for $k\in \{1,2,3\}.$ Based on this, the disguised state of ${{Z}}_{i}$ is represented as ${\tilde{{Z}}}_{1} = {{Z}}_{1}+{{\delta }}_{31}$ or ${\tilde{{Z}}}_{i} = {{Z}}_{i}+{{W}}_{i},\ $where ${{W}}_{i} = \left[\dfrac{{{\delta }}_{3i,1}}{\gamma _{i}},\dfrac{{{\delta }}_{3i,2}}{\gamma _{2i}},\dfrac{{{\delta }}_{3i,3}}{\gamma _{i}}\right],$ $\gamma _{i} = \dfrac{\Upsilon _{i,1}}{\sum\nolimits_{i = 2}^{m}\Upsilon _{i,1}}$, and $\gamma _{2i} = \dfrac{\Upsilon _{i,1}^{2}}{\sum\nolimits_{i = 2}^{m}\Upsilon _{i,1}^{2}}$ for $i\in \{2,\ldots,m\}.$ For clear description, the calculation process of $\sum\nolimits_{i = 1}^{m}{{Y}}_{i}$ is described in Fig. 4(a).

Figure  4.  Description of the PPS-based state calculation.

DownLoad: Full-Size Img PowerPoint

With the similar strategy, the state ${{X}}_{i}$ can also be disguised. For instance, anchor node $i\in \{2,\ldots,m\}$ randomly generates matrix ${{S}}_{1,ij}$ in the same size as ${{X}}_{i}$ where $j\in \{2,\ldots,m\},$ such that $\sum\nolimits_{j = 2}^{m}{{S}}_{1,ij} = {{0}}.$ Through state summation, the disguised state of ${{X}}_{i}$ can be represented as ${\tilde{{X}}}_{i} = {{X}}_{i}+{{\delta }}_{1i},\ $where ${{\delta }}_{1i}$ is a random matrix with $i\in \{2,\ldots,m\}.$ Specially, the summation process of $\sum\nolimits_{i = 2}^{m}{{X}}_{i}$ can be described by Fig. 4(b).

Subsequently, anchor node $1$ sends disguised states ${\tilde{{Y}}}_{1}$ and ${\tilde{{Z}}}_{1}$ to the networks, while anchor node $i\in \{2,\ldots,m\}$ sends disguised states ${\tilde{{X}}}_{i}$, ${\tilde{{Y}}}_{i}$ and ${\tilde{{Z}}}_{i}$ to the networks. It is clear that, the real states of anchor nodes are not revealed.

Step 3: Calculation of ${\tilde{{A}}}$ and ${\tilde{{B}}}$

It is noted that $\sum\nolimits_{i = 2}^{m}{\tilde{{X}}}_{i} = \sum\nolimits_{i = 2}^{m}({{X}}_{i}+{{\delta }}_{1i}) = \sum\nolimits_{i = 2}^{m}{{X}}_{i}.$ Applying this property to all the elements, the values of ${{A}}_{11}$ and ${{B}}_{11}$ can be obtained with ${\tilde{{X}}}_{i}$ and ${\tilde{{Y}}}_{i}.$ Meanwhile, the values of ${{A}}_{12},$ ${{A}}_{21},$ ${{B}}_{12}$ and $B_{21}$ can be obtained with ${\tilde{{Z}}}_{i}.$ Moreover, the values of $A_{22}$ and $B_{22}$ can be directly acquired, because $\Upsilon _{i,1}^{2}$ and $\Upsilon _{i,1}^{3}$ are pre-known. Accordingly, the values of ${\tilde{{A}}}$ and ${\tilde{{B}}}$ are indirectly calculated, where the privacy information of anchor nodes is not leaked.

Step 4: Position Estimation

With the results in Step 3, the estimation of ${{x}}_{{\rm{a}}}$ in (13) can be easily calculated. Accordingly, the clock skew $\alpha _{{\rm{a}}}$ can be obtained by an exhaustive search, and hence, we obtain

From (14) and (15), we have

Aa a result, by substituting (16) into (14), the clock offset $\beta _{{\rm{a}}}$ can be calculated as $\beta _{{\rm{a}}} = T_{{\rm{a,a}}}-\alpha _{{\rm{a}}}(t_{{\rm{a}},i}-{t_{\rm{r}}}/{\alpha _{{\rm{a}}}}-\tau _{{\rm{a}},i})$.

B PPS and PPDP Based Localization for Ordinary Sensor

In this section, active sensor node and anchor node $i\in \{1,\ldots,m\}$ provide localization services for ordinary sensor node. In order to remove the effect of clock offset (i.e., $\beta _{{\rm{p}}}$), we define the following time difference, i.e.,

Based on (17), the relationship between time difference and propagation delay can be constructed as

where $\tau _{i,{\rm{p}}}$ is the one-way propagation delay between anchor node $i$ and ordinary sensor node, $\tau _{{\rm{a}},{\rm{p}}}$ is the one-way propagation delay between ordinary sensor node and active sensor node. In addition, $\varpi _{i,{\rm{p}}}$ and $\varpi _{{\rm{a}},{\rm{p}}}$ represent the measurement noises, satisfying the distributions of $\varpi _{i,{\rm{p}}}\sim {\cal{N}}(0,$ $\sigma _{\rm{mea}}^{2})$ and $\varpi _{{\rm{a}},{\rm{p}}}\sim {\cal{N}}(0,$ $\sigma _{\rm{mea}}^{2}).$ Based on this, the noise $\varpi _{i,{\rm{a}},{\rm{p}}}$ satisfies the distribution of $\varpi _{i,{\rm{a}},{\rm{p}}}\sim {\cal{N}}(0,$ $2\sigma _{\rm{mea}}^{2}).$

With (18), we have the following distance difference

where $M_{i} =c \left(t_{i,i}+t_{{\rm{r}},i}-\dfrac{T_{\rm{a,a}}-\beta _{\rm{a}}}{\alpha _{{\rm{a}}}}-\dfrac{t_{\rm{r}}}{\alpha _{{\rm{a}}}}\right)$. In addition, $d_{i,{\rm{p}}} = c \tau _{i,{\rm{p}}}$ is the relative distance between anchor node $i$ and ordinary sensor node, while $d_{{\rm{a}},{\rm{p}}} =c\tau _{\rm{a,p}}$ denotes the relative distance between ordinary sensor node and active sensor node. Besides, $e_{i,{\rm{a}},{\rm{p}}} = c \varpi _{i,{\rm{a}},{\rm{p}}}$ is the noise of distance difference measurement, satisfying the distribution of $e_{i,{\rm{a}},{\rm{p}}}\sim {\cal{N}}(0,2 c ^{2}\sigma _{\rm{mea}}^{2}).$

Since the ordinary sensor node cannot initiatively send timestamps, the clock skew (i.e., $\alpha _{{\rm{p}}}$) cannot be removed by using the relationship in (7). In order to remove the effect of clock skew, we define the following equation

Rearranging (20), one can obtain $\dfrac{\Delta {\cal{T}}_{1,{\rm{a,p}}}}{\Delta {\cal{T}}_{i,{\rm{a,p}}}}(M_{i}+d_{i,{\rm{p}}}-d_{{\rm{a}}, {\rm{p}}}+ e_{i,{\rm{a}},{\rm{p}}}) = M_{1}+d_{1,{\rm{p}}}-d_{{\rm{a}},{\rm{p}}}+e_{1,{\rm{a}},{\rm{p}}},$ i.e., $D_{i,1,{\rm{p}}}M_{i}-M_{1}+(1-D_{i,1, {\rm{p}}}) d_{{\rm{a}},{\rm{p}}}\! =\! d_{1,{\rm{p}}}-D_{i,1,{\rm{p}}}d_{i,{\rm{p}}}\!-\! D_{i,1,{\rm{p}}}e_{i,{\rm{a}},{\rm{p}}}\!+\!e_{1,{\rm{a}},{\rm{p}}}$, where $D_{i,1,{\rm{p}}} \!=\! \dfrac{\Delta {\cal{T}}_{1,{\rm{a,p}}}}{\Delta {\cal{T}}_{i,{\rm{a,p}}}}.$ Based on this, we have

where $Q_{i,1,{\rm{p}}} = D_{i,1,{\rm{p}}}M_{i}-M_{1}$ and $e_{i,1,{\rm{p}}} =$ $e_{1,{\rm{a}},{\rm{p}}}{\small -}D_{i,1,{\rm{p}}}e_{i,{\rm{a}},{\rm{p}}}$.

In order to minimize the measurement noise, we define ${{x}}_{{\rm{p}}} = \left[ {{p}}_{{\rm{p}}}^{T},\;d_{{\rm{a}},{\rm{p}}},\;\;d_{1,{\rm{p}}}\right] ^{T}$, and therefore the following LS estimation problem is formulated, i.e.,

The nonlinear problem in (22) can be transformed into the following linear LS problem

where ${{H}}$ $=$ $[{{h}}_{1},\ldots,{{h}}_{m-1}]^{T}$ and ${{Q}}$ $=$ $[{{q}}_{1},\ldots,{{q}}_{m-1}]^{T}$. Specially, the $j$th element of ${{H}}$ is defined as ${{h}}_{j} = [D_{j+1,1,{\rm{p}}}({{p}}_{{\rm{a}}}-{{p}}_{1})^{T}+ D_{j+1,1,{\rm{p}}}^{2}({{p}}_{j+1}-{{p}}_{{\rm{a}}})^{T}$, $(1-D_{j+1,1,{\rm{p}}})Q_{j+1,1,{\rm{p}}}$, $-Q_{j+1,1,{\rm{p}}}]$ for $j\in \{1,\ldots,m-1\}$. Moreover, the $j$-th element of ${{Q}}$ is ${{q}}_{j} =$ $-Q_{j+1,1,{\rm{p}}}^{2}-(1-D_{j+1,1,{\rm{p}}})^{2}{{p}}_{{\rm{a}}}^{T}{{p}}_{{\rm{a}}}-{{p}}_{1}^{T}{{p}}_{1}+2(1-D_{j+1,1,{\rm{p}}}){{p}}_{{\rm{a}}}^{T}{{p}}_{1}+D_{j+1,1,{\rm{p}}}^{2}{{p}}_{j+1}^{T} {{p}}_{j+1}$.

Remark 2: It is noticed that, at least five reference nodes are required to locate the ordinary sensor node$.$ The reason associated with this design can be summarized as follows: 1) Five unknown parameters are required to be estimated in (23), (i.e., ${{p}}_{{\rm{p}}}\in {\mathbb{R}}^{3\times 1}$, $d_{{\rm{a}},{\rm{p}}}\ $ and $d_{1,{\rm{p}}})$, and thereby five linear independent equations should be constructed; 2) To this end, ordinary sensor node needs to receive localization services from at least five reference nodes, through which the estimation of ${{p}}_{{\rm{p}}}$, $d_{{\rm{a}},{\rm{p}}}\ $ and $d_{1,{\rm{p}}}$ can be guaranteed.

Accordingly, the direct estimation of ${{x}}_{{\rm{p}}}$ can be acquired by using the traditional LS estimator, which is given as

Similar to Section IV-A, the direct calculation of ${{x}}_{\rm{p}}$ can lead to privacy leakage, because matrices ${{H}}$ and ${{Q}}$ contain the position information of anchor nodes. In order to handle this issue, a PPS and PPDP based strategy is given to indirectly calculate ${\hat{{x}}}_{\rm{p,direct}}.$ Motivated by this, we denote ${{H}}^{\rm{T}}{{H}}$ and ${{H}}^{\rm{T}}{{Q}}$ as ${\tilde{{H}}}$ and ${\tilde{{Q}}},$ respectively. As a result, the indirect estimation of ${{x}}_{{\rm{p}}}$ can be expressed as

With regard to (25), the main calculation process for ordinary sensor node is detailed as follows.

Step 1: Matrix Construction

For the convenience of computation, we define ${\tilde{{H}}} = [{{H}}_{11}$, ${{H}}_{12}$, ${{H}}_{13}$; ${{H}}_{21}$, $H_{22}$, $H_{23}$; ${{H}}_{31}$, $H_{32}$, $H_{33}]\in {\mathbb{R}}^{5\times 5}$ and ${\tilde{{Q}}} = [{{Q}}_{11}$; $Q_{21}$; $Q_{31}]\in {\mathbb{R}}^{5}$. Referring to the definitions of ${{H}}\ $ and ${{Q}},$ the elements of ${\tilde{{H}}}$ and ${\tilde{{Q}}}$ are constructed as

Therefore, the estimation of ${{x}}_{{\rm{p}}}$ in (25) can be rewritten as

Step 2: PPS and PPDP Based State Calculation

Similar to Section IV-A, the real states of active sensor node are given as ${\bar{{X}}}_{{\rm{a}}} = [-{{p}}_{{\rm{a}}},$ ${{p}}_{{\rm{a}}}{{p}}_{{\rm{a}}}^{T},$ $-{{p}}_{{\rm{a}}},$ ${{p}}_{{\rm{a}}},$ ${{p}}_{{\rm{a}}},$ ${{p}}_{{\rm{a}}},$ $(0;-{{p}}_{{\rm{a}}}^{T}{{p}}_{{\rm{a}}};0),$ ${{p}}_{{\rm{a}}}{{p}}_{{\rm{a}}}^{T}{{p}}_{{\rm{a}}},$ $(0;-{{p}}_{{\rm{a}}}^{T}{{p}}_{{\rm{a}}};0),$ $(0;{{p}}_{{\rm{a}}}^{T}{{p}}_{{\rm{a}}};0)]$, ${\bar{{Y}}}_{{\rm{a}}} = [{{p}}_{{\rm{a}}},$ $(0;{{p}}_{{\rm{a}}}^{T}{{p}}_{{\rm{a}}};0)]$, ${\bar{{Z}}}_{{\rm{a}}} = [{{p}}_{{\rm{a}}}^{T};$ $(0,{{p}}_{{\rm{a}}}^{T}{{p}}_{{\rm{a}}},0);$ diag$({{p}}_{{\rm{a}}})]$ and ${\bar{{M}}}_{{\rm{a}}} = {{p}}_{\rm{a}}^{T}$. The real states of anchor node $1$ are ${\bar{{Y}}}_{1} = [-{{p}}_{1},$ $(0;{{p}}_{1}^{T}{{p}}_{1};0)]$ and ${\bar{{M}}}_{1} = {{p}}_{1}$. The real states of anchor node $i\in \{2,\ldots,m\}$ are ${\bar{{X}}}_{i} = [{{p}}_{i},$ ${{p}}_{i}{{p}}_{i}^{T},$ ${{p}}_{i},$ $-{{p}}_{i},$ $-{{p}}_{i},$ $-{{p}}_{i},$ $(0;{{p}}_{i}^{T}{{p}}_{i};0),$ ${{p}}_{i}{{p}}_{i}^{T}{{p}}_{i},$ $(0;{{p}}_{i}^{T}{{p}}_{i};0),$ $(0;-{{p}}_{i}^{T}{{p}}_{i};0)]$, ${\bar{{Z}}}_{i} = [{{p}}_{i},$ ${{p}}_{i},$ diag$({{p}}_{i}^{T}{{p}}_{i};{{p}}_{i}^{T}{{p}}_{i};{{p}}_{i}^{T}{{p}}_{i})]$, and ${\bar{{M}}}_{2} = {{p}}_{{\rm{a}}}-{{p}}_{1}$.

In order to protect the privacy of ${\bar{{X}}}_{{\rm{a}}}$ and ${\bar{{X}}}_{i}$, the random matrix ${{W}}_{1,\bar{i}\bar{j}}$ is generated for node $\bar{i}$ where node $\bar{i}$ denotes active sensor node and anchor node $i$, i.e., $\bar{i}\in \{$$1,2,\ldots,m\}$ and $\bar{j}\in \{$1, $2,\ldots,m\}.$ It is noted that ${{W}}_{1,\bar{i}a}+\sum\nolimits_{j = 2}^{m}{{W}}_{1,\bar{i}\bar{j}} = {{0}}$. Then, node $\bar{i}$ keeps ${{W}}_{1,\bar{i}\bar{i}\;}$ and sends the rest to the other $m-1$ nodes. By adding the received matrices to ${{W}}_{1,\bar{i}\bar{i}\;}$, a random matrix ${{\varphi }}_{1\bar{i}}$ can be obtained. Denote the $k$th column of ${{\varphi }}_{1i}$ as ${{\varphi }}_{1i,k}$ for $k\in \{1,\ldots,12\}$. Based on this, the disguised state of ${\bar{{X}}}_{\bar{\imath}}$ can be represented as ${\tilde{{\bar{{X}}}}_{{\rm{a}}}} = {\bar{{X}}}_{{\rm{a}}}+{{\varphi }}_{1{\rm{a}}}$ or ${\tilde{{\bar{{X}}}}_{i}} = {\bar{{X}}}_{i}+{{K}}_{i}$, where

for $i\in \{2,$$\ldots,m\}.$ Subsequently, active sensor node sends disguised state $\tilde{{\bar{{X}}}}{_{{\rm{a}}}}$, while anchor node $i\in \{2,\ldots,m\}$ sends disguised state ${\tilde{{\bar{{X}}}}_{i}}$ to the networks. Clearly, this process is based on the PPS strategy, while the real states of active sensor and anchor nodes are not revealed.

With the similar strategy, the state ${\bar{{Y}}}_{{\rm{a}}}$ and ${\bar{{Y}}}_{1}$ can also be disguised, i.e., ${\tilde{{\bar{{Y}}}}_{{\rm{a}}}} = {\bar{{Y}}}_{{\rm{a}}}+{{\varphi }}_{2{\rm{a}}}$ and ${\tilde{{\bar{{Y}}}}_{\rm{1}}} = {\bar{{Y}}}_{\rm{1}}+{{\varphi }}_{21}$, where ${{\varphi }}_{2{\rm{a}}}$ and ${{\varphi }}_{21}$ are the random noise generated by active sensor node and anchor node 1, respectively. Then, active sensor node and anchor node $1$ send ${\tilde{{\bar{{Y}}}}_{{\rm{a}}}}$ and ${\tilde{{\bar{{Y}}}}_{\rm{1}}}$ to the networks. In order to protect the privacy of ${\bar{{Z}}}_{i}$ for $i\in \{2,\ldots,m\}$, the ordinary sensor node randomly generates matrix ${{\varphi }}_{3i}$ to anchor node $i$. Denote the $k$th column of ${{\varphi }}_{3i}$ as ${{\varphi }}_{3i,k}$ for $k\in \{1,2,3,4,5\}.$ As a result, the disguised state of ${\bar{{Z}}}_{i}$ is given as $\tilde{{\bar{{Z}}}}{_{i}} = {\bar{{Z}}}_{i}+{{K}}_{3i}$, where ${{K}}_{3i} = \left[\frac{{{\varphi }}_{3i,1}}{\vartheta _{3i}}, \right.$ $\frac{{{\varphi }}_{3i,2}}{\vartheta _{3i}},$ $\frac{{{\varphi }}_{3i,3}}{\vartheta _{3i}},$ $\frac{{{\varphi }}_{3i,4}}{\vartheta _{3i}},$ $\left. \frac{{{\varphi }}_{3i,5}}{\vartheta _{3i}}\right]$ for $i\in \{2,\ldots,m\}$. Subsequently, anchor node $i$ sends $\tilde{{\bar{{Z}}}}{_{i}}$ to active sensor node. Active sensor node obtains ${\tilde{{\bar{{Z}}}}_{i}}{\bar{{Z}}}_{{\rm{a}}}$ and sends it to the networks. For clear description, calculation process of ${\bar{{Z}}}_{i}{\bar{{Z}}}_{{\rm{a}}}$ is shown in Fig. 5(a).

Figure  5.  Description of PPS and PPDP based state calculation.

DownLoad: Full-Size Img PowerPoint

To protect the privacies of ${\bar{{M}}}_{{\rm{a}}}$, ${\bar{{M}}}_{1}$ and ${\bar{{M}}}_{2},$ we construct ${{L}}_{{\rm{a}}} =$ diag $\{\log {\bar{{M}}}_{{\rm{a}}}\}$, ${{L}}_{1} =$ diag $\{\log {\bar{{M}}}_{1}\}$ and ${{L}}_{2} =$ diag $\{\log {\bar{{M}}}_{2}\}$ for active sensor node, anchor nodes $1$, $2$, respectively. This process is named as PPDP, because the adoption of multiplication. Then, the ordinary sensor node generates two random matrices ${{\varsigma }}_{1}$ and ${{\varsigma }}_{2}$ with the same size as ${{L}}_{1}$ and sends them to active sensor node. The active sensor node calculates ${{U}}_{11} = {{L}}_{{\rm{a}}}+{{\varsigma }}_{1}$ and ${{U}}_{12} = {{L}}_{{\rm{a}}}+{{\varsigma }}_{2},$ and then sends them to the anchor nodes 1 and 2, respectively. After, anchor node 1 calculates ${{U}}_{2} =$ ${{U}}_{11}+{{L}}_{1}$ and sends it to ordinary sensor node. Meanwhile, anchor node 2 calculates ${{U}}_{3} =$ ${{U}}_{12}+{{L}}_{2}$ and sends it to ordinary sensor node. The ordinary sensor node retrieves the logarithm matrix by subtracting ${{\varsigma }}_{1}$ and ${{\varsigma }}_{2}$, i.e., ${{U}}_{2}-{{\varsigma }}_{1} = {{L}}_{{\rm{a}}}+{{L}}_{1} =$ diag$\{\log {\bar{{M}}}_{{\rm{a}}}{\bar{{M}}}_{1}\}$ and ${{U}}_{3}-{{\varsigma }}_{2} = {{L}}_{{\rm{a}}}+{{L}}_{2} =$ diag$\{\log {\bar{{M}}}_{{\rm{a}}}{\bar{{M}}}_{2}\}.$ Through the exponential transform, the values of ${\bar{{M}}}_{{\rm{a}}}{\bar{{M}}}_{1}$ and ${\bar{{M}}}_{{\rm{a}}}{\bar{{M}}}_{2}$ can be obtained. This process can be described by Fig. 5(b).

Step 3: Calculation of ${\tilde{{H}}}$ and ${\tilde{{Q}}}$

According to (26), the values of ${{H}}_{11}$, ${{H}}_{12}$, ${{H}}_{13}$, ${{H}}_{21}$, ${{H}}_{31}$, $H_{32}$, ${{Q}}_{11}$, $Q_{21}$ and $Q_{31}$ can be obtained through ${\tilde{{\bar{{X}}}}_{{\rm{a}}}}$, ${\tilde{{\bar{{X}}}}_{i}}$, ${\tilde{{\bar{{Y}}}}_{{\rm{a}}}}$, ${\tilde{{\bar{{Y}}}}_{\rm{1}}}$, ${\tilde{{\bar{{Z}}}}_{i}}{\bar{{Z}}}_{{\rm{a}}}$, ${{U}}_{2}$ and ${{U}}_{3}$. Meanwhile, the values of $H_{22}$, $H_{23}$, $H_{32}$ and $H_{33}$ can be directly acquired, because $D_{i,1,{\rm{p}}}$ and $Q_{i,1,{\rm{p}}}$ are pre-known. Accordingly, the values of ${\tilde{{H}}}$ and ${\tilde{{Q}}}$ are calculated, and more importantly, the privacy can be protected.

Step 4: Position Estimation

Based on Step 3, ${{x}}_{{\rm{p}}}$ in (26) can be easily estimated, i.e., the position of ordinary sensor node can be located under asynchronous clock and privacy preservation.

C Consequence When There Exist Dishonest Nodes

In the above sections, the proposed privacy preserving algorithms need cooperation among nodes, and require each node to be honest. However, underwater nodes are usually deployed in harsh and open environments, making them extremely vulnerable to security attack. For instance, an attacker can cause nodes to have imprecise locations, which leads to the dishonesty of nodes. To cope with this issue, we present the consequence when there exist dishonest nodes.

Without loss of generality, it is assumed that all the nodes are honest in the first localization interval, i.e., $[T_{\rm{a,a}},$ $\delta \alpha _{{\rm{a}}}]$ for the active sensor node and $[T_{\rm{a,p}},$ $\delta \alpha _{{\rm{p}}}]$ for the ordinary sensor node. As a result, from (4), the position vector of active sensor node at timestamp $T_{\rm{a,a}}^{{\#}}$ can be predicted as

By employing the PPS-based localization algorithm in Section IV-A, the position of active sensor node at timestamp $T_{\rm{a,a}}^{{\#}}$ can be estimated as ${\tilde{{p}}}_{T_{\rm{a,a}}^{{\#}}}.$ Thereby, the difference between ${{p}}_{T_{\rm{a,a}}^{{\#}}}$ and ${\tilde{{p}}}_{T_{\rm{a,a}}^{{\#}}}$ can be given as $e _{{\rm{a}}}(T_{\rm{a,a}}^{{\#}}) = \left\vert {{p}}_{T_{\rm{a,a}}^{{\#}}}-{\tilde{{p}}}_{T_{\rm{a,a}}^{{\#}}}\right\vert .$

Similarly, from (5), the position vector of ordinary sensor node at timestamp $T_{\rm{a,p}}^{{\#}}$ can be predicted as

With the PPS-based localization algorithm in Section IV-B, the position of ordinary sensor node at timestamp $T_{\rm{a,p}}^{{\#}}$ can be estimated as ${\tilde{{p}}}_{T_{\rm{a,p}}^{{\#}}}.$ Accordingly, the difference between ${{p}}_{T_{\rm{a,p}}^{{\#}}}$ and ${\tilde{{p}}}_{T_{\rm{a,p}}^{{\#}}}$ can be given as $e _{{\rm{p}}}(T_{\rm{a,p}}^{{\#}}) = \left\vert {{p}}_{T_{\rm{a,p}}^{{\#}}}-{\tilde{{p}}}_{T_{\rm{a,p}}^{{\#}}}\right\vert .$

In the following, let ${\vec{\rho}}$ denote the threshold of $e _{{\rm{a}}}(T_{{\rm{a,a}}}^{{\#}}),$ where ${\vec{\rho}}$ is dependent on the accuracy requirement for the localization system. Particularly, when the condition of $e _{{\rm{a}}}(T_{\rm{a,a}}^{{\#}})>{\vec{\rho}}$ and $e_{{\rm{p}}}(T_{\rm{a,p}}^{{\#}})>{\vec{\rho}}$ holds, the nodes in USNs can be considered to be dishonest, otherwise the nodes are dishonest. In order to show more clearly, Fig. 6 is presented to depict the consequence when there exist dishonest nodes.

Figure  6.  Depiction of consequence when there exist dishonest nodes.

DownLoad: Full-Size Img PowerPoint

V. Performance Analyses

A Equivalence Analyses

We first investigate the equivalences of estimators (12) and (25). Then, the following theorems are given.

Theorem 1: Consider the linear LS problem for active sensor node, as described in (10). By applying the PPS-based asynchronous localization algorithm, the indirect estimation ${\hat{{X}}}_{ {\rm{a,indirect}} }$ in (12) is equivalent to the one in (11).

Proof: It is noted that, ${{A}}_{11}$, ${{A}}_{12},$ ${{A}}_{21},$ ${{B}}_{11}$, ${{B}}_{12}$ and $B_{21}$ can be derived from ${\tilde{{X}}}_{i}$, ${\tilde{{Y}}}_{i}$ and ${\tilde{{Z}}}_{i}.$ Specially,

As ${{\delta }}_{31}\sum\nolimits_{i = 2}^{m}$diag$({\small \Upsilon }_{i,1}$, ${\small \Upsilon }_{i,1}^{2}$, ${\small \Upsilon }_{i,1})+\sum\nolimits_{i = 2}^{m}{{W}}_{i}$diag$({\small \Upsilon }_{i,1}$, ${\small \Upsilon }_{i,1}^{2}$, ${\small \Upsilon }_{i,1}) = {{0}},$ the value of $[{{A}}_{12},{{B}}_{12},(0;B_{21};0)]$ is equivalent to the direct calculation, i.e., ${{A}}_{12},$ ${{B}}_{12}\ $and $B_{21}$ can be correctly calculated. Applying this implementation to the other elements, one has $[{{A}}_{11},{{B}}_{11}] = \sum\nolimits_{i = 1}^{m}{\tilde{{Y}}}_{i} = \sum\nolimits_{i = 1}^{m}{{Y}}_{i}+\sum\nolimits_{i = 1}^{m}{{\delta }}_{2i} = \sum\nolimits_{i = 1}^{m}{{Y}}_{i}$ because $\sum\nolimits_ {i = 1}^{m}{{\delta }}_{2i} = {{0}}.$ Then, it is known that ${{A}}_{11}\ $and ${{B}}_{11}$ can be correctly calculated.

It is noticed that the values of $A_{22}$ and $B_{22}$ can be computed directly by $\Upsilon _{i,1}.$ Moreover, one has ${{A}}_{21} = {{A}}_{12}^{{T}}.$ Thereby, the values of ${{A}}_{11}$, ${{A}}_{12},$ ${{A}}_{21},$ $A_{22},$ ${{B}}_{11}$, ${{B}}_{12}$, $B_{21}$ and $B_{22}$ are equivalent to the direct calculation. Therefore, we can know ${\hat{{X}}}_{\rm{a,indirect}}$ is equivalent to ${\hat{{X}}}_{\rm{a,direct}}$. ■

Theorem 2: Consider the linear LS problem for ordinary sensor node, as shown in (23). By applying PPS and PPDP based asynchronous localization algorithm, estimation ${\hat{{X}}}_{ {\rm{p,indirect}} }$ in (25) is equivalent to the one in (24).

Proof: Referring to the elements of ${{H}}_{11},$ we know that the matrix ${{p}}_{{\rm{a}}}-{{p}}_{1}$ can be obtained from ${\tilde{{\bar{{Y}}}}_{{\rm{a}}}}+{\tilde{{\bar{{Y}}}}_{\rm{1}}.}$ Because of ${{\varphi }}_{2{\rm{a}}}+{{\varphi }}_{21} = {{0}}$, one has ${\tilde{{\bar{{Y}}}}_{{\rm{a}}}}+{\tilde{{\bar{{Y}}}}_{\rm{1}} = }{\bar{{Y}}}_{{\rm{a}}}+{{\varphi }}_{2{\rm{a}}}+{\bar{{Y}}}_{1}+{{\varphi }}_{21} = {\bar{{Y}}}_{{\rm{a}}}+{\bar{{Y}}}_{1},$ i.e., ${{p}}_{{\rm{a}}}-{{p}}_{1}$ can be correctly calculated.

Next, we study the other elements of ${{H}}_{11}.$ Clearly, $-{{p}}_{{\rm{a}}}\sum\nolimits_{i = 2}^{m}D_{i,1,{\rm{p}}}^{3}+\sum\nolimits_{i = 2}^{m}D_{i,1,{\rm{p}}}^{3}{{p}}_{i}$ and $\sum\nolimits_{i = 2}^{m}D_{i,1,{\rm{p}}}^{4}{{p}}_{{\rm{a}}}{{p}}_{{\rm{a}}}^{{T}}$ $+\sum\nolimits_{i = 2}^{m}D_{i,1,{\rm{p}}}^{4} {{p}}_{i}{{p}}_{i}^{{T}}$ can be obtained from ${\tilde{{\bar{{X}}}}_{{\rm{a}}}}$ and ${\tilde{{\bar{{X}}}}_{i}}$ for $i\in \{2,\ldots,m\}$. According to Step 2 in Section IV-B, we have

It is noted that, ${{\varphi }}_{1{\rm{a}}}(:,1:4){\sum\nolimits_{i = 2}^{m}}$ diag $\{(D_{i,1,{\rm{p}}}^{3},$ ${D_{i,1,{\rm{p}}}^{4},}$ ${D_{i,1,{\rm{p}}}^{4},}$ ${D_{i,1,{\rm{p}}}^{4})}\}+\sum\nolimits_{i = 2}^{m}{{K}}_{i}(:,1:4)$diag${(D_{i,1,{\rm{p}}}^{3}}$, ${D_{i,1,{\rm{p}}}^{4},}$ ${D_{i,1,{\rm{p}}}^{4},}$ ${D_{i,1,{\rm{p}}}^{4})} = {{0}}{.}$ Then, $-{{p}}_{{\rm{a}}}\sum\nolimits_{i = 2}^{m}D_{i,1,{\rm{p}}}^{3}+\sum\nolimits_{i = 2}^{m}D_{i,1,{\rm{p}}}^{3}{{p}}_{i}$ and $\sum\nolimits_{i = 2}^{m}D_{i,1,{\rm{p}}}^{4}{{p}}_{{\rm{a}}}{{p}}_{{\rm{a}}}^{T} +$$\sum\nolimits_{i = 2}^{m}D_{i,1,{\rm{p}}}^{4}$ ${{p}}_{i}{{p}}_{i}^{T}$ can be correctly calculated. Moreover, the last element of ${{H}}_{11}$, i.e., $\sum\nolimits_{i = 2}^{m}D_{i,1,{\rm{p}}}^{4}{{p}}_{i}{{p}}_{{\rm{a}}}^{T},$ can be obtained from ${\tilde{{\bar{{Z}}}}_{i}}{\bar{{Z}}}_{1}$ for $i\in \{2,\ldots,m\}$. Because $\sum\nolimits_{i = 2}^{m}D_{i,1,{\rm{p}}}^{4}{{K}}_{3i}(:,1){\bar{{Z}}}_{1}(:,1) = {{0}},$ one has $\sum\nolimits_{i = 2}^{m}D_{i,1,{\rm{p}}}^{4}{{p}}_{i}{{p}}_{{\rm{a}}}^{T} = \sum\nolimits_{i = 2}^{m}D_{i,1,{\rm{p}}}^{4}{\tilde{{\bar{{Z}}}}_{i}(:,1)}{\bar{{Z}}}_{1}(:,1) = \sum\nolimits_{i = 2}^{m}D_{i,1,{\rm{p}}}^{4}$${\bar{{Z}}}_{i}(:,1){\bar{{Z}}}_{1}(:,1).$ Based on this, we know $\sum\nolimits_{i = 2}^{m}D_{i,1,{\rm{p}}}^{4}{{p}}_{i}{{p}}_{{\rm{a}}}^{T}$ can be correctly calculated.

Based on this, we know ${{H}}_{11}$ can be correctly calculated. Applying this implementation to the other parts, the values of ${{H}}_{12}$, ${{H}}_{13}$, ${{H}}_{21}$, ${{H}}_{31}$, ${{Q}}_{11}$, $Q_{21}$ and $Q_{31}$ can be correctly acquired. As $H_{22}$, $H_{23}$, $H_{32}$ and $H_{33}$ are pre-known, ${\hat{{x}}}_{\rm{p,indirect}}$ in (25) is equivalent to ${\hat{{x}}}_{\rm{p,direct}}$ in (24). ■

B Level of Privacy Preservation

In the following, we investigate the level of privacy preservation for the proposed localization algorithms. To support our conclusion, the following definition is provided.

Definition 1 [19]: For node ${\cal{A}}$, it needs extra information to construct at least $N_{{\rm{p}}}$ independent equations to estimate the private position of node ${\cal{B}}$. Then, node ${\cal{B}}$ can preserve $\{N_{{\rm{p}}}\}$-privacy to node ${\cal{A}}$, where $N_{{\rm{p}}} = N_{\rm{scal}}-N_{\rm{eq}}$. Of note, $N_{\rm{scal}}$ denotes the number of unknown scalar variables in the private information of node ${\cal{B}}$, and $N_{\rm{eq}}$ is maximum number of independent equations that node ${\cal{A}}$ can construct.

Based on Definition 1, we have the following Theorem.

Theorem 3: With the LS estimator (12), the PPS-based asynchronous localization algorithm for active sensor node can guarantee the following levels of privacy preservation: 1) To anchor node $1,$ the active sensor node can preserve $\{3\}$-Privacy while anchor node $i\in \{2,\ldots,m\}$ can preserve $\{3m-7\}$-privacy; 2) To anchor node $i\in\{2,\ldots,m\}$, the active sensor node and anchor node $j\in \{1,\ldots,m\}/\{i\}$ can preserve $\{3m-2\}$-privacy; 3) To active sensor node, if $m>{15}/{2},$ anchor node $i\in \{1,\ldots,m\}$ can preserve $\{3m-(15+m)\}$-privacy.

Proof: For anchor node 1, we have the values of $\sum\nolimits_{i = 2}^{m}{{p}}_{i}$ and $\sum\nolimits_{i = 2}^{m}{{p}}_{i}^{{T}}{{p}}_{i}$, where the number of independent equations is at most $4$ and the number of unknown scalar variables is $3(m-1)$. Particularly, anchor node 1 has no information about active sensor node$.$ With regard to this case, active sensor node can preserve $\{3\}$-privacy to anchor node 1. Since $3(m-1)>4$ always holds, anchor node 1 is unable to know the other anchor nodes’ locations. As a result, anchor node $i\in \{2,\ldots,m\}$ can preserve $\{3(m-1)-4\}$-privacy to anchor node 1, which implies the statement 1) holds.

For anchor node $i\in \{2,\ldots,m\},$ it only has the range difference ratios $\gamma _{i}$ and $\gamma _{2i}$, which can construct at most $2$ independent equations. The number of unknown scalar variables to anchor node $i\in \{2,\ldots,m\}$ is $3m.$ Thereby, the locations of active sensor node and anchor node $j\in \{1,\ldots,m\}/\{i\}$ can be protected since $3m>2$ holds. Thus, statement 2) holds.

For active sensor node, the available information includes: range difference $\Upsilon _{i,1}$, $i\in \{2,\ldots,m\}$, ${{A}}_{11}$, ${{A}}_{12}$, ${{A}}_{21}$, ${{B}}_{11}$, ${{B}}_{12}$ and $B_{21}$. Clearly, ${{A}}_{11}$ is a symmetric matrix, and then active sensor node can construct at most $6$ independent equations. For $\Upsilon _{i,1}$, ${{A}}_{12}$, ${{B}}_{11}$, ${{B}}_{12}$ and $B_{21}$, the maximum numbers of independent equations that active sensor node can construct are $m-1$, $3$, $3$, $3$ and $1$, respectively. Accordingly, the total number of independent equations is at most $15+m.$ The number of the unknown scalars to active sensor node is $3m$. Then, the active sensor node cannot know anchor nodes’ locations when the condition of $m>{15}/{2}$ holds$.$ That means anchor node $i\in \{1,\ldots,m\}$ can preserve $\{3m-(15+m)\}$-privacy, i.e, the statement 3) holds. ■

In addition, we investigate the level of privacy preservation for the PPS and PPDP based localization algorithm.

Theorem 4: Consider the LS estimator (25), we have the following levels of privacy preservation: 1) To active sensor node, ordinary sensor node can preserve $\{3\}$-privacy while anchor node $i\in \{1,\ldots,m\}$ can preserve $\{3m\}$-privacy; 2) To anchor node 1, ordinary sensor node can preserve $\{3\}$-privacy while active sensor node and anchor node $j\in \{2,\ldots,m\}$ can preserve $\{3m\}$-privacy; 3) To anchor node 2, ordinary sensor node, active sensor node and anchor node $j\in \{1,\ldots,m\}/\{2\}$ can preserve $\{3(m+1)-9\}$-privacy; 4) To anchor node $i\in \{3,\ldots,m\}$, ordinary sensor node, active sensor node and anchor node $j\in \{1,\ldots,m\}/\{i\}$ can preserve $\{3(m+1)-6\}$-privacy; 5) To ordinary sensor node, if $m>12$, anchor node $i$ can preserve $\{3(m+1)-(2m+15)\}$-privacy.

Proof: For active sensor node, the location information of anchor node $i\in \{1,\ldots,m\}$ and ordinary sensor node is not available. Thereby, ordinary sensor node can preserve $\{3\}$-privacy and anchor node $i\in \{1,\ldots,m\}$ can preserve $\{3m\}$-privacy. Thus, statement 1) holds. The proof of statement 2) is similar to the one of statement 1), thus it is omitted.

For anchor node 2, we know the values of ${{p}}_{{\rm{a}}}-{{p}}_{1}$, $\vartheta _{3}$, $\vartheta _{23}$, $\vartheta _{33}$, $\vartheta _{43}$, $\vartheta _{53}$ and $\vartheta _{63}$. Based on this, at most $9$ independent equations can be constructed. It is worth mentioning that, the number of unknown scalar variables to anchor node $2$ is $3(m+1)$. Thereby, the locations of ordinary sensor node, active sensor node and anchor node $j\in \{1,\ldots,m\}/\{2\}$ can be protected since $3(m+1)>9$ always holds. Therefore, the statement 3) holds. The proof of statement 4) is similar to the one of statement 3), and hence it is omitted.

For ordinary sensor node, the available information includes: $D_{i,1,{\rm{p}}}$, $Q_{i,1,{\rm{p}}}$, $i\in \{2,\ldots,m\}$, ${{H}}_{11}$, ${{H}}_{12}$, ${{H}}_{13}$, ${{H}}_{21}$, ${{H}}_{31}$, ${{Q}}_{11}$, $Q_{21}$ and $Q_{31}$. Clearly, ${{H}}_{11}$ is a symmetric matrix. Thus, the ordinary sensor node can construct at most $6$ independent equations. For $D_{i,1,{\rm{p}}}$, $Q_{i,1,{\rm{p}}}$, ${{H}}_{12}$, ${{H}}_{13}$, ${{Q}}_{11}$, $Q_{21}$ and $Q_{31}$, the maximum numbers of linear equations that ordinary sensor node can construct are given as $m-1$, $m-1$, $3$, $3$, $3$, $1$ and $1$, respectively. Accordingly, the total number of independent equations is at most $2m+15.$ Since the number of the unknown scalars to ordinary sensor node is $3(m+1)$, the ordinary sensor node cannot know the location of anchor nodes when the condition $m>12$ holds. That means anchor node $i\in \{1,\ldots,m\}$ can preserve $\{3(m+1)-(2m+15)\}$-privacy, i.e, the statement 5) holds. ■

C Collision Avoidance of Packet

Corollary 1: Let us define $\epsilon = (d_{ {{\rm{a}}} ,i}-d_{ {\rm{a}} ,j}-d_{j,i})/ c -t_{ {\rm{r,}} j}$, $\epsilon _{1} = (d_{ {\rm{a,p}} }-d_{ {\rm{a}} ,j}-d_{j, {{\rm{p}}} })/c -t_{ {\rm{r,}} j}$, $\epsilon _{2} = (d_{j {\rm{,p}} }-d_{j,i}-d_{i {\rm{,p}} })/ c -t_{ {\rm{r}} ,i}$, and $\epsilon _{3} = (d_{ {\rm{a}} ,j}-d_{j,i}-d_{ {\rm{a,}} i})/c-t_{ {\rm{r}} ,i}$. For $i\in \{1,\ldots m\}$ and $j\in \{1,\ldots, i-1\},$ packet collision can be avoided if $t_{j,j}-t_{ {\rm{a}} ,j}>\max \{\epsilon,\epsilon _{1}\}$ and $t_{i,i}-t_{j,i}>\max \{\epsilon _{2},\epsilon _{2}\}$ are both satisfied.

Proof: To start with, the time difference when anchor node $i$ receives packet from active sensor node and anchor node $j$ is denoted as $\Delta _{j,i},$ the time difference when ordinary sensor node receives packet from active sensor node and anchor node $j$ is denoted as $\Delta _{j,{\rm{p}}},$ the time difference when ordinary sensor node receives packet from anchor node $j$ and anchor node $i$ is denoted as $\Delta _{i,{\rm{p}}},$ while the time difference when active sensor node receives packet from anchor node $j$ and anchor node $i$ is denoted as $\Delta _{i,{\rm{a}}}$. According to these definitions and noting Fig. 2, the following relationship can be obtained, i.e.,

From Fig. 2, one can infer that the conditions of preventing packet collision are $\Delta _{j,i}>0$, $\Delta _{j,{\rm{p}}}>0$, $\Delta _{i,{\rm{p}}}>0$, and $\Delta _{i,{\rm{a}}}>0$. To this end, we rearrange (29) as

which yields

Clearly, if $t_{j,j}-t_{{\rm{a}},j}>\max \{\epsilon ,\epsilon _{1}\}$ and $t_{i,i}-t_{j,i}>\max \{\epsilon _{2},\epsilon _{2}\}$ are both satisfied, the inequality (31) holds. ■

D Communication Overhead

In this section, we analyse the communication overhead of the proposed localization algorithms. Referring to [18], one knows the communication overhead is evaluated by the transmission of elements. Meanwhile, it is easy to see that the communication overhead of PPS-based localization algorithm for active sensor node is dominated by the state calculation in Step 2. Similarly, the communication overhead of PPS and PPDP based localization algorithm for ordinary sensor node is also dominated by the state calculation in Step 2. Accordingly, the transmission of elements of localization algorithm for active sensor node can be calculated as

Similarly, the transmission of elements of localization algorithm for ordinary sensor node can be calculated as

VI. Simulation and Experiment Results

A Simulation Studies

In this section, the simulations are implemented on MATLAB 2017b. Initially, ten active sensor nodes and ten ordinary sensor nodes are randomly deployed in an area of $600\;{\rm m} \times 600\;{\rm m}\times 600\;{\rm m}$, as depicted in Fig. 7. It is designed that anchor nodes can efficiently communicate with active and ordinary sensor nodes, i.e., data packets during the communication process can be successfully received and decoded. In addition, some parameters used for the simulation are given as: $\sigma _{\rm{mea}} = 0.001$, $m = 8$,$\ {\vec{\rho}} =$ 20 m, and $c = 1500$ m/s.

Figure  7.  Deployment of anchor and sensor nodes, where the circle (i.e., $\bigcirc$), rectangle (i.e., $\square$) and star (i.e., $\bigstar$) denote the active sensor node, ordinary sensor and anchor node, respectively.

DownLoad: Full-Size Img PowerPoint

1) Equivalence Between Our Method and Traditional Method

It is noted that, the privacy preservation is employed into the asynchronous localization of USNs, through which PPS and PPDP based localization algorithms are designed to hide privacy information. To verify the effectiveness of the proposed localization algorithms, the actual and localized positions of active sensor node (labelled as “1”) are shown in Fig. 8(a). In this figure, the traditional LS method refers to the estimation in (11), where the privacy preservation of anchor nodes is not considered. For clear description, the localization error of active sensor node is defined as err$_{1} = \left\Vert {{p}}_{{\rm{a}}}-{\hat{{p}}}_{{\rm{a}}}\right\Vert .$ Correspondingly, the localization errors are shown in Fig. 8(b). From Figs. 8(a) and 8(b), we can see the localization accuracies obtained by PPS-based asynchronous localization algorithm and traditional LS algorithm are completely the same. This result verifies the effectiveness of Theorem 1.

Figure  8.  Equivalence evaluation of positions and location errors for sensor nodes.

DownLoad: Full-Size Img PowerPoint

Similarly, the actual and localized positions of ordinary sensor node (labelled as “2”) are also shown in Fig. 8(a). Define the localization error of ordinary sensor node as err$_{2} = \left\Vert {{p}}_{{\rm{p}}}-{\hat{{p}}}_{{\rm{p}}}\right\Vert ,$ then localization errors with the two methods are presented in Fig. 8(c). Clearly, localization accuracies obtained by PPS and PPDP-based asynchronous localization algorithm are coincided with the ones by traditional LS estimation (24). This result verifies the effectiveness of Theorem 2.

2) Comparison With Synchronous Localization Algorithm

In [19], the authors adopted PPS into TDOA-based localization, where the target sends localization request to anchor nodes. However, the TDOA-based localization method in [19] can achieve localization task only in the case of synchronized clock, i.e., $\alpha _{{\rm{a}}} = 1$ $(\alpha _{{\rm{p}}} = 1)$ and $\beta _{{\rm{a}}} = 0$ $(\beta _{{\rm{p}}} = 0)$. To verify this judgement, we consider the following two scenarios for ordinary sensor node: 1) $\alpha _{{\rm{p}}} = 1$ and $\beta _{{\rm{p}}} = 0$; 2) $\alpha _{{\rm{p}}}\neq 1$ and $\beta _{{\rm{p}}}\neq 0.$ Based on this, the actual and localized positions of ordinary sensor node in Scenario 1 are shown in Fig. 9(a), and the localization errors are presented in Fig. 9(b). Clearly, the localization task can be achieved for ordinary node under two methods, since the location errors are both confined into a desired bound. Under the same assumption, the clock skew is set as $\alpha _{{\rm{p}}} = 1.02$ while the clock offset is set as $\beta _{{\rm{p}}} =$ 0.5 s for Scenario 2. Correspondingly, the actual and localized positions of ordinary sensor node are shown in Fig. 9(c), while the localization errors are shown in Fig. 9(d). Clearly, the asynchronous clocks seriously affect the localization accuracy and the localization task is not achieved by the method in [19]. Through this comparison, one obtains the consideration of asynchronous clocks is necessary in the case of sensor nodes achieving location task passively.

Figure  9.  Comparison with synchronous localization algorithm, e.g., [19].

DownLoad: Full-Size Img PowerPoint

3) Comparison With Asynchronous Localization Algorithm

To remove the influence of asynchronous clocks, an asynchronous localization algorithm based on iterative least squares estimators was presented in [13], where the clock skew was ignored, i.e., $\alpha _{{\rm{a}}} = 1$ and $\alpha _{{\rm{p}}} = 1$. In addition, the location privacy of anchor nodes is not considered in [13]. In the following, we ignore the clock skew, through which the asynchronous localization algorithm in [13] and the proposed algorithm are both conducted to locate sensor nodes under the same assumption. Then, the positions and localization errors of sensor nodes are presented in Fig. 10(a) and Fig. 10(b), respectively. It is obvious that the localization task can be achieved without clock skew under two methods. In the following, we consider a general case, i.e., $\alpha _{{\rm{a}}}\neq 1$ and $\alpha _{{\rm{p}}}\neq 1.$ Specially, the clock skews are set as $\alpha _{{\rm{a}}} = 1.03$ and $\alpha _{{\rm{p}}} = 1.02,$ while the clock offsets are set as $\beta _{{\rm{a}}} =$ 0.1 s and $\beta _{{\rm{p}}} =$0.5 s. Based on this, the localized positions of active sensor node are shown in Fig. 10(c), and the localization errors are given in Fig. 10(d). Meanwhile, the localized positions of ordinary sensor node are shown in Fig. 10(e), whose localization errors are given in Fig. 10(f). From Figs. 10(c)-(f), one knows the clock skew reduces the localization accuracy. Alternatively, the proposed algorithm can eliminate the effect of clock offset and clock skew. Thereby, the position task can be achieved. Through the above comparisons, we obtain that the consideration of clock skew is necessary, and the proposed asynchronous localization algorithm in this paper can effectively eliminate the impact of the clock skew.

Figure  10.  Comparison with asynchronous localization algorithm, e.g., [13]

DownLoad: Full-Size Img PowerPoint

4) Performance for the Mobility Compensation Strategy

As provided in Section III-B, a mobility compensation strategy is developed to balance the tradeoff between communication cost and localization accuracy. To verify the effectiveness, the measurement window $T_{\rm{w}}$ and sampling interval $\delta$ are set as 4 s and 1 s, respectively. Of note, the clock skew $\alpha _{{\rm{a}}}$ (or $\alpha _{{\rm{p}}}$) is estimated by the located positions at timestamps $T_{\rm{a,a}}$ (or $T_{\rm{a,p}}$) and $T_{\rm{a,a}}^{{\#}}$ (or $T_{\rm{a,p}}^{{\#}}$)$.$ Thus, the clock skew $\alpha _{{\rm{a}}}$ (or $\alpha _{{\rm{p}}}$) in the first measurement window cannot be estimated, due to the lack of position information (i.e., ${{p}}_{{\rm{a}}}^{{\#}}$ or ${{p}}_{{\rm{p}}}^{{\#}}$). In view of this, the clock skew $\alpha _{{\rm{a}}}$ (or $\alpha _{{\rm{p}}}$) in the first measurement window is set as $1$. Accordingly, the localization errors of an active sensor node and an ordinary sensor node in three measurement windows are shown in Fig. 11(a) and Fig. 11(b), respectively. Correspondingly, the estimated clock skews $\alpha _{{\rm{a}}}$ and $\alpha _{{\rm{p}}}$ are represented in Fig. 11(c). It is clear that, the estimated position in the first measurement window is not very accurate. After the first measurement window, the clock skews $\alpha _{{\rm{a}}}$ and $\alpha _{\rm{p}}$ are both corrected, whose accuracy is improved.

Figure  11.  Performance for the mobility compensation strategy in three measurement windows. Of note, “1” denotes estimated errors by the algorithm in Section IV, “2” denotes estimated errors by mobility compensation strategy.

DownLoad: Full-Size Img PowerPoint

5) Consequence When There Exist Dishonest Nodes

In the above results, the nodes are assumed to be honest. As mentioned in Section IV-C, if the condition of $e_{{\rm{a}}}(T_{\rm{a,a}}^{{\#}})>{\vec{\rho}}$ and $e _{{\rm{p}}}(T_{\rm{a,p}}^{{\#}})>{\vec{\rho}}$ holds, the nodes in USNs can be considered to be dishonest, otherwise the nodes are dishonest. To show the consequence when there exist dishonest nodes, dishonest data are added to the position and timestamps information of anchor node 4. To be specific, ${{p}}_{4}$ is tampered with ${{p}}_{4}+10{{\xi }}_{1}$, the time $t_{{\rm{a}},4}$ is tampered with $t_{{\rm{a}},4}+0.5\xi _{2}$, and the time $T_{4,{\rm{p}}}$ is tampered with $T_{4,{\rm{p}}}+0.5\xi _{3}$, where ${{\xi }}_{1}$, $\xi _{2}$ and $\xi _{3}$ denote zero-mean Gaussian noises with a variance $1$. Correspondingly, the predicted trajectories and estimated positions of active sensor node are shown in Fig. 12(a), while the predicted trajectories and estimated positions of ordinary sensor node are shown in Fig. 12(b). Clearly, the estimated positions of active sensor node and ordinary sensor node are outside the cylinder when there exist dishonest nodes, i.e., the distance differences exceed the threshold ${\vec{\rho}}$.

Figure  12.  Consequence when there exist dishonest nodes.

DownLoad: Full-Size Img PowerPoint

B Experiment Studies

Experiment results are presented in this section, and we only check the effectiveness of the PPS-based asynchronous localization algorithm for active sensor node due to limited experiment conditions in our lab. To be specific, the experiment is carried out in a tank of $6\;{\rm m} \times 4\;{\rm m} \times 1\;{\rm m}$, and the hardware in the experiment is mainly comprised of the following three parts: 1) Base stations: Base stations act as surface buoys, whose role is to provide self-localization and clock synchronization services for anchor nodes. 2) Anchor nodes: When anchor nodes are on the surface of the water, they employ ultra-wideband technology [41] to acquire their positions via the cooperation with base stations. After acquiring their position information, anchor nodes sink to the bottom of the tank, and then provide localization service for the active sensor node. 3) Active sensor node: An AUV is employed to perform the role of active sensor node. It is worth mentioning that the aforementioned communication links are all wireless. Meanwhile, the experimental configuration is shown in Fig. 13(a), and the experiment setup is depicted in Fig. 13(b).

Figure  13.  Experiment description of the PPS-based asynchronous localization algorithm for active sensor node.

DownLoad: Full-Size Img PowerPoint

In order to estimate the position of active sensor node, underwater acoustic modems are required to provide communication capability for the sensor-to-anchor wireless links. Then, an acoustic modem that consists of STM32 processor, transmitter and receiver is designed in our lab, as shown in Fig. 14(a). To verify the effectiveness of our modem, the received analog signals are presented on the top of Fig. 14(b). These analog signals can be converted to digital signals, as shown on the bottom of Fig. 14(b). Clearly, the transmitted preamble and the guard interval in Fig. 14 can be identified, which indirectly verify the effectiveness of the designed acoustic modem.

Figure  14.  Construction of acoustic modem module.

DownLoad: Full-Size Img PowerPoint

With the embedded communication system, the position of active sensor node can be estimated. To this end, the position vectors of anchor nodes are set as ${{p}}_{1} =$ $[-0.6,0.6,-0.5]^{T}$, ${{p}}_{2} = [0.9,0.6,-0.5]^{T}$, ${{p}}_{3} = [0.9,-0.9,-0.5]^{T}$ and ${{p}}_{4} = [-0.6, -0.9, -0.5]^{T}.$ In addition, we assume that eleven different points are required to be localized, i.e., the active senor node is deployed at eleven different points. By using the localization protocol, some timestamp measurements (see Table II) are conducted to estimate the position information of active sensor node. Accordingly, the actual and localized positions of active sensor node are shown in Fig. 15(a), while the localization errors are presented in Fig. 15(b). In addition, the clock of active sensor node can be inferred as $\alpha _{{\rm{a}}} = 1.0008$ and $\beta _{{\rm{a}}} = 152.0373$ μs. Clearly, the PPS-based asynchronous localization algorithm in this paper can achieve localization task, since all the localization errors are close to zero. These results reflect that the asynchronous localization algorithm designed in Section IV-A is effective and meaningful.

Table  II.  Relative Timestamps Measurements (μs)

	$T_{\rm{a,a}}$	$t_{\rm{a,1}}$	$t_{\rm{a,2}}$	$t_{\rm{a,3}}$	$t_{\rm{a,4}}$
Point 1	64 762	65 584	65 892	65 582	65 042
Point 2	65 637	66 530	66 637	66 270	66 084
Point 3	62 384	63 104	63 233	63 104	62 949
Point 4	72 563	73 129	73 283	73 412	73 284
Point 5	84 369	84 816	85 002	85 369	85 263
Point 6	57 296	57 929	57 743	58 190	58 296
Point 7	66 437	67 257	66 717	67 257	67 567
Point 8	82 653	83 547	83 100	83 286	83 653
Point 9	54 698	55 698	55 331	55 145	55 592
Point 10	72 734	73 864	73 554	73 014	73 558
Point 11	63 647	64 927	64 447	63 847	64 667

 | Show Table

DownLoad: CSV

Figure  15.  Experiment results of the PPS-based asynchronous localization algorithm for active sensor node.

DownLoad: Full-Size Img PowerPoint

VII. Conclusion

With consideration of privacy preservation, this paper studies an asynchronous localization issue for USNs. In order to eliminate the effect of asynchronous clocks (i.e., clock offset and skew), an asynchronous localization protocol including mobility compensation strategy is presented. Based on this, the PPS and PPDP based localization algorithms are designed to hide privacy information, where the performance analyses are also presented. Finally, simulation and experiment results show that the localization algorithm in this paper can achieve localization task, while the effect of clock can be eliminated.