基于最小误差平方和的无线传感器网络多边定位算法.docVIP

基于最小误差平方和的无线传感器网络多边定位算法 126传感器与微系统(Transducer andMicrosystem Technologies)xx年第33卷第7期基于最小误差平方和的无线传感器网络多边定位算法周海洋，余剑。 ，张卫涛(1电子工程学院电子线路教研室，安徽合肥230037；2解放军63758部队。 福建厦门361021)摘要多边定位算法是无线传感器网络节点定位中常用的定位算法。 针对相关文献提出的多边定位算法中盲节点坐标估计值和节点编号有关的问题，提出了一种基于最小误差平方和的多边定位算法。 不同的参考节点作为消元对象产生的误差平方和不同，通过选取误差平方和最小值来确定位置最优估计值。 结合CC2430芯片，设计了定位实验，并在上位机进行了数据分析。 实验结果表明该定位算法可以有效地降低定位误差，最大定位精度提高达到36m。 关键词多边定位算法；误差平方和；估计值TP391A1000-9787 (xx)07-0126-03M ultilaterallocalization algorithmfor wireless sensor worksbased onminimum error sum of squares ZHOUHaiyang，YU Jian，ZHANG Weitao(1Department ofElectronic Circuit，Electronic EngineeringInstitute，Hefei230037，China；263758Troops，PLA，Xiamen361021，China)AbstractMultilateral localization algorithm isa momalgor ithmfor wirelesssensor works(WSNs)node localizationAiming atproblems shownin relevantliteratures relatedto estimationvalue of blind nodecoordinate andnumber ofnodes inmultilateration algorithm，present amultilateral localization algor ithmbased onminimum errorsum of squaresError sum ofsquares generatedby different referencenode aselimination objectis different，and byselecting theminimum va lue oferrorsumof squaresto determihe optimal estimatedvalueof positionThe localization experiment isdesigned withthe chipof CC2430，and analyzedatas byupper PCThe experimental resultsshow thatthis algorithm canef fectivelyreduce localization error，the biggestlocalization precisionis increasedup to36mKey wordsmultilateral localizationalgor ithm；e rorsumof squares；estimated value0引言在无线传感器网络的各研究分支中，节点定位是无线传感器网络中的重要技术。 目前无线传感器网络节点定位方法主要分为两类基于测距的(rangebased)方法和非基于测距的(ra nge-free)方法?，基于测距的方法需要测量节点间的距离或者角度信息，然后使用三边测量、三角测量或者多边定位算法实现节点间的定位。 目前常见的测距技术包括接收信号强度指示(received signalstrength indication，RSSI)法、到达角(angle ofarriva l，AOA)法J、到达时间(time ofarriva l，TOA)法和到达时间差(time difference ofarriva l，TDOA)法J。 本文主要研究的是基于RSSI的定位算法。 这种方法是通过测出接收信号的场强值和已知的信道衰落模型及发xx-11-06射信号的场强值估算出收发信机节点之间的距离，根据多个距离值即能估计出目标的位置。 一般情况下，如果同时有3个参考发信机节点，就可以确定收信机节点的位置了。 基于RSSI的定位方法克服了TOA，TDOA和AOA方法需要额外的硬件设备的缺点，实现起来比较简单。 它首先需要确定待测环境下的信号传播模型的各个参数，然后便可根据定位目标接收到的参考点的接收信号强度计算出定位目标与参考点之间的距离，进而利用几何法计算出定位目标的位置。 多边定位算法是几何法中比较常用的一种算法，通过多个参考节点与定位节点之间的距离构建方程，通过最小二乘法求解，具有较高的定位精度，但是多边法也存在不足之处，构建方程过程中参考节点序号的选取会对定位精度产生一定影响。 本文通过对测距误差平方和的分第7期周海洋，等基于最小误差平方和的无线传感器网络多边定位算法127析，选取合适的参考节点序号，有效地提高了定位精度。 1基于RSSI的多边定位算法原理如图1所示，已知参考节点A，A2，A。 ，A4?的坐标为(，Y)，(，Y2)，(。 ，Y。 )，(，Y4)?。 设位置节点(盲节点)A。 坐标为(，Y。 )，参考节点与盲节点之间的测距距离为d。 ，d2，d3，d4?。 设盲节点的位置估计值为(，Y)，参考节点到估计位置的距离与测距之间的差异用式 (1)表示(，)=d一，i=1，2，3，?n (1)误差平方和记为F(，)=E (2)目前的常用的方法是通过最小二乘法来获取最优的位置估计，具体过程如下首先对公式 (2)处理得A如5。 图1多边定位算法原理图Fig1Principle diagramof multilaterallocalization algorithml一一n y一)，l，一2= (3)然后将第1个至第n-1个方程分别减去第n个方程(此处选取的是第n个方程作为消元中的被减方程)，后可得。 一)+2(yl-y)Y=一+一一+d一n)+2(Y2-Yn)y z2一+一一+ (4)；一。 一)2+2(一。 一y)y-x一一+一1一d一+写成线性方程的形式AX=口，其中A=-X2-y22Y-y，22y2I() (一)口鬣2222t x2口I zn d1一+一y一一+J(=c AA-1A曰c6元法由式 (1)得到了式 (5)，解式 (6)是式 (5)最小二乘解，但一般不是最小化估计均方误差平方和(式 (2)的最优估计值。 这一现象对最后的定位精度也会有影响。 3算法的提出针对多边定位算法存在的问题，本文提出一种基于最小误差平方和的多边定位算法，对于盲节点周围的n个参考节点，依次选取式 (3)中每个节点所对应的方程作为消元过程需要减去的对象，得到n个不同等式AX曰，这样?会得到n个不同的位置估计X=X，X2，?，代人式 (2)，可以得到n个误差平方和值F(墨)，F()，F(X3)，?，(X)，选取其中最小的误差平方和F(X)=r ainF()，F()，F()，?，(X)，最后根据最小误差平方和所对应的估计值作为盲节点的最终坐标。 4实验结果与分析本文研究的是以RSSI测距为基础的多边定位算法，实验使用TI公司的无线收发芯片CC2430完成固定节点和待定节点间的通信以及RSSI的采集。 CC2430有一个内置的RSSI，其数字值为8位有符号的二进制补码，可以从寄存器位RSSILRSSI VAL读出。 在基于RSSI测距实验中，信号衰减模型一般简化为RSSI一(10nlgd+A)， (7)式中n为信号衰减因子，范围一般为2-5；d为定位节点与参考节点之间的距离，单位为m；A为定位节点与参考节，、，【，(，128传感器与微系统第33卷点之间的距离，d为1m时测得的信号功率。 实验中，测得n为35，A为40dBm。 实验场景是选择在学校操场的空旷区域，区域大小为15m15m，4个参考节点放置在正方形区域的4个角落。 如图2所示。 ，m图2实验场景(15m x15m)Fig2Experimental scelle实验结果以(5，5)m，(5，10)m，(10，5)m，(10，10)m为例，分别分析了4个参考节点分别作为消元对象时所产生的误差平方和值和定位精度，本文选取测试坐标和实际坐标之间的欧氏距离作为定位精度量值。 以盲节点实际位置为(5，5)m为例，从图3可以看到当4谚考节点作为消元过程对象时，误差平方和最小，此时对应定位精度也最高。 图 4、图 5、图6同样显示了误差平方和最小的对应的参考节点作为消元对象时，定位精度是最高的。 g、11O董86登2O消元对应的参考节点消元对应的参考节点()误差平方和(b)定位误差(a)error SUmofsquares(b)localization elTor图3盲节点位于(5，5)m误差平方和和定位误差Fig3Error samofsquares and localization error at5，5)m l0量86鹭20消元对应的参考节点消元对应的参考节点(a)误差平方和(b)定位误差(a)e rorsum ofsquares(b)localization glTOr图4盲节点位于(5。 10)m误差平方和和定位误差Fig4Er ror SUmofs quaresandlocalizat ionerror o f blindnode a t(5，10)m如表1，不同的参考节点作为消元对象会产生不同的定位误差。 最大的定位误差34m左右，而最小误差平方梃、椒lO点86鹭2O消元对应的参考节点消元对应的参考节点(a)误差平方和(b)定位误差(a)elTor sum ofsquares(b)localization error图s盲节点位于(10，5)m误差平方和和定位误差F5Error sumofsquares and localizationerror o fblindno dea t(10，5)Ill108642消元对应的参考节点消元对应的参考节点(a)误差平方和(b)定位误差a)e rorsumofsquaresb)localizationerror图6盲节点位于(10。 10)m误差平方和和定位误差Fig6Error sumofsquaresandlocalizationerrorof blindno deat(10，10)m和对应的参考节点作为消元对象所产生的的定位精度明显提高，以本文实验的4个定位位置为例，最大定位精度可达到36m。 表1定位精度对比表Tab1Com parisonof localization precision5结论本文在结合文献分析多边定位算法基础上，提出了基于最小误差平方和的多边对位算法，根据不同参考节点作为消元对象产生的误差平方和，选取合适的参考节点作为消元对象，这种方法对于提高定位精度有较好的效果。 以实验中的参考位置为例，定位精度最大可提高36m。 但是该方法性能的提高是以牺牲计算复杂度为代价实现的，因此，这种更适合对于计算复杂度要求不高的定位场景。 参考文献1Mao Guoqiang，Fidan B，Anderson BD0Wireless sensor -works localizationtechniquesJComputer Networks，xx，51 (10)2529-25532王琦基于无线传感器网络的室内定位技术研究与实现D西安西安电子科技大学，xx11-15(下转第132页)132传感器与微系统第33卷recognition inparts fromsingl edepth imagesCxxIEEE Conference on ComputerVision andPattern Recognition(CVPR)，201I1297-13046Schwarz A，Mkhi taryanA，Mateus D，et a1Human skeletontracking fromdepth datausing geodesicdistances andoptica lf lowJIma geand VisionComputing，xx，30 (3)2172267Zheng Xiao，Fu Mengyin，Yang Yi，et a13D Humanpostures recog nitionusing KinectCxx4th Inter national Conferenceon IntelligentHumanMachine Systemsand Cyberics(IHMSC)，xx344-3478Penny JS，David JB，Steven B，et a1A studyto evaluatea lowcost virtual reality system for home-based rehabilitation of theup-per limbfollowing strokeJInter nationalJourna lon Disabilityand HumanDevelopment，xx，10 (4)337-3419Stone EE，Skubic MEva luationof aninexpensive depthcamera forpassive inhome fallrisk assessmentCxx5th Internationa lConfer enceOil PervasiveComputing Technologiesfor Healtheare(Perva siveHealthxx)，xx71-7710Huang JDKinerehabA Kinectba sedsystemforphysical rehabilitation apilot studyfor youngadults withmotor disabilitiesCProceedings ofthe13th International ACMSIGACCESS Conferenceon Computers andAessibility，xx319-32011Lange B，Chienyen Chang，Suma E，et a1Development and c一)(上接第125页)6Ammari HM，Das SKCentralized and clusteredk-coverage pro-tocols forwir elesssensorworksJIEEE TransactionsonComputers，xx，61 (1)118-1337任彦，张思东，张宏科无线传感器网络中覆盖控制理论与算法J软件学报，xx，17 (3)4224338林祝亮，冯远静基于粒子群算法的无线传感器网络覆盖优化策略J计算机仿真，xx，26 (4)1901939李燕君，潘建无线传感器网络的节点智能部署方法研究J计算机科学，xx，39 (8)115-118，13510王瑞琪，张承慧，李珂基于改进混沌优化的多目标遗传算、(上接第128页】3章坚武，张璐基于Zig Bee的RSSI测距研究J J传感技术学报，xx，22 (2)285-2884Pat wariN，Hero AO，Perkins M，et a1Relative locati on estima-tion inwirelesssensorworksJIEEE Tansactionson SignalProcessing，xx，51 (8)2137-21485Priyanath NB，Chakraborty A，Ba lakrishnaHThe cricket locationsuppor tsystemcProceedi ngof Mobile Computing and Networking，Boston，ACM，20003243-一6Niculescu D，Nath BAd Hoepositioning system(APS)using valuationof lowcost gamebased balancerehabilitation toolusing theMicrosof tKineet sensorCxx33rd AnnualInter nationalConference ofthe IEEEEnneef ingin Medicineand BiologySociety，xx1831-183412Yeh SC，HwingW Y，Hua ngTC，eta1A studyf orthe applicationofbody sensingin assistedrehabilitation trainingCxxInternationalSymposium onComputer，Consumer andControl，IS3Cxx，xx922-92513Da GanaA，Chaves T，Figueiredo L，et a1PosterImproving motorrehabilitation processthrough ana turalinteraction basedsystem usingKinect sensorCxxIEEE Symposiumon3D UserInterfaces(3DUI)，xx145-14614Ra bejaL J，Chaudhary A，Singa lK，et a1Tracking off ingertips andcenters ofpalm usingKinectCxxT hirdInternational Conferenceon ComputationalIntelligence，Modelling andSimulation，xx248-252fl5Satyavolu S，Bruder G，Willemsen P，et a1Aua ly