IEEE COMMUNICATIONS SURVEYS & TUTORIALS, VOL. 12, NO.

2, SECOND QUARTER 2010

205

A Survey on Scheduling in IEEE 802.16 Mesh Mode

Miray Kas, Burcu Yargicoglu, Ibrahim Korpeoglu, and Ezhan Karasan
AbstractIEEE 802.16 standard (also known as WiMAX) denes the wireless broadband network technology which aims to solve the so called last mile problem via providing high bandwidth Internet even to the rural areas for which the cable deployment is very costly. The standard mainly focuses on the MAC and PHY layer issues, supporting two transmission modes: PMP (Point-to-Multipoint) and mesh modes. Mesh mode is an optional mode developed as an extension to PMP mode and it has the advantage of having an improving performance as more subscribers are added to the system using multi-hop routes. In 802.16 MAC protocol, mesh mode slot allocation and reservation mechanisms are left open which makes this topic a hot research area. Hence, the focus of this survey will mostly be on the mesh mode, and the proposed scheduling algorithms and performance evaluation methods. Index TermsWiMAX, IEEE 802.16, Mesh Networks, Distributed Scheduling, Centralized Scheduling
TABLE I BASIC I NFORMATION ON W I MAX S TANDARDS 802.16 Application Frequency Band MAC Architecture Peak Data Rate Transmission Scheme LOS, xed 10-66 GHz PMP 134 Mbps SC 802.16d-2004 NLOS, xed 2-11 GHz PMP, Mesh 75 Mbps SC, 256 OFDM, 2048 OFDM 802.16e-2005 NLOS, mobile 2-6 GHz PMP 30 Mbps 128-2048 SOFDMA

I. I NTRODUCTION TAGGERING growth of the Internet causes more increase on the demand for higher-speed Internet access. Although wired technologies like DSL or cable offer broadband connections, they usually cover areas with the highest density of population. However, satisfying the requirements of users within rural areas having little wired infrastructure has become an urgent need. Wireless broadband access appears to provide the best possible solution which would overcome this so called last mile problem. IEEE 802.16 also known as WiMAX (Worldwide Interoperability for Microwave Access) is introduced to enable the last mile broadband wireless access [1]. Radio coverage of about 5 miles with a bandwidth of up to 70 Mbps is offered without requiring deployment of expensive base stations. IEEE 802.16 standards family is the standardization of a WirelessMAN air interface along with the MAC layer and multiple physical layer specications of broadband wireless access systems. 802.16 supports working in both licensed and unlicensed portions of the frequency spectrum. The aim of 802.16, the rst version of the standard which was approved in December 2001, was to make high data rates available to users having Line of Sight (LOS) connectivity. WiMAX, with its mesh mode support, provides broadband connections in
Manuscript received 31 July 2008; revised 28 November 2008 and 24 March 2009. This work is partially supported by The Scientic and Technical Research Council of Turkey (TUBITAK) with grant number EEEAG104E028. M. Kas, B. Yargicoglu, and I. Korpeoglu are with Department of Computer Engineering, Bilkent University (e-mail: {miray, yargic, korpe}@cs.bilkent.edu.tr). E. Karasan is with the Department of Electrical and Electronics Engineering, Bilkent University (e-mail: ezhan@ee.bilkent.edu.tr). Digital Object Identier 10.1109/SURV.2010.021110.00053

wider areas even to users with Non-Line-of-Sight connections (NLOS). IEEE 802.16, operates in the licensed spectrum between 10 and 66 GHz employing single carrier (SC) scheme in the PHY layer. In order to enable NLOS communication, IEEE 802.16a was completed in 2003 as an amendment to the previous standard offering OFDM physical layer and support for orthogonal frequency division multiple access (OFDMA) in the MAC layer. By the end of 2004, IEEE 802.16(d)2004 replaced previous versions and it was called the Fixed WiMAX. With this revision, mesh topologies are supported via enhancements to the MAC layer in addition to point-tomultipoint (PMP) topologies, and the supported frequencies are set to be within 2 and 11 GHz. As of Dec 7th 2005, IEEE 802.16e-2005 standard is approved and became the ofcial standard for Mobile WirelessMAN. IEEE 802.16e is published as an amendment to 802.16d, making corrections where appropriate and introducing new features. Through this revision, mobility is allowed via modications in the MAC layer and scalable OFDMA (SOFDMA) is specied for the physical layer. Table I shows basic differences between the three versions of WiMAX standards (802.16, 802.16d and 802.16e). WiMAX standards are currently under further development as summarized in Figure 1. As mentioned before, the radio coverage ranges of WiMAX networks are measured in kilometers which makes IEEE 802.16 based networks suitable for constructing metropolitan area networks (MANs) while IEEE 802.11 based networks radios have ranges in the order of a few hundred meters, hence usually aimed for constructing small local area networks (LANs). It can be inferred from their intended uses that there are some basic differences between IEEE 802.11 and 802.16 standards.

1553-877X/10/$25.00 c 2010 IEEE

206

IEEE COMMUNICATIONS SURVEYS & TUTORIALS, VOL. 12, NO. 2, SECOND QUARTER 2010

Fig. 2.

OFDM vs. OFDMA

Fig. 1.

IEEE 802.16 Published Standards and Drafts TABLE II BASIC D IFFERENCES B ETWEEN W I MAX AND W I F I 802.16d Coverage (up to) Frequency Band Data Rate (up to) Multiplexing Services (QoS) 10 kilometers 2-11 GHz 75 Mbps Burst TDM/ TDMA/ OFDMA UGS, rtPS, nrtPS, BE 802.11 300 meters 2.4, 5 GHz 54 Mbps CSMA BE

A dramatic difference from IEEE 802.11 MAC is that IEEE 802.16 MACs subscriber stations use TDMA while in IEEE 802.11 carrier sensing mechanisms are used. As another difference, in order to overcome the hidden terminal problem, RTS/CTS/Data/ACK mechanism is used in IEEE 802.11, but in IEEE 802.16 connection setup through a threeway handshake is done prior to any transmission. Besides, in IEEE 802.16 the channel for the control message exchange is separated from that of data transmission allowing the data transmissions to take place without being affected by the contention in the control channel. Another improvement that has been adopted in IEEE 802.16 is that a single request message can be used to allocate multiple slots contiguously, which is not possible in IEEE 802.11. In addition, in its PMP mode, IEEE 802.16d supports four QoS classes while there is only the best-effort service dened in 802.11 standards (In 802.16e, a fth service class called ertPS is further dened.) Furthermore, IEEE 802.11 has performance constraints as it operates in the unlicensed portion of the spectrum. Operating under both licensed and unlicensed portions of the spectrum, IEEE 802.16 offers operation over broader ranges. Table II summarizes the basic differences between IEEE 802.11 and 802.16 standards. Considering all these differences, it becomes infeasible to directly apply the studies for IEEE 802.11 to IEEE 802.16. IEEE 802.16 received wide attention from research community and industry mainly due to its being a promising technology and standards leaving performance sensitive parts open for vendors implementation. Although the standard species control messages, the details of scheduling mechanism in mesh

mode (either centralized or distributed) that allocates data slots for transmission are left open for further research. Considering the scheduling in IEEE 802.16 mesh mode as a promising research area, this article surveys existing approaches in IEEE 802.16 mesh mode scheduling and explores their key points along with the common features and differences observed among these studies. The rest of the paper is structured as follows. In Section II, general overview of IEEE 802.16 PHY and MAC layers are given and in Section III, information regarding the two WiMAX network topologies (PMP and Mesh) is provided. Section IV overviews the scheduling mechanisms for WiMAX mesh networks, and Section V and VI examines the studies on centralized and distributed scheduling respectively. Section VII covers cross-layer studies done on WiMAX mesh networks. In Section VIII, analysis and inferences are presented, laying out the noteworthy shared points and differences. Section IX highlights open research issues, and nally Section X concludes the paper. II. PHY AND MAC L AYER OVERVIEW A. PHY Layer The WiMAX physical layer is based on orthogonal frequency division multiplexing which is a digital encoding and modulation technique used by many broadband systems. 802.16d supports both Orthogonal Frequency Division Multiplexing (OFDM) with 256 FFT (Fast Fourier Transform) and Orthogonal Frequency Division Multiple Access (OFDMA) with 2048 FFT [2]. OFDM uses multicarrier modulation in which the given data stream is divided into several lower bit rate streams that are modulated and transmitted simultaneously on separate subchannels. As a result, the data throughput is increased enabling high-speed data and multimedia communications along with resilience to interference and low multipath distortion. OFDM allows one user at a time on the channel. On the other hand, OFDMA is the multi-user version of OFDM which allows multiple users access the channel at the same time. Subsets of sub-carriers are assigned to individual users allowing simultaneous transmissions from several users. An exemplary subchannel-slot assignment scenario with OFDM and OFDMA is depicted in Figure 2. Different from the 802.16d standard, 802.16e WiMAX employs Scalable OFDMA (SOFDMA) where FFT sizes can vary from 128 to 2048 according to the channel bandwidth in order to keep the carrier spacing constant across different bandwidth channels. Scalable bandwidth opportunity and subchannelization techniques on 802.16e OFDMA results

KAS et al.: A SURVEY ON SCHEDULING IN IEEE 802.16 MESH MODE

207

TABLE III MAC P ROTOCOL S UBLAYERS Sublayer CS CPS PS Function Guarantee QoS for ows Access control, bandwidth and power management, scheduling Set up secure connections among SSs 0 1 2 3 Type

TABLE IV T YPE OF D ATA D ELIVERY S ERVICES Symbolic Name of Service Type UGS RT-VR NRT-VR BE ERT-VR Meaning Unsolicited Grant Service Real-Time Variable Rate Service Non-Real-Time Variable Rate Service Best Efforts Service Extended Real-Time Variable Rate Service Scheduling Service UGS rtPS nrtPS BE ertPS

in better network performance management meeting specic capacity and coverage requirements [2]. B. MAC Layer In MAC layer, 802.16e has several improvements over the 802.16d standard in order to enable mobility support by dening seamless handover and power conservation mechanisms for portable devices. To enable a seamless handover of ongoing connections from one base station to another, the standard provides one mandatory and two optional handoff methods. Multicast and broadcast services are also supported by the 802.16e standard. Besides, in order to preserve battery life in end devices, a series of sleep and idle mode power management functions are dened. MAC protocol for WiMAX consists of three sublayers named as Convergence Sublayer (CS), Common Part Sublayer (CPS), and Privacy Sublayer (PS). The functions of these sublayers are given in Table III: WiMAX MAC is connection oriented and each link is identied by a unidirectional CID (Connection Identier). In CS, higher layer protocol addresses such as IP addresses are mapped onto CIDs and SFIDs (Service Flow Identier). With this, every transmission is inserted to a queue associated with its service type. In the standard, CS for ATM and packet networks are dened, however, only CSs for IP and Ethernet are decided to be implemented by WiMAX Forum [3]. Furthermore, PHS (Payload Header Suppression) is another functionality of CS dened in the standard as optional [4]. CPS is the core of the MAC layer carrying the functionalities of ranging, scheduling, bandwidth management, construction and transmission of MAC PDUs. This part is investigated in three subsections in 802.16d standard: PMP, Mesh and Data /Control plane. Having mentioned that CPS constitutes the core of MAC functionality, more information about PMP and Mesh modes will be provided in the next section. The last sublayer of 802.16 MAC, PS, is responsible for providing private access to the subscribers across a xed wireless network through encryption. III. W I MAX N ETWORK T OPOLOGIES IEEE 802.16 MAC protocol was rstly designed for PMP wireless access applications. Then, in 2004, with IEEE 802.16d standard [4], an optional mesh operating mode was introduced as an extension to the PMP mode. Currently, two operational modes are supported: PMP mode and the optional Mesh mode.

A. PMP Mode PMP mode is the traditional cellular like transmission mode in wireless communication systems. There is a central base station (BS) with a sectorized antenna and multiple subscriber stations (SS). The trafc is only between SSs and BS, no direct trafc among SSs is supported. The link from SS to BS is called the uplink and the link from BS to SS is called the downlink. The downlink bandwidth is fully controlled by BS and SSs share the uplink bandwidth on a per demand basis. BS is the only transmitter at downlink transmission and is able to handle multiple independent sectors simultaneously. The downlink transmission is usually broadcast. As it is the only transmitter in the direction it serves, a BS does not have to coordinate with other BSs apart from handover issues. Besides, each SS has to be within single-hop distance to BS along with the requirement of clear LOS transmission range. Supporting Quality-of-Service (QoS) is an important issue in which various QoS requirements have to be satised for both uplink and downlink channels. Different kinds of trafc models yield different service types to be handled in the MAC scheduler. In 802.16d PMP mode, four service types are considered for QoS purposes: Unsolicited Grant Service (UGS), real-time Polling Service (rtPS), non-real-time Polling Service (nrtPS) and Best Effort (BE). A fth service class, extended real-time Polling Service (ertPS), is included with the IEEE 802.16e-2005 standard. [5]. UGS service class is for the real-time constant bit rate (CBR) applications such as VoIP. Unsolicited data grants are allocated to eliminate the overhead and latency of the request/grant process. During the connection establishment, maximum sustained trafc rate is declared and BS assigns xed bandwidth grants in each frame accordingly. rtPS service class is for supporting real-time applications that produce variable-sized data packets periodically such as MPEG video. These applications have specic bandwidth requirements, hence the opportunity for dynamic bandwidth request must be ensured. Therefore, SS receives unicast polls from BS and it is allowed to specify the size of each request. This is done by dedicated periodic slots and the bandwidth request is guaranteed to be received in time by BS. ertPS service class combines features from UGS and rtPS service classes. An initial ensured bandwidth allocation is done as in UGS and then this allocated bandwidth can be decreased or increased as in the case of rtPS.

208

IEEE COMMUNICATIONS SURVEYS & TUTORIALS, VOL. 12, NO. 2, SECOND QUARTER 2010

TABLE V PMP M ODE VS . M ESH M ODE PMP Mode Frame Structure Separate Uplink & Downlink Subframes Low, should be designed for the worst case Only between BS and SSs Lower than it is in mesh mode TDD, FDD Mesh Mode Uplink & Downlink trafc is not differentiated High, can take advantage of such links Trafc among SSs is also possible Higher than it is in PMP mode FDD

Tolerance for Links with High Loss Trafc Direction Coverage Probability of a New Node Duplexing

nrtPS service class is the most appropriate for the delaytolerant applications. As in rtPS, dedicated periodic slots are used for the bandwidth request opportunity, but with much longer periods. Although minimum bandwidth is also guaranteed for this type of connections, connections belonging to this service class may also use contention slots for bandwidth requests if the dedicated request slots are not enough for the ows bandwidth requirements. Finally, BE service class is for the trafc with no minimum level of service requirements. Like in nrtPS, contention slots are used for bandwidth request opportunities as long as there is space available. B. Mesh Mode Mesh networks receive attention since supporting multi-hop routing is considered as a must in order to achieve high data rates over long distances. Both in IEEE 802.16d and IEEE 802.16e, there is support for an optional mesh topology. Yet, mesh extension is only dened for OFDM air interface; it is not available for the OFDMA interface. At this point, we should clarify that IEEE 802.16e supports mesh mode as it also encompasses features dened in 802.16d. However, for mobile WiMAX whose addition led 802.16e to be a standard in its own right, mesh mode is not supported. Among the set of drafts under development, IEEE 802.16j also focuses on providing multi-hop capabilities in order to enhance the throughput and coverage area of a mobile WiMAX network. The proposed topology is a relay network in the form of a tree which has the BS as the root and multiple levels of Relay Stations (RS) to provide multi-hop communication between the MSs and the BS [6]. In other words, the path between an MS and the BS may only contain RSs. In IEEE 802.16 mesh mode, similar to the 802.16j relay mode, SSs may have no direct link to BS. However, there are no network entities called Relay Stations and communication between BS and an SS can be done via routing over multiple SSs and links of all transmissions between two nodes are bidirectional. This makes an SS not only a host but also a router that forwards packets on behalf of others. Since mesh networks allow each SS to act as a router forwarding other nodes data, the mesh network is not restricted to one-hop

Fig. 3.

Mesh Mode Frame Structure

routes; hence it enables communication over longer distances. Besides, the capacity of the network increases substantially as new nodes join the network, providing alternative routes. Links for new SSs joining in the network are initialized having unique link identiers. The communication in mesh mode can be established in two ways. If there is centralized control of BS over the network, then a centralized scheduling algorithm runs in the mesh BS and the uplink and downlink bandwidths are managed by BS. As an alternative approach, bandwidth management can be handled in a distributed manner (decentralized) in which all nodes periodically exchange their schedules and bandwidth requests/grants and then come up with a suitable communication schedule running the distributed scheduling algorithm installed in every node. Since the scheduling algorithms are left open in the standard, scheduling in WiMAX mesh mode has become an appealing research area. Table V tabulates some of the very basic differences between the PMP and Mesh modes. 1) Mesh Mode Frame Structure: In IEEE 802.16 mesh mode, only TDD is supported, while both of FDD and TDD are supported in PMP mode. In WiMAX mesh mode, only TDMA is used for channel access between BS and SSs and the channel is divided into frames (Figure 3). As seen in Figure 3, a frame has two subparts: control subframe and data subframe. The control subframe is for carrying control messages for network conguration and negotiating the schedule of data subframe minislots. The length of the control subframe is 7 * MSH-CTRL-LEN where seven refers to the number of OFDM symbols which is xed to increase

KAS et al.: A SURVEY ON SCHEDULING IN IEEE 802.16 MESH MODE

209

TABLE VI M ESH M ODE S PECIFIC MAC M ANAGEMENT M ESSAGES Message Name 39 40 41 42 43 MSH-NCFG MSH-NENT MSH-DSCH MSH-CSCH MSH-CSCF Message Description Mesh Network Conguration Mesh Network Entry Mesh Distributed Schedule Mesh Centralized Schedule Mesh Centralized Schedule Conguration Connection Broadcast Basic Broadcast Broadcast Broadcast

reliability. Every control subframe consists of MSH-CTRLLEN (0-15) transmission opportunities (slots). There are two types of control subframes: network control subframe and scheduling control subframe. Scheduling control subframe is more frequently used than the network control subframe. The frames may be combined to form a super frame whose rst control subframe is dedicated as network control subframe and the rest as scheduling control subframes. The network control subframe is primarily for topology management. During this subframe, SSs send network conguration and entry messages to BS to inform about the changes. Such changes may be due to a new node entry or a disconnected node. The period of this kind of subframe is a network parameter. The scheduling control subframe is used for transmission of control messages that schedule the slots in the data subframe, that is, the transmission of the request and grant messages for data transmissions. OFDM data subframe is further divided into 256 slots. The size of each minislot can be calculated as (SymOF DM M SH CT RL LEN 7) 256 (1)

Parameters such as Next-Xmt-Mx and Xmt-HoldoffExponent are included in a MSH-DSCH message. These elds are then used to calculate the eligibility interval for transmission and the holdoff time of the node respectively. The message contains a one-bit ag indicating whether it is a request or a grant message and another eld indicating whether coordinated or uncoordinated scheduling is used. In addition, each node sends this message regularly to inform its neighbors about its schedule. 4) MSH-CSCH: Used for bandwidth request and granting when the centralized scheduling scheme is in use. If the Request/Grant Flag = 0, then the message is a grant message that is created by BS and forwarded along the routing tree. All SSs are eligible to send MSHCSCH:Request messages and if the Request/Grant Flag = 1, then the message carries a request to BS. 5) MSH-CSCF: Generated by BS and rebroadcasted by SSs in the routing tree. It is used for disseminating the channel conguration and routing tree information. It carries information about the channels available for centralized scheduling as well as the children information of the nodes in the routing tree. IV. OVERVIEW OF S CHEDULING IN M ESH M ODE Scheduling, in its most broad state, is dened as the allocation of limited resources to tasks over time [7]. In centralized scheduling, the resources are in the control of single decision maker which is aware of all jobs and their requests. On the other hand, in distributed scheduling, there are nodes/users/agents which compete for the resources with possibly conicting goals. SSs, the competing agents in IEEE 802.16, maintain some local information regarding their needs and they inform others via exchanging messages. Scheduling is one of the most important components of an 802.16 mesh network, severely affecting the overall performance of the system. Scheduling problem for 802.16 is dened as a sequence of time slots, where each possible transmission is assigned a time slot such that the transmissions on the same slot are collision free while the QoS requirements are fullled efciently and the total time to calculate the schedule is minimized. The most usual way to classify frame scheduling mechanisms in IEEE 802.16 mesh mode is to classify them as centralized and distributed scheduling. Distributed scheduling is further divided into two subclasses as coordinated and uncoordinated scheduling mechanisms. The main difference between coordinated and uncoordinated distributed scheduling is that the coordinated distributed scheduling claims to provide collision free transmission of MSH-DSCH messages. In coordinated distributed scheduling, all nodes arrange their transmissions through a pseudo-random algorithm so that their messages do not collide with messages from other nodes within their two-hop neighborhood. In uncoordinated scheduling, MSH-DSCH messages may collide and it is less reliable than the coordinated scheduling. Uncoordinated scheduling is usually preferred in fast ad-hoc setup of schedules and support of low duty-cycle trafc scenarios [8]. Distributed scheduling is usually advised for intranet

where SymOF DM stands for the OFDM symbols per frame. 2) Mesh Mode Specic MAC Messages: Table VI lists the MAC management messages that are specic for the mesh mode operation. 1) MSH-NCFG: Provides a basic level of communication between nodes. The data embedded in a MSH-NCFG message has many elds that have signicant uses in implementations of the proposed studies. For instance, it has two elds called MSH-CTRL-LEN and MSH-DSCH-NUM. MSHCTRL-LEN is the length of the mesh control subframe. Out of MSH-CTRL-LEN schedule control slots, MSHDSCH-NUM of them are used for distributed scheduling messages (MSH-DSCH) while the remaining ones are used for centralized scheduling messages (MSH-CSCH, MSH-CSCF). MSH-CSCH-DATA-FRACTION eld indicates the maximum percentage of data slots that can be allocated for distributed scheduling and it is determined at initial conguration of the network according to the partition scheme and remains xed thereafter. 2) MSH-NENT: Used for initial network entry and to gain synchronization. 3) MSH-DSCH: Carries grants/requests and information about slots that can be granted when distributed scheduling is used in the mesh mode.

210

IEEE COMMUNICATIONS SURVEYS & TUTORIALS, VOL. 12, NO. 2, SECOND QUARTER 2010

along the scheduling tree and all SSs receive the generated message. Then, according to the received MSH-CSCH:Grant message, each SS determines its actual uplink and downlink transmission time through a common algorithm that divides the frame proportionally to the assignments. B. Distributed Scheduling
Fig. 4. Types of Scheduling in Mesh Mode

trafc (the trafc among SSs) and centralized scheduling for Internet trafc (the trafc between an SS and a mesh BS or a gateway). Figure 5 presents a classication of these three types of scheduling mechanisms: Centralized Scheduling, Coordinated Distributed Scheduling, and Uncoordinated Distributed Scheduling. In the rest of this section, the centralized and distributed scheduling methods will be discussed in more detail. A. Centralized Scheduling In centralized scheduling, BS is responsible for determining resource allocation and informing back SSs through a scheduling tree which is rooted at BS. In order to maintain a routing tree in the network, BS generates and broadcasts MSH-CSCF message to all its neighbors. Then, the neighbors receiving this message continue to forward it to all their children until all SSs in the network are informed about the MSH-CSCF message and the routing tree information in it. Through this process, all SSs maintain information about the routing tree. The scheduling tree is updated upon registration of a new node, and the new scheduling tree is broadcasted by BS. Centralized scheduling is done in three steps as follows: 1) Collection of bandwidth requests from SSs 2) Determining resource allocations 3) Informing back the network In the rst step of the centralized scheduling, each SS having a packet to send, sends bandwidth request using the MSH-CSCH:Request message to its sponsor (parent) node. Each SS not only sends its own bandwidth request but also forwards the bandwidth requests received from its children. By this way, all the request messages in the network are routed to BS along the scheduling tree. The bandwidth an SS requires involves bandwidth for data transmission and data reception. If the node itself has free slots for the total required bandwidth, the request message is sent, otherwise the node quits. The request messages contain the node id, the data rate required for data transmission and the data rate required for data reception. When a node receives many requests from its children in that form, the message it forwards towards BS contains the list of all these requests. In the second step, BS has completed the reception of all the requests coming from SSs, and it determines the schedule by running a scheduling algorithm. This scheduling algorithm has a large impact on the performance and it is left unstandardized. In the last step, BS distributes the schedule by broadcasting MSH-CSCH:Grant message. The grant message propagates

The mechanism of the distributed scheduler is more complicated than that of the centralized scheduler since in the centralized scheduling the mesh BS acts as a cluster head which determines and distributes the time slots each SS may use. For distributed scheduling, the standard has dened the algorithm for EBTT mechanism, that is, the algorithm responsible for the allocation of control slots. However, the mechanism for the allocation of data slots is left unstandardized, open to vendors implementation. There are mainly two phases of distributed scheduling: 1) EBTT phase 2) Connection Setup with Neighbors (3-way handshake) 1) EBTT phase: Election Based Transmission Timing (EBTT) procedure is a distributed algorithm which is used to manage the control slots allocation, in other words transmission timing of broadcast messages to competing nodes in a collision-free manner in two-hop neighborhood (optionally, 3-hop neighborhood) without requiring explicit schedule negotiation. To be more specic, EBTT is used for the transmission time calculation in coordinated distributed scheduling for the MSH-NCFG and MSH-DSCH messages. Since these control slots are used to negotiate the schedule of data slots, the rst phase of distributed scheduling covers how the control slots are allocated to nodes. The intuition behind EBTT mechanism is to have nodes behave pseudo randomly so that all nodes can predict behavior of the nodes in its 2 or optionally 3 hop neighborhood. Therefore, the nodes send their packets without collisions. The randomized and predictable behavior is achieved through supplying each node with a random number generator seed according to a common rule. In other words, given the same kind of information, a node will be able to generate the same random number as another node, thus every node can predict what the other nodes generate. Assume that there is a node called X. We will focus on the most recent control slot it has selected to use, and then go over the procedure used to derive the next control slot it will use. Let Tx be the slot node X has selected and Txnext be the next slot it will choose. The interval between these two consecutive slots is the sum of two values: 1) Holdoff Time 2) Number of slots lost in contention The calculation of these values will be explored respectively. 1- Calculation of Holdoff Time In every MSH-DSCH message, Next-Xmt-Mx (mx) and Xmt-Holdoff-Exponent (exp) are included. The election algorithm assumes that the collisions happen only at the receiver and interference from two hop neighbors or even farther nodes are negligible if the network topology is designed carefully [9]. The nodes enter the competition to win the ownership of the

KAS et al.: A SURVEY ON SCHEDULING IN IEEE 802.16 MESH MODE

211

Fig. 5.

Comparison of Basic Scheduling Mechanisms in IEEE 802.16 Mesh Mode

2exp mx < Txnext 2exp (mx + 1)

(3)

Fig. 6.

Centralized Scheduling Illustration

slots by solving a virtual contention until they win. Once a node is the winner, the node intentionally skips as many slots as the Holdoff Time before entering the competition again. Holdoff-Time is calculated as: Holdof f T ime = 2(exp+4) (2)

From this formulation, the size of the eligibility interval can be derived as 2exp . To get its exact time of transmission, which lies within this eligibility interval, node X sets its temporary transmission time (Txtemp ) as the rst slot of its eligibility interval and then calculates the set of its eligible neighbors it will compete with. The set of competing nodes include the following: 1) Neighbors whose eligibility interval includes Txtemp , 2) Neighbors whose eligibility interval begins before Txtemp , 3) Neighbors whose Next-Xmt-Mx are not known. An election is held among this set of nodes. The seed for the pseudo-random algorithm selecting one of the eligible nodes as the winner of the slot consists of the combination of the competed slot id along with the IDs of all competing nodes. Since the seed value is known by all nodes, each node will produce the same result, so that they can all know who the winner is and predict others behavior without explicit message exchange. If node X is not the winner of the election, it sets its new temporary transmission time, Txtemp , as: Txtemp = Txtemp + 1 (4)

In other words, even if the Xmt-Holdoff-Exponent of a node is 0, it will have to skip at least 16 slots before joining the contention once again. The value of Xmt-Holdoff-Exponent is in the range of 0-7, therefore the range for Holdoff Time is [16-2048]. 2- Number of Slots Lost in Contention Upon skipping as many slots as Holdoff Time, node X becomes eligible to enter the competition again. To be able to compute its next transmission time exactly, it should know whether it is the winner for a given slot. Each node computes the set of possible competing nodes (among its 1-hop and 2-hop neighbors) for the slots in the interval it is eligible to compete. Next-Xmt-Mx (mx) and Xmt-Holdoff-Exponent (exp), which are transmitted in the MSH-DSCH messages, are used in the calculation of this eligibility interval as follows:

Once node X wins the election, it informs its neighbors to prevent collisions, and then the three-way handshake procedure gets started. 2) Connection Setup with Neighbors: Connection setup is a three-way handshake messaging procedure two nodes perform in order to negotiate upon the data slots they will exchange data. Connection setup in distributed scheduling is done in three steps: Step-1: Request Before initiating the message exchange procedure, the requester node (source) checks its own agenda to see if the data transmission rate it needs is above what it can achieve using all the free slots it has. If so, it quits the procedure directly. If it has enough number of slots itself, it sends a request message to the node that it wants to send data to or receive data from (destination), listing the IDs of its free slots and the

212

IEEE COMMUNICATIONS SURVEYS & TUTORIALS, VOL. 12, NO. 2, SECOND QUARTER 2010

TABLE VII D EPTH VS . FANOUT IN [13] Cause -Increasing Depth (#(hops from SS to BS)) -Decreasing Fanout (#(children per hop)) Increase Observed -Data Rate -Control Overhead -Spatial Reuse -No of Relay Transmissions Decrease Observed -Avg. Link Distance -Transmission Power -Interference

Fig. 7.

Three-way Handshake Procedure

data transmission rate it requires. Recall that requests/grants do not have to go through BS in mesh mode. Step-2: Grant Upon receiving the request message, the destination node checks if it has sufcient number of free slots to provide the data transmission rate the source node requires. If the destination node does not have enough slots, it just quits the procedure without sending any further messages. If it has, then the destination node checks its free slot IDs against the free slot IDs source node listed in the request message. If the number of matching slots meets the data transmission rate needed, then the destination node sets the states of these slots as busy (to be more specic, receiving) and sends back a grant message to the source listing the IDs of the minislots selected for transmission. Step-3: Conrmation At the last step, the source node sends out a conrmation message to the destination in the form of MSH-DSCH message which again includes all the slots granted and sets the states of the slots as transmitting. As seen, the framework for distributed scheduling is ready. However, the algorithm to be used in Step-2 of connection setup is left open. The details of the process according to which grants are done, in other words, the scheduler for the data slots is not standardized. V. S TUDIES ON C ENTRALIZED S CHEDULING The studies done in the eld of IEEE 802.16 mesh mode scheduling are grouped into two: studies on centralized scheduling and studies on distributed scheduling. The studies in the eld of centralized scheduling can be broadly divided into two: the ones that enhance spatial reuse by allocating non-interfering links to transmit concurrently and the ones with no spatial reuse [6]. There are some very basic issues affecting the design and performance of centralized scheduler and most of the research done revolves around these issues. One such frequently addressed issue is the capacity enhancement in wireless multi-hop networks. Among the suggested solutions, achieving spatial reuse with concurrency among multi-hop transmissions appears as the one closest to bring improvement to the overall throughput of such systems. However, while achieving concurrency, interference must be prevented and this is a challenging and major problem for the multi-hop WiMAX mesh networks.

Besides, the structure of the routing tree in the network plays an important role and enhances the performance of centralized scheduling by reducing interference between links, balancing the trafc load and shortening the period of requests and grants. Considering these two issues, some articles investigate the design trade offs involved in the mesh tree construction, and some articles propose a routing tree construction algorithm and a scheduling mechanism exploiting the features of the tree constructed on a particular purpose. While [10] only gives a scheduling mechanism based on well-known algorithms like Round-Robin or MaxWeight, [11], [12] perform scheduling via considering QoS requirements in the IEEE 802.16 mesh networks. A. Spatial Reuse Oriented Studies To start with the routing tree construction, in [13], the performance of the centralized scheduling based mesh networks is investigated via analyzing the design trade offs (depth vs. fanout) involved in the mesh tree construction. The base argument in this study is that, long links increase the distance that can be served while being able to support only low bit rates whereas shorter links work with higher rates. Reducing the depth reduces the number of transmissions needed for the same packet hence reduces the control packet overhead. However, increasing the depth increases the data rate but reduces the distance, thus the area covered. The authors also point out that if the distance is longer (in terms of meters), the needed transmission power is higher which in turn causes higher interference and decreases the chance of having spatial reuse, a topic which is also studied in [14]. Finally, the authors recommend having deeper trees which split long links into multiple smaller links considering the simulation results obtained. The discussed changes and their corresponding effects are presented in Table VII. In [14], an interference-aware routing tree construction algorithm and an enhanced centralized mesh scheduling scheme achieving high spectral utilization are given. The proposed scheduling scheme considers selecting the routes with less interference so as to improve the throughput. To achieve this, the authors dene a blocking metric for a route which is used during the route construction, modeling the number of nodes whose transmissions will be blocked by the route. For this, interference level of routes in the mesh is modeled. Each joining node selects its sponsor node among its neighbors with the minimum interference level. Therefore, all the routes are constructed with the minimum interference level. Next three papers extend the idea presented in [14].

KAS et al.: A SURVEY ON SCHEDULING IN IEEE 802.16 MESH MODE

213

TABLE VIII E NHANCEMENTS ON [14] Key Features of [14] Route Construction Blocking Metric Scheduling Scheme Enhancements Impact of entry order prevented [15] Blocking Metric redened as num of blocked nodes x num of packets [16] Biggest hop-count comes rst [15] Fairness, 4 different link-selection criteria [17]

TABLE IX C OMPARISON OF T HREE C ENTRALIZED S CHEDULING A LGORITHMS IN [18] Scheduling Algorithm 802.16 Algorithm Load-balancing Algorithm Bellman-Ford Algorithm Key Feature Ranking with Breadth-rst Traversal of Routing-tree Link-scheduling version of [14] Bandwidth-Optimal Ranking according to Bellman-Ford on Conict Graph Spatial Reuse No Yes Yes

In [16], the idea in [14] is extended and the blocking metric is redened. In this study, the blocking metric of a node X is dened to be the number of blocked nodes multiplied by the number of packets at X. Then, similarly, the path with minimum blocking metric is selected. In [15], same approach in [14] is adapted with an incremental improvement on it. This improved method enables adjustment of the impacted SSs sponsoring nodes upon a newly entered node to the network. Hence, the impact of the entry order in construction of the routing tree is prevented unlike in [14]. Both of the proposed scheduling algorithms ([14] and [15]) seek high spectral utilization and system throughput maximizing the number of concurrent transmissions without creating interference. In [14], trafc capacity request of each SS is considered and the proposed solution allocates unit trafc starting from the highest demand to the lowest until there is no unallocated capacity request. However, [15] considers the delay of relaying data and determines the order of transmission time same as MSH-CSCH:Request message order, in which nodes with the biggest hop-count comes rst, ones with the same hop-count keep their orders. [17] also focuses on the tree structure to handle centralized scheduling to achieve reduction in the length of scheduling, improvement in the channel utilization ratio and decrease the transmission delay. They propose an O(n2 ) Transmission-Tree Scheduling (TSS) Algorithm which grants slots to SSs proportional to their demands, preventing nodes from starvation, thereby achieving fairness. The idea behind is the hop-by-hop circulation of service tokens. It works by assigning a service token for each slot and when a link is scheduled the token count of the transmitter is reduced whereas the token count of the receiver is increased. In allocation of slots in each iteration, link selection can be done in four ways rather than allocating for the link with the highest unallocated trafc demand as in [14]. Link selection criteria are given as: random, mininterference, nearest to BS and farthest to BS. According to the simulation results presented in the paper, among these four link selection methods, best results are achieved by nearest to BS, followed by random and min-interference and the performance of farthest to BS is the worst among four. The reason is that in mesh topologies, the nodes close to BS become the bottleneck. Giving priority to their links over the others reduce the scheduling time required. Table VIII summarizes the enhancements brought over [14]. In [18], three constraints that the 802.16 centralized scheduling protocol enforces on the centralized scheduling algorithms are identied:

1) The assignment of link bandwidths should construct a tree which has BS as its root. 2) Bandwidth assignments to links should comply with the end-to-end bandwidth demands so that the requests are satised as much as possible. 3) Since the overhead of each transmission is large, the number of transmissions per frame for each link should be limited. Aiming to address these requirements, a centralized bandwidth assignment algorithm which assigns bandwidth to links upon the collection of end-to-end bandwidth requests is proposed. In this algorithm, the authors put emphasis on the routing tree structure. There are two distinct routing trees both of which are in the form of spanning trees. One of these trees is associated with the uplink trafc and the second one is associated with the downlink trafc. The overall bandwidth required by each link is calculated by adding up the trafc of each path passing through that particular node. Using these bandwidth requirements, the number of required OFDM symbols (if not all the requirements can be satised, then is link is assigned as much as possible) is assigned to each link. This value is used as an input to the three centralized scheduling algorithms discussed in the paper (802.16 Algorithm, Loadbalancing Algorithm, Bellman-Ford Algorithm). The common point of all these three algorithms is that they all get the number of required OFDM symbols (the number of slots) as their input, and they all rank the links so that the links with lower ranks transmit before the links with higher ranks. The ranking schemes is what essentially differentiates these three algorithms (See Table IX). Among these three algorithms, Bellman-Ford algorithm provides the best results in terms of spatial reuse, bandwidth allocation and end-to-end delay [18]. In [19], a centralized scheduling algorithm which aims to maximize throughput under the fairness model subject to capacity constraints is proposed. Each SS node has a fairness weight fi which is determined according to pricing or other system-wide objectives. This article is one rare study which mentions pricing as a constraint integrated into scheduling decision. To have a supporting point for their fairness model proposal, the authors suggest that if the actual trafc demands of nodes are not taken into account and fairness is dened as hard-fairness, then the achievable capacity region achieved by hard-fairness (each node is given a weight regardless of the actual trafc demand) algorithm is a sub-region of the capacity

214

IEEE COMMUNICATIONS SURVEYS & TUTORIALS, VOL. 12, NO. 2, SECOND QUARTER 2010

region achieved in the case of varying fairness weights. Another important claim is that the number of possible activation sets (sets of links in the scheduling tree that can be activated concurrently) is typically exponential in the number of links, even in the sub-optimal formulations. B. QoS Oriented Studies [12] proposes joint routing and centralized scheduling solutions. However, they present algorithms providing QoS to real time and interactive data applications with efcient use of network resources and they assume that there is no spatial reuse. In addition, an admission control policy is provided for new TCP connections when the network is congested. The authors start with covering how a routing protocol for IEEE 802.16 mesh should be. Fixing the routing within the network along with the use of shortest path algorithm is suggested. Their reason of choosing xed routing is not to have loops on the routes to be able to reserve resources along the path, and keep the route the same for a node unless the link is too bad. Then, QoS requirements and behaviors of TCP and UDP trafc are presented in detail and the scheduling algorithms are handled in three distinct parts: QoS for Real Time Trafc (meeting the needs of UDP trafc), QoS for TCP Trafc, and joint scheduling of UDP and TCP that provides QoS in a network serving both real and non-real time applications. In providing QoS to TCP applications, the authors consider one xed and one adaptive xed allocation scheme. In adaptive xed allocation scheme, each SS is assigned a xed number of slots according to its average link rate. [11] also proposes a QoS mechanism and a BS scheduler for centralized scheduling. The QoS mechanism is developed from the QoS of PMP mode with a slight change in node identiers. Five virtual IDs are assigned to each node, one for each of the ve serving classes dened in the standard [5]. The proposed BS scheduler makes decisions according to each SSs current request and the grants given to all SSs in the network. The delay for real-time and multimedia services is intended to be reduced in considerable amount by this way. [10] is another research proposing algorithms for the centralized scheduler. Round Robin, Earliest Deadline First, Greedy and Modied Decit Round Robin are among the most commonly preferred scheduling algorithms. In [10], adapting the traditional approaches, two algorithms are proposed. One operates in Round-Robin fashion and the other operates in Greedy fashion. The Round-Robin based algorithm executes the following steps for every SS in a Round-Robin fashion. If the node has data to receive, for every node that is on its route towards BS on the scheduling tree, it sets the states of as many slots required by its child as RX (Receiving). Then, it is checked if this node is the destined node. If not, it has to be an intermediate node on the scheduling tree and it should forward the data it receives. Therefore, the next set of slots is marked as TX (Transmitting) to be used in forwarding process of this data as the store-forward mechanism is in use. If the number of slots marked for a node (either intermediate or destination node) exceeds 256 slots, the algorithm returns fail. Same process is applied if the node has data to send.

In the greedy algorithm proposed, mini-slot reuse is adapted on top of the Round Robin algorithm. Every node that has data to send, checks every node that is on its route to BS on the scheduling tree to see if it can use that nodes jth time slot via checking if there is a collision between the currently examined layers node and its previous node. This is important, as each nodes request keeps its parent nodes busy in that particular time slot. If there is no collision, then the nodes jth slot is set as receiving, and its previous node (its parent in the scheduling tree) is set as transmitting unless it is the mesh-BS itself. In [10], the pseudo-codes of the algorithms are given. IEEE 802.16 standard offers a partitioning scheme, which partitions the minislots of a data subframe into two. The minislots in the rst partition are scheduled by a centralized scheduler, and the slots in the second partition are scheduled via distributed scheduling. At the initial conguration of the network, the MSH-CSCH-DATA-FRACTION parameter is set and broadcasted through MSH-NCFG messages as previously mentioned in Section III-B. This parameter indicates the maximum percentage of the minislots in a frame that can be used by the centralized scheduler. Hence, the rest of the minislots can be used by distributed scheduler [4]. Considering the importance of the frame utilization, in [10] a partition scheme which aims to improve the partition scheme in the standard is given. In the partition scheme given by the standard, the MSH-CSCH-DATA-FRACTION parameter is set at the initial network conguration. It then remains xed and cannot be adjusted thereafter; hence the slot utilization may not be maximized. The proposed Combined Distributed Centralized (CDC) scheme addresses this shortcoming and increases the utilization by exibly allocating the unused slots without considering the scheduling type reserved for that slot. SSs see which of their slots are used upon receiving the grants from BS. Therefore, it is possible to allocate slots of distributed scheduling for centralized scheduling, and to use the rest for distributed scheduling next time and vice versa. Figure 8 provides a comparison of the centralized scheduling studies discussed in this survey. If there are multiple ticks, the number of ticks stands for the number of different solutions developed in the corresponding article regarding the discussed feature. VI. S TUDIES ON D ISTRIBUTED S CHEDULING The research about distributed scheduling for IEEE 802.16 can be mainly grouped into two. The rst group focus on the performance evaluation of the distributed schedulers and derive or extend a mathematical model to analyze and model its behavior or propose techniques to improve the performance of EBTT or scheduler mechanism. The studies in the second group mostly propose algorithms to fulll the scheduling step left open in the standard. In relation to their specic approaches, these can be classied further. There are other possible classications as well. For instance, there are studies for single BS mesh networks whereas some studies state that they are for mesh networks having multiple BSs. Also, there are some other publications that propose methods for fullling the QoS requirements in IEEE 802.16 networks. These usually try to imitate the way QoS is handled

KAS et al.: A SURVEY ON SCHEDULING IN IEEE 802.16 MESH MODE

215

Fig. 8.

Comparison of Centralized Scheduling Studies

in PMP mode and/or to introduce prioritization. For the rest of this section, the ideas and approaches adapted in these studies are explored further. A. Studies with Focus on Performance of EBTT Mechanism In [20], the authors derive a stochastic model for the distributed scheduler of the mesh mode via exploiting the idea that the EBTT mechanism lies in the heart of the distributed scheduler of mesh mode. The authors motivation for deriving such a stochastic model has a very valid argument which is based on emphasizing the differences between IEEE 802.11 and IEEE 802.16. In addition, understanding the scheduler behavior is a must for correctly analyzing the performance of a system. The authors consider the time between two consecutive transmissions (the time between Tx and Txnext ) and the delay for connection setup as the performance metrics and derive formulations in order to estimate these. They hold the assumption that the transmit sequences of all nodes in the control subframe form statistically independent renewal processes [20]. As explained in Section IV, the interval is the sum of the exponential Holdoff Time and the next transmission time which depends on the number of slots lost in competition. Hence, the interval between successive transmission opportunities of a node is modeled depending on the expected number of competing nodes and the topology of these nodes. For instance, under the general topology scenarios there may be other competing nodes whose schedules are not known by the node. Such nodes are also included in the formulation as potentially competing nodes. Also, the number of slots that are lost is approximated with a geometric distribution. Let N be the number of competing nodes and E(S) is the estimation of the slots lost in competition. E(S) = (N 1) 2(exp+4) 2exp + E(S) +1 + E(S) (5)

Consequently, the mean time between two consecutive transmissions is calculated as follows: Txnext Tx = Holdof f T ime + E(S) (6)

These two formulations are very important since they are at the heart of delay and transmission interval calculation and

very useful in overall delay and throughput estimations. These formulas are referred to in many other papers as well. An important result the authors of [20] happen to realize gives inspiration to other studies in literature. According to their results, the holdoff exponent values have a much higher effect on the system than the contention. In their simulations, they demonstrate that the connection setup delay depends on the different holdoff exponent values selected. Therefore, the exponent values should be adjusted, in other words, prioritized. In [21], this idea is combined with EBTTs being one of the most important components of the scheduler performance. An extended version EBTT (Election Based Transmission Timing) mechanism which tries to increase network performance via considering the network contention (in other words adjusting the holdoff time) is proposed. The holdoff times given to the nodes are prioritized. That is, 0 expMeshBS < expActive < expP otentialF orwarding < expInactive 7 The holdoff times of the nodes are adjusted in accordance with their status updates and whether the network contention has exceeded a certain threshold. Moreover, they are suggesting having a limit on the maximum requestable bandwidth in order to provide fairness to some extent. In [22], the authors worked on the same subject and pointed out that if the EBTT mechanism is left as the way it is, collisions are very likely although it is designed to work in a collision free manner. They also demonstrate that there is a signicant amount of delay incurred on data packets due to back-off time which is of at least 16 slots long after each MSH-DSCH transmission. It is also pointed out that the reference point calculation for two hop neighbors is unstandardized as well as the consistent numbering of CDSCH transmission opportunities. The reference point in time is not mentioned in the standard but if the sender of the MSHDSCH is two or more hops away, the node will not know the original transmission time of the message and a reference point time will gain importance. The consistent numbering of transmission opportunities is important as it is the seed value for the pseudo-random component of EBTT mechanism. To enhance the mechanism further, they propose to replace the constant exponent in Eq(1) with 0 which is given as

216

IEEE COMMUNICATIONS SURVEYS & TUTORIALS, VOL. 12, NO. 2, SECOND QUARTER 2010

TABLE X P ERFORMANCE PARAMETERS AND T HEIR O BSERVED E FFECTS [9] Change of Parameter Holdoff Exponent Frame Duration Number of Control Slots per Frame Number of Neighbors Observed Effect Minimum Holdoff Time Average Access Interval Average Access Interval Average Access Interval Probability of winning a slot Number of Competitors Control Slots Utilization

Number of Nodes

4 in the standard. As their future work, they plan adapting a dynamic exponent value to meet QoS requirement which revolves around the same idea highlighted in [20], and they have published it in [21], as previously mentioned. In [9], the performance of mesh election procedure is investigated via extensive simulations. Table X provides a list of the investigated parameters and their corresponding effects on the networks. In [8], the importance of holdoff time is again emphasized and combined with the idea of proposing an election algorithm to replace the current one to be able to guarantee collision-free scheduling under non-quasi environments as the interference is the key limitation in mesh network performance. Once a node becomes eligible to enter the competition for slots, it sets its temporary transmission time (Txtemp ) as the rst slot of its eligibility interval and increments it one by one every time it loses until it wins. The authors propose to have the very last slot of the eligibility interval as Txtemp and claim that this will reduce the interference and contention. This study in some way makes an objection to the standards basic assumption that the interference from more than two-hop neighborhood is negligible. Indeed, as they also point out, this issue is taken into account in the standard since an optional parameter is dened for the election mechanism which runs the competition among three-hop neighborhood to reduce the collisions even further. The simulation results justify the tradeoff between holdoff time and reception collision ratio as expected, having more delay but less contention and collisions. B. Studies with Focus on Algorithm Proposals In [23], another work dealing with QoS, the priority/class based handling of packet transmissions is introduced when the network gets congested. The proposed priority/class based implementation of QoS mechanism in mesh mode is similar to the idea in the PMP mode. The information they use for this prioritization is embedded in the MAC frame. In PMP mode, three elds can be dened, Reliability, Priority/Class, and Drop Precedence, and they propose to make use of these elds to achieve QoS requirements. In the rst version of their algorithm (A1), the authors suggest computing the number of requested minislots rst and then checking if there are sufcient number of contiguous minislots available. If yes, a grant message is sent to the requester, otherwise failure information is sent. In order to

support QoS, they suggest checking whether the utilization of the frame (ratio of minislots allocated) is above a preset threshold value. If so, the network is considered as congested and priority values come into play, otherwise all the requests are treated to be the same level. In the second version of their algorithm (A2), they add another checkpoint to check if the network has become congested while it was not congested by the time of the rst check point. There are other studies that propose to allocate the slots in proportion with some metric such as number of ows or the amount of trafc demand rather than introducing prioritization mechanism. In [24], multiple algorithms with increasing complexity are proposed. The easiest algorithm they propose is to share the slots of a frame among the nodes according to the number of nodes in the network so that every node gets equal share. Then, they propose to have the shares of nodes in proportion to the number of ows each node has. The authors then again improve their ideas and try out giving more slots to the nodes with higher trafc demand. However, such a slot allocation algorithm either causes too many collisions because of the same competing set as the entire network or disables spatial reuse of the slots by not setting the network as a whole competing set. Finally, a scheduling algorithm based on nite elds is given to overcome the vulnerability to topology changes. The idea is to change the requirement of collision free transmission in every slot into having only one slot to have collision free transmission. [25] is another study on distributed scheduling in TDMA networks proposing an algorithm with the aim of minimizing the ordering delay, and the proposed algorithm has applicability in WiMAX networks. This algorithm is a two-phase algorithm. The rst phase includes an iterative procedure which, by exchanging link scheduling information between nodes, constructs a conict graph and nds a feasible schedule based on the distributed Bellman-Ford algorithm running on this conict graph. The second part of the algorithm is a wavebased termination procedure which is used to detect whether all the nodes are scheduled and if a new schedule should be activated. It is emphasized in the simulation results that their algorithm has attractive practical performance despite the high worst case complexity. Contiguous allocation of slots is a commonly seen approach in many studies [10], [15], [24]. For instance, in [10], the authors allocate contiguous slots to a node in each frame. In [15], the proposed algorithm looks up if there are enough contiguous slots to meet the demand and returns failure otherwise. [24] explains the reason for this approach through the overhead introduced to the control messages. If the slots are not contiguous, the size of the information contained in MSH-DSCH message listing the granted slots becomes important since each availability is represented in 32 bits [10]. All the studies examined so far focus on coordinated distributed scheduling, leaving uncoordinated distributed scheduling out as it is more unreliable, and allowing collisions to happen very frequently. It may also be due to that the standard pushes the uncoordinated scheduling should not cause collisions with the schedules decided by the coordinated schedulers [26]. To the best of our knowledge, there is no study on uncoordinated distributed scheduling. Figure 9 presents

KAS et al.: A SURVEY ON SCHEDULING IN IEEE 802.16 MESH MODE

217

Fig. 9.

Comparison of Distributed Scheduling Studies

a comprehensive comparison of the distributed scheduling related studies discussed in this survey. VII. C ROSS - LAYER S TUDIES In the literature, there is a set of recent papers such as [27], [28], [29], focusing on cross-layer features which can be used to enhance the scheduler performance in WiMAX mesh mode. Although there are other studies making use of cross-layer features, e.g. [14], [21], [23], the studies discussed in this section differ from the others in the sense that they not only focus on scheduling but also propose to loosen strict layered architecture to attain better performance. Most of the cross-layer studies try to improve the centralized scheduler performance either by involving distributed scheduler or by designing the scheduling algorithm to be adaptable with either the network layer, or the physical layer or both. In [27], [28], cross-layering network and MAC layers is considered, whereas in [29] an intelligent MAC layer which acts coherently with the routing layer as well as the physical layer is preferred. [27] focuses on the idea that the split between the distributed and centralized scheduling in a time frame may not actually represent the ratio between the intranet and Internet trafc. The links that are in the centralized scheduling tree are called centralized links and the rest of the links between any two SSs are called distributed links. The authors suggest checking the queue lengths of the associated centralized links and change the route for the Internet trafc to the distributed links if the queue length of a centralized link exceeds a certain threshold. Their aim is to reduce the end-to-end delay and number of packet of drops in the Internet trafc. However, not to hinder the actual intranet trafc for a long time, they switch back to the normal routes (the routes through the centralized links) if the congestion (queue length) drops below a certain threshold. In [27], algorithms for some of the unstandardized components are presented as well. To handle the Internet trafc, the authors developed a Hop Count Aware (HCA) BS scheduler which prioritizes SSs in accordance with their hop counts. Since the requests from SSs are delivered to BS through the concatenation of requests, an SSi with a hop-count HCi and a

Fig. 10.

Cross-layer Architecture Proposed by [28]

request of size Rqsti is known to consume HCi .Rqsti amount of trafc and the slots are assigned accordingly. In [28], cross-layer concept is introduced and a centralized BS scheduling algorithm based on multi-path routing is proposed. The implementation of the cross-layer module is separated into two interdependent sub-modules: 1) Multi-path Routing Module 2) Centralized Scheduling Module The Multi-path Routing Module in the Network Layer is responsible for multi-path source routing (searching for different routes and selecting the optimized routes), interference avoidance, load balancing and QoS guarantee. The optimized route is selected via calculating a metric as a combination of least interference, load balance and QoS indicators. The routing module passes the routing tree and interference table down to the MAC layer. MAC layer contains the Centralized Scheduling Module which uses the information obtained from the Multi-path Routing Module and is responsible for the resource allocation, spatial reuse and request collection. MAC layer is also responsible for informing the Multi-path Routing Module about SS resource requests. Associating these requests with the possible available routes, the mesh BS can then assign minislots to SSs using the information obtained from interference table and the routing tree. The proposed cross-layer structure is given in Figure 10. The algorithm proposed for BS centralized scheduler maintains two lists of links: rst one for the links that have demands to be satised (Pending Links List) and the second one for the

218

IEEE COMMUNICATIONS SURVEYS & TUTORIALS, VOL. 12, NO. 2, SECOND QUARTER 2010

links that are already scheduled (Scheduling Links List). The algorithm selects the link Li with the highest QoS demand from the Pending Links List and moves Li into the Scheduling Links List. Then, checking the interference table, the links that can communicate concurrently with Li are also removed from Pending Links List and put into the Scheduling Links List. In [29], a novel cross-layer structure is presented which achieves increase in the overall network throughput as well as decrease in the power consumption by overcoming mutual interferences. The interfering link pairs are specied as input to the proposed cross-layer architecture. The authors put emphasis on three distinct parts as the components of this architecture: Power Control Process, Tree-type Routing Construction, and Tree-level based Scheduling (See Figure 11). Power control process is responsible for determining power used for transmission as well as the selection of modulation and coding rate (AMC). The formed routing tree promotes the use of shorter links rather than the longer ones in order to keep transmission power and interference low. In addition, the neighbor number ratio is checked to encourage the use of less congested links so that congestion is avoided and power consumption is reduced. The scheduling algorithm combines the rate adaptation and the power control algorithms. In the scheduling algorithm, the requests are relayed while being concatenated at each node with the children nodes requests. Each node assigns bandwidth to its links in proportion to its links queue loads. A more general and in-depth discussion on the importance of cross-layer operation for scheduling in emerging broadband wireless systems is provided in [30]. VIII. A NALYSIS AND I NFERENCES This section is devoted to layout the similarities and differences among the distributed and centralized scheduling related studies. Centralized scheduling studies sometimes use ideas that have common points with the studies on PMP mode. For instance, in [10], two algorithms one of which is Round Robin based are proposed for centralized scheduler of the mesh topology. Similarly, [31] presents a Weighted Round Robin based scheduling algorithm for WiMAX BS running in PMP mode. The key idea is that since the scheduling must be performed very quickly during the current frame for the next one. Unlike previous works on that subject, they propose a simple one level scheduling mechanism that performs the slot allocation according to QoS and bandwidth requirements rather than complex schedulers or a hierarchy of schedulers. The proposed scheduling mechanism [31] involves three stages. The rst stage is the calculation of the minimum number of slots for each connection according to ve different service classes dened by the IEEE 802.16d-e specications [4], [5]. The next stage is allocation of the unassigned slots to some connections (work-conserving behavior) according to the maximum number of slots calculated previously for each connection. In the last stage, the order of slots to improve the QoS guarantee is selected. A sample algorithm is presented which shows that the interleaved slot order would be better

in order to decrease the maximum jitter and delay values but disadvantageous because of the increased size of the UL-MAP and DL-MAP messages. These two studies [10], [31] form just an example which demonstrates that there are many similarities between the approaches adapted for PMP mode and centralized scheduling in mesh mode. Many other examples can be found in the literature. For instance, in [32], WiMAX 802.16e OFDMA systems are mainly targeted. In [32], enhancing the performance by assigning multiple carriers to users within each time slot of a frame is considered. For this purpose, MaxWeight algorithm in single-carrier environments is examined and adapted to the multi-carrier case. In this respect, the authors suggest a very straightforward approach for adaptation of single carrier scheduling algorithms to multi-carrier scheduling algorithms. The authors discuss that it is possible to schedule each carrier independently and one by one using a single carrier algorithm. However, they develop techniques to overcome the possible drawbacks of this approach. This case shows a path for the adaptation of algorithms designed for 802.16d mode to the 802.16e mode. On top of this, centralized scheduling based studies have some other similarities with studies on distributed scheduling. For instance, for algorithms designed to work with the IEEE 802.16 mesh topology, the messaging format used must be aligned with the mesh frame format. Hence, most of the proposed studies (centralized/distributed) either directly use the data embedded in MSH-XXXX messages elds or make use of them to derive the values they require. There are also various points that centralized scheduling and distributed scheduling can be compared. In [33], the performance of centralized scheduling vs. distributed scheduling is compared. Referring to their simulation results, the authors conclude that centralized scheduling outperforms distributed scheduling and the gap of performance gets larger in a faster way as the number of nodes and hops increase. In [34], this point is also discussed and the authors draw attention to that unnoticed interference can severely reduce the throughput performance of WiMAX networks if a pure distributed scheme is used as shown in their previous work [8]. The reason for this is explained as centralized mesh scheduling combines the low overhead of centralized scheduling along with the performance of multihop mesh connectivity. Yet, it is still pointed out that the setup phase during which the mesh BS collects the requests may take long and degrade the performance. However, in some cases, distributed scheduling is preferred over centralized scheduling due to its being more exible and responsive. This is because SSs take their decisions locally according to their local information and physical channel status. Besides, the intranet trafc is handled without keeping mesh BS busy [9]. In [10], it is also recommended that centralized scheduling should be used for the Internet trafc and distributed scheduling should be used for the intranet trafc. This makes the centralized scheduling trafc the dominant trafc type in the network. Another point which is quite important for both centralized and distributed scheduling is the collisions due to conicts. There are two main types of conicts that should be avoided in order to achieve a collision free schedule:

KAS et al.: A SURVEY ON SCHEDULING IN IEEE 802.16 MESH MODE

219

Fig. 11.

Cross-layer Architecture Proposed by [29]

1) Primary Conict: Observed if a node is scheduled to transmit and receive at the same time. 2) Secondary Conict: Observed if a node is scheduled to receive from two different nodes simultaneously or a links transmission is corrupted by the interference from a neighboring link. The solutions for handling the secondary type of conicts are quite different from one another. In [8], an objection is made to the standards basic assumption that the interference from more than two-hop neighborhood is negligible. In contrast, in [19], the secondary conicts are mostly ignored since BS and SSs are typically equipped with directional (e.g., beamforming) antennas. IX. O PEN R ESEARCH I SSUES The discussion so far indicates that there are many issues to be considered in proposing a solution for scheduling in WiMAX mesh networks. Below, some of the key issues are highlighted: 1) Most of the studies on distributed scheduling so far focus on the the theoretical aspects of the performance evaluation, and the proposed algorithms are usually very vaguely described. A robust slot allocation algorithm with a clear pseudo-code and extensive simulation results would be very well received in the research community. 2) The dynamic partitioning of the time frame between the centralized and distributed scheduling has been investigated in two papers so far, each of which handles this issue from very different aspects [10], [27]. Proposing a dynamic partitioning scheme which is adjusted in accordance with the number of lost/dropped packets or the channel quality indicators might be interesting. 3) More studies on cross-layer optimizations that use routing and/or physical layer information in different aspects are needed. The number of papers addressing this issue is quite limited. 4) In order to provide guaranteed throughput to stations, a scheduling algorithm must be supported by Call Admission Control and Congestion Control modules. A possible research direction may be on scheduling which considers scheduling together with Call Admission Control and Congestion Control so that more ows satisfying QoS requirements are admitted. A comprehensive survey on call admission control in wireless networks is

5)

6)

7)

8)

9)

10)

provided in [35] while [36], [37] provide information on different aspects of QoS in wireless systems in general. Different routing schemes establishing routes through different strategies might be developed or adapted from previous studies in the literature. To the best of our knowledge, there are no publications that compare the affects of different routing schemes over a WiMAX mesh network where a certain scheduling scheme is xed. Majority of the mesh scheduler algorithms in the literature do not consider delay and jitter together although they are very important for multimedia applications. Fairness should be considered both at the station level (among SSs) and the user level (inside an SS). The proposed algorithms generally leave out one or the other. In addition to addressing these two levels fairness problems together, the future algorithms should also ensure that no starvation is incurred. There are many reliable simulation tools designed for PMP mode [38], [39], [40]. However, there are not many publicly available tools that support the mesh mode operation. A recent patch supporting 802.16 mesh mode on ns-2 is provided [41]. The drawback of [41] is that it is not inter-operable with ns-2 routing algorithms and physical interference modules. A simulation tool, implemented on a widely used simulation environment such as Qualnet, OPNET or ns-2 with a pluggable 802.16 mesh architecture, which supports the replacement of unstandardized algorithms or which extends the previous simulation modules [38], [39], [40] would also be extremely useful for the research community. There are studies that try to reduce the overhead [10], [15], [24] by employing contiguous slot allocation as much as possible. However, most of the articles proposing scheduling algorithms present no simulation results that analyze thoroughly the overhead and the reduction in the overhead achieved by the application of a certain approach in the algorithm. Scheduling might be investigated along with the pricing issues achieving the optimization of the use of radio resources as well as the optimization of the revenue of the operator [42].

X. C ONCLUSION The number of papers published so far indicates that problems regarding centralized scheduling issues are better

220

IEEE COMMUNICATIONS SURVEYS & TUTORIALS, VOL. 12, NO. 2, SECOND QUARTER 2010

explored while there is still a lot to be done in the area of distributed scheduling. Moreover, adaptation of schedulers to handle mobility properly without being too vulnerable to topology changes is another issue still waiting to be explored. Studies proposing ideas on scheduling related research issues which are presented in Section IX and on other points left open by the standard and studies involving more complicated simulation scenarios and simpler and clearer analytical results are to be expected. R EFERENCES
[1] I. W. G. . on Broadband Wireless Access Standards, Ieee working group 802.16 on broadband wireless access standards web page, http://www.ieee802.org/16/. [2] I. Motorola, WiMAX: E vs. D The Advantages of 802.16e Over 802.16d, 2007. [3] J. Andrews, A. Ghosh, and R. Muhamed, Fundamentals of WiMAX. Prentice-Hall, 2007. [4] IEEE Standard for Local and Metropolitan Area Networks Part 16: Air Interface for Fixed Broadband Wireless Access Systems, IEEE Std 802.16-2004, pp. 1895, 2004. [5] IEEE Standard for Local and Metropolitan Area Networks Part 16: Air Interface for Fixed Broadband Wireless Access Systems-Amendment 2: Physical and Medium Access Control Layers for Combined Fixed and Mobile Operation in Licensed Bands, IEEE Std 802.16e-2005 (Amendment to IEEE Std 802.16-2004), pp. 1864, 2005. [6] D. Ghosh, A. Gupta, and P. Mohapatra, Scheduling in Multihop WiMAX Networks, 2008. [7] A. Attanasio, G. Ghiani, L. Grandinetti, and F. Guerriero, Auction algorithms for decentralized parallel machine scheduling, Parallel Comput., vol. 32, no. 9, pp. 701709, 2006. [8] H. Zhu and K. Lu, Performance of IEEE 802.16 Mesh Coordinated Distributed Scheduling under Realistic Non-Quasi-Interference Channel. [9] C. Cicconetti, A. Erta, L. Lenzini, and E. Mingozzi, Performance Evaluation of the Mesh Election Procedure of IEEE 802.16/WiMAX, Proceedings of the 10th ACM Symposium on Modeling, Analysis, and Simulation of Wireless and Mobile Systems, pp. 323327, 2007. [10] S. Cheng, P. Lin, D. Huang, and S. Yang, A Study on Distributed/Centralized Scheduling for Wireless Mesh Network, International Conference On Communications And Mobile Computing, pp. 599 604, 2006. [11] M. Kuran, B. Yilmaz, F. Alagoz, and T. Tugcu, Quality of Service in Mesh Mode IEEE 802.16 Networks, 14th International Conference on Software, Telecommunications and Computer Networks, 2006. [12] H. Shetiya and V. Sharma, Algorithms for Routing and Centralized Scheduling in IEEE 802.16 Mesh Networks, IEEE Wireless Communications and Networking Conference, 2006. [13] S. Nahle, L. Iannone, B. Donnet, and T. Friedman, Investigating Depth-Fanout Trade-Off in WiMAX Mesh Networks, Proc. 1st WEIRD Workshop, 2007. [14] H. Wei, S. Ganguly, R. Izmailov, and Z. Haas, Interference-aware IEEE 802.16 WiMAX Mesh Networks, Vehicular Technology Conference, 2005. VTC 2005-Spring. 2005 IEEE 61st, vol. 5. [15] J. Tao, F. Liu, Z. Zeng, and Z. Lin, Throughput Enhancement in WiMAX Mesh Networks Using Concurrent Transmission, Wireless Communications, Networking and Mobile Computing, 2005. Proceedings. 2005 International Conference on, vol. 2, 2005. [16] F. Jin, A. Arora, J. Hwang, and H. Choi, Routing and Packet Scheduling in WiMAX Mesh Networks, in Broadband Communications, Networks and Systems, 2007. BROADNETS 2007. Fourth International Conference on, 2007, pp. 574582. [17] B. Han, W. Jia, and L. Lin, Performance Evaluation of Scheduling in IEEE 802.16 based Wireless Mesh Networks, Computer Communications, vol. 30, no. 4, pp. 782792, 2007. [18] P. Djukic and S. Valaee, Centralized Scheduling Algorithms for 802.16 Mesh Networks, WiMax/MobileFi: Advanced Research and Technology, 2007. [19] M. Cao, V. Raghunathan, and P. Kumar, A Tractable Algorithm for Fair and Efcient Uplink Scheduling of Multi-hop WiMAX Mesh Networks, in Proceedings of WiMesh, vol. 6, 2006, pp. 93100. [20] M. Cao, W. Ma, Q. Zhang, X. Wang, and W. Zhu, Modelling and Performance Analysis of the Distributed Scheduler in IEEE 802.16 Mesh Mode, Proceedings of the 6th ACM International Symposium on Mobile Ad Hoc Networking and Computing, pp. 7889, 2005.

[21] N. Bayer, B. Xu, V. Rakocevic, and J. Habermann, Improving the Performance of the Distributed Scheduler in IEEE 802.16 Mesh Networks, Vehicular Technology Conference, 2007. VTC2007-Spring. IEEE 65th, pp. 11931197, 2007. [22] N. Bayer, D. Sivchenko, B. Xu, V. Rakocevic, and J. Habermann, Transmission Timing of Signalling Messages in IEEE 802.16 Based Mesh Networks, Proc. European Wireless, pp. 25, 2006. [23] L. Fuqiang, Z. Zhihui, T. Jian, L. Qing, and L. Zhangxi, Achieving QoS for IEEE 802.16 in Mesh Mode, Proceedings of the 8th International Conference on Computer Science and Informatics, Salt Lake City, Utah, USA, vol. 5, pp. 31023106, 2005. [24] B. Makarevitch, Distributed Scheduling for WiMAX Mesh Network, Personal, Indoor and Mobile Radio Communications, 2006 IEEE 17th International Symposium on, pp. 15, 2006. [25] P. Djukic and S. Valaee, Distributed Link Scheduling for TDMA Mesh Networks, in Communications, 2007. ICC07. IEEE International Conference on, 2007, pp. 38233828. [26] N. Abu Ali, A.-E. Taha, H. Hassanein, and H. Mouftah, IEEE 802.16 Mesh Schedulers: Issues and Design Challenges, Network, IEEE, vol. 22, no. 1, pp. 5865, Jan - Feb 2008. [27] M. Kuran, G. Gur, T. Tugcu, and F. Alagoz, Cross-layer RoutingScheduling in IEEE 802.16 Mesh Networks, in Proceedings of the 1st International Conference on MOBILe Wireless MiddleWARE, Operating Systems, and Applications. ICST (Institute for Computer Sciences, Social-Informatics and Telecommunications Engineering) ICST, Brussels, Belgium, 2008. [28] Y. Cao, Z. Liu, and Y. Yang, A Centralized Scheduling Algorithm Based on Multi-Path Routing in WiMAX Mesh Network, in Wireless Communications, Networking and Mobile Computing, 2006. WiCOM 2006. International Conference on, 2006, pp. 14. [29] M. Peng, Y. Wang, and W. Wang, Cross-layer Design for Tree-type Routing and Level-Based Centralized Scheduling in IEEE 802.16 Based Wireless Mesh Networks, Communications, IET, vol. 1, no. 5, pp. 999 1006, 2007. [30] M. Shariat, A. Quddus, S. Ghorashi, and R. Tafazolli, Scheduling as an Important Cross-Layer Operation for Emerging Broadband Wireless Systems, IEEE Communications Surveys & Tutorials, vol. 11, no. 2, pp. 7486, 2009. [31] A. Sayenko, O. Alanen, J. Karhula, and T. H m l inen, Ensuring a aa the QoS Requirements in 802.16 Scheduling, Proceedings of the 9th ACM International Symposium on Modeling Analysis and Simulation of Wireless and Mobile Systems, pp. 108117, 2006. [32] M. Andrews and L. Zhang, Scheduling Algorithms for Multi-Carrier Wireless Data Systems, Proceedings of the 13th Annual ACM International Conference on Mobile computing and Networking, pp. 314, 2007. [33] S. Redana and M. Lott, Performance Analysis of IEEE 802.16 a in Mesh Operation Mode, Proc. of the 13 thIST SUMMIT, Lyon, France, June, 2004. [34] K. Lu, Y. Qian, H. Chen, and S. Fu, WiMAX Networks: from Access to Service Platform, Network, IEEE, vol. 22, no. 3, pp. 3845, 2008. [35] M. Ahmed, Call Admission Control in Wireless Networks: a Comprehensive Survey, IEEE Communications Surveys & Tutorials, vol. 7, no. 1, pp. 4968, 2005. [36] L. Hanzo-II and R. Tafazolli, A Survey of QoS Routing Solutions for Mobile Ad Hoc Networks, IEEE Communications Surveys & Tutorials, vol. 9, no. 2, pp. 5070, 2007. [37] J. Soldatos, E. Vayias, and G. Kormentzas, On the Building Blocks of Quality of Service in Heterogeneous IP Networks, IEEE Communications Surveys & Tutorials, vol. 7, no. 1, pp. 6988, 2005. [38] J. Chen, C. Wang, F. Chee-Da Tsai, C. Chang, S. Liu, J. Guo, W. Lien, J. Sum, and C. Hung, The Design and Implementation of WiMAX Module for ns-2 Simulator, ACM International Conference Proceeding Series; Vol. 202, 2006. [39] J. Freitag and N. da Fonseca, WiMAX Module for the ns-2 Simulator, Personal, Indoor and Mobile Radio Communications, 2007. PIMRC 2007. IEEE 18th International Symposium on, pp. 16, 2007. [40] NIST, The Network Simulator NS2 NIST Add-on IEEE 802.16 Model (MAC+PHY), 2007. [41] C. N. G. at the University of Pisa and B. W. N. L. at Georgia Institute of Technology, ns2 Contibuted Code: IEEE 802.16 Wireless Mesh Networks in ns-2, Online. Accessed from http://nsnam.isi.edu/nsnam/index.php/Contributed Code. [42] A. Belghith and L. Nuaymi, Scheduling Algorithms for WiMAX, seminar Presentation (2007), Available at www.rennes.enstbretagne.fr/ bertran/ader/seminaire 2007 10 25.pdf. g

KAS et al.: A SURVEY ON SCHEDULING IN IEEE 802.16 MESH MODE

221

Miray Kas received her B.S. and M.S degrees from the Department of Computer Engineering, Bilkent University, Ankara, Turkey in 2007 and 2009, respectively. She is currently a Ph.D. student in the Electrical and Computer Engineering Department of Carnegie Mellon University. Her current research interests include computer networks and wireless ad hoc/mesh networks.

Ibrahim Korpeoglu received his Ph.D. and M.S. degrees from University of Maryland at College Park, both in Computer Science. He is currently an assistant professor in the Computer Engineering Department of Bilkent University, Ankara, Turkey. Prior to joining Bilkent University, he worked in Ericsson, IBM T.J. Watson Research Center, Bell Labs, and Telcordia Technologies, in USA. He has served on the program committees of several conferences and published numerous papers in the area of computer networking. His research interests include computer networks, wireless ad hoc and sensor networks, wireless mesh networks, distributed systems, and P2P networks.

Burcu Yargicoglu received her B.S. degree in the Department of Computer Science from Bilkent University, Turkey in 2007. She is currently a member of the Bilkent Networking and Research Group as an M.S. candidate at Bilkent University. Her research interests are in the area of wireless networking with a focus on multicast protocols in ad hoc and sensor networks.

Ezhan Karasan received B.S. degree from Middle East Technical University, Ankara, Turkey, M.S. degree from Bilkent University, Ankara, Turkey, and Ph.D. degree from Rutgers University, Piscataway, New Jersey, USA, all in electrical engineering, in 1987, 1990, and 1995, respectively. During 19951996, he was a post-doctorate researcher at Bell Labs, Holmdel, New Jersey, USA. From 1996 to 1998, he was a Senior Technical Staff Member in the Lightwave Networks Research Department at AT&T Labs-Research, Red Bank, New Jersey, USA. He has been with the Department of Electrical and Electronics Engineering at Bilkent University since 1998, where he is currently an associate professor. Dr. Karasan is a member of the Editorial Board of Optical Switching and Networking journal. He is the recipient of 2004 Young Scientist Award from Turkish Scientic and Technical Research Council (TUBITAK), 2005 Young Scientist Award from Mustafa Parlar Foundation and Career Grant from TUBITAK in 2004. Dr. Karasan received a fellowship from NATO Science Scholarship Program for overseas studies in 1991-94. His current research interests are in the application of optimization and performance analysis tools for the design, engineering and analysis of optical networks and wireless ad hoc/mesh/sensor networks.