Genetic algorithm based ARINC-664 worst case delay optimization using network calculus
Genetik algoritma ve network calculus ile ARINC-664 uçtan uca gecikme optimizasyonu
- Tez No: 709365
- Danışmanlar: PROF. DR. HAKAN ALİ ÇIRPAN
- Tez Türü: Yüksek Lisans
- Konular: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol, Elektrik ve Elektronik Mühendisliği, Computer Engineering and Computer Science and Control, Electrical and Electronics Engineering
- Anahtar Kelimeler: Belirtilmemiş.
- Yıl: 2022
- Dil: İngilizce
- Üniversite: İstanbul Teknik Üniversitesi
- Enstitü: Lisansüstü Eğitim Enstitüsü
- Ana Bilim Dalı: Elektronik ve Haberleşme Mühendisliği Ana Bilim Dalı
- Bilim Dalı: Telekomünikasyon Mühendisliği Bilim Dalı
- Sayfa Sayısı: 75
Özet
Günümüzde, yeni nesil uçakların zorlu gereksinimlerini karşılamak için dinamik kaynak paylaşımını sağlayan Entegre Modüler Aviyonik (IMA) konsepti popüler hale gelmiştir. Deterministik ağ (DTN), sınırlı gecikme ve düşük gecikme varyasyonu (jitter) ile alt sistemler arasında iletişim sağlamak için IMA platformunun önemli bir teknolojisidir. Bir uçak içindeki entegre fonksiyonların sayısı arttıkça, IMA sistemleri arasında değiş tokuş edilen veri miktarı önemli ölçüde büyür. Haberleşen düğümlerin sayısındaki bu tür bir büyüme, geleneksel aviyonik iletişim standartları tarafından düzgün bir şekilde ele alınamadığından, Ethernet tabanlı deterministik ağ teknolojileri geliştirilmiştir. ARINC-664, Zaman Tetiklemeli Ethernet (Time-Triggered Ethernet - TTEthernet) ve Zamana Duyarlı Ağ (Time Sensitive Network - TSN) gibi Ethernet tabanlı çözümler, deterministik ağ kategorisinde yaygın olarak kullanılan çözümlerdir. ARINC-664, veya Aviyonik Tam Çift Yönlü Anahtarlamalı Ethernet (Avionics Full Duplex Ethernet - AFDX), Airbus tarafından 2005'te piyasaya sürülmüş olan hizmet kalitesini (Quality of Service - QoS) sağlamak için bant genişliğinin iletişim düğümleri arasında paylaşıldığı deterministik bir veri ağıdır. Aviyonik güvenlik açısından emniyet kritik cihazların haberleşmesi için oluşturulmuştur. Ayrıca, ARINC-664 karmaşık senkronizasyon mekanizması gerektirmediği ve bu nedenle sertifikasyonu nispeten daha kolay olduğu için en yaygın kullanılan çözümlerden birisidir. Günümüzde halihazırda rafta hazır ticari bir ürün olarak (Commercial off-the-shelf - COTS) firmalar tarafından satılmaktadır. ARINC-664 sanal bağlantı (Virtual Link - VL), uç nokta (End System - ES) ve anahtar (Switch - SW) olmak üzere 3 temel bileşenden oluşmaktadır. VL bir kaynaktan uç sistemden, bir veya daha fazla hedef uç sisteme tanımlanan uçtan uca bağlantı türüdür. Sanal bağlantılar sıralı paketler arası minimum süreyi belirlemek için kullanılan bant genişliği tahsis aralığı (BAG), paketin alabileceği en küçük ve en büyük uzunluğu tanımlamak için kullanılan $L_{min}$ ve $L_{max}$ ve akışların önceliğini belirtmek için öncelik (priority) parametreleri ile tanımlanırlar. Uç noktalar bu sanal bağlantıların başlangıç veya son noktalarıdır. Gönderilecek olan sanal bağlantıların parametrelerine uygun olup olmadığının kontrolünün yanında gecikme varyasyonunu kontrol ederek ağın daha önceden belirlenen özelliklere göre çalışmasını sağlamaktadırlar. Temel görevi gelen ve giden paketleri uzak noktadaki uygulamalara taşımaktır. Anahtar ise yine uç nokta gibi sanal bağlantı parametrelerinin kontrolünü yapmaktadır. Giriş portuna bağlı olan uç nokta veya anahtardan gelen sanal bağlantıları önceden belirlenmiş bir veya daha fazla çıkış portuna yönlendirerek uç noktalara veya kendisi gibi başka anahtarlara yönlendirilmesini sağlar. ARINC-664 Ethernet tabanlı deterministik bir ağ protokolüdür. Bu sebeple önceden planlanması (pre-configured) gerekir ayrıca katı zamanlama gereksinimlerinin karşılandığından emin olmak gerektiği için çevrimdışı ağ planlaması yapılması gerekmektedir. Bununla birlikte bütün trafiklerin özelliklerinin yani sanal bağlantı parametrelerinin (kaynak ve hedef uç noktaları, hız ve paket boyutu vb.), ağdaki uç nokta ve anahtarların konum ve bağlantılarının önceden belirlenmiş olması gerekmektedir. Parametreler belirlenirken ağın tümü için uç sistem, anahtar, akış özellikleri ve sayıları göz önünde bulundurulmalıdır. Ayrıca, ARINC-664 standardının belirlemiş olduğu kısıtlamaların ağdaki her bir eleman için karşılanıp karşılanmadığının kontrol edilmesi gerekmektedir. Bu gibi hesaplamalar için matematiksel bir yönteme ihtiyaç duyulmaktadır. Ağ hesabının (NC) temeli, min-plus cebirin matematiksel teorisinde yatar ve entegre hizmet ağları, akış kontrolü, çizelgeleme ve gecikme boyutlandırma gibi ağ oluşturmadaki gecikme analizi problemlerine ilişkin detaylı bilgiler sağlayan bir araçtır. Ağ hesabı, ARINC-664 dahil olmak üzere aviyonik ağların en kötü durum gecikme sınırlarını elde etmek için kullanılan yaygın bir yaklaşımdır. Her bir akış için en kötü durum gecikmesini sunması ağ sistemini planlayan veya tasarlayan kişi için kolaylık sağlamaktadır. Böylece ARINC-664 için mümkün olabilecek konfigürasyon parametreleri belirlenebilmektedir. ARINC-664 standardında bulunan, her bir anahtar için sunulmuş yüksek ve düşük öncelik olmak üzere 2 çeşit trafik mevcuttur. Bunların sistemi planlayan açısından atamasını yapmak karmaşık ağlarda zor olabilmektedir. Bunun yanında öncelik sınıfının belirlenmesi, diğer trafiklerin göz önünde bulundurulmasının yanında birden fazla ARINC-664 anahtardan geçilmesi gibi durumların da hesaba katılması gerekmektedir. Bu çalışma, genişletilmiş öncelik konseptini (extended priority concept) kullanarak sanal bağlantıların öncelik seviyelerinin etkin bir şekilde belirlenmesi için ağ hesabı ve ARINC-664 tabanlı genetik algoritma ile, bir ağ gecikme optimizasyonu sunmaktadır. ARINC-664 standardında yalnızca iki öncelik düzeyi bulunurken, genişletilmiş öncelik kavramı, sanal bağlantıların zamanlayıcı (scheduler) tarafından seçimini iyileştirmek için öncelik düzeylerinin sayısını arttırmaktadır. Sanal bağlantıların öncelik seviyelerine göre olası her ataması için ağ hesabı analizinin yapılması, ağdaki tüm sanal bağlantılar için en kötü durum gecikme sonuçlarını göz önünde bulundurmayı gerektirmektedir. Genişletilmiş öncelik konsepti ile artan arama alanına (search space) makul bir şekilde uygun bir çözüm bulmak veya zaman açısından verimli bir şekilde keşfetmek için bir genetik algoritma kullanılır. Genetik algoritma ve genişletilmiş öncelik konseptine sahip ARINC-664 için ağ hesabı MATLAB üzerinde uygulanmıştır. Çalışmada genişletilmiş öncelik konsepti uygulanmış ARINC-664 ağ için genetik algoritma parametrelerinin (popülasyon sayısı, mutasyon oranı, değişim oranı vb.) optimum değerleri belirlenmiştir ve sonrasında bu parametreler ile karmaşık ağlar için sonuçlar elde edilmiştir. Böylece genetik algoritmanın daha hızlı, verimli çalışması ve doğru sonuçlar elde edilmesi beklenmiştir. Ayrıca genetik algoritmada en kötü gecikmelerinin maksimumunu, ortalamasını ve standart sapmasını en aza indirmeyi amaçlayan üç farklı uygunluk fonksiyonu (fitness or cost function) tanımlanmıştır ve analizler bu uygunluk fonksiyonlarının çıktılarıyla yapılarak ağdaki etkisi gözlenmiştir. Gerçek dünyada, bilgisayar ağları genişletilebilir olmaları nedeniyle karmaşık bir yapıya sahiptir, bu nedenle ağ simülasyonları, topoloji modellerini araştırmak veya incelemek için sıklıkla kullanılır. Günümüzde belirli zamanlarda bileşen değişkenlerini örnekleyen veya değiştiren ağlar için çok sayıda ayrık olay simülatörü bulunmaktadır. OMNeT++, NS-2/NS-3 ve NetSim bunlardan bir kaçıdır. OMNeT++ açık kaynak kodlu olması ve birçok kütüphaneye sahiplik etmesi gibi özelliklerinden dolayı günümüzde popülerliğini korumaktadır. Bu çalışmada ARINC-664 ağ standardının simülasyon modelini oluşturma kapsamında OMNeT++ simülasyon aracı kullanılmıştır. Böylece ARINC-664'ün uç nokta ve anahtar modeli uygulanarak, genişletilmiş öncelik konsepti ve genetik algoritma ile optimize edilmiş ağın simülasyon ortamındaki sonuçları elde edilerek karşılaştırmalar yapılmıştır. Buradan elde edilecek sonuçların genetik algoritma ile elde edilen sonuçlar ile uyumlu olması beklenmiştir. Genişletilmiş öncelik kavramının, sanal bağlantıların zamanlayıcı tarafından seçilme kümesini genişlettiğinden, ağdaki uçtan uca gecikme değerlerinin optimizasyon imkanı artmaktadır. Uygun maliyet fonksiyonu seçilirse genetik algoritma optimizasyon yaklaşımının ağdaki bütün uçtan uca gecikme değerleri için istenen hedeflere başarılı bir şekilde ulaşabileceği gösterilmiştir. Simülasyon sonuçları her zaman ağ hesabı sınırlarından daha düşüktür çıkmaktadır. Hem simülasyonda hem de ağ hesabında sonuçların önerilen konsept ile daha başarılı bir şekilde gecikme değerleri elde edilmesi optimizasyonda başarı sağladığını göstermektedir.
Özet (Çeviri)
The Integrated Modular Avionics (IMA) concept, which enables dynamic resource sharing to provide challenging requirements of next-generation aircraft, has been gained significant attention. Deterministic network (DTN) is a key technology of the IMA platform to provide communication among sub-systems with bounded latency and jitter. The quantity of data transferred across IMA systems becomes more essential as the number of integrated functions within an aircraft grows. Because some of the existing avionics communication protocols cannot keep up with the increase in the number of communicating nodes, Ethernet-based DTN solutions have been proposed. Ethernet-based solutions such as ARINC-664, IEEE Time-triggered Ethernet (TTEthernet), and Time Sensitive Network (TSN) are commonly used for DTN. ARINC-664 is the most widely used solution since it does not require a complex synchronization mechanism, and hence, its certification is relatively easier. Ethernet-based deterministic network solution requires offline network planning to make sure that strict timing requirements are met. Network Calculus (NC) is heavily used tool to calculate the worst-case delay bounds for each ARINC-664 network configuration. This thesis presents a Genetic Algorithm (GA) based ARINC-664 network delay optimization using the NC, where the GA is used to effectively search the mapping of ARINC-664 Virtual Links (VLs) to priority levels using the extended priority scheme. While there are only two priority levels in the ARINC-664 standard, the extended priority concept increases the number of priority levels to improve the schedulability of VLs. For each possible assignment of the VLs to the priority levels, the NC analysis provides the worst-case delay results for all VLs. We define three different fitness functions aiming to minimize the maximum, the average, and the standard deviation of the worst-case VL delays, respectively. The results demonstrate that the extended priority concept improves the schedulability of VLs and the GA optimization approach can successfully achieve the desired objectives for the VL delays if the appropriate cost function is selected. In this thesis, we also implement the ARINC-664 End System (ES) and Switch (SW) simulation model in OMNeT++ which is used to simulate and analyze computer networks to verify the NC results of the extended priority concept. The simulation results are always lower than the NC bounds, indicating that the proposed concept successfully provides delay optimization.
Benzer Tezler
- Path optimization for switchless ARINC 664 using heuristic search algorithms
Sezgisel arama algoritmalarını kullanarak anahtarsız ARINC 664 için yol optimizasyonu
SEDAT KAYA
Yüksek Lisans
İngilizce
2022
Savunma ve Savunma TeknolojileriYıldız Teknik ÜniversitesiAviyonik Mühendisliği Ana Bilim Dalı
DOÇ. DR. HÜSEYİN ÜVET
DR. İBRAHİM HÖKELEK
- Genetic algorithm based delay optimization for switchless ARINC 664 network topologies
Anahtarsız ARINC 664 ağ topolojileri için genetik algoritma tabanlı gecikme optimizasyonu
BEKİR GÜL
Yüksek Lisans
İngilizce
2022
Elektrik ve Elektronik MühendisliğiYıldız Teknik ÜniversitesiAviyonik Mühendisliği Ana Bilim Dalı
DR. ÖĞR. ÜYESİ MUHAMMET GARİP
DR. İBRAHİM HÖKELEK
- Making warehouse location decisions with machine learning methods: A case of a Turkish logistics company
Büyük veri makine öğrenme yöntemleri ile depo lokasyon kararlarının alınması: Bir Türk lojistik şirketi örneği
AYCAN SARIÇAM
Yüksek Lisans
İngilizce
2024
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolBahçeşehir ÜniversitesiBüyük Veri Analitiği ve Yönetimi Ana Bilim Dalı
DOÇ. DR. ATINÇ YILMAZ
- Genetic algortithm for the optimization of a gas storage field converted from a depleted gas reservoir
Tüketilmiş gaz rezervuarından dönüştürülen yeraltı gaz depolama sahasının genetik algoritma kullanılarak optimizasyonu
BARIŞ GÜYAGÜLER
Yüksek Lisans
İngilizce
1998
Petrol ve Doğal Gaz MühendisliğiOrta Doğu Teknik ÜniversitesiPetrol ve Doğal Gaz Mühendisliği Ana Bilim Dalı
DOÇ. DR. FEVZİ GÜMRAH
- Genetic algorithm based optimization of renewable power production process
Bir yenilenebilir güç üretim sisteminin genetik algoritma yöntemi ile optimizasyonu
ÖMER FARUK KURT
Yüksek Lisans
İngilizce
2019
Makine MühendisliğiGaziantep ÜniversitesiMakine Mühendisliği Ana Bilim Dalı
DOÇ. DR. AYŞEGÜL ABUŞOĞLU