Community wireless networks (CWNs) have been proposed to spread broadband network access to underprivileged, underprovisioned, and remote areas. Research has focused on optimizing network performance through intelligent routing and scheduling, borrowing solutions from mesh networks. Surprisingly, however, there has been no work on how to make efficient use of multiple channels in CWNs in the presence of multiple gateways and a single radio per device. In fact, today's deployments in underprivileged areas are primarily single-radio and do operate on a single channel. Frequency selection in such CWNs is very complex because it does not only determine the nodes' channel of operation, but also the gateway and the routing tree to the gateway-a rather computationally intensive task. In this paper, we propose, design, implement, and evaluate SWARM, a practical system that allows a CWN to make effective use of the available wireless channels in order to offer globally optimal performance. SWARM improves performance versus current single-channel protocols by up to 7.7 × in our experiments. Moreover, while we should be expecting performance gains due to channel diversity, we clearly demonstrate that up to 3.7 × improvement is attributed to the network organization into efficient traffic distribution structures.

Community wireless networks (CWNs) have been proposed to spread broadband network access to underprivileged, under-provisioned and remote areas. Research has focused on optimizing network performance through intelligent routing and scheduling, borrowing solutions from mesh networks. Surprisingly, however, there has been no work on how to make efficient use of multiple channels in CWNs in the presence of multiple gateways, and a single radio per device. In fact, today's deployments in under-privileged areas are primarily single radio and do operate on a single channel [20]. Frequency selection in such CWNs is very complex because it does not only determine the nodes' channel of operation but also the gateway and the routing tree to the gateway - a rather computationally intensive task. In this paper, we propose, design, implement, and evaluate SWARM, a practical system that allows a CWN to make effective use of the available wireless channels in order to offer globally optimal performance. SWARM improves performance versus current single channel protocols by up to 7.7× in our experiments. Moreover, while we should be expecting performance gains due to channel diversity, we clearly demonstrate that up to 3.7 x improvement is attributed to the network organization into efficient traffic distribution structures.

Several multicast protocols for mobile ad hoc networks have been proposed, which build multicast trees by using location information that is available from the Global Positioning System (GPS) or localization algorithms and use geographic forwarding to forward packets down the multicast trees. These stateless multicast protocols carry encoded membership, location, and tree information in each packet and are more efficient and robust than stateful protocols (for example, ADMR and ODMRP), as they avoid the difficulty of maintaining distributed state in the presence of frequent topology changes. However, current stateless multicast protocols are not scalable to large groups because of the per-packet encoding overhead, and the centralized group membership and location management. We present the hierarchical rendezvous point multicast (HRPM) protocol, which significantly improves the scalability of stateless multicast with respect to the group size. HRPM consists of two key design ideas: 1) hierarchical decomposition of a large group into a hierarchy of recursively organized manageable-sized subgroups and 2) the use of distributed geographic hashing to construct and maintain such a hierarchy at virtually no cost. Our detailed simulations demonstrates that HRPM achieves significantly enhanced scalability and performance due to hierarchical organization and distributed hashing.

Community wireless mesh networks (WMNs) are increasingly being deployed for providing cheap, low maintenance Internet access. For the successful adoption of WMNs as a last-mile technology, we argue that a guarantee of per-client fairness is critical. Specifically, WMNs should support a bitrate-for-bucks service model similar to other popular access technologies such as Cable/DSL.We analyze the effectiveness of both off-the-shelf and theoretically optimal approaches towards providing such a service. We propose the APOLLO system that outperforms both these approaches.APOLLO seamlessly integrates three synergistic components: theory-guided service planning and subscription, rate-based admission control to enforce the planned service, and a novel distributed light-weight fair scheduling scheme to deliver the admitted traffic. We evaluate APOLLO using simulations and testbed experiments.

Community wireless networks have been proposed as a powerful technique to spread broadband network access to underprivileged, under-provisioned and remote areas. These networks consist of a few Internet gateways which are reached by homes using multi-hop wireless links between wireless routers. The benefits of such networks include low costs for deployment due to reduced wiring needs, low maintenance and increased flexibility. Current practice in routing protocols for such networks (e.g. LQSR, OLSR and SrcRR) is for routing protocols to obtain information about the link quality (via some metric such as ETT, ETX) and select a gateway to whom a route minimizes the cost of the metric. All nodes operate on the same known frequency to maintain connectivity.

Multi-hop wireless mesh networks are increasingly being deployed for last-mile Internet access. Typically, network algorithms such as routing, channel assignment and topology control for such networks rely heavily on metrics that intend to capture link "quality" across the network. However, the underlying dynamics of the proposed link metrics themselves have not yet been studied in detail. In this paper, we study the dynamics of the most popular link metrics in real network deployments. Using two wireless mesh testbeds, we measure a number of link metrics across different hardware platforms and network environments. The collected measurements allow us to study the stability and sensitivity of the different metrics to various conditions. Our study provides several insights and future research directions on how network algorithms need to adapt to link dynamics as well as how popular and widely used link metrics can be improved.

Routing protocols have traditionally been based on finding shortest paths under certain cost metrics. A conventional routing metric models the cost of a path as the sum of the costs on the constituting links. This paper introduces the concept of a Markovian metric, which models the cost of a path as the cost of the first hop plus the cost of the second hop conditioned on the first hop, and so on. The notion of the Markovian metric is fairly general. It is potentially applicable to scenarios where the cost of sending a packet (or a stream of packets) over a link may depend on the previous hop of the packet (or the stream). Such scenario arises, for instance, in a wireless mesh network equipped with local mixing, a recent link layer advance. This scenario is examined as a case study for the Markovian metric. The local mixing engine sits between the routing and MAC layers. It maintains information about the packets each neighbor has, and identifies opportunities to mix the outgoing packets via network coding to reduce the transmissions in the air. We use a Markovian metric to model the reduction of channel resource consumption due to local mixing. This leads to routing decisions that can better take advantage of local mixing. We have implemented a system that incorporates local mixing and source routing using a Markovian metric in Qualnet. The experimental results demonstrate significant throughput gain and resource saving.

The stationary nature of nodes in a mesh network has shifted the main design goal of routing protocols from maintaining connectivity between source and destination nodes to finding high-throughput paths between them. In recent years, numerous link-quality-based routing metrics have been proposed for choosing high-throughput paths for unicast protocols. In this paper we study routing metrics for high-throughput tree or mesh construction in multicast protocols. We show that there is a fundamental difference between unicast and multicast routing in how data packets are transmitted at the link layer, and accordingly there is a difference in how the routing metrics for each of these primitives are designed. We adapt certain routing metrics for unicast for high-throughput multicast routing and propose news ones not previously used for high-throughput. We then study the performance improvement achieved by using different link-quality-based routing metrics via extensive simulation and experiments on a mesh network testbed, using ODMRP as a representative multicast protocol. Our testbed experiment results show that ODMRP enhanced with linkquality routing metrics can achieve up to 17.5% throughput improvement as compared to the original ODMRP.

Wireless mesh networks (WMNs) have been proposed as an effective solution for ubiquitous last-mile broadband access. Three key factors that affect the usability of WMNs are high throughput, cost-effectiveness, and ease of deployability. In this paper, we propose DMesh, a WMN architecture that combines spatial separation from directional antennas with frequency separation from orthogonal channels to improve the throughput of WMNs. DMesh achieves this improvement without inhibiting cost-effectiveness and ease of deployability by utilizing practical directional antennas that are widely and cheaply available (e.g., patch and yagi) in contrast to costly and bulky smart beamforming directional antennas. Thus, the key challenge in DMesh is to exploit spatial separation from such practical directional antennas despite their lack of electronic steerability and interference nulling, as well as the presence of significant sidelobes and backlobes. In this paper, we study how such practical directional antennas can improve the throughput of a WMN. Central to our architecture is a distributed, directional channel assignment algorithm for mesh routers that effectively exploits the spatial and frequency separation opportunities in a DMesh network. Simulation results show that DMesh improves the throughput of WMNs by up to 231% and reduces packet delay drastically compared to a multiradio multichannel omni antenna network. A DMesh implementation in our 16-node 802.11b WMN testbed using commercially available practical directional antennas provides transmission control protocol throughput gains ranging from 31% to 57%

The use of wireless in local loop (WiLL) has generated considerable interest due to the advantages it offers such as ease and low cost of deployment and maintenance. With an increase in the number of subscribers in the network, it becomes expedient to employ spectrum reusability techniques such as the use of multihop relaying in order to improve the capacity of the wireless systems. Throughput enhanced wireless in local loop (TWiLL) is one such architecture that employs multihop relaying and shortcut relaying to reuse bandwidth in WiLL systems. Compared to other multihop wireless network architectures, TWiLL architecture assumes significance due to its potential use in fixed wireless broadband services such as LMDS (local multipoint distribution service) and MMDS (multichannel multipoint distribution system). Analysis of the call acceptance ratio (CAR) in multihop wireless architectures including TWiLL is nontrivial as the Erlang B formula no longer holds. In this paper, we build multidimensional Markov chains to analyze the performance of multihop wireless systems such as TWiLL that has multiple types of channels. We also compare the results of our analysis with results from simulations. We observe that multihop relaying and shortcut relaying lead to a significant increase in the CAR of WiLL systems. Also, the free space propagation model that is normally used to model the radio channel is a very unrealistic model and does not consider reflection, diffraction, scattering, and multipath propagation that hinder transmissions in WiLL systems. In this paper, we studied the effect of several realistic radio channel propagation models on the performance of the TWiLL system through analysis and simulations

In this paper, we study the problem of providing fairness in multi-hop wireless infrastructure access. In such networks, it is well known that the use of current media access and transport protocols can result in severe unfairness and even starvation for flows originated from different numbers of hops away from a wired infrastructure point or gateway. In this paper, we study a different type of fairness that exists in such networks - flows initiated by nodes that are similar numbers of hops away from the gateway can experience significant unfairness, and such unfairness exists even for perfectly symmetrical node distribution and channel conditions. We denote such fairness as symmetrical fairness. We first provide a framework to characterize and measure symmetrical fairness. We then perform an extensive set of simulation experiments to quantify the causes of symmetrical unfairness. Finally, we develop and study a distributed routing algorithm that significantly improves the symmetrical fairness

Mobile robot teams have many useful applications such as search and rescue, exploration and hazard detection and analysis. Communication between the robots of a team as well as between the robots and a human operator or controller are useful for many applications. Many applications of mobile robots involve scenarios in which no communication infrastructure such as base stations exist (e.g. demining in battlefields) or the existing infrastructure is damaged (e.g. search and rescue after an earthquake). In such scenarios, it is necessary for mobile robots to form an ad hoc network to enable communication by forwarding each other’s packets. In many applications, group communication can be used for flexible control, organization, and management of the mobile robots. Multicast provides a bandwidth efficient communication method between a source and a group of robots. In this paper, we propose an efficient multicast protocol MRMM (Mobile Robot Mesh Multicast) for deployment in mobile robot networks. MRMM exploits the fact that mobile robots know what velocity they are instructed to move at and for what distance in building a long lifetime sparse mesh for group communication that is more efficient. Our results show that MRMM provides an efficient group communication mechanism that can potentially be used in many mobile robot application scenarios.

Mobile multi-robot teams are useful in many critical applications such as search and rescue. Explicit communication among robots in such mobile multi-robot teams is useful for the coordination of such teams as well as exchanging data. Since many applications for mobile robots involve scenarios in which communication infrastructure may be damaged or unavailable, mobile robot teams frequently need to communicate with each other by using ad hoc networking. In such scenarios, energy efficient routing protocols to deliver messages among robots are a key requirement. In this paper, we propose and evaluate two routing protocols tailored for use in ad hoc networks formed by mobile multi-robot teams: Mobile Robot Distance Vector (MRDV) and Mobile Robot Source Routing (MRSR). Both protocols exploit the unique mobility characteristics of mobile robot networks to perform efficient routing. Our simulation study show that both MRDV and MRSR incur lower overhead while operating in mobile robot networks when compared to traditional mobile ad hoc network routing protocols such as DSR and AODV.

Geographic routing protocols allow stateless routing in mobile ad hoc networks (MANETs) by taking advantage of the location information of mobile nodes and thus are highly scalable. A central challenge in geographic routing protocols is the design of scalable distributed location services that track mobile node locations. A number of location services have been proposed, but little is known about the relative performance of these location services. In this paper, we perform a detailed performance comparison of three rendezvous-based location services that cover a range of design choices: a quorum-based protocol (XYLS) which disseminates each node's location to O(/spl radic/N) nodes, a hierarchical protocol (GLS) which disseminates each node's location to O(logN) nodes, and a geographic hashing based protocol (GHLS) which disseminates each node's location to O(1) nodes. We present a quantitative model of protocol overheads for predicting the performance tradeoffs of the protocols for static networks. We then analyze the performance impact of mobility on these location services. Finally, we compare the performance of routing protocols equipped with the three location services with two topology-based routing protocols, AODV and DSR, for a wide range of network sizes. Our study demonstrates that when practical MANET sizes are considered, robustness to mobility and the constant factors matter more than the asymptotic costs of location service protocols. In particular, while GLS scales better asymptotically, GHLS is far simpler, transmits fewer control packets, and delivers more data packets than GLS when used with geographic routing in MANETs of sizes considered practical today and in the near future. Similarly, although XYLS scales worse asymptotically than GLS, it transmits fewer control packets and delivers more data packets than GLS in large mobile networks.

We study the problem of supporting communication in mobile sensor networks formed by teams of mobile robots equipped with sensors. We assume that in addition to communicating with each other by implicit or environmental means, the robots are equipped with wireless communication capability and effectively form a mobile ad hoc network (MANET). However, unlike typical MANETs where the primary communication pattern is any-to-any, such mobile multi-robot sensing networks need to support sensing applications which exhibit a many-to-one communication pattern. We evaluate the ability of current ad hoc network routing protocols to support communication in such sensing networks using detailed simulations of 50 robots. We consider typical communication patterns that arise in sensing applications and their impact on success rates, routing overhead, and energy costs of the mobile sensor network.

In this paper, we examine the communication model widely used in simulation studies of mobile ad hoc networks (MANETs). We find that the communication model uses an overly simplistic traffic pattern which restricts the number of connections that originate from each source node to be one or two, and thus the communication model may not represent traffic patterns in many potential applications in MANETs. We then propose a new communication model which extends the previous communication model to include a more general traffic pattern that varies the number of connections per source node. We study the performance impact of traffic patterns on various routing protocols via detailed simulations of a MANET of 112 mobile nodes. Our simulation results show that many of the conclusions drawn in previous protocol comparison studies no longer hold under the new communication model. These results motivate the need for performance evaluation of MANETs to not only include rich and diverse mobility models as has been done in the past but also include diverse traffic patterns that stress a wide set of protocol design issues.