Expected Path Bandwidth Based Efficient Routing Mechanism in Wireless Mesh Network

Abstract

Wireless mesh networks (WMNs) are being developed actively and deployed widely for a variety of applications, such as public safety, environment monitoring, and citywide wireless Internet services. Considering inter- and intra-flow interference ,optimal routing in wireless mesh networks is a challenge. A new routing metric, expected path bandwidth (EPBW), where the varying link rate (due to wireless channel quality) and the dynamic link load (considering the inter- and intra-flow interference) have been considered to estimate EPBW accurately which solves the routing problem occurred due to inter- and intra-flow interference. Also based on the EPBW, a distributed routing protocol for WMNs, aiming to maximize network throughput is also proposed. The design of the same in various scenarios is done to evaluate the protocol performance extensively using NS- 2 simulation. Simulation results show that the proposed protocol and metric can substantially out-perform the state-of-the-art routing metrics, such as expected transmission count (ETX) and expected transmission time (ETT), and previous routing protocols including AODV and DSDV.

Index Terms

Wireless Mesh Network, Signal Noise Ratio, Expected Path Bandwidth, Cross Layer Routing Protocol

INTRODUCTION

Wireless Mesh Network (WMN) consists of several radio nodes which are arranged in the mesh topology. The components of wireless mesh networks are mesh routers, mesh clients, gateways. Even though one node present the WMN could not operate for long time, the other nodes in the network can communicate directly or through some intermediate nodes. Wireless mesh network is an extraordinary kind of wireless ad-hoc network. WMN can offer dynamic and cost efficient connectivity in certain places. In WMN each and every node is act as router (i.e.,) the source node send the data to the destination directly or through some intermediate nodes. That intermediate nodes boost up the received signal as well as choose the next forwarding node based on its knowledge about the WMN.

Generally, the WMN have the constant topology apart from addition of node to the network or failure occurs in the network. As the mesh routers and clients are present in the wireless mesh network, the WMN have hybrid structure of network. The routing protocols used in ad-hoc network are applicable for WMN but the WMN specifically have the hybrid routing protocols. In hybrid routing protocol, the traffic flow is handled by utilizing proactive routing scheme. The hybrid routing protocol of WMN did not consider the security issues. In this paper, our proposed scheme will provide better security when selecting the route between two nodes.

RELATED WORK

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. The integration of WMNs with other networks such as the Internet, cellular, IEEE 802.11, IEEE 802.15, IEEE 802.16, sensor networks, etc., can be accomplished through the gateway and bridging functions in the mesh routers. Mesh clients can be either stationary or mobile, and can form a client mesh network among themselves and with mesh routers. 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). They are undergoing rapid progress and inspiring numerous deployments. WMNs will deliver wireless services for a large variety of applications in personal, local, campus, and metropolitan areas. Despite recent advances in wireless mesh networking, many research challenges remain in all protocol layers. This paper [1] presents a detailed study on recent advances and open research issues in WMNs. System architectures and applications of WMNs are described, followed by discussing the critical factors influencing protocol design. Theoretical network capacity and the state-ofthe- art protocols for WMNs are explored with an objective to point out a number of open research issues. Finally, testbeds, industrial practice, and current standard activities related to WMNs are highlighted.

This paper [2] presents the expected transmission count metric (ETX), which finds high-throughput paths on multi-hop wireless networks. ETX minimizes the expected total number of packet transmissions (including retransmissions) required to successfully deliver a packet to the ultimate destination. The ETX metric incorporates the effects of link loss ratios, asymmetry in the loss ratios between the two directions of each link, and interference among the successive links of a path. In contrast, the minimum hop-count metric chooses arbitrarily among the different paths of the same minimum length, regardless of the often large differences in throughput among those paths, and ignoring the possibility that a longer path might offer higher throughput.

This paper describes the design and implementation of ETX as a metric for the DSDV and DSR routing protocols, as well as modifications to DSDV and DSR which allow them to use ETX. Measurements taken from a 29-node 802.11b test-bed demonstrate the poor performance of minimum hop-count, illustrate the causes of that poor performance, and confirm that ETX improves performance. For long paths the throughput improvement is often a factor of two or more, suggesting that ETX will become more useful as networks grow larger and paths become longer.

Recently, the IEEE has standardized the 802.11 protocol for Wireless Local Area Networks. The primary medium access control (MAC) technique of 802.11 is called distributed coordination function (DCF). DCF is a carrier sense multiple access with collision avoidance (CSMA/CA) scheme with binary slotted exponential backoff. This paper [3] provides a simple, but nevertheless extremely accurate, analytical model to compute the 802.11 DCF throughputs, in the assumption of finite number of terminals and ideal channel conditions. The proposed analysis applies to both the packet transmission schemes employed by DCF, namely, the basic access and the RTS/CTS access mechanisms. In addition, it also applies to a combination of the two schemes, in which packets longer than a given threshold are transmitted according to the RTS/CTS mechanism. By means of the proposed model, in this paper we provide an extensive throughput performance evaluation of both access mechanisms of the 802.11 protocol.

Provides a comparative analysis of various routing strategies that affect the end-to-end performance in wireless mesh networks. [4]First improve well-known link quality metrics and routing algorithms to enhance performance in wireless mesh environments. We then investigate the route optimality, i.e., whether the best end-to-end route with respect to a given link quality metric is established, and its impact on the network performance. Network topologies, number of concurrent flows, and interference types are varied in our evaluation and we find that a non-optimal route is often established because of the routing protocol’s misbehavior, inaccurate link metric design, interflow interference, and their interplay. Through extensive simulation analysis, we present insights on how to design wireless link metrics and routing algorithms to enhance the network capacity and provide reliable connectivity.

The first version IS a straightforward Implementation of the basic algorithm. It is mainly presented to illustrate the method used. This version generates cliques in alphabetic (lexicographic) order. The second version is derived from the first and generates cliques in a rather unpredictable order in an attempt to minimize the number of branches to be traversed. This version tends to produce the larger cliques first and to generate sequentially cliques having a large common intersection. The detailed algorithm for version 2 is presented here [5].

Description of the algorithm version I. Three sets play an important role in the algorithm. (1) The set compsub is the set to be extended by a new point or shrunk by one point on traveling along a branch of the backtracking tree. The points those are eligible to extend comp sub i.e. that are connected to all points in compsub, are collected recursively in the remaining two sets. (2) The set candidates is the set of all points that will in due time serve as an extension to the present configuration of compsub. (3) The set not is the set of all points that have at an earlier stage already served as an extension of the present configuration of compsub and are now explicitly excluded.

ROUTING PROTOCOL DESIGN

A. Route Discovery

In EPBWR, route discovery operate in an on-demand fashionto reduce the overhead. When a source node S needs to senddata to a destination node D, it initiates the route discoveryprocess. It first broadcasts a routing request message (RREQ). When a neighboring node receives the RREQ, it firstmeasuresthe SNR, and use the smoothed SNR to estimate the link qualityand calculate the EBW of the link according to the monitoredlink idle probability. Then it checks whether there exists a cliquein the path from the source node to itself, and calculates theEPBW of the path and broadcasts again until the destination receives the RREQ.

B. Route Calculation

As the EPBW is determined by the cliques along the path and the available bandwidth of each clique, a conflict graph is helpful to identify the cliques. To construct the conflict graph Gv, each link belongs to path Pv is converted to a vertex in Gv. and two vertexes are connected with an edge if they conflict with each other. The well-known Bron - Kerbosch’s algorithm and Cliquebandwidth functions are used to perform the route calculation.Our proposed distributed route. Discovery algorithm is given in Algorithm 1.

C. Route Maintenance

After route discovery, the source successfully obtains a path to deliver data. As the wireless network changes dynamically, the path throughput may become lower or even worse, the path may fail; or, a better path may occur. In these cases, a new suitable path should be found.

D. Route Recovery

Routing failure most likely occurs during the following two processes. One is the routing information loss when it is sent back from the destination to the source, and the other is due to disconnection during the data transferring process. When a RREQ reaches the destination, it will return a RREP with the path vector and the EPBW to the source. Although the links in WMNs are not symmetrical, the reverse path from the destination to the source is typically available, although the reverse path throughput can be different. During the data transferring process, when the path becomes disconnected, the node who fails to transmit the packet will return a route error message (RERR) to the source. The source node then initiates a new RREQ message to find a new path.

EVALUATION AND ANALYSIS

We implemented the EPBWR protocol in NS2 network simulator and designed experiment under one scenario with 49 nodes in thenetwork. The default parameters used in the simulation are listed in Table I. The modulation schemes are adaptively changed among DBPSK, DQPSK, CCK55, CCK11, according to the measured SNR value. Once the path throughput decreases exceeding the threshold of 20%, or otherwise every 20 s an UREQ message is sent out. Channel Quality and Load Aware Routing delivery ratio, packet loss ratio, delay are investigated and compared with previous routing protocol.

In this project we are taking 7 X 7 nodes in located at a square- grid in a 1000m_1000m area as shown in fig.2. The neighboring node distances in both horizontal and vertical directions are 100 m. The date sends from node 46 to node 4 and there are interference flows with CBR traffic between intermediate node in the horizontal and vertical direction.

We compare the throughput of different routing protocols in scenario 1 is shown in Fig. 3(A). The EPBWR outperforms other three protocols with stable and higher throughput. The throughputs of DSR and AODV decrease fast at the presence of interference traffic. DSDVperforms poorly in such scenario too. The comparison in throughput shows that EPBWR has better adaptively than the other protocols.

In fig. 3(B) show that loss rate comparison of EPBWR with other routing protocols. The loss rate is very low loss compare between other protocols. DSDV is higher loss than the AODV. DSR is very high loss.EPBWR is low delay compare with other protocols. The AODV is much high delay then DSR. The DSDV is also higher delay. Due to higher delay, the packet loss is increased more and more so that we cannot achieve the expected throughput. In channel quality and

load aware routing is achieve the expected throughput at very low loss and delay as show in 3(C) and also compare throughput comparison as shown in Table II.

CONCLUSION

In this paper, we have presented a new expected path bandwidth metric called EPBW, considering the physical channel quality, the impact of inter- and intra-flow interference. We have further proposed a distributed routing protocol EPBWR (Expected Path Bandwidth source Routing) using the proposed metric EPBW (Expected Path Bandwidth) and implemented it in NS-2. The simulation results have shown the proposed protocol and the previous routing protocols including AODV, DSDR, and DSR. In the future, we will extend this work to improve load balance, combine end-to-end delay into the metric to meet the QoS requirements of users. How to use redundant route and caching method to improve the robustness remains an open issue worth further investigation.

References

I. F. Akyidiz, X. Wang, and W. Wang, ”Wireless Mesh Networks: A Survey,” Computer Networks, Vol 47, pp. 445-487, 2005. D. De Couto, D. Aguayo, J. Bicket, and R. Morris, ”A highthroughput path metric for multi-hop wireless routing,” WIRELESS NETWORKS, vol. 11, pp. 419-434, 2005. G. Bianchi,”Performance analysis of the IEEE 802.11 distributed coordination function,” Selected Areas in Communications, IEEE Journal on, vol. 18, pp. 535-547, 2000. S. Kim, O. Lee, S. Choi, and S. Lee, ”Comparative analysis of link quality metrics and routing protocols for optimal route construction in wireless mesh networks,” Ad Hoc Networks, vol. 9, pp. 1343-1358, 2011. C. Bron and J. Kerbosch, ”Algorithm 457: finding all cliques of an undirected graph,” Commun. ACM, vol. 16, pp. 575-577, 1973. The network simulator ns-2, 2009. http://www.isi.edu/nsnam/ns.