Study on multi-channel mesh deterministic access for wireless mesh LAN

Abstract

IEEE802.11s draft proposes a new medium access control (MAC) function-mesh deterministic access (MDA), which is mainly used for single-channel wireless mesh local area network (LAN). In single-channel environment, collisions between control packets and data packets may occur very often. In order to provide higher performance and network capacity for wireless mesh LAN, this article develops an algorithm for MDA to work well on multi-channel wireless mesh LAN. To reduce the hardware requirements in design, a mesh point (MP) only equips single transceiver to support multi-channel environment. To completely avoid the collision between control packets and data packets, the interval of the meshed delivery traffic indication message is first divided into contention period and data transmission period. We newly define a neighbor MP status table for MPs to support multi-channel environment. The mechanism of reserving MDA opportunity (MDAOP) adopts the four-way-handshaking mode to reduce hidden node problem; we propose channel load first random fit and multi-channel best fit mechanisms to select MDAOP. We also propose a multi-channel MDA (MMDA) algorithm to improve the overall performance of wireless mesh LAN in multi-channel environment. The theoretical analysis gives the upper limit of the throughput for MMDA. The simulation experiments clearly show the results in multi-channel wireless mesh LAN environment that MMDA performs better than the enhanced distributed channel access in throughput, average waiting time, and packet drop ratio both in the saturated and non-saturated mode.[PUBLICATION ABSTRACT]

Lee et al. EURASIP Journal on Wireless Communications and Networking 2012, 2012:313

http://jwcn.eurasipjournals.com/content/2012/1/313

RESEARCH Open Access

Study on multi-channel mesh deterministic access for wireless mesh LAN

Bih-Hwang Lee1*, Hung-Chi Chien1 and Jhih-Ming Chen2

Abstract

IEEE802.11s draft proposes a new medium access control (MAC) function-mesh deterministic access (MDA), which is mainly used for single-channel wireless mesh local area network (LAN). In single-channel environment, collisions between control packets and data packets may occur very often. In order to provide higher performance and network capacity for wireless mesh LAN, this article develops an algorithm for MDA to work well on multi-channel wireless mesh LAN. To reduce the hardware requirements in design, a mesh point (MP) only equips single transceiver to support multi-channel environment. To completely avoid the collision between control packets and data packets, the interval of the meshed delivery traffic indication message is first divided into contention period and data transmission period. We newly define a neighbor MP status table for MPs to support multi-channel environment. The mechanism of reserving MDA opportunity (MDAOP) adopts the four-way-handshaking mode to reduce hidden node problem; we propose channel load first random fit and multi-channel best fit mechanisms to select MDAOP. We also propose a multi-channel MDA (MMDA) algorithm to improve the overall performance of wireless mesh LAN in multi-channel environment. The theoretical analysis gives the upper limit of the throughput for MMDA. The simulation experiments clearly show the results in multi-channel wireless mesh LAN environment that MMDA performs better than the enhanced distributed channel access in throughput, average waiting time, and packet drop ratio both in the saturated and non-saturated mode.

Keywords: IEEE802.11s, medium access control (MAC), mesh deterministic access (MDA), wireless mesh LAN

Introduction

With the popularity of wireless local area network (LAN) , it is inevitable to increase the network coverage.As outdoor wiring is not easy, the multi-hop technology of wireless mesh network becomes more important.IEEE802.11s working group aims to build the wireless mesh network standard. IEEE802.11s draft [1] provides a distributed network environment, so that each node can do self-configuration with the surrounding environment and does not need a service provider. In IEEE802.11s draft, the medium access control (MAC) protocol has great influence for wireless LAN performance [2] and it follows the enhanced distributed channel access (EDCA) of the original IEEE802.11e [3], containing congestion control [4], power saving [5], synchronization [6,7], and beacon collision avoidance [8]. In addition, IEEE802.11s

draft itself also defines a new MAC function-mesh deterministic access (MDA) to improve the performance of wireless mesh LAN.

In the recent IEEE802.11s researches, most literatures focus on the routing and gateway selection. In the routing area, IEEE802.11s draft proposes a hybrid wireless mesh protocol to provide on-demand and proactive routing modes [9-11]. The VoIP performances of several different routing mechanisms in wireless mesh LANs are compared [12]. Some routing methods have also been proposed, like the multi-metric ad-hoc on-demand distance vector routing methods [13], the mechanism of supporting mobility path management [14], the combined routing and traffic shaping decisions to enhance the efficiency of the distributed coordination function (DCF) [15]. Neishaboori and Kesidis [16] use the link/ load-sensitive metric for routing, while Lee et al. [17] propose a new routing protocol to select high throughput paths based on channel diversity information and reduce the broadcast overhead of control messages. In the

* Correspondence: mailto:[email protected]

Web End [email protected]

1National Taiwan University of Science and Technology, 43, Keelung Rd., Section 4, Taipei 106, TaiwanFull list of author information is available at the end of the article

2012 Lee et al.; licensee Springer. This is an Open Access article distributed under the terms of the Creative Commons

Attribution License (http://creativecommons.org/licenses/by/2.0

Web End =http://creativecommons.org/licenses/by/2.0), which permits unrestricted use, distribution, and reproduction

in any medium, provided the original work is properly cited.

Lee et al. EURASIP Journal on Wireless Communications and Networking 2012, 2012:313 Page 2 of 10

http://jwcn.eurasipjournals.com/content/2012/1/313

gateway selection, a gateway selection mechanism is proposed to reduce the occurrence of broadcast loop by connecting the external network [18], while Ashraf et al.[19] combine the gateway load, route interference, and route quality as the basis for selecting the gateway.

According to the studies [20,21], using multi-channel architecture is more effective than single-channel architecture to enhance performance and reduce collision probability in IEEE802.11 network, but the researches for the IEEE802.11s MAC enhancement are relatively fewer and mainly discuss on the single-channel MAC protocol design. For example, in order to improve the utilization of transmission media, Nandiraju et. al. [22] propose a queue management scheme for multi-hop networks to increase the fairness of multi-hop flows using available buffer. Ranjitkar and Ko [23] propose an aggressive block acknowledge (ACK) scheme to improve the performance of 802.11s mesh network. Vishnevsky et al. [24] make beacons responsible to support MDA for delay-sensitive multimedia applications. Based on MDA, Chen and Emeott [25] develop a scheduled mesh access (SMA) mechanism, which has better anti-interference ability than EDCA. Finally, this article proposes a multi-channel single-transceiver MAC protocol called multi-channel MDA (MMDA) algorithm to further enhance the overall performance of wireless mesh LAN.

This article is organized as follows. The next section is to describe the proposed MMDA algorithm. MMDA analysis in throughput section describes the MMDA throughput analysis and Simulation experiments section shows the simulation results. Finally, the article ends with some conclusions.

Description of the proposed MMDA algorithmIn the original MDA, a mesh delivery traffic indication message (DTIM) interval is defined between two consecutive beacon frames. According to IEEE802.11s draft, the slot size of mesh DTIM interval is set to 32 s, in which a mesh point (MP) can reserve MDA opportunity (MDAOP) to transmit data. An MDAOP can be used by MP periodically until an MP finishes transmission and releases it. MDA is established by using two control packets: MDA Setup Request and MDA Setup Reply.

Figure 1 shows the operation of MDA mechanism. Before the source MP transmits data, it sends an MDA Setup Request packet to the destination MP for requesting MDAOP setup. The destination MP will reply an MDA Setup Reply packet to the source MP if it can satisfy the request of MDAOP setup, i.e., MDA mechanism is completed and the source MP can periodically use MDAOP to transmit data. However, in IEEE802.11s draft, not every MP in wireless mesh LAN supports MDA mechanism.

Mesh DTIM interval architectureIn MMDA algorithm, we further split mesh DTIM interval into contention period (CP) and data transmission period (DTP) as shown in Figure 2. In CP, MPs use contention mechanism for reserving MDAOP, and DTP lets the successful MP to establish MDAOP at the selected channel to transmit data, which is to make sure that control packets and data packets can be transmitted in different intervals and avoid the collisions between them. Because MMDA algorithm allows an MP only equips a single transceiver in wireless mesh LAN, only a channel(i.e., CH1) is listened by all MPs in CP; then MPs know the channel information in DTP, but CH1 can be used to transmit data in DTP. The maximum size of an MDAOP to be reserved in DTP is 4096 s (or 128 slots), which can be used by MP periodically at the same location of each DTP in the following mesh DTIM interval.

In order to make MPs achieve timing synchronization in wireless mesh LAN, we use the IEEE802.11 ad-hoc timing synchronization mechanism, because MMDA algorithm uses the new defined mesh DTIM interval architecture. An MP sends beacon in accordance with the principles of DCF at the beginning of each beacon interval; the other MPs will cease sending beacon if any MP sends beacon successfully; then the MPs will take the timestamp value in beacon. This article also requires that each MP must build a neighbor MP status table (NMST) to make sure that MPs know their neighbor MPs status and the channel state information, including MP ID (identification), the channel ID currently used by MP, offset from MDAOPs starting position to the beginning of subinterval, duration of MDAOP, periodicity (i.e., the number of MDAOPs in DTP). For

Mesh DTIM Inteval MDAOP reserved by MPA

time

Beacon

AIFS

aSlot

aSlot

aSlot

MDA Setup Request

AIFS

MDAOP

MPA

MPB

Busy

WM

AIFS

aSlot

aSlot

MDA Setup Reply

Figure 1 MDA mechanism.

Lee et al. EURASIP Journal on Wireless Communications and Networking 2012, 2012:313 Page 3 of 10

http://jwcn.eurasipjournals.com/content/2012/1/313

Mesh DTIM Interval

Contention Period

Data Transmission Period

CH1 CH2

CHNc

...

...

to be capsulated into the MDA Setup Request packet which will be sent to its target MP. Before MP sends the MDA Setup Request packet in CP, it uses backoff algorithm according to CSMA/CA mechanism defined by IEEE802.11 standard [27]. After waiting for a random time, the source MP sends the MDA Setup Request packet to its target MP successfully.

DurationMDAOP Slot Numbers

MDAOP

Beacon

Slots

Beacon

Figure 2 Mesh DTIM interval architecture of MMDA algorithm.

example, if periodicity is equal to 4, it means that DTP are divided into four subintervals, while the four MDAOPs are located in the same distance from the beginning of these four subintervals. We also need to modify MDAOP reservation element, because the MDAOP reservation element of the original MDA control packet is designed for single-channel environment. Therefore, it is necessary to add a new Channel ID field into MDAOP reservation element to support the operation of multi-channel environment.

Four-way-handshaking mechanism for MMDA algorithm Similarly as the original IEEE802.11 ad-hoc networks, wireless mesh LAN also has hidden node problem [26]. In order to effectively solve this problem, MMDA algorithm uses four-way-handshaking mechanism instead of two-way-handshaking mechanism in the original MDA. In other words, MMDA uses four control packets, including MDA Setup Request, MDA Setup Reply, MDA ACK (acknowledge), and MDA ADV (advertisement), to reserve MDAOP, where MDA ACK and MDA ADV are newly defined in this article. When an MP has data to transmit, it needs to decide the size of MDAOP used in DTP to obtain the required bandwidth shown as Equation (1), where Trans_Data_Size and Channel_Trans_ Rate are the transmitted data size and channel transmission rate, respectively.

Slot NumbersMDAOP

Trans Data Size 32s

Channel Trans Rate

2 2

After the target MP receives the MDA Setup Request packet, it copies the same information (channel ID, offset, duration, and periodicity) to an MDA Setup Reply packet and sends back to its source MP if it can satisfy the requirements of the source MP. When the source MP receives the MDA Setup Reply packet, it waits an additional short inter-frame space (SIFS) time and sends back an MDA ACK packet to the target MP to confirm the MDAOP setup. The neighbor MPs of the source MP update the content of NMST after overhearing the MDA ACK packet. The target MP needs to reply an MDA Adv packet to inform the source MP that the MDAOP setup is successful, when the target MP receives the MDA ACK packet; then the neighbor MPs of the target MP update the content of NMST by overhearing the MDA Adv packet. After finishing the four-way-handshaking mechanism, MDAOP is completely established; then MDAOP can be used to transmit data periodically in DTP. The details of the MMDA four-way-handshaking mechanism can be found in Figure 3. Conversely, the target MP may select another MDAOP (including channel ID, offset, duration, and periodicity) according to its own NMST if it cannot satisfy the requirements of the source MP. The information of new MDAOP will be put into an MDA Setup Reply packet and sends back to its source MP. The source MP sends an MDA ACK packet back to the target MP if it agrees the new MDAOP. Otherwise, the source MP does not send the MDA ACK packet back to the target MP if it disagrees. The target MP knows the setup of the new MDAOP fails if it does not receive the MDA ACK packet within a period of time.

After completing the MMDA four-way-handshaking mechanism, the MDAOP owner just needs to wait an SIFS time to access its own MDAOP, i.e., the MDAOP owner has higher priority to access the MDAOP and avoids the interference from the other MPs. The MDAOP setup may fail if any one of four control packets is collided, damaged, or lost in transmission, i.e., MP needs to restart the MMDA four-way-handshaking mechanism. In addition, the MMDA four-way-handshaking mechanism should be completed before the end of CP, otherwise it fails. An MP may restart to reserve MDAOP until the next CP of the mesh DTIM interval. This article allows an

1

When an MP establishes MDAOP, it uses two extra slots for guard slots, one in front and another one in back of its own MDAOP, to avoid being affected by the delay or incomplete synchronization of the other MDAOPs; the MDAOP duration can be obtained by Equation (2). Because the source MP can know which duration in every channel currently being used, according to channel ID, offset, duration, and periodicity of each MP in NMST. After the source MP determines MDAOP duration, it can find the suitable location and duration for its own MDAOP and determine its own MDAOPs channel ID, offset, duration, and periodicity

Lee et al. EURASIP Journal on Wireless Communications and Networking 2012, 2012:313 Page 4 of 10

http://jwcn.eurasipjournals.com/content/2012/1/313

MDA Setup Request

MDA

ACK

MDAOP

MDA Setup Reply

MDA

Adv

Data Transmission Period (at selected CH)

MDA control packet sent by source MP MDA control packet sent by destination MP

Figure 3 MMDA four-way-handshaking mechanism.

Contention Period (at CH1)

MP to reserve different MDAOPs to transmit data on the same channel or different channels in DTP, if MP needs more than one MDAOP to meet the transmission request. However, the MDAOPs on different channels cannot be overlapped in time, and the MP should complete the corresponding MMDA four-way-handshaking mechanisms for these MDAOPs. Figure 4 shows an example of multiple MDAOPs used by MPA on different channels in DTP and Table 1 shows the NMST content corresponding to Figure 4.

If an MP wants to send data to a destination MP, the steps of MMDA algorithm can be summarized as follows:

Step1: To check NMST to find available durations to satisfy the required size of MDAOP in every channel. Step2: To select the position of these durations to establish MDAOP.

Step3: To start four-way-handshaking mechanism in CP.

Step4: To start transmission in the MDAOP on the selected channel in DTP after the completion of four-way-handshaking mechanism.

Step5: To use the established MDAOP to periodically send data to the destination MP.

MDAOP selection mechanism for MMDA algorithmAn MP is called non-MDA-MP (NMP) if it does not support MDA mechanism; conversely an MP is called MMP if it supports MDA mechanism. An NMP may occupy other MPs MDAOP, because it arbitrarily selects duration on the channel and does not know the distribution of MDAOPs on the channel. An MMP must wait

until NMP finishing transmission; therefore, an MP can only transmit data in the remaining MDAOP duration, which degrades the throughput of MP. Furthermore, the MPs MDAOP may fully be occupied by NMP in the worst case and make the MP be unable to transmit any data in its own MDAOP. In order to avoid the aforementioned situation, NMP also needs NMST and listens the control packets on CH1 in CP, so NMP knows the distribution of MDAOPs and obtains the channel state information. However, NMP still has to use the proposed four-way-handshaking mechanism to obtain the time slots on CH1 in CP, and then NMP can use the time slots to transmit data in DTP.

By using NMST, NMP can avoid selecting other MMPs MDAOP, but MMP still records the information of the received NMPs control packets into its NMST, including NMPs channel ID, offset, and duration, but the MDA-support field is marked as 0, where duration here means the slot number used for NMP to transmit data. The information will be removed from NMST after the end of mesh DTIM interval, which means NMP has released the time slots.

When a source MMP wants to create MDAOP to send data to its target MMP, it first gets the channel state information according to its own NMST and avoids selecting the MDAOPs used by other MPs. Different MDAOP selection mechanism may affect the performance of wireless mesh LAN. Cicconetti et al. [28] propose two MDAOP selection mechanism: random fit and best fit, while these two mechanisms only apply to single-channel network structure but not multi-channel network structure. We want to improve these two mechanisms to work on multi-channel wireless mesh LAN; therefore, MMDA algorithm also have two MDAOP selection mechanisms: channel load first random fit (CLFRF) and multi-channel best fit (MCBF).

CH 4

CH 5

10 20 30 40 50 60 70 80 90 100 110 120

Table 1 NMST records the corresponding information of MDAOPs in Figure 4

MP ID Channel ID Offset Duration Periodicity MDA-support MPA 4 10 20 1 1

MPA 5 40 20 1 1 MPA 4 80 30 1 1

10 20 30 40 50 60 70 80 90 100 110 120

MDAOPs used by MPA

Figure 4 MDAOPs used by MPA on different channels in DTP.

Lee et al. EURASIP Journal on Wireless Communications and Networking 2012, 2012:313 Page 5 of 10

http://jwcn.eurasipjournals.com/content/2012/1/313

CLFRF mechanismThe CLFRF mechanism is to randomly select duration from the lightest loading channel for MDAOP reservation, which has the advantage of simple and no more complex operation. The main purpose of CLFRF is to balance the channel load among all channels and avoid some channels always at overload situation to degrade throughput. First MP can obtain a channel having the lightest loading (e.g., channel r) according to its own NMST in multi-channel wireless mesh LAN. Let x be the size of MDAOP and Arx be the subset of free locations large enough to contain an MDAOP of duration x on channel r, as shown in Equation (3), where di, oi means the ith free location that di is the duration of contiguous slots and oi is the offset from this locations starting position to the beginning of subinterval. Then MP randomly selects the location drnd,

ornd among this subset to establish MDAOP, shown in Equation (4).

Arjx di; oiArjdix

f g 3 drnd; ornd random di; oiArjx

f g 4

MCBF mechanismThe goal of the MCBF mechanism is to find the best fit location from all channels to build the requested MDAOP, i.e., MCBF is to select the minimum duration from these durations, hence the advantage of MCBF is to minimize the remaining space after building MDAOP and to avoid causing a large fragmentation. First MMP finds out the subset Ac|x having free locations large enough to contain an MDAOP of duration x on channel c, shown in Equation (5), then it finds the minimum free location of each channel to meet the requested MDAOP. Let us denote dbestc; obestc be the minimum free location

on channel c to contain an MDAOP of duration x. Then we can get the minimum free locations for all channels, respectively, from CH1 to CHNc. Finally, MP selects the smallest duration among these minimum free locations, where dbest, obest is the best fit location for MDAOP,

shown in Equation (6).

dbestc; obestc arg min

di;oiAcjx

di x

f g 5

dbest; obest min dbest1; obest1

h i; dbest2; obest2

h i; . . . ;

f

dbestNc; obestNc

6

MDAOP teardown and relocation mechanisms for MMDA algorithmThe source MMP must release the occupied MDAOP when it completes transmitting data. Before sending teardown packet, the source MMP will enter the backoff

mechanism at the beginning of CP. After backoff mechanism finished, the source MMP sends a teardown packet to the destination MMP for releasing the occupied MDAOP. The neighbor MMPs of the source MMP will update NMST and release the occupied time slots of the MDAOP. After receiving the tear-down packet, the destination MP needs to forward it to its neighbor MMPs to release the occupied time slots of the MDAOP as well. Because the original tear-down packet is designed for single-channel environment, it is not applied to our MMDA algorithm. Therefore, we add the new Channel ID field into the format of the teardown packet to support the operation of multi-channel environment.

When an MMP wants to establish MDAOP, it may find according to NMST that all of the remaining durations on each channel cannot meet the MDAOP size. However, after checking NMST, we will find that some channels total remaining time slots can meet the MDAOP, which is caused by serious fragmentation on every channel. To avoid the waste of channel space, we use MDAOP relocation mechanism to deal with. However, to avoid too complex relocation action, resulting in too many MDAOPs to be moved, we hope to move only one MDAOP to solve this problem instead.

First MP will choose the lightest load channel according to NMST; MP knows the distribution of MDAOPs on the channel, and further finds out the MDAOP having enough front and back time slots to meet the MPs own MDAOP size. MP will send an MDAOP relocation request packet to the owner of the MDAOP in the next CP of mesh DTIM interval, if the MDAOP meet the requirements. The requested MP will reply an MDAOP relocation reply packet if it can perform the MDAOP relocation; otherwise it will reply an MDAOP relocation reject packet if it cannot perform the MDAOP relocation. After finishing the MDAOP relocation, MP may have the sufficient number of time slots to establish MDAOP.

MP will find the second lightest load channel and repeat the above steps, if it cannot find the MDAOP to satisfied MDAOP relocation request on the lightest channel. The MDAOP relocation mechanism fails if there is no MDAOP to meet MDAOP relocation request on all channels. Next we explain it by using an example of a two-channel network environment that the distributions of MDAOPs on CH1 and CH2 are shown as

Figure 5, and the numbers on channels represent the number of free time slots. Let us suppose that MPD needs to use 60 time slots of its MDAOP. From Figure 5 we can find MDAOP2 used by MPB on CH1 has the total of 70 slots in front and back of it i.e., 30 + 40 = 70 slots, which can meet the needs of MPD. MPD will send an MDAOP relocation request packet

Lee et al. EURASIP Journal on Wireless Communications and Networking 2012, 2012:313 Page 6 of 10

http://jwcn.eurasipjournals.com/content/2012/1/313

MDAOP1 MDAOP2 MDAOP3

MDAOP4 MDAOP5 MDAOP6

MDAOPs used by MPA

MDAOPs used by MPB

MDAOPs used by MPC

CH 1

CH 2

10 10 20

30 40

Data Transmission Period Figure 5 The distribution of MDAOPs on CH1 and CH2 in DTP.

to MPB in the next CP of mesh DTIM interval. MPB will first check whether it can do this relocation or not (including the forward shift and backward shift) according to its own NMST. If MPB agrees on this relocation, it asks its partner MP (e.g., MPE) which is using the same MDAOP with MPB. If MPE also agreed, MPB will send MDAOP relocation reply packet back to MPD, then MPD can use the space to establish MDAOP after relocation. If MPB or MPE cannot perform MDAOP relocation, MPB will reply an MDAOP relocation reject packet to MPD, which means that MPDs MDAOP relocation request is rejected.

MMDA analysis in throughputIn this section, we analyze the proposed MMDA algorithm based on the saturated contention in CP. To simplify the analysis, we only consider the two-hop wireless mesh LAN environment. We assume that there are totally n MPs operated in CP with the saturation mode binary exponential backoff; W0 is the initial contention window; and pc is collision probability caused by two or more MPs transmissions at the same time. The transmission probability pt of MP can be obtained by Equation (7) [29], where MP contends with each other until successful transmission in CP without limiting the maximum backoff stage. Similarly, pt can also be obtained by

Equation (8).

pt

2 1 2pc

W0 1 pc

1 2pc

7

pic n

pji n

psucc n

; for i

0; 1; 2 . . . and j 0; 1; 2 12

I n X

1 i0

1=n 1 8 We can easily obtain the unique solutions of pt and pc, respectively, by solving Equations (7) and (8), if n and W0 are given. In addition, pt(n) and pc(n) can be considered as the functions of n for pt and pc, respectively, by assuming W0 is a fixed system parameter. Therefore, the probabilities of successful transmission and idle channel can also be considered as a function of n and expressed by Equations (9) and (10), respectively. Similarly, pc(n) is shown in Equation (11). In addition, we will consider the

other parameters as the functions of n later in this article.

psucc n npt n

1 pt n

n 1 9

pi n 1 pt n

n 10

pc n 1 pi n

psucc n

11 According to the content of NMST, MP knows that the durations will be used in DTP and avoid selecting these durations; then MP can reserve MDAOP by completing MMDA four-way-handshaking mechanism. Let us denote Tcp to be the duration of CP, which obviously affects the number of successful contentions in CP. Let us also denote Tcp_c to be the critical duration of CP,

which is the minimum duration of CP for MPs to successfully reserve all available MDAOPs. Let us assume that an MP will experience i times of collision and j empty slot times before successfully reserving an MDAOP in CP with n MPs to contend, whose joint probability mass function, Pss(i, j, n), can be obtained by

Equation (12), where I and J are the random variables that an MP will experience i times of collision and j empty slots before successfully reserving an MDAOP in CP, respectively. Furthermore, the means of I and J can be expressed as the functions of n and obtained by Equations (13) and (14), respectively.

pss i; j; n p I i; J j

i j

j

i X

1 j0

pt 1 1 pc

pss i; j; n 13

J n X

1 j0

j X

1 i0

pss i; j; n 14

Let us denote Ts and Tc to be the durations of each successful MMDA four-way-handshaking contention and collision shown as Equations (15) and (16), respectively, where TMDASRQ, TMDASRP, TMDAACK, TMDAADV,

Lee et al. EURASIP Journal on Wireless Communications and Networking 2012, 2012:313 Page 7 of 10

http://jwcn.eurasipjournals.com/content/2012/1/313

TDIFS, and TSIFS are the durations of MDA Setup Re

quest, MDA Setup Reply, MDA Acknowledge, MDA Advertisement, DIFS, and SIFS, respectively. Let us define Tr(n) as the average time to reserve an MDAOP for an

MP in CP, which can be obtained by Equation (17), where Ti is a slot time that should be long enough to access the channel state information. Let us denote TDTIM

and TDTP to be the durations of mesh DTIM interval and DTP, respectively, where TDTP can be obtained by Equation (18).

Ts T

MDASRQ

Table 2 Simulation parametersParameters Values Number of MPs 32

Slot time 32 s MP transmission range 60 m Channel capacity 1 Mbps dot11MeshRetryTimeout 500 ms dot11MeshMaxRetries 6 Simulation time 150 s

T

MDASRP

T

MDAACK

T

MDAADV

TDIFS 3TSIFS 15 Tc T

MDASRQ

TDIFS 16

Tr n

I n Tc

J n Ti Ts 17

TDTP TDTIM Tcp 18

Let us denote Na to be the available MDAOPs provided for MPs to reserve in DTP shown in Equation(19), where Nc, B, D, and L are the number of channels in wireless mesh LAN, Each channels bandwidth, MDAOP duration, and the average interval between two MDAOPs, respectively. Let us define Nmin as the

minimum value of n and Na; then, the critical duration of CP Tcp_c(n) can be obtained by Equation (20).

Hence, the available MDAOPs will be completely reserved by MPs within CP, if Tcp is longer than Tcp_c.

Let us define Tm as the mth sub-critical duration of CP that m MPs can successfully reserve MDAOPs, which can be obtained by Equation (21). We define G (n) as the number of MPs that can successfully reserve MDAOPs in a CP, which can be obtained by Equation(22). Let us denote S(n) to be the throughput of MPs, which can be obtained by Equation (23). Finally, the average throughput of each MP, s(n), can be obtained by Equation (24).

Na

TDTP B D L

Nc 19

Tcp c n X

Nmin

x0

100

MMDA(Analysis)

MMDA(MCBF)

EDCA

MMDA(CLFRF)

Tr n x

20

Tm n X

m 1 x0

80

60

Tr n x

for 1 m N

min

21

AverageThroughput(kbps)

40

G n

min n; m

TcpTm; Tm1for m

0; 1 . . .; N

20

min

1 22

S n

G n

D

TDTIM 23

s n

0

2 3 4

Number of Channels

S n

n 24

Simulation experimentsThis section performs the simulation experiments. We use C# to design simulation program, and consider wireless mesh LAN topology with 32 MPs in a random style. We also assume that all MPs are fixed and do not consider propagation delay and background noise. The other simulation parameters are shown in Table 2. We consider both saturated and non-saturated modes, and the packet arrival distribution of non-saturated mode is Poisson distribution. In the constant bit rate (CBR) traffic class, the packet size is assumed to be 512 bytes. The variable bit rate (VBR) traffic class is exponentially distributed, we assume the average packet size is 256 bytes, the maximum and minimum packet sizes are 512 and 64 bytes, respectively. We will compare the performances of MMDA using CLFRF mechanism, known as MMDA (CLFRF); MMDA using MCBF mechanism, known as MMDA (MCBF) and EDCA.

Two-hop scenarioFirst, we consider that the number of hops is limited to two in wireless mesh LAN for CBR traffic at the saturated mode. We assume that the mesh DTIM interval length, the length of CP, and MDAOP duration are 30 ms, 6 ms, and 128 slots, respectively. In Figure 6, the MMDA (analysis) curve shows the upper limit of the

Figure 6 Average throughput of two-hop scenario in the

saturated mode.

Lee et al. EURASIP Journal on Wireless Communications and Networking 2012, 2012:313 Page 8 of 10

http://jwcn.eurasipjournals.com/content/2012/1/313

300

300

AverageThroughput(kbps)

AverageThroughput(kbps)

MMDA(MCBF)

EDCA

MMDA(CLFRF)

MMDA(CLFRF,2ch)

MMDA(CLFRF,4ch)

MMDA(MCBF,2ch)

MMDA(MCBF,4ch)

EDCA(2ch)

EDCA(4ch)

250

250

200

200

150

100

150

50

100

0 50 100 150 200 250 300 350 400

2 3 4

Number of Channels

Traffic Load (kbps)

Figure 7 Average throughput for CBR traffic in the saturated

mode.

Figure 9 Average throughput for CBR traffic in the

non-saturated mode.

theoretical analysis; we can find the curves of MMDA (MCBF) and MMDA (analysis) are very close. MMDA (MCBF) can approach the theoretical upper limit, because it has smaller fragmentation; conversely due to the larger fragmentation, MMDA (CLFRF) performs worse than MMDA (MCBF). When using EDCA, the source MP and the destination MP have to coordinate which channel to use, so the source MP must contend with the other MPs in CP. In addition, the source MP needs to reserve TXOP (transmission opportunity) by contention mechanism in DTP, which increases network overhead and more collisions. Furthermore, TXOP cannot periodically be used in every mesh DTIM interval, so it also increases the number of contentions and causes EDCA having poor performance.

Multi-hop scenarioIn this section, we consider the multi-hop wireless mesh LAN in both saturated and non-saturated modes. We randomly place 32 MPs in the square of 300 m 300 m. We assume that the mesh DTIM interval length and CP are 100 and 10 ms, respectively. We allow each MP to

get more than one MDAOP to transmit data in DTP. Performance evaluation includes the average throughput, average waiting time (the time from packet entering the queue to leaving the queue), and packet drop ratio will be investigated. Figures 7 and 8 show the average throughput for CBR and VBR traffics, respectively, in the saturated mode. It is obvious that MMDA (CLFRF) and MMDA (MCBF) perform better than EDCA, because the situation is very similar to the two-hop scenario.

Figures 9, 10, 11, 12, 13, and 14 show the results for the CBR and VBR traffics in the non-saturated mode, and it is obvious that both MMDA (CLFRF) and MMDA (MCBF) perform better than EDCA in average throughput, average waiting time, and packet drop ratio. The poor performance of EDCA is because EDCA needs to contend in both CP and DTP, and then it just can reserve TXOP, which causes more collisions and increases network overhead. Whatever the saturated or non-saturated mode is used, the simulation results show that in CBR traffic mode, the average throughput of MMDA (CLFRF) and MMDA (MCBF) is close, but in VBR traffic

300

300

MMDA(MCBF)

EDCA

MMDA(CLFRF)

MMDA(CLFRF,2ch)

MMDA(CLFRF,4ch)

MMDA(MCBF,2ch)

MMDA(MCBF,4ch)

EDCA(2ch)

EDCA(4ch)

AverageThroughput(kbps)

AverageThroughput(kbps)

250

250

200

200

150

100

150

50

100

0 50 100 150 200 250 300 350 400

2 3 4

Number of Channels

Traffic Load (kbps)

Figure 8 Average throughput for VBR traffic in the saturated

mode.

Figure 10 Average throughput for VBR traffic in the

non-saturated mode.

Lee et al. EURASIP Journal on Wireless Communications and Networking 2012, 2012:313 Page 9 of 10

http://jwcn.eurasipjournals.com/content/2012/1/313

500

MMDA(CLFRF,2ch)

MMDA(CLFRF,4ch)

MMDA(MCBF,2ch)

MMDA(MCBF,4ch)

EDCA(2ch)

EDCA(4ch)

80%

MMDA(CLFRF,2ch)

MMDA(CLFRF,4ch)

MMDA(MCBF,2ch)

MMDA(MCBF,4ch)

EDCA(2ch)

EDCA(4ch)

Average Waiting Time (ms)

450 400 350 300 250 200 150 100

50

Packet Drop Ratio

70%

60%

50%

40%

30%

20%

10%

0%

0 50 100 150 200 250 300 350 400

50 100 150 200 250 300 350 400

Traffic Load (kbps)

Traffic Load (kbps)

Figure 11 Average waiting time for CBR traffic in the

non-saturated mode.

Figure 13 Packet drop ratio for CBR traffic in the non-saturated

mode.

mode the average throughput of MMDA (MCBF) is better than MMDA (CLFRF). This is because the data packet size in VBR traffic mode is variable and MMDA (CLFRF) uses random mechanism to select the location of MDAOP, it will causes that the smaller MDAOP occupies the larger free location and results in the waste problem of channel resource.

In Figures 11 and 12, the average waiting times of MMDA (CLFRF), MMDA (MCBF), and EDCA increase when traffic load increases, because MP suffers more contentions to transmit data when packet arrival rate increases. For MMDA (CLFRF) and MMDA (MCBF), MP needs to wait until the next mesh DTIM interval, if it cannot complete MMDA four-way-handshaking before the end of CP. Therefore, MMDA (CLFRF) and MMDA (MCBF) need to wait for several mesh DTIM intervals to transmit data packets when traffic load increases, which significantly make the average waiting time increase. Figures 13 and 14 show the packet drop ratio also increases, because packets will be dropped for time out or reached the retransmission limit when traffic load increases.

Conclusions

This research makes the MDA of IEEE802.11s draft to work well on multi-channel wireless mesh LAN to provide higher performance and network capacity. MMDA algorithm uses four-way-handshaking mechanism to reduce hidden node problems, and mesh DTIM interval is divided into CP and DTP to completely avoid the collision between control packets and data packets. MMDA algorithm is designed with only single transceiver, so it can reduce the hardware resource requirements and design complexity. NMST helps MP to know the distribution of MDAOPs on each channel and makes MP easily to select an available MDAOP. These two MDAOP selection mechanisms, CLFRF and MCBF, make MP to select the location of MDAOP more effectively. Because of these designs, MMDA algorithm works well on multi-channel wireless mesh LAN. The theoretical analysis gives the upper limit of the throughput for MMDA. The simulation experiments clearly show the results in multi-channel wireless mesh LAN environment that the throughput of MMDA is better than EDCA both in saturated and non-saturated modes. In addition, MMDA

500

80%

MMDA(CLFRF,2ch)

MMDA(CLFRF,4ch)

MMDA(MCBF,2ch)

MMDA(MCBF,4ch)

EDCA(2ch)

EDCA(4ch)

MMDA(CLFRF,2ch)

MMDA(CLFRF,4ch)

MMDA(MCBF,2ch)

MMDA(MCBF,4ch)

EDCA(2ch)

EDCA(4ch)

Average Waiting Time (ms)

450 400 350 300 250 200 150 100

50

Packet Drop Ratio

70%

60%

50%

40%

30%

20%

10%

0%

0 50 100 150 200 250 300 350 400

50 100 150 200 250 300 350 400

Traffic Load (kbps)

Traffic Load (kbps)

Figure 12 Average waiting time for VBR traffic in the

non-saturated mode.

Figure 14 Packet drop ratio for VBR traffic in the non-saturated

mode.

Lee et al. EURASIP Journal on Wireless Communications and Networking 2012, 2012:313 Page 10 of 10

http://jwcn.eurasipjournals.com/content/2012/1/313

also has the lower average waiting time and packet drop ratio than EDCA. Obviously, the proposed MMDA algorithm can effectively improve overall performance of multi-channel wireless mesh LAN.

Competing interestsThe authors declare that they have no competing interests.

AcknowledgmentsThis study was supported in part by the National Science Council (NSC) of Taiwan under Grant no. NSC 99-2221-E-011-119.

Author details

1National Taiwan University of Science and Technology, 43, Keelung Rd., Section 4, Taipei 106, Taiwan. 2Ling Tung University, 1, Ling Tung Rd, Taichung 408, Taiwan.

Received: 12 June 2012 Accepted: 25 September 2012 Published: 16 October 2012

References1. IEEE std, 802.11s/d2.02 Part 11, Wireless LAN Medium Access Control (MAC) and Physical Layer (PHY) Specifications Amendment 10: mesh networking (2008)

2. G.R. Hiertz, S. Max, Y. Zang, T. Junge, D. Denteneer, IEEE 802.11s MAC fundamentals, in Proceedings of IEEE International Conference on Mobile Ad-hoc and Sensor Systems (MASS 2007), ed. by, 2007, pp. 18

3. IEEE std. 802.11e-2005, Wireless LAN Medium Access Control (MAC) and Physical Layer (PHY) Specifications Amendment 8: Medium Access Control (MAC) Quality of Service Enhancements (2005)

4. H. Aoki, S. Takeda, K. Yagyu, A. Yamada, IEEE 802.11s wireless LAN mesh network technology. NTT DoCoMo Tech. J. 8(2), 1321 (2006)

5. G.R. Hiertz, S. Max, Z. Rui, D. Denteneer, L. Berlemann, Principles of IEEE 802.11s, in Proceedings of 16th International Conference on Computer Communications and Networks (ICCCN 2007), ed. by (2007), pp. 10021007

6. J. Camp, E. Knightly, The IEEE 802.11s extended service set mesh networking standard. IEEE Commun. Mag. 46(8), 120126 (2008)

7. J.H. Chiang, T. Chiueh, Accurate clock synchronization for IEEE 802.11-based multi-hop wireless networks, in Proceedings of 17th IEEE International Conference on Network Protocols (ICNP 2009), ed. by (2009), pp. 1120

8. M.J. Lee, J. Zheng, Y.B. Ko, D.M. Shrestha, Emerging standards for wireless mesh technology. IEEE Wireless Commun. 13(2), 5663 (2006)

9. K. Yang, J.F. Ma, Z.H. Miao, Hybrid routing protocol for wireless mesh network, in Proceedings of International Conference on Computational Intelligence and Security (CIS '09), ed. by (2009), pp. 547551

10. A.O. Lim, X. Wang, Y. Kado, B. Zhan, A hybrid centralized routing protocol for 802.11s WMNs. Mob. Netw. Appl. J 13(12), 117131 (2008)

11. W.J. Yoon, S.H. Chung, S.J. Lee, Y.S. Lee, An efficient cooperation of on-demand and proactive modes in hybrid wireless mesh protocol, in Proceedings of 33rd IEEE Conference on Local Computer Networks (LCN 2008), ed. by (2008), pp. 5257

12. A. Ksentini, O. Abassi, A comparison of VoIP performance over three routing protocols for IEEE 802.11s-based wireless mesh networks (WLAN Mesh), in Proceedings of 6th ACM International Symposium on Mobility Management and Wireless Access (MOBIWAC08), ed. by (2008), pp. 147150

13. Q. Shen, X. Fang, A multi-metric AODV routing in IEEE 802.11s, in Proceedings of IEEE International Conference on Communication Technology (ICCT 06), ed. by (2006), pp. 14

14. J. Li, J. Yun, K. Cho, K. Han, Path management scheme to support mobile station in wireless mesh networks for U-healthcare applications, in Proceedings of Wireless Telecommunications Symposium (WTS 2009), 2009, pp. 14

15. C. Pepin, U.C. Kozat, S.A. Ramprashad, A joint traffic shaping and routing approach to improve the performance of 802.11 mesh networks, in Proceedings of 4th IEEE International Symposium on Modeling and Optimization in Mobile, Ad-hoc and Wireless Networks, ed. by (2006),pp. 110

16. A. Neishaboori, G. Kesidis, SINR-sensitive routing in wireless 802.11 mesh networks, in Proceedings of 5th IEEE International Conference on Mobile Adhoc and Sensor Systems (MASS 2008), ed. by (2008), pp. 623628

17. S.H. Lee, Y.B. Ko, Y.G. Hong, H.J. Kim, A new MIMC routing protocol compatible with IEEE 802.11s based WLAN mesh networks, in Proceedings of IEEE International Conference on Information Networking (ICOIN2011), ed. by (2011), pp. 126131

18. G. Isabwe, K.S. Kim, A novel approach to WLAN mesh interworking with multiple mesh portals, in Proceedings of 5th IEEE International Conference on Mobile Ad-hoc and Sensor Systems (MASS 2008), ed. by (2008), pp. 641646

19. U. Ashraf, S. Abdellatif, G. Juanole, Gateway selection in backbone wireless mesh networks, in Proceedings of Wireless Communications and Networking Conference (WCNC), ed. by (2009), pp. 19

20. M.A. Marsan, D. Roffinella, Multichannel local area network protocols. IEEE J. on Selected Areas in Commun. 1(5), 885897 (1983)

21. A. Baiocchi, A. Todini, A. Valletta, Why a multichannel protocol can boost IEEE 802.11 performance, in Proceedings of the 7th ACM International Symposium on Modeling, Analysis and Simulation of Wireless and Mobile Systems, ed. by (2004), pp. 143148

22. N.S. Nandiraju, D.S. Nandiraju, D. Cavalcanti, D.P. Agrawal, A novel queue management mechanism for improving performance of multihop flows in IEEE 802.11s based mesh networks, in Proceedings of Performance, Computing, and Communications Conference (IPCCC 2006), ed. by (2006), pp. 162168

23. A. Ranjitkar, Y.B. Ko, Performance enhancement of IEEE 802.11s mesh networks using aggressive block Ack. scheme, in Proceedings of International conference on Information Networking (ICOIN 2008), ed. by (2008), pp. 15

24. V. Vishnevsky, A. Lyakhov, A. Safonov, S. Shpilev, Beaconing for MDA support in IEEE 802.11s mesh networks, in Proceedings of IEEE 18th Symposium on Personal, Indoor and Mobile Radio Communications (PIMRC 2007), ed. by (2007), pp. 15

25. Y. Chen, S. Emeott, Impact of scheduled mesh access on the capacity of wireless mesh links, in Proceedings of Radio and Wireless Symposium (RWS 2009), ed. by (2009), pp. 107110

26. H. Jasani, N. Alaraje, Evaluating the performance of IEEE 802.11 network using RTS/CTS mechanism, in Proceedings of IEEE International Conference on Electro/Information Technology, ed. by (2007), pp. 616621

27. IEEE 802.11 Working Group, Wireless LAN Medium Access Contro1 (MAC) and Physical Layer (PHY) specifications. (1997)

28. C. Cicconetti, L. Lenzini, E. Mingozzi, Scheduling and dynamic relocation for IEEE 802.11s mesh deterministic access, in Proceedings of 5th Annual IEEE Communications Society Conference on Sensor, Mesh and Ad Hoc Communications and Networks (SECON '08), ed. by ( 2008), pp. 1927

29. B.J. Kwak, N.O. Song, L.E. Miller, Performance analysis of exponential backoff. IEEE/ACM Trans. Netw. 13(2), 343355 (2005)

doi:10.1186/1687-1499-2012-313Cite this article as: Lee et al.: Study on multi-channel mesh deterministic access for wireless mesh LAN. EURASIP Journal on Wireless Communications and Networking 2012 2012:313.

Submit your manuscript to a journal and benet from:

7 Convenient online submission7 Rigorous peer review7 Immediate publication on acceptance7 Open access: articles freely available online 7 High visibility within the eld7 Retaining the copyright to your article

Submit your next manuscript at 7 springeropen.com