Modeling human mobility in obstacle-constrained ad hoc networks

In this paper we present a mobility model for ad hoc networks consisting of human-operated nodes that are deployed in obstacle-constrained environments. According to this model, the network nodes move around the obstacles in a way that resembles how humans bypass physical obstructions. A recursive procedure is executed by each node at its current position to determine the next intermediate destination point until the final destination point is reached. The proposed mobility model is validated using real-life trace data and studied using both mathematical analysis and simulations. Furthermore, the model is extended to incorporate several operational aspects of ad hoc networks in mission critical scenarios, where it is best applicable. These extensions include hierarchical node organization, distinct modes of node activity, event-based destination selection and impact of the physical obstacles on signal propagation. The model is implemented as an add-on module in Network Simulator (ns-2).     

Topology and mobility considerations in mobile ad hoc networks

A highly dynamic topology is a distinguishing feature and challenge of a mobile ad hoc network. Links between nodes are created and broken, as the nodes move within the network. This node mobility affects not only the source and/or destination, as in a conventional wireless network, but also intermediate nodes, due to the network’s multihop nature. The resulting routes can be extremely volatile, making successful ad hoc routing dependent on efficiently reacting to these topology changes.

In order to better understand this environment, a number of characteristics have been studied concerning the links and routes that make up an ad hoc network. Several network parameters are examined, including number of nodes, network dimensions, and radio transmission range, as well as mobility parameters for maximum speed and wait times. In addition to suggesting guidelines for the evaluation of ad hoc networks, the results reveal several properties that should be considered in the design and optimization of MANET protocols.     

Reactive routing for mobile cognitive radio ad hoc networks

Although more than a decade has passed from the proposal of the Cognitive Radio paradigm, in these years the research has mainly focused on physical and medium access issues, and few recent works focused on the problem of routing in cognitive networks. This paper addresses such a problem by evaluating the feasibility of reactive routing for mobile cognitive radio ad hoc networks. More specifically, we design a reactive routing protocol for the considered scenario able to achieve three goals: (i) to avoid interferences to primary users during both route formation and data forwarding; (ii) to perform a joint path and channel selection at each forwarder; (iii) to take advantage of the availability of multiple channels to improve the overall performance. Two different versions of the same protocol, referred to as Cognitive Ad-hoc On-demand Distance Vector (CAODV), are presented. The first version exploits inter-route spectrum diversity, while the second one exploits intra-route spectrum diversity. An exhaustive performance analysis of both the versions of the proposed protocol in different environments and network conditions has been carried out via numerical simulations. The results state the suitability of the proposed protocol for small mobile cognitive radio ad hoc networks.     

Mobility–capacity–delay trade-off in wireless ad hoc networks

We show that there is a trade-off among mobility, capacity, and delay in ad hoc networks. More specifically, we consider two schemes for node mobility in ad hoc networks. We divide the entire network by cells whose sizes can vary with the total number of nodes n, or whose size is independent of the number of nodes. We restrict the movement of nodes within these cells, calculate throughput and delay for randomly chosen pairs of source–destination nodes, and show that mobility is an entity that can be exchanged with capacity and delay. We also investigate the effect of directional antennas in a static network in which packet relaying is done through the closest neighbor and verify that this approach attains better throughput than static networks employing omnidirectional antennas.     

Localized broadcast incremental power protocol for wireless ad hoc networks

We investigate broadcasting and energy preservation in ad hoc networks. One of the best known algorithm, the Broadcast Incremental Power (BIP) protocol, constructs an efficient spanning tree rooted at a given node. It offers very good results in terms of energy savings, but its computation is centralized and it is a real problem in ad hoc networks. Distributed versions have been proposed, but they require a huge transmission overhead for information exchange. Other localized protocols have been proposed, but none of them has ever reached the performances of BIP. In this paper, we propose and analyze an incremental localized version of this protocol. In our method, the packet is sent from node to node based on local BIP trees computed by each node in the broadcasting chain. Local trees are constructed within the k-hop neighborhood of nodes, based on information provided by previous nodes, so that a global broadcasting structure is incrementally built as the message is being propagated through the network. Only the source node computes an initially empty tree to initiate the process. Discussion and results are provided where we argue that k = 2 is the best compromise for efficiency. We also discuss potential conflicts that can arise from the incremental process. We finally provide experimental results showing that this new protocol obtains very good results for low densities, and is almost as efficient as BIP for higher densities.     

A cross layer scheme for adaptive antenna array based wireless ad hoc networks in multipath environments

A medium access control (MAC) protocol (NULLHOC) for ad hoc networks of nodes with antenna arrays is presented. The antenna array is used for transmit and receive beamforming with the purpose of increasing spatial reuse by directing nulls at active transmitters and receivers in the neighborhood. In contrast to previous work with directional antennas, our approach is applicable to multipath channels, such as occur indoors or in other rich scattering environments. The MAC protocol is designed to support the control information exchange needed to direct nulls toward other users involved in existing communication sessions. Knowledge of the channel coefficients between a transmitter or receiver and its neighbors is used to design transmit or receive beamformer weights that implement the requisite nulling. Simulations are used to demonstrate the improvements in throughput and transmit powers that are obtained in this approach relative to the IEEE 802.11 MAC protocol. We also analyze the effects of channel estimation errors on our protocol and propose a simple modification of the basic (NULLHOC) protocol to minimize their impact. This work was supported in part by National Science Foundation grants ECS-9979408 and ANI-9980526. Any opinions, findings and conclusions or recommendations expressed in this publication are those of the author(s) and do not necessarily reflect the views of the funding agencies.     

Onto scalable wireless ad hoc networks: Adaptive and location-aware clustering

Clustering is a widely used solution to provide routing scalability in wireless ad hoc networks. In the literature, clustering schemes feature different characteristics and purposes, however few schemes are context-aware. This work proposes a new solution called Distributed and Location-aware Clustering (DiLoC), a clustering scheme designed to operate in indoor environments, providing mechanisms to gather context location information in order to ease the maintenance of clusters, thus resulting in a stabler network topology in order to provide a scalable network topology for an efficient routing. DiLoC considers three distinct approaches, regarding the characteristics of the deployment environment, aiming to cover infrastructure-less, infrastructure and hybrid network scenarios. DiLoC was evaluated and compared with a similar clustering scheme, featuring the stability, amount of clustered nodes and network load. Included results demonstrate a scalable algorithm with a significant high stability.     

Quality of service support in IEEE 802.11 wireless ad hoc networks

Supporting Quality of Service (QoS) in wireless networks is a challenging problem. The IEEE 802.11 LAN standard was developed primarily for elastic data applications. In order to support the transmission of real-time data, a polling-based scheme called the point coordination function (PCF) was introduced in IEEE 802.11. However, PCF was not able to meet the desired and practical service differentiation requirements to fulfill the need of real-time data. Therefore, Task Group E of the IEEE 802.11 working group released several IEEE 802.11e drafts, whose main task is to support QoS in IEEE 802.11 LANs. The polling scheme of PCF is extended in IEEE 802.11e into the more complex hybrid coordination function (HCF). We found that HCF has several performance issues that may affect its anticipated performance. In this paper, we address these issues and propose a QoS enhancement over PCF, called enhanced PCF (EPCF) that enables Wireless LAN to send a combination of voice, data and isochronous data packets using the current IEEE 802.11 PCF. First, we compare the performance of the proposed model (EPCF) with the HCF function of the IEEE 802.11e through simulation. Second, we extend the proposed model (EPCF) to work in a multihop wireless ad hoc mode and present the advantages and limitations in this case. Simulation results demonstrate an enhanced performance of our scheme over the legacy PCF and a comparable performance to the IEEE 802.11e HCF in terms of the average delay and system throughput. However, EPCF is much simpler than HCF, provides flow differentiation, and is easy to implement in the current IEEE 802.11 standard.     

Smart antenna based broadcasting in wireless ad hoc networks

Smart antennas have the advantage over traditional omnidirectional antennas of being able to orientate radio signals into the concerned directions in either transmission mode or in reception mode. Since the omnidirectional antenna use in broadcasting over the whole network is the source of an excessive redundancy of broadcast packet receptions within each node, we suggest using smart antennas to improve the medium usage in the case of broadcasting. We propose to adapt a current broadcast protocol to smart antenna applications and present two smart antenna broadcast approaches. We also present a comparative performance study between omnidirectional and smart antennas when broadcasting. We show that we can improve battery power utilisation and bandwidth usage with smart antennas.     

PPMA, a probabilistic predictive multicast algorithm for ad hoc networks

Ad hoc networks are collections of mobile nodes communicating using wireless media without any fixed infrastructure. Existing multicast protocols fall short in a harsh ad hoc mobile environment, since node mobility causes conventional multicast trees to rapidly become outdated. The amount of bandwidth resource required for building up a multicast tree is less than that required for other delivery structures, since a tree avoids unnecessary duplication of data. However, a tree structure is more subject to disruption due to link/node failure and node mobility than more meshed structures. This paper explores these contrasting issues and proposes PPMA, a Probabilistic Predictive Multicast Algorithm for ad hoc networks, that leverages the tree delivery structure for multicasting, solving its drawbacks in terms of lack of robustness and reliability in highly mobile environments. PPMA overcomes the existing trade-off between the bandwidth efficiency to set up a multicast tree, and the tree robustness to node energy consumption and mobility, by decoupling tree efficiency from mobility robustness. By exploiting the non-deterministic nature of ad hoc networks, the proposed algorithm takes into account the estimated network state evolution in terms of node residual energy, link availability and node mobility forecast, in order to maximize the multicast tree lifetime, and consequently reduce the number of costly tree reconfigurations. The algorithm statistically tracks the relative movements among nodes to capture the dynamics in the ad hoc network. This way, PPMA estimates the node future relative positions in order to calculate a long-lasting multicast tree. To do so, it exploits the most stable links in the network, while minimizing the total network energy consumption. We propose PPMA in both its centralized and distributed version, providing performance evaluation through extensive simulation experiments.     

An ad hoc networking scheme in hybrid networks for emergency communications

This paper describes an ad hoc networking scheme and routing protocol for emergency communications. The objective of the network is to collect damage assessment information quickly and stably in a disaster. The network is configured with a hybrid wireless network, combining ad hoc networks and a cellular network to maintain connectivity between a base station (BS) and nodes even in a disaster. In the event that a direct link between the BS and a node is disconnected due to damage or obstacles, the node switches to the ad hoc mode, and accesses the BS via neighboring nodes by multihopping. The routing protocol proposed in this paper discovers and builds a route by way of monitoring neighbors’ communications instead of broadcasting a route request packet. The network employs a dedicated medium access control protocol based on TDM (Time Division Multiplexing) for multihopping in ad hoc networks to maintain accessibility and to perform a short delay. Experiments showed that approximately 90% of nodes are capable of reaching the BS within a few hops, even in conditions where only 20% of nodes maintain direct connections to the BS. In addition, the results showed that it is feasible for the network to operate in a short delay for delivering a packet to the BS. However, throughput is not retrieved sufficiently due to the restriction of the access protocol, whereas reachability does improve sufficiently. Therefore, the network is suitable for collecting damage assessment information and transmitting urgent traffic quickly and stably, while the data is restricted to a small amount.     

A column generation method for spatial TDMA scheduling in ad hoc networks

An ad hoc network can be set up by a number of units without the need of any permanent infrastructure. Two units establish a communication link if the channel quality is sufficiently high. As not all pairs of units can establish direct links, traffic between two units may have to be relayed through other units. This is known as the multi-hop functionality. In military command and control systems, ad hoc networks are also referred to as multi-hop radio networks.

Spatial TDMA (STDMA) is a scheme for access control in ad hoc networks. STDMA improves TDMA by allowing simultaneous transmission of multiple units. In this paper, we study the optimization problem of STDMA scheduling, where the objective is to find minimum-length schedules. Previous work for this problem has focused on heuristics, whose performance is difficult to analyze when optimal solutions are not known. We develop novel mathematical programming formulations for this problem, and present a column generation solution method. Our numerical experiments show that the method generates a very tight bound to the optimal schedule length, and thereby enables optimal or near-optimal solutions. The column generation method can be used to provide benchmarks when evaluating STDMA scheduling algorithms. In particular, we use the bound obtained in the column generation method to evaluate a simple greedy algorithm that is suitable for distributed implementations.     

Power proximity based key management for secure multicast in ad hoc networks

As group-oriented services become the focal point of ad hoc network applications, securing the group communications becomes a default requirement. In this paper, we address the problem of group access in secure multicast communications for wireless ad hoc networks. We argue that energy expenditure is a scarce resource for the energy-limited ad hoc network devices and introduce a cross-layer approach for designing energy-efficient, balanced key distribution trees to perform key management. To conserve energy, we incorporate the network topology (node location), the “power proximity” between network nodes and the path loss characteristics of the medium in the key distribution tree design. We develop new algorithms for homogeneous as well as heterogeneous environments and derive their computational complexity. We present simulation studies showing the improvements achieved for three different but common environments of interest, thus illustrating the need for cross-layer design approaches for security in wireless networks. Loukas Lazos received the B.S. and M.S. degrees from the Electrical Engineering Department, National Technical University of Athens, Athens, Greece, in 2000 and 2002, respectively. He is currently working towards the Ph.D. degree in the Electrical Engineering Department, University of Washington, Seattle. His current research interests focus on cross-layer designs for energy-efficient key management protocols for wireless ad-hoc networks, as well as secure localization systems for sensor networks. Radha Poovendran received the Ph.D. degree in electrical engineering from the University of Maryland, College Park, in 1999. He has been an Assistant Professor in the Electrical Engineering Department, University of Washington, Seattle, since September 2000. His research interests are in the areas of applied cryptography for multiuser environment, wireless networking, and applications of information theory to security. Dr. Poovendran is a recipient of the Faculty Early Career Award from the National Science Foundation (2001), Young Investigator Award from the Army Research Office (2002), Young Investigator Award from the Office of Naval Research (2004), and the 2005 Presidential Early Career Award for Scientists and Engineers, for his research contributions in the areas of wired and wireless multiuser security.     

On-demand power management for ad hoc networks

Battery power is an important resource in ad hoc networks. It has been observed that in ad hoc networks, energy consumption does not reflect the communication activities in the network. Many existing energy conservation protocols based on electing a routing backbone for global connectivity are oblivious to traffic characteristics. In this paper, we propose an extensible on-demand power management framework for ad hoc networks that adapts to traffic load. Nodes maintain soft-state timers that determine power management transitions. By monitoring routing control messages and data transmission, these timers are set and refreshed on-demand. Nodes that are not involved in data delivery may go to sleep as supported by the MAC protocol. This soft state is aggregated across multiple flows and its maintenance requires no additional out-of-band messages. We implement a prototype of our framework in the ns-2 simulator that uses the IEEE 802.11 MAC protocol. Simulation studies using our scheme with the Dynamic Source Routing protocol show a reduction in energy consumption near 50% when compared to a network without power management under both long-lived CBR traffic and on–off traffic loads, with comparable throughput and latency. Preliminary results also show that it outperforms existing routing backbone election approaches.     

A cross-layer framework for multiobjective performance evaluation of wireless ad hoc networks

In this paper we address the problem of finding the optimal performance region of a wireless ad hoc network when multiple performance metrics are considered. Our contribution is to propose a novel cross-layer framework for deriving the Pareto optimal performance bounds for the network. These Pareto bounds provide key information for understanding the network behavior and the performance trade-offs when multiple criteria are relevant. Our approach is to take a holistic view of the network that captures the cross-interactions among interference management techniques implemented at various layers of the protocol stack (e.g. routing and resource allocation) and determines the objective functions for the multiple criteria to be optimized. The resulting complex multiobjective optimization problem is then solved by multiobjective search techniques. The Pareto optimal sets for an example sensor network are presented and analyzed when delay, reliability and energy objectives are considered.     

Bypass routing: An on-demand local recovery protocol for ad hoc networks

On-demand routing protocols for ad hoc networks reduce the cost of routing in high mobility environments. However, route discovery in on-demand routing is typically performed via network-wide flooding, which consumes a substantial amount of bandwidth. In this paper, we present bypass routing, a local recovery protocol that aims to reduce the frequency of route request floods triggered by broken routes. Specifically, when a broken link is detected, a node patches the affected route using local information, which is acquired on-demand, and thereby bypasses the broken link. We implemented SLR (Source Routing with Local Recovery) as a prototype of our approach. Simulation studies show that SLR achieves efficient and effective local recovery while maintaining acceptable overhead.     

A secure group key management scheme for hierarchical mobile ad hoc networks

In this paper, we present a secure group key management scheme for hierarchical mobile ad hoc networks. Our approach aims to improve both scalability and survivability of group key management for large-scale wireless ad hoc networks. To achieve our goal, we propose the following approaches: (1) a multi-level security model, which follows a modified Bell-La Padula security model that is suitable in a hierarchical mobile ad hoc networking environment, and (2) a decentralized group key management infrastructure to achieve such a multi-level security model. Our approaches reduce the key management overhead and improve resilience to any single point failure problem. In addition, we have developed a roaming protocol that is able to provide secure group communication involving group members from different groups without requiring new keys; an advantage of this protocol is that it is able to provide continuous group communication even when the group manager fails.     

A distributed laxity-based priority scheduling scheme for time-sensitive traffic in mobile ad hoc networks

Characteristics of Mobile Ad hoc Networks such as shared broadcast channel, bandwidth and battery power limitations, highly dynamic topology, and location dependent errors, make provisioning of quality of service (QoS) in such networks very difficult. The Medium Access Control (MAC) layer plays a very important role as far as QoS is concerned. The MAC layer is responsible for selecting the next packet to be transmitted and the timing of its transmission. We have proposed a new MAC layer protocol that includes a laxity-based priority scheduling scheme and an associated back-off scheme, for supporting time-sensitive traffic. In the proposed scheduling scheme, we select the next packet to be transmitted, based on its priority value which takes into consideration the uniform laxity budget of the packet, the current packet delivery ratio of the flow to which the packet belongs, and the packet delivery ratio desired by the user. The back-off mechanism devised by us grants a node access to the channel, based on the rank of its highest priority packet in comparison to other such packets queued at nodes in the neighborhood of the current node. We have studied the performance of our protocol that combines a packet scheduling scheme and a channel access scheme through simulation experiments, and the simulation results show that our protocol exhibits a significant improvement in packet delivery ratio under bounded end-to-end delay requirements, compared to the existing 802.11 DCF and the Distributed Priority Scheduling scheme proposed recently in [ACM Wireless Networks Journal 8 (5) (2002) 455–466; Proceedings of ACM MOBICOM '01, July 2001, pp. 200–209].     

分级ad hoc网络中的一种应用层故障诊断算法

针对应用层故障提出了一种故障诊断算法——“基于簇的比较诊断算法”，该算法在分级ad hoc网络中利用簇首对簇内节点的集中控制功能优化了诊断过程，实现了诊断期问网络拓扑变化时对移动节点的诊断。证明了算法的正确性，并分析了算法的性能。仿真结果表明，该算法突破了“基于比较的故障诊断”在诊断过程中网络拓扑不能发生变化的限制，大大减小了“基于比较的故障诊断算法”由于诊断消息的洪泛导致的大量的系统开销。     

Improving TCP performance in ad hoc networks using signal strength based link management

Mobility in ad hoc networks causes frequent link failures, which in turn causes packet losses. TCP attributes these packet losses to congestion. This incorrect inference results in frequent TCP re-transmission time-outs and therefore a degradation in TCP performance even at light loads. We propose mechanisms that are based on signal strength measurements to alleviate such packet losses due to mobility. Our key ideas are (a) if the signal strength measurements indicate that a link failure is most likely due to a neighbor moving out of range, in reaction, facilitate the use of temporary higher transmission power to keep the link alive and, (b) if the signal strength measurements indicate that a link is likely to fail, initiate a route re-discovery proactively before the link actually fails. We make changes at the MAC and the routing layers to predict link failures and estimate if a link failure is due to mobility. We also propose a simple mechanism at the MAC layer that can help alleviate false link failures, which occur due to congestion when the IEEE 802.11 MAC protocol is used. We compare the above proactive and reactive schemes and also demonstrate the benefits of using them together and along with our MAC layer extension. We show that, in high mobility, the goodput of a TCP session can be improved by as much as 75% at light loads (when there is only one TCP session in the network) when our methods are incorporated. When the network is heavily loaded (i.e., there are multiple TCP sessions in the network), the proposed schemes can improve the aggregate goodput of the TCP sessions by about 14–30%, on average.