Metaheuristic-Based Approaches for Solving the Controller Placement Problem in Software-Defined Wireless Sensor Networks (SDWSNs)

Abstract

Software-Defined Networking (SDN) is well-known as a master solver for many traditional networks restrictions. Network management flexibility is the SDN core characteristic that recently becomes a hot topic for many researchers to improve network performance. A critical issue arises specifically for the multi-controller SDN-based network, namely the controller placement problem (CPP), known as an NP-hard problem. Solving such problems in a reasonable amount of time is usually carried out using metaheuristic algorithms. This thesis presents different approaches for solving the CPP which are based on metaheuristic algorithms such as the genetic algorithm (GA) and the greedy randomized adaptive search procedure (GRASP). The first approach is a fault tolerance metaheuristic-based scheme (FTMBS) that we proposed for solving the CPP in wireless software-defined networks. The FTMBS is a multi-objective-based scheme aiming to maximize network connectivity and the load balance among controllers, minimize the network worst-case latency, and maximize the network lifetime in the presence of faulty nodes. In the presence of conflicting multi-objective metrics, the decision-maker or the network administrator decides on the compromise between these conflicting metrics. We defined the selection criteria for the number of SDN controllers ahead of time that achieves the targeted average percentage of network improvement. Simulations carried out for three and five controllers showed that three controllers were enough for such networks. We have shown the efficiency of the proposed FTMBS scheme under various percentages of faulty nodes as it has lower latency compared to the random distribution of controllers among cluster heads and the cluster-based network partition algorithm (CNPA). Also, we have verified the goodness of the solutions by showing that the GA solutions have a good approximation to the Pareto optimal solutions provided by the Non-dominating Sorting Genetic Algorithm (NSGA-II). In addition, the proposed FTMBS scheme showed its superiority over various state-of the-art schemes for different network performance metrics on the cost of having a bit higher complexity. The second approach, namely the ALBATROSS scheme, is an energy-efficient strategy for WSNs, which is a modification of the FTMBS scheme. The albatross bird's dynamic soaring scheme is adopted in the cluster heads selection algorithm, and the selected cluster heads are taken as inputs for the heuristic algorithm to solve the CPP. Simulation results showed that the ALBATROSS scheme saves the network energy and outperforms other existing energy-aware schemes found in literature. However, it has a bit higher complexity than other schemes. Besides, in Appendix A, we have provided an example of using the SDN technology in a practical environment other than WSNs, such as wireless body area networks (WBANs). Keywords: Software-defined networking, controller placement problem, meta heuristic algorithm, network performance enhancement.

ÖZ: Yazılım Tanımlı Ağ Oluşturma (SDN), geleneksel ağın karşılaştığı birçok geleneksel kısıtlamalara karşı ana bir çözücü olarak iyi bilinir. Ağ yönetimi esnekliği, birçok araştırmacı için ağ performansını geliştirme konusunda ilgi alanı haline gelmiş olan SDN temel özelliğidir. Çok denetleyicili SDN tabanlı ağ için kritik bir sorun olan ve NP-zor problem olarak da bilinen denetleyici yerleştirme sorunu (CPP) ortaya çıkmaktadır. Bu tür problemlerin makul bir sürede çözülmesi genellikle meta sezgisel algoritmalar kullanılarak gerçekleştirilir. Bu tezde, genetik algoritma (GA) ve açgözlü randomize uyarlamalı arama prosedürü (GRASP) gibi meta-sezgisel algoritmalara dayanan CPP'nin çözümü için farklı yaklaşımlar sunmaktadır. İlk yaklaşım, FTMBS olarak adlandırılan kablosuz yazılım tanımlı ağlarda CPP'yi çözmek için önerdiğimiz hata toleransı meta-sezgisel tabanlı bir şemadır. FTMBS, ağ bağlantısını ve denetleyiciler arasındaki yük dengesini en üst düzeye çıkarmayı, denetleyicilerin kendileri arasındaki en kötü durum gecikmesini en aza indirmeyi ve hatalı düğümlerin varlığında ağ ömrünü en üst düzeye çıkarmayı amaçlayan çok amaçlı bir şemadır. Birbiri ile çatışan çok amaçlı ölçümlerin varlığında, karar verici veya ağ yöneticisi bu sözkonusu ölçümler arasındaki uzlaşmaya karar verir. Hedeflenen ortalama ağ iyileştirme yüzdesine ulaşan SDN denetleyicilerinin sayısı için seçim kriterleri önceden belirlenmiştir. Üç ve beş denetleyici için simülasyonlar yapılmış olup, bu tür ağlar için üç denetleyicinin yeterli olduğu belirlenmiştir. Önerilen FTMBS şemasının verimliliğini, çeşitli hatalı düğüm yüzdeleri altında, kontrolörlerin küme kafaları ve küme tabanlı ağ bölümleme algoritması (CNPA), ve rastgele dağılımına kıyasla daha düşük gecikme süresine sahip olduğunu gösterdik. Ayrıca, GA çözümlerinin, Baskın Olmayan Sıralama Genetik Algoritması (NSGA- II) tarafından sağlanan Pareto optimal çözümlerine iyi bir yaklaşıma sahip olduğunu göstererek çözümlerin iyiliğini doğruladık. Ek olarak, önerilen FTMBS şeması, biraz daha yüksek karmaşıklığa sahip olma maliyetiyle farklı ağ performans ölçütleri için çeşitli son teknoloji şemalara göre üstünlüğünü göstermiştir. İkinci yaklaşım, yani ALBATROSS şeması, FTMBS şemasının bir modifikasyonu olan WSN'ler için enerji verimli bir stratejidir. Ağ enerjisinden tasarruf etmeyi amaçlayan albatross kuşunun dinamik yükselme şeması, SDN denetleyicilerinin seçimleri için dikkate alınacak ağ küme kafalarını etkin bir şekilde seçmek için benimsenmiştir. Simülasyon sonuçları, ALBATROSS şemasının ağ enerjisini koruduğunu ve literatürde bulunan farklı mevcut enerjiye duyarlı şemalardan daha iyi performans gösterdiğini ortaya çıkarmıştır. Ayrıca, Ek A'da, kablosuz vücut alanı ağları (WBANs) gibi WSN'ler dışında pratik bir ortamda SDN teknolojisinin kullanımına bir örnek sunduk. Anahtar Kelimeler: Yazılım tanımlı ağ oluşturma, denetleyici yerleştirme problemi, meta-sezgisel algoritma, ağ performansı geliştirme