Tez No	İndirme	Tez Künye	Durumu
765594		Novel data partitioning and scheduling schemes for dynamic federated vehicular cloud / Dinamik federe araç bulutu için yeni bir görev yükü paylaşımı ve iş planlaması şemaları Yazar:WISEBORN MANFE DANQUAH Danışman: PROF. DR. DENİZ TURGAY ALTILAR Yer Bilgisi: İstanbul Teknik Üniversitesi / Lisansüstü Eğitim Enstitüsü / Bilgisayar Mühendisliği Ana Bilim Dalı / Bilgisayar Mühendisliği Bilim Dalı Konu:Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol = Computer Engineering and Computer Science and Control Dizin:	Onaylandı Doktora İngilizce 2022 194 s.
Son on yılda, acil durum araç bildirimi ve otomatik yol hızı denetleme sistemleri gibi birçok Akıllı Ulaşım Sistemi (AUS) uygulaması tasarlanmış ve devreye alınmıştır. AUS uygulamalarının dağıtımındaki artış, araç ortamlarında bilgi işlem kaynaklarına yönelik yüksek bir talebe yol açmıştır. Şu anda, araç içi olanlar da dahil olmak üzere neredeyse tüm AUS uygulama hizmeti sağlayıcıları, müşterilere hizmet sağlamak için İnternet bulut altyapısına güvenmektedir. Ancak, İnternet bulutu, araç ortamlarında kesintili İnternet bağlantısı nedeniyle hizmet erişiminde yüksek gecikmeden muzdariptir. Bu zorluğu aşmak için, araştırmacılar, iletişim için Kablosuz Yerel Alan Ağlarına (KYAA) veya tasarsız ağlara daylı mobil bulut bilişim, uç bilgi işlem ve araç bulut bilişim gibi diğer dağıtılmış bilgi işlem teknolojilerinin kullanılmasını önerdiler. Mobil bulut bilişim, araç ortamlarında işleme ve depolama hizmetleri sunsa da, mobil bulut bilişim sunucularının nispeten sınırlı hesaplama kapasitesi ve daha kısa pil ömrü sorunları, onu diğer dağıtılmış bilgi işlem paradigmalarına kıyasla daha az tercih edilir. Öte yandan, ağın ucuna daha yakın bilgi işlem hizmetlerinin sağlanmasını gerektiren uç bilgi işlem, istemcilere uygulamalarını yürütmeleri için düşük erişim gecikmesi sağlar. Ancak, araç ortamlarında uç bilgi işlem dağıtımı, ilk altyapı kurulum ve yönetiminin yüksek maliyeti nedeniyle uygulamaların yürütülmesinde finansal maliyetleri arttirmaktadir. Araçlara ve Yol Kenarı Birimlerine (YKB'lara) gömülü olan kaynakları kullanarak hizmetlerin sağlanmasını gerektiren araç bulut bilişimi, araçlara gömülü kaynakların verimli kullanımı gibi avantajları nedeniyle tartışmasız diğer dağıtılmış bilgi işlem paradigmalarına en iyi alternatiftir. Avrupa Otomobil Birliği (AOB) ve İstatistik Araştırma Departmanına göre, 1990 ve 2019 yılları arasında Avrupa Birliği ve Amerika Birleşik Devletleri'nde sırasıyla yaklaşık 418 milyon ve 276 milyon araç tescil edildi. CEICData ayrıca Türkiye'de yaklaşık 20 milyon aracın tescil edildiğini tahmin ediyor. Otomotiv endüstrisinin büyüme modeline dayalı olarak, bu araştırmada, önümüzdeki on yılda sadece dünya çapında kayıtlı araç sayısında bir artış olmayacağı, aynı zamanda içlerinde gömülü bilgi işlem kaynaklarının da artacağı öngörülmektedir. Farklı bilgi işlem kaynaklarına sahip çok sayıda araçla birlikte çok sayıda yollarda ve otoparklarda, yeterince kullanılmayan bilgi işlem kaynaklarının olması bekleniyor. Bu nedenle, araç bulut hizmetlerinin sağlanması, araçlarda gömülü bulunan kaynakların verimli kullanılmasına ve böylelikle yeşil teknolojinin benimsenmesine yol açacaktır. Ayrıca, modern araçların ve YKB'ların Tasarsiz Araç Ağı (TAA) kullanılarak iletişim yetenekleriyle tasarlandığı göz önüne alındığında, araç bulut bilişimi, dağıtım öncesinde yollar boyunca ve otoparklarda ek iletişim donanımı altyapısı kurulumu gerektirmeyecektir. Araç ortamlarında araç bulut hizmetlerine erişim, İnternet bulutu gibi diğer dağıtılmış bilgi işlem paradigmalarına erişime kıyasla nispeten daha düşük gecikme süresi içerir. Tüm gelişen teknolojilerde olduğu gibi araç bulut hizmetlaerin shaya aktarılmadan önce bazı problemlerinin, ele alınması gerekir. Araç bulut bilişiminin problemleri, esas olarak araç kaynaklarının benzersiz özelliklerinden ve TAA'in sınırlı iletişim bant genişliğinden kaynaklanmaktadır. Araç ortamlarında, yani yollarda ve park yerlerinde, araçlar uzun süreli: durağan değil hareketlidir. Bu da araçlar da yer alan gömülü kaynakları hareketli hale getirir. Ayrıca bulut hizmetleri sağlamak üzere düzenlenen araçların kaynakları farklı kişilere aittir (dağıtılmış mülkiyet). Kaynakların yüksek hareketliliği ve dağıtılmış mülkiyeti, araç kaynaklarının, kaynak sahibi tarafından kaynakların geri çekilmesi veya araçların yüksek hareketliliğinin neden olduğu aralıklı ağ bağlantısı kesilmesi nedeniyle sağlanan araç bulutundan aniden çıkabileceği anlamına gelir. Bu nedenle kaynakların dağıtılmış mülkiyeti ve araçların yüksek hareketliliği, araç kaynaklarının değişken olmasına neden olarak kullanılabilirliklerini ve güvenilirliklerini ön görülemez hale getirir. Araç bulutunun bir iletişim omurgası olarak hizmet eden TAA'in iletişim bant genişliğinin kapasite kısıtlaması, araç ortamlarında veri yoğun ve bant genişliği yoğun uygulamaların iletiminin araç bulut bilişiminde bir problem yaratacağı anlamına gelir. Kaynakların dağıtılmış sahipliği, sınırlı iletişim bant genişliği ve araçların yüksek mobilitesi, araç bulut bilişiminde kaynakların düşük kullanılabilirliğine ve düşük güvenilirliğine yol açtığı düşünüldüğünde, sanal makine geçişi gibi tüm kaynak yönetimi işlemlerini olumsuz etkiler. Bu nedenle, bu araştırmanın ana odak noktası, araç bulutunun zorluklarını ele almak ve araç bulut bilişiminin tanımlanan özelliklerinin olumsuz etkilerini iyileştirmek için yeni çözümler önermektir. Tezin başlangıcında, araç bulutunun soykütüğü, araç bulutu sağlama modeli türleri ve araç bulut mimarisi gibi kavram ve teknolojileri içeren araç bulut bilişiminin arka planı sunulmustur. Ardından, bu araştırmada önerilen kaynak yönetimi tekniklerinin üç aşamalı sınıflandırması kullanılarak ayrıntılı bir kaynak yönetimi araştırması sunulmustur. Araç bulut bilişim kavramlarının gözden geçirilmesine dayalı olarak, bu tezde yeni bir dağıtılmış araç bilişim paradigması, Gönüllü Araç Bilişimi (GAB) önerilmiştir. GAB, araç sahiplerinin, kanserin daha derin anlaşılması için hesaplamayı kullanan "Compute The Cure" kanser projesi gibi bir topluluğa faydalı olan bilimsel projelerin yürütülmesine yönelik boşta işlem birimlerini bağışlayabilecekleri gönüllü bir bilgi işlem platformudur. Bu araştırmada, GAB'nin tam olarak konuşlandırılmasının son zamanlarda artan, bilimsel projelerin yürütülmesi için büyük hesaplama kaynaklarına olan talebi karşılaycağı öngörülmektedir. Ayrica bu tezde araç bulutunda sınırlı kaynak kapasitesi ve kaynakların değişkenliği sorununun üstesinden gelmek için Dinamik Federe Araç Bulutu (DFAB) kavramı, tanıtılmiştir. DFAB, Hizmet Olarak Hesaplama (HoH) gibi belirli bir araç bulut hizmeti sağlamak için yolda hareket eden farklı araçlardan gelen kaynakların organizasyonunu gerektirir. DFVC'de kaynaklar farklı araçlardan derlenmiş olsa da, hizmetlerin sağlanması için tek bir mantıksal birim olarak organize edilmiştir. Bir DFAB'nin oluşturulması, kaynak tabanlı kümelerin oluşturulmasını, yani benzer kaynak ve hareketlilik özelliklerine sahip araçların tek bir birim olarak gruplandırılmasını ve araç kümesindeki kaynakları yönetmek için küme başkanı olarak bilinen bir liderin seçilmesini içerir. Bir İlgi Bölgesinde (İB) oluşturulan kaynak tabanlı kümelerin yapısı dikkate alınarak, bu tezde iki farklı DFAB şeması önerilmektedir: Küme Tabanlı Araç Bulutu (KTAB) ve Takım Tabanlı Araç Bulutu (TTAB). KTAB'de, yüksek itibara sahip araçlar (sahipler) ve yolda bir İB'ine aıt kaynaklar, tüm küme üyelerinin aynı şeridi kullanması ve araçlar arasında sabit bir boşluk bırakması koşuluna bağlı kalmaksızın kümeler halinde düzenlenir. Öte yandan TTAB, sabit bir boşluğa, yani tüm araçlar arasındaki mesafeye ve bulutun sağlanmasının tüm süresi boyunca aynı şeridin kullanımına sıkı sıkıya bağlı kalmayı gerektiren küme tabanlı araç bulutunun bir çeşididir. Hizmetler. Başka bir deyişle, TTAB, kaynakları belirli bulut hizmetleri sunmak için düzenlenmiş tüm araçlar arasında sürekli bir boşluk bulunan bir konvoydur. Kaynakların sınırlı hesaplama kapasitesi ve kısıtlama iletişim bant genişliği sorununu ele almak için, DBAB tarafından işlenecek büyük veri yükü (bölünebilir yük) bölümlenir ve Görev Yükü Paylaşımı ve İş Planlaması (GYPİP) şemaları kullanılarak bireysel araç düğümlerine dağıtılır. Bu nedenle, bu tezin ana temalarından biri, DBAB'nin araç kaynaklarının ve TAA'in iletişim kanalının özelliklerini dikkate alan yeni GYPİP şemaları tasarlamak ve uygulamaktır. Bu tasarım DBAB için iletişim omurgasının oluşturulması anlamını taşımaktadır. Kaynakların hesaplama kapasitesi, veri iletim bant genişliği kapasitesi ve AGA'te veri iletiminde yaşanan iletişim gecikmesi dikkate alınarak, bu araştırmada önerilen verimli GYPİP şemaları, zamanlama ve veri akış diyagramları kullanılarak geliştirilen matematiksel modeller aracılığıyla tasarlanmıştır. KTAB ve TTAB için GYPİP şemaları, benzersiz özellikleri ve işlemleri nedeniyle literatürde var olanlardan farklı şekilde modellenmiştir. KTAB için önerilen GYPİP şeması, araç küme liderinin türetilmiş kapalı form matematiksel denklemleri kullanarak her araç için veri yığınını belirlediği ve ardından veri parçalarını doğrudan KTAB'deki ilgili araçlara işlemek üzere tek bir sıçrama ile dağıttığı dikkate alınarak modellenmiştir. Araçlar işlendikten sonra işlenen veri parçalarını doğrudan araç küme liderine iletir. Bu tezde KTAB için GYPİP şeması, UniDRM olarak anılan birleşik veri, kaynak ve kanal yönetimi çerçevesinin bir parçası olarak uygulanmaktadır. Veri bölümleme ve çizelgeleme için farklı kriterler veya hedefler göz önünde bulundurularak, zamana duyarlı, maliyete duyarlı ve güvenilirliğe duyarlı üç farklı DPS şeması önerilmiştir. TTAB için, veri bölümleme, türetilmiş kapalı form denklemleri kullanılarak öncü düğüm, yani takımın ilk düğümü tarafından gerçekleştirilir. Takım üyelerinin belirlenen veri parçaları daha sonra ya doğrudan (tek sekme) ya da çok sekmeli aktarım yoluyla dağıtılır. Kapalı form denklemleri, müfrezelerdeki araçların, müfreze Bilgi Akışı Topolojileri (BAT) olarak adlandırılan komşu düğümleri ile nasıl bilgi alışverişinde bulunduklarına dayalı olarak tasarlanan veri akışı ve zamanlama diyagramları dikkate alınarak türetilmiştir. Bu tezde, mevcut müfreze BAT'leri: Çift Yönlü (ÇY), Çift Yönlü Lider (ÇYL) ve Hepsinden Tümüne (HT), altı farklı DPS şeması için matematiksel modeller türetmek üzere değiştirilir; Çift Yönlü-Özyinelemeli (ÇY-Ö), Çift Yönlü Geçmeli (ÇY-G), Çift Yönlü Lider-Özyinelemeli (ÇYL-Ö), Çift Yönlü Lider Geçmeli (ÇYL-G), Çift Yönlü Lider Toplama -Özyinelemeli (ÇYLT-Ö) ve Çift Yönlü Lider Toplama-Geçmeli (ÇYLT-G). Omnet++, Sumo, Veins ve Plexe benzetim platformları kullanılarak geliştirilen gerçekçi simülasyonlar ile önerilen GYPİP şemalarının detaylı başarım analizi yapılmıştır. Performans analizinden, ÇYL-Ö ve ÇYL-G şemalarının görev yürütme hızı açısından en iyi performansa sahip olduğu gözlemlendi. Bununla birlikte, ÇY-Ö, ÇY-G, ÇYLT-Ö ve ÇYLT-G şemaları, işlenmiş veri bölümlerinin toplanması, işlenmiş veri bölümlerini iletmeden önce her araç tarafından gerçekleştirildiğinden, GYPİP sürecinde bağımlılıkları zorlama avantajına sahiptir. Bu araştırmada, araç ortamlarında veri iletiminin temel zorluklarından biri olan, yani iletişim kanalındaki tıkanıklığın neden olduğu iletişim gecikmesinin belirlenmesi, stokastik modelleme yoluyla ele alınmaktadır. Modellenen iletişim gecikme değerleri, araç ortamlarında daha gerçekçi olmaları için GYPİP şemalarına dahil edilmiştir. TTAB için farklı GYPİP şemaları geliştirerek, literatürde bölünebilir veri bölümleme ve programlamanın uzun süredir devam eden zorluklarından biri: doğrusal olarak düzenlenmiş bağlı heterojen işlemciler ağının işlem süresi için kapalı form denklemlerinin modellenmesi ve türetilmesi ele alınmaktadır. Literatüre göre, özyinelemeli denklemleri çözerken bireysel veri bölümleri için ifadelerde görünen karmaşık kombinatoryal terimler nedeniyle bağlı işlemcilerin heterojen lineer ağı için kapalı form denklemleri yoktur. Ancak bu araştırmada cebirsel işlemler kullanılarak kapalı form denklemler türetilmiş ve modellenmiştir. Sonüç olarak, bu tez, araçlardaki sınırlı kullanılabilir kaynak kapasitesi ve araç iletişim kanalının bant genişliği kısıtlaması dahil olmak üzere, araç bulut bilişiminin temel zorluklarına yeni çözümler sunmaktadır.
In the last decade, many Intelligent Transport Systems (ITS) applications, that rely on the Internet cloud infrastructure have been deployed to provide services to clients in vehicular environments. However, the Internet cloud suffers from high latency in service access and intermittent Internet disconnection in vehicular environments. In response to these challenges, researchers have proposed the use of other distributed computing technologies such as mobile cloud computing, edge computing, and vehicular cloud computing which may rely on Wireless Local Area Networks (WLAN) or Ad-hoc networks for communication to provide computing resources and services in vehicular environments. Vehicular cloud computing, an emerging distributed computing paradigm that provides cloud services using the resources embedded in vehicles and Road Side Units (RSUs), is arguably the best alternative to other distributed computing systems because of its advantages. The provision of vehicular cloud services leads to efficient utilization of the abundant resources in embedded vehicles and therefore embraces green technology in vehicular environments. Considering that modern vehicles and RSUs have been designed with communication capabilities through the use of the Vehicular Ad-hoc Network (VANET), vehicular cloud computing may not require additional communication hardware infrastructure installation along roads and at parking lots before its deployment. Furthermore, access to vehicular cloud services may involve a relatively lower latency and fewer intermittent disconnections due to the close proximity of vehicular cloud resources to clients and the use of VANET which may provide better connections among vehicular resources and clients than the connection to Internet cloud in vehicular environments. As with all emerging technologies of which vehicular cloud is not an exception, some challenges need to be addressed before its full real-world deployment. The challenges of vehicular cloud computing are mainly caused by the unique characteristics of vehicular resources and the limited communication bandwidth of VANET. In vehicular environments, i.e., on roads and parking lots, vehicles are not permanently stationed but mobile, making the resources embedded in vehicles highly mobile. Also, the resources of vehicles that are organized to provide cloud services belong to different people (distributed ownership). The high mobility and distributed ownership of resources imply that vehicular resources may exit the provisioned vehicular cloud abruptly by either withdrawal of resources by the resource owner or intermittent network disconnection caused by the high mobility of vehicles. Therefore distributed ownership of resources and high mobility of vehicles cause vehicular resources to be volatile, making their availability and reliability unpredictable. The capacity constraint of the communication bandwidth of VANET, which serves as a communication backbone of vehicular cloud, implies that the transmission of data-intensive and bandwidth-intensive applications in vehicular environments is a challenge in vehicular cloud computing. Considering that the distributed ownership of resources, limited communication bandwidth, and high mobility of vehicles lead to low availability and low reliability of resources in vehicular cloud computing, they adversely affect almost all resource management operations, such as virtual machine migration. Therefore, the main focus of this dissertation is to propose novel solutions to address the challenges of vehicular cloud and ameliorate the adverse effects of the identified characteristics of vehicular cloud computing. As an introduction, the background of vehicular cloud computing and a detailed survey of resource management operations in vehicular cloud are presented using a three-phase taxonomy of resource management techniques proposed in this dissertation. Based on the review of vehicular cloud computing concepts, a novel distributed vehicular computing paradigm, Vehicular Volunteer Computing (VVC), is proposed in this dissertation. VVC is a volunteer computing platform where vehicle owners may donate their idle processing units towards the execution of scientific and other projects that are beneficial to a community, such as the "Compute The Cure" cancer project. The concept of a Dynamic Federated Vehicular Cloud (DFVC) is introduced in this dissertation to overcome the challenge of limited resource capacity and volatility of resources in vehicular cloud. The DFVC entails the organization of resources from different vehicles moving on the road to provide a specific vehicular cloud service such as Computation-as-a-Service (CaaS). Although the resources are collated from different vehicles in the formation of DFVC, they are organized as a single logical unit for the provision of services. The formation of a DFVC involves forming resource-based clusters, i.e., grouping vehicles with similar resource and mobility characteristics as a single unit and selecting a leader, known as a cluster head, to manage the resources in a cluster of vehicles. By considering the structure of resource-based clusters formed in a Region of Interest (RoI), two different DFVC schemes are proposed in this dissertation: the Cluster-Based Vehicular Cloud (CBVC) and the Platoon-Based Vehicular Cloud (PBVC). In the CBVC, vehicles (owners) with a high reputation and idle resources on an RoI on the road are organized into clusters without adhering to the condition that all cluster members use the same lane and maintain a fixed gap between vehicles. The PBVC, on the other hand, is a variant of the cluster-based vehicular cloud that requires strict adherence to a constant gap, i.e., the distance between all vehicles and the use of the same lane throughout the entire period of the provision of cloud services. In other words, the PBVC is a convoy with a constant gap between all vehicles whose resources are organized to offer specific cloud services. In order to address the challenge of limited computation capacity of resources and constraint communication bandwidth, a large divisible data load to be processed by the DFVC is partitioned and distributed to the individual vehicular nodes using efficient Data partitioning and Scheduling (DPS) schemes. One of the central themes of this dissertation is, therefore, to design and implement novel DPS schemes that consider the characteristics of vehicular resources of the DFVC and the communication channel of VANET: the communication backbone for DFVC. By considering the computation capacity of resources, data transmission bandwidth capacity, and communication delay experienced in data transmission in VANET, efficient DPS schemes proposed in this dissertation are designed through mathematical models developed using timing and data flow diagrams. The DPS schemes for the CBVC, and PBVC are modeled differently because of their unique characteristics and operations. The proposed DPS scheme for the CBVC was modeled with the consideration that the cluster head determines the data chunk for each vehicle using derived closed form mathematical equations and then distributes the data chunks directly as a single hop to the respective vehicles in the CVBC to process. After processing, the vehicles then transmit the processed data chunks directly to the cluster head. The DPS scheme for the CBVC is implemented as part of a unified data, resource, and channel management framework, which is referred to as the UniDRM in this dissertation. Considering different criteria or objectives for data partitioning and scheduling, three distinct DPS schemes, time-aware, cost-aware, and reliability-aware, are also proposed in this dissertation. For the PBVC, the data partitioning is carried out by the lead node, i.e., the first node of the platoon, using derived closed form equations. The determined data chunks of the platoon members are then distributed either directly (single hop) or through multi-hop transmission. The closed form equations were derived considering data flow and timing diagrams designed based on how vehicles in platoons exchange information with their neighbor nodes, which is referred to as platoon Information Flow Topologies (IFT). In this dissertation, existing platoon IFTs: the Bi-Directional (BD), Bi-Directional Lead (BDL), and the All- to- All IFT (A2A) are modified to derive mathematical models for six different DPS schemes, namely, the Bi-Directional-Recursive (BD-R), Bi-Directional Interlaced (BD-I), Bi-Directional Lead-Recursive (BDL-R), Bi-Directional Lead-Interlaced (BDL-I), Bi-Directional Lead Aggregate-Recursive (BDLA-R), and Bi-Directional Lead Aggregate-Interlaced (BDLA-I). Through realistic simulations developed via the use of the simulation platforms Omnet++, Sumo, Veins, and Plexe, a detailed performance analysis of the proposed DPS schemes were carried out. By developing the different DPS schemes for the PBVC, one of the long-standing challenges of divisible data partitioning and scheduling in the literature: the modeling and derivation of closed form equations for determining the percentage of data chunks and the processing time of the linearly arranged network of connected heterogeneous processors, is addressed. According to the literature, there are no closed form equations for the heterogeneous linear network of connected processors because of the complicated combinatorial terms that appear in expressions for individual data partitions while solving the recursive equations. However, using algebraic manipulations, closed form equations have been derived and modeled in this dissertation. In all, this dissertation presents novel solutions to key challenges of vehicular cloud computing, including the limited available capacity of resources in vehicles and the bandwidth constraint of the vehicular communications channel.