17 Pages
English

Critical node lifetimes in random networks via the Chen Stein method

-

Gain access to the library to view online
Learn more

Description

Niveau: Supérieur, Doctorat, Bac+8
Critical node lifetimes in random networks via the Chen-Stein method Massimo Franceschetti? and Ronald Meester† Abstract This paper considers networks where nodes are connected randomly and can fail at random times. It provides scaling laws that allow to find the critical time at which isolated nodes begin to appear in the system as its size tends to infinity. Applications are in the areas of sensor and ad-hoc networks where nodes are subject to battery drainage and ‘blind spots' formation becomes a primary concern. The techniques adopted are based on the Chen-Stein method of Poisson approximation, which allows to obtain elegant derivations that are shown to improve upon and simplify previous related results that appeared in the literature. Since blind spots are strongly related to full connectivity, we also obtain some scaling results about the latter. 1 Introduction In this paper we present results for networks where nodes are connected ran- domly and can fail at random times. We consider two percolation-theory based models of random networks. The first one finds its original formulation in a paper by Broadbent and Hammersley [3], who considered grid networks made of edges that are drawn independently with probability p. Today, applications of this simple model range from random electrical networks to reliability theory, statistical mechanics and epidemics, to name a few. We refer to [11] for exten- sive references and for a more detailed account of these applications.

  • gilbert's continuum

  • critical time

  • random grid

  • since isolated vertices

  • chen-stein method

  • dimensional poisson

  • poisson distribution

  • random networks


Subjects

Informations

Published by
Reads 66
Language English

Exrait

CriticalnodelifetimesinrandomnetworksviatheChen-SteinmethodMassimoFranceschettiandRonaldMeesterAbstractThispaperconsidersnetworkswherenodesareconnectedrandomlyandcanfailatrandomtimes.Itprovidesscalinglawsthatallowtofindthecriticaltimeatwhichisolatednodesbegintoappearinthesystemasitssizetendstoinfinity.Applicationsareintheareasofsensorandad-hocnetworkswherenodesaresubjecttobatterydrainageand‘blindspots’formationbecomesaprimaryconcern.ThetechniquesadoptedarebasedontheChen-SteinmethodofPoissonapproximation,whichallowstoobtainelegantderivationsthatareshowntoimproveuponandsimplifypreviousrelatedresultsthatappearedintheliterature.Sinceblindspotsarestronglyrelatedtofullconnectivity,wealsoobtainsomescalingresultsaboutthelatter.1IntroductionInthispaperwepresentresultsfornetworkswherenodesareconnectedran-domlyandcanfailatrandomtimes.Weconsidertwopercolation-theorybasedmodelsofrandomnetworks.ThefirstonefindsitsoriginalformulationinapaperbyBroadbentandHammersley[3],whoconsideredgridnetworksmadeofedgesthataredrawnindependentlywithprobabilityp.Today,applicationsofthissimplemodelrangefromrandomelectricalnetworkstoreliabilitytheory,statisticalmechanicsandepidemics,tonameafew.Wereferto[11]forexten-sivereferencesandforamoredetailedaccountoftheseapplications.ThesecondmodelisanaturalextensionofthefirstonetothecontinuumplaneandwasproposedbyGilbert[10].Heconsiderednodesrandomlylocatedontheplane,accordingtoatwo-dimensionalPoissonpointprocess,andedgesconnectingpairsofnodesthatarewithinrange2rofeachother.Thisgivesafamilyofrandomgraphs,parametrisedbythedensityλofthepointprocess,orequivalentlybytheradiusrofthediscs.Gilbert’smodel,aswellasmoregeneralrandomcon-nectionmodels,areextensivelydiscussedin[15].Recently,therehasbeenaMassimoFranceschettiiswiththeDepartmentofElectricalandComputerEngineering,UniversityofCaliforniaatSanDiego,LaJolla,CA.RonaldMeesteriswiththeDepartmentofMathematics,VrijeUniversiteit,Amsterdam,TheNetherlands.1