International Journal Papers
Permanent URI for this collectionhttp://dl.cerist.dz/handle/CERIST/17
Browse
10 results
Search Results
Item A critical review of quality of service models in mobile ad hoc networks(Inderscience Enterprises Ltd, 2019) Bouchama, Nadir; Aïssani, Djamil; Djellab, Natalia; Nouali-Taboudjemat, NadiaQuality of service (QoS) provisioning in mobile ad hoc networks (MANETs) consists of providing a complex functionality in a harsh environment where resources are scarce. Thus, it is very challenging to build an efficient solution to address this issue. The proposed solutions in the literature are broadly classified into four categories, namely: QoS routing protocols, QoS signalling, QoS-aware MAC protocols and QoS models, which are the main concern of our study. The contribution of this paper is threefold: Firstly, we propose a set of guidelines to deal with the challenges facing QoS models design in ad hoc networks. Secondly, we propose a new taxonomy for QoS models in ad hoc networks. Finally, we provide an in-depth survey and discussion of the most relevant proposed frameworks.Item Lifetime-Aware Backpressure : A New Delay-Enhanced Backpressure-Based Routing Protocol(IEEE, 2019-03) Kabou, Abdelbaset; Nouali-Taboudjemat, Nadia; Djahel, Soufiene; Yahiaoui, Saïd; Nouali, OmarDynamic backpressure is a highly desirable family of routing protocols known for their attractive mathematical properties. However, these protocols suffer from a high end-to-end delay making them inefficient for real-time traffic with strict end-to-end delay requirements. In this paper, we address this issue by proposing a new adjustable and fully distributed backpressure-based scheme with low queue management complexity, named Lifetime-Aware Backpressure (LTA-BP). The novelty in the proposed scheme consists in introducing the urgency level as a new metric for service differentiation among the competing traffic flows in the network. Our scheme not just significantly improves the quality of service provided for real-time traffic with stringent end-to-end delay constraints, but interestingly protects also the flows with softer delay requirements from being totally starved. The proposed scheme has been evaluated and compared against other state-of-the-art routing protocol, using computer simulation, and the obtained results show its superiority in terms of the achieved end-to-end delay and throughput.Item Reachability in big graphs : A distributed indexing and querying approach(Elsevier, 2021-09) Hocine, Imane; Yahiaoui, Saïd; Bendjoudi, Ahcene; Nouali-Taboudjemat, NadiaThe advent of Big graphs characterized by their enormous number of nodes, with multiple edges between them makes the existing reachability query indexing approaches unable to guarantee a reasonable time for both the index construction and query steps. Therefore a novel approach that takes into account these new characteristics during the graph processing is needed. In this paper, we propose an Overlay Graph-based Distributed Reachability Indexing approach (ODRI), an indexing scheme through which the index construction and reachability query are processed in a parallel and distributed manner. The key idea of ODRI is to process a Big graph as a set of smaller subgraphs (partitions) interconnected to each other through an overlay graph. In this way, the partitions can be indexed in parallel and, at the same time, the reachability information can also be extracted. Hence, the index construction and query processing time will be reduced significantly. Therefore, ODRI ensures the scalability of Big graphs, which is a challenge for the existing reachability approaches. Besides, we formally prove that this strategy preserves the reachability properties. Using real-life data, we experimentally verify that our approach outperforms the state-of-the-art methods, and is scalable in terms of the number of partitions, regardless of how graphs are distributed.Item A Survey on Distributed Graph Pattern Matching in Massive Graphs(ACM, 2021-02) Bouhenni, Sarra; Yahiaoui, Saïd; Nouali-Taboudjemat, Nadia; Kheddouci, HamamacheBesides 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.Item Distributed graph pattern matching via bounded dual simulation(Elsevier, 2022-09) Bouhenni, Sarra; Yahiaoui, Saïd; Nouali-Taboudjemat, Nadia; Kheddouci, HamamacheGraph Pattern Matching (GPM) finds subgraphs of a large data graph that are similar to an input query graph. It has many applications, such as pattern recognition, detecting plagiarism, and finding communities in social networks. Current real-world applications generate massive amounts of data that cannot be stored on the memory of a single machine, which raises the need for distributed storage and processing. Recent relaxed GPM models, although of polynomial time complexity, are nevertheless not distributed by nature. Moreover, the existing relaxed GPM algorithms are limited in terms of scalability. In this paper, we propose Bounded Dual Simulation (BDSim) as a new relaxed model for a scalable evaluation of GPM in massive graphs. BDSim captures more semantic similarities compared to graph simulation, dual simulation, and even strong simulation. It preserves the vertices’ proximity by eliminating cycles of unbounded length from the resulting match graph. Furthermore, we propose distributed vertex-centric algorithms to evaluate BDSim. We prove their effectiveness and efficiency through detailed theoretical validation and extensive experiments conducted on real-world and synthetic datasets. To the best of our knowledge, BDSim is the first relaxed GPM model that captures the cyclic structure of the query graph while being feasible in cubic time.Item Multi-objective offline and online path planning for UAVs under dynamic urban environment(2022-03) Sadallah, Nassim; Yahiaoui, Saïd; Bendjoudi, Ahcene; Nouali-Taboudjemat, NadiaThis paper presents a multi-objective hybrid path planning method MOHPP for unmanned aerial vehicles (UAVs) in urban dynamic environments. Several works have been proposed to find optimal or near-optimal paths for UAVs. However, most of them did not consider multiple decision criteria and/or dynamic obstacles. In this paper, we propose a multi-objective offline/online path planning method to compute an optimal collision-free path in dynamic urban environment, where two objectives are considered: the safety level and the travel time. First, we construct two models of obstacles; static and dynamic. The static obstacles model is based on Fast Marching Square (FM2) method to deal with the uncertainty of the geography map, and the unexpected dynamic obstacles model is constructed using the perception range and the safety distance of the UAV. Then, we develope a jointly offline and online search mechanism to retrieve the optimal path. The offline search is applied to find an optimal path vis-a-vis the static obstacles, while the online search is applied to quickly avoid unexpected dynamic obstacles. Several experiments have been performed to prove the efficiency of the proposed method. In addition, a Pareto front is extracted to be used as a tool for decision making.Item Efficient parallel edge-centric approach for relaxed graph pattern matching(Springer, 2022-02) Bouhenni, Sarra; Yahiaoui, Saïd; Nouali-Taboudjemat, NadiaPrior algorithms on graph simulation for distributed graphs are not scalable enough as they exhibit heavy message passing. Moreover, they are dependent on the graph partitioning quality that can be a bottleneck due to the natural skew present in real-world data. As a result, their degree of parallelism becomes limited. In this paper, we propose an efficient parallel edge-centric approach for distributed graph pattern matching. We design a novel distributed data structure called ST that allows a fine-grain parallelism, and hence guarantees linear scalability. Based on ST, we develop a parallel graph simulation algorithm called PGSim. Furthermore, we propose PDSim, an edge-centric algorithm that efficiently evaluates dual simulation in parallel. PDSim combines ST and PGSim in a Split-and-Combine approach to accelerate the computation stages. We prove the effectiveness and efficiency of these propositions through theoretical guarantees and extensive experiments on massive graphs. The achieved results confirm that our approach outperforms existing algorithms by more than an order of magnitude.Item GPU-based Bees Swarm Optimization for Association Rules Mining(Springer, 2014) Djenouri, Youcef; Bendjoudi, Ahcène; Mehdi, Malika; Nouali-Taboudjemat, Nadia; Habbas, ZinebAssociation Rules Mining (ARM) is a well-known combinatorial optimization problem aiming at extracting relevant rules from given large scale data sets. According to the state of the art, the bio-inspired methods proved their efficiency by generating acceptable solutions in a reasonable time when dealing with small and medium size instances. Unfortunately, to cope with large instances such as the webdocs benchmark, these methods require more and more powerful processors and are time expensive. Nowadays, computing power is no longer a real issue. It can be provided by the power of emerging technologies such as GPUs that are massively multi-threaded processors. In this paper, we investigate the use of GPUs to speed up the computation. We propose two GPU-based bees swarm algorithms for association rules mining (SE-GPU and ME-GPU). SE-GPU aims at evaluating one rule at a time where each thread is associated with one transaction, whereas ME-GPU evaluates multiple rules in parallel on GPU where each thread is associated with several transactions. To validate our approaches, the two algorithms have been executed to solve well-known large ARM instances. Real experiments have been carried out on an Intel Xeon 64 bit quad-core processor E5520 coupled to an Nvidia Tesla C2075 GPU device. The results show that our approaches improve the execution time up to x100 over the sequential mono-core BSO-ARM algorithm. Moreover, the proposed approaches have been compared with CPU multi-core ones (1 to 8 cores). The results show that they are faster than the multi-core versions what ever the number of used cores.Item On performance evaluation and design of atomic commit protocols for mobile transactions(Springer US, 2010-02) Nouali-Taboudjemat, Nadia; Chehbour, Fairouz; Drias, HabibaThe challenges of wireless and mobile computing environments have attracted the attention of researchers to revisit the conventional transaction paradigm. Indeed, this paradigm is an indispensable asset in modern information systems. The atomicity property of a distributed transaction is ensured with the use of an atomic commit protocol (ACP). Due to their great importance for transaction systems, the recent advances in mobile computing development have renewed the interest in the design of ACPs for mobile systems. The work presented in this paper studies the impact of the various and fluctuant parameters of wireless and mobile systems on a set of ACPs for mobile environment. It highlights performance indices which give orientations to the design of an adaptable approach that supports different atomicity notions satisfying a wide range of applications and environment requirements.Item Extraction des lésions dans des images de scanner cérébral pour système de télédiagnostic(Springer-Verlag, 2004) Lassouaoui, Nadia; Hamami, Latifa; Nouali-Taboudjemat, Nadia; Aït Abdelkader, BelaïdLe cancer est l’une des maladies les plus répandues dans le monde. Des chercheurs ont pensé à réaliser des systèmes qui seront des outils d’aide au diagnostic et à la décision pour les médecins. La mise sur réseau de tels systèmes permet d’avoir une application de télédiagnostic, le but est d’apporter «une seconde opinion» par un spécialiste distant pour confirmer ou infirmer le diagnostic établi par le praticien local, ou bien aider ce dernier à arriver à un diagnostic correct. Afin de concevoir un tel système, plusieurs aspects sont à prendre en charge. L’un des aspects les plus importants sont les problèmes liés à la taille des images médicales par rapport au débit de transmission. Pour cela, dans le cas du cancer du cerveau, nous proposons de concevoir un module pour l’extraction des lésions, son rôle est d’extraire la lésion tout en respectant sa taille, sa forme et sa position. Ainsi, les images à transmettre sont à deux niveaux de gris, noir et blanc, donc la taille diminue. Un second objectif de ce module est de simplifier l’image pour le médecin tout en conservant toutes les caractéristiques morphologiques de la lésion. Pour cela, nous pouvons procéder de deux manières, soit extraire les limites des lésions, soit extraire toute la zone correspondant à la surface des lésions. Nous utilisons des opérateurs basés sur la théorie de le morphologie mathématique, des résultats prometteurs ont été obtenus, ce qui permettra au médecin d’entamer sûrement l’étape de diagnostic en local ou à distance. Dans ce papier nous présentons principalement notre système de télédiagnostic ainsi les différents algorithmes pour la conception de ce module de segmentation.