Articles

Practical approaches to development of mesh network technology

Nowadays the so-called mesh networks are increasingly widespread; they feature decentralized, flexible and dynamic structure where network nodes are not bound to the central station and any node can act as coordinator or repeater functions [1, 2, 5]. Thanks to this structure the mesh networks have a number of doubtless advantages:

  • High reliability as any node can substitute a lost coordinator or repeater,
  • Capability to "detour" physical or artificial "obstacles" in the radio channel thanks to a large number of possible combinations of routes,
  • A mesh network can transmit information using low-power radio signals which are more difficult to triangulate or intercept.


However, the mesh topology represents a number of issues with no clear solutions up to date. These problems can be, for the sake of convenience, subdivided in two groups, "Arbitration" and "Routing".

Arbitration. In the star networks, the central node distributes the network channel between the child nodes by itself in the optimum way. In the mesh network, the nodes independently shall come to an agreement and give network channel to the higher-priority data. A set of rules and algorithms regulating access of the network nodes to the channel is called arbitration.

The arbitration is needed when it is impossible or inexpedient to assign a separate radio channel to each node. The arbitration becomes particularly critical at the moment of network self-organization or change in network structure, and in case of relaying/broadcasting critical broadcast messages. The development of arbitration algorithms faces the following issues:

  • Identification of wanted signal. To arrange communication between network nodes, a node ready for data transmission shall be able to identify the wanted signal in the channel. For example, in encrypted channels noise may be separated from wanted signal not before receiving a data packet suitable for decoding. In such cases the known ways of access to channel, such as DCF, become ineffective.
  • Hidden node. It often happens in mesh networks that two nodes do not hear each other and start transmitting, while the third node can hear both of them simultaneously. In such a data superimposition situation the third node will most likely fail to recognize the wanted signal and may start transmitting too. So, all three nodes will be transmitting simultaneously in the same radio channel.
  • Unprotected node. In situation may occur when transmitting nodes are capable of disabling whole segments of the network. It happens when a node starts transmitting for one isolated network segment and does not permit the adjacent node to transmit to other segment.
  • The node capacity issue is a combination of the two above said issues. Weak nodes contribute to the hidden node issue, and powerful transmitters contribute to the unprotected node issue.

 

Routing, i.e. selecting a packet forwarding route between two nodes, has no unambiguous solutions as well. There are two known methods:

  • Dynamic routing, when a now, having received a packet, retransmit the packet back (unless the packet is addressed to this node). Sooner or later, the packet will reach the destination. An obvious disadvantage of this method is that sending one packet involves nearly the entire network thus resulting in significant throughput loss.
  • Static routing is when each node acting as the Coordinator knows the network structure. The number of possible links and, respectively, the required volume of information are proportional to the square of the number of nodes. Relaying and continuous updating this information overload the network as well.


Thus, all the above mentioned and profoundly interrelated issues of the mesh networks tickled us to start a detailed and integrated research aimed at finding efficient solutions.

This research was aimed at the following problems:

  1. To review publications and existing methods of mesh network organization.
  2. To develop a numerical and computer simulation model of a mesh network.
  3. To obtain experimental demonstration of model consistency.
  4. To use the simulation model to verify the efficiency of our own approaches to mesh network organization and to perform comparative analysis against known approaches.
  5. To verify experimentally the consistency of the methods we developed.


We employed two experimental setups. The first setup comprised 10 self-contained devices based on TRX nRF24L01+ and microcontroller ARM Cortex M4 operating under in-house developed real-time operating system RTOS MAX. The mesh network is arranged as an add-on to RTOS kernel. The purpose of this setup was to run and test the mesh algorithms we developed and to compare them with existing ones.

The second more sophisticated setup was based on two SDR modems based, in turn, on TRX LimeMicro LMS6002D, FPGA Altera Cyclone4 and controller ARM9. The purpose of this setup was to construct and experimentally evaluate the simulation model with SDR modem operational features, in particular, a number of options of modulation, encoding and parallel transmission via several radio channels [3, 4].

The simulation model was developed in Visual Studio under OS Windows. Preliminary numerical modeling, planning and supervision of the numerical experiments, and processing and result visualization were carried out in MathWorks MATLAB.

The results of multiple physical experiments were generalized in a physical model; the model approximates interaction between nodes contending the channel and determines the probability of data reception by a node, also in case of simultaneous transmission by several nodes.

The physical model is linked with a transceiver driver emulator that simulates time-dependent data transmission processes structurally common for all transceivers. This driver has an interface compatible with interfaces of real device drivers. The next level is the RTOS MAX emulator enabling simulation of multitask processes within the developed model. The top level where the mesh algorithms are implemented is a hardware independent software running in the same way in model and in actual prototype. Thus, the four-level simulation model was developed that isolates the hardware-dependent processes from high level software; the model helped us to solve the following problems:

  • Emulation and debugging of the software for the prototype (the software may have been developed and debugged well before the prototype),
  • Automated planning, running and supervising the numerical experiments,
  • Focused search of critical bottlenecking conditions,
  • Preparation and substantiation of intensive testing program to demonstrate network operation in extreme conditions with a limited number of nodes,
  • Preparation and substantiation of Requirement Specification for network infrastructure and equipment.


The consistency of the developed model was verified in a number of experiments. The number of packets lost during transmission between two nodes (50,000 packets) at the setup and in the model differed by less than 1%: 76% at the setup and 77% in the model. The simulation model trained at the two prototypes demonstrated its consistency in further experiments with a complete set of 10 physical devices.

By now, the model helped to streamline and test all the known mesh network algorithms. Particular attention was given to development of own arbitration algorithms that enable increasing the useful traffic up to 95% of the maximum.

This research is not yet completed; however some conclusions can already be made.

Physical experiment and simulation modeling demonstrated that the SDR modem capabilities (such as channel switching, parallel use of channels, switching between modulation methods) considerably extended the capabilities of the mesh network and enabled optimal grouping of nodes thus helping to eliminate the above mentioned effects of "hidden", "unprotected" and "powerful" nodes.

The developed simulation model appeared to be an extremely convenient tool considerably speed up and cheapen development of new mesh network algorithms. In particular, the simulation model makes it possible to find optimum combinations of network setup parameters and enables comparison of operation of different algorithms in a statistically reasonable manner.

In the course of intensive testing (including acceptance tests) the simulation model enables preparing an optimum work plan and uses fewer physical devices to considerably reduce both cost and duration of research.

REFERENCES

  1. A.I. Lyakhov, I.A. Pustogarov, S.A. Shpilev. Multi-Channel Mesh Networks: Approach Analysis and Performance Estimation // Information processes. — 2008. — V. 8, No. 3. — pp. 173-192.
  2. G.V. Popkov. Mesh Networks: Development Prospects, Potential Applications // Problemy informatiki. — 2012. — No.3. — pp. 74-79.
  3. Draves R., Padhye J., Zill B. Routing in Multi-Radio, Multi-Hop Wireless Mesh Networks // ACM Mobicom. — 2004.
  4. Yu H. Mohapatra P., Liu X. Channel Assignment and Link Scheduling in Multi-Radio Multi-Channel Wireless Mesh Networks// Mobile Networks and Applications archive. —2008. — V. 13. — 169-185 p.
  5. Naveed A., Salil S. Kanhere, Sanjay K. Jha. Topology Control and Channel Assignment in Multi-radio Multi-channel Wireless Mesh Networks//. Proc. of MASS. — 2007. — 1-9 p.

 

A.N. YUSUPOV, Candidate of Biological Sciences, A.A. SPIRKOV, S.A. TURKIN
AstroSoft

Get In Touch

  • Gelsingforsskaya 3, corpus 11D
    194044, St. Petersburg, Russia
  • +79522068225
  • This email address is being protected from spambots. You need JavaScript enabled to view it.