Search

We consider a large distributed MIMO system where wireless users with single transmit and receive antenna cooperate in clusters to form distributed transmit and receive antenna arrays. We characterize how the capacity of the distributed MIMO transmission scales with the number of cooperating users, the area of the clusters and the separation between them, in a line-of-sight propagation environment. We use this result to answer the following question: can distributed MIMO provide significant capacity gain over traditional multi-hop in large adhoc networks with n source-destination pairs randomly distributed over an area A? Two diametrically opposite answers and have emerged in the current literature. We show that neither of these two results are universal and their validity depends on the relation between the number of users n and \sqrtA/λ, which we identify as the spatial degrees of freedom in the network. λ is the carrier wavelength. When \sqrtA/λ≥ n, there are n degrees of freedom in the network and distributed MIMO with hierarchical cooperation can achieve a capacity scaling linearly in n as in , while capacity of multihop scales only as \sqrtn. On the other hand, when \sqrtA/λ≤ \sqrtn as in , there are only \sqrtn degrees of freedom in the network and they can be readily achieved by multihop. Our results also reveal a third regime where \sqrtn≤\sqrtA/λ≤ n. Here, the number of degrees of freedom are smaller than n but larger than what can be achieved by multi-hop. We construct scaling optimal architectures for this intermediate regime. [ABSTRACT FROM PUBLISHER]

The task of estimating path available bandwidth is difficult but paramount for QoS routing in supporting bandwidth-demanding traffic in multirate and multihop wireless ad hoc networks. The multirate capability and the impact of background traffic has not been carefully studied for the problem of estimating path available bandwidth in prior works. In this paper, we develop a theoretical model for estimating the available bandwidth of a path by considering interference from both background traffic and traffic along the path. We show that the clique constraint widely used to construct upper bounds does not hold any more when links are allowed to use different rates at different time. In our proposed model, traditional clique is coupled with rate vector to more properly characterize the conflicting relationships among links in wireless ad hoc networks where time-varying link adaption is used. Based on this model, we also investigate the problem of joint optimization of QoS routing and link scheduling. Several routing metrics and a heuristic algorithm are proposed. The newly proposed conservative clique constraint performs the best among the studied metrics in estimating available bandwidth of flows with background traffic. [ABSTRACT FROM AUTHOR]

In this paper, we model the network throughput gains of two types of wireless network coding (NC) schemes, including the conventional NC and the analog NC schemes, the traditional non-NC transmission scheduling schemes in multihop, multi-channel, and multi-radio wireless ad hoc networks. particular, we first show that the network throughput gains conventional NC and analog NC are (2n)/(2n-1) and n/( respectively, for the n-way relay networks where n ≥ 2. we propose an analytical framework for deriving the network throughput gain of the wireless NC schemes over general wireless network topologies. By solving the problem of maximizing network throughput subject to the fairness requirements our proposed framework, we quantitatively analyze the throughput gains of these two types of wireless NC schemes a variety of wireless ad hoc network topologies with different routing strategies. Finally, we develop a heuristic joint scheduling, channel assignment, and routing algorithm that at approaching the optimal solution to the optimization problem under our proposed framework. [ABSTRACT FROM AUTHOR]

One of the distinctive features in a wireless ad hoc network is lack of any central controller or single point of authority, in which each node/link then makes its own decisions independently. Therefore, fully cooperative behaviors, such as cooperation for increasing system capacity, mitigating interference for each other, or honestly revealing private information, might not be directly applied. It has been shown that power control is an efficient approach to achieve quality of service (QoS) requirement in ad hoc networks. However, the existing work has largely relied on cooperation among different nodes/links or a pricing mechanism that often needs a third-party involvement. In this paper, we aim to design a non-cooperative power control algorithm without pricing mechanism for ad hoc networks. We view the interaction among the users' decision for power level as a repeated game. With the theory of stochastic fictitious play (SFP), we propose a reinforcement learning algorithm to schedule each user's power level. There are three distinctive features in our proposed scheme. First, the user's decision at each stage is self-incentive with myopic best response correspondence. Second, the dynamics arising from our proposed algorithm eventually converges to pure Nash Equilibrium (NE). Third, our scheme does not need any information exchange or to observe the opponents' private information. Therefore, this proposed algorithm can safely run in a fully selfish environment without any additional pricing and secure mechanism. Simulation study demonstrates the effectiveness of our proposed scheme. [ABSTRACT FROM AUTHOR]

We investigate issues that Bluetooth may face in evolving from a simple wire replacement to a large-scale ad hoc networking technology. We do so by examining the efficacy of Bluetooth in establishing a connected topology, which is a basic requirement of any networking technology. We demonstrate that Bluetooth experiences some fundamental algorithmic challenges in accomplishing this seemingly simple task. Specifically, deciding whether there exists at least one connected topology that satisfies the Bluetooth constraints is NP-hard. Several implementation problems also arise due to the internal structure of the Bluetooth protocol stack. All these together degrade the performance of the network, or increase the complexity of operation. Given the availability of efficient substitute technologies, Bluetooth's use may end up being limited to small ad hoc networks. [ABSTRACT FROM AUTHOR]

Fair queueing of rate and delay-sensitive packet flows in a shared-medium, multihop wireless network is challenging due to the unique design issues. These issues include: 1) spatial contention among transmitting flows in a spatial locality, as well as spatial reuse of bandwidth through concurrent flow transmissions in different network locations; 2) conflicts between ensuring fairness and maximizing spatial channel reuse; and 3) the distributed nature of ad hoc fair queueing. In this paper, we propose a new topology-independent fair queueing model for a shared-medium ad hoc network. Our fairness model ensures coordinated fair channel access among spatially contending flows, while seeking to maximize spatial reuse of bandwidth. We describe packetized algorithms that realize the fluid fairness model with analytical performance bounds. We further design a distributed implementation which approximates the ideal centralized algorithm. We present simulations and analysis on the performance of our proposed algorithms. [ABSTRACT FROM AUTHOR]

We propose a new routing graph, the restricted Delaunay graph (RDG), for mobile ad hoc networks. Combined with a node clustering algorithm, the RDG can be used as an underlying graph for geographic routing protocols. This graph has the following attractive properties: 1) it is planar; 2) between any two graph nodes there exists a path whose length, whether measured in terms of topological or Euclidean distance, is only a constant times the minimum length possible; and 3) the graph can be maintained efficiently in a distributed manner when the nodes move around. Furthermore, each node only needs constant time to make routing decisions. We show by simulation that the RDG outperforms previously proposed routing graphs in the context of the Greedy perimeter stateless routing (GPSR) protocol. Finally, we investigate theoretical bounds on the quality of paths discovered using GPSR. [ABSTRACT FROM AUTHOR]

We investigate from an algorithmic perspective the maxmin fair allocation of bandwidth in wireless ad hoc networks. We formalize the maxmin fair objective under wireless scheduling constraints, and present a necessary and sufficient condition for maxmin fairness of a bandwidth allocation. We propose an algorithm that assigns weights to the sessions dynamically such that the weights depend on the congestion in the neighborhood, and schedules the sessions that constitute a maximum weighted matching. We prove that this algorithm attains the maxmin fair rates, even though it does not use any information about the statistics of the packet arrival process. [ABSTRACT FROM AUTHOR]

In this paper, the network planning problem in wireless ad hoc networks is formulated as the problem of allocating physical and medium access layer resources or supplies to minimize a cost function, while fulfilling certain end-to-end communication demands, which are given as a collection of multicast sessions with desired transmission rates. We propose an iterative cross-layer optimization, which alternates between: 1) jointly optimizing the timesharing in the medium access layer and the sum of max of flows assignment in the network layer and 2) updating the operational states in the physical layer. We consider two objectives, minimizing aggregate congestion and minimizing power consumption, respectively, corresponding to operating in a bandwidth-limited regime and in an energy-limited regime. The end result is a set of achievable tradeoffs between throughput and energy efficiency, in a given wireless network with a given traffic pattern. We evaluate our approach quantitatively by simulations of community wireless networks and compare with designs that decouple the layers. We demonstrate that significant performance advantages can be achieved by adopting a full-fledged cross-layer optimization. Furthermore, we observe that optimized solutions generally profit from network coding, physical-layer broadcasting, and traffic-dependent physical states. [ABSTRACT FROM AUTHOR]

In a wireless network with multihop transmissions and interference-limited link rates, can we balance power control in the physical layer and congestion control in the transport layer to enhance the overall network performance while maintaining the architectural modularity between the layers? We answer this question by presenting a distributed power control algorithm that couples with existing transmission control protocols (TCPs) to increase end-to-end throughput and energy efficiency of the network. Under the rigorous framework of nonlinearly constrained utility maximization, we prove the convergence of this coupled algorithm to the global optimum of joint power control and congestion control, for both synchronized and asynchronous implementations. The rate of convergence is geometric and a desirable modularity between the transport and physical layers is maintained. In particular, when congestion control uses TCP Vegas, a simple utilization in the physical layer of the queueing delay information suffices to achieve the joint optimum. Analytic results and simulations illustrate other desirable properties of the proposed algorithm, including robustness to channel outage and to path loss estimation errors, and flexibility in trading off performance optimality for implementation simplicity. This paper presents a step toward a systematic understanding of "layering" as "optimization decomposition," where the overall communication network is modeled by a generalized network utility maximization problem, each layer corresponds to a decomposed subproblem, and the interfaces among layers are quantified as the optimization variables coordinating the subproblems. In the case of the transport and physical layers, link congestion prices turn out to be the optimal "layering prices." [ABSTRACT FROM AUTHOR]

We consider the problem of determining the maximum capacity of the media access (MAC) layer in wireless ad hoc networks. Due to spatial contention for the shared wireless medium, not all nodes can concurrently transmit packets to each other in these networks. The maximum number of possible concurrent transmissions is, therefore, an estimate of the maximum network capacity, and depends on the MAC protocol being used. We show that for a large class of MAC protocols based on virtual carrier sensing using RTS/CTS messages, which includes the popular IEEE 802.11 standard, this problem may be modeled as a maximum Distance-2 matching (D2EMIS) in the underlying wireless network: Given a graph G(V, E), find a set of edges E' ⊆ E such that no two edges in E' are connected by another edge in E. D2EMIS is NP-complete. Our primary goal is to show that it can be approximated efficiently in networks that arise in practice. We do this by focusing on an admittedly simplistic, yet natural, graph-theoretic model for ad hoc wireless networks based on disk graphs, where a node can reach all other nodes within some distance (nodes may have unequal reach distances). We show that our approximation yields good capacity bounds. Our work is the first attempt at characterizing an important "maximum" measure of wireless network capacity, and can be used to shed light on previous topology formation protocols like Span and GAF that attempt to produce "good" or "capacity-preserving" topologies, while allowing nodes to alternate between sleep and awake states. Our work shows an efficient way to compute an upper bound on maximum wireless network capacity, thereby allowing topology formation algorithms to determine how close they are to optimal. We also outline a distributed algorithm for the problem for unit disk graphs, and briefly discuss extensions of our results to: 1) different node interference models; 2) directional antennas; and 3) other transceiver connectivity structures besides... [ABSTRACT FROM AUTHOR]

In recent years, there has been an increasing interest to deliver multimedia services over wireless ad hoc networks. Due to the existence of hidden terminal and absence of central control, the medium access control protocol as used in the ad hoc networks may lead to channel capture, where some flows monopolize the channel while others suffer from starvation. As a consequence, the system throughput and fairness are greatly degraded. After showing that static power control leads to channel capture, we propose and study a distributed dynamic power control scheme termed "power adaptation for starvation avoidance" (PASA), which dynamically adjusts the transmission power of a node so as to avoid starvation. PASA is shown to be effective in breaking channel captures, hence improving short-term fairness among contending flows. It is simple, fully autonomous and requires no communication overhead. Via extensive simulations, we show that our power control algorithm achieves much better fairness without compromising system throughput through better spatial reuse. Our experiments with video sequences transmitting over different network topologies show that PASA achieves much better video quality with lower start-up delay and buffer requirement. [ABSTRACT FROM AUTHOR]

Guaranteeing continuous streaming of multimedia data from service providers to the users is a challenging task in wireless ad hoc networks, particularly when node mobility is considered. The topological dynamics introduced by node mobility are further exacerbated by the natural grouping behavior of mobile users, which leads to frequent network partitioning. Network partitioning poses significant challenges to the provisioning of continuous multimedia streaming services in wireless ad hoc networks, since the partitioning disconnects many mobile users from the centralized streaming service. In this paper, we propose NonStop, a collection of novel middleware-based run-time algorithms that ensures the continuous availability of such multimedia streaming services, while minimizing the overhead involved. The network-wide continuous streaming coverage is achieved by partition prediction and service replication on the streaming sources and assisted by distributed selection of streaming sources on regular mobile nodes and users. The proposed algorithms are validated by extensive results from performance evaluations. [ABSTRACT FROM AUTHOR]