211service.com
Inteligencja sygnału
MacArthur Fellow Dina Katabi, SM ’98, PhD ’03, wykorzystuje fizyczne właściwości fal radiowych, aby zwiększyć wydajność obliczeń. 20 października 2015
W 1989 roku Dina Katabi, SM ’98, PhD ’03, podobnie jak wszyscy syryjscy seniorzy szkół średnich, przystąpiła do standaryzowanego testu, który określił, do jakich kierunków studiów kwalifikuje się na uniwersytecie. Zajęła szóste miejsce w kraju.
Oznaczało to, że czeka ją szkolenie medyczne – najbardziej prestiżowy staż licencjacki, dostępny tylko dla studentów z najwyższymi wynikami na egzaminie. Co więcej, mówi, pochodzę z rodziny, która składa się wyłącznie z lekarzy. Mój ojciec jest lekarzem, większość moich ciotek i wujków to lekarze, mój dziadek jest lekarzem – jest tak wielu lekarzy po obu stronach. Więc to była droga dla mnie.
Ale po roku studiów, podczas których była na szczycie swojej klasy, Katabi doznała objawienia. Po prostu zdecydowałam: „Nie mogę żyć bez matematyki”, mówi. Przeniosła się więc do mniej prestiżowego programu studiów z zakresu elektrotechniki na Uniwersytecie w Damaszku. To była wielka kłótnia z moimi rodzicami, mówi.
Dwadzieścia pięć lat później wygląda to na całkiem dobrą decyzję: Katabi, obecnie Andrew (1956) i Erna Viterbi, profesor inżynierii elektrycznej i informatyki oraz członek Laboratorium Informatyki i Sztucznej Inteligencji (CSAIL), jest w trzeci rok genialnego stypendium MacArthura i właśnie wróciłem z zaprezentowania niektórych swoich nowych prac prezydentowi Obamie w Białym Domu. Protokoły sieciowe oparte na jej pracach znalazły zastosowanie w produktach komercyjnych, a jej innowacyjna reinterpretacja problemu zakłóceń o częstotliwości radiowej zmienia sposób, w jaki inżynierowie projektują sieci bezprzewodowe. Ale to nie znaczy, że sprzeciw jej rodziców był bezpodstawny. Medycyna była nie tylko bardziej cenionym zawodem w Syrii, ale także oferowała tam znacznie więcej możliwości zatrudnienia i przyciągała większą liczbę kobiet.
Społeczeństwo syryjskie w tym czasie było dość liberalne, mówi Katabi. Ale mimo to jej rodzice martwili się, że wejście w zawód z niskim odsetkiem kobiet utrudni jej życie. Mówi, że to coś, co odczuwamy nawet w USA w pewnych dziedzinach. Katabi szacuje, że tylko od 10 do 15 procent jej koleżanek z klasy zajmujących się elektrotechniką stanowiły kobiety.
Po ukończeniu studiów – znowu jako najlepsza w swojej klasie – Katabi przyjechała do Stanów Zjednoczonych na studia podyplomowe, podążając śladami ojca, który przyjechał na specjalizację medyczną. Po zdobyciu tytułu magistra informatyki na MIT rozpoczęła studia doktoranckie pod kierunkiem Davida Clarka, starszego naukowca w Laboratorium Informatyki (które od tego czasu połączyło się z Laboratorium Sztucznej Inteligencji w celu wyprodukowania CSAIL) oraz, przez większość lat 80. był głównym architektem protokołów internetowych.
Bardzo szybko stało się jasne, że zamierza wykonać jakąś wybitną pracę, mówi Clark. Wniosła bardzo charakterystyczne wykształcenie, ponieważ miała wykształcenie zarówno w zakresie elektrotechniki, jak i informatyki, więc miała szerszy zakres umiejętności niż wielu studentów informatyki, co pozwoliło jej podjąć inny zestaw problemów.
Rozprawa Katabi dotyczyła protokołów sieciowych, obszaru specjalizacji Clarka, ale przyjęła nietypowe podejście. Centralnym problemem w zarządzaniu siecią jest kontrola przeciążenia — ograniczanie transmisji, gdy grożą zablokowaniem sieci. Mechanizm kontroli przeciążenia Internetu polegał na tym, że każdy komputer monitorował własną transmisję i, jeśli wykrył oznaki przeciążenia, jednostronnie zmniejszał szybkość transmisji.
Takie podejście wydawało się działać w praktyce, ale nie miało solidnych podstaw teoretycznych. Katabi zaimportowało zasady z teorii sterowania, która analizuje zachowanie dużych systemów dynamicznych, do projektu protokołu sieciowego. Korzystając z tych zasad, ona i jej współpracownicy mogli nie tylko zaprojektować lepsze mechanizmy kontroli przeciążenia, ale także zapewnić matematyczną pewność, że będą działać na dużą skalę.
Cisco, największy na świecie producent sprzętu sieciowego, od tego czasu włączył część prac Katabi w zakresie kontroli przeciążenia do jednego ze swoich produktów, a 12 lat po obronie swojej pracy doktorskiej zdobył nagrodę Test of Time przyznaną przez sieć Association for Computing Machinery i grupa komunikacyjna, która honoruje wcześniejsze badania, które okazały się szczególnie wpływowe.
Dina Katabi i jej grupa pracują nad nowym urządzeniem do nawigacji w pomieszczeniach i śledzenia lokalizacji. Yorkshire terrier Katabi, Mica, służy jako obiekt w eksperymentach dotyczących dokładnego śledzenia za pomocą sygnałów bezprzewodowych. Szymon Simard
Powiedziałbym, że w pewnym sensie zmieniła standard publikowania w tej przestrzeni, mówi Clark. Po wykazaniu użyteczności teorii sterowania w zrozumieniu tych algorytmów, o wiele trudniej było pomyślnie opublikować artykuł bez użycia tego rodzaju analizy.
W 2003 roku, na mocy swojej pracy doktorskiej, MIT złapała Katabi jako młodszy członek wydziału. Jednym z jej pierwszych zajęć dydaktycznych podyplomowych były sieci teleinformatyczne, których uczyła z teoretykiem informacji Muriel Médard, profesorem Cecilem H. Greenem na wydziale elektrotechniki i informatyki.
W tym czasie Médard badał kodowanie sieciowe, które było wówczas jednym z najbardziej obiecujących nowych tematów w teorii informacji. W przypadku konwencjonalnego routingu internetowego pakiet danych przesyłany z komputera w Bostonie do komputera w Kalifornii wygląda dokładnie tak samo w dniu przyjazdu, jak w dniu wyjazdu. Wszystkie bity znajdują się w tym samym miejscu. Każdy pakiet podąża również jedną, określoną trasą przez sieć. Ale jeśli jedno z łączy na tej trasie jest martwe, pakiet po prostu nie przejdzie.
W przypadku kodowania sieciowego dany router w sieci zamiast tego mieszałby zawartość pakietów, które otrzymuje w pewnym oknie czasowym, wysyłając połączone pakiety przez wszystkie dostępne łącza. Jeśli pakiety zostaną zatrzymane na przeciążonym routerze, router może je po prostu odrzucić; każdy odbiorca może następnie wyodrębnić informacje przeznaczone tylko dla niego, identyfikując nakładanie się hybrydyzowanych pakietów przybywających innymi trasami.
Médard i współpracownicy opracowali eleganckie dowody matematyczne, z których wynika, że kodowanie sieciowe powinno zwiększyć pojemność sieciową danych. Ale to Katabi, pracując z Médardem, doktorantami z własnej grupy Katabi i badaczami z University of Cambridge, zademonstrowali pierwszą praktyczną implementację kodowania sieciowego, testując ją w sieci routerów Wi-Fi pokrywających dwa piętra MIT Centrum Stata. Odkryli, że ich protokoły trzykrotnie zwiększyły przepustowość sieci.
W 2011 roku Katabi i Médard założyli firmę Code On Technologies, aby skomercjalizować swoje prace nad kodowaniem sieci. Od tamtej pory Code On nawiązało współpracę z ośmioma innymi firmami bezprzewodowymi, aby rozpocząć budowę infrastruktury, która umożliwi użytkownikom Wi-Fi korzystanie z kodowania sieciowego. W testach wykazali, że ich system jest nawet pięć razy szybszy niż konwencjonalna sieć Wi-Fi.
Jednak myślenie o tym, jak zrealizować eleganckie abstrakcje kodowania sieciowego, zwróciło uwagę Katabi na jeden z podstawowych problemów sieci bezprzewodowych: zakłócenia. Jeśli pobliskie urządzenia bezprzewodowe transmitują w tym samym czasie, ich sygnały zakłócają się nawzajem, tworząc coś, co inżynierowie nazywają kolizją. W tradycyjnej sieci bezprzewodowej kolizja spowodowałaby, że oba sygnały byłyby nieczytelne, więc inżynierowie potraktowali zakłócenia jako coś, czego należy unikać. Badania Katabiego wprowadziły filozoficzną zmianę w postrzeganiu zakłóceń. Ona i jej uczniowie nie tylko pokazali, jak zrekonstruować przesyłane informacje w obecności kolizji, ale byli również w stanie wykorzystać zakłócenia w celu zwiększenia szybkości transmisji danych w sieciach bezprzewodowych.
W swojej pracy magisterskiej Katabi przeanalizowała sieci komunikacyjne na poziomie pakietów przechodzących przez nie. Mówi, że jej praca z Médardem polegała na przejściu poza pakiet do pojedynczego kawałka. I w tym momencie to było jak, po co się na tym zatrzymywać? Dlaczego nie zejdziemy poniżej tego i nie pójdziemy na sygnał?
Następnie wykorzystanie fizycznych właściwości sygnałów bezprzewodowych do wspomagania obliczeń wykonywanych wcześniej na poziomie bitu stało się tematem pracy Katabi. Jednym z głośnych przykładów było dekodowanie zygzakiem, które zdobyło nagrodę za najlepszy papier na Sigcomm 2008, głównej konferencji grupy sieciowej i komunikacyjnej ACM. (Laboratorium Katabi ponownie zdobyłoby nagrodę trzy lata później za system, który zapobiega manipulowaniu przy dostępnych bezprzewodowo implantach medycznych, takich jak rozruszniki serca i defibrylatory).
Po prostu zdecydowałem: „Nie mogę żyć bez matematyki”.
W swoim artykule dotyczącym dekodowania zygzakowatego Katabi i jej uczniowie opisali algorytmy, które analizują kolejne kolizje tych samych transmisji i identyfikują w jednej z nich odcinek sygnału, który pochodzi tylko od jednego nadawcy. Następnie odejmują ten sygnał od drugiej kolizji, odzyskując część transmisji od drugiego nadawcy, którą odejmują od pierwszej kolizji, odzyskując część transmisji z pierwszego sygnału i tak dalej, zygzakiem między kolizjami. Chociaż proces dekodowania jest złożony, naukowcy byli w stanie wykazać, że wykorzystuje on przepustowość wydajniej niż inne rozwiązania problemu kolizji.
W 2012 r. algorytm, który Katabi pomógł opracować do obliczania transformaty Fouriera, która jest niezbędna w wielu zadaniach przetwarzania sygnałów, został nazwany jednym z Przegląd technologii MIT 10 przełomowych technologii. Ta praca była w pewnym sensie odwrotnością procesu, który wyprowadził ją od teoretycznych abstrakcji kodowania sieciowego do fizycznych właściwości fal elektromagnetycznych. Jedna z jej uczennic zastanawiała się nad praktycznym problemem rozplątywania sygnałów wysyłanych na różnych częstotliwościach w tym samym czasie. Jeśli znasz częstotliwości z góry, możesz łatwo odfiltrować te, które Cię nie interesują: tak działa radio FM. Ale co, jeśli nie znasz wcześniej częstotliwości?
Po tym, jak Katabi i jej uczeń zaprojektowali wysoce wydajny algorytm dla tego problemu, zdali sobie sprawę, że ich rozwiązanie może pomóc w przyspieszeniu obliczeń transformaty Fouriera, która rozbija sygnał złożony na jego częstotliwości składowe. Opracowana pierwotnie do analizy wymiany ciepła, transformata Fouriera jest szeroko stosowana nie tylko w przetwarzaniu sygnałów, ale także w kompresji danych, analizie finansowej i rozwiązywaniu równań różniczkowych.
Współpracując z Piotrem Indykiem, innym informatykiem z MIT, Katabi opracował algorytm, który po raz pierwszy od lat 60. XX wieku zwiększa szybkość obliczania transformaty Fouriera. Algorytm działa tylko w określonym zakresie przypadków, ale w tych przypadkach przyspieszenie może być dramatyczne — nawet dziesięciokrotne. Oprócz umożliwienia szybkiej kompresji terabajtów danych, mówi Katabi, algorytm może być przydatny w zaawansowanej technologii MRI, grafice, astronomii, spektroskopii i metodach badania struktury białek za pomocą magnetycznego rezonansu jądrowego.
W ostatnich latach Katabi bada medyczne zastosowania technologii bezprzewodowych. Jej nagradzany system ochrony bezprzewodowych implantów medycznych obejmuje drugie urządzenie bezprzewodowe, zwane tarczą, które w zasadzie można nosić jako zegarek lub wisiorek. Tarcza blokuje nieautoryzowane próby dostępu do implantu, ale przekazuje transmisje wykorzystujące odpowiedni klucz kryptograficzny. W nagłych wypadkach lekarz może po prostu zdjąć osłonę, aby przesłać nowe instrukcje do implantu.
Katabi i jej uczniowie zbadali również nowe zastosowanie fal radiowych o częstotliwości Wi-Fi: obrazowanie. W swoich wstępnych wynikach wykazali, że mogą wykrywać ruch nawet przez obiekty stałe. Ale ostatnio pokazali, że wyrafinowane przetwarzanie sygnałów radiowych o bardzo niskiej mocy może mierzyć częstość oddechów człowieka, a nawet tętno, z odległości kilkudziesięciu metrów.
Naukowcy założyli firmę o nazwie Emerald, aby opracować medyczne zastosowania tej technologii, takie jak zdalne monitorowanie parametrów życiowych w celu wykrycia początku choroby u osób starszych. Produkt Emerald może również ostrzegać opiekunów w przypadku upadku pacjenta. W sierpniu 2015 r. Katabi i reszta zespołu Emerald zostali zaproszeni do Gabinetu Owalnego, aby zademonstrować system prezydentowi Obamie.
Potencjalne zastosowania medyczne jej najnowszej pracy dają Katabi poczucie, że zatoczyła koło na pierwszym roku studiów w Damaszku. Nie wróciła jednak do Syrii od wybuchu wojny domowej. Jej rodzice mają amerykańskie paszporty i mogą wyjechać w dowolnym momencie. Ale nie zrobią tego.
Zadzwonię do nich, a oni powiedzą: „Och, nie martw się – teraz jest bardzo normalnie, w nocy są tylko eksplozje, ale przeważnie dzień jest w porządku” – mówi. O czym mówisz? To normalne? Cały czas się o nich martwię. Ale ich przyjaciele wciąż tam są. Tam jest ich życie.
Chociaż Katabi nie widuje swoich rodziców tak często, jak kiedyś, istnieją aspekty ich osobowości, które uważa za nieuniknione. Myślę, że mam najgorsze z mojej mamy i taty – rzeczy, których po prostu nienawidziłam w nich, mówi. Mam niecierpliwość mojej mamy i jestem bardzo ognisty, i czego chcę, chcę.
A od jej ojca? Dostałam od niego, że jestem pracoholiczką, mówi. Nie przeszkadza mi to, ale ludzie wokół mnie mogą.