一种基于FCM的DV-HOP定位算法

孙爱晶,李益佳

(西安邮电大学 通信与信息工程学院,陕西 西安 710121)

无线传感器网络(Wireless Sensor Network,WSN)现在已经广泛应用于各个领域。在WSN中,传感器节点对覆盖范围内的对象进行信息的采集和传播[1-2]。如果传感器节点的位置不明确,得到的信息价值将会降低。因此,WSN中节点的定位问题尤为重要,其中距离矢量跳数定位[3](Distance Vector Hop,DV-HOP)算法因其成本低、且易于部署等优点得到广泛应用,但DV-HOP算法定位误差较大。

很多研究者对DV-HOP定位算法进行了相关改进以减小定位误差。文献[4]通过对数据分组结构的改进降低了平均每跳距离的误差,但该方法容易受节点分布的影响。文献[5]通过多通信半径广播锚节点位置信息,并结合节点远近度修正待定位节点与锚节点的测距值减小定位误差,但该方法需要较高的锚节点密度。文献[6]利用机器学习中极限学习机计算未知节点的位置,训练的数据只能适用于当前部署的定位环境且需要大量的锚节点。文献[7]在未知节点定位之前对锚节点进行安全检测以减少定位干扰,并没有充分利用锚节点的信息。

大多数的改进算法都是以节点部署较为均匀为前提,通过各种方法降低定位误差。但是,在实际应用中,定位区域内节点的分布受环境、地形及气候等因素的影响,往往是不均匀的。为了降低DV-HOP算法在锚节点密度低且节点分布不均匀的定位环境下的定位误差,拟提出一种用模糊C-均值算法(Fuzzy C-Means,FCM)改进的DV-HOP定位算法。该算法提出了相似度与关联度的概念,通过FCM算法对锚节点进行分簇并提出了分簇策略,未知节点根据所提入簇策略进行簇内定位,然后进行簇间坐标的融合以实现全局定位。最后,将所提算法与DV-HOP定位算法、基于粒子群改进的DV-HOP[8](DV-HOP for Particle Swarm Optimization,PSODV-HOP)定位算法以及基于几何改进的DV-HOP[9](Improved DV-HOP,IDV-HOP)定位算法进行了定位误差的对比仿真实验,从而验证所提算法的有效性。

1 基本问题描述

目前的定位算法根据是否基于测距分为基于测距的定位算法与无需测距的定位算法[10]。基于测距的定位算法包括接收信号强度指示 (Receiver Signal Strength Indicator,RSSI)、到达时间差[11](Time Difference of Arrival,TDOA)及到达角度[12]( Angle of Arrival,AOA)等算法。与距离有关的定位算法通常需要额外的硬件进行信号参数的测量,因而成本高且不适宜大面积部署。无需测距的定位算法包括DV-HOP定位算法[4]、多维定标(Multidimen-Sional Scaling,MDS)算法[13]及质心定位算法[14]等。在无需测距的定位算法中,通常给少量的节点配备全球定位系统(Global Positioning System,GPS)使之成为位置已知的锚节点。然后未知节点根据其与锚节点之间的位置关系与拓扑关系计算自身位置,因此无需测距的定位算法成本低且适合大规模的WSN部署应用。其中,DV-HOP定位算法因实施简单且易于扩充等优点而受到关注。

DV-HOP定位算法容易受到锚节点数目以及节点分布的影响,导致平均跳距与最小跳数有较大的误差,从而在后续的计算中造成较大的定位误差。在实际应用中因环境等因素出现网络中的节点分布不均匀的情况,会进一步加剧网络中平均跳距与最小跳数的误差。为了改善在节点分布不均匀环境下定位误差较大的问题,在现有研究的基础上,提出在DV-HOP定位算法的基础上引入FCM对节点进行分簇定位的算法。所提算法在分簇阶段使用FCM算法对锚节点进行分簇,为了防止分簇后簇内锚节点数目不能满足定位的需求,提出了与相似度相关的分簇策略,而未知节点则根据与各簇锚节点的关联度进行入簇定位,以期通过所提算法中分簇定位的思想减少节点分布不均匀对平均跳距和最小跳数影响,进而降低定位误差。

2 DV-HOP定位算法原理及误差分析

2.1 DV-HOP定位算法原理

DV-HOP定位算法是由D.Niculescu和B.Nath提出的基于分布式无需测距原理的定位算法[15],类似于传统网络中的距离向量路由机制。假设在定位环境中有n个锚节点、m个未知节点(n≥3且m≫n)。一个未知节点至少要与3个锚节点产生距离关系才能建立可解方程组求解其位置。因此,n≥3是必要条件。而m≫n是要确保通过少量锚节点定位未知节点,从而保证算法实际应用上的合理性。

DV-HOP定位算法在定位时,首先计算节点之间的最小跳数,然后计算锚节点平均每跳的距离,利用最小跳数与平均跳距估算未知节点与锚节点之间的距离,最后用最小二乘法计算未知节点的坐标。DV-HOP定位算法具体包括计算节点间的最小跳数、计算锚节点的平均跳距、计算未知节点到锚节点的距离和最小二乘法计算未知节点的坐标等4个步骤。

步骤1计算节点间的最小跳数。首先,锚节点通过泛洪广播的方式向网络中的邻居节点发送数据包。数据包中包括节点的位置信息和跳数初始值,即初始跳数设为0跳。节点每收到一个数据包,都会将跳值增加1,并将数据保存在其位置信息表中。然后,该节点会将跳值增加的数据包转发到其邻居节点,并丢弃来自同一节点的跳值更大的数据包。从节点的位置信息表可以得到节点之间的最小跳数。

步骤2计算锚节点的平均跳距。得到节点之间的最小跳数之后,锚节点用接收到的其他锚节点的位置数据和最小跳数计算该锚节点的平均跳距,其表达式为

(1)

式中：(xi,yi)与(xj,yj)分别表示锚节点i与锚节点j的坐标;hij表示锚节点i与锚节点j之间的最小跳数。此时,得到每个锚节点的平均跳距。

步骤3计算未知节点到锚节点的距离。当锚节点向网络发送其平均跳距时,未知节点在第一次接收到锚节点的平均跳距之后,用该锚节点的平均跳距计算从未知节点到各个锚节点的直线距离,即未知节点u到锚节点i之间的计算距离,其表达式为

dui=Sihui

(2)

式中,hui表示未知节点u到锚节点i的跳数。

步骤4最小二乘法计算未知节点的坐标,其原理是通过各个锚节点到未知节点的距离计算出未知节点的坐标。在DV-HOP定位算法中,所有的锚节点都参与未知节点的定位,未知节点按照式(2)计算到各个锚节点的距离并与锚节点建立距离方程组,其表达式为

(3)

式中：(x1,y1),(x1,y1),…,(xn,yn)分别表示n个锚节点的坐标;(xu,yu)表示未知节点u的坐标。

用最小二乘法对式(3)的方程组进行求解,将式(3)的前(n-1)个方程分别与第n方程进行线性变换后得到的线性矩阵为

AX=B

(4)

其中,

式中：A表示锚节点的信息矩阵;X表示未知节点的坐标矩阵;B表示锚节点的距离矩阵。

(5)

2.2 DV-HOP定位算法的误差分析

2.2.1 锚节点对DV-HOP定位算法的影响

DV-HOP定位算法通常使用定位环境内的所有锚节点参与未知节点的定位,具体的锚节点对DV-HOP定位算法的影响如图1所示,图1中的圆点为未知节点,五角星为锚节点。

图1 锚节点对DV-HOP算法的影响

图1中DV-HOP定位算法会用全部的4个锚节点定位未知节点,但锚节点a距离未知节点较远,此时盲目地使用所有锚节点会带来较大的定位误差。因此,在定位未知节点时要根据锚节点与未知节点的关系有选择地使用锚节点。考虑对锚节点按照距离关系进行分簇,将圆内的锚节点分为一簇。未知节点进入该簇定位,避免了锚节点a带来的定位误差。因此,采用分簇锚节点的方法对锚节点进行选择,可以避免DV-HOP定位算法中盲目使用所有锚节点带来的定位误差。

2.2.2 节点分布对DV-HOP定位算法的影响

通常在DV-HOP定位算法应用的定位环境中,将节点的分布默认为是一种较为均匀的分布,节点分布较均匀的定位环境如图2所示,定位环境内无较大的无节点空白区域。但是,受地形、气候及气候等因素的影响,部署节点时节点的分布有可能是不均匀的。当与图2同样数目的节点分布不均匀时,节点分布不均匀定位环境如图3所示,定位环境内出现较大的无节点空白区域。所提算法大都是在节点分布较均匀的定位环境情况下提出的,在节点分布不均匀定位环境中定位效果往往不太好。因此,所提算法能更好地适应节点分布不均匀的定位环境。

图2 节点分布较均匀的定位环境

图3 节点分布不均匀定位环境

由图2和图3可以看出,在图2较为均匀的定位环境中,锚节点a1到未知节点u1的跳数为4跳。在图3中由于节点的不均匀分布,在定位环环境内存在大块无节点的空白区域,此时用最小跳数与平均跳距得到的距离会出现严重的误差。当节点分布不均匀时,由于空白区域的影响产生了多余的曲折路径,此时锚节点a1到未知节点u1的跳数为8跳,而实际上两点之间的距离并没有这么大。在节点分布不均匀的环境下与分布较为均匀的环境下跳数相差4跳,此时根据式(2)得到的估算距离误差很大,从而导致存在较大的定位误差。

3 FCM算法

为了避免所有的锚节点参与定位带来的定位误差,考虑引入FCM算法[16]对DV-HOP算法进行改进,即根据距离分簇锚节点实现对未知节点的分簇定位。FCM算法是基于划分聚类的算法,广泛应用于图像分割中。FCM的思想是使得被划分到同一簇的对象之间尽可能相似,而不同簇之间的差异尽可能大。在无线传感器网络中可以表现为节点对某一聚类中心的隶属度是模糊的,隶属度可以表示为

(6)

式中：pij表示节点i对聚类中心j的隶属度;q表示聚类的数目。点i对所有的聚类中心的隶属度总和为1。

如果存在n个锚节点被随机分布在定位环境内,网络的聚类中心数为q。此时,FCM算法可以通过将目标函数最小化,使得整个网络的锚节点按地理相似度分为q类,则FCM算法的目标函数为

(7)

式中：∂为模糊系数;dij为第个i锚节点与第j个聚类中心的欧氏距离。

隶属度pij可以表示为

(8)

式中,dik为第个i锚节点与第k个聚类中心的欧氏距离。

聚类中心cj可以表示为

(9)

式中,xj表示第j个锚节点。

当迭代停止时,输出锚节点的聚类结果。此时,FCM算法对锚节点进行分簇之后,就会把分布最紧密的锚节点分为一簇。

4 基于FCM的DV-HOP定位算法

所提算法在DV-HOP算法的基础上引入FCM算法进行分簇定位,并定义了相似度与关联度,提出锚节点的分簇策略与未知节点的入簇策略。

4.1 锚节点分簇策略

DV-HOP算法在网络中广播得到节点之间的最小跳数和平均跳距之后,引入FCM算法将位置已知的锚节点按照节点之间的距离分簇。

假设将定位环境中的n个锚节点分为l簇,r1为第一簇,r1内的所有锚节点数为a。一般l的取值根据网络中的锚节点数及其分布情况进行设定。考虑到实际情况,l取值不应过大,在仿真环境中经过验证,将l设为3是比较合理的。此外,还要保证每一个簇内的锚节点数不少于3,才能与未知节点建立可解方程组(3)求解未知节点的坐标。如果簇内的锚节点数目大于等于3,那么该簇可以进行簇内定位;如果簇内锚节点的数目小于3,那么要将与该簇相似度最小的非本簇锚节点依次纳入该簇,直到该簇的锚节点数目大于等于3。

定义锚节点的相似度为D,若r1内的锚节点数小于3,对r1进行非本簇锚节点的入簇,则第j个不属于r1簇的锚节点对r1的相似度的表达式为

(10)

当Djr1值越大,说明锚节点j与r1簇的距离就越大,值越小则说明锚节点j与r1簇的距离越小。

每次选择相似度最小的锚节点,才能使得入簇之后的锚节点与簇内原本的锚节点距离最小。分簇锚节点减小了传统算法中使用全部的锚节点参与定位带来的定位误差。

4.2 未知节点入簇策略

将锚节点分簇且保证每一个簇都满足定位要求之后,未知节点根据关联度进行入簇定位。

假设此时r1簇内的锚节点为b(b≥3),未知节点的关联度为H。此时未知节点u对r1簇的关联度的表达式为

(11)

式中,hui表示未知节点u与锚节点i之间的跳数。关联度Hur1值越大,说明锚节点i与r1簇的跳数越大;关联度Hur1值越小,则说明锚节点i与r1簇的跳数越小。

考虑跳数的大小在一定程度上反映了距离的大小,因此要选择与簇r1关联度最小的未知节点入簇。此时,入簇之后的未知节点与该簇的跳数最小,从而降低了定位误差。

4.3 簇间坐标的整合

将定位环境中的n个锚节点分为l簇,若每一簇定位v个未知节点,则第l个簇求得的未知节点坐标信息为

(12)

将l个簇的未知节点坐标进行融合,得到的全局未知节点的坐标矩阵为

(13)

此时,经过FCM算法改进的DV-HOP定位算法完成定位环境内所有未知节点的定位。

4.4 改进算法流程

通过引入FCM算法对DV-HOP定位算法进行优化,设计了锚节点的分簇策略以及未知节点的入簇策略,得到了一种基于FCM算法的DV-HOP定位算法,其具体的流程如图4所示。基于FCM算法的DV-HOP定位算法是一种分簇定位的思想,其在DV-HOP定位算法中定义了相似度与关联度的概念并引入FCM算法制定了分簇策略与入簇策略。首先,通过FCM算法将所有的锚节点根据欧氏距离进行分簇。然后,锚节点根据分簇策略确保每一簇都能完成对未知节点的定位,而未知节点则通过入簇策略分别进入不同的锚节点簇进行定位。最后,各个簇进行簇间坐标的融合以实现全局未知节点的定位。所提算法将全局定位转化为分簇定位,增强了算法对节点分布的适应性。

图4 基于FCM的DV-HOP定位算法流程

5 实验与仿真

5.1 仿真环境

为了验证所提算法的有效性,在100 m×100 m的定位区域内,部署100个无线传感器节点,分别在节点分布较为均匀和节点分布不均匀的定位环境中进行两组实验。

对定位算法评价的指标是节点的平均定位误差e,其表达式为

(14)

5.2 仿真结果及分析

5.2.1 节点分布较为均匀的定位环境

在如图5所示的节点分布较为均匀的定位环境内,保持节点总数为100个、锚节点比例为8%及节点的通信半径为25.0 m。DV-HOP定位算法与所提算法分别对各个节点的定位误差进行仿真,各个节点定位误差仿真结果分别如图6和图7所示。

图5 节点较为均匀分布环境

图7 基于FCM的DV-HOP定位算法的节点定位误差

由图5、图6及图7可以看出：在节点分布较为均匀的定位环境下,DV-HOP定位算法各个节点的定位误差主要集中在20.0～60.0 m内,其平均定位误差为42.4 m;所提算法各个节点的定位误差主要集中在10.0～30.0 m内,而其平均定位误差为24.9 m。在节点分布较为均匀的稀疏锚节点定位环境中,所提算法的平均定位误差较DV-HOP定位算法降低41.2%,这说明提出的改进算法在稀疏锚节点且节点分布较为均匀的定位环境下有明显效果。

在图5所示的定位环境下保持节点总数为100个、节点的通信半径为25.0 m,将锚节点的密度依次设为5%、10%、15%、20%、25%、30%,分别对所提算法、DV-HOP定位算法、PSODV-HOP定位算法[15]与IDV-HOP定位算法[16]的平均定位误差进行仿真,具体的均匀分布下锚节点比例对平均定位误差的影响结果如图8所示。

图8 锚节点比例对平均定位误差的影响

由图8可以看出,所提算法、DV-HOP定位算法、PSODV-HOP定位算法以及IDV-HOP定位算法等4种算法在节点分布较为均匀环境下,当锚节点比例变化时平均定位误差的变化情况。由于锚节点数目越多和有效信息越多,平均定位误差越小,各种算法的平均定位误差均随着锚节点数目的增加而降低,因此平均定位误差均随着锚节点数目的增加而降低。当锚节点为5个时,DV-HOP定位算法的平均定位误差为51.2 m,PSODV-HOP定位算法的定位误差为43.3 m,IDV-HOP定位算法的定位误差为35.2 m,所提算法的平均定位误差为37.7 m。此时,所提算法的平均定位误差略高于IDV-HOP定位算法。当锚节点大于10个之后,所提算法的平均定位误差迅速下降并明显低于其他3种算法。由此可见,所提算法是有效的。

5.2.2 节点分布不均匀的定位环境

节点分布不均匀的定位环境即存在大块无节点的空白区域中保持节点总数为100个、锚节点比例为8%、节点通信半径为25.0 m,如图9所示。用DV-HOP定位算法与所提算法分别对各个节点的定位误差进行仿真,节点定位误差仿真结果分别如图10和图11所示。

图9 节点不均匀分布环境

图10 DV-HOP定位算法的节点定位误差

图11 基于FCM的DV-HOP定位算法的节点定位误差

由图9、图10和图11可以看出：在节点分不均匀的定位环境下,由于节点的不均匀分布且定位时未对锚节点进行选择,导致部分未知节点的定位误差较小,而大部分未知节点的定位误差较大,DV-HOP定位算法的平均定位误差为47.8 m;各个节点的定位误差主要集中在20.0 m附近,与DV-HOP定位算法相比,所提算法节点定位误差大于 40.0 m的节点显著减少,而其平均定位误差为20.5 m。所提算法与DV-HOP定位算法相比,平均定位误差降低57.1%,这说明所提算法在稀疏锚节点且节点分布不均匀定位环境下效果明显。

在图9所示的定位环境下保持节点总数为100个、节点的通信半径为25.0 m,将锚节点的密度依次设为5%、10%、15%、20%、25%、30%,分别对所提算法、DV-HOP定位算法、PSODV-HOP定位算法和IDV-HOP定位算法的平均定位误差进行仿真,不均匀分布下锚节点比例对平均定位误差的影响结果如图12所示。

图12 锚节点比例对平均定位误差的影响

由图12可以看出,所提算法、DV-HOP定位算法、PSODV-HOP定位算法以及IDV-HOP定位算法等4种算法在节点分布不均匀定位环境下当锚节点比例变化时的平均定位误差。当锚节点为20时,所提算法的平均定位误差与另外3种定位算法相比,分别降低52%、45%与31%。仿真结果表明,随着锚节点的比例增加,4种算法的平均定位误差都在逐渐降低,但在不均匀分布下的定位环境中,所提算法的定位误差显著低于其他的3种算法,这说明所提算法能够更好地适应不均匀的定位环境。

6 结语

针对DV-HOP定位算法在锚节点稀疏且未知节点分布不均匀的定位环境下存在的定位误差较大的问题,提出了基于FCM算法的DV-HOP算法。所提算法定义了锚节点的相似度与未知节点的关联度,并基于此提出了锚节点的分簇策略与未知节点的入簇策略。首先,引入FCM算法,对锚节点按照距离进行分簇后采用分簇策略,以减少所有锚节点参与定位所带来的定位误差。其次,未知节点根据入簇策略进行簇内定位,从而减少了未知节点分布不均匀带来的定位误差。最后,为了验证所提算法的有效性,将其与DV-HOP定位算法、PSODV-HOP定位算法及IDV-HOP定位算法等3种算法分别在节点分布较为均匀和节点分布不均匀的定位环境下进行对比。在节点分布较为均匀的定位环境下,当锚节点为5个时,所提算法的平均定位误差略高于IDV-HOP定位算法;当锚节点大于10个之后,所提算法平均定位误差迅速下降并明显低于其他3种算法。在节点分布不均匀的定位环境下,4种算法的平均定位误差虽然都在逐渐降低,但所提算法的定位误差显著低于其他3种算法。仿真结果表明,所提算法不仅有较低的定位误差,还能够更好地适应不均匀的节点分布环境。