Of points, stars and meshes

June 9, 2008 at 2:09 pm nbtventures Leave a comment

In wireless device networks (in fact, in any network), there are several methods for routing data from one node to another. We review the more common methods here.

Network Topologies

The topology of a network describes how individual nodes in the network connect to one another. (Note: the word “topology” derives from a branch of mathematics and from map making. If the word seems alien to you, you can simply substitute the word “layout” whenever you see it.)

The three most common topologies—point to point, star and mesh—are shown in the figure above. For now, assume that all nodes support bidirectional communication—they can both send and receive messages—but we will discuss unidirectional communication and its implications below.

Point-to-point Networks

A network that uses a point-to-point topology, or more succinctly, a point-to-point network, consists of two nodes. This is the simplest arrangement that can still be called a network. Node A can send messages to node B, and node B can send messages to node A.

Wireless point-to-point networks are often used for simple remote monitoring applications, such as collecting data from a single seismic sensor. In addition, a number of companies sell “wireless bridges” for wired networks, such as this wireless Ethernet bridge or 4-20 mA current loop bridge for industrial applications.

Beyond simple wire replacement, a simple bridge is useful in hazardous environments where running a wire is difficult or dangerous: in power substations, a single pair of wires can develop dangerously large voltage potentials. In these environments, a wireless link sidesteps all the problems associated with a wired connection.

Star Networks

Anyone who has worked with a WiFi is already familiar with a star topology: terminal nodes (such as the WiFi adapter in your laptop) communicate directly to a central control node (e.g. the Access Point in a WiFi network). A terminal node cannot communicate directly with another terminal node (in the star topology picture above, node B cannot communicate directly with node C) but it can send a message through the central node to be relayed.

Other examples of star networks are cell telephones (the towers are the central nodes, the handsets are the terminal nodes), and any centrally broadcast signal such as FM radio or television.

A network with star topology has the advantage of simplicity: all of the intelligence of the network can reside in the central node, which simplifies the design and operation of the terminal nodes.

On the other hand, this leads to a potential single point of failure—the entire network stops if the central node goes down for any reason.

And in some environments, getting sufficient RF coverage from the central node can be challenging: a friend of mine once said “It’s like trying to illuminate an entire supermarket from one really bright bulb hanging in the middle of the store. No matter how bright you make the bulb, you’ll still get shadows.” (Note: if you were that friend, please send me a note so I can give you proper credit!! — rdp)

For Computer Networks, usually there’s an easy fix when you find yourself in a radio shadow: simply move closer to the access point. But in Device Networks, it’s not so easy if the wireless node is attached to a two ton tank: it may be impractical to relocate the radios. This is one place where Mesh Networks can really help.

Mesh Networks

In a mesh network, nodes serve as “mini-routers” and can relay messages on behalf of their neighbors. This means that two nodes don’t need to have a direct radio link in order to communicate — all that is required is a set of “hops” to connect from one node to the next. In the mesh network figure above, node B cannot communicate directly to node D, but it can send a message to node C that will in turn re-transmit the message to node D.

Strictly speaking, a Mesh Network doesn’t require a central point of control. In fact, many network protocols such as ZigBee assign special powers to a “coordinator” node, but that is not part of the definition of a mesh network.

A mesh network is called self-organizing and self-healing if it can establish and maintain routing information among nodes without human intervention even as nodes come and go or the physical environment changes. Since Device Networks by definition need to operate without human intervention, nearly all mesh networking algorithms designed for Device Networks are both self-organizing and self-healing.

Simplex, Half Duplex, Full Duplex

Above, we showed examples of bi-directional networks, in which each node can transmit as well as receive. There are a few examples of uni-directional networks, so this is a good time to introduce the terms simplex, half duplex and full duplex.

a simplex channel sends data in one direction only. A television broadcast channel is an example of a simplex channel: the transmission tower always transmits and never receives.
a half-duplex channel sends data in both directions, but only one direction at a time. A CB radio or a walkie-talkie is an example of a half-duplex channel: once you push the microphone button to talk, you can no longer hear what is being transmitted on the channel. Most wireless LAN implementations are half-duplex: the WiFi adaptor in your laptop waits in receive mode until the access point gives it permission to transmit, it switches into transmit mode long enough to send a packet of data, then reverts to receive mode.
a full-duplex channel can send data in both directions at the same time. In fact, many full-duplex channels are implemented as pair of simplex channels: one for transmitting and one for receiving. Your cell phone communicates to the cell tower on one frequency channel while the tower simultaneously communicates with your phone on another frequency channel.

Some wireless sensor networks are built using simplex channels with uni-directional communication: data flows from a single sensor (in a point-to-point network) or from multiple sensors (in a star network) to a collection point. Since only sensor data is being collected, there is no need to communicate back to the sensor.

One does not commonly find a mesh network built using simplex communication links: nodes need to be able to transmit and receive in order to relay messages for their neighbors. (Strictly speaking, you could build a multi-hop mesh network using all simplex channels arranged in a directed graph, but I don’t know of any such implementations.)

Sensor Network != Mesh Network

One caveat: many people use the terms “wireless sensor network” and “mesh network” as if they are interchangeable. It’s important to keep in mind that a “sensor network” is an application, while “mesh” is an implementation detail. While it is true that a mesh network is often the architecture of choice for a wireless sensor networks, there have been many successful implementations that use point-to-point or star topologies.