一种基于分簇的3D-RSSI的定位算法

刘晓鑫，方旺盛，张永建

（江西理工大学信息工程学院，赣州341000）

引 言

随着无线传感器网络（WSN）的发展，节点定位技术已经渗入到生活的各个方面，无线传感器网络之间的协作能够进行目标跟踪、井下定位、紧急求救、森林火灾等［1-2］。

对于大多数无线传感器网络，没有与位置相结合的信息是没有意义的。在节点精确定位的同时，还要提高路由效率，降低功耗，延长整个网络的寿命。现有的算法中按照信息处理方式可分为两类：集中式算法和分布式算法［3-4］。集中式算法的缺点在于中心节点位置附近的节点会因通信数据过大导致节点能量耗完，以致整个网络数据处理中心瘫痪。分布式算法则适用于大规模无线传感网络，典型的分布式算法的优点在于获得精确位置估算的同时尽可能延长了整个网络的生命周期［5］。

在大规模无线传感网络中，由于不断迭代，以至于最后的节点位置出现较大的误差，所以本文提出分簇算法的节点定位算法，在各分簇中把误差降低到最低，然后从sink节点开始把各簇的位置的节点合并，最后完成全局节点的定位。在定位算法方面考虑到算法复杂度、成本等，本文选取基于RSSI的定位算法。RSSI节点定位方法通过接收锚节点上的功率，计算传播功耗，利用理论将RSSI强度转化为距离，利用最小二乘法估计未知节点位置坐标。但在计算过程中不断叠加的误差，使得整个网络的节点定位误差增大。故本文从减少通信开支、降低成本和节能角度提出了一种基于分簇的3D-RSSI的定位算法，首先确定各簇内的簇首，簇首内保存着各簇的拓扑结构，各簇内节点之间的距离通过接收到的信号强度来确定，随后从sink节点开始融合各簇间的未知的位置，来实现整个网络的定位。

1 本文分簇算法

1.1 LEACH协议

分簇算法［6］最大程度上延长整个网络的寿命，简化了整个网络定位的复杂度，并且减少了网络通信量，使得整个网络节点定位更加精确。本文选用LEACH 路由协议［7］，LEACH 协议是无线传感网络中的一种基于簇类结构和分层技术的协议，相比于传统Flooding和Gossiping协议，较大程度上节约了能量。LEACH 路由协议其基本思想是以循环方式随机选择簇首节点，将整个网络的能量负载平均分配到每个节点上，从而降低能耗来延长网络的生存时间。LEACH 定义了“轮”的概念，每一轮由初始化和稳定工作两个阶段组成。在初始化阶段，随机选择节点作为簇首，成为簇首之后广播其信息，簇首周围的节点根据接收到的信号强度来判断是否要加入该簇，并告知簇首。在稳定工作阶段，节点完成了对周围坏境的信息采集、数据融合，并发送至汇聚节点。完成这一轮后进入下一工作周期。分簇节点自定位技术包括三个步骤：①各个簇的构建；②簇内节点位置的估算；③各簇节点的融合和全局节点的定位。这三个阶段都由LEACH 协议来完成，这种适合用于二维坐标的算法也可推广到三维空间中。

簇首节点的选取是LEACH 协议中的关键，具体的选择办法是：启动节点，各节点产生一个［0，1］之间的随机数，若该值小于阀值T（n），则该节点成为簇首。在每轮循环中，如果节点已经当选为簇首，则把T（n）设置为0，该节点在这一轮中不会再次当选为簇首。如果节点尚未当选为簇首，则会以概率T（n）参与选择；并伴随着当选过簇首的节点数量的增多，剩余节点的T（n）增大，产生小于T（n）随机数的概率随之增大，所以节点当选为簇首的概率增大。剩下一个节点未当选时，T（n）＝1，表示该节点无条件成为簇首。T（n）的计算公式如下：

其中，p 为期望的簇首节点中的百分比；r是当前轮数；r mod（1／p）代表这一轮循环中当选过簇首节点的个数，G是在最后的1／p轮中未成为簇首节点的节点集；T（n）实际上是在第r轮尚未成为簇首节点的节点成为簇首的平均概率。

1.2 基于节点势的分簇算法

对LEACH 协议作简要的改进，分簇过程从位于网路中心的sink节点开始，首先以sink节点作为其中一个簇首，簇内节点依次按规则寻找临近节点，直到找到对应的簇首。簇从sink节点逐渐向网络各个方向扩展，直到整个网路被覆盖。寻找相邻簇首的具体规则如图1所示。

2 信号模型

2.1 RSSI无线信号传输模型

无线信号的传输路径损耗对于RSSI定位算法［8-9］的精度影响很大。常用的路径损耗模型有：自由空间传播模型、对数距离路径损耗模型和哈它模型等。自由空间传播模型是假设在一个理想的传播环境，在发送者和接收者之间只存在一条无障碍的直线传播路径。接收端收到的信号平均功率pr（d）为：

图1 节点寻找簇首流程图

其中，pt为发送信号的强度，Gt和Gr分别是发送端和接收端的天线增益，L（L≥1）为系统损失，λ为波，d为接收端与发送端之间的距离。通常情况下，取Gt＝Gr＝1，L＝1。

从（1）式可以看出在d＝0时，接收功率是无意义的，因此对于该模型通常是定义一个参考距离d0，在d0所接收到的功率当成是参考功率，则（1）式可改写为：

在实际环境中，由于存在多径效应及噪声的干扰，接收端收到的功率和自由空间传播模型的计算结果存在较大误差，利用如下对数损耗模型对其进行修正：

其中，pr（d）与长度相关的路径耗散，d0是从发送器附近测量的参考距离；α为路径衰减因子；取值一般2～4之间，N为随机噪声，服从均值为零的高斯分布。

2.2 三维RSSI定位模型

在无线传感器网络中，对于二维定位系统，通过3个或3个以上的锚节点的距离可以确定一个未知节点的坐标。推广到三维定位系统中，需要4个或以上的锚节点的距离确定一个未知节点的坐标。假设在无线传感器网络三维系统中，存在k个不在同一平面的锚节点（x1，y1，z1），（x2，y2，z2），（x3，y3，z3），…，（xk，yk，zk），并且锚节点到未知节点的距离分别为d1，d2，d3，…，dk。利用最小二乘法定位未知节点：

将前面k-1个方程分别减去最后一个方程得到：

式（5）的线性方程表示方式为A·X＝b，其中：

3 仿真与分析

本文用MATLAB仿真分析经典3D-RSSI模型、分簇3D-RSSI模型和参考文献［6］算法，在1000×1000×1000 m3的正方体空间中，随机分布1000 个节点，锚节点占10%～30%。三种算法各仿真50次，仿真结果取50次的平均值。

定位误差在无线传感器网络中是判断定位算法的重要指标，首先仿真研究锚节点个数与平均定位误差的关系，路径耗散指数n取4，通信半径为60m，信标节点由开始的100（30%）个，每次仿真增加40 个，直至达到300（30%）个，实验仿真表明，如图2～图5所示，平均定位误差随着锚节点数量的增加而递减。由此可证本文分簇3D-RSSI模型优于经典3D-RSSI算法。

覆盖率也是判断定位误差的重要参数。实验仿真表明，覆盖率随着锚节点数量而增大，由此可以推断在大规模无线传感网络中，分簇算法不仅平均误差减小了，而且也提高了覆盖率。

图2 锚节点数量与平均定位误差关系

图3 锚节点数量与定位覆盖率关系

图4 分簇空间节点的定位效果图

在图2中，仿真表明随着锚节点的增加，每次增加10个锚节点，仿真平均误差随着锚节点数量的增加而减小，说明锚节点的数量在节点定位精确度方面有着重要作用，但锚节点的增加会导致成本费用的提高，所以锚节点数量控制在15%左右最为合理。在图3中覆盖率也是相同的问题。

图5 整个网络的节点定位效果图

图4～图5分别是分簇定位效果和整个网络的定位效果图。相比集中式算法，本文提出的算法节省了能耗，提高了定位精确度，且没有增加硬件成本。

采用CC1100 芯片测试两节点之间的性能，CC1100是一款超低功耗UHF频段无线收发芯片，为低功耗无线应用而设计。在接收、传输模式下，传输速率为1.2kbps，在433MHz时，电流值为15.4mA，在实际应用方面有一定的价值。

结 语

本文首先提出了在三维空间中适用于大规模网络的节点定位算法，在空间中实现分簇，降低了通信量和复杂度，在使用较小能耗的同时实现对整个网络的覆盖。相比集中式算法而言，本文提出的分簇定位算法能够在空间中最大发挥优势，避免了某些节点能量过早消耗完。本文还提出运用3D-RSSI算法来实现对节点的精确定位，下一步将研究复杂环境下的分簇定位算法。

［1］李晓维，徐勇军，任丰原.无线传感器网络技术［M］.北京：北京理工大学出版社，2007.

［2］He T，Cheng D，Blum B M，et al.Rang-free localization schemes in large scale sensor network［C］／／Proceedings of the 9 th Annual International Conference on Mobile Computing and Net-working，MOBIHOC 2003.San Diego（CA，USA），2003.New York（NY，USA）：ACM Press，2003：81-95.

［3］Bal M，Liu M，Shen W，et al.Localization in cooperative wireless sensor networks：a review［C］／／The 13th IEEE International Conference on Computer Supported Cooperative Work in Design.Santiago，April 2009：22-24.

［4］King C，King S L，Vincent T.Localization in sensor networks with limited number of anchors and clustered placement［C］／／Proc.of the IEEE Wireless Communications and Networking Conference，2007：4425-4429.

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

［6］Miao Y，Cui L.A low complexity cluster localization method for wireless sensor network［J］.Chinese High Technology Letters，2009，19（4）：348-355.

［7］龙际珍，陈沅涛，邓冬梅，等.基于LEACH 协议的助理簇首分簇算法［J］.计算机工程，2011，37（7），103-105.

［8］李刚，陈俊杰.基于信标节点RSSI自校正的WSN 的三维定位［J］.华中科技大学学报，2011，39（11）：347-350.

［9］张爱清，叶新荣，胡海峰，等.基于RSSI每跳分级和跳距修正的DV-Hop改进算法［J］.仪器仪表学报，2012，33（11）：2553-2559.