基于二次栅格划分的移动sink最小路径构建算法 -- 西北工业大学学报,2016,34(6):1016-1021
论文:2016,Vol:34,Issue(6):1016-1021
引用本文:
王薇, 史浩山, 黄鹏宇, 高宝建, 牛进平, 王举. 基于二次栅格划分的移动sink最小路径构建算法[J]. 西北工业大学学报
Wang Wei, Shi Haoshan, Huang Pengyu, Gao Baojian, Niu Jinping, Wang Ju. A Routing Planning Algorithm base on Twice Grid Division for Mobile Sink[J]. Northwestern polytechnical university

基于二次栅格划分的移动sink最小路径构建算法
王薇1,2, 史浩山1, 黄鹏宇3, 高宝建2, 牛进平2, 王举2
1. 西北工业大学 电子信息学院, 陕西 西安 710072;
2. 西北大学 信息科学与技术学院, 陕西 西安 710069;
3. 西安电子科技大学 通信工程学院, 陕西 西安 710071
摘要:
在无线传感器网络中引入移动sink能够有效解决能量空洞问题,从而提高无线传感器网络的生存时间。但是移动sink的移动速度限制通常会影响数据收集的时延特性,文章的研究重点即如何为移动sink构建最佳巡航路径,从而减小信息收集时延。充分利用传感器节点的通信范围,将构建最佳路径问题转化为求解带邻域的旅行商问题TSPN(traveling salesman problem with neighborhoods),并提出了一种基于二次栅格划分的可变长编码单亲遗传算法的最佳路径构建方法。该算法首先在网络区域中使用粗粒度栅格进行划分,并利用可变长度编码的单亲遗传算法获得最佳途经栅格,从而构造出初始最佳路径。然后对于每一个途经栅格再次使用细粒度栅格进行划分以优化收集路径。仿真结果表明,新算法能够获得更短的数据收集路径,大幅度减低了网络信息收集时延,有效地拓展了网络的生存时间。
关键词:    无线传感器网络    移动sink    TSPN    栅格    最短路径   
A Routing Planning Algorithm base on Twice Grid Division for Mobile Sink
Wang Wei1,2, Shi Haoshan1, Huang Pengyu3, Gao Baojian2, Niu Jinping2, Wang Ju2
1. School of Electronics and Information, Northwestern Polytechnical University, Xi'an 710072, China;
2. School of Information and Technology, Northwest University, Xi'an 710069, China;
3. School of Telecommunications Engineering, Xidian University, Xi'an 710071, China
Abstract:
Introduce mobile sinks into wireless sensor networks can balance the energy level of the sensor nodes, resolve the hotspot problem and prolong the lifetime of the whole network. However, the mobility of the sink may also introduce additional delays. Therefore, it is important to design an efficient routing protocol for the mobile sink. In this paper, we deduce this routing planning problem into a Traveling Salesman Problem with Neighborhoods (TSPN). In addition, we propose a routing design algorithm base on twice grid division and variable-length Partheno-genetic Algorithm. In this algorithm, we divide the network area with the grids coarse-grained, and obtain the grids on the best path with variable-length Partheno-genetic Algorithm. We then divide every grid on the path with the grids fine-grained in order to optimize the path. Finally, we implement this algorithm in Matlab and the simulation results show that the proposed algorithm can significantly improves the efficiency and effectiveness of the routing planning for the mobile sink.
Key words:    wireless sensor network    mobile sink    TSPN    routing planning    grid division   
收稿日期: 2016-04-12     修回日期:
DOI:
基金项目: 国家自然科学基金(61170218、61602379)与陕西省教育厅自然科学基金(15JK1742、12JK0937)资助
通讯作者:     Email:
作者简介: 王薇(1977-),女,西北工业大学博士研究生,西北大学讲师,主要从事信息网络理论、无线传感器网络研究。
相关功能
PDF(1219KB) Free
打印本文
把本文推荐给朋友
作者相关文章
王薇  在本刊中的所有文章
史浩山  在本刊中的所有文章
黄鹏宇  在本刊中的所有文章
高宝建  在本刊中的所有文章
牛进平  在本刊中的所有文章
王举  在本刊中的所有文章

参考文献:
[1] Ou C H. A Localization Scheme for Wireless Sensor Networks Using Mobile Anchors With Directional Antennas[J]. IEEE Sensors Journal, 2011, 11(7):1607-1616
[2] Olariu S, Stojmenovi I. Design Guidelines for Maximizing Lifetimeand Avoiding Energy Holes in Sensor Networks with Uniform Distribution and Uniform Reporting[C]//IEEE Infocom, 2006:1-12
[3] Zhao M, Yang Y. Bounded Relay Hop Mobile Data Gathering in Wireless Sensor Networks[J]. IEEE Trans on Computers, 2012, 61(2):265-277
[4] Lin K, Chen M, Zeadally S, et al. Balancing Energy Consumption with Mobile Agents in Wireless Sensor Networks[J]. Future Generation Computer Systems, 2012, 28(2):446-456
[5] Guo S, Wang C, Yang Y. Joint Mobile Data Gathering and Energy Provisioning in Wireless Rechargeable Sensor Networks[J]. IEEE Trans on Mobile Computing, 2014, 13(12):2836-2852
[6] Liao W H, Lee Y C, Kedia S P. Mobile Anchor Positioning for Wireless Sensor Networks[J]. IET Communications, 2011, 5(7):914-921
[7] Chen H, Shi Q, Tan R, et al. Mobile Element Assisted Cooperative Localization for Wireless Sensor Networks with Obstacles[J]. IEEE Trans on Wireless Communications, 2010, 9(3):956-963
[8] Gao S, Zhang H, Das S K. Efficient Data Collection in Wireless Sensor Networks with Path-Constrained Mobile Sinks[J]. IEEE Trans on Mobile Computing, 2010, 10(4):592-608
[9] Ma M, Yang Y, Zhao M. Tour Planning for Mobile Data-Gathering Mechanisms in Wireless Sensor Networks[J]. IEEE Trans on Vehicular Technology, 2013, 62(4):1472-1483
[10] 郜帅, 张宏科. 时延受限传感器网络移动Sink路径选择方法研究[J]. 电子学报, 2011, 39(4):742-747 Gao Shuai, Zhang Hongke. Optimal Path Selection for Mobile Sink in Delay-guaranteed[J]. Acta Electronica Sinica, 2011, 39(4):742-747(in Chinese)
[11] Xing G, Wang T, Jia W, et al. Rendezvous Design Algorithms for Wireless Sensor Networks with a Mobile Base Station[C]//ACM International Symposium on Mobile Ad Hoc Networking and Computing, 2008:231-240
[12] Xing G, Wang T, Xie Z, et al. Rendezvous Planning in Wireless Sensor Networks with Mobile Elements[J]. IEEE Trans on Mobile Computing, 2008, 7(12):1430-1443
[13] 袁远, 彭宇行, 李姗姗,等. 高效的移动sink路由问题的启发式算法[J]. 通信学报, 2011, 32(10):107-117 Yuan Yuan, Peng Yuxing, Li Shanshan, et al. Efficient Heuristic Algorithm for the Mobile Sink Routing Problem[J]. Journal on Communications, 2011, 32(10):107-117(in Chinese)
[14] He L, Pan J, Xu J. A Progressive Approach to Reducing Data Collection Latency in Wireless Sensor Networks with Mobile Elements[J]. IEEE Trans on Mobile Computing, 2013, 12(7):1308-1320