22-01-2013, 01:07 PM
Shortest Path Finder In Wireless Ad-hoc Network
1Shortest Path Finder.pptx (Size: 231.02 KB / Downloads: 23)
Wireless Ad-hoc Network
Ad-hoc is a Latin word and it means “for this(purpose)”
A wireless ad-hoc network is a decentralized type of wireless network.
The network is ad-hoc because it does not rely on a pre existing infrastructure.
An ad hoc network typically refers to any set of networks where all devices have equal status on a network and are free to associate with any other ad hoc network devices in link range.
Ad-hoc networks can use flooding for forwarding the data.
Each node in the network act as a router, forwarding data packets for other nodes.
A single transmission by a node can be received by all nodes with in it’s range.
The network is self-organizing.
Nodes are able to detect the presence of other nodes and join them into the network.
The nodes don’t need to be of the same type(phone, PDA, laptop, sensor, etc.)
APPLICATIONS
The decentralized nature of wireless ad-hoc networks makes them suitable for a variety of applications where central nodes can't be relied on.
The presence of dynamic and adaptive routing protocols enables ad-hoc networks to be formed quickly.
Technical Requirements
An ad-hoc network is made up of multiple “nodes” connected by “links”.
Links are influenced by the node's resources and by behavioural properties , as well as by link properties .
The network must allow any two nodes to communicate, by relaying the information via other nodes.
A “path” is a series of links that connects two nodes.
Various routing methods use one or two paths between any two nodes; flooding methods use all or most of the available paths.
ADVANTAGES OF DIJKSTRA’S SHORTEST PATH ALGORITHM
Once it has been carried out you can find the least cost path to all permanently labelled nodes/devices.
Dijkstra's algorithm has an order of n2 so it is efficient enough to use for relatively large problems.
Maintain large network
Comparison
results from two algorithms agree
Bellman-Ford
calculation for node n needs link cost to neighbouring nodes plus total cost to each neighbour from s
each node can maintain set of costs and paths for every other node
can exchange information with direct neighbors
can update costs and paths based on information from neighbors and knowledge of link costs
Dijkstra
each node needs complete topology
must know link costs of all links in network
must exchange information with all other nodes