International Journal of Scientific & Engineering Research, Volume 5, Issue 9, September-2014 1253

ISSN 2229-5518

Shortest Path Exploration in Wireless Mesh

Networks Improved Energy Efficiency

1 K.Kumaravel Ph.D,(Research Scholar), Dept of Computer Science, Govt, Arts

College(Autonomous) Coimbatore, India

K_kumara_vel2001@yahoo.com

2 Dr.A.Marimuthu, Associate Professor, Dept of Computer Science, Govt Arts

College(Autonomous), Coimbatore, India

Mmuthu2005@yahoo.com

3 Mincy Sabu M.Phil (Research scholar), Dept of Computer Science, Dr.N.G.P.

Arts & Science College, Coimbatore , India mincysabu@gmail.com

Abstract: In wireless mesh network the nodes are dynamically self-organized and self- configured networks create a changing topology and keep a mesh connectivity to offer Internet access to the users. The shortest path problem is one of the most fundamental problems in networking. This problem can be solved by many techniques and algorithm. In this paper we find the shortest path by using the fittest nodes in the network. By using the fittest node we can send the packets to the destination without packet loss, delay in packets. Average end to end delay is decreased by increasing bandwidth and the results are shown.

Keywords: Wireless mesh networks, shortest path, packet loss, delay in packets, average end to end delay.

INTRODUCTION:

A wireless mesh network (WMN) is a mesh network created through the connection of wireless access points installed at each network user's locale. Each network user is also
a provider, forwarding data to the next node.
The networking infrastructure is decentralized and simplified because each node need only transmit as far as the next node. Wireless mesh networking could allow people living in remote areas and small businesses operating in rural neighborhoods to connect their networks together for affordable Internet connections.In a full mesh topology, every node communicates with every other node, not just back and forth to a central router. In another variation, called a partial mesh network, nodes communicate with all nearby nodes, but not distant nodes. All communications are between the clients and the access point servers. The client/server relationship is the basis for this technology [1].
A wireless mesh network (WMN) is a communications network made up of radio nodes organized in a mesh topology. Wireless mesh networks often consist of mesh clients, mesh routers and gateways. The mesh clients are often laptops, cell phones and other wireless devices while the mesh routers forward traffic to and from the gateways which may, but

International Journal of Scientific & Engineering Research, Volume 5, Issue 9, September-2014 1254

ISSN 2229-5518

need not, connect to the Internet. The coverage area of the radio nodes working as a single network is sometimes called a mesh cloud. Access to this mesh cloud is dependent on the radio nodes working in harmony with each other to create a radio network. A mesh network is reliable and offers redundancy. When one node can no longer operate, the rest of the nodes can still communicate with each other, directly or through one or more intermediate nodes. Wireless mesh networks can self form and self heal. Wireless mesh networks can be implemented with various wireless technology including 802.11, 802.15, 802.16, cellular technologies or combinations of more than one type.
The principle is similar to the way packets travel around the wired Internet— data will hop from one device to another until it reaches its destination. Dynamic routing algorithms implemented in each device allow this to happen. To implement such dynamic routing protocols, each device needs to communicate routing information to other devices in the network. Each device then determines what to do with the data it receives
— either pass it on to the next device or keep it, depending on the protocol. The routing algorithm used should attempt to always ensure that the data takes the most appropriate (fastest) route to its destination [2].
The shortest path problem is the problem of finding a path between two vertices (or nodes) in a graph such that the sum of the weights of its constituent edges is minimized. This is analogous to the problem of finding the shortest path between two intersections on a road map: the graph's vertices correspond to intersections and the edges correspond to road segments, each weighted by the length of its road segment.The shortest path problem can be defined
for graphs whether undirected, directed,
or mixed. It is defined here for undirected graphs; for directed graphs the definition of path requires that consecutive vertices be connected by an appropriate directed edge.
Two vertices are adjacent when they are both incident to a common edge. A path in an undirected graph is a sequence of

vertices such that is adjacent to for . Such a path is called a path of length from to . (The are variables; their numbering here relates to their position in the sequence and needs not to relate to any canonical labeling of the vertices.)Let be the edge incident to both and . Given a real-valued weight function , and an undirected (simple) graph , the shortest path from to is the path (where and ) that over all

possible minimizes the
sum When each edge in the graph has unit weight or , this is equivalent to finding the path with fewest edges.
The problem is also sometimes called the single-pair shortest path problem, to distinguish it from the following variations:
• The single-source shortest path problem, in which we have to find shortest paths from a source vertex v to all other vertices in the graph.
• The single-destination shortest path problem, in which we have to find shortest paths from all vertices in the directed graph to a single destination vertex v. This can be reduced to the single-source shortest path

International Journal of Scientific & Engineering Research, Volume 5, Issue 9, September-2014 1255

ISSN 2229-5518

problem by reversing the arcs in the directed graph.
• The all-pairs shortest path problem, in which we have to find shortest paths between every pair of vertices v, v' in the graph[3].

The most important algorithms for solving this problem are:

• Dijkstra's algorithm solves the single-source shortest path problem.
• Bellman–Ford algorithm solves the single- source problem if edge weights may be negative.

• A* search algorithm solves for single pair shortest path using heuristics to try to speed up the search.

• Floyd–Warshall algorithm solves all pairs shortest paths.
• Johnson's algorithm solves all pairs shortest paths, and may be faster than Floyd– Warshall on sparse graphs.
• Viterbi algorithm solves the shortest stochastic path problem with an additional probabilistic weight on each node.
There are lots of Algorithm used to find the shortest path in the network from source to destination. In this paper we find the shortest path using the fittest node in the network to overcome the packet loss and the delay in sending packets. We also overcome Average end to end delay by increasing the bandwidth.

RELATED WORKS:

Recent researches have dealt with mainly three techniques: highway hierarchy, bit vector, and transit node routing [4–8]. The highway hierarchy is similar to ours and the ordinary layer network approach. The layer network approach considers the set of edges which are frequently used when going to farther
destinations and uses the network as a highway.
However, it has no assurance of optimality; hence it definitely differs from more recent algorithms despite it likely being the most popular method in modern car navigation systems
Suppose that an edge e is included in the shortest path from v to u, and an endpoint of e is the kvth closest vertex to v , and the other endpoint is the kuth closest vertex to u. If both kv and ku are larger than a threshold value h, we call e a highway. . The highway hierarchy method [6,7] constructs a highway network composed of highway edges. We start by executing Dijkstra’s algorithm on the original network, then go to the highway network after h steps. The highway network is usually sparser than the original network; thus the computational time is shortened. Moreover, by constructing highway network upon highway network recursively, the computational time becomes much shorter. In contrast to the layer method, the highway hierarchy method does not lose optimality. Short preprocessing time is also an advantage of this method.
The highway hierarchy method finds the edges common to the middle of the shortest paths. In contrast to this, bit vector finds a common structure to the shortest paths between a vertex and a region. When the source vertex is close to the region including the target vertex, the edges to be examined become many, and hence computational time increases. By increasing the number of the regions q , the bit vector can increase the efficiency instead of increasing memory usage. Moreover, the preprocessing of the bit vector needs to solve the all pairs shortest paths problem, and thereby it takes a long time.
The third method is transit node routing [8]. In the preprocessing phase, it selects the transit vertices such that for any pair of distant vertices, at least one transit vertex is included in

International Journal of Scientific & Engineering Research, Volume 5, Issue 9, September-2014 1256

ISSN 2229-5518

their shortest path. Then, we compute all pairs shortest paths of the transit vertices, and these are stored as a data structure. When we execute the Dijkstra’s algorithm, we can directly move from a transit vertex near the source to a transit vertex near the destination. In practice, every node has a transit node in its neighbors; thus we can find the shortest path in a short time (usually in O(1) time).[9]

SHORTEST PATH EXPLORATION:

The idea behind the shortest path exploration is the optimum route (OR) is that route between a source node and a destination, providing the following specifications:
• We create multi-hop neighbor from source to destination
• The fittest node is found using the higher energy in the network.
• The node which has more energy will be found and those nodes are used to find the shortest path from source to destination.
• It is the shortest route between the source and destination.
• The same destination, unless the joint node is one of the Destination’s neighbors. (No joint node (JN) or joint link (JK)).
The shortest path problem is the problem of finding a path between two vertices (or nodes) in a graph such that the sum of the weights of its constituent edges is minimized. The shortest path problems are solved by different algorithms and techniques. In this paper we find the shortest path algorithm using the fittest node in the given mesh networks from source to destination. The fittest node is found using the higher energy in the network. The node which has more energy will be found
and the nodes are used to find the shortest path from source to destination.
The idea behind using the fittest node we can overcome the packet loss, delay in sending packets due to less energy in nodes. We increase the bandwidth for the nodes to overcome the Average end to end delay. As the bandwidth increases the average end to end delay is decreased.

IMPLEMENTATION:

In Wireless mesh networks we find the shortest path using the fittest node in the network. The fittest node is calculated using the higher energy in the networks. The node which has more energy will be found and those nodes are used to find the shortest path from source to destination. By using the fittest node we can overcome the packet loss, delay in sending packets due to less energy in nodes. We increase the bandwidth for the nodes to overcome the Average end to end delay. As the bandwidth increases the average end to end delay is decreased. The implementation results is shown in fig.1

Fig:1 Decrease in Average end to end delay

International Journal of Scientific & Engineering Research, Volume 5, Issue 9, September-2014 1257

ISSN 2229-5518

CONCLUSION:

The shortest path problem is one of the most fundamental problems in networking. This problem can be solved by many techniques and algorithm. In this paper we find the shortest path by using the fittest nodes in the network. The node which has more energy will be found and those nodes are used to find the shortest path from source to destination. By using the fittest node we can overcome the packet loss, delay in sending packets due to less energy in nodes. We increase the bandwidth for the nodes to decrease the Average end to end delay. As the bandwidth increases the average end to end delay is decreased.

REFERENCE:

[1]searchnetworking.techtarget.com/definition/w ireless-mesh-network
[2]http://en.wikipedia.org/wiki/Wireless_mesh_
networrk
[3]en.wikipedia.org/wiki/Shortest_path_problem
[4].Goldberg, A.V., Kaplan, H., Werneck, R.: Reach for a*: efficient point-to-point shortest path algorithms. In: Proceedings of the Workshop on Algorithm Engineering and Experiments (ALNEX). (2006) 129–143
[5].Kohler, E., Mohring, R.H., Schilling, H.: Acceleration of shortest path and constrained shortest path computation. In:Experimental and Efficient Algorithms. Volume 3503 of Lecture Notes in Computer Science., Springer (2005)
126–1
[6].Sanders, P., Schultes, D.: Highway hierarchies hasten exact shortest path queries. In: Proceedings of the 13th European Symposium on Algorithms. Volume 3669 of Lecture Notes in Computer Science., Springer (2005) 568–57
[7]Sanders, P., Schultes, D.: Engineering

Highway hierarchies. In: Proceedings of the

14th European Symposium on Algorithms.
Volume 4168 of Lecture Notes in Computer
Science., Springer (2006) 804–816
[8]Bast, H., Funke, S., Matijevic, D., Sanders, P., Schultes, D.: In transit to constant shortest- path queries in road networks.In: Proceedings of the Workshop on Algorithm Engineering and Experiments (ALNEX). (2007) 46–5
[9]www.nii.ac.jp/TechReports/08-004E.pdf
[10]christine e. Jones, krishna m. Sivalingam, prathima agrawal and jyh cheng chen, A Survey of Energy Efficient Network Protocols for Wireless Networks. Wireless Networks 7, 343–
358, 2009 Kluwer Academic Publishers.
Manufactured in The Netherlands
[11] K.Kumaravel, Mincy Sabu, Dr.A Marimuthu, “Optimal Routing Algorithm Used In Wireless Mesh Networks For Energy

Efficiency” International Journal Of Engineering

Science And Research Technology ,Vol. 3 Issue
1 - January, 2014
[12] A. Salkintzis and P.T. Mathiopoulos (Guest Eds.), The Evolution of Mobile Data Networking, IEEE Personal Communications
3(2) (2000).
[13] I. F. Akyildiz and X. Wang, "A Survey on Wireless Mesh Networks," IEEE Commun. Mag., vol. 43, no. 9, Sept. 2005, pp. S23-S30. (Pubitemid 41638080)