Enhancing mesh networks

Last month we covered 4.9 GHz networks and the packet radio protocols used on these networks, particularly IEEE 802.11a. An important enabling technology for 4.9 GHz networks is ad hoc networking, also known as mesh networking. Much of the basic research in this area was funded by the Defense Advanced Research Projects Agency (DARPA), and the results of this research appear today in many commercial products. IEEE 802.11 wireless LANs are the main commercial application of mesh networking, but current mesh protocols are proprietary. The IEEE wireless LAN committee is considering a draft amendment, denoted 802.11s, which would define how wireless devices should interconnect to create a mesh network.

Mesh networks have two key features, according to C-K Toh’s Ad Hoc Mobile Wireless Networks: They are self-organizing and adaptive. Mesh network nodes can detect the presence of other network nodes and perform the necessary “handshake” to establish the link and ultimately create a reliable path between source and destination. No central administrator is required to make end-to-end connections.

A wireless mesh network is a set of two or more devices equipped with radios and special networking capability. Each device is a network node capable of originating traffic or routing traffic to other network nodes. Each node can communicate with another node within radio range or, through an intermediate node, with a node that is beyond radio range. Like many modern wireline networks, wireless mesh networks use shortest-path algorithms to find the best path between source and destination.

The shortest-path metric is not necessarily physical distance. The network adaptively measures link conditions to pick the path that is considered best by some metric. The best path might provide the most reliable link or the fewest intermediate nodes, or it might result in the highest data rate.

Figure 1 illustrates a typical mesh network topology. Note that connections exist between nodes only when the link can be closed. The absence of a connection between two nodes indicates that the distance is too great, or perhaps interference makes the link unfeasible.

A practical application of mesh networking concerns the elimination of wired infrastructure at intermediate network nodes. A typical 802.11 network requires each access point (AP) to be connected to a wired Ethernet computer network. In conventional 802.11 networks, APs talk to end users and to the wired network, but not to other APs. Mesh networks allow each mesh point (MP) to talk to other MPs for the purpose of finding the shortest path to a wired connection and to save infrastructure costs.

The principal advantage of mesh networking for this application is lower installation costs for outdoor nodes that are far from any wired infrastructure. Another advantage of mesh networks is the robustness created by adaptive routing algorithms. Such algorithms are especially important for networks with mobile nodes, because network connections change rapidly as such nodes move in and out of the radio coverage provided by myriad fixed nodes.

Mesh networks create challenges that do not exist in conventional 802.11 networks and, in some cases, can worsen those that do. Some of these challenges include throughput degradation, frequency planning, self-organization, routing, hidden and exposed nodes, latency, quality of service provisioning, multicasting, security, and energy management. We can’t address all of these topics here, so we’ll limit our discussion to the first four.

Throughput degradation

The simplest and most common type of mesh network employs a single frequency throughout the network. Such networks suffer significant throughput loss compared to multifrequency networks. First, throughput can be no greater than 50% of the burst rate because each node must operate in a Time Division Duplex (TDD) mode, where it alternates between receiving and transmitting. Each intermediate node cuts throughput in half again, so large networks with multiple intermediate nodes must necessarily have low throughput.

For example, consider an 802.11a network operating at a burst rate of 6 Mb/s on all links and using an end-to-end path with two intermediate nodes. The path has four nodes. Assuming equal traffic demand in both directions, the throughput is only ⅛ of 6 Mb/s, or 750 kb/s. Thus, an important metric for the shortest-path algorithm is the number of intermediate nodes, which should be minimized.

Frequency planning

One way to mitigate the throughput degradation caused by intermediate nodes is to employ multiple pairs of frequencies (one pair for each link). With enough frequencies, we can — in theory — achieve the highest throughput (equal to the burst rate), but if the network is adaptive, it also must change frequencies when necessary to maintain connections. Also, some minimum distance must be maintained between simultaneous co-channel nodes to preclude harmful interference and the resulting loss in throughput. If the network includes mobile nodes, frequency planning must be adaptive. The cellular industry already employs a form of adaptive frequency planning called Dynamic Channel Allocation (DCA) in its frequency-reuse networks, but such schemes are rare in 802.11 networks.

The minimum practical frequency reuse plan is N=3. The 2.4 GHz unlicensed band has only three non-overlapping channels (each 20 MHz wide), which is not enough to employ full duplex channels, which require 2N (or six) frequencies. There are more frequencies available in the 5 GHz band. At 4.9 GHz, there is less spectrum than at 2.4 GHz, but manufacturers do sell modified 802.11a radios that operate at 10 MHz and 5 MHz bandwidths with proportionally smaller maximum burst rates.

Self-organization

Self-organization is a requirement unique to mesh networks. The network must organize and maintain itself without the use of a central administrator. Self-organization involves several major activities, including neighboring node discovery, topology organization and topology reorganization, according to Ad Hoc Wireless Networks — Architectures and Protocols by C.S.R. Murthy and B.S. Manoj. During the neighbor-discovery phase, each node gathers information on its immediate neighbors within radio range. Doing so may require the use of short packets called beacons. In the topology-organization phase, each node gathers information about the entire network and stores this information in memory. Reorganization consists of the periodic exchange of topology and adapting to changes in the topology.

Routing

The routing protocol has several responsibilities: exchange route information among nodes; find a feasible path based on a specified metric (minimum number of nodes, least interference, strongest signal, minimum power required, expected lifetime of link, least contention, minimum delay, etc.); identify path breaks; mend broken paths; and use the minimum overhead possible. The wireless channel sufficiently differs from the wireline channel so that wireline routing protocols should not be used on wireless mesh networks. Bandwidth is at a premium, so the routing protocol must be fully distributed with a minimum amount of overhead. The algorithm also must be adaptive to deal with frequency topology changes caused by mobile nodes. Finally, the setup time must be short to reduce latency.

Jay Jacobsmeyer is president of Pericle Communications Co., a consulting engineering firm in Colorado Springs, Colo. He holds BS and MS degrees in electrical engineering from Virginia Tech and Cornell University, respectively, and has more than 25 years of experience as a radio frequency engineer.