Pazarlık oyununa dayalı verimli fırsatçı ağ yönlendirme algoritması
Fırsatçı bir ağ, kaynak düğüm ile hedef düğüm arasında tam bir yol gerektirmeyen bir ağdır. Bir "depolama-ileri" yönlendirme modu benimser ve iletişim gecikmesi ve bölünebilir ağ elde etmek için düğüm hareketliliğinin getirdiği karşılaşma fırsatlarını kullanır. . Uygulamada, düğümün sınırlı kaynakları nedeniyle, kendi kaynaklarını korumak için düğüm bencil davranışlar gösterecektir. Fırsatçı ağlardaki düğümlerin bencilliği iki kategoriye ayrılabilir: cezaya dayalı ve ödül temelli.
Ceza mekanizmasına dayalı yönlendirme algoritması, esas olarak TFT stratejisine dayalı yönlendirme algoritmasına odaklanır. TFT stratejisi, yani oyunun başlangıcında, her bir düğüm oyunu oynamak için ortak bir yönlendirme stratejisi kullanır ve ardından mevcut düğüm, son oyun sırasında diğer düğüm tarafından benimsenen stratejiyi benimser.
Ödül mekanizmasına dayalı yönlendirme algoritması, esas olarak sanal para biriminin yönlendirme algoritmasına dayanır. CBS mekanizmasında, alıcılar ve satıcılar sırayla teklif verir, ancak üç tur sonra feshedilmeleri gerekir, yani üçüncü teklif için karşı taraf kabul etmelidir. Bu mekanizma, bencil düğümlerin işbirliğini teşvik edebilir ve birden fazla oyunda oyun sürecinin neden olduğu tüketimi azaltabilir. GSCP mekanizması, olasılıksal yönlendirmeye dayalı bir düğüm pazarlık oyunu mekanizmasıdır. Mekanizma, düğüme gelen mesajın değerinin, hedef adrese ulaşma olasılığı ile orantılı olduğunu varsayar. Mesaj, düşük değerli düğümden satılır ve yüksek değerli düğüm tarafından satın alınır. Mesaj, hedef düğüme ulaşır.
1 Ağ modeli ve sorun açıklaması
1.1 Ağ modeli
Tanım 1 (mesaj değeri) Düğüm hareketi sürecinde, düğüme gönderilen mesajın değeri, düğümün mesajın hedef adresini karşılama olasılığı ile pozitif olarak ilişkilidir. Varsayalım ki, d düğüm i, m mesajını hedef adresine d, ulaştırma olasılığıdır. Mesajın başlangıç değeri, V, katılımcı düğüm i'ye m mesajının değeridir ve değeri V = · Pi, d'dir.
Tanım 2 (Alış ve satış modeli) B düğümü, S düğümünde m mesajını almak isterse, S'ye bir satın alma talebi gönderecek ve satın alma fiyatını x belirleyecektir. S'nin fayda değeri, fiyat x'in altında pozitifse, S B'yi kabul eder. Ve m'yi B'ye gönderin; aksi takdirde, alıcı ve satıcı bir anlaşma sağlanana veya iletişim kesilene kadar bir sonraki pazarlık oyununu oynayacaklardır.
1.2 Sorun açıklaması
Araştırmada pazarlık oyunlarına dayalı mevcut fırsatçı ağ algoritmalarının aşağıdaki problemlere sahip olduğu tespit edildi:
(1) Mevcut GSCP algoritmasında, tek bir oyunda, yalnızca her iki tarafın getirileri 0'dan az olmadığında, iki taraf bir işleme ulaşacak ve başarılı bir işlem stratejisi benimseyecektir.Veri paketi satın alındığında satıcının kar etmiş olabileceğini düşünmez, bu da azalır Oyunda iki taraf arasındaki işlemlerin tamamlanma oranı ve iki tarafın oyunda benimsediği başarı stratejilerinin oranı.
(2) Düğümler, veri paketlerini iletmeden önce SV-DP mesajlarını değiştirmelidir: iki düğüm karşılaştığında ve DP listesi etkileşimi tamamlandığında, DP listesini alan düğüm, iki düğüm ve diğer düğümler arasındaki karşılaşma olasılığını bilebilir; bu Düğümün SV'deki bazı veri paketlerinin hedef düğümünü karşılama olasılığı, toplantı düğümününkinden daha yüksekse, toplantı düğümü veri paketini satın almayacaktır.Mevcut mekanizma, bu tür veri paketinin özetini SV'ye ekleyecek ve toplantı düğümüne gönderecektir. , Paket özetinin fazlalığıyla sonuçlanır.
(3) Veri paketi işlemleri sürecinde fazlalık kontrol mesajları vardır. Mevcut ilgili literatürde, veri paketleri iki düğüm arasında alınıp satıldığında, veri paketlerinin satın alınmasını talep eden satın alma mesajının alıcı düğüm tarafından satıcı düğümüne ayrı olarak gönderilmesi gerekir. Araştırmadan sonra, satın alma mesajının kaynak ve hedef düğümlerinin, SV mesajının kaynak ve hedef düğümleri ile aynı olduğu, bu nedenle SV-DP mesajlarının birleştirilip birlikte gönderilebileceği ve böylece ağ ek yükünün azaltılabileceği bulunmuştur.
(4) Veri paketi etkileşimi sürecinde düğüm, veri paketinin TTL alan değerini kontrol mesajları yoluyla (merhaba mesajı ve SV mesajı dahil) bilemez, bu da düğümün yaşam boyu alan değeri 1 olan veri paketini satın alması olasılığına yol açar ve bu da başarısızlıkla sonuçlanır. Gerekli yönlendirme ek yükü ve işlemleri.
2 EORB algoritması
Pazarlık oyunlarına dayanan mevcut fırsatçı ağ yönlendirme algoritmalarındaki yukarıdaki sorunları çözmek için, bu makale verimli bir fırsatçı ağ yönlendirme algoritması-EORB (Pazarlık oyununa dayalı Verimli Fırsatçı ağ Yönlendirme algoritması) önermektedir ve veri paketlerinin uyarlanabilir düzeneğini kullanır. SV-DP haberlerinin ve satın alma haberlerinin soyut, uyarlanabilir kombinasyonu, gelir satın alma ve satma oyun stratejisinin ve diğer mekanizmaların kapsamlı değerlendirmesi.
2.1 EORB algoritmasının yeni mekanizması
2.1.1 Uyarlanabilir Azaltılmış Paket Özeti
Bu makale "Uyarlanabilir Basitleştirilmiş Paket Özeti" ni önermektedir. Temel ilkesi aşağıdaki gibidir: Düğüm, veri paketini SV-DP veya DP-SV-BUY mesajına yüklemeden önce veri paketinin yaşam süresi alanının değerinin 1'den büyük olup olmadığına karar verir ve Veri paketindeki mevcut düğüm ile hedef düğümün buluşma olasılığının, veri paketindeki hedef düğüm ile buluşma düğümünün buluşma olasılığından daha az olup olmadığı, öyleyse, mevcut düğüm veri paketinin özetini SV-DP veya DP-SV-BUY mesajına yükler, Bu, gereksiz veri paketi özetlerinin yüklenmesini önler ve bunun neden olduğu gereksiz kontrol bilgilerini ortadan kaldırır.
2.1.2 SV-DP ve satın alma mesajının uyarlanabilir kombinasyonu
Mevcut fırsatçı ağ olasılıksal yönlendirme algoritmasında, mesajlarla etkileşime giren karşılaşma düğümünün süreci Şekil 1'de gösterilmektedir. Bu etkileşim süreci, sinyal fazlalığı problemine sahiptir.
Bu soruna yanıt olarak, bu makale "SV-DP mesajlarını ve satın alma mesajlarını uyarlamalı olarak birleştirmeyi" önerir ve temel ilkeleri aşağıdaki gibidir:
SV-DP mesaj etkileşim aşamasının işleyişinde, mevcut düğüm diğer taraftan SV-DP mesajını aldıktan sonra, diğer tarafın SV listesindeki mesajın hedef adresine, diğer tarafın olasılık listesindeki hedef adrese ulaşma olasılığına ve düğümün olasılık listesine dayanır. Mesajın hedef adresine ulaşma olasılığı, mesajın satın alınıp alınmayacağını belirlemek için kullanılır.
Mesaj satın alınırsa, oyun dengesi altındaki mesajın optimal fiyatı hesaplanır.Düğümün SV listesi mesajı diğer düğüme gönderilirken satın alınması gereken mesaj, yeni bir DP-SV-SATIN AL mesajı oluşturmak için SV listesinin arkasına eklenir. Mesajın hedef adresini mesaj için alıntı olarak biçimlendirin ve ayarlayın. DP-SV-BUY mesajını aldıktan sonra, karşı düğüm ilgili satın alma mesajını çıkarabilir. DP-SV-BUY mesaj formatı Şekil 2'de gösterilmektedir ve geliştirilmiş mesaj etkileşim süreci Şekil 3'te gösterilmektedir.
2.1.3 Alım satım gelirini kapsamlı bir şekilde değerlendiren oyun stratejisi
Problem (4) 'e yanıt olarak, bu makale "ticaret gelirini kapsamlı bir şekilde değerlendiren yeni bir oyun stratejisi" mekanizması önermektedir.Yeni mekanizmanın temel prensibi aşağıdaki gibidir.
Satıcı düğüm ile hedef düğüm arasındaki karşılaşma olasılığı ile alıcı düğüm ile hedef düğüm arasındaki olasılık arasındaki fark, oyun sürecindeki iletim ve alım kayıplarını telafi edebildiğinde, alıcı düğüm, alt oyun dengesinin optimal fiyatına göre satıcı düğümüne bir teklif önerir. .
Aksi takdirde, üretilen fayda, oyunda gönderme ve alma kaybını telafi etmek için yeterli olmadığında, alıcı düğüm teklifi düşürür ve yeni fiyat, kendi yararının 0 olduğu zamana karşılık gelen fiyat olur. Satıcı düğümü, mesajı satın almanın fayda değerini ve alıcının Önerilen yeni teklif altındaki fayda değerinin toplamının 0'dan büyük olup olmadığı, teklifin kabul edilip edilmeyeceğini belirler, 0'dan büyükse teklifi kabul eder, aksi takdirde teklifi reddeder. Bu düğümün kapsamlı fayda değerinin (alış ve satış) 0'dan az olmadığı varsayımı altında, bu mekanizma, oyundaki iki taraf arasında başarılı işlemlerin olasılığını artırır, böylece mesaj iletme oranını hızlandırır ve mesajın hedef düğüme ulaşma gecikmesini azaltır. .
2.2 EORB algoritması çalışması
EORB algoritması işlem adımları aşağıdaki gibidir:
(1) S ve B düğümleri birbirlerinin iletişim aralığına girer ve komşu keşfi yoluyla bilgi alışverişi yapabileceklerini öğrenirler.
(2) Düğüm S, B düğümüne SV listesi ve olasılık listesi mesajlarından oluşan bir SV-DP mesajı gönderir. S düğümünün geçerli SV-DP mesajında atlama sayısı 1 olan bir mesaj yoksa, S düğümü doğrudan karşılaşan düğüm B'ye gönderir Kendi SV-DP mesajı; mevcut S düğümünün SV-DP mesajında atlama sayısı 1 olan bir mesaj varsa ve mesajın hedef adresi mevcut karşılaşmanın B düğümü değilse, SV listesindeki mesaja karşılık gelen özet listeden kaldırılır. Silin ve ardından bir SV-DP mesajı gönderin.
(3) B düğümü, S düğümünün SV-DP mesajını aldıktan sonra, ilk olarak adım (2) 'deki aynı işleme göre kendi mesajını işler ve diğer tarafın SV-DP mesajını aşağıdakileri belirlemek için kullanır: B düğümü ve önbellekteki m mesajı Hedef düğümün karşılaşma olasılığı S düğümünden daha yüksekse, m mesajına karşılık gelen özet kendi SV listesinden silinir; daha sonra diğer tarafın SV-DP mesajındaki her bir özet mesajın hedef adresi, diğer tarafın olasılık listesindeki hedef adrese ulaşma olasılığı ve Düğüm olasılık listesindeki mesajın hedef adresine ulaşma olasılığı, mesajın satın alınıp alınmayacağını belirler. Mesajı satın alırsanız, oyun dengesi altında mesajın optimal fiyatını hesaplayın.Düğümün SV mesajını diğer düğüme gönderirken satın alınması gereken mesajı SV-DP mesajına ekleyin ve mesajın hedef adresini ayarlayın Mesajı alıntılamak için, DP-SV-BUY mesajıyla birleştirilir.
(4) Düğüm S, B düğümünden DP-SV-BUY mesajını aldıktan sonra, SV listesini arar ve karşılaştırır.Kendi SV'si ile aynı SV kaynak adresine ve mesaj etiketine sahip bir mesaj varsa, mesajın talep edildiğini ve hedef adresin değerini belirtir. Bu, mesajın teklifidir ve S düğümü, alış ve satış gelirlerinin toplamını kapsamlı bir şekilde dikkate alarak teklifi kabul edip etmeyeceğine karar verir.
(5) S düğümü, B düğümünden gelen teklifi kabul ettikten sonra, B düğümüne karşılık gelen bir mesaj gönderir.
(6) B düğümü satın alınan mesajı aldıktan sonra, kendi imzasıyla bir işlem makbuzu oluşturur ve bunu S düğümüne gönderir.
(7) Düğüm S işlem dekontunu aldıktan sonra, daha sonra işlem takas merkezi (CCC) ile karşılaşırsa, işlem dekontunu CCC'ye sunacak ve CCC, ücretleri kesecek ve makbuza göre her iki tarafın hesaplarını yeniden yükleyecektir.
2.3 Cinsiyet Teorisi Analizi
Lemma 1: GSCP algoritması ile karşılaştırıldığında, EORB algoritmasının mesaj iletme hızı daha yüksektir.
GSCP'de, oyun sırasında alıcının ve satıcının fayda değerini hesaplama formülü ve oyun dengesinin en uygun teklifi:
Formülde, Vi, m mesajının i düğümüne değerini, ci (r), r-inci oyundaki i düğümünün maliyetini temsil eder, ui, i düğümünün faydasını temsil eder, T (m), m mesajını iletme maliyetini ve P (m) M mesajının alınma maliyetini temsil eder ve x mesaj işlem fiyatını temsil eder. Yalnızca uB ve uS, 0'dan az olmadığında, mesaj satıcı düğümünden alıcı düğümüne iletilebilir. UB ve uS'nin 0'dan az olmama olasılığının Pb ve Ps olduğu varsayıldığında, oyun mesajının yönlendirme olasılığı şöyledir:
EORB algoritmasında, alıcı düğüm uB 0'dan az olmadığında mesajı satın almayı kabul edecek ve satıcı kapsamlı bir şekilde ub mesajını ve satışın yararını ve ut değerini satın alacaktır. Ut 0'dan küçük değilse, Ardından satıcı düğümü mesajı satmayı kabul eder. Ub her zaman pozitif olduğundan, ut'un 0'dan küçük olmaması olasılığının Pt olduğu varsayılırsa, uS'nin 0'dan küçük ve ut'un 0'dan küçük olmaması olasılığı Ps1'dir, bu durumda oyun mesajının iletme olasılığı:
Denklem (3) ve denklem (4) 'ten, Pn'nin > P, EORB algoritmasının daha yüksek bir mesaj iletme hızı olduğu kanıtlanmıştır.
Lemma 2: EORB algoritmasının kontrol ek yükü, GSCP algoritması ve HLPR-MG algoritmasından daha düşüktür.
Ağda m mesaj olduğunu, bir düğüm tarafından gönderilen bir mesajın enerji tüketim değerinin olduğunu, mesajın kaynak düğümden hedef düğümüne ortalama atlama sayısının ETX olduğunu, düğüm tarafından taşınan her mesajın ortalama enerji tüketiminin olduğunu ve mesaj iletim süresinin is olduğunu varsayalım. , GSCP algoritmasında mesaj iletimini tamamlamak için gereken toplam enerji tüketimi EGSCP ve gecikme TGSCP şunlardır:
EORB algoritmasında mesaj iletimini tamamlamak için gereken toplam enerji tüketimi ve gecikme şunlardır:
Bilinen EEORB < EGSCP, TEORB < TGSCP kanıtladı.
Lemma 3: "Uyarlamalı olarak azaltılmış paket sindirimi" mekanizmasının benimsenmesi, SV etkileşim aşamasının ek yükünü azaltabilir.
Ağdaki düğümler tarafından taşınan ortalama mesaj sayısının m olduğu varsayıldığında, mesajdaki atlama sayısı 1'e düşürülmüştür ve karşılaşan düğümdeki mesaj olmayan ortalama hedef düğüm sayısı n (n < m), birim uzunluktaki SV listesi (yani SV listesinin yalnızca bir mesaj özeti içerdiği anlamına gelir) enerji tüketimi gerektirir, bu nedenle "uyarlamalı olarak azaltılmış paket özeti" mekanizması kullanılmaz ve mevcut düğüm diğer düğümlerle temas halindedir. SV etkileşimi sırasında tüketilen enerji:
"Uyarlamalı olarak azaltılmış veri paketi özeti" mekanizmasında, diğer düğümlerle SV etkileşiminde mevcut düğüm tarafından tüketilen enerji:
Gördüğün gibi, Enew < Eorig, kanıtladı.
3 Simülasyon parametreleri ve istatistikleri
3.1 Simülasyon parametreleri
Bu makalenin spesifik simülasyon parametreleri Tablo 1'de gösterilmektedir.
3.2 Simülasyon sonuçları ve analizi
(1) Kontrol ek yükü
Şekil 4'ten, EORB algoritmasının kontrol ek yükünün, her bir senaryodaki diğer iki algoritmadan daha düşük olduğu görülebilir. Ana nedenler şunlardır: SV mesajının içeriği uyarlamalı olarak basitleştirilmiştir, bu da kontrol mesajının uzunluğunu azaltır; SV-DP mesajını ve satın alma mesajını uyarlamalı olarak birleştirme mekanizması, kontrol mesajlarının sayısını azaltır.
(2) Ağ işleme hızı
Şekil 5'ten, EORB algoritmasının ağ veriminin daha yüksek olduğu görülebilir. Bunun başlıca sebebi şudur: Satın alma ve satmanın faydalarını kapsamlı bir şekilde ele alan oyun stratejisi, alıcılar ve satıcılar arasında başarılı işlemlerin olasılığını arttırır; SV SV-DP mesajlarının ve satın alma mesajı mekanizmalarının uyarlamalı olarak birleştirilmesi, kontrol mesajlarının sayısını azaltır ve geçersizliği azaltır Mesaj etkileşimini kontrol edin.
(3) Ortalama uçtan uca gecikme
Şekil 6'dan görülebileceği gibi, EORB algoritması daha düşük ortalama uçtan uca gecikmeye sahiptir. Bunun nedeni şudur: Satın alma ve satmanın faydalarının kapsamlı bir şekilde değerlendirilmesi, hem alıcıların hem de satıcıların işlem başarı oranını iyileştirir; SV-DP mesajlarının ve satın alma mesajlarının uyarlanabilir kombinasyonu, kontrol mesajlarının sayısını azaltır ve kontrol mesajlarının etkileşim sürecini azaltır.
(4) Mesaj varış oranı
Şekil 7'deki algoritmaların karşılaştırılmasından, EORB algoritmasının mesaj iletimi başarı oranını iyileştirdiği görülebilir. Bunun nedeni şudur: Satın alma ve satmanın faydalarını kapsamlı bir şekilde değerlendiren oyun stratejisi, alıcılar ve satıcılar arasındaki başarılı işlemlerin olasılığını artırır ve mesajın ulaşmasının başarı oranını artırır; SV-DP mesajlarının ve satın alma mesajı mekanizmalarının uyarlanabilir kombinasyonu, kontrol mesajlarının sayısına izin verir. Azaltma, kontrol mesajlarının etkileşim süreci azaltılır, bu da mesajların ulaşma oranını iyileştirmek için faydalıdır.
4. Sonuç
Pazarlık oyunlarına dayanan mevcut fırsatçı ağ yönlendirme algoritmalarının aşırı ek yükü ve düşük işlem başarı oranı sorunlarını hedefleyen bu makale, verimli bir fırsatçı ağ yönlendirme algoritması - EORB önermektedir. Algoritma, paket sindirimlerinin uyarlanabilir düzene sokulması, SV-DP mesajlarının ve satın alma mesajlarının uyarlanabilir bir şekilde birleştirilmesi ve mesaj iletme oranını hızlandıran, mesaj geliş oranını artıran ve ortalama mesajı azaltan ticaret gelirini kapsamlı bir şekilde değerlendiren bir oyun stratejisi gibi mekanizmaları benimser Geciktirin ve sistemin ek yükünü azaltın.
Referanslar
Xiong Yongping, Sun Limin, Niu Jianwei, ve diğerleri, Opportunity Network. Journal of Software, 2009, 20 (1): 124-137.
STAVROULAKI V, TSAGKARIS K, LOGOTHETIS M, ve diğerleri Fırsatçı ağlar IEEE Vehicular Technology Magazine, 2011, 6 (3): 52-59.
SHEVADE U, SONG H, QIU V, ve diğerleri. DTNS'de Teşvik-farkında yönlendirme.IEEE Uluslararası Ağ Protokolleri Konferansı Devam Etmesi, Orland, ABD, 2008: 238-247.
Liu Qilie, Hou Pengxiang. Fırsat Ağında Teşvik Düğümü Algılama Stratejisi Araştırması.Congqing University of Posts and Telecommunications (Natural Science Journal), 2015, 27 (2): 266-272.
WU F, CHEN T, ZHONG S, vd.Oportünist ağlarda olasılığa dayalı yönlendirme için işbirliğini teşvik etmek için oyun-teorik bir yaklaşım. Kablosuz İletişim Üzerine IEEE İşlemleri, 2013, 12 (4): 1573-1583.
Ren Zhi, Suo Jianwei, Liu Wenpeng ve diğerleri.Çok partili pazarlık oyununa dayalı olarak yüksek verimli ve düşük ek yüke sahip fırsat ağ yönlendirme algoritması. Journal of Communications, 2015, 36 (6): 2015129.
yazar bilgileri:
Ren Zhi, Kang Jian, Xu Zhaokun
(İletişim ve Bilgi Mühendisliği Okulu, Chongqing Posta ve Telekomünikasyon Üniversitesi, Chongqing 400065)
