InTechOpen uses cookies to offer you the best online experience. By continuing to use our site, you agree to our Privacy Policy.

Computer and Information Science » Communications and Security » "Wireless Mesh Networks - Efficient Link Scheduling, Channel Assignment and Network Planning Strategies", book edited by Andrey V. Krendzel, ISBN 978-953-51-0672-2, Published: August 14, 2012 under CC BY 3.0 license. © The Author(s).

Chapter 1

Application of Genetic Algorithms in Scheduling of TDMA-WMNs

By Vahid Sattari Naeini and Naser Movahhedinia
DOI: 10.5772/48528

Article top


A TDMA-WMN with its conflicting links
Figure 1. A TDMA-WMN with its conflicting links
HCF super-frame structure
Figure 2. HCF super-frame structure
MAC PDU format
Figure 3. MAC PDU format
Frame structure for the mesh mode
Figure 4. Frame structure for the mesh mode
Mesh CID format
Figure 5. Mesh CID format
Topology of the scenario
Figure 6. Topology of the scenario
A typical frame (chromosome) with its SSecs (genes) associated with Figure 1
Figure 7. A typical frame (chromosome) with its SSecs (genes) associated with Figure 1
CBR packet loss versus increased number of CBR connection, while VBR and ABR connections are fixed at 1
Figure 8. CBR packet loss versus increased number of CBR connection, while VBR and ABR connections are fixed at 1
VBR packet loss versus increased number of VBR connections, while CBR and ABR connections are fixed at one
Figure 9. VBR packet loss versus increased number of VBR connections, while CBR and ABR connections are fixed at one
Residual packets in the three queues, while MTs are monotonically increased
Figure 10. Residual packets in the three queues, while MTs are monotonically increased

Application of Genetic Algorithms in Scheduling of TDMA-WMNs

Vahid Sattari Naeini and Naser Movahhedinia

1. Introduction

WMN (Wireless Mesh Network) is usually built on fixed stations and interconnected via wireless links to form a multi-hop network. Typical and inexpensive deployment of WMNs use some MSSs(Mesh Subscriber Station) and one MBS (Mesh Base Station), where their multi-hop feature can be utilized to increase their range of accessibility in rural areas effectively. Moreover, since they are dynamically self-organized and self-configuring, these networks turn to be more reliable.

TDMA-WMN (Time Division Multiple Access-WMN) is a special WMN which has some special features: TDM (Time Division Multiplexing) is adopted between MSSs and the MBS to access the air interface; frames are defined and divided into some equal duration subframes to provide better timing and synchronization to MSSs. As these subframes (called transmission opportunities) are taken by MSSs to transmit packets on unidirectional links, it’s more preferable to schedule each link rather than each node connection.

Four sources of interference are defined in TDMA-WMNs:

  • Transmitter-Transmitter: each node can’t receive data flows from more than one source.

  • Receiver-Receiver: each node can’t send data flows to more than one destination.

  • Transmitter-Receiver: each node can’t receive and transmitsimultaneously.

  • Transmitter-Receiver-Transmitter: two sources can’t transmit at the same time while the transmitter and the receiver share a neighbor which can hear both transmissions. For example, in Figure 1wherethe two conflicting links (e1 and e7) are shown with bold lines, nodes cannot transmit simultaneously as they share the same neighbor (Node 2) which can here both transmissions.

The first three sources of interference are known as first hop conflict (primary conflicts) and the fourth one is knows as second hop conflict (secondary conflicts). Second hop conflict is disregarded in most of the presented works [1], [2].


Figure 1.

A TDMA-WMN with its conflicting links

A major challenge in WMNs is to provide QoS support and fair rate allocation among data flows. Almost all of the routing and scheduling algorithms presented in the literature have one common weak point: when the MBS collects requests larger than the frame length from all the MSSs, these algorithms shrink link durations to fit in the frames. Scaling down the link durations may cause some drawbacks in guaranteeing the QoS requirements of voice and video traffic. Two schemes can be exploited to overcome this problem: 1) A call admission control mechanism can be deployed to avoid link duration shrinkage; 2) A new scheduling method may be proposed to schedule the packets received from the underlying network. In this chapter we focus on the second solution with respect to the first solution.

Scheduling in WMNs is divided in two categories: centralized and distributed scheduling. In centralized scheduling, there existsoneMBS and the other stations (MSSs) relay packets of other stations to/from end points (in this chapter we call these end points as MTs, while MSSs assume to be fixed). The main purpose of this chapter is related to centralized scheduling and admission control.

On the other hand, rapid growth of wireless networks has commenced challenging issues in co-deployment of various technologies including WiFi, WiMAX. While WiFi networks are very popular for providing data services to Internet users in LAN environments, WiMAX technology has been adopted for MAN networks to provide urban accessibility to hot spots or end users. These two technologies seem to be competitors; however, they can interworkto gain metro-networks performance, cost effectiveness and coverage area. This configuration can be used in TDMA-WMNs, however when the same frequency band is employed with different network elements (e.g., the U-NII frequency at 5GHz may be shared among IEEE 802.16d and IEEE 802.11a or IEEE 802.11n), more complex strategies are required for scheduling and packet translation from one technology to another.

In this chapter, with respect to the interoperability of WiFi and TDMA-WMNs networks, we develop a scheduling and admission control mechanism among data flows such that the QoS requirements of delay sensitive traffic types can be provisioned and elastic traffic types get a fair duration of bandwidth.

To provide QoS support for delay sensitive traffic over WiFi, IEEE 802.11e introduces two types of channel access methods: EDCA (Enhanced Distributed Channel Access) and HCCA (Hybrid Coordination Channel Access). Since the HCCA function deployed in the MTs is essentially designed to meet the negotiated QoS requirements of admitted flows, we apply this function to the WiFi network [3], [4].

The chapter is organized as follows: in sections 2, some research activities in scheduling mechanisms in WMNs and IEEE 802.11 are summarized. In section 3, we introduce an overview of IEEE 802.16 and IEEE 802.11(e) standards. QoS comparison between IEEE 802.11 and IEEE 802.16 mesh modes are described in this section. Fourth section is devoted to describe the system model. In this section we introduce the basic assumptions of the system and formally describe the system. In fifth section, the genetic algorithm is briefly described and its application to our problem is discussed. The proposed method is evaluated using simulation results in section 6. Finally, conclusions are drawn in seventh section.

2. Related works

Centralized scheduling mechanism in WMNs has been investigated in [1], [2], [5]-[10], [32-33]. Most of the research activities in this area are not suitable for TDMA mesh networks (e.g., IEEE 802.16d). They consider only primary conflicts in which the connections share a neighbor, while TDMA-WMN is faced with secondary conflicts where the transmitter and the receiver share a neighbor, which can hear both transmissions.

The main algorithm in IEEE 802.16d finds a link ranking during a breath-first traversal of the routing tree. This algorithm has no idea for spatial reuse in the network. Spatial reuse in these networks has been investigated in [5], [7]-[10]. Ref. [9]uses Transmission-Tree Scheduling (TTS) algorithm that is based on graph coloring. This algorithm don’t consider the protocol overhead of TDMA scheduling. While [10]uses the load-balancing algorithm to increase spatial reuse, [8] considers Bellman-Ford method for both spatial reuse and minimum TDMA delay. These schemes don’t take into account the underlying network behavior which can affect scheduling of traffic flows of other MSSs. On the other hand, these algorithms shrink the link duration when the frame is short for scheduling the links.

Application of intelligent scheduling methods in wireless mesh networks has been inspired by the fact that finding a schedule in TDMA scheduling is NP-complete [11]. Ref. [12] uses fuzzy hopfield neural network technique to solve the TDMA broadcast scheduling problem in wireless sensor networks. Artificial neural network with reinforcement learning has been introduced in [13] to schedule downlink traffic of wireless networks. A genetic algorithm approach is used in [2] to find the schedule related to each link in a WMN. Here again, their scheduling method merely considers the traffic flown on the links; however, how these links empty their queues has not been elaborated.

None of the above research activities, consider neither the underling network behavior nor the types of traffic streams flown on the links. Our system model is different from the previous works in two aspects. First, we take into account the underlying network traffic related to each MSS. Second, the algorithm proposed in this chapter is such that shrinking the link duration doesn’t affect the minimum QoS requirements of real-time traffic types.

3. IEEE 802.16 and IEEE 802.11e: An overview

3.1. Overview of IEEE 802.11e

The multiple access mechanism in 802.11e is arisen in super-frames which start with beacon frames having the same duration as beacon intervals. The super-frame comprises an optional CFP (Contention Free Period) followed by a CP (Contention Period) divided into equal duration SIs as shown in Figure 2. At each SI (Service Interval), each QSTA (QoS Station) should transmit its own traffic streams with respect to its QoS constraints. This mechanism is called HCCA function which defines a centrally-controlled polling-based medium access scheme for IEEE 802.11e WLANs. Each SI is divided into a CAP (Controlled Access Phase) period and an optional EDCA period in which the traffic streams having less stringent QoS constraints contend for access to the medium. Usually best effort traffic streams such as HTTP use this period which offers no QoS guarantee. The CAP period is further divided into a number of TXOPs (Transmission Opportunity). Each TXOP is granted by QAP (QoS Access Point) to each QSTA and each QSTA is responsible for sharing this period among its traffic streams.


Figure 2.

HCF super-frame structure

3.2. Overview of IEEE 802.16 mesh mode

IEEE 802.16 MAC PDUs (Protocol Data Unit) (Figure 3) begin with a fixed-length generic MAC header (6 bytes). The MAC header field contains a 2 bytes CID (Connection Identifier) field which carries 8 bits Link ID used for addressing nodes in the local neighborhood. The header is followed by the Mesh sub-header (2 bytes) which includes Xmt Node Id. Mesh BS grants Node Ids to candidate nodes when authorized to the network. After the variable length payload there exists a 4 bytes CRC. The medium in IEEE 802.16 mesh mode is divided into equal duration frames (Figure 4), consisting of two sub-frames:

  • Data sub-frame,

  • Control sub-frame.

The control sub-frame is divided into MSH-CTRL-LEN transmission opportunities indicated in the ND (Network Descriptor). Each transmission opportunity comprises 7 OFDM symbols, so the length of the control sub-frame is fixed and equal to 7×MSH-CTRL-LEN OFDM symbols.


Figure 3.

MAC PDU format


Figure 4.

Frame structure for the mesh mode

Nodes can transmit based on the granted bandwidth and a transmission schedule which is worked out using a common distributed algorithm. The data sub-frame is used for this purpose which is divided into transmission opportunities comprising 256 mini-slots based on the standard. However, there may be fewer than 256 mini-slots depending on the frame size and the size of the control sub-frame. Frame duration which is indicated in ND is determined by MBS to avoid losing synchronization with the connecting nodes. MSH-CSCH-DATA-FRACTION indicated in ND specifies the fraction of data sub-frame which can be used for centralized scheduling. The remaining part of the data sub-frame is used for decentralized scheduling.

3.3. QoS Comparison between WiFi and WiMAX mesh mode

Providing QoS in IEEE 802.11e comes with a new coordination function called HCF. The HCF controlled channel access is for the parameterized QoS, which provides the QoS based on the contract between the AP and the corresponding QSTA(s). First, a traffic stream is established between the AP and an QSTA. A set of traffic characteristics and QoS requirement parameters are negotiated between the AP and QSTA and the traffic stream should be admitted by the AP. The QoS control field in the MAC frame format is a 16 bits field which facilitates the description of QoS requirements of application flows. Its TID (4 bits) identifies the TC (0-7) or the TS (8-15) to which the corresponding MSDU in the FB field belongs. The last eight bits are used usually by QAP to receive the queue size of QSTAs. After admission, the AP specifies the TXOP duration for the QSTA based on the traffic characteristics. So, the QoS is provided based on connections established between AP and QSTA(s).

Unlike WiFi, the QoS in the mesh mode of IEEE 802.16 is provided in a packet by packet basis. Each transmitted packet contains the mesh CID. Figure 5 shows the structure of mesh CID used in unicast messages. In order to enable differentiated handling of packets, the queuing and forwarding mechanisms deployed at individual nodes may make use of the values for the Type, Reliability, Priority/Class, and Drop Precedence fields. The Type field is used to distinguish between different categories of messages. This field may be used to prioritize the transmission of management messages transmitted in the data sub-frame (e.g., messages for uncoordinated distributed scheduling). The Reliability field is employed to specify unacknowledged transmitted packets (when ARQ is enabled). This allows the packet to be retransmitted for up to four times. The Priority/Class field allows the classification of the messages into eight priority classes. This can be used by the queuing and forwarding mechanisms at each node to differentiate the packet treatment for different classes. The Drop Precedence field indicates the likelihood of a packet being dropped during congestion.


Figure 5.

Mesh CID format

4. System model

SSHC stationary end nodes (Figure 6) are able to communicate from one side with MTs and from the other side with MSSs or MBS via their PHY layers in both sides. In the following subsections we develop a genetic based system for scheduling the packets waiting in the SSHCs queues.


Figure 6.

Topology of the scenario

5.1. Basic assumptions

In this chapter we consider a WMN with one MBS and some MSSs (Figure 6). We consider access traffic in the mesh network, so the routes of the traffic form a binary tree rooted at the MBS. MSSs relay numerous traffic types (data, voice or video) between their MTs and other MSSs or the MBS. The MBS, MSSs, and MTs share the same frequency band.The routing tree that is made by the MBS is a binary tree [14], and we assume that it’s known in advanced.

For better support of QoS, we consider MBS and MSSs use TDMA-based scheduling in their MAC layer; however, because of IEEE 802.11 deployment in most mobile devices (laptops and cell phones), MTs use contention-based medium access method. In a given TDMA frame (of the length for example 20ms), some MSSs are sending frames upward or downward the network, while the others are collecting (distributing) frames from (to) MTs. Since the tree rooted at the MBS is a binary one, each MSS has maximum of six logical links to its neighbor MSSs; three for sending and another three for receiving packets (Figure 1). As wireless transceivers are usually half duplex [8], they can’t be used for reception and transmission at the same time. So there are six queues in each MSS, three of these are to store the outbound packets and three others are for inbound packets to queue for reception. However, in our model receiving queues are ignored as they are considered in sending nodes; hence at most three queues are considered for scheduling. It’s worthy to note that we schedule only one queue at each leaf node and two queues at the MBS. Moreover we schedule only the links that have non-empty queues. Each queue is filled by MTs (shown in Figure 6) or the receiving links at that node. For example in Figure 1, the queue of e2 can be filled by the queue of e4.

Let, M be the set of all the stations (including MSSs and the MBS) in the system, indexed by m=1,2,…,M. We consider M>1; i.e., there is at least one MSS. In most of the mesh networks, the frame length is fixed and may not be changed; otherwise the whole system should be restarted [8]; hence the frame length is fixed at L milliseconds. Each transmission in the frame is along with some overheads, so the number of transmissions for each link should be limited to one per frame to minimize transmission overhead.

Let 𝜓 be the set of all the links in the system. We take a subset I of 𝜓 (I⊂𝜓), in which the links have non empty queues. Each iI has one queue per traffic type which are assumed to have unlimited sizes for the sake of simplicity.

Each queue has some restricted QoS traffic specifications; this means that each queue should be scheduled appropriately and get emptied in a desired time. Since the frame length is fixed and all of the links in the system should be scheduled at each frame (because of their restricted QoS requirements), there is a limited interval for each queue to get scheduled. Nevertheless, some of the nodes may not find enough transmission opportunity to evacuate all of their queues, causing the system not to be able to fulfill QoS constraints of delay sensitive traffic types. So, a scheduling method is strongly necessary to satisfy QoS requirements of voice and video traffic. On the other hand, bandwidth allocation to more stringent QoS traffic types may cause starvation for elastic traffic. As such, we define a threshold (k), to assure the elastic traffic types to be scheduled at each k frames.

Let km,i,j be the length of the jth queue (filled by MTs or other MSSs), associated with ith outgoing link, related to mth MSS. So, [km,i,j] is an M × I × J matrix. Each queue should be scheduled to transmit its packets over the appropriate link based on the QoS requirements of its content.

[km,i,j] is available at the MBS through some control messages. Assuming that a 64Kbps voice stream should be serviced in each frame, it generates a 160 bytes packet which is to be transmitted in each 20ms frame. In case of a video traffic stream, its packets should be scheduled every two frames [15].

Some of the main parameters of each traffic type in the system are as follows [16]:

  • Delay Bound (D): Maximum amount of time allowed (including queuing delay) to transmit a frame across the wireless interface.

  • Mean Data Rate (ρ): Average bit rate at the MAC layer required for the packet transmissions.

  • Nominal Packet Size (L): Average packet size.

  • Maximum Packet Size (M): Maximum packet size.

  • Minimum Service Interval (mSI): Minimum interval between the start of successive service period.

  • Maximum Service Interval (MSI): Maximum interval between the start of successive service period.

  • Next, we describe the formal formulation of our system.

5.2. Problem formulation

Each queue is scheduled once in each frame. We assume that spatial reuse is deployed in the routing algorithm, so:

mMiIjJTrm,i,jFF, F=kL, k=1,2,3,

Where Tr is the data transferred from the queue j in the current frame, associated with ith outgoing link, related to mth MSS. L is the length of the frame and F is a parameter that specifies the scheduling duration which is a sub-multiple of L. The above inequality means that due to spatial reuse mechanism applied to the system, the number of transmissions may exceed the frame length.

At the end of each frame, the remaining number of packets in all of the queues should be minimized:

minKminKmMiIjJKm.i.jF-mMiIjJTrm,i,jF, F=kL

In the above minimization problem, K specifies the number of residual packets waiting in the queue for scheduling. We assume three different queues (e.g., CBR, VBR, and elastic traffic) for each link with higher priorities indexed by lower numbers. The following constraints are applied on queuedepletions:

Trm,i,1F>0, F=kL
Trm,i,2F>0, F=kL
Trm,i,3F>0, F=kL
Trm,i,1F>Trm,i,3F Trm,i,2F>Trm,i,3F Trm,i,1F>Trm,i,2F F=kL

Inequality (3) means that the first queue should be scheduled in every k frame. Two other inequalities state that their related queues may be scheduled in every k frame optionally. Inequality (6) demonstrates that the priority of the first queue is higher than the second one and the second queue is more prior than the third one.

The minimization problem (2) with its constraints (1), (3), (4), (5), and (6) are such that they can’t be solved by simple mathematics; since the problem shown to be NP-complete [11]. Heuristic solutions might work in certain cases, but they fail to adapt to different network scenarios [2].

The above optimization problem can be bounded and reformulated such that speed convergence can be obtained as described in the following sentences. As the first queue is reserved for CBR traffic streams, the second queue is reserved for VBR traffic streams, and third one is reserved for elastic (ABR) traffic type, then the first queue should be serviced in each frame, and the second one should be services in every two frames [15]. After that, the remaining bandwidth (if any) is considered for the third queue. Available bandwidth should be fairly shared among the queues. For this purpose, we take advantage of a threshold (k) to force the scheduler to take a minimum percent of the available bandwidth for elastic data types. This causes a fair scheduling method for elastic traffic types and will be presented in the simulation results. Now we have the following optimization problem with its conditions. It can be seen from the minimization problem (7) that the number of queues per each link and the number of links per each node is bounded on 3 (as discussed earlier); so the search space is limited and convergence to the termination conditions will be faster than the previous problem (2).

minKminKm=1Mi=13j=13Km,i,jkL-m=1Mi=13j=13Trm,i,jkL, k>2

Subject to:

(8) (9) (10)
Trm,i,3kL>0, k>2
Km,i,1L>0 Km,i,22L>0 Km,i,3kL>0, k>2

5.3. Admission control

The CBR queue should be emptied at the end of its schedule or the backlogged packets are to be dropped. So,the new connection should be rejected if the following equation is not satisfied:

Km,i,1L-Trm.i,1L=0 mM, iI

While the VBR queue get filled in different intervals, we put a threshold on the top of its queue. If the number of the packets available in the queue is greater than this threshold, then any new call will be rejected. So:

Km,i,22L-Trm.i,22L<Ϣ1mM, iI

The elastic traffic queue can be filled every time a packet is generated, but may cause undesirable delay, so, we impose a threshold (τ2) on the third queue as well. However τ2 should be greater than τ1, since elastic data types have lighter QoS constraints than VBR data types.

Km,i,3kL-Trm.i,3kL<Ϣ1k>2, mM, iI

6. Application of genetic algorithm in scheduling of SSHCs queues

In the following subsections we first present an overview of genetic algorithm, and then we develop a GA-based scheduling mechanism for the problem.

6.1.Genetic. algorithm: An overview

The genetic algorithm is a search heuristic that mimics the process of natural evolution. This heuristic is routinely used to generate useful solutions to optimization problems. Genetic algorithms belong to the larger class of evolutionary algorithms, which generate solutions to optimization problems using techniques inspired by natural evolution, such as inheritance, mutation, selection, and crossover [17], [18].

In a genetic algorithm, a population of strings (called chromosomes or the genotype of the genome), which encode candidate solutions (called individuals, creatures, or phenotypes) to an optimization problem, evolves toward better solutions. An initial population is created from a random selection of solutions (which are analogous to chromosomes). A value for fitness is assigned to each solution (chromosome) depending on how close it actually is to solve the problem and arrive to the answer of the problem. Those chromosomes with higher fitness values are more likely to reproduce offspring. The offspring is a product of the father and mother, whose composition consists of a combination of genes from them (this process is known as crossing over). This generational process is repeated until a termination condition has been reached. Common terminating conditions are:

  • A solution is found that satisfies minimum criteria.

  • Fixed number of generations reached.

  • The highest ranking solution's fitness is reaching or has reached a plateau such that successive iterations no longer produce better results.

  • Manual inspection

  • Combinations of the above.

At each stage, crossover and mutation genetic operators may be applied to the new strings. Crossover is a genetic operator that combines two chromosomes (parents) to produce a new chromosome (offspring). The idea behind crossover is that the new chromosome may be better than both of the parents if it takes the best characteristics from each of the parents.

As an example, suppose there are two chromosomes 1 and 2 which are represented as a binary string, the most used way of encoding a chromosome, as the following:

  • Chromosome 1 - 1101100100110110

  • Chromosome 2 - 1101111000011110

Crossover selects genes from parent chromosomes and creates a new offspring. The simplest way how to do this is to choose randomly some crossover point and everything before this point copy from the first parent and everything after the crossover point copy from the second parent. | is the crossover point. The following shows this process:

  • Chromosome 1 - 11011 | 00100110110

  • Chromosome 2 - 11011 | 11000011110

  • Offspring 1 - 11011 | 11000011110

  • Offspring 2 - 11011 | 00100110110

After performing the crossover, mutation is used to maintain genetic diversity from one generation of population chromosomes to the next. It introduces some local modifications of the individuals in the current population on order to explore new possible solutions. For binary encoding of chromosome, we can switch a few randomly chosen bits from 1 to 0 or from 0 to 1. For our example, the mutation process is shown as the following:

  • Original offspring 1 - 1101111000011110

  • Original offspring 1 - 1101100100110110

  • Mutated offspring 1 - 1100111000011110

  • Mutated offspring 2 - 1101101100110110

The pseudo-code of a basic GA is summarized as follows:

  1. Choose the initial population of individuals

  2. Evaluate the fitness of each individual in that population

  3. Repeat on this generation until termination: (time limit, sufficient fitness achieved, etc.)

  4. Select the best-fit individuals for reproduction.

  5. Breed new individuals through crossover and mutation operations to give birth to offspring.

  6. Evaluate the individual fitness for new individuals.

  7. Replace least-fit population with new individuals.

6.2. A GA-based approach for the scheduling problem

In the previous section, the optimization problem which is needed to create a population was formally defined. This population is created by the MBS based on the fact that the MBS gathers queues’ statistics of SSHCs through some control messages. Each chromosome of the population is such that every queue gets its service once per frame, so the scheduling overhead could be minimized. Each queue is scheduled as close to the beginning of the frame as possible, so that its transmission does not overlap with transmissions of its conflicting links. The scheduling period is set to two frames, since VBR traffic streams get their services every two frames.


Figure 7.

A typical frame (chromosome) with its SSecs (genes) associated with Figure 1

Each gene is defined as a scheduling section (SSec). A scheduling section is composed of one or more time slots in which a queue and its non-conflicting queues are scheduled to transmit in parallel. The first scheduling section is started at the beginning of the frame. All the scheduling sections are consecutive and non-overlapping.

The crossover operator is 0.5-uniform crossover [19]. Each SSec of one chromosome can be exchanged with equal-size SSec of another chromosome, with a constant probability of 0.5. Each scheduling section (gene) is subject to random mutation with a small independent probability. We use permutation encoding; hence each gene replaces with a duplicate of other equal-size genes (e.g., replace the SSec3 with the SSec5 in Figure 7).

Finally, we should use some QoS metrics of the network (that we want to optimize) to define the fitness function. It can be seen from the Eq. (7) that we are interested in depletion of all the queues in the scheduling period. On the other hand, when more queues get emptied, higher performance will be reached; hence, Eq. (7) can be explicated as Eq. (16).

maxTrmaxTrm=1Mi=13j=13Trm,i,jkL-k×L lN, k>2

So we define the fitness function (F.F.) as follows:


7. Simulation results

We developed a TDMA-WMN system based on Orthogonal Frequency Division Multiplexing (OFDM) air interface that works in 5GHz frequency band using NS-2 simulator [20]. Basic OFDM parameters are listed in Table 1. OFDM symbol duration is about 14µs. TDMA frame duration (L) is set to 20ms. While TDMA-WMN uses BPSK-1/2 modulation technique, the underlying network (WLAN) uses 16QAM-1/2 modulation technique. Different modulation techniques have been used; because interference between MTs of different SSHCs should be avoided (Figure 6).

OFDM ParametersValueScenario
Sampling rateDepend on BW23.04MHz
Useful time TB256.T11.11µs
CP time TG2.78µs
Symbol time TsymTG+TB13.89µs
Carriers NFFT256
Data Carriers192

Table 1.

Basic OFDM parameters

We define three types of traffic in the system: CBR, VBR, and ABR traffic streams. CBR traffic (e.g., voice over IP without silent suppression (G.711)), has constant packet size with constant packet interval. VBR traffic (e.g., H.263 video), has variable packet size with variable packet interval feature. At last, elastic traffic (e.g., FTP), can adjust its transmission rate gradually.

Voice and video traffic stream specifications are as follows:

  1. G.711 voice (CBR traffic) which generates packets of 160 bytes with mean service interval of 20ms (64 Kb/s of average sending rate).

  2. H.263 video (VBR traffic) which has been obtained from “Jurassic Park I” trace file, available in [21].

Traffic specifications of these two types of traffic are summarized in Table 2. For the sake of simplicity, we assume that elastic flows are generated using CBR traffic sources with packet size of 1000 bytes.

TSPEC Param.G.711 VoiceH.263 Video (Park Jurassic I)
Mean Bit Rate (Kbps)64260
Delay Bound (ms)2020
Mean SDU Size (Byte)1604533.67
Maximum Burst Size (Byte)16011817
Minimum Service Interval (ms)200
Maximum Service Interval (ms)2040

Table 2.

Traffic specification parameters of traffic types

In order to evaluate the performance of the proposed scheduler and the admission control procedure, the topology of Figure 6is considered as the scenario. All of the end nodes (SSHCs) are active, while the intermediate nodes (MSSs) pass only the traffic of the end nodes. SSHCs are configured to work in both WLAN and TDMA-WMN modes; while, MSSs work in TDMA-WMN mode. k is fixed at 4, since elastic traffic queues are scheduled every four frames. From one hand, this value is not too small that causes some drawbacks on delay sensitive traffic types and on the other hand it’s not too large that leads to unfairness.

At first, we assume one VBR MT and one ABR MT and a number of CBR MTs which are gradually increased (Figure 8). It can be seen when there is no admission control mechanism, as the number of MTs exceeds 10, packets of the newly added MTs are dropped. The proposed admission control mechanism for this traffic type works well, since none of the packets has been dropped when it is applied.


Figure 8.

CBR packet loss versus increased number of CBR connection, while VBR and ABR connections are fixed at 1

In the next simulation, the number of CBR MTs and ABR MTs are fixed to one and the number of VBR MTs (Figure 9) is gradually increased. Since the packet size and the arrival time are variable in case of the packets of these traffic types, the number of admitted VBR MTs is less than the number of admitted CBR MTs. In this figure the packet loss is due to the threshold (τ1) applied to the queue length. Here again the proposed admission control mechanism works well for this type of traffic.

For the last simulation, we removed all of the thresholds to see how many packets will be backlogged in the queues after scheduling the queues. For this purpose we monotonically increase the number of CBR, VBR, and ABR MTs in each SSHC. It can be seen from Figure 10 that the CBR queue is at its normal size, since almost all of its packets are serviced in appropriate time. However, after the second frame, all of the packets of elastic data type are queued, since there is no chance for them to be scheduled. Moreover, since all of the VBR packets do not receive the opportunity to be scheduled, the VBR queue length increases monotonically.


Figure 9.

VBR packet loss versus increased number of VBR connections, while CBR and ABR connections are fixed at one


Figure 10.

Residual packets in the three queues, while MTs are monotonically increased

Eliminating the thresholds causes the queue size of ABR and VBR traffic to increase, while by using these thresholds (Figure 8 and Figure 9) a fair bandwidth allocation can be reached.

8. Conclusion

In this chapter we considered an important aspect of TDMA-WMNs: Traffic flow requirements on scheduling the links. Moreover, we considered the underlying network which can affect the overall system performance despite previous research. We assumed three types of traffic with different QoS requirements and formulated a model describing the scheduling optimization problem which is to be solved to minimize queues in the system. We develop a genetic algorithm method to find the optimal schedule for each relaying node. Furthermore to be able to fulfill QoS requirements of established connections, we developed an admission control mechanism. Finally, the performance of the proposed GA algorithm along with the admission control procedure was evaluated by simulating a typical network scenario. Simulation results showed effectiveness of our admission control and scheduling mechanisms. In our next work, we introduce some new mechanisms including MIMO technique to the above-mentioned system and investigate its performance. Meanwhile, application of genetic algorithms in distributed scheduling of WMNs is investigated.


1 - X. Cheng, P. Mohapatra, S-J. Lee, and S. Banerjee, MARIA: Interference-Aware admission control and QoS routing in wireless mesh networks, ICC, 2008.
2 - L. Badia, A. Botta, L. Lenzini, A. genetic, to. approach, routing. joint, scheduling. link, wireless. for, networks. mesh, Hoc. Ad, vol. Networks, 7 654664 , 2009.
3 - “IEEE 802.11e Medium access control (mac) quality of service (qos) enhancements,” 2005.
4 - C. Cicconetti, L. Lenzini, E. Mingozzi, G. Stea, efficient. An, layer. cross, for. scheduler, traffic. multimedia, wireless. in, area. local, with. I. E. E. E. networks, 80211 HCCA, ACM SIGMOBILE Mobile Computing and Communications Review, 11 3146 , July 2007.
5 - S. Liu, S. Feng, W. Ye, H. Zhuang, allocation. Slot, in. algorithms, scheduling. centralized, for. I. E. E. E. scheme, 80216 based wireless mesh networks, Computer Communications, 32 943953 , 2009.
6 - W. Liao, S. P. Kedia, A. K. Dubay, A. centralized, algorithm. scheduling, Wi. M. A. X. for, network. N. O. M. S. mesh, 2010 858861 .
7 - H. , Y. Wei, S. Ganguly, R. Izmailov, Z. Haas, I. E. E. E. Interference-aware, 80216 WiMax mesh networks, VTC, 2005, 31023106 .
8 - P. Djukic, S. Valaee, aware. Delay, scheduling. link, multi-hop. T. D. M. A. for, networks. I. E. E. E. A. C. M. wireless, on. Transactions, vol. Networking, 17 870883 , June 2009.
9 - B. Han, W. Jia, L. Lin, evaluation. Performance, scheduling. of, I. E. E. E. in, 80216 based wireless mesh networks, Computer Communications, 30 782792 , Nov. 2007.
10 - D. Kim, A. Ganz, Fair, multihop. efficient, algorithm. scheduling, I. E. E. E. for, 80216 BWA systems, Broadnets, 2005, 895901 .
11 - W. Wang, Y. Wang, X-Y. Li, W-Z, Song, O. Frieder, Efficient Interference-Aware TDMA Link Scheduling for Static Wireless Networks, MobiCom, 2006.
12 - Y-J. Shen and M-S. Wang, Broadcast scheduling in wireless sensor networks using fuzzy Hopfield neural network, Expert systems with applications, vol. 34 900907 , 2008.
13 - P. Fiengo, G. Giambene, E. Trentin, downlink. Neural-based, algorithm. scheduling, broadband. for, networks. wireless, Communications. Computer, vol, 30 207218 , 2007.
14 - “IEEE Std 802.16-2004, IEEE standard for local and metropolitan area networks part 16: air interface for fixed broadband wireless access systems,” 2004.
15 - X. Cheng, P. Mohapatra, S-J. Lee, and S. Banerjee, Performance evaluation of video streaming in multihop wireless mesh networks, NOSSDAV, 2008.
16 - I. Inan, F. Keceli, E. Ayanoglu, adaptive. An, Qo. S. multimedia, for. scheduler, 80211 wireless LANs, IEEE ICC, 2006.
17 - E. Ilavarasan, P. Thambidurai, Algorithm. Genetic, Task. for, on. Scheduling, Heterogeneous. Distributed, System. Computing, Review. International, Computers. on, Vol. Software, 1 n. 3, 233242 , 2006.
18 - R. K. Jena, P. Srivastava, G. K. Sharma, A. Review, Genetic. on, in. Algorithm, Parallel, Environment. Distributed, Review. International, Computers. on, Vol. Software, 3 n. 5, 532544 , 2008.
19 - S. N. Sivanandam, S. N. Deepa, Introduction to Genetic Algorithms (Springer-Verlag, Berlin Heidelberg, ISBN: 978-3-540-73189-4, 2008).
20 - N. S. Network, Simulator, [. Accessed, March 2012
21 - P. Seeling, M. Reisslein, B. Kulapala, performance. Network, using. evaluation, size. frame, traces. quality, single-layer. of, video. a. two-layer, I. E. E. E. tutorial, Surveys. Communications, Tutorials, 6 6 2 5878 , 2004.
22 - “IEEE 802.11a, Part 11:Wireless LAN Medium Access Control (MAC) and Physical Layer (PHY) Specifications: High-Speed Physical Layer Extension in the 5 GHz Band, supplement to IEEE 802.11 Standard,” 2000.
23 - J. Gross, M. Emmelmann, A. Punal, A. Wolisz, I. E. E. E. Enhancing, with. 802.11a/n, single-user. O. F. D. M. dynamic, Performance. adaptation, vol. Evaluation, 66, 240257 , 2009
24 - “IEEE 802.11n Enhancements for higher throughput, amendment 4 to ieee 802.11 part 11: Wireless lan medium access control (mac) and physical layer (phy) specifications,” 2007.
25 - J. Zou, D. Zhao, C. B. R. Real-time, scheduling. traffic, I. E. E. E. in, wireless. 802.16-based, networks. mesh, Networks. Wireless, 15 15 6572 , 2009.
26 - P. Djukic, S. Valaee, algorithms. Scheduling, for, 80216 mesh networks, WiMax/MobileFi: Advanced Research and Technology (Y. Xiao, ed.), Auerbach Publications, 2007, 267288 .
27 - M. Rashid, E. Hossain, V. K. Bhargava, channel. Controlled, scheduling. access, guaranteed. for, S. Qo, 802.11e-based. W. L. A. in, I. E. E. E. Ns, on. Transactions, Communications. Wireless, vol, 7 4 12871297 , 2008.
28 - H. Cheng, X. Jia, H. Liu, Access Scheduling on the Control Channels in TDMA Wireless Mesh Networks, MSN, 2007.
29 - Y. Hou, K. Leung, A. distributed, framework. scheduling, multi-user. for, gain. diversity, of. quality, in. service, mesh. wireless, I. E. E. E. networks, on. Transactions, Communications. Wireless, vol, 8 12 59045915 , 2009.
30 - H. Cheng, N. Xiong, L. T. Yang, Y. -S, Distributed. Jeong, algorithms. scheduling, channel. for, in. T. D. M. A. access, mesh. wireless, The. networks, of. Journal, vol. Supercomputing, 45 1 105128 , 2008.
31 - “IEEE Standard for Information technology-Telecommunications and information exchange between systems-Local and metropolitan area networks-Specific requirements- Part 11: Wireless LAN Medium Access Control (MAC) and Physical Layer (PHY) Specifications,” 2007.
32 - J. Luo, C. Rosenberg, A. Girard, Wireless. Engineering, Networks. Mesh, Scheduling. Joint, Power. Routing, Control, Adaptation. I. E. E. E. A. C. M. Rate, on. Transactions, vol. Networking, 18 5 13871400 , Oct. 2010.
33 - J. Joseph, M. Princy, on. Analysis, Scheduling, Balancing. Load, in. Techniques, Mesh. Wireless, International. Networks, of. Journal, Applications. Computer, vol, 42 12 2012.