Nefeli Gkouti, Prodromos Malakasiotis, Stavros Toumpis, Ion Androutsopoulos. Proceedings of the 18th Conference of the European Chapter of the Association for Computational Linguistics (Volume 1: Long Papers). 2024.

For randomly distributed nodes sending packets to a central gateway using slotted Aloha with a constrained number of retransmissions over a wireless fading channel, we take an iterative approach to compute the total traffic density of packet transmissions and collision-induced retransmissions as a function of the node-gateway distance. From this, we compute the outage probability, throughput, and energy consumption. This method can be used to analyze and dimension Low-Power Wide-Area Networks (LPWANs). Applying it in LoRa illustrates design tradeoffs concerning outage probability, spreading factors, energy consumption, and cell size. It notably shows that permitting more retransmissions helps the nodes near the gateway but hurts distant ones.

We present a method for experimentally measuring the capacity region of a wireless network, defined here as the set of all possible combinations of simultaneously achievable link transmission rates. Due to the inherent complexity of the problem, measuring the capacity region exactly typically involves a prohibitively large volume of experiments. Therefore, the method is based on a judicious, tunable algorithm, employing online machine learning, which aims at reducing the volume of experiments conducted. In order to evaluate the efficiency of the method, and also to demonstrate the usefulness of having the capacity region available, we apply our method to a network of Raspberry Pi nodes placed inside a building and communicating using IEEE 802.11. In particular, we compare the performance of an optimal, centrally organized communication scheme, computed using the measured capacity region within a network optimization formulation, with the performance of a simple communication scheme that uses multihop TCP flows.

An increasing number of Low Latency Applications (LLAs) in the entertainment, IoT, and automotive domains require response times that challenge the traditional application provisioning using distant Data Centres. The fog computing paradigm extends cloud computing at the edge and middle-tier locations of the network, providing response times an order of magnitude smaller than those that can be achieved by the current “client-to-cloud” network model. Here, we address the challenges of provisioning heavily stateful LLA in the setting where fog infrastructure consists of third-party computing resources, i.e., cloudlets, that come in the form of “data centres in the box”. We introduce FogSpot, a charging mechanism for on-path, on-demand, application provisioning. In FogSpot, cloudlets offer their resources in the form of Virtual Machines (VMs) via markets, collocated with the cloudlets, that interact with forwarded users’ application requests for VMs in real time. FogSpot associates each cloudlet with a price based on applications’ demand. The proposed mechanism’s design takes into account the characteristics of cloudlets’ resources, such as their limited elasticity, and LLAs’ attributes, like their expected QoS gain and engagement duration. Lastly, FogSpot guarantees the end users’ requests truthfulness while focusing in maximising either each cloudlet’s revenue or resource utilisation.

A mobile wireless delay-tolerant network (DTN) model is proposed and analyzed, in which infinitely many nodes are initially placed on R2according to a uniform Poisson point process (PPP) and subsequently travel, independently of each other, along trajectories comprised of line segments, changing travel direction at time instances that form a Poisson process, each time selecting a new travel direction from an arbitrary distribution; all nodes maintain constant speed. A single information packet is traveling towards a given direction using both wireless transmissions and sojourns on node buffers, according to a member of a class of utility-based routing rules. For this model, we compute the long-term averages of the speed with which the packet travels towards its destination and the rate with which the wireless transmission cost accumulates. Because of the complexity of the problem, we employ two intuitive, simplifying approximations; simulations show that the approximation error is typically small. Our results provide intuition on the fundamental trade-off that exists in mobile wireless DTNs between the packet speed and the packet delivery cost. The framework developed here is both general and versatile, and can be used as a starting point for further investigation.

We study a mobile wireless network in which nodes travel on an infinite plane along trajectories comprised of linear segments; a single packet is traveling towards a destination located at an infinite distance, employing both wireless transmissions and sojourns on node buffers. In this setting, we calculate analytically the long-term averages of (i) the speed with which the packet travels towards its destination and (ii) the rate with which the wireless transmission cost accumulates with distance traveled. Due to the problem's complexity, we use two approximations; simulations show that the resulting errors are modest.

An infinite number of nodes move in ℝ2according to a random waypoint model; a single packet is traveling towards a destination (located at an infinite distance away) using combinations of wireless transmissions and physical transport on the buffers of nodes. In earlier work [1] we defined two performance metrics, namely, the long-term average speed with which the packet travels towards its destination, and the rate with which transmission cost accumulates with distance covered. Explicit expressions were derived for these metrics, under specific ergodicity assumptions. In this paper we give a precise description of the induced Markov process, we show that it is indeed (uniformly) geometrically ergodic, and that the law of large numbers holds for the random variables of interest. In particular, we show that the two performance metrics are well-defined and asymptotically constant with probability one.

Cloud computing has been tremendously successful in providing a commercial infrastructure for hosting computationally intensive applications. Nevertheless, an increasing number of Low Latency Applications (LLAs) notably in the entertainment, IoT, and automative domains require response times much smaller than the supported ones by the typical “client-to-cloud” network model. Cloudlets have been introduced as “data centres in a box”, for bringing computing resources “closer” to the end users. As a result, LLAs can take advantage of cloudlets to improve their Quality-of-Service (QoS) by reducing the underlying response times between their users and application instances' location. In this work, we study the emerging market of stateful LLAs' provisioning over geo-distributed third-party cloudlets. We assume that cloudlets offer their resources in the form of Virtual Machines (VMs) via collocated markets. Forwarding requests for LLAs interact with cloudlet markets for performing on-path and on-demand resource provisioning. We introduce a pricing scheme where users pay a fixed price for each time unit of their engagement to an LLA instance. Our evaluation on realistic topologies and application requests demonstrate the merits of on-demand provisioning when accompanied by a pay-as-you-go pricing scheme.

We study a simple one-dimensional, discrete-time network model that consists of two nodes moving on a discrete circle, changing their direction of movement randomly, and a single packet travelling in the clockwise direction, using combinations of transmissions between the two nodes (when they are co-located) and physical transports on their buffers. In this setting, we provide exact, explicit expressions for the long-term averages of the packet speed and the wireless transmission cost. Our work is a first step towards providing simple and exact results for more realistic wireless delay-tolerant network models.

We study a wireless network comprising an infinite number of nodes moving in ℝ2according to a Random Waypoint (RWP) mobility model. Each node is equipped with a radio transceiver with transmission range R; a transmission across a distance d incurs a quadratic cost d2. We assume that a packet is generated at one node and must be delivered to a destination located at an infinite distance in the direction of the positive x-axis through a combination of wireless transmissions and physical transports on the buffers of nodes. A routing rule specifies when a wireless transmission should take place. Given this setting, we develop an analytic framework, using tools from stochastic geometry and Markov chains theory, to evaluate, with certain approximations, the tradeoff between the speed with which the packet travels toward the destination and the transmission cost incurred per unit of distance. Simulation results show a good match with the analytical results.

We propose and prove a theorem that allows the calculation of a class of functionals on Poisson point processes that have the form of expected values of sum-products of functions. In proving the theorem, we present a variant of the Campbell-Mecke theorem from stochastic geometry. We proceed to apply our result in the calculation of expected values involving interference in wireless Poisson networks. Based on this, we derive outage probabilities for transmissions in a Poisson network with Nakagami fading. Our results extend the stochastic geometry toolbox used for the mathematical analysis of interference-limited wireless networks.

We investigate the statistics of the number of time slots T that it takes a packet to travel through a chain of wireless relays. Derivations are performed assuming an interference model for which interference possesses spatiotemporal dependency properties. When using this model, results are harder to arrive at analytically, but they are more realistic than the ones obtained in many related works that are based on independent interference models. First, we present a method for calculating the distribution of T. As the required computations are extensive, we also obtain simple expressions for the expected value E[T] and variance Var[T]. Finally, we calculate the asymptotic limit of the average speed of the packet. Our numerical results show that spatiotemporal dependence has a significant impact on the statistics of the travel time T. In particular, we show that, with respect to the independent interference case, E[T] and Var[T] increase, whereas the packet speed decreases.

We study a linear multihop network that is formed by wireless devices that can directly communicate pairwise whenever two devices are within range of each other. This Device-to-Device communication model is expected to play a significant role in future 5G wireless networks due to its advantages (e.g., cellular offloading, increased throughput and low cost/energy communication). In such networks, devices are typically selfish and compete for channel access aiming at maximizing their own throughput while at the same time avoiding packet collisions. In this setup, we study how an efficient coexistence of these devices may be achieved, using a game-theoretic approach. First, we model the contention for the channel as a game and study the structural properties of the resulting Nash Equilibria (NE). Then, we design a distributed, round-based scheme that is guaranteed to converge to a NE. We compare quantitatively and qualitatively this scheme with previous work. We show that this scheme converges faster to a NE, in a number of rounds that is proportional to the logarithm of the number of nodes of the network. Moreover, the convergence is monotonic, meaning that the percentage of nodes that finalize their strategy is increasing in each round.

We investigate the problem of replication in large wireless networks that employ caching in the case of a single file whose popularity varies with time. As opposed to the case of static popularity, in this case for the network resources to be efficiently allocated the replication should vary with time. In this study, we first outline the low-level operations of wireless networks with caching, which involve decisions of combinatorial complexity, such as about the contents of all network caches. To overcome this complexity, we approximate the network optimization with a formulation based on the frequency of file replication across the network - a high-level perspective, amenable to mathematical analysis. We present a solution that is based on looking ahead into the future and has a simple graphical representation.

This short paper describes the objectives and initial results of project I-CAN: Information-Centric Future Mobile and Wireless Access Networks. I-CAN seeks to radically advance the integration of cellular and wireless access technologies by developing and evaluating architectures and procedures for future access networks based on Information-Centric Networking (ICN).

An infinite number of nodes travel on ℝ2, along straight lines, with a common speed υn. Any transmission across a distance d incurs a cost c(d). We devise and study, both by analysis (using stochastic geometry tools) and simulation, forwarding rules that transport packets towards a given direction using combinations of wireless transmissions and physical transfers on node buffers. The forwarding rules are evaluated in terms of two metrics: the packet delivery delay and the aggregate transmission cost, both per unit of distance covered. We explore the tradeoff between these two metrics in terms of the points on the delay-cost plane achieved by our forwarding rules.

We study flow optimization in wireless Delay Tolerant Networks (DTNs), using Capacity Region Evolving Graphs (CREGs). CREGs comprise cascaded subgraphs which represent the network topology at consecutive time intervals called epochs. The data flows jointly attainable at all wireless links during each time interval are described in terms of a respective capacity region. We associate the sizes of the node buffers at the beginning and end of time with a set of cost and utility functions, and formulate the transport problem of maximizing the sum of the utilities minus the sum of the costs. Then, we present a primal decomposition algorithm for solving this flow optimization problem exactly and efficiently, taking advantage of its special structure. This algorithm unavoidably relies on the knowledge, in advance, of the complete evolution of the network topology at all epochs. As this is a stringent requirement, we devise a heuristic online algorithm that arrives at efficient (but suboptimal) flows at each epoch without looking into future epochs.

We show by means of stochastic geometry that interference dynamics has a strong impact on the performance of cooperative relaying. For both conventional and multi-hop-aware cooperative relaying we show that the packet delivery probability significantly changes with the dependence of interference among the links. Depending on the scenario under consideration, this change could be either an increase or decrease of the packet delivery probability. Especially for multi-hop-aware cooperative relaying, the performance gain is heavily reduced when interference possesses high temporal and spatial dependence.

In Delay Tolerant Networks (DTNs), there is a fundamental tradeoff between the aggregate transport cost of a packet and the delay in its delivery. We study this tradeoff in the context of geographical routing in wireless DTNs. We first specify the optimal cost/delay tradeoff, i.e., the tradeoff under optimal network operation, using a dynamic network construction termed the Cost/Delay Evolving Graph (C/DEG) and the Optimal Cost/Delay Curve (OC/DC), a function that gives the minimum possible aggregate transportation cost versus the maximum permitted delivery delay. We proceed to evaluate the performance of two known delay tolerant geographic routing rules, i.e., MOVE and AeroRP, a delay tolerant version of the geographic routing rule that selects as next relay the node for which the cost-per-progress ratio is minimized, and finally two novel rules, the Balanced Ratio Rule (BRR) and the Composite Rule (CR). The evaluation is in terms of the aggregate packet transmission cost as a function of the maximum permitted packet delivery delay. Simulations show that CR achieves a cost/delay tradeoff that is overall the closest to the optimal one specified by the OC/DC, while BRR achieves the smallest aggregate transmission costs for large packet delays and a fixed transmission cost model.

The efficient management of the radio spectrum is a key functionality in every type of wireless network. Wireless nodes generally have heterogeneous QoS targets, which sometimes cannot be satisfied for all of them due to the high interference levels that frequently arise, even in sparse topologies. In this work, we propose a distributed negotiation-based power control algorithm that aims at maximizing the number of nodes achieving their QoS targets. Our algorithm combines the influential Foschini-Miljanic power control algorithm with a bargaining-inspired phase (among the unsatisfied nodes only). In particular, all nodes are endowed with an initial budget; unsatisfied nodes randomly pick others to negotiate with for the level of their transmission powers; if a negotiation leads to an agreement, a node gives some (predefined) reward to the other and the latter reduces its power to the agreed level; the process is then repeated, using the updated budgets. Simulations show that, under various negotiation scenarios, our scheme is more efficient than previously proposed approaches that impose on the "weakest" nodes (those that are further from their targets) to turn off their power completely. More importantly, our scheme leads to a statistical rotation of the set of nodes that achieve their target, independently of the initial budget allocation, and hence is more fair.

We study flow optimization in cognitive Wireless Mesh Networks (WMN) that lease bandwidth from a collocated cellular network (CN). We develop a distributed mechanism that such WMNs can use to optimize their traffic given their own utilities and costs and the costs that the CN is charging for the use of its channels. We evaluate the mechanism in a synthetic scenario using the topology of a deployed WMN and time-varying traffic requirements induced from real-life vehicle mobility traces. Simulations show that the mechanism can track well the changes in the problem parameters, continuously keeping close to the optimum operation point.

We study load balancing in wireless networks with a single class of traffic, focusing our attention on an important example, i.e., wireless sensor networks. The analysis is based on the wireless minimum cost problem, an optimization problem that implicitly captures the effects of interference through the novel use of an arc cost function that depends on the amount of traffic flowing through nearby links. We present an algorithm that optimizes the flow by modifying the traffic along cycles constructed during an initialization phase. Its operation may be viewed as trying to satisfy Kirchhoff's Voltage Law on an electric circuit containing interferistors. It is robust, distributed, with minimal communication overhead, and converges quickly. Furthermore, when the traffic is elastic, the algorithm can be easily modified to also perform congestion control.

We develop bounds on the capacity of wireless multihop networks when the traffic pattern is non-uniform, i.e., not all nodes are the sources and sinks of similar volumes of traffic. Our results are asymptotic, i.e., they hold with probability going to unity as the number of nodes goes to infinity. We study (i) asymmetric networks, where the numbers of sources and destinations of traffic are unequal, (ii) multicast networks, in which each created packet has multiple destinations, (Hi) cluster networks, that consist of clients and a limited number of cluster heads, and each client wants to communicate with any one of the cluster heads, and (iv) hybrid networks, in which the nodes are supported by a limited infrastructure. Our findings quantify the fundamental capabilities of these wireless multihop networks to handle traffic bottlenecks, and point to correct design principles that achieve the capacity without resorting to overly complicated protocols.

We study routing for massively dense wireless networks, i.e., wireless networks that contain so many nodes that, in addition to their usual microscopic description, a novel macroscopic description becomes possible. The macroscopic description is not detailed, but nevertheless contains enough information to permit a meaningful study and performance optimization of the network. Within this context, we continue and significantly expand previous work on the analogy between optimal routing and the propagation of light according to the laws of Geometrical Optics. Firstly, we pose the analogy in a more general framework than previously, notably showing how the eikonal equation, which is the central equation of Geometrical Optics, also appears in the networking context. Secondly, we develop a methodology for calculating the cost function, which is the function describing the network at the macroscopic level. We apply this methodology for two important types of networks: bandwidth limited and energy limited.

In this correspondence, we determine the optimal power allocation, that achieves any specified point on the boundary of the capacity region, for sets of parallel Gaussian multiple-access channels (MACs) and sets of parallel Gaussian broadcast channels (BCs). The power allocation is across the parallel channels and, within each channel, across the users. In both cases, there is a single constraint on the total power used. First, the allocation for the parallel MACs is determined, in a simple form, using the Karush-Kuhn-Tucker (KKT) conditions and a simple Lagrangian argument. Using this result, the allocation for the parallel BCs is derived using recent findings on the duality of the MAC and BC.

A spatially distributed set of sources is creating data that must be delivered to a spatially distributed set of sinks. A network of wireless nodes is responsible for sensing the data at the sources, transporting them over a wireless channel, and delivering them to the sinks. The problem is to find the optimal placement of nodes, so that a minimum number of them is needed. The critical assumption is made that the network is massively dense, i.e., there are so many sources, sinks, and wireless nodes, that it does not make sense to discuss in terms of microscopic parameters, such as their individual placements, but rather in terms of macroscopic parameters, such as their spatial densities. Assuming a particular interference-limited, capacity-achieving physical layer, and specifying that nodes only need to transport the data (and not to sense them at the sources, or deliver them at the sinks once their location is reached), the optimal node placement induces a traffic flow that is identical to the electrostatic field created if the sources and sinks are replaced by a corresponding distribution of positive and negative charges. Assuming a general model for the physical layer, and specifying that nodes must not only transport the data, but also sense them at the sources and deliver them at the sinks, the optimal placement of nodes is given by a scalar nonlinear partial differential equation found by calculus of variations techniques. The proposed formulation and derived equations can help in the design of large wireless sensor networks that are deployed in the most efficient manner, not only avoiding the formation of bottlenecks, but also striking the optimal balance between reducing congestion and having the data packets follow short routes.

We introduce two new medium access control (MAC) protocols for wireless ad hoc networks, the progressive backoff algorithm (PBOA) and the progressive ramp up algorithm (PRUA). Both protocols divide time in frames in which a contention slot is followed by a data slot. PBOA is integrated with a well known power control algorithm. PRUA performs no power control, and so is not as energy efficient, but can achieve a tight packing of transmissions by allowing nodes to make educated decisions during the contention period. Under both protocols, contenting nodes try to select their potential destinations so that spatial reuse is as high as possible, even if that means transmitting a packet that is not on the head of their routing buffer. We compare both protocols with carrier sense multiple access with collision avoidance (CSMA/CA), and also with the power control MAC (PCM) protocol. We also compare them with a hypothetical MAC protocol that would be able to make optimal decisions and so achieve the network capacity. We show that both protocols perform better than CSMA/CA and PCM in terms of throughput and robustness with respect to the choice of the routing protocol. Also, PRUA is more energy efficient than CSMA/CA, and PBOA is more energy efficient than both CSMA/CA and PCM. However, due to their distributed nature, our protocols still can not achieve the network capacity, even in simple network topologies

We investigate the spatial distribution of wireless nodes that can transport a given volume of traffic in a sensor network, while requiring the minimum number of wireless nodes. The traffic is created at a spatially distributed set of sources, and must arrive at a spatially distributed set of sinks. Under a general assumption on the physical and medium access control (MAC) layers, the optimal distribution of nodes induces a traffic flow identical to the electrostatic field that would exist if the sources and sinks of traffic were substituted with an appropriate distribution of electric charge. This analogy between electrostatics and wireless sensor networks can be extended in a number of different ways. For example, Thomson's theorem on the distribution of electric charge on conductors gives the optimal distribution of traffic sources and sinks (that minimizes the number of nodes needed) when we have a limited degree of freedom on their initial placement. Electrostatics problems with Neumann boundary conditions and topologies with different types of dielectric materials can also be interpreted in the context of wireless sensor networks. The analogy also has important limitations. For example, if we move to a three dimensional topology, adapting our general assumption on the physical and MAC layers accordingly, or we stay in the two dimensional plane but use an alternative assumption, that is more suited to ultra wide band communication, the optimal traffic distribution is not in general irrotational, and so can not be interpreted as an electrostatic field. Finally, the analogy cannot be extended to include networks that support more than one type of traffic.

We determine the maximum transport capacity of a Gaussian broadcast channel and of a Gaussian multiple access channel. Transport capacity is defined as the sum, over all simultaneous transmissions, of the product of the transmission rate with a reward r(x), where x is the distance between the receiver and the transmitter. In the case of the broadcast channel, the optimization is performed over all allocations of the transmitter power to the signals intended for the different receivers. In the case of the multiple access channel, the optimization is performed over all allocations of power at the transmitters that satisfy a sum constraint. Our approach is to assume a large number of receivers (or transmitters) and formulate the problem within the framework of the calculus of variations

We study a setting in which a spatially distributed set of sources is creating data that must be delivered to a spatially distributed set of sinks. A network of wireless nodes is responsible for sensing the data, transporting them over a wireless channel to the sink locations, and delivering them to the sinks. The problem is to find the optimal placement of these nodes, so that the minimum number of nodes is needed. Our approach is to assume a massively dense network, in which there are so many sources, sinks, and wireless nodes, that it does not make sense to model the network in terms of microscopic parameters, such as their individual placements, but rather in terms of macroscopic parameters, such as their spatial densities. We use calculus of variations to describe the optimal spatial density of nodes, that minimizes their total number but can still support the whole traffic, in terms of a scalar, nonlinear, partial differential equation. The derivation is under a general model for the physical layer, that encompasses many cases of interest. Our work can help in the design of networks that are deployed in the most efficient manner, not only avoiding the formation of bottlenecks, but also striking the optimal balance between avoiding congestion and having the data packets follow short routes.

We study the transport capacity of a Gaussian multiple access channel, which consists of a set of transmitters and a single receiver. The transport capacity is defined as the sum, over all transmitters, of the product of the transmission rate with a reward r(x), which is a function of the distance x between the transmitter and the receiver, and quantifies the usefulness of the transmitting information over a distance x. Assuming that the sum of the transmitter powers is upper bounded, we present in closed form the optimal power allocation among the transmitters, that maximizes the transport capacity. We then present simple expressions for the optimal power allocation and induced transport capacity, as the number of transmitters approaches infinity. We also study the transport capacity of a Gaussian broadcast channel, which consists of a single transmitter and multiple receivers. Here, the transport capacity is defined as the sum, over all receivers, of the product of the transmission rate with a reward r(x). We determine in closed form the maximum possible transport capacity and the distribution of the available transmitter power among the receivers that achieve it. Although this result has already been reported in the literature, our derivation is shorter, and leads to simpler expressions. Our results can be used to gain intuition and develop good design principles in a variety of settings. For example, they apply to the uplink and downlink channel of cellular networks, and also to sensor networks which consist of multiple sensors that communicate with a single central station.

We study wireless ad hoc networks with a large number of nodes. We first focus on a network of n immobile nodes, each with a destination node chosen in random. We develop a scheme under which, in the absence of fading, the network can provide each node with a traffic rate /spl lambda//sub 1/(n)=K/sub 1/(nlog n)/sup -1/ 2/. This result was first shown in J. Hightower and G. Borriello (2001) under a similar setting, however the proof presented here is shorter and uses only basic probability tools. We then proceed to show that, under a general model of fading, each node can send data to its destination with a rate /spl lambda//sub 2/(n)=K/sub 2/n/sup -1// /sup 2/(log n)/sup -3/2/. Next, we extend our formulation to study the effects of node mobility. We first develop a simple scheme under which each of the a mobile nodes can send data to a randomly chosen destination node with a rate /spl lambda//sub 3/(n)=K/sub 3/n/sup -1/2/(log n)/sup -3/2/, and with a fixed upper bound on the packet delay d/sub max/ that does not depend on n. We subsequently develop a scheme under which each of the nodes can send data to its destination with a rate /spl lambda//sub 4/(n)=K/sub 4/n/sup (d-1)/ 2/(log n)/sup -5/ 2 /provided that nodes are willing to tolerate packet delays smaller than d/sub max/(n)<K/sub 5/n/sup d/, where 0<d<1. With both schemes, a general model of fading is assumed. In addition, nodes require no global topology or routing information, and only need to coordinate locally. The above results hold for an appropriate choice of values for the constants K/sub i/, and with probability approaching 1 as the number of nodes n approaches infinity.

We present capacity results for three classes of wireless ad hoc networks, using a general framework that allows their unified treatment. The results hold with probability going to 1 as the number of nodes in the network approaches infinity, and under a general model for channel fading.We first study asymmetric networks that consist of n source nodes and around nd destination nodes, communicating over a wireless channel. Each source node creates data traffic that is directed to a destination node chosen at random. When ½ ‹ d ‹ 1, an aggregate throughput that increases with n as n½ is achievable. If, however, 0 ‹ d ‹ ½, bottlenecks are formed and the aggregate throughput can not increase faster than nd.We also consider cluster networks, that consist of n client nodes and around nd cluster heads, communicating over a wireless channel. Each of the clients wants to communicate with one of the cluster heads, but the particular choice of cluster head is not important. In this setting, the maximum aggregate throughput is on the order of nd, and it can be achieved with no transmissions taking place between client nodes.We conclude with the study of hybrid networks. These consist of n wireless nodes and around nd access points. The access points are equipped with wireless transceivers, but are also connected with each other through an independent network of infinite capacity. Their only task is to support the operation of the wireless nodes. When ½ ‹ d ‹ 1, an aggregate throughput on the order of nd is achievable, through the use of the infrastructure. If, however, 0 ‹ d ‹ ½, using the infrastructure offers no significant gain, and the wireless nodes can achieve an aggregate throughput on the order of n½ by using the wireless medium only.

We introduce a methodology for studying wireless ad hoc networks in a multihop traffic environment. Our approach is to use theoretical upper bounds on network performance for evaluating the effects of various design choices: we focus on power control, the queuing discipline, the choice of routing and media access protocols, and their interactions. Using this framework, we then concentrate on the problem of medium access for wireless multihop networks. We first study CSMA/CA, and find that its performance strongly depends on the choice of the accompanying routing protocol. We then introduce two protocols that outperform CSMA/CA, both in terms of energy efficiency and achievable throughput. The progressive back off algorithm (PBOA) performs medium access jointly with power control. The progressive rump up algorithm (PRUA) sacrifices energy efficiency in favor of higher throughput. Both protocols slot time, and are integrated with queuing disciplines that are more relaxed than the first in first out (FIFO) rule. They are totally distributed and the overhead they require does not increase with the size and node density of the network.

We define and study capacity regions for wireless ad hoc networks with an arbitrary number of nodes and topology. These regions describe the set of achievable rate combinations between all source-destination pairs in the network under various transmission strategies, such as variable-rate transmission, single-hop or multihop routing, power control, and successive interference cancellation (SIC). Multihop cellular networks and networks with energy constraints are studied as special cases. With slight modifications, the developed formulation can handle node mobility and time-varying flat-fading channels. Numerical results indicate that multihop routing, the ability for concurrent transmissions, and SIC significantly increase the capacity of ad hoc and multihop cellular networks. On the other hand, gains from power control are significant only when variable-rate transmission is not used. Also, time-varying flat-fading and node mobility actually improve the capacity. Finally, multihop routing greatly improves the performance of energy-constraint networks.

We define and study capacity regions for ad hoc wireless networks with an arbitrary number of nodes and topology. These regions describe the set of achievable rate combinations between all source-destination pairs in the network under various transmission strategies, such as variable rate transmission, single hop or multihop routing, power control, and successive interference cancellation. With slight modifications, the developed formulation can handle multihop cellular networks, time-varying flat-fading channels and node mobility. Numerical results indicate that multihop routing, spatial reuse, and successive interference cancellation significantly increase the capacity of the network. On the other hand, gains by power control are not significant when the transmission rate is adapted to the channel SINR. We also find that time-varying flat fading and node mobility improve the performance of the network. Similar trends are observed for the special case of multihop cellular networks.