基于二次栅格划分的移动sink最小路径构建算法-西北工业大学学报.PDF

２０１６年１２月 西 北 工 业 大 学 学 报 Ｄｅｃ． ２０１６ 第３４卷第６期 Ｊｏｕｒｎａｌ ｏｆ Ｎｏｒｔｈｗｅｓｔｅｒｎ Ｐｏｌｙｔｅｃｈｎｉｃａｌ Ｕｎｉｖｅｒｓｉｔｙ Ｖｏｌ．３４ Ｎｏ．６ 基于二次栅格划分的移动ｓｉｎｋ最小路径构建算法 １，２ １ ３ ２ ２ ２ 王薇 ，史浩山 ，黄鹏宇 ，高宝建 ，牛进平 ，王举 æ １．西北工业大学 电子信息学院，陕西 西安　 ７１００７２；２．西北大学 信息科学与技术学院，陕西 西安　 ７１００６９ö ç ÷ è３．西安电子科技大学 通信工程学院，陕西 西安　 ７１００７１ ø 摘　 要：在无线传感器网络中引入移动ｓｉｎｋ 能够有效解决能量空洞问题，从而提高无线传感器网络 的生存时间。 但是移动ｓｉｎｋ 的移动速度限制通常会影响数据收集的时延特性，文章的研究重点即如 何为移动ｓｉｎｋ构建最佳巡航路径，从而减小信息收集时延。 充分利用传感器节点的通信范围，将构建 最佳路径问题转化为求解带邻域的旅行商问题ＴＳＰＮ（ｔｒａｖｅｌｉｎｇ ｓａｌｅｓｍａｎ ｐｒｏｂｌｅｍ ｗｉｔｈ ｎｅｉｇｈｂｏｒｈｏｏｄｓ）， 并提出了一种基于二次栅格划分的可变长编码单亲遗传算法的最佳路径构建方法。 该算法首先在网 络区域中使用粗粒度栅格进行划分，并利用可变长度编码的单亲遗传算法获得最佳途经栅格，从而构 造出初始最佳路径。 然后对于每一个途经栅格再次使用细粒度栅格进行划分以优化收集路径。 仿真 结果表明，新算法能够获得更短的数据收集路径，大幅度减低了网络信息收集时延，有效地拓展了网 络的生存时间。 关　 键　 词：无线传感器网络；移动ｓｉｎｋ；ＴＳＰＮ；栅格；最短路径 中图分类号：ＴＰ３９３　 　 　 文献标志码：Ａ　 　 　 文章编号：１０００⁃２７５８（２０１６）０６⁃１０１６⁃０６ 　 　 近年来无线传感器网络 ＷＳＮ（ｗｉｒｅｌｅｓｓ ｓｅｎｓｏｒ 解决能量空洞问题。 ｎｅｔｗｏｒｋ）在环境监测、火情监测、战场探察等方面得 近年来，移动 ｓｉｎｋ 的概念应运而生，利用移动 ［１］ 到了广泛的应用 。 在这些网络中，大量的感知节 ｓｉｎｋ可以优化数据的采集过程，并延长整个网络的 点被部署到被测区域中，每当有敏感事件发生时，传 ［３⁃５］ 生存时间 ，也可利用移动ｓｉｎｋ来辅助节点定位， 感器节点将收集到的数据经由多跳路径传输给静止 ［６⁃７］ 由此显著提高定位精度 。 在以上的研究中，我 的汇聚节点（ｓｉｎｋ 节点）。 由于全网收集的信息都 们可以看到由于移动节点收集信息时更贴近传感器 要逐渐中转、汇聚，因此必然会导致靠近 ｓｉｎｋ 节点 节点，因此更利于提高信息收集的数量与质量，很好 的普通节点需要承载更多传输负荷，从而消耗更多 地解决ｓｉｎｋ 固定时节点间耗能均衡的问题。 的能量，最终加速其死亡，并缩短了整个网络的生存 但是在实际的应用环境中，ＷＳＮ布设范围通常 ［２］ 时间，这就是所谓的“能量空洞”问题 。 较大，而受数据传输和承载平台的限制，移动 ｓｉｎｋ 在本项目组所承担的野生金丝猴相关研究课题 的移动速度大多不高，因此与静止 ｓｉｎｋ 节点相比 中，我们也发现了“能量空洞”问题的存在。 我们将