International Journal of Communications, Network and System Sciences
Vol.09 No.08(2016), Article ID:69597,15 pages
10.4236/ijcns.2016.98028

Joint Routing and Admission Control in Wireless Mesh Network

Fawaz A. Khasawneh, Abderrahmane Benmimoune, Michel Kadoch

Department of Electrical Engineering, École de Technologie Supérieure (ETS)-University of Quebec, Montreal, Canada

Copyright © 2016 by authors and Scientific Research Publishing Inc.

This work is licensed under the Creative Commons Attribution International License (CC BY).

http://creativecommons.org/licenses/by/4.0/

Received 13 May 2016; accepted 6 August 2016; published 9 August 2016

ABSTRACT

Wireless Mesh Network is a promising technology with many challenges yet to be addressed. Novel and efficient algorithms need to be developed for routing and admission control with the objective to increase the acceptance ratio of new calls without affecting the Quality of Service (QoS) of the existing calls and to maintain the QoS level provided for the mobile calls. In this paper, a novel Markov Decision-based Admission Control and Routing (MDACR) algorithm is proposed. The MDACR algorithm finds a near optimal solution using the value iteration method. To increase the admission rate for both types of calls, a multi-homing admission and routing algorithm for handoff and new calls is proposed. This algorithm associates the user with two different access points which is beneficial in a highly congested network and proposes a new routing metric to assure seamless handoff in the network. Our proposed algorithm outperforms other algorithms in the literature in terms of handoff delay, blocking probability, and number of hard handoff.

Keywords:

Wireless Mesh Network, Markov Decision Process, Multi-Homing, Admission Control, Routing

1. Introduction

Wireless Mesh Network (WMN) architectures can be categorized into three types, as shown in Figure 1. Firstly, the basic wireless infrastructure (or backbone) architecture is formed by the mesh routers, which allow wireless connectivity, routing and gateway functionality. In addition to the IEEE 802.11 radio protocol, a diversified range of radio technologies may be integrated to facilitate the radio communication of the infrastructure. In this architecture, the mesh routers are responsible for creating self-healing, self-configuring links among themselves

Figure 1. Wireless mesh network architectures.

for the provision of a wireless link. The conventional clients with a wired connection may connect to the wireless router via an Ethernet link. Clients can directly access the wireless network if they have the same radio protocol; otherwise they have to access the network via their own base stations. Secondly, there is the client WMN architecture, where client nodes create a peer-to-peer network among client devices and maintain configuration and routing functions. It does not require mesh routers. The protocol used in this architecture is based on single radio. This protocol requires more functionalities to be served by client devices as compared to those in the backbone architecture. The third type of WMN is the hybrid architecture, which is the combination of both backbone and client WMN architectures. This architecture is advantageous since it employs backbone architecture to integrate different types of radio technologies (WiMAX, Wi-Fi, cellular, etc.) into the same platform, and the client WMN architecture facilitates better connectivity between clients and wider coverage inside the network [1] [2] .

WMN has many applications because of its high speed, ease of implementation and low setup cost. One of its most promising applications is the provision of last mile wireless internet access. The versatility and flexibility of a WMN make it the most common networking solution. However, a WMN has some intrinsic performance and topology issues due to its network being dynamic and unpredictable, leading to QoS and reliability issues, which need to be addressed. QoS is a NP-complete problem, so does not have global solution [3] . To improve performance without compromising the attractive features of WMN, requires the design of a joint QoS aware admission and routing protocol. In WMN, a tree-based routing algorithm is preferred due to the static topology structure. The route discovery process involves large overhead. Many algorithms have been proposed that use different routing metrics to adjust and assess routing conditions in the WMN. Some of these routing metrics are interference, packet loss, link quality, congestion, hop count, among others. However, choosing a single routing metric for addressing the issues in the WMN can solve single routing issue and breeds other issues as a tradeoff. The WMN still lacks a single routing algorithm that can simultaneously consider all the routing issues based on all of the routing metrics. This paper proposes a unique, dynamic Markov Decision-based Admission Control and Routing protocol (MDACR), which integrates multiple routing metrics to yield a widely compatible routing protocol with consistent and reliable output.

The rest of the paper is organized as follows: Section 2 introduces the literature review. Section 3 describes problem formulation, performance measurement and objectives. Section 4 depicts our novel proposed admission and routing algorithm and the associated mathematical Markov model. Section 5 introduces the system model. Numerical results are shown and discussed in Section 6. Section 7 concluded our paper.

2. Related Work

There are many published studies on efficient and advanced management of routing algorithms. The different algorithms and methodologies for routing presented in those studies are discussed here.

Wireless Mesh Network (WMN) is an innovative networking technology, which has an unpredictable medium and frequently changing networking topology characteristics. These characteristics make routing design challenging. Researchers in [4] proposes a novel congestion control routing algorithm named Least Congestion QoS-aware Routing (LCQSR). This innovative algorithm finds the best destination path, easing overall congestion. The basis of the algorithm is a metric called Degree of Congestion Control (DCC), which explores and exploits the dynamic nature of two MAC layer statistical parameters: Frame Transmission Efficiency ( FTE ) and available Residual Bandwidth. The proposed algorithm takes advantage of a cross layer design approach to find a better compromise between routing performance and reliability of the system, the main disadvantages of this algorithm are that the performance deteriorates with dynamicity of the network and in a highly congested network situations, where DCC is very high, the new call will be rejected due to unavailable bandwidth, in our proposed algorithm the probability of call rejection is reduced even in a highly congested network situations.

To resolve the routing discovery complexity issues associated with WMN, an improved version of the DSR algorithm is proposedin [5] called NDOUTE, which is a new node disjoint Ad hoc On-Demand Multipath Distance Vector (AOMDV) based routing algorithm. Unlike DSR, NDOUTE adds a “broadcasting node table” and a “source routing sequence” into the RREQ, RREP packets, avoiding the possibility of creating a reverse routing loop. The benefit is the creation of numerous paths to the destination, which in turn reduces the computational complexities associated with the selection of single destination path. In this algorithm, two disjoint routes are discovered, at the time of first route failure all the traffic is supposed to be routed through the other route automatically, but at that time the other route might be unavailable due to bandwidth unavailability. In case of highly congested networks, the possibility that the backup path is unavailable is high due to bandwidth unavailability. Our proposed algorithm reduces the routing discovery complexity and increase the admission rate compared to [5] .

The exploitation of the attractive and versatile performance features of multi-channel WMNusing multipath routing algorithm is done in [6] . The throughput of multichannel WMN can improve significantly with dynamic channel utilization. Traditional routing protocols do not consider implementation of multipath routing, most of them are based on single path routing. To address these issues and to increase end-to-end throughput, Tran et al. proposes Joint Multi-channel and Multi-path routing (JMM) algorithm that works in between MAC layer and network layer. The proposed solution integrates multi-path routing with multi-channel link layer. JMM manages channel usage by dividing time into slots and assigning them to channels, it maintains dual path traffic flows. It is obvious that the proposed algorithm resolves the contention among competing traffics by assigning those different channels, different time slots and different paths in an intelligent and efficient manner. Therefore, the throughput increases significantly. In this algorithm, the reordering complexity is very high at the destination. Compared to our proposed algorithm, the reordering complexity is reduced by allowing the call traffic to be routed at most though two paths with two different channels.

Another paper [7] presents a novel routing metric for multi-hop, multi-radio WMNs that can facilitate choosing a high-throughput path, from the source to the destination. The metric is designed for a static wireless network with stationary nodes. The metric weights each link against the expected time of transmission (ETT) for a packet through a link. These weights being functions of bandwidth of the link and the packet loss rate. The metrics, Weighted Cumulative ETT (WCETT) are formed by integrating the individual link weights with the path metric. The same channel interferences are dealt with by this metric. The call Multi-Radio Link-Quality Source Routing (MR-LQSR) is the routing protocol that incorporates the WCETT metric into it. In this algorithm, the highly congested network situation is still a problem.

It is really important to find a robust paths for both new calls as well as handoff calls coming into the network. In [8] - [19] , mobility management algorithms are proposed. In those protocols, the traffic for handoff call is routed through another path which is completely disjoint with the old reserved path. In our proposed algorithm, we focus on finding a robust path for new calls in a highly congested network by triggering the multi-homing feature and route the traffic into two maximally jointed paths in order to increase the admission rate and decrease the reordering complexity at the destination. On the other hand for the handoff call, a multi-homing feature is triggered in case of highly congested network and a maximally jointed paths with the old reserved path is found in order to decrease the hard handoff ratio and decrease the handoff delay. This will be shown in the results section below.

Comparison between joint and disjoint routing algorithms is discussed in [20] , however in a highly congested networks, joint routing alone is not enough, so we associate our routing algorithm decision with triggering multi-homing, [21] , whenever needed. A novel markov decision process model, with its defined rewards, discount factor, transition probabilities, is introduced to verify our results and obtain a near optimal solution for our proposed algorithm.

3. Problem Formulation and Objectives

This section introduces the problem formulation and defines the optimization model. Our proposed algorithm is designed for situations where the network is highly congested. Let G = (N, L) be an undirected graph. Where N is the set of nodes in the network and L is the set of links in the network. To each vertex. Let the available bandwidth be (1-Lu) in link, where Lu is the bandwidth utilization in each link l. In most of the cases, and with high probability, when a handoff or a new call is arrived into the network, the minimum required bandwidth for user k which is denoted by brk, is not available. The available bandwidth in each link is described in Equation (1) below:

(1)

Over a period of time T, our objective function is to maximize the number of users accepted in the whole network. In order to maximize the number of accepted users, multi-homing is triggered to accept the call via two or more access points. For simplicity purposes and to decrease the reordering complexity at the destination side a single user is allowed to connect to only two access points if needed. A reward function should be defined to distinguish between different paths that can be selected for a new or a handoff calls. In our scenario, when a new or handoff call arrives to the network, one of the following six route options can be selected for the new path as described below:

Ÿ Arrival of a new call and routed to one path (a1).

Ÿ Arrival of a new call and routed to two disjoint paths (a2).

Ÿ Arrival of a new call and routed to two joint paths (a3).

Ÿ Arrival of a handoff call and routed to only one path which is maximally disjointed with the old primary path (a4).

Ÿ Arrival of a handoff call and routed to only one path which is maximally jointed with the old primary path (a5).

Ÿ Arrival of a handoff call and routed to a maximally disjointed paths, old path and the two paths selected for the handoff call are all completely disjointed (a6).

Ÿ Arrival of a handoff call and routed to a maximally jointed paths, old path and the selected one or two paths for the handoff call are all maximally jointed with each other (a7).

Choosing one of the routing possibilities in a highly congested network environment will be based on priority. Higher reward values will be assigned for handoff calls and joint paths. If we have a case where the new or handoff call is rejected, the reward parameter will be equal to 0. But, if we have a case when the new or handoff call is accepted in one of the 7 above routing possibilities (a1, a2, a3, a4 a5, a6, a7), the reward parameter will be equal to Rj. Hence, we can write:

(2)

The values of the rewards are written in Table 1 below:

Now we can define our objective function which will be to maximize the number of calls accepted over a period of time T, the objective function could be expressed as:

Table 1. Reward values.

(3)

where fij(T) is the multiplication of Ai(T) which is the number of users accepted at node i and the summation of the rewards given to each user based on the selected route as explained previously. Hence, we can define our optimization model as indicated below:

(4)

Subject to:

(5)

where Rj is the reward assigned for choosing one path over the other. To solve the above optimization problem, we propose a Markov Decision Process and a value iteration method to find a near optimal solution.

Review of Performance Measurements

In this section, we introduce the performance measurements for blocking probability, average bandwidth utilization, and handoff delay as defined below:

1. Blocking Probability (BP):

The call is blocked whenever there is no available bandwidth in the network and the queue is full. This can be expressed by the following formula:

(6)

where P[C = c] is the probability that there is exactly c calls in the system, so if any other call arrives it will be blocked. Where is the server utilization that can be calculated by dividing the arrival rate over the service rate.

2. Handoff Delay (Dhandoff):

Handoff delay is the time required for the mobile node to reserve new resources for the handoff call, this is divided to three sub-delays, which are TDL, TNetwork, and TApplication.

(7)

where TDL is the handoff delay coming from data link layer, TNetwork is the delay from the network layer and TApplication is the delay from the application layer. The most dominant factor affecting the handoff delay is the one resulting from the network layer [2] [22] , and it is composed of discovering the route, associate the handoff call with the new discovered route and update the location of the mobile node for the future routing decisions. In this paper we will focus on finding the handoff delay caused by the network layer.

4. Our Proposed Algorithm

As mentioned previously, we have two types of calls in the network which are new or handoff calls. In our scenario, whenever a new call arrives to the highly congested network, it is with high probability will be rejected due to lack of bandwidth in the network, our proposed algorithm will connect the new call with two access points and route the user traffic from source to the destination through two different paths using multi-homing in order to increase the admission rate. Those two paths could be joint or disjoint paths, more reward will be assigned to the joint path which gives us better QoS compared to the disjoint path as shown in the results section. In the mathematical model below, we design a Markov decision process to make decisions on the selection of the route for the new and handoff calls. Our model shows the benefits of using joint routing and multi-homing over the disjoint routing and no multi-homing scenario in terms of QoS.

We divided the network topology into two levels, the first level is the network access level and the other level is the backhaul network level. As shown in Table 2, when a new call is arriving and bandwidth is available in the two network levels then there is no need to trigger Multi-Homing (MH) and one route is found for the

Table 2. Triggering multi-homing and routing based on the availability bandwidth.

new call traffic. However, if the bandwidth is available at the access network level but not at the backhaul network level then our proposed algorithm will trigger MH feature in the access network level in order to split the new call traffic between two paths, in this way the probability of accepting the new call increases since the required bandwidth is reduced by the half. In this scenario, it is better to find a Maximally Jointed (MJ) paths in order to decrease the reordering complexity at the destination side. In the third case (C3), we have a situation where the bandwidth is not available at the access network level and available at the backhaul network level. In this case, MH is also triggered in order to increase the admission rate by splitting the new call traffic into two different paths and a MJ paths is also preferred to reduce the reordering complexity at the destination side. In the last case (C4), which is the worst case scenario, we do not have available bandwidth either in the access network level or in the backhaul network level. In this case, MH is also triggered, and a MJ path is preferred.

On the other hand, when a handoff call is arriving and bandwidth is available in the two network levels then there is no need to trigger Multi-Homing (MH) and one route is found for the handoff call traffic which is Maximally Jointed with the mobile user Old (MJO) path. However, if the bandwidth is available at the access network level but not at the backhaul network level then our proposed algorithm will trigger MH feature in the access network level in order to split the handoff call traffic between two paths, in this way the probability of accepting the handoff call increases since the required bandwidth is reduced by the half. In this scenario, it is better to find a Maximally Jointed Trio paths with the mobile user Old (MJTO) path in order to decrease the reordering complexity at the destination side and to reduce the handoff delay. In the other case (C7), we have a situation where the bandwidth is not available at the access network level and available at the backhaul network level. In this case, MH is also triggered in order to increase the admission rate by splitting the handoff call traffic into two different paths and a MJTO paths is also preferred to reduce the reordering complexity at the destination side and the handoff delay. In the last case (C8), which is the worst case scenario, we do not have available bandwidth either in the access network level or in the backhaul network level. In this case, MH is also triggered, and a MJTO paths is preferred.

4.1. Markov Decision Process Model

Whenever an existing user call, which is routed through the path П1 is moving, a new path should be discovered which is denoted by П2. If the two paths are joint and there are some common links between the two paths then this joint situation is denoted by J (П1, П2), otherwise it will be denoted by D (П1, П2).

In order to model our problem using MDP, states should be defined. In our situation, we have four different states which are reject, one path state, joint paths state and disjoint paths state as shown in Figure 2. Two different types of calls are defined which are new calls and handoff calls. The definition of each state is described below.

States of the presented Markov model in our work are representing the connection of the mobile terminal with three possible types of paths through the network which could be one path, joint or disjoint paths, and the situation when the mobile terminal is not active or not able to connect to one of the access points due to the lack of bandwidth?reject state. Transitions probabilities between states of the Markov chain are defined to represent all possible transitions from one state to another as shown below in Figure 2.

Figure 2. Markov decision process state diagram.

Ÿ Reject state (state 0): as we mentioned above that we have either new or handoff call. Whenever we have a new call and could not find available bandwidth to admit this new call into the network, this call will be in the reject state and stay there until bandwidth is reserved for this call. On the other hand, if we have handoff call which is moving to another highly congested part of the network, this call might be rejected and transferred to the reject state until some bandwidth is available. The transition probabilities from reject state to the other states are denoted by P01, P02, P03. The last transition probability P00 happened when the call in the reject state and still there is no bandwidth available.

Ÿ One path state (state 1): when a new call is arriving it will be in state 0, suppose that there is enough available bandwidth in the network, then there is no need to trigger the multi-homing feature and the packets for this call is routed from source to destination through one route only and the call is transferred into state 1 with transition probability P01. However, if there is no available bandwidth in the network, multi-homing feature is triggered to choose more than one AP as needed and the call is transferred from state 0 to either state 2 or state 3 with transition probabilities P02 and P03, respectively. The transition probabilities from one link state to the other states are denoted by P10, P12, P13. The last transition probability P11 happened when the user call packets are routed though one path and the user is not moving.

Ÿ Joint paths state (state 2): a call will be in this state if the packets are routed through two different paths which are joint, denoted by J (П1, П2). This could be for new or handoff calls arriving into a highly congested network and obliged to connect to two different AP and make two joint paths, The transition probabilities from joint link state to the other states are denoted by P20, P21, P23. The last transition probability P22 happened when the call in the joint link state and still there is no bandwidth available.

Ÿ State 3. In this state of the presented Markov model, the mobile terminal is connected to two access points that create disjoint paths. P33 is the probability that the mobile terminal is again in disjoint paths state. P31 is the probability when the mobile terminal connected with just one access point. One of the reasons for this occasion could be lost signal with one of the two connected AP when mobile terminal gets in a position where it can receive signal from just one AP. P32 is the probability for transition from disjoint paths state to joint paths state. This transition probability can happen if, for example, some of the routers in the joint link have some failure and joint link cannot be established. P30 is the transition probability when the mobile terminal will end the active session when it is in the disjoint paths state.

From the above explained states and state transition probabilities we can develop the following matrix P. We can use Psi[x] to present the steady-state probability at some x-th moment. Using Pij[x] we can denote the transition probabilities from state i to state j, where i, j Î 0,1, ×××, Nstate. In our case Nstate is equal to 3. Using this terms the matrix P will be given by:

(8)

When a terminal starts a new connection, it changes the idle state 0 to some of the nonzero states. If the terminal finishes the session while it is in some of the nonzero states, the transition to state 0 is accomplished. All the states of the proposed Markov model are recurrent non-null and the equilibrium state probabilities can be determined solving the equation 11. The sum of the steady-state probabilities is equal to 1, so we can write:

(9)

In practical scenarios, factor that has the greatest influence on the values of the above mentioned steady-state probabilities Psi[x] is the coverage of the access points. If the mobile terminal while moving most of the time is in overlapping coverage of two or more access points steady-state probabilities Ps2[x], Ps3[x] are more probable. So, in this case Ps2[x], Ps3[x] would have higher values than Ps1[x]. But, if most of the time mobile terminal moves in locations with coverage of just one access point, then steady-state probabilities Ps1[x], Ps0[x] would have higher values, and this is especially true for Ps0[x] when the network is congested and the accessibility of the access points is low.

In our proposed model we will use the well-known Poisson process to describe the arrival of the new sessions (packets or calls) in the coverage areas with mean arrival rates of λ1-link, λjl (jl means joint link) and λdl (dl means disjoint link).

The duration of the session will be denoted with Tsession. This duration of the session is exponentially distributed with a mean of 1/μ. μ represents the average completion rate of the session. Probability of the session termination or completion will be denoted with Ptermination. From the Markov model in the Figure 2 it can be concluded that:

(10)

Inter-arrival time will be denoted with Tiar and it is equal to:

(11)

Since, we previously developed 4 states in the proposed Markov model for the proposed routing algorithm, it is obvious that:

(12)

According to the above conditions, the probability that the mobile terminal is connected to the disjoint link will be:

(13)

The probability that the mobile terminal is connected to the joint link will be:

(14)

The probability that the mobile terminal is connected to just one link is going to be:

(15)

Hence, according to all previously developed equations related to the proposed Markov model it is apparent that the probability of the new session arrival with one link will be Pnew1-link = P01, and to the joint link and disjoint link, Pnewjl = P02, Pnewdj = P03. So, we can conclude that the probability of the new session arrival will be expressed as:

(16)

We already developed Markov model for the proposed routing scheme. So, after defining the states, probabilities and arrival rates of the sessions using One Link, Joint Link and Disjoint Link States, now we could build numerical analysis of the horizontal handover probabilities of the possible links. The overall horizontal handover probability is:

(17)

Every state that was previously explained in the Markov model includes a group of events that are denoted with Si, because each of these three different types of links has a number of access points and routers, denoted with Nr. The probability of being in any of the three defined states Ps1, Ps2, Ps3 is specified with the probability of being connected with one link, joint links or disjoint links inside the network. Hence, we can write:

(18)

where Psiz[x] is the probability that the mobile terminal is attached to the z-th access point or router from i-th link (the link could be One Link, Joint Link or Disjoint Link) at the x-th moment of time. Hence, the probabilities of the state transitions can be written as:

(19)

Each of the probabilities could be computed using the horizontal handover algorithm. The transition probability from state i to state j could be written in terms of the rewards and joint degree weight variables as follows:

(20)

where wijr is the joint degree weight which expresses the number of common links between the old primary path and the new candidate path r in case of moving from state i to state j. The multi-homed joint route has the highest joint degree weight in case of a highly congested network. Rij is the reward assigned in case of moving from state i to state j in every possible route r.

4.2. Rewards and Discount Factors

In this section we will develop the reward and discount factor of the Markov Decision Process for the proposed model. We will denote Ra (Si, Sj) as immediate reward or expected immediate reward received after transition to state Sj from state Si. We will also define here γ Î [0,1] as the discount factor, which presents the difference in importance between future rewards and present rewards. We must mention in this context that the theory of Markov Decision processes doesn’t declare that states or actions (in our case denoted as transitions from one state to another) are finite. But, in our proposed model we assume that they are finite.

Each of the states in our model has a reward denoted as {R0, R1, R2, R3}. On each time step, we can assume that our state is Si get given reward Ri and randomly move to another state P(NextState = Sj/ThisState = Si) = Pij, all future rewards are discounted by γ.

We will use J*(Si) to define the expected discounted sum of future rewards starting with the state Si. So we will have:

(21)

If we use vector notion we can write:

(22)

Now, we will remind ourselves that we proposed a markov model system with 4 possible states: idle state, one path state, joint state and disjoint state. A reward or payoff is presenting the cost of serving the user and this value depends of the type of the session, new session or handover session. Our aim is to accept or reject users in order to maximize the expected value of the rewards.

Call admission control according to our proposed model work in this way for the new sessions, if the requested bandwidth of the new session is equal to or below the actual available bandwidth of the accessible access point, then the transition from State 0 to State 1 is more reasonable because one path is enough to fulfill the user’s requirements. But, if the requested bandwidth of the new session is above the available bandwidth of the accessible access point (it happens when the network is highly congested), our proposed routing algorithm suggests multi-homed joint path to be used in order to have more optimized network. If the requested bandwidth of the new session is still above the offered bandwidth of the access points that obtain joint link, then the new session will be finally blocked in this case. Disjoint path state is the option used by algorithms proposed in the literature. Comparison between multi-homed joint paths and non multi-homed disjoint paths is introduced in the result section.

Call admission control according to our proposed model work in this way for the handoff sessions, If the mobile terminal is in State 1 connected to one path and it is in the phase of handover, then if the requested bandwidth of the mobile terminal is equal or below the offered bandwidth from the new accessible access point, the best solution is again to have one path. So, in this case mobile terminal will stay in the same State 1. But, if the offered bandwidth from the new accessible AP is below the requested, then mobile terminal will try multi-homed joint link, so transition to State 2 will be made. Furthermore, if joint link is not possible, then the handoff call will be blocked. A comparison between multi-homed joint paths and non multi-homed disjoint paths is introduced in the result section. Those are the most important state transition, other state transitions are explained before. Taking into our consideration, that the new call can be admitted into the network with the specified QoS required by the call, without affecting the QoS for the existing calls in the network [23] .

5. System Model

System model consists of one gateway and 10 to 25 mesh routers which are uniformly distributed to cover the whole simulation area of 400m × 400m and serve the arriving new and handoff calls. All mesh routers are connected to other neighboring routers in their transmission range as shown in Figure 3 below. The arrival of new calls are described using Poisson process with arrival rate λ, the duration of the call is exponentially distributed with a mean of 1/µ, where µ is the average completion rate of a call. The users are moving randomly within the same domain, which means that we are dealing with horizontal intra domain handoff scenarios. Our proposed algorithm is tested when the network is highly congested with link bandwidth utilization equal to Lu. QoS requirement for both new and handoff calls should be met.

Figure 3. System model.

6. Numerical Results

In our simulation, the MAC layer used protocol between the mesh routers is 802.11a with frequency band of 5GHz where eight non-overlapping channels are used simultaneously without interference. The communication between the mesh clients and routers is done using 802.11b with frequency band of 2.5 GHz and only three orthogonal channels are available to use. The list of simulation parameters are shown below in Table 3.

Below are the results, showing a comparison between our proposed algorithm and disjoint routing algorithm used in the literature.

Figure 4 shows the New Call Blocking Probability (NCBP) when the congestion level increases in the network for both cases, multi-homing and non multi-homing scenarios are simulated. When the level of congestion is low and the resources are available, multi-homing and non multi-homing scenarios are having the same blocking probability. However, when the congestion is increasing the necessity of using multi-homing is increased in order to reduce the blocking probability for the new call, as the traffic is divided between two different disjoint paths.

Handoff Call Blocking Probability (HCBP) is calculated taking into our consideration the four possible scenarios shown in Figure 5 below. For the handoff calls, our proposed algorithm outperforms other algorithms whenever we have a high level of congestion in the network. A maximally jointed path with the old primary path is giving us better blocking probability compared to the disjoint routing since less resources are needed to connect the new path with the old path whereas more resources are needed in case of disjoint routing, so in case of the high level of congestion the needed resources to establish the call might not be available and the call might be blocked. Multi-homing is adding another level of assurance for reducing HCBP, where the required bandwidth for the handoff call is divided between two access points in order to maintain the QoS requirements for the handoff call.

Number of Hard Handoffs (NHH) is the number of times the handoff call is disconnected due to lack of resources. Regardless of the applied algorithm, the number of hard handoffs in the system is increasing when the congestion is increasing. However, our proposed algorithm reduces NHH since it forces the handoff call to be routed to a maximally jointed path with the old reserved path and it also provides the feature of using multi-homing in case of congestion is existing in the network as shown in Figure 6.

In Figure 7, Handoff Delay (HD) is calculated. As previously defined, handoff delay is calculated on three layers which are application, network and data link layer. The most dominant part in the handoff delay is the one located in the network layer which is related to routing. As shown in Figure 7, we can notice that when multi-homing is used in case of disjoint routing the handoff delay is bigger than the case when there is no multi-homing and disjoint routing, this is because in the case of multi-homing two routes should be discovered. The

Table 3. Simulation parameters.

Figure 4. New call blocking probability (NCBP).

Figure 5. Handoff call blocking probability (HCBP).

best handoff delay is obtained when multi-homing feature is disabled and joint routing is enabled, in this case only one route should be discovered which is maximally jointed with the old route.

We assume that when a new or handoff call reaches our network a connection should be established before the real data transmission starts. Uplink Constant Bit Rate (CBR) traffic is assumed to be sent from all the mesh clients to the destination gateway through one or more mesh routers. The packets reaching to each mesh router is handled using Time Division Duplex (TDD). Our proposed routing algorithm is distributed, which means that

Figure 6. Number of hard handoffs (NHH).

Figure 7. Handoff delay (HD).

each router is responsible for making the routing decision based on notification messages received periodically from the neighboring routers to know the buffer occupancy, bandwidth availability in each candidate next mesh router and the joint degree metrics. Random waypoint model is used to simulate the movement of the mobile users in the network. In our proposed protocol, the congestion status monitoring in each link in the network is essential.

As a resource allocation framework multi-hop relay is introduced for 5G networks [24] , for better capacity and coverage, future work can be done to design a seamless handoff solution in multi-hop 5G networks taking into consideration our proposed algorithm to improve the QoS provided by existing handoff management algorithms proposed in the literature.

The network traffic pattern is dynamic, and changes in an unexpected way is normal thing to face. An enhancement of our proposed algorithm is to design a network traffic pattern prediction algorithm, [25] , and use the result of the prediction in the routing decision for better QoS.

7. Conclusion

The routing and admission control is studied jointly in this paper, where a novel routing protocol is merged with multi-homing to get better QoS for new and handoff calls in WMN. Handoff algorithms proposed in the literature find a new path for the handoff call which is completely disjointed with the old primary path, and reject the calls in case of highly congested networks. Our proposed algorithm introduces a new routing approach for new and handoff calls which is based on finding a maximally jointed path with the old primary path and enable the multi-homing feature in case of highly congested network. Our proposed algorithm is compared with four different scenarios where multi-homing and joint routing is enabled or disabled. An MDP markov model is introduced and solved using value iteration method to find a near optimal solution. Our proposed algorithm, MDACR, outperforms other algorithms proposed in the literature in terms of handoff delay, new and handoff calls blocking probability, and number of hard handoffs especially in the case of highly congested networks. MDACR gives the mobile user with seamless handoff approach with higher admitted users in the network.

Cite this paper

Fawaz A. Khasawneh,Abderrahmane Benmimoune,Michel Kadoch, (2016) Joint Routing and Admission Control in Wireless Mesh Network. International Journal of Communications, Network and System Sciences,09,311-325. doi: 10.4236/ijcns.2016.98028

References

  1. 1. Akyildiz, I.F. and Wang, X.D. (2005) A Survey on Wireless Mesh Networks. IEEE Communications Magazine, 43, S23-S30.

  2. 2. Xie, J. and Wang, X. (2008) A Survey of Mobility Management in Hybrid Wireless Mesh Networks. IEEE Network, 22, 34-40.
    http://dx.doi.org/10.1109/MNET.2008.4694172

  3. 3. Sun, X.-M. and Lv, X.-Y. (2009) Novel Dynamic Ant Genetic Algorithm for QoS Routing in Wireless Mesh Networks. 5th International Conference on Wireless Communications, Networking and Mobile Computing, WiCom’09, 1-4.
    http://dx.doi.org/10.1109/wicom.2009.5305851

  4. 4. Song, W. and Fang, X.M. (2006) Routing with Congestion Control Using Cross-Layer Design in Wireless Mesh Network. IET International Conference on Wireless, Mobile and Multimedia Networks, 1-3.

  5. 5. Qu, Z.Y., Ren, W.W. and Wang, Q.C. (2010) A New Node-Disjoint Multi-Path Routing Algorithm of Wireless Mesh Network. International Conference on Computer, Mechatronics, Control and Electronic Engineering (CMCE), 4, 1-3.

  6. 6. Tarn, W.-H. and Tseng, Y.-C. (2007) Joint Multi-Channel Link Layer and Multi-Path Routing Design for Wireless Mesh Networks. INFOCOM 2007, 26th IEEE International Conference on Computer Communications, 2081-2089.

  7. 7. Draves, R., Padhye, J. and Zill, B. (2004) Routing in Multi-Radio, Multi-Hop Wireless Mesh Networks. Proceedings of the 10th Annual International Conference on Mobile Computing and Networking (MobiCom’04), ACM, New York, 114-128.
    http://dx.doi.org/10.1145/1023720.1023732

  8. 8. Ren, M.S., Liu, C., Zhao, H.Z., Zhao, T. and Yan, W. (2007) MEMO: An Applied Wireless Mesh Network with Client Support and Mobility Management. IEEE Global Telecommunications Conference, GLOBECOM’07, 5075-5079.
    http://dx.doi.org/10.1109/glocom.2007.962

  9. 9. Huang, R.S., Zhang, C. and Fang, Y.G. (2007) A Mobility Management Scheme for Wireless Mesh Networks. IEEE Global Telecommunications Conference, GLOBECOM’07, 5092-5096.
    http://dx.doi.org/10.1109/glocom.2007.965

  10. 10. Wang, H., Huang, Q., Xia, Y., Wu, Y.C. and Yuan, Y.G. (2007) A Network-Based Local Mobility Management Scheme for Wireless Mesh Networks. IEEE Wireless Communications and Networking Conference, WCNC, 3792-3797.
    http://dx.doi.org/10.1109/wcnc.2007.694

  11. 11. Hung, T.C., Phuc, L., Duy, N.N., Quynh, D.N.T., Cuong, L.Q., Jung, B.K. and Kang, Y. (2009) The Proposed Improvement 3-Layer Mobility Management Scheme for Wireless Mesh Networks Using IP Prefix Mechanism. 11th International Conference on Advanced Communication Technology, ICACT 2009, 2, 953-958.

  12. 12. Li, Y.N. and Chen, I.-R. (2012) Mobility Management in Wireless Mesh Networks Utilizing Location Routing and Pointer Forwarding. IEEE Transactions on Network and Service Management, 9, 226-239.

  13. 13. Majumder, A. and Roy, S. (2012) A Forward Pointer Based Mobility Management Scheme for Multi-Hop Multi-Path Wireless Mesh Network. International Conference on Data Science & Engineering (ICDSE), 194-197.
    http://dx.doi.org/10.1109/icdse.2012.6281899

  14. 14. Majumder, A., Roy, S. and Kumar Dhar, K. (2013) Design and Analysis of an Adaptive Mobility Management Scheme for Handling Internet Traffic in Wireless Mesh Network. Annual International Conference on Emerging Research Areas and 2013 International Conference on Microelectronics, Communications and Renewable Energy (AICERA/ ICMiCR), 1-6.
    http://dx.doi.org/10.1109/aicera-icmicr.2013.6575968

  15. 15. Li, H. and Xie, J. (2013) GaS: A Gateway Scheduling-Based Handoff Scheme in Single-Radio Infrastructure Wireless Mesh Networks. Proceedings IEEE of INFOCOM, Turin, 1860-1868.
    http://dx.doi.org/10.1109/infcom.2013.6566985

  16. 16. Li, H. and Xie, J. (2014) GaS: A Gateway Scheduling-Based Beamforming Scheme for Handoff Support in Wireless Mesh Networks. IEEE Transactions on Vehicular Technology, 63, 4560-4573.
    http://dx.doi.org/10.1109/TVT.2014.2313144

  17. 17. Mamidi, A.V., Babu, S. and Manoj, B.S. (2015) Dynamic Multi-Hop Switch Handoffs in Software Defined Wireless Mesh Networks. 2015 IEEE International Conference on Advanced Networks and Telecommunications Systems (ANTS), Kolkata, 15-18 December 2015, 1-6.
    http://dx.doi.org/10.1109/ANTS.2015.7413638

  18. 18. Qin, L. and Zhao, D. (2015) Channel Time Allocations and Handoff Management for Fair Throughput in Wireless Mesh Networks. IEEE Transactions on Vehicular Technology, 64, 315-326.
    http://dx.doi.org/10.1109/TVT.2014.2320596

  19. 19. Majumder, A. and Roy, S. (2014) A Tree Based Mobility Management Scheme for Wireless Mesh Network. 2014 2nd International Conference on Emerging Technology Trends in Electronics, Communication and Networking (ET2ECN), Surat, 26-27 December 2014, 1-8.
    http://dx.doi.org/10.1109/et2ecn.2014.7044983

  20. 20. Khasawneh, F.A., BenMimoune, A., Kadoch, M. and Osama, S.B. (2014) Intra-Domain Handoff Management Scheme for Wireless Mesh Network. Proceedings of the 12th ACM International Symposium on Mobility Management and Wireless Access, Montreal, 21-26 September 2014, 9-13.

  21. 21. Khasawneh, F.A., BenMimoune, A., Kadoch, M., Alomari, A. and Al-Khrayshah, M. (2015) Multihoming Admission and Mobility Management in Wireless Mesh Network. 2015 International Conference on Computer, Information and Telecommunication Systems (CITS), Gijon, 15-17 July 2015, 1-5.
    http://dx.doi.org/10.1109/CITS.2015.7297763

  22. 22. Zhao, W. and Xie, J. (2012) IMeX: Intergateway Cross-Layer Handoffs in Internet-Based Infrastructure Wireless Mesh Networks. IEEE Transactions on Mobile Computing, 11, 1585-1600.
    http://dx.doi.org/10.1109/TMC.2011.192

  23. 23. Dhurandher, S.K., Woungang, I., Obaidat, M.S., Kumar, K., Joshi, M. and Verma, M. (2015) A Distributed Adaptive Admission Control Scheme for Multimedia Wireless Mesh Networks. IEEE Systems Journal, 9, 595-604.
    http://dx.doi.org/10.1109/JSYST.2013.2296336

  24. 24. BenMimoune, A., Khasawneh, F.A., Kadoch, M. and Rong, B. (2015) Resource Allocation Framework in 5G Multi-Hop Relay System. 2015 IEEE Global Communications Conference (GLOBECOM), San Diego, 6-10 December 2015, 1-6.

  25. 25. Khasawneh, F.A., Benmimoune, A., Kadoch, M. and Khasawneh, M.A. (2015) Predictive Congestion Avoidance in Wireless Mesh Network. 2015 3rd International Conference on Future Internet of Things and Cloud (FICloud), Rome, 24-26 August 2015, 108-112.
    http://dx.doi.org/10.1109/FiCloud.2015.69