E-postama gönder VERTEX COVER BASED LINK MONITORING TECHNIQUES FOR WIRELESS SENSOR NETWORKS
Öz
VERTEX COVER BASED LINK MONITORING TECHNIQUES FOR WIRELESS SENSOR NETWORKS
Abstract
Wireless sensor networks (WSNs) are generally composed of numerous battery-powered tiny nodes that can sense from the environment and send this data through wireless communication. WSNs have wide range of application areas such as military surveillance, healthcare, miner safety, and outer space exploration. Inherent security weaknesses of wireless communication may prone WSNs to various attacks such as eavesdropping, jamming and spoofing. This situation attracts researchers to study countermeasures for detection and prevention of these attacks. Graph theory provides a very useful theoretical basis for solving WSN problems related to communication and security issues. One of the important graph theoretic structures is vertex cover (VC) in which a set of nodes are selected to cover the edges of the graph where each edge is incident to at least one node in VC set. Finding VC set having the minimum cardinality for a given graph is an NP-hard problem. In this paper, we describe VC algorithms aiming link monitoring where nodes in VC are configured as secure points. We investigate variants of VC problems such as weight and capacity constrained versions on different graph types to meet the energy-efficiency and load-balancing requirements of WSNs. Moreover, we present clustering and backbone formation operations as alternative applications of different VC infrastructures. For each VC sub-problem, we propose greedy heuristic based algorithms.
Keywords: Wireless Sensor Networks, Link Monitoring, Graph Theory, Vertex Cover, NP-Hard Problem.
KABLOSUZ SENSÖR AĞLARI İÇİN KÖŞE ÖRTME TABANLI BAĞLANTI İZLEME TEKNİKLERİ
Özet
Kablosuz sensor ağlar (KSAlar) genellikle ortamdan algılayabilen ve bu verileri kablosuz iletişim yoluyla gönderebilen pille çalışan çok sayıda küçük düğümden oluşur. KSAlar askeri gözetim, sağlık hizmetleri, madenci güvenliği ve uzay keşfi gibi çok çeşitli uygulama alanlarına sahiptir. Kablosuz iletişimin doğasında var olan güvenlik zayıflıkları, KSAları gizli dinleme, sinyal bozma ve sahtekarlık gibi çeşitli saldırılara eğilimli hale getirebilmektedir. Bu durum, araştırmacıları bu saldırıların tespiti ve önlenmesine yönelik karşı önlemleri incelemeye yöneltmektedir. Çizge teorisi, iletişim ve güvenlik sorunları ile ilgili KSA sorunlarını çözmek için çok yararlı bir teorik temel sağlar. Önemli çizge teorik yapılardan biri köşe örtmedir (KÖ), bu yapıda her bir kenarın KÖ kümesindeki en az bir düğüme bitişik olacak şekilde çizgenin tüm kenarlarını kapsayacak bir dizi düğüm seçilmektedir. Verilen bir çizge için en az elemana sahip KÖ kümesini bulmak NP-zor bir problemdir. Bu makalede, KÖdeki düğümlerin güvenli noktalar olarak yapılandırıldığı bağlantı izlemeyi amaçlayan KÖ algoritmaları açıklanmaktadır. KSAların enerji verimliliği ve yük dengeleme gereksinimlerini karşılamak için, farklı çizge yapılarında KÖ problemlerinin ağırlık ve kapasite kısıtlı versiyonları gibi çeşitli türleri çalışılmaktadır. Ayrıca kümeleme ve omurga oluşturma işlemlerini farklı KÖ altyapılarının alternatif uygulamaları olarak sunulmaktadır. Her KÖ alt problemi için, açgözlü sezgisel tabanlı algoritmalar önerilmektedir.
Anahtar Kelimeler: Kablosuz Sensör Ağları, Bağlantı İzleme, Çizge Teorisi, Kenar Örtme, NP-Zor Problem.
Anahtar Kelimeler
Tam Metin:
PDF (English)Referanslar
I. Akyildiz, W. Su, Y. Sankarasubramaniam, and E. Cayirci, “Wireless sensor networks: a survey,” Computer Networks, vol. 38, no. 4, pp. 393 – 422, 2002.
M. Tubaishat and S. Madria, “Sensor networks: an overview,” Potentials, IEEE, vol. 22, no. 2, pp. 20–23, 2003.
J. Yick, B. Mukherjee, and D. Ghosal, “Wireless sensor network survey,” Computer Networks, vol. 52, no. 12, pp. 2292 – 2330, 2008.
V. Potdar, A. Sharif, and E. Chang, “Wireless sensor networks: A survey,” in 2009 International Conference on Advanced Information Networking and Applications Workshops, 2009, pp. 636–641.
A. Hadjidj, M. Souil, A. Bouabdallah, Y. Challal, and H. Owen, “Wireless sensor networks for rehabilitation applications: Challenges and opportunities,” Journal of Network and Computer Applications, vol. 36, no. 1, pp. 1 – 15, 2013.
P. Rawat, K. D. Singh, H. Chaouchi, and J. M. Bonnin, “Wireless sensor networks: A survey on recent developments and potential synergies,” J. Supercomput., vol. 68, no. 1, p. 1–48, Apr. 2014.
B. Rashid and M. H. Rehmani, “Applications of wireless sensor networks for urban areas: A survey,” Journal of Network and Computer Applications, vol. 60, pp. 192 – 219, 2016.
S. R. Jino Ramson and D. J. Moni, “Applications of wireless sensor networks — a survey,” in 2017 International Conference on Innovations in Electrical, Electronics, Instrumentation and Media Technology (ICEEIMT), 2017, pp. 325–329.
R. E. Mohamed, A. I. Saleh, M. Abdelrazzak, and A. S. Samra, “Survey on wireless sensor network applications and energy efficient routing protocols,” Wirel. Pers. Commun., vol. 101, no. 2, p. 1019–1055, Jul. 2018.
H. Karl and A. Willig, Protocols and Architectures for Wireless Sensor Networks. Hoboken, NJ, USA: John Wiley Sons, Inc., 2005.
J. L. Gross and J. Yellen, Graph Theory and Its Applications, Second Edition (Discrete Mathematics and Its Applications). Chapman Hall/CRC, 2005.
J. Bondy and U. Murty, Graph Theory, 1st ed. Springer Publishing Company, Incorporated, 2008.
D. B. West, Introduction to graph theory, 2nd ed. Prentice Hall Of India Pvt.Ltd., 2011.
Jingbo Dong, Qing Chen, and Zhisheng Niu, “Random graph theory based connectivity analysis in wireless sensor networks with rayleigh fading channels,” in 2007 Asia-Pacific Conference on Communications, 2007, pp. 123–126.
L. Ding and Z.-H. Guan, “Modeling wireless sensor networks using random graph theory,” Physica A: Statistical Mechanics and its Applications, vol. 387, no. 12, pp. 3008 – 3016, 2008.
N. Nasser and L. Arboleda, Clustering in Wireless Sensor Networks: A Graph Theory Perspective, 03 2008, pp. 161 – 193.
H. Kenniche and V. Ravelomananana, “Random geometric graphs as model of wireless sensor networks,” in 2010 The 2nd International Conference on Computer and Automation Engineering (ICCAE), vol. 4, 2010, pp. 103–107.
D. Sarioz, “Geometric graph theory and wireless sensor networks,” Ph.D. dissertation, USA, 2012.
K. Gao, P. Suganthan, Q.-K. Pan, M. Tasgetiren, and A. Sadollah, “Artificial bee colony algorithm for scheduling and rescheduling fuzzy flexible job shop problem with new job insertion,” Knowledge-Based Systems, vol. 109, 06 2016.
H. Rhim, T. Karim, R. Abassi, D. Sauveron, and S. Guemara, “A multi-hop graph-based approach for an energy- efficient routing protocol in wireless sensor networks,” Human-centric Computing and Information Sciences, vol. 8, 12 2018.
M. Z. Masoud, Y. Jaradat, I. Jannoud, and M. A. A. Sibahee, “A hybrid clustering routing protocol based on machine learning and graph theory for energy conservation and hole detection in wireless sensor network,” International Journal of Distributed Sensor Networks, vol. 15, no. 6, p. 1550147719858231, 2019.
U. O., “New heuristic algorithm for unweighted minimum vertex cover,” Problems of Cybernetics and Informatics, pp. 1–4, 2012.
S. Cai, K. Su, C. Luo, and A. Sattar, “Numvc: An efficient local search algorithm for minimum vertex cover,” J. Artif. Int. Res., vol. 46, no. 1, p. 687–716, Jan. 2013.
B. Caskurlu, V. Mkrtchyan, O. Parekh, and K. Subramani, “On partial vertex cover and budgeted maximum coverage problems in bipartite graphs.” in IFIP TCS, ser. Lecture Notes in Computer Science, J. Díaz, I. Lanese, and D. Sangiorgi, Eds., vol. 8705. Springer, 2014, pp. 13–26.
Z. Ma, Y. Fan, K. Su, C. Li, and A. Sattar, “Local search with noisy strategy for minimum vertex cover in massive graphs,” in Proceedings of the 14th Pacific Rim International Conference on Trends in Artificial Intelligence, ser. PRICAI’16. Springer, 2016, p. 283–294.
E. Hong and M.-J. Kao, “Approximation Algorithm for Vertex Cover with Multiple Covering Constraints,” in 29th International Symposium on Algorithms and Computation (ISAAC 2018), ser. Leibniz International Proceedings in Informatics (LIPIcs), W.-L. Hsu, D.-T. Lee, and C.-S. Liao, Eds., vol. 123. Dagstuhl, Germany: Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2018, pp. 43:1–43:11.
C. W. Cheung, X. M. Goemans, and C.-w. S. Wong, “Improved algorithms for vertex cover with hard capacities on multigraphs and hypergraphs,” SODA, pp. 1714–1726, 2014.
J. Wu, X. Shen, and K. Jiao, “Game-based memetic algorithm to the vertex cover of networks,” IEEE Transactions on Cybernetics, vol. 49, no. 3, pp. 974–988, 2019.
C. Witt, “Analysis of an iterated local search algorithm for vertex cover in sparse random graphs,” Theoretical Computer Science, vol. 425, pp. 117 – 125, 2012, theoretical Foundations of Evolutionary Computation.
A. Bazzi, S. Fiorini, S. Pokutta, and O. Svensson, “No small linear program approximates vertex cover within a factor 2 – e,” in Proceedings of the 2015 IEEE 56th Annual Symposium on Foundations of Computer Science (FOCS), ser. FOCS ’15. USA: IEEE Computer Society, 2015, p. 1123–1142.
H. Xu, T. K. S. Kumar, and S. Koenig, “A new solver for the minimum weighted vertex cover problem,” in Proceedings of the 13th International Conference on Integration of Artificial Intelligence and Operations Research Techniques in Constraint Programming (CPAIOR), 2016, pp. 392–405.
S. Shimizu, K. Yamaguchi, T. Saitoh, and S. Masuda, “A fast heuristic for the minimum weight vertex cover problem,” 2016 IEEE/ACIS 15th International Conference on Computer and Information Science (ICIS), pp. 1–5, 2016.
M. Pourhassan, T. Friedrich, and F. Neumann, “On the use of the dual formulation for minimum weighted vertex cover in evolutionary algorithms,” in Proceedings of the 14th ACM/SIGEVO Conference on Foundations of Genetic Algorithms, ser. FOGA ’17. New York, NY, USA: Association for Computing Machinery, 2017, p. 37–44.
S. Cai, W. Hou, J. Lin, and Y. Li, “Improving local search for minimum weight vertex cover by dynamic strategies,” in Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence, IJCAI-18. International Joint Conferences on Artificial Intelligence Organization, 7 2018, pp. 1412–1418.
H. Xu, X.-Z. Wu, C. Cheng, S. Koenig, and T. K. S. Kumar, “The buss reduction for the k-weighted vertex cover problem,” in ISAIM, 2018.
M. R. Islam, I. Arif, and R. Shuvo, “Generalized vertex cover using chemical reaction optimization,” Applied Intelligence, vol. 49, 01 2019.
D. Tsur, “Weighted vertex cover on graphs with maximum degree 3,” CoRR, vol. abs/1810.12982, 2018.
R. Li, S. hu, S. Cai, J. Gao, Y. Wang, and M. Yin, “Numwvc: A novel local search for minimum weighted vertex cover problem,” Journal of the Operational Research Society, pp. 1–12, 06 2019.
M. Pourhassan, F. Shi, and F. Neumann, “Parameterized analysis of multiobjective evolutionary algorithms and the weighted vertex cover problem,” Evolutionary Computation, vol. 27, no. 4, pp. 559–575, 2019.
S. Kratsch and F. Neumann, “Fixed-parameter evolutionary algorithms and the vertex cover problem,” in Proceedings of the 11th Annual Conference on Genetic and Evolutionary Computation, ser. GECCO ’09. New York, NY, USA: Association for Computing Machinery, 2009, p. 293–300.
Y. Zhang, Y. Shi, and Z. Zhang, “Approximation algorithm for the minimum weight connected k-subgraph cover problem,” Theoretical Computer Science, vol. 535, pp. 54 – 58, 2014.
S. C.-w. Wong, “Tight algorithms for vertex cover with hard capacities on multigraphs and hypergraphs,” in Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, ser. SODA ’17. USA: Society for Industrial and Applied Mathematics, 2017, p. 2626–2637.
H.-T. Wei, W.-K. Hon, P. Horn, C.-S. Liao, and K. Sadakane, “An O(1)-Approximation Algorithm for Dynamic Weighted Vertex Cover with Soft Capacity,” in Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2018), ser. Leibniz International Proceedings in Informatics (LIPIcs), E. Blais, K. Jansen, J. D. P. Rolim, and D. Steurer, Eds., vol. 116. Dagstuhl, Germany: Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2018, pp. 27:1–27:14.
S. Bhattacharya, M. Henzinger, and G. F. Italiano, “Deterministic fully dynamic data structures for vertex cover and matching,” in Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, ser. SODA ’15. USA: Society for Industrial and Applied Mathematics, 2015, p. 785–804.
S. Bhattacharya, M. Henzinger, and G. F. Italiano, “Design of dynamic algorithms via primal-dual method,” CoRR, vol. abs/1604.05337, 2016.
S. B. van Rooij and J. M. M. van Rooij, “Algorithms and complexity results for the capacitated vertex cover problem,” in SOFSEM 2019: Theory and Practice of Computer Science, B. Catania, R. Královicˇ, J. Nawrocki, and G. Pighizzini, Eds. Cham: Springer International Publishing, 2019, pp. 473–489.
Y. Li, Z. Yang, and W. Wang, “Complexity and algorithms for the connected vertex cover problem in 4-regular graphs,” Applied Mathematics and Computation, vol. 301, pp. 107 – 114, 2017.
R. Krithika, D. Majumdar, and V. Raman, “Revisiting connected vertex cover: FPT algorithms and lossy kernels,” CoRR, vol. abs/1711.07872, 2017.
M. Johnson, G. Paesani, and D. Paulusma, Connected Vertex Cover for (sP1+P5)-Free Graphs, 09 2018, pp. 279–291.
Y. Zhang, J. Wu, L. Zhang, P. Zhao, J. Zhou, and M. Yin, “An efficient heuristic algorithm for solving connected vertex cover problem,” Mathematical Problems in Engineering, vol. 2018, pp. 1–10, 09 2018.
Y. Li, W. Wang, and Z. Yang, “The connected vertex cover problem in k-regular graphs,” Journal of Combinatorial Optimization, vol. 38, pp. 635–645, 03 2019.
Madde Ölçümleri
Metrics powered by PLOS ALM
Refback'ler
- Şu halde refbacks yoktur.
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.
Selçuk-Teknik Dergisi ISSN:1302-6178