Autosoft Journal

Online Manuscript Access


A Multi-Objective Metaheuristics Study on Solving Constrained Relay Node Deployment Problem in WSNS



Abstract

This paper studies how to deploy relay nodes into traditional wireless sensor networks with constraint aiming to simultaneously optimize two important factors; average energy consumption and average network reliability. We consider tackling this multi-objective (MO) optimization problem with three metaheuristics, which employ greatly different evolutional strategies, and aim at an in-depth analysis of different performances of these metaheuristics to our problem. For this purpose, a statistical procedure is employed to analyse the results for confidence, in consideration of two MO quality metrics; hypervolume and coverage of two sets. After comprehensive analysis of the results, it is concluded that NSGA-II provides the best performance.


Keywords


Pages

Total Pages: 10
Pages: 367-376

DOI
10.1080/10798587.2017.1294873


Manuscript ViewPdf Subscription required to access this document

Obtain access this manuscript in one of the following ways


Already subscribed?

Need information on obtaining a subscription? Personal and institutional subscriptions are available.

Already an author? Have access via email address?


Published

Volume: 24
Issue: 2
Year: 2018

Cite this document


References

Akyildiz, I.F. et al. "Wireless Sensor Networks: a Survey." Computer Networks 38.4 (2002): 393-422. Crossref. Web. https://doi.org/10.1016/S1389-1286(01)00302-4

Bhattacharyya, B., and S.K. Goswami. "Reactive Power Optimization Through Evolutionary Techniques: A Comparative Study Of The Ga, De And Pso Algorithms." Intelligent Automation & Soft Computing 13.4 (2007): 453-461. Crossref. Web. https://doi.org/10.1080/10798587.2007.10642976

Cheng, Long et al. "A Pso-Based Maintenance Strategy in Wireless Sensor Networks." Intelligent Automation & Soft Computing 21.1 (2014): 65-75. Crossref. Web. https://doi.org/10.1080/10798587.2014.919716

Cheng, Xiuzhen et al. "Relay Sensor Placement in Wireless Sensor Networks." Wireless Networks 14.3 (2007): 347-355. Crossref. Web. https://doi.org/10.1007/s11276-006-0724-8

Deb, K. et al. "A Fast and Elitist Multiobjective Genetic Algorithm: NSGA-II." IEEE Transactions on Evolutionary Computation 6.2 (2002): 182-197. Crossref. Web. https://doi.org/10.1109/4235.996017

Fanding D. Journal of Southwest Jiaotong University

Ford, L. R., and D. R. Fulkerson. "Maximal Flow through a Network ." Canadian Journal of Mathematics 8.0 (1956): 399-404. Crossref. Web. https://doi.org/10.4153/CJM-1956-045-5

Gou, Jin, Fei Wang, and Wei Luo. "Mining Fuzzy Association Rules Based on Parallel Particle Swarm Optimization Algorithm." Intelligent Automation & Soft Computing 21.2 (2014): 147-162. Crossref. Web. https://doi.org/10.1080/10798587.2014.957482

Xiaofeng Han et al. "Fault-Tolerant Relay Node Placement in Heterogeneous Wireless Sensor Networks." IEEE Transactions on Mobile Computing 9.5 (2010): 643-656. Crossref. Web. https://doi.org/10.1109/TMC.2009.161

Hou, Y.T. et al. "On Energy Provisioning and Relay Node Placement for Wireless Sensor Networks." IEEE Transactions on Wireless Communications 4.5 (2005): 2579-2590. Crossref. Web. https://doi.org/10.1109/TWC.2005.853969

Johnston, Mark D. "An Evolutionary Algorithm Approach To Multi-Objective Scheduling Of Space Network Communications." Intelligent Automation & Soft Computing 14.3 (2008): 367-376. Crossref. Web. https://doi.org/10.1080/10798587.2008.10643001

Kang, Qinma, and Hong He. "Honeybee Mating Optimization Algorithm For Task Assignment In Heterogeneous Computing Systems." Intelligent Automation & Soft Computing 19.1 (2013): 69-84. Crossref. Web. https://doi.org/10.1080/10798587.2013.771438

Konstantinidis, Andreas, and Kun Yang. "Multi-Objective K-Connected Deployment and Power Assignment in WSNs Using a Problem-Specific Constrained Evolutionary Algorithm Based on Decomposition." Computer Communications 34.1 (2011): 83-98. Crossref. Web. https://doi.org/10.1016/j.comcom.2010.08.011

Lanza-Gutierrez, Jose M., and Juan A. Gomez-Pulido. "Studying the Multiobjective Variable Neighbourhood Search Algorithm When Solving the Relay Node Placement Problem in Wireless Sensor Networks." Soft Computing 20.1 (2015): 67-86. Crossref. Web. https://doi.org/10.1007/s00500-015-1670-0

Li, Zhenhua, and Hai-Lin Liu. "Integrating Preference by Means of Desirability Function with Evolutionary Multi-Objective Optimization." Intelligent Automation & Soft Computing 21.2 (2014): 197-209. Crossref. Web. https://doi.org/10.1080/10798587.2014.961313

Lilliefors, Hubert W. "On the Kolmogorov-Smirnov Test for Normality with Mean and Variance Unknown." Journal of the American Statistical Association 62.318 (1967): 399-402. Crossref. Web. https://doi.org/10.1080/01621459.1967.10482916

Liu, Hai-Lin, Yuping Wang, and Yiu-Ming Cheung. "A Multi-Objective Evolutionary Algorithm Using Min-Max Strategy And Sphere Coordinate Transformation." Intelligent Automation & Soft Computing 15.3 (2009): 361-384. Crossref. Web. https://doi.org/10.1080/10798587.2009.10643036

Ma, Chuang et al. "A Fault-Tolerant Algorithm of Wireless Sensor Network Based on Recoverable Nodes." Intelligent Automation & Soft Computing 17.6 (2011): 737-747. Crossref. Web. https://doi.org/10.1080/10798587.2011.10643183

Mann, H. B., and D. R. Whitney. "On a Test of Whether One of Two Random Variables Is Stochastically Larger Than the Other." The Annals of Mathematical Statistics 18.1 (1947): 50-60. Crossref. Web. https://doi.org/10.1214/aoms/1177730491

Misra, Satyajayant, Nahid Ebrahimi Majd, and Hong Huang. "Approximation Algorithms for Constrained Relay Node Placement in Energy Harvesting Wireless Sensor Networks." IEEE Transactions on Computers 63.12 (2014): 2933-2947. Crossref. Web. https://doi.org/10.1109/tc.2013.171

Nandy, Sudarshan et al. "Color Image Segmentation By Cuckoo Search." Intelligent Automation & Soft Computing 21.4 (2015): 673-685. Crossref. Web. https://doi.org/10.1080/10798587.2015.1025480

Nebro, Antonio J. et al. "AbYSS: Adapting Scatter Search to Multiobjective Optimization." IEEE Transactions on Evolutionary Computation 12.4 (2008): 439-457. Crossref. Web. https://doi.org/10.1109/Tevc.2007.913109

Nigam, Ashutosh, and Yogesh K. Agarwal. "Optimal Relay Node Placement in Delay Constrained Wireless Sensor Network Design." European Journal of Operational Research 233.1 (2014): 220-233. Crossref. Web. https://doi.org/10.1016/j.ejor.2013.08.031

Peiravi, Ali, Habib Rajabi Mashhadi, and S. Hamed Javadi. "An Optimal Energy-Efficient Clustering Method in Wireless Sensor Networks Using Multi-Objective Genetic Algorithm." International Journal of Communication Systems 26.1 (2011): 114-126. Crossref. Web. https://doi.org/10.1002/dac.1336

Rauf, Abdul, and Eisa A. Aleisa. "PSO Based Automated Test Coverage Analysis of Event Driven Systems." Intelligent Automation & Soft Computing 21.4 (2014): 491-502. Crossref. Web. https://doi.org/10.1080/10798587.2014.966479

Sierra, Margarita Reyes, and Carlos A. Coello Coello. "Improving PSO-Based Multi-Objective Optimization Using Crowding, Mutation and ∈-Dominance." Evolutionary Multi-Criterion Optimization (2005): 505-519. Crossref. Web. https://doi.org/10.1007/978-3-540-31880-4_35

Villasenor Alva, José A., and Elizabeth González Estrada. "A Generalization of Shapiro-Wilk”s Test for Multivariate Normality." Communications in Statistics - Theory and Methods 38.11 (2009): 1870-1883. Crossref. Web. https://doi.org/10.1080/03610920802474465

Wei, Xuyang et al. "Mining Users Interest Navigation Patterns Using Improved Ant Colony Optimization." Intelligent Automation & Soft Computing 21.3 (2015): 445-454. Crossref. Web. https://doi.org/10.1080/10798587.2015.1015778

William, L.H. & Hays, W.L. (1975). Statistics: Probability, Inference, and Decision (2nd Edn) (pp. 203–270). New York, NY: Holt, Rinehart and Winston.

Xiuzhen Cheng et al. "Strong Minimum Energy Topology in Wireless Sensor Networks: Np-Completeness and Heuristics." IEEE Transactions on Mobile Computing 2.3 (2003): 248-256. Crossref. Web. https://doi.org/10.1109/TMC.2003.1233530

Kenan Xu et al. "Relay Node Deployment Strategies in Heterogeneous Wireless Sensor Networks." IEEE Transactions on Mobile Computing 9.2 (2010): 145-159. Crossref. Web. https://doi.org/10.1109/TMC.2009.105

Xue, Yu et al. "A Hybrid Evolutionary Algorithm for Numerical Optimization Problem." Intelligent Automation & Soft Computing 21.4 (2014): 473-490. Crossref. Web. https://doi.org/10.1080/10798587.2014.962239

Yang, Dejun et al. "Two-Tiered Constrained Relay Node Placement in Wireless Sensor Networks: Computational Complexity and Efficient Approximations." IEEE Transactions on Mobile Computing 11.8 (2012): 1399-1411. Crossref. Web. https://doi.org/10.1109/tmc.2011.126

Yazdani, M., B. Naderi, and M. Mousakhani. "A Model and Metaheuristic for Truck Scheduling in Multi-Door Cross-Dock Problems." Intelligent Automation & Soft Computing 21.4 (2015): 633-644. Crossref. Web. https://doi.org/10.1080/10798587.2015.1014620

Zitzler E. Doctoral thesis ETH NO. 13398

Zitzler, E., and L. Thiele. "Multiobjective Evolutionary Algorithms: a Comparative Case Study and the Strength Pareto Approach." IEEE Transactions on Evolutionary Computation 3.4 (1999): 257-271. Crossref. Web. https://doi.org/10.1109/4235.797969

JOURNAL INFORMATION


ISSN PRINT: 1079-8587
ISSN ONLINE: 2326-005X
DOI PREFIX: 10.31209
10.1080/10798587 with T&F
IMPACT FACTOR: 0.652 (2017/2018)
Journal: 1995-Present

SCImago Journal & Country Rank


CONTACT INFORMATION


TSI Press
18015 Bullis Hill
San Antonio, TX 78258 USA
PH: 210 479 1022
FAX: 210 479 1048
EMAIL: tsiepress@gmail.com
WEB: http://www.wacong.org/tsi/