Academic & Scientific Articles

Permanent URI for this communityhttp://dl.cerist.dz/handle/CERIST/3

Browse

Subject: search.filters.subject.Distributed algorithms

Search Results

Now showing 1 - 4 of 4
  • Thumbnail Image
    Item
    A Survey on Distributed Graph Pattern Matching in Massive Graphs
    (ACM, 2021-02) Bouhenni, Sarra; Yahiaoui, Saïd; Nouali-Taboudjemat, Nadia; Kheddouci, Hamamache
    Besides its NP-completeness, the strict constraints of subgraph isomorphism are making it impractical for graph pattern matching (GPM) in the context of big data. As a result, relaxed GPM models have emerged as they yield interesting results in a polynomial time. However, massive graphs generated by mostly social networks require a distributed storing and processing of the data over multiple machines, thus, requiring GPM to be revised by adopting new paradigms of big graphs processing, e.g., Think-Like-A-Vertex and its derivatives. This article discusses and proposes a classification of distributed GPM approaches with a narrow focus on the relaxed models.
  • Thumbnail Image
    Item
    Improved coverage through area-based localization in wireless sensor networks
    (IEEE, 2013-10) Lasla, Noureddine; Younis, Mohamed; Badache, Nadjib
    Ensuring area coverage is one of the key requirements of wireless sensor networks (WSNs). When nodes are randomly placed in the area of interest, redundancy is often provisioned in order to lower the probability of having voids, where part of the area is not within the detection range of any sensor. To extend the lifetime of the network, a duty cycle mechanism is often applied in which only a subset of the nodes are activated at a certain time while the other nodes switch to low-power mode. The set of active nodes are changed over time in order to balance the load on the individual sensors. The selection of active nodes is subject to meeting the coverage requirement. Assessing the coverage of a sensor is based on knowing its position. However, localization schemes usually yield a margin of errors which diminishes the coverage fidelity. Conservative approaches for mitigating the position inaccuracy assume the worst-case error across the network and end up activating excessive number of nodes and reduces the network lifetime. In this paper, we present an approach for estimating a bound on the maximum error for the position of each sensor and propose a distributed algorithm for achieving high fidelity coverage while engaging only a subset of the sensors. The simulation results confirm the performance advantages of our approach.
  • Thumbnail Image
    Item
    Fast distributed multi-hop relative time synchronization protocol and estimators for wireless sensor networks
    (Elsevier, 2013-11) Djenouri, Djamel; Merabtine, Nassima; Mekahlia, Fatma Zohra; Doudou, Messaoud
    The challenging problem of time synchronization in wireless sensor networks is considered in this paper, where a new distributed protocol is proposed for both local and multi-hop synchronization. The receiver-to-receiver paradigm is used, which has the advantage of reducing the time-critical-path and thus improving the accuracy compared to common sender-to-receiver protocols. The protocol is fully distributed and does not rely on any fixed reference. The role of the reference is divided amongst all nodes, while timestamp exchange is integrated with synchronization signals (beacons). This enables fast acquisition of timestamps that are used as samples to estimate relative synchronization parameters. An appropriate model is used to derive maximum likelihood estimators (MLE) and the Cramer-Rao lower bounds (CRLB) for both the offset-only, and the joint offset/skew estimation. The model permits to directly estimating relative parameters without using or referring to a reference’ clock. The proposed protocol is extended to multi-hop environment, where local synchronization is performed proactively and the resulted estimates are transferred to the intermediate/end-point nodes on-demand, i.e. as soon as a multi-hop communication that needs synchronization is initiated. On-demand synchronization is targeted for multi-hop synchronization instead of the always-on global synchronization model, which avoids periodic and continuous propagation of synchronization signals beyond a single-hop. Extension of local MLE estimators is proposed to derive relative multi-hop estimators. The protocol is compared by simulation to some state-of-the-art protocols, and results show much faster convergence of the proposed protocol. The difference has been on the order of more than twice compared to CS-MNS, more than ten times compared to RBS, and more than twenty times compared to TPSN. Results also show scalability of the proposed protocol concerning the multi-hop synchronization. The error does not exceed few microseconds for as much as 10 hops in R4Syn, while in CS-MNS, and TPSN, it reaches few tens of microseconds. Implementation and tests of the protocol on real sensor motes confirm microsecond level precision even in multi-hop scenarios, and high stability (long lifetime) of the skew/offset model.
  • Thumbnail Image
    Item
    Self-stabilizing algorithms for minimal global powerful alliance sets in graphs
    (ELSEVIER SCIENCE, 2013-05) Belhoul, Yacine; Yahiaoui, Saïd
    We propose a self-stabilizing distributed algorithm for the minimal global powerful alliance set problem in an arbitrary graph. Then, we give self-stabilizing algorithms for some generalizations of the problem. Using an unfair distributed scheduler, the proposed algorithms converge in O (mn) moves starting from an arbitrary state