一种线型结构无线传感器网络的时间同步算法.pdf

第 4 l卷 第 2期 2 01 5年 2月 工矿 自 动化 I n dus t r y a n d M i ne Aut o ma t i on V0 l _ 4 1 NO ． 2 Fe b ． 2 O 1 5 文章 编 号 1 6 7 1 2 5 1 X 2 0 1 5 0 2 0 0 7 5 0 4 D OI 1 0 ． 1 3 2 7 2 5． i s s n ． 1 6 7 l _ 2 5 l X ． 2 0 1 5 ． 0 2 ． 0 2 1 卑璐璐 ， 张然， 韩丽娜， 等． 一种线型结构无线传感器网络的时间同步算法[ J ] ． 工矿 自动化， 2 0 1 5 ， 4 1 2 7 5 7 8 ． 一 种线型结构无线传感器网络的时间同步算法 卑 璐璐 ， 张 然 。 ， 韩 丽娜 ， 李 菲菲 1 ． 中 国矿 业 大学 信 息与 电气 工程 学 院 ，江苏 徐 州 2 2 1 1 1 6 ； 2 ． 中国矿业 大学 物联 网 感知矿 山 研究 中心 ，江苏 徐 州 2 2 1 0 0 8 摘 要 针 对 煤矿 井 下液 压 支架模 糊控 制监 测 系统 网络拓 扑 ， 提 出 了一 种适 用 于线 型结构 无 线传感 器 网络 时间同步算法。该算法同步过程分为簇 间同步和簇 内同步 ， 簇 间同步采用双 向同步机制修正时间偏移的 法减 少同步误差 ， 簇 内同步通过最小平方线性拟合方法构造逻辑时钟函数 ， 从而得到簇 内任一节点与簇首 点 的频偏 和相 偏 估计 值 ， 以提 高同步精 度 。仿 真结 果表 明 ， 该 算 法能有 效 减 少时 间同步误 差和 能量 消耗 。 关 键 词 线型 结构 ；无线传 感 器 网络 ；时间 同步 ；簇 间 同步 ；簇 内同步 中图分 类号 TD 6 5 5 文献 标 志码 A 网络 出版 时间 2 0 1 5 0 2 0 3 1 5 2 4 网络 出版 地址 h t t p ／ ／ ww w． c n k i ． n e t ／ k c ms ／ d e t a i l ／ 3 2 ． 1 6 2 7 ． TP ． 2 0 1 5 0 2 0 3 ． 1 5 2 4 ． 0 2 1 ． h t ml A t i me s y n c h r o n i z a t i o n a l go r i t h m f o r wi r e l e s s s e n s o r ne t wo r k o f l i n e a r s t r u c t u r e BEI Lul u 一， ZH ANG Ra n 一， H AN Li na 一，LI Fe i f e i 。 1． Sc ho ol o f I nf o r m a t i o n a nd El e c t r i c a l En gi n e e r i n g，Chi n a Uni v e r s i t y o f M i n i ng a n d Te c hn o l og y， Xu z h o u 2 2 1 1 1 6 ，Ch i n a ；2 ． I n t e r n e t o f Th i n g s P e r c e p t i o n Mi n e Re s e a r c h Ce n t e r ，Ch i n a Un i v e r s i t y o f Mi n i n g a n d Te c h n o l o g y ，Xu z h o u 2 2 1 0 0 8 ，Ch i n a Ab s t r a c t I n vi e w o f ne t wo r k t o po l og y of f uz z y c o nt r o l a nd m o ni t or i n g s ys t e m o f un de r g r ou nd hy dr a u l i c s u ppo r t ，t he p a pe r p r op os e d a t i m e s y nc hr on i z a t i o n a l g o r i t hm a d a pt e d t o wi r e l e s s s e n s o r ne t wo r k o f l i n e a r s t r u c t u r e wh i c h i n c l u d e s a d j a c e n t c l u s t e r s y n c h r 0 n i z a t i o n a n d i n t e r n a l c l u s t e r s y n c h r o n i z a t i o n． Th e a d j a c e n t c l u s t e r s y n c h r o n i z a t i o n a d o p t s b i s y n c h r o n o u s me c h a n i s m wh i c h c o r r e c t s t i me o f f s e t t o de c r e a s e s v nc hr on i z a t i o n e r r o r s ． The i nt e r n a l c l us t e r s y nc hr o ni z a t i on o bt a i ns f r e q ue n c y a nd p ha s e o f f s e t b e t we e n a n y n o d e a n d h e a d n o d e i n t h e c l u s t e r b y c o n s t r u c t i n g l o g i c c l o c k f u n c t i o n t h r o u g h l e a s t s q u a r e l i n e a r f i t t i ng m e t ho d t o i mpr o ve s y nc hr on i z a t i o n pr e c i s i o n．The s i mul a t i on r e s ul t s s h o w t ha t t h e a l go r i t h m c a n e f f e c t i v e l y r e du c e s yn c h r o ni z a t i o n e r r or s a nd e ne r g y c on s u m p t i o n． Ke y wo r d s l i n e a r s t r u c t u r e ； wi r e l e s s s e n s o r n e t wo r k； t i me s y n c h r o n i z a t i o n； a d j a c e n t c l u s t e r s y nc hr o ni z a t i o n；i nt e r na 1 c l us t e r s y nc hr on i z a t i o n 收稿 日期 2 0 1 4 1 2 2 4 ； 修回 日期 2 0 1 5 0 1 1 2 ； 责任编辑 盛男 。 基金项 目 “ 十二五” 国家科技支撑计划资助项 目 2 O 1 2 B AH1 2 B 0 1 。 作者简介 卑璐璐 1 9 8 1 一 ， 女 ， 辽 宁铁岭人 ， 博士研究生 ， 主要研究方 向为无线通信和微波技术 ， E ma i l b e i l u l u 1 6 3 ． C O 1T I 。 [ 7] [8 ] 吴绍华 ， 张钦宇 ， 张乃 通． UwB无 线传感 器 网络 中基 于匹配滤 波检 测 的 T OA估 计 [ J ] ． 软件 学 报 ， 2 0 0 9 ， 2 O 1 1 3 0 1 0 3 0 2 2 ． ALS I NDI N ． LI Xi n r o n g， P AHLAVAN K． An a l y s i s of t i me o f a r r i v a l e s t i ma t i o n us i ng wi de ba n d me a s u r e me n t s o f i n d o o r r a d i o p r o p a g a t i o n s [ J ] ． I E E E [ 9] [ 1 O ] Tr a ns a c t i on s on I ns t r ume n t a t i o n a n d M e a s u r e me nt ， 2 0 0 7， 5 6 5 t 5 3 7 - 1 5 4 5 ． 刘琚 ， 李静 ． 一 种在非 视距 环境 中 的 T D 0A ／ AO A混 合定位方法[ J ] ． 通信学报 ， 2 0 0 5 ， 2 6 5 6 3 6 8 ． 翟彦蓉 ， 黄欢 ， 张 申 ， 等． 基 于 D O A 和 TD OA的井 下 定位算法研究 E J ] ． 工矿 自动化 ， 2 0 1 3 ， 3 9 1 1 5 7 6 0 ． 的方节 7 6 工矿 自动化 2 0 1 5年 第 4 1卷 0 引言 在煤 矿 井 下 放顶 煤 开 采 和安 全 生 产过 程 中 ， 液 压 支架 工作状 态 的实 时监测 非 常重要 。现有 的液压 支 架监测 系 统存 在线 路 易 中断 、 不 便 于 数 据传 输 等 缺点l 】 ] 。无线传感器 网络因其布置灵活、 维护方便 、 控 制简单 而 得到越 来 越多 的应用 _ 2 。 ] ， 因此将 无 线传 感 器 网络 应 用 于 液 压 支 架 监 测 系统 具 有 重 要 的 意 义 。时间同步是无线传感器 网络应用 的关键技术 ， 关 于无 线传 感器 网络 时 间同步 算法 的研 究 主要 归 为 3类 ① 提高时 间同步精度 的相关算法研究 ， 如传 感 器 网络 时 间 同 步 协 议 T i mi n g s y n c P r o t o c o l f o r S e n s o r Ne t wo r k s ， TP S N 算 法 ； ② 提 高 时 间同步 中 相 关指 标 ， 如开 销 、 鲁 棒 性 等 的相 关 算 法 研 究 ， 如 参 考 广播 同步 Re f e r e n c e B r o a d c a s t S y n c h r o n i z a t i o n ， RB S 算 法 ； ③ 时 间 同步 算 法 用 于 某 一 特定 网 络 拓 扑 结构 的优 化 及改 进 ， 如 针 对 网状 网 络 的洪 泛 时 间 同 步协议 F l o o d i n g T i me S y n c h r o n i z a t i o n P r o t o c o l ， F TS P 算 法_ 4 ] 。本 文 基 于煤 矿 井 下 液 压 支架模 糊控 制 监测 系 统 的 线 型结 构 网络 拓 扑 ， 提 出 了一 种适用 于 线型结 构 的无 线传 感器 网络 时 间同步 算 法 T i me S y n c h r o n i z a t i o n A l g o r i t h m o f L i n e a r S t r u c t u r e ， TS AL S 。该 算 法 通 过 基 于 双 向 同步 机 制 的簇 间 同步 和采 用最 小平 方线 性拟 合 的簇 内 同步 方法 ， 可 提高 全 网时 间同步 精度 ， 有效 解决 由于时 间 同步 误差 造成 的液压 支架模 糊控 制偏 差 问题 。 1 液压 支 架模糊 控 制监 测 系统 液压支 架模糊 控 制监 测系 统对 监测 到 的压 力 数 据进行模 糊识 别 ， 得 到 液压 支架 所 处 的工 作状 态 ， 当 判断 液压支架处 于增阻工作 状态且 增 阻时间过 长时 ， 系统 可及时通 知 液压 支架 操作 人 员增 大液 压 支架 压 力 ， 辅 助实现顶煤 破碎 ， 提高 放顶煤开采效 率[ 5 ] 。 采 用 2 ． 4 GHz无 线 传输 的无 线 传 感 器 网络 节 点 可有 效避 免 有线 网络 布 线 带来 的不 便 ， 能够 很 好 地适 应 煤矿 井 下 的实际 应用 环境 。液压 支 架模糊 控 制监测系统无线传感器网络部署 在液压支架 的前 后柱和顶板布置终端节点 ， 终端节点将采集 的液压 支架压力数据实时传递到簇首节 点， 簇首节点将数 据转发至 [ 聚节点 ， 最后通过煤矿井下千兆以太环 网传 送至 地面 监测 中心 。液 压支 架模糊 控 制监 测系 统 网络拓 扑如 图 1所 示 ， 工 作 面 无 线 传 感器 网络 覆 盖 的 宽度及 高 度 范 围远 小 于 其 长度 范 围 ， 网络 节 点 基本 呈线 型结 构分 布 。 汇聚节点 O 簇首节点 终端节点 图 1 液压支架模糊控制监测系统 网络拓扑 2算法 实现 为 了使整 个 网络 结构 更 加 合 理 ， 且 不 至 于产 生 额 外 的能量 消耗 ， 首先 在 T S AL S中设 定 如 下 条 件 ① 簇首节点时间同步请求能且仅能被其他簇首节 点 接受 并进 行传 递 ； ② 终端 节点 能且 仅 能 和距 离 其 最 近 的簇首 节 点通信 。 TS AL S分 为 网络 结 构建 立 阶段 和 时 间 同步 阶 段 。网络结 构 建立 阶段 由汇 聚节 点 发 起 ， 每个 簇 首 节点将与其相邻的簇首节点保存 至本地路 由表 中。 在 形 成簇 时 ， 簇 首节 点需 限制 终端 节点 数 目， 平衡 网 络结 构 ， 防止 1个 簇 内终 端 节 点 过 多 ， 影 响 通 信 质 量 。时 间同步 阶段 分为 簇 间同步 和簇 内同步 。 2 ． 1 簇 间 同步 簇 问 同步 由汇 聚节 点 周期 性 发 起 ， 汇 聚 节点 或 上层簇首节点 向与其相邻的下层簇首节点发送同步 分组 数据 包 ， 其 中包含 源节 点 I D、 目标 节点 I D、 层次 号 和 同步序号 。 下层 簇首 节点 接 收到 汇聚节 点或 上层 簇首 节点 的 同步分 组数 据包 后 ， 立 即返 回应答 分组 数据 包 ， 其 中包 含 源节 点 I D、 同步序 号和 发送 时间 t 。 汇 聚节 点或 上层簇 首 节点 收到 下层簇 首 节点 回 复 的应答 分组 数 据 包后 记 录本 地 时 间 t ， 比较 同 步 序 号是 否和其 发送 的同步 序号一 致 。如果 一 致则 返 回应答确认分组数据包 ， 其中包含 t ， t 以及返 回应 答 确认 分组 数据 包 的时 间 t 。 ； 如 果不 一 致 则 丢 弃 该 数 据包 ， 继续 等 待 下层 簇 首 节 点 应 答 。若 在 超 过 设 定 的 时间 内汇 聚节点 或上 层簇 首节 点仍 没有 收 到下 层簇首节点的应答 ， 则重新发起 同步过程 。 下层簇首节点接收到应答确认分组数据包后 ， 记录本地时间 t 。通过 3次信息交换 ， 下层簇首节 点可 得到 t 一t 4个 时 间 点 ， 并 通过 式 1 得 出与 汇 聚节点或上层簇首节点 的时钟偏差 △， 进而可 以调 整本地时钟与汇聚节点或上层簇首节点时钟同步。 △ 一 二 1 下层簇首节点修改其时钟偏移量后 ， 保证此时 与汇 聚 节 点 或 上 层 簇 首 节 点 时 钟 一 致 ， 同 步 过 程 结束 。 2 0 1 5年第 2期 卑璐璐等 一种线型结构无线传感器网络的时间同步算法 7 7 2 ． 2 簇 内同步 簇 内同步 采用 基 于发 送 一 接 收 机 制 和 接 收 一接 收机制相结合的方式完成同步过程 。首先簇首节点 周 期 性发 送广 播 同 步数 据 包 ， 同 时选 择 簇 内某 一 节 点为参考节点进行双向同步。簇首节点通过与参考 节点交换时间戳信息得到参考节点接收广播信息的 基 准 时 间 T ， 然 后簇 首节 点 将 该基 准 时 间 进行 广 播发送 ， 其他簇 内节点接收该基准 时间后与本地记 录时 间 组 成 时间戳 对 [ ￡ ， 丁 ] i 为 正 整 数 ， 表 示 时 间戳对 组 数 ， 并 将 其 存 人 数 据 缓 冲 区 ， 通 过 读 取 缓 冲区 内一 定 时 间 的历 史 数 据 完 成 曲线 拟 合 ， 得 到 本地 逻辑 时 钟 函数 ， 进 而修 改 和调 整本 地 时钟 ， 完成 簇 内节 点 的同步 。 2 ． 3逻 辑 时钟 构造 为 得 出本 地 逻 辑 时 钟 函数 ， 首先 需 建 立 其 对应 的数 学模 型 ] T i 一 a t b 2 式中 n 为簇内任一节点 k的本地记 录时问相对簇 基准 时 间 的频偏 ； b 为簇 内任 一 节 点 k的 本 地记 录 时 间相 对簇 基准 时 间 的相 偏 。 若 要 通 过该 模 型 求 出 实 际物 理 时 间 ， 需 对 变量 n ， b 进行求解 。通过多轮簇内同步过程 ， 所有簇内 节 点能 够获 取 多组 时 间戳 对 E t i ， T ] ， 对 多 组 历 史 数据 进行 曲线 拟 合 ， 就 可 得 到 簇 内任 一 节 点 尼的 本 地记 录时 间与该 簇基 准 时间 的频 偏 n 和 相偏 b 。 设数据缓冲区中有 m个时间戳对I t i ， T ] ， 根据最小平方线性拟合方法 ， 残差平方和为 Q一 [ 口 t 十b 一丁 ] 。 3 对 Q求偏 导并 令 其为 0 ， 则 fO a k 一 蓦 2 [ T ㈤ ～ _ 0 { ‘ 卅 ‘ 4 l 一 耋 2 ㈤ ] 一 。 整 理可得 ∑ b ∑ 一∑T 一0 J 5 l n ∑￡ b 一∑T 一0 则 ∑ [ 丁 z ] 一∑f ∑丁 i 1 t 1 i 一 1 ∑￡ 一[ ∑ ] 。 丁㈤一 6 采用 8个数据进行线性回归拟合能够在保证计 算结果较为精确的条件下尽可能减少计算量 ] ， 因 此 需在 簇 内任一 节 点 忌的本地 内存 中建 立 1个 可包 含 8 组 时 间戳对 的队列形 式数 据缓 冲区 。当缓 冲区 数 据数 量达 到设 置 的 8时 ， 可 按式 6 计 算得 出簇 首 节点与簇 内任一 节点 是的相对 时钟 频偏 12 和相 偏 b ， 簇 内节点则可根据该值调整其 内部时钟。 3算 法仿 真 采 用 NS 2平 台[ 8 对 TS AL S进 行 仿真 验证 。为 增 强仿 真 环境 的 真实 性 ， 所 有 节 点 按 实 际 情况 进 行 布置 终 端 节 点呈 直 线 分 布 ， 共 有 1 6 0个 终 端节 点 ， 其 中距 离 汇 聚 节 点 最 近 的终 端 节 点 编 号 为 0 ， 距 离 汇 聚节 点最 远 的终 端 节 点 编 号 为 1 6 0 ， 相 邻 2个 终 端节 点之 间 的距 离 为 1 ． 5 m； 簇 首节 点平 均 分 布在 终端节点的上方 ， 共有 1 7个簇首节点， 相邻 2个簇 首节点之间的距离为 1 5 m。设仿真时间为 4 0 0 0 S ， 仿真周期为 2 0 s ， 则 仿真轮数为 2 0 0 。分别从 同步 精 度及 能量 消耗 2个 方面 比较 T P S N 与 T S AL S的 性 能 。 3 ． 1 同步误 差 3 ． 1 ． 1全 网 同步 误 差 在 线 型 网络 拓 扑 结 构 中 ， 较 远 节 点 必须 通 过 多 跳 才 能 与 汇 聚 节 点 通 信 ， 导 致 同 步 误 差 增 大 。 TP S N 与 TS AL S同步误差 如 图 2 所 示 ， 2种 算法 的 同步误差均随着时间同步报文传输跳数的增加而增 大 ， 但采 用 T P S N 产 生 的 同 步 误 差 远 高 于 采 用 TS AL S产 生 的 同步误差 ， 且 TS AL S同步 误 差 的增 加 幅度 并 不 明显 。这是 由于 TS AL S在 簇 问 同步 时 采 用双 向同步 技术 ， 能 够保证 其 同步精 度较 高 ； 在簇 内同步时 采用 基 于 接 收 一 接 收 机 制 和 发 送 一 接 收单 向 同步机 制相结 合 的方 法 ， 消 除 了 同步 消 息 的发 送 时延 和传播时延 ， 并且在簇 内节点采用 构造逻 j Il】j 9 1 1； 匣 节点编号 图 2 T P S N与 T S AL S同步误差 比较 7 8 工矿 自动化 2 0 1 5年 第 4 1卷 U 50 l 00 1 3 U ZU u 时间同步轮数 图 3 T P S N 与 TS A L S在不 同时间同步 周 期下 的同步误 差 比较 3 ． 2 能量 消耗 在无线传感器 网络中， 绝 大部分能量消耗在节 点 数据 发 送 和 接 收 时 ， 所 以 可 通 过 分 析 T P S N 与 TS AL S的同步 报 文 数来 近似 分 析 算法 能 耗 。通 过 仿 真得 到 TP S N 的 总报文数 为 1 2 1 7 9 个 ， TS AL S的 总报 文数 为 7 4 7 9个 ， 可 知 TS AL S比 T P S N 更 加 节省 能量 ， 从 而可 延长 整个 网络及 节点 的生 存周 期 。 这是 由 于 TS AL S同步过程 分 为簇 间 同步 和簇 内 同 步， 当远端节点需要 同步时 ， 只要和簇首节点进行簇 间 同步 即 可 ， 而 T P S N则 需 消耗 更 多 能量 转 发 同步 报文 。 4 结语 结合液压支架模糊控制监测系统 的网络拓扑 ， 提 出 了一 种 适 用 于 线 型 结 构 的时 间 同步 算 法 Ts AL S 。该 算 法 中簇 间 同 步 采 用 标 准 的 双 向 同步 机制减小同步误差 ； 簇 内同步采用构造逻辑时钟的 方法 ， 并对 多组 时 间戳 对 进 行 最 小平 方线 性 拟 合 来 提高 同步 精 度。仿 真 结 果表 明， 与 T P S N 相 比， T S AL S在线型结构的无线传感器 网络 中具有更高 的 时间 同步精 度 和较小 的能 量消 耗 。 参考文献 E 1 ] 王桃 ， 刘晓文 ， 乔欣 ， 等． 基 于无线 传感 器 网络的液 压 支架压 力 监 测 系 统 设 计 [ J ] ． 工 矿 自 动 化 ， 2 0 1 4 ， 4 0 6 7 - 1 0 ． E 2 ] 周嗣 勇． 煤 矿安全监控无线传感器 网络协议与定 位技 术研究[ D ] ． 北京 ； 北京交通 大学 ， 2 0 0 7 ． r 3 ] ZHANG X H．Au t o ma t i c c a l i b r a t i o n o f me t h a n e mo n i t o r i n g b a s e d o n w i r e l e s s s e n s o r n e t wo r k [ c] ／ ／ I n t e r n a t i o na 1 Con f e r e n c e on W i r e l e s s C o mmu n i c a t i o n s ， Ne t wo r k i n g a n d M o b i l e C o mp u t i n g， Be ij i n g， 2 0 0 8 1 - 4 ． [ 4 ] 张然 ， 李菲菲 ， 张 申， 等． 一种矿 震监测 的 WS Ns 按需 分层 时 间 同 步算 法 [ J ] ． 中 国矿 业 大 学 学 报 ， 2 0 1 4 ， 4 3 6 1 0 4 6 1 0 5 0 ． [ 5 ] 张 申， 黄欢 ， 翟彦蓉 ， 等． 液压 支架工 作状 态模糊 识别 系统研究I- J ] ． 工矿 自动化 。 2 0 1 2 ， 3 8 6 5 2 5 5 ． [ 6 ] 全渝娟 ， 刘桂雄 ， 刘波 ， 等 ． 具有漂移补偿 的 R C R时钟 同步模型E J ] ． 华南理工大学 学报 自然科学 版 ， 2 0 1 0 ， 3 8 5 7 6 7 9 ． E T ] MAR O TI M， KUS Y B， S I MO N G， e t a 1 ． Th e f l o o d i n g t i me s y n c h r o n i z a t i o n p r o t o c o 1 [ c ] ／ ／ P r o c e e d i n g s o f t h e 2 n d I n t e r n a t i o n a l Co n f e r e n c e o n E m b e d d e d Ne t wor ke d S e ns or S ys t e m s， Ba l t i mor e， 2 0 04 3 9 4 9． E 8 3 徐雷鸣 ， 庞博 ， 赵 耀． NS与网络模 拟E M] ． 北京 人 民 邮 电出版社 ， 2 0 0 3 ． [ 9 ] GAN E R I WAL S ， KUMAR R， S R I VAS T AVA M B ． Ti mi n g s y n c p r o t o c o l f o r s e n s o r n e t wo r k s[ C] ／ ／ Pr o c e e di n gs of t he 1 s t I nt e r n a t i ona l Co nf e r e nc e o n Emb e d d e d Ne t wo r k e d S e n s o r S y s t e ms ， Lo s An g e l e s ， 20 03 1 3 8 1 49． E 1 o ] 杨春 明． 无 线传感 器 网络 时间 同步算 法 的研究 E D ] ． 合肥 中国科学技术大学 ， 2 0 0 8 ． [ 1 1 ] S I C HI T I U M L， VE E R ARI T T I P HA N C ． S i mp l e ， ac c ur a t e t i me s yn c hr oni z a t i o n f or wi r e l e s s s e ns or n e t wo r k s [ C 3 ／ ／P r o c e e d i n g s o f t h e I E E E Wi r e l e s s Commun i c a t i o ns a nd Ne t wor ki n g Conf e r e n c e， Los Ange l e s， 20 03 1 2 66 1 27 3 ．