Merkezi olmayan ağlarda mesaj iletimi için öncekilerden daha seri bir algoritma ve diğerlerinden farklı olarak mesajın teslimi garanti.
Doğaçlama ağlar – iletişim ağları mobil sensörlerle değişken olarak kurulur ve genelde merkezi değildir, yani hiç bir düğüm ağın tümünün ne şekilde olduğunu bilmez.
Merkezi olmayan ağlarla ilgili ortaya çıkan sorulardan biri ağın şeklinin belli olmadığı durumlarda bile mesajların her bir düğüme ulaşmasının nasıl garanti edileceğidir. Bu ay münferit algoritmalar üzerine ACM-SIAM sempozyumunda MIT Elektrik Mühendisliği ve Bilgisayar Bilimi Bölümünden yüksek lisans öğrencisi Bernhard Haeupler, bu soruya cevap veren yeni algoritması ile ödül aldı.
Haeupler’in algoritması bu konu üzerine geçmişte geliştirilen algoritmalardan daha hızlı. Asıl önemli nokta ise deterministik olması yani mesajın gereki her noktaya iletilebileceği garanti. Daha önceki algoritmalar ihtimallere dayanıyordu yani probabilistikti: ne kadar uzun süre çalıştırılırsa çalıştırılsın her zaman mesajın bir veya daha fazla noktaya ulaşmama ihtimali vardı.
Ağ üzerinde bir nokta ağın haritasını biliyorsa, deterministik mesaj yönlendirme algoritması geliştirmek nispeten kolay. Ancak doğaçlama ağlarda bu tip bir merkezileştirmek bir kaç nedenden pratik değil: doğaçlama ağların çalıştığı ortamlarda bir süpervizör noktaya güvenmek genelde mümkün değildir ve/veya ağın şekli sürekli değişkenlik arzeder dolayısıyla da network haritası da kısa sürede geçerliliğini yitirir. Son olarak doğaçlama ağları oluşturan cihazlar genelde batarya ile çalışır ve bir noktaya süpervizör rolü yüklemek ve bu noktaya diğerlerinden sürekli bilgi aktarılması bataryanın hızlı boşalmasına neden olur.
Müşterek aksiyon
Bu alanda çalışanlar gibi Haeupler ağ üzerindeki iletişimi seri halinde ilerleyen bir oyun gibi tasavvur ediyor. Oyunun her bir roundunun süresi bir düğümün komşuları ile bilgi alış verişi için geçen süre ve algoritmanın basit versiyonunda her bir düğüm bir komşu seçerek bilgi alış verişine başlıyor, sonra ikinci bir düğüm seçiyor ve her iki düğümle birden bilgi alış verişine başlıyor. Böylece düğüm komşuları tarafından gönderilen bilgileri almış ve üçüncü bir komşu seçtiğinde doğrudan ya da dolaylı bilgi almadığı bir düğümü seçmiş olur. Sonrasında da her üç noda bilgi göndermeye başlar. Algoritma bu şekilde, doğrudan ya da dolaylı olarak bilgi almadığı hiçbir düğüm kalmayıncaya kadar, haber almadığı yeni düğümler seçerek devam eder, her bir seçimde de yeni bir round başlar.
Bu algoritma mantığında Haeupler, bir düğümün seçip, doğrudan iletişim kurması gereken komşu düğüm sayısının ağ içinde bulunan düğüm sayısının 2 tabanlı logaritması olduğunu ispatlamış. Haeupler, algoritmanın bir düğümün komşuları ile iletişime geçmek üzere geçirmesi gereken round sayısını düşüren daha seri bir versiyonunu da geliştirmiş. Bu versiyonda komşuların adreslerinin saptaması yapılmış. Haeupler, “bu versiyonda ne kadar yüksek hıza çıkabilirseniz gibi gözüküyor ana henüz bunun ispatını yapamadım” diyor.
Adaptasyon: http://web.mit.edu/newsoffice/2013/ad-hoc-networks-0109.html