Neighborhood tracking for mobile ad hoc networks

In mobile ad hoc networks (MANETs), node mobility causes network topologies to change dynamically over time, which complicates such important tasks as broadcasting and routing. In a typical efficient localized approach, each node makes forwarding decisions based on a neighborhood local view constructed simply by collecting received “Hello” messages. That kind of neighborhood local view can become outdated and inconsistent, which induces a low-coverage problem for efficient broadcasting tasks and a low-delivery ratio problem for efficient routing tasks. In this paper, we propose a neighborhood tracking scheme to guarantee the accuracy of forwarding decisions. Based on historical location information, nodes predict the positions of neighbors when making a forwarding decision, and then construct an updated and consistent neighborhood local view to help derive more precise forwarding decisions. The inaccuracy factors of our scheme are also discussed and an accessory method is provided for possible usage. Simulation results illustrate the accuracy of our proposed tracking scheme. To verify the effectiveness of our scheme, we apply it to existing efficient broadcast algorithms. Simulation results indicate that our neighborhood tracking scheme can improve the protocols coverage ratio greatly.     

An efficient packet sensing MAC protocol for wireless networks

The Group Allocation Multiple Access with Packet-Sensing (GAMA-PS) protocol for scheduling real-time and datagram traffic in a wireless LAN is specified and analyzed. By maintaining a dynamically-sized cycle that changes in length depending on the amount of network traffic, GAMA-PS is able to efficiently control channel access while ensuring that there are no collisions of data packets. Each cycle contains a contention period and a group-transmission period; a station with data to send competes for membership in the “transmission group” by using packet sensing to successfully complete an RTS/CTS message exchange during the contention period. Once a station is a member of the transmission group, it is able to transmit a collision-free data packet during each cycle; as long as a station has data to send, it maintains its position in the group. This revised version was published online in June 2006 with corrections to the Cover Date.     

Embracing interference in ad hoc networks using joint routing and scheduling with multiple packet reception

We present an approach that takes advantage of multi-packet reception (MPR) to reduce the negative effects of multiple access interference and therefore increase the capacity of an ad hoc network. We analyze the performance upper bound of joint routing and scheduling for ad hoc networks that embrace interference by using MPR. We formulate the optimization problem under a deterministic model and seek to maximize the aggregate network throughput subject to minimum rate requirements. We then propose a polynomial-time heuristic algorithm aimed at approximating the optimal solution to the joint routing and channel access problem under MPR. We show the effectiveness of our heuristic algorithm by comparing its performance with the upper bound.     

A routing architecture for mobile integrated services networks

A drawback of the conventional Internet routing architecture is that its route computation and packet forwarding mechanisms are poorly integrated with congestion control mechanisms. Any datagram offered to the network is accepted; routers forward packets on a best-effort basis and react to congestion only after the network resources have already been wasted. A number of proposals improve on this to support multimedia applications; a promising example is the Integrated Services Packet Network (ISPN) architecture. However, these proposals are oriented to networks with fairly static topologies and rely on the same conventional Internet routing protocols to operate. This paper presents a routing architecture for mobile integrated services networks in which network nodes (routers) can move constantly while providing end-to-end performance guarantees. In the proposed connectionless routing architecture, packets are individually routed towards their destinations on a hop by hop basis. A packet intended for a given destination is allowed to enter the network if and only if there is at least one path of routers with enough resources to ensure its delivery within a finite time. Once a packet is accepted into the network, it is delivered to its destination, unless resource failures prevent it. Each router reserves resources for each active destination, rather than for each source–destination session, and forwards a received packet along one of multiple loop-free paths towards the destination. The resources and available paths for each destination are updated to adapt to congestion and topology changes. This mechanism could be extended to aggregate dissimilar flows as well. This revised version was published online in June 2006 with corrections to the Cover Date.     

From link dynamics to path lifetime and packet-length optimization in MANETs

We present an analytical framework and statistical models to accurately characterize the lifetime of a wireless link and multi-hop paths in mobile ad hoc networks (MANET). We show that the lifetimes of links and paths can be computed through a two-state Markov model. We also show that the analytical solution follows closely the results obtained through discrete-event simulations for two mobility models, namely, random direction and random waypoint mobility models. We apply these models to study practical implications of link lifetime on routing protocols. First, we compute optimal packet lengths as a function of mobility, and show that significant throughput improvements can be attained by adapting packet lengths to the mobility of nodes in a MANET. Second, we show how the caching strategy of on-demand routing protocols can benefit from considering the link lifetimes in a MANET. Finally,we summarize all the analytical results into a comprehensive performance analysis on throughput, delay and storage.

Combining on-demand and opportunistic routing for intermittently connected networks

While current on-demand routing protocols are optimized to take into account unique features of mobile ad-hoc networks (MANETs) such as frequent topology changes and limited battery life, they often do not consider the possibility of intermittent connectivity that may lead to arbitrarily long-lived partitions. In this work, we introduce the space-content-adaptive-time routing (SCaTR) framework, which enables data delivery in the face of both temporary and long-lived MANET connectivity disruptions. SCaTR takes advantage of past connectivity information to effectively route traffic towards destinations when no direct route from the source exists. We show through simulations that, when compared to traditional on-demand protocols, as well as opportunistic routing (e.g., epidemic), SCaTR increases delivery ratio with lower signaling overhead in a variety of intermittently connected network scenarios. We also show that SCaTR performs as well as on-demand routing in well-connected networks and in scenarios with no mobility predictability (e.g., random mobility). In the latter case, SCaTR delivers comparable reliability to epidemic routing with considerably lower overhead.     

Optimal Unicast Capacity of Random Geometric Graphs: Impact of Multipacket Transmission and Reception

We establish a tight max-flow min-cut theorem for multi-commodity routing in random geometric graphs. We show that, as the number of nodes in the network n tends to infinity, the maximum concurrent flow (MCF) and the minimum cut-sparsity scale as θ(n²r³(n)/k), for a random choice of k = ω(n) source-destination pairs, where n and r(n) are the number of nodes and the communication range in the network respectively. The MCF equals the interference-free capacity of an ad-hoc network. We exploit this fact to develop novel graph theoretic techniques that can be used to deduce tight order bounds on the capacity of ad-hoc networks. We generalize all existing capacity results reported to date by showing that the per-commodity capacity of the network scales as θ(1/r(n)k) for the single-packet reception model suggested by Gupta and Kumar, and as θ(nr(n)/k) for the multiple-packet reception model suggested by others. More importantly, we show that, if the nodes in the network are capable of (perfect) multiple-packet transmission (MPT) and reception (MPR), then it is feasible to achieve the optimal scaling of θ(n²r³(n)/k), despite the presence of interference. In comparison to the Gupta-Kumar model, the realization of MPT and MPR may require the deployment of a large number of antennas at each node or bandwidth expansion. Nevertheless, in stark contrast to the existing literature, our analysis presents the possibility of actually increasing the capacity of ad-hoc networks with n even while the communication range tends to zero!     

Receiver-Oriented Multiple Access in Ad Hoc Networks with Directional Antennas

Directional antennas can adaptively select radio signals of interest in specific directions, while filtering out unwanted interference from other directions. A couple of medium access protocols based on random access schemes have been proposed for networks with directional antennas, using the omnidirectional mode for the transmission or reception of control packets in order to establish directional links. We propose a distributed receiver-oriented multiple access (ROMA) scheduling protocol, capable of utilizing multi-beam forming directional antennas in ad hoc networks. Unlike random access schemes that use on-demand handshakes or signal scanning to resolve communication targets, ROMA computes a link activation schedule in each time slot using two-hop topology information. It is shown that significant improvements on network throughput and delay can be achieved by exploiting the multi-beam forming capability of directional antennas in both transmission and reception. The performance of ROMA is studied by simulation, and compared with a well-know static scheduling scheme that is based on global topology information.     

Efficient Group Coordination in Multicast Trees

The majority of today's Internet applications relies on point-to-point communication. In recent years, however, multipoint communication support has become the foundation for such applications as multiparty video conferencing, distributed interactive simulations, and collaborative systems. We describe a novel protocol to coordinate multipoint groupwork within the IP-multicast framework. The protocol supports Internet-wide coordination for large and highly-interactive groupwork, relying on the dissemination of coordination directives among group members across a shared end-to-end multicast tree. We also describe how addressing extensions to IP multicast can be used for our multisite coordination mechanism.