无线传感器网络(WSN)技术是物联网(Internet of Things，IoT)派生出的一个重要分支，有着良好的发展前景。近年来，WSN主要应用在国防和军事系统、智能电网、智能工业、精细农田、城市交通等方面^[1-2]。

WSN由许多价格低，体积小，功耗低，多功能的传感器节点通过一定的通信协议自行构成分布式网络，可感知、采集监测区域内用户所需的信息，在对数据信息分析处理后，最终以无线通信的方式将结果转发给用户^[3]。在WSN中，节点一般通过人工随机布设或飞机撒播的形式部署在监测区域中，实现信息的采集与感知。在感知和采集数据之前，必须知道事件发生的具体位置。因此，位置信息对于WSN的应用至关重要。目前，最常见的方法就是给传感器节点配备GPS模块获取位置信息，但GPS定位容易受外界环境的干扰，导致接收到的信号不准确或无法接收信号；且GPS模块体积大，定位过程中会消耗大量的能量。为此，科研专家采取了一种解决办法^[4]，给少部分传感器节点配置GPS模块获取相应的位置坐标，大部分节点的位置信息通过算法实现。因此，研究WSN中的节点定位算法是十分有必要的。

WSN定位技术分成两种：基于测距的定位和无需测距的定位^[5-6]。其中，测距的定位方法需要通过测量节点间的真实距离或利用方位角度进行定位，定位精确度较高，但需要提供硬件设备，大大增加了成本。无需测距定位算法根据网络连通性来定位，与前者相比，对硬件要求不高，成本低，功耗小，抗干扰性能好，实用性较强。据此，现常采用无需测距的定位方法进行定位，特别是距离矢量跳数(Distance Vector-Hop，DV-Hop)节点定位算法，实现方法简单，不需要提供硬件设备，所需节点比例较低，是WSN中应用最多的一种定位算法。针对DV-Hop算法存在的缺陷，国内外许多学者对其进行了改善和研究。文献[7]根据节点接收的RSSI值来决定节点间是否属于邻居关系，该算法虽然解决了跳数产生的误差，但RSSI阈值的确定存在一定的难度；文献[8]提出一种DV-Hop改进算法，该算法虽能减小定位误差，但多次通信增加了能量开销；文献[9]首先采用节点间多跳最短路径相似度因子修正节点的每跳平均距离，减小跳距引起的误差，其次使用改进的模拟退火(Simulated Annealing，SA)算法对节点初始位置进行优化，进一步提高定位精确度；文献[10]提出了一种跳距改进算法，这种方法虽能降低定位误差，但忽略了在计算待测节点与已知节点间距离时仍使用相同的平均跳距去估计其他节点间的距离，导致最后获得的待测节点坐标相当不准确。为了克服文献[10]算法存在的不足以及DV-Hop算法跳距引起的误差，本文首先通过加权系数加权原平均跳距，计算待测节点与已知节点间距离时不再使用相同的平均跳距估算；然后采用信标节点间距离产生的偏差值构造跳距校正系数，进一步校正跳距，在一定程度上解决跳距累积的误差；最后引入改进的AIA代替极大似然估计法优化待测节点坐标，将求解方程组问题转化为目标函数求最优解的问题，最优解即为待测节点坐标，从而获得更好的求解精确度。

1 DV-Hop定位算法及误差分析

DV-Hop定位方法由美国学者Dragos Niculescu等提出^[11-12]，是一种基于距离矢量路由思想的无需测距的定位算法^[13-14]，其基本原理是根据节点间距离的远近选择最佳路径进行定位。

1.1 DV-Hop定位算法的具体步骤

步骤1：在监测区域内信标节点通过泛洪技术将自身信息发送到网络中，其他节点接收。信息组成一个数据包，其结构为$\left\{ {I{D_i}, \left( {{x_i}, {y_i}} \right), Hopnu{m_i}, RSS{I_i}} \right\}$，其中初始跳数值为0。当其他节点收到此数据包时，ID标记用于确定该数据包之前是否已接收过，如果接收过，且跳数值小于当前接收的跳数值，则舍弃该数据包，保留最小跳数值，并将跳数值加1，再次转发于网络中。这样其他节点都会获得来自信标节点的最小跳数。

步骤2：利用式(1)计算信标节点的平均跳距，将计算得到的平均跳距作为校正值继续发送于网络中，当其他节点接收到该校正值时，就可以估算出未知节点与信标节点间的距离。

信标节点的平均跳距为：

$ Hopsiz{e_i} = \frac{{\sum\limits_{i \ne j} {\sqrt {{{({x_i} - {x_j})}^2} + {{({y_i} - {y_j})}^2}} } }}{{\sum\limits_{i \ne j} {Hopnu{m_{ij}}} }} $

(1)

式中：$\left( {{x_i}, {y_i}} \right)$, $({x_j}, {y_j})$分别为信标节点i与j的位置坐标；$Hopnu{m_{ij}}$为信标节点i与j间的最小跳数值。

未知节点与信标节点间的估计距离为：

$ d = Hopnu{m_{i'j'}} \times Hopsiz{e_i} $

(2)

式中$Hopnu{m_{i'j'}}$为未知节点与信标节点间的最小跳数值。

步骤3：只有待测节点至少能接收到3个信标节点时才能定位。定位节点的坐标一般可通过三边测量法、角度测量法或极大似然估计法估算得到。

1.2 DV-Hop定位算法的误差分析

1) 距离d估算不准确：在DV-Hop定位算法的第二阶段，计算未知节点与信标节点间距离d，如图 1所示，

A, B, C为已知节点，O为未知节点。由式(1)分别计算出$Hopsiz{e_A} = \frac{{{L_1} + {L_3}}}{{5 + 6}}$, $Hopsiz{e_B} = \frac{{{L_1} + {L_2}}}{{5 + 2}}$, $Hopsiz{e_C} = \frac{{{L_2} + {L_3}}}{{2 + 6}}$，并转发于网络中，未知节点O获取距离自身最近信标节点B的平均跳距Hopsize_B将其作为全网的平均跳距，估算出O与A间的距离为d_A=3×Hopsize_B；O与B间的距离为d_B=2×Hopsize_B；O与C间的距离为d_C=3×Hopsize_B。在这个过程中，使用了同一个平均跳距值去估算待测节点与其他已知节点间的距离，必然会造成很大误差。

2) 待测节点位置坐标计算方法不合理：在计算待测节点坐标时，常利用三边测量法、角度测量法或极大似然估计法构建方程组，最终以矩阵的形式表示节点坐标。以极大似然估计法为例，假如在监测区域中未知节点能接收到m个信标节点，其坐标分别是(x₁, y₁), (x₂, y₂), …, (x_m, y_m)，未知节点(x, y)到信标节点间的距离分别为d₁, d₂, …, d_m。由两点间距离公式可得：

$ \left\{ {\begin{array}{*{20}{c}} {\sqrt {{{\left( {x - {x_1}} \right)}^2} + {{\left( {y - {y_1}} \right)}^2}} = {d_1}}\\ {\sqrt {{{\left( {x - {x_2}} \right)}^2} + {{\left( {y - {y_2}} \right)}^2}} = {d_2}}\\ \vdots \\ {\sqrt {{{\left( {x - {x_m}} \right)}^2} + {{\left( {y - {y_m}} \right)}^2}} = {d_m}} \end{array}} \right. $

(3)

变换式(3)，以矩阵AX=a的形式表示，其中A, a如(4)~(5)所示。

$ \mathit{\boldsymbol{A}} = 2 \times \left[ {\begin{array}{*{20}{c}} {\left( {{x_1} - {x_m}} \right)}&{\left( {{y_1} - {y_m}} \right)}\\ \vdots & \vdots \\ {\left( {{x_{m - 1}} - {x_m}} \right)}&{\left( {{y_{m - 1}} - {y_m}} \right)} \end{array}} \right] $

(4)

$ \mathit{\boldsymbol{a}} = \left[ {\begin{array}{*{20}{c}} {{x_1}^2 - {x_m}^2 + {y_1}^2 - {y_m}^2 + {d_m}^2 - {d_1}^2}\\ \vdots \\ {{x_{m - 1}}^2 - {x_m}^2 + {y_{m - 1}}^2 - {y_m}^2 + {d_m}^2 - {d_{m - 1}}^2} \end{array}} \right] $

(5)

最终未知节点坐标(x, y)可表示为：

$ \mathit{\boldsymbol{\hat X}} = \left[ {\begin{array}{*{20}{c}} x\\ y \end{array}} \right] = {\left( {{\mathit{\boldsymbol{A}}^T}\mathit{\boldsymbol{A}}} \right)^{ - 1}}{\mathit{\boldsymbol{A}}^T}\mathit{\boldsymbol{a}} $

(6)

从式中不难看出，矩阵A与a所产生的误差会严重影响待测节点位置坐标的准确性，式中A的误差主要来源于信标节点坐标获取时由硬件设备(如GPS或实际测量等)引起的，这种误差一般无法避免；矩阵a的误差主要是距离估计时的估算误差，该误差可以降低。但采用这种方法在求解待测节点坐标时，2种误差累积会使定位误差越来越大；而且，在求解$\mathit{\boldsymbol{\hat X}} = {\left( {{\mathit{\boldsymbol{A}}^T}\mathit{\boldsymbol{A}}} \right)^{ - 1}}{\mathit{\boldsymbol{A}}^T}\mathit{\boldsymbol{a}}$时，矩阵A^TA可能会存在不可逆的情况，导致最终无法获取待测节点坐标。此外，如果网络中信标节点数量较少时，利用极大似然估计法得到的待测节点坐标会存在较大误差。因此，选择合适的位置坐标计算方法对DV-Hop算法定位精确度的提高非常重要。

2 本文改进算法 2.1 加权校正平均跳距

由于网络中的传感器节点随机分布，因此各节点间的跳段距离不均匀，网络中各处的平均跳距信息都不相同，如果使用相同平均跳距(将靠未知节点最近信标节点的平均跳距作为整个网络的平均跳距信息)去估算待测节点与信标节点间距离，计算出的节点坐标会存在一定的误差，影响定位精确度。为此，本文融入加权思想，对网络中所有信标节点的跳距信息配以相应的权值，使距离较远和较近的信标节点带来的误差影响相同，这样能充分体现出不同信标节点对定位节点的影响。若定位节点距离信标节点较近，利用对应跳数的倒数构造加权系数，对平均跳距赋予较大的权值；同理，若节点间距离较远，则赋予较小的权值加权平均跳距。因此，通过加权能使网络中的平均每跳距离更接近真实值，达到减小定位误差的效果。式(7)为加权系数λ_i：

$ {\lambda _i}{\rm{ = }}\left( {1/{H_i}} \right)/\sum\limits_{i = 1}^m {\frac{1}{{{H_i}}}} $

(7)

式中：H_i表示定位节点与信标节点间的跳数；m为定位节点能接收到信标节点的个数。

根据式(8)求出加权后的平均跳距为：

$ Hopsiz{e_i}^\prime = \sum\limits_{i = 1}^m {{\lambda _i} \times Hopsiz{e_i}} $

(8)

在计算待测节点与信标节点间距离时，会涉及到信标节点平均跳距的计算，如果把信标节点的估计距离看成真实距离，必定会造成很大误差。因此采用信标节点间距离引起的偏差值得到一个跳距校正值，进一步修正跳距，跳距校正系数为：

$ {C_i} = \frac{{\sum\limits_{i \ne j} {\left[ {\left( {{d_t} - {d_e}} \right)/Hopnu{m_{ij}}} \right]} }}{m} $

(9)

式中：${d_t} = \sqrt {{{({x_i} - {x_j})}^2} + {{({y_i} - {y_j})}^2}} $为信标节点的真实距离；${d_e} = Hopsiz{e_i}^\prime \times Hopnu{m_{ij}}$为信标节点的估计距离。将式(9)求得的跳距校正系数求和后，对所有参与定位的信标节点取平均值，再与加权平均跳距值相加，得到最后的全网平均每跳距离为：

$ Hopsiz{e_{final}} = Hopsiz{e_i}^\prime + \sum\limits_{i = 1}^m {{C_i}} /m $

(10)

2.2 改进的AIA优化待测节点坐标

人工免疫算法由Farmer等在1986年率先提出^[15-17]，他将免疫概念应用到工程领域中，探讨了免疫系统与人工智能(Artificial Intelligence，AI)之间的关系，并开始对AIA进行深入研究。AIA模仿了生物领域免疫系统中抗原和抗体增殖的原理，是将生物免疫中的抗原和抗体进行抽象化的一种智能优化算法。其基本思想是：抗原识别，产生抗体，亲和度判断抗体和抗原的相似程度，通过抗体的繁殖、分化、克隆选择和变异等一系列操作，达到高亲和度的抗体不断进行繁殖寻优的过程。

AIA优化过程中遇到的重要免疫算子基本定义以及计算方法：

1) 抗体与抗原的亲和度。在免疫优化算法中，通常用亲和度函数描述抗体与抗原之间的相似度(即可行解与目标函数最终解的接近程度，评价可行解的质量)，一般通过目标函数特性建立适当的亲和度函数，用Aff_i表示：

$ Af{f_i} = f\left( {{F_i}} \right) $

(11)

式中F_i为根据实际问题确定的目标函数。Aff_i值越大，说明抗体与抗原越接近，即所求解与最优解越匹配。

2) 抗体浓度。抗体浓度指抗体在所有种群中所占的分量，能充分体现出抗体种群多样性的大小，是免疫优化中的另一个重要算子，记为D_i。由文献[18]可知，假设将每个抗体根据亲和度值由小到大排序划分成n等分，其中n=1, 2, …, n，各个等分区间上的抗体总数记为Sum(n)，则抗体浓度为：

$ {D_i} = \frac{{Sum\left( n \right)}}{n} $

(12)

从式中可以看出，亲和度越高的抗体，浓度反而越低，被进化的机会越大。

3) 免疫选择概率的计算。选择概率是AIA优化过程中促进高亲和度抗体进化、抵制低亲和度抗体繁殖的概率，其作用是提高抗体种群的多样性。根据文献[18]，假设亲和度的选择概率为${P_{{A_i}}} = Af{f_i}{\rm{ /}}\sum\limits_{i = 1}^n {Af{f_i}} $，抗体浓度的选择概率为${P_{{D_i}}} = 1 - \left( {{D_i}{\rm{ /}}\sum\limits_{i = 1}^n {{D_i}} } \right)$，则整个过程中被选中的概率P_i为：

$ {P_i} = \beta {P_{{A_i}}} + \left( {1 - \beta } \right){P_{{D_i}}} $

(13)

式中β$\left( {0.5 < \beta < 1} \right)$为免疫调节因子，调节${P_{{A_i}}}$和${P_{{D_i}}}$的权重，且${P_{{A_i}}}, {P_{{D_i}}} \in \left( {0, 1} \right)$。可以看出，亲和度高、浓度低的抗体被选择进化的几率较大。整个过程中，不但能充分保持抗体的多样性，而且还能提高算法全局搜索最优解的能力。

4) 免疫克隆操作。通过文献[19]可知，在AIA中克隆是通过亲和度大小对抗体进行复制，得到更多优质种群的过程。如式(14)所示：

$ {G_i} = INT\left( {\frac{S}{{X{I_i}}}} \right) $

(14)

式中：G_i为克隆的抗体数；INT()表示取整函数；S为种群数目，$X{I_i}\left( {X{I_i} = 1, 2, \cdots } \right)$表示抗体根据亲和度值从大到小排列的序号数。可以看出，抗体亲和度越大，克隆的数目越多；亲和度越小的抗体，克隆的数目越少。

由于AIA具有保持多样性好、记忆学习能力强、搜索效率高和鲁棒性等优点，因此广泛用于各大科研领域中，如故障诊断、智能优化、数据挖掘、路径规划、模式识别、计算机安全等^[20]。在优化问题中，AIA具有重要的研究价值，但直接将AIA应用在DV-Hop算法待测节点坐标优化方案中，则会存在易陷入局部最优，而并非全局最优以及算法寻优时间过长的问题，影响DV-Hop定位结果。据此，本文对AIA进行改进，在局部搜索过程中采用高斯变异的方式，因为高斯分布(正态分布)具有集中性、对称性强的特点，当抗体基因发生突变时，通过高斯变异的相关参数使抗体在局部范围内进行扰动，扩大解的搜索范围，找到更多更好的抗体，将最优解作为待测节点坐标。改进后的AIA与原始AIA相比，不仅可以跳出局部最优解，而且还能加快算法收敛速度，使DV-Hop算法获得更好的定位性能。

利用式(15)得到高斯变异后的新抗体为：

$ g' = g + k \times N\left( {0, 1} \right) $

(15)

$ k = \frac{1}{\eta }{e^{ - Af{f_i}}} $

(16)

式中：g为抗体基因；$g'$为高斯变异后的抗体基因；k为扰动算子；η$\left( {\eta > 0} \right)$为控制亲和度Aff_i的衰减因子。

改进AIA优化DV-Hop节点定位算法的具体步骤为：

步骤1：初始化网络，获取最小跳数信息。

步骤2：利用式(7)~(10)，计算加权校正平均跳距，并计算节点间的距离。

步骤3：构建合适的目标函数，将其看作抗原。根据定位节点与信标节点间的距离公式可得目标函数为：

$ {F_i} = \frac{1}{m}\sum\limits_{i = 1}^m {\left( {\sqrt {{{\left( {x - {x_i}} \right)}^2} + {{\left( {y - {y_i}} \right)}^2}} - {d_i}} \right)} $

(17)

式中：d_i表示定位节点到信标节点的估计距离；$m\left( {m \ge 3} \right)$为定位节点能接收到信标节点的个数。

步骤4：根据抗原随机生成相应的抗体，即目标函数的可行解，以解空间的形式表示。

步骤5：根据目标函数F_i建立合适的亲和度函数，如式(18)所示，α为(0, 1)上的常数。

$ Af{f_i} = \frac{1}{{1 + {e^{\alpha {F_i}}}}} $

(18)

若Aff_i值越大，则抗体与抗原越接近，同时将每次计算出的亲和度大的抗体通过记忆细胞留存下来，便于记忆单元更新，直到亲和度的值不再发生变化，说明此时的亲和度值最大，满足这个条件迭代终止，输出结果。

步骤6：利用式(12)计算抗体浓度。

步骤7：免疫选择操作，利用式(13)计算选择概率。

步骤8：通过式(14)对上述进化的抗体克隆，得到更多高亲和度的种群。

步骤9：利用式(15)和式(16)对原始AIA改进，扩大搜索范围，找到更好的抗体。

步骤10：通过克隆抑制对上述变异后的抗体再次选择，抑制浓度高、亲和度低的抗体繁殖。

步骤11：更新种群，利用高亲和度、低浓度的抗体代替低亲和度、高浓度的抗体，产生新的抗体。最后，返回步骤5再次判断，如果满足终止条件，则输出全局最优解，目标函数所求解即为定位节点坐标；否则，继续寻优判断。

3 实验仿真结果及分析 3.1 仿真环境

本文通过Matlab仿真平台对改进后的DV-Hop定位算法和原DV-Hop算法在节点总数、信标节点比例以及通信半径三方面分别进行仿真实验对比。仿真环境及相关参数设置如表 1所示。

将平均定位误差作为算法定位精确度的衡量准则，平均定位误差如式(19)所示。

$ Erro{r_{ave}} = \frac{{\sum\limits_{i = 1}^K {\sum\limits_{j = 1}^M {\frac{{\sqrt {{{\left( {{x_t} - {x_e}} \right)}^2} + {{\left( {{y_t} - {y_e}} \right)}^2}} }}{R}} } }}{{KM}} $

(19)

式中：$\left( {{x_t}, {y_t}} \right)$为未知节点的真实坐标；$\left( {{x_e}, {y_e}} \right)$为未知节点的估计坐标；M表示未知节点的数量。

3.2 仿真分析

1) 不同节点数目下各算法定位性能的对比分析。如图 2所示，在其他因素都不变的情况下，节点总数在[50, 400]之间变化时，各算法的平均定位误差一直减小且趋于平缓。从图中可以清楚地看出，本文跳距改进后的算法平均定位误差低于文献[10]提出的算法，定位精确度明显有所提升。在节点总数超过300时，各算法的平均定位误差基本保持不变。这是因为，随着节点数量的增加，节点间相互通信的竞争和通信开销也随着增加，影响了定位结果，此刻增加节点数目不能再降低定位误差。当节点总数为200时，本文跳距改进后的算法与文献[10]改进算法相比，平均定位误差减小了5.5%，与原DV-Hop算法对比，平均定位误差降低了8.2%；原始AIA优化后的算法和改进AIA优化后的算法与原DV-Hop算法相比，平均定位误差分别减小了12.4%和15.7%。

2) 网络中随机分布不同数量的信标节点时各算法平均定位误差的对比分析。假设传感器节点总数为100，节点通信半径R=30 m，信标节点分别取5, 10, 15, 20, 25, 30时，各算法的平均定位误差变化如图 3所示。由图可看出，随着信标节点数的增加，各算法的平均定位误差均减小，当信标节点数超过20时，平均定位误差保持稳定。这是因为，当网络中信标节点数增加时，信标节点的平均跳距计算误差减小，进一步减小了待测节点与信标节点间距离的估计误差，定位精确度提高。但不能一直增加信标节点数目，因为信标节点数增加的同时，定位成本也相应增加了，会对未知节点的定位产生一定的影响。当信标节点为15时，本文改进算法较文献[10]算法平均定位误差降低了6.5%，较原DV-Hop算法平均定位误差降低了9.7%；与原DV-Hop定位算法相比，在跳距改进的基础上，通过原始AIA优化后的定位算法与改进AIA优化后的定位算法平均定位误差分别减小了11.6%, 14.1%。由此可见，相比于原DV-Hop定位算法，改进后的算法在定位精确度方面有很大提升。

3) 不同通信半径下对各算法定位性能的分析。传感器节点总数为100，信标节点数为25，其他参数不变，通信半径取20 m, 25 m, 30 m, 35 m, 40 m, 45 m, 50 m时，平均定位误差变化情况如图 4所示。各算法的平均定位误差随着通信半径的不断增加而减小，当节点通信半径大于40 m时，平均定位误差基本趋于平缓。节点通信半径增加，网络连通度变好，节点间的路径选择减少，跳数和跳距的计算误差就会减小，定位精确度提高。但通信半径的增加，使节点通信能量开销也随之增大，定位不佳。从图中可以看出，当节点通信半径为35 m时，本文改进算法的定位性能明显优于文献[10]算法，平均定位误差减小4.3%，相比于原DV-Hop定位算法，平均定位误差减小9.1%，定位精确度有明显提高。在跳距改进的基础上，引入免疫优化，算法的定位精确度进一步提升，与传统DV-Hop算法相比，原始AIA优化后的算法平均定位误差降低了13.6%；改进AIA优化后的算法平均定位误差降低了16.1%。由此可见，改进后的算法有着良好的定位性能。

4) 算法收敛性能对比。假如种群数量S=40，免疫调节因子β=0.75，实验迭代次数τ增大到80次时，定位误差变化以及算法收敛情况如图 5所示。从图中可以看出，通过高斯变异改进的AIA与原始AIA相比，算法收敛速度有明显提升。改进AIA在第20次实验之后，定位误差已保持不变，此时收敛速度趋于平稳状态；而原始AIA的收敛速度在第50次实验时才达到平稳，说明改进的AIA能明显缩短算法的寻优时间，加快算法收敛速度，有着良好的定位稳定性。在第30次迭代时，改进AIA优化DV-Hop算法的定位误差达到22.2%，而原始AIA优化DV-Hop算法的定位误差为23.9%，定位误差减小了1.7%，因此，改进AIA不但能提高算法收敛速度，而且还能降低定位误差。由此可见，改进AIA在算法稳定性方面明显优于原始AIA，同时能使DV-Hop定位算法获得更好的定位精确度。

4 结论

为解决传统DV-Hop节点定位算法在计算待测节点与信标节点间距离时存在的误差以及未知节点坐标计算方法不合理问题，提出了一种改进的DV-Hop算法。在计算信标节点平均跳距时，融入加权思想，通过节点间的跳数构造加权系数对原平均跳距进行加权处理，避免了使用相同平均跳距去估算节点间距离；利用信标节点间距离产生的偏差，建立跳距校正值得到最终的平均跳距；最后在跳距改进的基础上，利用改进的AIA优化待测节点坐标，通过高斯变异算法扩大解的搜索范围，获得更优的解。仿真实验表明，本文跳距改进后的算法定位精确度明显优于文献[10]提出的算法；改进后的算法与传统DV-Hop定位算法相比，从不同角度降低了定位误差，获得了更好的定位精确度，同时，算法的收敛性能也明显提升，有着良好的定位稳定性。由于在亲和度判断过程中需要选取最佳解，因此增加了一定的计算复杂度，在定位精确度不变的前提下，如何减少计算量是下一步需要研究的重要内容。