GEOAKOM: A smart geocasting protocol for vehicular networks
GEOAKOM: Araç ağları için konuma göre akıllı yönlendirme yöntemi
- Tez No: 664930
- Danışmanlar: PROF. DR. SEMA FATMA OKTUĞ
- Tez Türü: Yüksek Lisans
- Konular: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol, Computer Engineering and Computer Science and Control
- Anahtar Kelimeler: Belirtilmemiş.
- Yıl: 2021
- Dil: İngilizce
- Üniversite: İstanbul Teknik Üniversitesi
- Enstitü: Lisansüstü Eğitim Enstitüsü
- Ana Bilim Dalı: Bilgisayar Mühendisliği Ana Bilim Dalı
- Bilim Dalı: Bilgisayar Mühendisliği Bilim Dalı
- Sayfa Sayısı: 73
Özet
Bilgi ve haberleşme teknolojilerinin gelişmesi ile birlikte, araçlar haberleşme yeteneklerine sahip olmaya başlamışlardır. Araç haberleşmesinin temel amacı güvenli ve rahat sürüş olanağı sunarken, aynı zamanda kazaları engellemek, yol kullanım verimliliğini artırmak ve doğa dostu ulaşım olanağı sunmaktır. Araç ad-hoc ağları haberleşme modeli, araçlara yakınlarında bulunan diğer araçlarla, ağ elemanlarıyla, yayalarla ve alt yapı üniteleriyle haberleşme imkanı sunmaktadır. Bu imkanları sunabilmek için araç ağları düşük gecikme, yüksek güvenilirlik ve uygulama için gerekli olan veri hızı gibi gereksinimlere ihtiyaç duymaktadır. Özel Kısa Menzilli İletişim (IEEE 802.11p standartına dayanır), LTE teknolojisine dayanan araç haberleşmesi (cmWave), mmWave, Görünür Işık iletişimi vb. teknolojiler araç ağlarının ihtiyaç duyduğu bu teknik özellikleri karşılayabilmek için geliştirilmiştir. Araç ağı uygulamaları, güvenlik uygulamaları ve güvenlik dışı uygulamalar olarak sınıflandırılmıştır. Güvenlik uygulamaları, trafik kazalarını önlemek ve aktif yol güvenliği sağlamak için geliştirilmiştir. Güvenlik uygulamarı için araçlar arasında güvenlik bilgileri aktarılması gerekmektedir. Araç durum uyarısı, araç tipi uyarısı, çarpışma uyarısı, şerit değiştirme yardımı, sollama uyarısı, acil durum uygulamaları güvenlik uygulamaları için örnek kullanım durumlarıdır. Güvenlik dışı uygulamalar, trafik deneyiminin verimliliğini artırmayı, trafik akışını yönetmeyi, trafik sıkışıklığını azaltmayı ve bilgi-eğlence hizmetleri sağlamayı amaçlamaktadır. Hız yönetimi ve ortaklaşa gezinme uygulamaları verimli trafik akışı, koordinasyon ve trafik yönetimi sağlamaktadır. Bilgi-eğlence uygulamaları ise bildirimler, medya indirme ve küresel internet hizmetleri gibi bilgi ve eğlence hizmetleri sağlamaktadır. Mesaj yönlendirme protokolleri, kaynak ve hedef araçlar arasındaki yönlendirme yolunu tanımlar ve mesaj yönlendirme kararını verir. Yönlendirme protokolleri, iletim stratejilerine göre tek noktaya yönlendirme, çok noktaya yönlendirme, küme tabanlı yönlendirme, geniş yayın yönlendirme ve konuma dayalı yönlendirme olarak ayrılmaktadır. Konuma dayalı yönlendirme pozisyona bağlı olarak yapılan bir mesaj yönlendirme şeklidir. Konuma dayalı yönlendirme ile mesajlar belirli bir coğrafi konumdan başka bir coğrafi konuma yönlendirilirler. Araçların sahip olduğu Küresel Konumlandırma Sistemi (GPS) sayesinde, konuma dayalı yönlendirme modeli araç ağları için önemli bir mesaj yönlendirme çözümüdür. Araç ağları yüksek mobiliteye sahip oldukları ve araçların şehir içindeki dağılımları dinamik olarak hızlı bir şekilde değiştiği için, araçlar için konuma dayalı yönlendirme algoritmaları geliştirmek zordur. Literatürede bulunan konuma dayalı yönlendirme yöntemlerinin çoğu büyük ölçekli kentsel ağların yüksek mobilite ve dinamik değişen yapısı için gerekli isterleri karşılayamamaktadırlar. Araçların kentsel hareketlilikleri kullanılarak bazı anlamlı modeller yaratılabilmektedir. Eğer iki araç belirli bir zamanda belirli bir konumda karşılaşıyorsa, bu iki araç sonraki günlerde tekrar karşılaşabilir. Ayrıca otobüs, tramvay gibi toplu taşıma araçları ve otomobil, taksi gibi özel taşıma araçları bazı özel hareketlilik modeline sahiptirler. Örneğin, otobüsler genellikle aynı rota üzerinde hareket ederler ve duraklardan geçiş saatleri belirlidir. Taksiler genellikle taksi duraklarına yakın yerlerde hareket ederler ve taksi sürücülerinin tercih ettikleri belirli rotalar vardır. Bu bilgilere göre, araçlardan toplanan GPS verileri kullanılarak anlamlı veri kümeleri oluşturulabilir ve bu veri kümeleri ile akıllı mesaj yönlendirme modelleri geliştirilebilir. Bu tez çalışmasında, büyük ölçekli kentsel ağlar için akıllı yönlendirme modeli olan GeoAKOM algoritması sunulmuştur. Türkiye'nin Bursa şehrindeki taksilerin GPS verileri toplanmış, hareketlilik modelleri analiz edilmiş ve bu model mesaj yönlendirme kararı verilirken kullanılmıştır. Hareketlilik modeli, mikro ölçekte ve makro ölçekte olmak üzere iki yönden incelenmiştir. Makro ölçekte, kentin genel hareketlilik modeli analiz edilir. Mikro ölçekte ise her bir aracın hareketlilik modeli incelenir ve bu modeller mesaj yönlendirme kararı verilirken kullanılır. GPS kayıtlarını analiz etmek için, her aracın her GPS konumu bir hücre ile temsil edilir. Makro ölçek analizi için, hücreler k-ortalama kümeleme algoritması kullanılarak kümelenir. Bir mesaj yaratıldığı zaman, mesajın yaratıldığı küme ile mesajın ulaşması istenilen hedef küme arasındaki en kısa yol Dijkstra'nin en kısa yol algoritması kullanılarak hesaplanır. Bu hesaplanan en kısa yol, mesaj başlığına kaydedilir. İki araç karşılaştığı zaman, eğer araçların rotaları biliniyorsa, araçların mesajin hedef kümesine gitme olasılığı hesaplanır. Eğer araçların rotaları bilinmiyorsa, aracın gideceği bir sonraki küme tahmin modeli kullanılarak tahmin edilir. Bütün araçların GPS kayıtları kullanılarak, Tüm K-Dereceli Markov Modeli yöntemi ile tahmin modeli eğitilir. Bu eğitilmis model her araca kaydedilir ve bir sonraki kümeyi tahmin etmede kullanılır. Eğer karşılaşılan aracın mesajın hedef kümesine gitme olasılığı daha yüksekse, mesaj karşılaşılan araca gönderilir. Eğer karşılaşılan aracın mesajın hedef kümesine gitme olasılığı daha düşükse, aracın iletişim geçmişi bilgisi mesaj yönlendirme kararı için kullanılır. Sunulan GeoAKOM algoritmasının performansı, ONE simülasyon ortamı kullanılarak izlenmiştir. Ortalama gecikme süresi, mesaj iletim oranı ve ortalama hop sayısı, k-ortalama kümeleme algoritmasının farklı k değerleri (k=20, k=30 ve k=40) için incelenmiştir. GeoAKOM algoritmasının performansı, GeoMobCon algoritması, İlk Temas yönlendirme algoritması ve Yön Odaklı yönlendirme algoritması ile karşılaştırılmıştır. Tüm K-Dereceli Markov Modeli'nin performansı farklı sekans tahmin algoritmalarından olan Geçişe Yönelik Döngüsel Olmayan Grafik ve Kompakt Tahmin Ağacı+ algoritmaları ile karşılaştırılmıştır. Karşılaştırmalara ve performans değerlendirmelerine göre, bütün tahmin algoritmaları çok yakın başarı oranlarına sahip olduğu için ortalama gecikme süresi, mesaj iletim oranı ve ortalama hop sayısı için benzer değerler sunmaktadır. Tüm K-Dereceli Markov Modeli'nin tahmin etme süresi diğer algoritmalara göre daha düşüktür. Bu nedenle yönlendirme algoritması tasarlanırken, Tüm K-Dereceli Markov Modeli tahmin algoritması olarak seçilmiştir. GeoMobCon algoritmasında, her araç kendine ait mikro ölçekli hareketlilik modeli oluşturmak zorundadır ve bu model koşullu olasılıklar kümesinden oluşmaktadır. Her araç kendi mikro ölçekli hareketlilik modelini, bir kümeden başka bir kümeye hareket ettiği zaman güncellemek zorundadır. Bu mikro ölcekli hareketlilik modeli, rotası belirli olmayan araçlar icin mesaj yönlendirme kararı verilirken kullanılmaktadır. GeoAKOM algoritmasında ise, bütün araçların GPS verileri kullanılarak tahmin modeli bir kere eğitilir ve bu eğitilmiş tahmin modeli her araca yüklenir. Rotası bilinmeyen araçlar için, mesaj yönlendirme kararı verilirken araçlara yüklenen tahmin modeli kullanılarak bir sonraki gidilecek küme tahmin edilir. Bu nedenle, GeoAKOM algoritması sayesinde araçlar kendi mikro ölçekli hareketlilik modelini oluşturmak ve her yeni kümeye girildiği zaman bu modeli güncellemek zorunda değillerdir. Simülasyon sonuçları göstermektedir ki, GeoAKOM rotaları belli olmayan ve geçmiş GPS bilgisi bulunmayan araçlar için de başarılı ve basit bir mesaj yönlendirme çözümü sunmaktadır. İncelenen simülasyon sonuçlarına gore, GeoMobCon ve GeoAKOM algoritmaları İlk Temas yönlendirme algoritması ve Yön odaklı yönlendirme algoritmasına gore mesaj iletim oranı ve ortalama hop sayısı için daha iyi performans göstermektedir.
Özet (Çeviri)
With the evolution of information and communication technologies, vehicles are able to have communication capabilities. The main goal of vehicular communication is to provide safe and comfortable driving, efficient use of roads and nature friendly transportation. Vehicular communication is a must for autonomous driving. Vehicular Ad Hoc Networks (VANETs) provide communication ability to vehicles with nearby vehicles, network elements, pedestrians and infrastructure units. In order to provide such a communication ability, VANETs need some technical requirements such as low latency, high reliability, enough (depending on the job/aplication) data rate. Several vehicular network technologies, such as Dedicated Short Range Communication (based on IEEE 802.11p standard), LTE based Vehicle to Everything communication (cmWave), mmWave, Visible Light Communication etc., are developed to meet the technical requirements of VANETs. Geocast routing is a position based routing approach which transfers messages from one geographical area to another geographical area. Thanks to vehicles having global positioning system (GPS), geocast routing is one of the promising routing models for VANETs. Because of the highly mobile and dynamic structure of VANETs, developing a geocast routing technique is very challenging. In the literature, several geocast routing protocols are proposed. Some well known geocast routing protocols do not meet the requirements of highly mobile, rapidly changing network structure of large urban networks. Researches show that, in the urban mobility, some significant patterns for vehicles can be observed. It is observed that if two vehicles encounter with each other at a certain time, they are likely to encounter again in the following days. Also, public transportation vehicles (buses,trams, etc.) and private transportation vehicles (taxis, automobiles, etc.) have specific mobility models. For example, buses follow the same path every day and taxis mostly serve in a specific area around a cabstand point. Based on this information, GPS data which are collected from these vehicles can be used as a valuable dataset to generate smart message routing techniques. In this thesis study, a smart geocast routing technique GeoAKOM is proposed for large scale urban networks. Based on the GPS data of the taxis in Bursa, Turkey, a database is generated. The mobility patterns of taxis are examined and these patterns are used to make geocast routing decisions. In order to achieve this, mobility pattern of the city is analyzed in two levels: 1) macroscopic level, and 2) microscopic level. In the macroscopic level, city's overall mobility pattern is analyzed. In the microscopic level, each vehicle's mobility pattern is analyzed along with macroscopic pattern of the city to make a routing decision. When analyzing GPS records, each GPS location of a vehicle is represented by a cell. For the macroscopic pattern analysis, cells are grouped into clusters by using k-means clustering algorithm. When a message is created, shortest path from message source to destination cluster is calculated with the Dijkstra's shortest path algorithm. This calculated shortest path is embedded into the message header. When two vehicles encounter each other, if the route of the vehicle is known, the likelihood of the vehicle reaching to the message destination is calculated. If the route of the vehicle is unknown, a model is used to predict the next cluster of the vehicle. By using the GPS records of all vehicles, a prediction model is trained using All K-Order Markov Model (AKOM) algorithm. This trained model is embedded to each vehicle and it is used for the next cluster prediction. If the mobility based likelihood value of the encountered vehicle is bigger than that of the message carrier vehicle, the message is forwarded to the encountered vehicle. Otherwise, contact-history information is used for routing decision. The performance of GeoAKOM is evaluated under several scenarios using the ONE simulator. Average delay, message delivery ratio and average hop count values are analyzed for different k-means clustering parameters, i.e. k=20, k=30 and k=40. The performance of GeoAKOM is compared with the GeoMobCon algorithm, the First Contact routing algorithm and the Direction-oriented routing algorithm. Also the performance of various other prediction algorithms such as Transition Directed Acyclic Graph (TDAG) , Compact Prediction Tree+ (CPT+) is presented. In GeoMobCon, every vehicle needs to maintain its own individual microscopic mobility pattern which consists of a set of conditional probabilities. Hence, each vehicle needs to update its individual microscopic mobility pattern when it enters to a cluster. This microscopic mobility pattern is used to make message routing decision for the vehicles with unknown routes. In GeoAKOM, the prediction model is trained once with all vehicles' past GPS data and this prediction model is loaded to every vehicle. For vehicles with unknown route, the next cluster is predicted by using this prediction model. Therefore, vehicles do not need to maintain individual microscopic mobility patterns. Results show that GeoAKOM gives promising message routing results for the vehicles with unknown routes and for the vehicles which have no GPS history. Simulation results also show that GeoMobCon and GeoAKOM perform better than the First Contact routing and the Direction-oriented routing in terms of message delivery ratio and average hop count.