【读论文】To Hide Private Position Information in Iocalization Using Time Difference of Arrival

写在前面

??好久都没有发博客了，这半年一直在准备考研的复试，研究生录取后又开学忙毕业的活动和手续，毕业后联系了研究生的导师，老师给了我很多的指导，学习了MATLAB，LATEX，也读了一些论文。所以直到现在才想起自己好像还有一个CSDN博客，啊哈哈哈。上来以后发现自己多了一些粉丝，为数不多的几篇博客访问量也到了四位数，非常感谢大家。读研以后论文一定是不能少看的，所以我决定我的博客中增加一个 【读论文】系列，把我读的论文的一些理解 （不是原文翻译） 记录在这里，希望能对大家有所帮助。如果你觉得我帮到了你，别忘了点赞、关注、评论，谢谢大家~

论文简介

??今天要读的论文是《To Hide Private Position Information in Iocalization Using Time Difference of Arrival》，我自己翻译一下就是《使用到达时差法在定位过程中隐藏私有位置信息》。论文的原文可以在这里找到。
定位这个事生活中每天都在发生，用到的设备大概分为两类，一类是目标点设备，也就是发起定位的那个设备，比如咱们的手机。另一类是锚点设备，他们帮助我们定位，起到参考点的作用，比如移动、联通他们的基站。这时候就产生了一个问题：
如果由目标点来计算自己的位置信息，那么锚点就需要把他们的位置信息发送给目标点，用于计算。这是很可怕的事情，如果目标点是一个黑客的恶意设备呢？他就轻轻松松的获取了所有锚点的位置，军事上首先对这些目标进行打击，咱们的定位系统就瘫痪了。那能不能锚点设备算好了目标点的位置，然后直接发送给目标点呢？也不太好，因为我们也不想暴露自己的位置给锚点，这怎么办的？这篇论文讲的就是这个事。

到达时差法（Time Difference of Arrival）

??说到达时差法TDOA（Time Difference of Arrival）之前，先说说到达时间法TOA(Time of Arrival)。这个方法大家都知道，在这里给大家提个醒。
问题： 在一个二维平面中，有三个点分别为A(0,0)、B(0,5)、C(5,0)，现在有一个点D，他距离A为 $5\sqrt 2$ ，距离B为5，距离C为5，请问D点的坐标是多少？
答： 我想大家都知道怎么解，最简单的就是直接画个图，以A为圆心， $5\sqrt 2$为半径画圆（我随便举的例子，这个数好像不太好操作）；以B为圆心，5为半径画圆；以C为圆心，5为半径画圆画圆。D点的位置就在三个圆圈的交点处(5,5)。
在这个问题中ABC为锚点，D为目标点。现实的定位问题中，目标点到锚点的距离 $d$是通过两个设备之间单次的通信时间 $t$和电磁波的传播速度 $c$算出来的，也就是 $d=tc$。这就是到达时间法，用信号到达锚点的时间来算锚点设备与目标点之间的距离。
到达时间法有一个缺点，他要求所有参与此次定位的锚点的时钟（时间）是一致的，这样到算出的距离 $d$才有意义。你可以自己想一想他们之间的时钟不一致会是什么情况？
为了降低这样的限制，就可以有到达时差法。我们把目标点与锚点A之间的距离 $d_A$,目标点与锚点B之间的距离 $d_B$相减，求 $d_{AB}=d_A-d_B$。之后以AB为焦点， $d_{AB}$为距离差，画双曲线。双曲线的交点就是目标点的位置。这是图形化的表示，那在实际计算中应该怎么算呢？原文中已经给出，就不再啰嗦了，结论就是公式(7)。

隐私保护求和（Privacy-Preserving Summation）

??说完了到达时差法后需要再介绍一下隐私保护求和算法（PPS）。它能够在保证求和结果不受影响的情况下保护每一个求和项的信息。对照着下图，说一说他的工作流程。
比如这个Node 0想要算Node 1~3的位置信息 $X$求和的结果。一般来说就直接把X发送给节点0，之后求和就行了。但这样每一个节点的信息 $X$就暴露给节点0了，着不是我们想要的。隐私保护求和算法怎么做呢？发送信息的所有节点（假设有m个，图中是3个），每一个节点生成m个大小 $X$一样的随机矩阵 $W$，且随机矩阵的和为零矩阵。比如 $X$是一维信息，值是[6] ，某一个节点就生成三个随机矩阵[3][2][-5]，自己保留其中的一个，把剩下的分发给参与发送数据的其他节点。所有节点把自己留下的一个和收到的m-1个随机矩阵相加，形成了最终用于加密的矩阵。节点在发送信息的时候把最终用于加密的矩阵和要发送的信息相加，发送给节点0。节点0收到数据后将这些数据相加，因为随机矩阵的和为0，所以求和的值不受影响，同时又保证了发送信息的结点把自己的隐私信息加密起来。节点0无法获取每一个节点他们的 $X$是多少。

将上述两种方法结合用于定位

??如何将PPS应用于TDOA定位呢？得将TDOA的计算公式（7）做一下变形，让式子中的隐私信息变成求和的方式。原文中也给了推导，这里就不罗嗦了，懒得翻的可以看下图。

最终公式（7）变成了这个样子，其中的每一项由上图的公式计算得到。

场景以及协议的设计

场景分类

??之前我们提到了时差，根据这个时差存储在哪也可以分为两种情况。将时差信息存储在锚点设备中，比如目标点与锚点1的时差信息存在锚点1中、目标点与锚点2的时差信息存在锚点2中。这种我们称作场景一。将所有的时差信息存储在目标点中，这种我们称作场景二。文中对场景一、二分别设计了通信协议，他们的思想都是一致的，在这篇博客中我们主要介绍场景一下的协议，场景二类比一下你应该就懂了。

场景一下的协议设计

因为原文中说得很简陋，不易理解。为了更加直观地解释这个协议。我在每一步中补充了一些操作，可能和原文翻译上不一致，但是操作的内容是一样的，大家放心。
1）锚点 $1{{\sim}} m{-}1$ 通过PPS算法发送 $\bm{x}_i$, $\bm{x}^\text{T}_i\bm{x}_i$ , $d_{im}$ 和 $d^2_{im}$ 给锚点 $m$ 然后锚点 $m$ 计算 $\sum^{m-1}_{i=1}\bm{x}_i$ , $\sum^{m-1}_{i=1}\bm{x}^\text{T}_i\bm{x}_i$ , $\sum^{m-1}_{i=1}d_{im}$ and $\sum^{m-1}_{i=1}d^2_{im}$ 。
2）锚点 $1{{\sim}} m{-}1$ 通过PPS算法发送 $\bm{x}_i\bm{x}^\text{T}_i$ 给目标点。锚点 $m$ 通过PPS算法发送 $(m-1)\bm{x}_m\bm{x}^\text{T}_m-(\sum^{m-1}_{i=1}\bm{x}_i)\bm{x}^\text{T}_m-\bm{x}_m(\sum^{m-1}_{i=1}\bm{x}^\text{T}_i)$ 给目标点，之后目标点计算 $A_{11}$ ;
3）锚点 $1{{\sim}} m{-}1$ 通过PPS算法发送 $\bm{x}_id_{im}$ 给目标点. 锚点 $m$ 通过PPS算法发送 $-\bm{x}_m\sum^{m-1}_{i=1}d_{im}$ 给目标点，之后目标点计算 $A_{12}$ 因为 $A_{21}=A^\text{T}_{12}$，所以直接转置就算出了 $A_{21}$;
4）锚点 $1{{\sim}} m{-}1$ 通过PPS算法发送 $d^2_{im}$ 给目标点，之后目标点计算 $A_{22}$ ，锚点 $1{{\sim}} m{-}1$ 通过PPS算法发送 $-d^3_{im}$ 给目标点，之后目标点计算 $B_{22}$；
5）锚点 $1{{\sim}} m{-}1$ 通过PPS算法发送 $\bm{x}_i\bm{x}^\text{T}_i\bm{x}_i$ 给目标点，锚点 $m$ 通过PPS算法发送 $(m-1)\bm{x}_m\bm{x}^\text{T}_m\bm{x}_m-(\sum^{m-1}_{i=1}\bm{x}_i)\bm{x}^\text{T}_m\bm{x}_m-\bm{x}_m(\sum^{m-1}_{i=1}\bm{x}^\text{T}_i\bm{x}_i)$给目标点，之后目标点计算 $B_{11}$ ;
6）锚点 $1{{\sim}} m{-}1$ 通过PPS算法发送 $-\bm{x}_id^2_{im}$ 给目标点，锚点 $m$ 通过PPS算法发送 $\bm{x}_m\sum^{m-1}_{i=1}d^2_im$ 给目标点，之后目标点计算 $B_{12}$;
7）锚点 $1{{\sim}} m{-}1$ 通过PPS算法发送 $\bm{x}^\text{T}_i\bm{x}_id_{im}$ t给目标点，锚点 $m$ 通过PPS算法发送 $-\bm{x}^\text{T}_i\bm{x}_m\sum^{m-1}_{i=1}d_{im}$ 给目标点，之后目标点计算 $B_{21}$
8）目标点计算 $\hat{\bm{x}}_0$。
原文中给了这个协议的示意图：

我在看论文的时候自己也画了一个（画的有点乱），大家看看哪个好理解就看哪个吧：

理解了协议一，在场景二下的协议就不难理解了，这里就不再继续说了。

隐私保护等级

??最后说一说隐私保护等级。现在已经有了很多关于隐私保护的协议，但是这个协议它的保护程度究竟是多少呢？一直没有一个统一的标准和定义，在这篇文中作者给了一个隐私保护等级的概念。
比如A的隐私信息有N个未知量，B通过自己已知的信息能够列X个方程来估计A的隐私信息。那么就称A对B保持了{N-X}的隐私。之后他们利用这个概念对自己提出的协议进行了分析。

??好啦，这篇论文解析就写到这，如果你感觉帮到了你，别忘了点赞、关注、评论。你的支持就是我继续写下去的动力，谢谢大家~