211service.com
Signalintelligens
MacArthur Fellow Dina Katabi, SM ’98, PhD ’03, utnyttjar fysiska egenskaper hos radiovågor för att göra beräkningen mer effektiv. 20 oktober 2015
1989 gjorde Dina Katabi, SM ’98, PhD ’03, liksom alla syriska gymnasieålder, ett standardiserat test som skulle avgöra vilka utbildningar hon var behörig till vid universitetet. Hon slutade sexa i nationen.
Det innebar att hon var på väg till medicinsk utbildning - den mest prestigefyllda grundutbildningen, endast tillgänglig för studenterna med de högsta poängen på provet. Dessutom, säger hon, kommer jag från en familj som bara är läkare. Min far är läkare, de flesta av mina mostrar och farbröder är läkare, min farfar är läkare – det finns så många läkare på båda sidor. Så det var vägen för mig.
Men efter ett års studier, under vilket hon var överst i sin klass, fick Katabi en uppenbarelse. Jag bestämde mig bara, 'Jag kan inte leva utan matematik', säger hon. Så hon gick över till den mindre prestigefyllda läroplanen för elektroteknik vid Damaskus universitet. Det var ett stort bråk med mina föräldrar, säger hon.
Tjugofem år senare ser det ut som ett ganska bra beslut: Katabi, numera Andrew (1956) och Erna Viterbi professor i elektroteknik och datavetenskap och medlem av Computer Science and Artificial Intelligence Lab (CSAIL), är i tredje året av ett genistipendium från MacArthur och precis tillbaka från att presentera några av sitt nya arbete för president Obama i Vita huset. Nätverksprotokoll baserade på hennes arbete har hittat sin väg till kommersiella produkter, och hennes innovativa omtolkning av problemet med radiofrekvensstörningar förändrar hur ingenjörer designar trådlösa nätverk. Men det betyder inte att hennes föräldrars motstånd var ogrundat. Medicin var inte bara det mer uppskattade yrket i Syrien, utan det erbjöd också många fler sysselsättningsmöjligheter där och drog till sig ett större antal kvinnor.
Det syriska samhället på den tiden var ganska liberalt, säger Katabi. Men trots det var hennes föräldrar oroliga för att gå in i ett yrke med en låg andel kvinnor skulle göra hennes liv svårare. Det är något som även i USA känner vi inom vissa områden, säger hon. Katabi uppskattar att endast 10 till 15 procent av hennes klasskamrater inom elektroteknik var kvinnor.
Efter att ha tagit examen – återigen, i toppen av sin klass – kom Katabi till USA för forskarskola, och följde i sin fars fotspår, som hade kommit för sin medicinska specialisering. Efter att ha tagit en magisterexamen i datavetenskap vid MIT, skrev hon in sig på doktorandprogrammet, under ledning av David Clark, en senior forskare vid Laboratory for Computer Science (som sedan dess har gått samman med Artificial Intelligence Laboratory för att producera CSAIL) och, under större delen av 1980-talet, Internets främsta protokollarkitekt.
Det blev väldigt snabbt klart att hon skulle göra ett enastående arbete, säger Clark. Hon hade en mycket utpräglad bakgrund, eftersom hon hade utbildning i både elektroteknik och datavetenskap, så hon hade ett bredare spektrum av färdigheter än många datavetenskapsstudenter, och det lät henne ta sig an en annan uppsättning problem.
Katabis avhandling handlade om nätverksprotokoll, Clarks expertområde, men hon tog ett ovanligt tillvägagångssätt. Ett centralt problem i nätverkshantering är överbelastningskontroll – att strypa tillbaka överföringar när de hotar att strypa nätverket. Internets mekanism för kontroll av överbelastning var för varje dator att övervaka sina egna överföringar och, om den upptäckte tecken på överbelastning, att ensidigt minska sin överföringshastighet.
Det tillvägagångssättet verkade fungera i praktiken, men det hade inte en särskilt säker teoretisk grund. Katabi importerade principer från styrteori, som analyserar beteendet hos stora dynamiska system, till nätverksprotokolldesign. Genom att använda dessa principer kunde hon och hennes medarbetare inte bara designa bättre mekanismer för överbelastningskontroll utan också ge matematisk garanti för att de skulle fungera i stor skala.
Cisco, världens största tillverkare av nätverksutrustning, har sedan dess införlivat en del av Katabis arbete med överbelastningskontroll i en av sina produkter, och 12 år efter att hon disputerade vann den Test of Time-priset från Association for Computing Machinerys nätverk och kommunikationsgrupp, som hedrar tidigare forskning som har visat sig vara särskilt inflytelserik.
Dina Katabi och hennes grupp har arbetat på en ny enhet för inomhusnavigering och platsspårning. Katabis Yorkshire terrier, Mica, fungerar som ämne i experiment med exakt spårning med trådlösa signaler. Simon Simard
Jag skulle säga att hon i någon mening ändrade standarden för vad som krävs för att publicera i det här utrymmet, säger Clark. Efter att hon visat nyttan av kontrollteori för att förstå dessa algoritmer, blev det mycket svårare att framgångsrikt publicera ett dokument utan att använda den typen av analys.
År 2003, på grund av sin avhandling, tog MIT upp Katabi som en juniorfakultetsmedlem. En av hennes första forskarutbildningsuppdrag var Data Communication Networks, som hon undervisade med informationsteoretikern Muriel Médard, Cecil H. Green-professorn i elektroteknik och datavetenskap.
Vid den tiden hade Médard undersökt nätverkskodning, som då var ett av de mest lovande nya ämnena inom informationsteori. Med konventionell Internet-routing, om ett datapaket går från en dator i Boston till en dator i Kalifornien, ser det exakt likadant ut vid ankomsten som det gjorde vid avresan. Alla bitar är på samma plats. Varje paket följer också en enda, bestämd väg genom nätverket. Men om en av länkarna längs den vägen är död kommer paketet helt enkelt inte att gå igenom.
Med nätverkskodning skulle en given router i nätverket istället blanda ihop innehållet i paket den tar emot inom ett visst tidsfönster, och skicka de kombinerade paketen ut över alla tillgängliga länkar. Om paket hålls kvar vid en överbelastad router kan routern helt enkelt släppa dem; varje mottagare kan sedan extrahera informationen som bara är avsedd för den genom att identifiera överlappningen i hybridiserade paket som anländer över andra rutter.
Médard och kollegor hade utarbetat eleganta matematiska bevis som slog fast att nätverkskodning skulle öka nätverkens datakapacitet. Men det var Katabi, som arbetade med Médard, doktorander i Katabis egen grupp och forskare vid University of Cambridge, som demonstrerade den första praktiska implementeringen av nätverkskodning, och testade det på ett nätverk av Wi-Fi-routrar som täcker två våningar av MIT:s Stata Center. De upptäckte att deras protokoll ökade nätverkets kapacitet tre gånger.
2011 grundade Katabi och Médard ett företag, Code On Technologies, för att kommersialisera sitt arbete med nätverkskodning. Code On har sedan dess samarbetat med åtta andra trådlösa företag för att börja bygga infrastrukturen som gör det möjligt för Wi-Fi-användare att dra nytta av nätverkskodning, och i tester har de visat att deras system är så mycket som fem gånger så snabbt som en konventionella Wi-Fi-nätverk.
Att fundera på hur man förverkliga de eleganta abstraktionerna av nätverkskodning hade dock uppmärksammat Katabis på ett av de grundläggande problemen med trådlösa nätverk: störningar. Om trådlösa enheter i närheten sänder samtidigt, stör deras signaler varandra, vilket skapar vad ingenjörer kallar en kollision. I ett traditionellt trådlöst nätverk skulle en kollision göra båda signalerna oförståeliga, så ingenjörer har behandlat störningar som något som bör undvikas. Katabis forskning introducerade ett filosofiskt skifte i hur interferens uppfattas. Hon och hennes elever har inte bara visat hur man rekonstruerar överförd information i närvaro av kollisioner, de har också kunnat utnyttja störningar för att öka datahastigheterna i trådlösa nätverk.
För sin avhandling hade Katabi analyserat kommunikationsnätverk i nivå med paketen som färdades över dem. Hennes arbete med Médard gick liksom bortom paketet till den individuella biten, säger hon. Och vid den tidpunkten var det som, varför stanna vid biten? Varför går vi inte under det och går till signalen?
Därefter blev det ett tema för Katabis arbete att använda de fysiska egenskaperna hos trådlösa signaler för att stödja beräkningar som tidigare utförts på bitnivån. Ett högprofilerat exempel var sicksackavkodning, som vann priset för bästa papper vid Sigcomm 2008, huvudkonferensen för ACM-nätverket och kommunikationsgruppen. (Katabis labb skulle vinna priset igen tre år senare, för ett system som förhindrar manipulering av trådlöst tillgängliga medicinska implantat som pacemakers och defibrillatorer.)
Jag bestämde mig bara, 'Jag kan inte leva utan matematik.'
I sin artikel om sicksackavkodning beskrev Katabi och hennes elever algoritmer som analyserar på varandra följande kollisioner av samma sändningar och identifierar, i en av dem, en signalsträcka som kommer från endast en avsändare. Sedan subtraherar de den signalen från den andra kollisionen, återställer en del av överföringen från den andra sändaren, som de subtraherar från den första kollisionen, återställer en del av överföringen från den första signalen, och så vidare, sicksackande fram och tillbaka mellan kollisioner. Även om avkodningsprocessen är komplex, kunde forskarna visa att den använde bandbredden mer effektivt än andra lösningar på kollisionsproblemet.
År 2012 utsågs en algoritm som Katabi hjälpte till att utveckla för att beräkna Fouriertransformen, som är nödvändig för en mängd signalbehandlingsuppgifter, till en av MIT Technology Review 10 banbrytande teknologier. Det arbetet var på sätt och vis motsatsen till den process som ledde henne från de teoretiska abstraktionerna av nätverkskodning till de fysiska egenskaperna hos elektromagnetiska vågor. En av hennes elever funderade på det praktiska problemet med hur man reda ut signaler som skickas med olika frekvenser samtidigt. Om du känner till frekvenserna i förväg är det lätt att filtrera bort de du inte är intresserad av: det är så FM-radio fungerar. Men vad händer om du inte känner till frekvenserna i förväg?
Efter att Katabi och hennes elev hade designat en mycket effektiv algoritm för detta problem, insåg de att deras lösning kunde hjälpa till att påskynda beräkningen av Fourier-transformen, som bryter en sammansatt signal i dess ingående frekvenser. Ursprungligen utformad för analys av värmeöverföring, används Fourier-transformen i stor utsträckning inte bara i signalbehandling utan i datakomprimering, finansiell analys och lösning av differentialekvationer.
I samarbete med Piotr Indyk, en annan MIT-datavetare, utvecklade Katabi en algoritm som för första gången sedan 1960-talet ökar hastigheten med vilken Fouriertransformen kan beräknas. Algoritmen fungerar bara i ett specifikt område av fall, men i dessa fall kan hastighetshöjningen vara dramatisk – upp till tiofaldig. Förutom att göra det möjligt att snabbt komprimera terabyte av data, säger Katabi, kommer algoritmen sannolikt att vara användbar för avancerad MRI-teknik, grafik, astronomi, spektroskopi och metoder för att studera proteinstruktur med kärnmagnetisk resonans.
Under de senaste åren har Katabi utforskat medicinska tillämpningar av trådlös teknologi. Hennes prisbelönta system för att skydda trådlösa medicinska implantat involverar en andra trådlös enhet, kallad en sköld, som i princip kan bäras som en klocka eller hänge. Skölden blockerar obehöriga försök att komma åt implantatet, men den vidarebefordrar överföringar som använder lämplig kryptonyckel. I en nödsituation kan en läkare helt enkelt ta bort skölden för att skicka nya instruktioner till implantatet.
Katabi och hennes elever har också utforskat en ny användning av Wi-Fi-frekvensradiovågor: bildbehandling. I sina första resultat visade de att de kunde upptäcka rörelse även genom fasta föremål. Men på senare tid har de visat att sofistikerad bearbetning av radiosignaler med ultralåg effekt kan mäta mänskliga andningsfrekvenser, och till och med hjärtfrekvenser, från dussintals meter bort.
Forskarna grundade ett företag, kallat Emerald, för att utveckla medicinska tillämpningar av tekniken, såsom fjärrövervakning av vitala tecken för att upptäcka uppkomsten av sjukdom hos äldre. Emeralds produkt kan också varna vårdgivare om en patient faller. I augusti 2015 bjöds Katabi och resten av Emerald-teamet in till Oval Office för att demonstrera systemet för president Obama.
De potentiella medicinska tillämpningarna av hennes senaste arbete ger Katabi en känsla av att ha fullbordat sitt första år på college i Damaskus. Hon har dock inte varit tillbaka till Syrien sedan inbördeskriget bröt ut. Hennes föräldrar har amerikanska pass och kan lämna när som helst. Men det kommer de inte.
Jag ringer dem och de kommer att säga: 'Åh, oroa dig inte - nu är det väldigt normalt, det är bara explosioner på natten, men mestadels är dagen bra', säger hon. Vad pratar du om? Det är normalt? Jag oroar mig för dem hela tiden. Men deras vänner är kvar. Deras liv finns där.
Även om Katabi inte ser sina föräldrar lika mycket som hon brukade, finns det aspekter av deras personligheter som hon finner oundvikliga. Jag tror att jag fick det värsta av min mamma och min pappa – de saker jag bara hatade i dem, säger hon. Jag har min mammas otålighet, och jag är väldigt eldig, och det jag vill vill jag ha.
Och från hennes far? Jag fick av honom att jag är arbetsnarkoman, säger hon. Jag har inget emot det, men människor runt mig kanske.