Constrained Minimum Passage Time in Random Geometric Graphs
- PDF / 1,419,776 Bytes
- 13 Pages / 439.37 x 666.142 pts Page_size
- 48 Downloads / 249 Views
Constrained Minimum Passage Time in Random Geometric Graphs Ghurumuruhan Ganesan1 Received: 9 March 2019 / Accepted: 3 September 2020 © Springer Science+Business Media, LLC, part of Springer Nature 2020
Abstract Let G be a random geometric graph formed by n nodes with adjacency distance rn and let each edge of G be assigned an independent exponential passage time with mean that depends on the graph size n. We connect G to two nodes source sA and destination sB at deterministic locations spaced dn apart in the unit square and find upper and lower bounds on the minimum passage time between sA and sB through paths in G having constant stretch, i.e., whose length is constrained to be proportional to the Euclidean distance between sA and sB . Keywords Random geometric graphs · Minimum passage time · Constant stretch paths Mathematics Subject Classification Primary: 60J10 · 60K35 · Secondary: 60C05 · 62E10 · 90B15 · 91D30
1 Introduction Random geometric graphs (RGGs) are natural models for wireless networks Penrose [8, 9, 12] where nodes of the graph model the communication terminals (like mobiles or sensors) and edges represent the link between two terminals. Typically, communicating across a link incurs a delay (passage time) which is modelled as a positive random edge weight and it is of interest to estimate the minimum passage time between any two given nodes in the network. For constant passage times, Bradonijic et al. [2] study efficient broadcast in RGGs by determining the shortest path to each node from the broadcaster and Franceschetti et al. [3] use percolation theoretic techniques to study transmission capacity in wireless networks. Using bin-covering techniques Pandurangan and Muthukrishnan [11] study paths with low stretch where the number of edges is proportional to the Euclidean * Ghurumuruhan Ganesan [email protected] 1
Institute of Mathematical Sciences, HBNI, Chennai, India
13
Vol.:(0123456789)
Algorithmica
distance between the endvertices. Recently, in Ganesan [6], we considered infection spread in RGGs where each edge is assigned an independent exponential weight with unit mean and obtain the speed of infection spread. In Ganesan [7], we studied diameter and stretch in random geometric graphs. In this paper, we consider RGGs with passage time distributions that depend on the graph size n and study minimum passage time paths with constant stretch (we provide the details in the following subsection). This kind of situation arises, for example, in sensor networks [5] where the total network transmit power is constrained and the network lifetime may be reduced if the sensors use up battery power with limit. In such a case, each sensor is allocated a portion of the overall energy budget and allowed to operate within this limit. In turn this implies that the probability that a link between two (sensor) nodes is good enough for communication, depends on the overall network size. Accordingly the link passage time distribution also depends on n and it is beneficial to communicate usi
Data Loading...
