An Efficient Data Dissemination Scheme for Nearest

JournalofResearchandPracticeinInformationTechnology,Vol.38,No.2,May2006181AnEfficientDataDisseminationSchemeforNearestNeighbourQueryProcessingKwangJinParkDepartmentofComputerScienceandEngineering,KoreaUniversity5-1,Anam-dong,Seongbuk-Ku,Seoul136-701,[e-mail]mationservices(LDISs)produceanswerstoqueriesaccordingtothelocationoftheclientissuingthequery.InLDIS,techniquessuchascaching,prefetchingandbroadcastingareeffectiveapproachestoreducingthewirelessbandwidthrequirementandqueryresponsetime.However,theclient’smobilitymayleadtoinconsistencyproblems.Inthispaper,weintroducethebroadcast-basedLDISscheme(BBS)forthemobilecomputingenvironment.IntheBBS,broadcasteddataitemsaresortedsequentiallybasedontheirlocationandtheserverbroadcaststhelocationdependentdata(LDD)alongwithanindexsegment.Then,wepresentadataprefetchingschemeandOBC(ObjectBoundaryCircle),inordertoreducethequeryresponsetime.Theperformanceoftheproposedschemeisinvestigatedinrelationtovariousenvironmentalvariables,suchasthedistributionsofthedataitems,theaveragespeedoftheclientsandthesizeoftheservicearea.ACMClassification:H.2.8Manuscriptreceived:18May2005CommunicatingEditor:JohnGrundyCopyright©2006,AustralianComputerSocietyInc.Generalpermissiontorepublish,butnotforprofit,allorpartofthismaterialisgranted,providedthattheJRPITcopyrightnoticeisgivenandthatreferenceismadetothepublication,toitsdateofissue,andtothefactthatreprintingprivilegesweregrantedbypermissionoftheAustralianComputerSocietyInc.1.INTRODUCTIONMobilelocation-dependentinformationservices(LDISs)havedrawnalotofattentionfromwirelessdataindustriesinthepastfewyears.Thisgrowthinmobilecommunicationspresentsnewaspectstotheresourceassignmentproblemaswellasnewapplications.Intheseservices,informationprovidedtomobileusers’reflectstheircurrentgeographicallocations.Locationdependentdataisadatawhosevaluedependsonthelocation.Theanswertoaquerydependsonthegeographicallocationwherethequeryoriginates.Let’sconsideranexampleinwhichauserdrivesacarandwantstofindthenearestgasstations.Theusersendsaquery,suchas,“whatarethenamesandlocationsofthegasstationsneartomycurrentlocation?”,usinghismobiledevice.Oncetheusergetstheanswerfromtheserver,hewillvisitthegasstationsinorderofthenearesttohislocationbasedonprice.Tohandlesuchaquery,thepositionsoftheobjectsandtheusermustbefound.Inthispaper,weproposethebroadcast-basedLDISschemeunderageometriclocationmodel.Wefirstintroducethebroadcastbasedlocationdependentdatadeliveryscheme(BBS).Inthisscheme,theserverperiodicallybroadcastsreports,whichcontainstheIDsofthedataitems(e.g.,buildingnames)andthevaluesofthelocationcoordinatestotheclients.Thebroadcasteddataobjectsaresortedsequentially,basedontheirlocationbeforebeingbroadcasted.Then,weintroducetheprefetchingschemeinLDISforthemobilecomputingenvironment.ByusingtheproposedJRPIT38.2.QX16/3/062:39PMPage181AnEfficientDataDisseminationSchemeforNearestNeighbourQueryProcessingJournalofResearchandPracticeinInformationTechnology,Vol.38,No.2,May2006182schemes,theclient’saccessandtuningtimesaresignificantlyreduced.Themaincontributionsofourworkcanbesummarizedasfollows:•Itisnotnecessaryfortheclienttowaitforandtuneintoaparticularindexsegment,ifithasalreadyidentifiedthenearestobjectbeforetheindexsegmenthasarrived.ThistechniquesignificantlyreducestheaccesstimeinthebroadcastbasedLDISenvironment.•Theclientsimplyadjuststhevalueofkwhenitperformsthek-NNqueryprocessing.•Theclientcanalsoperformtheak-NNqueryprocessingwithoutanindexsegment.Inthiscase,thebestaccesstimeisobtained,sincenoindexisbroadcastalongwiththefile(Imielinskietal,1994).Therestofthepaperisorganizedasfollows:Section2givesthebackgroundofthebroadcastmodelandLDISscheme.Section3describestheproposedalgorithms.TheperformanceanalysisandevaluationispresentedinSections4and5respectively.Finally,Section6concludesthispaper.2.BACKGROUNDWiththeadventofhighspeedwirelessnetworksandportabledevices,datarequestsbasedonthelocationofmobileclientshaveincreasedinnumber.However,thereareseveralchallengestobemetinthedevelopmentofLDISs(Leeetal,2002),suchastheconstraintsassociatedwiththemobileenvironmentandthedifficultyoftakingtheuser’smovementintoaccount.Hence,varioustechniqueshavebeenproposedtoovercomethesedifficulties.2.1BroadcastModelDatabroadcastinginawirelessnetworkconstitutesanattractiveapproachinthemobiledataenvironment.However,thewirelessbroadcastenvironmentisaffectedbythenarrownetworkbandwidthandthebatterypowerrestrictionsofthemobileclients.(1,m)indexisoneoftechniquesthatattemptstoaddressthisissue,byinterleavingindexinginformationamongthebroadcastdataitems(Imielinksietal,1997;Imielinskietal,1994).Atthesametime,theclientcanreduceitsbatterypowerconsumptionthroughtheuseofselecttuning.Byaccessingtheindexsegment,themobileclientisabletopredictthearrivaltimeofthedesireddataitem.Thus,itcanstayinthepowersavingmodemostofthetime,andtuneintothebroadcastchannelonlywhentherequesteddataarrives.(1,m)indextechniquescanbeevaluatedintermsofthefollowingfactors:•AccessTime:Theaveragetimeelapsedfromthemome