无线传感器网络(WSN)[1-3]融合了多种新科技，如智能感知技术、分布式信息处理技术．随着智能时代的到来，以及物联网和相关新技术突飞猛进的发展，WSN的研究进行的得如火如荼，在诸多领域得到广泛应用，例如健康医疗、预警监测、智能家居和矿山安全监测等[4-6]．而在使用过程中，数百个无线传感器节点总是被随机分布在待监测区域内，只有准确地得到这些未知节点的位置信息才能确保传感器监测信息的有效性．因此，无线传感器网络的节点定位技术十分重要．定位算法的常见分类有基于距离和非基于距离的定位算法[7-8]．前者结合节点间的距离信息再依据几何学知识获取未知节点的准确信息；后者根据网络中节点连通性解算未知节点的坐标信息．在非基于距离定位算法中，dv-hop[9-11]便是其中具有代表性的一种，由于其定位成本低廉且算法简单易实现的优点得到了众多研究者青睐．党宏社[12]提出了根据接收信号强度指示的比值修正dv-hop节点间跳数,再用加权质心算法进一步提升算法定位结果准确性，虽然该算法提升了定位算法性能，但未全面考虑dv-hop 算法产生定位误差的影响因子；高美凤[13]提出了结合遗传粒子群的 dv-hop定位算法，与初始算法相比定位精度得到了提高，但因为引入粒子群算法，所以算法的时间复杂度大幅度上升，同时也增加了时间和能量消耗；王磊[14]提出一种基于跳距修正，并且利用差分进化算法对节点坐标进行二次优化的算法，此方法在一定程度上减小了dv-hop算法的定位误差，但寻优效率有进一步的提升空间．Deepak Prashar[15]提出了一种新的基于距离误差修正的算法，以减小由基本跳数带来的误差，此方法对基本dv-hop和基于粒子群优化的dv-hop都有很好的优化效果，但计算过程繁琐且搜索效率较低．王国武[16]引入遗传算法和模拟退火算法对dv-hop平均跳距计算方式进行了改进，提高了节点定位精度，但未能兼顾改进优化算法的时间复杂度．惠海波[17]在WSN传统dv-hop定位算法的基础上，利用改进后的模拟退火算法计算信标节点的平均跳距，定位精度有一定提升，但优化算法能耗也随之增大．因此，这里提出了一种基于遗传模拟退火优化的dv-hop定位算法(DGSA，dv-hop location algorithm based on genetic simulated annealing)引入跳数调整因子有效控制节点间跳数信息，从而减小由于节点间跳数的不合理对定位结果造成的误差．先借助共线度，不让会对节点平均跳距产生较大误差的信标节点参与计算，再结合加权处理方式计算出最终节点平均跳距．此外将局部搜索能力优良的的模拟退火算法与遗传算法相结合形成混合算法，从而提升算法寻优效率和定位精度．1 dv-hop定位算法1.1　算法模型dv-hop算法的实现步骤主要分为以下3步．1.1.1　计算最小跳数传感器网络中所有信标节点遵循距离矢量协议，向通信范围内的邻居节点广播消息分组，其中包含自身的ID及跳数，接收到消息分组的节点保存最小跳数,并将自身跳数加1后，再继续转发，为避免节点储存冗余信息同时也为了提高算法定位结果准确性，所有的节点都只保留每一个信标节点的坐标和最小跳数参数．1.1.2　计算信标节点平均跳段距离每个信标节点利用第一个阶段结束后记录的到其他节点的坐标和最小跳数，可以由以下公式计算出自身平均跳距，Q=∑i≠j(xi-xj)2+(yi-yj)2/∑i≠jhij，(1)式中：(xi,yi)和(xj,yj)分别为信标节点i，j的坐标；hij为两节点间的最小跳数．然后再将包含平均跳距的数据广播到整个无线传感器网络．未知节点将最先接收到的平均跳距值作为自身平均跳距．1.1.3　计算未知节点坐标将第二阶段中的平均跳距，乘以最小跳数，便得到了未知节点与每个信标节点间的距离d．设未知节点坐标为(x,y)，信标节点坐标为(xi,yi) (i=1，2，…，n)，方程组为：(x1-x)2+(y1-y)2=d12;(x2-x)2+(y2-y)2=d22;⋮(xn-x)2+(yn-y)2=dn2. (2)由极大似然估计法可得方程组    x12-xn2-2(x1-xn)x+y12-yn2-2(y1-yn)y=d12-dn2;    x22-xn2-2(x2-xn)x+y22-yn2-2(y2-yn)y=d22-dn2;                              ⋮    xn-12-xn2-2(xn-1-xn)x+yn-12-yn2-2(yn-1-yn)y=dn-12-dn2, (3)将方程组(3)整理成矩阵形式AX=B可得        2(x1-xn)2(y1-yn)2(x2-xn)2(y2-yn)⋮2(xn-1-xn)2(yn-1-yn)xy=d12-dn2-x12+xn2-y12+yn2d22-dn2-x22+xn2-y22+yn2⋮dn-12-dn2-xn-12+xn2-yn-12+yn2. (4)通过最小二乘法，可得待确定位置的节点的坐标式为X=(ATA)-1ATB．1.2　误差分析1.2.1　跳数误差dv-hop定位算法流程如图1所示．dv-hop是通过节点间的通信来确定跳数，把信标节点通信范围内所有节点都记为1跳．如图2所示，A，B，C，D均为信标节点，虚线圆圈为节点A的通信范围．节点A，B之间的距离远远小于节点A，C之间的距离，但根据dv-hop第一阶段计算节点间跳数的原则，它们之间的跳数都是1跳．这种情况下采用dv-hop定位算法就会因为节点间跳数的不合理给定位结果带来较大误差．10.13245/j.hust.240066.F001图1dv-hop定位算法流程图10.13245/j.hust.240066.F002图2跳数误差示意图1.2.2　平均跳距误差因为平均跳距是借助信标节点的分布情况计算得到的，然而由于网络内部节点的分布一般都是不均匀的，即网络拓扑存在差异，所以在节点间跳数较多时，就会导致节点间的距离为折线如图3中实线部分所示，通常都会大于实际距离(图中虚线部分)．10.13245/j.hust.240066.F003图3平均跳距误差示意图2 遗传模拟退火优化的dv-hop定位算法2.1　dv-hop算法优化从上文可知，造成dv-hop定位算法定位精度不高的影响因素主要有两个：节点间跳数的不合理；平均跳距往往与实际情况相差较大．所以在对dv-hop算法提出优化时，可以从这两方面进行考虑，从而提升算法定位精度．2.1.1　跳数优化为减小节点间跳数对定位精度的影响，通过引入跳数调整因子对节点获得的原始跳数hij进行修正．跳数调整因子须要借助精确跳数和偏差系数获得．精确跳数为Hij=Dij/R，其中：R为通信半径；Dij为信标节点间实际距离．偏差系数为Mij=Hij-hij / hij．偏差系数Mij的值越大则说明dv-hop算法第一步估测出来的跳数值与节点间精确跳数值相差越大，也就是误差越大，为了减小误差，引入跳数调整因子对跳数信息进行修正，即cij=1-Mij2，修正之后的节点间跳数值为h¯ij=cijhij．2.1.2　平均跳距的改进为减小在传统dv-hop算法中节点平均跳距对定位精度的影响，本文首先引入共线度去除会对信标节点平均跳距产生较大误差的信标节点，再借助跳数误差值对参与计算的信标节点进行加权处理，最终得到修正后的平均跳距．定义节点i的最大理想跳数为Si=max(li1/R,li2/R,li3/R,li4/R)，式中li1,li2,li3,li4表示节点i距离矩形分布范围4个顶点的距离．当信标节点i和j之间最小跳数大于Si时，说明节点i和j间的跳数太大，再将节点j参与到计算节点i的平均跳距，会令定位算法结果产生较大误差，故将信标节点j去除．用δij=Dij/R-hij计算两节点间的理想跳数和最小跳数间的差值，其中：Dij为信标节点i和j之间的实际距离；R是通信半径；hij是信标节点i和j之间的最小跳数．节点j在参与计算节点i平均跳距的权重为wij=δij-1/∑l≠imδil-1，式中m表示参与计算节点i平均跳距的节点总数．δij越大，wij越小，这样就可以减小引起定位结果误差过大的节点的影响力，增强提高定位结果精度的节点的能力，改进后平均跳距为Q¯=∑j≠imwij×Dijhij．2.2　基于遗传-模拟退火的定位优化在对传统dv-hop算法进行最小跳数和平均跳距修正后，利用最小二乘法求得待确定位置的节点的坐标式，接下来将其作为遗传模拟退火算法DGSA的输入值，经过该混合算法输出的结果便是得到优化后的节点定位值．遗传算法(GA，genetic algorithm)结合了生物自然选择与遗传知识，能够很好地解决寻优问题并得到广泛应用．但是单一GA算法局限性也较为明显，即会由于算法缺陷无法跳出局部最优解范围．对此提出了混合算法，让遗传算法能与其他算法相互渗透，使得在实际应用中达到更优良的优化效果，如本文遗传模拟退火算法．模拟退火[18]是一种随机寻优，它的显著优势便是在迭代过程中概率保持突跳性，不会陷入局部最小．因此，将二者结合形成混合算法．操作步骤具体为：将通过遗传算法新产生的后代在进入下一代群体之前先应用模拟退火技术，使之先移动到最近的局部最优点．假定(xi,yj)为用最小二乘法计算得到的未知节点i的初始坐标，节点i与信标节点j间的距离为dij=(xi-xj)2+(yi-yj)2．建立适应度函数f(xi,yi)，具体为f(xi,yi)=∑j=1nDij-dij-1，式中Dij为节点i和j间实际距离．适应度值越大，定位越准确．2.2.1　算法的初步选择采用好理解也很实用的轮盘赌法进行选择运算，即根据优胜劣汰原则选择出适应度值较高的个体，选择概率为pi,a=f(a)∑ f(a)，式中：f(a)为个体a的适应度；∑f(a)为种群中个体适应度之和．利用轮盘赌法选择个体时，会产生1个[0，1]之间的均匀随机数，借此得到可以进行下一步运算的个体，个体被选中的概率和适应度大小相关．2.2.2　交叉将两个父代个体的部分结构进行交换重组从而形成新的个体的过程称为交叉．交叉运算使得GA拥有自身的独特性，不同于其他算法，同时也使GA算法能更好地在问题的解集里找到最优值．所以选取合适的交叉率pc值十分重要．自适应遗传算法中的pc为pc=k1(fmax-f)fmax-favg    (favg≤f);k2    (favgf),式中：fmax为群体中最大的适应值；favg为群体的平均适应值；f为要交叉的两个个体中较大的适应值；k1,k2均为某一常数．当交叉率pc较大时，新个体产生的速度快，但是随之遗传算法的稳定性也可能会减弱，即群体中那些具有高适应值的个体结构可能会遭到破坏；倘若交叉率pc值设置过小，此时遗传算法的稳定性得到了保证，但新个体产生的速度和得到最优解的过程会变得缓慢．因此在仿真实验时须要不断设置不同的交叉率pc．此外，在交叉重组的过程中，要避免出现“近亲结合”．2.2.3　变异为改善算法的局部收敛效率，选取合适的变异概率同样也十分重要．遗传算法中自适应变异概率为pm=k3(fmax-f)fmax-favg    (favg≤f);k4    (favgf),式中：k3,k4均为常数，取值范围为[0，1]；f为变异个体的适应度，在变异后产生的新子代中引入模拟退火算法，使其达到局部最优．2.2.4　模拟退火x为当前可行解，xnew为迭代更新后的解，以降温概率p进行更新，即p=1    (Δf≥0);exp(Δf /θ)    (Δf0),式中：Δf=f(xnew)-f(x)；θ为温度参数，初步将θ设置为90 ℃．实际应用中，由于必须考虑算法复杂度以及时间和能量的消耗等问题，模拟退火过程中的温度管理计算公式为θ=αθ(α∈(0,1))．为了保证较大的搜索空间，α一般取接近于1的值，如0.95和0.9．DGSA算法流程如图4所示．10.13245/j.hust.240066.F004图4DGSA算法流程图3 仿真分析为判断DGSA算法是否能有效提高定位结果的准确性，借助Matlab(R2016b)仿真实现DGSA算法，所用电脑处理器为Intel(R) Core(TM) i5-8250U CPU@1.60 GHz，系统为Windows10．仿真实验主要观察信标节点比例、通信半径及节点总数对平均定位误差φ的影响．平均定位误差为φ=(NR)-1∑k=1N(xk-x^k)2+(yk-y^k)2，式中：(xk,yk)和(x^k,y^k)分别表示未知节点k的实际位置和虚拟位置；N为未知节点个数；R为通信半径．为了得到更好的实验对比效果，选择传统dv-hop定位算法、DV-HOP-GA (DV-HOP Genetic-Algorithm Location)[19]算法和文献[20]提出的一种改进的布谷鸟搜索移动信标节点定位算法(AFCS)进行对比测试，然后对测试结果展开分析．WSN仿真实验参数设置为：网络规模100 m×100 m；网络节点总数为50，100，150，200，250，300和350；信标节点比例为0.05，0.10，0.15，0.20，0.25，0.30和0.35；通信半径为20，25，30，35，40，45和50 m；温度为90 ℃；温度管理计算因子α=0.95；迭代次数t=100．3.1　信标节点比例对定位精度的影响将100个无线传感器节点，无规则地散布在须要进行监测的区域内，设R=20 m,信标节点比例分别取为5%，10%，15%，20%，25%，30%和35%，仿真结果见图5．10.13245/j.hust.240066.F005图5信标节点比例与平均定位误差间关系如图5所示，随着信标节点比例的增大，3种算法定位误差逐渐减小．通过dv-hop算法的实现步骤可知，信标节点越多，作为影响定位结果的关键参数即节点间跳数就会越小，算法的定位精度也得到了提升．同时可以观察到：当信标节点比例控制在10%的条件下时，平均定位误差由大到小依次为dv-hop算法、AFCS算法、DV-HOP-GA算法和DGSA算法，这说明DGSA算法相比于三种对比算法在相同的信标节点数条件下达到了更好的定位结果．在不同信标节点比例条件下，DGSA算法的平均定位误差分别比传统dv-hop算法、DV-HOP-GA算法和AFCS算法下降了42.56%，7.10%和3.86%．3.2　通信半径对定位精度的影响在须要进行监测区域内无规则布设100个节点，设信标节点个数为20，令R从20 m增加至50 m．仿真结果如图6所示．从图6可以看出：随着R的增大，定位误差逐步减小，当R取同一值时，DGSA定位精度最高，当R30 m时，定位误差变化的趋势变得很小，逐渐趋于稳定值．R增大，节点要消耗更多通信能量，而传感器节点由电池供电，且监测环境比较恶劣时，无法及时对电池进行充电，节点续航能力严重不足时便不能再进行数据的监测，所以为了追求尽可能低的定位误差而去牺牲节点通信能量是得不偿失的且效果甚微，在不同通信半径条件下，DGSA算法定位误差分别比dv-hop，DV-HOP-GA和AFCS算法降低了51.87%，6.70%和5.76%．10.13245/j.hust.240066.F006图6通信半径与平均定位误差之间的关系3.3　节点总数对定位精度的影响将节点总数分别设置为50，100，150，200，250，300和350，并始终将信标节点比例设置为20%，令R=20 m，仿真结果如图7所示．由图7可以看出：平均定位误差随着节点总数的增大而逐步减小．在节点总数变化的过程中，当节点总数取200时，按照平均定位误差数值由大到小对算法进行排序依次是：dv-hop算法，DV-HOP-GA算法，AFCS算法，DGSA算法．这说明DGSA算法可以利用相同的节点量取得更高的定位精度．在不同节点总数条件下，DGSA算法定位精度分别比dv-hop，DV-HOP-GA算法和AFCS算法提高了46.13%，16.92%和3.47%．10.13245/j.hust.240066.F007图7节点总数与平均定位误差之间的关系3.4　算法运行时间上面3组仿真实验都是观察算法定位精度是否得到有效提升，下面通过仿真分析算法效率是否也得到了提高，结果如图8所示．10.13245/j.hust.240066.F008图8节点总数与算法运行时间之间的关系由图8可知：DGSA算法的运行时间明显低于其他三种对比算法．在节点总数为350的条件下，DGSA算法运行时间与AFCS算法差距不大，但明显小于dv-hop和DV-HOP-GA算法．此时DGSA，DV-HOP-GA和dv-hop算法的运行时间分别为0.63，1.05和2.15 s．DGSA算法的运行时间分别比DV-HOP-GA和dv-hop算法减少了0.42 s和 1.52 s．这说明，DGSA在相同的节点总数条件下运行时间更短，算法寻优效率更高．4 结语基于传统dv-hop定位算法，结合遗传以及模拟退火算法，提出了基于遗传-模拟退火优化的dv-hop定位算法．首先引入跳数调整因子对节点间跳数信息进行修正，再用加权处理方式优化平均跳距，降低了dv-hop算法因本身局限性产生的定位误差；其次将局部搜索能力优良的的模拟退火算法引入遗传算法中进行寻优．由仿真结果可以看出：DGSA算法在定位精度和寻优效率方面要明显优于dv-hop，DV-HOP-GA和AFCS算法．DGSA算法性能优良，或可帮助解决其他类似的数据采集中出现的问题．但是目前DGSA算法只适用于二维空间，因此下一步将根据三维空间特性，展开定位算法的设计与研究，以满足不断提高的传感器网络空间定位需求．