Weighted Voting Game Based Relay Node Management In Vanets

thumbnail.default.placeholder
Tarih
2016 -12-16
Yazarlar
Biyar, Elham Dehghan
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
Geleneksel VANET (Araç Geçici Ağı) açılımında yol kenarı birimleri (RSU) ile kesintisiz ve güçlü bağlantı kurulumlarında ciddi problemler ortaya çıkmaktadır. Bilinen bir gerçek olarak bu sorun araçların yüksek hareketliliği ile tetiklenmesinden doğmaktadır. Bu sorunu gidermek için en uygun çözümün, röle görevi gören en optimum aracın seçilmesi ile mümkün olabilir. Bunun bir sonucu olarak bu çalışmada en uygun ve optimum röle aracının ağırlıklı oylama yöntemi kullanılarak algoritmik seçiminin yapılması ile ilgili öneri getirilmiştir. Oyun teorisi yaklaşımımızda röle aracı seçimleri çeşitli yardımlaşma koalisyonları ile gerçekleştirilmiştir. Belirtilmelidir ki, oyun teorisi interaktif karar verme gibi karmaşık durumlarda matematiksel analiz ve modelleme yapabilen uygulamalı matematik algorittması ile dizayn edilen mükemmel bir araçtır. Sunduğumuz ağırlıklı oylama yöntemi algoritması Banzhaf güç ölçüsünün kullanılarak paket dağıtımları esnasında, artan throughput lar ve azaltılan mesaj iletişim gecikmeleri gibi adil ve optimal sonuçlar ortaya çıkmasını sağlar. Performans değerlendirme sonuçları, kendisini düşünen bağımsız düğümler içeren beraber çalışmayan metodlarla karşılaştırıldığında ağırlıklı oylama oyun teorimiz throughput larda yaklaşık 24\% artış ve mesaj iletim gecikmelerinde 18\% azalış göstermektedir. Bu algoritma farklı hız menzillerinde tekrarlanmaktadır. Genel bir giriş ve tanımlama olarak röle düğüm yönetimi 1.kısmında sunulmaktadır. VANET (Araç Geçiçi Ağı) bilgi ve iletişimdeki son ilerlemelerle birlikte sürücülerin rahat ve verimli seyahatleri için yol boyunca gerekli bilgileri sağlayarak sürücülere yardımcı olan önemli bir konsept olmuştur. Araçların daimi hareketi topolojinin dinamik olarak değişimine neden olduğu için dinamik olarak yol kenarı iletişim noktalarıyla sürekli ve güçlü bir bağlantının kurulması ve sürdürülebilirliği için zordur. Bu problemlerin üstesinden gelmek ve verimli optimal bir bağlantıyı yönetmek için bazı araçları röle olarak bağlantıyı güçlendirmek ve takviye etmek amaçlı kullanılması gerekmektedir. Tatmin edici bir metod sağlamak bu seçim için gerekmektedir. Araçları yollarda sürekli bir şekilde hareket yapmalari ve topoloji değişimleri nedeniyle zor bir durumdur. Literatür araştırması kısmında farklı röle bağı seçim metodları değerlendirilmiştir. Contribution kısmında önerilen çalışmanın çerçevesi ve algoritması ile ilgili özet bir bilgilendirme yapılmıştır. 2.Bölümde, Araç geçici ağı hakkında ayrıntılı açıklama yapılmıştır. Bu bölümde VANET'in ana kullanım amacı ve ayrıca sistem bileşenleri anlatılmaktadır. Ayrıca, VANET uygulaması ile ilgili özet açıklamada yapılmıştır. VANET uygulaması, güvenlikten trafik verimliliğine ve eğlence uygulamalarına kadar çeşitlilik içerir. Ek olarak, VANET karakteristiği zorluk tanımlamalarının önemli bir faktörü olarak bahsedilmiştir. İletişim modellerinin farklı metdoları VANET'in ayrılmaz kısımları olarak gösterilmiştir. Çeşitli yönlendirme protokollerinde bu bölüm içerisinde bahsedilmiştir. Oyun teorisi problemli olan bazı durumların çözümlenmesi için mükemmel bir araçtır. Bu aracın matematiksel analiz ve modelleme yapabilen uygulamalı matematik algoritması ile dizayn edilir. 3.Bölümde oyun teorisinin kullanım nedeni bu çalışma içinde bahsedilmiştir. Oyunların genel sınıflandırılması gösterilmiştir. Oylama oyunu katılımcıların en makul ve uygun olan adayın seçiminde ortak bir sonuç belirlemesine izin vermektedir. Oylama oyununun çeşitleride yine bu bölümde anlatılmaktadır. Bu çeşitlerden bir tanesi ağırlıklı oylama yöntemi olarak adlandırılır.Her oyuncunun ağırlığı o oyuncunun sahip olduğu gücün miktarını temsil etmez. Adil sonuçlara ulaşmak için, detaylı bir şekilde gösterilmiş ve açıklanmış bazı çeşitli güç endeks ölçüleri vardır. Banzhaf güç ölçüsü bu güç indekslerinden biridir. Bu indeks, oylama sonuçlarının oy verenler arasında eşit dağıtılmadığı bir oy sonucunun değişim oranını ifade eder. Oyunlar kendi aralarında koalisyona girme ya da koalisyondan çıkmak haklarına sahiptir. Bu nedenle, araçların hareketli olması dolayısıyla Banzhaf güç ölçüsü kullanılmaktadır. Eğer bir oyuncu stratejisini değiştirir ve diğerleri sabit kaldığında, stratejisini değiştiren oyuncu strateji değişiminden çok fazla bir fayda kazanç elde edemeyebilir. Bu Nash dengesi olarak adlandırılı. Nash dengesinin kısa bir özeti her oyunun temeli olarak verilmiştir. Bölüm 4 te Ağ mimarisi ve sistem modeli anlatılmış ve detaylandırılmıştır. Ağ özeti gösterilmiştir. Anchor ve Relay araç ifadeleri tanıtılmıştır. Dahası, çalışmamızda sunduğumuz algoritmanın bir açıklaması yapılmıştır. VANET elementleri arasında röle düğümü seçimi ve oyun teorisinin oluşumunda bir haritalama yapılmıştır. Ağ topoloji örnekleri ve sunulan sistem model şemaları gösterilmiştir. Önerdiğimiz sistem modelimiz tarama, bağlanma girişimi, koalisyon şekillendirmesi, oylama, optimal röle seçimi, paket dağıtımını içerir. Pay-off fonksiyonu hem anchor hem röle araçları için hesaplanmıştır. Bu hesaplama röle aracı ile RSU arasındaki linkin transmisyon olasılığına dayanarak ve ayrıca kullanılabilir bant genişliğine,bant genişliği özelliğine ve hizmetin bedeline göre hesaplanmıştır. 5.Bölümde deneysel sonuçlar ve performans değerlendirmesi sağlanmıştır. Sunulan kooperatif ağırlıklı oy oyun algoritmasının performans değerlendirilmiş ve Matlab kullanılarak kooperatif olmayan yaklaşım karşılaştırılmıştır. 2 farklı hız menziline sahip araçlar bu algoritma kullanılarak incelenmiştir. Performans değerlendirme sonuçları göstermektedir ki, bizim sunduğumuz algoritma kooperatif olmayan metodla karşılaştırıldığında throughput sonuçlarındaki artışlar ve mesaj dağıtımları hakkkında ki gecikme azaltılmıştır. Ek olarak, gerçekçi VANET simülasyonu dikkate alınmış. Bu simülasyon için gerçek dünya verileri kullanımı gerekmektedir. Bu bilgiler haritalar, istatistiksel veriler, trafik sayaçları, gerçek izleri, GPS tabanlı veri elde edilebilir. Bu bilgiler trafik jeneratörleri kullanılarak işlenir. Gerçekçi trafik jeneratörler VANET simülasyonları kalitesini artırmak için önemlidir. Basit hareketlilik modellerinin kullanımı iyimser iletişim için yol açar. Sonunda, sonuç bölümü tüm adımları ve yöntemleri açıklamaktadır. Bu bölümde tüm kullanılan yöntemlerin kısa bir açıklaması verilmektedir.
In traditional Vehicular Ad Hoc Networks (VANETs) deployments, permanent and robust connection establishment to road side units (RSU) has arisen as a crucial problem. Here it is a known fact that, this challenge has been triggered by high mobility pattern of vehicles. To handle this problem, optimal relay vehicle selection can be seen as an efficient solution. To this end, in this work, we propose a novel optimal and fair relay vehicle selection algorithm based on weighted voting game. In our game theoretic approach, relay vehicle selections have been performed by various cooperative coalitions. Note that game theory is a perfect tool while designing such an algorithm as it is a formal applied mathematical tool to analyze and model complicated situations of interactive decision making. Our proposed weighted voting game algorithm can achieve fair and optimal results as well as increasing throughput and decreasing message transmission delay during packet dissemination as a result of using Banzhaf power measure. Performance evaluation results showed that compared to non-cooperative methods, throughput increases approximately by 24\% and message dissemination delay decreases by 18\%. This algorithm is repeated for various speed ranges. A general introduction and explanation of relay node management was presented in chapter 1. With recent advances in Information and communications technology VANET has become an important concept in order to provide an efficient and convenient road trips for drivers by obtaining required information along the road. Due to the mobile nature of vehicles that results in dynamic topological changes, establishing permanent and robust connection with road side units for maintaining connectivity has arisen as a challenging issue. To overcome these problems and for efficient management of optimal connectivity, it is essential to use some of the vehicles as a relay for compensation and reinforcement of connection. Providing a satisfying method for this selection is required and it is a challenging issue due to dynamic environment of roads. In literature survey part different methods of relay node selection is considered. In contribution section a brief introduction of proposed framework and algorithm has been given. In chapter 2, a detailed description of vehicular ad hoc networks is given. In this chapter the main purpose of using (VANET), and also their system components are discussed. Furthermore, a brief explanation of VANETs application is mentioned. The application of VANET varies from safety applications to traffic efficiency and infotainment applications. In addition, characteristic of VANETs which is an important factor of challenge recognition is considered. Different methods of communication pattern that is an inseparable part of every VANET is illustrated. Various type of routing protocols are also discussed. Game theory is a perfect tool while resolving some problematic situations. It is a formal applied mathematical tool to analyze and model complicated situations of interactive decision making. In chapter 3, the reason of game theory usage in this work is discussed. A general classification of games is shown. Voting game permits participants to come up with a common decision to choose the most eligible and suitable candidate. This method is used in this work for relay node selection and categorized. One type of voting game is called weighted voting game. Each player’s weight doesn’t represent the amount of power that player holds. For achieving fair results, there exist couple of power indices measures that are illustrated and explained in details. Banzhaf power measure is one of power indexes. It is defined by the probability of changing an outcome of a vote where voting rights are not equally divided among the voters. Players are free to enter and leave the coalitions. Therefore, because of mobile nature of vehicles we use this power index method. If one of the players changes its strategy and other players remain constant, the specific player can’t acquire more benefits from that change in its strategy, this is called Nash equilibrium point. A brief definition of Nash Equilibrium that is the fundamental of each game is also given. Network architecture and system model is discussed and detailed in Chapter 4. The abstract network is shown. Anchor and Relay vehicle phrases are introduced. Moreover, an explanation of our proposed algorithm is given. A mapping between VANET elements for relay node selection and game theory is happened. Network topology examples and also proposed system model schema are shown. System model is consist of scanning, connection attempt, forming coalition, voting, optimal relay selection, and packet dissemination. Pay-off functions for both anchor and relay vehicles are calculated regarding to transmission probability of links between relay vehicle and RSU, available bandwidth of RSU, bandwidth characteristic of vehicle, and the cost of the service. Chapter 5, provided experimental results and performance evaluation. The performance of proposed cooperative weighted voting game algorithm is evaluated and compared with non-cooperative approach by using Matlab. Vehicles with 2 different speed ranges are examined by using this algorithm. Performance evaluation results showed that compared to the non-cooperative method increment in throughput results and decrement in message dissemination delay are achieved. In addition, a Realistic VANET Simulations is considered. A real world data is needed for realistic VANET simulations. Accumulating realistic data is required for this simulation. These information is processed using traffic generators. Realistic traffic generators are important to enhance the quality of VANET simulations. Usage of simple mobility models leads to optimistic communications. At the end, the conclusion part explains all the steps and methods. In this section a brief explanation of all the used methods are given.
Açıklama
Tez (Yüksek Lisans) -- İstanbul Teknik Üniversitesi, Fen Bilimleri Enstitüsü, 2016
Thesis (M.Sc.) -- İstanbul Technical University, Institute of Science and Technology, 2016
Anahtar kelimeler
Oyun Teorisi, Araç Geçici Ağlar, Ağırlıklı Oylama Yöntemi, Banzhaf Güç Ölçüsü, Adil Röle, Game Theory, Pay-off Function, Vanets, Weighted Voting Game, Banzhaf Power Measure, Fair Relay
Alıntı