Some questions about fruitymesh

Mohamed-GN commented 3 years ago

what is the size of fruitymesh code (to know if it can fits in my project).
what is the differnece between these variables : totalInConnections,totalOutConnections,meshMaxInConnections,meshMaxOutConnections
i want to set a mesh with a line (one input connection and one output connection for every node) topology (auto-forming) what are the modification that should be done (if not currently supported, is it easy to be implemented).
i changed the variables listed above to :
u8 totalInConnections = 2; //3; u8 totalOutConnections = 1;//3; u8 meshMaxInConnections = 2; //2; u8 meshMaxOutConnections = 1; //3; i got a problem where nodes can't join the mesh despite it is obvious that they have the possibilty : also is it possible to change scan parameters so that always the best parntner is chosen (for example extend advertisement and scan time so all nodes knows about each other and make the best decision)

mariusheil commented 3 years ago

Hi,

As for the code size, I just compiled a minimal example and it used around 56kb of flash. There are a lot of features that are not necessary and could be stripped out and you could probably get something around 30kb but this needs some manual work as we did not make all features optional in our code.

The number of connections is only relevant for RAM consumption, not flash. The "total" connections represent the number of connections reserved from the SoftDevice so that e.g. Smartphones can connect to the mesh and so that mesh nodes can contact other mesh nodes to tell them to cancel other connections. The "mesh" connections on the other hand are the onex exclusively for the stable mesh.

I cannot currently check what you would need to change, but maybe try to use 2 totalIn + out connections and try to use 1 meshIn and 1 meshOut connection. But the algorithm wasn't developed to solve such scenarios and I guess it will fail in most real world examples to build a line of mesh nodes. I guess you would need to develop a whole new connection strategy to get what you want. What are you exactly trying to achieve?

For changing the scanning parameters, you would need to extend numNodesForDecision and maxTimeUntilDecisionDs but it's been a long time since I played around with these parameters, so good luck ;-) In the end, you will only choose the best connection partner from the local knowledge and not the globally best partner as this would mean doing an optimum calculation for the whole mesh at once.

Marius

Mohamed-GN commented 3 years ago

Thanks Marius i am trying to implement your mesh code on my rf modem (not bleutooth) the device we have supports one Tx front end and one Rx front end so at one time we can only send to next node and receive from previous node and vice versa to get an optimal throughput the topology should be a line. Where nodes start sending to upstream and receiving from downstream and in the next switch instant do the opposite i really need this topology so if you have any idea where can i start and modify the algorithm to get it

Le lun. 20 sept. 2021 à 21:28, Marius Heil @.***> a écrit :

Hi,

As for the code size, I just compiled a minimal example and it used around 56kb of flash. There are a lot of features that are not necessary and could be stripped out and you could probably get something around 30kb but this needs some manual work as we did not make all features optional in our code.

The number of connections is only relevant for RAM consumption, not flash. The "total" connections represent the number of connections reserved from the SoftDevice so that e.g. Smartphones can connect to the mesh and so that mesh nodes can contact other mesh nodes to tell them to cancel other connections. The "mesh" connections on the other hand are the onex exclusively for the stable mesh.

I cannot currently check what you would need to change, but maybe try to use 2 totalIn + out connections and try to use 1 meshIn and 1 meshOut connection. But the algorithm wasn't developed to solve such scenarios and I guess it will fail in most real world examples to build a line of mesh nodes. I guess you would need to develop a whole new connection strategy to get what you want. What are you exactly trying to achieve?

For changing the scanning parameters, you would need to extend numNodesForDecision and maxTimeUntilDecisionDs but it's been a long time since I played around with these parameters, so good luck ;-) In the end, you will only choose the best connection partner from the local knowledge and not the globally best partner as this would mean doing an optimum calculation for the whole mesh at once.

Marius

— You are receiving this because you authored the thread. Reply to this email directly, view it on GitHub https://github.com/mwaylabs/fruitymesh/issues/189#issuecomment-923271827, or unsubscribe https://github.com/notifications/unsubscribe-auth/ANME3DVTER7IOQRCZOVMAY3UC6KPHANCNFSM5ELTOKVQ . Triage notifications on the go with GitHub Mobile for iOS https://apps.apple.com/app/apple-store/id1477376905?ct=notification-email&mt=8&pt=524675 or Android https://play.google.com/store/apps/details?id=com.github.android&referrer=utm_campaign%3Dnotification-email%26utm_medium%3Demail%26utm_source%3Dgithub.

siretty commented 3 years ago

Hello @Mohamed-GN,

Marius is currently not available, so I'll chime in :)

Implementing the FruityMesh algorithm on a system that does not use BLE underneath will be ... tricky. E.g. FruityMesh requires broadcasts to all neighboring nodes during the phase where the mesh is forming (and technically also afterwards, in order to detect new (not-yet-)mesh nodes in the vicinity and to deal with lost connections).

I was (sort of) able to reproduce your result (overriding the variable in Conf::LoadDefaults):

After setting the parameters to

totalInConnections = 2;
totalOutConnections = 2;
meshMaxInConnections = 1;
meshMaxOutConnections = 1;

the mesh actually formed a line

On the other hand I can imagine physical placements of nodes where forming a line is not possible at all:

Please excuse the crude drawing. Assume that the dotted gray lines are connections which cannot be established (e.g. due to distance), while the green ones can be established. There is no possible way to create a line topology to connect all four nodes in this example. It may be a bit construed, but it is only meant to illustrate Marius' point.

Even with only one RX and TX front end, you are able to implement multiple connections. You'll have to do what the BLE link layer is doing - multiplex your RX and TX front ends and include address information such that the receiver knows if it was meant by the transmitter. You'll likely also have to follow strict timing requirements, such that multiple connections are able to live side-by-side on a single node. Example (just from the top of my head, not actually a recommendation):

Node 1: [On-Air Slot Conn. A][On-Air Slot Conn. B][... no RX or TX ...][On-Air Slot Conn. A][On-Air Slot Conn. B] ...
Node 2: [On-Air Slot Conn. A][           ... no RX or TX ...          ][On-Air Slot Conn. A][... no RX or TX ...] ...

The interval between slots of the same connection must be the same for nodes 1 and 2 and the start-time must also be the same (approximately at least, ususally there is some variance and a preamble 'ringing' which allows the receiver to lock on to the transmitter).

You now also have to (somehow) know who is transmitting and receiving in which slot (similar to how central and peripheral for BLE connections work) and also allow for some time which can be used to receive broadcasts and transmitt broadcasts (similar to how advertisements work).

This will put you on the way to re-implement BLE however, and I'm not sure that this is your intention.

Best wishes Daniel

Mohamed-GN commented 3 years ago

Thank you very much @siretty I know that it is sometime impossible to form a line, but suppose all distances are short enough to establish a connection is it always possible to form a line by adding some modification to the algorithm, also i knew from Marius that you are planning to make algorithm central (not all nodes start connecting together) is that going to be provided soon Best wishes Mohamed

siretty commented 3 years ago

Any help by a central entity which could provide hints, still requires a communication channel to the involved nodes. This means that the mesh would still have to be able to be established (be it suboptimal or not) and then - later on - receive hints about how to form a more optimal mesh.

Even then - it is hard to globally optimize the connections as it isn't even clear that connections which might be stable for some time, are actually always stable - imagine e.g. a heavy door which is usually open, but sometimes closed; a connection through that door would sometimes provide good connectivity, but might fail to connect entirely at other times.

The dynamic environment is where the 'suboptimal' nature of the algorithm actually shines, it doesn't always take the 'best' connection available at any given time, but over longer periods it generally converges to a stable mesh topology.

It's likely that we will not implement the central guidance in the near future. The idea has been floating around for some time, though and it is possible that we pick it up.

As a hint, if you want to develop an algorithm for line-topology search yourself - the problem is (imho) equivalent to the travelling salesman problem (TSP) with a particular metric for the path length (namely the maximum over all segment costs, instead of the sum over all segment costs). As far as I'm aware there are fast, approximate, centralized algorithms using stochastic methods - e.g. ant colony optimization (see e.g. this wikipedia article as an entry point - there are other methods as well).

Depending on how you run the optimization algorithm, some will be able to handle dynamic environments better than others.

Mohamed-GN commented 3 years ago

Thank you very much @siretty I will search for this problem, the best part of Fruitymesh is that is modular, so it is clear where changes to be made, maybe if i get good results i will share it with you in the future. Best wishes

bluerange-io / bluerange-mesh

Some questions about fruitymesh #189