Nonnumerical Algorithms and Problems

1、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 briefa

2、nnouncement: virtualmobilenodesformobileadhocnetworks ben-gurionuniversityben-gurionuniversity shlomidoleveladschiller sethgilbert mitcsail nancya.lynch mitcsail u.ofconnecticut,mitcsail alexa.shvartsman texasamuniversity jenniferwelch categoriesandsubjectdescriptors:f.2.2theoryofcomputa-tion:nonnum

3、ericalalgorithmsandproblemsgeneralterms:algorithms,theory keywords:dynamicdistributedalgorithms,fault-tolerance abstract devisingalgorithmsformobilenetworksishard.itisimportant,then,todeveloptechniquesandabstractionstoeasethedesignofalgorithmsformobilenetworks.weproposeonesuchabstraction,thevirtualm

4、obilenodeabstraction. thekeydif cultyinmobilenetworksisthecompletelyunpre-dictablemotionofthenodes.thiscomplicationis,ofcourse,unavoidable:thede ningfeatureofamobilenetworkisthatthenodes,infact,move.theotherdif cultyistheunpredictableavail-abilityofnodesthatcontinuallyjointhesystemandfail. themotion

5、,however,alsopresentsanopportunity:ifmobilenodesmovedinausefulway,algorithmscouldtakeadvantageofthemotion,performingevenmoreef cientlythaninstaticnet-works.thisideaisillustratedbyhatzisetal.in2,whichde nesthenotionofacompulsoryprotocol,onethatrequiresasubsetofthemobilenodestomoveinaspeci cmanner.the

6、ypresentanef cientcompulsoryprotocolforleaderelection.theroutingpro-tocolsofchatzigiannakisetal.1andlietal.3providefurtherevidencethatcompulsoryprotocolsaresimpleandef cient. itmaybedif cult,however,toensurethatmobilenodesmoveasdesired,especiallyforhighlydynamicsystemswherenodesmayfailorbedivertedfr

7、omtheprescribedpath.thusourobjectiveistoretaintheeffectivenessofcompulsoryprotocolswithoutimposingrequirementsonthemotionofthenodes. weproposeexecutingalgorithmsonvirtualmobilenodes,ab-stractnodesthatmoveinapredetermined,predictablemanner.vir-tualmobilenodes(vmns)aresimulatedbyrealnodesinthenet-work

8、.themotionofavmnisdeterminedinadvance,andisknowntotheprogramsexecutingonthevmns.forexample,avmnmaytraversetheplaneinaregularpattern,oritmayperformapseudorandomwalk.themotionofthevmnsmaybecom-pletelyuncorrelatedwiththemotionoftherealnodes:evenifalltherealnodesaremovinginonedirection,thevirtualnodesma

9、ytravelintheoppositedirection. forafullversionofthispaper,see4.thisworkissupportedinpartbynsfgrants ccr-0098305,itr-0121277,64961-cs,9988304,0311368,9984774and0098305,afsor#f49620-00-1-0097,darpa#f33615-01-c-1896,nttmit9904-12,texasadvancedresearchprogram000512-0091-2021,anibmfacultyaward,theisraeli

10、ministryofdefenseandministryoftradeandindustry. copyrightisheldbytheauthor/owner. podc04,july2528,2021,st.johns,newfoundland,canada.acm1-58113-802-4/04/0007. thisabstractionsimpli esthesolutionofmanyproblems.vmnscanbeusedtoroutemessage,usingcompulsoryprotocolsdevisedbychatzigiannakisetal.1).similarl

11、y,vmnscanbeusedtocol-lectandevaluatedatainasensornetwork,ortoimplementgroupcommunicationservicesbycollectingandorderingmessages.wepresentthemobilepointemulator,anewalgorithmthatim-plementsrobustvmns.themainideaofthealgorithmistoal-lowrealnodestravelingnearthelocationofavmntoassistinemulatingthevmn.i

12、nordertoachieverobustness,thealgorithmreplicatesthestateofavirtualnodeatanumberofrealmobilenodes.astheexecutionproceeds,thealgorithmcontinuallymod-i esthesetofreplicassothattheyalwaysremainnearthevirtualnode.weuseareplicatedstatemachineapproach,augmentedtosupportjoins,leaves,andrecoveries,tomaintain

13、theconsistencyofthereplicas.aslongasthepathofthevirtualnodetravelsthroughdenseareasofthenetwork,thevirtualnodedoesnotfail.ifavmndoesfail,itcanrecoverwhenitagainreentersadensearea. thevmnframeworkintroducesnewhorizonsforfurtherre-search.onepathofinvestigationistodevisefurtherapplicationsforthevmnabst

14、raction.whilewehavebeguntodevelopsomebasicprotocolsbasedonvmnsthataresimplerandmoreintuitivethantraditionalsolutions,muchanalysisandevaluationremain.anothersigni cantpathofinvestigationistodevelopimprovedvmnimplementations.inthispaperwehaveassumedthatthepathofavmnis xedinadvance,andthesetofvmnsis xe

15、dinadvance.inmanycases,thisisnotonlysuf cient,butinfactadvantageous,asthelocationofavmncanbeknownapriori.however,forsomeapplicationsitwouldbeusefulifthepathofthevmncouldbedeterminedon-the- y. inaddition,long-termrobustnessofthevmnabstractioncouldbeimprovedifthevirtualnodeswereself-stabilizing.webeli

16、evethatwithafewmodi cations,themobilepointalgorithmcanbemadeself-stabilizing. finally,thecorrectnessofthemobilepointemulatordependsonrelativelystrongassumptionsaboutthelocalcommunicationamongthemobilenodes.wewouldliketobetterunderstandthefeasibilityofthecurrentmodel,andalsotodevelopversionsofthealgorithmthatrelyonweakernetworkmodels. references 1i.chatzigiannakis,s.nikoletseas,p.spirakis.anef cientcommunication strategyforad-hocmobilenetworks.indisc,2021. 2k.p.hatzis,g.p.pentaris,p.g.spirakis,v.t.tampakas,r.b.tan. fundamentalcontrolalgorithmsinmobilenetworks.inspaaa