Nonnumerical Algorithms and Problems

Devising algorithms for mobile networks is hard. It is important, then, to develop techniques and abstractions to ease the design of algorithms for mobile networks. We propose one such abstraction, the Virtual Mobile Node abstraction. The key difficulty in

BriefAnnouncement:

VirtualMobileNodesforMobileAdHocNetworks

Ben-GurionUniversityBen-GurionUniversity

ShlomiDolevEladSchiller

SethGilbert

MITCSAIL

NancyA.Lynch

MITCSAIL

U.ofConnecticut,MITCSAIL

AlexA.Shvartsman

TexasA&MUniversity

JenniferWelch

CategoriesandSubjectDescriptors:F.2.2[TheoryofComputa-tion]:NonnumericalAlgorithmsandProblemsGeneralTerms:Algorithms,Theory

Keywords:dynamicdistributedalgorithms,fault-tolerance

Abstract

Devisingalgorithmsformobilenetworksishard.Itisimportant,then,todeveloptechniquesandabstractionstoeasethedesignofalgorithmsformobilenetworks.Weproposeonesuchabstraction,theVirtualMobileNodeabstraction.

Thekeydif cultyinmobilenetworksisthecompletelyunpre-dictablemotionofthenodes.Thiscomplicationis,ofcourse,unavoidable:thede ningfeatureofamobilenetworkisthatthenodes,infact,move.Theotherdif cultyistheunpredictableavail-abilityofnodesthatcontinuallyjointhesystemandfail.

Themotion,however,alsopresentsanopportunity:ifmobilenodesmovedinausefulway,algorithmscouldtakeadvantageofthemotion,performingevenmoreef cientlythaninstaticnet-works.ThisideaisillustratedbyHatzisetal.in[2],whichde nesthenotionofacompulsoryprotocol,onethatrequiresasubsetofthemobilenodestomoveinaspeci cmanner.Theypresentanef cientcompulsoryprotocolforleaderelection.Theroutingpro-tocolsofChatzigiannakisetal.[1]andLietal.[3]providefurtherevidencethatcompulsoryprotocolsaresimpleandef cient.

Itmaybedif cult,however,toensurethatmobilenodesmoveasdesired,especiallyforhighlydynamicsystemswherenodesmayfailorbedivertedfromtheprescribedpath.Thusourobjectiveistoretaintheeffectivenessofcompulsoryprotocolswithoutimposingrequirementsonthemotionofthenodes.

Weproposeexecutingalgorithmsonvirtualmobilenodes,ab-stractnodesthatmoveinapredetermined,predictablemanner.Vir-tualmobilenodes(VMNs)aresimulatedbyrealnodesinthenet-work.ThemotionofaVMNisdeterminedinadvance,andisknowntotheprogramsexecutingontheVMNs.Forexample,aVMNmaytraversetheplaneinaregularpattern,oritmayperformapseudorandomwalk.ThemotionoftheVMNsmaybecom-pletelyuncorrelatedwiththemotionoftherealnodes:evenifalltherealnodesaremovinginonedirection,thevirtualnodesmaytravelintheoppositedirection.

Forafullversionofthispaper,see[4].ThisworkissupportedinpartbyNSFgrants

CCR-0098305,ITR-0121277,64961-CS,9988304,0311368,9984774and0098305,AFSOR#F49620-00-1-0097,DARPA#F33615-01-C-1896,NTTMIT9904-12,TexasAdvancedResearchProgram000512-0091-2001,anIBMfacultyaward,theIsraeliMinistryofDefenseandMinistryofTradeandIndustry.

Copyrightisheldbytheauthor/owner.

PODC’04,July25–28,2004,St.Johns,Newfoundland,Canada.ACM1-58113-802-4/04/0007.

Thisabstractionsimpli esthesolutionofmanyproblems.VMNscanbeusedtoroutemessage,usingcompulsoryprotocolsdevisedbyChatzigiannakisetal.[1]).Similarly,VMNscanbeusedtocol-lectandevaluatedatainasensornetwork,ortoimplementgroupcommunicationservicesbycollectingandorderingmessages.WepresenttheMobilePointEmulator,anewalgorithmthatim-plementsrobustVMNs.Themainideaofthealgorithmistoal-lowrealnodestravelingnearthelocationofaVMNtoassistinemulatingtheVMN.Inordertoachieverobustness,thealgorithmreplicatesthestateofavirtualnodeatanumberofrealmobilenodes.Astheexecutionproceeds,thealgorithmcontinuallymod-i esthesetofreplicassothattheyalwaysremainnearthevirtualnode.Weuseareplicatedstatemachineapproach,augmentedtosupportjoins,leaves,andrecoveries,tomaintaintheconsistencyofthereplicas.Aslongasthepathofthevirtualnodetravelsthroughdenseareasofthenetwork,thevirtualnodedoesnotfail.IfaVMNdoesfail,itcanrecoverwhenitagainreentersadensearea.

TheVMNframeworkintroducesnewhorizonsforfurtherre-search.OnepathofinvestigationistodevisefurtherapplicationsfortheVMNabstraction.WhilewehavebeguntodevelopsomebasicprotocolsbasedonVMNsthataresimplerandmoreintuitivethantraditionalsolutions,muchanalysisandevaluationremain.Anothersigni cantpathofinvestigationistodevelopimprovedVMNimplementations.InthispaperwehaveassumedthatthepathofaVMNis xedinadvance,andthesetofVMNsis xedinadvance.Inmanycases,thisisnotonlysuf cient,butinfactadvantageous,asthelocationofaVMNcanbeknownapriori.However,forsomeapplicationsitwouldbeusefulifthepathoftheVMNcouldbedeterminedon-the- y.

Inaddition,long-termrobustnessoftheVMNabstractioncouldbeimprovedifthevirtualnodeswereself-stabilizing.Webelievethatwithafewmodi cations,theMobilePointalgorithmcanbemadeself-stabilizing.

Finally,thecorrectnessoftheMobilePointEmulatordependsonrelativelystrongassumptionsaboutthelocalcommunicationamongthemobilenodes.Wewouldliketobetterunderstandthefeasibilityofthecurrentmodel,andalsotodevelopversionsofthealgorithmthatrelyonweakernetworkmodels.

References

[1]I.Chatzigiannakis,S.Nikoletseas,P.Spirakis.Anef cientcommunication

strategyforad-hocmobilenetworks.InDISC,2001.

[2]K.P.Hatzis,G.P.Pentaris,P.G.Spirakis,V.T.Tampakas,R.B.Tan.

Fundamentalcontrolalgorithmsinmobilenetworks.InSPAAarchive,SaintMalo,France,1999.

[3]Q.Li,D.Rus.Sendingmessagestomobileusersindisconnectedad-hoc

wirelessnetworks.InMobiCom,2000.

[4]S.Dolev,S.Gilbert,N.A.Lynch,E.Schiller,A.A.Shvartsman,J.Welch.

Virtualmobilenodesformobileadhocnetworks.Tech.Rep.MIT-LCS-TR-937,2004.

本文来源：https://www.bwwdw.com/article/t5s1.html