基于传感网的目标定位方法的中英文翻译

传感器网中络基于分布范围差异的目标定位

Chartchai Meesookho 和Shrikanth Narayanan

电机工程学系

维特比工程学院

南加州大学

摘要——目标定位是传感器网络中的关键应用。各种传统方法可以应用，并已提出，以范围差（RD）为基础的方法是有吸引力，是由于提高了准确性和易于实现。当基于范围差方法的基本概念被采用在传感器网络的情况下，需要制定数据采集、汇总程序的方案并且受到能源约束。目前的挑战是设计一个经济、准确的算法。本文中，在范围的差异定位方法的基础上，我们提出了一种分布式算法，这种方法允许每个参与的传感器存在时延估计。所采集的数据使用了顺序最小二乘方案进行融合，这样能够以当前的估计为基础选择合适的传感器。结果，采用逼真的模拟模型评估，说明了分布式定位产生误差小并且比较集中的方法消耗更少的能源。当参与的传感器的数量很少时，分布式的定位在精度方面的优势更为突出，然而当参与的传感器的数量是很大的时候，能够节约更多的能量。该方法的精确度也更强大，可以降低目标信号能源并且序列瞬时误差的估算可以被近似，并用于协调成本和系统性能评估。

Ⅰ．简介

目标定位是推动实施传感器网络应用的关键之一。大量的传感器能够观察冗余和接近目标，因此，为改善目标定位和跟踪性能提供了机会。一些应用实例包括在战场上军用车辆的定位和跟踪自然栖息地的野生动物。最近，传统的目标定位方法已应用于传感器网络的情况下。这个范围差（RD）的方法是在这方面特别有吸引力[1]，因为它比最大似然（ML）估计法[3]，[4]更加易于实施，比基于能源定位更加准确[5]，且不需要由目标产生信号的先验知识。虽然基于分布式方法的基本概念可以被应用到传感器网络的问题中，数据汇总过程需要得到发展和改进。在诸如雷达和麦克风阵列的传统系统中，利用每一个传感器收集时间序列数据，在进程中需要基本的信息，被假定为在中央处理单元可用的，无需关注在收集这些信息所产生的费用。然而，由于传感器网络典型的电池供电、无线的特点，需要考虑传感器之间时间序列数据交换的能量消耗。目前的挑战是设计一个经济、准确的算法。在文献[1]中，在传感器阵列测试平台实施定位，但通信费用没有考虑。在文献[2]中，已对以集群为基础的架构进行声音目标跟踪的研究。然而，系统性能集群内的通信协议问题并没有解决。我们认为，设计的算法对该系统的效率的影响依赖于非常具体的方法来实现。在这篇论文中，基于范围差异的定位，我们提出了一种分布式算法，这种算法允许每一个参与的传感器产生的时延估计，

所以，在时间序列数据传输发生的能源量可以减少。获得的数据，这些数据的范围不同，使用顺序最小二乘法方案进行融合。顺序性质提供了基于每个时间步长的当前估计选择高效的传感器，从而使精度得到改善。结果，使用实际的模型和情况进行评估，说明了分布式定位比较集中的方法产生更小误差和消耗更少的能量。值得注意的是，当参与的传感器的数量很少时，分布式的定位在精度方面的优势更为突出，然而当参与的传感器的数量是很大的时候，能够节约更多的能量。该方法也很强劲，其精确度基本不受目标信号低能量（低信噪比）的影响并且序列瞬时误差的估算可以被近似，并用于协调成本和系统性能评估。

Ⅱ．聚类的目标定位

因为集中处理全球的信息或从所有传感器收集测试数据似乎没有吸引力，或许可能是可行的，尤其是在一个庞大而密集的传感器领域，由于通信成本高的要求，适当的解决办法是在任务中将传感器分摊成更小的组来操作，其中每个组都有一个地方处理单元。对本地数据进行融合和压缩的处理可以用来为原始数据传输到基站或最终用户节约能量。这些传感器通常称为集群并且一个传感器被选中成为簇首，它扮演一个本地进程单元的角色。在传感器网络中用来分散处理的通用节能聚类协议可以在文献[6]中找到。一个目标定位问题使用聚类技术可能需要较为具体的表述。既然最终目标是要找出一个特定的点也是最有可能的目标位置，在相应的目标区域关键信息应是可靠的。因此，可能需要最为有效的聚类，而且激发了一个在特定的时间和地点高效的集群设计。集群形成协议的目的是用于目标定位和跟踪，这在文献[7]中已经出现，其中，动态时空聚类（DSTC）算法，提出了一种基于最近点方法(CPA)的集群形成协议的功能。在文献[8]中zhao等人介绍的驱动传感器信息查询使用一个信息效用的措施使得动态聚类获得最大信息增益。声目标跟踪动态聚类，已经在文献[9]中提出了。假设一个放置在人烟稀少的高功能传感器方案（可望发挥簇头的作用）并且当簇头检测到的声信号强度超过预定的阀值时会形成一个群集。群集的重点是整合在每个群集成员收集到的代表从每个群集赚取知识的测量值。这是相当具体的应用，以描述与集群的形成相关的信息管理机制。一般来说，所有成员与簇头沟通是直接的或者是多跳通信。在集群里信号处理功能是在转移压缩数据到基站或最终用户之前被执行。我们称这是一个集中的处理方案。某一特定的应用,如目标定位使用传统的方法，然而，需要谨慎的设计，以获得准确和成本效益的系统。最主要的原因是，在每个传感器观测是通常时间序列数据。当群的设计是大到达地方化准确性要求，为了单独传送在群头将被处理的所有群成员的这样数据，特别需要花费的很多通信。另一种方法是将分布式处理后，通过根据为特定应用程序的使用方法的特点而定的某种手段。我们利用一个众所周知的方案，基于范围差的定位，在传感器网络中的分布式处理表明当与集中的方法进行比较，该系统的性能可以提高。

Ⅲ.基于最小二乘法的范围差的定位

范围差（RD）是来自到达的时间差（TDOA）的估计，通过距离和信号在媒介中传播的速度之间的关系。时延估计技术[10]是用来确定TDOAs的基本工具。我们假定存在一个最优的时延估计器，产生受到加性噪声扰动的不确定的到达时间差估计。在文献[11]，[12]中已经提出了几种基于范围差的方法。我们专注于一个在文献[11]中提出的封闭形式最小二乘法，因为据报道它比其它方案有更高的效率并且能够在高信噪比（SNR）的环境下接近克拉默带宽（CRB）。设N传感器分配给参加定位进程的坐标为 x1,y1 ,..... xN,yN 。假设目标的坐标为Zs xs,ys ,传感器i和j之间的距离不同，其中i，j=1， ，N ，距离dij可以通过基本的关

系获得：dij Di Dj其中Di= xs xi ys yi 。通常使用一个任意关于范22

围差的参考传感器。如果没有一般性的损失，选择 x1,y1 作为定位的参考传感器。

从其它传感器收集到的时间序列数据和在参考传感器收到的信号会产生到达时间差估计，范围差是来自使用信号传播速度知识测得的到达时间差。然而在现实应用中，因为到达时间差估计存在错误使得确切的范围差不可用。因此，我们得到

di1=di1 ni1，i=1， ，N。到达时间差估计是通过与高斯分布数据的广义交叉

获得，通常渐进地分布在高信噪比的环境下。因此，范围差估计也是高斯分布的，假设ni1～N 0, i21 。定位问题可以演化成一个线性最小二乘问题，A b，其中

x2 A

xNy2 yNd12 dN1 xs ， ys Rs 2 R12 d12 1 R ，b ，i2 R2 d2 N1 N xi x1 yi y1 22

这些线性最小二乘方程可以通过批处理方式和方案来解决， ATA ATb。 1

但是，我们可以不通过用连续最小二乘法解线性方程的方法得到 ，这可以通过设A n =A n 1 a T n 和b n = b 1 b 2 b n T来描述。连续最小二乘估计变成 T

T n n 1 n b n a n n 1 （1）

n n 1 a n 1 a n n 1 a n T

n n a n n 1 （2） T

指数n对应第nth个传感器。

Ⅳ. 数据模型

静态声目标产生一个WSS高斯随机观察过程s t ，假设目标强度衰减的速率与距离平方成反比。加性高斯测量噪声的扰动 i t ，通过xi t = s t i Di i t 接

收到第ith个传感器的信号。通过平均时间窗口可以计算出能量T=

样本数，fs为yi k =

以得到

yi k =Mfs，其中M是1M kMj k 1 M 1xi j 的采样频率。假设s t 和 i t 是独立的，可2 s t t （3） 22D2

i

var yi k = s2 t 22 t 2 Di 2M （4）

2设s t ～N 0, s2 ,每个传感器噪声具有相同的分布，所以 i t ～N 0, 。

PSD Gs f 信号、PSD G f 噪声，连贯性是指在中心频率f0处具有较平坦的带

宽f2 s z。每一个传感器的信噪比：。根据文献[10],语音估计的22Gw,i f Di Gs,i f

克拉默带宽如下：

ij2 8T 3 2 Cij f f f0 f0 2 2 1 Cij

1

G f 1 s,i

G ,i f 133 1 其中，Cij= G f 1 s,j G ,j f 1

在表格中可以简单的推导出估计的方差， i21 12 D12，其中

2

1 3D13

223 f f 8T f0 f0 SNR 2 2 0

2 D13 1 SNR0

033 f f 2 8T f0 f0 SNR 2 2 （5），SNR0是指 2s2 。注意 i21是第ith个

传感器与假设在前一个位置的参考传感器之间的语音方差。这种差异是与常数Di2成正比， 12和 是与D12相对应的。因此，一个固定的参考传感器，关于从更远的

传感器到目标传感器的语音是不准确的。

Ⅴ.分布式定位

从基于范围差的定位方法的描述，我们注意到有两个关键的步骤，是到达时间差估计和通过解最小二乘方程得到目标的位置。在一个集中的方案中，簇头要采用这两个步骤。簇头应该是一个参考传感器并且到达时间差是关于可以通过时延估计获得的集群成员。分布式定位的概念可以用在每一个参与的传感器的一些进程中，不仅在簇头中。如果从簇头收集到的时间序列数据被传送给参与的传感器，时延估计就可以获得了。广播数据从一个参考传感器传到许多参与传感器预计比相反的方向需要更少的通信开销。求解最小二乘方程组包括两个机制，取决于是否应用了批次或连续的进程。批量估计要求所有的测量值在同一时刻都是可用的，而在连续测量估计只需要同时提供从第（n - 1）个传感器获和一个到达时差相应的第n个传感器获得的估计。然而，后者要求更小的计算复杂性，因为当有大量参与的传感器导致矩阵较大时它没有处理逆矩阵的负担。另一个优点是，当前的估计可以作为先验信息用于正确选择下一个参与传感器。根据数据模型可知，时延估计方差与传感器到目标节点距离的平方成正比，通过考虑最近的传感器当前的估计来简单的选择首选的传感器。因此，结合时间延迟估计分布式处理和连续最小二乘定位的思想，可望改善通信开销和准确性方面的定位性能。通过使用前面定义的符号，我们提出以下算法：

1） 一个在一定的时间窗口中收到最高的平均信号能量的传感器被选定作为初始

传感器。请注意这个“初始传感器”是用来调用传感器，这个传感器是用来取代“簇头” 启动进程的。

2） 初始传感器在最大的广播范围广播收集到的时间序列数据到k个最近的相邻节

点，其中k是最初预计参与传感器的数量。根据广播范围的覆盖面和传感器密度，可能会获得少于k个传感器。

3） 每一个相邻的传感器运行时延估计使用在传感器中收集到的时间序列数据和

从初始传感器传送的数据来估计到达时延差。

4） 初始估计是通过基于到达时间差的批次估计获得，到达时间差是通过三个最近

相邻传感器计算出。如果有少于三个传感器已经收到它的数据，相邻传感器可能要求广播从初始传感器收到的时间序列数据。

5） k-4最近的传感器的初始估计是从批次估计器获得，预期参与顺序最小二乘法。

在下面的估计k-i变为最近的传感器，其中i是那些已经包括在定位进程中传感器的数量。

6） 连续估计的路线是由上一步中所描述的凸壳插入算法解决旅行商问题（TSP）

路线的传感器构成[15]。

7） 这一估计使用公式（1）以连续的方式更新。只有 和 需要通过传感器传送。

8） 每次估计更新，由基于新的估计路线也更新并且剩余参与传感器的数量在减

少。

9） 如果路径中的下一个传感器没有收到簇头的时间序列数据，当前传感器将数据

广播到下一个传感器，包括位于广播范围的k j个最近的传感器，其中j是已经收到数据的传感器的数量。

Ⅵ.实验结果

对于实验模拟，我们假设一个100×100平方米得传感器区域，随机分布2500个传感器。假设静态声目标位置在传感器区域内有一个均匀分布，并且产生一个3500-4500Hz的信号。延迟的时间和平均能量估计数据观测时间是1秒，其中采样

2率是9000Hz。 s2和 分别是100和1，所以SNR0=100。参加的传感器的数目是

10,15,20和25。广播范围是5米。估计误差通过均方误差（MSE）来评估， xs100蒙特卡洛实验进行平均的目标定位和传感器拓扑结构影 xs ys yx 。22

响。对于每一个拓扑结构，100个路径用来平均噪声。我们假定在每个传感器接收到信号的平均能量有一个正态分布的均值和方差，在（3）及（4）中已被定义。接收到最高能量的传感器被选择成为初始传感器适用于分布式方法和集中方法的簇头。

图1说明了，不同参与传感器的数量的集中式和分布式定位的均方误差。很明显，通过分布式的方法引起的误差小于集中的方法。其原因是，分布式算法使用直接估计的先验信息来选择参与传感器序列，包括用最近的传感器来估计目标位置。由于接近目标的传感器提供更加准确的时延估计，正如在上一节所述，在得出结果之前，与采用集中方法的预选参与传感器相比时，定位的准确性提高了。当参与传感器的数量增加时，这两种算法产生的差距就变小了，因为大量的传感器使得这两种方法在覆盖的范围内更加相似。我们还研究了两个方案的表现，其中 s2是对应于不同的目标所产生的信号（SNR）的能量的变化。使用 s2的值为

10,40,70,100，并且参与传感器的数量为15。在图2的结果表明，当 s2减少时集

中方案比分布式方案遭受更多。这也影响了这两种方案选择不同的参与传感器。当 s2较小时，SNR0也较小，这使得公式（5）中的 变大。因此 i21是与Di2以高

速率成正比。传感器和目标之间的距离在定位性能上变得更加有影响力的。集中式方案选择的传感器很可能比分布式方案选择的传感器距离目标的距离要更远，因此产生更大的误差。我们用文献[6]中描述的一阶无线电模型来评估通信开销。为了在距离为d的两地交换kbit数据，无线电花费ET Eelec*k amp*k*d2和x

ERx Eelec*k。ET和ER分别代表的传输和接收数据的能量消耗。Eelec=50nJitxx

是用来运行发送器或接收器线路的能量，并且 amp=100pJbitm2是用来传输放

大。我们假设每一个数据样本和在 、 中的数据代表每一个元素需要8字节编码。因此，对于时间序列数据交换，k=（采样率）×（观测时间）×（比特/样本）=9000*1*8=72000 bit。对于在最小二乘法中的通信需求，k=（在 、 中求和的元素的数目）×（比特/样本）=（3+9）*8=96 bit。因为ET和ER与k成正比，x x

我们可以看到，时间序列数据交换花费的能量比连续估计更新所花费的数额更多。图3说明了这两种方案所消耗的能量。可以看到，与集中式方案相比分布式方案能够节约大量的能量，特别是当传感器的数量很大的时候。这可以简单地解释，第一，参考传感器与L个参与传感器之间的通信在广播范围之内。在集中计划要求L个传输，以便获得代表所有参与的传感器的时间延迟估计，但对于分布式算法只有一个传输是不够的。对于分布式算法的额外成本是用来从每个传感器时间延迟估计中按顺序提取的到达时间差。正如以上指出，这种沟通的成本相对较小。第二，因为目标传感器超出了参考传感器的广播范围，在集中式方案中需要多跳通信并且目标传感器的数据传输最终仍然要到达参考传感器。另一方面，在集中式方案中目标传感器能够从在第一跳就已经从参考传感器接收到数据的传感器获得数据。这就要求通信距离较短并且比集中式方案需要更少的能量。因此，当需要多跳通信或者像图3中参与传感器的数量增加时，分布式方法的优点更为突出。我们也研究了分布式方法的收敛问题，考虑到每个迭代的定位误差和连续估计之间的距离不同。图4显示了这两个数额密切相关。这种情况的好处是，我们可以大约从序列估计中评估当前误差。当精度已经达到可以接受或要求的水平时，如果我们要节省不必要的花费，这一点很重要。

图1. 分布式方法产生误差小于集中的方法

图2. 分布式方法的准确性比集中式方法受低能量的目标信号影响较小

图3.集中式方法消耗的能量大于分布式方法消耗的能量

图4. 距离误差和连续估计之间的距离是和高度相关的

Ⅶ. 结论和未来工作

我们提出了一个基于距离差定位方法的分布式算法，这个算法允许每一个参与传感器产生的时延估计。到达时间差是从时间延迟估计中计算出来的，使用顺序最小二乘方案融为一体，这使选择合适的传感器以目前估计为基础。结果表明，

该分布式定位方法比集中式方法生产更小的误差和消费更少的能量。当参与传感器数量少和参与传感器的数量增加而更加节能时，对于误差的考量分布式处理的优势更加明显。该方法在降低目标信号能量和可以近似的估计序列瞬时错误方面较为强劲并用于调和成本和系统性能。在未来我们的目标是研究时间延迟估计对时间同步误差的影响，因此，那就是定位性能。

参考文献

[1] J. C. Chen, L. Yip, J. Elson, H. Wang, D. Maniezzo, R. E. Hudson, K. Yao, and D. Estrin, “Coherent acoustic array processing and localization on wireless sensor networks,” in Proceedings of the IEEE, vol. 91,Aug 2003.

[2] Q. Wang, W. Chen, R. Zheng, K. Lee, and L. Sha, “Acoustic targettracking using tiny wireless sensor devices,” in IPSN 2003, 2003.

[3] J. C. Chen, R. E. Hudson, and K. Yao, “Maximum-likelihood source localization and unknown sensor location estimation for widebandsignals in the near-field,” IEEE Transactions on Signal Processing, 2002.

[4] R. J. Kozick and B. M. Sadler, “Source localization with distributed sensor arrays and partial spatial coherence,” IEEE Transactions on Signal Processing, 2004.

[5] X. Sheng and Y. Hu, “Energy based acoustic source localization,” inIPSN, 2003.

[6] W. R. Heinzelman, A. Chandrakasan, and H. Balakrishnan, “Energyefficient communication protocol for wireless microsensor networks,” in Proc. 33rd Hawaii International Conference on System Sciences, 2000.

[7] S. Phoba, N. Jacobson, and R. Brooks, “Sensor network based localization and target tracking through hybridization in the operational domains of beamforming and dynamic space-time clustering,” in GLOBECOM 2003, 2003.

[8] M. Chu, H. Haussecker, and F. Zhao, “Scalable information-driven sensor querying and routing for ad hoc heterogeneous sensor networks,” International Journal of High

Performance Computing Applications,2002.

[9] W. Chen, J. C. Hou, and L. Sha, “Dynamic clustering for acoustic target tracking in wireless sensor networks,” IEEE Trans. on Mobile Computing, vol. 3, no. 3, Jul-Sep 2004.

[10] C. H. Knapp and G. C. Carter, “Time delay estimation,” in ICASSP’76,1976.

[11] Y. Huang, J. Benesty, and G. W. Elko, “Real-time passive source localization: A practical

linear-correction least-squares approach,” IEEE Trans. Speech and Audio Processing, vol. 9, no. 8, Nov 2001.

[12] Y. T. Chan and K. C. Ho, “A simple and efficient estimator for hyperbolic location,” IEEE Transactions on Signal Processing, 1994.

[13] G. C. Carter, “Time delay estimation for passive sonar signal processing,”IEEE Transactions

on Acoustics, Speech, and Signal Processing,1981.

[14] S. M. Kay, Fundamentals of Statistical Signal Processing. Prentice Hall, 1993.

[15] T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, Introduction to Algorithms. McGraw-Hill, 2001.

Distributed Range Difference Based TargetLocalization in Sensor

Network

Chartchai Meesookho and Shrikanth Narayanan

Department of Electrical Engineering

Viterbi School of Engineering

University of Southern California

Abstract

Target localization is a key application in the sensor network context. Of the various conventional methods can be applied, and have been proposed, the Range Difference (RD) Based method is attractive due to improved accuracy and ease of implementation it affords. While the basic concepts of the RD based method can be adopted to the case of sensor networks, the data acquisition and aggregation procedures need to be formulated and characterized subject to the energy constraint. The challenge is to design an efficient algorithm that is economical and still accurate. In this paper, based on range difference localization method, we propose a distributed algorithm which allows the time delay estimation to be carried out at each participating sensor. The acquired data is fused using a sequential least squares scheme which enables the appropriate sensor selection based on the current estimate. The results, evaluated using realistic simulation models, illustrate that the distributed localization produces smaller error and consumes less energy than the centralized method. The advantage of distributed localization in terms of the accuracy becomes more conspicuous when the number of participating sensors is small while the energy saving increases when the number of participating sensors is large. The proposed method accuracy is also more robust to decreasing target signal energy and the instantaneous error from the sequence of estimates can be approximated and used to reconcile the cost and the system performance.

Ⅰ.INTRODUCTION

Target localization is one of the key motivating applications for implementing sensor networks. A large number of sensors enable the redundancy of the observations and close proximity to the target, and thus, improving the chances for improved target localization and tracking performance. Some example applications include localizing military vehicles in a battlefield and tracking wild animals in their natural habitat. Recently, conventional target localization methods have been applied to the case of sensor networks. The Range Difference (RD) based method is particularly attractive in this context [1], [2] since it offers better ease of implementation than the Maximum Likelihood (ML) estimator [3], [4], is more accurate than energy based localization [5], and does not require the prior knowledge of the signal generated by the target. While the

basic concepts of the RD based method can be adopted to the sensor networks problem, the data aggregation procedure needs to be developed and characterized. In traditional systems such as radars and microphone arrays, time series data collected from each sensor, the fundamental information needed in the process, is assumed to be available at the central processing unit without the concern for the cost incurred in gathering such information. However, due to the characteristics of sensor networks, which are typically battery-powered and wireless, the energy expenditure for time series data exchange between sensors should be taken into account. The challenge is to design an efficient algorithm that is economical and still accurate. In [1], localization was implemented on a sensor array testbed but the communication cost was not considered. The cluster-based architecture for acoustic target tracking was studied in [2]. Nonetheless, the system performance subject to the communication protocol within the cluster was not addressed. We believe that the impact of the designed algorithm on the system efficiency is highly dependent on what specific method is implemented. In this paper, based on range difference localization, we propose a distributed algorithm which allows time delay estimation to be carried out at each participating sensor so that the amount of energy incurred for time series data transmission can be decreased. The acquired data, which are the range differences, are fused using a sequential least squares scheme. The sequential nature allows for efficient sensor selection based on the current estimate at each time step, thus, enabling accuracy to be improved. The results, evaluated using realistic models and conditions, illustrate that the distributed localization produces smaller error and consumes less energy than the centralized method. Notably, the advantage of distributed localization in terms of the accuracy becomes more significant when the number of participating sensors is small while the energy saving increases when the number of participating sensors is large. The proposed method is also robust in that its accuracy is less affected by a target signal with low energy (lower SNR) and the instantaneous error from the sequence of estimates can be approximated and used to reconcile the cost and the system performance.

Ⅱ.CLUSTERING FOR TARGET LOCALIZATION

Since a centralized global processing of information or measurements gathered from all sensors does not seem to be attractive, or may be feasible, especially in a large and dense sensor field due to the demands of high communication cost, an appropriate solution is to divide the sensors into a number of smaller groups to operate on the tasks where each group has a local processing unit. The fusion and compression of locally processed data can save the energy used for the transmission of raw data to the base station or the end user. These groups of sensors are commonly called clusters and one sensor is selected to be a cluster head playing the role of a local processing unit. Generic

energy-efficient clustering protocols for decentralized processing in sensor network can be found in

[6]. A target localization problem using clustering technique may require a somewhat more specific formulation. Since the ultimate goal is to identify a particular point which is the most likely target location, the critical information should be available in the corresponding target area. Hence, only the most informative cluster may be needed and that motivates the design of an efficient cluster formation at the particular time and place. Cluster forming protocols for the purpose of target localization and tracking have been presented in [7] where the Dynamic Space-Time Clustering (DSTC) algorithm was proposed to work as a cluster forming protocol based on Closest Point of Approach (CPA). Information Driven Sensor Querying (IDSQ) introduced by Zhao et al [8] allows the maximum information gain for the dynamic clustering using an information utility measure. Dynamic clustering for acoustic target tracking was presented in [9]. A sparsely placed high-capability sensor scenario (expected to play cluster head roles) is assumed and a cluster is formed when the acoustic signal strength detected by the cluster head exceeds a predetermined threshold. The cluster’s priority is to integrate the measurements collected at each cluster member to represent the earning knowledge from each cluster. It is fairly application specific in order to describe the mechanism of the information management associated with the cluster formation. Generally, all members communicate with the cluster head either by direct or multi-hop communication. The signal processing functions are carried out at the cluster head before transferring compressed data to the base station or end user. We will call this a centralized processing scheme. A specific application such as target localization using conventional methods, however, requires a circumspect design in order to obtain an accurate and cost-effective system. The main reason is that the observation at each sensor is commonly time series data. To individually transmit such data from all cluster members to be processed at cluster head entails a large amount of overall communication cost particularly when the cluster is designed to be large to reach the localization accuracy requirement. An alternative is to apply distributed processing by some means depending upon the characteristics of the utilized methods for a particular application. We exploit a well-known scheme, the range difference based localization, for distributed processing in sensor networks and demonstrate that the system performance can be improved when compared with the centralized method.

Ⅲ. RANGE DIFFERENCE BASED LEAST SQUARE LOCALIZATION

Range Differences (RD) can be derived from Time Difference of Arrival (TDOA) estimation through the relationship between distance and traveling speed of the signal over a medium. Time delay estimation technique [10] is the fundamental tool used to determine TDOAs. We will assume the existence of an optimal time delay estimator producing estimated TDOA perturbed by additive noise to model uncertainty. There have been a number of RD-based approaches proposed in the past

[11], [12]. We focus on a closed-form least square method proposed in [11] since it was reported to

be more efficient than the other schemes and was shown to approach the Cramer Rao Bound (CRB) in high Signal to Noise Ratio (SNR) environments. Let N sensors be assigned to participate in the localization process located at coordinates x1,y1 ,..... xN,yN . Assuming the target is located

atZs xs,ys , the differences of the distance between sensors i and j where i, j = 1, . . . , N and

the source denoted by dij can be obtained by the basic relation: dij Di Dj where Di = xs xi ys yi . RDs with respect to one arbitrary reference sensor are typically used. 22

Without the loss of the generality, we select x1,y1 to be the location of reference sensor. The

time series data collected from the other sensors together with the received signal at the reference sensor can produce the TDOA estimates and RDs can be derived from TDOAs using the knowledge of signal traveling speed. In the real application, however, the actual RDs are not available since

there are some errors from TDOA estimation. Consequently, We have di1= di1 ni1, i = 1. . . N.

The TDOA estimate obtained by generalized cross correlation with Gaussian data is asymptotically normally distributed in high SNR environment [13]. Therefore, the RD estimate is also Gaussian and we assume ni1～ N 0, i2 . The Localization problem can be formulated as a linear least squares 1

x2 A b, where A

xN

x1 yi y1 22y2 yNproblem, 2d12 R12 d12 xs 1 ， ys，b ， 2 R2 d2 dN1 Rs N1 NRi xi

These linear least square equations can be solved by a batch approach and the solution, AA Ab. However, we can update without having to resolve the linear equations by a T 1T

sequential least squares procedure [14] which can be described by letting A n = A n 1 aT n Tand

b n = b 1 b 2 b n T. The sequential least square estimator becomes n 1 a n T， n n 1 n b n a n n 1 （1）， n T1 a n n 1 a n

n n a n n 1 （2）and index Tn corresponds to the n sensor. th

Ⅳ. DATA MODEL

A static acoustic target generating a WSS Gaussian random observation process, s t , is assumed where the intensity attenuates at the rate that is inversely proportional to the distance from

the target. Perturbed by additive Gaussian measurement noise i t , the received signal at ith

sensor is given by xi t = s t i Di i t . The energy can be calculated by averaging over a

time window T=

yi k =Mfs where M is the number of samples and fs is the sampling frequency as 2xi j . Assuming 1M

2kMj k 1 M 1s t and t are independent, we get

yi k = s t t (3) var y k =2 s2 t 22 t D2i 2D2

iiM (4) ，Let s t ～

22N 0, s and the noise at each sensor has the same distribution so that i t ～N 0, . The

signal PSD Gs f

bandwidth Δ , the noise PSD Gs f , and the coherence are assumed to be flat over a f z centered at frequency f0. The SNR at each

sensor,2 s 22Gw,i f Di Gs,i f.According to [10], CRB of the TDE estimate is the 33 f f f0 f0 2 2 1following ij2 8T 3 2 Cij 1 Cij

1

1 where Cij= G f 1 s,i

G ,i f G f 1 s,j G ,j f 1 It is simple to derive that the variance of the estimate

222can be in the form, i1 1 D1,

where 2

1 3D1233 f f 2 8T f0 f0 SNR 2 2 0

2 D13 1 SNR0

3

2 3

0 f f 8T f0 f0 SNR 2 2 (5) and SNR0 denotes 2s2 . Please note

th2that i1 is the variance of TDE between i sensor and the reference sensor as assumed in the

22previous section. Such variance is proportional to Di where the constants, 1 and are

functions of D12. Therefore, with a fixed reference sensor, TDE with respect to the farther sensors

from the target is less accurate.

Ⅴ. DISTRIBUTED LOCALIZATION

From the description of the range difference based localization method, we can note that there are two key steps which are TDOA estimation and target localization obtained by solving least square equations. In a Centralized scheme, both steps take place at the cluster head. The cluster head should be a reference sensor and TDOAs with respect to the cluster members can be obtained through time delay estimation. The distributed localization concepts can be adopted by enabling some processes to occur at each participating sensor, not just at the cluster head. If time series data collected at the cluster head is transmitted to the participating sensors, time delay estimation can be operated there. Broadcasting the data from one reference sensor to many participating sensors is expected to require less total communication overhead than in the opposite direction. Solving least square equations encompasses two mechanisms depending on whether batch or sequential procedure is applied. Batch estimator requires all measurements available at the same time whereas sequential estimator needs only the estimate obtained from the (n 1)th sensor and a TDOA corresponding to the nth sensor. The latter, however, demands less computational complexity as it does not have to deal with matrix inversion which might be burdensome when the matrix is large due to a large number of participating sensors. Another advantage is that the current estimate can be used as the prior information to properly select the next participating sensor. According to the data model that the variance of time delay estimation is proportional to the square distance between the sensor and the target, the preferred sensors can be simply selected by considering the nearest sensors to the current estimate. Consequently, combining the ideas of distributed processing for time delay estimation and sequential least square localization is expected to improve the localization performance in terms of both communication cost savings and accuracy. By using the notations defined in the previous section, we propose the following algorithm:

1) The sensor which receives the highest average signal energy in a certain time window is selected to be an initial sensor. Please note that the term “initial sensor” is used to call the sensor that starts the process instead of “cluster head”.

2) The initial sensor broadcasts collected time series data to at most k nearest neighbors within the maximum radio range where k is the initial expected number of participating sensors. There might be a possibility that less than k sensors can be reached depending on the coverage of the radio range and the density of the sensor field.

3) Each neighbor operates time delay estimation using time series data collected at the sensor and the one sent from the initial sensor to estimate TDOAs.

4) The initial estimate is obtained by using batch estimator based on TDOAs computed by the three nearest neighbors. The neighbor might be requested to broadcast time series data received from the initial sensor if there are less than three sensors that have already received it.

5) k-4 nearest sensors to the initial estimate achieved from the batch estimator are expected to participate in the sequential least square method. It becomes k i nearest sensors for the following estimate where i is a number of sensors that are already included in the localization process. The route of sequential estimator is constructed from the sensors described in the previous step by convex hull insertion algorithm for Traveling Salesman Problem (TSP) route [15].

7) The estimate is updated in the sequential fashion by using (1). Only and

be sent across the sensors. are needed to

8) Every time the estimate is updated, the route is also updated based on the new estimate and the decreasing number of remaining participating sensors.

9) If the next sensor in the path has not received time series data from the cluster head, the current sensor will broadcast the data to the next sensor including at most k j nearest sensors located in the radio range where j is the number of sensors which already received the data.

Ⅵ.EXPERIMENTAL RESULTS

For the experimental simulation, we assume a 100x100 square meter sensor field with 2,500 sensors randomly and uniformly placed. A static acoustic target location is assumed to have a uniform distribution within the sensor field and generates a 3500-4500Hz signal. The data observation time for time delay and average energy estimate is 1 second where sampling rate is

29000Hz. s2 and are 100 and 1, thus SNR0=100. The numbers of participating sensors

considered are 10,15,20 and 25. The radio range is 5 meters.The estimation error is evaluated by the Mean Square Error(MSE), xs xs ys yx . 100 Monte Carlo trials were conducted to 22

average the effect of target location and sensor topology. For each topology, 100 runnings are used to average the noise. We assume that the average energy of the received signal at each sensor has a normal distribution with the mean and variance defined in (3) and (4). The sensor which receives the highest energy is selected to be the initial sensor for the distributed method and the cluster head for the centralized

method.Figure 1 illustrates the MSE for both centralized and distributed localization with different numbers of participating sensors. It is obvious that the error caused by the distributed method is smaller than the centralized method. The reason is that the distributed algorithm uses the immediate estimate as the prior information to select the sequence of the participating sensors that include the nearest sensors to the estimated target location. Since the closer sensors to target provide the more accurate time delay estimation as described in the previous section, the localization accuracy is

improved when compared with the centralized method which preselects the participating sensors before achieving the result. The difference in the error caused by the two algorithms becomes smaller when the number of participating sensors increases since a large number of sensors make the coverage of region activated by both algorithms more similar. We also study the performance of both schemes when s2 is varied which corresponds to the variation of the energy of the signal (SNR)

created by the target. Values of s2= 10, 40, 70, and 100 are used and the number of participating

sensors is 15. The results in Figure 2 illustrates that the centralized scheme suffers more than distributed scheme when s2 decreases. This is also affected by the different participating sensors

selected by both schemes.When s2 is small, SNR0 is small and it makes in (5) become

large. i2, thus, is proportional to Di2 with a higher rate. Thedistance between sensors and target 1

becomes more influential on the localization performance. The sensors selected by the centralized scheme which are likely to be farther from the target than those selected by distributed scheme, therefore,produce larger error.We use the first order radio model described in [6] for the communication overhead evaluation. To exchange k-bit data between a distance d, the radio expends ETx Eelec*k amp*k*d2 and ER Eelec*k. ET and ER represent the energy xxx

dissipated by the transmitting and receiving data, respectively.Eelec=50nJit is the energy used

to run the transmitter or receiver circuitry and amp=100pJbitm is for the transmission

2

amplifier. We assume that each data sample and the data representing each element in and requires 8 bits to be encoded. Thus, for time series data exchange, k = (Sampling Rate) x (Observation Time) x (bits/sample)=9000*1*8=72000bits. For the communication required in

sequential least square, k = (Summation of number of elements in and ) x (bits/sample)= (3+9)*8 = 96 bits. As ET and ER ∝ k, we can note that the energy spent to exchange the time xx

series data is much more than the amount used for sequential estimate update. Figure 3 illustrates the energy dissipated by both schemes. It is can be noticed that the distributed method enables significant amount of energy savings compared to the centralized method, particularly when the number of sensors is large. This can be simply explained by considering, firstly, the communication between reference sensor and L participating sensors within the radio range.The centralized scheme requires L transmissions in order to obtain the time delay estimates with respect to all participating sensors while only one transmission is enough for distributed algorithm. The extra cost for distributed algorithm is what is used to sequentially aggregate TDOAs extracted from time delay

本文来源：https://www.bwwdw.com/article/qa0j.html