最短路径距离矩阵修正的多维标度定位算法.pdf

第2 9 卷 第 1 期 2 0 1 6 年 1 月 传 感 技 术学 报 C HI N ES E J OU RNA L OF S E NS ORS AN D AC T UA TO RS V0 1 2 9 No 1 J a n 2 0 1 6 M u lt id im e n s io n a l S c a ling Lo ca liz a t io n Alg o r it h m Ba s e d o n t h e S h o r t e s t Pa t h M a t r ix Co r r e ct io n REN Ke q ia n g ZHUANG Fa n g wa n g S ch o o l o fI n f o r ma t i o nE n g i n e e r i n g J ia n g x i U n i v e r s i t y o f S ci e n ce a n d T e ch n o l o g y G a n z h o u J i a n g x i 3 4 1 0 0 0 C h i n a Abs t r act I n o r de r t o r e d uce t h e d if f e r e n ce b e t we e n t h e s ho r t e s t p a t h dis t a n ce ma t r ix a nd Eu cli de a n d is t a nce ma t r ix a n imp r o v e d a lg o ri t h m o f mu h id ime n s io n a l s ca li n g n o d e l o ca liz a t io n wa s p r o p o s e d t o e n h a n ce t h e n o d e lo ca liz a t i o n a ccu r a cy o f MD S MA P C a lg 0 r i t h m T h e a lg o r it h m ma d e s o me imp r o v e m e n t s o n MD S MA P C a 1 g o r it h m T h e s h o rt e s t p a t h d i s t a n ce ma t ri x w a s co r r e ct e d b y u s in g h e u r is t ic s e a r ch s t r a t e g y S O a s t o r e d u ce t h e e rro r b e t we e n t h e s h o rt e s t p a t h d is t a n ce ma t r i x a n d t h e a ct u a l Eu cli d e a n d is t a n ce ma t ri x T h e n s ma co f a lg o ri t h m it e r a t iv e e r r o r f u n c t io n i n s t e a d o f s in g u la r v a lu e d e co mp o s i t i o n S VD wa s u t i liz e d t o s o lv e t h e p r o b le m o f n o d e l o ca liz a t io n wh ich co u ld o p t imiz e a n d imp r o v e t h e s o lv in g p r o ce s s o f n o d e lo ca liz a t io n T h e e x p e ri me n t a l r e s u lt s s h o w t h a t co mp a r e d w it h MD S MA P C a lg 0 r it h m t h e imp r o v e d a lg o rit h m ca n r e d u ce t h e e rr o r o f t h e s h o rt e s t p a t h d is t a n ce e f f e ct iv e ly i mp r o v e t he n o d e lo ca liz a t io n a ccu r a cy a n d it ha s b e t t e r a da p t a b ilit y t o t he ir r e g u la r n e t wo r k 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 t h e s h o rt e s t p a t h MD S MA P C a lg o rit h m n o d e lo ca liz a t io n m u h id ime n s io n a l s ca lin g s ma co f a lg o ri t h m EE A CC 6 1 5 0 P 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 1 0 2 2 最短路径距离矩阵修正的多维标度定位算法 任克强 庄放望 江西理工大学信息工程学院 江西 赣州 3 4 1 0 0 0 摘要 为了减小最短路径距离矩阵与欧氏距离矩阵之间的差异 提高 M D S M A P C 算法的节点定位精度 提出一种改进的多维标度节点定位算法 该算法对 M D S M A P C 算法进行了以下改进 采用启发式的搜索 策略对最 短路径距离矩 阵进行修正 以减少最短路 径距离矩 阵与实 际的欧 氏距离矩阵之间的误差 利用 s m a co f 算法迭代误差函数代替 S V D分解来求解节点的定位问题 以优化和改善节点定位的求解过程 实验 结果表明 与 M D S M AP C 算法相 比 改进算法能够减少最短路径距离的误差 有效提高节点的定位精度 并且对不规则 网络具有更好 的适应性 关键词 无线传感器网络 最短路径 M D S M A P C 算法 节点定位 多维标度 s m a co f 算法 中图分类号 T P 3 9 3 文献标识码 A 文章编号 1 0 0 4 1 6 9 9 2 0 1 6 0 1 一 O 1 2 9 0 7 无 线 传 感 器 网 络 WS N Wir e le s s S e n s o r N e t w o r k 由大量部署在监测区域 内的廉价微 型传感器 节点构成 它是一种 自组织 分布式处理 以及快速 展开的无线网络n 传感器节点的位置信息对 WS N的监测活动极其重要 获取准确 的传感器节点 位置信息是 WS N进行相关监测以及传感器节点进 行下一步活动和决策的基础 WS N的节点定位 算法 按定 位机 制 的不 同可分 为基 于测距 R a n g e 收稿 日期 2 0 1 5 0 8 0 6 修改日期 2 0 1 5 1 0 2 0 b a s e d 的算法 和测距无关 R a n g e f r e e 的算法口 R a n g e b a s e d算法通过测量节点之间的距离或角度 来实现定位 R a n g e f r e e算法则无需测量节点之间 的距离和角度信息 而是根据网络的连通性等信息 来实现定位 R a n g e b a s e d的代表算法有基于到 达时间 T 0 A T ime o f Ar r i v a 1 的定位 基于到达时间 差 T D O A T ime D if f e r e n ce o f A r r iv a 1 的定位 基于接 收信号强度指示 R S S I R e ce i v e d S i g n a l S t r e n g t h I n d i in 报 I g 2 91 3 0 co m 2 9 卷 w w w ch in a t I a n s d u ce r s j 昏 ca t o r 的定位 以及 基于到达角度 A O A A n g l e o f A r r i v a 1 的定位等算法 R a n g e f r e e的代表算法有 距离 向量一 跳段 D V h o p D is t a n ce V e ct o r h o p 定 位 凸规 划C o n v e x O p t imiz a t i o n 定 位 以及 多维 标 度 MD s Mu lt id im e n s io n a l S ca li n g 定位等算法 MD S是一种将多维空间中的研究对象简化到低 维空间中进行定位 分析和归类 并且保持研究对象 之间原有关系的多元数据分析技术 S h a n g Y i等人 将 MD S技术应用于 WS N的节点定位 提出了 MD S MA P算法n 该算法利用节点间的连通性或距离估 计信息进行定位 将节点间最短路径距离近似为节点 间的欧氏距离 再利用 MD S方法进行定位 当网络拓 扑不规则时 由于最短路径距离与节点间实际的欧氏 距离相差较大 严重影响算法的定位精度 为了解决 最短路径距离与节点间实际欧氏距离的差异性问题 国内外研究人员提出了不同的 MD S MA P算法改进 和优化方案 文献 1 2 将网络拓扑分解为多个局部 地图 再按分布式的计算模式对局部地图进行 MD S MA P定位 减少了最短路径距离与节点间实际欧氏 距离的误差 但在 R a n g e F r e e 环境的定位精度依然 不高 文献 1 3 在生成相对地图的过程中采用迭代 更新的方式来改善定位性能 使其定位精度有 了较大 的提升 但计算复杂度较高 节点的能耗较大 文献 1 4 采用距离矩阵重构的方式来替代最短路径距离 矩阵 并用奇异值分解 S V D S in g u la r Va lu e D e co mp o s it io n 低秩近似的方法来求解距离矩 阵 文献 1 5 提出基于距离矩阵重构的 WS N多维标度定位算法 利用节点间的相关信息对距离矩阵进行线性重构 然 后使用经典 MD S进行定位 取得 了较好 的定位精 度 文献 1 6 针对 MD S MA P在不均匀 网络中定位 精度较低的问题 提出一种可用于不均匀 网络的节点 定位算法 有效地减小了平均定位误差 文献 1 7 提 出改进距离重构 的三维节点定位算法 该算法利用 MD S MA P算法获取节点之间相对的坐标 并采用精 度更高的坐标映射方案对坐标转换过程进行优化 取 得了较高的三维节点定位精度 针对最短 路径距离与节点之 间实 际欧氏距 离 的差异性 问题 本 文提 出一 种基于最 短路径距 离 矩阵修正的多维标度定位算法 M D S D M C M D S D is t a n ce Ma t r ix C o r r e ct io n 通过 修 正最 短 距离 矩 阵来逼近欧 氏距 离矩 阵 以提高节点的定位精 度 1 多维标度定位算法 MD S M A P C 是一种基 于经 典 MD S C la s s ica l MD S C MD S 的多维标度定位算 法 该算法 将各个 节点视作一个实体元素 各节点之间的相似性用欧 氏空间距离来表示 通过建立欧氏空间距离与相似 性信息 的线性 映射关 系后 就可在多维空间内获得 节点的分布 如果获得的相似性信息与欧氏空间 距离的差异不大 则利用 C MD S就可得到各节点之 间相对 的位置空间分布 令 P 为 T t 维空间中i和 两个点的相似性信 息 通 常 等 价 于 欧 氏 空 间距 离 d i 点 坐标 为 J 点坐标为 则 d m 一 J 1 一 x j f 1 和 两点欧 氏空间距离的平方为 T 一 2 x i r x j X j 定义 1 一 v r 则平方距离 矩阵 D d 2 N 可表示为以下 内积形式 D O e 一2 2 其中 为元素全 1的 1 维向量 定义中心矩 阵 日 卜 e e N J 为单位矩阵 对 D进行双中心化 B 一 H D H H X X H 3 对 进行 S V D分解 可得到 B 队 从而可 以求解 X V A 2 MD S D MC算法 MD S M A P C 算法以节点之间的最短路径距 离替代欧 氏空 间距离 并采用 S VD分解求解节点 位置 在 密集且 分布均匀 的网络环境 中 最短 路 径距 离可 以近似 欧 氏空 间距离 但在 稀疏且 分布 不均 的 网络环境 中 最短 路径距离 与欧 氏空间距 离 的差异往往很 大 此 时两者近似 将产 生较大 的 误 差 此 外 当 网络规 模很 大时 采用 S V D分解 求解节 点位置 比较 复杂且定位精度不高 本文针 对这 些 问题 提 出 MD S D MC算 法 对 MD S MA P C 算法进行了两个方面的改进 采用启发式 的搜 索策略对最 短距离矩 阵进行修 正 以减 少最 短距 离矩 阵与实际 的欧氏距离矩 阵之 间的误差 使用 s m a co f 算法迭代误差函数代替 S V D分解 来 求解定位 问题 以改 善和优 化节点定位 的求解 过程 2 1 最短距离矩阵的修正 假定节点所能辐射范 围的通信半径 为 R C 两 个 节 点 之 间 的距 离 无 法 直 接 获 取 如 图 1 所示 第1 期 任克强 庄放望等 最短路径距离矩阵修正的多维标度定位算法 1 3 1 图 1 最短距离矩阵修正示意图 如果用最短路径算法求 取的最短路径距离来 近 似 代 替 A C节 点 之 间 的距 离 则 有 A C A B B C 即 d d 很 明显 这种近似存在误差 为 了减少误差 本文通过以下启发式的搜索策略来修正最短距离 矩阵 根据余弦定理 有 L d 1 d 2 2 d 1 d 2 C O S LA B C 4 LA B C LA B C 2 LC 2 B C 5 为 简化 问题 的讨 论 假 定 C点是 的 中 点 则 函数 N S x 一 d l j 1 0 一 i 1 1 其 中 i j 为节点间的估算距离 d i 4 x i 为节 点间的欧氏距离 将式 1 0 展开得到 I v N N s x 吉 琵 吒 一 N i lj l 1 1 2 d i j i 1 1 将式 1 1 转化成矩阵形式 Js 晶 专 吒 抑 一 d l 1 2 晶 一 吾 tm ce X H X tra ce 一 i 1 J 1 一 其 中 t r a ce 为迹运算 代表矩阵的对角线元素之和 是由所有节点组成的矩阵 是 的 转置 日为中心矩阵 日 一 e e N 为单位矩阵 是关于 的中心矩阵 其元素由式 1 3 组成 C 2 B C L C B C 1 告 c2 c1 告 7 r dB C 2 7 L A B C L A B C 2 告 仃 一 A A B C 2 7 1 L A B C 2 8 由上可得 L d 1 d 2 一2 dld 2 C O S LABC d1 2 一 2 d 1 d 2 c0 s L AB C 2 d 1 d 2 2 d 1 d 2 s i n 1L A B C 2 9 因此 通过 以上方法修正最短距离矩 阵 可以 改 善用 最 短距 离矩 阵 近似 欧 氏距 离矩 阵产 生 的 误差 2 2 求解节点位置的改进 对于节点数 目为 的网络 使用 S V D分解求 解节点位置的复杂度 为 O N 当节点规模很大时 一 般采用迭代的方法代替 S V D分解 以提高求解节 点位置的效率 本文采用 M e t r i c M D S 求解节点的 位置 并利用 s m a co f 算法迭代误差函数代替 S V D 方法求解节点 的定位 问题 以下简称 为 MD S MA P s ma co f 算法 定义函数 Js 作为估算距离与实际距离的误差 一 丁 i d t 0 1 3 一 叫 i j P 1 p i 采用 m a co f 算法 定义辅助函数 z 为 z N N 毛一 t 瑚 X H X t r a ce z r 一 i 1 1 一 1 4 每次迭代 k 采用 Z X 由于 的梯度 函数为 V 司 N X H 一 z 1 5 令梯度为 0 可以得到 一 一 1 日 1 6 根 据矩 阵 日 的特性 可 以推 导 出 的迭代 形式 k 一 1 一 V却 1 7 从而 节点的坐标可通过迭代 的方式求得 分析式 1 7 的迭代公 式 求解该递归过程 的复 杂度 为 O N 即节点 坐标 求 解过 程 的复杂 度为 O N 而执行 S V D分解求解节点位置的复杂度为 O N 因此 通过 ma co f 算法可有效降低求解节 点位置的复杂度 第 1 期 任克强 庄放望等 最短路径距 离矩 阵修正的多维标度定位算法 1 3 3 由实验结果可知 在矩形 网络 中 M D S M A P c 算法 的平 均定 位误 差 为 1 8 7 M D S M A P s m a e o f 算 法 的平 均 定 位 误 差 有 了 的 改 善 为 1 6 9 而 MD S D MC算 法 的平 均 定 位 误 差 仅 为 4 1 有效 的提高了定位 的精度 在 c 型 网络中 由于不规则 网络 的影 响 出现了拓扑空洞的情况 最 短路 径 距离 矩 阵存 在 较大 的误 差 导 致 MD S M A P c 算法的平均定位误差高达 1 1 7 8 而采 用 MD S M AP s m a co f 算 法 和 MD S DMC算 法 的平 均定位误差分别为 9 5 和 1 7 MD S D MC算法大 幅度 的减小 了平 均定位误 差 因此 在 C型 网络 中 MD S D MC算法可 以有效减少最短路径距离 的 差 异 改 善 定 位 性 能 提 高 对 不 规 则 网络 的适 应性 3 2 非理想传输模型下的定位 非理想传输模 型的定位可用不规则 的信号模 型来模拟实际的环境 采用不规则度 D O I D e g r e e o f I r r e g u la r 表征锚节点的传播信号在传输的过程 中受 到的影响 D O I 值反映了锚节点信号广播的不规则 程度 该实验主要比较三种算法在非理想传输模 型 的不同网络拓扑下的性能 在实验场景 的两种 网 络拓扑下 随机部署 3 0 0个节点 在通信半径为 0 2 L以及 D O I 为 0 2的情况下 矩形 网络平均连通 度 为 3 O 3 c 型 网络 平 均 连通 度 为 3 5 9 分别 用 MD S MA P C 算法 MD S MAP s m a co f 算法和 MD S D MC算法进行定位 该实验的节点分布以及定位 误差如 图 5 图 7所示 0 0 0 0 o 赢 0 X L a 矩形网络分布图 X L b c 型网络分布图 图5 非理想传输模型下的网络分布 甍 套 X L b MD S MA P s ma e o f 算法定位结果 X L c MD S D MC 算法定位结果 图6 非理想传输模型下矩形网络的定位 0 6 一 0 2 0 4 O O 1 0 2 0 3 0 4 0 5 0 6 0 7 0 8 0 9 1 0 X L a MDS MA P C 算法定位结果 L b MD S M A P s a mco f 算法定位结果 X L c MD S D M C 算法定位结果 图7 非理想传输模型下C形网络的定位 0 9 8 7 6 5 4 3 21 0 1 0 0 0 0 O O O O 0 传感技术学报 1 3 4 W W W ch in a t r a n s d u ce r s co rn 第2 9 卷 由实验结果可知 在非理想传输模型的矩形网 络中 M D S MA P C 算法 M D S M A P s m a co f 算法以 及 MD S D MC算法 的平均定位误差分别 为 2 0 7 1 7 4 和 8 1 MD S D MC算法 的定 位性能有 了明 显的改善 而在非理想传输模型的c 型网络中 由 于最短路径距 离矩 阵差 异 的影 响不 同 MD S M A P c 算法 M D S M A P s m a co f 算法以及 M D S D M C算 法 的平均定 位误差分 别为 1 1 8 1 0 7 和 1 8 1 MD S D MC算法定位性 能的提 升更 为显著 因此 MD S D MC算法能够较稳定 的适应非理想传输模 型 的节点定位 提高不规则网络的节点定位精度 3 3 不同连通度的定位误差 该实验主要比较三种算法在不同通信半径和 连通度下 的性 能 在实验场景的两种网络拓扑下 随机部署 3 0 0个节点 节 点通信半径 r 分别取 0 1 2 5 L 0 1 5 L 0 1 7 5 L 0 2 L 0 2 2 5 L和 0 2 5 L时 矩形 网络 的连通度分别 为 1 3 6 1 8 7 2 5 1 3 1 1 3 8 0和 4 8 3 C型 网 络 的连 通 度 分 别 为 1 6 5 2 2 8 2 9 1 3 8 2 4 5 1和 5 1 3 实验结果如图 8所示 从图 8可 以看 出 M D S D M C算法在不同连 通度 的定位性 能均优 于 MD S MA P C 算法 在连 通 度较 低 的情 况 下 MD S D MC算 法 的定 位精 度 有 了 明显 的提高 特别 是在 C型 网络 中 定位 精 度 的提高 幅度更大 因此 与 MD S MA P c 算法 相 比 MD S D MC算 法 在不 规 则 网络 拓扑 下 有更 好的适应性 在 WS N的定位应用中具有明显的 优势 连通度 b C 型网络 图8 不同连通度的归一化平均定位误差比较 4结 论 针对 M D S M A P C 算法中的距离矩阵问题 提 出 MD S D MC算法 该算法采用启发式搜索的最 短路径距离修正策 略来减小最短路径距离与实 际 欧氏距离之间的误差 有效地提高了节点的定位精 度和对不规则网络的适应性 引入 s m a co f 算法迭代 误差 函数取替 S VD分解来优化节点定位 的求解过 程 进一步提升了算法的性能 在理想传输模型 非理想传输模型以及不 同 传输半径和连通度的算法仿真对比实验中 M D S D MC 算法均表现出比M D S MA P C 算法更加优异 的性能 进而验证 了改进方法是正确和有效的 减小最短路径距离与实际欧氏距离之间的 误 差是提 高多维 标度节 点定位算法性能 的有效途 径 之一 如何进 一步减小距离矩 阵之间的差 异是 后续重点 的研究工作 参考文献 1 L iu Qi a n g Hu a n g Xi a o h o n g L e n g S u p e n g e t a 1 D e p l o y me n t S t r a t e g y o f Wi r e l e s s S e n s o r Ne t w o r k s f o r I n t e r n e t o f T h in g s J J C h in a C o m mu n i ca t i o n s 2 0 1 1 8 8 1 1 1 1 2 0 2 侯洪涛 周鸿伟 李群 等 卫星导航系统接收传感器网络的攻 击检测研究 J j 系统工程与电子技术 2 0 1 4 3 6 6 1 1 9 5 1 2 0 0 3 王福豹 史龙 任丰原 无线传感器网络中的自身定位系统和 算法 J 软件学报 2 0 0 5 1 6 5 8 5 7 8 6 8 4 张亚 明 史浩 山 刘 燕 等 不对称链 路环境 下的 WS N节点 定 位算法 J 传感技术学报 2 0 1 4 2 7 3 3 2 0 3 2 6 5 刘瑜 衣晓 何友 基于分治求精的无线传感器网络节点定位 算法 J 系统工程与电子技术 2 0 1 2 3 4 9 1 9 0 6 1 9 1 3 6 钱志鸿 王义君 面向物联网的无线传感器网络综述 J 电子 与信息学报 2 0 1 3 3 5 1 2 1 5 2 2 7 7 P a r k J W P a r k D H L e e C A n g l e a n d R a n g i n g B a s e d L o ca li z a t i