Search

We present a silent self-stabilizing distributed algorithm computing a maximal |$\ p$| -star decomposition of the underlying communication network. Under the unfair distributed scheduler, the most general scheduler model, the algorithm converges in at most |$12\Delta m + \mathcal{O}(m+n)$| moves, where |$m$| is the number of edges, |$n$| is the number of nodes and |$\Delta $| is the maximum node degree. Regarding the time complexity, we obtain the following results: our algorithm outperforms the previously known best algorithm by a factor of |$\Delta $| with respect to the move complexity. While the round complexity for the previous algorithm was unknown, we show a |$5\big \lfloor \frac{n}{p+1} \big \rfloor +5$| bound for our algorithm. [ABSTRACT FROM AUTHOR]

Self-monitoring is a simple and effective mechanism for surveilling wireless sensor networks, especially to cope against faulty or compromised nodes. A node v can monitor the communication over a link e if both end-nodes of e are neighbors of v . Finding a set of monitoring nodes satisfying all monitoring constraints is called the edge-monitoring problem . The minimum edge-monitoring problem is known to be NP-complete. In this paper, we present a novel self-stabilizing algorithm for computing a minimal edge-monitoring set under the unfair distributed scheduler. For sparse networks the time complexity of this new algorithm is much lower than the currently best known algorithm. [ABSTRACT FROM AUTHOR]

In computer networks area, the minimal dominating sets (MDS) and maximal independent sets (MIS) structures are very useful for creating virtual network overlays. Often, these set structures are used for designing efficient protocols in wireless sensor and ad-hoc networks. In this paper, we give a particular interest to one kind of these sets, called Independent Strong Dominating Set (ISD-set). In addition to its domination and independence properties, the ISD-set considers also node's degrees that make it very useful in practical applications where nodes with larger degrees play important role in the networks. For example, some network clustering protocols chose nodes with large degrees to be cluster-heads, which is exactly the result obtained by an ISD-set algorithm. Thence, we propose the first distributed self-stabilizing algorithm for computing an ISD-set of an arbitrary graph (called ISDS). Then, we prove that ISDS algorithm operates under the unfair distributed scheduler and converges after at most rounds requiring only space memory per node where Δ is the maximum node degree. The complexity of ISDS algorithm in rounds has the same order as the best known self-stabilizing algorithms for finding MDS and MIS. Moreover, performed simulations and comparisons with well-known self-stabilizing algorithms for MDS and MIS problems showed the efficiency of ISDS, especially for reducing the cardinality of dominating sets founded by the algorithms. [ABSTRACT FROM AUTHOR]