الگوریتم مسیریابی توازن بار برای شبکه های مش بی سیم چند کاناله A load-balancing routing algorithm for multi-channel wireless mesh networks

Wireless mesh networks (WMNs) are multi-hop wireless networks with mesh connectivity. A WMN is composed of gateway nodes, mesh routers and mesh clients. Mesh routers form the mesh backbone with low mobility and usually each router is equipped with several wireless interface cards (Akyildiz and Wang, 2005; Pathak and Dutta, 2011). The IEEE 802.11 medium access control (MAC) (IEEE 802.11 Working Group, 2003) protocol is often used in WMNs where routers work with one channel. For single channel, the peak data rate at the MAC layer for IEEE 802.11 a/g (IEEE 802.11 Working Group, 2003) is 54Mbps, and the actual throughput for the application layer is almost half (Raniwala and Chiueh, 2005). Interference from adjacent nodes also decreases the transmission rate. Therefore, the problem of increasing network capacity is important. Since the physical layer protocol of IEEE 802.11 a/b/g (IEEE 802.11 Working Group, 2003) provides multiple orthogonal channels, the wireless interface cards of mesh routers can operate in multiple orthogonal channels simultaneously which can increase the capacity and performance of WMNs. In multi-channel WMNs, the network load increases with the number of users. Some routers, especially the ‘hot’ routers, may become the congested node and the links connected with them will become the bottleneck links. When the congested nodes exist, the probability of long time delay and packets loss increase significantly. However, the routing protocols used for WMNs, such as AODV (Perkins et al., 2003) and HWMP (Kim et al., 2012), do not consider the influence of hot nodes. Once the congested state is formed, it will be maintained until the load reduces or the new paths set up. Therefore, a major challenge in the design of routing protocol in multi-channel WMNs is to balance network load between routers to avoid congestions. For WMNs, the problem of load-balancing can be divided into gateway load-balancing and router loadbalancing (Juan et al., 2012; Tokito et a1., 2009). By current traffic conditions, gateway load-balancing chooses routers associated with gateways and router load-balancing chooses the path for flows. Recently, researchers have proposed load-balancing routing (LBR) for multi-channel WMNs (Narayan, 2013; Le et al., 2009; He et al., 2012; Jung et al., 2009; Wellons and Xue, 2011; Singh and Lobiyal, 2012). A new cross layer routing metric proposed in Narayan (2013) aims at estimating the interference, load and delay of a link efficiently to improve the performance. A LBR protocol for multi-radio mesh network (LBM) (Le et al., 2009) is designed to balance traffic load among channels, in which the route metric of LBM is composed of traffic load and interference. The load-balanced connected dominating set (LBCDS) problem is discussed (He et al., 2012), in which constructing an LBCDS and load-balanced allocating dominatees to dominators are investigated simultaneously. A distributed potential-field-based anycast routing scheme (Jung et al., 2009) can aid in balancing load among gateways and mesh nodes. Wellons and Xue (2011) develops a performance-ratio robust routing formulation for multi-radio, multi-channel networks that exploit traffic demands that fall into a predicted region. Singh and Lobiyal (2012) propose an algorithm by using an adaptive back-off strategy to realise load balance among sensor nodes and achieve fairly uniform cluster head distribution across the network. The routing protocol proposed in this paper is based on router load-balancing and addresses the issues to minimise the load difference among routers. The network model for multi-channel WMNs with single gateway is presented. Based on this model, the LBR algorithm is proposed, including a link allocation algorithm and load-balancing route-selection algorithm. The link allocation algorithm allocates all links to channels to minimise network interference degree. After that, a load-balancing routeselection algorithm is proposed to decrease the load difference among routers. Using the LBR algorithm, the new flows will select the route with low interference and low load. Therefore, the traffic load is distributed uniformly as much as possible and the performance of network is improved. The rest of this paper is organised as follows. In Section 2, we present the network model for WMNs. After that, link allocation algorithm is proposed in Section 3. In Section 4, load-balancing route-selection algorithm is proposed. In Section 5, simulation results are presented and analysed. In Section 6, we summarise the main results of the paper.