Over the past few years, Mesh networks have become more popular, following the trend to create more wireless things. As with other technology trends, there have been a plethora of different mesh networking technologies and architectures.

This series of articles is intended to bring order to the mess of mesh networks. Here in Part 1, network basics will be discussed, focusing on the specifics of wireless, as well as the criteria for evaluating different wireless mesh networking technologies.

In Part 2, I will provide an overview of five different mesh related technologies, including key characteristics, network architecture, strengths and limitations. This information will be aggregated to create an evaluation of these different approaches, including when they should be applied.

To begin we start with the basics of networking and different topologies. It is important to note that network topologies describe the interaction and interconnection of the participants. This means how they communicate with each other and how they establish paths between each other.

Network topologies are not always what they seem. In the wired days, they generally followed the path of the wires " very simple. If devices were wired in a ring, then the network topology is a ring. The journey to wireless complicates everything because we all share the same air space so the path and access method is not always obvious. For example, is a WiFi access point a star topology or a bus?

Some common terminology
Before we go further in looking at these questions, it is important to first understand some common terminology which will be used throughout this article.

DSSS - Direct sequence spread spectrum. This is a method of encoding a signal which distributes information over a wide path of spectrum using a pseudo random code. Because of the wide spreading, the signal appears to be noise for those without the spreading code.

FHSS - Frequency hopping spread spectrum. Similar to DSSS, the big difference is that it uses a more constrained spreading algorithm and changes channels as a function of time, theoretically making the transmission more immune to interference.

TSMP - Time synchronized mesh protocol. This is a mesh protocol that uses time slots to allocate spectrum for communication between two nodes. Because time slots differ over pairs, interference is minimized because access to the channel is controlled by timeslot.

AODV - Ad-hoc on-demand distance vector routing algorithm. AODV is a pure on-demand route acquisition algorithm - nodes that do not lie on active paths do not maintain any routing information nor participate in any periodic routing table exchanges. Furthermore, a node does not have to discover and maintain a route to another node until the two need to communicate.

Cluster-Tree - Region based mesh network routing algorithm. In this algorithm, routes are formed and maintained between clusters of nodes. Route discovery is completed and maintained between the clusters " providing access to the children of each cluster.

ISM - Industrial Scientific and Medical band. This describes the frequency bands that can be used license free. Generally we refer to the 2.4 GHz band, but it also covers spectrum in 900 MHz, 5.8 GHz, 433 MHz in North America. 2.4 GHz is used worldwide.

IPv6 - Internet Protocol Version 6. This is the latest version of the popular IP or Internet Protocol. With Version 6, the IP address structure, routing and class of service changes. It is part of the TCP/IP suite of protocols sponsored by the IETF.

PAN ID - Personal Area Network Identifier. This is the term for the network name assigned to particular personal area network.

CSMA - Carrier sense multiple access. This protocol defines the channel access technique deployed by Ethernet, WiFi and bus oriented networks. It provides a method for detecting collisions and retransmitting as a method to acquire a communications channel.

TDMA - Time division multiple access. The protocol defines the channel access technique used by TSMP and GSM networks in which a communications channel is divided into time slots. Each node is allocated a specific time slot for communication.

Network Types
Now that we have a feel for the terminology, we first look at different network topologies commonly used. Figure 1 below shows three such topologies: Star, Bus and Ring.

Figure 1. Three typical wireless network topologoes

In the Ring, nodes are connected from one to the next. Communications messages are forwarded around the ring in either a clockwise and/or counter-clockwise fashion.

As a message is forwarded, the node checks to see if the message is meant for itself, if so, it keeps the message, if not, it forwards it on. It is most common in cabled networks (wire or fiber), but could conceivably be used in a wireless fashion as well but is not practical unless being used over long distances.

In the Bus, all nodes share a common communications medium and contend for using it. Typically this means some kind of CSMA type approach. Since a common medium is used, collisions and retransmissions increase with traffic loading.

In the wired case, these types of systems are referred to as hubs - which are generally no longer used. In the wireless case, it is more complicated because open space is often a shared medium, so even if routing is handled in a star, ring or other topology, open space often appears as a bus. More on this later as it is one of the fundamental hurdles in wireless networking.

In the Star, nodes are connected through a master, central node. This central node is responsible for looking at each message and forwarding it out on the proper communications link.

While various star architectures have been used over time, the most commonly known in the wired space is the Ethernet Switch. In the wireless space, the WiFi access point is also a familiar example since all messages are routed through the access point; however, even though messages are routed through the access point, open space is accessed via CSMA, a bus type protocol.

Mesh networking is more complete
A mesh network employs some level of more complete interconnection among nodes. This means that paths are not defined by a specific architectural pattern, but rather by the connections themselves.

In the full mesh topology, each node (workstation or other device) is connected directly to each of the others. In the partial mesh topology, some nodes are connected to all the others, but some of the nodes are connected only to those other nodes with which they exchange the most data. Figure 2 below illustrates a full mesh where each of the five nodes is connected to all the others.

Figure 2. A fully connected wireless mesh network configuration.

Other important thing to note about a mesh is that some or all nodes may be routers and some or all nodes may be end points. Typically, full interconnection is not achieved unless the network is very small.

Full interconnection gets very complex very quickly. In addition, wired mesh networks tend not be practical due to the complexities of connecting all the wires.

Figure 3 below illustrates three different instantiations of mesh networks. The green nodes are end devices, the yellow are routers (which may also be end devices) and the purple is the network coordinator responsible for allowing joining and departing from the mesh (more on this later).

Note that one instantiation of a mesh can be a star - a mesh with one router and the rest end points. The Cluster-Tree network is a combination of near full connectivity among routers and end points hanging off individual routers. The Peer-to-peer mesh generally gives equal rights to all nodes, including routing and end point functionality.

Figure 3. Three mesh networking instantiations

What makes wireless networks so different.
While we have discussed that mesh networks aren't really practical for wired networks, it is also important to look at the other differences between wired and wireless domains.

So what else makes wireless different? On the positive side, wireless makes it possible to have more connections since it is not practical or cost effective to create a full mesh with wires. However, on the negative side, wires are predictable, reliable and well understood.

Wireless forces the sharing of an already noisy, uncontrollable medium called open space. Hence, while wireless gives us more flexibility, the uncertainty of wireless drives the need for more connection pathsand more complexity.

When evaluating wireless, particularly mesh networks, there are a number of hard problems that need to be solved, including:

Accessing the medium. Since we all share open space, listening is more important than talking. If everyone talks at once, listening is difficult. So radios must be good listeners if they are going to have a chance to get a word in edge wise, so to speak.

Discovering routes. Determining paths in a wireless mesh network is difficult because the environment is dynamic. In this case, there are two choices: Planning the trip in advance, or taking it one step at a time. Often times doing both is best " this usually involves retracing one's steps and repeating well traveled routes.

Adapting to a changing environment. In a wireless world, paths to nodes can disappear and re-appear. This is due to changing signal conditions or traffic conditions.

Sleeping and Waking. Once we go wireless, the next step is often to find a way to do away with the traditional power cable. This means batteries and the need for effective power management.

The most common way of handling power management is putting the nodes to sleep when they are not being used. This sounds well and good until it is time to wake up.

How to Compare
Given that we now understand the basics of networks, in particular mesh networks, the next question that should be addressed is how do we compare them? For this, we look at criteria of security, reliability, power management, scalability, data movement, and cost.

Security. This is as much about the perception of threat as actual threat. Nonetheless, security is easily evaluated by the traditional factors that are well understood in the industry.

The first is encryption " protecting the information itself. Modern encryption wants at least AES128 as an algorithm (128 bit key). The next is authentication, which is validating that the users (or nodes) are who they say they are. This is typically handled by key exchange or authenticated certificate.

Last is authorization, which should be thought of as granting permission associated with having the right key or certificate. Beyond these, there are other factors which are associated with the ease of distributing and configuring the authorization and authentication mechanisms.

Reliability. The best way to think of reliability is the ability of a message to be delivered to the desired destination on time. If the message always arrives at the destination when expected, the network is very reliable.

Secondly, we want the message to arrive at the destination, even if it is a bit late. The components for evaluating reliability for wireless mesh networks have to do with the following:

1) Frequency agility: this is detecting and adapting the network around potential interference.

2) Message loss potential:  this is the question as to whether messages get lost in the shuffle. With all the re-routing and different paths, the network must be very careful to ensure messages don't get lost and that duplicate messages following different routes get discarded.

3) Adaptability: This is best described as the network's ability for changing the routing to accommodate for nodes disappearing while still preventing lost messages. This is most effective if done quickly.

4) Single points of failure: Are there any single points of failure, what is the risk of them failing and how is recovery handled?

Power Management. The most frequent question asked when discussing wireless sensor networks is how long will my batteries last? As soon as the cord is cut, everyone wants to still keep maintenance low.

Viewed in the context of the network architecture, power management is analyzed in terms of end nodes, router nodes and network coordinators. It is most important to have low powered, power efficient end nodes because they are most likely to be far from traditional wired power sources.

The routers are second. Battery powered routers, or routers that sleep, extend the flexibility of the architecture are necessary. Finally, the coordinator is usually powered. Now, in the context of nodes that can sleep, we then look at their average power consumption.

his is best assessed by looking at the combination of how they wake up, how frequently they wake up, total transmitting time and total listening time. Since the most power is consumed when radios transmit, it is important to keep this to a minimum.

Scalability. How big can the network get before it fails, at least on a practical level? All the networks have large physical limits in the 10s of thousands, but the practical design of the network is always much smaller.

This is because scalability is related both to reliability mechanisms and nature of the application. If a network never has any problems which cause rerouting, then network routing tables will never change, meaning cached routes will always work and there will be few retransmissions or reroutes because of failures. The end result is a very stable network that can be very large.

The other aspect concerns the type and volume of data. This data flow can be placed into three categories: Dribble Data, Bursty Data and Streaming Data " and they mean just like they sound.

Dribble data is periodic, infrequent and slow, while streaming data is constant, etc. A network can be very large if the traffic is dribble data because the flow follows consistent patterns, with plenty of bandwidth. Sleeping networks do well with dribble data, but scale poorly with streaming data.

Data Movement. Now we look in more detail at data flow, not for network scalability purposes, but for raw capacity. There is a classic trade-off in needs: Does the application require lots of data with low latency or does it require dribble data with long, non-deterministic latency?

As such, in evaluating networks for data movement, a combination of the following five variables needs to be considered: data rate, latency, packet size, fragmentation and range.

 Cost. Cost is measured by the individual unit cost as well as the cost to maintain the network. In this context, maintenance is often difficult to quantify and deployment cost is often forgotten.

It is easiest to quantify those variables that are most perceptible, namely the actual purchase cost of a transceiver system per node. This becomes a bit more complicated when trading off the number of battery powered or sleeping nodes.

For example, assume all end points need to be sleeping end points and a point to multipoint system is not practical due to range. Then a network that does not have sleeping routers will need to deploy powered routers in addition to the end points as compared to a network that has sleeping routers.

Hence, even if all radios are the same cost, more radios are needed in the powered router system. However, if power is available, then it becomes a non issue. So, the cheapest radio may not be the best for the application. The other point is that the cost of the radio tends to be looked at related to the cost of the device to which it is connected.

Next in Part 2: Comparing Zigbee and alternative wirlesss mesh technologies.

Joel K. Young is senior vice president and Chief Technical Officer at Digi International.