Meshtastic

Mesh-Routing algorithm

Hi, following from a couple of previous forum discussions, I think this topic deserve a thread.
I’m re-reading the source for the message distribution algorithm

And - oh boy - I think there is a lot of room for improvement.
I’m trying to come up with and idea that works in more than one use case, for example hiking and long-range data transmission.
Also I think the algorithm for message distribution should be at the same time energy-aware and inherently robust to guarantee the delivery of the message.
The first idea that come to mind is to have two classes of nodes: moving and stationary.
Router nodes, highly requested in other threads, will be a subset of the stationary ones; for those nodes a couple of assumptions will be made: the energy consumption is ‘less’ of a problem, and their geographical position is not changing over time (duh).
Moving nodes will be assumed to have less energy available (being only battery-powered) and constantly moving, meaning that their access to other nodes is subject to change.
This categorization can be derived from GPS data, or user-defined in some other way.
As soon as I come up with a more complete idea I’ll update the thread!
Best

5 Likes

I have a use case where a router node will be mounted high up on a moving vehicle, so I think the assumption that routers are stationary won’t always be true.

Essentially, I’ll have a router back in base camp and then a router mounted on top of a support vehicle.

:slight_smile:

Mhh, you’re right. What do we mean by router? How do you define it?

The current definition is it’s a device that doesn’t draw much power, screen is rarely turned on, etc.

In the future, we’ve discussed routers as a preferred node in the routing algorithm.These are possibly devices that are more likely to have line of sight than other devices.

Ok. I then would disentangle characteristics and preferences.
Drawing more or less power is determined by the traffic and use, availability of power is defined in the network set-up.
From a routing perspective, defining moving and stationary nodes may make sense because some will need to re-define their accessibility to other nodes in the network, other not.
Preferring that a packet transit over a router instead of another nodes make sense.
I’ll then say we should define nodes being moving/stationary and routers/enders.
What do you think?

I started this post a few days a go. I haven’t dug in to the details too much, and even if I did I don’t have enough background knowledge to know how well it serves the different requirements. But it seems to be well supported.

From what I’ve seen it looks very promising.

I’m gonna take a look at it! Thanks

1 Like

I think that sounds pretty good.

Ok, it looks nice, but my fear is that it’s not dynamical enough. The whole parent-child structure is efficient and robust, but in the ‘hiking’ scenario the re-discovery of new devices may need to happen multiple times, and the protocol seems not optimized for that.

@fvsura thanks for looking into this, I think you can make some great contributions here!

@mc-hamster it sounds like you have been playing with attenuators some; have you used them to test mesh behavior? Ideally, for testing purposes, I’d like to have multiple nodes in different corners of my house that can’t communicate directly, but can through intermediate nodes in the middle. So far, I have what should be about ~21dB of attenuation on two of my nodes at opposite ends of my house. Even with the antennas pointed directly away from each other, they can still communicate directly! I was surprised this was the case. Maybe my attenuators are no good, or maybe i need more attenuation? 21dB on both sides seems like it should be plenty to me.

Setting up a testing rig with un-attenuated nodes deployed in the field isn’t really very viable for me. If I could come up with a testing setup where the corner nodes still have access to my WiFi, but can’t communicate via LoRa directly I think it would help me a lot.

You should really put each board in a metal enclosure to shield uncontrolled radiation from the PCB.
21 dB is the SNR reported by the firmware or an approximation based on your (directional?) antenna (rear?) gain?

I built a 60db attenuator for that purpose.

Lora has an incredible link budget. It works even when the signal is below the noise floor.

21dB is what the attenuators I have put together should work out to. I recently got a nanovna2, but I haven’t had a chance to confirm that they really are 21dB with it. When it comes to RF, I have much to learn.

Thanks for the suggestion. I’ll see if shielding the PCBs helps some. I’m just using stock antennas now, so they are omnidirectional. I have been pointing them directly away from each other(so that the tips are pointed 180 degrees away from each other). I think I have a 900Mhz antenna somewhere I think I can try on of these https://www.getfpv.com/tbs-diamond-antenna.html.

I’m impressed by how well LoRa can perform. My biggest issue with it is getting good performance in the field where there are mountains and trees and so forth. RF is a total black art to me. I guess I must be getting emissions from the PCB or signals bouncing off the walls in my house or something.

Wow! ok, i guess i probably also need more attenuation too. I’m surprised that that much is necessary as 21dB should work out to roughly a factor of ~125 reduction in emitted/received power. If I really have that on both ends(and I may very well not, I barely know what I’m doing here) it’s wild to me that anything is getting through!

I’ll try shielding and more attenuation next.

hja

6b5c73c0a67a4141ca63a5a6ffa8dee341adcd5e

3 Likes

Sorry, didn’t mean to hijack this thread!!

I’d be interested in seeing the mesh routing algorithm improved to better support dynamic routing of messages between longer chains of nodes with intermittent connectivity due to movement and terrain/obstacles. It seems like there isn’t really much open source/affordable solutions out there that handle this situation well.

I know this is a really hard problem, and not sure how I can contribute to the algorithm itself other than through maybe building a testing rig of some sort to try algorithms/parameters ideas.

I’ll shut up now!

The thread went other way but my suggestion is to consider DTN/bundle protocol (e.g. RFC5050) instead of B.A.T.M.A.N. B.A.T.M.A.N. needs all nodes online to form a mesh but this does not requires this. I’m big fan of B.A.T.M.A.N. but after discovering this - I’m fan of this too :slight_smile:
There is OSS libraries like NASA IOPN or ud3tn for this.

More info for concept:

1 Like

Hi,
Seems interesting, could you link me a paper or two to better dig into it?

I like the idea of DTN. A quick look at the wikiP page and the links I checked out make it seem at least at first glance to lack traction and active development. Many of the links are 10+ years old and can only be accessed through the way back machine.

Is there a modern project that has this running in esp32 or similar devices?

Please check this: µD3TN | D3TN

There is also NASA’s ION: https://www.nasa.gov/sites/default/files/atoms/files/1.2_lecture_-_intro_to_ion_implentation_of_the_dtn_architecture.pdf

IOS is even included in Ubuntu:
% apt-cache search ion | grep -w ‘^ion’
ion - NASA implementation of Delay-Tolerant Networking (DTN)
ion-doc - Interplanetary Overlay Network - examples and documentation

1 Like