D2D iletişiminde RLE kodlama ikili ağacına dayalı keşif mesajı tasarımı
Li Xiaowen, Li Xinmei, Wang Xiaojuan
(Chongqing Posta ve Telekomünikasyon Üniversitesi, Chongqing Mobil İletişim Anahtar Laboratuvarı, Chongqing 400065)
D2D (Cihazdan Cihaza) iletişim, bir iletişim ağındaki komşu cihazlar arasında doğrudan bilgi alışverişi yapan bir teknolojidir.Cihazların, aynı uygulamaya sahip olduklarında ve aynı aktif durumda olduklarında komşu cihazlarla doğrudan bağlantı kurmasını sağlar. İletişim. Büyük veri hacimli cihaz uygulamaları ile sınırlı spektrum kaynakları arasındaki çelişkiyi amaçlayarak, RLE kodlama ikili ağaç yapısına dayalı keşif mesajları oluşturmak için bir yöntem önerilmiştir. Geleneksel uygulama tanımlama değeri yerine uygulama tanımlama değeri aralığını kullanarak, düğümün keşif yeteneğini geliştirmek için keşif mesajının boyutu azaltılabilir ve komşu cihaz tarafından gönderilen keşif mesajı alındığında, kod çözmeden sonra yinelemeli alt bölüm araması gerçekleştirilir. Yöntem, hızlı arama amacına ulaşabilir. Son olarak, sonuçların doğruluğu teorik analiz ve simülasyon deneyleri ile doğrulanır.
Çin Kütüphanesi Sınıflandırma Numarası: TN929.5
Belge tanımlama kodu: Bir
DOI: 10.16157 / j.issn.0258-7998.170987
Çince alıntı biçimi: Li Xiaowen, Li Xinmei, Wang Xiaojuan. D2D iletişiminde RLE kodlama ikili ağacına dayalı mesaj keşfi tasarımı.Elektronik Teknoloji Uygulaması, 2017, 43 (12): 81-84, 88.
İngilizce alıntı biçimi: Li Xiaowen, Li Xinmei, Wang Xiaojuan. D2D iletişiminde RLE kodlama ikili ağacına dayalı mesaj tasarımı bulma. Elektronik Tekniğin Uygulanması, 2017, 43 (12): 81-84, 88.
0 Önsöz
5G iletişimi için anahtar aday teknolojilerden biri olan D2D iletişim teknolojisi, komşu hizmet cihazları arasında doğrudan iletişim gereksinimlerini karşılayabilir ve hizmet veren baz istasyonunun yükünü azaltma avantajına sahiptir. D2D iletişiminde yakınlığa dayalı hizmetleri gerçekleştirmenin ilk adımı olan D2D keşif süreci, aynı ve aktif uygulama programlarının cihaz çiftleri arasına kurulduğu gerekçesiyle uygulanır. Geleneksel olarak, D2D keşif sürecinde kullanılan keşif mesajı uygulama adına göre tasarlanır, bu sadece belleği artan veri gereksinimlerini karşılayamaz hale getirmekle kalmaz, aynı zamanda veri aktarım hızını da azaltır.
Bu nedenle, bu konudaki ilgili belgeler de sürekli olarak ortaya çıkmaktadır. Literatür, hash fonksiyonuna dayalı olarak keşif mesajlarının oluşturulması için bir şema önermektedir. Literatür, literatüre dayalı olarak keşif mesajını yapılandırmak için çiçek filtresinin kullanımını ekler Şemada, keşif mesajı, çiçeklenme filtresi veri yapısı ve K hash fonksiyonlarına dayalı olarak tasarlanmıştır. Literatüre göre, uygulama keşfi sürecinde yanlış pozitifler kaçınılmazdır ve hata olasılığının azaltılması, keşfedilen bilginin boyutunu önemli ölçüde artıracaktır.
Bu nedenle, bu makale RLE kodlama ikili ağaç keşif mesajına dayalı bir tasarım önermektedir. Uygulamanın kimlik değeri aralığı, keşif mesajının boyutunu küçültmek için tanımlama değeri yerine keşif mesajında kullanılır ve ardından sayfalama aralığını belirtmek için bir ikili ağaç kullanılır ve RLE tarafından kodlanan ikili ağacın bit bilgisi, uygulamanın değer aralığını işletim cihazına bildirmek için kullanılır. Böylelikle verimli ve hatasız bir cihaz çifti bulma işlemi gerçekleştirilebilir.
1 Keşif süreci ve modeli
Cihazdaki her bir uygulamanın tanımlanmasını kolaylaştırmak için, bu makale, uygulama adına karşılık gelen ASCII değerinin toplamını tanımlama değeri olarak kullanır. Her uygulamanın adı farklı olduğu için, kimlik değeri her uygulamayı benzersiz şekilde tanımlayabilir. Mevcut cihazdaki çeşitli uygulamaların adlarını sayın ve işgal edilen bayt sayısının Şekil 1'de gösterildiğini bulun.
Evrensellik perspektifinden bakıldığında, her uygulamanın adını belirlemek için 72 bit kullanılabilir. Belli bir keşif döngüsünde iş başvurusu sayısının n, iş dışı başvuru sayısının m, n1, m0 olduğunu varsayarsak, keşif döngüsüne dahil olan toplam başvuru sayısı L'dir. = n + m, uygulama tanımlayıcı değerinin maksimum değerinin M ve M = 272 olduğu varsayıldığında, iş uygulamasının sayfalama aralığının maksimum uzunluğu M ve minimum uzunluk 1'dir. Belirli bir keşif döngüsündeki tüm sayfa aralıkları bir sayfa grubu Gp oluşturur ve tamamlayıcı kümesi, sayfalanmamış alanın değer aralığıdır.
Aslında, keşif mesajı, RLE kodlamasından sonra sayfa grubu Gp'nin tanımlayıcılarından biridir.
2 Keşif mesajı tasarımı
Bu yazıda önerilen RLE kodlamasına dayanan ikili ağaç yöntemi, bu dağıtımı RLE kodlamasından sonra bir sayfalama ikili ağaç Tp aracılığıyla benzersiz bir şekilde ifade eder ve bir Tp, bir Gp'ye karşılık gelir. Spesifik süreç aşağıda açıklanmaktadır.
2.1 İkili keşif mesajları ağacının yapısı
Keşif döngüsü sırasında, cihaz, uygulama tanımlayıcı değerine göre benzersiz bir şekilde bir ikili keşif mesajları ağacı oluşturabilir. Sayfalama aralığı bir ikili ağaçla temsil edildiğinde, tüm değer aralığını a {M, M / 2, M / 4, M / 8, ...} gibi belirsiz uzunluktaki çoklu düğümlere bölmek için yinelemeli orta nokta alt bölüm yöntemi kullanılır. . Yinelemeli alt bölüm sürecinde, her bölüm kapsamı yalnızca işlem dışı uygulamalar veya iş uygulamaları içeriyorsa, süreç sona erer; daha küçük (daha büyük) kapsam iş başvurularını ve işlem dışı uygulamaları içermiyorsa, o zaman Daha küçük (daha büyük) bir aralığın orta noktasında yinelemeli alt bölüm gerçekleştirin. Her bir alt bölüm işlemine, mevcut ikili ağaca bir sol (sağ) düğüm eklenerek ve bir kök düğüm başlatılarak eşlik edilir. Ve bu şekilde, işleri veya iş dışı uygulamaları içerecek bir kapsam kalmayana kadar, keşif mesajlarının ikili ağacının yapımı tamamlanır.
Yukarıdaki sürece bağlı olarak, cihaz Algoritma 1 aracılığıyla belirli bir Gp için ikili bir ağaç oluşturabilir.
Algoritma 1:
(1) x = 0, y = M-1 olduğu ilk arama aralığını ayarlayın ve geçerli düğümü kök düğüm olarak ayarlayın;
(2) Arama aralığı için, orta nokta ikiye bölünmesi ile sırasıyla ve;
(3) Daha küçük (büyük) aralık yalnızca iş uygulaması tanımlayıcısını içeriyorsa, sonraki adım bölünmez. Geçerli düğümün sol (sağ) tarafına bir yaprak düğüm ve bir kenar eklenir;
(4) Daha küçük (büyük) aralık yalnızca çalışmayan uygulama tanımlama değerlerini içeriyorsa, sonraki adım bölünmez. Geçerli düğümün sol (sağ) tarafına düğüm eklemeyin;
(5) Daha küçük (büyük) aralık iki farklı uygulama tanımlama değeri içeriyorsa, sonraki adıma geçin. Geçerli düğümün sol (sağ) tarafına bir düğüm ve bir kenar ekleyin ve arama aralığını sum () olarak değiştirin ve (2) adımına geçin;
(6) Kapsamın daha fazla bölünmesi yoksa mesaj ikili ağacın yapımının tamamlandığı görülür, aksi takdirde adım (2) 'ye gidin.
2.2 Keşif mesajının yapısı
Kablosuz kanalda D2D iletişim sürecinin gerçekleştirilmesini kolaylaştırmak için, bu kağıt mesaj ikili ağacının ikili bit dizgisini dönüştürme işlemini gerçekleştirir.
Bölüm 2.1'den, düğümlerin derecelerine ve bağlantılarına göre aşağıdaki dört farklı türe ayrılabileceği görülebilir:
(1) Sol ve sağ alt ağaç / yaprak düğümlü düğümler;
(2) Yalnızca sol alt ağaç / yaprak düğümü olan düğümler;
(3) Yalnızca sağ alt ağaç / yaprak düğümü olan düğümler;
(4) Yaprak düğümün kendisi.
Bu nedenle, her bir düğüm, Tablo 1'de gösterilen prensibe göre iki bit ile temsil edilebilir ve genişlik-birinci geçiş kuralını izleyen ikili ağaca göre, her bir düğümün iki biti, bir ikili bit dizisi oluşturmak için çıkarılır ve ardından algoritma 2 Kullanılan RLE kodlaması, bit dizisini son keşif mesajına kodlar.
Bit dizisi yalnızca iki farklı "0" ve "1" değeri içerdiğinden, keşif mesajının RLE kodlama işlemi için iki bayt kullanılabilir.
Algoritma 2:
(1) Bit dizisinin uzunluğunu hesaplayın, sayma değişkenini ve konum işaretçisini başlatın ve Algoritma 1 tarafından üretilen bit dizisini okuyun;
(2) Döngüsel olarak okunan değeri, şu anda RLE kodlanacak değerle karşılaştırın:
Eşit ise, sayaç 1 artırılır ve konum göstergesi eşit olmayan değer görünene kadar 1 artırılır.Sayma değerinin ilk ve değerin son olduğu kurala göre keşif mesajını oluşturun ve adım (3) 'e geçin;
Aksi takdirde, değeri doğrudan keşif mesajına kaydedin, konum işaretçisine 1 ekleyin ve (3) adımına geçin;
(3) Bit dizisinin sonu okunursa, program sona erer;
(4) Programı sonlandırın ve keşif mesajının yapısını tamamlayın.
Böylelikle cihazdaki uygulama, keşif mesajının bit dizisine bağlı olarak aktif olup olmadığını belirleyebilir. İlk olarak, cihaz RLE aracılığıyla bit dizgisinin kodunu çözer ve sonra bit dizisini önce genişlik ölçütüne göre bir ikili ağaca dönüştürür ve ardından aygıttaki uygulama tanımlama değerinin ikili ağaç tarafından temsil edilen kümeye ait olup olmadığını belirler, yalnızca kimlik değeri Yalnızca set ayarlandığında, bu uygulamayı içeren terminal hedef cihaz olarak kabul edilebilir. Spesifik değerlendirme yöntemi aşağıdaki gibidir:
(1) İlk olarak, RLE tarafından kodlanan bit dizisini alın;
(2) Geçerli değeri döngüsel olarak okuyun, val 0 ve val 1 ise, sonraki değer bu değere göre görüntülenmek üzere val'e eklenecektir; val = 0 veya val = 1 ise, orijinal değer görüntülenecektir;
(3) Düğümün değer aralığını başlatın, başlangıç ve bitiş konumları Başlangıç = 0 ve bitiş = 0'dır ve mevcut değerlendirme düğümü kök düğüm olarak kabul edilir;
(4) Halihazırda yargılanan her bir düğüm için, aygıttaki uygulama, tanımlama değerinin düğüm tarafından belirtilen aralığa ait olup olmadığına karar vermelidir;
(5) Mevcut karar düğümü bir yaprak düğüm ise, cihazdaki uygulamanın aktif olduğu kabul edilir ve karar sürecinden çıkılır. Aksi takdirde, orta noktayı orta olarak ayarlayın = (Başlangıç + bitiş) / 2;
(6) Mevcut tanımlama değeri > orta;
Mevcut düğümün sağ alt ağacı mevcutsa, Başlangıç = orta ayarını yapın, sağ alt ağacın kök düğümünü geçerli değerlendirme düğümü olarak ayarlayın ve (2) adımını gerçekleştirin;
Aksi takdirde, yani hak alt ağacı olmadığı için cihaz çalıştırılacak uygulaması olmadığını düşünür;
(7) Kararın kimlik değeri < orta;
Mevcut düğümün sol alt ağacı varsa, bitiş = orta olarak ayarlayın, düğümün sol alt ağacının kök düğümü geçerli değerlendirme düğümüdür ve adım (2) yürütülür;
Aksi takdirde, programdan çıkın;
(8) Programı sonlandırın.
Özetle, keşif mesajı, keşif mesajının boyutunu küçültebilen ikili bir bit dizisine kopyalanır. Aynı zamanda, bit dizilerinin kullanılması nedeniyle, çok sayıda işletim uygulaması olsa bile, önerilen yöntem yanlış pozitif hatalar sunmayacaktır. Ve karmaşıklığı açısından, ikili arama algoritması kadar etkilidir.
3 performans analizi
Mesajları keşfetmek için ideal tasarım, en kısa mesajlar aracılığıyla çok sayıda cihazı keşfetmektir ve hata oranı olmayacaktır. Yukarıdaki analize dayalı olarak, önerilen keşif mesajı çok sayıda uygulamayı doğru bir şekilde gösterebilir. Ek olarak, bu belgede önerilen tasarımın performansı, cihazdaki çalışan ve çalışmayan uygulamaların sayısına bağlıdır.
Sayfalama ikili ağacındaki her düğüm iki bit ile temsil edildiğinden, ilk analiz ikili ağaçta beklenen düğüm sayısıdır. Dağıtım aralığında L uygulamaları olduğunu varsayalım.İkili mesaj ağacının, uygulama tanımlama değerlerinin farklı dağılımlarına göre değiştiği bulunduğundan, E (M, n, m) beklenti fonksiyonu, bulunacak ikili ağaçta beklenen düğüm sayısı olarak tanımlanır. Nerede Mn + m, n1. Düğümlerin farklı özelliklerine göre, bu makale E (M, n, m) hesaplamak için özyinelemeli analiz kullanır. Aralıkta n iş ve m iş dışı uygulama olduğunu varsayarsak, bu durumda oluşturulan belirli bir ikili ağacın olasılığı P (M, n, m, i, j) olarak tanımlanır, yani: belirli ikili ağaçta , Kök düğümün sol alt ağacıyla temsil edilen aralık, i işleri ve j iş dışı uygulamaları içerir ve sağ alt ağaç tarafından temsil edilen aralık, ni işleri ve mj iş dışı uygulamaları içerir. Tablo 2, farklı belirli ikili ağaçların düğüm sayısını ve olasılıklarını göstermektedir.
Daha sonra, ikili ağaçtaki toplam düğüm sayısı bir kök düğüme ve sol ve sağ alt ağaçlardaki toplam düğüm sayısına bölünür. Sol alt ağaçta ve sağ alt ağaçta beklenen düğüm sayısı sırasıyla E (M / 2, i, j) ve E (M / 2, n-i, m-j) olarak ifade edilebilir.
İstatistiksel beklentilerin tanımına göre Tablo 2'de listelenen diğer durumlar da aynı şekilde analiz edilebilir. Başlangıç durumu için, E (2,1,1) = 2 ve E (M, n, 0) = 1, burada n1, m = 0, M > 2.
Tablo 2'den ikili ağacın düğümlerinin istatistiksel beklentilerini bulabiliriz:
İş başvurularının sayısı toplam başvuru sayısından çok daha az olduğundan, bu makalede sadece nM / 2 durumu ele alınmıştır.Belirli bir m, mn için, maksimum düğüm sayısı olasılığı:
Formül (2) 'de mesaj ikili ağacının düğüm sayısının E (M, n, m) olduğunu varsayarsak, bu E (M, n, m)' ye karşılık gelen bilgi Tablo 3'te gösterilmektedir.
Literatürden, genellik kaybı olmaksızın, bir bit dizgisinde 0 görünme olasılığının p, 0p1 olduğu varsayılırsa, 1 görünme olasılığı 1-p'dir; vb., Uzunluk 0 p'nin olasılığı pl (1-p) ve 1 uzunluklu l uzunluğu olasılığı p (1-p) l'dir.
Bu makalede, belirli bir konumda 0 olasılığı:
(4) ve (5) denklemlerini karşılaştırarak, önerilen yöntemin istatistiksel standartlarda keşif mesajlarının boyutunu önemli ölçüde azaltabileceği elde edilebilir. Bu, sonraki simülasyon sonuçlarında daha fazla doğrulanabilir.
Mesajın boyutunu keşfetmek, verimli D2D iletişimini gerçekleştirmenin anahtar konularından biridir, bu nedenle bu makale, mesaj boyutunu bulma yolunu inceleyerek önerilen yöntemin performansını değerlendirir. Şekil 2, farklı iş uygulamaları altında önerilen şemanın kümülatif dağılım diyagramını göstermektedir Bu şekilden, simülasyon sonuçlarının% 90'ında önerilen şemanın küçük bir bit uzunluğuna sahip işleri iyi bir şekilde bulabileceği elde edilebilir. Şekil 3'ten, önerilen şemadaki keşif mesajının boyutunun diğer üç şemadan daha iyi olduğu sonucuna varılabilir. Geleneksel şemada, keşif mesajı tüm uygulamaların adlarını içerdiğinden ve boyutu geleneksel şema ile karşılaştırıldığında 72n bit olduğundan, diğer üç şema keşif mesajı azaltma yönteminde önemli geliştirmeler elde etmiştir. Dahası, yanlış pozitif hatalar ve çiçeklenme şemasındaki bit sayısı ile karşılaştırıldığında, önerilen şemanın daha iyi etkileri vardır. Ve bu yazıda önerilen şema, keşif mesajının boyutunu kısaltma amacını daha iyi gerçekleştiren ikili ağaç temelinde yeniden RLE kodlaması gerçekleştirir.
4. Sonuç
Bu makale, keşif mesajlarının boyutunu azaltarak D2D iletişim sistemlerindeki keşif kapasitesi sorununu çözmek için yeni bir yöntem önermektedir. RLE tarafından kodlanan keşif mesajlarının ikili ağacı, geleneksel mekanizmada iş uygulama programının isim listesini taşımaktan daha etkili olan iş başvurusu programının kimlik aralığını belirtmek için tasarlanmıştır. Ayrıca teorik analiz ve simülasyon yoluyla elde edilebilir ve mesajın boyutunun önemli ölçüde küçültülmesi beklenir. Bu nedenle, bu yazıda önerilen yöntem D2D iletişim sisteminin keşif kabiliyetini arttırır ve çok sayıda cihaz iletişimini destekleyebilir. Gelecekteki çalışmalar için, önerilen şema, nadir görülen aşırı ağırlıklı mesaj boyutu durumunun üstesinden gelmek için de optimize edilebilir.
Referanslar
ASADI A, Wang Qing. Hücresel Ağlarda Cihazdan Cihaza iletişim üzerine bir anket Arash IEEE Communications Surveys and Tutorials, 2014, 16 (4): 1801-1809.
Dong Ziqiang, Liu Cancan. Yakınlık hizmetine dayalı D2D düğüm keşif teknolojisine genel bakış. Mikrobilgisayar ve Uygulama, 2016, 35 (16): 60-62, 66.
CHOI K W, LEE H, CHANG S C. Cihazdan Cihaza iletişimde mobil uygulamaları keşfetmek: Hash fonksiyonuna dayalı yaklaşım 2014 IEEE 79. Araç Teknolojisi Konferansı (VTC Baharı), 2014: 1-5.
CHOI K W, WIRIAATMADJA D T. Hücresel Cihazdan Cihaza iletişimde mobil uygulamaları keşfetme: Karma işlevi ve çiçeklenme filtresi tabanlı yaklaşım Mobil Hesaplamada IEEE İşlemi, 2016, 15 (3): 336-349.
Zhou Aiwu, Wu Guojin, Cui Dandan Geliştirilmiş bir ikili ağaç çok parçalı destek vektör makine algoritması. Mikrobilgisayarlar ve Uygulamalar, 2011, 30 (6): 14-21.
Shi Yulong, Xi Wei, Zhou Hua. NB-IoT sistemindeki ikili ağaca dayalı verimli çağrı mesajı tasarımı. IEEE İletişim ve NetWorking Standartları Konferansı (CSCN), 2016: 1-6.
CHOI K W, Zhu Han. LTE gelişmiş sistemde yakınlığa dayalı hizmet için Cihazdan Cihaza keşif. IEEE Journal on Selected Areas in Communications, 2015, 33 (1): 55-66.
