(r,s)-civilized graphs by Krumke, Marathe, and Ravi Dial-M 1998 and Wireless Networks Journal Vol. 3(2) 2003 Other generalizations of the unit disk graph have been proposed, e.g. d May have an edge if dWe need something between UDG and arbitrary graphs: general enough to model reality as close as possible restrictive enough to allow useful theoretical results DIALM-POMC 2003ĥ Quasi Unit Disk Graph Definition Unit Disk Graph:Įdge between u and v if |u-v|♱ No edge between u and v if |u-v|>1 Definition Quasi Unit Disk Graph: Edge between u and v if |u-v| Realistic Models We need more general graph models However, arbitrary graphs are too general to obtain strong results for routing, etc. Far from reality BUT: There are numerous theoretical results. Simple Models Unit Disk Graph is most widely applied model: Underlying assumption: All nodes are in R2, have exactly the same transmission range (normalized to one), and there are no obstacles. Mobile Devices communicating via radio Network without centralized control (base station) We consider the abstraction level of graphs DIALM-POMC 2003
#Unit disk graph how to#
Graph Models for Mobile Ad-Hoc Networks Quasi Unit Disk Graphs Related Work Volatile Memory Routing Flooding Lower Bound for Message Complexity Topology for Optimal Flooding Greedy + Flooding Volatile Memory Routing Algorithms Combining Greedy and Flooding Geometric Routing for How to obtain a planar graph Optimality of AFR/GOAFR DIALM-POMC 2003 1 Ad-Hoc Networks Beyond Unit Disk Graphsįabian Kuhn Roger Wattenhofer Aaron ZollingerĢ Overview Introduction Flooding Greedy + Flooding Geometric Routing for
0 kommentar(er)
