结合极大似然距离估计的MDS-MAP节点定位算法.pdf

第2 9 卷第4 期 2 0 1 6 年 4月 传 感 技术 学 报 C HI NE S E J OUR NAL OF S E NS O RS AN D AC T U AT OR S Vo l 29 No 4 Ap r 201 6 Lo c a liz a t io n Alg o r it h m f o r W ir e le s s S e n s o r Ne t wo r k s Ba s e d o n M DS M AP I nt e g r a t e d wit h M a ximum Lik e liho o d Es t ima t ing L I J in r o n g 一 WANG Wa n lia n g J I E ri n g Y AO Xin w e i 1 C o ll e g e o fC o m p u t e r S c i e n c e T e c h n o l o g y Z h ej i a n gU n i v e r s i t yo fT e c h n o l o g y H a n g z h o u 3 1 0 0 2 3 C h in a 2 S c h o o l o f A u t o m a t i o na n dE l e c t r i c E n g i n e e r i n g Z h e j i a n gU n i v e r s ityofS c i e n c e T e c h n o l o g y H a n g z h o u 3 1 0 0 2 3 3 C h i n a A b s t r a c t T h e mu lt id ime n s i o n a l s c a lin g MD S p o s it io n in g a lg o r it h ms o f w ir e le s s s e n s o r n e t w o r k s u s u a lly u s e t h e le n g t h o f s h o r t e s t p a t h in lie u o f t he Euc lide a n d is t a n c e b e t we e n t wo n o d e s t o b uil d t h e d is t a nc e ma t r ix whic h ma y r e s u lt in la r g e p o s it io n ing e r r o r s e s p e c ia ll y wh e n t h e n e t wo r k t o p o lo g y is ir r e g u la r To s o lv e t hi s pr o b le m a n e w lo c a liz a t io n a lg o r it h m MD S MA P ML E w a s p r o p o s e d in t h is w o r k in w h ic h t h e MD S MA P me t h o d a n d Ma x im u m Li ke liho o d Es t ima t in g wa s c o mb in e d The in f o r ma t io n c o min g f r o m t h e 1 一 h o p n e ig h bo r s a r e de e me d a s t h e in p ut o f t h e ma x imu m l ike lih o o d me t ho d t o e s t ima t e t h e r e la t iv e c o o r d in a t e o f t h e t e s t e d n o d e And t h is pr o c e s s will it e r a t e u nt il a ll u n kn o wn n o d e s r e la t iv e c o o r din a t e a r e e s t ima t e d An d t h e n t he g l o ba l ma p c a n b e t r a n s f o r me d t o a n a bs o lu t e ma p b a s e d o n t h e a b s o lu t e p o s i t io n s o f a n c h o r s S im u la t io n r e s u lt s s h o w s t h a t t h e MD S MA P ML E a lg o r i t h m c a n g e t h ig h p o s it io nin g pr e c is io n e i t he r f o r r e g ula r o r ir r e g u la r ne t wo r k I n a d d it io n t he p o s it io n in g e r r o r s c a n s t a y r e la t iv e ly c o n s t a n t a t a lo w le v e l whe n t h e ne t wo r k c o n ne c t iv it y v a r y wit h in a c e rta in r a ng e Ke y wo r d s w ir e le s s s e n s o r n e t w o r k s l o c a liz a t io n a lg o r it h m m u l t i d im e n s io n a l s c a lin g m a x imu m lik e lih o o d 6 2 1 0 Q E E AC c 7 2 3 0 d o i 1 0 3 9 6 9 0 is s n 1 0 0 4 1 6 9 9 2 0 1 6 O 4 0 1 8 结合极大似然距离估计的MD S MA P 节点定位算法 李津蓉 王万良 介 婧 姚信威 1 浙江工业大学计算机科学与技术学院 杭州 3 1 0 0 2 3 2 浙江科技学院自动化与电气工程学院 杭州 3 1 0 0 2 3 摘 要 基于多维定标的定位算法通常利用节点间的最短路径长度代替欧式距离构建距离矩阵 当网络拓扑结构不规则时 会导致较大的定位误差 针对这一问题 提出了一种结合极大似然距离估计和多维定标 的节点定位算法 M D S MA P ML E 算法将待测节点的一跳邻居节点信息作为极大似然方法的输入 利用与邻居节点的距离信息计算待测节点的相对坐标 然后 根据已知锚节点的坐标 将所有节点的相对坐标映射为绝对坐标 实验结果表明 针对规则网络和不规则网络 MD S MA P ML E 算法均可取得较好的定位精度 且当网络连通度在一定范围内变化时 定位误差可保持在较低的稳定区间内 关键 词 无线传感网络 定位算法 多维定标 极大似然方法 中图分类号 T P 3 9 3 文献标识码 A 文章编号 1 0 0 4 1 6 9 9 2 0 1 6 0 4 0 5 7 2 0 6 无 线传感器网络 中的节点定位机制是指依靠 有 限的位置已知节点 确定布设区域 内其它节点的 位置 建立各个传感器节点 问的二维或三维空 间关 系 高密度的传感器节点通过近距离感知物理世 界 为分析计算系统提供具有较高准确性和实时性 的信息 而在大多数情况下 只有结合准确的位置 信息 传感器所获得的数据才有实际的应用价值 如 目标定位与跟踪 险情监测 环境勘查等 基于多维定标 MD S Mu lt i D ime n s i o n a l S c a lin g 的节点定位算法 MD S MA P 2 由于其所需锚节点的 数 目少 且可在基于测距和无需测距两种情况下使 用 近年来成为节点定位技术的研究热点 但 由于 MD S MA P算法利用 网络节点间的最短距离近似欧 式距离 导致 网络 的距离矩 阵不准确 特别是当网 络拓扑结构不规则或网络中存在通信空洞时 由于 节点 间的最短路径距离与实 际的欧式距离差距较 项 目来源 国家 自然科学基金项 目 6 1 3 7 9 1 2 3 国家 自然科 学基金项 目 6 1 4 0 2 4 1 4 浙江省 自然科学基金项 目 L Q 1 4 F 0 5 0 0 0 2 收稿 日期 2 0 1 5 1 卜2 9 修改 日期 2 0 1 6 0 1 0 7 第4 期 李津蓉 王万 良等 结合极 大似然距 离估计的 MD S MA P节点定位算法 5 7 3 大 导致最终节点定位结果的误差难以接受 针对 MD S MA P所存在的问题 S h a n g 提出了分 布式 MD S算法 MD S MA P P 这种方法首先将两 跳之内的邻居节点利用 MD S算法获得局部地 图 然 后利用贪婪算法对局部地图进行融合得到所有节点 的相对坐标 最后利用坐标已知的锚节点将各节点的 相对坐标映射为绝对坐标 在此基础之上 一系列基 于 网络分簇的 MD S MA P算法 被提 出 这类算法 的基本思想是首先将 网络节点基于某种策略分成若 干 簇 各个簇头节点利用局部信息对簇 内节点进行 定位 再将簇内地图通过融合算法构成全局地图 这 类算法利用局部路径信息对节点进行定位 避免了远 距离节点问的最短路径距离与欧式距离 的较大误差 因此定位精度较高 但这类算法通常存在以下问题 1 分簇算法较复杂 且簇的划分对后续算法的运行效 率及定位精度有较大影响 2 局部地图的融合过程开 销较大 且会出现误差累积问题 针对 以上算法不足 本文提出一种结合极大似 然距离估计 的 MD S MA P节点定位算 法 MD S MA P ML E MD S MA P ML E 算法首先利用 MD S方法 对一个一跳连接子 网 即子 网内各个节点均 为一跳 邻居关系 内的所有节点进行定位 然后利用极大 似然方法对子 网外 的其余节点进行定位 逐 步扩散 子 网直至覆盖整个 网络 仿真实验表明 针对规则 网络和不规则 网络 该算法 均可取得 较好 的定 位 精度 1 MDS MAP ML E 算法 为 了避免经典 MD S MA P算法 中利用节点间的 最短 路径距 离近似 欧式距离 所造成 的计算误 差 MD S MA P ML E 算法 的基 本思想是首先仅利用一 跳邻居间的距离信息进行节点定位 然后将 已定位 的节点作为极大似然算法n 圳 中的锚节点 对相邻 节点进行定位 逐步扩大 已定位节点 的范 围 直至 覆盖整个网络 假设 自组织网络内共有 个传感器节点 节点 集合记为 对应的坐标 向量为 X i x X 一 其 中 X Y 1 表示第 i个节点 的坐标 MD S MA P ML E 算法步骤如下 S t e p 1 根据 网络 连通情况 构建全 网邻 接矩 阵 A N N 若节点 i与 为一跳邻居关系 则矩阵 元素 a 1 否则 a 0 S t e p 2 在全局网络 中找到一跳邻居子网 这相 当于在全局网络所对应的无向图 G中找到一个全连接 子 图 这 通 常被 称 为 最 大 团 问题 MC P Ma x imu m C liq u e P r o b le m 是一 N P完全问题 需要使用相应的 优化策略搜索最优解 但在我们的实际应用中只需要 找到一个全连接子图即可 而并不要求为最大子图 因 此为了简化算法 我们采用以下策略 在邻接矩阵A 中删除邻居最少的节点所对应的行 和列 得到矩 阵 A 检查矩阵 A 是否为全 1 矩阵 是则退出循环 否则 令 A A 回到步骤 当以上算法结束时 A 中所有行 或列 所对应节点的集合记为 啷 其 中所有节点为全连接关系 构成 了 1 跳邻居子网 网 络中的其余节点集合记为 即 I c S t e p 3 计算 1 跳邻居子 网中所有节点的相对 坐标 由于 V 中所有节点均为一跳邻居关系 因此直接利用测距方法所 获得 的节点距离测量值 构建节点距离矩阵 并利用 MD S方法计算 中 所有节点的相对坐标值 S t e p 4 根据全 网邻接矩阵 A 在 中找到 一 个节点 v 要求集合 中与 v 构成一跳邻居关 系 的 节 点 数 大 于 等 于 3 假 设 节 点 集 合 1 2 c L o s E D 且 与节 点 均为 一 跳邻居关系 由于在 S t e p 3中已通过 MD S方法计 算得到 的坐标 因此可利用极大似然方 法计算节点 v的坐标 记录节点 V 的坐标 并将节点 从 集 合 转 移 到 功 集 合 即 V o P E N V o P E N V V c L 0 s E D c L o s E D U S t e p 5 重复 S t e p 4 直至集合 V o 此时 啪 集合包含了网络中的所有节点 且已计算获 得所有节点的相对坐标矩阵 X r S t e p 6 利用 坐标 已知 的锚节点 将 集 合 中节 点 的 相 对 坐 标 矩 阵 转 换 为 绝 对 坐 标 矩 阵 X X 1 X 一 当 算 法 结 束 时 所 得 到 的 绝 对 坐 标 矩 阵 不 r即是对节点实际坐标的估计值 以上所述算法是基于测距的 若传感器节点无测距 能力 则可直接把 S t e p 3和 S t e p 4中所涉及到的一 跳邻居节点 的距离设定 为 1 或通信半径 即可 因 此 MD S MA P ML E 算法 既可用于 基于测距 的情 况 也可用在非基 于测距的情况 2 实验研究及性能分析 为 了测试 MD S M A P ML E 算法对 自组织传感 器 网络 中节点 的定位性能 我们在 Ma t la b 2 0 1 2 b环 境下分别对规则 网络 和不规则 网络 中的节点定位 进行了仿真实验 传感技术学报 5 7 6 w w w c h in a t r a n s d u c e r s c o m 第2 9 卷 当网络 中的节点数量或节点通信半径变化 时 均会影 响网络连通度 进而对定位算 法的结果产生 影响 为此我们在不 同的网络连通度下 对两种算 法分别在规则 网络 和不规则 网络 中的定位误差进 行了比较 比较结果如图 7所示 从图 7可以看出 MD S M AP算法的定位误差会 随着连通度 的提高明显下降 而 MD S MA P ML E 算 法的定位误差则保持一个稳定的较低水平 分析两 种算法的工作原理 可知其原因如下 MD S MA P算法 的定位误差主要来 自于节点间的最短路径距离与欧 式距离的偏差 当连通度较低时 由于任意两节点间 的连通路径数量较少 使得所选 出的最短路径长度与 Co n ne c t iv it v 两节点的欧式距离有很大偏差 导致定位误差较大 而当网络连通度提高时 节点的最短路径长度与欧式 距 离 接 近 使 得 定 位 误 差 显 著 降低 MD S MA P ML E 算法 的定位误差主要 由节点的测距误差所导 致 网络连通度的提高可以增加待测节点的邻居数 量 若测距误差满足高斯分布 使用极大似然算法计 算待测节点的相对坐标时 可以更好地消除测距误差 的影响 但 当测距误差不是很显著时 小于 5 邻 居节点数量的增加对定位误差 的消除不会产生明显 作用 因此 对于 MD S MA P ML E 算法而言 只要待 测节点的已知邻居数量满足算法要求 即可在一定范 围的网络连通度内保持较低的定位误差水平 呈 0 暮 羔 图7 两种算法在不同网络连通度下的定位误差比较 由于网络节点 间的测量距离是获得节点相对 坐标的唯一依据 因此测距误差会对定位结果产生 严重影响 为此 在实验 中考虑了测量误差为通信 距离的 0 2 0 范围内 并假设测量误差满足正态分 布 对 MD S MA P ML E 和 MD S MA P的定位误差进 行 了比较 比较结果如图 8 所示 Ra n g e e r r o r R 图8 两种算法在不同测量误差下的定位误差比较 由图 8 可以看出 当测距误差上升时 MD S MA P M L E 与 M D S M A P算法定位误差的增长趋势基本 一 致 无明显的误差积累现象 这实际上得益于测距 误差为正态分布的假设 由于在 MD S MA P ML E 算法的每次迭代过程中 使用极大似然算法对未知 节点进行定位时 利用了多个邻居节点与未知节点 的距离信息 测距误差在一定程度上相互抵消 可获 得较为准确的定位结果 但如果测距误差不满足正 态分布 或用于定位 的邻居节点数量较少时 则会产 生较严重的误差累积现象 在这种情况下 如何进一 步提高算法的容错性还需进行更为深人的研究 3 结 论 本 文提出了一种基于极大似然方法估计节点 间欧式距离的无线传 感器网络 多维定标 自定位算 法 MD S MA P ML E 该算法避免 了经典 MD S MA P 算法 中利用最短路径近似欧式距离所导致的误 差 仿真实验表明 MD S MA P ML E 算法在规则网 第4 期 李津蓉 王万良等 结合极大似然距 离估计的 MD S MA P节点定位算法 5 7 7 络和不规则 网络中均可获得较高的定位精度 且当 网络连通度在一定范 围内变化时 定位误差可保持 在一个相对稳定的低水平区间之内 但 MD S MA P ML E 算法仍属于集 中式定位算法 且计算速度与 MD S MA P算法相 比无 明显优势 在此方 面需做进 一 步的深入研究 参考文献 1 于海斌 梁炜 曾鹏 智能无线传感器网络系统 M 第 2 版 北京 科学 出版社 2 0 1 3 2 3 4 5 Amin K Oh S Ro b u s t L o ca l iz a t io n f r o m I n co mp l e t e L o ca l I nf o r ma t io n J I E E E AC M T r a n s a ct i o n s o n N e t w o r k i n g 2 0 1 3 2 1 4 1 1 3 1 1 1 4 4 刘政 基于粒子群优化的多维标度节点定位算法 J 传感技 术学报 2 0 1 5 2 8 8 1 2 2 8 1 2 3 2 Ama r A W a n g Y Y L e u s G e t a 1 E x t e n d in g t h e Cl a s s ica l Mu l t i d ime ns io n a l S ca l in g Al g o ri t h m Giv e n P a r t ia l Pa ir wis e Dis t a n ce Me a s u r e me n t s J I E E E S i g n a l P r o ce s s i n g L e t t e r s 2 0 1 0 1 7 5 4 7 3 4 7 6 明良 赵 刚 谢桂 海 等 面 向智能 空间 的位置感 知算法研 究 J 软件学报 2 0 0 9 2 0 3 6 7 1 6 8 1 李津蓉 1 9 7 7 一 女 天津市人 博士 副 教授 现为浙江科技学院自动化与电气 工程学院教师 浙江工业大学计算机科学 与技术学院博士后 主要研究方向包括 无线传感器网络 机器学习 智能计算等 介婧 1 9 7 2 一 女 博士 博士后 教 授 现为浙江科技学院自动化与电气 工程学院教师 主要研究方向包括智 能控制 调度优化 智能系统及检测装 备 群智能及机器人 6 S h a n g Y R u ra l W I mp r o v e d MD S b a s e d L o ca t io n C P r o e o f t h e 2 3 r d C o n f o f t h e I EEE Co mmu n ica t io n s S o cie t y 2 0 0 4 2 6 4 0 2 6 51 1 7 j S h o n M J o M C h o o H A n I n t e r a ct i v e C l u s t e r B a s e d MD S L o ca l i z a t io n S ch e me f o r Mu l t ime d ia I n f o r ma t io n in W ir e l e s s S e n s o r Ne t w o r k s J C o mp u t e r C o m mu n i ca t io n s 2 0 1 2 3 5 1 5 1 9 2 1 1 9 2 9 8 王勇 胡 良梁 袁巢燕 基于密度分簇的无线传感器网络定位 算法 J 电子科技大学学报 2 0 1 3 4 3 3 4 0 6 4 0 9 1 9 J S h o nM C h o iW C h o oH e t a 1 A C l u s t e r B a s e dMD S S ch e me f o r R a n g e F r e e L o ca