Scheduling communication in real-time sensor applications

HuanLi,PrashantShenoy,DepartmentofComputerScience,UniversityofMassachusetts,

KrithiRamamritham

Dept.ofComputerScienceandEngineering,

IndianInstituteofTechnology,Amherst,MA01003

lihuan,shenoy@cs.umass.edu

Abstract

Weconsideraclassofwirelesssensorapplications—suchasmobilerobotics—thatimposetimelinesscon-straints.Weassumethattheseapplicationsarebuiltus-ingcommodity802.11wirelessnetworksandfocusontheproblemofprovidingqualitatively-betterQoSduringnet-worktransmissionofsensordata.Ourtechniquesarede-signedtoexplicitlyavoidnetworkcollisionsandminimizethecompletiontimetotransmitasetofsensormessages.WearguethatthisproblemisNP-completeandpresentthreeheuristics,basedonedgecoloring,toachievethesegoals.Oursimulationsresultsshowthattheminimumweightcolorheuristicisrobusttoincreasesincommunicationdensityandyieldsresultsthatareclosetotheoptimalsolution.

1Introduction

Thedesignofwirelesssensorapplicationshasreceivedincreasedresearchattentioninrecentyears.Asensorappli-cationtypicallyincludesacollectionofsensorsthatcontin-uouslymonitorthesurroundingenvironmentandacollec-tionofsinksthataggregate,process,andreacttothesen-sorydata.Communicationbetweenthesensorsandsinksrequiresanetwork;sincetheinherentnatureofmanysensorapplicationsprecludestheuseofwirednetworks,wirelessnetworksarecommonlyusedinsuchapplications.

Inthiswork,weconsideraclassofwirelesssensorap-plicationsthatimposetimelinessconstraintsonthetrans-missionandprocessingofsensorydata.Werefertosuchapplicationsasreal-timesensorapplications.Anexampleofsuchanapplicationisateamofrobotssearchingforpeo-pletrappedinabuildingonfire.Eachrobotisequippedwithasetofsensorssuchastemperatureandpressuremon-itors,videocameras,GPS,andinfra-redmonitors.Notall

Mumbai400076,Indiakrithi@cse.iitb.ac.in

R1S1R2(Blocked)S3S2R3(Blocked)R4(Blocked)Figure1.Falseblockingproblem(blockingpropagatesfromtoto)

Inthispaper,weconsidertechniquestoavoidsuchprob-lemsinsensorapplications.Weexploitthespecificchar-acteristicsofsensorapplications,suchastheroboticssce-nario,todevisenetworktransmissiontechniquessothatcol-lisionsareexplicitlyavoidedandthetotaltimefortransmit-tingasetofmessagesisminimized(byparallelizingnon-interferingtransmissionstotheextentpossible).

WearguethattheproblemisNP-completeandpresentheuristicsbasedonedgecoloringtoaddressthisproblem.Wediscussmodificationstoourapproachtoincorporatetimelinessconstraints.Wealsopresentan-basedoptimalalgorithmtoenablecomparisonswithourheuristics.Weconductadetailedsimulationstudytoevaluateourheuris-ticsandfindthattheminimumweightcolorheuristicisro-busttoincreasesincommunicationdensityandyieldsre-sultsthatareclosetotheoptimalsolution.Inconjunc-tionwithclusteringandgroupingtechniques,webelievesuchcommunicationschedulingtechniquescanadaptwelltolargescalesensornetworks.

Therestofthispaperisstructuredasfollows.Section2presentsoursystemmodelandtheproblemformulation.Sections3and4presentouredgecoloring-basedheuristicsandtheoptimalsolution,respectively.Section5presentssimulationresults.Section6discusseshowourschemecanbeextendedtohandledeadlineconstraints.Section7presentsrelatedworkand,finally,Section8summarizesourwork.

2BackgroundandProblemFormulation

Inthissection,wepresentthesystemmodel,andthenformulatetheproblemofschedulingcommunicationinreal-timesensorapplications.

2.1SystemModel

Considerawirelesssensorapplicationwithnodes.Wedenotedesignatedsendernodesby.Eachnodehasawirelessnetworkandinterfacereceiverwithnodesacer-bytaintransmissionrange;dependingontheexactwirelessin-terfaceemployed(e.g.,802.11bversus802.11g),differentnodesmayhavedifferenttransmissionranges.Eachnodecanbeasenderorareceiverorboth,andnobase-stationsareassumedinthisenvironment.Anodeshouldbewithinthetransmissionrangeofasendertobeaneligiblereceiver,andallcommunicationisassumedtobeunicast.Thetermssourceandsenderaswellassinkandreceiverareusedin-terchangeablyinthispaper.

Thecommunicationmediumisassumedtobesharedbyallnodesinthesystem.Ifareceiveriswithintherangeofmultiplesenders,theninterferencemayhappenifmorethanonesenderattemptstotransmitsimultaneously.However,therewillbenointerferenceiftworeceiversaremutually

outsidetheothersender’srange.InFigure2,

isinthetransmissionrangeofsenderand;ifbothsendersat-tempttosimultaneouslycommunicatewiththeirreceivers,interferencemayoccur.Ontheotherhand,cantransmitmessagesinparallelwitheitheroftheothertransmissions.Inthiswork,weassumethatthelocationofeachnodeisknownatalltimes,andthusthenatureoftheoverlapcanbedeterminedforthepurposeofschedulingthenetworktransmissions.Thisisareasonableassumption,sinceintheroboticsexample,robotscarryGPSreceiversandcanaddi-tionallyuselocalizationalgorithms[10]topreciselydeter-minetheirlocations.

ObserveinFigure2thatsourceand.Suchascenariosendsdatamighttotwodifferentreceiversre-sultfromtheneedtotransmitdatafromdifferentsensorsonrobottodifferentrobots.Theunicastnatureofthecom-municationnecessitatesseparatemessagestoeachreceiver.Topreciselystatetheseassumptions,letdenotethatdenoteiswithinamessagethetransmissiontransmissionrangefromofto,and

.

Wehavefollowingsystemconstraints.

NetworkInterfaceConstraint:Atanyinstant,anodecanbeeitherasenderorareceiver,butnotboth.

RangeConstraint:Anodecanreceiveamessageonlyifitiswithinthesender’srange,i.e.,

.

InterferenceConstraint:Twosimultaneoustransmis-sionswillnotinterfereifandonlyifbothreceiversaremutuallyoutsidetheothersender’srange.Thatis,

.

S1R2R1R4S3S2R3Figure2.Acommunicationexample

UnicastConstraint:Eachmessagecanhaveonlyonerecipient.

Givenasetofsenders,receivers,theirlocationsandtransmissionranges,thecommunicationschedulermustde-termineatransmissionschedulesuchthattheabovecon-straintsaresatisfiedandthetimetocompletealltransmis-sionsisminimized(byparallelizingnon-interferingtrans-missions).WerefertothisproblemastheOptimalParallelCommunicationScheduling(OParCS)problem.

2.2CommunicationScheduler

Inthiswork,weassumeacentralizedschedulerforschedulingmessagetransmissions.Thisisareasonableas-sumptionforapplicationssuchasroboticssinceacentral-izedpathplannerisusedtodeterminethemovementforeachrobotaswellasforthewholegroup.Consequently,theschedulercanruninconjunctionwiththeplannertode-terminewheneachmessageshouldbetransmitted.

Theschedulercanbeinvokedperiodicallyorondemand(liketheschedulerstudiedinSpringSystem[11]).Uponeachinvocation,theschedulermustscheduleallmessagesthathavebecomereadyfortransmissionsincethepreviousinvocation(thus,anewlyarrivingmessagemustwaitun-tilthenextschedulinginstancebeforeitcanbescheduledfortransmission).Wheninvoked,theschedulerconsidersthecurrentschedule(i.e.,themessagesthatweresched-uledinapriorinvocationandareawaitingtransmission)andallnewlyarrivedmessagesateachnode.Twoapproachesarepossibleforgeneratinganewschedule.Inthefirstap-proach,theunsentmessagesandthenewmessagesarecon-sideredtocomputeanewschedule.Thesecondapproachisincremental—itdeterminesanewscheduleforthenewmessagesandappendsthatscheduletothecurrentsched-ule;theapproachessentiallyassignsatransmissiontimetoeachnewmessagewhilekeepingthecurrentscheduleun-changed.Ineithercase,thetransmissiontimesarethenconveyedtothecorrespondingsendernodes.

2.3Graph-basedRepresentationoftheProblem

Considerasetofmessagesthatareawaitingtransmis-sionatvariousnodes.Theschedulingproblemcanbefor-mulatedusingaweighted,directedgraph,inwhicheachvertexdenotesanodeinthesensorapplication,

andadirectededgefromvertex

toindicatesthatamessageneedstobesentfromto.Theweightoftheedgedenotesthetransmissioncost(time)andisafunc-tionofthemessagelength(andthetransmissionrate).Werefertothisgraphasthecommunicationgraph.Eachvertexisassociatedwithatransmissionrange,therefore,theinter-ferenceset,,includesallpairwiseedgesthatwillincurinterferenceifmessagesaretransmittedthroughthoseedgesatthesametime.Iftherangeofeachtransmis-sionisknowninadvance,wecanobtaintheinterferencesetbycheckingtheinterferenceconstraintsinpolynomialtime.Givensuchagraphandassociatedinterferenceset,theOParCSproblemcanbeformulatedasfollows.Input:Graph,aweightfunctionthatassignsapositiveweighttoeachedge,andtheinterferenceconstraintset.

Problem:FindapartitionofEintodisjointsets

suchthat,

1.,

2.donotshareacommonendpoint

in

,

3.

isminimized.

Thefirstconditionavoidsinterferenceduringmessagetransmissions,whilethesecondconditionaddressesthenet-workinterfaceandunicastconstraints;therangeconstraintisimpliedintheinput.

Proposition1:TheOParCSproblemisNP-complete.TheproblemisNP-completeevenifallweightsareequal.Theproofisgivenin[7].

3HeuristicCommunicationScheduling

Considerasimplifiedversionoftheproblemwhereallmessagesareofequallength(edgeweightsarenormalizedto1)andthereisnointerferencebetweenanyofthemes-sages.Inthiscase,theonlyconstraintisthatalladjacentedges(sharingacommonendpoint)cannotbescheduledsimultaneously.Sinceanedgecoloringofagraphisanassignmentofcolorstotheedgessuchthatadjacentedgesreceivedistinctcolors,wecancolortheedgessothatedgeswiththesamecolorcanbescheduledsimultaneously.Inthissimplifiedversion,thenumberofcolorsintheedgecoloringisequivalenttothetimeslotstakentoschedulethetransmission.However,determiningtheminimumnumberofcolorsisalsoNP-Complete[5].

Inthissection,weproposepolynomialtimeheuristicsfortheOParCSproblem.Ourheuristicsuseedgecoloringasabuildingblock—notethatedgecoloringcannotbeuseddirectlysinceitdoesnotexplicitlyconsiderweightsonedges,nordoesitconsidertheinterferenceconstraint.Bothofthesefactorsshouldbetakenintoaccountwhengenerat-ingatransmissionscheduleforourproblem.

Inthefollowing,wefirstpresentacolor-basedheuristicandthendiscussthreecolorselectionstrategiesforcoloringedges.ThenotationusedinthissectionissummarizedinTable1.

edgeIDvertexIDcolorIDedgeofthecolorofisadjacentto

theweight,communicationdelay,ofedgetheweightofthecolorthepaletteassociatedwith

08082C1123815C2C33814Figure4.Anexample

weightgreaterthan.Theseareessentiallycolorsthatareassociatedwithamessagethatislongerthanthecurrentmessage.Ifthepalettehassuchcolors,theMWCheuristicpicksacolorwiththeleastweight.Notethattheinterfer-enceconstraintmuststillbesatisfiedwhenpickingacolor.Ifnocolorinthepalettehasaweightgreaterthantheedgeweight,thentheheuristicsimplypicksthecolorwiththemaximumweightfromtheonesinthepalette.

Insummary,theheuristicattemptstoassignmessageswith“similar”lengthswiththesamecolorandavoidsin-creasingtheweightofacolorwheneverpossible.Doingsoenablestheheuristictoreducethecompletiontimeforallmessages.

RandomColorSelection(RCS)Heuristic:Theran-domcolorselectionheuristicpicksarandomcolorfromthepalettesuchthattheinterferenceconstraintissatisfied.LeastUsedColor(LUC)Heuristic:Theleastusedcolorisacommonheuristicforgeneralcoloringproblemsandwechoosethisheuristictodetermineitseffectivenessforourcommunicationschedulingproblem.Thisheuristicpickstheleastusedcolor—thecolorwiththeleastnumberofedges—suchthattheinterferenceconstraintissatisfied.ConsidertheexampledepictedinFigure4.Supposeinitially,eachpalettehashasthemaximumcolorsdegree,withtheweightheuristicofbegins0.Sincevertexbyassigningdistinctcolors(.Afterasdeletingshowninthetherelatedfigure)color(s)toalledgesincidentonfromthepalette,edgehasthesmallestpalette2colors,while

has3colors),andisconsidered(itnext.has

IfusingMWC,becauseselectedfor;ifusingLUC,sinceisthe,coloriscurrentlyleastusedcolor,ischosenand.Now,letusconsideredge.Anycolorexceptisapossiblecolor.IfweuseMWC,since,andarealllessisthethanheaviestedge(theweightsofallcolors),ischosenand.ForLUC,sincehavebeenevenlyused,anypossiblecolorcanbechosen.Intheaboveanalysis,weassumethatthereisnointerfer-enceinanystep.Hence,thecompletiontimeforMWCis

,which

isalsotheoptimalsolution;forLUC,beforeassigningedge

,thecompletiontimeis:

.

4OptimalCommunicationScheduling

Inthissection,wepresentanoptimalsolutiontotheOParCSproblem—asolutionthatminimizesthecomple-tiontimeforalltransmissions,subjecttotheconstraints.SincetheproblemisNP-complete,theoptimalsolutionhasexponentialcomplexity.Nevertheless,itisusefultocon-sidersuchasolutiontoenablecomparisonswithourpro-posedheuristics.

Ourtechniqueusesdirectedsearchbasedontheal-gorithm.searchhasbeenshowntobeoptimallyefficientinthatnoothersearchalgorithmwillexpandfewernodesinthesearchtreetolocatetheoptimalsolution[3].Thesearchprocessbuildsasearchtreeinwhichtherootnoderepresentstheoriginalcommunicationgraph.Expandinganodeinvolvestwosteps.First,itfindsallmatchingsforthecurrentexpandingnode(amatchingisasubsetofedgessuchthatnotwoedgesshareavertex),subjecttothein-terferenceconstraints.Then,foreachmatching,thecorre-spondingedgesaredeletedfromthenode(graph)andtheresultinggraphisaddedasaleafnodetothetree.

Tofindthenextnodetobeexpanded,anevaluationfunc-tionisneededinsothatthenodewiththelowestvalueisselected.Here,isthecostofthepathfromtheroottonode,andistheestimatedcostofthecheapestpathfromtothegoal.Toguaranteethatthesearchalgorithmiscompleteandoptimal,re-quiresthatfunctionshouldneveroverestimatethecosttoreachthegoal.

Inouralgorithm,thefunctionisdefinedasthesumofthecostsofallmatchingsalongthepathfromtheroottothenode.Letdenotethecostofedgeintheorig-inalcommunicationgraph,denoteanoderepresentingagraphinthesearchtree,anddenoteachildofthisnoderepresentinggraph,thenisdefinedas:

2 1.8C = 50C = 100) C 1.6WM 1.4 ot d 1.2erap 1mo 0.8C ( R 0.6TC 0.4MWC 0.2RCSLUC 0 20 25 30 35 40 45 50Number of NodesFigure5.Effectofthenumberofnodes5SimulationResults

Weconductasimulationstudytoevaluatetheperfor-manceofourheuristics.Ourstudyalsocomparestheheuristicstotheoptimalsolutioncomputedbythesearchalgorithm.

Weassumethatthesensornetworkisrepresentedbya3-tuple,whereisintheareaof

units.theissetthenumberofnodes,

Eachofpositionsisgeneratedforthenodesran-domlyintheareaforitsandcoordinates.isthesetoftransmissionranges.Weconvertthecommunicationnet-workintoadirectedgraph,sothatislessthaniforandequalonlytoiftheEuclideandistancebetween

,and

randomly.Thechosencommunicationovercost.foreachtransmissionisAllresultsshowninthissectionareobtainedasthemeanofatleast1000runsorwith.Ineachrun,onecommunicationconfidenceintervalgraphin

is

generatedwithsomespecificsettings.Sincethealgorithmsattempttominimizethetotalcompletiontimeforalltrans-missionsinagraph,theperformanceismeasuredbycom-paringthecompletiontimesacrossdifferentalgorithms.Forinstance,ifwehavegraphs,andthecomparisonresultfortopergraph,is

andifweuseCompletion

TimeRatio(CTR)todenotethemean,thenwehave:

5.1ComparisonofHeuristics

Inthissection,wecomparethethreecolorselectionheuristicsbyvaryingthreesystemparameters,thenumberofnodes,thenumberofedgesandthetransmissionrange.

2.6 2.4) 2.2 CW 2M 1.8 ot 1.6der 1.4apm 1.2oC 1 ( R 0.8TC 0.6 0.4MWC 0.2RCSLUC 0 100 200 300 400 500 600 700 800 900Number of EdgesFigure6.Effectofthenumberofedges

5.1.1EffectoftheNumberofNodes

Tostudytheimpactofthenumberofnodes(tematicallyvary

from20to50.Foreach,),wewegener-sys-atesufficientdifferentcommunicationgraphsanddeterminethetotaltimetoscheduleallmessages(foreachgraph)us-ingthethreeheuristics.Figure5showstheofthethreeheuristics(weusethecompletiontimeoftheMWCasthenormalizingfactor).

Ascanbeseen,theminimumweightcolor(MWC)heuristicoutperformstheothertwoheuristics.Randomcolorselection(RCS)yieldscompletiontimesthatarewithinofMWC,buttheperformanceisnotsensitivetothevalueof.Theleastusedcolor(LUC)heuristichastheworstperformance.ThisisbecauseLUCalwaystriestofindthecolorthatiscurrentlyleastused,whichactu-allydecreasestheabilitytoschedulemessagesinparallel.ThesuddenincreaseintheLUCcurvereflectstheimpactoftheinitialpalettesize.Forafixedpalettesize,whenincreases,thedecreases.Thisindicatesiftheinitialpalettesizeisclosertothenumberofcolorsneeded,thebetteristheLUCperformance.Wechoosemorecolorsat

becausethepalettehasnotenoughcolorstocover

alledges.(Inthefigure,meansthattheinitialnum-berofcolorsinthepaletteis50).

5.1.2EffectoftheNumberofEdges

Thenumberofedgesreflectsthecommunicationdensity.Figure6plotsthecompletiontimeratioforthethreeheuris-ticsasthenumberofedgesvaries.Again,theMWCout-performstheothertwoheuristics.Randomcolorselectionisabout10-18%worseandisnotsensitivetodifferentcom-municationdensities.ForLUC,whenthedensityissmall,thenumberofcolorschosenismuchlargerthannecessary(anddependsontheinitialpalette).TheperformanceofLUCimprovesasthenumberofedgesincreases.

2 1.8CTR ( Compared to MWC ) 1.4 1.2 1 0.8 0.6 0.4 0.2 0 20 25 30 35RangeMWCN = 20N = 40N = 60N = 70 40 45 50CTR ( Compared to MWC ) 1.6 3 2.8 2.6 2.4 2.2 2 1.8 1.6 1.4 1.2 1 0.8 0.6 0.4 0.2 0 20MWCN = 20N = 40N = 60N = 70 25 30 35Range 40 45 50(a)RCSvsMWC(b)LUCvsMWC

Figure7.Effectofrange

5.1.3EffectoftheRange

Inthisexperiment,transmissionrangeofanodeisvariedfrom20to50.Foragivenrange,wedeterminethecom-pletiontimesforthethreeheuristicsforsensornetworkscontaining20,40,60and70nodes.Toavoidtheimpactofpalettesize,theinitialpaletteissettohave100colors.Figure7(a)comparesthecompletiontimesofRCSandMWC,whileFigure7(b)comparesthecompletiontimesofLUCandMWC.WefindthatMWCoutperformstheothertwoheuristicsacrossallrangesandnetworksizes.Likeinthepreviousexperiment,theperformanceofrandomcolorselectioniswithin10-20%ofMWC,whilethatofLUCissignificantlyworse.ForLUC,foragiven,initiallythecurvegoesuptosomepeak,andthendropsastherangeincreases.Thisisbecause,initially,thenumberofnodeshasmoreimpactonthecommunicationdensity,andaftersomepoint,thedominates.

Overall,ourresultsshowthatMWCheuristicyieldsthebestperformanceamongthethreeheuristics.Thisisnotsur-prisingsincetheheuristictakesthecompletiontimeofeachcolorintoaccountwhenassigningcolorstoedges(whichinturn,helpsminimizethetotalcompletiontime).Next,wecomparetheperformanceofthisheuristictotheoptimalsolution.

thesearchtreeforoneinstance,andcantakeseveralhourstofindasolutiononaPentium-4workstation).

Weconducttwoexperiments.Inthefirstexperiment,eachnodeisassumedtohaveadifferenttransmissionrange;wevarythenumberofnodesandcomputethecompletiontimesoftheschedulesproducedbyMWCand.Inthesecondexperiment,eachnodeinthenetworkhasaniden-ticaltransmissionrange;wevarythenumberofnodesandcomputethecompletiontimes.Becauseofthespacelimit,weonlyshowtheresultsofthefirstexperiment(theresultsofthesecondexperimenthavesimilartrendandaredetailedin[7]).Figure8.(a)plotstheCTR(normalizedbytheop-timalsolution);andFigure8.(b)plotsthefractionofthecaseswhereMWCyieldsasolutionidenticaltotheoptimalsolution.

Weobservethefollowingbehavior:

1.ThetimetocompletetransmissionsusingMWCiswithinoftheoptimalsolutionforsensornet-worksofupto20nodes(and20edges).

2.WhilethesolutionyieldedbyMWCisdifferentfromtheoptimalsolutioninalargefractionofthecases,thissub-optimalscheduleisonlyaboutatmost6-8.5%worseforavarietyoftransmissionranges.3.Whenthetransmissionrangebecomeslarger,e.g.,in

,orthenumberofnodesincreases,the

performanceactuallybecomesstable,i.e.,stillwithin8.5%oftheoptimalsolution,whichindicatesthatMWCisrobustevenwhenthecomplexityincreases.

5.2MWCversustheOptimalSolution

MWCisatime-basedheuristicthathasbetterperfor-mancethantheothertwoheuristicsintermofminimizingthecommunicationcompletiontime.WeconstructseveralexamplestounderstandhowfarMWCisfromtheoptimalschedule.Sincethe-basedoptimalsolutionhasexpo-nentialcomplexityastheproblemscales,itiscomputation-allyfeasibletocompareMWCwiththeoptimalsolutiononlyforsmallnetworksizes.Consequently,werestricttheinputtonomorethan20nodes(and20edges)inourexper-iments(thisstillinvolvesexpandingsearchnodesin

5.3SummaryofResults

Ourexperimentsobtainthefollowingresults:

MWCisthebestofthethreeheuristicsacrossawide

rangeofsystemparameters.Thebetterperformanceisaresultoftakingthecommunicationtimeintoaccountwhengeneratingaschedule.

1.1 1CTR ( Compared to Optimal Result ) 1.08Fraction of Identical Results 0.8 1.06 1.04 1.02 1OPTR = [10,50]R = [10,60]R = [10,70]R = [10,80] 11 12 13 14 15Number of NodesR = [10,50]R = [10,60]R = [10,70]R = [10,80] 0.6 0.4 0.2 0.95 10 0 10 11 12 13 14 15Number of Nodes(a)CompletionTimeofMWCtoOPT(b)FractionofIdenticalResults

Figure8.MWCVersusOPTforvaryingtransmissionranges

RCSisaclosesecondintermsofthecompletiontimesofitsschedules.Further,RCSperformsstableasthenumberofnodesincreasesortherangeparame-terchanges.

LUChasworstperformanceandisverysensitivetotheinitialnumberofcolorsinthepalette.

Forsmallnetworks,theresultsofMWCareclosetotheoptimalsolution.

TheperformanceofMWCcanbeconsideredtobesta-ble,evenwithincreasingrangeandnumberofnodes,becauseitsperformanceiswithin8.5%oftheoptimalsolution.

6IncorporatingTimelinessConstraints

Ourheuristicssofarhavefocusedonschedulingmes-sagesinordertominimizecompletiontime.Sinceweareconcernedwithreal-timesensorapplicationsinthiswork,itisconceivablethatmessageswillhavedeadlinesonwhentheyshouldbereceivedatthedestinationnode.Ingeneral,thesedeadlineswillbedeterminedbythedeadlineoftheprocessingtaskatthesinkthatwillconsumethedata,oncereceived.Itispossibletoenhanceourheuristicstotakedeadlinesofmessagesintoaccount.

Oneapproachistofirstdetermineacoloringofedgesbasedonthetechniquesdescribedintheprevioussection.Observethatwhilemessageswithidenticalcolorscanbescheduledinparallel,ourheuristicsleavetheorderingofcolorsunspecified.Forinstance,ifagraphisassignedtwocolors,redandblue,thenwecouldscheduleallredmes-sagesfirst,followedbythebluemessages,orviceversa.Wecanexploitthisflexibilitytotakedeadlinesintoaccount.Wedefinethedeadlineofacolortobetheminimumdead-lineofallmessageswiththatcolor.Wecanthensimplyordercolorsbytheirdeadline.Doingsoorderstheschedul-ingofmessagesacrossvariouscolors—colorswithearlier

deadlinesgetscheduledbeforethosewithlaterdeadlines(messagesofthesamecolorarescheduledinparallel,likebefore).Notethat,regardlessoftheorderingofcolors,thetotalcompletiontimeremainsunchanged.

Anotherapproachistoincorporatedeadlineswhenas-signingcolorstoedges.Thiswillrequireustomodifytheedgecoloringheuristicsoutlinedintheprevioussec-tion.Whileadetaileddiscussionofsuchheuristicsisbe-yondthescopeofthispaper,wepresentabriefdiscussiononhowsuchatechniquemightwork.Thetechniquewillneedtobalancethreefactors—theweight,thedeadline,andthepalettesizeofanedge.Edgescanbechosenbasedonthemostimportantfactor.Forinstance,ifmeetingdead-linesisaprimarygoalandreducingcompletiontimesisasecondarygoal,thenedgescanbechosenforcoloringintheorderoftheirdeadlines,suchasEDF.Iftheoppositeistrue,theedgesarechosenbasedontheirpalettesizesandthencolorisassignedonthedeadlinesandweights.Adetailedexpositionoftheseideasisthesubjectoffuturework.

7RelatedWork

Real-timeissuesthatariseinvariouslayersofthenet-workstackinsensornetworksarestudiedin[14].IntermsofMAClayer,theauthorspointedoutthatakeyresearchchallengeistoprovidepredictabledelayand/orprioritiza-tionguarantees,whileminimizingoverheadpacketsanden-ergyconsumption.Ourworkaimstoprovidetheexplicitdelayfordatatransmissionsbyavoidingcollisions;atthesametime,thetotaltransmissiontimeforsendingsensormessagesisminimized.

Othereffortsthataddressreal-timeissuesinsensornet-worksincludethedesignofthecommunicationstackandreal-timerouting.Forexample,RAP[9]isareal-timecommunicationarchitectureforlarge-scalewirelesssen-sornetworksthatincludesanovelpacketschedulingpol-icycalledvelocitymonotonicscheduling.Inthismethod,therequestedvelocityismappedtoaMAC-layerpriority,

whichinturnreducesthedeadlinemissratio.In[4],anadaptivereal-timeroutingprotocol,SPEED,usesfeedback-basedtechniquesthattrytosatisfyper-hopdeadlinesinfaceofunpredictabletraffic.AEDF-basedMACprotocolisex-ploitedinahexagonalcellularnetworkarchitecturein[2],andtheschedulabilityconditionisgivenforahybridmes-sagesetconsistingofhardperiodicandsoftaperiodicmes-sages.

Incellulartelephonessystems,acommunicationchannel—abandoffrequencies—canbeusedsimultane-ouslybymanycallersifthesecallersarespatiallyapartandtheircallsdonotinterferewithoneanother.Thisproblemissimilartoourproblemintermsoftheabilitytoreusethechannel.Thedifferenceisthatthereisnoneedtoconsidertransmissioncostsandtimeconstraints.Ramanathan[13]introducedaunifiedalgorithmforefficient(T/F/C)DMAchannelassignmenttonetworknodesortointer-nodallinksina(multihop)wirelessnetworks.In[6],theauthorsestab-lishedarelationshipbetweenthemutualexclusionproblemandthedistributeddynamicchannelallocationproblem.

8Conclusions

Inthispaper,weconsideredaclassofwirelesssensorapplications—suchasmobilerobotics—thatimposetimeli-nessconstraints.Weassumedthatthesesensorapplicationsarebuiltusingcommodity802.11wirelessnetworksandfo-cusedontheproblemofprovidingqualitatively-betterQoSduringnetworktransmissionofsensordata.Weproposedthreeheuristicsbasedonedgecoloringthataredesignedtoexplicitlyavoidnetworkcollisionsandminimizethecom-pletiontimetotransmitasetofsensormessages.Oursimu-lationresultsshowedthattheminimumweightcolorheuris-ticsyieldsthebestperformanceacrossarangeofsystemsparametersandisclosetotheoptimalsolutioninthesensornetworkstested.

Aspartoffuturework,weplantoevaluatetheeffective-nessofourtechniquesbyimplementingthemintoasensortestbed.Todoso,weplantodesignaschedulerabovetheMAClayertoprioritizethepackettransmissionsbasedonthetransmissionschedule.Wealsoplantoexaminetheim-pactofmessagedeadlinesandwillextendourtechniquestomulti-hopsensornetworks.

9Acknowledgment

WethankShrikumarHariharasubrahmanian,ZihuiGeandZhengzhuFengforvarioushelpfuldiscussionsandcomments.Wealsothanktheanonymousrefereesfortheircomments.

References

[1]V.Bharghavan.Performanceevaluationofalgorithmsfor

wirelessmediumaccess.InIEEEPerformanceandDepend-abilitySymposium(IPDS),pages86–95.IEEE,July1998.[2]M.Caccamo,L.Y.Zhang,L.Sha,andG.Buttazzo.An

implicitprioritizedaccessprotocolforwirelesssensornet-works.InProceedingsoftheIEEEReal-TimeSystemSym-posium(RTSS).IEEE,December2002.

[3]R.DechterandJ.Pearl.Generalizedbest-firstsearchstrate-giesandtheoptimalityofA*.JournaloftheACM(JACM),32(3):505–536,July1985.

[4]T.He,J.A.Stankovic,C.Lu,andT.F.Abdelzaher.Speed:

Astalelessprotocolforreal-timecommunicationinsensornetworks.InInternationalConferenceonDistributedCom-putingSystems(ICDCS),May2003.

[5]I.Holyer.TheNP-completenessofedge-coloring.SIAM

JournalonComputing,10(4):718–720,November1981.[6]J.Jiang,T.-H.Lai,andN.Soundarajan.Ondistributed

dynamicchannelallocationinmobilecellularnetworks.IEEETransactionsonParallelandDistributedSystems,13(10):1024–1037,October2002.

[7]H.Li,P.Shenoy,andK.Ramamritham.Schedulingcom-municationinreal-timesensorapplication.TechnicalReportTR-04-05,UniversityofMassachusettsatAmherst,January2004.

[8]H.Li,J.Sweeney,K.Ramamritham,R.A.Grupen,and

P.Shenoy.Real-timesupportformobilerobotics.InIEEERealTimeTechnologyandApplicationsSymposium(RTAS),pages10–18.IEEE,May2003.

[9]C.Lu,B.M.Blum,T.F.Abdelzaher,J.A.Stankovic,

andT.He.Rap:Areal-timecommunicationarchitec-tureforlarge-scalewirelesssensornetworks.InIEEERealTimeTechnologyandApplicationsSymposium(RTAS).IEEE,September2002.

[10]S.Meguerdichian,S.Slijepcevic,V.Karayan,and

M.Potkonjak.Localizedalgorithmsinwirelessad-hocnet-works:locationdiscoveryandsensorexposure.InProceed-ingsofthe2ndACMinternationalsymposiumonMobileadhocnetworking&computing,pages106–116.ACM,2001.[11]K.Ramamritham,J.A.Stankovic,andP.Shiah.Effi-cientschedulingalgorithmforreal-timemultiprocessorsys-tems.IEEETransactionsonParallelandDistributedSys-tems,1(2):184–194,April1990.

[12]S.Ray,J.B.Carruthers,andD.Starobinski.RTS/CTS-inducedcongestioninadhocwirelessLANs.InWire-lessCommunicationsandNetworkingConference(WCNC),March2003.

[13]S.Ramanathan.Aunifiedframeworkandalgorithmforchan-nelassignmentinwirelessnetworks.WirelessNetworks,5(2):81–94,March1999.

[14]J.A.Stankovic,T.F.Abdelzaher,C.Lu,L.Sha,andJ.C.

Hou.Real-timecommunicationandcoordinationinembed-dedsensornetworks.ProceedingsoftheIEEE,91(7):1002–1022,2003.