The paper is devoted to Time Division Multiple Access Link Scheduling Protocols in wireless sensor networks for full duplex (two-way) communication, where each sensor is scheduled on an incident link as a transmitter ...
详细信息
ISBN:
(纸本)9780769546766
The paper is devoted to Time Division Multiple Access Link Scheduling Protocols in wireless sensor networks for full duplex (two-way) communication, where each sensor is scheduled on an incident link as a transmitter and as a receiver in two different time slots. We formulate the full duplex link scheduling problem (FDLSP) as distance-2 edge coloring in bi-directed graphs. We proves that there exists Delta-approximation algorithm for FDLSP (Delta being the maximum node degree in the network). Then, we present two distributed algorithms. The first is a synchronous algorithm based on finding maximal independent sets. The second is an asynchronous depth first search (DFS) algorithm. The maximal independent set based algorithm requires only O(Delta log*n) communication rounds (where n is the number of processors in the network) for growth bounded graphs, which is a realistic geometric model of sensor networks. For general graphs, the maximal independent set based algorithm requires O(Delta(4) + Delta(3)log*n) communication rounds, improving upon the previous best algorithm with O(n Delta(2) + n(2)m) communication rounds (where m is the number of links in the network). The asynchronous DFS based algorithm requires only O(n) communication rounds for both general and growth bounded graphs. The simulations show that the proposed algorithms assign on average equal or fewer number of time slots compared to the best known distributed algorithm while being significantly faster.
Rate adaptive media streams bear similarities to both elastic (e.g., file transfer) and inelastic (e.g., voice) network traffic classes. As such a service model for streaming media should incorporate characteristics o...
详细信息
Rate adaptive media streams bear similarities to both elastic (e.g., file transfer) and inelastic (e.g., voice) network traffic classes. As such a service model for streaming media should incorporate characteristics of both classes: guaranteed minimum rates (for minimally acceptable quality of service (QoS)) and an efficient mechanism for intelligently allocating excess capacity among the competing streams. In this paper we apply the system decomposition Kelly (Charging and rate control for elastic traffic. European Transactions on Communications 8:33-37, 1997) and distributed algorithms framework Kelly et al. (Rate control in communication networks: shadow prices, proportional fairness, and stability. J Oper Res Soc 49:237-252, 1998), developed by Frank Kelly et al. in the context of elastic traffic, to a service model for rate adaptive media streams. Our aim is to allocate excess capacity among competing streams so as to maximize a weighted client-average QoS, where each client QoS is defined as the time-average utility of the instantaneous received rate. We develop the corresponding system decomposition and distributed algorithms appropriate for rate adaptive media streams. Two distinct classes of distributed algorithms are derived: i) a distributed algorithm for dynamic adaptation, where the instantaneous subscription level of each stream is adjusted in response to network updates on route congestion levels, and ii) a distributed algorithm for static adaptation. The stationary point of the static adaptation algorithm is an admission policy that assigns each stream a fixed (in time) transmission rate as a function of the stream volume (the total number of bits associated with the media object). Our results, consistent with earlier work Weber and de Veciana (Rate adaptive multimedia streams: optimization and admisssion control. IEEE/ACM Trans Netw 13(6):1275-1288, December 2005a), confirm the intuitive idea that client average QoS is maximized by granting preferen
Consider a wireless network consisting of a set of wireless nodes and a set of communication links, where each communication link corresponds to a pair of nodes that are within communication radius of each other. Unde...
详细信息
ISBN:
(纸本)9781728152844
Consider a wireless network consisting of a set of wireless nodes and a set of communication links, where each communication link corresponds to a pair of nodes that are within communication radius of each other. Under the primary interference model, two communication links cannot be active at the same time if they are incident to a common node. This model of interference arises in Bluetooth networks, where transmissions between a master node and slave nodes in a piconet are scheduled by time-division duplexing, and in CDMA systems when each node is equipped with a single transceiver. Each communication link has a certain minimum bandwidth quality-of-service requirement. The admission control problem is to determine whether the network has sufficient resources to satisfy the bandwidth requirements. In this work, distributed algorithms are proposed for this admission control problem, and performance guarantees of these distributed algorithms are given. If each node has knowledge of a certain global parameter, then a distributed algorithm for flow admission control is given which has the same performance as an optimal, centralized algorithm, i.e. the distributed algorithm gives a condition that is both necessary and sufficient for a set of flow rates to be feasible.
This demonstration showcases distributed algorithms for configuration control in multi-robot systems.. These algorithms include examples of gradient communication, clustering and dispersion, group motion, and network ...
详细信息
ISBN:
(纸本)9781595936387
This demonstration showcases distributed algorithms for configuration control in multi-robot systems.. These algorithms include examples of gradient communication, clustering and dispersion, group motion, and network characterization. The algorithms are demonstrated on a swarm of 15 mobile robots.
We propose a novel distributed approach to exploit sleep mode capabilities of links in an Internet Service Provider network. Differently from other works, neither a central controller, nor the knowledge of the current...
详细信息
ISBN:
(纸本)9781467310161
We propose a novel distributed approach to exploit sleep mode capabilities of links in an Internet Service Provider network. Differently from other works, neither a central controller, nor the knowledge of the current traffic matrix is assumed, favoring a major step towards making sleep mode enabled networks practical in the current Internet architecture. Our algorithms are able to automatically adapt the state of network links to the actual traffic in the network. Moreover, the required input parameters are intuitive and easy to set. Extensive simulations that consider a real network and traffic demand prove that our algorithms are able to follow the daily variation of traffic, reducing energy consumption up to 70% during off peak time, with little overheads and while guaranteeing Quality of Service constraints.
This paper considers the problem of distributively verifying and ensuring strong connectivity of directed networks. Strong connectivity of a directed graph associated with the communication network topology is crucial...
详细信息
ISBN:
(纸本)9781665436595
This paper considers the problem of distributively verifying and ensuring strong connectivity of directed networks. Strong connectivity of a directed graph associated with the communication network topology is crucial in ensuring the convergence of many distributed algorithms. Specifically, inspired by maximum consensus algorithm, we first propose a distributed algorithm that enables nodes in a networked system to verify strong connectivity of a directed graph. Then, given an arbitrary weakly connected directed graph, we develop a distributed algorithm to augment additional links to ensure the directed graph's strong connectivity. Both algorithms are implemented without requiring information of the overall network topology and are scalable (linearly with the number of nodes) as they only require finite storage and converge in finite number of steps. Finally, the proposed distributed algorithms are demonstrated via several examples.
The shortest path problem is possibly the most important problem for data routing in multimedia communication. Chen and Chin have proposed a new variant of shortest path problem, termed the quickest path problem. The ...
详细信息
ISBN:
(纸本)0818690143
The shortest path problem is possibly the most important problem for data routing in multimedia communication. Chen and Chin have proposed a new variant of shortest path problem, termed the quickest path problem. The quickest path problem is find quickest paths in a computer network to transmit a given amount of data with minimal transmission time. The selection of quickest paths depends on both the characteristics of the computer network and the amount of data to be transmitted. The quickest path problem is to find quickest paths to send a certain amount of data through a communication network. Besides, if the quickest paths are required to go through a specified path, then the restricted problem is called the constrained quickest path problem. In this paper, some new distributed routing algorithms are developed for multimedia data transfer in an asynchronous communication network For all pairs of nodes in a network, an O(mn) messages and O(m) time distributed algorithm is first presented to find constrained quickest paths, and then an O(mn) messages and O(m) time distributed algorithm is present to enumerate the first k quickest paths.
In this paper we study fractional coloring from the angle of distributed computing. Fractional coloring is the linear relaxation of the classical notion of coloring, and has many applications, in particular in schedul...
详细信息
ISBN:
(纸本)9783030795269;9783030795276
In this paper we study fractional coloring from the angle of distributed computing. Fractional coloring is the linear relaxation of the classical notion of coloring, and has many applications, in particular in scheduling. It was proved by Hasemann, Hirvonen, Rybicki and Suomela [19] that for every real alpha > 1 and integer Delta, a fractional coloring of total weight at most alpha(Delta + 1) can be obtained deterministically in a single round in graphs of maximum degree Delta, in the LOCAL model of computation. However, a major issue of this result is that the output of each vertex has unbounded size. Here we prove that even if we impose the more realistic assumption that the output of each vertex has constant size, we can find fractional colorings of total weight arbitrarily close to known tight bounds for the fractional chromatic number in several cases of interest. More precisely, we show that for any fixed epsilon > 0 and Delta, a fractional coloring of total weight at most Delta+epsilon can be found in Omega(log* n) rounds in graphs of maximum degree Delta with no K Delta+1, while finding a fractional coloring of total weight at most Delta in this case requires Omega(log log n) rounds for randomized algorithms and Omega(log n) rounds for deterministic algorithms. We also show how to obtain fractional colorings of total weight at most 2+ epsilon in grids of any fixed dimension, for any epsilon > 0, in O(log* n) rounds. Finally, we prove that in sparse graphs of large girth from any proper minor-closed family we can find a fractional coloring of total weight at most 2+ epsilon, for any epsilon > 0, in O(log n) rounds.
Technological advances, especially in the miniaturization of robotic devices foreshadow the emergence of large-scale ensembles of small-size resource-constrained robots that distributively cooperate to achieve complex...
详细信息
Technological advances, especially in the miniaturization of robotic devices foreshadow the emergence of large-scale ensembles of small-size resource-constrained robots that distributively cooperate to achieve complex tasks (e. g., modular self-reconfigurable robots, swarm robotic systems, distributed microelectromechanical systems, etc.). These ensembles are formed by independent, intelligent and communicating units which act as a whole ensemble. These units cooperatively self-organize themselves to achieve common goals. These systems are thought to be more versatile and more robust than conventional robotic systems while having at the same time a lower cost. These ensembles form complex asynchronous distributed systems in which every unit is an embedded system with its own but limited capabilities. Coordination of such large- scale distributed embedded systems poses significant algorithmic issues and open new opportunities in distributed algorithms. In my thesis, I defend the idea that distributed algorithmic primitives suitable for the coordination of these ensembles should be both identified and designed. In this work, we focus on a specific class of modular robotic systems, namely large-scale distributed modular robotic ensembles composed of resource-constrained modules that are organized in a lattice structure and which can only communicate with neighboring modules. We identified and implemented three building blocks, namely centrality-based leader election, time synchronization and self-reconfiguration. We propose a collection of distributed algorithms to realize these primitives. We evaluate them using both hardware experiments and simulations on systems ranging from a dozen modules to more than ten thousand modules. We show that our algorithms scale well and are suitable for large-scale embedded distributed systems with scarce memory and computing resources.
A self-reconfigurable modular robot can change its own shape by rearranging the connectivity of the modules of which it is composed. In this paper, we focus on a two-dimensional lattice-arrayed self-reconfigurable mod...
详细信息
ISBN:
(纸本)9781467347082;9781467347075
A self-reconfigurable modular robot can change its own shape by rearranging the connectivity of the modules of which it is composed. In this paper, we focus on a two-dimensional lattice-arrayed self-reconfigurable modular robotic system. Each module can move to a neighboring lattice under certain motion constraints, communicate with its neighbors and act upon local knowledge only. A scalable shape sculpting algorithm based on the manipulation of regularly shaped voids within the lattice ("holes") is given. We present detailed solutions to the conflict test and settlement problem encountered when applying this algorithm, and make improvement on the efficiency of shape sculpting. We believe that the algorithm can potentially generalize to 3D and scale to handle millions of modules.
暂无评论