1,721,112 research outputs found
Fast Gossip via Non-reversible Random walk
Full text linkDistributed computation of average is essential for many tasks such as estimation, eigenvalue computation, scheduling in the context of wireless sensor and ad-hoc networks. The wireless communication imposes the gossip constraint: each node can communicate with at most one other node at a given time. Recent interest in emerging wireless sensor network has led to exciting developments in the context of gossip algorithms for averaging. Most of the known algorithms are iterative and based on certain reversible random walk on the network graph. Subsequently, the running time of algorithm is affected by the diffusive nature of reversible random walk. For example, they take Ω(n2) time to compute average on a simple path or ring graph of n nodes. In contrast, an optimal (simple) centralized algorithm takes [unk](n) time to compute average in a path. This raises the following questions: is it possible for a distributed algorithm to compute average in O(n) time for path graph? is it possible to improve over diffusive behavior of current algorithms in arbitrary graphs? In this paper, we answer the above questions in affirmative. To overcome the diffusive nature of algorithms, we utilize non-reversible random walks. Specifically, we design our algorithms by "projecting down" the "lifted" non-reversible random walks of Diaconis-Holmes-Neal (2000) and Chen-Lovasz-Pak (1999). The running time of our algorithm is square-root of the time taken by corresponding reversible random walk for a large class of graphs including path
Local rules for global MAP: When do they work?
No full textWe consider the question of computing Maximum A Posteriori (MAP) assignment in an arbitrary pair-wise Markov Random Field (MRF). We present a randomized iterative algorithm based on simple local updates. The algorithm, starting with an arbitrary initial assignment, updates it in each iteration by first, picking a random node, then selecting an (appropriately chosen) random local neighborhood and optimizing over this local neighborhood. Somewhat surprisingly, we show that this algorithm finds a near optimal assignment within n log n iterations with high probability for any n node pair-wise MRF with geometry (i.e. MRF graph with polynomial growth) with the approximation error depending on (in a reasonable manner) the geometric growth rate of the graph and the average radius of the local neighborhood - this allows for a graceful tradeoff between the complexity of the algorithm and the approximation error. Through extensive simulations, we show that our algorithm finds extremely good approximate solutions for various kinds of MRFs with geometry
Switched networks with maximum weight policies: Fluid approximation and multiplicative state space collapse
No full textWe consider a queueing network in which there are constraints on which queues may be served simultaneously; such networks may be used to model input-queued switches and wireless networks. The scheduling policy for such a network specifies which queues to serve at any point in time. We consider a family of scheduling policies, related to the maximum-weight policy of Tassiulas and Ephremides [IEEE Trans. Automat. Control 37 (1992) 1936–1948], for single-hop and multihop networks. We specify a fluid model and show that fluid-scaled performance processes can be approximated by fluid model solutions. We study the behavior of fluid model solutions under critical load, and characterize invariant states as those states which solve a certain network-wide optimization problem. We use fluid model results to prove multiplicative state space collapse. A notable feature of our results is that they do not assume complete resource pooling.National Science Foundation (U.S.) (CAREER CNS-0546590
Randomized Scheduling Algorithm for Queueing Networks
Full text linkThere has recently been considerable interest in design of low-complexity, myopic, distributed and stable scheduling algorithms for constrained queueing network models that arise in the context of emerging communication networks. Here we consider two representative models. One, a queueing network model that captures randomly varying number of packets in the queues present at a collection of wireless nodes communicating through a shared medium. Two, a buffered circuit switched network model for an optical core of future internet to capture the randomness in calls or flows present in the network. The maximum weight scheduling algorithm proposed by Tassiulas and Ephremides [IEEE Trans. Automat. Control 37 (1992) 1936–1948], leads to a myopic and stable algorithm for the packet-level wireless network model. But computationally it is expensive (NP-hard) and centralized. It is not applicable to the buffered circuit switched network due to the requirement of nonpreemption of the calls in the service. As the main contribution of this paper, we present a stable scheduling algorithm for both of these models. The algorithm is myopic, distributed and performs few logical operations at each node per unit time.National Science Foundation (U.S.). Project (CNS 0546590)National Science Foundation (U.S.). Project (TF 0728554)United States. Defense Advanced Research Projects Agency. Information Theory for Mobile Ad-Hoc Networks ProgramUnited States. Air Force Office of Scientific Research (Complex networks project
Feasible Rate Allocation in Wireless Networks
Full text linkRate allocation is a fundamental problem in the operation of a wireless network because of the necessity to schedule the operation of mutually interfering links between the nodes. Among the many reasons behind the importance of efficiently determining the membership of an arbitrary rate vector in the feasibility region, is its high relevance in optimal cross layer design. A key feature in a wireless network is that links without common nodes can also conflict (secondary interference constraints). While the node exclusive model problem has efficient algorithms, it has long been known that this is a hard problem with these additional secondary constraints. However, wireless networks are usually deployed in geographic areas that do not span the most general class of all graphs possible. This is the underlying theme of this paper, where we provide algorithms for two restricted instances of wireless network topologies. In the first tractable instance, we consider nodes placed arbitrarily in a region such that (a) the node density is bounded, and (b) a node can only transmit or interfere with other nodes that are within a certain limited radius. We obtain a simple (1 - epsi) polynomial-time approximation scheme for checking feasibility (for any epsi > 0). The second instance considers the membership problem of an arbitrary rate-vector in the feasible set, where the nodes are distributed within a slab of fixed width (there are no density assumptions). Specifically, the results in [13] are shown to extend to a much more general class of graphs, which we call the (dmin,dmax) class of graphs, and this generalization is used to obtain a strongly polynomial time algorithm that decides membership of a rate-vector where the hosts are distributed within an infinite corridor with fixed cross-section
Editorial introduction
Full text linkWe are pleased to present this special issue “Recent Trends in the Mathematics of Wireless Communication Networks: Algorithms, Models, and Methods.” Wireless communication systems have experienced a spectacular expansion over the last few decades, now providing the predominant means of Internet access. The capacity of these systems is constrained by a set of scarce resources such as radio frequencies, transmit power, and time slots. Information theory offers a powerful mathematical framework to understand how these transmission resources should be allocated so as to maximize the capacity at the physical layer, yielding valuable insights for the design of efficient schemes for, e.g., modulation, coding, and power control. Typically, however, information-theoretic models pertain to idealized scenarios: They do not account for random user behavior and dynamics at higher network layers; the practical application-specific performance requirements are largely ignored, and algorithmic implementation constraints are usually not considered. Designing systems while systematically addressing all of these aspects has posed major challenges in the last few decades. The vital need for wireless networks with significantly better performance has rejuvenated research activities toward tackling these challenges
- …
