# State-aware re-configuration model for multi-radio wireless mesh networks.

AbstractJoint channel assignment and routing is a well-known problem in multi-radio wireless mesh networks for which optimal configurations is required to optimize the overall throughput and fairness. However, other objectives need to be considered in order to provide a high quality service to network users when it deployed with high traffic dynamic. In this paper, we propose a re-configuration optimization model that optimizes the network throughput in addition to reducing the disruption to the mesh clients' traffic due to the re-configuration process. In this multi-objective optimization model, four objective functions are proposed to be minimized namely maximum link-channel utilization, network average contention, channel re-assignment cost, and re-routing cost. The latter two objectives focus on reducing the re-configuration overhead. This is to reduce the amount of disrupted traffic due to the channel switching and path re-routing resulted from applying the new configuration. In order to adapt to traffic dynamics in the network which might be caused by many factors i.e. users' mobility, a centralized heuristic re-configuration algorithm called State-Aware Joint Routing and Channel Assignment (SA-JRCA) is proposed in this research based on our re-configuration model. The proposed algorithm re-assigns channels to radios and re-configures flows' routes with aim of achieving a tradeoff between maximizing the network throughput and minimizing the re-configuration overhead. The ns-2 simulator is used as simulation tool and various metrics are evaluated. These metrics include channel-link utilization, channel re-assignment cost, re-routing cost, throughput, and delay. Simulation results show the good performance of SA-JRCA in term of packet delivery ratio, aggregated throughput and re-configuration overhead. It also shows higher stability to the traffic variation in comparison with other compared algorithms which suffer from performance degradation when high traffic dynamics is applied.

Keywords: Multi-Radio Wireless Mesh Networks, State-Aware Re-configuration, Joint Channel Assignment and Routing

1. Introduction

Wireless mesh network (WMN) is one of the key technologies, which will dominate wireless networking in this decade [1]. It helps to realize the network connectivity anywhere, anytime with simplicity and low cost. The wireless mesh network is predicted to be one of the key components in the converged networks of the future, providing flexible high bandwidth wireless backhaul over large geographical areas. Wireless mesh networks consist of two kinds of network elements, namely, mesh routers (MRs) and mesh clients (MCs). Mesh routers form the backbone of the network and connected with each other through the backhaul links. On the other hand, mesh clients are the network users that generate traffic in the network. When more mesh clients are connected to wireless mesh network, there is a requirement to improve the transport capacity of the backbone. In this purpose, the Multi-Radio multi-Channel architecture is introduced to wireless mesh networks based on IEEE 802.11 technology (see Fig. 1). In such a case, mesh routers can exploit the availability of multiple radios to simultaneously transmit and/or receive on several orthogonal frequency channels i.e. 12 channels in 802.11a and 3 channels in 802.11b. This architecture increases the throughput by reducing the interference on backhaul links. Channel assignment (CA) [2-5] in a multi-radio WMN environment consists of assigning channels to the radio interfaces in order to achieve efficient channel utilization and minimize interference. However, channel assignment and routing configuration are interdependent issues and both influence the network performance. This is since channel assignment and routing determine the contention and interference level over the backhaul wireless link. Therefore, finding the joint configuration of both is considered as main challenges in multi-radio WMN (MR-WMN) and several joint solutions for channel assignment and routing were proposed and evaluated in the literature [6-16]. Some other issues is also been studied in the literature to improve the performance of multi-hop wireless networks such as developing routing metrics [17-19] , multi-channel MAC protocols [20], power and topology control [21-23].

In this paper, we propose a multi-objective optimization model for joint channel and routes reconfiguration in MR-WMNs. In comparison with existing models that only optimize the network throughput and fairness based on user's demands distribution, our model accounts the reconfiguration overhead when channel and routes re-configured due to user's traffic dynamics in the network. In particular, the proposed model find the configuration that optimally distribute the backhaul traffic load over links and channels to reduce the contention/interference level over backhaul links in conjunction with reducing the overhead imposed by applying this new configuration. This model will significantly minimize the service disruption occurs with existing joint approaches applied in scenarios with high traffic dynamics.

The contributions of this paper threefold. First, we propose a multi-objective re-configuration model with four objective functions to configure channels and routes in MR-WMNs; moreover the proposed model is the first model to consider the re-configuration problem for joint channel assignment and routing. Second, we propose a centralized greedy heuristic algorithm to solve the joint re-configuration model. This is since the re-configuration model includes channel assignment which is proven to be an NP-hard problem [6]. Third, the performance of the proposed algorithm is evaluated and results shows good performance under different degree of traffic dynamics.

The rest of the paper is organized as follows. Section 2 provides an overview of related research. The re-configuration problem and the mathematical formulation of the problem is presented in Section 3. Section 4 introduces the proposed re-configuration algorithm, called SA-JRCA (State-aware Joint Routing and Channel Assignment), to solve the reconfiguration model. Section 5 presents the performance metrics and the simulation results. Finally, Section 6 concludes the paper.

2. Related Work

_The channel assignment approaches in MR-WMNs are surveyed in many works in the literature such as [24-28] and the joint approaches of channel assignment and routing are surveyed in [29-31]. The joint configuration of channels and routes in MR-MC WMNs in the literature such as [6, 13] are mainly based on centralized load-aware solutions where configuration of routes and channels are obtained for a given distribution of traffic load demands across the network. The heuristic algorithm proposed in [6] iterates over channel assignment and routing steps to optimize the network cross-section good-put. This is obtained by matching the links' expected loads to the links' virtual capacities. A mathematical formulation of the problem as Mixed-Integer Linear Programming (MILP) is presented in [7]. Maximizing the difference between the effective capacities and the traffic loads on links reduces the contention. The MILP can be solved for small-scale networks using commercial software such as CPLEX [32]. However, to solve real-world large-scale networks an Iterated Local Search (ILS) algorithm is proposed [32]. The binary routing variable in MILP is relaxed to simplify the computational cost. Then based on the obtained values of the routing parameters routes between source-destination pairs are found.

Further improvement to the ILS algorithm is proposed by [9] to overcome the capacity issues of the single channel assumption in the initial stage. In same context, [33] extends the work of [6] to support directional antenna. Work in [8] optimizes the network performance by adjusting the link's transmission rates and by integrating link's transmission rates as a part of the joint configuration problem. A greedy heuristic algorithm with layer-2.5 forwarding paradigm to forward the Internet traffic is also proposed. The forwarding scheme does not maintain routing tables; instead, a static flow rate is assigned to each links that forms the basis of forwarding criterion and updating the link cost information locally. A Markov chain model is developed to evaluate and determine the optimum value of different parameters. In [34], the problem is decomposed into a number of sub-problems equal to the number of mesh routers and each sub-problem has an ILP formulation with objective function similar to [7] and with local constraints. The nodes are grouped into subsets defined as network crew and visited based on some ranking function. Branch-and-cut method is used to solve each sub problem. A new metric based on contention on links, routes length and interference is used to select the best solution over all network crew and ranking.

A genetic algorithm is developed in [11] to find an optimal configuration of channels and routes in the planning stage. The algorithm involves solving a linear program model of multichannel routing as a fitness function. The linear programming optimization function is maximizing network capacity and total traffic from/to the Internet. In [35], the configuration problem for dynamic TCP flows is formulated as Mixed-Integer Nonlinear Program with the objective of maximizing the proportional fairness. The number of re-assigned channels is constrained in the formulation and a greedy heuristic routing and channel assignment algorithms proposed with flow rate allocation. The work also is extended to consider link transmission rate allocation [36]. In [12], an oblivious routing is used to find routes that optimize the worst-case network performance over a set of possible traffic demands. The proposed solution starts by dividing the time intervals into time slots with each configuration bearing separate time intervals. The traffic demands are characterized at time slots as a convex region in n-dimensional space, where n represents the number of mesh routers. The traffic profile is partitioned into a predefined number of slots with the objective of minimizing the convex hull volume over all partitions using hill-climbing algorithm. The nonlinear programing problem is transformed to linear programming problem by finding the dual formulation of the slave LP problem of the original problem. Using LP solver to solve the routing problem flow-link-channel variable is determined. This is followed by channel assignment step.

In addition, there are also some research papers [10, 34, 35, 36, 38] aiming to solving the problem with Link scheduling in the field of wireless mesh networks. This is with the assumption that synchronous coordination is supported at link levels. These works can be classified based on their channel assignment types to static channel assignment as in [13, 37, 38] or dynamic channel assignment as in [39-41]. Firstly, in static channel assignments channels are allocated to radios and links for relatively long period of time. In [13] the joint channel assignment, routing and scheduling problem is formulated as ILP and then it relaxed to LP with objective of maximizing the achievable scaling factor of demands. The traffic demand obtained from solving the LP is then scaled down to ensure feasible link scheduling. In [37], the problem also formulated as LP problem and is solved in two steps where additional constraints are added to the problem based on the solution obtained from the first step. In [38], the link load is first estimated by distributing the new load of each flow on all available predefined paths based on hop count. A heuristic algorithm is proposed for handling the channel assignment problem. Then a greedy heuristic algorithm schedules the link to time slots for meeting the expected load on each link. Thus, flow allocation is computed for determining the amount of traffic to be routed on each path with the objective of maximizing the amount of traffic routed for each flow. Secondly, dynamic channel assignment works assume that radio interfaces are capable of switching their channel in a small time compared with the time slots. Thus, wireless links can operate on different channels at different time slots. Due to the fast development of the hardware technology, neglected channel switching delay will be achieved in the near future [42]. However, with the current hardware channel switching still produce considerable overhead and delay [43].

Recently, there are also some exploration literatures [35, 36, 38, 43-46] for re-configuration problem in MR-WMN. A heuristic algorithm proposed in [43] to deal with the channel re-assignment problem. The algorithm starts from the previous channel assignment and find the new one with bounding the number of re-assigned channel to a predefined parameter. The work extended in [41] with improvement in the link priorities and by integrating the link transmission rate control. In similar way, [35] also constrains the total number of re-assignments. In [45] the previously assigned channels are tested first on links and then reassigned if this assignment reduces the interference level and does not violate the radio-node constraints. In [47], the migration from one channel configuration to the new one is modeled as an assignment problem and the migration that reduces the number of links that require channel switching is selected. In [38], the channel switching overhead is considered in calculating the expected throughput for each channel and the channel with the highest expected throughput is assigned to the link. Channel switching problem in cognitive network is studied in [48]. However, the problem considered here is slightly different than the previous one, where the optimization objective is to reduce the frequency distance between the current and the successive channels, as secondary users might be forced to switch their channels to avoid interference with primary users' activities. In [49], flow re-routing problem is studied and a three-step heuristic algorithm is presented. The number of re-routed flows is restricted to a predefined threshold. The routes are obtained using Dijkstra algorithm with a cost metric is calculated for each link and penalty constants are multiplied with that cost if the link was inactive links in the old configuration.

In summary, the majority of proposed solutions in literature have considered the configuration for either planning stage or by considering stable distribution over long period of time. This may not be the case for real life scenarios, where the traffic is characterized to be highly dynamic due to user mobility. Therefore, an efficient algorithm is needed to adapt the variation in the traffic load. Although, some of the papers have considered re-configuration problem to accommodate the traffic dynamics for either channel assignment or routing, considering the advantage of the joint configuration of routes and channels is not well studied in the literature. Thus, this paper introduces a re-configuration model in 802.11-based MR-WMNs that jointly solve these two inter-dependent configurations and has good adaptability to the traffic dynamics.

3. Problem formulation

3.1 Re-configuration problem description

The re-configuration process results in channel switching in several wireless links and radios. According to [50], the delay involved in channel switching is approximately 80 microseconds. According to [51], the switching delay in 802.11a is around 328 microseconds, which is equal to the time of transmission of 1024 byte in a rate of 25 Mbps using the same technology. Furthermore, Li et al. [52] show that this latency can rise, up to scale of seconds due to the effect of upper layer protocols. The authors in [53] presented an experimental study on the interruption associated with channel switching, which is in order of 10 seconds with the use of OLSR protocol due to fast link failure update in channel switching. Thus, the authors have recommended a modification to the existing routing protocol, which can reduce the overhead associated with channel switching. This can be concluded as, synchronization issues can still cause channel-switching overhead even with centralized routing paradigm that involves no link status update. This is due to the inability of radios on a link to achieve perfectly the same switching time and links might goes down for a period of time. Similar to channel re-assignment, re-routing can results in a higher packet drop and traffic disruption to active traffic flows, where some of on-the-fly packets cannot find the routes to their destinations. The previous works have avoided this problem by maintaining a fully connected topology with a number of predefined paths between senders and receivers [38, 47] or by using source routing scheme as in [38, 44, 47]. A fully connected network topology requires allocating channels to all logical links. This can affect the channel diversity where several adjacent links will be forced to assign same channel to maintain radio-node constraint. Therefore, the developed model must also control the re-routing overhead that can cause intolerant disruption especially for real-time multimedia applications.

3.2 network model

We consider MR-WMN based on 802.11 technology as an access network. MR-WMN consists of stationary mesh routers that aggregate traffic from mobile mesh clients within their coverage areas. These mesh routers form a wireless backbone is used to forward the Internet traffic to/from the mesh clients to gateways in multi-hop fashion. Gateway is a mesh router with a wired link to the wired network. Multiple radios are installed at mesh routers where each one can be tuned to operate on one of non-overlapped channels (3 non-overlapped channels in 802.11b and 12 non-overlapped channels in 802.11a). Wireless links between mesh routers and clients are assumed to have no interference with backhaul links. A single gateway scenario is considered here.

The backbone of the network is modeled as directed graph G(V, E) with V nodes and E logical links. The V denotes the set of all mesh routers and E denotes the set of backhaul links between these routers. A logical link exists for a pair of mesh routers if both are in the transmission range of each other. The logical links are presented by edges in G(V, E) while the routers are presented by the nodes. C denotes the set of the orthogonal channels. Let f [member of] FL presents a downward traffic flow directed from the gateway node to a mesh router (sink node) and let [PHI](f) presents the traffic load (data rate) for flow f [member of] FL. [PHI](f) can be obtained at the gateway node. A single path is assigned to each flow to avoid the out-of-order problem. Thus, only inbound Internet traffic is accounted since it is the dominated traffic load of Internet users' traffic. Interference modeled as two-range model [54], each radio interface has two ranges (transmission and interference ranges) and communication is possible between any two radios if both reside within the transmission range of each other. Two radios may interfere if they reside within the interference range of each other and use same communication channel. Interference range ([R.sub.T]) is assumed to be double of the transmission range ([R.sub.I]). Furthermore, all wireless links are bidirectional and for a successful transmission on a link all radio interfere with the transmitting interface, or the receiving interface must be silent during the transmission. For each logical link [e.sub.ij] a set of potential interference links [F.sub.ij] [subset] E is defined based on the interference model and both [e.sub.pq] [member of] [F.sub.ij], [e.sub.ij] interfere if they operate on same channel.

3.3 Mathematical formulation

We formulate the state-aware joint configuration as a multi-objective optimization model with four objective functions. Solving this optimization model leads to obtain flow-path assignment and channel-interface-link assignment that optimize the objective functions. The first two objectives are to minimize the channel utilization, interference level and contention throughout the network. However, simply minimizing the links utilization may increase the re-configuration overhead and thus conflict with the third and fourth objectives, which aim to minimize the flow re-routing and channel re-assignment overhead. The problem is formulated as multi-objective mixed integer nonlinear programing, where all constraints and objective functions are linear except the second objective function, which is nonlinear. The model is described with the notations in Table 1. The state-aware problem are formulated as follows:

Min [Util.sub.max] (1)

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (2)

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (3)

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (4)

Subject to:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (5)

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (6)

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (7)

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (8)

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (9)

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (10)

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (11)

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (12)

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (13)

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (14)

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (15)

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (16)

The objective function (1) is to minimize the maximum link-channel utilization [7] over all links and channels. This improves the network throughput by minimizing the maximum congestion over all links. However obj (1) only does not guarantee reducing contention over the network since the channel-utilization for several links may approach [Util.sub.max]. Therefore, (2) is introduced to minimize another proposed metric referred as network average contention (NetCont). Objective (2) aims to minimizing the average contention over all active links, not only the maximum utilization value. The next two objectives seek to minimize the channel reassignment cost (3) and routing re-assignment cost (4). The channel re-assignment cost (Cost-CA) is calculated as the amount of disrupted traffic due to channel switching, which is the total loads on links requires channel switching on at least one of their ends. Finally, the routing reassignment cost (Cost-RO) defined as the summation of the route re-assignment cost of over all the flows.

The re-route cost of a flow is calculated as the number of mesh routers, which has been excluded, in the new configuration, from the forwarding set of that flow multiplied by the flow's rate. The set of constraints is introduced as follows: Constraint (5) is the radio interface constraint, where number of channels assigned to a MR must be less than the number of interfaces at that node. Furthermore, a channel can only be assigned to one interface at any node since assigning the same channel to multiple interfaces has no advantage. Constraints (6),(7) require that to have an active link between two nodes both must have a common channel assigned on one of their interfaces. Constraints (8), (9) are the topology constraints that ensure that each logical link can only be mapped to at most one channel to reduce the complexity of the routing layer. Constraints (10), (11) are the flow-topology constraints to ensure that only links with traffics will be signed as an active links. Flow conservation at each mesh router is ensured in (12). Where the net difference between the outgoing flow and the incoming flow is equal to 1 at the gateway node and is equal to -1 at the destination and zero otherwise. Path hop count is constrained as in (13) to avoid long paths. (14) represents the aggregated traffic load over a link on a specific channel. (15) represent the utilization of a link on a channel as defined in [43]. The link capacity in calculation is depends on the transmission rate of the 802.11 standard and the size of the upper layers packets and the length of the link. For the sake of simplicity, we assume that all links have a same bandwidth and equal transmission rate. The maximum link-channel utilization over all links is constrained as in (16), and a large positive constant [beta] is added to the right side in (16) to ensure that link-channel utilization is only considered for active links.

The re-configuration problem illustrated in this work is an NP-hard problem. This is since the simpler channel assignment problem has been proved by [6] as an NP-hard problem, thus, an efficient algorithm is required to approximate the solution. Therefore, a heuristic algorithm called State-Aware Joint Routing and channel Assignment (SA-JRCA) is proposed in next section in order to find sufficient solutions to the model.

4. Proposed state-aware re-configuration algorithm

This section describes the proposed re-configuration algorithm. The gateway is in charge of monitoring the inbound traffic arriving from the Internet to each mesh router and predefined reconfiguration policy could trigger the re-configuration process based on the traffic condition. Then new configuration is applied on all mesh routers at the same time. Meanwhile, mesh routers must synchronize their clocks to avoid extra overhead at the re-configuration step. Furthermore, the Address Resolution Protocol (ARP) also has to be disabled to avoid the lockup process associated with ARP. The buffered packets at each router are re-routed to the updated output interfaces and some packets might dropped at this stage if the updated configuration does not include route to their destination.

4.1 Algorithm description

The proposed algorithm identifies the set of active links and assigns channels to these links only. This is to avoid affecting the channel diversity across the network, since assigning channels to all links can force some neighboring links to assign same channel and this increase the contention and interference level. Algorithm (1) shows the steps of SA-JRCA algorithm. The algorithm starts with step one where flows (gateway to mesh router) are sorted in increasing order based on the number of candidate paths to each flow. Then, a path is assigned to each flow and initial load on each active link is obtained. The solution is further improved in step 2 by reroute some flows to reduce the value of a cost function. At this step active links with their associated traffic load is obtained and channels are assigned to active links. This is followed by physical to logical channel mapping to reduce the channel re-assignment cost.

Algorithm 1 SA-JRCA algorithm Input: logical topology, traffic load, Interference info Output: channel and routes configuration Step1: initial routing configuration Compute the candidate paths to each flow using DFS. Sort the set of flows F based on the number of candidate pats increasing order for each f [member of] F do Check all candidate paths to route f Assign the path that results the lowest cost function (17) end for Step2: routing adjustment while (iteration < max iteration no.) Let FL be the set of flows travers the link with the highest link-utilization for each f [member of] FL, p [member of] f's candidate paths do Compute cost function when p is used to route f end for pick the pairs (p, f) with the lowest cost and assign p to f (*) end while Step3: channel assignment Assign channels to active links using CA (algorithm 2) Map logical channel to physical channel to achieve objective function (3) (*) CA is executed after each path selection Algorithm 2 Channel Assignment Algorithm Input: network graph, interference info, load on active links Output: channel assignments to active links Sort active links in decreasing order based on their load for each e [member of] active links, c [member of] channels do Calculate Contention-Cost (18) if c is assigned to e. /* to conserve radio-interference constraint some channels on some links and radios may require to re-assigned different channels as [6] */ Assign the channel with the lowest Contention-Cost to e end for

In initial routing stage, the set of candidate paths from the gateway node to each sink mesh router is obtained using depth first search (DFS) algorithm. The DFS algorithm is executed once for each flow and paths are recalculated only after each topology changes. The DFS algorithm recursively call depth first search function, and only valid paths (path with length less than a constant number from their shortest path hop count) from the gateway to the sink mesh router are stored in the candidate path set. The flows then are sorted in increasing order based on their available number of candidate paths. The candidate paths for each flow are checked one by one to select the one with the lowest cost to route that flow. The cost function for a given configuration is calculated as in equation 17:

Cost Function = Cost-Contention + [beta]. Cost-RO (17)

Cost-Contention = NetAvgCont + [Util.sub.max] (18)

where, [beta] is the route-variation weighting parameter and Cost-Contention is calculated as in (18). Cost-RO is included in the cost function to ensure that the re-routing is considered in the first and second steps of the algorithm. The value of [beta] specifies how much the new configuration is restricted with the old paths. Hence, a higher [beta] leads to a less route variation. In contrast, lower value of [beta] makes the route selection more flexible and less restricted by the previous routes. The active link's set is updated after each flow-path assignment. The algorithm iterates for each flow until a path is assigned to each flow. Channel assignment algorithm (algorithm 2) is called to assign a channel for active links with an objective to reduce the Cost-Contention in the network. Firstly, active links are sorted and visited in a decreasing order, based on the amount of traffic load carried on each link. For each link, all channels are tested and the channel leads to the least Cost-Contention is assigned to that link. Due to radio-constraints, the number of channels assigned to the links incident in one node cannot exceed the number of interfaces at that node. Further links re-assignment may be required if the radio constraints is violated. Flows are visited and the paths are assigned in an increasing order where earlier assignments do not account for the later ones. The algorithm looks for possible improvement by adjusting the routes of some flows and then routing adjustment phase is executed. Links with highest channel-link utilization are selected and re-routing flows that can cause improvement to the cost function is performed. The algorithm iterates for predefined number of iterations (fixed to 3 in the simulation scenarios) or when there is no further improvement. At the end of the routing adjustment stage, the set of active links with the associated load is obtained. Then channel assignment algorithm assigns logical channels to all active links. This is followed by logical to physical channels (actual channels) mapping to reduce the channel re-assignment cost objective (3) by reducing the overhead of the channel switching process. The channel mapping problem can be modeled as an assignment problem, and the problem can be represented as weighted bipartite graph and hence it turn to be finding the minimum weight matching (Fig. 2). The weight associated with assigning a physical channel j to the logical channel i is calculated as the procedure below:

Procedure physical to logical channel mapping Input: logical channel assigned to active links, previously assigned channels to MRs Output: physical channel assignments to active links Let [??], CH be the sets of logical and physical channels. Let SCH(n) be the set of previously assigned channels to the radios on MR n. /*Calculation of the weight on each edge of the bipartite graph*/ for every ([ch.sub.i], [ch.sub.j]) [member of] [??] x CH do [W.sub.ij] = 0 for every e(a,b) [member of] active links do if [ch.sub.i] is the logical link assigned to e then if [Ch.sub.j] [??] LCH(a)v [Ch.sub.j] [??] LCH(b)then Add the traffic load on link e to the [w.sub.ij] end for end for Find the minimum weight matching using Hungarian algorithm Replace logical channels with physical channels

Then, Hungarian algorithm [55] is applied to obtain the optimal mapping that results the lowest possible channel re-assignment overhead.

5. Evaluations and Simulation

This section describes the evaluation and simulation of the proposed scheme. Firstly, the performance metrics are introduced to evaluate the performance of the proposed scheme. Then, the simulation system comprehensively evaluated the SA-JRCA by comparing it with some related proposals in terms of various performance metrics.

5.1 Performance evaluation metrics

Several performance metrics are considered to evaluate the performance of the proposed algorithm. This metrics includes average network throughput, packet delivery ratio (PDR), average packet drop (PD) caused by re-routing. In addition, the Jains fairness index [56] is also used to measure the fairness among different flows. The Jain's fairness index (JFI) for packet delivery ratio is calculated by the equation:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (18)

where PDR(f) is the achieved packet delivery ratio of flow f and N is the total number of flows. The Jean's fainess index value ranges from 1/N (the worst fairness) and 1(the best value is when all flows experiance the same PDR). Other metrics such as maximum channel-link utilization ([Util.sub.max]), network average contention (NetAvgCont), normalized channel re-assignment (Cost-Chan) and re-routing costs (Cost-Rout) are also evaluated. Cost-Chan is normalized to the highest possible Cost-Chan (when all active links in the network disrupted due to channel reassignment process) and Cost-Rout is normalized to the highest possible Cost-Rout (when all flows in the network select a totally different routes after the re-routing process).

5.2 Generation of traffic load sequences

A dynamic download traffic load is used to evaluate the proposed scheme. In generating a correlated traffic sequences the total load on the network is fixed to L. The simulation time is divided into several equal time intervals and the network load equally divided to all flows at the beginning, i.e. 20 flows with total load of 4Mbps, the rate assigned to each flow is 200Kbps. For each subsequence time interval, rate is increased by v*L/|F| for 50% of a randomly selected flows, where |F| is the total number of flows and v is a parameter to control the traffic variation percentage. The remaining flows decreases their rates by v*L/|F|. The total network load is conserved in this way. Increasing the value of v generates a higher dynamic traffic sequences.

5.3 Simulation setup

This section developed a simulation system, which was built on the NS2 simulator with multichannel extensions. The proposed algorithm is compared with two works from literature, a heuristic channel re-assignment algorithm called MVCRA [46] and a centralized heuristic joint channel assignment and routing algorithm (refer here as JRCA) [6]. Since the number of reassigned channels in MVCRA is constrained to a predefined value, for comparison purpose we adjusted this value to be equal to the average number of re-assignments obtained from running SA-JRCA algorithm over all time intervals. Moreover, traffic load on backhaul links obtained from running SA-JRCA is also applied as input to MVCRA. On the other hand JCAR is used as a static configuration and it executed only once to obtain only one configuration over all time interval. The average rates of flows over the simulation time are used as input to JCAR. The number of flows is fixed to 20 flows for all simulations. The time of simulation is divided into 8 intervals of 30 seconds length. SA-JRCA and MVCRA are re-executed to adapt to traffic dynamics for each time interval but JRCA is executed only once. The grid topology is used in the simulation where multiple candidate paths are available to route each flow. A total of 49 MRs is used in the topology with a gateway node located in the middle. The gateway node equipped with 3 radio interfaces to overcome the bottleneck around the gateway. The number of interfaces on MRs is varies from 2 to 3.

The summary of the common simulation parameters, which has been used in all simulation scenarios, is presented in Table 2. Fig. 3 shows the grid topology with the gateway at the middle. The destination mesh routers for flows are the nodes highlighted by red color.

5.4 Simulation results and performance analysis

A set of simulation experiments is conducted to evaluate the proposed re-configuration algorithm (SA-JRCA). The performance first evaluated for 6 channels, 2 radio per node, [beta]= 1, L = 4 Mbps, and v = 40%. Fig. 4 shows that SA-JRCA has the lowest [Util.sub.max] and NetAvgCont, and the highest PDR over all time intervals followed by MVCRA and JCAR. In order to study the statistical dependence between both [Util.sub.max], NetAvgCont and network performance represented by PDR, Spearman's [rho] [57] has been used. The results show stronger negative correlation (value of -0.927) between PDR and [Util.sub.max] than NetAvgCont (value of -0.998). These results justify the use of the proposed contention metric in the cost function to better estimation of the network configuration quality. The lower performance of JCAR comes from its channel diversity problem, which increases the contention level over the network. The degradation of MVCRA performance comes from that adjusting the channels on some links can have a ripple effect that forces to a sequence of improper assignments due to radio-node constraints. On the other hand, SA-JRCA starts channel assignment process from scratch and this followed by channel mapping to reduce the channel re-assignment cost [Cost.sub.ch].

5.4.1 The impact of [beta] the route-variation weighting parameter

Minimizing the contention cost (equation 18) might conflict with minimizing the re-routing cost. The proposed algorithm need to trade-offs between these two conflicted objectives. This can be performed by introducing [beta] as route-variation weighting parameter. Simulation is run to study the effect of different value of [beta] on the performance. [beta] is varied from 0 (algorithm does not consider any constriction of flow re-routing) to a very large number (no re-routing is permitted). Simulation is conducted with following parameters: 3 radios per node, 6 channels, L = 4 Mbps, and v = 40%. Fig. 5, shows that impact of [beta] over normalized Cost-Rout, PD, average [U.sub.max]. The decreased number of PD when [beta] is increased is affected by many factors including the flows' rates, the paths length (hop-count), the interfaces' buffer size and the congestion level on links. On the other hand the network contention increased ([Util.sub.max] has increased from 0.43 to 0.6) when [beta] varied from 0 to a large number.

5.4.2 The impact of number of radios

The number of radios is one of the most critical factors influencing network performance and capacity in MR-WMNs. Simulations are conducted with different number of interfaces to study the performance. In the first simulation each mesh routers is configured with 2 interfaces, with total of 99 radios on the network. The number then increased to 3 interfaces per mesh router with total of 147. Other simulation parameters are as following: L = 4 Mbps, 6 channels, [beta]=1, and v = 40%. Fig. 6 shows the average NetAvgCont, average PDR, and normalized Cost-CA. The results show only slight improvement in SA-JRCA PDR when the number of radios increased. This is since SA-JRCA efficiently utilizes the available number of channels (6 channels) even with lower number of radios. On the other hand the performance of MVCRA is highly degraded with lower number of interfaces. This is due to ripple effect, which has higher impact to the reassignment process with lower number of radios. With less number of radios mesh routers has lower probability of having a common channel with their neighbors and this might invoke a sequence of uncontrolled re-assignments.

5.4.3 The impact of number of channels

The impact of the number of channels on the performance of SA-JRCS is studied in this section and simulation is conducted for this purpose with following parameters: 3 radios per MR, L = 5 Mbps, [beta]=1 and v = 40%. The NetAvgCont, average throughput, normalized Cost-CA and Jain's Fairness Index is obtained for each number of channels. The throughput increase is evaluated when number of channels increases from 5 to 9 channels is as follows (Fig. 7): SA-JRCA (from 3.826 Mbps to 4.85 Mbps), MVCRA (from 3.002 Mbps to 3.937 Mbps), and JCAR (from 2.467 Mbps to 2.901 Mbps). SA-JRCA shows also a higher average Jain's fairness index for PDR over different number of channels. The average end-to-end delay achieved by each algorithm is also evaluated. From Fig. 7 It can be seen that SA-JRCA achieves the lowest end-to-end delay compared with MVCRA and JCAR over different number of channels. SA-JRCA gets higher average end-to-end delay when number of channel is 5. This is because packet delivery ratio is only calculated for the successfully received packets and it ignores the dropped packets from its calculations. Hence, with lower number of channels (5 channels) both MVCRA and JCAR experience much higher rate of packet loss especially for flows with longer paths. Thus, most of the calculated end-to-end delay is for packets successfully received by mesh routers that are closer to gateway node which are relatively have less end-to-end delay compared to longer flows. The proposed SA-JRCA experiences less end-to-end delay compared to MVCRA and JCAR. The average end-to-end decreases from 0.079374 seconds (5 channels) to 0.03211 seconds (9 channels) for SA-JRCA. On the other hand JCAR experiences the highest average end-to-end delay. The end-to-end delay is decreased from 0.0648093 seconds to 0.060705 seconds for MVCRA when the number of channel is increased from 8 and 9.

5.4.4 The impact of traffic dynamics and network load

The purpose of the SA-JRCA is to accommodate the real-time traffic dynamics and balance the network load. SA-JRCA achieves the highest PDR and shows the lowest affection with respect to the amount of traffic variation when different level of traffic dynamics is applied. A simulation with 3 radios per MR, L = 6 Mbps, [beta] = 1, 6 channels and for traffic sequences generated with different load dynamic. As in Fig. 8 the slop of PDR of SA-JRCA, MVCRA and JCAR trend are -0.0005, -0.0307, and -0.0243 respectively when v varied from 10% to 50%. On the other hand, studying the performance of the proposed algorithm under different network load helps to understand the efficiency of utilizing the network resources. A simulation scenario is conducted for this purpose.

For each simulation, 2 radios per MR, L = 6 Mbps, 6 orthogonal channels, [beta] = 1, and v = 40% is considered. The average aggregated throughput achieved for each network load when network traffic load is increased from 2 Mbps to 6 Mbps shown in Fig. 8 As it can be seen from the result, SA-JRCA algorithm outperforms the other algorithms. When the total network load is fixed to 6 Mbps SA-JRCA, in average, delivers 77% of the total traffic while in average MVCRA and JCAR deliver 49.77% and 37.42% from the total traffic, respectively.

6. Conclusion

This paper addressed the re-configuration problem for MR-WMNs in order to resolve the channels and routes re-assignment in dynamic network traffic environment. We proposed a multi-objective optimization model aims to at finding a good network configuration while maintaining a low re-configuration overhead. In order to assess the quality of the network configuration, channels' utilization and the overall contention on the wireless links are measured. Moreover, a cost function for channel re-assignment and path re-routing is also presented. Then, we proposed a heuristic algorithm to solve the re-configuration model with a trade-off between the network configuration quality and re-configuration overhead. The proposed algorithm, called State-Aware Joint Routing and Channel Assignment (SA-JRCA), re-assigns the channels and routes with the awareness of the current network configuration, hence reduces the reconfiguration overhead. Simulation results shows that SA-JRCA could achieve efficient resources utilization even with less number of radio interfaces and channels. Furthermore, simulations also conducted with different degree of traffic dynamics and results shows that SA-JRCA achieves the highest packet delivery ratio and less affected by traffic dynamics degree in comparison to the benchmark works JCAR and MVCRA. In addition, integrating an association mechanism to our re-configuration model for better resource utilization and an optimal load distribution on the backhaul link will be of our interest in the future.

References

[1] I. Akyildiz, and X. Wang, Wireless mesh networks: John Wiley & Sons, 2009. Article (CrossRef Link)

[2] W. Pak, and S. Bahk, "Traffic Flow Estimation based Channel Assignment for Wireless Mesh Networks," TIIS, vol. 5, no. 1, pp. 68-82, 2011. Article (CrossRef Link)

[3] M.K. Hossain, T.C. Keong, L.C. Kwang and Y.C. Yeow. "A Dynamic Channel Switching Policy Through P-learning for Wireless Mesh Networks," KSII Transactions on Internet & information Systems, vol.10, no. 2, pp.608-627, 2016.

[4] J. Wang and W. Shi. "Partially overlapped channels-and flow-based end-to-end channel assignment for multi-radio multi-channel wireless mesh networks," China Communications, vol. 13, no. 4, pp.l-13, 2016. Article (CrossRef Link)

[5] A.U. Chaudhry, R.H. Hafez and J.W. Chinneck. "Realistic interference-free channel assignment for dynamic wireless mesh networks using beamforming," Ad Hoc Networks, vol. 51, pp.21-35, 2016. Article (CrossRef Link)

[6] A. Raniwala, K. Gopalan, and T.-c. Chiueh, "Centralized channel assignment and routing algorithms for multi-channel wireless mesh networks," ACM SIGMOBILE Mobile Computing and Communications Review, vol. 8, no. 2, pp. 50-65, 2004. Article (CrossRef Link)

[7] A. Mohsenian-Rad, and V. Wong, "Joint logical topology design, interface assignment, channel allocation, and routing for multi-channel wireless mesh networks," IEEE Transactions on Wireless Communications, vol. 12, no. 6, pp. 4432-4440, 2007. Article (CrossRef Link)

[8] S. Avallone, I. F. Akyildiz, and G. Ventre, "A channel and rate assignment algorithm and a layer-2.5 forwarding paradigm for multi-radio wireless mesh networks," IEEE/ACM Transactions on Networking (TON), vol. 17, no. 1, pp. 267-280, 2009. Article (CrossRef Link)

[9] X. Huang, S.-l. Feng, and H.-c. Zhuang, "Cross-layer fair resources allocation for multi-radio multichannel wireless mesh networks," in Proc. of 5th International Conference on Wireless Communications, Networking and Mobile Computing, pp. 1-5, 2009. Article (CrossRef Link)

[10] V. Gardellin, S. K. Das, L. Lenzini, C. Cicconetti, and E. Mingozzi, "G-PaMeLA: A divide-and-conquer approach for joint channel assignment and routing in multi-radio multi-channel wireless mesh networks," Journal of parallel and distributed computing, vol. 71, no. 3, pp. 381-396, 2011. Article (CrossRef Link)

[11] T.-Y. Lin, K.-C. Hsieh, and H.-C. Huang, "Applying genetic algorithms for multi-radio wireless mesh network planning," Vehicular Technology, IEEE Transactions on, vol. 61, no. 5, pp. 2256-2270, 2012. Article (CrossRef Link)

[12] J. Wellons, and Y. Xue, "The robust joint solution for channel assignment and routing for wireless mesh networks with time partitioning," Ad Hoc Networks, vol. 13, pp. 210-221, 2014. Article (CrossRef Link)

[13] M. Alicherry, R. Bhatia, and L. E. Li, "Joint Channel Assignment and Routing for Throughput Optimization in Multiradio Wireless Mesh Networks," IEEE Journal on Selected Areas in Communications, vol. 24, no. 11, pp. 1960-1971, 2006. Article (CrossRef Link)

[14] L. Farzinvash and M. Dehghan, "A cross-layer approach for multi-layer multicast routing in multi-channel multi-radio wireless mesh networks," International Journal of Ad Hoc and Ubiquitous Computing, vol. 21, no. 1, pp.26-40, 2016. Article (CrossRef Link)

[15] S. Avallone and A. Banchs, "A channel assignment and routing algorithm for energy harvesting multiradio wireless mesh networks," IEEE Journal on Selected Areas in Communications, vol. 34, no. 5, pp. 1463-1476, 2016. Article (CrossRef Link)

[16] A.R. Ulucinar and I. Korpeoglu, "Distributed joint flow-radio and channel assignment using partially overlapping channels in multi-radio wireless mesh networks," Wireless Networks, vol. 22, no. 1, pp.83-104, 2016. Article (CrossRef Link)

[17] D.G Narayan and U. Mudenagudi, "A Cross-Layer Framework for Joint Routing and Resource Management in Multi-radio Infrastructure Wireless Mesh Networks," Arabian Journal for Science and Engineering, pp. 1-17, 2016. Article (CrossRef Link)

[18] XU. Yi-Han, W. U. Yin, and S. O. N. G Jun, "A Routing Metric to Improve Route Stability in Mobile Wireless Sensor Networks," KSII Transactions on Internet & information Systems vol. 10, no. 5, 2016.

[19] X. Shao, R. Wang, H. Huang, and L. Sun, "Load Balanced Coding Aware Multipath Routing for Wireless Mesh Networks," Chin. J. Electron, vol. 24, pp.8-12, 2015. Article (CrossRef Link)

[20] S. Zhuo, Z. Wang, Y. Q. Song, Z. Wang, and L. Almeida, "A Traffic Adaptive Multi-channel MAC Protocol with Dynamic Slot Allocation for WSNs," IEEE Transactions on Mobile Computing, vol. 15 no. 7, pp. 1600-1613, 2016. Article (CrossRef Link)

[21] J.Avonts and c. Blondia, "A framework to compare topology algorithms in multi-channel multi-radio wireless mesh networks," Computer Networks, vol. 98, pp.89-108, 2016. Article (CrossRef Link)

[22] E.N. Maleki and G. Mirjalily, "Fault-tolerant interference-aware topology control in multi-radio multi-channel wireless mesh networks," Computer Networks, vol. 110, pp.206-222, 2016. Article (CrossRef Link)

[23] X. Bao, L. Han, C. Deng, H. Zhang and W. Tan, "Robust topology construction method with radio interface constraint for multi-radio multi-channel wireless mesh network using directional antennas," International Journal of Distributed Sensor Networks, vol. 12, no. 9, 2016. Article (CrossRef Link)

[24] S. Iqbal, A. H. Abdullah, K. Hussain, and F. Ahsan, "Channel Allocation in Multi-radio Multichannel Wireless Mesh Networks: A Categorized Survey," KSII Transactions on Internet & information Systems, vol. 9, no. 5, pp. 1642-1661, 2015.

[25] W. Si, S. Selvakennedy, and A. Y. Zomaya, "An overview of channel assignment methods for multi-radio multi-channel wireless mesh networks," Journal of Parallel and Distributed Computing, vol. 70, no. 5, pp. 505-524, 2010. Article (CrossRef Link)

[26] H.A. Mogaibel, M. Othman, S. Subramaniam and N.A.W.A. Hamid, "Review of channel assignment approaches in multi-radio multi-channel wireless mesh network," Journal of Network and Computer Applications, vol. 72, pp. 113-139, 2016. Article (CrossRef Link)

[27] A. Musaddiq, F. Hashim, C.A.B.C. Ujang and B.M. Ali, "Survey of channel assignment algorithms for multi-radio multi-channel wireless mesh networks," IETE Technical Review, vol. 32, no. 3, pp. 164-182, 2015. Article (CrossRef Link)

[28] A.A. Al Islam, M.J. Islam, N. Nurain and V. Raghunathan. "Channel Assignment Techniques for Multi-Radio Wireless Mesh Networks: A Survey," IEEE Communications Surveys & Tutorials, vol. 18, no. 2, pp.988-1017, 2016. Article (CrossRef Link)

[29] O. M. Zakaria, A. H. A. Hashim, W. H. Hassan, O. O. Khalifa, M. Azram, L. B. Jivanadham, M. L. Sanni, and M. Zareei, "Joint Channel Assignment and Routing in Multiradio Multichannel Wireless Mesh Networks: Design Considerations and Approaches," Journal of Computer Networks and Communications, vol. 2016, pp. 24, 2016. Article (CrossRef Link)

[30] Y. Qu, B. Ng and W. Seah, "A survey of routing and channel assignment in multi-channel multi-radio WMNs," Journal of Network and Computer Applications, vol. 65, pp.120-130, 2016. Article (CrossRef Link)

[31] S. Avallone and A. Banchs, "A channel assignment and routing algorithm for energy harvesting multiradio wireless mesh networks," IEEE Journal on Selected Areas in Communications, vol. 34, no. 5, pp. 1463-1476, 2016. Article (CrossRef Link)

[32] I. I. CPLEX, "V12. 1: User's Manual for CPLEX," International Business Machines Corporation, vol. 46, no. 53, pp. 157, 2009.

[33] N. Sadeghianpour, T. C. Chuah, and S. W. Tan, "Joint channel assignment and routing in multiradio multichannel wireless mesh networks with directional antennas," International Journal of Communication Systems, vol. 28, no. 9, pp. 1521-1536, 2015. Article (CrossRef Link)

[34] C. Cicconetti, V. Gardellin, L. Lenzini, and E. Mingozzi, "PaMeLA: A joint channel assignment and routing algorithm for multi-radio multi-channel wireless mesh networks with grid topology," in Proc. of 6th International Conference on Mobile Adhoc and Sensor Systems, pp. 199-207, 2009. Article (CrossRef Link)

[35] J. J. Galvez, and P. M. Ruiz, "Efficient rate allocation, routing and channel assignment in wireless mesh networks supporting dynamic traffic flows," Ad Hoc Networks, vol. 11, no. 6, pp. 1765-1781, 2013. Article (CrossRef Link)

[36] J. J. Galvez, and P. M. Ruiz, "Joint link rate allocation, routing and channel assignment in multi-rate multi-channel wireless networks," Ad Hoc Networks, vol. 29, pp. 78-98, 2015. Article (CrossRef Link)

[37] M. Nekoui, A. Ghiamatyoun, S. N. Esfahani, and M. Soltan, "Iterative cross layer schemes for throughput maximization in multi-channel wireless mesh networks," in Proc. of 16th International Conference on Computer Communications and Networks, pp. 1088-1092, 2007. Article (CrossRef Link)

[38] A. A. Franklin, A. Balachandran, and C. S. R. Murthy, "Online reconfiguration of channel assignment in multi-channel multi-radio wireless mesh networks," Computer Communications, vol. 35, no. 16, pp. 2004-2013, 2012. Article (CrossRef Link)

[39] M. Kodialam, and T. Nandagopal, "Characterizing the capacity region in multi-radio multi-channel wireless mesh networks," in Proc. of the 11th annual international conference on Mobile computing and networking pp. 73-87, 2005. Article (CrossRef Link)

[40] X.-Y. Li, A. Nusairat, Y. Wu, Y. Qi, J. Zhao, X. Chu, and Y. Liu, "Joint throughput optimization for wireless mesh networks," Mobile Computing, IEEE Transactions on, vol. 8, no. 7, pp. 895-909, 2009. Article (CrossRef Link)

[41] H. Li, Y. Cheng, C. Zhou, and P. Wan, "Multi-dimensional conflict graph based computing for optimal capacity in MR-MC wireless networks," in Proc. of IEEE 30th International Conference on Distributed Computing Systems (ICDCS), pp. 774-783, 2010. Article (CrossRef Link)

[42] X. Meng, K. Tan, and Q. Zhang, "Joint routing and channel assignment in multi-radio wireless mesh networks," in Proc. of IEEE International Conference on Communications, pp. 3596-3601m 2006. Article (CrossRef Link)

[43] S. Avallone, F. P. D'Elia, and G. Ventre, "A traffic-aware channel re-assignment algorithm for wireless mesh networks," in Proc. of Wireless Conference (EW), 2010 European, pp. 683-688, 2010. Article (CrossRef Link)

[44] J. J. Galvez, P. M. Ruiz, and A. Gomez-Skarmeta, "Responsive Online Load-Balancing Routing and Load-aware Channel Re-Assignment in Multi-Radio Multi-Channel Wireless Mesh Networks," University of Murcia, Spain, Tech. Rep, 2011.

[45] J. J. Galvez, P. M. Ruiz, and A. F. G. Skarmeta, "TCP flow-aware Channel Re-Assignment in Multi-Radio Multi-Channel Wireless Mesh Networks," in Proc. of IEEE Eighth International Conference on Mobile Ad-Hoc and Sensor Systems, pp. 262-271, 2010. Article (CrossRef Link)

[46] S. Avallone, G. Stasi, and A. Kassler, "A traffic-aware channel and rate reassignment algorithm for wireless mesh networks," IEEE Transactions on Mobile Computing, vol. 12, no. 7, pp. 1335-1348, 2013. Article (CrossRef Link)

[47] A. Kanagasabapathy, A. A. Franklin, and C. Murthy, "An adaptive channel reconfiguration algorithm for multi-channel multi-radio wireless mesh networks," IEEE Transactions on Wireless Communications, vol. 9, no. 10, pp. 3064-3071, 2010. Article (CrossRef Link)

[48] S. Arkoulis, E. Anifantis, V. Karyotis, S. Papavassiliou, and N. Mitrou, "On the optimal, fair and channel-aware cognitive radio network reconfiguration," Computer Networks, vol. 57, no. 8, pp. 1739-1757, 2013. Article (CrossRef Link)

[49] Y. Zhou, S.-H. Chung, and H.-Y. Jeong, "Reconfiguring Multi-Rate Wi-Fi Mesh Networks with Flow Disruption Constraints," Dynamics in Logistics, pp. 383-393: Springer, 2013. Article (CrossRef Link)

[50] F. Herzel, G. Fischer, and H. Gustat, "An integrated CMOS RF synthesizer for 802.11 a wireless LAN," IEEE Journal of Solid-State Circuits, vol. 38, no. 10, pp. 1767-1770, 2003. Article (CrossRef Link)

[51] M. Yun, Y. Zhou, A. Arora, and H.-A. Choi, "Channel-assignment and scheduling in wireless mesh networks considering switching overhead," in Proc. of IEEE International Conference on Communications, pp. 1-6, 2009. Article (CrossRef Link)

[52] P. Li, N. Scalabrino, Y. Fang, E. Gregori, and I. Chlamtac, "How to effectively use multiple channels in wireless mesh networks," IEEE Transactions on, vol Parallel and Distributed Systems, 20, no. 11, pp. 1641-1652, 2009. Article (CrossRef Link)

[53] S. Avallone, and G. Di Stasi, "An experimental study of the channel switching cost in multi-radio wireless mesh networks," IEEE Communications Magazin,, vol. 51, no. 9, pp. 124-134, 2013. Article (CrossRef Link)

[54] A. Iyer, C. Rosenberg, and A. Karnik, "What is the right model for wireless channel interference?," IEEE Transactions on Wireless Communications, vol. 8, no. 5, pp. 2662-2671, 2009. Article (CrossRef Link)

[55] H. W. Kuhn, "The Hungarian method for the assignment problem," Naval research logistics quarterly, vol. 2, no. 1-2, pp. 83-97, 1955. Article (CrossRef Link)

[56] R. Jain, D.-M. Chiu, and W. Hawe, "A quantitative measure of fairness and discrimination for resource allocation in shared computer systems," Hudson, MA: Eastern Research laboratory, Digital Equipment Corporation 1984.

[57] C. Spearman, "The proof and measurement of association between two things," The American journal of psychology, vol. 15, no. 1, pp. 72-101, 1904. Article (CrossRef Link)

Omar M. Zakaria (1,2), Aisha-Hassan Abdalla Hashim (1), Wan Haslina Hassan (2), Othman Omran Khalifa (1), Mohammad Azram (3), Shidrokh Goudarzi (2), Lalitha Bhavani Jivanadham (2) and Mahdi Zareei (4)

(1) Faculty of Engineering, International Islamic University Malaysia, Malaysia; [e-mail: dr.omar.zakaria@ieee.org ; aisha@iium.edu.my ; khalifa@iium.edu.my] ;

(2) Malaysia-Japan International Institute of Technology, Universiti Teknologi Malaysia, Malaysia; [e-mail: wanhaslina.kl@utm.my; shidrokhgoudarzi@gmail.com; bjlalitha2@gmail.com]

(3) Department of Mathematics and Statistics, Sultan Qaboos University, Oman [azram50@hotmail.com]

(4) School of Engineering and Sciences, Tecnologico de Monterrey, Mexico [m.zareei@ieee.org]

(*) Corresponding author: Omar M. Zakaria

Received April 8, 2016; revised November 10, 2016; accepted December 3, 2016; published January 31, 2017

Omar M. Zakaria received his B.Sc. in Informatics Engineering from University of Aleppo, Syria in 2006 and his M.S., and Ph.D. degrees in Computer and Communication Engineering from International Islamic University Malaysia (IIUM) in 2010 and 2015 respectively. Currently, he is a research officer at Communication System and Networks Laboratory, Malaysia-Japan International Institute of Technology (MJIIT)--University Technology Malaysia (UTM). His research interests are mainly in resource allocation and management, wireless communications and networks.

Aisha Hassan Abdalla Hashim graduated from Electronics Engineering, Gezira University (1990). She received her MSc in Computer Science University of Khartoum (1996) and her PhD in Computer Engineering (2007) from International Islamic University Malaysia. Currently she is a professor at Electrical & Computer Engineering Department, Faculty of Engineering International Islamic University Malaysia. She is IEEE Senior Member and IET Member. Her research interest is Mobile Networks and Mobile Multicast.

Wan Haslina Hassan received her MSc in Computation from Oxford University in 1993 and her PhD in Electrical Engineering from Universiti Teknologi Malaysia. She was appointed as a lecturer at International Islamic University Malaysia in 1995. She worked as Associate Professor and Head, Dept of Networks & Telecommunications at Sunway University from 2008 to 2011. Currently, she is the Head of Communication Systems & Networks Research Group at Malaysia-Japan International Institute of Technology, Universiti Teknologi Malaysia (Kuala Lumpur) where she is supervising postgraduates students in the areas of nano/molecular communications, content-centric networks, intelligent architectures for mobility management, and network security. Her current research interests are in the area of computer/mobile/bio-communications and information/network security.

Othman O. Khalifa received his B.Sc. in Electronic Engineering from the Garyounis University, Libya in 1986 and M.Sc. in Electronics Science Engineering and PhD in Digital Image Processing from Newcastle University, UK in 1996 and 2000 respectively. He worked in industrial for eight years and Head of the department of Electrical and Computer Engineering, IIUM. Currently, he is a Professor at the department of Electrical and Computer Engineering His area of research interest is Communication Systems, Digital image / video processing, Wavelets, Fractal and Pattern Recognition. He published more than 200 papers in international journals and Conferences. He is SIEEE member, IEEE computer, Image processing and Communication Society member.

Mohammad Azram received his B.Sc. and M.Sc. (with distinction) in Mathematics from the University of Peshawar, Pakistan in 1974 and 1976 respectively. He started his career as a lecturer in the Department of Mathematics, University of Peshawar in Jan. 1977. He received his MS and Ph.D in Mathematics from the University of Idaho (USA) in 1985 and 1989 respectively. He had joined the International Islamic University of Malaysia in 1999 and served as a professor since 2001, a Deputy Dean (Academics, Centre for Postgraduate Studies) and Head (Dept of Sc, Faculty of Engg). Currently, he is visiting faculty at DOMAS, Sultan Qaboos University, Oman. He was invited as Keynote/invited speaker for several International conferences. He is a senior member of International Association of Computer Science and Information Technology, International Advisory Board Member of International Institute of Engineers and Researchers and a member of the Australian Mathematical Society and Pakistan Mathematical Society. He is associated with many journals as Managing Editor, Advisory Board, Chief Editor. He has authored about 90 Journal articles/referred proceedings and about 9 book's chapters.

Shidrokh Goudarzi is a Ph.D. candidate at the Universiti Teknologi of Malaysia. She obtained her master degree from Universiti Teknologi Malaysia. Her field of Study is Communication System and Wireless Network. She has academic experience from Islamic Azad University in Iran. Her research interests are in wireless networks, artificial intelligence, and next generation networks.

Lalitha Bhavani is a PhD student in the Electronic of Systems Engineering Department at the Malaysia Japan Intl' Institute of Technology, Universiti Teknologi Malaysia. Her research and publication interests include wireless network security, cloud computing security and molecular communication.

Mahdi Zareei received his M.Sc. in Computer Network from University of Science, Malaysia (USM) in 2011. In 2013, he joined Communication Systems and Networks research group at Malaysia-Japan International Institute of Technology (MJIIT), University of Technology Malaysia (UTM) as a PhD student. He performed part of his PhD research at Osaka University in 2015 and graduated from his PhD in 2016. He received several best paper awards from different international conferences. Currently, his research mainly focuses on cognitive radio network, wireless sensor network, ad hoc network and optimisation. He is an IEEE member.

Table 1. Notations parameters and variables N The set of MRs in the network. E The set of edges between MRs (logical links). [e.sub.ij] Edge between MRs i and j. C The set of the orthogonal channels. I(x) The number of interfaces at MR (X). [R.sub.T] The transmission range of each interface. [R.sub.I] The interference range of each interface. FL The set of flows in the network. [[PHI].sup.f] The traffic rate of flow f. [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] The minimum path hop count from GW to the destination of flow f [F.sub.ij] The set of links interfere with link [e.sub.ij]. [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] A binary variable, =1 1 if i assign channel k to one of its interfaces in the new configuration and 0 otherwise. [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] A binary constant, =1 1 if i assign channel k to one of its interfaces in the old configuration and 0 otherwise. [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] A binary variable, =1 if [e.sub.ij] uses channel k, and 0 otherwise. [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] A binary variable, =1 if in the new configuration flow f uses channel k over [e.sub.ij] in its path and 0 otherwise. [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] A binary constant, =1 if in the old configuration flow f uses channel k over [e.sub.ij] in its path and 0 otherwise. [GAMMA] Tunable variable, where[GAMMA] [greater than or equal to] 1 [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] The capacity of link [e.sub.if]over channel k. [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] The aggregated traffic load from all flows over link [e.sub.ij] and channel k. [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] Maximum channel-link utilization over all links NetCont Network average contention Cost-CA Channel re-assignment cost Cost-RO Routing cost [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] The inverse of capacity of link [e.sub.ij] over channel k [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] The utilization of channel k at link [e.sub.ij]. [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] A binary constant, =1 if assigning channel k to link [e.sub.ij] will cause channel switching overhead, and 0 otherwise. [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] A constant equal to the traffic load associated with flow f if i is one of the forwarding mesh routers of f in the old configuration, and 0 otherwise. [beta] Large positive constant. Table 2. Simulation parameters Simulation Area 2000 x 2000 [m.sup.2] Simulation Time 250 sec Topology Grid Number of MRs 49 Transmission Range 255 m Interference Range 510 m Propagation Model Two-ray ground MAC Protocol 802.11 CSMA (RTS-CTS Disabled) Link Bandwidth 11 Mbps Traffic Type CBR (UDP) Packet Size 512 byte Buffer Size 50 Packets # Radios at Gateway 3

Printer friendly Cite/link Email Feedback | |

Author: | Zakaria, Omar M.; Hashim, Aisha-Hassan Abdalla; Hassan, Wan Haslina; Khalifa, Othman Omran; Azram, M |
---|---|

Publication: | KSII Transactions on Internet and Information Systems |

Article Type: | Report |

Date: | Jan 1, 2017 |

Words: | 10476 |

Previous Article: | Secondary system initialization protocol using FFT-based correlation matching for cognitive radio ad-hoc networks. |

Next Article: | Overlay multicast update strategy based on perturbation theory. |

Topics: |