中南大学信息科学与工程学院物联网定位技术实验报告书实验名称：网络定位算法研究成员：董嘉伟指导老师:张士庚完成时间：2013-6-1目录●实验目的●实验设备●实验要求●实验背景●实验原理●实验实现（部分）●实验结果展示及分析●实现小结一、实验目的掌握常用网络定位算法，并能够独立完成和实现。
二、实验设备硬件：计算机软件：VS2012、C#4.0三、实验要求●在给定的两个网络中，编程实现前面所讲的定位算法●选择至少两个定位算法进行实现●计算所得的定位结果的误差●对不同定位算法的效果进行分析比较●撰写实验报告●扩展：考虑距离测量有误差的情况？四、实验背景无线传感器网络(WSN)定位问题在军事、楼宇自动化、跟踪与监测等方面都有广泛的应用，一直是WSN的技术热点之一。
尽管全球无线定位系统(GPS)提供了很好定位手段，并在很多方面发挥着重要的作用，但也存在着一些不足。
比如：GPS不适合于室内环境定位，其能量消耗将减少传感器节点的生存寿命，GPS 及其天线增大了节点的体积等，因此GPS并不适用于无线传感器网络。
针对无线传感器网络开展专门的不依赖于GPS的定位研究（特别是分布式定位算法），具有重要的意义。
很多学者研究了无线传感器网络节点精确定位问题，提出了许多有效的算法。
这些算法依据是否计算节点间的距离，可分为距离无关定位算法和距离相关定位算法。
距离无关定位算法如最小包含圆算法、DV-Hop(distance vector-hop)算法、多向度量法(MDS)等。
这些方法大多通过几何方法实现，依赖于网络的拓扑结构，从而影响了定位精度。
距离相关定位算法一般先通过某种测距方法确定未知节点与初始锚节点的距离，然后根据这个距离利用三边关系、多边关系或边角关系等确定未知节点的位置。
测距方法有到达时间法(TOA)、到达时间差法(TDOA)、接收信号强度法(RSSI)等。
距离相关定位算法的定位精度依赖于测距的准确性，其测距误差可用测距的百分比来衡量。
依据到初始锚节点的跳数可以分为单跳定位和多跳定位，单跳定位算法如APIT定位算法，到达角定位算法[10]等。
多跳定位算法如DV-Hop(distance vector-hop)算法、迭代多边定位(iterative multilateration) 算法等。
单跳定位早于无线传感器网络的出现，是多跳定位的基本技术。
五、实验原理当网络的连通性较好时(每个节点至少有3个邻居节点)，设盲节点(xi，Yi)的周围有k个参考节点 (x1,y1)，(x2,y2)，(x3,y3)…(x4,Y4)，它们与盲节点(xi,yi)的之间的测距离为r,1,r2,r3,…,rk。
设(Xi,yi)的估计值为(x0,y0)。
参考节点到估计位置距离与测距之间的差异用fi（x0,y0）表示：求解如下最小二乘估计来获得最优的位置估计(x0, y0)：当矩阵A 是列满秩时可以得到如式所示的最小二乘解。
迭代多边定位过程如下：首先由预定的锚节点( 坐标给定) 通过式估计盲节点的坐标，然后将这些已定位的盲节点当作参考节点参与其他盲节点的定位，下一轮得到坐标的盲节点又可以做为参考节点参与其他盲节点的定位。
依次类推，式层层迭代运行，对网络中的所有盲节点进行定位( 如图1 所示) 。
图1 多边定位迭代运行在图1 中初始锚节点1 ，节点2 ，节点3可用来估计节点4 的位置，初始锚节点3 ，节点5 ，节点6 可用来估计节点7 的位置，节点 4 和节点7 当做参考节点，和节点 6 一起估计节点8 的位置。
当然节点8 可以当作参考节点去参与其他盲节点的定位。
六、实验实现本次使用C#语言来实现，详细源码看压缩包中工程文件。
节点类Node：using System;using System.Collections;using System.Collections.Generic;using System.Linq;using System.Text;namespace网络定位算法比较{class Node//节点类{//节点属性private int NodeID;//节点ID号private double realX;//节点的真实经度private double realY;//节点的真实纬度private bool IsBasic;//是否为锚节点private ArrayList arNode = new ArrayList();//索引器数组public void setID(int id){this.NodeID=id;}public int getID(){return this.NodeID;}public void setRealX(double realX){this.realX = realX;}public double getRealX(){return this.realX;}public void setRealY(double realY){this.realY = realY;}public double getRealY(){return this.realY;}public void setIsBasic(int a){if (a == 1)this.IsBasic = true;elsethis.IsBasic = false;}public bool getIsBasic(){return this.IsBasic;}public double X { set; get; }public double Y { set; get; }//索引器public Node this[int index]{get { return (Node)arNode[index];}set { arNode.Insert(index, value); }}}}迭代计算方法Calc()：public void Calc(int id, int num){//Node[] node = NodeList.ToArray();double[] nodeX= new double[num];//存放锚节点X坐标信息double[] nodeY= new double[num];//存放锚节点Y坐标信息double[] dist=new double[num];//存放距离信息int nodesum=0;//参与计算的节点数量，最大值为num-1for (int i = 1; i < 321; i++){if (distance[id, i] > 0 && NodeList[i - 1].getIsBasic() == true){nodeX[nodesum] = NodeList[i - 1].getRealX();nodeY[nodesum] = NodeList[i - 1].getRealY();dist[nodesum] =distance[id,i];nodesum++;}}Matrix MatrixA = new Matrix(num,2);//矩阵AMatrix Matrixb = new Matrix(num,1);//矩阵bfor (int s = 0; s < nodesum; s++){MatrixA[s,0]=2*(nodeX[nodesum-1]-nodeX[s]);MatrixA[s,1]=2*(nodeY[nodesum-1]-nodeY[s]);Matrixb[s, 0] = dist[s] * dist[s] - dist[nodesum-1] * dist[nodesum-1] - (nodeX[s] * nodeX[s] - nodeX[nodesum-1] * nodeX[nodesum-1]) - (nodeY[s] * nodeY[s] - nodeY[nodesum-1] * nodeY[nodesum-1]);}Matrix temp1 = MatrixA.Transpose();Matrix temp2 = temp1 * MatrixA;Matrix temp3 = temp2.Inverse();Matrix temp4 = temp3 * temp1;Matrix temp5 = temp4 * Matrixb;NodeList[id - 1].X = temp5[0, 0];NodeList[id - 1].Y = temp5[1, 0];NodeList[id - 1].setIsBasic(1);}迭代过程：bool flag=true;int tid, tcnt, cnt;while (flag){flag = false;tid = -1;tcnt = 0;for (int i = 1; i <= 320; i++){if (NodeList[i - 1].getIsBasic() == true)//||i!=124)continue;cnt = 0;for (int s = 1; s <= 320; s++)if (distance[i, s] > 0 && NodeList[s - 1].getIsBasic() == true){cnt++;//MessageBox.Show("1");}if (cnt > tcnt){tid = i;tcnt = cnt;}}if (tcnt >= 3){flag = true;Calc(tid, tcnt);}}七、实验结果展示及分析程序主界面展示导入节点信息误差计算如上图展示过程中一样，该程序初步完成实验要求。
在误差计算及分析模块中，可以看到在输入非锚节点124后，通过迭代多边式定位计算得出节点124的位置，存在误差但误差及其微小，可以忽略不计。
之所以取得较好的实验效果，是因为导入的节点信息和拓扑信息较全，未知节点周围存在较多的锚节点和计算后升级成的锚节点，误差较小。
实际生活过程中，锚节点分布并非均匀，而且迭代计算中计算量较大，当节点数目庞大时，会带来巨大的计算问题。
所以迭代式多边定位适合节点数目较少且节点拓扑信息完整的网络中。
八、实验小结通过本次试验，我掌握了多种网络定位算法，对迭代多边式定位算法有了更深入的了解。
除此之外，我还复习了部分线性代数的知识，矩阵运算方面借助网上查找到CMatrix.dll得以完成，极大地缩减了工作量。
本次实验中采用了我最熟悉的语言C#，重温了C#语言中的文件操作、匿名类型、索引器、自动属性等高级语言特性，使我的编程能力得到了提升。