Energy aware endurance framework for mission critical aerial networks

thumbnail.default.alt
Tarih
2019
Yazarlar
Özçevik, Yusuf
Süreli Yayın başlığı
Süreli Yayın ISSN
Cilt Başlığı
Yayınevi
Fen Bilimleri Enstitüsü
Institute of Science and Technology
Özet
Cisco teknik raporuna göre (Visual Networking Index, VNI), internete bağlı hareketli cihaz sayısı dünya genelinde hızla artmaktadır. Rapora göre, 2017 yılında 8.6 milyar olarak tespit edilen cihaz sayısının 2022 yılı itibarıyla 12.3 milyara ulaşması beklenmektedir. Cihaz sayısında öngörülen artış dikkate alındığında, bu cihazlar tarafından üretilen mobil veri trafiğinin de artması kaçınılmazdır. Aynı rapora göre, dünya genelinde aylık mobil veri trafiği 2017 yılında 12 Exabyte iken, 2022 yılında 77 Exabyte olması öngörülmektedir. Söz konusu artışın mevcut karasal ağ alt yapıları ile yönetilmesi son derece zordur. Bu sebeple, yenilikçi ağ alt yapılarına duyulan gereksinim günden güne ortaya çıkmaktadır. İnternete bağlı cihaz sayısı ve bu cihazların ürettiği mobil veri trafiğinde yaşanan artışa paralel olarak, günümüzde gelişen teknolojilerden biri de havasal ağlardır. Uluslararası İnsansız Araç Sistemleri Derneği (Association for Unmanned Vehicle Systems International) raporuna göre, Amerika Birleşik Devletleri için İnsansız Hava Aracı (İHA) endüstrisinden doğan doğrudan ekonomik etki 2015 yılında 1.2 milyar amerikan doları iken, 2025 yılında 5.1 milyar amerikan doları olması beklenmektedir. Aynı raporda, İHA'ların uygulama alanlarından bir tanesi de haberleşme sistemleri olarak belirtilmektedir. Belirtilen gelişmeler doğrultusunda, İHA kullanılarak oluşturulan havasal ağ topolojileri son yıllarda yayın olarak kullanılmaktadır. Havasal ağlar tek başlarına bir servis alt yapısı oluşturmak üzere kullanıldığı gibi gibi karasal ağ ekipmanlarına yardımcı olmak üzere de kullanılır. Her iki kullanım amacının ortak özelliklerinden birisi havasal ağların kısa zamanlı ve göreve özel olmasıdır. Ağın havadaki fiziksel varlığını sürdürebilmek için bir güç kaynağına ihtiyaç duyulması, bu durumun en önemli sebebi olarak gösterilebilir. Bu bağlamda, enerji farkındalığı, havasal ağlarda asgari bakım maliyeti ile daha uzun bir dayanıklılık sağlamak için üzerinde durulması gereken en önemli konulardan biri olarak ele alınmaktadır. Literatürdeki çalışmalarda, havasal ağlar için enerji farkındalığı sağlamak üzere bir çok çalışma yapılmış olsa da, bu çalışmaların sadece bir kısmı ağın havadaki varlığını sürdürmesi için gerek duyduğu zorunlu enerjiyi dikkate alır. Havasal ağlarda, hesaplama ve haberleşme için harcanan ernerji miktarının, ağı havada tutmak için gereken enerji miktarına göre çok daha az olduğu bilinmektedir. Dahası, bir İHA'nın uçarken harcadığı enerji miktarı; uçuş yönü, uçuş hızı gibi bir çok parametreye ve maruz kaldığı fiziksel kuvvetlere göre farklılık gösterir. Bu sebeple, bu tezde, bir İHA'nın uçuş karakteristiği ile enerji tüketimi ilişkisi göz önüne alınarak, havasal ağın sürekliliğini sağlamak için gerek duyulan İHA değişimleri sırasında, enerji farkında bir uçuş planlaması sunulur. Havasal ağlarda, bir İHA'nın enerji tüketimini etkileyen en önemli faktör, İHA'nın maruz kaldığı fiziksel kuvvetlerdir ve uygun bir enerji farkındalığı sağlamak için dikkate alınması gerekir. İHA'ya etki eden bileşenler arasında, yer çekimi kuvveti, en belirleyici kuvvettir ve bir İHA'nın hareketi esnasında harcadığı enerji ile doğrudan ilişkilendirilebilir. Bu sebeple, tezde, enerji tüketimiyle ilişkili bir topoloji grafı modellenmektedir. Bu grafta, İHA konumları düğümlerle, bir yolu katetmek için gereken enerji tüketim maliyetleri ise kenarlarla ifade edilmektedir. Önerilen yaklaşımın doğrulanması için üç farklı yönlü ve tamamlanmış graf modeli sunulur ve her bir graph modelinde yer çekimine karşı yapılan hareketler farklı şekilde maliyetlendirilir. Topoloji grafı oluşturulduktan sonra, bir optimizasyon problemi sağlamak ve belirlenen algoritmik bir yaklaşımla bir çözüm kümesi önermek için Tamsayılı Doğrusal Programlama (Integer Linear Programming, ILP) ile birlikte bir Havasal Toplama ve Dağıtma Problemi (Aerial Pickup and Delivery Problem, APDP) tanıtılır. Sunulan topoloji modeli ve optimizasyon problemi göz önüne alındığında, İHA değişimine gerek duyulan bir t anında, en az enerji tüketimine sahip uçuş planlamasını sağlamak üzere bir Mekansal Uçuş Planlayıcısı (Spatial Flight Planner) önerilir. Uçuş planlayıcısının gerçeklenmesi için Dinamik Programlama (Dynamic Programing, DP) yaklaşımıyla Bellman-Ford algoritması kullanılarak topoloji grafı üzerindeki en az maliyetli uçuş planı araştırılır. Ayrıca, önerilen sistem, havasal ağın tüm operasyonel zamanını göz önünde bulunduran ve sadece t zamanındaki minimum enerji tüketimini değil, aynı zamanda küresel arama alanını tarayan Zamansal Uçuş Planlayıcısı (Temporal Flight Planner) adlı bir uçuş planlama algoritması ile ilave bir geliştirme daha ortaya koyar. Genişleyen arama alanını makul bir sürede taramak üzere Genetik Algoritmalar (Genetic Algorithms, GA) yaklaşımı kullanılır. Böylece, olası çözüm kümesinin bir kısmı elenerek optimuma yakın bir alt çözüm kümesi taranır ve sistemden daha kısa sürede yanıt alınır. Önerilen sistemin gerçeklenmesinden sonra, algoritmaların zaman ve bellek karmaşıklıklarını ölçmek üzere bir dizi analiz yürütülmekedir. Tezde incelenen havasal ağ için belirlenen uygulama alanı ve çalışılan senaryolar dikkate alındığında, sonuçların uygun sınır dahilinde olduğu belirtilebilir. Önerilen sistemin değerlendirilmesi ve topoloji hakkında enerji farkındalığı gözetmeyen geleneksel bir yaklaşım ile karşılaştırılması için kapsamlı bir simülasyon ortamı sunulmaktadır. Bu sebeple, üç farklı senaryo ölçeği göz önüne alınarak farklı sayıda İHA, karasal son kullanıcı ve kapsama alanı belirlenir. Dahası, simülasyon ortamının oluşturulması ve çıktıların elde edilmesi için gereken bir dizi simülasyon aracı tanıtılır. Ayrıca, simülasyon boyunca kullanılacak ağ mimarisine ilişkin tüm varsayımlar açıkca sunulur. Tezde tanıtılan sistemin değerlendirmesi için, çeşitli boyut ve kanat tipine sahip İHA'lardan en yaygın olarak kullanılan, döner kanatlı dronlar kullanılmaktadır. Simülasyon ortamında test edilen havasal ağın bir sosyal etkinlik için bir araya toplanan kullanıcılara hizmet sağladığı düşünülmektedir. Önerilen sistem ve geleneksel yaklaşım için her bir senaryo ölçeği dört saat çalıştırılarak simülasyon ortamından veriler toplanır ve tezde tanıtılan üç performans kriteri üzerinden bir karşılaştırma sağlanır. Bu performans kriterlerinden δ, simülasyon boyunca harcanan toplam enerji miktarının normalize edilmesiyle elde edilir ve 0-100 arası değerler almaktadır. Değerlendirme sonucuna göre, önerilen sistem, δ parametresi dikkate alındığında %20'ye varan enerji tasarrufu sağlamaktadır. Performans kriterlerinden ikincisi, γ parametresi, havasal ağın varlığı boyunca, hava-kara arasında, ihtiyaç duyulan toplam dron değiştirme sayısını göstermektedir. Bir başka deyişle, hizmet süresi boyunca enerji kaynağını tüketen ve yerdeki yedek dronlardan biri ile değiştirilmesi gereken toplam dron sayısıdır. Elde edilen bulgulara göre, önerilen sistem kullanıldığında, %15'e kadar daha az sayıda dron enerji kaynağını tüketerek değişime ihtiyaç duymaktadır. Performans kriterlerinden üçüncüsü ise, η, bir dronun ortalama havada kalma süresini işaret etmektedir. Önerilen sistem ile bu değer %18 oranında artırılmaktadır. Değerlendirme sonuçlarından elde edilen bulgulara göre, önerilen sistemin, geleneksel bir yönteme göre daha başarılı bir enerji farkındalığı yarattığı vurgulanabilir. Dahası, arama alanının zaman ekseninde genişletilmesi sonucu elde edilen bulguların, belirli bir t anı için elde edilen bulgulara göre daha da iyi olduğu gösterilmektedir. Öte yandan, geniş arama alanında tarama yaparak makul bir sürede çözüm bulmak için kullanılan evrimsel algoritmalar, (Evolutionary Algorithms), rassal yapıları gereği her zaman en iyi sonucu bulmayı garanti etmemektedir. Bu sebeple, GA yönteminin kullanılması ile elde edilen sonuçların evrensel optimum sonuca ne kadar yakın olduğu, sistemin başarımının kanıtlanması açısından, incelenmektedir. Buna göre, Zamansal Uçuş Planlayıcısı'nın DP ve GA yaklaşımları ile gerçeklenmesi sonucu elde edilen bulgular birbirleriyle karşılaştırılır. GA gerçeklemesi ile elde edilen bulguların, DP gerçeklemesi ile elde edilen bulgulara göre %5'e kadar daha kötü enerji farkındalığına sebep olduğu; ancak, GA gerçeklemesi ile sistemin 30 kata kadar daha kısa sürede yanıt vermesinin sağlandığı gösterilmektedir. Bu sebeple, sistemin uygun bir şekilde hizmet verebilmesi için GA yaklaşımının kullanımı onaylanmaktadır. Sonuç olarak, önerilen sistem kullanıldığında, çalışmada ele alınan geleneksel yaklaşımdan daha uygun bir enerji farkındalığı sağlandığı ve önerilen sistemin evrimsel algoritmalar kullanılarak gerçeklenmesinin, daha makul sürede yanıt vermeye yardımcı olurken, sağlanan çözümlerin üstünlüğüne zarar vermediği savunulabilir. Simülasyonlar sırasında önerilen sistem tarafından bulunan çözümlerde, uçuş planlamasının havadaki dronlar arasında yer değiştirmeler içerdiği rapor edilmektedir. Bu sebeple, karasal son kullanıcıların servis taleplerini kesintisiz olarak karşılamak üzere, dronlar üzerine konuşlandırılmış Havasal Baz İstasyonları (HBİ) arasında kullanıcı devri yapılması gerekmektedir. Elde edilen bulgulara göre, önerilen sistem, geleneksel bir yönteme kıyasla %14'e kadar daha fazla kullanıcı devri sayısına (Ψ) sebep olmaktadır. Literatürdeki çalışmalara göre, kullanıcı devri sayısının artması durumunda son kullanıcı performansına dair bazı parametrelerde düşüş yaşandığı görülmektedir. Bu nedenle, önerilen sistemin sebep olduğu kullanıcı devri sayısının, son kullanıcı performansına etkisini araştırmak üzere, simülasyon ortamı genişletilerek ortalama kullanıcı düzlemi gecikmesi parametresi (average access link latency) ve paket kayıp oranı parametresi (packet loss ratio) incelenmektedir. İncelemede, gerçek zamanlı ve gerçek zamanlı olmayan uygulamaların ürettiği heterojen bir son kullanıcı trafiği göz önünde bulundurulur. Değerlendirme sonuçlarına göre, önerilen sistemin %10'a kadar daha fazla ortalama kullanıcı düzlemi gecikmesine ve %19'a kadar daha fazla paket kaybı oranına neden olduğu belirlenir. Sonuç olarak, önerilen sistemin son kullanıcı perspektifinde bir bozulmaya neden olduğu, ancak enerji farkındalığı perspektifinden ise önemli miktarda bir enerji tasarrufu sağladığı sonucuna varılmaktadır. Dahası, literatürde yer alan teknik raporlar incelendiğinde, son kullanıcı performansında meydana gelen kötüleşmenin kabul edilebilir bir seviyede olduğu ortaya konmaktadır. Ayrıca, önerilen sistemin son kullanıcı performansı üzerindeki olumsuz etkisini sınırlandırmak adına, bir Kullanıcı Devri Faktörü İyileştiricisi (Handover Factor Optimizer) algoritması sisteme eklenir. Böylece, son kullanıcı performansında meydana gelebilecek bozulma, önceden belirlenen bir kullanıcı faktörü değeri ile sınırlandırılır. Önerilen eklenti üzerinde gerçekleştirilen zaman karmaşıklığı ve bellek karmaşıklığı analizleri de tezde sunulmaktadır. Son olarak, önerilen sistemin farklı trafik istekleri olan son kullanıcılar üzerindeki etkisini daha ayrıntılı incelemek üzere, sadece gerçek zamanlı ve sadece gerçek zamanlı olmayan trafik istekleri üreten simülasyon ortamları ayrı ayrı incelenmektedir. Böylece, önerilen sistem nedeniyle kullanıcı performansında meydana gelen düşüş farklı trafik isteklerine göre detaylıca ele alınmaktadır ve önerilen sistemin farklı kullanım senaryoları için uygulanabilirliği araştırılmaktadır. Değerlendirme sonuçlarına göre, gerçek zamanlı olmayan trafik istekleri ile ele alınan senaryoda, daha fazla kullanıcı düzlemi gecikmesi ve paket kaybı oranı olduğu görülmektedir. Bu nedenle, önerilen sistemin, gerçek zamanlı olmayan trafik isteği bulunan son kullanıcılar için dikkatli bir şekilde görevlendirilmesi gerektiği vurgulanır. Bununla birlikte, önerilen sistemin uygulama alanı ve tezde incelenen senaryolar dikkate alındığında, genel olarak Hiper-Metin Transfer Protokolü (Hypertext Transfer Protocol Version 3, HTTP3) ve Hızlı Kullanıcı-Datagram-Protokolü İnternet Bağlantıları (Quick User-Datagram-Protocol (UDP) Internet Connections, QUIC) gibi yeni nesil gerçek zamanlı protokoller kullanan son kullanıcı uygulamarı karşımıza çıkmaktadır. Sonuç olarak, bir son kullanıcı tarafından üretilebilecek her iki trafik tipi için, önerilen sistem nedeniyle meydana gelen performans düşüşünün, sistemdeki enerji tasarrufu göz önüne alındığında, kabul edilebilir düzeyde olduğu iddia edilir.
The number of networked mobile devices has increased excessively all around the world and the data traffic requests generated by such devices has begun to overwhelm conventional network infrastructures, recently. At the same time, the proliferation of Unmanned Aerial Vehicles (UAV) in different application areas has also increased. Eventually, these two concepts have been interacting with each other in these days and UAVs becomes one of the most popular tools interacting with computer networking to compose aerial networks. The deployment of such networks provides a flexible and efficient management of traffic requests with a mission specific temporary intention, especially for short duration scenarios. Beside the opportunities provided in aerial networks, there are some major challenges should be carefully recognized to provide the existence of the network in a reasonable and proper way. Energy awareness is one of the major challenges in aerial networks to provide a longer endurance with minimum maintenance cost. There is a considerable amount of interest in the literature to provide energy efficiency for an aerial network. However, the compulsory energy demand to maintain the existence on the air is neglected in most of them. Thus, in the thesis, the major energy consumer of an aerial network is determined as the flying capability and an energy aware endurance framework is presented by taking the flight path planning into account. The energy awareness for a flight planning in an aerial network can be understand in a proper way by considering the fact that there is a relation between energy consumption and flight characteristic of a UAV. The physical forces exposed by a UAV determine the amount of energy consumption during a path traversal. For this purpose, an energy consumption related topology graph is presented in the thesis by accounting a digraph model that has a UAV in each vertex and also has energy consumption cost on each edge. The gravity force is taken into account for graph modeling because of being the determinant one that cause a compulsory energy consumption and three different digraph model are presented for the validation of the proposed approach. Moreover, an Aerial Pick-up and Delivery Problem (APDP) is presented with Integer Linear Problem (ILP) to provide an optimization problem and to recommend a solution set with an algorithmic approach. Considering the graph model provided, a Spatial Flight Planner is implemented using Bellman-Ford algorithm with Dynamic Programming (DP) approach and a flight planning is provided with minimum energy consumption cost when new flight routes is required in the topology at a certain time t. A further improvement is presented in the proposed model with another flight planning algorithm named Temporal Flight Planner that considers the entire operational time of the aerial network and seeks out not only the minimum energy consumption at time t, but also the global search space. The Genetic Algorithms (GA) fashion is utilized to implement Temporal Flight Planner in order to prune some of the solution candidates in the enlarged search space and respond in a reasonable amount of time. Subsequent to the implementation, a complexity analysis for time and memory requirements of the algorithms is also conducted and it is presented that the outcomes are restricted within an appropriate boundary considering the deployment purposes of studied scenarios. A certain case study is presented to evaluate the proposed framework and compare it with a conventional replenishment approach that does not take any information about the topology into account. To this end, three different scale of simulation scenarios and a set of simulation tools are introduced for the evaluation. Moreover, the assumptions about the network architecture is presented clearly and the type of UAVs to be deployed are determined as rotary wings i.e. drones. Eventually, the energy awareness for the end-system perspective is evaluated with respect to a normalized energy consumption value during the operational time (δ), the number of total replenishments between the ground and air named as the replenishment factor (γ), and an average endurance per drone (η). According to the evaluation outcomes, up to 20% less δ value is obtained that corresponds to a remarkable amount of energy saving with the deployment of the proposed framework to compared with a conventional one. Similarly, γ value is decreased with a ratio up to 15% and η value is increased with 18% indicating less number of terrestrial replenishments and more average endurance per drone, respectively. Moreover, considering the stochastic improvement characteristic of evolutionary algorithms, an investigation for GA implementation is conducted to determine the optimality closeness of the provided solution to the global optimum. As a consequence, it can be inferred from the evaluation that the proposed framework is able to provide an energy aware topology maintenance compared with a conventional replenishment approach and the implementation of the proposed framework using evolutionary algorithms does not damage the optimality of provided solutions; rather, it helps to respond in more reasonable duration. The effect of the proposed framework from an end-user perspective is also investigated because it is reported during the simulations that the proposed solution includes some replacement between the drones on the air. Hence, this situation corresponds a more number of end-system initiated handovers for a terrestrial end-user in average. To this end, the number of end-system initiated handovers i.e. the handover factor (Ψ) is investigated for both of the proposed model and a conventional one. A difference up to 14% is reported between these two approaches where the proposed model causes more handovers. Accordingly, the effect of number of end-system initiated handovers is examined with respect to some end-user Quality of Experience (QoE) parameters including average access link latency and packet loss ratio. A heterogeneous end-user traffic generated by real time and non-real time applications is considered in the evaluation. According to the evaluation results, it is presented that the proposed framework causes 10% more average access link latency and 19% more packet loss ratio. As a conclusion, it is deduced from the evaluation that the proposed framework provides causes a disruption on end-user perspective whereas it provides a significant amount of energy saving from the end-system perspective. The trade off between them is also verified in the literature and a Handover Factor Optimizer algorithm is appended to the proposed framework in order to bound the deterioration inside admissible level through a predefined handover factor value. The analyzes for the additional algorithm is also presented. A final investigation is conducted for the effect of the proposed framework on the end-user parameters under different traffic request including only real time traffic requests and non-real time traffic requests. Hence, the deterioration level for different traffic requests is identified and feasibility of the proposed framework is questioned. According to the evaluation results, it is seen that there are more access link latency and packet loss ratio under the case with non-real time traffic requests. Nonetheless, the application field for the proposed system and scenarios studied in the thesis are real time in general because of recent application protocols used by terrestrial end-users such as Hypertext Transfer Protocol Version 3 (HTTP3) and Quick User-Datagram-Protocol (UDP) Internet Connections (QUIC). As a consequence, it can be claimed that the performance degradation of an end-user for both traffic types are in acceptable level considering the energy savings in the end-system.
Açıklama
Tez (Doktora) -- İstanbul Teknik Üniversitesi, Fen Bilimleri Enstitüsü, 2019
Theses (Ph.D.) -- İstanbul Technical University, Institute of Science and Technology, 2019
Anahtar kelimeler
Bilgisayar ağları, Veri iletme sistemleri, Enerji tüketimi, Uzaktan kumandalı uçak, Computer networks, Data transmission systems, Energy consumption, Drone aircraft
Alıntı