湖南大学无线传感器报告定位算法APIT和RSSI

无线传感器网络实验题目 定位算法学生： 学号： 完成时间： 一、实验目的掌握matlab工具的使用方法。了解APIT或RSSI算法原理，熟悉APIT或RSSI算法代码，分析APIT或RSSI算法实验结果。二、实验原理APIT算法概述（一）基本思想首先确定多个包含未知节点的三角形区域这些三角形区域的交集是一个多边形，它确定更小的包含未知节点的区域计算这个多边形的质心，并将质心作为未知节点的位置。（二）基本过程未知节点首先收集其临近新标节点的信息。从这些信标节点组成的集合中任意选取三个节点。假设集合中有n个元素，那么共有Cn3种不同的选取方法，确定Cn3个不同三角形，逐一测试未知节点是否位于每个三角形内部，知道穷尽所有Cn3种组合表达式计算包含目标节点所有三角形的重叠区域

(三)APIT算法分四步：1)信标交换;((2)三角形内点测试(PIT,Point-In-Triangulationtesting)3)交集运算计算三角形的重合区域;(4)重心(COG,CenterofGravity)计算求节点的位置。(四)定位的理论基础PIT：最佳三角形内点测试法PIT原理:假如存在一个方向，节点M沿着这个方向移动会同时原理或接近A.B.C,那么节点M位于三角形ABC外，否则，节点M位于三角形ABC内。（五） APIT算法的具体步骤收集信息：位置节点收集邻近信标节点的信息，入位置，标志号，接受的信号强度，邻居节点之间交换各自接受到的信标节点的信息APIT测试测试未知节点是否在不同信标节点组成三角形内部计算重叠区域，统计包含未知节点三角形，计算所有三角形的重叠区域计算未知节点的位置计算重叠区域的质心位置，作为未知节点的位置（六） RSSI算法1.基本思想一直发射节点的发射信号强度，接收节点根据收到信号的强度，计算出信号的传播损耗，利用理论或者经验的模型将传输损耗转化为距离再利用已经有的算法计算出节点的位置信号强度（RSS）①通过信号在传播中的衰减来估计节点之间的距离②根据信道模型求解距离③信道的时变特性：（1）信道由于受到多径衰减（Multi-pathFading）R(dO)doR(d)6R(dO)doR(d)6-I标物他三、实验内容和步骤APIT：APIT代码如下所示：functionAPIT(grid_length)%InAPIT,thesensornodesarenothomogeneous%thecommunicationrangeofanchorsislargerthanthatofunknownnodes%comm_r:thecommunicationrangeoftheunknownnode.it'ssavedinneighbor.mat%thecommunicationrangeoftheanchornodeis:times*comm_r,savedinneighbor.mat%~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~load'../DeployNodes/coordinates.mat';load'../TopologyOfWSN/neighbor.mat';disp('时间较长，耐心等待...')；unknown_node_index=all_nodes.anchors_n+1:all_nodes.nodes_n;row_n=ceil(all_nodes.square_L/grid_length);col_n=row_n;centroid_x=repmat(([1:col_n]-0.5)*grid_length,row_n,1)；centroid_y=repmat(transpose(([1:row_n]-0.5)*grid_length),1,col_n)；fori=unknown_node_indexdisp([num2str(i),':我在跑，不要催啦...']);neighboring_anchor_index=find(neighbor_matrix(i,1:all_nodes.anchors_n)==1)；neighboring_anchor_n=length(neighboring_anchor_index);ifneighboring_anchor_n>=3gridmap=zeros(row_n,col_n);grid_covered_flag=zeros(row_n,col_n);fora=1:neighboring_anchor_n-2forb=a+1:neighboring_anchor_n-1forc=b+1:neighboring_anchor_n%~~判断未知节点i是否在三角形abc内部%ApproximateP.I.TTest:"IfnoneighborofMisfurtherfrom/closetoallthreeanchorsA,BandCsimultaneously,%Massumesthatitisinsidetriangleabc.Otherwise,Massumesitresidesoutsidethetriangle."neighboring_node_index=setdiff(find(neighbor_matrix(i,:)==1),neighboring_anchor_index([abc]));neighboring_node_rss_of_abc=neighbor_rss(neighboring_node_index,neighboring_anchor_index([abc]));in_out_judge=neighboring_node_rss_of_abc>repmat(neighbor_rss(i,neighboring_anchor_index([abc])),length(neighboring_node_index),1);ifany(sum(transpose(in_out_judge))==0|sum(transpose(in_out_judge))==3)%outsideGrid_in_triangle_abc=inpolygon(centroid_x,centroid_y,all_nodes.estimated(neighboring_anchor_index([abc]),1),all_nodes.estimated(neighboring_anchor_index([abc]),2));%被三角形abc覆盖到的网格gridmap=gridmap-Grid_in_triangle_abc;else%insideGrid_in_triangle_abc=inpolygon(centroid_x,centroid_y,all_nodes.estimated(neighboring_anchor_index([abc]),1),all_nodes.estimated(neighboring_anchor_index([abc]),2));%被三角形abc覆盖到的网格gridmap=gridmap+Grid_in_triangle_abc;endgrid_covered_flag=grid_covered_flag|Grid_in_triangle_abc;endendendifany(any(grid_covered_flag))weight_max=max(max(gridmap(grid_covered_flag)));weight_max_index=intersect(find(gridmap==weight_max),find(grid_covered_flag==1));[weight_max_ind_row,weight_max_ind_col]=ind2sub(size(gridmap),weight_max_index);all_nodes.estimated(i,:)=mean([weight_max_ind_colweight_max_ind_row;weight_max_ind_colweight_max_ind_row]*grid_length-0.5*grid_length);

all_nodes.anc_flag(i)=2;endendendsave'../LocalizationError/result.mat'all_nodescomm_r;end锚节点通信半径是源节点通信半径的2倍，采用正方形随机分布

如上图所示红色*表示锚节点，蓝色O表示未知节点的估计位置，黑色O表示不能被定位的未知节点，蓝色-表示未知节点的定位误差（连接未知节点的估计位置和真实位置），一共300个节点:60个锚节点,240个未知节点,0个不能被定位的未知节点，定位误差为0.93787锚节点通信半径变成4倍以后程序运行速度明显变慢，理论上分析定位误差应该是更加大了因为未知节点所在的三角形增多了，所以定位误差更大。锚节点通信半径变为1倍，未知节点变多，误差变小。一共300个节点:60个锚节点,240个未知节点,11个不能被定位的未知节点定位误差为0.33242o£¥200100a+¥定位误差團1000900800700600500400300o£¥200100a+¥定位误差團1000900800700600500400300Z 7V ” 巳*Q I II I I I I『 I I I 70 100 200 300 400 500 600 700 800 900 1000一共400个节点:80个锚节点,320个未知节点,8个不能被定位的未知节点定位误差为0.32564APIT优缺点：在定位精度、硬件成本、节点分布和锚节点密度等方面性能优越。在邻居节点数目增多情况下，定位误差呈下降趋势，在锚节点的密度和锚节点通信距离上升的情况下，定位误差上升。改进：网络边缘区域未知节点拥有较少的邻居锚节点，这样更加容易早场他们无法满足APIT的定位条件，有些节点邻居锚节点少于3个，它们都将成为未确定节点。对于不满足APIT定位条件的节点，当邻居锚节点大于等于3个时，采用三边测量法定位，否则可以使用其他例如RSSI方法测出节点位置。RSSI：RSSIFirst：functionRSSI()%未知节点利用邻居锚节点进行定位，没有邻居锚节点的未知节点无法定位%根据接收信号强度转化为距离。规则传播模型下得到的距离跟实际距离没有误差%不规则通信模型下，规则传播模型下得到的距离跟实际距离存在误差%~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~load'../DeployNodes/coordinates.mat';load'../TopologyOfWSN/neighbor.mat';directory=cd;cd'../TopologyOfWSN/TransmissionModel/';cd(model);unknown_node_index=all_nodes.anchors_n+1:all_nodes.nodes_n;fori=unknown_node_indexneighboring_anchor_index=intersect(find(neighbor_matrix(i,:)==1),find(all_nodes.anc_flag==1));%只利用邻居锚节点进行定位neighboring_anchor_n=length(neighboring_anchor_index);ifneighboring_anchor_n>=3trydist=rss2dist(neighbor_rss(neighboring_anchor_index,i),1);catchdist=rss2dist(neighbor_rss(neighboring_anchor_index,i));endneighboring_anchor_location=all_nodes.estimated(neighboring_anchor_index,:);%~~~~~~~~~~~~~~~~~~~~~~~~~三边测量法(最小二乘法)A=2*(neighboring_anchor_location(1:neighboring_anchor_n-1,:)-repmat(neighboring_anchor_location(neighboring_anchor_n,:),neighboring_anchor_n-1,1));neighboring_anchor_location_square=transpose(sum(transpose(neighboring_anchor_location.A2)));dist_square=dist42;b=neighboring_anchor_location_square(1:neighboring_anchor_n-1)-neighboring_anchor_location_square(neighboring_anchor_n)-dist_square(1:neighboring_anchor_n-1)+dist_square(neighboring_anchor_n);all_nodes.estimated(i,:)=transpose(A\b);all_nodes.anc_flag(i)=2;endend%~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~cd(directory);save'../LocalizationError/result.mat'all_nodescomm_r;endRSSISecond：functionRSSI_second()%未知节点一旦被定位就充当起锚节点的功能，向周围邻居发送自己的估计坐标信息%未知节点把已经定位的未知节点与锚节点同等对待%根据接收信号强度转化为距离。规则传播模型下得到的距离跟实际距离没有误差%不规则通信模型下，规则传播模型下得到的距离跟实际距离存在误差%~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~load'../DeployNodes/coordinates.mat';load'../TopologyOfWSN/neighbor.mat';directory=cd;cd'../TopologyOfWSN/TransmissionModel/';cd(model);unknown_node_index=all_nodes.anchors_n+1:all_nodes.nodes_n;whiletruefori=unknown_node_indexneighboring_anchor_index=intersect(find(neighbor_matrix(i,:)==1),find(all_nodes.anc_flag~=0));%已经定位的未知节点也视为锚节点neighboring_anchor_n=length(neighboring_anchor_index);ifneighboring_anchor_n>=3trydist=rss2dist(neighbor_rss(neighboring_anchor_index,i),1);catchdist=rss2dist(neighbor_rss(neighboring_anchor_index,i));endneighboring_anchor_location=all_nodes.estimated(neighboring_anchor_index,:);%~~~~~~~~~~~~~~~~~~~~~~~~~三边测量法(最小二乘法)A=2*(neighboring_anchor_location(1:neighboring_anchor_n-1,:)-repmat(neighboring_anchor_location(neighboring_anchor_n,:),neighboring_anchor_n-1,1));neighboring_anchor_location_square=transpose(sum(transpose(neighboring_anchor_location.A2)));dist_square=dist.A2;b=neighboring_anchor_location_square(1:neighboring_anchor_n-1)-neighboring_anchor_location_square(neighboring_anchor_n)-dist_square(1:neighboring_anchor_n-1)+dist_square(neighboring_anchor_n);all_nodes.estimated(i,:)=transpose(A\b);all_nodes.anc_flag(i)=2;endendtryunknown_node_index==transpose(find(all_nodes.anc_flag==0));break;catchunknown_node_index=transpose(find(all_nodes.anc_flag==0));endend%~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~cd(directory);save'../LocalizationError/result.mat'all_nodescomm_r;endRSSIThird：functionRSSI_third()%有邻居锚节点的未知节点只利用邻居锚节点进行定位，没有邻居锚节点的未知节点才利用已经定位了的邻居未知节点进行定位%根据接收信号强度转化为距离。规则传播模型下得到的距离跟实际距离没有误差%不规则通信模型下，规则传播模型下得到的距离跟实际距离存在误差load'../DeployNodes/coordinates.mat';load'../TopologyOfWSN/neighbor.mat';directory=cd;cd'../TopologyOfWSN/TransmissionModel/';cd(model);%~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~Ioop=1;%有邻居锚节点的未知节点只利用邻居锚节点进行定位unknown_node_index=all_nodes.anchors_n+1:all_nodes.nodes_n;whiIetruefori=unknown_node_indexneighboring_anchor_index=intersect(find(neighbor_matrix(i,:)==1),find(aII_nodes.anc_fIag==1|aII_nodes.anc_fIag==Ioop));neighboring_anchor_n=Iength(neighboring_anchor_index);ifneighboring_anchor_n>=3trydist=rss2dist(neighbor_rss(neighboring_anchor_index,i),1);catchdist=rss2dist(neighbor_rss(neighboring_anchor_index,i));endneighboring_anchor_Iocation=aII_nodes.estimated(neighboring_anchor_index,:);%~~~~~~~~~~~~~~~~~~~~~~~~~三边测量法(最小二乘法)A=2*(neighboring_anchor_Iocation(1:neighboring_anchor_n-1,:)-repmat(neighboring_anchor_Iocation(neighboring_anchor_n,:),neighboring_anchor_n-1,1));n