Signal intelligens

MacArthur Fellow Dina Katabi, SM ’98, PhD ’03, udnytter radiobølgers fysiske egenskaber for at gøre beregningen mere effektiv. Ved

• Larry Hardesty arkiv side

20. oktober 2015

I 1989 tog Dina Katabi, SM ’98, PhD ’03, ligesom alle syriske gymnasieelever, en standardiseret test, der skulle afgøre, hvilke uddannelser hun var berettiget til på universitetet. Hun sluttede på sjettepladsen i nationen.

Det betød, at hun var på vej til medicinsk uddannelse - den mest prestigefyldte bacheloruddannelse, kun tilgængelig for de studerende med de højeste karakterer på eksamen. Desuden, siger hun, kommer jeg fra en familie, der udelukkende er læger. Min far er læge, de fleste af mine tanter og onkler er læger, min bedstefar er læge - der er så mange læger på begge sider. Så det var vejen for mig.

Men efter et års studier, hvor hun var på toppen af ​​sin klasse, fik Katabi en åbenbaring. Jeg besluttede bare: 'Jeg kan ikke leve uden matematik,' siger hun. Så hun overgik til det mindre prestigefyldte pensum for elektroingeniør ved Damaskus Universitet. Det var en stor kamp med mine forældre, siger hun.

Femogtyve år senere ligner det en ret god beslutning: Katabi, nu Andrew (1956) og Erna Viterbi professor i elektroteknik og datalogi og medlem af Computer Science and Artificial Intelligence Lab (CSAIL), er i tredje år af en MacArthur geni-legat og lige tilbage fra at præsentere noget af sit nye værk for præsident Obama i Det Hvide Hus. Netværksprotokoller baseret på hendes arbejde har fundet vej til kommercielle produkter, og hendes innovative genfortolkning af problemet med radiofrekvensinterferens ændrer den måde, ingeniører designer trådløse netværk på. Men det betyder ikke, at hendes forældres modstand var ubegrundet. Ikke alene var medicin det mere højt skattede erhverv i Syrien, men det tilbød også mange flere beskæftigelsesmuligheder der og tiltrak et større antal kvinder.

Det syriske samfund på det tidspunkt var ret liberalt, siger Katabi. Men alligevel var hendes forældre bekymrede for, at det ville gøre hendes liv sværere at gå ind i et erhverv med en lav procentdel af kvinder. Det er noget, som vi selv i USA føler på visse områder, siger hun. Katabi anslår, at kun 10 til 15 procent af hendes klassekammerater i elektroteknik var kvinder.

Efter at have afsluttet sin eksamen – igen i toppen af ​​sin klasse – kom Katabi til USA for at studere, og fulgte i sin fars fodspor, som var kommet for at få sin medicinske specialisering. Efter at have opnået en mastergrad i datalogi ved MIT, tilmeldte hun sig ph.d.-programmet under vejledning af David Clark, en seniorforsker ved Laboratory for Computer Science (som siden er fusioneret med Artificial Intelligence Laboratory for at producere CSAIL) og, i det meste af 1980'erne, internettets hovedprotokolarkitekt.

Det blev meget hurtigt klart, at hun ville gøre noget fremragende arbejde, siger Clark. Hun havde en meget karakteristisk baggrund, fordi hun havde en uddannelse i både elektroteknik og datalogi, så hun havde en bredere vifte af kompetencer end mange datalogistuderende, og det lod hende løfte en anden række problemer.

Katabis afhandling handlede om netværksprotokoller, Clarks ekspertiseområde, men hun tog en usædvanlig tilgang. Et centralt problem i netværksstyring er overbelastningskontrol - at drosle tilbage transmissioner, når de truer med at kvæle netværket. Internettets overbelastningskontrolmekanisme var for hver computer at overvåge sine egne transmissioner og, hvis den opdagede tegn på overbelastning, ensidigt reducere sin transmissionshastighed.

Den tilgang så ud til at fungere i praksis, men den havde ikke et særlig sikkert teoretisk fundament. Katabi importerede principper fra kontrolteori, som analyserer opførsel af store dynamiske systemer, til netværksprotokoldesign. Ved at bruge disse principper kunne hun og hendes samarbejdspartnere ikke kun designe bedre overbelastningskontrolmekanismer, men også give matematisk sikkerhed for, at de ville fungere i stor skala.

Cisco, verdens største producent af netværksudstyr, har siden inkorporeret noget af Katabis arbejde med overbelastningskontrol i et af sine produkter, og 12 år efter hun forsvarede sin afhandling, vandt det Test of Time-prisen fra Association for Computing Machinerys netværk og kommunikationsgruppe, som hædrer tidligere forskning, der har vist sig særlig indflydelsesrig.

Dina Katabi og hendes gruppe har arbejdet på en ny enhed til indendørs navigation og lokationssporing. Katabis Yorkshire terrier, Mica, tjener som emne i eksperimenter med nøjagtig sporing med trådløse signaler. Simon Simard

Jeg vil sige, at hun på en eller anden måde flyttede standarden for, hvad der skal til for at udgive i dette rum, siger Clark. Efter at hun demonstrerede nytten af ​​kontrolteori til at forstå disse algoritmer, blev det meget sværere at udgive et papir uden at bruge den slags analyser.

I 2003, i kraft af sin afhandling, fik MIT Katabi optaget som juniorfakultetsmedlem. En af hendes første kandidatundervisningsopgaver var Data Communication Networks, som hun underviste sammen med informationsteoretikeren Muriel Médard, Cecil H. Green-professor i elektroteknik og datalogi.

På det tidspunkt havde Médard undersøgt netværkskodning, som dengang var et af de mest lovende nye emner inden for informationsteori. Med konventionel internet-routing, hvis en pakke med data rejser fra en computer i Boston til en computer i Californien, ser den præcis det samme ud ved ankomsten, som den gjorde ved afgang. Alle bits er på samme sted. Hver pakke følger også en enkelt, bestemt rute gennem netværket. Men hvis et af linkene langs den rute er dødt, vil pakken simpelthen ikke gå igennem.

Med netværkskodning ville en given router i netværket i stedet blande indholdet af pakker, den modtager inden for et tidsrum, og sende de kombinerede pakker ud over alle de tilgængelige links. Hvis pakker bliver holdt op ved en overbelastet router, kan routeren blot droppe dem; hver modtager kan derefter udtrække den information, der kun er beregnet til den, ved at identificere overlapningen i hybridiserede pakker, der ankommer over andre ruter.

Médard og kolleger havde udtænkt elegante matematiske beviser, der fastslår, at netværkskodning skulle øge netværks datakapacitet. Men det var Katabi, der arbejdede sammen med Médard, kandidatstuderende i Katabis egen gruppe og forskere ved University of Cambridge, der demonstrerede den første praktiske implementering af netværkskodning, idet de testede det på et netværk af Wi-Fi-routere, der dækker to etager af MIT's. Stata Center. De fandt ud af, at deres protokoller øgede netværkets kapacitet tre gange.

I 2011 grundlagde Katabi og Médard et firma, Code On Technologies, for at kommercialisere deres arbejde med netværkskodning. Code On har siden indgået partnerskab med otte andre trådløse virksomheder for at begynde at bygge infrastrukturen, der vil gøre det muligt for Wi-Fi-brugere at drage fordel af netværkskodning, og i test har de vist, at deres system er så meget som fem gange så hurtigt som en konventionelt Wi-Fi-netværk.

At tænke på, hvordan man kan realisere de elegante abstraktioner af netværkskodning, havde imidlertid trukket Katabis opmærksomhed på et af de grundlæggende problemer ved trådløse netværk: interferens. Hvis trådløse enheder i nærheden sender samtidig, interfererer deres signaler med hinanden og producerer, hvad ingeniører kalder en kollision. I et traditionelt trådløst netværk ville en kollision gøre begge signaler uforståelige, så ingeniører har behandlet interferens som noget, der skal undgås. Katabis forskning introducerede et filosofisk skift i, hvordan interferens opfattes. Ikke alene har hun og hendes elever vist, hvordan man rekonstruerer transmitteret information i nærvær af kollisioner, de har også været i stand til at udnytte interferens for at øge datahastighederne på trådløse netværk.

Til sin afhandling havde Katabi analyseret kommunikationsnetværk på niveau med de pakker, der rejste over dem. Hendes arbejde med Médard bevægede sig på en måde ud over pakken til den enkelte bit, siger hun. Og på det tidspunkt var det sådan, hvorfor stoppe ved lidt? Hvorfor går vi ikke under det og går til signalet?

Derefter blev det et tema for Katabis arbejde at bruge de fysiske egenskaber af trådløse signaler til at understøtte beregninger, der tidligere er udført på bitniveau. Et højt profileret eksempel var zigzag-afkodning, som vandt prisen for bedste papir ved 2008 Sigcomm, hovedkonferencen for ACM-netværks- og kommunikationsgruppen. (Katabis laboratorium ville vinde prisen igen tre år senere for et system, der forhindrer manipulation med trådløst tilgængelige medicinske implantater såsom pacemakere og defibrillatorer.)

Jeg besluttede bare, 'Jeg kan ikke leve uden matematik.'

I deres papir om zigzag-afkodning beskrev Katabi og hendes elever algoritmer, der analyserer successive kollisioner af de samme transmissioner og identificerer, i en af ​​dem, et signalstykke, der kun kommer fra én afsender. Så trækker de signalet fra den anden kollision, genvinder en del af transmissionen fra den anden afsender, som de trækker fra den første kollision, genopretter en del af transmissionen fra det første signal og så videre, zigzaggende frem og tilbage mellem kollisioner. Selvom afkodningsprocessen er kompleks, var forskerne i stand til at vise, at den brugte båndbredde mere effektivt end andre løsninger på kollisionsproblemet.

I 2012 blev en algoritme Katabi var med til at udvikle til beregning af Fourier-transformationen, som er essentiel for en lang række signalbehandlingsopgaver, udnævnt til en af MIT Technology Review 10 banebrydende teknologier. Det arbejde var på en måde det omvendte af den proces, der førte hende fra de teoretiske abstraktioner af netværkskodning til de fysiske egenskaber af elektromagnetiske bølger. En af hendes elever overvejede det praktiske problem med, hvordan man adskiller signaler sendt ved forskellige frekvenser på samme tid. Hvis du kender frekvenserne på forhånd, er det nemt at filtrere dem fra, du ikke er interesseret i: det er sådan FM-radio fungerer. Men hvad hvis du ikke kender frekvenserne på forhånd?

Efter at Katabi og hendes elev havde designet en meget effektiv algoritme til dette problem, indså de, at deres løsning kunne hjælpe med at fremskynde beregningen af ​​Fourier-transformationen, som opdeler et sammensat signal i dets konstituerende frekvenser. Oprindeligt udtænkt til analyse af varmeoverførsel, er Fourier-transformationen udbredt, ikke kun i signalbehandling, men i datakomprimering, finansiel analyse og løsning af differentialligninger.

I samarbejde med Piotr Indyk, en anden MIT-computerforsker, udviklede Katabi en algoritme, der for første gang siden 1960'erne øger hastigheden, hvormed Fourier-transformationen kan beregnes. Algoritmen virker kun i en specifik række tilfælde, men i disse tilfælde kan hastigheden være dramatisk - op til det tidobbelte. Ud over at gøre det muligt at komprimere terabytes af data hurtigt, siger Katabi, vil algoritmen sandsynligvis være nyttig til avanceret MR-teknologi, grafik, astronomi, spektroskopi og metoder til at studere proteinstruktur med kernemagnetisk resonans.

I de seneste år har Katabi udforsket medicinske anvendelser af trådløse teknologier. Hendes prisvindende system til beskyttelse af trådløse medicinske implantater involverer en anden trådløs enhed, kaldet et skjold, der i princippet kan bæres som et ur eller vedhæng. Skjoldet blokerer uautoriserede forsøg på at få adgang til implantatet, men det videresender transmissioner, der bruger den passende kryptografiske nøgle. I en nødsituation kunne en læge blot fjerne skjoldet for at sende nye instruktioner til implantatet.

Katabi og hendes elever har også udforsket en ny brug af Wi-Fi-frekvens radiobølger: billeddannelse. I deres første resultater demonstrerede de, at de kunne detektere bevægelse selv gennem faste genstande. Men for nylig har de vist, at sofistikeret behandling af radiosignaler med ultralav effekt kan måle menneskelige åndedrætsfrekvenser, og endda hjertefrekvenser, fra snesevis af meter væk.

Forskerne grundlagde et firma, kaldet Emerald, for at udvikle medicinske anvendelser af teknologien, såsom fjernovervågning af vitale tegn for at opdage begyndelsen af ​​sygdom hos ældre. Emeralds produkt kan også advare plejepersonale, hvis en patient falder. I august 2015 blev Katabi og resten af ​​Emerald-teamet inviteret til det ovale kontor for at demonstrere systemet for præsident Obama.

De potentielle medicinske anvendelser af hendes seneste arbejde giver Katabi følelsen af ​​at være kommet fuld cirkel til sit første år på college i Damaskus. Hun har dog ikke været tilbage til Syrien, siden borgerkrigen brød ud. Hendes forældre har amerikansk pas og kunne rejse når som helst. Men det vil de ikke.

Jeg ringer til dem, og de vil sige: 'Åh, bare rolig - nu er det meget normalt, der er kun eksplosioner om natten, men for det meste er dagen fin,' siger hun. Hvad snakker du om? er det normalt? Jeg bekymrer mig om dem hele tiden. Men deres venner er der stadig. Deres liv er der.

Selvom Katabi ikke ser sine forældre så meget som hun plejede, er der aspekter af deres personligheder, som hun finder uundgåelige. Jeg tror, ​​jeg fik det værste ved min mor og min far - de ting, jeg bare hadede i dem, siger hun. Jeg har min mors utålmodighed, og jeg er meget brændende, og hvad jeg vil, vil jeg have.

Og fra hendes far? Jeg fik fra ham, at jeg er arbejdsnarkoman, siger hun. Det gider jeg ikke, men det kan folk omkring mig.

skjule