Bölüm 78: Zaman Eşitleme ve Konum Bulma

Birbirlerine sorarak ve birbirlerini ölçerek. İki problem aynı yerden besleniyor: ortada her düğümün danışabileceği mutlak bir kaynak yok. İnternetteki bir bilgisayar saatini bir zaman sunucusuna sorabilir, telefonun konumunu uydular verir. Tarladaki düğümün ise elinde yalnızca kendi kristali ve komşularından duyduğu mesajlar var.

Önce zaman. İki düğümün saati neden aynı kalmıyor?

Saatler neden kayar?

Bir düğümün saati, bir kristalin titreşimini sayan bir sayaç. Kristaller tam etiketlerindeki frekansta titreşmiyor. 52. bölümde Ethernet’in kristaller için milyonda 100’e kadar sapmaya izin verdiğini görmüştün. Ucuz sensör düğümlerinde de milyonda birkaç düzinelik sapmalar olağan.

Milyonda 50’lik sapma küçük görünüyor. Hesabı yapınca öyle değil:

İki düğümden biri milyonda 50 hızlı, öteki 50 yavaşsa aralarındaki fark bunun iki katı hızla açılıyor. Kristalin frekansı sıcaklıkla da oynuyor; gündüz güneş alan bir düğüm ile gölgedeki komşusu farklı hızlarda yaşlanıyor.

Zamanın neden bu kadar önemli olduğu da birkaç yerden geliyor. Bir aracın geçişini üç düğüm algıladıysa, aracın hızı ve yönü bu algılamaların sırasından ve aralarındaki sürelerden çıkıyor. 76. bölümdeki TSCH, düğümlerin aynı 10 milisaniyelik dilimde uyanmasına dayanıyor; saatler dilim içindeki pay kadar kayarsa iki düğüm birbirini hiç duymuyor. Aşağıda göreceğin bazı konum yöntemleri ise mikrosaniyelik hassasiyet istiyor.

Bir mesaj ne kadar sürede gider?

Zamanı eşitlemenin tek yolu mesaj göndermek. “Saat şu an 12:00:00,000” diyen bir mesaj alıcıya ulaştığında artık 12:00:00,000 değil. Aradaki gecikmenin parçaları sensör ağlarında ayrıntıyla incelendi:

2. bölümdeki tabloda yayılım, iletimden dört yüz kat büyüktü. Burada tablo tersine dönüyor: iletim, yayılımdan on iki bin kat uzun. Asıl ders ise son sütunda. Belirsizliğin neredeyse tamamı iki uçta, yazılımın ve erişim kuralının içinde. Bu yüzden hassas eşitleme protokollerinin ortak hilesi, zaman damgasını yazılımda değil, radyonun frame’in başlangıç işaretini gönderdiği ya da aldığı anda basmak. Böylece hazırlama ve erişim süreleri hesaptan tamamen çıkıyor.

İki yönlü zaman alışverişi

İnternetteki zaman protokolü NTP ile aynı fikir. A düğümü B’ye bir mesaj gönderiyor ve iki uç dört an kaydediyor: A’nın gönderdiği an T1 ve B’nin aldığı an T2, B’nin cevabı gönderdiği an T3 ve A’nın aldığı an T4. T1 ile T4 A’nın saatine, T2 ile T3 B’nin saatine göre. Gidiş ile dönüşün aynı sürdüğünü varsayınca:

saat farkı  = ( (T2 − T1) − (T4 − T3) ) / 2
tek yön     = ( (T4 − T1) − (T3 − T2) ) / 2

Bir örnek. B’nin saati A’nınkinden 0,5 milisaniye ileride, mesaj 40 mikrosaniyede gidiyor, B cevabını 10 mikrosaniye sonra gönderiyor. Milisaniye cinsinden:

T1 = 1000,000   (A)       T2 = 1000,540   (B)
T3 = 1000,550   (B)       T4 = 1000,090   (A)

saat farkı = ( 0,540 − (−0,460) ) / 2 = 0,500 ms
tek yön    = ( 0,090 − 0,010 ) / 2    = 0,040 ms

Formül her iki sayıyı da doğru buluyor. Varsayımın bozulduğu yer, gidiş ile dönüşün farklı sürdüğü durum; o farkın yarısı doğrudan hataya ekleniyor.

2003’te yayımlanan TPSN bu alışverişi bütün ağa yaydı. Önce kökten başlayarak her düğüme bir seviye veriliyor. Sonra her düğüm, bir üst seviyedeki komşusuyla iki yönlü alışveriş yapıp ona eşitleniyor. Zaman damgaları radyo katmanında basıldığı için komşu iki düğüm arasındaki ortalama hata 16,9 mikrosaniyede kaldı. Aynı donanımda denenen ve birazdan göreceğin RBS’nin hatası 29,13 mikrosaniyeydi; iki yönlü alışveriş onu yaklaşık iki kat geçti.

Göndereni denklemden çıkarmak: RBS

2002’de yayımlanan RBS (Reference Broadcast Synchronization) soruyu bambaşka bir yerden yakaladı. Bir düğüm bir başvuru mesajı yayınlıyor. Mesajın içinde hiçbir zaman bilgisi yok. Onu duyan alıcılar, mesajın geldiği anı kendi saatleriyle not ediyor. Sonra alıcılar bu notları kendi aralarında değiş tokuş ediyor.

Hilenin inceliği şurada. Başvuru mesajının hazırlanması, erişim için beklemesi ve iletimi bütün alıcılar için ortak; hepsi aynı mesajı aynı anda duyuyor. Alıcıların notları arasındaki fark bu yüzden gönderenin belirsizliğini hiç içermiyor, yalnızca alıcıların saat farkını gösteriyor. Belirsizliğin iki ucundan biri böylece tamamen ortadan kalkıyor.

Berkeley düğümlerinde hata dağılımının standart sapması 11,1 mikrosaniye çıktı. Linux çalıştıran el bilgisayarlarında 6,3 mikrosaniyeye indi; aynı donanımda NTP’den sekiz kat iyiydi. Başvuru mesajı birkaç kez tekrarlanırsa alıcılar yalnızca saat farkını değil, farkın değişim hızını da hesaplayabiliyor.

Taşkın ve eğim: FTSP

2004’te yayımlanan FTSP iki fikri birleştirerek bu alanın en çok kullanılan protokollerinden biri oldu.

Bir kök düğüm düzenli aralıklarla eşitleme mesajı yayıyor ve bu mesaj ağ boyunca taşkınla yayılıyor. Her mesaj, göndereninin “küresel zaman” tahminini taşıyor ve bu damga radyo katmanında, frame’in başlangıç işaretinin havaya çıktığı anda yazılıyor. Alıcı da damgayı aynı işaretin geldiği anda alıyor. Belirsizliğin iki ucunun ikisi de hesaptan çıkıyor.

İkinci fikir, eğimi öğrenmek. Alıcı son birkaç eşitleme noktasını tutup bunlara bir doğru uyduruyor. Doğrunun kesişimi saat farkını, eğimi ise saatin ne kadar hızlı ya da yavaş çalıştığını veriyor. Aradaki önemi bir hesap gösteriyor. Eşitleme mesajları 30 saniyede bir geliyorsa, milyonda 50 sapan bir saat iki mesaj arasında 1,5 milisaniye kayar. Eğim bilinirse bu kayma hesaplanıp düzeltiliyor ve hata mikrosaniyeler düzeyinde kalıyor.

Sonuçlar Mica2 düğümlerinde ölçüldü. On sekiz saat süren bir deneyde tek sekmedeki ortalama mutlak hata 1,48 mikrosaniye, en büyüğü 6,48 mikrosaniyeydi. Çok sekmeli ağda hata her sekmede yaklaşık 0,5 mikrosaniye büyüdü.

Konum: uzaklıktan yere

Bir düğüm, konumu bilinen birkaç çapa düğüme olan uzaklığını ölçebiliyorsa kendi yerini hesaplayabilir. Uzaklığı ölçmenin üç yolu var ve her biri başka bir fiziğe dayanıyor.

Sinyal gücü. Gelen sinyalin gücü mesafeyle düşüyor ve her radyo bu gücü zaten ölçüp RSSI olarak bildiriyor. 34. bölümdeki serbest uzay formülünde mesafe terimi 20·log₁₀(d) idi, yani mesafe iki katına çıkınca kayıp 6 dB artıyordu. Yere yakın ve engellerin arasında bu terimin katsayısı 30 ile 40’a çıkıyor. Formül ters çevrilince uzaklık çıkıyor. 1 metrede −45 dBm ölçülen bir verici, katsayı 30 alınırsa −75 dBm’lik bir sinyal için 10 metre uzakta hesaplanıyor. Sorun şu: çok yollu yayılım yüzünden ölçüm birkaç desibel oynamakta çok rahat. Aynı sinyal −78 dBm ölçülürse hesap 12,6 metre veriyor. Yalnızca 3 dB’lik bir oynama %26’lık bir uzaklık hatası. Sinyal gücü bedava ama kaba.

Varış zamanı. Sinyalin yolda geçirdiği süre ölçülürse mesafe hız çarpı süre. Radyo dalgası için bu nanosaniye hassasiyetli saat istiyor. 2000’de MIT’de geliştirilen Cricket zekice bir yol buldu: işaretçiler bir radyo mesajı ile bir ultrason sinyalini aynı anda gönderiyor. Radyo mesajı neredeyse anında geliyor, ses ise saniyede yaklaşık 343 metreyle yavaş yavaş. İkisi arasındaki 10 milisaniyelik fark 3,4 metre demek ve bunu ölçmek için sıradan bir saat yetiyor. Tasarımın bir de gizlilik yönü vardı: konumu merkezde bir sunucu değil, cihazın kendisi hesaplıyordu. Bugün aynı ölçümü radyo dalgasıyla doğrudan yapan ultra geniş bant radyolar var. Işık bir nanosaniyede 30 santimetre yol alıyor. Bu radyolar çok kısa darbeler gönderdiği için varış anını nanosaniye düzeyinde yakalayabiliyor ve uzaklığı on santimetreler düzeyinde buluyor; eşya bulucu etiketlerdeki ve bazı telefonlardaki hassas yön bulma bu teknolojiyle.

Geliş açısı. Birden çok antenden oluşan bir dizi, sinyalin hangi yönden geldiğini antenler arasındaki faz farkından çıkarabiliyor. İki çapadan gelen iki yön, bir konum demek. Bluetooth 5.1 bu yetenek için bir standart getirdi.

Uzaklıklar elde edildikten sonrası geometri. İki boyutta üç çapaya olan uzaklık, üç çember demek ve çemberler düğümün yerinde kesişiyor. Çapalar (0, 0), (10, 0) ve (0, 10) noktalarında, ölçülen uzaklıklar 5, √65 ve √45 olsun:

x² + y²          = 25
(x − 10)² + y²   = 65
x² + (y − 10)²   = 45

ikinciden birinciyi çıkar:   −20x + 100 = 40   →   x = 3
üçüncüden birinciyi çıkar:   −20y + 100 = 20   →   y = 4

Uzaklıklardan konuma giden bu hesabın adı trilaterasyon. Denklemleri birbirinden çıkarmak kareleri yok ediyor ve geriye doğrusal denklemler kalıyor. Ölçümler gürültülü olduğunda çemberler tek noktada kesişmiyor; o zaman daha fazla çapa kullanılıyor ve hataların karesini en küçük yapan nokta seçiliyor.

Uzaklık ölçmeden konum

Uzaklık ölçmek pahalı ya da güvenilmez olabilir. Menzilden bağımsız yöntemler yalnızca “kimi duyuyorum” bilgisini kullanıyor.

Merkez yöntemi. Düğüm, duyabildiği çapaların konumlarının ortalamasını kendi konumu sayıyor. Başka hiçbir ölçüm gerektirmiyor; doğruluğu çapaların sıklığına bağlı.

DV-Hop. 2001’de önerilen bu yöntem, 42. bölümdeki uzaklık vektörü fikrini konuma uyguluyor. Her çapa ağa kendi konumunu yayıyor ve her düğüm her çapaya kaç sekme uzakta olduğunu öğreniyor. Çapalar birbirlerinin konumunu bildiği için ortalama bir sekmenin kaç metre tuttuğunu hesaplayabiliyor. 60 metre aralıklı iki çapa arasında 4 sekme varsa bir sekme 15 metre. Bu sayı ağa duyuruluyor ve A çapasından 3 sekme uzaktaki bir düğüm kendini ona 45 metre uzakta sayıyor. Birkaç çapaya olan bu tahmini uzaklıklardan konum, yukarıdaki gibi hesaplanıyor.

Yöntemin zaafı, düğümlerin düzgün dağılmış olduğu varsayımı. Arada bir göl varsa sekmeler gölün kıyısından dolaşıyor, sekme sayısı gerçek mesafeden hızla uzaklaşıyor ve tahmin bozuluyor.

Konuma dayanan her şey bir saldırı yüzeyi de açıyor. Sahte konum yayan bir çapa bütün komşularını yanıltabiliyor. Daha incelikli olanı solucan deliği: saldırgan ağın iki uzak noktası arasına hızlı bir tünel kurup paketleri bir uçtan ötekine aktarıyor. Birbirinden kilometrelerce uzak iki düğüm kendini komşu sanıyor; hem sekme sayıları hem yönlendirme tabloları bozuluyor.

Özet

• Saat kayması birikir: milyonda 50’lik sapma dakikada 3, günde 4,3 saniye eder. Sıcaklık da kristalin hızını değiştirir.
• Belirsizlik uçlardadır: hazırlama ve erişim süreleri milisaniyeler oynar, yayılım ihmal edilebilir. Hassas protokoller zaman damgasını radyo katmanında basar.
• İki yönlü alışveriş saat farkını ve gecikmeyi birlikte bulur: dört zaman damgası, gidiş ile dönüşün eşit sürdüğü varsayımıyla.
• RBS göndereni, FTSP her iki ucu denklemden çıkarır: FTSP ayrıca saatin eğimini öğrenerek tek sekmede 1,5 mikrosaniye civarında kalır.
• Konum uzaklıktan ya da bağlantıdan çıkar: sinyal gücü ucuz ama kaba, varış zamanı ve ultra geniş bant hassas; merkez yöntemi ve DV-Hop ölçüm gerektirmez ama düzgün dağılım ister.

Artık düğümler bir ölçümün ne zaman ve nerede alındığını biliyor. Bütün bu protokoller sahaya çıktığında ne oldu? Gerçek bir adada, bir ağacın gövdesinde, bir yanardağın eteğinde bu ağlar neyi ölçtü ve sahada ne bozuldu?