考虑最大暴露值的无线传感器网络最小暴露路径优化算法

doi:10.3969/j.issn.1000-1093.2018.04.014

兵工学报 ›› 2018, Vol. 39 ›› Issue (4): 743-752.doi: 10.3969/j.issn.1000-1093.2018.04.014

考虑最大暴露值的无线传感器网络最小暴露路径优化算法

杨廷鸿^1,2，方海洋¹，姜大立¹，方玲²

(1.陆军勤务学院军事物流系, 重庆 401331; 2.陆军勤务学院基础部, 重庆 401331)

收稿日期:2017-08-01 修回日期:2017-08-01 上线日期:2018-05-30
作者简介:杨廷鸿(1978—), 男, 博士研究生。E-mail: yth_ah@163.com
基金资助:
国家自然科学基金项目(61372194、61672038、70871119、61502520、10971227、21377166、81260672)

Optimization Algorithm for Minimum Exposure Path in Wireless Sensor Networks Considering Maximum Exposure

YANG Ting-hong^1,2, FANG Hai-yang¹, JIANG Da-li¹, FANG Ling²

(1.Department of Military Logistics, Army Logistics University, Chongqing 401331, China;2.Department of Foundation, Army Logistics University, Chongqing 401331, China)

Received:2017-08-01 Revised:2017-08-01 Online:2018-05-30

摘要/Abstract

摘要： 为解决当前多数算法在求解无线传感器网络中最小暴露路径（MEP）时未考虑其路径上最大暴露值的问题，将该信息融合到经典Dijkstra算法（DA）中，构建了考虑最大暴露值的DA（DAME），并与导向相遇随机漫步（TGSARWI）算法相结合，形成TGSARWI DAME. 仿真结果表明：该算法在维持计算复杂度与TGSARWI DA相当的前提下，能够很好地规避暴露值较大的路段，将MEP上的最大暴露值平均降低14.7%；该算法能实现MEP的暴露度与TGSARWI DA的高度一致，其平均相对误差不超过2.2%；与经典DA相比，该算法不仅计算复杂度大大降低，还能在路径暴露度略有上升的条件下显著降低最大暴露值；该算法可应用于战场穿越等传感器重点部署领域。

关键词: 无线传感器, 最大暴露值, 网格划分, 最小暴露路径, 随机漫步

Abstract: Most of current methods for solving the minimum exposure path in wireless sensor networks do not consider the maximum exposure path. The information of maximum exposure is integrated into Dijkstra algorithm (DA), and a Dijkstra algorithm considering maximum exposure (DAME) is proposed. Then the target guiding self-avoiding random walk with intersection (TGSARWI) algorithm is combined with DAME to build TGSARWI DAME. TGSARWI DAME algorithm can avoid the sections of greater exposures in finding the minimum exposure path. Meanwhile, it can maintain the feature of TGSARWI DA, which can cut computation complexity. Simulated results indicate that TGSARWI DAME can reduce maximum exposure by 14.7%, and get the similar path exposure obtained by the TGSARWI DA with the average relative error of less than 2.2%. TGSARWI DAME is evaluated by comparing it with DA. Although the path exposure increases slightly, the maximum exposure decreases significantly. The proposed algorithm could be applied to the important fields, such as battlefield crossing, in which multiple sensors are deployed.Key

Key words: wirelesssensor, maximumexposure, gridpartition, minimumexposurepath, randomwalk

中图分类号:

TP212.9

杨廷鸿，方海洋，姜大立，方玲. 考虑最大暴露值的无线传感器网络最小暴露路径优化算法[J]. 兵工学报, 2018, 39(4): 743-752.

YANG Ting-hong, FANG Hai-yang, JIANG Da-li, FANG Ling. Optimization Algorithm for Minimum Exposure Path in Wireless Sensor Networks Considering Maximum Exposure[J]. Acta Armamentarii, 2018, 39(4): 743-752.

参考文献

［1］ Shahid N, Naqvi I H, Qaisar S B. Characteristics and classification of outlier detection techniques for wireless sensor networks in harsh environments: a survey［J］. Artificial Intelligence Review, 2015, 43(2): 193-228.
［2］ Mahmood M A, Seah W K G, Welch I. Reliability in wireless sensor networks: a survey and challenges ahead［J］. Computer Networks, 2015, 79(1):166-187.
［3］ Lewis F L. Wireless sensor networks［M］∥Cook D J, Das S K. Smart Environments: Technologies, Protocols, and Applications. Hoboken, NJ, US:Wiley-Interscience, 2005: 11-46.
［4］ Iyengar S S, Brooks R R. Distributed sensor networks: sensor networking and applications［M］. Boca Raton, FL, US: CRC Press, 2016: 35-56.
［5］ Khan S, Pathan A S K, Alrajeh N A. Wireless sensor networks: current status and future trends［C］ ∥ Proceedings of 2012 IEEE Symposium on Computer Applications and Industrial Electronics. Boca Raton, FL, US:IEEE, 2012: 267-272.
［6］ Srbinovska M, Gavrovski C, Dimcev V. Environmental parameters monitoring in precision agriculture using wireless sensor networks［J］. Journal of Cleaner Production, 2015, 88: 297-307.
［7］ Ball M G, Qela B, Wesolkowski S. A review of the use of computational intelligence in the design of military surveillance networks ［M］. Heidelberg, Germany: Springer， 2016: 663-693.
［8］ Wu J, Ota K, Dong M X,et al. A hierarchical security framework for defending against sophisticated attacks on wireless sensor networks in smart cities［J］. IEEE Access, 2016(4):416-424.
［9］ Zhu C, Zheng C L, Shu L, et al. A survey on coverage and connectivity issues in wireless sensor networks［J］. Journal of Network and Computer Applications, 2012, 35(2): 619-632.

［10］ Mini S, Udgata S K, Sabat S L. Sensor deployment and scheduling for target coverage problem in wireless sensor networks［J］. IEEE Sensors Journal, 2014, 14(3): 636-644.
［11］ Megerian S, Koushanfar F, Potkonjak M. Worst and best-case coverage in sensor networks［J］. IEEE Transactions on Mobile Computing, 2005, 4(1): 84-92.
［12］ Meguerdichian S, Koushanfar F, Qu G, et al. Exposure in wireless ad-hoc sensor networks［C］∥Proceedings of the 7th Annual International Conference on Mobile Networking & Computing. Rome, Italy: ACM, 2001:139-150.
［13］ Clouqueur T, Phipatanasuphorn V, Ramanathan P, et al. Sensor deployment strategy for target detection［C］∥Proceedings of the 1st ACM International Workshop on Wireless Sensor Networks & Applications. Atlanta, GA, US: ACM, 2002: 42-48.
［14］ Gelfand I M, Fomin S V. Calculus of variations［M］. Heidelberg, Germany: Springer, 1966: 727-751.
［15］ Djidjev H N. Approximation algorithms for computing minimum exposure paths in a sensor field［J］. ACM Transactions on Sensor Networks, 2010, 7(3): 145-153.
［16］ Veltri G, Huang Q F, Qu G, et al. Minimal and maximal exposure path algorithms for wireless embedded sensor networks［C］∥
International Conference on Embedded Networked Sensor Systems. Los Angeles, CA, US:IEEE, 2003.
［17］ Djidjev H N. Efficient computation of minimum exposure paths in a sensor network field［C］∥Proceedings of the International Conference on Distributed Computing in Sensor Systems. Santa Fe, NM, US: Springer, 2007: 295-308.
［18］ Zhang W Z, Li M L, Shu W， et al . Smart path-finding with local information in a sensory field［C］∥2nd International Conference on Mobile Ad-hoc and Sensor Networks . Hong Kong, China: IEEE，2006.
［19］ Zhou J. A nodal integration and post-processing technique based on Voronoi diagram for Galerkin meshless methods［J］. Computer Methods in Applied Mechanics and Engineering, 2003, 192(35): 3831-3843.
［20］ Megerian S, Koushanfar F, Qu G, et al. Exposure in wireless sensor networks: theory and practical solutions［J］. Wireless Networks, 2002, 8(5): 443-454.
［21］ Liu L, Zhang X, Ma H D. Minimal exposure path algorithms for directional sensor networks［J］. Wireless Communications and Mobile Computing, 2014, 14(10): 979-994.
［22］ Liu X S, Kang G X, Zhang N B. Percolation theory-based exposure-path prevention for 3D-wireless sensor networks coverage［J］. KSII Transactions on Internet & Information Systems, 2015, 9(1): 126-148.
［23］ Feng H, Luo L, Wang Y, et al. A novel minimal exposure path problem in wireless sensor networks and its solution algorithm［J］. International Journal of Distributed Sensor Networks, 2016, 12(8): 1550147716664245.
［24］ Liu L, Song Y N, Zhang H Y. Physarum optimization: a biology-inspired algorithm for the steiner tree problem in networks［J］. IEEE Transactions on Computers, 2015, 64(3): 818-831.
［25］ Yang T H, Jiang D L, Fang H Y. Target guiding self-avoiding random walk with intersection algorithm for minimum exposure path problem in wireless sensor networks［J］. EURASIP Journal on Wireless Communications and Networking, 2018(1): 33.
［26］罗卿, 林亚平, 尹波. 传感器区域中基于网格的穿越轨迹算法研究［J］. 通信学报, 2011, 32(6): 67-77.
LUO Qing, LIN Ya-ping, YIN Bo. Traversal trajectory based on grid in wireless sensor networks field［J］. Journal on Communications, 2011, 32(6): 67-77. (in Chinese)
［27］ Liu L, Han G, Wang H. Obstacle-avoidance minimal exposure path for heterogeneous wireless sensor networks［J］. Ad Hoc Networks, 2017, 55:50-61.
［28］ Liu L, Zhang X, Ma H D. Minimal exposure path algorithms for directional sensor networks［C］∥IEEE Conference on Global Telecommunications. Honolulu, Hawaii, US: IEEE, 2009:6155-6160.

第39卷
第4期2018 年4月兵工学报ACTA
ARMAMENTARIIVol.39No.4Apr.2018

[1]	段仕轩，李艳军，曹愈远，张兴成，宋甫成，柯宇航. 双基推进剂/包覆层界面脱粘敲击检测的策略[J]. 兵工学报, 2022, 43(8): 1779-1791.
[2]	张石，张百海，王飞帆，关子霄. 基于跳数量化的无线传感器网络节点定位算法[J]. 兵工学报, 2017, 38(5): 932-939.
[3]	温龙飞, 崔灵果, 张百海, 金雪. 不均匀布置传感器网络定位优化算法[J]. 兵工学报, 2013, 34(5): 639-643.
[4]	朱明强, 侯建军, 刘颖, 苏军峰. 基于自适应比例修正无迹卡尔曼滤波的目标定位估计算法[J]. 兵工学报, 2013, 34(5): 561-566.
[5]	赵军，陈祥光，刘春涛，余向明，岳彬. 分布式多信道媒体访问控制协议在无线传感器网络中的应用研究[J]. 兵工学报, 2012, 33(6): 695-701.

考虑最大暴露值的无线传感器网络最小暴露路径优化算法

Optimization Algorithm for Minimum Exposure Path in Wireless Sensor Networks Considering Maximum Exposure

PDF

可视化

被引次数

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 5

编辑推荐

Metrics

本文评价