基于Euclidean修正的分布式加权定位算法

フ 要:传统的多维定标（MDS）算法由于采用多跳距离代替节点间的直接距离，生成的局部网络准确度低，在不规则网络中定位误差大。相对于现有的算法，引入Euclidean方法来产生多跳节点间的准确距离，并采用一种加权机制来改进协强系数，以抑制累积误差。仿真结果表明该方法在C型网络和低连通度的矩形网络定位中能取得更好的效果。

ス丶词:加权多维标度； 多跳距离；局部地图； 接收信号强度指示； 节点定位； 无线传感器网络

ブ型挤掷嗪: TN929.5；TP212.9 文献标志码:A

Abstract: The traditional MultiDimensional Scaling (MDS) algorithm adopts multihop distance to replace direct distance, resulting in low accuracy of the local network and large localization error in irregular network. Relative to the existing algorithms， the paper introduced the Euclidean algorithm to generate accurate multihop distance between nodes, and used weighting mechanism to improve the coefficient of stress. The simulation results show that in low connectivity rectangle network and Cshape network localization, this method achieves better performance.

Key words: weighted MDSMAP；multihop distance；local map；Received Signal Strength Indication (RSSI)；node localization；Wireless Sensor Network (WSN)

0 引言

对于无线传感器网络（Wireless Sensor Network,WSN），不仅需要采集数据，还需要明白这些数据所来自的空间位置[1-2]。通常的定位方法按照有无锚节点分为两类。有锚节点的定位方法通常简单易行，但是缺点在于对锚节点精度的依赖性比较高，而且每个节点都要能够直接与锚节点进行通信。实际情况中，由于有的节点和锚节点距离太远，导致无法定位，无锚节点的定位算法刚好弥补了这种不足。多维定标(MultiDimensional Scaling,MDS)［3-4］技术是一种有锚节点和无锚节点相结合的算法，它利用节点间相对位置关系进行定位，在没有锚节点时也能得到节点间的相对坐标。在大型网络，尤其是那些联通度较高的网络有很好的定位效果，但是对于联通度较低的网络，定位误差非常明显。在此基础上产生了许多改进的算法：MDSMAP(P)[5]算法采用生成局部地图的方法，将多跳跳数限定在4跳范围内，之后再将局部地图进行融合，然而如果局部地图不够准确，多次融合的过程中会产生较大的累积误差。MDSMAP(P，O，R)[6]算法，用迭代更新的方式求解相异性矩阵，使得生成的相对地图更为准确。MDSMAP(W) [7]算法考虑到相隔越远的节点间其距离误差也越大，在约束条件中引入了加权系数以抑制累积误差。然而这些方法都没有从根本上计算出准确的多跳距离。本文对以上问题进行了研究，结合以上各算法优点，提出了MDSMAP(E)算法，采用Euclidean方法得到准确的多跳距离，从而明显降低了低连通度网络中的定位误差。

1 经典MDSMAP算法

若一个图的每条边长度确定且具有刚性，那么由这些边连接而成的几何图形就被完全确定了［8］。

MDSMAP(C)［9］算法通过实体间的相异性来建立相对坐标。用pij表示实体i，j之间的相异性。用dij=(xi-xj)2+(yi-yj)2表示实体i，j的欧氏距离。实体间越相似，它们的距离就越接近。用式ij=f(pij)П硎竟兰凭嗬搿2⒍ㄒ宕价函数

Stressl=∑ij,i≠j(ij-dij)2(1)

求解相对坐标的问题就转化为了求式(1)的最小值的问题。在经典MDS中，取Иij=a+b•pij。求解式(1)的步骤是首先令P2=(p2ij)，双中心化P2У玫姜

A=-12(I-1nE)•P2•(I-1nE) (2)

其中I为单位矩阵，E为元素全为1的矩阵。对得到的A矩阵进行奇异值分解(Singular Value Decomposition,SVD)得到矩阵B=VAV′。求得坐标矩阵オ

X=VA12(3)

该算法的结果并不理想，其误差主要来源于两个方面：1)对于不能直接测距的节点采用多跳距离代替其欧氏距离，结果误差较大。2)在实际情况中相异性与欧氏距离并非满足简单的线性关系，采用Иij=a+b•pijП硎惊Иij=f(pij)显然是不够准确的。特别是C型网络，这些误差往往高达通信半径的1.5倍甚至更高。

为了减小欧氏距离带来的误差，MDSMAP(P，C)算法［7］构建两跳内的局部地图，距离误差得以控制，之后再将所有的局部地图通过旋转，平移变换“融合”到一起，该方法取得一定的效果。但局部地图内的最大跳数为4跳，一些实体间的欧氏距离仍然不准确，这将导致局部地图的变形。这种变形虽然十分微小，但是在多次的地图融合过程中会产生较大的误差积累，特别是在网络不规则分布的边缘处。

2 现有的改进算法

继经典MDSMAP算法之后陆续出现了一些非线性关系的MDS算法， 它们的特点都是将Иij=f(pij)У墓叵涤靡桓雎足单调关系的表达式代替，如表1所示。

而相异性和欧氏距离并没有这么强的单调约束，pij和ij只需要满足，对于任意i，j相异性小的实体距离更近，即当pij

xki=xk-1i+αn-1∑j∈M,j≠i(1-k-1ijdk-1ij)(xk-1j-xk-1i)(4)

yki=yk-1i+αn-1∑j∈M,j≠i(1-k-1ijdk-1ij)(yk-1j-yk-1i)(5)

其中:Е廖步长因子，M表示节点i两跳范围内所有节点的集合， n为M中的所有节点个数。オ

е钡椒嵌攘开MDS协强系数S小于容许误差ε，如式(6)所示：オ

S=Stressl=∑ij,i≠j(ij-dij)2∑ij,i≠jd2ij < ε(6)オ

非度量MDS(P，O)虽然解决了相异性和欧氏距离非线性的问题，但未解决节点多跳距离不准确的问题。

3 MDSMAP(E)

针对以上问题，对非度量MDS算法进行了以下改进：1)使用Euclidean算法计算多跳节点的间距，从而比MDS算法得到的相对地图更为精确；2)由于协强系数反映的是估算位置的欧氏距离和实际位置欧氏距离的偏差大小，因而一跳节点的间距对图形“刚度”的影响更大，跳数越多影响越小。定义加权协强系数［7］：

S = WStressl = ∑ij,i≠jωij(ij-dij)2∑ij,i≠jd2ij(7)お

式中Е鬲ij=1/pij。Фㄎ徊街枞缦隆＊

3.1 计算多跳节点的距离

每个节点和它附近两跳范围内的节点通信组成局部地图，通过RSSI值获得每对可通信节点间的距离。用Euclidean算法代替Floyd算法获得最短路径距离矩阵Pij。オ

Euclidean的具体算法如下：D是A的两跳邻居,

p2AD = p2AC + p2CD-2cos∠ACD(8)

cos∠BCD = p2BC + p2CD-p2BD2pBCpCD(9)

cos∠BCA = p2BC + p2CA-p2BA2pBCpCA(10)

当B，C在AD同侧时∠ACD=∠BCD-∠BCA，在异侧时∠ACD=∠BCD+∠BCA。オ

以上两种情况均有可能，但是正确的结果必须满足：

1）в捎D为A的两跳邻居，故max{pAB，pBC，pCD，pBD，pAC}

2）若两种情况计算出来的pAD都满足步骤1）中的表达式，则找到D的一个邻跳邻居E，且E是B(或C)的邻居，那么用E代替C(或B)，来计算同侧和异侧情况的pAD，从4个距离值中选出两个最接近的值作为pAD。オ

如图3，在计算出2跳距离pAD，pAEУ幕础上可以计算出3跳距离pAF。オ

3.2 生成局部地图[11]

对每一个节点执行以下算法：

步骤1 执行经典MDS算法生成初始估计坐标(x0i,y0i)。オ

步骤2 计算初始欧氏距离：

d0ij = (x0i-x0j)2 + (y0i-y0j)2オ

步骤3 用PAV单调回归算法计算出И0ij。オ

步骤4 对两跳范围内的所有节点，采用下面两式叠代更新局部地图坐标

xk+1i = xki-αSx/Sx(11)

yk+1i = yki-αSy/Sy(12)オ

作如下近似:

xki=xk-1i+αn-1∑j∈M,j≠iωij(1-k-1ijdk-1ij)(xk-1j-xk-1i)(13)

yki=yk-1i+αn-1∑j∈M,j≠iωij(1-k-1ijdk-1ij)(yk-1j-yk-1i)(14)

取Е=0.1。オ

步骤5 更新计算欧氏距离：

dkij = (xki-xkj)2 +(yki-ykj)2オ

步骤6 用PAV算法更新估计欧氏距离Иkij。オ

步骤7 计算协强系数。

WStressl = ∑ij,i≠jωij(kij-dkij)2∑ij,i≠j(dkij)2(15)オ

步骤8 若协强系数WStressl

3.3 地图融合

首先选择一块具有最多节点的地图作为中心地图，然后选择与这块中心地图有最多公共交点的地图作为下一次将融合的地图。本文通过旋转、镜像、平移和缩放将融合地图投影到中心地图上，可以通过公共点坐标的对比来实现，实现变换后的坐标点与其本身在主地图中坐标均方误差最小。

设Y为公共点在融合地图中的坐标矩阵，X为公共点在主地图中的坐标矩阵。Y^为投影后的坐标矩阵。于是问题变为求如下坐标变换：オ

ИY^=sYT+lt′(16)

其中:T为旋转镜像矩阵，要求T′T=E(E为单位矩阵)，s为缩放系数，l与Y相同列数的全1向量，t为坐标平移向量矩阵，使得ИY^与XУ木方误差最小，即要求最小化L(s,t,T)：オ

L(s,t,T)=tr［X-(sYT+lt′)］′［X-

(sYT+lt′)］(17)

其中tr代表矩阵的迹(取矩阵对角元素和的操作)。

通过普鲁克分析求出使该代价函数最小的变换矩阵：

1)计算矩阵C=X′JY，其中オ

J=I-n-1E(18)

2)计算矩阵CУSVD分解:

C=PΦQ′(19)

3)求得旋转变换矩阵:

T=QP′(20)

4)求得缩放系数:

s=tr(X′JYT)/tr(Y′JY)(21)

5)求得平移向量矩阵

t=n-1(X-sYT)′l (22)

执行变换=sAT+lt′，Ы融合地图的所有节点矩阵A投影到主地图上，形成新的主地图，重复以上过程直到主地图包含所有节点，得到整张地图后再通过所有锚节点位置将相对地图通过旋转、镜像、平移和缩放变换为绝对地图。

4 算法分析

在Matlab环境下分别对矩形随机网络和C型随机网络进行了仿真。图4是200个节点随机分布在100@m×100@m区域内的矩形网络的一个例子。该网络通信半径15@m，测距误差5%，平均网络连通度12.5，含4个锚节点(图中表示锚节点，表示待定位节点)。采用MDSMAP(E)算法的误差仅为3.11%。图5是不同算法定位结果，其中表示估计位置，线段指向实际位置。

由仿真实验结果可以看出，在网络有较大空洞处(连通度较低)，MDSMAP(C)会产生较大的定位误差，MDSMAP(P，C)通过局部地图信息融合的方法，有效控制了这些误差。而MDSMAP(P，O，R)在此基础上改进了欧氏距离和相异性关系，对全局地图进行了修正，取得了明显的效果。MDSMAP(E)使用Euclidean得到了更加准确的多跳距离，并采用加权误差度量机制，从进一步提高了算法定位的准确性。

图6是160个节点随机分布在100@m×100@m区域内的C型网络，通信半径15@m，测距误差5%，平均网络连通度10.95，锚节点个数为4(图中表示锚节点， 表示待定位节点)。定位误差图7中表示估计位置，线段指向实际位置。

由图7可以看出，部分区域连通度相对较低的C型网络，MDSMAP(C)算法的误差达到了130%，MDSMAP(P，C)算法的误差为35.29%，较大的误差主要集中在连通度较低的C型网络“两端”，MDSMAP(P，O，R)算法通过修正的办法将误差控制在了18.7%。而MDSMAP(E )算法获得了准确的多跳距离，这相当于提高了网络的连通度，误差仅为9.93%。仿真结果表面MDSMAP(E)算法更能适应不规则网络的定位要求。

图8是50次定位实验的平均误差和连通度的关系曲线，在节点数目固定的情况下，我们通过扩大通信半径来增加连通度。由图可以看出，在连通度较低的情况下，锚节点数目对定位结果的影响较大，而连通度较高的情况下，影响较小。在平均连通度增加到30时各算法都有较小的定位误差，MDSMAP(C)算法在C型网络中的定位除外，因为虽然连通度增加了，但多跳距离的误差随着通信半径的增大也更高。而在连通度较低时MDSMAP(E)算法具有明显的优势。

5 结语

在研究了MDSMAP(C)算法和MDSMAP(P，O，R)算法的缺陷后，提出了MDSMAP(E)算法。该算法从多跳距离的计算和融合过程中误差的控制两个方面来提高定位精度。经理论分析和实验证明，在连通度较低的情况下该算法优势明显，但不足之处在于该算法复杂度高、节电能量消耗大。在无线传感器网络的实际应用上，对定位精度和能耗往往要进行折中考虑，下一步还需要设计一种分簇机制减少局部地图融合次数。

げ慰嘉南:

[1] 王福豹，史龙，任丰原.无线传感器网络中的自身定位系统和算法 ［J］. 软件学报， 2005，16(5): 857-868.

[2] 廖先林，张铨荣，王光兴，等.无线传感器网络节点定位问题研究［J］. 武汉理工大学学报:信息与管理工程版,2007，12(5):47-51.

[3] BORG I, GROENER P. Modern multidimensional scaling theory and applications［M］.New York: SpringerVerlag，1997.

[4] COX M. Multidimensional scaling［M］. London: Chapman and Hall，1994.

[5] SHANG Y， RUML W， ZHANG Y. Improved MDSbased localization［C］// Proceedings of IEEE International Conference on Computer Communications 2004. New York:IEEE,2004:2640-2651.

[6] VIVEKANANDAN V,WONG V. Ordinal MDSbased localization for wireless sensor networks［J］. International Journal of Sensor Networks,2006,1(3/4):1-5.

[7] VO N, VO D S, CHALLA S. Weighted nonmetric MDS for sensor localization［C］// International Conference on Advanced Technologies for Communications 2008. Berlin:SpringerVerlag, 2008: 391-394.

[8] EREN T， GOLDENBERG D，WHITELEY W， et al. Rigidity computation and randomization in network localization［C］// 23rd Annual Joint Conference of the IEEE Computer and Communications Societies.New York:IEEE，2004: 2673-2684.

[9] SHANG Y，RUML W，ZHANG Y，et al. Localization from mere connectivity［C］// Proceedings of the 4th ACM International Symposium on Mobile Ad Hoc Networking and Computing. New York:ACM,2003: 201-212.

[10] 肖玲，李仁发，罗娟. 基于非度量多维标度的无线传感器网络节点定位算法［J］.计算机研究与发展，2007，44(3):399-405.

[11] 马震，刘云，沈波. 分布式无线传感器网络定位算法MDSMAP(D) ［J］.通信学报，2008，29(6):57-62.