基于模糊聚类的加权协作定位算法

汪子为，房亮

（延安大学 物理与电子信息学院,陕西延安 716000）

无线传感器网络被应用于许多领域，例如环境监控，医疗机构中的患者跟踪，军事行动和活动区域识别[1]。在上述应用场景中，无线传感器网络的大多数应用都需要通过传感器定位获取目标的位置信息，才能更好地了解该目标地区的情况，以便及时采取有效的措施和控制[2]。但是，当无线传感器被部署在偏远和恶劣的环境中时，其性能则会受到资源和传输的限制[3]，因此提高节点定位精度和网络效率成为无线传感器网络中的主要挑战。

无线传感器网络的定位技术一般可分为两种：基于测距的定位技术和无需测距的定位技术[4]。其中无需测距的技术只能进行粗略定位，无法满足高精度需求，而基于测距的技术虽然定位精度相对较高，但对软硬件同时也有更高的要求[5]。基于接收信号强度（Received Signal Strength Indication,RSSI）的测距技术是无线传感器网络定位中常用的测距方法之一，网络中每个节点之间的距离可由RSSI估算[6]。但是由于反射、多径传播等因素的影响，RSSI值可能会不准确，导致定位出现较大的误差。为了减小RSSI测距误差，研究人员进行了许多角度的尝试。Shen等[7]通过使用加权质心算法将RSSI测量值加权使定位更加精准。Hussein等[8]则将梯度下降算法应用于表示RSSI测距精度的目标函数中，达到减小误差的效果。Hongbo等[9]设计深度神经网络作为分类器，将定位问题建模为分类问题，在利用RSSI测距时辅以信道状态信息和基于定位的深度学习来提高定位精度，有效减小了定位误差。

与使用单个传感器相比，显而易见地，使用多个传感器作为参考节点汇集其数据可以提高信息的准确性。但这些传感器并非随意组合，参考节点的选择及数据的处理至关重要，因此许多研究者将聚类方法应用到节点选择中以提高定位精度。Nomura等[10]使用基于层次聚类的方法来选择属于不同簇的参考节点，通过考虑参考节点的位置偏差来缩小用于位置估计的信标节点，从而选出合适位置的信标节点来缩小定位误差。Guo等[11]提出一种自聚类的测量组合方法，使用通过双曲线定位算法获得的源位置估计用作聚类模式，调整单位RSSI值，以使估计的未知节点位置与实际位置之间的差异最小。Shi等[12]设计了一种新的基于k均值聚类的跟踪算法，将RSSI分为减少、正常和增加三类，借此选取更符合实时情况的参考节点，提高了定位精确性和稳定性。

上述工作在提高无线传感器网络中定位精度方面有一定的应用价值，然而，鲜有算法考虑定位目标分布广且彼此相距较远的场景。由于定位范围广、信标节点分布随机且稀疏，若直接令信标节点对未知节点进行定位，不仅开销庞大，RSSI测距信息还会受周围环境因素影响导致定位精度下降。为了弥补这一不足，本文提出基于模糊聚类的加权协作定位算法WCFC（Weighted collaborative positioning algorithm based on fuzzy clustering），针对信标节点分布稀疏的户外环境，将信标节点合理地划分成若干个簇，在各个簇中将被定位过的未知节点转化为信标节点进行协作定位，同时对RSSI值进行加权处理，尽可能地降低环境对定位精度的影响。

1 系统模型

WCFC算法具体应用于以下场景：在M*N的区域中，随机分布p个信标节点和q个未知节点，通信范围设为R。其中，信标节点配备GPS，可以获得自身和其他信标节点的位置信息。还可以接收到未知节点的RSSI信息，利用RSSI信息获取未知节点相对于信标节点的位置[13]。针对实际的应用环境，一般选取两种传播路径损耗模型：自由空间传播模型和对数正态分布模型[14]。自由空间传播模型一般用于发射端与接收端之间完全无阻挡的情况下，典型的应用是卫星通信系统和微波视距无线链路。对数正态分布模型一般用于节点发射的无线电信号在传播过程中受到多径、障碍物等环境影响的情况下，所以本文选用对数正态分布模型作为传播路径损耗模型来计算未知节点与锚节点之间的距离[15]：

其中，d是发送节点与接收节点之间的距离，RSSI是接收信号强度，P(d0)是在近地参考距离为d0（通常d0=1 m）时的接收信号强度，α是路径损耗因子，其值取决于特定的传播环境，λ是均值为0的高斯随机变量。信标节点与未知节点之间的距离d可以由式(1)计算。未知节点可以发送信号也可以接收到信标节点的信息。初始定位时，本文采用传统的三边定位算法[16]，见图1。

图1 三边定位模型图

2 WCFC算法

为了降低系统传输信号的开销和损耗，减小RSSI测距误差对定位精度的影响，加快定位收敛速度，WCFC算法将分布稀疏的信标节点按照一定的规则分簇，在簇内进行协作定位和数据处理，用三边定位算法将被定位的未知节点转化为信标节点，再对RSSI信息进行加权处理。该算法分为两个阶段：分簇和定位。

分簇阶段：在分簇算法的选择上，由于传感器距离远，可用的参数较少，通常用于定位的聚类算法为k-均值聚类算法和模糊聚类算法[17]。前者仅利用每个节点之间的距离进行聚类，但在聚类时，某一簇可能过于孤立，导致信标节点分布不均，定位误差过大。为了提高定位精度和资源分配的合理性，本文采用模糊聚类算法对信标节点进行聚类。WCFC算法的分簇可分为四个步骤：

步骤一：用模糊聚类算法对所有信标节点进行聚类。模糊聚类算法具体如下：

1）随机初始化集群成员值μij，目标函数

4)计算目标函数 Jm，重复 1）～4），直到 Jm的值小于指定的最小阈值或进行到预先设定的迭代次数。得到每个聚类的聚类中心cj和每簇信标节classi点。

步骤二：定义信标节点分簇规则。聚类过程中若该簇中只有两个信标节点，则该信标节点搜寻自己相邻的里面有三个以上信标节点的簇，然后将符合要求的相邻簇中距离该簇最近的信标节点纳入该簇范围。若只有两个信标节点的簇找不到符合要求的信标节点，或出现了只有一个信标节点的簇，则重复步骤一直到所有初始簇符合要求。

步骤三：将未知节点划分到对应的簇中。计算所有信标节点对于簇心的距离，再利用信标节点接收到的未知节点的RSSI信息估算通信范围内所有未知节点相对于簇心的距离，将距离簇心最远的未知节点的距离当作簇半径，并为该簇每一个未知节点打上唯一标记IDclassi。

步骤四：剔除簇中重复的未知节点。若该簇中的未知节点被标记了两个及两个以上的IDclassi，则该未知节点纳入距离其最近的一个簇。

定位阶段：在簇内进行基于RSSI优化的协作定位。利用三边定位算法对未知节点进行定位，未知节点只有能够接收到3个及以上信标节点的信息才有被定位的可能[18]。但是当未知节点距离初始信标节点非常远时，RSSI的测距信息因为环境影响误差会很大。基于此，本文提出一种协作定位算法，信标节点对远处未知节点的定位可以通过先定位近处的未知节点传递实现，这样系统不仅仅能够通过信标节点实现对未知节点的定位，还可以利用未知节点间的信息传输来完成所有节点的定位。系统内所有的节点功能相同，地位对等，每一个节点都可以参与未知节点的定位，从而能够实现对节点资源的充分利用，提高系统鲁棒性。

每次对未知节点进行定位时，选取距离该未知节点最近的三个信标节点，提高定位的效率。但是该信标节点可能是在协作定位时由未知节点转化过来的，本身位置信息存在误差，且可能不是信号强度最好的三个信标节点。为了弥补信号强度由于环境因素而对算法结果产生误差的缺陷，提高信号强度的完整性与准确率，算法引入RSSI优化机制，通过为RSSI值求得一个加权系数，用加权后的RSSI值代替原始RSSI值。具体步骤如下：

步骤一：设要被定位的未知节点为Ui(x0,y0)，该点选取的三个信标节点坐标为B1(x1,y1)、B2(x2,y2)、B3(x3,y3)，未知节点接收到的信号强度为RSSIi，求得平均值：

步骤二：对于来自三个信标节点的信号强度，如果RSSImean与RSSIi相差较大，给予一个相对小的权值，反之则给予一个相对大的权值。得到权重因子ki

步骤三：得到三个信标节点修正后的RSSIi′值：

步骤四：利用步骤三得到修正后的RSSIi′，对其余的未知节点进行定位。重复步骤一到步骤三，直到所有未知节点都被定位。

3 仿真实验

对所提出的WCFC算法进行仿真实验，并将所得的实验结果分别同Dv-hop[16]、三边定位及协作定位算法[19]进行对比。定位误差是由定位处的节点坐标和真实节点坐标之间的欧式距离[20]表示：

其中，(xM,yM)为定位处的节点坐标，(xT,yT)为真实节点坐标，d为两者之间的欧式距离。

在一定区域内随机稀疏部署信标节点和未知节点来模拟定位目标分布广且彼此相距较远的应用场景，然后使用WCFC算法对未知节点进行定位。图2展示了500×500 m2范围内，信标节点均匀分布30个，未知节点均匀分布200个，聚类数为5的分簇情况。

图2 信标节点聚类结果

图2中不同形状的较大节点代表不同簇中的信标节点，较小的黑色圆点代表未知节点。由图2可知分簇结果满足了定位要求，每个簇中至少包含三个信标节点，且各簇划分合理分布均匀，有利于下一阶段定位的进行。

在边长为500 m的区域范围内，设置初始信标节点个数为12个，未知节点200个，初始信标节点和未知节点均遵循均匀分布，将信标节点分为3簇，其定位情况如图3所示。

图3 协作定位算法与本文算法的对比

图3中横轴是信标节点数目，纵轴是定位误差，单位是m。从图3中可以看出，本文算法和只应用协作定位算法都呈现出信标节点数量越多，定位误差越小的结果。但是由于WCFC算法对RSSI进行了加权处理，因此相比于只应用协作定位算法，本文算法在不同信标节点数量上定位精度提高了10%～15%。

在边长为500 m的区域内，均匀分布200个未知节点，依次均匀分布15个、20个、25个信标节点，分别用WCFC、Dv-hop、三边定位及协作定位算法将未知节点分成4簇，其定位情况如图4所示。

图4 协作定位算法、Dv-hop算法和三边定位算法与本文算法的对比

图4中横轴是信标节点数目，纵轴是定位误差，单位是m。由图4中可以看出，将本文算法的定位误差与在等同条件下的三边定位算法，Dv-hop算法和协作算法相比较的情况下，当信标节点数目增加时，四种算法的定位误差都呈现减小的趋势，说明增多参与定位的信标节点可以减小定位误差。但是当信标节点数量相同时，本文算法误差最小，说明WCFC算法在对信标节点进行最优化分簇之后，增加了定位的有效信标节点数目，定位精度得到了有效提高。

4 结论

本文通过将聚类的思想与传统定位算法相结合，给出一种基于模糊聚类的加权协作定位算法，主要解决定位时信标节点分布稀疏的野外环境对RSSI测距的影响及定位收敛速度慢的问题。通过模糊聚类，先对信标节点进行划分，再在各个簇内进行基于RSSI加权处理的协作定位，不仅加快了定位的收敛速度，节省了系统能耗，还尽可能降低了由于距离、噪声等因素对RSSI测距信息的影响。由仿真结果可以看出，在信标节点足够多时，本文算法同Dv-hop和三边定位算法相比定位误差得到了很大程度地减小，但与没有引入RSSI权值信息的协作算法的定位精度相差不大，所以只适用于信标节点稀疏的情况。未来工作可考虑将本文算法应用在动态场景中进行测试，在未知节点运动状态下探索算法进一步优化的方法。