无线传感器网络的定位摘要无线传感器网络节点自身定位至关重要,在军事和民用领域中有着广泛的应用前景.目前的定位算法主要分为两种类型,即基于距离的定位算法和距离无关的定位算法.这两种类型的算法各有优势和不足.考虑了两种算法的优缺点,为了有效抑制复杂环境对无线传感器网络节点定位精度的影响,以三边定位算法为基础,提出了三边质心定位法, DV-HOP改进法两种较为精确的改进算法.对于问题一,为了改进三边测距法,我们引进质心法,建立基于三边测距法、质心法的三边质心定位法(通过计算相交圆的交点,在每两个圆相交产生的两个交点中找到与另一个圆距离较小的点,共可找到三个点,用这三点所确定的区域的质心来估计未知节点的坐标),在此基础上我们继续运用加权补偿法,对区域定位误差加以考虑,求得更准确的未知节点的坐标.对于问题二,我们采用DV-HOP改进法,首先确定各节点之间的最小跳距即最小跳数,由此估算出各节点之间的距离,再结合三角测量法,三边算法,多次计算取平均值,最终确定各未知节点的坐标.对于问题三:针对本问,我们采用三边测量法、三边质心定位法、DV-HOP测量法,分别对已知仿真算例中的未知节点进行定位运算,同时借助MATLAB软件进行求解,最后得出由未知节点实际坐标,结果见附表二.对于问题四,首先,我们将通过三种方法求出的各未知节点坐标值与附件中所给出的数据进行对比观察,然后由此总结分析三种方法的合理性和优缺点,比较三种算法的优劣.鉴于所给出的三种算法,基于本问题所给出的信息量(未知节点到周围三个信标节点的距离,各信标节点的坐标,各未知节点的真实坐标,仿真算例),DV-HOP改进法所得结果较为精确.关键词:无线网络定位三边质心定位法加权补偿法DV-HOP改进法一、问题重述随着科技发展,物联网已成为新一代信息技术的重要组成部分,它通过各种信息传感设备,实时采集光、声、热、电、力学、化学、生物、位置等各种信息,与互联网结合形成的一个巨大网络.无线传感器网络(WSN, Wireless Sensor networks),作为物联网的重要组成部分,通过无线通信方式形成的一个多跳自组织网络.无线传感器网络的很多应用场合必须知道节点的位置,因此节点定位技术是WSN 的关键技术和研究热点.然而,在所有节点上都配备GPS 等定位设施成本很高.因此,一般只在部分节点通过GPS 定位设备获得自身的精确位置,这些节点称为信标节点(beacon node);而其它未知节点(unknown node)则通过网络连接信息和节点内部相互测距通过几何计算来估计其位置坐标.RSSI 是一种测距相关的定位技术,它通过接收到的信号强度测定信标节点(,)i i x y 与未知节点的距离i d ,进而根据某种算法计算未知节点的坐标(,)x y .三边测量法是WSN 自定位算法中的一种易于实现,开销小的定位算法.具体算法如下:根据两点之间的距离公式可列以下方程组:⎪⎪⎩⎪⎪⎨⎧=-+-=-+-=-+-232323222222212121)()()()()()(d y y x x d y y x x d y y x x 解方程得:'1)(B A A A X T T -= ⎥⎦⎤⎢⎣⎡----=)(2)(2)(2)(232323131y y x x y y x x A ⎥⎥⎦⎤⎢⎢⎣⎡-+-+--+-+-=222323222322212323212321d d y y x x d d y y x x B ⎥⎦⎤⎢⎣⎡=y x X 即:未知节点的坐标.由于实际环境中信号强度测定存在误差,导致测量距离d 存在随机误差,三边测量法的定位误差较大.故对以下问题进行解答:1、 给出三边测量法的改进模型算法;2、 查阅相关资料,提出一种新的定位模型算法;3、 分别用三边测量法和问题1、2给出的新方法对下图给出的仿真算例中的未知节点进行定位;4、 根据附件所给出的数据,分析三种方法的合理性和优缺点,比较三种算法的优劣.二、问题分析问题1属于模型改进问题,因此,我们首先应该找出原模型中的不足,即:在三边测距算法中没有考虑到特殊情况,也就是如果出现无解情况时将无法求出未知节点坐标,所以,我们将质心定位算法的思想引入到三边测距算法中,通过计算相交圆的交点,找到与两个圆交点与另一个圆距离较小的三点,在这三点所确定的区域的质心来估计未知节点,在此基础上我们继续运用加权补偿模型,对区域定位误差加以考虑,求得更准确的未知节点D的坐标.问题2是属于创新模型类型的数学问题,解决这类问题时,首先,我们通过查阅相关资料了解在每一步可用的各种算法的基础上,选取了一种可行的算法,即DV-HOP改进法,并在原算法的基础上进行改进,使其测距及求解的结果更加精准. 由于本题的附件中对于每个未知节点仅给出了与相邻的三个信标节点的距离,为了测量准确,我们通过确定计算未知节点和每个信标节点的最小跳数及最小跳距,估算出未知节点到任意信标节点的距离,从而多次利用三角测量法确定质心,建立出更加准确的模型.问题3要求我们分别用三种方法对35个未知节点进行定位.三边测量法计算过程中,我们利用给出矩阵对其进行求解,得出35个点的测量坐标,并结合实际坐标绘出坐标图及各点误差图.问题4首先我们对附表中给出的数据与我们在第三问中所求的值进行对比,并运用MATLAB绘制出各种模型所求数值与附表三中给出的数值对比图,然后通过观察对比,总结分析三种方法的合理性和优缺点,比较三种算法的优劣.三、模型假设1、无线传感器网络中参考节点位于未知节点的外侧,并且全网中存在的参考节点多于3个2、无线传感器节点布设均匀,不存在节点分布的大面积密集区域或大面积空白区域3、在DV-HOP改进法中用信标节点间的直线距离代替曲线距离四、符号说明,n, A的质心0n每跳的平均跳距未知节点与某个信标节点的,x y e e 1c x五、模型建立及求解5.1对三边测距算法的改进5.1.1基于三边测距算法和质心算法的三边质心定位法三边质心定位法将质心定位算法思想引入到三边测距算法中,通过计算相交圆的交点及由交点组成区域的质心来估计未知节点,使估算出的未知节点坐标准确度提高.三边测距算法的实现设未知节点D 的坐标(,)d d x y ,A, B , C 3个信标节点的坐标分别为(,)a a x y ,(,)b b x y ,(,)c c x y ,它们到 D 的距离分别为,,ad bd cd d d d . 则可得如下方程组:222222222()()()()()()a a ad b b bd c c cd x x y y d x x y y d x x y y d ⎧-+-= (1)⎪-+-= (2)⎨⎪-+-= (3)⎩式 (1)减式 (3) ,式 (2)减式 (3)后联立方程2222222222222()2()2()2()a c a c a c a c cd adb c b c b c b c cd bdx x x y y y x x y y d d x x x y y y x x y y d d ⎧-+-=-+-+-⎪⎨-+-=-+-+-⎪⎩ 可解得 D 点的坐标(,)d d x y .三边测距算法确定未知节点的坐标的思想可用图 1来表示.图1由于三边测距算法基于两条直线的交点来估算未知节点的坐标,没有充分利用 A, B , C 3个节点的坐标信息,使估算的未知节点的坐标可能存在比较大的误差.在图2,图3的情况下,根据(1)(2)(3)式可解出圆 A 与圆 C 的交点1ac M 1,1()ac ac x y ，2ac M 2,2()ac ac x y ,圆 B 与圆 C 的交点1bc M 1,1()bc bc x y ,2bc M 2,2()bc bc x y ,圆 A 与圆 B 的交点1ab M 1,1()ab ab x y ,2ab M 2,2()ab ab x y .通过将圆 A 与圆C 交点1ac M 1,1()ac ac x y ，2ac M 2,2()ac ac x y 代入式2222()()x x y y -+-,判断大小可找出两点距圆 B 的圆心较近的点,假设为1ac M 1,1()ac ac x y .同理可找出圆 B ,圆 C 交点中距圆 A 较近的点设为1bc M 1,1()bc bc x y ,圆 A,圆 B 交点中距圆 C 的圆心较近的点设为2ab M 1,1()ab ab x y .依据质心思想估算未知节点D 的坐标为111111(,)(,)33ac ab bc ac ab bc d d x x x y y y x y ++++= (4).5.1.2加权补偿法模型 如图2所示, 12A , A ,, A i 为信标节点,B 为未知节点.由于信标节点通常也具备通过RSSI 测距的功能,所以可以将信标节点0A 作为未知节点,0A 可以通过信标节点111222A (,), A (,),, A (,)i i i x y x y x y 的信息来计算自身的坐标,然后和实际位置比较得出信标节点000A ( x , y )的坐标误差, 该误差表示信标节点所在的区域的定位误差.当真正的未知节点B 处于信标节点0A 所在区域时,由于二者定位过程的环境和采用的信标节点大致相同(未知节点B 在定位过程中还用到了信标节点0A ),所以相信二者具有相同的定位误差.当未知节点B 定位时,对上述误差进行补偿,从而提高未知节点的定位精度.未知节点B 和信标节点0A 的距离越小,上述误差补偿机制就越准确.同理,网络中的其他信标节点,也可以计算自身的坐标误差.图2从上述分析可知,要想对未知节点的定位误差进行补偿首先需要获得信标节点的坐标误差.获得信标节点坐标误差的过程中, 由于取不同的3个信标节点做三边定位也会得到不同的测量值,需要用这些测量值来得到最终的信标节点A0的计算坐标.本文采用加权质心算法来计算信标节点的计算坐标.如图3所示假设0102030n ,A ,A ,,A A 为0A 坐标的多个不同测量值;0A 为01A ,02A ,03A …0n A 的质心;12,,,n d d d 为坐标0A 到坐标0102030n ,A ,A ,,A A 的距离.定义1:信标节点的计算坐标11(5)ni i i ni ii x x y yρρ==⎧=⎪⎪⎨⎪=⎪⎩∑∑ 式中,11(6)1i nj j jd d ρ==∑为加权因子,表示坐标oi A 的权重,离质心0A '的距离越近,所占的权重就越大;i x 为oi A 的X 坐标值,i y 为oi A 的Y 坐标值.所以信标节点的坐标误差为(7)x cyc e x x e y y =-⎧ ⎨=-⎩ 式中,x 为信标节点X 坐标实际值;c x 为信标节点计算坐标X 值;y 为信标节点Y 坐标实际值;c y 为信标节点计算坐标Y 值.信标节点的坐标误差反映了系统针对该节点附近区域的定位能力.然而定位系统实际应用过程中,未知节点B 不一定正好处于某个信标节点附近,而是可能离各个信标节点距离相当,所以并不能按照理想情况直接只用0A 的坐标误差去补偿未知节点B 的坐标误差.但是,每个信标节点所在区域的定位误差都可以通过信标节点坐标误差来反映,综合考虑所有信标节点坐标误差就可以得到由信标节点所构成的区域的定位误差,只要未知节点B 处于该区域内,其坐标误差可以用该误差进行补偿.这里的区域大小需根据网络不同的精度要求和节点密度来具体设定.如图2所示,当未知节点B 处于由信标节点12A , A ,, A i 构成的区域时,先通过RSSI 值计算出这些信标节点和自身的距离,然后综合各个信标节点的的坐标误差可以得出未知节点所在区域的定位误差. 定义2:未知节点校正误差11()(8)()mx j xj j my j yjj e e e e ωω==⎧=⨯⎪⎪⎨⎪=⨯⎪⎩∑∑ 其中,11(9)1j mcl j cld d ω==∑是加权因子,表示信标节点j A 的坐标误差对未知节点校正误差的决定权,从前文分析可知,信标节点j A 离未知节点的距离越近,所占的权重越大.m 为用于坐标校正的信标节点个数.所以未知节点D 最终坐标为11(10)c xc yx x e y y e ⎧=+⎪ ⎨=+⎪⎩ 式中,1c x 为未知节点加权质心法计算的X 坐标;1c y 为未知节点加权质心法计算的Y 坐标.将质心算法所求的未知节点D 的坐标代入式(10)中,即可更准确地估计出未知节点D 的坐标.5.2新的定位模型算法:DV-HOP 改进法5.2.1计算未知节点与每个信标节点的最小跳数信标节点以广播方式向邻居节点发送包括跳数字段的自身位置信息元组,跳数字段的初值设为0,接收节点接收到该信息元组后将跳数加1并记录下该信标节点的位置和跳数,将该元组转发给它的邻居节点.若节点接收到多个来自于同一信标节点的元组,则节点只保留跳数最小的元组信息.通过这种方法网络中每个节点都能够记录下自己到每个信标节点的最小跳数,并获得信标节点的位置信息. 5.2.2计算未知节点与信标节点的平均跳段距离通过第一阶段,每个信标节点可获得其他信标点的位置信息和最小相隔跳数, 由于信标节点间的距离已知,可利用式估算出每跳的平均跳距:1j jj iH h =≠=∑其中(,)i i x y ,(,)j j x y 是信标节点的坐标,i h 是信标节点,i j 的最小跳数.当信标节点计算出平均跳距后, 以广播的方式将最小跳距发送给网络中所有节点.未知节点收到平均跳距后,乘以自己记录的跳数,计算出到该信标节点的距离.如图4,A,B,C 是信标节点,D 是一个待定位的未知节点.三个信标节点间距离已确定,分别是28.9128,24.6364,24.2668,A 接收到B 、C 的最小跳数是分别是 3,3 .则A 的最小跳距是(28.912824.6324)8.92426+=.同理,B 、C 的最小跳距分别是10.6359, 9.7806.由于节点D 到A,B,C 的跳数分别是1,2,2,则节点D 到A,B,C 的距离分别估算为8.924218.9242⨯=, 11.311812.998710.6359320.708311.311812.998713.1270+⨯⨯=++11.311811.47519.7806318.209511.311811.475113.9270+⨯⨯=++.可得到综合模型为:121212()(12)1(13)(14)i j j j j nij j d H n d d d d d d d d d d d ωω=⨯⨯+++ =+++++=+++其中i d 为未知节点与某个信标节点的估算距离,H 为每跳的平均跳距,n 为一个信标节点接收到另外两个信标点的最小跳数,j ω为加权因子,ij d 为未知节点到所对应信标点的实际距离. 5.2.3计算自身位置未知节点获得与多个信标节点的估算距离后,以与未知节点距离较近的信标节点中的三个为一组,应用三角测量法求出其坐标,最后取平均值.图5如图5所示,A 、B 、C 三个信标节点的坐标分别为(,),(,),(,)a a b b c c x y x y x y ,未知节点D 相对于节点A 、B 、C 的角度分别为:∠ADB ,∠ADC ,∠BDC ,假设未知节点D 的坐标为(,)d d x y .对于节点A 和C 以及∠ADC ,如果AC 在△ABC 内,则唯一能够确定一个圆,设圆心为111(,)o o O x y ,半径为1r ,则1AO 22ADB απ∠-∠＝B ＝（）,并存在如式(15)所示公式:112211(15)22cosrrr rα⎧=⎪⎪=⎨=-由式(6.4)应用MATLAB就能够确定圆心O1的坐标和半径1r.同理,可以确定相应的圆心和半径.最后根据三边测量算法⎪⎪⎩⎪⎪⎨⎧=-+-=-+-=-+-232323222222212121)()()()()()(dyyxxdyyxxdyyxx解方程得:'1)(BAAAX TT-=⎥⎦⎤⎢⎣⎡----=)(2)(2)(2)(232323131yyxxyyxxA⎥⎥⎦⎤⎢⎢⎣⎡-+-+--+-+-=222323222322212323212321ddyyxxddyyxxB由11122233(,),(,),(,)o o o o o oO x y O x y O x y,最终确定D(,)d dx y的坐标.5.3用三种算分别进行求解采用三边测量法时,我们首先将三十五组数据分别代入方程,进行求解,得到三十五个未知节点的测量坐标.对于三边质心定位法,DV-HOP加权法,我们将数据分别代人,依据所给出的计算方法,对其分别求解,部分数据如下(全部数据见附录):三边测量法:横坐标x i28.8082 8.7543 13.7998 14.336 2.817 23.9412 4.7875 16.102 纵坐标y i76.4452 84.8894 94.9097 69.2593 57.9941 42.1071 30.0939 17.5076 三边质心定位法:横坐标x i28.9123 8.589 13.9923 14.4465 3.0273 23.7832 4.9852 16.0912 纵坐标y i76.6781 84.7765 95.003 69.2789 57.882 42.0731 30.0273 17.5823 DV-HOP加权法:横坐标x i28.7045 7.5201 13.9034 14.0148 3.8341 23.2491 6.2201 14.7072 纵坐标y i74.945 83.736 95.3021 67.3902 57.8302 40.6433 29.5284 17.0301 5.4通过数据进行模型评价首先我们对附表中给出的数据与我们在第三问中所求的值进行对比,并运用MATLAB绘制出各种模型所求数值与附表三中给出的数值对比图,如下:三边测量法求得点坐标与实际点坐标对比图三边测量法求得点坐标与实际点坐标误差图三边测量法求得点坐标与实际点坐标对比图三边质心定位法求得点坐标与实际点坐标误差图DV-HOP改进法求得点坐标与实际点坐标对比图DV-HOP改进法求得点坐标与实际点坐标误差图已知的信息较少,且所测得未知节点与信标节点之间的距离都比较准确时,可以直接采用三边测量法;当已知的信息较少,且所测得未知节点与信标节点之间的距离误差较大时,可以采用三边质心定位法,并结合加权补偿法,对节点所在区域的坐标误差加以考虑;当所给出的点相对较多,且很密集时,可以采用DV-HOP改进法.鉴于所给出的三种算法,基于本问题所给出的信息量(未知节点到周围三个信标节点的距离,各信标节点的坐标,各未知节点的真实坐标,仿真算例),DV-HOP改进法所得结果较为精确.参考文献[1]方红雨,崔逊学.无线传感器网络的定位问题综述,电脑与信息技术,2005,13(6):1-6;[2]周小波,乔钢柱,曾建潮.无线传感器网络中基于RSSI的加权DV-HOP定位方法,计算机工程与应用,2011,47(14):2-3;[3]周立君,刘宇.基于RSSI 的无线传感器网络节点定位技术研究,电子测量技术,2010,33(8);[4]赵昭,陈小慧.无线传感器网络中基于RSSI的改进定位算法[J].传感器技术学报,2009,22(3):391-392;[5] 刁在筠,刘桂真,宿洁,马建华.运筹学,北京:科学出版社,2004;[6]江世宏.MATLAB语言与数学实验,北京:科学出版社,2007.附件附件一参考程序:>> x1=59.793;>> y1=52.193;>> x2=50.576;>> y2=19.444;>> x3=33.525;>> y3=41.082;>> d1=14.886;>> d2=19.637;>> d3=17.379;>> A=[2*(x1-x3),2*(y1-y3);2*(x2-x3),2*(y2-y3)];B=[x1^2-x3^2+y1^2-y3^2+d3^2-d1^2;x2^2-x3^2+y2^2-y3^2+d3^2-d2^2]; X=inv(A'*A)*A'*BX =51.237239.4336>> x1=59.793;y1=52.193;>> x2=33.525x2 =33.5250>> y2=41.082;>> x3=55.184;>> y3=65.936;>> d1=15.381;>> d2=13.853;>> d3=20.531;>> A=[2*(x1-x3),2*(y1-y3);2*(x2-x3),2*(y2-y3)];B=[x1^2-x3^2+y1^2-y3^2+d3^2-d1^2;x2^2-x3^2+y2^2-y3^2+d3^2-d2^2]; X=inv(A'*A)*A'*BX =45.148948.1974>> x1=45.507;y1=89.035;>> x2=55.184;>> y2=65.936;>> x3=65.783;>> y3=92.836;>> d1=11.209;>> d2=32.035;>> d3=14.034;>> A=[2*(x1-x3),2*(y1-y3);2*(x2-x3),2*(y2-y3)];B=[x1^2-x3^2+y1^2-y3^2+d3^2-d1^2;x2^2-x3^2+y2^2-y3^2+d3^2-d2^2]; X=inv(A'*A)*A'*BX =52.578197.9151>> x1=45.507;y1=89.035;x2=55.184;y2=65.936;x3=65.783;y3=92.836;>> d1=16.619;>> d2=14.536;>> d3=13.374;>> A=[2*(x1-x3),2*(y1-y3);2*(x2-x3),2*(y2-y3)];B=[x1^2-x3^2+y1^2-y3^2+d3^2-d1^2;x2^2-x3^2+y2^2-y3^2+d3^2-d2^2]; X=inv(A'*A)*A'*BX =60.066380.1532>> x1=78.226;>> y1=73.538;>> x2=55.184;y2=65.936;x3=65.783;y3=92.836;>> d1=13.672;>> d2=35.189;>> d3=17.592;>> A=[2*(x1-x3),2*(y1-y3);2*(x2-x3),2*(y2-y3)];B=[x1^2-x3^2+y1^2-y3^2+d3^2-d1^2;x2^2-x3^2+y2^2-y3^2+d3^2-d2^2];X=inv(A'*A)*A'*BX =83.651287.5213附件二三种算法全部结果未知节1 2 3 4 5 6 7 8点i三边测量法:横坐标x i28.8082 8.7543 13.7998 14.336 2.817 23.9412 4.7875 16.102 纵坐标y i76.4452 84.8894 94.9097 69.2593 57.9941 42.1071 30.0939 17.5076三边质心定位法:横坐标x i28.9123 8.589 13.9923 14.4465 3.0273 23.7832 4.9852 16.0912 纵坐标y i76.6781 84.7765 95.003 69.2789 57.882 42.0731 30.0273 17.5823 DV-HOP加权法:横坐标x i28.7045 7.5201 13.9034 14.0148 3.8341 23.2491 6.2201 14.7072 纵坐标y i74.945 83.736 95.3021 67.3902 57.8302 40.6433 29.5284 17.0301未知节910111213141516点i三边测量法:横坐标x i25.05297.736131.541638.170951.237245.148946.176639.7083纵坐标y i 5.5002 6.6417.341129.157939.433648.197460.971476.4329三边质心定位法:横坐标x i25.10327.732131.567238.327851.202145.367846.008139.7134纵坐标y i 5.2971 6.023817.389229.893239.227848.003260.337676.3289 DV-HOP加权法:横坐标x i25.1078.04733.63438.038150.832146.82146.920337.8725纵坐标y i17 5.11315.782328.564241.830348.903458.380174.9388未知节1718192021222324点i三边测量法:横坐标x i54.4152.578160.066383.651287.046861.01978.971567.2212纵坐标y i0.563897.915180.153287.521389.089953.65258.55671.5994三边质心定位法:横坐标x i49.239752.618759.935783.337987.362869.324579.002167.0231纵坐标y i39.27397.812380.1687.440889.562158.783258.44171.5589DV-HOP加权法:横坐标x i53.819952.08458.27181.89389.44473.740179.450365.4861纵坐标y i50.721896.802380.283485.920290.8760.82457.83270.2207未知节2526272829303132点i三边测量法:横坐标x i71.863679.934893.577186.58195.008177.734864.410965.7193纵坐标y i48.508640.275635.953112.76587.146213.417427.772535.5503三边质心定位法:横坐标x i71.839279.982593.442186.91295.102877.760164.448765.9871纵坐标y i48.503240.206736.012312.73717.013213.402127.321935.668 DV-HOP加权法:横坐标x i72.639578.24991.13288.34296.820178.739167.812866.461纵坐标y i49.803638.91335.30811.448 5.98314.93725.743935.6391未知节333435点i三边测量法:横坐标x i27.426327.287520.5485纵坐标y i27.032652.775158.7658三边质心定位法:横坐标x i27.091227.313120.4481纵坐标y i27.276652.660158.7125DV-HOP加权法:横坐标x i27.30228.304521.943纵坐标y i26.920451.903459.3107。