Low Degree Connectivity in Ad-Hoc Networks*

Ludek Kucera

Charles University, Prague




The aim of the paper is to investigate the average case behavior of certain algorithms that are designed for connecting mobile agents in the two- or three-dimensional space. The general model is the following: let X be a set of points in the d-dimensional Euclidean space Ed, d ≥ 2; r be a function that associates each element of x ε X with a positive real number r(x). A graph G(X,r) is an oriented graph with the vertex set X, in which (x,y) is an edge if and only if ρ(x,y)≤ r(x), where ρ(x,y) denotes the Euclidean distance in the space Ed. Given a set X, the goal is to find a function r so that the graph G(X,r) is strongly connected (note that the graph G(X,r) need not be symmetric). Given a random set of points, the function r computed by the algorithm of the present paper is such that, for any constant δ, the average value of r(x)δ  (the average transmitter power) is almost surely constant.


Keywords: wireless network, radio network, power minimizing, probabilistic analysis, percolation theory



(visualization of algorithms)


A system of applets for algorithm visualization and teaching

The system covers the following algorithms:

Data Structures: binary search tree, AVL-tree, red&black tree, Btree

Sorting: mergesort, heapsort, quicksort, bubble sort, O(N) time median, bitonic sorting

Graph Algorithms: different algorithms for shortest path, min spanning tree and network flows, spectral heuristic for min-cut

Arithmetic Algorithms: carry look-ahead addition, fast Fourier transform

Geometric Algorithms: convex hull and Voronoi diagram in the plane

String Searching: Rabin-Karp, Knuth-Morris-Pratt, Aho-Corasick

Linear Programming: geometric intuition of Simplex Algorithm

Algovision is used for teaching algorithm at the Charles University (advanced undergraduate course), a textbook based on Algovision (Czech and English edition) is expected in the second quarter of 2006. The applets are designed to show not only how, but also why the algorithms work, in certain cases even proof of correctness and/or complexity is visualized or animated.



*presented at European Symposium on Algorithms 2005.