【定位问题】基于matlab RSSI和模拟退火优化粒子群算法求解无线传感器网络定位问题【含Matlab源码 1766期】

一、简介

1 引言
随着物联网技术的发展，传感器通过通信连接在一起，形成了一个巨大的无线传感器网络，广泛应用于各行各业[。然而，由于传感器节点不能全部配备昂贵的传感器节点，因此GPS对所有传感器节点位所有传感器节点。因此，无线传感器网络技术最关心的是实现传感器节点的精确定位。

通常,无线传感网络中主要有与距离有关和与距离无关两类定位算法。与距离相关的定位算法主要包括TOA算法、TDOA[6]算法和三边定位算法；与距离无关的定位算法主要包括质心定位算法APIT算法、DV-Hop算法和MDS-MAP算法等。然而，目前的定位算法在定位精度和实际应用方面仍存在一些不足。为了进一步提高传感器网络的定位精度，国内外研究人员进行了更深入的研究。在国外,Bulusu利用传感器网络的连接，获取未知节点周围的参考节点，作为邻居节点，然后将邻居节点形成的纹理作为未知节点的近似位置。Sretenovi等待城市环境RSSI在加权质心定位算法中应用模型数据，确定传感器节点的位置，实验结果表明该方法更具实用价值。Sai等在RSSI并行萤火虫算法是在提高目标函数的基础上提出的，将定位问题转化为非线性无约束问题，表明该算法具有更高的定位精度。Mass-Sanchez采用粒子群算法对等DV-hop优化定位算法，获得比加权DV-hop和双曲线DV-hop定位精度更好。在中国，李腾宇是基于RSSI在参考节点距离的数学模型中使用加权质心定位算法测量的未知节点GASA算法优化求解，定位精度更高。在质心定位算法的基础上，谢国民采用了PSO-GSA该算法优化了相关参数和位置信息，有效地提高了复杂煤矿环境中人员的定位精度。基于张颤等RSSI在加权质心定位的基础上，将定位的未知节点作为参考节点，然后定位其他未知节点。该方法可有效减少网络连接度低时无法定位的节点数量。王晨等人工鱼群算法的适应性函数是根据信号识别强度获得的距离和参考节点的位置信息，寻求质量定位算法的定位过程，提高了定位精度，但计算量大大提高。

鉴于当前质心定位算法中存在的定位精度不能满足实际应用要求、计算量大、成本高等问题，本文结合了群体智能算法的优秀性能RSSI基于粒子群模拟退火优化算法，提出了纹理定位算法计算简单的优点-RSSI(Particle Swarm Optimization,Simulated Annealing algorithm and RSSI,PSO-SA-RSSI)质心定位算法。以传统的质心定位算法为基础，评价本文算法在定位精度方面的性能RSSI基于粒子群算法的优化和加权质心定位算法RSSI(Particle Swarm Optimization and RSSI,PSO-RSSI)对比模拟质心定位算法。实验结果表明，本文不仅定位精度高，而且具有计算简单、泛化性能强等突出优点。

2 纹理定位算法
2.1 无线电信号传输损耗模型
无线电信号传输损耗模型是无线传感器网络定位技术中最常用的模型。自由空间传输模型的通信区域是以发射节点为原点的圆，通信区域内的接收节点可以接收信号，否则无法进行数据交换。在理想环境下，传感器接收端节点测量的信号接收强度指示值Pr从接收端到发射端的距离d满足型(1):

但在实际应用中，无线电信号传输会受到传输距离、物体反射、折射和散射等诸多因素的影响。在自由空间模型中添加高斯分布因子可以更好地模拟无线电信号在实际环境中的传输过程，因此可以描述为无线电信号传输损失模型：

其中,χ代表高斯分布因素；Pr代表接收节点接收信号的功率；Pt代表发射节点发出信号的功率；PL(d0)代表参考距离为d0时路径损耗功率；η代表路径损失指数；d代表接收节点与发射节点之间的距离；d0代表距离地面的参考高度，通常取1 m。

2.2 基于RSSI加权质心定位算法
传统的纹理定位算法主要是根据传感器之间的连通性，将靠近未知节点的邻居节点形成多边形，并将多边形纹理作为定位系统中未知节点的坐标，但定位精度差，实际应用价值低。为了提高定位算法的定位精度，一些研究人员提出了建议RSSI通过引入加权质心定位算法RSSI无线电信号传输损传输数据帧时，无线电信号传输损耗模型可以获得未知节点与参考节点之间的距离，并将该距离作为定位未知节点的权重值，以提高定位精度。

假设未知节点附近的参考节点坐标分别为(x1,y1),(x2,y2),…,(xi,yi),…,(xn,yn),未知节点的传统纹理定位坐标为：

与传统的质心定位算法相比，加权质心定位算法只选择最近未知节点的三个参考节点A,B与C形成围绕未知节点的三角形，通过三角形的纹理确定未知节点的位置。假设未知节点到达A,B和C 三个参考节点之间的距离分别记录为dA,dB和dC,未知节点的位置坐标为：

需要注意的是，当最近未知节点的参考节点不到3个时，定位过程无法完成。为了解决这一问题，在实际定位过程中，将定位的未知节点作为伪参考节点参与定位过程，使通信范围内不到3个参考节点的未知节点也能实现准确定位。

3 PSO-SA优化的RSSI纹理定位算法
群智能算法作为一种优化算法在各个领域均有应用,其中粒子群算法和模拟退火算法是当前群智能算法研究领域的热点。粒子群算法具有参数少、求解简单、全局搜索能力强等优点。模拟退火算法是根据热力学中物体的热溶解过程提出的算法，运行效率高，解决过程不受初始条件的影响，可用于解决大规模组合优化问题。本文提出了一种结合模拟退火算法优化的混合群智能算法，即粒子群算法RSSI纹理定位算法不仅可以保持粒子群算法操作简单、易于实现的优点，还可以改善粒子群算法容易陷入局部极值点的情况，减少算法的运行时间，提高算法的准确性。

3.1 适应度函数
未知节点坐标准确定位的本质是通过多次循环迭代适应函数来解决适应函数的最小值，以准确确定未知节点的位置坐标。所以在基础上RSSI构建合理的适应性函数对于确定未知节点的位置坐标非常重要。假设选择离未知节点最近的三个节点A(xA,yA),B(xB,yB)和C(xC,yC)为邻居节点,其与未知节点之间的距离分别记为:

使用参考节点A,BC与未知节点之间的距离(dA,dB和dC)和基于RSSI模型测距方法(见式(2)获得的距离(d1,d2和d结合模型退火算法的适应性函数为：

3.2 PSO-SA优化算法步骤
利用PSO-SA优化质心定位算法的基本位算法的基本思想是：首先，使用RSSI模型实现了参考节点与未知节点之间的距离，然后确定了未知节点周围的三角形；最后，使用PSO-SA混合群智能算法对上节中构造的适应度函数进行寻优求解,实现对未知节点位置信息的确定,其中PSO-SA智能算法的步骤如下。

步骤1 初始化粒子组和模拟退火算法。
1)粒子群算法的初始化:
群粒的初始位置是三个参考节点的质地x(i)=(xi,yi)=(xA,yA) (xB,yB) (xC,yC)3.粒子速度初始化为vi=rand;设置每个粒子的最佳位置pi=(xi,yi)最佳位置的起始值pbest=f(xi,yi);最后一个粒子中最后一个粒子的解是全球最优解，然后与其他粒子的最优解进行比较取最小解的位置作为全局最优解的位置pall=(xi,yi),并将全局搜索的极值设置为groupFit。

2)模拟退火算法的初始化:
退火常数的初始化K,初始温度T=f(pall)log5。
步骤2 当模拟退火系统的能量状态从E1变化到E2时利用Metropolis算法准则:

步骤3 更新位置x(i)和速度v(i),r1和r二是随机数。
v(i 1)=wv(i) c1r1(i)(pi-x(i)) c2r2(i)*(pall_plus-x(i)) (8)
x(i 1)=x(i) v(i 1) (9)
步骤4 判断一个新的粒子群是否是最优位置和最优位置，是否是粒子群的最优位置和最优位置。然后在每次迭代后更新最优位置。更新权重系数w(n 1)=w(n)?0.5N。
步骤5 退火操作T(n 1)=KT(n),n=1,2,…,N。
步骤6 在迭代结束之前，得到最优解位置，否则转到步骤2完成迭代次数。
综上所述,PSO-SA如图1所示。

图1 PSO-SA混合群智能算法的流程

二、部分源代码

%信标节点位于等边三角形顶点的仿真 
clc 
clear all 
%S为三个选定的信标节点坐标矩阵,节点坐标已知(为便于仿真及验证,代码中采用的等边三角形)
%依次测试信标节点间距离放大t倍时的定位效果
for t = 1:10 
    S=[0,0;5*t,5*t*sqrt(3);10*t,0]; 
    nums = [S(1,1),S(1,2),S(2,1),S(2,2),S(3,1),S(3,2)]; 
    p = min(nums); 
    q = max(nums); 
    L = sqrt((S(1,1)-S(3,1))^2+(S(1,2)-S(3,2))^2); 
    m = 100; 
    %生成在[p,q]上满足均匀分布的随机数矩阵 
    %即生成一组m行2列的有可能落在等边三角形区域内的坐标 
    numbox = p+(q-p)*rand(m,2); 
     
    %计数初值,最终根据计算将随机生成的点中落在等边三角形区域内的坐标存放于新的矩阵 
    n = 1; 
    for i = 1:m 
        dA(i) = sqrt((numbox(i,1)-S(1,1))^2+(numbox(i,2)-S(1,2))^2); 
        dB(i) = sqrt((numbox(i,1)-S(2,1))^2+(numbox(i,2)-S(2,2))^2); 
        dC(i) = sqrt((numbox(i,1)-S(3,1))^2+(numbox(i,2)-S(3,2))^2); 
        %将确实在等边三角形区域内的坐标存入P_position矩阵 
        if (dA(i)<=L) && (dB(i)<=L) && (dC(i)<=L) 
            P_position(n,1) = numbox(i,1); 
            P_position(n,2) = numbox(i,2); 
            n = n+1; 
        end 
    end 
    %N为随机生成的点中落在等边三角形区域内的点(测试点)的个数 
    N = n-1 
    if N == 0 
        disp('所取的随机坐标无一落在等边三角形内,请增大m值重新运行程序.') 
        return 
    end 
 
    %计算测试点离三个顶点的实际距离 
    %dis为N行3列的矩阵,用于存放N个测试点分别到等边三角形三个顶点A,B,C的实际距离 
    for i = 1:N 
        dis(i,1) = sqrt((P_position(i,1)-S(1,1))^2+(P_position(i,2)-S(1,2))^2); 
        dis(i,2) = sqrt((P_position(i,1)-S(2,1))^2+(P_position(i,2)-S(2,2))^2); 
        dis(i,3) = sqrt((P_position(i,1)-S(3,1))^2+(P_position(i,2)-S(3,2))^2); 
    end 
 
    %根据函数Distance计算测试点离三个顶点的测试距离(考虑了衰减及环境误差等) 
    %dis_test为N行3列的矩阵,用于存放N个测试点分别到等边三角形三个顶点A,B,C的测试距离 
    a = 7; %由RSSI计算T-R距离时使用的参数 
    for i = 1:N 
        dis_test(i,1) = Distance(dis(i,1),a); 
        dis_test(i,2) = Distance(dis(i,2),a); 
        dis_test(i,3) = Distance(dis(i,3),a); 
    end 
     
    %根据函数Triangle及求得的测试距离进行定位 
    %P_calculate为N行2列的矩阵,用于存放定位后的N个坐标 
    for i = 1:N 
        [P_temp_SAPSO,fv]= SAPSO(@fitness,500,2,2,0.6,20,2,S,dis_test(i,1),dis_test(i,2),dis_test(i,3)); 
        P_calculate_SAPSO(i,1) = P_temp_SAPSO(1); 
        P_calculate_SAPSO(i,2) = P_temp_SAPSO(2); 
        P_temp = Triangle(S,dis_test(i,1),dis_test(i,2),dis_test(i,3));
        P_calculate_Triangle(i,1) = P_temp(1); 
        P_calculate_Triangle(i,2) = P_temp(2); 
    end 
    
    %由于测试距离相比真实距离有误差,三角计算中的两圆有可能无交点,导致方程无实根. 
    %于是P_calculate中会出现虚数.在测试中虚数无实际意义,因此取其实部存放于另一矩阵 
    for i = 1:N 
        P_calculate_Triangle_real(i,1) = real(P_calculate_Triangle(i,1)); 
        P_calculate_Triangle_real(i,2) = real(P_calculate_Triangle(i,2)); 
    end 
 
    %对比测试点的定位坐标与实际坐标之间的误差 
    P_position; 
    P_calculate_SAPSO;
    P_calculate_Triangle_real;
    %计算定位结果与真实坐标之间的距离误差平均值e_average(测试点等概率) 
    e_sum_SAPSO = 0; 
    e_sum_Triangle=0;
    e_max_SAPSO=0;
    e_max_Triangle=0;
    for i = 1:N 
        e_SAPSO = sqrt((P_calculate_SAPSO(i,1)-P_position(i,1))^2+(P_calculate_SAPSO(i,2)-P_position(i,2))^2); 
        if e_SAPSO>e_max_SAPSO
            e_max_SAPSO=e_SAPSO;
        end
        e_sum_SAPSO = e_sum_SAPSO+e_SAPSO; 
        e_Triangle=sqrt((P_calculate_Triangle_real(i,1)-P_position(i,1))^2+(P_calculate_Triangle_real(i,2)-P_position(i,2))^2);
        if e_Triangle>e_max_Triangle
            e_max_Triangle=e_Triangle;
        end
        e_sum_Triangle=e_sum_Triangle+e_Triangle;
    end 
    e_average_SAPSO = e_sum_SAPSO/N; 
    e_average_SAPSO_box(t)=e_average_SAPSO
    e_average_Triangle=e_sum_Triangle/N;
    e_average_Triangle_box(t)=e_average_Triangle
    e_max_SAPSO_box(t)=e_max_SAPSO
    e_max_Triangle_box(t)=e_max_Triangle
    e_average_percent_SAPSO = e_average_SAPSO/L; 
    e_average_percent_SAPSO_box(t)= e_average_percent_SAPSO
    e_average_percent_Triangle = e_average_Triangle/L;
    e_average_percent_Triangle_box(t)=e_average_percent_Triangle
end 
 
t = [1:10]; 
figure;
plot(t,e_average_SAPSO_box(t),'k-',t,e_average_Triangle_box(t),'k-.')
xlabel('t')
ylabel('平均定位误差')
legend('SAPSO','Triangle')
grid on;
figure;
plot(t,e_max_SAPSO_box(t),'k-',t,e_max_Triangle_box(t),'k-.')
xlabel('t')
ylabel('最大定位误差')
legend('SAPSO','Triangle')
grid on;
figure;
plot(t,e_average_percent_SAPSO_box(t),'k-',t, e_average_percent_Triangle_box(t),'k-.')
xlabel('t')
ylabel('平均定位误差率')
legend('SAPSO','Triangle')
grid on;

三、运行结果

四、matlab版本及参考文献

1 matlab版本
2014a

2 参考文献
[1]王改云,王磊杨,路皓翔.基于混合群智能算法优化的RSSI质心定位算法[J].计算机科学. 2019,46(09)