Multi-hop Ad Hoc Wireless Communication
draft-baccelli-multi-hop-wireless-communication-06

Abstract

This document describes some characteristics of communication between nodes in a multi-hop ad hoc wireless network. These are not requirements in the sense usually understood as applying to formulation of a requirements document. Nevertheless, protocol engineers and system analysts involved with designing solutions for ad hoc networks must maintain awareness of these characteristics.

Status of this Memo

This Internet-Draft is submitted to IETF in full conformance with the provisions of BCP 78 and BCP 79.

Internet-Drafts are working documents of the Internet Engineering Task Force (IETF). Note that other groups may also distribute working documents as Internet-Drafts. The list of current Internet- Drafts is at http://datatracker.ietf.org/drafts/current/.

Internet-Drafts are draft documents valid for a maximum of six months and may be updated, replaced, or obsoleted by other documents at any time. It is inappropriate to use Internet-Drafts as reference material or to cite them other than as "work in progress."

Copyright Notice

Copyright (c) 2011 IETF Trust and the persons identified as the document authors. All rights reserved.

This document is subject to BCP 78 and the IETF Trust's Legal Provisions Relating to IETF Documents (http://trustee.ietf.org/license-info) in effect on the date of publication of this document. Please review these documents carefully, as they describe your rights and restrictions with respect to this document.

Table of Contents

• 1. Introduction
• 2. Multi-hop Ad Hoc Wireless Networks
• 3. Common Packet Transmission Characteristics in Multi-hop Ad Hoc Wireless Networks
• 3.1. Asymmetry, Time-Variation, and Non-Transitivity
• 3.2. Radio Range and Wireless Irregularities
• 4. Alternative Terminology
• 5. Security Considerations
• 6. IANA Considerations
• 7. References
• Appendix A. Acknowledgements
• Authors' Addresses

1. Introduction

The goal of this document is to describe some aspects of multi-hop ad hoc wireless communication. Experience gathered with [RFC3626] [RFC3561] [RFC3684] [RFC4728] [RFC5449] [RFC2501] [DoD01] shows that this type of communication presents specific challenges. This document briefly describes these challenges, which one should maintain awareness of, when designing Internet protocols for ad hoc networks.

2. Multi-hop Ad Hoc Wireless Networks

For the purposes of this document, a multi-hop ad hoc wireless network will be considered to be a collection of devices that each have a radio transceiver, that are using the same physical and medium access protocols, that are moreover configured to self-organize and provide store-and-forward functionality on top of these protocols as needed to enable communications. The devices providing network connectivity are considered to be routers. Other non-routing wireless devices, if present in the ad hoc network, are considered to be "end-hosts". The considerations in this document apply equally to routers or end-hosts; we use the term "node" to refer to any such network device in the ad hoc network.

An example of multi-hop ad hoc wireless network is a wireless community network such as Funkfeuer [FUNKFEUER] or Freifunk [FREIFUNK], that consists in routers running OLSR [RFC3626] on 802.11 in ad hoc mode with the same ESSID at link layer. Multi-hop ad hoc wireless networks may also run on link layers other than 802.11.

Note however that simple hosts communicating through an access point with 802.11 in infrastructure mode do not form a multi-hop ad hoc wireless network, since the central role of the access point is determined a priori, and since nodes other than the access point do not generally provide store-and-forward functionality.

3. Common Packet Transmission Characteristics in Multi-hop Ad Hoc Wireless Networks

Let A and B be two nodes in a multi-hop ad hoc wireless network N. Suppose that, when node A transmits a packet through its interface on network N, that packet is correctly received by node B without requiring storage and/or forwarding by any other device. We will then say that B "hears" packets from A. Note that therefore, when B can hear IP packets from A, the TTL of the IP packet heard by B will be precisely the same as it was when A transmitted that packet.

Let S be the set of nodes that can hear packets transmitted by node A through its interface on network N. The following section gathers common characteristics concerning packet transmission over such networks, which were observed through experience with [RFC3626] [RFC3561] [RFC3684] [RFC4728] [RFC5449].

3.1. Asymmetry, Time-Variation, and Non-Transitivity

First, there is no guarantee that a node C within S can, symmetrically, send IP packets directly to node A. In other words, even though C can "hear" packets from A (since it is a member of set S), there is no guarantee that A can "hear" packets from C. Thus, multi-hop ad hoc wireless communications may be "asymmetric". Such cases are not uncommon.

Second, there is no guarantee that, as a set, S is at all stable, i.e. the membership of set S may in fact change at any rate, at any time. Thus, multi-hop ad hoc wireless communications may be "time-variant". Such variations are not unusual in multi-hop ad hoc wireless networks due to variability of the wireless medium, and to node mobility.

Now, conversely, let V be the set of nodes from which A can directly receive packets -- in other words, A can "hear" packets from any node in set V. Suppose that node A is communicating at time t0 through its interface on network N. As a consequence of time variation and asymmetry, we observe that A:

1. cannot assume that S = V,
2. cannot assume that S and/or V are unchanged at time t1 later than t0.

Furthermore, transitivity is not guaranteed over multi-hop ad hoc wireless networks. Indeed, let's assume that, through their respective interfaces within network N:

1. node B and node A can hear each other (i.e. node B is a member of sets S and V), and,
2. node A and node C can also hear each other (i.e. node C is a also a member of sets S and V).

These assumptions do not imply that node B can hear node C, nor that node C can hear node B (through their interface on network N). Such "non-transitivity" is not uncommon on multi-hop ad hoc wireless networks.

In a nutshell: multi-hop ad hoc wireless communications can be asymmetric, non-transitive, and time-varying.

3.2. Radio Range and Wireless Irregularities

Section 3.1 presents an abstract description of some common characteristics concerning packet transmission over multi-hop ad hoc wireless networks. This section describes practical examples, which illustrate the characteristics listed in Section 3.1 as well as other common effects.

Wireless communication links are subject to limitations to the distance across which they may be established. The range-limitation factor creates specific problems on multi-hop ad hoc wireless networks. In this context, it is not uncommon that the radio ranges of several nodes partially overlap. Such partial overlap causes communication to be non-transitive and/or asymmetric, as described in Section 3.1.

For example, as depicted in Figure 1, it may happen that a node B hears a node A which transmits at high power, whereas B transmits at lower power. In such cases, B can hear A, but A cannot hear B. This examplifies the asymmetry in multi-hop ad hoc wireless communications as defined in Section 3.1.

              Radio Ranges for Nodes A and B
   
           <~~~~~~~~~~~~~+~~~~~~~~~~~~~>
                         |      <~~~~~~+~~~~~~>
                      +--|--+       +--|--+
                      |  A  |======>|  B  |
                      +-----+       +-----+

   Figure 1: Asymmetric Link example. Node A can communicate with
	 node B, but B cannot communicate with A.

Another example, depicted in Figure 2, is known as the "hidden node" problem. Even though the nodes all have equal power for their radio transmissions, they cannot all reach one another. In the figure, nodes A and B can hear each other, and A and C can also hear each other. On the other hand, nodes B and C cannot hear each other. When nodes B and C try to communicate with node A at the same time, their radio signals collide. Node A will only be able to detect noise, and may even be unable to determine the source of the noise. The hidden terminal problem illustrates the property of non-transitivity in multi-hop ad hoc wireless communications as described in Section 3.1.

                 Radio Ranges for Nodes A, B, C
     
   <~~~~~~~~~~~~~+~~~~~~~~~~~~~> <~~~~~~~~~~~~~+~~~~~~~~~~~~~>
                 |<~~~~~~~~~~~~~+~~~~~~~~~~~~~>|
              +--|--+        +--|--+        +--|--+
              |  B  |=======>|  A  |<=======|  C  |
              +-----+        +-----+        +-----+
     
	
   Figure 2: The hidden node problem. Nodes C and B
             try to communicate with node A at the same time,
             and their radio signals collide.
       

Another situation, shown in Figure 3, is known as the "exposed node" problem. In the figure, node A is transmitting (to node B). As shown, node C cannot communicate properly with node D, because of the on-going transmission of node A, polluting C's radio-range. Node C cannot hear D, but node D can hear C because D is outside A's radio range. Node C is then called an "exposed node", because it is exposed to co-channel interference from node A and thereby prevented from exchanging protocol messages to enable transmitting data to node D -- even though the transmission would be successful and would not interfere with the reception of data sent from node A to node B.

                   Radio Ranges for Nodes A, B, C, D
      
  <~~~~~~~~~~~~+~~~~~~~~~~~~> <~~~~~~~~~~~~+~~~~~~~~~~~>
               |<~~~~~~~~~~~~+~~~~~~~~~~~~>|<~~~~~~~~~~~~+~~~~~~~~~~~~>
            +--|--+       +--|--+       +--|--+       +--|--+
            |  B  |<======|  A  |       |  C  |======>|  D  |
            +-----+       +-----+       +-----+       +-----+

     Figure 3: The exposed node problem. When node A is communicating
	    with node B, node C is an "exposed node".

Hidden and exposed node situations are not uncommon in multi-hop ad hoc wireless networks. Problems with asymmetric links may also arise for reasons other than power inequality (e.g., multipath interference). Such problems are often resolved by specific mechanisms below the IP layer. However, depending the link layer technology in use and the position of the nodes, such problems due to range-limitation and partial overlap may affect the IP layer.

Besides radio range limitations, wireless communications are affected by irregularities in the shape of the geographical area over which nodes may effectively communicate (see for instance [MC03], [MI03]). For example, even omnidirectional wireless transmission is typically non-isotropic (i.e. non-circular). Signal strength often suffers frequent and significant variations, which are not a simple function of distance. Instead, it is a complex function of the environment including obstacles, weather conditions, interference, and other factors that change over time. The analytical formulation of such variation is often considered intractable.

These irregularities also cause communications on multi-hop ad hoc wireless networks to be non-transitive, asymmetric, or time-varying, as described in Section 3.1, and may impact the IP layer. There may be no indication to IP when a previously established communication channel becomes unusable; "link down" triggers are generally absent in multi-hop ad hoc wireless networks.

4. Alternative Terminology

Many terms have been used in the past to describe the relationship of nodes in a multi-hop ad hoc wireless network based on their ability to send or receive packets to/from each other. The terms used in this document have been selected because the authors believe (or at least hope) they are unambiguous, with respect to the goal of this document (see Section 1).

Nevertheless, here are a few other terms that describe the same relationship between nodes in multi-hop ad hoc wireless networks. In the following, let network N be, again, a multi-hop ad hoc wireless network. Let the set S be, as before, the set of nodes that can directly receive packets transmitted by node A through its interface on network N. In other words, any node B belonging to S can "hear" packets transmitted by A. Then, due to the asymmetry characteristic of wireless links:

- We may say that node B is reachable from node A. In this terminology, there is no guarantee that node A is reachable from node B, even if node B is reachable from node A.

- We may say that node A has a link to node B. In this terminology, there is no guarantee that node B has a link to node A, even if node A has a link to node B.

- We may say that node B is adjacent to node A. In this terminology, there is no guarantee that node A is adjacent to node B, even if node B is adjacent to node A.

- We may say that node B is downstream from node A. In this terminology, there is no guarantee that node A is downstream from node B, even if node B is downstream from node A.

- We may say that node B is a neighbor of node A. In this terminology, there is no guarantee that node A is a neighbor of node B, even if node B a neighbor of node A. As it happens, the terminology for "neighborhood" is quite confusing for asymmetric links. When B can hear signals from A, but A cannot hear B, it is not clear whether B should be considered a neighbor of A at all, since A would not necessarily be aware that B was a neighbor. Perhaps it is best to avoid the "neighbor" terminology except for symmetric links.

This list of alternative terminologies is given here for illustrative purposes only, and is not suggested to be complete or even representative of the breadth of terminologies that have been used in various ways to explain the properties mentioned in Section 3.

5. Security Considerations

This document does not have any security considerations.

6. IANA Considerations

This document does not have any IANA actions.

7. References

Appendix A. Acknowledgements

This document stems from discussions with the following people, in alphabetical order: Jari Arkko, Teco Boot, Carlos Jesus Bernardos Cano, Ian Chakeres, Thomas Clausen, Christopher Dearlove, Ralph Droms, Ulrich Herberg, Paul Lambert, Kenichi Mase, Thomas Narten, Erik Nordmark, Alexandru Petrescu, Stan Ratliff, Zach Shelby, Shubhranshu Singh, Fred Templin, Dave Thaler, Mark Townsley, Ronald Velt in't, and Seung Yi.

Authors' Addresses