无线传感器网络改进质心算法的节点自定位

张 华，刘玉良，单海校

（浙江海洋学院机电工程学院，浙江舟山 316000）

传感器节点自定位就是根据少数已知位置的节点，按照某种定位机制确定自身的位置。在无线传感器网络各种应用中，应当知晓监测目标的具体位置，没有确切监测消息的位置没有任何意义[1]。根据节点是否知道自身的位置信息，把传感器节点分为信标节点和未知节点；按照定位过程中是否需要测量节点之间的实际距离，把定位算法分为基于距离的定位算法和距离无关的定位算法。无须测距的定位机制仅仅依靠网络的连通性等参数进行定位，主要定位机制包括质心算法、DV-Hop算法、Amorphous算法、APIT算法等。距离无关的定位机制定位性能受环境因素的影响小，虽然定位的误差相应有所增加，但定位精度能够满足多数传感器网络的应用要求，是目前大家普遍重点关注的定位机制[1-7]。

质心算法是南加州大学的Nirupama Bulusu等提出了一种仅基于网络节点连通性的定位算法，这种估算的精度取决于信标节点的密度和分布。许多人针对质心算法提出了改进思路，文献[2]提出一种密度自适应的HEAP算法，通过在信标节点密度低的区域增加新标节点，以提高定位的精度；文献[3]中提对距离无关的几种定位机制进行了比较，信标节点密度的大小影响了定位精度的高低，还有一些文献通过对信标节点与未知节点的距离的研究，如采用时间差或以距离作为权值参数来讨论定位的精度问题。考虑在不增加信标节点密度的情况下以节点间的距离作为约束，探讨通信半径和节点数对节点定位精度的影响，采用极大似然估计法对函数进行优化，改进节点自定位的精度。

1 传统质心算法

从现有的文献[4]和研究结果来看，对于以随机抛洒形式分布的，以自组织构建而成的无线传感器网络而言，节点一般有如下分布：均匀分布、高斯分布、瑞利分布等，其中以高斯分布模型最为常见。为研究问题方便，假定所有节点都布撒于同一个平面体系中，且各节点的通信模型选取圆形通信模型。

质心算法仅基于网络节点连通性，思想是：信标节点每隔一段时间，向邻居节点广播一个信标信号，信号中包含自身ID和位置信息。当未知节点接收到来自不同信标节点的信标信号数量超过某一个预设门限或接收一定时间后，该节点就确定自身位置为这些信标节点所组成的多边形的质心。

在传感器网络节点布置后，信标节点将周期性向周围发布自身信息。设有一未知节点p与周围n个信标节点建立联系，各信标节点的坐标分别为（x1，y1），（x2，y2），（x3，y4）…（xn，yn），按以上假设可以在二维空间中对问题进行探讨，按照质心算法的思路，未知节点对自身的估算坐标P（xcen，ycen）为，

然而试验表明，用质心坐标作未知节点的坐标，由于受到节点分布密度、节点分布模型、信号传输环境噪声，节点自身性能等影响，大约有90%未知节点定位精度低于信标节点间距的1/3[1,4]。

2 极大似然估计法的改进模型

质心算法完全基于网络的连通性，受分布密度、分布模型、信号传输模型等影响，使得定位误差较大[2,5]，从数学角度来说，质心坐标仅仅依赖于信标节点的坐标，没有受到其他条件的约束，本文考虑保留质心算法的定位优越性，以信标节点与未知节点之间的距离作约束，以提高定位精度。

假设该未知节点p与其通信的各信标节点间的距离分别为d1，d2，d3，…dn，按照解析几何原理建立信标节点与未知节点p间的距离方程组，其中，未知节点的坐标为估算坐标p（xest，yest），如下

极大似然估计法采用对上式各等式相减，变形并采用矩阵形式，进而通过线性方程求出未知节点坐标。将信标节点的坐标（x1，y1），（x2，y2），…，（xn，yn）看成 X1，X2，…，Xn的样本值，样本函数 P｛ X = Xi｝=p（（xi，y）i，θ），其中（xi，y）i∈D，θ∈D；D代表所设定的区域取值范围，传感器网络节点在相互之间通信过程中，受噪声干扰影响，节点分布密度，节点间距离测量误差以及节点自身计算能力不足引起的计算误差等[5,6]，将使得公式2不会全部成立，假设各信标节点与未知节点p之间的测距误差分别为δ1，δ2，…，δn

3 算法步骤设计

假设信标节点和未知节点可以分开进行布撒，首先将信标节点进行均匀分布，在100×100单位面积中，均匀布撒100个信标节点，信标节点通过GPS或者向周围发布自身信息等方式构建成网络，此时各信标节点都已经获知自身各种信息，然后再将未知节点随机布撒，设通信半径为R。节点初始分布图如图1所示。

算法设计如下：

①在100×100单位中，按均匀分布方式布置100个节点，作为信标节点，各信标节点都已知道自身信息；

②在该区域内，随机布撒若干节点，即为未知节点；各未知节点向周围发送信息，搜索自身通信范围内的信标节点；

③测算该未知节点与信标节点的距离；

④每个未知节点按照公式1计算出与其通信的信标节点的质心坐标；质心坐标作为该未知节点的初次估算位置；

⑤在图中标出该未知节点对应的质心坐标，并将质心与该未知节点用线画出；

⑥按照公式5计算出计算极大似然值，若是最大值则输出，若不是则返回③，继续搜索，寻求直到满足要求。

4 仿真结果及分析

在不同的通信半径，不同的未知节点数目的优化分布图形如下，其中通信半径分别取50单位和30单位，信标节点取均匀分布100个，未知节点分别取50个，20个。图中蓝色圆点表示信标节点，各坐标取值范围是0≤x≤100；0≤y≤100；红色“*”表示未知节点，蓝色“o”表示质心坐标位置，红色的短线表示某未知节点通信范围内的信标节点的质心与该未知节点的连线。采用主频为3G的计算机在matlab7.0.1环境下进行仿真。

图1 各节点初始化分布Fig.1 Distribution of each node initialization

图2 50个未知节点，通信半径30时节点分布Fig.2 50 unknown nodes,the nodes distribution when communication radius is 30

图3 50个节点，半径30时误差分布Fig.3 Error distribution 50 unknown nodes,communication radius of 30

图4 20个未知节点，通信半径30时节点分布Fig.4 The nodes distribution 20 unknown nodes,communication radius of 30

图5 20个节点，通信半径30误差分布Fig.5 Error distribution 20 unknown nodes,communication radius of 30

图6 20个未知节点，通信半径50时节点分布Fig.6 The nodes distribution 20 unknown nodes,communication radius of 50

图7 20个节点，通信半径50误差分布Fig.7 Error distribution 20 unknown nodes,communication radius of 50

图8 信标节点个数与误差值Fig.8 The number of beacon nodes and error

图1为节点初始分布图，表示信标节点均匀分布，未知节点随机分布，其中信标节点数目为100，未知节点数目为20。图2、图4、图6，表示未知节点与其所对应的质心点；图3、图5、图7表示各未知节点的测量误差值分布。图8表示信标节点与误差值的变化关系。

①从图2～图7可以看出，未知节点分布是非均匀分布，误差值跟节点数目有关；数目越大，误差越小；由于信标节点已经处于均匀分布状态，未知节点的数目也能对定位产生较大影响。考虑到实际情况，信标节点在完成部署以后，不间断的向周围传播自身信息，当其中有些未知节点在经过算法迭代完成自身定位后，也加入到不间断传播自己位置信息的行列，而这些未知节点自身的位置信息本身精度就不高，误差经过不断的迭代叠加，从而使得整体定位精度不够高。

②从图4和图6可以看出质心坐标有趋向中心分布，图4的通信半径为30单位，而图6为50单位，表明通信半径越大，质心坐标越向中心分布，此时误差值也越大（误差可对比图5和图7）；对比图2和图4，可以观察相同的通信半径下，节点数目越大，对应的误差值要越小。回到传感器网络实际状况，给定信标节点的位置是均匀分布，且密度较高，当通信半径在扩大时，表明某个未知节点周围与其通信的信标节点在增加，均匀分布的信标节点的质心位置一定会趋向于整个坐标中心位置，实际上，对应的未知节点却可能分布在边缘，这样使得误差值要明显偏大，如图6分布。

③从图8可以观察到信标节点与误差值的关系，表明在未知节点数目一定，通信半径一定的情况下，信标节点越多，所产生的误差值越小。文献[3]就是论证了通过在信标节点密度低的区域增加新标节点，以提高定位的精度。

5 结束语

仿真结果表明，采用极大似然估计法情况下，在信标节点均匀分布而未知节点随机分布的传感器网络中，节点的通信半径越大，误差越大，定位精度越低；信标节点的数目越多，误差越小，定位精度越高；当信标节点数目一定时，未知节点越多，误差越大，定位精度越低。

[1]孙利民,李建中,陈 渝,等.无线传感器网络[M].北京:清华大学出版社,2005.

[2]BULUSU N,HEIDEMANN J,ESTRIN D.Density adaptive algorithms for beacon placement in wireless sensor networks[C]//IEEE ICDCS’01,Phoenix,AZ.April 2001.

[3]HE Tian,HUANG Chengdu,BLUM Brian M,et al.Range-Free Localization Schemes in Large Scale Sensor Networks[C]//Proceedings of the 9th Annual Inter2 National Conference on Mobile Computing and Networking(MobiCom),San Diego,California,USA:ACM Press,2003:81-95.

[4]JOURDAN D B,DE WECK O L.Multi-objective genetic algorithm for the automated planning of a wireless sensor network to monitor a critical facility,2004:Citeseer.http://74.125.155.132/scholar?q=cache:Bcn_4LwctagJ:scholar.google.com/&hl=zh-CN&as_sdt=0

[5]田金鹏.无线传感器网络节点定位技术研究[D].上海:上海大学,2009.

[6]江 冰,吴元忠,谢冬梅.无线传感器网络节点自定位算法的研究[J].传感技术学报,2007,20(6):1 381-1 385.

[7]SHENG X,HU Y H.Maximum likelihood multiple-source localization using acoustic energy measurements with wireless sensor networks[C]//Signal Processing,IEEE Transactions on2005,53(1):44-53.