Represent the shortest path from all nodes to the sink.
1 view (last 30 days)
Show older comments
The below is an example of various nodes (marked in 1 to 10) in WSN. All the nodes are expected to be sending data to the sink(marked in brown). How do I compute the optimum path and connect them using lines from all the nodes to the sink?
Note:
1. Note, its not that each node, would directly send the data to the Sink, rather it may send the data to its neighboring node and then finally to the sink.
2. The number of nodes and its position is dynamic.
Appreciate an earlier response on this. Would be great, if you could give a code snippet as well.
Thanks in advance,
Sunil Kumar
4 Comments
Image Analyst
on 24 May 2014
What did you try exactly? Attach your code with the paper clip icon. It may elicit more responses if people have something to start with. Also let us know what toolboxes you've bought, particularly if you have any of the optimization toolboxes.
Answers (2)
Mamali
on 25 May 2014
Hi Sunil ,
I think you can run Dijkstra in your topology. see the link below for more info
Image Analyst
on 25 May 2014
This is a fairly hard problem I think. You could have anywhere from one line segment to 10 line segments. If you have just one, so that all nodes are connected, then this is the traveling salesman problem http://en.wikipedia.org/wiki/Traveling_salesman_problem. So you have to solve that, but you also have to solve for cases where you have 2, 3, ...10 paths to see if maybe their total path lengths are shorter (though I could be wrong - maybe 2 to 10 paths are guaranteed to be longer - I don't know). And for any of them, say 3 paths, there are tons of possible permutations of what nodes are on what path. Sorry but I'm not good enough at optimization to give you advice on how to solve it.
See Also
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!