STORE AND FORWARD SCHEDULING IN CLUSTERED VEHICULAR NETWORKS. M.Sc. THESIS. Salih Serdar GÜÇLÜ. Department of Computer Engineering - PDF

Description
ISTANBUL TECHNICAL UNIVERSITY GRADUATE SCHOOL OF SCIENCE ENGINEERING AND TECHNOLOGY STORE AND FORWARD SCHEDULING IN CLUSTERED VEHICULAR NETWORKS M.Sc. THESIS Salih Serdar GÜÇLÜ Department of Computer Engineering

Please download to get full document.

View again

of 65
All materials on our website are shared by users. If you have any questions about copyright issues, please report us to resolve them. We are always happy to assist you.
Information
Category:

Investor Relations

Publish on:

Views: 25 | Pages: 65

Extension: PDF | Download: 0

Share
Transcript
ISTANBUL TECHNICAL UNIVERSITY GRADUATE SCHOOL OF SCIENCE ENGINEERING AND TECHNOLOGY STORE AND FORWARD SCHEDULING IN CLUSTERED VEHICULAR NETWORKS M.Sc. THESIS Salih Serdar GÜÇLÜ Department of Computer Engineering Computer Engineering Programme MAY 2014 ISTANBUL TECHNICAL UNIVERSITY GRADUATE SCHOOL OF SCIENCE ENGINEERING AND TECHNOLOGY STORE AND FORWARD SCHEDULING IN CLUSTERED VEHICULAR NETWORKS M.Sc. THESIS Salih Serdar GÜÇLÜ ( ) Department of Computer Engineering Computer Engineering Programme Thesis Advisor: Associate Prof. Dr. Deniz Turgay ALTILAR MAY 2014 İSTANBUL TEKNİK ÜNİVERSİTESİ FEN BİLİMLERİ ENSTİTÜSÜ KÜMELENMİŞ ARAÇLAR ARASI AĞLARDA SAKLA VE İLET TİPİ İLETİŞİMLERİN ZAMANLANMASI YÜKSEK LİSANS TEZİ Salih Serdar GÜÇLÜ ( ) Bilgisayar Mühendisliği Anabilim Dalı Bilgisayar Mühendisliği Programı Tez Danışmanı: Associate Prof. Dr. Deniz Turgay ALTILAR MAYIS 2014 Salih Serdar GÜÇLÜ, a M.Sc. student of ITU Graduate School of Science Engineering and Technology successfully defended the thesis entitled STORE AND FORWARD SCHEDULING IN CLUSTERED VEHICULAR NETWORKS, which he/she prepared after fulfilling the requirements specified in the associated legislations, before the jury whose signatures are below. Thesis Advisor : Associate Prof. Dr. Deniz Turgay ALTILAR... Istanbul Technical University Jury Members : Prof. Dr. Sema Fatma OKTUĞ... Istanbul Technical University Assistant Prof. Dr. Müjdat SOYTÜRK... Marmara University... Date of Submission : 5 May 2014 Date of Defense : 28 May 2014 v vi vii To Sıla, viii FOREWORD Since the last year of bachelor of science, I have worked on vehicular networks. I had deep knowledge on vehicular networks from then to now. I would like express my gratitude to my supervisor, Assoc. Dr. D. Turgay Altılar for his excellent guidance and friendliness. I feel honoured to work with him. I appreciate my brother, my mother and my father for their faith in me. Finally, I would like to give my special thanks to my dear fianceé, Sıla Özen for her endless support during this journey. Without her, I could not have strength to complete this work. May 2014 Salih Serdar GÜÇLÜ (Computer Engineer) ix x TABLE OF CONTENTS Page FOREWORD... ix TABLE OF CONTENTS... xi ABBREVIATIONS... xiii LIST OF FIGURES... xv SUMMARY...xvii ÖZET... xix 1. INTRODUCTION Definition of Problem Purpose of Thesis Contributions of Thesis Structure of Thesis LITERATURE SURVEY AND MOTIVATION Vehicular Networks V2V2R and R2V2V Communications Scheduling First come first served Earliest deadline first Linear programming Motivation UPLINK AND DOWNLINK UTILIZATIONS Assumptions Uplink Utilization Downlink Utilization SIMULATIONS AND RESULTS Simulation Environment Uplink Simulation Downlink Simulation CONCLUSIONS AND FUTURE WORK Conclusions Future Work REFERENCES CURRICULUM VITAE xi xii ABBREVIATIONS ITS VANET RSU V2V V2R R2V V2V2R R2V2V EDF FCFS : Intelligent Transport Systems : Vehicular Ad-Hoc Network : Road-Side Unit, i.e. infrastructure : Vehicle to vehicle communication : Vehicle to Road-Side Unit : Road-Side Unit to Vehicle : Vehicle to vehicle to RSU communication : RSU to vehicle to vehicle communication : Earliest Deadline First : First Come First Served xiii xiv LIST OF FIGURES Page Figure 2.1 : IEEE 1609 protocol stack [1] Figure 3.1 : Message flow of the downlink model Figure 3.2 : A legal V2V communication between relay and receiver Figure 4.1 : Visualization of simulation environment Figure 4.2 : Uplink utilization results Figure 4.3 : Scheduling of scenario in Fig. 4.2(d) where the proposed model achieved %98.3 utilization Figure 4.4 : Downlink utilization results Figure 4.5 : Scheduling of scenario in Fig. 4.4(d) where the proposed model achieved %93.4 utilization xv xvi STORE AND FORWARD SCHEDULING IN CLUSTERED VEHICULAR NETWORKS SUMMARY Vehicular networks are highly mobile networks which comprise of vehicles and stationary units that are equipped with short range wireless communication devices. Vehicular networks are promising research area to increase driver safety, control vehicular traffic better, enable wider use of infotainment applications and beyond. Vehicular networks unique nature separates it from other kind of wireless networks with several new challenging problems. In vehicular networks, multi-hop communications with stationary infrastructure (i.e. road-side unit) is a studied problem. However, utilization of this type of communication is not considered lately. We designed models that can utilize communications between vehicles and road-side units avoiding expensive tools such as cellular communications or directional antennas. This thesis considers scheduling of vehicle to vehicle to roadside unit (V2V2R) communications in a clustered vehicular ad-hoc network (VANET) in order to improve communication channel utilization. Two novel communication models are proposed to increase amount of data that can be transferred between cluster of vehicles and the roadside unit, where each vehicle has its own data to be transferred. In addition to direct V2R communications, V2V2R communications are effectively employed for this purpose. A store and forward mechanism is used for scheduling V2V2R communications. Proposed model takes advantage of limited and predictable mobility patterns of the vehicles. It is assumed vehicles constitute a cluster which is a group of vehicles that move towards same direction with slightly similar velocity. Under the control of the cluster head, vehicles which would have idle time while staying in the range of RSU, volunteers to relay other vehicles data if necessary. V2V2R resource sharing problem is modelled as a linear programming problem without compromising scalability. Simulations proved that the proposed model achieves significantly higher utilization compared to earliest deadline based and first come first served based scheduling algorithms. Presented simulations shows that proposed models are able to almost fully utilizing communication channel. xvii xviii KÜMELENMİŞ ARAÇLAR ARASI AĞLARDA SAKLA VE İLET TİPİ İLETİŞİMLERİN ZAMANLANMASI ÖZET Araçlar arası ağlar yüksek derecede hareketliliğe sahip düğümlerden oluşan bir ağ tipidir. Bu ağlar, araçlar ve yol yanı birimlerinden oluşurlar. İlgili ağdaki düğümlerin herbirinde kısa mesafeler arası kablosuz iletişim kurmayı sağlayan araçlar mevcuttur. Bu ağlarda kullanılan araçlar kısa mesafeli kapsama alanı sağladıklarından, ağ topolojisi sık sık parçalanır. Yani, herhangi bir anda ağdaki bir araç hiçbir araçla iletişim kuramayacak bir durumda kalabilir. Araçlar arası ağlar genel anlamda karayolu trafiğindeki araçlar ve ek olarak özel yeteneklere sahip yol yanı birimlerinden oluşurlar. Araçlar arası ağlar; sürücü güvenliği, araç trafiği kontrolü, genel amaçlı uygulama kullanımı gibi amaçlar güden geniş bir araştırma alanıdır. Bu işlerin gerçekleştirildiği yol tipinin karakteristiğine göre haberleşme yordamları da birbirlerinden ayrılırlar. Örneğin, şehir içi ulaşımda araç sayısı fazla, araç hızı azken, otoyollarda araç sayısı az araç hızı fazla, kırsal kesimdeki yollarda da araç sayısı az araç hızı da azdır. Bu çeşitlilikler topolojinin yapısında ve değişkenliğinde kayda değer seviyede farklılıklara yol açtığından ötürü, literatürde tasarımı yapılan algoritmalar da genellikle tek bir yol tipinde çalışmak üzere üretilirler. Araçlar arası ağların özgün karakteristiği, bu ağları diğer türden kablosuz ağlardan ayırmaktadır. Bu yüzden, bu alana özgü bir çok problem doğmaktadır. Bu problemlerin büyük bir kısmı araçların hareket örüntülerinin içinde bulunulan ortama göre ciddi şekilde değişmesinden ve bu örüntülerin öngörülmesinin zorluğundan kaynaklanmaktadır. Bir çok yönlendirme algoritması hem şehir içi yollarda hem de şehir dışı yollarda aynı anda yüksek başarım sağlayamamaktadır. Araçlar arası ağların bu yapısından ötürü, çok sekmeli iletişimler kurabilmek oldukça zor bir problemdir. Sıkça başvurulan yöntemlerin çoğu beklenen başarımı gösterememektedir. Çünkü, çok sekmeli iletişimlerde, araçların hareketliliği yüksek olduğundan iletişim sıklıkla kopmakta, hatta topolojide parçalanmalar olabilmektedir. Çok sekmeli iletişimlerde, iletişim kanalının kapasitesinin yüksek oranda kullanımını sağlamayı amaçlayan yöntemler henüz yaygın değildir. Tez kapsamında tasarlanan modellerde iletişim kanalının yüksek oranda kullanımının sağlanması amaçlandı. Elde edilen başarılı sonuçlara ulaşırken, literatürdeki çoğu yöntemin aksine hücresel ağları, aynı anda ortamda bulunabilen iletişimleri, yönlendirilebilir antenleri ve buna benzer maliyet getiren cihazların kullanılmasından kaçınıldı. Bu tezde, kümelenmiş araçlar arası ağlarda araç - araç - ünite tipi iletişimlerin zamanlamasını yapabilen yöntemler tasarladık. Amacımız, iletişim kanalının yüksek oranda kullanımını sağlamaktır. Bu amaçla, araç kümesinden üniteye yükleme xix ve üniteden araç kümesine indirme olmak üzere iki zamanlama modeli tasarladık. Tasarladığımız yöntemlerde her bir aracın kendine has veri alış-verişleri olduğunu, aynı verinin alış-verişinin birden fazla araç için yapılmadığı durumu ele aldık. Araç - ünite tipi iletişimlere ek olarak gerçekleşmesini sağladığımız araç - araç - ünite tipi iletişimler sayesinde iletişim kanalının etkin kullanımını sağladık. Araç - araç - ünite tipi iletişimlerin başarıyla gerçekleşmesini sağlamak için sakla ve ilet tipi iletişim kavramından yararlandık. Sakla ve ilet tipi iletişimlerde, ara bağlantı düğümü alıcı ve vericiyle o an için iletişim kuramıyor olsa bile, elindeki mesajı ilgili hedefe gönderene kadar saklar. Bu yöntem gecikmeye toleranslı ağlarda sıkça kullanılsa da, araçlar arası ağlarda kullanılabilmesi için ek işler gerekir. Bu tez içerisinde, araçların sınırlı ve öngörülebilir bir hareketlilik örüntüsüne sahip olmasından faydalanarak sakla ve ilet tipi iletişimleri kullandık. Tezdeki yöntemler, araçların bir küme halinde ilerlediği durum için tasarlanmışlardır. Aynı kümedeki araçlar, aynı yönde hareket eden ve birbirine yakın hızlara sahip olan araçlardır. Her bir kümenin bir küme lideri vardır. Küme lideri, küme içi organizasyonu sağlayan sıradan bir araçtır. Küme liderinin kontrolü altında, ünitenin kapsama alanı içerisindeyken boş zamana sahip olan araçlar, veri transferini tamamlayamayacak durumda olan araçlara gönüllü olarak yardım ederler. Bahsedilen yöntemde araç - ünite tipi iletişimlere ek olarak kullanılacak olan araç - araç - ünite tipi iletişimler, doğrusal programlama yönteminin yardımıyla belirlenir. Hangi aracın hangi araç için ne kadar süreliğine ve hangi andan itibaren gönüllü olacağı probleminin doğrusal programlama problemine dönüşümü, tezin içeriğini oluşturmaktadır. Tasarlanan yöntem küme tabanlı olduğu için, ölçeklenebilirliği yüksektir. Tezde tasarımı yapılan yöntemde, küme lideri araçların ivmelerini, hızlarını ve pozisyonlarını anlık olarak bilmektedir. Bu bilginin elde edilmesi için bir çok yöntem kullanılabilir. Küme lideri, henüz yol yanı ünitesinin kapsama alanına girmeden önce, araçların yol yanı ünitesine yükleyeceği veri miktarını bilmektedir. Küme lideri, kümedeki araçların indireceği veri miktarını ise, herhangi bir küme üyesi yol yanı ünitesinin kapsama alanına girdiğinde öğrenir. Bu bilgi sayesinde küme lideri; her bir aracın yol yanı ünitesinin kapsama alanına giriş ve çıkış anlarını, her bir aracın kümedeki bir diğer aracın kapsama alanına ne zaman girip çıktığını bilir. Özetle, küme lideri topolojideki her bir değişikliğin ne zaman ve nerede yaşanacağını bilir. Küme lideri topolojideki her bir değişikliğin bilgisini elde etmesi sayesinde, topolojinin değişmediği en küçük zaman aralıklarını tespit eder. Bu zaman aralıklarında da kümedeki araçlardan hangilerinin birbirleriyle görüşebildiklerini tespit eder. Küme lideri halihazırda hangi aracın ne kadar bir veri transferi yapacağını ve bu transferin hangi yönde gerçekleşeceğini de bilmektedir. Bu sayede, doğrusal programlama yöntemlerini kullanarak; topolojinin değişmediği her bir anda hangi araç ikilisine iletişim verileceği veya hangi aracın yol yanı ünitesi ile iletişime geçebileceği tespit edilir. Topolojinin değişmediği en küçük zaman aralığı birden çok iletişim tarafından zaman paylaşımlı olarak kullanılabilir. Bu durumdan kaynaklı olarak, modelin son adımında topolojinin değişmediği en küçük zaman aralığının içinde bir zamanlama daha yapılır. Tüm bu işlemlerin ardından hangi aracın hangi anda hangi araçla(veya yol yanı ünitesi ile) iletişime geçeceği bilgisi elde edilir. Küme lideri, tasarlanan modeli çalıştırarak elde ettiği sonucu kümedeki tüm araçlara ve yol xx yanı ünitesine dağıtır. Yol yanı ünitesi ve kümenin diğer elemanları küme liderinin direktiflerine uygun hareket ederek veri transferlerini gerçekleştirirler. Tasarlanan yordam, Java dilinde geliştirilen benzetim yazılımları yardımıyla test edilmiştir. Elde edilen sonuçlara göre; tasarlanan algoritma ilk biten öncelikli ve ilk giren öncelikli şeklinde çalışan zamanlama algoritmalarından açıkça üstün sonuçlar üretmektedir. Ek olarak, tasarlanan yöntem uç test durumları ile denenmiştir. Bu durumların hemen hepsinde diğer algoritmalardan çok daha iyi sonuçlar elde edilmiştir. Bunun yanında, gerçekçi senaryolarda elde edilen sonuçlar, tasarımın iletişim kanalını neredeyse tamamen kullanabildiğini göstermiştir. xxi xxii 1. INTRODUCTION Vehicular networks are comprise of vehicles and stationary units that are equipped with short range wireless communication devices. Vehicular networks are promising research area which is expected to increase driver safety, control vehicular traffic better, enable wider use of infotainment applications and beyond [2]. Nature of the vehicular networks diversifies itself from other kind of wireless networks, creating a whole new research area. 1.1 Definition of Problem Vehicular networks has unique characteristics when it compared to other kind of wireless ad-hoc networks. Mobility of the nodes in vehicular networks are significantly higher which causes frequent partitions on the network topology [3]. In a frequently partitioned network, multi-hop communications are not viable due to loss of existing communication links. Hence, utilization of communication channel can drastically decrease. However, since the vehicles mobility are limited with roads, pattern of their mobility is predictable. Estimating future topology changes based on predictable mobility, can lead a scheduling scheme for multi-hop communications. 1.2 Purpose of Thesis Our motivation is increasing utilization of communication channel by proposing an efficient and scalable scheduling model for vehicle to infrastructure (V2R) and vehicle to vehicle to infrastructure (V2V2R) communications. Proposed methods can be implemented without a need for accessing other mobile network services e.g. cellular networks or without a need for performance enhancing tools such as directional antennas or multiple antennas. In the proposed model, vehicles constitute clusters. Each cluster determines its scheduling for V2R and V2V2R respectively. Proposed methods are aimed to be scalable with aid of clusters. In order to maximize the utilization, designed model adapts and combines some well known optimization 1 techniques with a novel approach. complexity. All designed algorithms have polynomial time 1.3 Contributions of Thesis Contributions of the thesis are: Demonstrating that use of clusters achieve higher utilization ratio with a scalable fashion Demonstrating that without an efficient scheduling model, communication channel is utilized inefficiently. Designing an efficient scheduling model that is close to fully utilizing communication channel. Designing a two step scheduling model for uplink utilization of V2V2R and V2R, which comprises of a task scheduling algorithm and a linear programming problem. Experimentally observing the best known task scheduling algorithm for first step of uplink utilization model. Designing a scheduling model for downlink utilization of V2V2R and V2R which turns scheduling problem into a linear programming problem. Comparing proposed scheduling models with existent scheduling algorithms in different scenarios. 1.4 Structure of Thesis This thesis is organized as follows: Literature survey that mentions vehicular networks and current research on communication channel utilization, are given in the next chapter. Chapter 3 introduces proposed models for uplink and downlink utilization in clustered vehicular networks. Comparative simulation results of proposed models and existing algorithms are presented in Chapter 4. Finally, section 5 concludes the thesis and giving future works. 2 2. LITERATURE SURVEY AND MOTIVATION In this chapter, vehicular networks briefly summarized. Current status of the research that is close to our work is presented. Methods that are being used have briefly presented. 2.1 Vehicular Networks Vehicular ad hoc networks (VANET), has taken considerable attention recently due to emergence of Intelligent Transport Systems (ITS). ITS aims to enable use of a vast range of applications e.g. improved driver safety, infotainment applications and traffic efficiency [4]. IEEE 1609 [1] proposed a protocol stack to be used in vehicular environments(fig. 2.1). However, it has been pointed out that applications with different kind of requirements might need extensions to this stack [5]. In [6], authors analysed broadcasting in IEEE Authors pointed out that IEEE 1609 can cause severe packet loss due to collisions. ITS applications usually require stationary infrastructures near the roads that can communicate with vehicles [2]. Infrastructures are also addressed as roadside units (RSUs). The use of RSUs provides improved driver safety, better quality of service, helping to improve the performance of the network. It is unreliable to design VANET by introducing only ad-hoc communication features without a fixed infrastructure. In ITS, both V2V and V2R communications are enabled. Moreover, concurrent use of V2V and V2R communications are vital to improve performance of network and fulfilling requirements of ITS applications. Additionally, use of RSUs are vital to ensure security of the vehicular network, since there might be extensive range of attacks to network due its partitioned nature. RSUs are trustworthy nodes of the network for vehicular nodes [7]. In vehicular networks, placement of RSUs is a challenging problem. For highway and rural areas, some 3 Figure 2.1: IEEE 1609 protocol stack [1]. probabilistic straightforward approaches are available [8]. But in the urban areas, placement of RSUs still stays as an open problem due to highly diverse mobility patterns of the vehicles. Most of the applications explicitly assume that RSUs are deployed to cross-roadings and traffic lights in urban areas. Mobility patterns of the vehicles are required to be estimated to have an efficient communication and routing model. In the literature, mobility patterns are divided to parts as: macro mobility, which is interested in checkpoints of the vehicles and micro mobility, which considers rather short ranged models [9]. Macro mobility models are still far away from being stable which makes multi-hop routing quite chall
Related Search
Similar documents
View more...
We Need Your Support
Thank you for visiting our website and your interest in our free products and services. We are nonprofit website to share and download documents. To the running of this website, we need your help to support us.

Thanks to everyone for your continued support.

No, Thanks