一种用于移动无线传感器网络的新型节点定位算法

，
＋ Ｆ ・ （ ｇ ． ． ｇ ） ， ｒ ｌ ＃ ｒ ２ ＃ ｒ ３ ∈ ［ １ ， ＾ ］ ， Ｆ ＞ ０ （ ４ ）
２ ． ２ 蒙特 卡 罗定位
式 中， 表示 第 ｇ 代种 群 中第 ｉ 个样 本 ， ｒ ｌ 、 ｒ ２ 、 ｒ ３ 是
蒙特 卡 罗 定位 （ ＭＣ Ｌ ） 算法 是 一 种典 型 的基 于 贝 叶斯 滤波 的非 测距 算 法 ， 其基 本思 想 是用 Ｎ 个带 有权
技术 交流
２ ０ １ ４． ２ 数 据 通 信
Ｔ ｅ ｃ ｈ ｎ ｏ ｌ ｏ ａ ｖ Ｄｉ ｓ ｃ ｕ ｓ ｓ ｉ ｏ ｎ
一
种用于移动无线传感器网络的新型节点 定位算法
一
毛万 东 岳文振 俞 能海 （ 中国科学 院 电磁 空间信息重点实验室 中国科学技术 大学 合￣ Ｅ ２ ３ ０ ０ ２ ７ ）
数 据 通 信 ２ ０ １ ４ ． ２
（ １ ） 预 测 。在 预 测 阶段 ， 节点根 据ｔ 一 １ 时 刻样 本位
置 以及 节点 的最 大 移动 速 度 ， 可得 到 当前 时 刻
１ ，ｄ ｆ 川） ≤ ｒ Ｐ ｚ ＝ ｍ １ “
， ｝ 、
ｆ 】
关键词：移动传感器网络 ； 定位 ； 差分演化； 节点置信度 ； 蒙特卡罗盒
１ 引言
样 效 率和定 位精 度不 高 。对 偶 Ｍ Ｃ Ｌ 和混合 ＭＣ Ｌ 算 法
一
Ｌ 算 法 的预 测 和 滤波 部 分对 调 ，并 且 以 无 线传 感器 网络ＷＳ Ｎ（ Ｗｉ ｒ ｅ ｌ ｅ ｓ ｓ Ｓ ｅ ｎ ｓ ｏ ｒ Ｎ ｅ ｔ ｗ ｏ ｒ ｋ ） 将 传 统 的ＭＣ Ｃ Ｌ 算法或对偶Ｍ Ｃ Ｌ 算法。 Ｗａ ｎ ｇ 等［ ５ １ 作 为一 种 新 型 的 网络 技 术 广 泛 地用 于环 境 检 测 、 军 定的概率执行Ｍ 事 目标 跟 踪 、 医疗 卫 生 、 智 能 交 通 等 领域 Ⅲ 。一般 来 提 出 了 自适应 采样 的定 位算 法 ，即在 定位 预 测 阶段 说 ，没有位置信息的传感器节点感知的数据是没有 根据计算得到 的锚箱的面积来 自适应调整满足条件 Ｈａ ｍｉ ｄ 和 Ｍｅ ｈ ｄ ｉ 等［ ６ １ 提 出 了一种在 采样 箱 意义的。在ＷＳ Ｎ 中由于受到成本 、 功耗 、 环境等问题 的样 本数 目。 Ｃ Ｌ 中地 随 机 采 样 的算 的约 束 ， 人 工部 署或 给每个 节 点配 置一 个 Ｇ Ｐ Ｓ 装 置 是 内均 匀 的采 样 而 非 传 统 的 Ｍ 不 现 实的 。因此 ， 节点 自定位 技术 是ＷＳ Ｎ 的一 个重要 法 ，如此 采样 可 以有 效 的避 免样 本 点集 中到 一块 区 研 究课 题 。
２ 基 本 知 识
２ ． １ 网 络 模 型
根 据式 将 当前 样本 集 合 中不 满 足条 件 的样 本 点
直 到样 本 集合 中的 这里 ， 为 了方 便 和其 他算 法 进行 比较 ， 我 们 采用 滤 除 。重复 以上 预测 和滤 波过 程 ， 不满足滤 了一 种 普遍 应用 的 网络模 型 ］ 。该 模 型 有 如下 假 设 样本达到一定 的数 目。由于采样 区域较大 ，
（ ４ ） 节点密度ｍ 以及锚节点密度ｎ ， 雇 义为节点通
ｍ ２ ｎ ２
信圆内的节点数 目， 即
％ 。仃ｒ ， 凡 ｄ ＝ 。７ ｒ ｒ （ １ ）
将其 中两个 样本 的 比例 差分 与 第 三个 样 本相 加 得 到 变异样 本 ， 如下 ：
ｇ
＝
摘
要：在移动无线传感器网络 中， 节点获取 自身的位置信息十分重要 。传统的基于蒙特卡 罗的移动节
点定位算 法都存在 采样效 率低 以及 需要很 高锚 节点 密度 的问题 。针 对 以上 问题 ， 本文提 出 了一种基 于差 分演
化 的 蒙特 卡 罗盒 定位 算法 （ ＤＥ ＭＣ Ｂ ） 。 该 算法利 用差分演化 对样本进行优 化 ， 让样 本主 动向 节点真 实位 置靠近 ， 而不是被 动的被滤 除 ； 同时 ， 引入 节点置信 度 的概 念 用于计 算样本权 值 。仿 真 实验结果 表 明 ， 与传 统的定位 算 法相 比， 该 算法提 高 了定位精度 和收敛速 度 ， 并 能很 好地应 用 于低锚 节点 密度 的环境 。
和定 义 ：
波 条件 的样 本 较多 ， 所 以需 要 大 量 的重 复 采样 ， 因而
滤波 阶段 需要 较 高 的锚 节 点密 （ １ ） 传感 器 节点 部署 。ｍ个传 感器 节 点 随机 部署 采样 效 率较低 。同时 ， 在 面积 大小 为ｓ 的平 面矩形 内 ， 其 中ｎ （ ｎ ＜ ｍ Ｊ 个 节点 为 度才 能使 得样 本 向节点 真 实所在 区 域靠 近 。
于两个传感器节点ｐ 和ｇ ，如果他们在彼此的通信半 父 子 混合 个 体 适 应 度 值 竞 争来 获得 新 一 代 的种 群 。 Ｅ 中第ｇ 代种群表示为 ｇ ＝ ０ … １． ． ， Ｐ － １ ，每一代种 径ｒ 内， 那么他们能够直接通信 ， 称ｑ 是ｐ 的一 跳 邻 居 设Ｄ 群 中包 含Ｎ Ｐ 个 样 本 矢量 ，即 ｑ 是ｐ 的两跳邻居节点。 每个 样本 矢量 为Ｄ 维， ｌ ｌ ｘ （ ３ ） 节 点 运动模 型 。传感 器 节点 在任 何时 刻 的速
． ３ 差分 演化 算 法 锚 节点 ， ｍ — ｎ 个 为普 通节 点 ， 也称 盲节 点 。 锚节 点在 任 ２
何 时刻 都 能直 接 获取 自身 的位置 信 息 ，如 通过 配 置
差分演化算法Ｄ Ｅ（ Ｄ ｉ ｆ ｆ ｅ ｒ ｅ ｎ ｔ ｉ ａ ｌ Ｅ ｖ ｏ ｌ ｕ ｔ ｉ ｏ ｎ ａ １ ） 算 法
１ ５
＿ 蔓 ｇ 旦
收信 号强 度 （ Ｒ Ｓ Ｓ Ｉ ） 来 计算 节 点之 问的距 离 ， 再 将 该距 离值 用 于蒙 特卡 罗算 法 。之后 的很 多 学 者都 将 研究 放在 基 于测距 的节点 定 位 。但 是这 种 方 法 的硬 件 功 耗过大 ， 不 适合 传感 器低 功耗 的要 求 。 尽管 以上 改 进算 法在 一 定程 度 上 提 高 了采样 效 率 和定位 精度，但是 仍 然存 在 采样 效 率 不高 以及需 要高 锚节 点 密度 的 问题 。 为此 ， 本文 在 ＭＳ Ｌ 算法 等Ｉ ２ ］ 样 本可 能在 的区域 ， 如下 ：
域， 提高了采样效率。黄梅根 、 王洁嗣 、 Ｘ ｕ ［ ９ ］ 和Ｆ ａ ｎ ［ Ｏ ｌ 根
在移动环境下 ， 由于节点 间的距离动态变化 ， 传 据节 点运 动 的连 续性 ，利用 节 点前 几 个 时刻 的运 动 统 的算 法 的定 位精 度会 随着 节点 移 动速 度 的增 加 而 信 息 来预 测 当前 时刻 节 点可 能 在 的 区域 ，可 以在 一 Ｙ ｉ 和Ｙ ａ ｎ ｇ 等… ］ 提 出的基 于多 急剧 下降 。 ２ ０ ０ ４ 年， Ｈ ｕ 和Ｅ ｖ ａ ｎ ｓ ［ ２ ￣ 鉴 了机 器人 定位 领 定程 度上提 高 采样效 率 。
技 术 交 流
２ ０ １ ４ ． ２ 数 据 通 信
Ｔ ｅ ｃ ｈ ｎ ｏｌ ｏ ｑ ｖ Ｄｉ ｓ ｃ ｕ ｓ ｓ ｉ ｏ ｎ
对 原种 群 中的样 本 和变 异种 群 中 的样 本 进 行
其 中， （ ｘ ｉ ， Ｙ ｉ ｊ 为第ｉ 个 一跳 邻 居锚 节点 的坐 标 。对
融合 交叉， 产生 …… …ｐ ￣ 、 ｇ ） 。
Ｌ 和 ＭＳ Ｌ ＊ 算 网络节点定位中。 传统的Ｍ Ｃ Ｌ 算法存在采样效率低 、 节点 用 于 当前 节 点 的定 位 ，并提 出了ＭＳ 需要高锚节点密度来提高定位精度 的问题。针对 以 法 ，但是 该算 法 需要 同时传 递 邻居 节 点前 一 时 刻 的 通信代价较大。 Ｚ ｈ ａ ｎ ｇ ［ ３ 】 在Ｍ ｓ Ｌ 算法的启 上问题 ，很多研究人员在Ｍ Ｃ Ｌ 算法的基础上做 了很 样本和权值 ， Ｌ ， ＷＭＣ Ｌ — Ａ， ＷＭＣ Ｌ — Ｂ， 多 改进 。Ｂ ａ ｇ ｇ ｉ ｏ 等 提 出了 ＭＣ Ｂ（ Ｍｏ ｎ ｔ ｅ — Ｃ ａ ｒ ｌ ｏ ｌ ｏ ｃ ａ ｌ ｉ ｚ ａ — 发下 ，提 出 了改进 算法 ＷＭＣ ｔ ｉ ｏ ｎ Ｂ ｏ ｘ ｅ ｄ ） 算法ｆ ３ ｌ ， 通过 利 用 一 跳 和 两跳 邻 居 锚 节 点 算法 同时利用锚节点和普通邻居节点来建立采样约 提 高 了采样 效率 ， 但 是 该算 法 在 每个 时 刻都 要 来 建 立采 样 约束箱 ， 缩 小 了采 样 的 区域 ， 在 一定 程 度 束 箱 ， 因而计算量较大。Ｚ ｈ ｕ 和Ｚ ｈ ｏ ｎ ｇ 等㈣ 利用接 上 提 高 了采样 效 率 ，但 在锚 节点 密 度低 的情 况下 采 迭代运行 ，
［ １ ， Ⅳ 尸 ］ 之间的随机值 ， Ｆ 为缩放因子控制样本发生变
异 的速 度 。 ｇ ｇ 为 ￣样 本差 异 向量 ， 反 应群 体 对 的 差 重的样本来估计节点位置的后验概率密度 ，并且利 用 重 要性 采 样 迭代更 新 这 些样 本 。算 法 主要 分 为 两 异度 。 （ ２ ） 交 叉 个阶段 ： 预测 和滤 波 。
ｔ ｏ ｒ ｎ 和Ｐ ｒ ｉ ｃ ｅ ［ 于 １ ９ ９ ７ 年提 出用 于解 决 连 续 空 的Ｇ Ｐ Ｓ 等。普通节点不能直接获得其位置信息， 需要 最 早 由Ｓ 间的全 局优 化 问题 。其 基本 思想 是通 过 运 用 当前 种 通过定位技术来获取其位置的估计 。 （ ２ ） 节点 通信 模式 。 所 有 节点 的通 信半径 为ｒ 。 对 群个 体 的差 来重 组 得 到突 变种 群 ，然后 运 用直 接 的
．
节点 ； 如果ｐ 和ｇ 之 间 的距 离 满 足ｒ ≤ｄ （ Ｐ ， ｑ ） ≤２ ， ， 那 么
＝
．
＝
０… １． ． ， Ⅳｌ Ｐ＿１，
＝
ｌ ， ． ． ． ， Ｄ。Ｄ Ｅ 算 法 过