Communicating viaFireflies: Geographic Routing onDuty-Cycled Sensors

-K --Cc E N Geographic routing isauseful andscalable point-to-point commuM nication primitive forwireless sensor networks. However, previous F workongeographic routing makestheunrealistic assumption that E allthenodes inthenetwork areawakeduring routing. Thisoverl Fl looks thecommondeployment scenario wheresensor nodesare LiH W J K duty-cycled tosaveenergy. Inthis paper weinvestigate several important aspects ofgeographic routing overduty-cycled nodes. First weextend existing geographic routing algorithms tohandle the Figutre :Geographic nrouting o n duty-cycled nodes. Eachlethighly dynamic networks resulting fromduty-cycling. Secondwe terrepresents asensor node;awakenodesareinboxes. Enprovide thefirst formal analysis oftheperformance ofgeographicroute from A otonD noe B mus decidetwewaitinfoC routing onduty-cycled nodes. Third, weusethis analysis tode- towakeuporroutigg thelongwayaroundtheobstacle (i.e., velop anefficient decentralized sleep scheduling algorithm forre- routing alogthepathB,B,G,I,L,1). ducing thenumber ofawakenodes while maintaining bothnetwork spatial queries [6]etc.Recent workongeographic routing [12 coverage anda(tunable) target routing latency. Finally, we evalu- 13]hasshownthat suchrouting canbedonequite efficiently even ateviasimulation theperformance ofourapproach versusruning inthepresence ofirregular radio ranges andlocalization errors. existing geographic routing algorithms onsensors duty-cycled ac- A keydrawback ofprevious workongeographic routing isthat cording toprevious sleep scheduling algorithms. Ourresults show, allexisting geographic routing algorithms andtheir analysis asperhaps surprisingly, that anetwork ofduty-cycled nodes canhave ...... ^ . . . su~~~~~~~tme azll thenodesinthenetwork azre azwake duiring rouiting. Howslightly better routing performance than astatic network that uses everinpractical deployments sensors areduty-cycled tosaveencomparable energy. Ourresults further showthatcompared topre- e 7 W v v v vious~~~~~~~~~~~~~~~ aloitm ou sle.ceuigagrih infcnlm