In this dissertation, we study data collection and its achievable network capacity in Wireless Sensor Networks (WSNs). Firstly, we investigate the data collection issue in dual-radio multi-channel WSNs under the protocol interference model. We propose a multi-path scheduling algorithm for snapshot data collection, which has a tighter capacity bound than the existing best result, and a novel continuous data collection algorithm with comprehensive capacity analysis. Secondly, considering most existing works for the capacity issue are based on the ideal deterministic network model, we study the data collection problem for practical probabilistic WSNs. We design a cell-based path scheduling algorithm and a zone-based pipeline scheduling algorithm for snapshot and continuous data collection in probabilistic WSNs, respectively. By analysis, we show that the proposed algorithms have competitive capacity performance compared with existing works. Thirdly, most of the existing works studying the data collection capacity issue are for centralized synchronous WSNs. However, wireless networks are more likely to be distributed asynchronous systems. Therefore, we investigate the achievable data collection capacity of realistic distributed asynchronous WSNs and propose a data collection algorithm with fairness consideration. Theoretical analysis of the proposed algorithm shows that its achievable network capacity is order-optimal as centralized and synchronized algorithms do and independent of network size. Finally, for completeness, we study the data aggregation issue for realistic probabilistic WSNs. We propose order-optimal scheduling algorithms for snapshot and continuous data aggregation under the physical interference model.

We investigate diverse aspects of the performance of wireless networks, including throughput, delay and distributed complexity. <br />One of the main challenges for optimizing them arises from radio interference, an inherent factor in wireless networks.<br />Graph-based interference models represent a large class of interference models widely used for the study of wireless networks,<br />and suffer from the weakness of over-simplifying the interference caused by wireless signals in a local and binary way.<br />A more sophisticated interference model, the physical interference model, based on SINR constraints,<br />is considered more realistic but is more challenging to study (because of its non-linear form and non-local property).<br />In this dissertation, we study the connections between the two types of interference models -- graph-based and physical interference models --<br />and tackle a set of fundamental problems under the physical interference model;<br />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.<br /><br />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.<br />The system performance optimization and tradeoffs with respect to throughput and delay require a ``global\'\' view across<br />transport, network, media access control (MAC), physical layers (referred to as cross-layer optimization)<br />to take advantage of the control planes in different levels of the wireless network protocol stack.<br />This can be achieved by regulating traffic rates, finding traffic flow paths for end-to-end sessions,<br />controlling the access to the wireless medium (or channels),<br />assigning the transmission power, and handling signal reception under interference.<br /><br />The theme of the dissertation is<br />distributed algorithms and optimization of QoS objectives under the physical interference model.<br />We start by developing the first low-complexity distributed scheduling and power control algorithms for maximizing the efficiency ratio for different interference models;<br />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.<br />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.<br />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.<br />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.<br />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.<br />%This fosters a deeper understanding of distributed scheduling from the network computing point of view.<br /><br /><br />We highlight our main technical contributions, which might be of independent interest to the design and analysis of optimization algorithms.<br />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.<br />We have developed techniques for queueing analysis under general stochastic traffic to analyze network throughput and delay properties.<br />We use randomized algorithms with rigorously analyzed performance guarantees to overcome the distributed nature of wireless data/control communications.<br />We factor in the availability of emerging radio technologies for performance improvements of our algorithms.<br />Some of our algorithmic techniques that would be of broader use in algorithms for the physical interference model include:<br />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).<br /> / Ph. D.

Benefiting from the constant and significant advancement of wireless communication technologies and networking protocols, Wireless Ad hoc NETwork (WANET) has played a more and more important role in modern communication networks without relying much on existing infrastructures. The past decades have seen numerous applications adopting ad hoc networks for service provisioning. For example, Wireless Sensor Network (WSN) can be widely deployed for environment monitoring and object tracking by utilizing low-cost, low-power and multi-function sensor nodes. To realize such applications, the design and evaluation of communication protocols are of significant importance. Meanwhile, the network performance analysis based on mathematical models is also in great need of development and improvement. This dissertation investigates the above topics from three important and fundamental aspects, including data collection protocol design, protocol modeling and analysis, and physical interference modeling and analysis. The contributions of this dissertation are four-fold. First, this dissertation investigates the synchronization issue in the duty-cycled, pipelined-scheduling data collection of a WSN, based on which a pipelined data collection protocol, called PDC, is proposed. PDC takes into account both the pipelined data collection and the underlying schedule synchronization over duty-cycled radios practically and comprehensively. It integrates all its components in a natural and seamless way to simplify the protocol implementation and to achieve a high energy efficiency and low packet delivery latency. Based on PDC, an Adaptive Data Collection (ADC) protocol is further proposed to achieve dynamic duty-cycling and free addressing, which can improve network heterogeneity, load adaptivity, and energy efficiency. Both PDC and ADC have been implemented in a pioneer open-source operating system for the Internet of Things, and evaluated through a testbed built based on two hardware platforms, as well as through emulations. Second, Linear Sensor Network (LSN) has attracted increasing attention due to the vast requirements on the monitoring and surveillance of a structure or area with a linear topology. Being aware that, for LSN, there is few work on the network modeling and analysis based on a duty-cycled MAC protocol, this dissertation proposes a framework for modeling and analyzing a class of duty-cycled, multi-hop data collection protocols for LSNs. With the model, the dissertation thoroughly investigates the PDC performance in an LSN, considering both saturated and unsaturated scenarios, with and without retransmission. Extensive OPNET simulations have been carried out to validate the accuracy of the model. Third, in the design and modeling of PDC above, the transmission and interference ranges are defined for successful communications between a pair of nodes. It does not consider the cumulative interference from the transmitters which are out of the contention range of a receiver. Since most performance metrics in wireless networks, such as outage probability, link capacity, etc., are nonlinear functions of the distances among communicating, relaying, and interfering nodes, a physical interference model based on distance is definitely needed in quantifying these metrics. Such quantifications eventually involve the Nodal Distance Distribution (NDD) intrinsically depending on network coverage and nodal spatial distribution. By extending a tool in integral geometry and using decomposition and recursion, this dissertation proposes a systematic and algorithmic approach to obtaining the NDD between two nodes which are uniformly distributed at random in an arbitrarily-shaped network. Fourth, with the proposed approach to NDDs, the dissertation presents a physical interference model framework to analyze the cumulative interference and link outage probability for an LSN running the PDC protocol. The framework is further applied to analyze 2D networks, i.e., ad hoc Device-to-Device (D2D) communications underlaying cellular networks, where the cumulative interference and link outage probabilities for both cellular and D2D communications are thoroughly investigated. / Graduate / 0984 / 0544 / tong1987fei@163.com

Este trabajo analiza la idoneidad de dos de los principales métodos de asignación de tareas en entornos con restricciones temporales. Se pondrá de manifiesto que ambos tipos de mecanismos presentan carencias para tratar tareas con deadlines, especialmente cuando los robots han de formar coaliciones. Uno de los aspectos a los que esta tesis dedica mayor atención es la predicción del tiempo de ejecución, que depende, entre otros factores, de la interferencia física entre robots. Este fenómeno no se ha tenido en cuenta en los mecanismos actuales de asignación basados en subastas. Así, esta tesis presenta el primer mecanismo de subastas para la creación de coaliciones que tiene en cuenta la interferencia entre robots. Para ello, se ha desarrollado un modelo de predicción del tiempo de ejecución y un nuevo paradigma llamado subasta doble. Además, se han propuesto nuevos mecanismos basados en swarm