一种基于FCM的DV-HOP定位算法.pdf
《一种基于FCM的DV-HOP定位算法.pdf》由会员分享,可在线阅读,更多相关《一种基于FCM的DV-HOP定位算法.pdf(9页珍藏版)》请在咨信网上搜索。
1、第 卷 第期 年月西安邮电大学学报J OUR NA LO FX I ANUN I V E R S I T YO FP O S T SAN DT E L E C OMMUN I C A T I ON SV o l N o M a r d o i:/j i s s n 一种基于F CM的D V HO P定位算法孙爱晶,李益佳(西安邮电大学 通信与信息工程学院,陕西 西安 )收稿日期:基金项目:国家自然科学基金项目(U )作者简介:孙爱晶(),女,教授,从事物联网技术及智能教育信息技术研究.E m a i l:s u n a i j i n g x u p t e d u c n李益佳(),女,硕士
2、研究生,研究方向为信息与通信工程.E m a i l:l i y i j i a c o m摘要:对锚节点稀少且未知节点分布不均匀的定位环境下距离矢量跳数(D i s t a n c eV e c t o rH o p,D V HO P)定位算法定位误差大的问题进行研究,提出一种基于模糊C 均值(F u z z yC m e a n s,F CM)的D V HO P定位算法.在D V HO P定位算法中引入F CM算法将锚节点进行分簇并提出分簇策略,未知节点则按照设定的算法流程选择入簇,在通过簇内定位后进行簇间坐标的融合从而实现全局定位.为了验证基于F CM的D V HO P定位算法的有效性,
3、将所提算法与D V HO P定位算法、基于粒子群的D V HO P(D V HO Pf o rP a r t i c l eS w a r m O p t i m i z a t i o n,P S O D V HO P)定位算法以及基于几何改进的D V HO P(I m p r o v e dD V HO P,I D V HO P)定位算法等种算法对比.仿真结果表明,基于F CM的D V HO P定位算法与其他种定位算法相比,其平均定位误差分别降低了、与,能更好地适应不均匀的节点分布环境.关键词:无线传感器网络;节点定位;距离矢量跳数定位算法;模糊C 均值算法;最小二乘法中图分类号:TN 文
4、献标识码:A文章编号:()D V H o pp o s i t i o n i n ga l g o r i t h mb a s e do nF CMS UNA i j i n g,L IY i j i a(S c h o o l o fC o mm u n i c a t i o n sa n dI n f o r m a t i o nE n g i n e e r i n g,X ia nU n i v e r s i t yo fP o s t sa n dT e l e c o mm u n i c a t i o n s,X ia n ,C h i n a)A b s t r a
5、 c t:T h ep r o b l e mo f l a r g ep o s i t i o n i n ge r r o ro fd i s t a n c ev e c t o rh o p(D V HO P)p o s i t i o n i n ga l g o r i t h mi nt h ep o s i t i o n i n ge n v i r o n m e n to ff e wa n c h o rn o d e sa n du n e v e nd i s t r i b u t i o no fu n k n o w nn o d e s i ss t u
6、d i e d,a n daD V HO Pp o s i t i o n i n ga l g o r i t h mb a s e do n f u z z yC m e a n s(F CM)i sp r o p o s e d I nt h eD V HO Pp o s i t i o n i n ga l g o r i t h m,t h eF CMa l g o r i t h mi s i n t r o d u c e d t oc l u s t e r t h ea n c h o rn o d e sa n dac l u s t e r i n gs t r a t
7、e g y i sp r o p o s e d T h eu n k n o w nn o d e sa r es e l e c t e d i n t ot h ec l u s t e ra c c o r d i n gt ot h eg i v e na l g o r i t h mp r o c e s s,a n dt h e nt h ec o o r d i n a t e sb e t w e e nt h ec l u s t e r sa r ef u s e da f t e rp o s i t i o n i n g i nt h ec l u s t e r
8、 t oa c h i e v eg l o b a l p o s i t i o n i n g I no r d e r t ov e r i f yt h ee f f e c t i v e n e s so f t h eD V HO Pp o s i t i o n i n ga l g o r i t h mb a s e do nF CM,t h ep r o p o s e da l g o r i t h mi s c o m p a r e dw i t ht h eDV HO Pp o s i t i o n i n ga l g o r i t h m,t h eD
9、V HO Pp a r t i c l es w a r m o p t i m i z a t i o n(P S ODV HO P)p o s i t i o n i n ga l g o r i t h m,a n dt h eDV HO P(I m p r o v e dDV HO P,I DV HO P)p o s i t i o n i n ga l g o r i t h m b a s e do ng e o m e t r i c i m p r o v e m e n t T h es i m u l a t i o nr e s u l t ss h o wt h a t
10、 t h eDV HO Pp o s i t i o n i n ga l g o r i t h mb a s e do nF CMr e d u c e s t h ea v e r a g ep o s i t i o n i n ge r r o rb y,a n d c o m p a r e dw i t ht h eo t h e rt h r e ep o s i t i o n i n ga l g o r i t h m sr e s p e c t i v e l y,w h i c hc a nb e t t e ra d a p tt ot h eu n e v e
11、nn o d ed i s t r i b u t i o ne n v i r o n m e n t K e y w o r d s:w i r e l e s ss e n s o rn e t w o r k;n o d ep o s i t i o n i n g;d i s t a n c ev e c t o rh o pp o s i t i o n i n ga l g o r i t h m;f u z z yC m e a n sa l g o r i t h m;l e a s t s q u a r e s第 卷第期孙爱晶,等:一种基于F CM的D V HO P定位算
12、法无线传感器网络(W i r e l e s sS e n s o rN e t w o r k,WS N)现在已 经广泛应用 于各个 领 域.在WS N中,传感器节点对覆盖范围内的对象进行信息的采集和传播 .如果传感器节点的位置不明确,得到的信息价值将会降低.因此,WS N中节点的定位问题尤为重要,其中距离矢量跳数定位(D i s t a n c eV e c t o rH o p,D V HO P)算法因其成本低、且易于部署等优点得到广泛应用,但D V HO P算法定位误差较大.很多研究者对D V HO P定位算法进行了相关改进以减小定位误差.文献 通过对数据分组结构的改进降低了平均每跳距
13、离的误差,但该方法容易受节点分布的影响.文献 通过多通信半径广播锚节点位置信息,并结合节点远近度修正待定位节点与锚节点的测距值减小定位误差,但该方法需要较高的锚节点密度.文献 利用机器学习中极限学习机计算未知节点的位置,训练的数据只能适用于当前部署的定位环境且需要大量的锚节点.文献 在未知节点定位之前对锚节点进行安全检测以减少定位干扰,并没有充分利用锚节点的信息.大多数的改进算法都是以节点部署较为均匀为前提,通过各种方法降低定位误差.但是,在实际应用中,定位区域内节点的分布受环境、地形及气候等因素的影响,往往是不均匀的.为了降低D V HO P算法在锚节点密度低且节点分布不均匀的定位环境下的定
14、位误差,拟提出一种用模糊C 均值算法(F u z z yC M e a n s,F CM)改进的D V HO P定位算法.该算法提出了相似度与关联度的概念,通过F CM算法对锚节点进行分簇并提出了分簇策略,未知节点根据所提入簇策略进行簇内定位,然后进行簇间坐标的融合以实现全局定位.最后,将所提算法与D V HO P定位算法、基于粒子群改进的D V HO P(D V HO Pf o rP a r t i c l eS w a r m O p t i m i z a t i o n,P S O D V HO P)定位算法以及基于几何改进的D V HO P(I m p r o v e dD V HO
15、 P,I D V HO P)定位算法进行了定位误差的对比仿真实验,从而验证所提算法的有效性.基本问题描述目前的定位算法根据是否基于测距分为基于测距的定位算法与无需测距的定位算法.基于测距的定位算法包括接收信号强度指示(R e c e i v e rS i g n a lS t r e n g t hI n d i c a t o r,R S S I)、到 达 时 间 差(T i m e D i f f e r e n c eo f A r r i v a l,T D OA)及 到 达 角度(A n g l eo fA r r i v a l,AOA)等算法.与距离有关的定位算法通常需要额外的硬
16、件进行信号参数的测量,因而成本高且不适宜大面积部署.无需测距的定位算法包括D V HO P定位算法、多维定标(M u l t i d i m e n S i o n a lS c a l i n g,MD S)算法 及质心定位算法 等.在无需测距的定位算法中,通常给少量的节点配备全球定位系统(G l o b a lP o s i t i o n i n gS y s t e m,G P S)使之成为位置已知的锚节点.然后未知节点根据其与锚节点之间的位置关系与拓扑关系计算自身位置,因此无需测距的定位算法成本低且适合大规模的WS N部署应用.其中,D V HO P定位算法因实施 简单且易于 扩充
17、等 优 点 而 受 到关注.D V HO P定位算法容易受到锚节点数目以及节点分布的影响,导致平均跳距与最小跳数有较大的误差,从而在后续的计算中造成较大的定位误差.在实际应用中因环境等因素出现网络中的节点分布不均匀的情况,会进一步加剧网络中平均跳距与最小跳数的误差.为了改善在节点分布不均匀环境下定位误差较大的问题,在现有研究的基础上,提出在D V HO P定位算法的基础上引入F CM对节点进行分簇定位的算法.所提算法在分簇阶段使用F CM算法对锚节点进行分簇,为了防止分簇后簇内锚节点数目不能满足定位的需求,提出了与相似度相关的分簇策略,而未知节点则根据与各簇锚节点的关联度进行入簇定位,以期通过
18、所提算法中分簇定位的思想减少节点分布不均匀对平均跳距和最小跳数影响,进而降低定位误差.D V HO P定位算法原理及误差分析 D V HO P定位算法原理D V HO P定 位 算 法 是 由D N i c u l e s c u和BN a t h提出的基于分布式无需测距原理的定位算法,类似于传统网络中的距离向量路由机制.假设在定 位 环 境 中 有n个 锚 节 点、m个 未 知 节 点(n且mn).一个未知节点至少要与个锚节点产生距离关系才能建立可解方程组求解其位置.西安邮电大学学报 年月因此,n是必要条件.而mn是要确保通过少量锚节点定位未知节点,从而保证算法实际应用上的合理性.D V H
19、O P定位算法在定位时,首先计算节点之间的最小跳数,然后计算锚节点平均每跳的距离,利用最小跳数与平均跳距估算未知节点与锚节点之间的距离,最后用最小二乘法计算未知节点的坐标.D V HO P定位算法具体包括计算节点间的最小跳数、计算锚节点的平均跳距、计算未知节点到锚节点的距离和最小二乘法计算未知节点的坐标等个步骤.步骤计算节点间的最小跳数.首先,锚节点通过泛洪广播的方式向网络中的邻居节点发送数据包.数据包中包括节点的位置信息和跳数初始值,即初始跳数设为跳.节点每收到一个数据包,都会将跳值增加,并将数据保存在其位置信息表中.然后,该节点会将跳值增加的数据包转发到其邻居节点,并丢弃来自同一节点的跳值
20、更大的数据包.从节点的位置信息表可以得到节点之间的最小跳数.步骤计算锚节点的平均跳距.得到节点之间的最小跳数之后,锚节点用接收到的其他锚节点的位置数据和最小跳数计算该锚节点的平均跳距,其表达式为Siij(xixj)(yiyj)ijhi j()式中:(xi,yi)与(xj,yj)分别表示锚节点i与锚节点j的坐标;hi j表示锚节点i与锚节点j之间的最小跳数.此时,得到每个锚节点的平均跳距.步骤计算未知节点到锚节点的距离.当锚节点向网络发送其平均跳距时,未知节点在第一次接收到锚节点的平均跳距之后,用该锚节点的平均跳距计算从未知节点到各个锚节点的直线距离,即未知节点u到锚节点i之间的计算距离,其表达
21、式为du iSihu i()式中,hu i表示未知节点u到锚节点i的跳数.步骤最小二乘法计算未知节点的坐标,其原理是通过各个锚节点到未知节点的距离计算出未知节点的坐标.在D V HO P定位算法中,所有的锚节点 都 参 与 未 知 节 点 的 定 位,未 知 节 点 按 照式()计算到各个锚节点的距离并与锚节点建立距离方程组,其表达式为(xxu)(yyu)du(xxu)(yyu)du(xnxu)(ynyu)du n()式中:(x,y),(x,y),(xn,yn)分别表示n个锚节点的坐标;(xu,yu)表示未知节点u的坐标.用最小二乘法对式()的方程组进行求解,将式()的前(n)个方程分别与第n
22、方程进行线性变换后得到的线性矩阵为A XB()其中,A(xxn)(yyn)(xnxn)(ynyn)Xxuyu Bxxnyyndu nduxnxnynyndu ndu(n)式中:A表示锚节点的信息矩阵;X表示未知节点的坐标矩阵;B表示锚节点的距离矩阵.根 据 最 小 二 乘 法 估 计 的 优 化 规 则m i n(BA X)T(BA X),对X求偏导,得到X的估计值X为X(ATA)ATB()D V HO P定位算法的误差分析 锚节点对D V HO P定位算法的影响D V HO P定位算法通常使用定位环境内的所有锚节点参与未知节点的定位,具体的锚节点对D V HO P定位算法的影响如图所示,图中
23、的圆点为未知节点,五角星为锚节点.图锚节点对D V HO P算法的影响第 卷第期孙爱晶,等:一种基于F CM的D V HO P定位算法图中D V HO P定位算法会用 全部的个锚节点定位未知节点,但锚节点a距离未知节点较远,此时盲目地使用所有锚节点会带来较大的定位误差.因此,在定位未知节点时要根据锚节点与未知节点的关系有选择地使用锚节点.考虑对锚节点按照距离关系进行分簇,将圆内的锚节点分为一簇.未知节点进入该簇定位,避免了锚节点a带来的定位误差.因此,采用分簇锚节点的方法对锚节点进行选择,可以避免D V HO P定位算法中盲目使用所有锚节点带来的定位误差.节点分布对D V HO P定位算法的影
24、响通常在D V HO P定位算法应用的定位环境中,将节点的分布默认为是一种较为均匀的分布,节点分布较均匀的定位环境如图所示,定位环境内无较大的无节点空白区域.但是,受地形、气候及气候等因素的影响,部署节点时节点的分布有可能是不均匀的.当与图同样数目的节点分布不均匀时,节点分布不均匀定位环境如图所示,定位环境内出现较大的无节点空白区域.所提算法大都是在节点分布较均匀的定位环境情况下提出的,在节点分布不均匀定位环境中定位效果往往不太好.因此,所提算法能更好地适应节点分布不均匀的定位环境.图节点分布较均匀的定位环境图节点分布不均匀定位环境由图和图可以看出,在图较为均匀的定位环境中,锚节点a到未知节点
25、u的跳数为跳.在图中由于节点的不均匀分布,在定位环环境内存在大块无节点的空白区域,此时用最小跳数与平均跳距得到的距离会出现严重的误差.当节点分布不均匀时,由于空白区域的影响产生了多余的曲折路径,此时锚节点a到未知节点u的跳数为跳,而实际上两点之间的距离并没有这么大.在节点分布不均匀的环境下与分布较为均匀的环境下跳数相差跳,此时根据式()得到的估算距离误差很大,从而导致存在较大的定位误差.F CM算法为了避免所有的锚节点参与定位带来的定位误差,考虑引入F CM算法 对D V HO P算法进行改进,即根据距离分簇锚节点实现对未知节点的分簇定位.F CM算法是基于划分聚类的算法,广泛应用于图像分割中
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 一种 基于 FCM DV HOP 定位 算法
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【自信****多点】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【自信****多点】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。