how to find Shortest path from source to destination in wireless sensor networks using matlab?

12 visualizaciones (últimos 30 días)
Among all the paths available from source to destination, I need to find the shortest path between source and destination....For example,in an area of 500*500 i have deployed 10 nodes randomly.considering 1st node as source and 10th node as destination now,I need matlab code for finding the optimized route from node1 to node10..can anyone please help??
  3 comentarios
Walter Roberson
Walter Roberson el 10 de Sept. de 2022
x = randi(500, 1, 10);
y = randi(500, 1, 10);
xy = [x; y].'
xy = 10×2
64 312 388 29 449 326 360 230 335 482 284 261 410 101 137 308 336 204 168 26
D = squareform(pdist(xy))
D = 10×10
0 430.1918 385.2545 307.1482 319.9078 225.8340 405.2616 73.1095 292.6568 304.3222 430.1918 0 303.1996 202.9409 456.0899 254.2440 75.2861 375.2892 182.5623 220.0205 385.2545 303.1996 0 130.9084 193.2149 177.3415 228.3550 312.5188 166.2919 411.0487 307.1482 202.9409 130.9084 0 253.2370 82.0792 138.3510 236.2478 35.3836 280.1428 319.9078 456.0899 193.2149 253.2370 0 226.8083 388.3117 263.5906 278.0018 485.6182 225.8340 254.2440 177.3415 82.0792 226.8083 0 203.6566 154.3308 77.1557 262.0706 405.2616 75.2861 228.3550 138.3510 388.3117 203.6566 0 342.6047 126.8267 253.3555 73.1095 375.2892 312.5188 236.2478 263.5906 154.3308 342.6047 0 224.5373 283.6988 292.6568 182.5623 166.2919 35.3836 278.0018 77.1557 126.8267 224.5373 0 244.7611 304.3222 220.0205 411.0487 280.1428 485.6182 262.0706 253.3555 283.6988 244.7611 0
G = graph(D)
G =
graph with properties: Edges: [45×2 table] Nodes: [10×0 table]
p = shortestpath(G, 1, 10)
p = 1×2
1 10
Shortest path is just to go directly from the beginning to the end.
This will always be the case unless:
  • you have range limitations; or
  • you have blocked paths; or
  • you have non-euclidean paths: due to reflections and different materials, direct paths might lead to traversing paths with slower signal transmission rates, and indirect paths might hypothetically travel routes that have higher signal transmission rates
%range limit
D(D > 250) = 0;
G1 = graph(D)
G1 =
graph with properties: Edges: [22×2 table] Nodes: [10×0 table]
p = shortestpath(G1, 1, 10)
p = 1×4
1 8 9 10

Iniciar sesión para comentar.

Respuesta aceptada

Walter Roberson
Walter Roberson el 24 de Mzo. de 2018
First construct a connection matrix with distances between nodes. Then use graph() or digraph() to build a graph object. You can then use shortestpath() to find the route between nodes.
Note that if you use euclidian distances and your graph is fully connected, then the shortest path is always direct from source to destination. Shortest path algorithms are for the case of noneucludian costs or the case where the graph is not fully connected.
An example of a noneucludian cost would be if there is a partly transparent obstacle such as a tree in some path that causes the energy requirements for that path to rise faster than the square of the distance. A full blockage such as concrete would prevent a path from being used. Reflections off of metal can have odd effects and can even provide better than euclidian energy costs if the reflection acts to focus a spreading signal.
Pure Euclidean costs also assume that there is an indefinitely large energy budget to transmit with, or that there is an indefinitely sensitive receiver with no noise. If these are not true then the graph will not be fully connected and a shortest path algorithm helps.

Más respuestas (2)

Matt J
Matt J el 16 de Sept. de 2014

Junaid Qadir
Junaid Qadir el 24 de Mzo. de 2018
You can use the Euclidean distance formula to find the nearest neighbor node.

Categorías

Más información sobre Networks en Help Center y File Exchange.

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!

Translated by