International Journal of Scientific & Engineering Research, Volume 3, Issue 2, February-2012 1

ISSN 2229-5518

Throughput Maximization in Wireless Mesh

Networks and its Applications

T.Nirmal Raj, G.Bhuvaneswari, S.Saranya

Abstract- Wireless mesh networks (WMNs) consist of mesh routers and mesh clients, where mesh routers have minimal mobility and form the backbone of WMNs. They provide network access for both mesh and conventional clients. This paper considers the interaction between channel assignment and distributed scheduling in multi-channel, multi radio Wireless Mesh Networks (WMNs). Recently, a number of distributed scheduling algorithms for wireless networks have emerged. Due to their distributed operation, these algorithms can achieve only a fraction of the maximum possible throughput. As an alternati ve to increasing the throughput fraction by designing new algorithms, we present a novel approach that takes advantage of the inherent multi-radio capability of WMNs. We show that this capability can enable partitioning of the network into subnetworks in which simple distributed scheduling algorithms can achieve 100% throughput. The partitioning is based on the notion of Local Pooling. Using this notion, we characterize topologies in which 100% throughput can be achieved distributedly with algo rithms, which characterized in Dijkstra and KBR (Key based routing) and also in this paper, we will discuss the applications of WMNs. Emerson process management comes under the industrial automation applications of WMNs using WirelessHart and Emerson’s smart wireless extreme applications. It is a secure and TDMA-based wireless mesh networking technology operating in the 2.4 GHz ISM radio band. Wireless HART is a newly developed industrial standard network by the Hart Communication Foundation (HCF), which is being currently replacing the existing HART network in the industries. The HART communication protocol is an open standard, master-slave token passing network protocol, where devices are connected over 4-20 mA analog loop. Process monitoring improving the overall efficiency of our plant, we can reduce costs and improve throughput.

Keywords: Wireless mesh networks, throughput, channel assignment, subnetwork, local pooling, Emerson process management and wirelessHart.

—————————— ——————————

1. INTRODUCTION

IN a mesh network, devices are connected with many redundant interconnections between network nodes. In a true mesh topology every node has a connection to every other node in the network.

Mesh topology
In WMNs, nodes are comprised of mesh routers and mesh clients. Each node operates not only as a host but also as a router, forwarding packets on behalf of other nodes that may not be within direct wireless transmission range of their destinations. A WMN is dynamically self-organized and self-configured, with the nodes in the network automatically establishing and maintaining mesh connectivity among themselves (creating, in effect, an ad hoc network). WMNs will be tightly integrated with the Internet, and IP has been accepted as a network layer protocol for many wireless networks including WMNs. However, routing protocols for WMNs are different from those in wired networks and cellular networks.
The main objective of this research is to maximizing the throughput in WMNs using shortest path routing algorithms and wireless HART. Wireless HART is a newly developed industrial standard network by the Hart Communication Foundation (HCF), which is being currently replacing the existing HART network in the industries.
This paper is used to maximize the throughput over the wireless mesh networks. The results of the algorithms (Dijkstra and KBR) shows in a graphical format, Compare to Dijkstra , KBR algorithm is best because it take less time , at the same time it will give accurate (100% throughput) result.
The main advantages of this study is to reduce the time and space complexity through network partitioning. The mesh routers are usually equipped with multiple wireless interfaces operating in orthogonal channels. Mesh routers are rarely mobile and usually do not have power constraints. The issues of channel allocation, scheduling, and routing in WMNs, assuming that the traffic statistics are given. Obtaining a centralized solution wireless network does not seem to be feasible, due to the communication overhead associated with continuously collecting the queue backlog information, and due to the limited processing capability of the nodes. On the other hand, distributed algorithms usually provide only approximate solutions, resulting in significantly reduced

IJSER © 2012 http://www.ijser.org

International Journal of Scientific & Engineering Research, Volume 3, Issue 2, February-2012 2

ISSN 2229-5518

throughput. Setting up a routing path in a very large wireless network may take a long time, and the end-to-end delay can become large. Furthermore, even when the path is established, the node states on the path may change. Thus, the scalability of a routing protocol is critical in WMNs.
We show that the multi-radio and multichannel capabilities of WMNs provide an opportunity for simple deterministic distributed algorithms to achieve high throughput. Mesh routers are usually equipped with multiple radios (transceivers) and can transmit and receive on multiple channels simultaneously. Hence, channels have to be allocated to the links and the transmissions on each link have to be scheduled to avoid collisions. By allocating different channels to different links, several non-interfering sub networks can be constructed which enable simple distributed scheduling algorithms to achieve 100% throughput. The network graphs satisfy Local Pooling, our approach is to partition of the network , such that each edge will be part and use different channel. Using either the Dijkstra algorithm and KBR algorithm enables a simple distributed scheduling algorithm to achieve the capacity region of the sub networks (i.e. achieve 100% throughput in the sub networks).
Applications of Wireless Mesh Network
 Broadband home networking
 Community and neighborhood networking
 Enterprising networking
 Metropolitan Area Networking (MAN)
 Transportation systems
 Building automation
 Industrial automation
 Health and medical systems
 Security and surveillance systems
In this research we will discuss about how Emerson is using wireless mesh network (WMN) in Industrial Automation system.
Most of the Industrial automation companies, they
spend a lot of money for cabling and wiring termination in the junction box and control panels. To reduce these cost, wireless network is used to control the plant and it is called wireless service in industrial automation. The technical authority will make decision to use wireless based on the following high level criteria in Industrial automation:
 Reduced engineering costs (including drawing and documentation)
 Reduced labor (field installation, commissioning, supervision)
 Reduced materials (terminations, junction boxes, wiring, cable trays/ conduits/ trunking, power supplies and control system components)
 Input/Output (I/O) capacity managements (each wireless Hart gateway essentially provides spare I/O capacity)
(Wireless HART- It is a wireless communication type between field instruments. Wireless Highway Addressable Transmission and Receiver used to communicate with control system device to field instruments).

Plant Management

The control network bridging and field data backhaul, to video process monitoring and plant surveillance, Emerson’s Smart Wireless technology puts valuable information within reach-easily and cost-effectively to give us better insights into what’s happening in our operation.
By improving the overall efficiency of our plant, you can reduce costs and improve throughput. Yet process variability can rob us of our desired efficiency. Emerson’s Smart Wireless help you easily and cost-effectively deploy the predictive intelligence needed to reduce variability and improve overall efficiency. Most plants can increase throughput by running closer to what the process and equipment are capable of, taking advantage of capacity previously hidden by less-than-optimum performance. The digital intelligence integrated into every level of PlantWeb architecture enables you to improve throughput. Improving throughput positions any organization for greater return and competitiveness, regardless of market condition. When capacity constrained, you can produce more with existing assets. When market-limited, you can achieve your target output with fewer operating units.

2. RELATED WORKS

Andrew Brzezinski and Gil Zussman [2008] et al [1] This paper considers the interaction between channel assignment and distributed scheduling in multi-channel multiradio Wireless Mesh Networks (WMNs). The topologies are used in order to develop a number of centralized channel assignment algorithms that are based on a matroid intersection algorithm. These algorithms pre- partition a network in a manner that not only expands the capacity regions of the subnetworks but also allows distributed algorithms to achieve these capacity regions and evaluate the performance of the algorithms via simulation and show that they significantly increase the distributedly achievable capacity region. We note that

IJSER © 2012 http://www.ijser.org

International Journal of Scientific & Engineering Research, Volume 3, Issue 2, February-2012 3

ISSN 2229-5518

while the identified topologies are of general interference
graphs, the partitioning algorithms are designed for networks with primary interference constraints.
Jianping song and deji chen [2008] et al [2] the study give an introduction to the architecture of WirelessHART and share their first-hand experience in building a prototype for this specification. And also they describe several challenges to tackle during the implementation, such as the design of the timer, network wide synchronization, communication security, reliable mesh networking, and the central network manager.
Ian F. Akyildiz and Xudong Wang [2005] et al [4] Wireless mesh networks (WMNs) consist of mesh routers and mesh clients, where mesh routers have minimal mobility and form the backbone of WMNs. They provide network access for both mesh and conventional clients. WMNs are anticipated to resolve the limitations and to significantly improve the performance of ad hoc networks, wireless local area networks (WLANs), wireless personal area networks (WPANs), and wireless metropolitan area networks (WMANs).
M. Alicherry and R. Bhatia [2006] et al [8] This study is the issues of channel allocation, scheduling, and routing in WMNs, assuming that the traffic statistics are given. In this paper, we study the issues of channel allocation and scheduling but unlike most previous works, we do not assume that the traffic statistics are known. Alternatively, we assume a stochastic arrival process and present a novel partitioning approach that enables throughput maximization in each partition by distributed scheduling algorithms

3. METHODOLOGY

I. Mesh Router.

The layout the network and its communication between the links are bi – directional and shows all possible matching which is static. The network shows available channels. When message passes in the form of packets from node to node , we use stable Schedule algorithm which takes maximum weight. We can consider the computation time. Different wireless technologies pose different constraints on the set of transmissions that can take place simultaneously. The model can be easily generalized to capture network graphs with directional links. In such a case, link (i, j) may interfere with different links than those link (j, i) interferes with. Accordingly, the interference graph will include a node for each directional link.

II. Channel Allocation

From the sub graphs , first we allocate all the channel . Then we allocate channel using the Channel Allocation algorithm .The main objective is to balance the number of edges across channels and to reduce the node degrees in each channel. The second contribution is the development of network partitioning (i.e. channel allocation) algorithms that generate sub networks with large capacity regions, while enabling distributed throughput maximization in each of the sub networks. To the best of our knowledge, this is the first attempt to study the algorithmic implications of Local Pooling.

III. Local Pooling


The sub graph is obtained from the sub networks network topology. We use greedy algorithms to remove the nodes (the longest queue). Then from the subnet partition , we get all possible and its edges and vertex. Under these constraints, the maximal weight independent set in the interference graph is equivalent to the maximal weight matching in the network graph. A maximal weight matching can be obtained in a distributed manner by the algorithm. For a network operating under primary interference constraints with a speedup of two (similar to allocating two channels to each link), a greedy maximal weight algorithm (implementable in a distributed manner) can guarantee at least the network stability region. We present three algorithms for improving the network capacity properties. Since the admissible region restricts the summed throughput of all edges incident on the same vertex in the network graph to 1, it is desirable to minimize the maximum vertex degree over the network graphs on each channel.

IJSER © 2012 http://www.ijser.org

International Journal of Scientific & Engineering Research, Volume 3, Issue 2, February-2012 4

ISSN 2229-5518

IV. Sub Networks

We analysis the sub graphs of the sub networks. Check the conditions and splits the sub graphs to set of vector depends on the degree .The algorithm BFS is used to search the all possible sub graphs and its distance and time. In terms of LoP(Local Pooling) conditions, we seek to partition the network edges into channels such that the interference graph in each channel satisfies OLoP(Overall Local Pooling). The OLoP requirement is extremely challenging to incorporate into an optimization algorithm that generates a channel allocation, because it seeks the SLoP(Sub graph Local Pooling) property for every sub graph on each channel.

V. Performance Evaluation

Here we are using Two Algorithms to find the shortest path among the networks. One is Dijkstra's algorithm and second one is KBR. We use both algorithm to find the BFS in terms of time consumption. Finally point in the figure for generated a sample path.

Application Of Wireless Mesh Network (Industrial

Automation)

WirelessHART is a Real-Time Mesh Network for Industrial Automation. Industrial Automation is a one type of wireless mesh network applications. Most of the Industrial automation companies, they spend a lot of money for cabling and wiring termination in the junction box and control panels. To reduce these cost, wireless network is used to control the plant and it is called wireless service in industrial automation.
WirelessHART is a cutting-edge standard for the wireless process industry (such as oil, gas, pharmaceutical, chemical
, pulp paper, power plant, and companies such as ABB, Emerson Process Management, Endress Hauser, MACTek, Pepperl Fuchs, Simens and more). This new standard provides a robust wireless mesh network protocol, and assists users with a quicker and smoother experience when operating their wireless technologies.
Performance of Dijkstra’s algorithm.

Performance of KBR algorithm


Graphical representation of Dijkstra’s and KBR

IJSER © 2012 http://www.ijser.org

International Journal of Scientific & Engineering Research, Volume 3, Issue 2, February-2012 5

ISSN 2229-5518

Block Diagram

Message

 Relax (u, v, w)

KBR (Key Based Routing)

Mesh

Router

Channel Channel allocation

Assignment

partition

Local pooling

KBR is a lookup method used in conjunction with
distributed hash tables (DHTs). While DHTs provide a method to find a host responsible for a certain piece of data, KBR provides a method to find the closest host for that data, according to some defined metric. This may not necessarily be defined as physical distance, but rather the number of network hops. KBR improves the efficiency of decentralized information retrieval in peer-to-peer networks.

Dijkstra’s Algorithm

Sub graphs

Sub networks

Dijkstra’s

& KBR

Performance evaluation

Our knowledge-based route finding can be described as
using knowledge about the road network to isolate the search and or to guide the problem solving. Two key types of knowledge used in the proposed approach are the knowledge of road types (e.g., minor roads, major roads, and expressways) and the knowledge that major roads and expressways naturally partition the whole network into many small areas or sub-networks. These two types of knowledge and some others are used to partition and to reorganize the whole network. An efficient search algorithm is employed to search for the best solution in the appropriate sub-networks rather than the whole network. Within this framework, we present three specific methods.
Dijkstra's algorithm solves the single-source shortest-path problem when all edges have non-negative weights. It is a graph search algorithm that solves the single-source shortest path problem for a graph with nonnegative edge path costs, producing a shortest path tree. This algorithm is often used in routing. It is a greedy algorithm and similar to Prim's Algorithm. For a given source vertex (node) in the graph, the algorithm finds the path with lowest cost (i.e. the shortest path) between that vertex and every other vertex.

DIJKSTRA (G, w, s)

 INITIALIZE SINGLE-SOURCE (G, s)
 S ← { } // S will ultimately contains vertices of final shortest-path weights from s
 Initialize priority queue Q i.e., Q ← V[G]
 while priority queue Q is not empty do
u ← EXTRACT_MIN(Q) // Pull out new vertex
 S ← S È {u}
// Perform relaxation for each vertex v adjacent to u
 for each vertex v in Adj[u] do
Each of these methods has its advantages and
disadvantages over the others, and is suitable for a different situation. Routing Consistency of Key-based routing (KBR) is Large key space and Routing to a destination close to a given key routings always reach the owner of the key.

Distributed Hash Table

Hash buckets are distributed across multiple machines Implements PUT(key, value) and GET(key) Structured P2P systems

Key-based routing

ROUTE (key, msg): sends a message to the node that is currently responsible for a given key. It Can be used to implement a distributed Hash Table
- Assign each node and each key an ID
- Each node knows about some number of other nodes
- Can efficiently “route” to nodes closer to any ID
- Use to implement things like distributed hash tables

IJSER © 2012 http://www.ijser.org

International Journal of Scientific & Engineering Research, Volume 3, Issue 2, February-2012 6

ISSN 2229-5518

4. CONCLUSION

In this paper we have applied Local pooling and partition in order to obtain results regarding the design of Wireless Mesh Networks. The application of BFS theories allows us to develop algorithms for pre-partitioning a mesh network into a number of high capacity sub networks such that in each of the sub networks can obtain 100% throughput. This paper primarily provides a theoretical contribution that lays the foundation for developing practical algorithms. Compare to Dijkstra algorithm KBR algorithm is best because it take less time , at the same time it will give accurate (100% throughput) result. And also in this research the reliability requirements in typical wireless industrial process control applications and in Emerson’s plant management improve the overall efficiency of our plant, using this we can reduce costs and improve throughput.

5. Future Enhancement

For example, a future research direction is to allow dynamic channel allocation. This will require to tailor the channel allocation algorithms for online and perhaps distributed operation.
In ongoing and future work, the Wireless Mesh Network deploys in a large-scale manufacturing factory, so that in future, it can evaluate the performance of Wireless mesh network management techniques in real industrial environments. Therefore, the technology will continue to look for more efficient approaches for constructing routing graphs and communication schedules to maximize the power saving in WirelessHART networks, and study their corresponding recovery mechanisms.

REFERENCES

[1] Brzezinski, A.; Zussman, G.; Modiano, E.; Fidelity Investments, Boston, MA “Distributed Throughput Maximization In Wireless Mesh Networks Via Pre-Partitioning”, Networking, IEEE/ACM Transactions on dec’08

[2] Jianping Song; Song Han; Mok, A.K.; Deji Chen; Lucas, M.; Nixon, M.; Dept. of Comput. Sci., Univ. of Texas at Austin, Austin, TX “WirelessHART: Applying Wireless Technology in Real-Time Industrial Process Control” Real-Time and Embedded Technology and Applications Symposium, 2008. RTAS '08. IEEE

[3] P. Chaporkar, K. Kar, X. Luo, and S. Sarkar, “Throughput and fairness guarantees through maximal scheduling in wireless networks,” IEEE Trans. Inform. Th., vol. 54, no. 2, Feb. 2008

[4] I. F. Akyildiz, X. Wang, and W. Wang, “Wireless mesh networks: a survey,” Computer Networks, vol. 47, no. 4, pp. 445–487, Mar. 2005..

[5] J. Dai and B. Prabhakar, “The throughput of data switches with and without speedup,” in Proc. IEEE INFOCOM’00, Mar. 2000.

[6] S. Ramanathan and E. L. Lloyd, “Scheduling algorithms for

multihop radio networks,” IEEE/ACM Trans. Netw., vol. 1, no. 2, pp.

166–177, Apr. 1993.

[7] X. Wu and R. Srikant, “Regulated maximal matching: a distributed scheduling algorithm for multi-hop wireless networks with nodeexclusive spectrum sharing,” in Proc. IEEE CDC-ECC’05, Dec.

2005.

[8] M. Alicherry, R. Bhatia, and L. E. Li, “Joint channel assignment and routing for throughput optimization in multi-radio wireless mesh networks,” IEEE J. Select. Areas Commun., vol. 24, no. 11, pp. 1960–

1971, Nov. 2006.

[9] G. Zussman, A. Brzezinski, and E. Modiano, “Multihop local

pooling for distributed throughput maximization in wireless

networks,” in Proc. IEEE INFOCOM’08, Apr. 2008.

[11] A. Dimakis and J. Walrand, “Sufficient conditions for stability of longest queue first scheduling: second order properties using fluid limits,” Adv. Appl. Probab., vol. 38, no. 2, pp. 505–521, June 2006.

[12] A. Brzezinski and E. Modiano, “Greedy weigthed matching for

scheduling the input-queued switch,” in Proc. CISS’06, Mar. 2006.

[13] A. Adya, P. Bahl, J. Padhye, A. Wolman, and L. Zhou, “A multi- radio unification protocol for IEEE 802.11 wireless networks,” in Proc. Broadnets’04, Oct. 2004.

[14]M. Kodialam and T. Nandagopal, “Characterizing the capacity region in multi-radio multi-channel wireless mesh networks,” in Proc. ACM MOBICOM’05, Sep. 2005.

[15] E. Modiano, D. Shah, and G. Zussman, “Maximizing throughput in wireless networks via gossiping,” in Proc. ACM SIGMETRICS’06, June 2006.

[16] http://www.emersonprocess.com/home/

AUTHORS PROFILE

T.Nirmal Raj M.Sc,. Mphil working as an Senior Assistant Professor in the Department of Computer Science and Applications in Sri Chandrasekharendra Saraswathi Viswa Mahavidyalaya, Enathur, Kanchipuram, Tamil Nadu. He has published more than 5 Papers in National, International journals and conferences. His research interest lies in the area of Network. mailto: tnirmalrajcse@gmail.com

G.Bhuvaneswari Mphil, Research Scholar in the

Department of Computer Science & Applications in

IJSER © 2012 http://www.ijser.org

International Journal of Scientific & Engineering Research, Volume 3, Issue 2, February-2012 7

ISSN 2229-5518

SCSVMV University, Enathur, Kanchipuram. She received

the degree in Master of Computer Science from Madras University in 2010. She has presented 1 papers in National conference & participated many National and International Conferences. Her interested area in research is Network. mailto: bhuvanagan@gmail.com

S.Saranya Mphil, Research Scholar in the Department of Computer Science & Applications in SCSVMV University, Enathur, Kanchipuram. She received the degree in Master of Computer Science from Madras University in 2010. She has presented 2 papers in National conference & participated many National and International Conferences. Her interested area in research is Network. mailto: sarandhana889@gmail.com

IJSER © 2012 http://www.ijser.org