Author Topic: Microcontroller mesh network  (Read 15133 times)

0 Members and 1 Guest are viewing this topic.

Offline sirhaggisTopic starter

  • Regular Contributor
  • *
  • Posts: 54
Microcontroller mesh network
« on: January 24, 2015, 12:49:41 pm »
G'day guys,
I'm working on a project where I am trying to connect many micro-controllers together in such a way that they can talk to their neighbours in a mesh network arrangement. Each controller will be a 32 bit entry level, something like an ARM Cortex M0 or similar. The idea is that every MCU can have up to 6 neighbours and the number of controllers can potentially be very large (e.g. 100s). Controllers need to be able to form communication channels across the mesh to arbitrary other controllers in the network, and also form groups of controllers to which members can broadcast to each other. If that were not complicated enough, I would like to be able to get some decent amount of bandwidth and low latency, even when controllers are at distant points in the network. Power usage is also a concern - e.g. constantly running polling code is out of the question, and I would expect that most controllers should sit largely idle in low power mode when they are not performing intensive tasks (e.g. listening for traffic).

So the main design decision I am struggling with at the moment is how to implement networking in such a way as to meet reasonable speed/latency/power requirements. Some immediate possibilities that I am considering and my thoughts on them are as follows:

- Multiplex a I2C or SPI connection to each neighbour controller and switch between them for communication. I'm not sure how well this would work in practice and whether there would be issues with lost data whilst switched to a different channel. Obviously the max bandwidth for any controller is limited by the bus speed shared across all connections, but that is workable as long as there is no data loss. Apparently there are some I2C multiplexing chips out there that I have not looked into yet. The problem with this approach seems to be potential latency issues because packet forwarding needs to be done in software and associated power costs. Also I'm not really sure how well I2C/SPI would operate in a multiplexed scenario.

- Shared bus. This option would create a shared bus (single wire) between all controllers with each having a unique address. This is obviously great for latency, but means the bandwidth of all communications is limited to the bus speed. I think there would also be more significant issues when the number of controllers start hitting the hundreds, such as address space issues and parasitic capacitance/noise on the bus, etc.

- Multiplexed channels. This is an idea I had that could allow multiple independent closed networks to be dynamically configured on the fly. It would involve using multiplexers/crosspoint chips at each controller to create direct links/channels through that point by switching appropriately (like a switchboard). So if you wanted to create a direct link between the controller on the left and right you would set the switches as appropriate using the controller, and a direct connection will be created between them. By setting the switches (with GPIO pins) you could create arbitrary groups of controllers that share the same bus and have multiple independent buses communicating with each other. This potentially has great latency and bandwidth properties but would come at the cost of complexity (and probably way too many multiplexers).

Given the severe practical concerns with having a shared bus, I think the other options are the way to go. Fully software routing has a certain appeal but I suspect the power and latency issues may make it impractical (although perhaps some combination of interrupts and DMA could practically address this?). A multiplexing arrangement is potentially very powerful, but I'm not sure the added complexity is worth it and there a potentially issues with the number of control pins available to set the multiplexers.

Something else I haven't looked into is whether there are exists cheap ICs that can offload the networking/switching logic for each controller and and only bother the MCU when there is traffic it needs to process. I'm not sure if such a thing exists that is a) physically compact and b) cheap (think $1-$2 range as there are potentially going to be hundreds of nodes). Does anybody know if such a thing exists?

Thoughts?
 

Offline Maxlor

  • Frequent Contributor
  • **
  • Posts: 565
  • Country: ch
Re: Microcontroller mesh network
« Reply #1 on: January 24, 2015, 01:10:45 pm »
Can you give some numbers for the average and max distance between nodes, as well as the latency and bandwidth requirements?

Btw, SPI, I2C and similar buses are problematic when used as a field bus, they'll pick up a lot of noise and achievable speed will be limited. I differential bus will probably perform better.
 

Offline sirhaggisTopic starter

  • Regular Contributor
  • *
  • Posts: 54
Re: Microcontroller mesh network
« Reply #2 on: January 24, 2015, 01:26:19 pm »
As an approximation I would say max distance would be 40 nodes, average about 5-10. Latency/bandwidth requirements are essentially 'as good as I can get', but as a figure perhaps 100-200Mbps between each node (although if there were a shared bus for all nodes it would need to be considerably higher), latency perhaps <10ms per link.

I agree on the noise issues, which is why I don't think I will be pursuing a shared bus over the whole network. In a switched channel arrangement there would obviously have to be limits on how large the networks are to avoid noise. A software approach would not have to worry about noise because the controllers would relay messages at each node to their neighbour.
 

Offline nctnico

  • Super Contributor
  • ***
  • Posts: 26906
  • Country: nl
    • NCT Developments
Re: Microcontroller mesh network
« Reply #3 on: January 24, 2015, 01:45:27 pm »
ETHERNET!
You can run your own protocol over existing hardware if implementing UDP or even TCP/IP is making things too complicated but you could be re-inventing the wheel here.
There are small lies, big lies and then there is what is on the screen of your oscilloscope.
 

Offline sirhaggisTopic starter

  • Regular Contributor
  • *
  • Posts: 54
Re: Microcontroller mesh network
« Reply #4 on: January 24, 2015, 02:48:24 pm »
Yes I have thought about ethernet and it would be an awesome solution if I could get it to work. I'm not so sure whether it would be feasible with the hardware constraints I have however - I am using entry level MCUs which don't natively support ethernet. I suppose it might be possible to implement it using GPIO's but that sounds hairy. Other than that there might be ethernet-on-a-chip type products that I could interface with, but I doubt they would fit in the $1-$2 each price range I am looking for (there will be many controllers implemented as modules that can be stacked).

Definitely something I will look into though.
Thanks
 

Offline sirhaggisTopic starter

  • Regular Contributor
  • *
  • Posts: 54
Re: Microcontroller mesh network
« Reply #5 on: January 24, 2015, 02:55:13 pm »
"Other than that there might be ethernet-on-a-chip type products that I could interface with, but I doubt they would fit in the $1-$2 each price range"

Scrap that, I just found some contenders - some less than $1 in bulk!
To the bat mobile!
 

Offline sirhaggisTopic starter

  • Regular Contributor
  • *
  • Posts: 54
Re: Microcontroller mesh network
« Reply #6 on: January 24, 2015, 03:54:06 pm »
There are a bunch of ICs that do something what I want here:
http://www.digikey.com/product-search/en?FV=fff40027%2Cfff801a4%2C908000d&k=ethernet&mnonly=0&newproducts=0&ColumnSort=1000011&page=1&stock=0&pbfree=0&rohs=0&quantity=&ptm=0&fid=0&pageSize=25

On further thought however, it would seem that I would need one ethernet transceiver for each neighbour connection, which means six of these per node. I'm looking into the possibility of ethernet multiplexing, but I'm not sure if that would actually work or not.
 

Offline sirhaggisTopic starter

  • Regular Contributor
  • *
  • Posts: 54
Re: Microcontroller mesh network
« Reply #7 on: January 24, 2015, 03:59:50 pm »
Something like this with built int TCP/IP stack is also possible, but its in the $3-$5 category, not $1ish category
http://wizwiki.net/wiki/lib/exe/fetch.php?media=products:w5500:w5500_ds_v105e_141111.pdf
 

Offline nctnico

  • Super Contributor
  • ***
  • Posts: 26906
  • Country: nl
    • NCT Developments
Re: Microcontroller mesh network
« Reply #8 on: January 24, 2015, 04:50:11 pm »
There are a bunch of ICs that do something what I want here:
http://www.digikey.com/product-search/en?FV=fff40027%2Cfff801a4%2C908000d&k=ethernet&mnonly=0&newproducts=0&ColumnSort=1000011&page=1&stock=0&pbfree=0&rohs=0&quantity=&ptm=0&fid=0&pageSize=25

On further thought however, it would seem that I would need one ethernet transceiver for each neighbour connection, which means six of these per node. I'm looking into the possibility of ethernet multiplexing, but I'm not sure if that would actually work or not.
Try to find a switch chip which is MII ports instead of an analog interface. If the MII port on that switch chip can be put into slave mode even better: you can bitbang the MII interface so you don't need a microcontroller with a MAC.
There are small lies, big lies and then there is what is on the screen of your oscilloscope.
 

Offline BlueBill

  • Regular Contributor
  • *
  • Posts: 169
  • Country: ca
Re: Microcontroller mesh network
« Reply #9 on: January 24, 2015, 05:44:08 pm »
Might be helpful if the OP would tell us what they're trying to build.
 

Offline Dave Turner

  • Frequent Contributor
  • **
  • Posts: 447
  • Country: gb
Re: Microcontroller mesh network
« Reply #10 on: January 24, 2015, 11:15:23 pm »
My first thought is a new take on a neural net  ;D
 

Offline sirhaggisTopic starter

  • Regular Contributor
  • *
  • Posts: 54
Re: Microcontroller mesh network
« Reply #11 on: January 25, 2015, 02:38:25 am »
Might be helpful if the OP would tell us what they're trying to build.

It is something of a thought experiment that I am considering taking further and actually seeing if it would work in practice. The idea is that you can have many cheap (think a few dollars) modules that have some processing capacity and can connect to other modules to create a highly parallel computing framework. It would probably use something like the MapReduce approach to allow problems to be distributed over the nodes and solved using the combined power of all nodes. The idea would be that you can keep adding modules (preferably on the fly while the system is running) to increase the processing power of the system. Nodes would share power and data connections with each of their neighbors.
 

Offline Richard Crowley

  • Super Contributor
  • ***
  • Posts: 4317
  • Country: us
  • KJ7YLK
Re: Microcontroller mesh network
« Reply #12 on: January 25, 2015, 02:48:04 am »
Quote
Build A Simple And Inexpensive Controller Area Network Node

Shown here is the schematic for a simple, inexpensive controller area network (CAN) node (Fig. 1). The PIC12C672 was chosen because of its low pin count (8 pins) and powerful feature set. This set includes an internal oscillator, on-board multichannel 8-bit analog-to-digital converter (ADC), multiple interrupt sources, and a low-power sleep mode.

A full CAN 2.0 implementation with message filtering is supplied by the MCP2510 14-pin standalone CAN controller. Therefore, the host microcontroller is relieved from performing any CAN-bus-related overhead. This is a key feature given the limited available code space of the PIC12C672. The PCA-82C251 transceiver was selected arbitrarily because this article focuses on implementing the CAN protocol, and the physical layer is undefined by CAN.

http://electronicdesign.com/boards/build-simple-and-inexpensive-controller-area-network-node

The code is available for download from the URL cited above.

Note that the concept could be applied to other sub-$1 8-pin microcontrollers (Atmel/Arduino, for example).

« Last Edit: January 25, 2015, 02:52:01 am by Richard Crowley »
 

Offline sirhaggisTopic starter

  • Regular Contributor
  • *
  • Posts: 54
Re: Microcontroller mesh network
« Reply #13 on: January 25, 2015, 03:52:10 am »
Great link Richard, I will definitely be looking into a CAN approach. My only concern with the given example is that all nodes would have to share the same network, limiting the total combined bandwidth of all nodes to 1Mbps. When we are considering hundreds of nodes this is probably going to be a severe constraint in most cases.

Currently I am thinking about whether an ethernet transceiver could be combined with a multiplexer to allow multiple ethernet links to be maintained while only requiring a single, cheap ethernet transceiver (rather than 6). The main issue I can see with this approach is how to deal with 'normal link pulses' which are sent every 8-24ms to check if the connection is up (I wonder how fast a transceiver can be activated/deactived to send data on request? Presumably auto-negotiation would have to be disabled?). In my mind, you could have a line from each controller to its neighbor that you set high to indicate you want to send it some data. When the neighbor node is ready to receive data it switches its transceiver with the mux and sets its line high to indicate it is ready to receive data. The sender also switches its multiplexer to connect the ethernet transceiver to that neighbor and a data exchange can occur. Pass through traffic would be handled by the MCU so there would be a latency/power cost, but this could probably be kept to reasonable levels by relying on interrupts.
Perhaps there are others with more knowledge of such details? I have never worked with ethernet at a low level.
 

Offline obiwanjacobi

  • Frequent Contributor
  • **
  • Posts: 988
  • Country: nl
  • What's this yippee-yayoh pin you talk about!?
    • Marctronix Blog
Re: Microcontroller mesh network
« Reply #14 on: January 25, 2015, 07:55:06 am »
My thoughts:

I would think of local buses for the connected nodes and off-loading communications to something very cheap (in $ and power consumption). This would allow the node to pass on data without the main processor waking up - saving energy.
I would also think of a protocol that allows adding nodes dynamically without having to manage the ID's or node-clusters manually (with switches or alike) - you would go insane if this gets too large. Again look to existing network protocols /switches for inspiration.

[2c]
Marc
Arduino Template Library | Zalt Z80 Computer
Wrong code should not compile!
 

Offline zapta

  • Super Contributor
  • ***
  • Posts: 6190
  • Country: us
Re: Microcontroller mesh network
« Reply #15 on: January 25, 2015, 09:32:31 am »
This project reminds the Transputer, used to be hot at the time.
 

Offline Mechanical Menace

  • Super Contributor
  • ***
  • Posts: 1288
  • Country: gb
Re: Microcontroller mesh network
« Reply #16 on: January 25, 2015, 11:34:44 am »
Might be helpful if the OP would tell us what they're trying to build.

It is something of a thought experiment that I am considering taking further and actually seeing if it would work in practice. The idea is that you can have many cheap (think a few dollars) modules that have some processing capacity and can connect to other modules to create a highly parallel computing framework. It would probably use something like the MapReduce approach to allow problems to be distributed over the nodes and solved using the combined power of all nodes. The idea would be that you can keep adding modules (preferably on the fly while the system is running) to increase the processing power of the system. Nodes would share power and data connections with each of their neighbors.

I think you'll end up needing a lot more power per node just to manage the network and distribute jobs, let alone actually get any work done. Just for the compute node OS I think you'll soon run out of ram and flash on the MCUs. Or maybe some sort of layout where you have more powerful control nodes that can support a full OS manage up to so many compute nodes would be a decent compromise?
« Last Edit: January 25, 2015, 11:39:12 am by Mechanical Menace »
Second sexiest ugly bloke on the forum.
"Don't believe every quote you read on the internet, because I totally didn't say that."
~Albert Einstein
 

Offline sirhaggisTopic starter

  • Regular Contributor
  • *
  • Posts: 54
Re: Microcontroller mesh network
« Reply #17 on: January 25, 2015, 12:05:19 pm »
Quote
I think you'll end up needing a lot more power per node just to manage the network and distribute jobs, let alone actually get any work done. Just for the compute node OS I think you'll soon run out of ram and flash on the MCUs. Or maybe some sort of layout where you have more powerful control nodes that can support a full OS manage up to so many compute nodes would be a decent compromise?
You may well be right, but that is part of the challenge :)

I do imagine that there could be nodes with different degrees of capability and could take on more of the burden of administrating the network - I am using cortex MCUs so in theory incorporating anything from an M0 to an M5 would be possible without too much extra work. There are probably also ways of arranging the network so that there doesn't have to be a great deal of routing overhead for each module - for example if a module knows its position in space relative to the other modules and the location of the destination module you could use a simple path finding algorithm that doesn't require it to keep track of nodes other than its immediate neighbors. A similar approach could be used to distribute jobs (in theory). I think using some kind of external communication support circuit could lessen the burden of waking up controllers to deal with some of the lower level details of communication. What that circuit could look like is still a bit of a mystery!
 

Offline Mechanical Menace

  • Super Contributor
  • ***
  • Posts: 1288
  • Country: gb
Re: Microcontroller mesh network
« Reply #18 on: January 25, 2015, 12:26:59 pm »
Is there anything like an ARM equivalent of a QUICC processor? I know the 68360 one not only the had the onboard processor that can deal with most networking on it's own but also exposed the 68020's (I think) data and address lines to the pins so you could add more RAM if needs be. Something of that sort of idea could be ideal.

When it comes to the network topolgy and protocols you've also got to decide what sort of work you'll be doing and whether a constant MIPS or "jobs per month" is more important to you.
Second sexiest ugly bloke on the forum.
"Don't believe every quote you read on the internet, because I totally didn't say that."
~Albert Einstein
 

Offline Richard Crowley

  • Super Contributor
  • ***
  • Posts: 4317
  • Country: us
  • KJ7YLK
Re: Microcontroller mesh network
« Reply #19 on: January 25, 2015, 03:08:41 pm »
Is there anything like an ARM equivalent of a QUICC processor? I know the 68360 one not only the had the onboard processor that can deal with most networking on it's own but also exposed the 68020's (I think) data and address lines to the pins so you could add more RAM if needs be. Something of that sort of idea could be ideal.

When it comes to the network topolgy and protocols you've also got to decide what sort of work you'll be doing and whether a constant MIPS or "jobs per month" is more important to you.

Horsepower does NOT appear to be a requirement here.
The main issue appears to be low-cost distributed I/O.
And the second issue appears to be integration and programming.

One downside of a "mesh" of self-contained micro-controllers is programming them properly to interact with all the other nodes.
It almost makes me think it would be better to have a single central processor that considers all the input parameters,
and makes the decisions and sends out the data to operate the system.  It doesn't take much processing power to do that.

If I were doing this, my first guess would be a second-hand PC as a central processor,
something easy to control, and with the capability of presenting a nice UI on the screen,
and some industry-standard interface protocol like I2C or maybe RS-485,
and using some standard wiring format like UTP/RJ-45 (i.e. common network cabling)

There is quite probably little I/O boards out there already available that implement this kind of thing.

This is not all that different from most industrial control systems where they have been doing this for decades.
And with systems with serious consequences if things aren't done properly.

« Last Edit: January 25, 2015, 03:11:02 pm by Richard Crowley »
 

Offline Mechanical Menace

  • Super Contributor
  • ***
  • Posts: 1288
  • Country: gb
Re: Microcontroller mesh network
« Reply #20 on: January 25, 2015, 03:49:07 pm »
Horsepower does NOT appear to be a requirement here.
The main issue appears to be low-cost distributed I/O.
And the second issue appears to be integration and programming.

Yeah, just properly read stuff like I should before posting that lol. Sorry folks.
Second sexiest ugly bloke on the forum.
"Don't believe every quote you read on the internet, because I totally didn't say that."
~Albert Einstein
 

Offline tszaboo

  • Super Contributor
  • ***
  • Posts: 7374
  • Country: nl
  • Current job: ATEX product design
Re: Microcontroller mesh network
« Reply #21 on: January 25, 2015, 04:01:09 pm »
Quote
I think you'll end up needing a lot more power per node just to manage the network and distribute jobs, let alone actually get any work done. Just for the compute node OS I think you'll soon run out of ram and flash on the MCUs. Or maybe some sort of layout where you have more powerful control nodes that can support a full OS manage up to so many compute nodes would be a decent compromise?
You may well be right, but that is part of the challenge :)

I do imagine that there could be nodes with different degrees of capability and could take on more of the burden of administrating the network - I am using cortex MCUs so in theory incorporating anything from an M0 to an M5 would be possible without too much extra work. There are probably also ways of arranging the network so that there doesn't have to be a great deal of routing overhead for each module - for example if a module knows its position in space relative to the other modules and the location of the destination module you could use a simple path finding algorithm that doesn't require it to keep track of nodes other than its immediate neighbors. A similar approach could be used to distribute jobs (in theory). I think using some kind of external communication support circuit could lessen the burden of waking up controllers to deal with some of the lower level details of communication. What that circuit could look like is still a bit of a mystery!
I was thinking about something similar, I wanted an extendable LED game of life simulator. That is communication in 8 directions, but with repeating, it is possible to reduce it to 4.
I've found that cheap microcontroller with existing identical communication interface is not an easy task, then the Atmel SAM D20/21 came out. They have 6 SERCOM, flexible serial communication modules. That seemed to be perfect for my purposes, you should take a look. Set it up as SPI or USART, point to point, and it is done nice and simple. Hope you are fine with the limitations.
 

Online edavid

  • Super Contributor
  • ***
  • Posts: 3382
  • Country: us
Re: Microcontroller mesh network
« Reply #22 on: January 26, 2015, 01:24:36 am »
It is something of a thought experiment that I am considering taking further and actually seeing if it would work in practice. The idea is that you can have many cheap (think a few dollars) modules that have some processing capacity and can connect to other modules to create a highly parallel computing framework. It would probably use something like the MapReduce approach to allow problems to be distributed over the nodes and solved using the combined power of all nodes. The idea would be that you can keep adding modules (preferably on the fly while the system is running) to increase the processing power of the system. Nodes would share power and data connections with each of their neighbors.

Why?  This is an inefficient way to build a distributed computer.  Using such cheap nodes reduces the cost effectiveness of the overall system.
You might as well buy a uniprocessor that's as fast as all the nodes put together.
 

Offline nctnico

  • Super Contributor
  • ***
  • Posts: 26906
  • Country: nl
    • NCT Developments
Re: Microcontroller mesh network
« Reply #23 on: January 26, 2015, 11:04:31 am »
On further thought however, it would seem that I would need one ethernet transceiver for each neighbour connection, which means six of these per node. I'm looking into the possibility of ethernet multiplexing, but I'm not sure if that would actually work or not.
If each node has short connections I strongly advise to use 1 microcontroller per node. Distributed systems are a pain in the ass to get working correctly due to all the possible error conditions.
There are small lies, big lies and then there is what is on the screen of your oscilloscope.
 

Offline splin

  • Frequent Contributor
  • **
  • Posts: 999
  • Country: gb
Re: Microcontroller mesh network
« Reply #24 on: January 26, 2015, 02:29:15 pm »
But what application code would you run on each node? If its fixed then fine, each node would be programmed from the outset with the problem solving code, with the problem data being distributed across the network to be processed.

But if you want this creation to be useable for different problems you'll presumably need to distribute new code to every node. Most low end Cortex devices have very limited RAM, so unless the application code is very small, each node will have to write the code into its Flash memory and run it from there. Certainly possible but perhaps rather slow to reprogram the whole network and you may also run into problems due to the limited number of rewrites of the Flash.

Splin
 

Offline SL4P

  • Super Contributor
  • ***
  • Posts: 2318
  • Country: au
  • There's more value if you figure it out yourself!
Re: Microcontroller mesh network
« Reply #25 on: January 26, 2015, 10:26:42 pm »
Just to keep your low-cost options open...
Not a solution for you in itself, but I stumbled across this link yesterday, which may give some ideas.

http://www.romanblack.com/blacknet/blacknet.htm
Don't ask a question if you aren't willing to listen to the answer.
 

Offline Richard Crowley

  • Super Contributor
  • ***
  • Posts: 4317
  • Country: us
  • KJ7YLK
Re: Microcontroller mesh network
« Reply #26 on: January 26, 2015, 10:33:11 pm »
Just to keep your low-cost options open...
Not a solution for you in itself, but I stumbled across this link yesterday, which may give some ideas.
http://www.romanblack.com/blacknet/blacknet.htm
That guy apparently never heard of 1-Wire designed by Dallas Semiconductors. Dallas was subsumed by Maxim which continues to sell many 1-wire products.
1-Wire is generally a board-area "network", mostly on the same (or adjacent) PCB.
http://www.maximintegrated.com/en/products/comms/one-wire.html
 

Offline SL4P

  • Super Contributor
  • ***
  • Posts: 2318
  • Country: au
  • There's more value if you figure it out yourself!
Re: Microcontroller mesh network
« Reply #27 on: January 26, 2015, 10:37:52 pm »
Just to keep your low-cost options open...
Not a solution for you in itself, but I stumbled across this link yesterday, which may give some ideas.
http://www.romanblack.com/blacknet/blacknet.htm
That guy apparently never heard of 1-Wire designed by Dallas Semiconductors. Dallas was subsumed by Maxim which continues to sell many 1-wire products.
1-Wire is generally a board-area "network", mostly on the same (or adjacent) PCB.
http://www.maximintegrated.com/en/products/comms/one-wire.html

The reason that BlackNet appealed, is because it can use the hardware`UART, and avoids implementing the fiddly 1-wire stack - and you can run really simple bespoke protocols as needed.
Valid comment tho. (I've been 'resetting' my DS 1-wire printer 'chips' for years !!!)
Cheers
Don't ask a question if you aren't willing to listen to the answer.
 

Offline sirhaggisTopic starter

  • Regular Contributor
  • *
  • Posts: 54
Re: Microcontroller mesh network
« Reply #28 on: January 27, 2015, 02:43:04 am »
Thanks for your input guys. I understand the comments regarding difficulties of distributed systems with low powered nodes and scarce RAM, although it is not a big concern in this case. There will actually be a mix of microcontrollers with different specs - those on the low-end will not actually have to do much work other than handle and relay sensor data across the network, plus forward packets/connections.

At this stage I have looked at various options and will most likely be pursuing a UART/RS-485 linkage approach. From my (somewhat limited) knowledge so far it should be possible to multiplex a single connection using a slightly non-standard approach, and make use of the onboard UART support of STM32 cortex MCUs. It appears this should be reasonably efficient approach if DMA and interrupts are used. I will probably use a custom connection/routing protocol with an efficient addressing scheme of my own design and use MCUs to relay packets with very limited network knowledge (my algorithm ideas are summarised below). I have looked into various other approaches like ethernet, I2C, SPI, etc but no others are really appropriate (e.g. ethernet relies on 15ms pulses to keep the connection alive, making it difficult to multiplex).

As far as establishing connections across the mesh of controllers, my current thoughts are to use an A* search algorithm when trying to establish connections, combined with small connection establishment and routing stacks at each node. Nodes will be given a location sensitive address (position in mesh) that enables each to rank its neighbors according to how close they are to the target (i.e. straight line path). They will then delegate to a neighbor who is closest to the target node to continue the search. Each node will keep a stack of connections that are currently being established and will move to a connection stack if a connection is made, or remove if connection fails (and sending fail message to the requesting node). Dead-ends will be handled by backtracking via the 'connecting' stack and trying the next closet node until a route is found or all neighbors have failed (in which case we fail to requesting node, causing a backtrack). When a connection is established, each node along the path will keep a stack of connection IDs, associated with the id of a neighbor it needs to relay packets to. When a connection is closed a special message will flow across this path and each node will remove the connection from their stack. Each node can optionally keep a cache of previous connections that enable them to quickly re-establish a connection without a full search - making this optional allows flexibility because low memory nodes can simply not implement the stack (or only a small one) and perform search every time a connection is requested (i.e. trade off between memory usage and connection establishment time/bandwidth). The advantage of this approach is that we can always find the shortest path to the destination node relatively efficiently (in most cases), and can still find connections in odd shaped node arrangements when there is no direct straight line path. This approach could also be extended to weight links and take into account different link speeds and bandwidth utilization, etc. The actual routing/connection work that is mandatory each node has to perform is minimal - each node only has to know about its neighbors when finding connections and routing is just a connection lookup (neighbor node id associated with a connection id) which means it should not consume a lot of node power. Additional optimisations are also possible depending on a nodes memory/processing capabilities. Packet sizes could be optimized according to scale, meaning it could be made to be very efficient. I'm aware that there are protocols that do similar things to the described, although the actual implementation in this case is not too hard with my background and will allow me to optimize it specifically to my particular scenario and addressing scheme.

Thoughts?
« Last Edit: January 27, 2015, 05:00:02 am by sirhaggis »
 

Offline sirhaggisTopic starter

  • Regular Contributor
  • *
  • Posts: 54
Re: Microcontroller mesh network
« Reply #29 on: January 27, 2015, 03:23:25 am »
It is something of a thought experiment that I am considering taking further and actually seeing if it would work in practice. The idea is that you can have many cheap (think a few dollars) modules that have some processing capacity and can connect to other modules to create a highly parallel computing framework. It would probably use something like the MapReduce approach to allow problems to be distributed over the nodes and solved using the combined power of all nodes. The idea would be that you can keep adding modules (preferably on the fly while the system is running) to increase the processing power of the system. Nodes would share power and data connections with each of their neighbors.

Why?  This is an inefficient way to build a distributed computer.  Using such cheap nodes reduces the cost effectiveness of the overall system.
You might as well buy a uniprocessor that's as fast as all the nodes put together.

MIPS is not the goal, but saying that there are certain problems that are better suited to distributed computation.
The advantage of a distributed approach is that nodes can be in different locations, among other things.
Also, for the right problem and setup, a few hundred distributed cortex MCUs will out perform any single processor.
 

Offline sirhaggisTopic starter

  • Regular Contributor
  • *
  • Posts: 54
Re: Microcontroller mesh network
« Reply #30 on: January 27, 2015, 03:26:47 am »
But what application code would you run on each node? If its fixed then fine, each node would be programmed from the outset with the problem solving code, with the problem data being distributed across the network to be processed.

But if you want this creation to be useable for different problems you'll presumably need to distribute new code to every node. Most low end Cortex devices have very limited RAM, so unless the application code is very small, each node will have to write the code into its Flash memory and run it from there. Certainly possible but perhaps rather slow to reprogram the whole network and you may also run into problems due to the limited number of rewrites of the Flash.

Splin

In general code updates will be infrequent and nodes will have their own code-base, however I also have some ideas for some simple distributed computation without the need to distribute flash updates for every execution. Limited RAM is an obstacle, but not an insurmountable one.
 

Online edavid

  • Super Contributor
  • ***
  • Posts: 3382
  • Country: us
Re: Microcontroller mesh network
« Reply #31 on: January 27, 2015, 06:55:48 am »
MIPS is not the goal, but saying that there are certain problems that are better suited to distributed computation.
The advantage of a distributed approach is that nodes can be in different locations, among other things.
Also, for the right problem and setup, a few hundred distributed cortex MCUs will out perform any single processor.

Can you name one problem where "a few hundred distributed cortex MCUs" will outperform a PC that costs the same, but is built out of X86 CPUs and standard GPUs?
 

Offline JVR

  • Regular Contributor
  • *
  • Posts: 201
  • Country: be
Re: Microcontroller mesh network
« Reply #32 on: January 27, 2015, 07:24:58 am »
RS485. You can get tranceivers that do 50mbps, can handle 200 nodes per bus and considering that most M0 cores max out at ~50Mhz, thats about as fast as you will go.
 

Offline sirhaggisTopic starter

  • Regular Contributor
  • *
  • Posts: 54
Re: Microcontroller mesh network
« Reply #33 on: January 27, 2015, 08:11:39 am »
MIPS is not the goal, but saying that there are certain problems that are better suited to distributed computation.
The advantage of a distributed approach is that nodes can be in different locations, among other things.
Also, for the right problem and setup, a few hundred distributed cortex MCUs will out perform any single processor.

Can you name one problem where "a few hundred distributed cortex MCUs" will outperform a PC that costs the same, but is built out of X86 CPUs and standard GPUs?

You're missing the point. I didn't specify an equivalent price comparison - if I were looking for MIPS per $ I would be taking an entirely different approach. If I were solving a problem that could be accommodated by a single processor/GPU combination then I wouldn't bother with the effort. If you want to know where distributed computing excels then look at MapReduce, which underlies much of Googles computing infrastructure. Some benefits of a distributed approach include far greater failure resilience (no single point of hardware failure), multiple hardware locations (for efficient location specific in/outs), flexible expansion (ability to add additional modules while the system is running), and (potentially) far fewer limitations on how far the system can be expanded (100s, 1000s of nodes, or in Googles case millions). In this project I'm taking a similar approach that takes advantage of locality to access, process and route various inputs and outputs efficiently, whilst computing larger problems across multiple nodes in the network, with significant failure resilience and the ability to add/remove modules as desired without disrupting the rest of the system. So in theory someone should be able to rip out a module or two and only its immediate capabilities will be affected.

« Last Edit: January 27, 2015, 08:40:46 am by sirhaggis »
 

Offline sirhaggisTopic starter

  • Regular Contributor
  • *
  • Posts: 54
Re: Microcontroller mesh network
« Reply #34 on: January 27, 2015, 08:27:45 am »
RS485. You can get tranceivers that do 50mbps, can handle 200 nodes per bus and considering that most M0 cores max out at ~50Mhz, thats about as fast as you will go.
Actually I intend to do something quite non-standard and run multiple independent UART/RS485 buses simultaneously with a single UART module, switching between them with a multiplexer to receive/transmit on multiple independent channels. I will probably run a separate line along with each interconnect that is set high when there is traffic waiting. The MCU will detect the low-high transition and run an interrupt which will switch the multiplexer to connect its UART to the appropriate line to receive incoming data. A return line will be set high to indicate that it is ready to receive the pending transmission and the sending MCU will transmit. In this case all UART buses between modules will only have the two nodes on them and can run at full speed without affecting non-local nodes (beyond servicing latency time) - I will just be introducing the ability to put the connection in 'pause' mode while another line is serviced. I'm not entirely sure this will work out, but I'm looking into it. It will certainly add latency when forwarding traffic across multiple modules, but from my initial calculations this shouldn't be particularly bad in the Mbps range. There are obviously lots of potential issues with this approach, but at this stage it seems to be a good tradeoff that will allow high throughput across the whole network regardless of how big it gets, whilst having reasonable power and latency attributes.
« Last Edit: January 27, 2015, 08:31:43 am by sirhaggis »
 

Offline LabSpokane

  • Super Contributor
  • ***
  • Posts: 1899
  • Country: us
Re: Microcontroller mesh network
« Reply #35 on: January 27, 2015, 10:52:20 am »
I've been thinking about this in the back of my head for a bit. You might reconsider Ethernet.  A lot of the architecture you're trying to implement in new hardware could be as cheaply bought in the form of managed switches and implemented with a spanning tree topology and vlans.
 

Offline sirhaggisTopic starter

  • Regular Contributor
  • *
  • Posts: 54
Re: Microcontroller mesh network
« Reply #36 on: January 27, 2015, 11:32:10 am »
I've been thinking about this in the back of my head for a bit. You might reconsider Ethernet.  A lot of the architecture you're trying to implement in new hardware could be as cheaply bought in the form of managed switches and implemented with a spanning tree topology and vlans.

You are correct, the main problem is doing it in the kind of price range I am looking for, as each node has to be <$5 complete. If I could find an ethernet switch chip in the range of $1-$2 that would be fantastic but so far I haven't seen anything close to that price range.
 

Offline splin

  • Frequent Contributor
  • **
  • Posts: 999
  • Country: gb
Re: Microcontroller mesh network
« Reply #37 on: January 28, 2015, 06:44:17 pm »
The Cortex M0 STM32F091 has 8 USARTS which should improve throughput and connectivity. Its only 48MHz with 256k Flash, 32K RAM
 

Offline jeremy

  • Super Contributor
  • ***
  • Posts: 1079
  • Country: au
Re: Microcontroller mesh network
« Reply #38 on: January 28, 2015, 10:21:59 pm »
Well just to throw my 2c in, I really think ethernet is the way to go.

I've never used them, but the IP175C is a 5+1 port 10/100 switch IC that can be had for less than $2 USD in singles from china: http://www.icplus.com.tw/pp-IP175C.html

datasheet here: https://www.insidegadgets.com/wp-content/uploads/2012/12/IP175C.pdf
 

Offline nctnico

  • Super Contributor
  • ***
  • Posts: 26906
  • Country: nl
    • NCT Developments
Re: Microcontroller mesh network
« Reply #39 on: January 28, 2015, 10:36:53 pm »
I have used the IP175 in a design. They aren't exactly low power. The newer versions seemed to have addressed that problem. That still doesn't solve the fact you need an ethernet phy stuck to each chip. Another way of doing it could be an FPGA which acts as an ethernet switch but can use SPI (or whatever) instead of a MAC towards the microcontrollers and a MAC + phy towards ethernet.
There are small lies, big lies and then there is what is on the screen of your oscilloscope.
 

Offline codeboy2k

  • Super Contributor
  • ***
  • Posts: 1836
  • Country: ca
Re: Microcontroller mesh network
« Reply #40 on: January 29, 2015, 12:20:26 am »
RS485. You can get tranceivers that do 50mbps, can handle 200 nodes per bus and considering that most M0 cores max out at ~50Mhz, thats about as fast as you will go.
Actually I intend to do something quite non-standard and run multiple independent UART/RS485 buses simultaneously with a single UART module, switching between them with a multiplexer to receive/transmit on multiple independent channels. I will probably run a separate line along with each interconnect that is set high when there is traffic waiting. The MCU will detect the low-high transition and run an interrupt which will switch the multiplexer to connect its UART to the appropriate line to receive incoming data. A return line will be set high to indicate that it is ready to receive the pending transmission and the sending MCU will transmit. In this case all UART buses between modules will only have the two nodes on them and can run at full speed without affecting non-local nodes (beyond servicing latency time) - I will just be introducing the ability to put the connection in 'pause' mode while another line is serviced. I'm not entirely sure this will work out, but I'm looking into it. It will certainly add latency when forwarding traffic across multiple modules, but from my initial calculations this shouldn't be particularly bad in the Mbps range. There are obviously lots of potential issues with this approach, but at this stage it seems to be a good tradeoff that will allow high throughput across the whole network regardless of how big it gets, whilst having reasonable power and latency attributes.

If you are going to go to the trouble to add an external IC (the multiplexor), then I'd suggest better to add a cheap Lattice FPGA or CPLD instead; these are available for a few dollars. They have enough I/Os that you can get your 6 serial channels directly from the hardware, and it can make routing decisions in hardware for packets that don't address the local node.  If you don't know FPGAs and HDL, then at least put a second microcontroller (like the CAN controller Richard described).  You really don't want to be using the main processor for muxing data and routing packets among 6 neighbors. Pulling data into the main CPU (every byte) only to send it out again will possibly consume a major portion of your processing time and the node will become useless, unless you reduce the communication rate and then the network will become useless. Better to offload that work,  either in a separate MCU with 2 or 3 UARTS + MUX (2 extra chips) or a CPLD/FPGA with 6 serial ports in hardware and some routing logic.

If you do decide to use a CPLD or FPGA , do not even think of it like a UART. instead, I'd make a simple synchronous serial port (synchronous, not asynchronous), duplicate it 6 times and add the routing logic in hardware based on bits in the frames. This is extremely easy to do.  Then use an on-board SPI channel to the main CPU for any control and data that is destined for the local node. Data not destined for the local node would be transferred internally with 1-bit time latency (after routing) between two I/O ports on the CPLD/FPGA.  This kind of synchronous serial port with frame level routing is dead easy to do in hardware.  Via a shift register, you buffer enough bits of the frame to determine routing (which should be in the first few bits), latch it, do a lookup in the hardware routing table, and transfer all bits of the frame to the next port until the end of frame; if the frame is for the local node, you shift-in the whole frame, latch it to memory, then interrupt the main CPU. Other bits of combinatorial logic and register logic is needed for control functions, but it's easy.

Synchronous frame level board to board and board to off-board protocols like Serial RapidIO, Infiniband, Aurora, etc. exist for this already, and there are (expensive!) hardware routing chips available for this too. They are complete SOCs with user-level protocols and specs for up to 10+ Gbps multi-lane networking, but I don't think you need all that.  You can still look to these protocols for guidance, but if all you are looking for is 1Mbit/s point-to-point and can do your own simple framing protocol, then you can get away with a simple roll-your-own hardware serial solution. You can add virtual circuit switching later if you wanted Node X to connect directly to Node Y in your mesh.

I'm writing this just to put forth another possible way for you to think about it.

And if you've never used an FPGA (and thus never used an HDL like VHDL or Verilog), then it's perhaps a simple enough reason to learn it :)
 

Offline sirhaggisTopic starter

  • Regular Contributor
  • *
  • Posts: 54
Re: Microcontroller mesh network
« Reply #41 on: January 29, 2015, 11:03:50 am »
Great points codeboy2k, definitely worth considering. FPGAs are something I have been meaning to get acquainted for a while now and are quite appealing to me - I understand the basics of how they operate but don't have much of an idea about how to work with them. Do you know of any good introductions to programming with FPGAs?
« Last Edit: February 01, 2015, 06:23:33 am by sirhaggis »
 


Share me

Digg  Facebook  SlashDot  Delicious  Technorati  Twitter  Google  Yahoo
Smf