Ateşböceği Zaman Senkronizasyon Algoritmasının Tıkanıklıktan Kaçınma Mekanizması Üzerine Araştırma
Hao Chuangbo, Şarkı Ping
(Makine ve Elektrik Mühendisliği Okulu, Pekin Teknoloji Enstitüsü, Pekin 100081)
Çoklu robotlarda dağıtılmış ateş böceği zaman senkronizasyon yönteminin problemlerine yönelik olarak, ağ senkronizasyona yakın olduğunda, senkronizasyon mesajı çakışır ve kanal tıkanıklığı artar Ateşböceği zaman senkronizasyon algoritmasının bir tıkanıklıktan kaçınma mekanizması önerilmiştir. Bağlantı sinyali, iletişim mesajı çatışması problemini etkin bir şekilde çözerek, faz büyüme süreci boyunca rastgele dağıtılır. Son olarak, simülasyon deneyleri, yüksek düğüm yoğunluklu bir ağ ortamında senkronizasyon sürecini hızlandırabileceğini, mesaj çakışmalarını büyük ölçüde hafifletebileceğini ve iyi senkronizasyon sonuçları elde edebileceğini kanıtlayan senkronizasyon stratejisinin etkinliğini doğrular.
Kablosuz sensör ağı; zaman senkronizasyonu; biyonik algoritma; ateş böceği algoritması
Çin Kütüphanesi Sınıflandırma Numarası: TP393.0
Belge tanımlama kodu: Bir
DOI: 10.16157 / j.issn.0258-7998.2017.05.001
Çince alıntı biçimi: Hao Chuangbo, Song Ping. Firefly Zaman Senkronizasyon Algoritmasının Tıkanıklıktan Kaçınma Mekanizması Araştırması.Elektronik Teknoloji Uygulaması, 2017, 43 (5): 7-10.
İngilizce alıntı biçimi: Hao Chuangbo, Song Ping.Ateş böceğinden esinlenen eşzamanlılık algoritmasının tıkanıklıktan kaçınma mekanizması.Elektronik Tekniğin Uygulanması, 2017, 43 (5): 7-10.
0 Önsöz
Çoklu robot işbirliği sürecinde birden fazla robottan oluşan ağın sürekli genişlemesiyle, ağ topolojisi giderek daha karmaşık hale geliyor ve geleneksel ve yaygın olarak kullanılan merkezi kablosuz ağ senkronizasyon teknolojisi, avantajlarını yavaş yavaş yitiriyor.İnsanların acilen dağıtılmış bir zaman senkronizasyonu algoritması geliştirmesi gerekiyor. Doğa, insanlara dağıtılmış senkronizasyon algoritmaları geliştirmeleri için ilham verdi, tipik bir örneği Güneydoğu Asya'daki ateşböceklerinin senkronize yanıp sönen fenomeni. MIROLLO RE ve STROGATZ SH tarafından yapılan önceki çalışmalara dayanarak, ateş böceği senkronizasyon modelinin dinamik MS PCO (MS Pulse Couple Oscillator, MS PCO) modeli kurulmuş ve tam bağlantılı ve gecikmesiz bir çoklu osilatör ağında yakınsayabileceği kanıtlanmıştır. . Ateş böceği senkronizasyon algoritmasının kullanılması, senkronizasyon sürecini ağ topolojisinden ayırarak karmaşık topolojilere sahip büyük ölçekli ağlara uyum sağlamasını sağlar ve senkronizasyonun sağlamlığı artırılır. Bu tür bir algoritma, süper çerçeve yapısı senkronizasyonunda ve ağ uykusunda uygulanmıştır.
Bununla birlikte, ateşböceği tabanlı zaman senkronizasyon algoritması, büyük ölçekli ağ zaman senkronizasyonu problemini bir dereceye kadar çözse de, acilen çözülmesi gereken iki problem vardır: Birincisi, şu anda kullanılan eşzamanlı darbe birleştirme mekanizmalarının çoğu, tüm ağ senkronizasyona yakın olduğunda mesajları eşzamanlı olarak senkronize edecektir. Çatışma, CSMA / CA'nın, algoritmanın kararlılığını etkileyecek şekilde ağ tıkanıklığına ve öngörülemeyen gecikmeye neden olabilecek en kötü performansı elde etmesini sağlar.İkincisi, WSN'nin donanımı, Firefly senkronizasyon algoritmasının çok sayıda kayan nokta işlemini karşılayamaz. Bu nedenle, bazı bilim adamları, Firefly senkronizasyon ağının mevcut sıkışıklığını ve rahatsızlığını telafi etmek için bu alanda çaba sarf etmişlerdir. Bununla birlikte, bu çalışmalar sadece belirli bir dereceye kadar hafifletici bir etki yapmaktadır.Yüksek yoğunluklu bir ağda, senkronizasyon mesajlarının merkezi iletimi yine de ciddi kanal çatışmalarına neden olacaktır.
Yoğun düğüm kümelerinde senkronizasyon mesajlarının gönderilmesindeki tıkanıklık problemini büyük ölçüde çözmek için, bu makale ateş böceği zaman senkronizasyon algoritmasının bir tıkanıklıktan kaçınma mekanizmasını araştırıyor ve rastgele darbe bağlama mekanizmasına dayalı kablosuz sensör ağları için dağıtılmış bir ortak zaman senkronizasyonu yöntemi önermektedir. , Ağ tıkanıklığından mümkün olduğunca kaçının, ağ bant genişliği kaynaklarını tam olarak kullanın ve ateş böceği senkronizasyon algoritmasının uygulanabilirliğini artırın.
1 Senkron matematiksel model kurulması
1.1 MS PCO modeli
Başlangıçta senkronize olmayan sistemler için, Charles her ağ düğümünü bir RC osilatörü olarak ele alır ve tek bir osilatörün iki temel matematiksel modelini oluşturur: biri serbest çalışan bir model, diğeri ise diğer düğümlerle birleştirilmiş bir modeldir. Düğümün serbest çalışma durumunda, osilatörün modeli:
Formülde, x normalleştirilmiş tek osilatör voltajını, S0 şarj hızını ve i direnç kaçak akım faktörünü temsil eder. Kapasitör voltajı maksimum değere, yani x = 1'e ulaştığında, osilatör hızla boşalır ve voltaj aniden sıfıra döner. Şu anda, vibratör, diğer osilatörlerin voltajını, ikinci matematiksel model olan bir kuplaj katsayısı by ile artırmak için diğer osilatörlerle darbeli birleştirilir:
MIROLLO R E ve STROGATZ SH, Charles modeline dayalı olarak düğümün dinamik modelini tanıttı ve osilatör MS PCO modelini kurdu:
1.2 Basitleştirilmiş faz modeli
Yukarıda sunulan MS PCO, ateş böceği senkronizasyonu için teorik analiz için temel sağlar. Bununla birlikte, hesaplama çekirdeği olarak MCU'lu kablosuz sensör ağ düğümlerinde, donanım hesaplama kaynakları sınırlıdır. Değerlere faz eşlemesi yapılırken, çok sayıda kayan nokta işlemi donanım kaynaklarını işgal edecek ve ağın normal işlevlerini etkileyecektir. Bu nedenle, bu makale MS ile ilgilidir. PCO modelindeki faz durumu haritalamanın özellikleri, MS PCO modelini basitleştirir ve karmaşık kayan nokta işlemlerinden kaçınmaya çalışır.
Formülde, faz yükseltmesidir; j (t) örnek alınarak, t anında i düğümünün faz değerini temsil eder. Yani, düğüm geçerli bir tetikleme sinyali aldığında, faz c1j (t) + c2 kadar artırılır ve faz eşiği ile karşılaştırıldığında eşiğe ulaşırsa tetiklenir. Bu şekilde, düğüm durum değerinin işlenmesi, fazın işlenmesi ile değiştirilebilir ve karmaşık faz durumu eşleştirmesi, işlemi basitleştirme amacına ulaşmak için basit bir işlemle değiştirilebilir.
2 Tıkanıklık önleme mekanizması
Geleneksel MS PCO modelinde, düğümler tetikleme anında eşzamanlı olarak bağlanır. Kablosuz sensör ağlarında, dürtü eşleştirme, senkronizasyon mesajları gönderen düğümler tarafından gerçekleştirilir ve bu, düğüm kümesi senkronizasyon durumuna yakın olduğunda düğümlerin senkronizasyon mesajı alışverişinin çok yoğunlaşmasına neden olacaktır. Bu amaçla, bu bölüm, aşırı mesaj değişiminin neden olduğu kanal çatışmalarını hafifletmek için tüm faz büyüme sürecinde senkronizasyon mesajlarını dağıtmak için Stokastik Darbe Çift Osilatörünü (SPCO) kullanan bir tıkanıklık önleme mekanizmasını tanıtır.
2.1 Rastgele darbe bağlantısı
SPCO'da, ağdaki düğüm senkronizasyonu ile MS PCO arasındaki temel fark, darbe bağlantısı için senkronizasyon mesajlarını tetikleme ve gönderme işleminin zaman ekseninde ayrılmasıdır. Mesaj bağlantısının tetiklenmesi ve senkronize edilmesinin iki görevi birbirinden bağımsızdır. Düğüm, çalışma sırasında bir döngüden daha büyük rasgele zaman aralıklarında kendi faz bilgisiyle senkronizasyon mesajları gönderir. Senkronizasyon mesajının gönderildiği zaman, düğümün fazının eşiğe ulaştığı zamandan ziyade rastgeledir ve senkronizasyon mesajının, saf darbe bilgisi yerine gönderme anında düğümün faz bilgisini içermesi gerekir.
SPCO modelinde, bir düğüm bir senkronizasyon mesajı aldığında, ondan faz bilgisini çıkarır, kendi fazıyla karşılaştırır ve efektif faz bilgisini filtreler ve basitleştirilmiş modele göre faz artışını hesaplar. Ve elde edilen faz artışı, faz üzerinde bir bağlantı etkisi oluşturmak için faza eklenir.
Açıklamanın rahatlığı için, iki düğüm A ve B'nin rastgele darbelerle bağlandığını ve düğüm B'nin rastgele fazda at bir senkronizasyon mesajı gönderdiğini varsayalım. A düğümünün işleme algoritmasının spesifik süreci aşağıdaki gibidir:
(1) Düğüm A, düğüm B senkronizasyon mesajını aldığında, alınan protokolün yerel fazını a ve başlangıç eki gecikme fazını d kaydeder ve B düğümünün iletim mesajını elde etmek için senkronizasyon mesajındaki verileri analiz eder. Metnin aşaması.
(2) Senkronizasyon mesajı filtrelemesi gerçekleştirin Filtreleme kuralı: ancak ve ancak -d + r ve 1 + -dr olduğunda, yani A düğümü ve B düğümü arasındaki faz hatası r aralığının dışındaysa ve Bir döngüde B düğümü A düğümünden önce tetiklenirse, alınan veri paketi geçerlidir. R'nin rolü, MS PCO modelindeki refrakter döneme (Refrakter Periyot) benzerdir, bu nedenle refrakter periyodunun uzunluğu olarak da adlandırılır.
(3) Etkili mesaj işleme gerçekleştirin. İşlemenin temel fikri, senkronizasyon mesajı gönderme periyodunda B düğümünün tetiklenmesini simüle etmek ve darbe bağlantısının A düğümünün fazı üzerindeki etkisini senkronizasyon mesajının alındığı ana kadar ilerletmektir. Zaman ilerledikçe, -d + r olduğu için, B düğümünün fazı A düğümüne liderlik edecek ve B düğümü önce A düğümü ile eşiğe ulaşacaktır. B düğümü faz eşiğine ulaştığında, A düğümünün faz değeri:
ayarlama adım uzunluğu olduğunda; r refrakter periyot uzunluğu; d başlangıç eki gecikme fazıdır; ve adım (1) 'de kaydedilen faz değerleridir; c1 ve c2 kuplaj sabitleridir. Bu senkronizasyon mesajının nihai sonucu, düğüm A'nın fazının artmasıdır.Genel olarak, senkronizasyon yakınsamaya yakın olduğunda düğüm kümesinin faz seğirmesini önlemek için, 'yu sağlamak gerekir. < < r, c1 ve c2 kuplaj sabitleri küçük sabitler olmalıdır.
Özet olarak, tetikleme sürecinin dinamik modeli şu şekilde özetlenmiştir:
ayarlama adımı uzunluğu olduğunda; r refrakter dönem uzunluğu; d başlangıç eki gecikme aşamasıdır; ve (1) adımında kaydedilen faz değerleridir; A (t) örnek olarak alındığında, bu, A düğümünün T zamanındaki faz değeri.
2.2 Kararsız denge aralığından kaçış
Düğümler, faz eşiğinin yarısı kadar farklılık gösterdiğinde, iki düğümün konum değişiminin, herhangi bir düğüm tarafından başka bir düğüme gönderilen senkronizasyon mesajının faz artışına yol açan faz ayarlamasının ayarlama adımını etkilemediğine dikkat edilmelidir. Etki neredeyse aynıdır ve iki düğüm arasındaki faz farkı nispeten değişmeden kalır. Bu dengesiz denge fenomenini önlemek için, faz eşiğinin yarısında bir kaçış aralığı ayarlamak gerekir.Düğümlerin faz farkı bu aralığa düştüğünde, ayarlama adımı boyutu hızla U ve U kaçış hızına yükselir. > , kararsız denge alanından kaçmasını sağlayın ve senkronizasyonu hızlandırma amacına ulaşın.
3 Simülasyon ve sonuç analizi
Bu bölümde, simülasyon doğrulaması, 2. bölümde önerilen SPCO senkronizasyon mekanizmasında gerçekleştirilir. Karşılaştırmayı kolaylaştırmak için simülasyon deneyleri, geleneksel MS PCO mekanizması ve deney yapmak için bu makalede tanıtılan SPCO mekanizması kullanılarak iki gruba ayrılmıştır. Faz ve senkronizasyon mesajı eşzamanlılığını kaydederek, SPCO mekanizmasının senkronizasyon süreci üzerindeki etkisi üç açıdan analiz edilir: senkronizasyon yakınsama doğruluğu, gerekli senkronizasyon süresi ve senkronizasyon mesajı eşzamanlılığı.
3.1 Simülasyon parametre ayarı
Kontrastı arttırmak için, iki simülasyon deney setinde bazı ortak simülasyon parametreleri vardır. Simülasyon deneyinde, 20 düğüm tam bağlantılı bir ağda düzenlenmiştir ve simülasyon süresi 400 saniyedir. Ağdaki her bir düğüm, diğer 19 düğüm ile bağlantılıdır. Düğümlerin başlangıç aşaması rastgele 0 ile 1 arasında dağıtılır. Düğümün faz eşiği 1 ve faz süresi 1 saniyedir. Düğümün refrakter periyodunun uzunluğu 0.1'e ayarlanır ve düğüm fazı senkronizasyon penceresinin boyutu 0.001'dir (yani, faz hatası 0.001 dahilindeyse düğümün senkronize olduğu kabul edilir). tatmin etmek < < r, kuplaj sabitleri c1 = 0.005, c2 = 0.005 olarak ayarlanmıştır, SPCO'daki kararsız denge aralığı ayarlanmıştır ve kaçış hızı 0.3'tür.
Simülasyon modelinin özgünlüğünü sağlamak için, her düğümün kristal osilatör hızı 50PPM artırılır ve mesaj alışverişi sırasında 10-100 s'lik rastgele bir gecikme ayarlanır. SPCO'nun senkronizasyon süresi ve doğruluğu üzerindeki etkisini karşılaştırmak için, kanal çakışmalarının senkronizasyon mesajı iletimi üzerindeki etkisi geçici olarak göz ardı edilir.
3.2 Simülasyon sonuçları ve analizi
Şekil 1, iki test simülasyon setinden önceki ve sonraki ağ düğümlerinin faz değişikliklerini göstermektedir. Düğüm setinin ilk fazının dağıldığı şekilden görülebilmektedir SPCO ve MS PCO'nun senkronizasyon işleminden sonra, simülasyon bittikten sonra düğüm setinin fazı yakınsamaktadır. Nihai senkronizasyon etkisi perspektifinden, SPCO tabanlı çakışma önleme mekanizması, senkronizasyon algoritmasının kararlılığını ve doğruluğunu etkilemez.
Ağdaki senkronizasyon mesajlarının eşzamanlılığını saymak için, birim zaman aralığı 0.0005 s'dir ve birim zaman aralığındaki farklı merkezi anlarda eşzamanlı senkronizasyon mesajlarının sayısı, iletişim tıkanıklığını tespit etmek ve aynı zamanda saymak için sayılır. Faz hatası, kanunu bulmak için uygundur.
Şekil 2, faz hatasını ve MS PCO senkronizasyon sürecindeki zaman içindeki eşzamanlı mesajların sayısını göstermektedir. Senkronizasyon süreci ilerledikçe, faz hatası azaldıkça eşzamanlı mesajların sayısının önemli ölçüde arttığı şekilden görülebilir. 350 sn sonra düğüm kümesi senkronizasyona ulaşır Birim zaman aralığında eşzamanlı düğüm sayısı 20'ye bile ulaşır. Büyük eşzamanlılık, kablosuz kanalda ciddi tıkanıklığa neden olur ve bu, o anda veri aktarımının istikrarına ve aciliyetine elverişli değildir.
Şekil 3, faz hatasını ve MS PCO senkronizasyon sürecindeki zaman içindeki eşzamanlı mesajların sayısını göstermektedir. Şebeke fazının 30 sn'de yakınsamaya ulaştığı ve faz hatasının azalmasıyla eşzamanlı mesaj sayısının artmadığı şekilden görülebilmektedir. Tüm düğüm kümesinin senkronizasyon mesajları tüm zaman ekseninde eşit olarak dağıtılır ve faz hatalarından etkilenmez.
Şekil 2 ve Şekil 3 karşılaştırıldığında, SPCO çakışma önleme mekanizmasının, senkronizasyon doğruluğunu etkilemeden sadece senkronizasyon süresini kısaltmakla kalmayıp, aynı zamanda zaman eksenindeki eşzamanlı senkronizasyon mesajlarının neden olduğu kanal tıkanıklığını da büyük ölçüde azalttığı görülebilir.
4. Sonuç
Bu makale, birden fazla robotun dağıtılmış zaman senkronizasyonunu gerçekleştirmek için rastgele darbe eşleştirme senkronizasyonuna dayanan bir ateş böceği senkronizasyon kanalı tıkanıklığından kaçınma mekanizması önermektedir. Makale önce geleneksel ateş böceği senkronizasyonunun matematiksel modelini basitleştiriyor ve bir kanal tıkanıklığından kaçınma mekanizması veriyor ve ardından simülasyon deneyleri aracılığıyla karşılaştırma doğrulaması yapıyor. Deneyler, geleneksel MS PCO ile karşılaştırıldığında, SPCO senkronizasyon mekanizmasının senkronizasyon doğruluğunu etkilemeden senkronizasyon sürecini hızlandırabildiğini ve tıkanıklıktan kaçınma mekanizmasının uygulanabilirliğini doğrulayan merkezi tetik bağlantısının neden olduğu kanal tıkanıklığını büyük ölçüde hafifletebileceğini kanıtlamıştır.
Rastgele darbe eşleme senkronizasyon mekanizması, bir mikro denetleyicide uygulanması kolay olan basitleştirilmiş bir faz modeli kullanır. Tetikleme bilgisinin iletimi, bant genişliğinden tam olarak faydalanabilir ve hatta düğümün normal veri paketleri ile birleşebilir. Algoritmanın kendisi paket kaybına duyarlı değildir ve kablosuz ortamın daha sert koşullarına uyum sağlayabilir.
Referanslar
Xu Chaonong, Xu Yongjun, Li Xiaowei.Kablosuz sensör ağlarında zaman senkronizasyonu için yeni teknoloji Bilgisayar Araştırma ve Geliştirme, 2008, 45 (1): 138-145.
ALLARD H A. Ateşböceklerinin eşzamanlı yanıp sönmesi. Science (New York, NY), 1935, 82 (2120): 151-152.
BUSCH N E, VINNICHE N K, WATERMAN AT, ve diğerleri Dalgalar ve türbülans Radio Science, 1969, 4 (12): 1377-1379.
CAM L, MACKEY M C. Saatlerden kaosa - yaşamın ritimleri. Nature, 1988, 336 (6195): 119.
PESKIN C S. Kalp fizyolojisinin matematiksel yönleri New York: Court Institute of Mathematical Sciences, New York University, 1975.
MIROLLO R E, STROGATZ S H. Darbe bağlı biyolojik osilatörlerin senkronizasyonu SIAM J Appl. Math., 1990, 50 (6): 1645-1662.
BOJIC I, PODOBNIK V, LJUBI I, ve diğerleri.Kendini optimize eden bir mobil ağ: Ateş böceği ile senkronize edilmiş aracılarla ağı otomatik olarak ayarlama. Inform Sciences, 2012, 182 (1): 77-92.
TYRRELL A, AUER G, BETTSTETTER C. Kablosuz ağlarda acil yuva senkronizasyonu IEEE T. Mobile Comput., 2010, 9 (5): 719-932.
LEIDENFROST R, ELMENREICH W. Bir 802.15.4 kablosuz ağda Firefly saat senkronizasyonu.EURASIP Gömülü Sistemler Dergisi, 2009 (1): 1-17.
HONG Y W, SCAGLIONE A. Büyük ölçekli sensör ağları ve uygulamaları için ölçeklenebilir bir senkronizasyon protokolü IEEE J.Sel.Area.Comm., 2005, 23 (5): 1085-1099.
