This paper introduces two distributed algorithms for resource allocation in cellular networks with coexisting femtocells and macrocells. Network interference in these complex networks is modeled by a random graph to m...
详细信息
ISBN:
(纸本)9781424492688
This paper introduces two distributed algorithms for resource allocation in cellular networks with coexisting femtocells and macrocells. Network interference in these complex networks is modeled by a random graph to maintain the complexity of the examined networks' interference scenarios while abstracting away details such as node density and propagation characteristics. We propose two distributed algorithms for interference-free resource assignment: An uncoordinated algorithm designed for a case with no communications between base stations, and a coordinated algorithm designed to exploit information sharing between base stations. We assess the two algorithms by comparing their performance against a centralized heuristic algorithm and a centralized genetic algorithm, which together approximate the (computationally intractable) optimal allocation.
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.
The opportunistic spectrum access (OSA) algorithms aim to maximize network throughput by ensuring orthogonal channel allocation among secondary users (SUs) in cognitive radio network (CRN). OSA is challenging in the d...
详细信息
ISBN:
(纸本)9781538611821
The opportunistic spectrum access (OSA) algorithms aim to maximize network throughput by ensuring orthogonal channel allocation among secondary users (SUs) in cognitive radio network (CRN). OSA is challenging in the decentralized CRN due to lack of coordination among SUs. Most of the existing algorithms assume prior knowledge of the number of active SUs to guarantee orthogonalization. In addition, they assume static network only where all SUs stay in the network throughout the horizon which is not feasible in practical conditions. However the dynamic network may also exist where the SUs can enter or exit the network at any time. Also, most of the existing algorithms assume an i.i.d. reward model whereas a markovian model may be more appropriate where the rewards are assumed to come from a finite, irreducible and aperiodic Markov chain represented by a single parameter probability transition matrix. Thus, our goal is to design a distributed algorithm for decentralized static and dynamic network without prior knowledge of the number of active SUs with i.i.d. as well as markovian reward model.
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.
Graph connectivity analysis is one of the primary ways to analyze the topological structure of social networks. Graph biconnectivity decompositions are of particular interest due to how they identify cut vertices and ...
详细信息
ISBN:
(纸本)9781665497473
Graph connectivity analysis is one of the primary ways to analyze the topological structure of social networks. Graph biconnectivity decompositions are of particular interest due to how they identify cut vertices and cut edges in a network. We present the first, to our knowledge, implementation of a distributed-memory parallel biconnectivity algorithm. As part of our algorithm, we also require the computation of least common ancestors (LCAs) of non-tree edge endpoints in a BFS tree. As such, we also propose a novel distributed algorithm for the LCA problem. Using our implementations, we observe up to a 14.8 x speedup from 1 to 128 MPI ranks for computing a biconnectivity decomposition.
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.
This paper presents the first (non-trivial) distributed planar embedding algorithm. We consider this a crucial first step in a broader program to design efficient distributed algorithms for planar networks. We work in...
详细信息
ISBN:
(纸本)9781450339643
This paper presents the first (non-trivial) distributed planar embedding algorithm. We consider this a crucial first step in a broader program to design efficient distributed algorithms for planar networks. We work in the standard distributed model in which nodes can send an O (log n)-bit message to each of their neighbors per round. In a planar network, with n nodes and diameter D, our deterministic planar embedding algorithm uses O (D . min{log n, D}) rounds to compute a combinatorial planar embedding, which consists of each node knowing the clockwise order of its incident edges in a fixed planar drawing. The complexity of our algorithm is near-optimal and matches the trivial lower bound of Omega(D) up to a log n factor. No algorithm outperforming the trivial round complexity of O(n) was known prior to this work.
A wireless mesh network (WMN) is a special type of wireless ad-hoc network, which consists of mesh clients, mesh routers and gateways to the Internet, organized in a mesh topology. The mesh clients are often laptops, ...
详细信息
ISBN:
(纸本)9780769549712
A wireless mesh network (WMN) is a special type of wireless ad-hoc network, which consists of mesh clients, mesh routers and gateways to the Internet, organized in a mesh topology. The mesh clients are often laptops, cell phones and other wireless devices. Mesh routers forward traffic between mesh clients and gateways. Despite a number of promising features provided by WMNs, such as low deployment cost, self-healing, etc., the throughput of WMNs is often limited by severe congestion and collisions, and thus cannot satisfy the increasing traffic demands of numerous applications. In this paper, we study how to maximize the throughput of IEEE 802.11n WMNs by joint routing and frame aggregation. Frame aggregation is to aggregate multiple frames into a large frame before transmission, to reduce communication overhead and alleviate collisions. We first show that previous frame aggregation strategies cannot achieve optimal network throughput. We then formulate the joint problem into a linear programming (LP) problem by considering traffic in the network as flow. As most previous algorithms for LP are centralized and difficult to deploy in large-scale WMNs, we propose a distributed algorithm to solve the formulated problem, in which each mesh router determines the amount of traffic flow for its adjacent links based on the traffic information of neighbors and interfering links. However, in realistic 802.11n WMNs, traffic is transmitted in frames instead of flow, and the traffic to different routers needs to be distinguished. Thus, we further provide an algorithm to determine the routing and frame aggregation strategy for each mesh router, using the traffic flow derived from the first algorithm. We have conducted extensive simulations to evaluate the proposed algorithms and the results demonstrate that the network throughput can be significantly improved compared with existing schemes.
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.
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.
暂无评论