Adaptive qos optimizations with applications to ra

AdaptiveQoSOptimizationswithapplicationstoRadarTracking?SouravGhosh1,JefferyHansen2,andRagunathan(Raj)Rajkumar3andJohnLehoczky41CarnegieMellonUniversity,[e-mail]2CarnegieMellonUniversity,[e-mail]3CarnegieMellonUniversity,[e-mail]4CarnegieMellonUniversity,[e-mail]sensornetworks,mobileadhocnet-workingandautonomoussystems,therelationshipbetweenlevelofserviceandresourcerequirementsisnotfixed.Environmentalfactorsoutsidethedirectcon-trolofthesystemaffectthisrelationshipandmayalsoaffecttheperceivedutilityofagivenlevelofservice.Radartrackingprovidesagoodexample.Inradarsystems,afixedamountofradarbandwidthandcomputingresourcesmustbeapportionedamongmultipletasks,eachofwhichcorrespondstoatarget.Inad-dition,environmentalfactorssuchasnoise,heatingconstraintsoftheradarandthespeed,distanceandmaneuverabilityoftrackedtargetsdynamicallyaffectthemappingbetweenthelevelofserviceandresourcerequirementsaswellasthemappingbetweenthelevelofserviceandtheuser-perceivedutility.Tobeabletohandlethesetasks,aQoSmanagermustbeadaptive,reactingtodynamicchangesintheenvironment,adjustingthelevelofserviceandreallocatingresourceseffi-ciently.Inthispaper,wepresentadynamicQoSoptimizationschemeforaradartrackingapplicationbasedonQ-RAM[1,2].Ourschemeisabletodealwithalargenumberofoperatingpointsinreal-timewithveryacceptablelossesintotalutilityaccrued.Thisresultismadepossiblebyanefficientheuristictocomputetheconcavemajorantofamulti-variatefunction,andanoff-linestorage-efficientdiscretizationofthestaticaspectsoftheproblemspace.ThesetwocontributionswillalsobeusefulinmanydynamicQoS-drivenapplicationsbeyondradartrack-ing.1IntroductionTraditionalQoSoptimizationalgorithmsassumethatacollectionoftaskscompeteforresources,witheachtaskreceivingsomebenefitfromthoseresources.Thegoalistoallocatetheresourcestotasksinsuchawayastooptimizethetotalbenefitreceivedbyallthetasks.Thisbenefitisoftencalled“utility”[3].AlargerQoSforataskgenerally?ThisworkwassupportedbyaDARPAMultidisciplinaryUniversityResearchInitiative(MURI)programadministeredbytheOfficeofNavalResearchunderGrantN00014-01-1-0576andbyDARPAundercontractnumberF33615-00-C-1729.requiresalargeramountofresourcesandresultsinlargerutility.Furthermore,theQoS-utilitycurveusuallysaturatesatahighQoSlevelwithfurtherincreasesinQoSyieldingsmallerincreasesinutility[1].Generally,itisassumedthatforagiveninvocationofatask,theutilityreceivedforaparticularamountofresourcesisconstant.Whilethisissufficientformanyapplications,thismaynotbethecaseforotherapplications.Anexampleofanapplicationwherethemappingbetweenresourcesandutilitymaychangedynamicallyisradartracking.Radartrackingischallenginginthatitdealswithalargenumberofdynamictasks,multipleresources,severalpracticalconstraintsandreal-timeoperation.Duetothehighcomplexityofhigh-qualitytrackinginreal-time,radarsystemshavetraditionallyusedratherstaticschemesinter-mixedwithoperator(somewhaterror-prone)intuitionofwhichcombinationsarelikelytowork.Itisim-portanttodevelopreal-timeresourceallocationalgorithmsthatwillleadnear-optimalresourceallocationsoverawiderangeofconditions.R1onlyR2onlyR3onlyR4onlyR1&R2R2&R3R3&R4R1&R4(a)RadarLayoutttxitwitriTiAi(b)DwellParametersFig.1.RadarModelInthispaper,wemodelaradarsystemasbeingcomposedofradartransceivers,apowersourceandanarrayofprocessorsforthesignalprocessingandtrackingalgo-rithms.Aradarsystemmustalsosatisfyphysicalconstraints,forexample,thedynamicsofanobjectbeingtracked(suchasitsspeed,accelerationanddistancefromtheradar),andenvironmentalfactorssuchasnoiseinfluencethetrackingprecision.Moreover,theradarsystemitselfimposescertainconstraints.Forexample,notonlymusttheutiliza-tionoftheresourcesbebelowanappropriateutilizationbound,otherconstraintssuchastheheatdissipationlimitsofaradartransmittermustalsobesatisfied.Theradarsystemresourcemanagementproblemsareasfollows:•Selectionofappropriatesettingsoroperatingpointsfortrackingtasks:Inthispaper,weaddressthisissue.WeusetheQoS-basedResourceAllocationModel(Q-RAM)[1,4]asthebuildingblockofourresourcemanagementframework.•Ensuringschedulabilityofthetasks:Weaddressthisin[5].Manyrecentstudieshavefocusedonphased-arraysystems,especiallyradarschedul-ing.Forexample,Goddardetal[6]useddataflowmodelforreal-timeschedulingofradartrackingalgorithms.Ontheotherhand,Shihetal[7,8]addressedtheschedulingissuesofradarfront-end.Inaddition,similartoouroptimizationmethodology,theyalsointroducedtheideaof“serviceclasses”designedoff-linetodeterminetheQoSoperatingpointsoftasks.Therestofthepaperisorganizedasfollows.Section2presentsourmodeloftheradarsystem.Section3presentstheQoSoptimizationschemesintheradarsystem.InSection4,weevaluateandcomparetheseschemes.InSection5,wequantizetheprob-lemspaceandalsoperformpartofthecomputationoff-line.InSection6,wedescribetheresultsfromthequantization.FinallyinSection7,wesummarizeourcontributionsandprovideabriefdescription