Spelling suggestions: "subject:"selfstabilizing"" "subject:"destabilizing""
1 |
Mobilité et gestion efficace des fréquences dans un réseau ad hoc à forte efficacité / Mobility model and resource allocation in high efficiency opportunistic networksPomportes, Stephane 12 December 2011 (has links)
En cas de catastrophes importantes, telles qu’un tremblement de terre ou un incendie, l’efficacité des forces de la sécurité civile nécessite une bonne coordination des différents groupes d’intervention. Suivant la nature et l’importance du sinistre, l’infrastructure des moyens de communications classique peut être détruite. Les forces d’intervention ont donc besoin de nouveaux outils de communication dits réseaux de circonstance. Ces réseaux posent de nouveaux problèmes de routage, pour maintenir la connectivité, mais aussi d’allocation de ressources, particulièrement importante dans un contexte de sécurité où les communications doivent être garanties. Dans une première partie, nous avons abordé la problématique de l’allocation de ressources dans les réseaux de circonstance utilisant le partage TDMA. Nos solutions visent une répartition équitable des canaux et prennent en compte une zone d’interférence double de celle de transmission.Evaluer de nouvelles politiques dans des réseaux déployés sur des scènes de catastrophe nécessite de nouveaux modèles de mobilité. Nous avons donc également développé un nouveau modèle de mobilité spécifique au déplacement des équipes de la sécurité civile. / When a major disaster occurs, such as an earthquake or fire, the efficiency of the rescue workers depends of the coordination between the different emergency teams. This coordination needs reliable communication equipments. In such a situation, however, the infrastructure for wireless communication is generally destroyed or unusable. It is therefore necessary to find adapted communication tools for the rescue workers known as opportunistic networks. These networks pose new challenging problems such as, for instance, resource allocation which is particularly important for the QoS satisfaction. In the first part of our thesis, we addressed the problem of resource allocation in ad hoc networks using the TDMA access mechanism. Our solutions aim to perform a fair distribution of channels and take into account an interference area twice as large as the transmission range. Evaluation of new policies for opportunistic networks deployed in disaster areas requires new mobility models. We developed a novel mobility model dedicated to the movement of rescue workers. Our model includes the group mobility and some characteristics of human mobility. It also incorporates a mechanism to circumvent obstacles presents in the simulation area.
|
2 |
Auto-organisation et routage dans les réseaux mobiles ad hoc / Self-organizing and routing in mobile ad hoc networksHaggar, Bachar Salim 30 June 2011 (has links)
Nos travaux se positionnent dans le cadre de l'algorithmique distribuée et plus particulièrement des réseaux ad hoc. Les réseaux ad hoc sont auto-organisés en permettant des échanges directs entre nœuds mobiles et ne reposent sur aucune infrastructure. Chaque nœud peut se déplacer librement et indépendamment des autres impliquant une modification perpétuelle de la topologie. Dans ce contexte, la probabilité que des défaillances surviennent dans le réseau est importante. Ces défaillances gênent le bon fonctionnement du réseau et peuvent même entrainer une paralysie de celui-ci. C'est pourquoi la conception de solutions pour de tels réseaux nécessitent des mécanismes de gestion de fautes. Parmi ceux-ci, l'approche d'auto-stabilisation permet à un système de gérer les fautes transitoires. Nous étendons cette approche pour répondre aux principaux problèmes liés à la mobilité des nœuds. Notre objectif est de répondre à un double besoin d'auto-organisation du réseau et d'optimisation du nombre de messages échangés. Notre approche consiste à découper le réseau en clusters afin de lui donner une structure hiérarchique. Cette dernière rend l'utilisation du réseau plus efficace et plus performante. L'algorithme que nous avons développé à cet effet est auto-stabilisant et n'est basé que sur des connaissances locales. Nous exploitons cette solution pour proposer deux utilisations efficaces : la diffusion d'informations dans le réseau et le routage. La diffusion d'informations exploite un arbre couvrant inter-clusters, construit sans surcoût, en parallèle de la clusterisation. Le routage quant à lui exploite cet arbre pour permettre à la fois d'optimiser le délai de bout en bout et le nombre de messages échangés. / Our work relies in the domain of distributed system, more preciselly ad hoc networks. Ad hoc networks are self-organized allowing direct exchanges between mobile nodes and do not rely on any infrastruture. Each node can move freely and independently of each others involving continuous topology variability. In this context, the probability that a failure occurs in the network is high. These failures hinder the proper functioning of the network and even causes its paralysis. Therefore, designing solutions for such networks requires fault management mechanisms. Among these, a self-stabilizating approach allows the system to withstand transient faults. We extend this approach to answer the problems induced by nodes mobility. We have two main objectives: a self-organizing network and optimizing number of exchanged messages. Our approach consists in dividing the network into clusters in order to give it a hierarchical structure. This solution allows a more efficient and effective network use. The algorithm that we developed for this purpose is a self-stabilizing algorithm based only on local informations. Based on this solution, we propose two efficient use cases: Information broadcast and a routing protocol. Information broadcast uses an inter-cluster spanning tree, generated without any overhead. In the same time as the clustering process. The routing protocol uses this tree for both round trip and number of exchanged messages optimization.
|
3 |
Large deviations and exit time asymptotics for diffusions and stochastic resonancePeithmann, Dierk 10 December 2007 (has links)
Diese Arbeit behandelt die Asymptotik von Austritts- und Übergangszeiten für gewisse schwach zeitinhomogene Diffusionsprozesse. Darauf basierend wird ein probabilistischer Begriff der stochastischen Resonanz (SR) studiert. Techniken der großen Abweichungen spielen eine zentrale Rolle. Im ersten Teil der Arbeit (Kapitel 1-3) werden Resultate aus der Theorie der großen Abweichungen für zeithomogene Diffusionen rekapituliert. Es werden die klassischen Resultate von Freidlin und Wentzell und Erweiterungen dieser Theorie präsentiert, und es wird an das Kramers''sche Austrittszeitengesetz erinnert. Teil II befasst sich mit dem Phänomen der SR, d.h. mit Periodizitätseigenschaften von Diffusionen. In Kapitel 4 werden physikalische Maße zur Messung der Periodizität diskutiert. Deren Nachteile legen es nahe, einem alternativen, probabilistischen Ansatz zu folgen, der hier behandelt wird. Das 5. Kapitel dient der Herleitung eines gleichmäßigen Prinzips der großen Abweichungen für Diffusionen mit schwach zeitabhängigem, periodischem Drift. Die Gleichmäßigkeit des Prinzips ermöglicht die exakte Bestimmung exponentieller Übergangsraten in Kapitel 6, das die zentralen Ergebnisse des 2. Teils beinhaltet. Hierdurch wird die Maximierung gewisser Übergangswahrscheinlichkeiten ermöglicht, was zum in Kapitel 7 studierten Resonanzbegriff führt. Teil III der Arbeit setzt sich mit der Asymptotik von Austrittszeiten sogenannter selbststabilisierender Diffusionen auseinander. In Kapitel 8 wird der Zusammenhang zwischen interagierenden Teilchensystemen und selbststabilisierenden Diffusionen erläutert und die Existenz- und Eindeutigkeitsfrage behandelt. Das 9. Kapitel dient dem Studium der großen Abweichungen dieser Klasse von Diffusionen. In Kapitel 10 wird das Kramers''sche Austrittszeitengesetz auf selbststabilisierende Diffusionen übertragen, und in Kapitel 11 wird der Einfluß der selbststabilisierenden Komponente auf das Austrittszeitengesetz illustriert. / In this thesis, we study the asymptotic behavior of exit and transition times of certain weakly time inhomogeneous diffusion processes. Based on these asymptotics, a probabilistic notion of stochastic resonance (SR) is investigated. Large deviations techniques play the key role throughout this work. In the first part (Chapters 1-3) we recall the large deviations theory for time homogeneous diffusions. We present the classical results due to Freidlin and Wentzell and extensions thereof, and we remind of Kramers'' exit time law. Part II deals with the phenomenon of stochastic resonance. That is, we study periodicity properties of diffusion processes. In Chapter 4 we explain the paradigm of stochastic resonance and discuss physical notions of measuring periodicity of diffusions. Their drawbacks suggest to follow an alternative probabilistic approach, which is treated in this work. In Chapter 5 we derive a large deviations principle for diffusions subject to a weakly time dependent periodic drift term. The uniformity of the obtained large deviations bounds w.r.t. the system''s parameters plays a key role for the treatment of transition time asymptotics in Chapter 6, which contains the main result of the second part. The exact exponential transition rates obtained here allow for maximizing transition probabilities, which finally leads to the announced probabilistic notion of resonance studied in Chapter 7. In the third part we investigate the exit time asymptotics of a certain class of so-called self-stabilizing diffusions. In Chapter 8 we explain the connection between interacting particle systems and self-stabilizing diffusions, and we address the question of existence. The following Chapter 9 is devoted to the study of the large deviations behavior of these diffusions. In Chapter 10 Kramers'' exit law is carried over to our class of self-stabilizing diffusions. Finally, the influence of self-stabilization is illustrated in Chapter 11.
|
4 |
Vers une structuration auto-stabilisante des réseaux ad hoc : cas des réseaux de capteurs sans fil / Towards a self-stabilizing structuring of ad hoc networks : the case of wireless sensor networksBa, Mandicou 21 May 2014 (has links)
Nous proposons un algorithme original de structuration des réseaux ad hoc nommé SDEAC dans le but d'optimiser les communications et de tolérer les pannes transitoires. SDEAC est auto-stabilisant, distribué et déterministe. Il utilise un modèle asynchrone à passage de messages et se fonde sur un voisinage à distance 1 pour construire des clusters non-recouvrants à k sauts. Nous montrons que partant d'une configuration quelconque et sans occurrence de pannes transitoires, SDEAC structure le réseau dans le pire des cas en n+2 transitions. En outre, son exécution nécessite une occupation mémoire de (Δu+1)*log(2n+k+3) bits pour chaque noeud u, avec Δu étant le degré de u, k le rayon maximal des clusters et n la taille du réseau. Par simulation sous OMNeT++, nous observons pour un réseau quelconque un temps de stabilisation très inférieur à celui du pire des cas d'une part. D'autre part, suite à l'occurrence de pannes transitoires après la stabilisation, nous constatons un temps de stabilisation inférieur à celui du clustering. Dans le contexte des RCSF, nous étudions la consommation énergétique de SDEAC suivant trois critères d'élection des cluster-heads (identité, degré et énergie résiduelle des noeuds) puis nous la comparons avec celle de la solution de Mitton et al. opérant dans le même modèle. Les résultats montrent que SDEAC permet le passage à l'échelle et réduit la consommation énergétique de 42% à 49%. Enfin, pour l'utilisation de SDEAC dans l'acheminement de l'information, nous proposons deux approches efficaces : (i) un routage sans agrégation qui minimise les délais de bout en bout et (ii) un routage avec agrégation partielle qui réduit la consommation énergétique totale offrant ainsi une meilleure durée de vie du réseau. / We propose SDEAC, a self-Stabilizing Distributed Energy-Aware and fault-tolerant Clustering algorithm. SDEAC uses an asynchronous message-passing model and is based on 1-hop neighboring to build non-overlapping k-hops clusters. We prove that, starting from an arbitrary configuration, SDEAC structures the network after at most n + 2 transitions and requires (Δu+1)log(2n+k+3) memory space for each node u, where n is the number of network nodes, Δu is the degree of u and k represents the maximum hops number. Through simulations under OMNeT++, we observe that over arbitrary network, the stabilization time is far below the worst case scenario. Furthermore, we remark that after faults, the re-clustering cost is significantly lower than the clustering cost. In the context of Wireless Sensor Networks (WSNs), we evaluate the energy consumption of SDEAC according to multiple criteria in the election of cluster-heads, such as nodes' identity, residual energy or degree and we compare it with the well-known message-passing based self-stabilizing clustering algorithm proposed by Mitton et al. Results show that SDEAC is scalable and reduces energy consumption between 42% and 49%.Afterwards, we propose efficient scenarios in order to transfer information: (i) the non-aggregation scenario that provides a better end-to-end delay and (ii) the partially-decentralized aggregation scenario that reduces the total energy consumption and prolongs the network lifetime.
|
5 |
Processus auto-stabilisants dans un paysage multi-puits / Self-stabilizing processes in a multi-well landscapeTugaut, Julian 06 July 2010 (has links)
Les processus auto-stabilisants sont définis comme des solutions d'équations différentielles stochastiques dont le terme de dérive contient à la fois le gradient d'un potentiel ainsi qu'un terme non-linéaire au sens de McKean qui attire le processus vers sa propre loi de distribution. On dispose de nombreux résultats lorsque l'environnement est convexe. L'objet de ce travail est de les étendre autant que possible au cas général notamment lorsque le paysage contient plusieurs puits. Des différences fondamentales sont constatées.Le premier chapitre prouve l'existence d'une solution forte. Le second s'intéresse aux lois de probabilités d'une telle solution. En particulier, l'existence et la non-unicité des mesures stationnaires sont mises en évidence sous des hypothèses faibles. Les chapitres trois et quatre sont affectés au comportement de ces mesures lorsque le coefficient de diffusion tend vers 0.Le chapitre cinq met en relation le processus auto-stabilisant avec des systèmes particulaires via une « propagation du chaos ». Il est ainsi possible de transposer certains résultats du système de particules sur le processus non-markovien et réciproquement. Le chapitre six est dédié au dénombrement exact des mesures stationnaires.Le chapitre sept est employé pour l'étude du comportement en temps long. D'une part, un résultat de convergence dans un cas simple est fourni. D'autre part, un principe de grandes déviations est mis en évidence par l'utilisation des résultats de Freidlin et Wentzell / Self-stabilizing processes are defined as the solutions of stochastic differential equations which drift term contains the gradient of a potential and a term nonlinear in the sense of McKean which attracts the process to its own law distribution. There are many results if the landscape is convex. The purpose of this work is to extend these in the general case especially when the landscape contains contains several wells. Essential differences are found.The first chapter proves the strong existence of a solution. The second one deals with the probability measure of the solution. Particularly, the existence and the non-uniqueness of the stationary measures are highlighted under weak assumptions. Chapter three and four are assigned to the asymptotic analysis in the small noise limit of these measures.Chapter five connects the self-stabilizing process and some particle systems via a « propagation of chaos ». It is thus possible to translate some results from the particle systems to the non-markovian process and reciprocally.Chapter seven is used to study the long time behavior. In one hand, a convergence's result is provided in a simple case. In the other hand, a large deviations principle is highlighted by using the results of Freidlin and Wentzell
|
6 |
A Gimbal Stabilizer : Self-stabilizing platform for holding objects horizontally stable / En självstabiliserande plattform med lastbärande förmågaSvjatoha, Maksims, Yosef Nezhad Arya, Behnam January 2019 (has links)
This bachelor thesis is about the design and construction of a self-stabilizing platform. The purpose of this system is to balance objects placed upon the platform by keeping the platform level regardless of how the mechanism itself is rotated. Its uses include stabilization of sensors, cameras and vehicle cockpits. The prototype was constructed using 3D printing and basic machining. It uses two DC motors, an inertial measurement unit, an Arduino Uno microcontroller and a motor driver. The inertial measurement unit acts as an accelerometer and gyroscope, it measures the change in position and angle relative to its starting position. The controller algorithm processes the sensor signal and calculates an appropriate output signal. This output signal regulates the two DC motors in such a way that compensates for any angle changes in the platform. This project is based on, and is the continuation of the work by J. Larsson, titled ”Gimbal stabilizer for cockpit bases of terrain vehicle or combat boat: A proof of concept”. The task is to develop it to a functioning physical prototype and implement a control system which is fast, responsive and precise. The controller tuning process involved a trial and error approach, using binary search between parameters that give a performance that is too slow and a performance that is too fast and unstable. A satisfactory performance was achieved and the platform could effectively stabilize objects that weigh 400 grams at its center, 200 grams at its edges and 100 grams at its corners. This takes 100 milliseconds on average. Besides bearing loads, the platform could also compensate for sudden forced angle changes and any tilting of the mechanism the platform is attached to. / Det här kandidatexamensarbetet handlar om konstruktionen och framtagningen av en prototyp för en självstabiliserande plattform med ändamålet att hålla ett objekt horisontellt stabil. Det innebär att oberoende av hur mekanismen vrids eller rör sig kommer plattformen alltid vara parallell med marken. Appliceringsområden för plattformen kan vara att stabilisera kameror och sensorer, samt att hålla förarkabinen i en båt horisontellt stabil oavsett hur vattnet runtomkring rör sig. Prototypen består av en 3D-printad mekanism med två likströmsmotorer, en tröghetssensor, Arduino och motordrivare. Tröghetssensorn fungerar som en accelerometer och gyroskop - den avläser hur mycket plattformen ändrar sitt läge och vinkel relativt de ursprungliga. Data från tröghetssensorn bearbetas i en Arduino Uno-mikrokontroller med hjälp av reglerteknik, där en så kallad PID-regulator beräknar utsignal beroende på insignal. Arduinon skickar sedan utsignalen till motordrivaren som reglerar likströmsmotorerna för att kompensera för eventuella vinkeländringar. Detta projekt ¨ar ett utvecklingsarbete av ett tidigare masterexamensarbete av J. Larsson, med titeln ’ ’Gimbal stabilizer for cockpit bases of terrain vehicle or combat boat: A proof of concept”. Målet är att gå från ett koncept till en praktisk och verklighetsbaserad prototyp, samt att designa en regulator med god precision, stabilitet och responstid. För att bestämma hur regulatoralgoritmen ska fungera användes binärsökning för att hitta vilka P, I och D-värden PID-regulatorn ska ha. Det innebär att man ständigt tar ett medelvärde av en för långsam regulator och en som är för snabb och aggressiv tills önskad prestanda uppnås. Den slutgiltiga prestandan ansågs vara tillräcklig och plattformen kunde effektivt stabilisera 400 gram i mitten på den, 200 gram på dess sidor och 100 gram på dess hörn på ungefär 100 millisekunder. Vidare kunde den kompensera för plötsliga påtvingade vinkeländringar och för lutning hos mekanismen som den sitter fast i.
|
7 |
Handheld container stabilizer / Självstabiliserande behållareMurtaza, Alexander, Stenström, Oscar January 2019 (has links)
Self-stabilizing systems can be found in many contexts. They are used in aircraft and camera gimbals to name a few. In this project, a self-stabilizing container was constructed. The construction consists of three parts. An inner ring which rotates around the Z-axis, an outer ring which rotates around the Y-axis and a handle with space for three DC motors and a microcontroller. In this project an Arduino Nano was used. To detect inclination an IMU (Inertial Measurement Unit) was deployed. An IMU is a sensor consisting of three gyroscopes and three accelerometers, one for each coordinate axis. The software for the construction consists of four parts; angle reading, a Kalman filter, two PID-controllers and a motor controller. When a container is inserted into the construction the four-part system keeps the container horizontal and stable. Experimental data shows that in 84% of the tests the construction could stabilize the container. / Självstabiliserande system kan man finna i många olika sammanhang. Några exempel på självstabiliserande system är flygplan och kamerastabilisatorer. I detta projekt konstruerades en självstabiliserande behållare. Konstruktionen består av tre delar. En ring som kan rotera runt Z-axeln, en ring som kan rotera runt Y-axeln och ett handtag med plats för likströmsmotorer och mikrokontroller. I detta projekt användes Arduino Nano. För att avläsa vinklarna användes en tröghetsmäatare. En tröghetsmätare är en sensor som består av tre gyroskop och tre accelerometrar, en för varje axel. Mjukvaran i konstruktionen består av fyra delar; vinkelavläsning, ett Kalmanfilter, två PID-regulatorer och motorkontroller. Beroende på vilken vinkel konstruktionen har kommer någon av motorerna att korrigera vinkeln på behållaren. Testerna visade att konstruktionen kunde stabilisera behållaren i 84% av alla tester.
|
8 |
Self-stabilizing algorithms for graph parameters / Algorithmes auto-stabilisants pour des paramètres de graphesNeggazi, Brahim 15 April 2015 (has links)
Le concept d'auto-stabilisation a été introduit par Dijkstra en 1973. Un système distribué est auto-stabilisant s'il peut démarrer de n'importe quelle configuration initiale et retrouver une configuration légitime en un temps fini par lui-même et sans aucune intervention extérieure. La convergence est également garantie lorsque le système est affecté par des fautes transitoires, ce qui en fait une approche élégante, non masquante, pour la tolérance aux pannes. L'auto-stabilisation a été étudiée dans divers domaines des systèmes distribués tels que les problèmes de synchronisation de l'horloge, de la communication et les protocoles de routage. Vu l'importance des paramètres de graphes notamment pour l'organisation et l'optimisation des communications dans les réseaux et les systèmes distribués, plusieurs algorithmes auto-stabilisants pour des paramètres de graphe ont été proposés dans la littérature, tels que les algorithmes autostabilisants permettant de trouver les ensembles dominants minimaux, coloration des graphes, couplage maximal et arbres de recouvrement. Dans cette perspective, nous proposons, dans cette thèse, des algorithmes distribués et autostabilisants pour certains problèmes de graphes bien connus, en particulier pour les décompositions de graphes et les ensembles dominants qui n'ont pas encore été abordés avec le concept de l'autostabilisation. Les quatre problèmes majeurs considérés dans cette thèse sont: partitionnement en triangles, décomposition en p-étoiles, Monitoring des arêtes, fort ensemble dominant et indépendant. Ainsi, le point commun entre ces problèmes, est qu'ils sont tous considérés comme des variantes des problèmes de domination et de couplage dans les graphes et leur traitement se fait d'une manière auto-stabilisante / The concept of self-stabilization was first introduced by Dijkstra in 1973. A distributed system is self-stabilizing if it can start from any possible configuration and converges to a desired configuration in finite time by itself without using any external intervention. Convergence is also guaranteed when the system is affected by transient faults. This makes self-stabilization an effective approach for non-masking fault-tolerance. The self-stabilization was studied in various fields in distributed systems such as the problems of clock synchronization, communication and routing protocols. Given the importance of graph parameters, especially for organization and communication of networks and distributed systems, several self-stabilizing algorithms for classic graph parameters have been developed in this direction, such as self-stabilizing algorithms for finding minimal dominating sets, coloring, maximal matching, spanning tree and so on. Thence, we propose in this thesis, distributed and self-stabilizing algorithms to some wellknown graphs problems, particularly for graph decompositions and dominating sets problems that have not yet been addressed in a view of self-stabilization. The four major problems considered in this thesis are: the partitioning into triangles, p-star decomposition, edge monitoring set and independent strong dominating set problems. The common point between these four problems is that they are considered as variants of dominating set and matching problems and all propositions deal with the self-stabilization paradigm
|
9 |
Algorithmes et applications pour la coloration et les alliances dans les graphes / Graph colorings and alliances : algorithms and applicationsYahiaoui, Said 05 December 2013 (has links)
Dans cette thèse, nous nous intéressons aux aspects algorithmiques et applications de deux problèmes de graphes, à savoir, la coloration et les alliances. La première partie concerne deux variantes de la coloration de graphes, la coloration Grundy et la coloration forte stricte. Nous commençons par l'étude du nombre Grundy des graphes réguliers. Nous donnons une condition fixe k, nous fournissons une condition nécessaire et suffisante pour que le nombre Grundy d'un graphe régulier soit au moins égal k. Nous caractérisons la classe des graphes cubiques (3-réguliers) pour laquelle le nombre Grundy est égal à 4, et nous présentons un algorithme linéaire pour déterminer le nombre Grundy d'un graphe cubique quelconque. Par ailleurs, en se basant sur la coloration forte stricte pour décomposer les arbres en petites composantes, nous présentons un nouvel algorithme pour l'appariement d'arbres étiquetés, non-ordonnés non-enracinés. Nous montrons que la distance calculée entre deux arbres est une pseudo-métrique. Nos expérimentations sur de larges bases synthétiques et des bases de données réelles confirment nos résultats analytiques et montrent que la distance proposée est précise et son algorithme est scalable. La seconde partie de cette thèse est consacrée aux alliances dans les graphes. Nous proposons un algorithme distribué autostabilisant pour la construction d'alliance offensive globale minimale dans un graphe arbitraire. Nous démontrons que cet algorithme converge sous le démon synchrone en temps linéaire. Ensuite, nous donnons le premier algorithme distribué autostabilisant pour le problème de l'alliance forte globale minimale dans un graphe quelconque. Nous prouvons que cet algorithme est polynomial sous le démon inéquitable distribué. Nous montrons par la suite, comment cet algorithme peut être adapté pour des généralisations du problème, comme la k-alliance forte et l'alliance forte pondérée. Enfin, en se basant sur les propriétés structurelles de l'alliance offensive, nous présentons une solution pour décentraliser le protocole de signalisation SIP. Ceci rend possible son déploiement dans un réseau mobile ad hoc / This thesis investigates the algorithmic aspects and applications of two graph problems, namely, colorings and alliances. In the first part, we focus on two variants of the proper vertex coloring, the Grundy coloring and the strict strong coloring. We start by the study of Grundy number for regular graphs. We give a sufficient condition for d-regular graphs with sufficiently large girth to have Grundy number equals d + 1. Then, using graph homomorphism, we obtain a necessary and sufficient condition for d-regular graphs to have Grundy number at least k. Moreover, we characterize cubic graphs (3-regular) for which the Grundy number is d + 1, and present a linear-time algorithm to determine the Grundy number of any arbitrary cubic graph. Subsequently, based on the strict strong coloring, we present an approach for the problem of matching labeled trees. Using this coloring, we propose a new algorithm to deterministically decompose a tree into small components. This leads to an efficient algorithm to measure an accurate distance between unrooted unordered labeled trees. The second part is devoted to the alliances in graphs. We first propose a linear-time self-stabilizing algorithm for the minimal global offensive alliance set problem, under the synchronous distributed scheduler. Then, we give the first self-stabilizing algorithm for the minimal global powerful alliance set problem in arbitrary graphs. Moreover, we show how this algorithm can be adapted to find the minimal global powerful k-alliance and the minimal weighted global powerful alliance sets. We prove that all these algorithms converge in polynomial-time under the unfair distributed scheduler. Finally, based on the structural properties of the offensive alliance, we propose a solution to decentralize the signaling protocol SIP. This enables SIP applications in mobile ad hoc networks
|
10 |
Simulations of a self-stabilizing fully submerged hydrofoil / Simulering av ett självstabiliserande helt nedsänkt bärplanssystemJacobson, Henry January 2023 (has links)
Two models of a self-stabilizing hydrofoil system is developed where the effects from the struts and hydrofoil give torques for angular rotations. Lifting line theory for the hydrofoil which can twist is used. Nonlinear versions of the models are also developed and compared to find that the linear models use valid approximations. Backward Differentiation Formula is used to get numerical solutions, and eigenvalues of linear system matrices are used to get stability regions. The models did not accurately capture what has been seen in testing. / Två modeller för ett självstabiliserande bärplanssystem utvecklas där effekter från stöttor och bärplan ger vridmoment för vinkelrotationer. Lyftande linjeteori för det skevande bärplanet används. Icke-linjära versioner av modellerna tas också fram och jämförs för att finna att de linjära modellerna använder giltiga approximationer. Backward Differentiation Formula används för att fram numeriska lösningar, och egenvärden i det linjära systemetsmatriser används för att hitta stabilitetsregioner. Modellerna fångade inte korrekt vad som har setts i testning.
|
Page generated in 0.0601 seconds