Distributed consensus on enclosing shapes and minimum time r(5)

ThealgorithmisclearlyasetofFloodMaxalgorithmsforleaderelection.Infacttheboundaryoftheorthotopeineachdirectionaisgivenbythecoordinatesofthepointsonsuchboundarywhicharecharacterizedbythepropertyofhavingthemaximumandminimumvalueoftheathcoordinaterespectively.

Inordertoprovethattheexactnumberofcommunica-tionroundsneededisTFloodMEO,simplyobservethatitisexactlytheminimumtimeforalltheleaderstopropagatetheirinformationthroughallthenetwork.Hencethisistheminimumtimeforeverypossibleconsensusalgorithmtoconverge.Butthisisexactlythetimetakenby2dFloodMaxalgorithmsrunningsimultaneouslyandthereforethetimetakenbyFloodMEO.

In this paper we introduce the notion of optimization under control and communication constraint in a robotic network. Starting from a general setup, we focus our attention on the problem of achieving rendezvous in minimum time for a network of first order

theMEB(MEO)ofagenti(forsomei∈{1,...,n})hasnotchangedandthealgorithmhasnotconvergedyet.ThentherewillexistaT>diamGsuchthattheMEB(MEO)ofagentiwillchangetoanewvalue.Butthismeansthatthenewvalue,storedTroundsbeforebysomeotheragentj,tookanumberofcommunicationroundsgreaterthandiamGtoarrivefromjtoiandthiscontradictsthede nitionofdiameterofG.

T∈Nsuchthatfort=

A.TimecomplexityofCCMEBandCCMEO

InthepreviouslemmawehaveproventhatthecontrolandcommunicationlawsCCMEBandCCMEOachieveconsensus.Nowweaskhowfasttheselawsaredependingonthecontrolboundrctrandthenumberofagents.

Theorem5.2:Forrcmm∈R+,d∈N,considerthenetworkSwithcommunicationedgemapeitherEdiskorEcube.Thefollowingstatementshold:

(i)foru[i]∈B(0,rctr),i∈{1,...,n},thecontroland

communicationlawCCMEBasymptoticallyconvergestotheminimumtimerendezvouscentralized+solutionMTR(Ecmpl,B(0,rctr))asrctr→0(forall xedn).(ii)foru[i]∈C(0,rctr),i∈{1,...,n},thecon-trolandcommunicationlawCCMEOconvergestotheminimumtimerendezvouscentralized+solutionMTR(Ecmpl,C(0,rctr))forrctr→0(forall xedn).Moreover,itisaconstantfactorapproximationofMTR(Ecmpl,C(0,rctr)),i.e.,TC(Trndzvs,CCMEO)∈Θ(n

rTctr

+FloodMEO.

(3)

The rststatementisprovenbyobservingthatTFloodMEOdoesnotdependonrctr,therefore,asrctr→0+,TMEOconvergestotheoptimalvalueofthecentralizedcase.

Inordertoprovethesecondstatement,observethatdiam(p[1](0),...,p[n](0))≤(n 1)rcmmandTFloodMEO∈Θ(n).Theresultfollowsbysubstitutingtheseboundsin(3).

In this paper we introduce the notion of optimization under control and communication constraint in a robotic network. Starting from a general setup, we focus our attention on the problem of achieving rendezvous in minimum time for a network of first order

B.DistributedminimumtimerendezvousinonedimensionInonedimension(alltheagentsspreadonaline),wecan ndaconditiononrctrensuringthatthemove-toward-MBCalgorithmisthesolutionofMTR(Edisk,B(0,rctr)).

Theorem5.5:Ford=1,letimaxandimintheagentsinthenetworkSwiththemaximumandminimumpositions.Ifrctr<1

rctr

Proof:Considertheinputsequenceofthecentralizedsolutionfortheagentimin(andequivalentlyforimax).Itisu[imin](t)=rctrforallt<T 1andu[imin](T 1)=MBC(p[1](0),...,p[n](0)) p[imin](T 1).SincetherendezvoustimeisboundedbythetimethatimaxandimintaketoreachMBC(p[1](0),...,p[n](0)),weneedtoprovethat,aslongastheconsensusontheminimalenclosingballisnotreached,thenu[imin](t)= u[imax](t)=rctr.Duetothesymmetryoftheproblemwewillgivetheproofonlyforimin.Itcanbeeasilyshownthatforallt≥1such

[imin]

thatpmax(t)=p[imax](0)(consensusisnotreached),thefollowingholds:

[imin]imin]

p[max(t+1)>pmax(t 1)+rcmm.

.

Itfollows:

MBC[imin](t+1)=

1

2

imin][imin]

(p[(0))max(t 1)+rcmm+p

=MBC[imin](t 1)+

1rcmm.

2

Thisleadsto

rctr+

1

4

rcmm.

Theothertwoassumptionsensuretheconditionfort=0.

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说医药卫生Distributed consensus on enclosing shapes and minimum time r(5)在线全文阅读。