To see the other types of publications on this topic, follow the link: Distributed algorithms for camera networks.
Dissertations / Theses on the topic 'Distributed algorithms for camera networks'
Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles
Consult the top 50 dissertations / theses for your research on the topic 'Distributed algorithms for camera networks.'
Next to every source in the list of references, there is an 'Add to bibliography' button. Press on it, and we will generate automatically the bibliographic reference to the chosen work in the citation style you need: APA, MLA, Harvard, Chicago, Vancouver, etc.
You can also download the full text of the academic publication as pdf and read online its abstract whenever available in the metadata.
Browse dissertations / theses on a wide variety of disciplines and organise your bibliography correctly.
1
Katragadda, Sandeep. "Distributed target tracking in wireless camera networks." Thesis, Queen Mary, University of London, 2017. http://qmro.qmul.ac.uk/xmlui/handle/123456789/25899.
Full textAbstract:
Distributed target tracking (DTT) is desirable in wireless camera networks to achieve scalability and robustness to node or link failures. DTT estimates the target state via information exchange and fusion among cameras. This thesis proposes new DTT algorithms to handle five major challenges of DTT in wireless camera networks, namely non-linearity in the camera measurement model, temporary lack of measurements (benightedness) due to limited field of view, redundant information in the network, limited connectivity of the network due to limited communication ranges and asynchronous information caused by varying and unknown frame processing delays. The algorithms consist of two phases, namely estimation and fusion. In the estimation phase, the cameras process their captured frames, detect the target, and estimate the target state (location and velocity) and its uncertainty using the Extended Information Filter (EIF) that handles non-linearity. In the fusion phase, the cameras exchange their local target information with their communicative neighbours and fuse the information. The contributions of this thesis are as follows. The target states estimated by the EIFs undergo weighted fusion. The weights are chosen based on the estimated uncertainty (error covariance) and the number of nodes with redundant information such that the information of benighted nodes and the redundant information get lower weights. At each time step, only the cameras having the view of the target and the cameras that might have the view of the target in the next time step participate in the fusion (tracking). This reduces the energy consumption of the network. The algorithm selects the cameras dynamically by using a threshold on their shortest distances (in the communication graph) from the cameras having the view of the target. Before fusion, each camera predicts the target information of other cameras to temporally align its information with the (asynchronous) information received from other cameras. The algorithm predicts the target state using the latest estimated velocity of the target. The experimental results show that the proposed algorithms achieve higher tracking accuracy than the state of the art under the five DTT challenges.
2
Ramakrishnan, Naveen. "Distributed Learning Algorithms for Sensor Networks." The Ohio State University, 2010. http://rave.ohiolink.edu/etdc/view?acc_num=osu1284991632.
Full text
3
Hong, Kirak. "A distributed framework for situation awareness on camera networks." Diss., Georgia Institute of Technology, 2014. http://hdl.handle.net/1853/52263.
Full textAbstract:
With the proliferation of cameras and advanced video analytics, situation awareness applications that automatically generate actionable knowledge from live camera streams has become an important class of applications in various domains including surveillance, marketing, sports, health care, and traffic monitoring. However, despite the wide range of use cases, developing those applications on large-scale camera networks is extremely challenging because it involves both compute- and data-intensive workloads, has latency-sensitive quality of service requirement, and deals with inherent dynamism (e.g., number of faces detected in a certain area) from the real world. To support developing large-scale situation awareness applications, this dissertation presents a distributed framework that makes two key contributions: 1) it provides a programming model that ensures scalability of applications and 2) it supports low-latency computation and dynamic workload handling through opportunistic event processing and workload distribution over different locations and network hierarchy.
To provide a scalable programming model, two programming abstractions for different levels of application logic are proposed: the first abstraction at the level of real-time target detection and tracking, and the second abstraction for answering spatio-temporal queries at a higher level. The first programming abstraction, Target Container (TC), elevates target as a first-class citizen, allowing domain experts to simply provide handlers for detection, tracking, and comparison of targets. With those handlers, TC runtime system performs priority-aware scheduling to ensure real-time tracking of important targets when resources are not enough to track all targets. The second abstraction, Spatio-temporal Analysis (STA) supports applications to answer queries related to space, time, and occupants using a global state transition table and probabilistic events. To ensure scalability, STA supports bounded communication overhead of state update by providing tuning parameters for the information propagation among distributed workers.
The second part of this work explores two optimization strategies that reduce latency for stream processing and handle dynamic workload. The first strategy, an opportunistic event processing mechanism, performs event processing on predicted locations to provide just-in-time situational information to mobile users. Since location prediction algorithms are inherently inaccurate, the system selects multiple regions using a greedy algorithm to provide highly meaningful information at the given amount of computing resources. The second strategy is to distribute application workload over computing resources that are placed at different locations and various levels of network hierarchy. To support this strategy, the framework provides hierarchical communication primitives and a decentralized resource discovery protocol that allow scalable and highly adaptive load balancing over space and time.
4
Song, Bi. "Scene analysis, control and communication in distributed camera networks." Diss., [Riverside, Calif.] : University of California, Riverside, 2009. http://gateway.proquest.com/openurl?url_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:dissertation&res_dat=xri:pqdiss&rft_dat=xri:pqdiss:3359910.
Full textAbstract:
Thesis (Ph. D.)--University of California, Riverside, 2009.Includes abstract. Title from first page of PDF file (viewed January 27, 2010). Includes bibliographical references (p. 99-105). Issued in print and online. Available via ProQuest Digital Dissertations.
5
Mehrotra, Shashank. "Distributed Algorithms for Tasking Large Sensor Networks." Thesis, Virginia Tech, 2001. http://hdl.handle.net/10919/33975.
Full textAbstract:
Recent advances in wireless communications along with developments in low-power circuit design and micro-electro mechanical systems (MEMS) have heralded the advent of compact and inexpensive wireless micro-sensor devices. A large network of such sensor nodes capable of communicating with each other provides significant new capabilities for automatically collecting and analyzing data from physical environments.
A notable feature of these networks is that more nodes than are strictly necessary may be deployed to cover a given region. This permits the system to provide reliable information, tolerate many types of faults, and prolong the effective service time. Like most wireless systems, achieving low power consumption is a key consideration in the design of these networks. This thesis presents algorithms for managing power at the distributed system level, rather than just at the individual node level. These distributed algorithms allocate work based on user requests to the individual sensor nodes that comprise the network. The primary goal of the algorithms is to provide a robust and scalable approach for tasking nodes that prolongs the effective life of the network.
Theoretical analysis and simulation results are presented to characterize the behavior of these algorithms. Results obtained from simulation experiments indicate that the algorithms can achieve a significant increase in the life of the network. In some cases this may be by an order of magnitude. The algorithms are also shown to ensure a good quality of sensor coverage while improving the network life. Finally, they are shown to be robust to faults and scale to large numbers of nodes.Master of Science
6
Tomozei, Dan-Cristian. "Distributed algorithms for peer-to-peer networks." Paris 6, 2011. http://www.theses.fr/2011PA066059.
Full textAbstract:
La thèse comporte trois parties. Chaque partie est consacrée à un problème algorithmique important pour les réseaux pair-à-pair. Dans la première partie on analyse des méthodes distribuées cherchant à caractériser les préférences d'usagers: On étend l'applicabilité des méthodes spectrales pour la récupération de structures cachées à des modèles probabilistes de faible rang pour les goûts des usagers. Par la suite, on propose une méthode distribuée basée sur des échanges de messages (message passing) à deux échelles séparées de temps, qui effectue le profilage des usagers d'un réseau pair-à-pair. On montre que cette méthode converge presque sûrement vers les vecteurs propres d'une matrice de similitude des usagers. Dans la deuxième partie on considère le problème d'estimation de distances dans Internet et de sélection de serveur à base d'un faible nombre de mesures. On attribue à chaque noeud des coordonnées virtuelles dans un certain espace de faible dimension et on utilise une fonction de pseudo-distance dans cet espace afin d'estimer des latences et des débits. Supposant que les mesures sont des distorsions de quantités métriques, on caractérise les performances d'une méthode simple pour l'estimation de latences. On montre également qu'il est possible d'avoir des estimations exactes des débits, si le routage suit le chemin de débit maximal. Dans la troisième partie on propose et on analyse une méthode distribuée pour control de flux dans les réseaux pair-à-pair de live-streaming qui prend en compte les couts réseau. On montre qu'une telle approche est optimale dans le cas ou les pairs implémentent le Network Coding.
7
Sidi, Bah Aladé Habib. "Distributed algorithms in autonomous and heterogeneous networks." Thesis, Avignon, 2012. http://www.theses.fr/2012AVIG0184/document.
Full textAbstract:
La diversité croissante des différents agents constituant les réseaux de communication actuels ainsi que la capacité accrue des technologies concurrentes dans l’environnement réseau a conduit à la prise en compte d’une nouvelle approche distribuée de la gestion du réseau. Dans cet environnement réseau évolué, le besoin en accroissement de la bande passante et en ressources rares, s’oppose à la réduction de la consommation énergétique globale.Dans notre travail nous nous intéressons à l’application de mécanismes distribués et de méthodes d’apprentissages visant à introduire d’avantage d’autonomie dans les réseaux hétérogènes, mobiles en particulier, tout en améliorant les performances par rapport aux débits et à la qualité de service. Notre étude se concentre principalement sur l’élaboration de mécanismes distribués stochastiques et énergétiquement efficaces en profitant des capacités de calcul de tous les agents et entités du réseau. Divers outils de la théorie des jeux nous permettent de modéliser et d’étudier différents types de systèmes dont la complexité est induite par la grande taille, l’hétérogénéité et le caractère dynamique des interconnexions. Plus spécifiquement, nous utilisons des outils d’apprentissage par renforcement pour aborder des questions telles que l’attachement distribué des utilisateurs permettant une gestion dynamique, décentralisée et efficace des ressources radio. Nous combinons ensuite les procédures de sélection d’accès à des méthodes d’optimisation distribuées du type gradient stochastique, pour adresser le problème de coordination des interférences intercellulaires (ICIC) dans les réseaux LTE-A. Cette approche se base sur un contrôle de puissance dynamique conduisant à une réutilisation fractionnaire des fréquences radios. Par ailleurs nous adressons dans les réseaux décentralisés non-hiérarchiques, plus précisément les réseaux tolérants aux délais (DTNs), des méthodes décentralisées liées à la minimisation du délai de transmission de bout en bout. Dans ce cadre nous nous intéressons, en outre des équilibres de Nash, à la notion d’équilibre évolutionnairement stables dans différents contextes de jeux évolutionnaires, jeux évolutionnaires décisionnels markoviens et jeux de minorité. Enfin, la majeure partie du travail effectué se rattachant aux tests et validations par simulations,nous présentons plusieurs éléments d’implémentations et d’intégrations liés à la mise en place de plateformes de simulations et d’expérimentationsGrowing diversity of agents in current communication networks and increasing capacitiesof concurrent technologies in the network environment has lead to the considerationof a novel distributed approach of the network management. In this evolvednetwork environment the increasing need for bandwidth and rare channel resources,opposes to reduction of the total energy consumption.This thesis focuses on application of distributed mechanisms and learning methodsto allow for more autonomy in the heterogeneous network, this in order to improveits performances. We are mainly interested in energy efficient stochastic mechanismsthat will operate in a distributed fashion by taking advantage of the computationalcapabilities of all the agents and entities of the network. We rely on application ofGame theory to study different types of complex systems in the distributed wirelessnetworks with dynamic interconnectivity.Specifically, we use the stochastic reinforcement learning tools to address issuessuch as, distributed user-network association that allows achieving an efficient dynamicand decentralized radio resource management. Then, we combine access selectionprocedures with distributed optimization to address the inter-cells interferencescoordination (ICIC) for LTE-advanced networks using dynamic power control and designof fractional frequency reuse mechanisms. Moreover we address in non-hierarchicalnetworks, more precisely in Delay Tolerant Networks (DTNs), decentralized methodsrelated to minimization of the end-to-end communication delay. In this framework weare interested, in addition to Nash equilibrium, to the notion of evolutionary stableequiliria in the different context of Evolutionary Games, Markov Decision EvolutionaryGames and Minority Games. As the major parts of our work includes testing andvalidations by simulations, eventually we present several implementations and integrationsmaterials for edition of simulation platforms and test beds
8
Xu, Songcen. "Distributed signal processing algorithms for wireless networks." Thesis, University of York, 2015. http://etheses.whiterose.ac.uk/9516/.
Full textAbstract:
Distributed signal processing algorithms have become a key approach for statistical inference in wireless networks and applications such as wireless sensor networks and smart grids. It is well known that distributed processing techniques deal with the extraction of information from data collected at nodes that are distributed over a geographic area. In this context, for each specific node, a set of neighbor nodes collect their local information and transmit the estimates to a specific node. Then, each specific node combines the collected information together with its local estimate to generate an improved estimate. In this thesis, novel distributed cooperative algorithms for inference in ad hoc, wireless sensor networks and smart grids are investigated. Low-complexity and effective algorithms to perform statistical inference in a distributed way are devised. A number of innovative approaches for dealing with node failures, compression of data and exchange of information are proposed and summarized as follows: Firstly, distributed adaptive algorithms based on the conjugate gradient (CG) method for distributed networks are presented. Both incremental and diffusion adaptive solutions are considered. Secondly, adaptive link selection algorithms for distributed estimation and their application to wireless sensor networks and smart grids are proposed. Thirdly, a novel distributed compressed estimation scheme is introduced for sparse signals and systems based on compressive sensing techniques. The proposed scheme consists of compression and decompression modules inspired by compressive sensing to perform distributed compressed estimation. A design procedure is also presented and an algorithm is developed to optimize measurement matrices. Lastly, a novel distributed reduced-rank scheme and adaptive algorithms are proposed for distributed estimation in wireless sensor networks and smart grids. The proposed distributed scheme is based on a transformation that performs dimensionality reduction at each agent of the network followed by a reduced–dimension parameter vector.
9
Saia, Jared. "Algorithms for managing data in distributed systems /." Thesis, Connect to this title online; UW restricted, 2002. http://hdl.handle.net/1773/6941.
Full text
10
Guillén, Alejandro. "Implementation of a Distributed Algorithm for Multi-camera Visual Feature Extraction in a Visual Sensor Network Testbed." Thesis, KTH, Kommunikationsnät, 2015. http://urn.kb.se/resolve?urn=urn:nbn:se:kth:diva-167415.
Full textAbstract:
Visual analysis tasks, like detection, recognition and tracking, are com- putationally intensive, and it is therefore challenging to perform such tasks in visual sensor networks, where nodes may be equipped with low power CPUs. A promising solution is to augment the sensor network with pro- cessing nodes, and to distribute the processing tasks among the process- ing nodes of the visual sensor network. The objective of this project is to enable a visual sensor network testbed to operate with multiple cam- era sensors, and to implement an algorithm that computes the allocation of the visual feature tasks to the processing nodes. In the implemented system, the processing nodes can receive and process data from differ- ent camera sensors simultaneously. The acquired images are divided into sub-images, the sizes of the sub-images are computed through solving a linear programming problem. The implemented algorithm performs local optimization in each camera sensor without data exchange with the other cameras in order to minimize the communication overhead and the data computational load of the camera sensors. The implementation work is performed on a testbed that consists of BeagleBone Black computers with IEEE 802.15.4 or IEEE 802.11 USB modules, and the existing code base is written in C++. The implementation is used to assess the performance of the distributed algorithm in terms of completion time. The results show a good performance providing lower average completion time.
11
Heo, Nojeong Varshney Pramod K. "Distributed deployment algorithms for mobile wireless sensor networks." Related electronic resource: Current Research at SU : database of SU dissertations, recent titles available full text, 2004. http://wwwlib.umi.com/cr/syr/main.
Full text
12
Wissinger, John W. (John Weakley). "Distributed nonparametric training algorithms for hypothesis testing networks." Thesis, Massachusetts Institute of Technology, 1994. http://hdl.handle.net/1721.1/12006.
Full textAbstract:
Thesis (Ph. D.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 1994.Includes bibliographical references (p. 495-502).
by John W. Wissinger.
Ph.D.
13
Huq, Sikder Rezwanul. "Locally self-adjusting distributed algorithms." Diss., University of Iowa, 2018. https://ir.uiowa.edu/etd/6594.
Full textAbstract:
In this dissertation, we study self-adjusting algorithms for large-scale distributed systems. Self-adjusting algorithms enable distributed systems to adjust their properties dynamically as the input pattern changes. Self-adjustment is an attractive tool as it has the potential to significantly improve the performance of distributed systems, especially when the input patterns are skewed.
We start with a distributed self-adjusting algorithm for skip graphs that minimizes the average routing costs between arbitrary communication pairs by performing topological adaptation to the communication pattern. Our algorithm is fully decentralized, conforms to the CONGEST model (i.e. uses O(log n) bit messages), and requires O(log n) bits of memory for each node, where n is the total number of nodes. Upon each communication request, our algorithm first establishes communication by using the standard skip graph routing, and then locally and partially reconstructs the skip graph topology to perform topological adaptation. We propose a computational model for such algorithms, as well as a yardstick (working set property) to evaluate them. Our working set property can also be used to evaluate self-adjusting algorithms for other graph classes where multiple tree-like subgraphs overlap (e.g. hypercube networks). We derive a lower bound of the amortized routing cost for any algorithm that follows our model and serves an unknown sequence of communication requests. We show that the routing cost of our algorithm is at most a constant factor more than the amortized routing cost of any algorithm conforming to our computational model. We also show that the expected transformation cost for our algorithm is at most a logarithmic factor more than the amortized routing cost of any algorithm conforming to our computational model.
As a follow-up work, we present a distributed self-adjusting algorithm (referred to as DyHypes) for topological adaption in hypercubic networks. One of the major differences between hypercubic networks and skip graphs is that hypercubic networks are more rigid in structure than that of skip graphs. This property of hypercubic networks makes self-adjustment significantly different compared to skip graphs. Upon a communication between an arbitrary pair of nodes, DyHypes transforms the network to place frequently communicating nodes closer to each other to maximize communication efficiency, and uses randomization in the transformation process to speed up the transformation and reduce message complexity. We show that, as compared to DSG, DyHypes reduces the transformation cost by a factor of O(log n), where n is the number of nodes involved in the transformation. Moreover, despite achieving faster transformation with lower message complexity, the combined cost (routing and transformation) of DyHypes is at most a log log n factor more than that of any algorithm that conforms to the computational model adopted for this work. Similar to DSG, DyHypes is fully decentralized, conforms to the CONGEST model, and requires O(log n) bits of memory for each node, where N is the total number of nodes.
Finally, we present a novel distributed load balancing algorithm called Meezan to address the load imbalance among large-scale networked cache servers. Modern web services rely on a network of distributed cache servers to efficiently deliver content to users. Load imbalance among cache servers can substantially degrade content delivery performance. Due to the skewed and dynamic nature of real-world workloads, cache servers that serve viral content experience higher load as compared to other cache servers. Our algorithm Meezan replicates popular objects to mitigate skewness and adjusts hash space boundaries in response to load dynamics in a novel way. Our theoretical analysis shows that Meezan achieves near perfect load balancing for a wide range of operating parameters. Our trace driven simulations shows that Meezan reduces load imbalance by up to 52% as compared to prior solutions.
14
Pandit, Saurav. "Approximation algorithms for distributed systems." Diss., University of Iowa, 2010. https://ir.uiowa.edu/etd/870.
Full textAbstract:
Distributed Approximation is a new and rapidly developing discipline that lies at the crossroads of various well-established areas of Computer Science - Distributed Computing, Approximation Algorithms, Graph Theory and often, Computational Geometry. This thesis focuses on the design and analysis of distributed algorithms to solve optimization problems that usually arise in large-scale, heavily dynamic, resource constrained networks, e.g. wireless ad-hoc and sensor networks, P2P systems, mobile networks etc. These problems can often be abstracted by variations of well-known combinatorial optimization problems, such as topology control, clustering etc. Many of these problems are known to be hard (NP-complete). But we need fast and light-weight distributed algorithms for these problems, that yield near-optimal solutions.
The results presented in this thesis can be broadly divided in two parts. The first part contains a set of results that obtain improved solutions to the classic problem of computing a sparse "backbone" for Wireless Sensor Networks (WSNs). In graph-theoretic terms, the goal is to compute a spanning subgraph of the input graph, that is sparse, lightweight and has low stretch. The term "low stretch" indicates that in spite of dropping many edges, the distance between any two nodes in the graph is not increased by much. We model WSNs as geometric graphs - unit ball graphs, quasi-unit ball graphs etc. in Euclidean spaces, as well as in more general metric spaces of low doubling dimension. We identify and exploit a variety of geometric features of those models to obtain our results.
In the second part of the thesis we focus on distributed algorithms for clustering problems. We present several distributed approximation algorithms for clustering problems (e.g., minimum dominating set, facility location problems) that improve on best known results so far. The main contribution here is the design of distributed algorithms where the running time is a "tunable" parameter. The advent of distributed systems of unprecedented scale and complexity motivates the question of whether it is possible to design algorithms that can provide non-trivial approximation guarantees even after very few rounds of computation and message exchanges. We call these algorithms "k-round algorithms". We design k-round algorithms for various clustering problems that yield non-trivial approximation factors even if k is a constant. Additionally, if k assumes poly-logarithmic values, our algorithms match or improve on the best-known approximation factors for these problems.
15
Nanongkai, Danupon. "Graph and geometric algorithms on distributed networks and databases." Diss., Georgia Institute of Technology, 2011. http://hdl.handle.net/1853/41056.
Full textAbstract:
In this thesis, we study the power and limit of algorithms on various models, aiming at applications in distributed networks and databases.
In distributed networks, graph algorithms are fundamental to many applications. We focus on computing random walks which are an important
primitive employed in a wide range of applications but has always been computed naively. We show that a faster solution exists and subsequently
develop faster algorithms by exploiting random walk properties leading to two immediate applications. We also show that this algorithm is optimal.
Our technique in proving a lower bound show the first non-trivial connection between communication complexity and lower bounds of distributed
graph algorithms. We show that this technique has a wide range of applications by proving new lower bounds of many problems. Some of these lower
bounds show that the existing algorithms are tight.
In database searching, we think of the database as a large set of multi-dimensional points stored in a disk and want to help the users to quickly find the most desired point. In this thesis, we develop an algorithm that is significantly faster than previous algorithms both theoretically and experimentally.
The insight is to solve the problem on the streaming model which helps emphasize the benefits of sequential access over random disk access. We also
introduced the randomization technique to the area. The results were complemented with a lower bound. We also initiat a new direction as an attempt to get a better query. We are the first to quantify the output quality using "user satisfaction" which is made possible by borrowing the idea of modeling users by utility functions from game theory and justify our approach through a geometric analysis.
16
Papalexidis, Nikolaos. "Distributed algorithms for beamforming in wirless [sic] sensor networks." Thesis, Monterey, Calif. : Naval Postgraduate School, 2007. http://bosun.nps.edu/uhtbin/hyperion-image.exe/07Jun%5FPapalexidis.pdf.
Full textAbstract:
Thesis (Electrical Engineer and M.S. in Electrical Engineering)--Naval Postgraduate School, June 2007.Thesis Advisor(s): Murali Tummala, John C. McEachen. "June 2007." Includes bibliographical references (p. 111-113). Also available in print.
17
Chong, Kheng Huat. "Dynamic routing algorithms for distributed packet-switched data networks." Thesis, Imperial College London, 1992. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.391256.
Full text
18
Yang, Jianchang. "FAULT-TOLERANT DISTRIBUTED CHANNEL ALLOCATION ALGORITHMS FOR CELLULAR NETWORKS." UKnowledge, 2006. http://uknowledge.uky.edu/gradschool_diss/329.
Full textAbstract:
In cellular networks, channels should be allocated efficiently to support communication betweenmobile hosts. In addition, in cellular networks, base stations may fail. Therefore, designing a faulttolerantchannel allocation algorithm is important. That is, the algorithm should tolerate failuresof base stations. Many existing algorithms are neither fault-tolerant nor efficient in allocatingchannels.We propose channel allocation algorithms which are both fault-tolerant and efficient. In theproposed algorithms, to borrow a channel, a base station (or a cell) does not need to get channelusage information from all its interference neighbors. This makes the algorithms fault-tolerant,i.e., the algorithms can tolerate base station failures, and perform well in the presence of thesefailures.Channel pre-allocation has effect on the performance of a channel allocation algorithm. Thiseffect has not been studied quantitatively. We propose an adaptive channel allocation algorithmto study this effect. The algorithm allows a subset of channels to be pre-allocated to cells. Performanceevaluation indicates that a channel allocation algorithm benefits from pre-allocating allchannels to cells.Channel selection strategy also inuences the performance of a channel allocation algorithm.Given a set of channels to borrow, how a cell chooses a channel to borrow is called the channelselection problem. When choosing a channel to borrow, many algorithms proposed in the literaturedo not take into account the interference caused by borrowing the channel to the cells which havethe channel allocated to them. However, such interference should be considered; reducing suchinterference helps increase the reuse of the same channel, and hence improving channel utilization.We propose a channel selection algorithm taking such interference into account.Most channel allocation algorithms proposed in the literature are for traditional cellular networkswith static base stations and the neighborhood relationship among the base stations is fixed.Such algorithms are not applicable for cellular networks with mobile base stations. We proposea channel allocation algorithm for cellular networks with mobile base stations. The proposedalgorithm is both fault-tolerant and reuses channels efficiently.KEYWORDS: distributed channel allocation, resource planning, fault-tolerance, cellular networks,3-cell cluster model.
19
MILLER, TAMARA GUERRA. "DISTRIBUTED SPARSITY-AWARE SIGNAL PROCESSING ALGORITHMS FOR SENSOR NETWORKS." PONTIFÍCIA UNIVERSIDADE CATÓLICA DO RIO DE JANEIRO, 2016. http://www.maxwell.vrac.puc-rio.br/Busca_etds.php?strSecao=resultado&nrSeq=27190@1.
Full textAbstract:
PONTIFÍCIA UNIVERSIDADE CATÓLICA DO RIO DE JANEIROCOORDENAÇÃO DE APERFEIÇOAMENTO DO PESSOAL DE ENSINO SUPERIOR
PROGRAMA DE EXCELENCIA ACADEMICA
Neste trabalho de dissertação são propostos algoritmos adaptativos que exploram a esparsidade em redes distribuídas de sensores para estimação de parâmetros e estimação espectral. São desenvolvidos algoritmos gradiente conjugado (CG) distribuído para os protocolos consenso e difusão em versão convencional e modificada (MCG). Esses algoritmos são desenvolvidos com exploração de esparsidade usando as funções penalidades l1 e log-sum. Os métodos propostos apresentam um melhor desempenho en termos de velocidade de convergência e desvio médio quadratico (MSD) que as já conhecidas variantes distribuídas do algoritmo least mean square (LMS) e muito próximo ao desempenho do algoritmo recursive least square (RLS). Além disso, propõe-se um algoritmo distribuído de optimização alternada de variáveis discretas e contínuas (DAMDC) baseado no LMS. O algoritmo DAMDC-LMS apresenta um desempenho muito próximo ao algoritmo oráculo e tem maior velocidade de convergência que os algoritmos estudados com exploração de esparsidade. Os resultados numéricos mostram que o algoritmo DAMDC-LMS pode ser aplicado em vários cenários.
This dissertation proposes distributed adaptive algorithms exploiting sparsity for parameter and spectrum estimation over sensor networks. Conventional and modified conjugate gradient (CG and MCG) algorithms using consensus and diffusion strategies are presented. Sparsity-aware versions of CG an MCG algorithms using l1 and log-sum penalty functions are developed. The proposed sparsity-aware and non-sparse CG and MCG methods outperform the equivalent variants of the least-mean square (LMS) algorithms in terms of convergence rate and mean square deviation (MSD) at steady state, and have a close performance to the recursive least square (RLS) algorithm. The diffusion CG strategies have shown the best performance, specifically the adapt then combine (ATC) version. Furthermore a distributed alternating mixed discretecontinuous (DAMDC) algorithm to approach the oracle algorithm based on the diffusion strategy for parameter and spectrum estimation over sensor networks is proposed. An LMS type algorithm with the DAMDC proposed technique obtains the oracle matrix in an adaptive way and compare it with the existing sparsity-aware as well as the classical algorithms. The proposed algorithm has an improved performance in terms of MSD. Numerical results show that the DAMDC-LMS algorithm is reliable and can be applied in several scenarios.
20
Raad, Patrick. "Protocol architecture and algorithms for distributed data center networks." Thesis, Paris 6, 2015. http://www.theses.fr/2015PA066571/document.
Full textAbstract:
De nos jours les données ainsi que les applications dans le nuage (cloud) connaissent une forte croissance, ce qui pousse les fournisseurs à chercher des solutions garantissant un lien réseau stable et résilient à leurs utilisateurs. Dans cette thèse on étudie les protocoles réseaux et les stratégies de communication dans un environnement de centre de données distribués. On propose une architecture cloud distribuée, centrée sur l’utilisateur et qui a pour but de: (i) migrer des machines virtuelles entre les centres de données avec un temps d’indisponibilité faible; (ii) fournir un accès résilient aux machines virtuelles; (iii) minimiser le délai d'accès au cloud. On a identifié deux problèmes de décision: le problème d'orchestration de machines virtuelles, prenant en compte la mobilité des utilisateurs, et le problème de basculement et de configuration des localisateurs, prenant en compte les états des liens inter- et intra-centre de données. On évalue notre architecture en utilisant une plate-forme de test avec des centres de données distribués géographiquement et en simulant des scenarios basés sur des traces de mobilités réelles. On montre que, grâce à quelques modifications apportées aux protocoles d'overlay, on peut avoir des temps d'indisponibilité très faibles pendant la migration de machines virtuelles entre deux centres de données. Puis on montre qu’en reliant la mobilité des machines virtuelles aux déplacement géographiques des utilisateurs, on peut augmenter le débit de la connexion. De plus, quand l’objectif est de maximiser le débit entre l’utilisateur et sa ressource, on démontre par des simulations que la décision de l'emplacement des machines virtuelles est plus importante que la décision de basculement de point d'entrée du centre de données. Enfin, grâce à un protocole de transport multi-chemins, on montre comment optimiser les performances de notre architecture et comment à partir des solutions de routage intra-centre de données on peut piloter le basculement des localisateursWhile many business and personal applications are being pushed to the cloud, offering a reliable and a stable network connectivity to cloud-hosted services becomes an important challenge to face in future networks. In this dissertation, we design advanced network protocols, algorithms and communication strategies to cope with this evolution in distributed data center architectures. We propose a user-centric distributed cloud network architecture that is able to: (i) migrate virtual resources between data centers with an optimized service downtime; (ii) offer resilient access to virtual resources; (iii) minimize the cloud access latency. We identify two main decision making problems: the virtual machine orchestration problem, also taking care of user mobility, and the routing locator switching configuration problem, taking care of both extra and intra data center link states. We evaluate our architecture using real test beds of geographically distributed data centers, and we also simulate realistic scenarios based on real mobility traces. We show that migrating virtual machines between data centers at negligible downtime is possible by enhancing overlay protocols. We then demonstrate that by linking cloud virtual resource mobility to user mobility we can get a considerable gain in the transfer rates. We prove by simulations using real traces that the virtual machine placement decision is more important than the routing locator switching decision problem when the goal is to increase the connection throughput: the cloud access performance is primarily affected by the former decision, while the latter decision can be left to intra data center traffic engineering solutions. Finally, we propose solutions to take profit from multipath transport protocols for accelerating cloud access performance in our architecture, and to let link-state intra data center routing fabrics piloting the cloud access routing locator switching
21
BORRA, DOMENICA. "Localization and Optimization Problems for Camera Networks." Doctoral thesis, Politecnico di Torino, 2013. http://hdl.handle.net/11583/2506434.
Full textAbstract:
In the framework of networked control systems, we focus on networks of autonomous
PTZ cameras. A large set of cameras communicating each other through a network
is a widely used architecture in application areas like video surveillance, tracking and motion.
First, we consider relative localization in sensor networks, and we tackle the issue of
investigating the error propagation, in terms of the mean error on each component of the
optimal estimator of the position vector. The relative error is computed as a function of the
eigenvalues of the network: using this formula and focusing on an exemplary class of networks
(the Abelian Cayley networks), we study the role of the network topology and the dimension
of the networks in the error characterization. Second, in a network of cameras one of the
most crucial problems is calibration. For each camera this consists in understanding what is
its position and orientation with respect to a global common reference frame. Well-known
methods in computer vision permit to obtain relative positions and orientations of pairs
of cameras whose sensing regions overlap. The aim is to propose an algorithm that, from
these noisy input data makes the cameras complete the calibration task autonomously, in a
distributed fashion. We focus on the planar case, formulating an optimization problem over
the manifold SO(2). We propose synchronous deterministic and distributed algorithms that
calibrate planar networks exploiting the cycle structure of the underlying communication
graph. Performance analysis and numerical experiments are shown. Third, we propose a
gossip-like randomized calibration algorithm, whose probabilistic convergence and numerical
studies are provided. Forth and finally, we design surveillance trajectories for a network of
calibrated autonomous cameras to detect intruders in an environment, through a continuous
graph partitioning problem.
22
Li, Junlin. "Distributed estimation in resource-constrained wireless sensor networks." Diss., Atlanta, Ga. : Georgia Institute of Technology, 2008. http://hdl.handle.net/1853/26633.
Full textAbstract:
Thesis (Ph.D)--Electrical and Computer Engineering, Georgia Institute of Technology, 2009.Committee Chair: Ghassan AlRegib; Committee Member: Elliot Moore; Committee Member: Monson H. Hayes; Committee Member: Paul A. Work; Committee Member: Ying Zhang. Part of the SMARTech Electronic Thesis and Dissertation Collection.
23
Ghodsi, Ali. "Distributed k-ary System: Algorithms for Distributed Hash Tables." Doctoral thesis, KTH, Mikroelektronik och Informationsteknik, IMIT, 2006. http://urn.kb.se/resolve?urn=urn:nbn:se:kth:diva-4186.
Full textAbstract:
This dissertation presents algorithms for data structures called distributed hash tables (DHT) or structured overlay networks, which are used to build scalable self-managing distributed systems. The provided algorithms guarantee lookup consistency in the presence of dynamism: they guarantee consistent lookup results in the presence of nodes joining and leaving. Similarly, the algorithms guarantee that routing never fails while nodes join and leave. Previous algorithms for lookup consistency either suffer from starvation, do not work in the presence of failures, or lack proof of correctness. Several group communication algorithms for structured overlay networks are presented. We provide an overlay broadcast algorithm, which unlike previous algorithms avoids redundant messages, reaching all nodes in O(log n) time, while using O(n) messages, where n is the number of nodes in the system. The broadcast algorithm is used to build overlay multicast. We introduce bulk operation, which enables a node to efficiently make multiple lookups or send a message to all nodes in a specified set of identifiers. The algorithm ensures that all specified nodes are reached in O(log n) time, sending maximum O(log n) messages per node, regardless of the input size of the bulk operation. Moreover, the algorithm avoids sending redundant messages. Previous approaches required multiple lookups, which consume more messages and can render the initiator a bottleneck. Our algorithms are used in DHT-based storage systems, where nodes can do thousands of lookups to fetch large files. We use the bulk operation algorithm to construct a pseudo-reliable broadcast algorithm. Bulk operations can also be used to implement efficient range queries. Finally, we describe a novel way to place replicas in a DHT, called symmetric replication, that enables parallel recursive lookups. Parallel lookups are known to reduce latencies. However, costly iterative lookups have previously been used to do parallel lookups. Moreover, joins or leaves only require exchanging O(1) messages, while other schemes require at least log(f) messages for a replication degree of f. The algorithms have been implemented in a middleware called the Distributed k-ary System (DKS), which is briefly described.QC 20100824
24
Cheung, Victor. "Distributed position estimation for wireless sensor networks /." View abstract or full-text, 2006. http://library.ust.hk/cgi/db/thesis.pl?COMP%202006%20CHEUNG.
Full text
25
Sun, Yijiang. "Distributed scheduling in multihop ad hoc networks." Click to view the E-thesis via HKUTO, 2008. http://sunzi.lib.hku.hk/HKUTO/record/B39558289.
Full text
26
Sun, Yijiang, and 孫一江. "Distributed scheduling in multihop ad hoc networks." Thesis, The University of Hong Kong (Pokfulam, Hong Kong), 2008. http://hub.hku.hk/bib/B39558289.
Full text
27
Sung, Minho. "Scalable and efficient distributed algorithms for defending against malicious Internet activity." Diss., Available online, Georgia Institute of Technology, 2006, 2006. http://etd.gatech.edu/theses/available/etd-07172006-134741/.
Full textAbstract:
Thesis (Ph. D.)--Computing, Georgia Institute of Technology, 2007.Xu, Jun, Committee Chair ; Ahamad, Mustaque, Committee Member ; Ammar, Mostafa, Committee Member ; Bing, Benny, Committee Member ; Zegura, Ellen, Committee Member.
28
Sun, Qiong, and 孙琼. "Topology-transparent distributed scheduling in wireless networks." Thesis, The University of Hong Kong (Pokfulam, Hong Kong), 2010. http://hub.hku.hk/bib/B44904101.
Full text
29
Nilsson, Thomas. "Distributed Multiple Access and Service Differentiation Algorithms for Wireless Networks." Doctoral thesis, Umeå : Department of Computing Science, Umeå Univ, 2008. http://urn.kb.se/resolve?urn=urn:nbn:se:umu:diva-1506.
Full text
30
Dhawan, Akshaye. "Distributed Algorithms for Maximizing the Lifetime of Wireless Sensor Networks." Digital Archive @ GSU, 2009. http://digitalarchive.gsu.edu/cs_diss/50.
Full textAbstract:
Wireless sensor networks (WSNs) are emerging as a key enabling technology for applications domains such as military, homeland security, and environment. However, a major constraint of these sensors is their limited battery. In this dissertation we examine the problem of maximizing the duration of time for which the network meets its coverage objective. Since these networks are very dense, only a subset of sensors need to be in "sense" or "on" mode at any given time to meet the coverage objective, while others can go into a power conserving "sleep" mode. This active set of sensors is known as a cover. The lifetime of the network can be extended by shuffling the cover set over time. In this dissertation, we introduce the concept of a local lifetime dependency graph consisting of the cover sets as nodes with any two nodes connected if the corresponding covers intersect, to capture the interdependencies among the covers. We present heuristics based on some simple properties of this graph and show how they improve over existing algorithms. We also present heuristics based on other properties of this graph, new models for dealing with the solution space and a generalization of our approach to other graph problems.
31
Gmyr, Robert [Verfasser]. "Distributed algorithms for overlay networks and programmable matter / Robert Gmyr." Paderborn : Universitätsbibliothek, 2018. http://d-nb.info/1151570087/34.
Full text
32
Silva, Pereira Silvana. "Distributed consensus algorithms for wireless sensor networks: convergence analysis and optimization." Doctoral thesis, Universitat Politècnica de Catalunya, 2012. http://hdl.handle.net/10803/131997.
Full textAbstract:
Wireless sensor networks are developed to monitor areas of interest with the purpose of estimating physical parameters or/and detecting emergency events in a variety of military and civil applications. A wireless sensor network can be seen as a distributed computer, where spatially deployed sensor nodes are in charge of gathering measurements from the environment to compute a given function. The research areas for wireless sensor networks extend from the design of small, reliable hardware to low-complexity algorithms and energy saving communication protocols.
Distributed consensus algorithms are low-complexity iterative schemes that have received increased attention in different fields due to a wide range of applications, where neighboring nodes communicate locally to compute the average of an initial set of measurements. Energy is a scarce resource in wireless sensor networks and therefore, the convergence of consensus algorithms, characterized by the total number of iterations until reaching a steady-state value, is an important topic of study.
This PhD thesis addresses the problem of convergence and optimization of distributed consensus algorithms for the estimation of parameters in wireless sensor networks. The impact of quantization noise in the convergence is studied in networks with fixed topologies and symmetric communication links. In particular, a new scheme including quantization is proposed, whose mean square error with respect to the average consensus converges. The limit of the mean square error admits a closed-form expression and an upper bound for this limit depending on general network parameters is also derived.
The convergence of consensus algorithms in networks with random topology is studied focusing particularly on convergence in expectation, mean square convergence and almost sure convergence. Closed-form expressions useful to minimize the convergence time of the algorithm are derived from the analysis.
Regarding random networks with asymmetric links, closed-form expressions are provided for the mean square error of the state assuming equally probable uniform link weights, and mean square convergence to the statistical mean of the initial measurements is shown. Moreover, an upper bound for the mean square error is derived for the case of different probabilities of connection for the links, and a practical scheme with randomized transmission power exhibiting an improved performance in terms of energy consumption with respect to a fixed network with the same consumption on average is proposed. The mean square error expressions derived provide a means to characterize the deviation of the state vector with respect to the initial average when the instantaneous links are asymmetric.
A useful criterion to minimize the convergence time in random networks with spatially correlated links is considered, establishing a sufficient condition for almost sure convergence to the consensus space. This criterion, valid also for topologies with spatially independent links, is based on the spectral radius of a positive semidefinite matrix for which we derive closed-form expressions assuming uniform link weights. The minimization of this spectral radius is a convex optimization problem and therefore, the optimum link weights minimizing the convergence time can be computed efficiently. The expressions derived are general and apply not only to random networks with instantaneous directed topologies but also to random networks with instantaneous undirected topologies. Furthermore, the general expressions can be particularized to obtain known protocols found in literature, showing that they can be seen as particular cases of the expressions derived in this thesis.Las redes de sensores inalámbricos se utilizan para monitorizar zonas de interés con el propósito final de estimar parámetros físicos y/o detectar situaciones de emergencia en gran variedad de aplicaciones militares y civiles. Una red de sensores inalámbricos puede ser considerada como un método de computación distribuido, donde nodos provistos de sensores toman medidas del entorno para calcular una función que depende de éstas. Las áreas de investigación comprenden desde el diseño de dispositivos hardware pequeños y fiables hasta algoritmos de baja complejidad o protocolos de comunicación de bajo consumo energético. Los algoritmos de consenso distribuidos son esquemas iterativos de baja complejidad que han suscitado mucha atención en diferentes campos debido a su gran espectro de aplicaciones, en los que nodos vecinos se comunican para calcular el promedio de un conjunto de medidas iniciales de la red. Dado que la energía es un recurso escaso en redes de sensores inalámbricos, la convergencia de dichos algoritmos de consenso, caracterizada por el número total de iteraciones hasta alcanzar un valor estacionario, es un importante tema de estudio. Esta tesis doctoral aborda problemas de convergencia y optimización de algoritmos de consenso distribuidos para la estimación de parámetros en redes de sensores inalámbricos. El impacto del ruido de cuantización en la convergencia se estudia en redes con topología fija y enlaces de comunicación simétricos. En particular, se propone un nuevo esquema que incluye el proceso de cuantización y se demuestra que el error cuadrático medio respecto del promedio inicial converge. Igualmente, se obtiene una expresión cerrada del límite del error cuadrático medio, y una cota superior para este límite que depende únicamente de parámetros generales de la red. La convergencia de los algoritmos de consenso en redes con topología aleatoria se estudia prestando especial atención a la convergencia en valor esperado, la convergencia en media cuadrática y la convergencia casi segura, y a partir del análisis se derivan expresiones cerradas útiles para minimizar el tiempo de convergencia. Para redes aleatorias con enlaces asimétricos, se obtienen expresiones cerradas del error cuadrático medio del estado suponiendo enlaces con probabilidad idéntica y con pesos uniformes, y se demuestra la convergencia en media cuadrática al promedio estadístico de las medidas iniciales. Se deduce una cota superior para el error cuadrático medio para el caso de enlaces con probabilidades de conexión diferentes y se propone, además, un esquema práctico con potencias de transmisión aleatorias, que mejora el rendimiento en términos de consumo de energía con respecto a una red fija. Las expresiones para el error cuadrático medio proporcionan una forma de caracterizar la desviación del vector de estado con respecto del promedio inicial cuando los enlaces instantáneos son asimétricos. Con el fin de minimizar el tiempo de convergencia en redes aleatorias con enlaces correlados espacialmente, se considera un criterio que establece una condición suficiente que garantiza la convergencia casi segura al espacio de consenso. Este criterio, que también es válido para topologías con enlaces espacialmente independientes, utiliza el radio espectral de una matriz semidefinida positiva para la cual se obtienen expresiones cerradas suponiendo enlaces con pesos uniformes. La minimización de dicho radio espectral es un problema de optimización convexa y, por lo tanto, el valor de los pesos óptimos puede calcularse de forma eficiente. Las expresiones obtenidas son generales y aplican no sólo para redes aleatorias con topologías dirigidas, sino también para redes aleatorias con topologías no dirigidas. Además, las expresiones generales pueden ser particularizadas para obtener protocolos conocidos en la literatura, demostrando que éstos últimos pueden ser considerados como casos particulares de las expresiones proporcionadas en esta tesis.
33
Carretti, Cesare Maria. "Comparison of Distributed Optimization Algorithms in Sensor Networks : Simulations and results." Thesis, KTH, Reglerteknik, 2008. http://urn.kb.se/resolve?urn=urn:nbn:se:kth:diva-105895.
Full textAbstract:
We consider a peer-to-peer approach to wireless sensor networks using the IEEE 802.15.4 standard, with sensors not synchronized, and without any routing protocol. Only communications between neighbors are allowed. In this scenario we do a comparison between four distributed algorithms that solve a special class of optimization problems, which are of great interest in networking applications. We want to retrieve, without a central node, the average of a scalar measurement from all sensors in the network. In the nal state, each sensor should have the global average of the considered measurement. To evaluate performances of the algorithms, we build an application for the network simulator ns2, and we do several simulations to evaluate convergence delay, and nal error, respect to time and to number of packets sent. In this thesis we present the algorithms from theoretical and practical point of views, we describe our application for ns2, and we show the results obtained, which show that this types of algorithms, if tuned properly, work well and are ready to be practically implemented in a real sensor network.
34
Garcia, Ruiz Jose E. [Verfasser]. "Distributed Positioning Algorithms in Underwater Acoustic Networks / Jose E Garcia Ruiz." Aachen : Shaker, 2006. http://d-nb.info/1186584734/34.
Full text
35
Jedda, Ahmed. "Distributed Algorithms for Networks Formation in a Scalable Internet of Things." Thèse, Université d'Ottawa / University of Ottawa, 2014. http://hdl.handle.net/10393/30979.
Full textAbstract:
The Internet of Things (IoT) is a vision that aims at inter-connecting every physical identifiable object (or, a thing) via a global networking infrastructure (e.g., the legacy Internet). Several architectures are proposed to realize this vision; many of which agree that the IoT shall be considered as a global network of networks. These networks are used to manage wireless sensors, Radio Frequency IDentification (RFID) tags, RFID readers and other types of electronic devices and integrate them into the IoT. A major requirement of the IoT architectures is scalability, which is the capability of delivering high performance even if the input size (e.g., number of the IoT objects) is large. This thesis studies and proposes solutions to meet this requirement, and specifically focuses on the scalability issues found in the networks of the IoT. The thesis proposes several network formation algorithms to achieve these objectives, where a network formation algorithm is an algorithm that, if applied to a certain network, optimizes it to perform its tasks in a more efficient manner by virtually deleting some of its nodes and/or edges.
The thesis focuses on three types of networks found in the IoT: 1) RFID readers coverage networks; whose main task is to cover (i.e., identify, monitor, track, sense) IoT objects located in a given area, 2) readers inter-communications networks; whose main task is to guarantee that their nodes are able to inter-communicate with each other and hence use their resources more efficiently (the thesis specifically considers inter-communication networks of readers using Bluetooth for communications), and 3) Object Name Systems (ONS) which are networks of several inter-connected database servers (i.e., distributed database) whose main task is to resolve an object identifier into an Internet address to enable inter-communication via the Internet. These networks are chosen for several reasons. For example, the technologies and concepts found in these networks are among the major enablers of the IoT. Furthermore, these networks solve tasks that are central to any IoT architecture. Particularly, the thesis a) studies the data and readers redundancy problem found in RFID readers coverage networks and introduces decentralized RFID coverage and readers collisions avoidance algorithms to solve it, b) contributes to the problem of forming multihop inter-communications networks of Bluetooth-equipped readers by proposing decentralized time-efficient Bluetooth Scatternet Formation algorithms, and c) introduces a geographic-aware ONS architecture based on Peer-To-Peer (P2P) computing to overcome weaknesses found in existing ONS architectures.
36
Lewin, Daniel M. (Daniel Mark) 1970. "Consistent hashing and random trees : algorithms for caching in distributed networks." Thesis, Massachusetts Institute of Technology, 1998. http://hdl.handle.net/1721.1/9947.
Full text
37
Liu, Junbin. "Distributed low-power image processing in wireless sensor networks for intelligent video surveillance applications." Thesis, Queensland University of Technology, 2012. https://eprints.qut.edu.au/63311/1/Junbin_Liu_Thesis.pdf.
Full textAbstract:
Distributed Wireless Smart Camera (DWSC) network is a special type of Wireless Sensor Network (WSN) that processes captured images in a distributed manner. While image processing on DWSCs sees a great potential for growth, with its applications possessing a vast practical application domain such as security surveillance and health care, it suffers from tremendous constraints. In addition to the limitations of conventional WSNs, image processing on DWSCs requires more computational power, bandwidth and energy that presents significant challenges for large scale deployments. This dissertation has developed a number of algorithms that are highly scalable, portable, energy efficient and performance efficient, with considerations of practical constraints imposed by the hardware and the nature of WSN. More specifically, these algorithms tackle the problems of multi-object tracking and localisation in distributed wireless smart camera net- works and optimal camera configuration determination.
Addressing the first problem of multi-object tracking and localisation requires solving a large array of sub-problems. The sub-problems that are discussed in this dissertation are calibration of internal parameters, multi-camera calibration for localisation and object handover for tracking. These topics have been covered extensively in computer vision literatures, however new algorithms must be invented to accommodate the various constraints introduced and required by the DWSC platform.
A technique has been developed for the automatic calibration of low-cost cameras which are assumed to be restricted in their freedom of movement to either pan or tilt movements. Camera internal parameters, including focal length, principal point, lens distortion parameter and the angle and axis of rotation, can be recovered from a minimum set of two images of the camera, provided that the axis of rotation between the two images goes through the camera's optical centre and is parallel to either the vertical (panning) or horizontal (tilting) axis of the image.
For object localisation, a novel approach has been developed for the calibration of a network of non-overlapping DWSCs in terms of their ground plane homographies, which can then be used for localising objects. In the proposed approach, a robot travels through the camera network while updating its position in a global coordinate frame, which it broadcasts to the cameras. The cameras use this, along with the image plane location of the robot, to compute a mapping from their image planes to the global coordinate frame. This is combined with an occupancy map generated by the robot during the mapping process to localised objects moving within the network.
In addition, to deal with the problem of object handover between DWSCs of non-overlapping fields of view, a highly-scalable, distributed protocol has been designed. Cameras that follow the proposed protocol transmit object descriptions to a selected set of neighbours that are determined using a predictive forwarding strategy. The received descriptions are then matched at the subsequent camera on the object's path using a probability maximisation process with locally generated descriptions.
The second problem of camera placement emerges naturally when these pervasive devices are put into real use. The locations, orientations, lens types etc. of the cameras must be chosen in a way that the utility of the network is maximised (e.g. maximum coverage) while user requirements are met. To deal with this, a statistical formulation of the problem of determining optimal camera configurations has been introduced and a Trans-Dimensional Simulated Annealing (TDSA) algorithm has been proposed to effectively solve the problem.
38
Yu, Dongxiao, and 于东晓. "Distributed algorithmic studies in wireless ad hoc networks." Thesis, The University of Hong Kong (Pokfulam, Hong Kong), 2014. http://hdl.handle.net/10722/206656.
Full textAbstract:
It has been envisioned that in the near future, wireless ad hoc networks would populate various application fields, ranging from disaster relief, environmental monitoring, surveillance, to medical applications, the observation of chemical and biological processes and community mesh networks. The decentralized and self-organizing nature of wireless ad hoc networks makes distributed algorithms fit very well in these networks, which however pose great challenges to the algorithm designers as they try to achieve optimal efficiency in communications. In this thesis, I develop a set of distributed algorithms addressing these challenges and solving some fundamental communication problems in wireless ad hoc networks.
Communications in wireless ad hoc networks happen on a shared medium, and consequently are subject to interference. The first part of the thesis focuses on disseminating information on multiple-access channels while avoiding collisions. For both single-channel and multi-channel networks, the complexity of information dissemination is investigated, and nearly optimal distributed algorithms are proposed.
The second part of the thesis focuses on designing efficient distributed algorithms for some fundamental problems under the physical Signal-to-Interference-plus-Noise-Ratio (SINR) interference model. The SINR model defines global fading interference with which the success of a signal reception depends on all simultaneous transmissions. Compared with graph based models, the SINR model reflects the fading and cumulative nature of radio signals. Hence, the SINR model represents the physical reality more precisely. However, the global nature of the SINR model makes the analysis of distributed algorithms much more challenging. Two types of fundamental problems are addressed in this part. The first type is closely related to communication coordination, including the wireless link scheduling problem and the node coloring problem. The second type of problems are about basic communication primitives, including the local broadcasting problem and the multiple-message broadcast problem. I investigate the complexity of these fundamental problems under the SINR interference model, and present efficient or optimal distributed algorithms.
In the third part of the thesis, I propose a general interference model that can include commonly adopted interference models as special cases, and study whether efficient distributed algorithms can still be designed and analyzed in such a general model. Specifically, the affectance model is proposed in this part, which depicts the relative interference (affectance) on communication links caused by transmitting nodes. Both graph based models and the SINR model can be transformed into the affectance model. Under this general model, distributed algorithms with worst-case guarantees for the local broadcasting problem are presented. I also show how to make use of the developed techniques to get nearly optimal algorithms under the graph based model and the SINR model.published_or_final_version
Computer Science
Doctoral
Doctor of Philosophy
39
Yu, Jia. "Distributed parameter and state estimation for wireless sensor networks." Thesis, University of Edinburgh, 2017. http://hdl.handle.net/1842/28929.
Full textAbstract:
The research in distributed algorithms is linked with the developments of statistical inference in wireless sensor networks (WSNs) applications. Typically, distributed approaches process the collected signals from networked sensor nodes. That is to say, the sensors receive local observations and transmit information between each other. Each sensor is capable of combining the collected information with its own observations to improve performance. In this thesis, we propose novel distributed methods for the inference applications using wireless sensor networks. In particular, the efficient algorithms which are not computationally intensive are investigated. Moreover, we present a number of novel algorithms for processing asynchronous network events and robust state estimation. In the first part of the thesis, a distributed adaptive algorithm based on the component-wise EM method for decentralized sensor networks is investigated. The distributed component-wise Expectation-Maximization (EM) algorithm has been designed for application in a Gaussian density estimation. The proposed algorithm operates a component-wise EM procedure for local parameter estimation and exploit an incremental strategy for network updating, which can provide an improved convergence rate. Numerical simulation results have illustrated the advantages of the proposed distributed component-wise EM algorithm for both well-separated and overlapped mixture densities. The distributed component-wise EM algorithm can outperform other EM-based distributed algorithms in estimating overlapping Gaussian mixtures. In the second part of the thesis, a diffusion based EM gradient algorithm for density estimation in asynchronous wireless sensor networks has been proposed. Specifically, based on the asynchronous adapt-then-combine diffusion strategy, a distributed EM gradient algorithm that can deal with asynchronous network events has been considered. The Bernoulli model has been exploited to approximate the asynchronous behaviour of the network. Compared with existing distributed EM based estimation methods using a consensus strategy, the proposed algorithm can provide more accurate estimates in the presence of asynchronous networks uncertainties, such as random link failures, random data arrival times, and turning on or off sensor nodes for energy conservation. Simulation experiments have been demonstrated that the proposed algorithm significantly outperforms the consensus based strategies in terms of Mean-Square- Deviation (MSD) performance in an asynchronous network setting. Finally, the challenge of distributed state estimation in power systems which requires low complexity and high stability in the presence of bad data for a large scale network is addressed. A gossip based quasi-Newton algorithm has been proposed for solving the power system state estimation problem. In particular, we have applied the quasi-Newton method for distributed state estimation under the gossip protocol. The proposed algorithm exploits the Broyden- Fletcher-Goldfarb-Shanno (BFGS) formula to approximate the Hessian matrix, thus avoiding the computation of inverse Hessian matrices for each control area. The simulation results for IEEE 14 bus system and a large scale 4200 bus system have shown that the distributed quasi-Newton scheme outperforms existing algorithms in terms of Mean-Square-Error (MSE) performance with bad data.
40
Jabeen, Farhana. "Distributed spatial analysis in wireless sensor networks." Thesis, University of Manchester, 2011. https://www.research.manchester.ac.uk/portal/en/theses/distributed-spatial-analysis-in-wireless-sensor-networks(f8a1f71a-81b0-4dc7-b520-b90a2393a61e).html.
Full textAbstract:
Wireless sensor networks (WSNs) allow us to instrument the physical world in novel ways, providing detailed insight that has not been possible hitherto. Since WSNs provide an interface to the physical world, each sensor node has a location in physical space, thereby enabling us to associate spatial properties with data. Since WSNs can perform periodic sensing tasks, we can also associate temporal markers with data. In the environmental sciences, in particular, WSNs are on the way to becoming an important tool for the modelling of spatially and temporally extended physical phenomena. However, support for high-level and expressive spatial-analytic tasks that can be executed inside WSNs is still incipient. By spatial analysis we mean the ability to explore relationships between spatially-referenced entities (e.g., a vineyard, or a weather front) and to derive representations grounded on such relationships (e.g., the geometrical extent of that part of a vineyard that is covered by mist as the intersection of the geometries that characterize the vineyard and the weather front, respectively). The motivation for this endeavour stems primarily from applications where important decisions hinge on the detection of an event of interest (e.g., the presence, and spatio-temporal progression, of mist over a cultivated field may trigger a particular action) that can be characterized by an event-defining predicate (e.g., humidity greater than 98 and temperature less than 10). At present, in-network spatial analysis in WSN is not catered for by a comprehensive, expressive, well-founded framework. While there has been work on WSN event boundary detection and, in particular, on detecting topological change of WSN-represented spatial entities, this work has tended to be comparatively narrow in scope and aims. The contributions made in this research are constrained to WSNs where every node is tethered to one location in physical space. The research contributions reported here include (a) the definition of a framework for representing geometries; (b) the detailed characterization of an algebra of spatial operators closely inspired, in its scope and structure, by the Schneider-Guting ROSE algebra (i.e., one that is based on a discrete underlying geometry) over the geometries representable by the framework above; (c) distributed in-network algorithms for the operations in the spatial algebra over the representable geometries, thereby enabling (i) new geometries to be derived from induced and asserted ones, and (ii)topological relationships between geometries to be identified; (d) an algorithmic strategy for the evaluation of complex algebraic expressions that is divided into logically-cohesive components; (e) the development of a task processing system that each node is equipped with, thereby with allowing users to evaluate tasks on nodes; and (f) an empirical performance study of the resulting system.
41
Cianci, Christopher Michael. "Distributed intelligent algorithms for robotic sensor networks monitoring discontinuous anisotropic environmental fields /." Lausanne : EPFL, 2009. http://library.epfl.ch/theses/?nr=4247.
Full textAbstract:
Thèse Ecole polytechnique fédérale de Lausanne EPFL, no 4247 (2009), Faculté informatique et communications IC, Programme doctoral Informatique, Communications et Information, Institut des sciences et technologies de l'environnement ISTE (Laboratoire de systèmes et algorithmes intelligents distribués DISAL). Dir.: Alcherio Martinoli.
42
Pham, Tien. "Distributed source localization and tracking algorithms for ad-hoc acoustic sensor networks." College Park, Md. : University of Maryland, 2006. http://hdl.handle.net/1903/3539.
Full textAbstract:
Thesis (Ph. D.) -- University of Maryland, College Park, 2006.Thesis research directed by: Electrical Engineering. Title from t.p. of PDF. Includes bibliographical references. Published by UMI Dissertation Services, Ann Arbor, Mich. Also available in paper.
43
Feldmann, Michael [Verfasser]. "Algorithms for distributed data structures and self-stabilizing overlay networks / Michael Feldmann." Paderborn : Universitätsbibliothek, 2021. http://d-nb.info/1231907754/34.
Full text
44
Teguig, Djamel. "Cooperative Spectrum Sensing Algorithms For Cognitive Radio Networks." Doctoral thesis, Universite Libre de Bruxelles, 2015. http://hdl.handle.net/2013/ULB-DIPOT:oai:dipot.ulb.ac.be:2013/219942.
Full textAbstract:
The work presented in this thesis concerns one of the key enabling techniques related to cognitive radio functionalities which is spectrum sensing as well as cooperative spectrum sensing. As cooperative spectrum sensing (CSS) approaches are commonly used for combating fading and improving detection performance, their performances using different combining rules have been analyzed. Due to the low implementation complexity, Goodness of Fit based spectrum sensing has been studied for cognitive radio applications. Motivated by its nice features of local sensing, a distributed consensus spectrum sensing for CR, has been presented, integrating a Goodness of Fit based spectrum sensing scheme.Le travail présenté dans cette thèse concerne l'une des techniques clés dans les fonctionnalités de la radio cognitive qui est la détection du spectre ainsi que la détection coopérative du spectre. La détection coopérative est couramment utilisée pour la lutte contre l’évanouissement du canal à fin d'améliorer les performances de la détection. Les performances de la détection coopérative en utilisant différentes règles de fusion ont été analysées. En raison sa simplicité, la détection du spectre par les testes d’adéquation a été étudiée pour les applications de la radio cognitive. Motivé par la caractéristique d’être indépendant de bruit, ces testes d’adéquation ont été utilisés pour la détection locale, pour la détection coopérative distribuée.
Doctorat en Sciences de l'ingénieur et technologie
info:eu-repo/semantics/nonPublished
45
Rajapaksage, Jayampathi S. "Data Aggregation through Web Service Composition in Smart Camera Networks." Digital Archive @ GSU, 2010. http://digitalarchive.gsu.edu/cs_theses/69.
Full textAbstract:
Distributed Smart Camera (DSC) networks are power constrained real-time distributed embedded systems that perform computer vision using multiple cameras. Providing data aggregation techniques that is criti-cal for running complex image processing algorithms on DSCs is a challenging task due to complexity of video and image data. Providing highly desirable SQL APIs for sophisticated query processing in DSC networks is also challenging for similar reasons. Research on DSCs to date have not addressed the above two problems. In this thesis, we develop a novel SOA based middleware framework on a DSC network that uses Distributed OSGi to expose DSC network services as web services. We also develop a novel web service composition scheme that aid in data aggregation and a SQL query interface for DSC net-works that allow sophisticated query processing. We validate our service orchestration concept for data aggregation by providing query primitive for face detection in smart camera network.
46
Berns, Andrew David. "Self-stabilizing overlay networks." Diss., University of Iowa, 2012. https://ir.uiowa.edu/etd/3431.
Full textAbstract:
Today's distributed systems exist on a scale that was unimaginable only a few decades ago. Distributed systems now can consist of thousands or even millions of computers spread across the entire world. These large systems are often organized into overlay networks - networks composed of virtual links, with each virtual link realized by one or more physical links. Self-stabilizing overlay networks promise that, starting from any weakly-connected configuration, the correct network topology is always built. This area of research is young, and prior examples of self-stabilizing overlay networks have either been for simple topologies, or involved complex algorithms that were difficult to verify and extend. We address these limitations in this thesis.
First, we present the Transitive Closure Framework, a generic framework to transform any locally-checkable overlay network into a self-stabilizing network. This simple framework has a running time which is at most a logarithmic number of rounds more than optimal, and in fact is optimal for a particular class of overlay networks. We also prove the only known non-trivial lower bound on the convergence time of any self-stabilizing overlay network. To allow fast and efficient repairs for local faults, we extend the Transitive Closure Framework to the Local Repair Framework. We demonstrate this framework by implementing an efficient algorithm for node joins in the Skip+ graph.
Next, we present the Avatar network, which is a generic locally checkable overlay network capable of simulating many other overlay networks. We design a self-stabilizing algorithm for a binary search tree embedded onto the Avatar network, and prove this algorithm requires only a polylogarithmic number of rounds to converge and limits degree increases to within a polylogarithmic factor of optimal. This algorithm is the first to achieve such efficiency, and its modular design makes it easy to extend. Finally, we introduce a technique called network scaffolding, which builds other overlay network topologies using the Avatar network.
47
McMurtrey, Shannon Dale. "Training and Optimizing Distributed Neural Networks Using a Genetic Algorithm." NSUWorks, 2010. http://nsuworks.nova.edu/gscis_etd/243.
Full textAbstract:
Parallelizing neural networks is an active area of research. Current approaches surround the parallelization of the widely used back-propagation (BP) algorithm, which has a large amount of communication overhead, making it less than ideal for parallelization. An algorithm that does not depend on the calculation of derivatives, and the backward propagation of errors, better lends itself to a parallel implementation.
One well known training algorithm for neural networks explicitly incorporates network structure in the objective function to be minimized which yields simpler neural networks. Prior work has implemented this using a modified genetic algorithm in a serial fashion that is not scalable, thus limiting its usefulness.
This dissertation created a parallel version of the algorithm. The performance of the proposed algorithm is compared against the existing algorithm using a variety of syn-thetic and real world problems. Computational experiments with benchmark datasets in-dicate that the parallel algorithm proposed in this research outperforms the serial version from prior research in finding better minima in the same time as well as identifying a simpler architecture.
48
Laitrakun, Seksan. "Distributed detection and estimation with reliability-based splitting algorithms in random-access networks." Diss., Georgia Institute of Technology, 2014. http://hdl.handle.net/1853/53008.
Full textAbstract:
We design, analyze, and optimize distributed detection and estimation algorithms in a large, shared-channel, single-hop wireless sensor network (WSN). The fusion center (FC) is allocated a shared transmission channel to collect local decisions/estimates but cannot collect all of them because of limited energy, bandwidth, or time. We propose a strategy called reliability-based splitting algorithm that enables the FC to collect local decisions/estimates in descending order of their reliabilities through a shared collision channel. The algorithm divides the transmission channel into time frames and the sensor nodes into groups based on their observation reliabilities. Only nodes with a specified range of reliabilities compete for the channel using slotted ALOHA within each frame. Nodes with the most reliable decisions/estimates attempt transmission in the first frame; nodes with the next most reliable set of decisions/estimates attempt in the next frame; etc. The reliability-based splitting algorithm is applied in three scenarios: time-constrained distributed detection; sequential distributed detection; and time-constrained estimation. Performance measures of interest - including detection error probability, efficacy, asymptotic relative efficiency, and estimator variance - are derived. In addition, we propose and analyze algorithms that exploit information from the occurrence of collisions to improve the performance of both time-constrained distributed detection and sequential distributed detection.
49
Pei, Guanhong. "Distributed Scheduling and Delay-Throughput Optimization in Wireless Networks under the Physical Interference Model." Diss., Virginia Tech, 2013. http://hdl.handle.net/10919/19219.
Full textAbstract:
We investigate diverse aspects of the performance of wireless networks, including throughput, delay and distributed complexity. One of the main challenges for optimizing them arises from radio interference, an inherent factor in wireless networks.
Graph-based interference models represent a large class of interference models widely used for the study of wireless networks,
and suffer from the weakness of over-simplifying the interference caused by wireless signals in a local and binary way.
A more sophisticated interference model, the physical interference model, based on SINR constraints,
is considered more realistic but is more challenging to study (because of its non-linear form and non-local property).
In this dissertation, we study the connections between the two types of interference models -- graph-based and physical interference models --
and tackle a set of fundamental problems under the physical interference model;
previously, some of the problems were still open even under the graph-based interference model, and to those we have provided solutions under both types of interference models.
The underlying interference models affect scheduling and power control -- essential building blocks in the operation of wireless networks -- that directly deal with the wireless medium; the physical interference model (compared to graph-based interference model) compounds the problem of efficient scheduling and power control by making it non-local and non-linear.
The system performance optimization and tradeoffs with respect to throughput and delay require a ``global\'\' view across
transport, network, media access control (MAC), physical layers (referred to as cross-layer optimization)
to take advantage of the control planes in different levels of the wireless network protocol stack.
This can be achieved by regulating traffic rates, finding traffic flow paths for end-to-end sessions,
controlling the access to the wireless medium (or channels),
assigning the transmission power, and handling signal reception under interference.
The theme of the dissertation is
distributed algorithms and optimization of QoS objectives under the physical interference model.
We start by developing the first low-complexity distributed scheduling and power control algorithms for maximizing the efficiency ratio for different interference models;
we derive end-to-end per-flow delay upper-bounds for our scheduling algorithms and our delay upper-bounds are the first network-size-independent result known for multihop traffic.
Based on that, we design the first cross-layer multi-commodity optimization frameworks for delay-constrained throughput maximization by incorporating the routing and traffic control into the problem scope.
Scheduling and power control is also inherent to distributed computing of ``global problems\'\', e.g., the maximum independent set problems in terms of transmitting links and local broadcasts respectively, and the minimum spanning tree problems.
Under the physical interference model, we provide the first sub-linear time distributed solutions to the maximum independent set problems, and also solve the minimum spanning tree problems efficiently.
We develop new techniques and algorithms and exploit the availability of technologies (full-/half-duplex radios, fixed/software-defined power control) to further improve our algorithms.
%This fosters a deeper understanding of distributed scheduling from the network computing point of view.
We highlight our main technical contributions, which might be of independent interest to the design and analysis of optimization algorithms.
Our techniques involve the use of linear and mixed integer programs in delay-constrained throughput maximization. This demonstrates the combined use of different kinds of combinatorial optimization approaches for multi-criteria optimization.
We have developed techniques for queueing analysis under general stochastic traffic to analyze network throughput and delay properties.
We use randomized algorithms with rigorously analyzed performance guarantees to overcome the distributed nature of wireless data/control communications.
We factor in the availability of emerging radio technologies for performance improvements of our algorithms.
Some of our algorithmic techniques that would be of broader use in algorithms for the physical interference model include:
formal development of the distributed computing model in the SINR model, and reductions between models of different technological capabilities, the redefinition of interference sets in the setting of SINR constraints, and our techniques for distributed computation of rulings (informally, nodes or links which are well-separated covers).
Ph. D.
50
Strothmann, Thim Frederik [Verfasser]. "Self-* Algorithms for distributed systems : programmable matter & overlay networks / Thim Frederik Strothmann." Paderborn : Universitätsbibliothek, 2017. http://d-nb.info/1137554843/34.
Full text