Development of A New Efficient Routing Scheme for WiMAX Mesh Networks

Published Online November 2013 in MECS

WiMAX (Worldwide Interoperability for Microwave Access) is a telecommunications protocol that provides fixed and mobile Internet access. The current WiMAX revision provides up to 40 Mega-bit/s with the IEEE 802.16m update expected to offer up to 1 Giga-bit/s fixed speeds. The name "WiMAX" was created by the WiMAX

Forum, which was formed in June 2001 to promote conformity and interoperability of the standard. The forum describes WiMAX as "a standards-based technology enabling the delivery of last mile wireless broadband access as an alternative to cable and DSL" [1].

The architecture of WiMAX mesh network is almost same as WMN (Wireless Mesh Network) [2]. Based on the wireless mesh network, the IEEE 802.16/WiMAX standard provides a mechanism for creating multi-hop mesh, which can be deployed as a high speed wide-area wireless network. The objective of our present work is an efficient approach for increasing the utilization of WiMAX mesh through appropriate design of multi-hop routing through a scheduling.

The rest of the paper is organized as follows. In section II, we give a short overview of wireless mesh network architecture. Section III presents different routing and scheduling strategies. In section IV,the proposed algorithm and its computational complexities are determined. The simulation results of the proposed algorithm are presented in section V and followed by conclusions in section VI.

• II.    Wireless Mesh Network

A wireless mesh network is a communications network made up of radio nodes in which there are at least two pathways of communication to each node. The coverage area of the radio nodes working as a single network becomes a mesh cloud. Access to this mesh cloud is dependent on the radio nodes working in harmony with each other to create a radio network [3]. When one node can no longer operates, all the rest can still communicate with each other, directly or through one or more intermediate nodes [4]. Wireless mesh builds routes between nodes only as desired by originating nodes. It maintains these routes as long as they are needed by the originating node. Wireless mesh nodes forms paths in term of hops which connect together to form the wireless mesh network [5].

• A. Mesh Architecture [4]

Wireless mesh architecture is a first step towards providing cost effective and dynamic high-bandwidth networks over a specific coverage area. Wireless mesh architectures infrastructure is, in effect, a router network minus the cabling between nodes. It's built of peer radio devices that don't have to be cabled to a wired port like traditional WLAN access points (AP) do. Mesh architecture sustains signal strength by breaking long distances into a series of shorter hops. Intermediate nodes not only boost the signal, but cooperatively make forwarding decisions based on their knowledge of the network, i.e. perform routing. Such architecture may with careful design provide high bandwidth, spectral efficiency, and economic advantage over the coverage area [6].

The architecture of WMNs can be classified into three main groups based on the functionality of the nodes. These are:

• 1.    Infrastructure/Backbone WMNs,

• 2.    Client WMNs,

• 3.    Hybrid WMNs [4].

Infrastructure/Backbone WMNs: An infrastructure wireless mesh network (WMN) is a hierarchical network consisting of mesh clients, mesh routers and gateways. Mesh routers constitute a wireless mesh backbone, to which mesh clients are connected as a star topology, and gateways are chosen among mesh routers providing Internet access. [4]

Client WMNs: Client meshing provides peer-to peer networks among client devices. In this type of architecture, client nodes constitute the actual network to perform routing and configuration functionalities as well as providing end user applications to customers. Hence, a mesh router is not required for these types of networks. In Client WMNs, a packet destined to a node in the network hops through multiple nodes to reach the destination. Client WMNs are usually formed using one type of radios on devices[5].

Hybrid WMNs: This architecture is the combination of infrastructure and client meshing. Mesh clients can access the network through mesh routers as well as directly meshing with other mesh clients. While the infrastructure provides connectivity to other networks such as the Internet, Wi-Fi, WiMAX, cellular, and sensor networks; the routing capabilities of clients provide improved connectivity and coverage inside the WMN. The hybrid architecture will be the most applicable case in our opinion[5].

• III.    Routing and Scheduling

Routing and scheduling is one of the most important scopes for improvement in WiMAX network. A good routing algorithm along with a scheduling algorithm controls the performance of the network. We have worked on the WiMAX mesh network with centralized routing and scheduling. In centralized scheduling and routing, we can use two types of radio link: Multiple radio link and single radio link. But here we are working

Figure 1: WiMAX Modes of operation.

on single radio link. In Mesh architecture route calculation is needed and to calculate route, we need scheduling. We have used Time Division Multiplexing (TDM) for radio access. In Fig. 1 we show the hierarchy architecture of WiMAX and the bold faceddouble line enclosed field is our working area.

• A.    Routing

A system that has a direct connection to the backhaul services outside the mesh network is termed as the meshBS. All the other systems of a mesh network are termed mesh SSs. Routing is the process through which the route of packet transmission between BS and SSs are determined. This is important, because in the WiMAX mesh network every SS is connected to internet or other network via BS. The route selectionprocedure is not arbitrary; rather it is based on some criteria or rules which is defined previously is called routing algorithm. Routing algorithms are divided into two categories depending on where the algorithm is running. These are:

• 1.    Centralized routing.

• 2.    Distributed routing.

If the routing algorithm runs on each nodes of the system then it is called distributed routing and if routing algorithm runs in BS only then it is called centralized routing. For details understanding of routing let’s consider an example shown in Fig. 2.

Figure2: A topology showing transmission range of all nodes.

Consider the transmission patterns of all nodes are Omni-directional/circular and equal transmission range of all nodes. In the figure2 the circle indicates the transmission range of each node. Here notice that, SS1 is within the transmission range of BS and SS2. SS2 is within the transmission range of SS1 and SS3. SS3 is within the transmission range of SS2. So SS1 can directly communicate with BS, SS2 as they are within the transmission range of SS1. Similarly SS2 can directly communicate with SS1 and SS3. And SS3 can directly communicate with SS2. These available communication paths/links are shown in figure 3 by line. Here the nodes which are within the transmission range of another node are called the neighbors of the last node. For example if we consider SS2, then its neighbors are SS1 and SS3. So a node can directly communicate only with its neighbor nodes and a node out of transmission range of BS communicates with BS via its neighbors and intermediate nodes.

BS

SS1

SS2

SS3

• Figure3: Network topology showing all links

Now observe that, for SS1 there is only one way to communicate with BS. But for SS2 and SS3 there are more than one way to communicate with BS. For SS2 and SS3 only one way must be used from all available ways to communicate with BS depending on the routing algorithm. This way selection to communicate between BS and all SSs is the routing. After selecting all the routes of all nodes we get a tree called routing tree [5].

• B.    Scheduling

In the mesh mode, scheduling is one of the most important problems that will impact the system performance. A scheduling is a sequence of fixed-length time slots, where each possible transmission is assigned a time slot in such a way that the transmissions assigned to the same time slot do not collide. Generally, there are two kinds of scheduling –

• 1.    Broadcast scheduling and

• 2.    Link scheduling.

In a broadcast scheduling, the entities scheduled are the nodes themselves. The transmission of a node is intended for, and must be received collision-free by all of its neighbors. While in a link scheduling, the links between nodes are scheduled. The transmission of a node is intended for a particular neighbor, and it is required that there be no collision at this receiver [7].

In[7] a study on collision-free centralized scheduling algorithm has done which is conformed to the defined mesh mode in IEEE 802.16 standard. Compared within existing scheduling algorithms, this scheme considers some distinct features of WMNs, such as the function of access networks and the inherent relay model. Moreover, this scheduling algorithm also considers some important performance metrics, such as fairness, channel utilization ratio and transmission delay.

There are three kinds of scheduling in IEEE 802.16 mesh mode:

• 1.    Centralized scheduling

• 2.    Coordinated distributed scheduling and

• 3.    Uncoordinated distributed scheduling [5].

In centralized scheduling, the BS shall gather traffic demands through MSH-CSCH (Mesh Centralized Scheduling) messages from all the SSs within a certain hop range and communicates the information to all the SSs. Subsequently, the SSs determine their own transmission opportunities in a distributed fashion, using a common predetermined algorithm with the same input information. Therefore, the outputs are the same for all these SSs.

The SSs will let the BS know their changes of traffic demands through MSH-CSCH messages. Then the BS will rebroadcast the adjusted traffic demands and the SSs can recalculate their transmission opportunities [7]. To quote IEEE 802.16 standard [7,8], the advantage of centralized scheduling is that ‘‘it is typically used in a more optimal manner than distributed scheduling for traffic streams, which persist over a duration that is greater than the cycle time to relay the new resource requests and distribute the updated schedule’’.

C.Existing Routing Algorithms

Many researchers have gone on centralized routing and scheduling in wireless mesh network using single radio links. In[9], the authors proposed a breadth first search algorithm to construct routing tree. According to this algorithm, when a new node that plans to join an active mesh network scans for active networks and listens to MSH-NCFG (Mesh Configuration) message. The new node starts the network entry process based on the information given by MSH-NCFG. Among all possible neighbors that advertise MSH-NCFG, the joining node selects a sponsoring node to connect to. A mesh network entry (MSH-NENT) message with net entry request information is then sent by the candidate node.

In [10], authors worked on interference aware IEE 802.16 mesh networks. They proposed interference aware routing and scheduling algorithm. They proposed an efficient approach for increasing the utilization of WiMAX mesh through appropriate design of multi-hop routing and scheduling. As multiple-access interference is a major limiting factor for wireless communication systems, they adopt an interference-aware design to increase the throughput of the wireless mesh network [5]. In particular, their scheme creates a tree-based routing framework, which along with scheduling is interference aware and results in a much higher spectral efficiency. Performance evaluation results show that their proposed interference-aware scheme achieves significant throughput enhancement over the basic IEEE 802.16 mesh network. Their proposed scheme includes a novel interference-aware route construction algorithm and an enhanced centralized mesh scheduling scheme, which consider both traffic load demand and interference conditions. This interference-aware design approach will lead to better spatial reuse and thus higher spectral efficiency [10].

To achieve efficient spectral utilization and high throughput in 802.16 mesh networks, the route construction within the mesh network is crucial. To this end, authors proposed an interference-aware route construction algorithm that considers interference condition in the mesh network [10]. The concept of blocking metric B ( k ) of a given route from the Mesh BS toward an SS node k is introduced to model the interference level of routes in the mesh. The blocking metric B ( k ) of a multi-hop route indicates the number of blocked (interfered with) nodes by all the intermediate nodes along the route from the root node toward the destination node k . Authors also define the blocking value b ( h ) of a node h , as the number of blocked (interfered with) nodes when node h is transmitting. Therefore, the blocking metric of a route will be the summation of the blocking values of nodes that transmit or forward packets along the route. Thus, node h ( i )’s blocking value b ( h ( i )) equals the number of neighboring nodes of h(i). The blocking metric along a route toward k , B ( k ) is equal to the summation of all the blocking value b ( h ( i )) for every node h ( i ) (including the source node and all the forwarding nodes) on the route k .Author’s design approach in the proposed interference-aware scheme is to select the routes with less interference.

To remove imperfect node selection problem it is needed to update all previous node’s route when a new node inserted. For this [5] proposes a routing algorithm. According to this algorithm, when a new node joins in the networks, then all the nodes are arranged in a list in ascending order to their distance from BS and all nodes will be set as unselected/un-routed nodes. So after that there will be no scheduling link, but all nodes have information about their neighbors. Then each node will be scanned from the ascending ordered list one by one and their route (i.e. parent) will be selected according to blocking metric concept. That means, the node will find the selected nodes from its neighbors and select one of them who have minimum blocking metric as its parent. If ambiguity occurs then it will be solved by [9] which are discussed above.

• D. Interference Aware Scheduling

IEEE 802.16 employs Time Division Multiple Access (TDMA) method and the policy for selecting scheduled links in a given time slot will definitely impact the system performance. In [7], the authors proposed a collision-free centralized scheduling algorithm for IEEE 802.16 based Wireless Mesh Networks (WMN) to provide high-quality wireless multimedia services. They designed a relay strategy for the mesh nodes in a transmission tree, taking special considerations on fairness, channel utilization and transmission delay. They also evaluated the proposed algorithm with four selection criteria through extensive simulations. The experimental results were instrumental for improving the performance of IEEE 802.16 based WMNs in terms of link scheduling.

In TDMA based links scheduling scheme, the authors made a considerable effort at maximizing the spatial reuse of the available bandwidth while at the same time eliminating the possibility of collision. Authors consider the following special scheduling problem: how to assign time slots to transmission links in IEEE 802.16 based WMNs so as (1) to reduce the length of scheduling; (2) to improve the channel utilization ratio and (3) to decrease the transmission delay, subjected to some constraints presented below (though it was partially discussed in the last chapter, hence it is discussed here again for convenience).

In particular, depending on the signaling mechanism, transmissions may collide in two ways in wireless networks: primary and secondary interference. Primary interference occurs when a node has to do more than one thing in a single time slot. The reason for this constraint is that the nodes cannot transmit and receive simultaneously and cannot transmit/receive more than one packet at the same time. Thus, this constraint is also referred to as the transmission/reception constraint. Secondary interference occurs when a receiver R tuned to a particular transmitter T is within the range of another transmitter whose transmissions, though not intended for R, interfere with the transmissions of T. This constraint is also referred to as the interference-free constraint. In [7], a SS is assigned Service Token (ST) based on its traffic demand. They use service token to allocate time slots to each link proportionally according to the traffic demand of the link’s transmitter, thus, the fairness is guaranteed (no nodes will be starved). A link can be scheduled only if the service token number of its transmitter is nonzero. Each time after a link is assigned a time slot, the service token of the transmitter is decreased by one and that of the receiver is increased by one. Thus, using the change of service token, they integrate the hop-by hop relay model of WMN into their algorithm.

• IV. Proposed Algorithm

We proposed a routing algorithm which removes the problems from the previous works. Ambiguity problem is one of them. This problem is removed by following:

• •    If there are more than one neighbor nodes with minimum blocking metrics, then select a node among them which have minimum hops to/from BS.

• •    If there are also more than one node with minimum hops no from/to BS, then select the node of minimum node id among them.

• •    There is no need to reset the channels again through all the SS.

• •    SS id will be managed by the BS.

• •    No need to sort the all SS. Only all SSs which are in BSs transmission range will be sorted. So some times will be saved and it will maintain a relation with the real time network mechanism.

• A.    Interference Aware New Routing Algorithm

Our proposed algorithm minimizes the time cost that is needed to reset all the nodes as unselected nodes which is the key term of routing algorithm in [5]. We captioned it as Interference Aware New Routing Algorithm.

• 1.    Set BS as selected/routed node.

• 2.    Sort all nodes in ascending order according to distance from BS which are placed in BS transmission range.

• 3.    Find neighbors and then selected nodes from neighbors.

• 4.    Find the node with minimum blocking metrics from selected nodes.

• 5.    Select the node with minimum hop, if there is more than one node in step 4.

• 6.    Select a node with minimum id, if there is more than one node in step 5.

• 7.    Set the node in step 6 as parents of scanned node.

• 8.    Set the scanned SS as routed/selected node and broadcast its route details to all his neighbor nodes.

• 9.    If any routed neighbor node of scanned SS finds less route cost from received route details than his parent node, do step 3 to 8.

Do steps 2 to 9 for each new node when inserted

• B.    Time Complexity Analysis

Let we start with the ref.[10], ti = route calculation time when ith node is inserted.

For n nodes total route calculation time is

T n 1 = t 1 + t 2 + ... + t n

Average route calculation time when a new node is inserted

Here, t does not vary so much than t_i , because in Interference Aware Routing Algorithm the route of new nodeis determined by using only its neighbor’s information.

So we can rewrite eq. (1) as, T_n 1 = n x t                (3)

Let, s = average time to sort all nodes in ascending order according to distance from BS.

Route calculation time of i th node

= i x ( 5 + t )

= i x t ; As 5 is very small compare to t .               (4)

Now considerref.[5],

For n nodes, total route calculation time

T n 2 = ( 5 + t ) + ( 5 + 2 t ) + ... + ( 5 + nt )

= n x 5 + (1 + 2 +... + n) x t n (n + 1)

= n x 5 + 2 x t(5)

For the proposed algorithm,

Total route calculation time for n nodes,

T_n 3 = ( 5 + t ) + ( 5 + t ) + ... + ( 5 + t )

= n x (5 + t)(6)

Performance gain compared to ref. [5]

n x (5 + t)

n(n+1)

n x 5 + 2 x t   5 + 2^7 x t t ; since s is very small compared to t n + 1

When n =1, from eq. (7) we found the ratio is 1, that means proposed algorithm needssame amount of time. But when n is very large, we can see that proposed algorithmdemands much less time compared to the algorithm in [5].

Now, Performance gain compared to ref. [10]

n x ( 5 + t ) n x t

5 + t

t

Here, we need only extra sorting time when comparing with [10]. And this sorting time is very small, because sorting occurs only once. So, setting s = 0 in eq. (8) gives a performance gain = 1, i.e. proposed algorithm is not better as well as no worse than that of ref. [10].

However, after connecting to the network if its neighbor finds that connected node has less cost to connect with the BS than its parent node, then that neighbor will change its’ parent and will connect with that new node. So here a time is required to change the parent node but this time is very small with respect to ( s + t ). If this time is represented as t p , then total time of eq. (6) becomes

^T n 3 = ^{n x ( 5 +} t ) ⁺ t p                                    ⁽⁹⁾

But t_p << n ×( s + t )

So we can write eq. (9) as, T_{n 3} = n x ( 5 + 1 )          (10)

• V.    Performance Evaluation

In this chapter we show the simulation results using four routing algorithms and one scheduling algorithm. Our simulation is based on centralized scheduling and one directional transmission. The parameters set for the performance evaluation are the Scheduling Length (SL), Channel Utilization Ratio(CUR) and average transmission delay. But we did not show simulation results of average transmission delay, because it is proportional to scheduling length. The length of scheduling is the most important performance measure of a scheduling/routing algorithm and it is considered in most of the existing literatures. From our simulation, first we find which scheduling criterion is best. Then we show that which routing algorithm gives the better performance using the best scheduling criterion. We find our routing algorithm gives the better performance over others in the aspect of scheduling length.

• A.    Simulation Setup

We have developed a simulation model using C programming language. Using this model any routing or scheduling algorithm can be run on a network topology and gives the output in terms of scheduling metric, Channel Utilization Ratio (CUR), scheduling length. It gives the visualized output of the network. The simulation model has designed in such a way that a given number of nodes can be randomly/manually distributed in an area of size 55 by 45 units. In our simulation, BS is placed at the center of the simulation area and nodes are distributed randomly around the BS. Each SS and BS has a fixed transmission range (it may be varied). All the simulation results presented here were obtained by running the simulation 100 times in randomly distributed nodes. We used equal ST for all nodes, so that the fairness is maintained.

First we set transmission range of all nodes to 4.5 units, minimum separation between nodes 2.5 units, maximum distance from BS is 4.9 units and vary the number of nodes from 50 to 100. Under this condition we take the output in terms of scheduling length and CUR for each of four routing algorithms. For each case we use the four scheduling criterion – nearest, farthest, random and minimum interference.

• B.    Simulation Results

In the graph we have denoted [9], [10], [5] and our proposed algorithm as RA1,RA2, RA3 and RA4respectively to express them easily. Now we will show some graphs to find out how our proposed algorithm works in different scheduling criteria.

CUR and SL Comparison: Inthis step of simulation, we compare the SL and CUR of four routing algorithm in the same environment. Here, transmission range of all nodes is 4.5 units; maximum distance from BS is 4.9 units. We used nearest scheduling criteria to compare among the four algorithms.

In case of nearest criteria, nodes that are nearest to the BS will get time slot first. If more than one node has same distance then tie is broken by using node id. Node with smaller id will get slot first [7], [11]. Our proposed routing algorithm is performing better than the RA1, RA2, and RA3algorithms. Fig. 4.(a)We can see that our algorithm is not performing well in the beginning as others are performing. But when the numbers of nodes are increasing, our algorithm is performing better than theothers. This is happening because every time, we are not constructing entire network for new nodes. We are only updating the neighbor nodes of the new node. Before connecting the new node to the network, we have to calculate less which means we have less interference. Performances will decrease for nearest scheduling criteria when transmission range is increasing. Because, Whentransmission range will increase, BS will get morenodes in his range and all of them will try to connect with BS in a single time slot. So interference will increase. When transmission range will increase, the network will act like Point to Multi-Point (PMP) architecture [12]. Because BS will get more nodes in his range andthese nodes will directly get connected with BS. In PMP, BS is connected with every SS directly. For PMP no routing algorithm is necessary [5],[12].

(a) CUR when scheduling criteria is nearest.

(b) CUR when scheduling criteria is farthest.

(c) CUR when scheduling criteria is random.

Figure 4:Comparison of Channel Utilization Ratio(CUR)among four routing algorithms.

(d) CUR when scheduling criteria is minimum interference

In farthest criteria, nodes, farthest distance to the BS will get the time slots first. Here, our proposed algorithm is also performing better than the other algorithms. Reasons are same as described for the nearest criteria for scheduling.

In random criteria, time slot will be given to any of the present nodes. This selection has no rules, nodes are chosen randomly. We can see that our proposed algorithm is performing better than the other algorithms. Reasons are same as described for the nearest criteria for scheduling.

In minimum interference criteria, nodes which have minimum interference will get the time slot. For all of the scheduling criteria, tie will be broken with minimum id [7]. We can see from the graph that our proposed algorithm is also performing better than the other algorithms.

From the Fig.4and Fig. 5 we can see that our proposed routing algorithm (RA4) performs better than any other routing algorithm. Fig. 4 shows that the overall Channel Utilization Ratio of RA4 is always high than others. Fig. 5 represents that the average Scheduling Length of RA4 is as close as to RA3 and better (less) than RA1 and RA2. At the beginning of the network, when node number is 50, other algorithms perform slightly better than our algorithm. But when node number increases sequentially, we can see that our algorithm performs better, which means, our algorithm is better for the large topology. When node number is large, our algorithm performs slightly better than RA3 and our algorithm mainly improves the performance of RA3. Though we are not resetting the total network, ouralgorithm will not create any circumstances where connectionless situation occurs for duration of time. Again in our algorithm we have proper description about the sorting. We also state that node id management system will be maintained by BS. So from the graphs we can say that our algorithm performs better when the node number is large.

(a) SL when scheduling criteria is nearest.

(b) SL when scheduling criteria is farthest.

(c) SL when scheduling criteria is random.

(d) SL when scheduling criteria is minimum interference.

Figure 5:Comparison of Scheduling Length (SL)among four routing algorithms .

• VI.    Conclusion

In this paper, we have proposed a routing algorithm for WiMAX mesh networks to improve its’ performance in the aspect of Scheduling Length (SL) and Channel Utilization Ratio (CUR). We have evaluated the performance of our routing scheme with a centralized scheduling algorithm for relay model. Our proposed algorithm can effectively improve the network performance for every selection policy used for thesystem. This is because our proposed algorithm considers a special route selection problem which was not considered in the previous algorithms. We have cleared the node id initialization problem and have given this management system to Base Station (BS). We have limited the sorting work of BS. In the previous works, all of the nodes were sorting according to the distance from BS. But in our algorithm, we only sorting the nodes those are in BS transmission range. So there is no unnecessary sorting mechanism in our algorithm. In our proposed algorithm, when a new node appears, it doesn’t reset the total network. It connects with the BS according to the [2] and after the connection establishment it sends an advertisement to all of its neighbor nodes telling the connection information. This information may have the hop number, blocking matrices etc. By using this information neighbor nodes will decide whether to change his parent or not. The only limitation of proposed algorithm is that it needs more computational time than previous if any node found smaller route cost in its neighbor nodes than its parent node; but this will not affect the network performance significantly.