Global ETD Search
Search theses and dissertations gathered from participating repositories worldwide. Every result links back to the library that holds it. No account is needed.
Results
Showing 1 to 20 of 22 for “"unit-disk graph"”.
-
Self-stabilizing k-clustering in mobile ad hoc networks
… is known to be NP -hard. If the network is a unit disk graph in a plane, BFS-MIS-CLSTR is within a factor of O(7.2552k) of choosing the minimal number of clusters; A lower bound is given, showing that any comparison-based algorithm for the k-clustering problem that takes o( diam) rounds has …
-
Algorithms for Unit-Disk Graphs and Related Problems
… we study algorithms for several problems on unit-disk graphs and related problems. The unit-disk graph can be viewed as an intersection graph of a set of congruent disks. Unit-disk graphs have been extensively studied due to many of their applications, e.g., modeling the topology of wireless …
-
Throughput Stability and Flows in Large-Scale Random Networks
… multicommodity flow on the corresponding random unit-disk graph and shown to be equivalent. In this way, using simple flow techniques and probability tools, a tight bound is derived on the rate of growth of the maximum stable throughput with a fairness constraint. As an application of these …
-
A generalization of the face routing algorithm to some non-planar networks
… for them. Routing algorithms which use the geographical location information of nodes are called position-based routing algorithms. In such algorithms, the ad hoc network is modeled as a geometric graph known as the unit disk graph. The FACE ROUTING algorithm is one such position-based routing …
-
Effective algorithms and protocols for wireless networking: a topological approach
… for such networks are based on the ideal model Unit Disk Graph (UDG) model or do not assume any model. Furthermore, many results assume the knowledge of location information of the network. In practice, sensor networks often deviate from the UDG model significantly. It is not uncommon to observe …
-
Partial Delaunay triangulations based routing, address configuration and date-centric storage in ad hock network
… algorithm that guarantees delivery in connected unit disk graphs (where two nodes are connected if and only if their distance is no more than the transmission radius, which is equal for all nodes). The FACE mode is a recovery mode used when no neighbor closer to destination exists. FACE mode …
-
Position-based routing algorithms for three-dimensional ad hoc networks
… routing algorithms, the nodes use the geographical information to make routing decisions. Recent research in this field addresses such routing algorithms in two-dimensional (2 D ) space. However, in real applications, the nodes may be distributed in three-dimensional (3 D ) space. …
-
Energy-efficient Data Aggregation Using Realistic Delay Model in Wireless Sensor Networks
… Hence, the LMST edges might be replaced by unit disk graph (UDG) edges which can progress further in LMST. The DEP metric is rooted on realistic degree-based delay model so that DEDA increases the delay reliability to a large extent compared to other hop-based algorithms. We also combine our …
-
3-D routing algorithms in mobile ad hoc networks
A unit disk graph and its proximity graphs are often used as the underlying topologies of a mobile ad hoc network. One category of unicast routing algorithms, position-based routing algorithms, has been developed and studied extensively in the context of 2-dimensions (2-D). This, however, poses …
-
Scalable analogue optimisation on a neutral atom array
… dipole traps are demonstrated, using novel holographic techniques to generate arrays of optical potentials capable of coherently trapping arrays of Rydberg atoms. Simulations presented in this thesis are used to confirm the viability of this scheme and find optimal trapping …
-
Bluetooth scatternet formation protocol for wireless devices based on maximal independent sets
… nodes that are positioned so that their unit disk graph is connected, the Bluetooth scatternet formation (BSF) problem is to select piconets, and the master and slave roles within each piconet, so that the obtained scatternet is connected, has some desirable properties, and shows good …
-
Load balancing in multi-hop wireless ad hoc networks
… in wireless ad hoc networks. Using a discrete unit disk graph model of the network, we analyze the distribution of load induced by greedy routing in the network with an all-to-all communication pattern between the nodes. We derive an estimate for average load of the nodes in the network. We …
-
A clustered back-bone for routing in ad-hoc networks
… clusters. The ultimate aim of forming a routing graph over which power-efficient routing can be implemented in a simple and effective manner is realized by partitioning the network into disjoint clusters and thereafter joining them through gateways to form a connected, planar back-bone which is …
-
Self-stabilizing group membership protocol
… is, a partition of X into disjoint connected subgraphs, which we call groups, each of diameter no greater than D. The minimal group partition problem is to find a D-partition {G1, ... Gm} of X such that no two groups can be combined; that is, for any Gi and Gj, where i ≠ j, either Gi U Gj is …
-
Routing in sensing-covered ad hoc networks
… approach is based on a grid technique and the unit disk graph ( UDG ). This technique makes sure that a region is fully covered by a small number of sensor nodes. To experiment with variations of the generated graph, we introduce a new subgraph of the UDG. This graph is a generalization of the …
-
Virtual backbone formation in wireless ad hoc networks
… network with symmetric links represented by a unit disk graph G = (V, E ), one way to construct this backbone is by finding a Connected Dominating Set (CDS) in G , which is a subset V' ✹ V such that for every node u, u is either in V' or has a neighbor in V' and the subgraph induced by V' is …
-
Network Modeling and Interference Analysis in Pervasive Technology
… networks are easily modeled by a family of graphs called unit disk graph (UDG). The degree distribution of a unit disk graph is an important aspect for investigating the behavior of a wireless network. In the literature, several studies was focused on the degree distribution of unit disk …
-
A Framework for Service Differentiation and Optimization in Multi-hop Wireless Networks
… framework, we first model the MHWN as a Unit Disk Graph (UDG). The optimal transmission schedule in the MHWN is related to the chromatic number of the UDG, which is very expensive to compute. However, the clique number, which is a lower bound on the chromatic number, can be computed in …
-
Disk Intersection Graphs: Models, Data Structures, and Algorithms
Let P be a set of n point sites in the plane. The unit disk graph UD(P) on P has vertex set P and an edge between two sites p,q of P if and only if p and q have Euclidean distance |pq| <= 1. If we interpret P as centers of disks with diameter 1, then UD(P) is the intersection graph of these disks, …
-
Routing and Stabbing
ROUTING. Let G be a simple, connected, undirected graph. We consider routing with preprocessing in G. In a preprocessing step, each vertex of G receives a label and a routing table. Then, we must be able to route a packet between any two vertices s and t of G, where each step may use only the label …
Page 1 of 2