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

doi:10.3969/j.issn.1000-1093.2018.04.014

Abstract

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

CLC Number:

TP212.9

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.

References

［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