Abstract: The vertex connectivity of a graph is the smallest number of vertices whose deletion separates the graph or makes it trivial. This work is devoted to the problem of vertex connectivity test of graphs in a distributed environment based on a general and a constructive approach. The contribution of this paper is threefold. First, using a preconstructed spanning tree of the considered graph, we present a protocol to test whether a given graph is 2-connected using only local knowledge. Second, we present an encoding of this protocol using graph relabeling systems. The last contribution is the implementation of this protocol in the message passing model. For a given graph G, where M is the number of its edges, N the number of its nodes and Δ is its degree, our algorithms need the following requirements: The first one uses O(Δ×N2) steps and O(Δ×logΔ) bits per node. The second one uses O(Δ×N2) messages, O(N2) time and O(Δ × logΔ) bits per node. Furthermore, the studied network is semi-anonymous: Only the root of the pre-constructed spanning tree needs to be identified.
Abstract: Sensor network applications are often data centric and
involve collecting data from a set of sensor nodes to be delivered
to various consumers. Typically, nodes in a sensor network are
resource-constrained, and hence the algorithms operating in these
networks must be efficient. There may be several algorithms available
implementing the same service, and efficient considerations may
require a sensor application to choose the best suited algorithm. In
this paper, we present a systematic evaluation of a set of algorithms
implementing the data gathering service. We propose a modular
infrastructure for implementing such algorithms in TOSSIM with
separate configurable modules for various tasks such as interest
propagation, data propagation, aggregation, and path maintenance.
By appropriately configuring these modules, we propose a number
of data gathering algorithms, each of which incorporates a different
set of heuristics for optimizing performance. We have performed
comprehensive experiments to evaluate the effectiveness of these
heuristics, and we present results from our experimentation efforts.