Represent the shortest path from all nodes to the sink.

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

[Image Analyst]

I assume you need to minimize the totaled length of all connecting lines? Also, I've tagged it as homework (like I assume you probably should have done).

[Sunil]

Yes, for the optimal path, the total length of all the connecting lines must be minimum.

I did try from my end, before posting.

Thank you,

Sunil Kumar

[Image Analyst]

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.

[Sunil]

I have the following toolboxes. Please let me know, if I need some other tool, inorder to achieve this.

MATLAB

Curve Fitting Toolbox

Database Toolbox

Signal Processing Toolbox

Statistics Toolbox

Attaching the code for reference. Note, Main-shorttestpath.m is the main program

Thanks

Sunil Kumar

Answer 1

[Mamali]

Hi Sunil ,

I think you can run Dijkstra in your topology. see the link below for more info

http://www.mathworks.co.uk/matlabcentral/fileexchange/5550-dijkstra-shortest-path-routing

[Sunil]

I am finding it challenging to find the solution using Dijkstra, since I don't have the segment details. All I have is the location details(pixels) of nodes. How do I go ahead with this? Appreciate an high level logic on this.

Thanks a lot!

Answer 2

[Image Analyst]

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.

[Sunil]

I am finding it challenging to find the solution using Travelling Salesman problem, since I don't have the segment details. All I have is the location details(pixels) of nodes. How do I go ahead with this? Appreciate an high level logic on this.

Thanks a lot!