Author Topic: Microcontroller mesh network  (Read 14991 times)

0 Members and 1 Guest are viewing this topic.

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.
 

Offline edavid

  • Super Contributor
  • ***
  • Posts: 3375
  • 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: 26682
  • 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