Swarm Intelligent Routing

Swarm in HART

  Autonomous Agents
  Mobile Communication
  Genetic Algorithms
  Swarm Intelligence
  Neural Networks
  Machine 2 Machine
  Grid Computing
  Lubrication System
  Vertex Cover Algorithm
Bluetronix, Inc.
35 River Street
Chagrin Falls, OH 44022


Build compatibility between Swarm and HART
HART (Highway Addressable Remote Transducer) is a communication Protocol that provides communication among filed instruments and Host Systems . HART is a global standard for smart process instrumentation and there are more than 20 million HART enabled devices. The HART protocol makes use of the Bell 202 Frequency Shift Keying (FSK) standard to superimpose digital communication signals at a low level on top of the 4-20mA.       

HART 7 is a wireless HART protocol that is the first open wireless mesh network communication standard designed especially for simple, reliable, secure, and low power wireless communication for applications such as measurement, control and asset management.     

The three main elements of wireless HART architecture are wireless field devices, gateways and a network manager . The network uses IEEE 802.15.4 compatible radios operating in the 2.4GHz Industrial, Scientific, and Medical radio band. Bluetronix swarm routing protocol is also mesh routing protocol used for IEEE 802.15.4 compatible radios operating in the 2.4GHz.

According to HART, each device in the mesh network can serve as a router for messages from other devices. In other words, a device doesn't have to communicate directly to a gateway, but just forward its message to the next closest device. This extends the range of the network and provides redundant communication routes to increase reliability. The interference and other factors has to be taken into consideration before forwarding the packet on the run so as to make sure that the path chosen will always be the best path. Swarm finds the better alternative paths on the move using the approach of “learning while routing”. Swarm algorithm guarantees the reliable relay of message. Malfunctioning nodes can be isolated in swarm routing i.e. swarm has inherent security mechanism. HART using source routing must have much more overhead than the Swarm algorithm as in source routing packets carries lots of overhead. Moreover, HART’s radio, if programmed by Swarm algorithm, provides easy setup; intelligent decision making to forward the message via known-good paths; quick and self reconfiguration capability with addition and removal of nodes from the network. This suites most of the HART’s routing solutions. A new variation of swarm algorithm (Location Based Swarm algorithm) can be used for wireless applications that require location information such as locating the assets. Swarm routing can be very promising in WirelessHart’s most of the applications – in peer-to-peer communication; in simple monitoring and closed loop control systems with its sensor data acquisition and relay capability; in process automation by providing the best alternative paths achieving system redundancy.

Bluetronix BlueStar sensor module in Lubrication System
The intelligent fluid sensor called multi-element lubrication health sensor developed at Rockwell Automation’s Advanced Technology Labs in Mayfield Heights, Ohio, provides important fluid information such as seal failure, water or metal debris contamination, low concentration of fluids in the machinery and so on. The sensor information is crucial for early fault detection in the machinery to avoid machinery failure and for regular maintenance. The information can be relayed to the control room wirelessly with the use of Bluetronix BlueStar sensor modules (see BlueStar data sheet in Fig. 2) from Bluetronix Inc integrated with health sensors. The manual command information can also be relayed from control room to the respective nodes. Moreover, the wireless ad hoc network environment created by these modules can use feedback control system to apply the fluids in the machinery automatically. Refer to Fig. 1 below for details.

Lubrication System

In this Fig. 1, grey nodes are BlueStar sensor modules with integrated health sensors; yellow nodes are BlueStar fluid level sensor module; white nodes are BlueStar modules without sensors; and a red node is the home node that is connected to PC via RS-232 cable. Extra modules in machinery and lubricants are used for back up in case of module failure. All the sensor information as well as modules’ IDs are relayed to the home node and displayed on the visualizer. Now, consider a scenario when a grey node sends low lubricant status of the machinery to actuator. This message will be forwarded by the nodes to the actuator nodes using Bluetronix’s swarm algorithm. Nodes at the actuator receive this message and open the valve of respective lubricants to replenish the fluid amount in the machinery. This cycle is stopped only when there is no low lubricant status message. If there is drastic reduction in lubricants, this emergency message will be relayed to the visualzer that triggers the alarm for immediate service. The yellow nodes periodically send the lubricant level message to home node and trigger alarm when the lubricant falls to certain level. As showed in Fig. 1, there are many alternative paths to relay the message. The swarm algorithm always chooses the best quality path for the message depending on the link pheromone values that are frequently updated depending on the network traffic. In Fig. 1, data from heath sensor node will follow the solid line path to reach to regular node at actuator having better pheromone values. If any node’s ID is missing from the visualzer either because it becomes non functional or its battery is dead, new node or battery has to be replaced as soon as possible for seamless operations. The lubrication system can also be controlled via control room (manual control) by sending the appropriate commands via visualzier. The command will be relayed to designated nodes from home node.

Some Features of Bluetronix BlueStar Modules

  • Bluetronix BlueStar modules are developed using available COTS (Commercial-off-the-shelf) components available in the market and are low cost; price in the range $55.00 - $150.00 depending on the type of sensors and the volume for product price.

  • Bluetronix modules are designed for wireless application so they have very low power consumption.

  • BlueStar modules act as a router with Bluetronix swarm routing algorithm embedded into them and hence are useful for point to multipoint applications. The wireless sensing capability avoids expensive wirings and re-wirings. Moreover, they provide unique point to multipoint capability different from the current trend of point-to-point relay of message (if available). The main advantages are MANET capability, flexibility, re-configurability, and very low overhead. The control room can be located anywhere out of sight of sensor nodes, the message will be relayed via regular nodes and even if one path fails, there are many alternative best paths for relaying the message i.e. no need for manual re-configuration, set-ups and painful retro fit cost.

  • If the volume of data (information) is very large and there is a need of large number of modules, Bluetronix 32-bit modules which are available in near future will work with those 8-bit modules with ease without any compatibility issue. This provides more processing power and memory.

The home node can be replaced in late 2009 with Bluetronix Gateway to provide Internet capability. Now the control room can be located geographically anywhere with Internet service.

data sheet

Fig. 2: Bluestar Data Sheet

Back to Top

Vertex Cover Algorithm: NP-complete
Vertex Cover is a NP-complete problem that can be stated as given G = (V,E) of order n, weather there exists a set C with k or fewer vertices such that every edge of G has at least one endpoint in C. As many practical problems are NP-complete, there is a need to tackle these problems. Vertex Cover is a NP-complete problem that can be stated as given G = (V,E) of order n, weather there exists a set C with k or fewer vertices such that every edge of G has at least one endpoint in C. No polynomial time algorithms for NP-complete problems have been developed; or in other words optimal solutions for these problems are intractable. However, there are ways to get around with NP-completeness. If the problem size is small, algorithm with exponential running time solves the purpose. For example, a simple algorithm for the knight problem of size 5X5 when ran in a computer with 2GHz dual-core processor gave the solution within a minute, and problem size of 6X6 took about 3 hours. For problem size 8X8, the algorithm ran for about 12 hours and froze. So, exponential time algorithm for problem size 6X6 is still viable.

Dr. Sanjaya Gajurel working at Bluetronix Inc., Chagrin Falls, OH, has developed a polynomial time algorithm known as Optical Vertex Cover Algorithm (OVCA) that guarantees the minimal vertex cover solution for any graph G (V, E). By compromising the complexity of algorithm, the size of vertex cover obtained will be equal or at most (optimal size + k) which can be assumed as optimal solution when k is constant. The value of k obtained by applying the algorithm to all known example graphs has not been found more than 1. The idea behind the proposed algorithm is to add the vertices in the vertex cover in descending order of degree of vertices. The algorithm chooses the vertex that has the highest degree first, so the largest number of edges is covered which is analogous to choosing the safe edge in Minimum Spanning Tree (MST). Further research is being conducted to provide proof for the aforementioned algorithm having approximation ratio close or equal to approximation factor of (optimal size + 1)/optimal size for any general graph; and can be expected to be include in future. As many practical problems are NP-complete, there is a need to tackle these problems.

Example: Vertex Cover: In Fig. 1, OVCA has been applied to graph that returns the minimum vertex cover as showed by grey vertices. The grey vertices cover all the edges in a graph. All the edges can be covered including three or more than three vertices in the vertex cover; however, there is no way to cover them with less than three vertices. Hence, grey nodes belong to the minimum vertex cover.


Vertex Cover Applications

  1. Update dataset in a network within seconds irrespective of the size of the network while greatly limiting the re-updates.

Consider a graph in Fig. 2 where the servers are connected in the network and have the same copy of dataset (e.g. account balance). We can propagate the updates to all the copies in following ways:

  • Update each copy of dataset individually in all servers. It is not feasible for larger networks.

  • Initiate the broadcast from one server and propagate it throughout the network. It is time consuming as it takes time for the update to propagate to the server away from the broadcasting server.

  • Initiate the broadcast from bunch of servers. It is not efficient way as it has communication overhead – multiple copies and updates.

  • Initiate the broadcast from the servers in a vertex cover – 2, 4, and 5 in Fig. 2 obtained using OVCA. Then, only local propagation is required i.e. node 2 will propagate the updates to servers 1 and node 3. Servers 5 being in the vertex cover does not receive the updates that prevents copies and re-updates. Moreover, using suitable ordering technique, server can be prevented to have two or more updates. Server 3 can be updated twice by server 2 and server 4. The ordering indicates that server 3 should have been updated by server 2 before so server 4 does not send updates to server 3.


2. Constructing the minimum number of communication towers to cover the area

Before constructing the communication towers, a field survey is performed to find the number of possible points so as to cover the area or provide communication signals to the area. Fig. 2 is a graph formulation for Fig. 3 and following are the ways to provide coverage to that area: i. Construct the communication towers at every possible point. This provides the full coverage to the area, however, there are redundancies. ii. Construct bunch of towers but not at every possible point. This may leave some of the area uncovered. iii. Use OVCA in the graph with possible points as vertices and coverage as edges to find the minimum vertex cover and construct all the towers at the points that belong to the vertex cover. In Fig. 2, there are 6 possible points but only three towers will be constructed at location 2, 4, and 5 which guarantees the full coverage.



Back to Top


White papers on our products and technologies are available upon request. E-mail us at innovation@bluetronix.net or call 440.247.3434.

Copyright 2009 Bluetronix, Inc. | All Rights Reserved