Printer Friendly

On the relationship between multicast/broadcast throughput and resource utilizations in wireless mesh networks.

1. Introduction

Wireless mesh networks (WMNs) have been recognized as a new class of multihop networks that provide low-cost solutions for broadband wireless applications [1]. A WMN is composed of three types of nodes: gateways, mesh routers, and mesh clients [1, 2]. Gateways enable the integration of various networks, for example, Wi-Fi, Zigbee, WiMAX, and cellular networks. Mesh routers have minimal mobility and form the backbone of the network. They have the functionality of both an access point and a relay node. As a relay node, mesh routers forward the packets from the source node to the destination nodes. However, as an access point, they provide network access for mesh clients within their coverage area. One challenge in WMNs is the degradation of the network's capacity due to the co-channel interference. This problem has motivated the researchers to improve the network's throughput using efficient schemes. An effective approach to mitigate the co-channel interference is to equip the mesh routers with multiple radios tuned to non-overlapping channels. The ability to utilize multiple radios allows the mesh routers to send/receive packets simultaneously on distinct channels and, therefore, increases the bandwidth available to the network [2]. However, due to the limited number of radios and non-overlapping channels, some links interfere with each other and cannot be active at the same time. These resource constraints degrade the performance of Multi-Channel Multi-Radio WMNs (MCMR-WMNs). Thus, a proper resource assignment strategy is required to improve the performance of such networks.

On the other hand, recently, the popularity of multimedia services such as IP-TV, video conference, and distant education, has significantly increased [3-5]. In this regard, the multicast routing provides underlying facilities for the multimedia applications in WMNs. The basic difference between multicast routing in wireless and wired networks is the broadcast nature of the wireless medium that results in a well-known property named wireless broadcast advantage (WBA) [6, 7]. Based on the WBA, a single transmission in a node simultaneously covers multiple neighboring receivers.

Minimizing the number of transmissions improves the utilization of the network resources and subsequently increases the network's throughput. Besides the number of transmissions, the load-balancing problem is another pertinent issue to be considered in MCMR-WMNs. This problem can be discussed from two perspectives: spatial load-balancing and channel load-balancing. From the viewpoint of a specific channel, when a part of the network experiences congestion, the new traffic flows should not be routed through that part. In addition, from the perspective of a specific location, the traffic load must be balanced over all available channels in the network. If the traffic load in the network is balanced, the interference will be decreased, and more resources will be available for accepting the future traffics.

To evaluate the performance of a MCMR-WMN, there are several criteria that often interact with each other. Thus, it is not possible to draw a clear boundary between them. In this regard, different approaches try to improve different aspects of the networks. One difficulty in comparing different schemes is the lack of a standard benchmark. Certainly, having a prior knowledge about the bounds of criteria and their corresponding relationship provides more options for the system administrator to control the parameters of the network.

Taking the above challenges into account, the main goal of this paper is to quantify the throughput in MCMR-WMNs. We focus on the scenario of multicast and broadcast sessions, where each session has a specific bandwidth requirement. On-demand requests arrive dynamically one by one without any prior knowledge of future arrivals. A session will be accepted if a routing tree with sufficient bandwidth on each link can be established. In particular, we provide a formulation to express the network's throughput in terms of the node utilization, the channel utilization, and the number of transmissions. We also discuss how appropriate use of the resources affects the network's throughput.

The rest of the paper is organized as follows. Section 2 surveys the previous related works. The details of the network model are described in Section 3. Section 4 presents a formulation to capture the resource utilizations. In Section 5, we derive analytical expressions for the multicast/broadcast throughput in both small-scale MCMR-WMN and large-scale MCMR-WMN. Section 6 presents the numerical results and the discussion. Finally, some concluding remarks are provided in Section 7.

2. Related Work

In past years, different aspects of MCMR-WMNs have been widely studied for unicast flows. In particular, some works endeavor to heuristically improve the network's performance [2, 8], while others focus on the optimization solutions [9-11]. In this regard, several routing metrics (such as ETX, ETT, WCETT, WCCETT, MIC, iAWARE, and MIND [1, 12]) have been proposed. However, due to the differences between unicast and multicast routing, the designed unicast schemes cannot be efficient for the multicast traffics. In one of the most fundamental researches on the multicast routing, the work in [4] compares the performance of the Minimum Steiner Trees (MSTs) and the Shortest Path Trees (SPTs) in Single-Channel Single-Radio WMNs (SCSR-WMNs). Experimental results in [4] show that SPTs offer a better performance than MSTs. In addition, the implementation difficulty of MSTs is another factor that makes SPTs more favorable in WMNs. However, none of these protocols consider the problems of load-balancing and resource utilization.

Roy et al. [13] study the high-throughput metrics for multicast routing in WMNs. They point out the difference between unicast and multicast routing and show how to adapt the unicast routing metrics for use in multicast flows. They also propose a low-overhead adaptive algorithm to incorporate the link-quality-based metrics to a representative multicast routing protocol.

As mentioned before, the ability to make an appropriate use of the network resources can efficiently increase the throughput in WMNs. In line with this concept, some works aim to minimize the number of transmissions required to deliver one packet from the source to all the destinations [14-16]. The authors in [15] propose a multicast routing metric, named Multi-Channel Minimum Number of Transmissions (MCMNT), that considers the wireless broadcast advantage and the channel diversity to minimize the network bandwidth consumed by the routing tree. MCMNT also tries to minimize the intra-flow interference in the network. Zeng et al. [16] propose two algorithms, named Level Channel Assignment (LCA) and Multi-Channel Multicast (MCM), to minimize the number of forwarding nodes and the total hop-count distances in MCMR-WMNs. These algorithms reduce the intra-flow interference using the heuristic channel assignment strategies. The authors in [16] show that the LCA and the MCM algorithms outperform the single-channel multicast in terms of the throughput and the delay. They also demonstrate that using all the partially overlapping channels instead of only the non-overlapping channels can further diminish the interference in the network.

In [17], Chiu et al. challenge the load-balancing issue in MCMR-WMNs. The basic idea in [17] is that if the traffic on the most-heavily loaded channel is minimized, the traffic load in the network will be balanced. In this way, they first present an integer linear programming formulation to optimally construct the bandwidth-guaranteed broadcast trees. Then, an efficient algorithm is proposed to heuristically improve the call acceptance rate in the network. Reference [18] proposes two load-aware metrics, named "Flow Load Multicast Metric (FLMM)" and "Reliable Flow Load Multicast Metric ([FLMM.sup.R])", for multicast routing in MCMR-WMNs. Although both metrics count the interference and the WBA, the latter case further considers the unreliability of the IEEE 802.11 MAC protocol. FLMMB uses the Packet Delivery Ratio (PDR) of the wireless links and reduces retransmission overheads. In line with this concept, the work in [19] suggests two distributed strategies, named "Multicast Auto-Rate Selection (MARS)" and "MARS-Retransmit (MARS-R)" The MARS scheme uses PDR of the wireless links at various transmission rates. The MARS-R algorithm facilitates the joint use of rate control and link-layer mechanisms (such as acknowledgments and retransmissions) to improve the reliability of high-throughput multicast flows.

During recent years, we have considered the problem of traffic engineering for multicast/broadcast flows in WMNs [3, 7, 20]. The work in [3] studies the special case of broadcasting for the small-scale WMNs. In [7], we present an Interference-Aware Joint Channel and Rate Selection (IAJCRS) algorithm to choose the best transmission rates and the best transmission channels for a given fixed routing tree. However, being bound to a routing tree reduces the freedom to choose the alternative feasible paths. Indeed, using a joint interference-aware routing scheme leads to a better utilization of the network resources. Accordingly, in [20], we propose two cross-layer algorithms, named the "Interference- and Rate-aware Multicast Tree (IRMT)" and the "Interference- and Rate-aware Broadcast Tree (IRBT)." As an advantage, the proposed algorithms jointly address the problems of multicast/broadcast routing tree construction, transmission rate selection, transmission channel selection, and call admission control.

One drawback of the previous works is that they pay less attention to the theoretical analysis of multicast/broadcast flows. Most of the literature tries to propose some heuristically or optimally solutions to improve different aspects of the network. Unlike the previous works, this paper quantifies the multicast and the broadcast throughput in both small-scale MCMR-WMN and large-scale MCMR-WMN. In this regard, we also present a simulation-based discussion to simultaneously study the effects of load-balancing and number of transmissions on the network's throughput.

3. Network Model and Assumptions

We consider a typical MCMR-WMN consisting of n stationary nodes (In this paper, the terms "mesh router" and "node" are used interchangeably for convenience.). Each node x is equipped with [R.sub.x] half-duplex radios tuned to one of the K available non-overlapping channels where no channel switching is allowed. For the sake of efficiency, the radios of a node are tuned to different non-overlapping channels. When a radio of a node transmits or receives the packets on a channel, other radios of the same node are able to communicate at the same time with neighboring nodes on other channels. In this paper, a single-rate framework is assumed for all link-layer transmissions. In addition, we suppose that the radios of the nodes are equipped with omnidirectional antennas characterized by the same transmission range and the same interference range. Node x is directly connected to node y and forms a wireless link, if and only if node y is within the transmission range of node x and they share a common channel. In this regard, we model the network as a directed graph G = (V, E), where V = {[v.sub.1], [v.sub.2],..., [v.sub.n]} is the set of vertices representing n nodes and E denotes the set of communication links. In this work, we consider the traffic model of on-demand multicast/broadcast sessions, where each admitted session creates a unique tree with a specific bandwidth requirement. In this way, we adopt a schedule-based MAC protocol, in which the conflict-free transmission is ensured by assigning the interfering transmitters to either send on different non-overlapping channels or send on the same channel but at different time slots.

4. Problem Formulation

The limited number of radios and the shared nature of wireless medium impose some resource constraints on MCMR-WMNs. In this section, we derive a formulation to capture the utilization of the network resources and to analyze the feasibility of multicast/broadcast session requests.

Definition 1. The capacity of the ith mesh router is defined as C(i) = [R.sub.i][c.sub.0], where [R.sub.i] represents the number of its radios and c0 is the capacity of the channels. In addition, we define the sent and the received traffic loads of the ith mesh router, denoted by [l.sub.s](i) and [l.sub.r](i), respectively, as [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] are the sent and the received traffic loads of the bth radio in the ith mesh router, respectively. Thus, the total traffic load of the ith mesh router is obtained as l(i) = [l.sub.s](i) + [l.sub.r](i), i = 1,..., n.

According to the assumption of the half-duplex radios, each radio can only send or receive on a fixed channel k at any time slot; therefore, it is required that

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (1)

Let [l.sup.j.sub.i] denote the created load by the jth session on the ith mesh router. Thus, the total load of the ith mesh router can be rewritten as [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], where ns is the number of active sessions. In general, each multicast/broadcast tree [T.sup.j] is composed of a set of MAC multicast transmissions on different nodes and channels. The number of transmissions of node i at the jth tree, denoted by [NT.sup.j.sub.i], is given by

[NT.sup.j.sub.i] = [summation over (k [member of] K)] [q.sup.j.sub.i, k], I = 1,...,, n, (2)

where K is the set of K available non-overlapping channels and [q.sup.j.sub.i, k] =1 if node i is a forwarding node on channel k at the jth tree, and [q.sup.j.sub.i, k] = 0 otherwise. In this case, we define the total number of transmissions for the jth tree as

NT([T.sup.j]) = [summation over (i [member of] V)] [NT.sup.j.sub.i]. (3)

In fact, NT([T.sup.j]) shows the number of transmissions required to deliver one packet from the source node to all the destinations at the jth multicast/broadcast tree. Thus, the average number of transmissions per active session is expressed as

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (4)

Since more transmissions take longer time on scheduling frame, minimizing the number of transmissions helps to improve the network's throughput. In a typical multicast/broadcast tree [T.sup.j], there are three kinds of nodes: source node [s.sub.j], forwarding nodes set ([FWD.sup.j]), and leaf nodes set (LFJ). For example, consider the multicast tree shown in Figure 1. Here, the number associated with each link represents the channel assigned to that link. All nodes of tree, except the source node, have one parent. The source node (e.g., node A), as the root of the tree, sends data toward its children. A forwarding node (e.g., nodes B, C, E, F, and I) acts as both parent and child node; as a child node, it receives data from its parent, while in the role of a parent node, it sends the traffic toward its children. A leaf node (e.g., nodes D, K, L, M, N, and P) only plays the role of a child and receives data from its parent. It is clear from Figure 1 that [NT.sup.j.sub.A] = [NT.sup.j.sub.B] = [NT.sup.j.sub.C] = [NT.sup.j.sub.E] = 1, while [NT.sup.j.sub.I] = [NT.sup.j.sub.F] = 2 (i.e., NT([T.sup.j]) = 8).

Since we assume the bandwidth-guaranteed trees with bandwidth requirement [tr.sup.j.sub.s], the created load by the jth session on the ith node can be generally formulated by the role of node and the number of its transmissions as

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (5)

Here, we define the utilization of the ith mesh router, denoted by U(i), as follows:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], (6)

where U(i) indicates the percentage of the ith node's capacity used for routing of [n.sub.s] multicast/broadcast sessions. For this case, the average utilization of the nodes is defined as

[bar.U] = 1/n [n.summation over (i = 1)] U(i), (7)

where n is the total number of nodes in the network.

On the other hand, due to the shared nature of the wireless medium, adjacent transmissions cannot occur simultaneously on the same channel. To formulate this issue, we use the channel utilization concept defined in [17] with minor modifications. For the described MCMR-WMN model, consider a fixed transmission rate of [c.sub.0]. Each MAC multicast transmission in the jth routing tree uses a time fraction of the scheduling frame that is equal to [tr.sup.j.sub.s]/[c.sub.0]. By definition, the utilization of channel k observed by node y ([X.sup.k.sub.y]) is the sum of the time fractions assigned to all nodes within the interference range of node y that are intended to transmit on channel k. Thus, considering [n.sub.s] admitted multicast/broadcast sessions, the utilization of channel k observed by node y is formulated as

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], (8)

where intf(y) denotes the set of interfering nodes located within the interference range of node y. For this case, the channel capacity constraint is given by

[X.sup.k.sub.y] [less than or equal to] 1, [for all]y [member of] V, [for all]k [member of] ch_list(y), (9)

where ch_list(y) indicates the set of assigned channels to the radios of node y. Since the radios of each node are assigned to different non-overlapping channels and no channel switching is allowed, one can show that condition (9) satisfies the described condition in (1). Therefore, the bandwidth-guaranteed multicast/broadcast sessions are feasible and schedulable if all interfering transmissions have a total load less than the normalized channel capacity. Different from the best-effort routing algorithms, quality of service (QoS) routing algorithms must use call admission control mechanisms to protect the QoS requirements of the existing flows [17, 21]. Clearly, it is desired to maximize the number of admitted sessions. In this regard, we define the network's throughput, denoted by [tau], as the sum of the traffic load of all admitted feasible sessions as [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

5. Network's Throughput versus Resource Utilizations in MCMR-WMNs

In this section, we aim to derive analytical relationships for the network's throughput in terms of the node utilizations, the channel utilizations, and the number of transmissions.

Theorem 2. If all sessions have the same traffic load, for example, [tr.sup.j.sub.s] = [T.sub.0], and the capacity of all nodes in the network is identical, for example, [R.sub.i] = R and C(i) = C, the average number of transmissions for the multicast flows is expressed as

[bar.NT] = nC/[n.sub.s][T.sub.0] [bar.U] - [bar.W], (10)

where [n.sub.s] and [bar.U] denote the number of admitted sessions and the average node utilization, respectively. In addition, [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] shows the average number of links in the tree of each session and W1 is the number of links in the jth multicast tree.

Proof. Under the assumption C(i) = C and using (6) and (7), we have

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], (11)

where (a) comes from (5) and the fact that each multicast routing tree includes three kinds of nodes: a source node, forwarding nodes, and leaf nodes. In the above equations, [NT.sup.j.sub.s] is the number of transmissions of source node, and [absolute value of [FWD.sup.j]] and [absolute value of [LF.sup.j]] denote the number of forwarding nodes and leaf nodes at the jth tree, respectively. On the other hand, from the graph theory [22]

[absolute value of [FWD.sup.j]] + [absolute value of [LF.sup.j]] = [W.sup.j]. (12)

Thus, (11) can be simplified as

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (13)

According to (3) and (4) and considering the fact that [NT.sup.j.sub.i] = 0 for i [not member of] {[s.sup.j], [FWD.sup.j]}, we have

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (14)

Thus,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (15)

As a result, [bar.NT] = (nC/[n.sub.s][T.sub.0])[bar.U] - [bar.W].

Corollary 3. For the broadcast case, (12) can be rewritten as [bar.[FWD.sup.j]] + [absolute value of [LF.sup.j]] = n - 1 [22]. Thus,

[bar.NT] = nC/[n.sub.s][T.sub.0] [bar.U] - n + 1. (16)

In the rest of the section, we first present the problem for the small-scale MCMR-WMNs, and then, we extend our work to the case of large-scale MCMR-WMNs. In addition, due to the similarity of equations for the multicast and the broadcast sessions, we follow the problem only for the broadcast sessions.

Small-Scale MCMR-WMNs. In a small-scale MCMR-WMN, we suppose that all nodes are located in the interference range of each other. Thus, the channel utilization observed by any node is identical. For a small-scale MCMR-WMN, we define the utilization of channel k denoted by [X.sup.k] and the average channel utilization [[bar.X].sub.SS] as follows:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], (17)

[[bar.X].sub.SS] = 1/K [K.summation over (k = 1)] [X.sup.k]. (18)

Lemma 4. Under the same conditions as in Theorem 2, the broadcast throughput of a small-scale MCMR-WMN is expressed in terms of the average node utilization and the average channel utilization, as follows:

[tau] = [c.sub.0]/n - 1 (nR[bar.U] - K[[bar.X].sub.SS]). (19)

Proof. Using (17) and averaging the utilization on different channels, we have

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], (20)

where (a) comes from (2)-(4), and the assumption [tr.sup.j.sub.s] = [T.sub.0]. Considering [tau] = [n.sub.s][T.sub.0], C = R[c.sub.0], and replacing [bar.NT] with the result in (16) for broadcast sessions, the throughput t can be expressed as [tau] = ([c.sub.0]/n - 1)(nR[bar.U] - K[[bar.X].sub.SS]).

Large-Scale MCMR-WMNs. Now, we extend the result of Lemma 4 to the large-scale MCMR-WMN case. In general, the channel utilization is a location-dependent parameter. However, due to the shared nature of the wireless medium, the channel utilizations observed by neighboring nodes are close to each other. Thus, considering the channel utilization observed by all nodes gives a lot of redundancy. One idea is to study the channel utilization observed by a special node on behalf of its neighbors. To address this solution, we define the "interference domain (ID)" and the "interference domain head" as follows.

Definition 5. The "interference domain" is defined as a subset of the network's nodes which satisfies three conditions.

(i) The interference domains have no common node that is, [ID.sub.i] [intersection] [ID.sub.j] = O, i [not equal to] j.

(ii) The interference domains span all nodes in the network that is, [[union].sup.M.sub.m = 1][ID.sub.m] = V, where M denotes the total number of interference domains.

(iii) Each interference domain, for example, the mth interference domain, includes a node denoted by [[xi].sub.m] so that only the nodes of [ID.sub.m] are located within the interference range of [[xi].sub.m]. We define [[xi].sub.m] as the "interference domain head" of [ID.sub.m].

It is clear from Definition 5 that a small-scale MCMR-WMN is a special case which consists of only one interference domain. The feasibility of condition (iii) is justified by the fact that mesh routers are usually deployed with careful planning. To clarify the above definition, consider a typical grid topology plotted in Figure 2 as a popular topology for the WMNs. Let the grid length be set to [L.sub.0]. In this case, for the interference range dintf, assume [square root of 2][L.sub.0] < [d.sub.intf] < 2[L.sub.0] which is a reasonable interference range [2]. Thus, we can model the interference domains as a 3 x 3 square grids as shown in Figure 2(b). This modeling satisfies conditions (i)-(iii) in Definition 5. In Figure 2(a), each circle represents an interference domain and the central black nodes play the role of the corresponding interference domain head.

Now, let the network be composed of M interference domains [ID.sub.1],..., [ID.sub.M]. For large-scale MCMR-WMNs, we define the average channel utilization [[bar.X].sub.LS] as follows:

[[bar.X].sub.LS] = 1/MK [K.summation over (k = 1)][M.summation over (m = 1)] [X.sup.k.sub.m], (21)

where [X.sup.k.sub.m] denotes the utilization of channel k observed by the mth interference domain head.

Theorem 6. Assume all sessions have the same traffic load, for example, [tr.sup.j.sub.s] = [T.sub.0]. The network's throughput of the large-scale MCMR-WMN is obtained as

[tau] = MK[c.sub.0]/[bar.NT] [[bar.X].sub.LS]. (22)

Proof. According to (8) and considering the condition (iii) in Definition 5, the utilization of the channel k observed by the mth interference domain head is given by

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (23)

Using (23) and averaging the utilization on different channels and different interference domain heads, we have

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], (24)

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], (25)

where (a) comes from assumption [tr.sup.j.sub.s] = [T.sub.0]. Under conditions (i) and (ii) in Definition 5 and using (2)-(4), we obtain

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (26)

Thus, (25) can be simplified as

[[bar.X].sub.LS] = [n.sub.s][T.sub.0][bar.NT]/MK[c.sub.0]. (27)

As a result, since [tau] = [n.sub.s][T.sub.0], the networks throughput can be obtained as [tau] = (MK[c.sub.0]/[bar.NT])[[bar.X].sub.LS].

Corollary 7. Under the same conditions as in Theorem 2, considering C = R[c.sub.0] and replacing [bar.NT] with the result in (16), the broadcast throughput of a large-scale MCMR-WMN is expressed in terms of the average node utilization and the average channel utilization as follows:

[tau] = [c.sub.0]/n - 1 (nR[bar.U] - MK[[bar.X].sub.LS]). (28)

It is clear that different parameters of the network interact with each other. Thus, it is not possible to draw a specified boundary between them. Due to the limited number of radios and non-overlapping channels, proper use of the resources could improve the performance of the network. In this regard, as we will show in the next section, the number of transmissions and the load-balancing significantly affect the network's throughput.

6. Numerical Results

In this section, we present a comprehensive evaluation on the relationship between the network's throughput and the resource utilizations. For this purpose, we apply the following protocols in a single-rate framework: SPT-JCRS [7], MCMJCRS [7], IRMT [20], and IRBT [20]. In our Matlab simulation setup, as shown in Figure 3, we consider a 6x6 square grid with n = 36 and M = 4, where nodes 8, 11, 26, and 29 are the interference domain heads. The grid length (the distance between neighbor nodes in the same row or column) and the interference range are set to 150 m and 280 m, respectively. We also use the random channel assignment, in which the radios of each node are randomly assigned to the distinct channels. Obviously, in the cases that the number of channels is less than or equal to the number of radios, this method will act as the common channel assignment strategy.

In the simulations, the broadcast session requests arrive one by one at the network without any knowledge of the future requests. The source of each session is selected randomly. In addition, the traffic model of all sessions is assumed to be Constant Bit Rate (CBR) with [tr.sup.j.sub.s] = 0.4 Mbps. Assuming R = 3, [c.sub.0] = 12 Mbps, and 25 broadcast session requests, we study the performance of the network for different number of channels; that is, K = 1,..., 6. It is clear that in the case of K = 1, we have a SCSR-WMN. Figure 4 compares the throughput of the aforementioned protocols in terms of the number of channels K. In addition, Table 1 shows the simulation results in more details. It should be noted that each data point is obtained by averaging the results of 15 individual runs on different randomly experiments. In this table, [bar.NT], [bar.U], [[bar.X].sub.LS], and [[tau].sub.sim] present the experimental results obtained for the average number of transmissions, the average node utilization, the average channel utilization, and the network's throughput, respectively. It is worth noting that the results in Table 1 exactly follow the described theoretical relationships in (16), (22), and (28). As an example, Table 1 compares [[tau].sub.sim] with the theoretical throughput [[tau].sub.theory] extracted from (28). Obviously, [[tau].sub.sim] is similar to [[tau].sub.theory] for different number of channels. This shows the validity of our analysis. This comparison can be also verified for relationships (16) and (22). It is clear that different parameters of the network interact with each other. In this situation, given the limited number of radios and channels, proper use of the resources could improve the performance of the network. Actually, using an efficient traffic engineering mechanism leads to better spectrum utilization and increases the fairness in the network. Thus, more resources will be available for accepting the future sessions and the overall throughput will be increased. In this regard, it is observed that the performance of the IRBT and the IRMT algorithms much better than that of the other two algorithms. In fact, the IRBT and the IRMT algorithms jointly address the transmission channel selection and the load-balanced routing tree construction [20]. These schemes not only take into account the number of transmissions, but also consider both inter-flow and intra-flow interferences to route the sessions through alternative feasible paths. Thus, the traffic load is balanced in the network. However, the MCMJCRS and the SPT-JCRS algorithms cannot efficiently use the resources of the network due to being limited to noninterference-aware routing trees.

In [20], we demonstrated that the IRBT algorithm balances the traffic load in the network more efficiently than the IRMT algorithm. The results in Table 1 also confirm this issue. From this table, we can see that the IRBT approach improves the utilization of the network resources. For K = 1, 2, 3 (i.e., common channel assignment), although the IRMT algorithm leads to less number of transmissions than the IRBT algorithm, the load-balancing ability of the IRBT makes both schemes have the same network's throughput. If the traffic load in the network is balanced, the interference will be decreased, and consequently, the call acceptance rate will be increased. In contrast, for K > 3, both IRMT and IRBT algorithms nearly have the same number of transmissions. In this situation, the load-balancing factor plays more efficient role in the network's performance. This causes the IRBT algorithm to show better throughput.

On the other hand, by increasing the number of channels, first the network's throughput linearly increases. However, for K > 3, it is gradually saturated. Due to the random channel assignment strategy, further increasing of the channels leads to the less number of common channels between the neighbor nodes. Thus, the possibility of enjoying the wireless broadcast advantage will be decreased. This increases the number of transmissions as shown in Table 1. In this situation, the lack of load-balancing could sufficiently reduce the network's throughput.

7. Conclusion

In this paper, the throughput of a MCMR-WMN was quantified. We focused on the scenario of on-demand QoS multicast/broadcast sessions, where each session has a specific bandwidth requirement. In particular, considering the resource constraints, we derived analytical relationships for the network's throughput in terms of the node utilization, the channel utilization, and the number of transmissions. This gives simple solutions for the future designs to predict the network's throughput based on the resource utilizations. In line with the proposed relationships, we also demonstrated that the network's throughput is significantly affected by both number of transmissions and degree of load-balancing. On one hand, minimizing the number of transmissions reduces the use of the network resources. On the other hand, load-balancing increases the fairness in the network. In this situation, more resources will be available for accepting the future sessions. Thus, the overall network's throughput will be increased.

http://dx.doi.org/ 10.1155/2013/794549

Acknowledgment

This work is supported by the Iranian Telecommunication Research Center (ITRC).

References

[1] P. H. Pathak and R. Dutta, "A survey of network design problems and joint design approaches in wireless mesh networks," IEEE Communications Surveys and Tutorials, vol. 13, no. 3, pp. 396-428, 2011.

[2] A. Raniwala and T.-C. Chiueh, "Architecture and algorithms for an IEEE 802.11-based multi-channel wireless mesh network," in Proceedings of the IEEE International Conference on Computer Communications (INFOCOM '05), vol. 3, pp. 2223-2234, March 2005.

[3] A. Avokh and G. Mirjalily, "Performance analysis of broadcasting in small-scale multi-radio multi-channel wireless mesh networks," in Proceedings of the 14th International Conference on Advanced Communication Technology (ICACT '12), pp. 537-542, February 2012.

[4] U. T. Nguyen and J. Xu, "Multicast routing in wireless mesh networks: minimum cost trees or shortest path trees?" IEEE Communications Magazine, vol. 45, no. 11, pp. 72-77, 2007

[5] Y. Li and I. Chen, "Dynamic agent-based hierarchical multicast for wireless mesh networks," Ad Hoc Networks, vol. 11, no. 6, pp. 1683-1698, 2013.

[6] J. E. Wieselthier, G. D. Nguyen, and A. Ephremides, "Energy-efficient broadcast and multicast trees in wireless networks," Mobile Networks and Applications, vol. 7, no. 6, pp. 481-492, 2002.

[7] A. Avokh, G. Mirjalily, and J. Abouei, "Joint channel and rate selection for multicast routing trees in wireless mesh networks," in Proceedings of the International Symposium on Telecommunications, pp. 548-553, November 2012.

[8] K. N. Ramachandran, E. M. Belding, K. C. Almeroth, and M. M. Buddhikot, "Interference-aware channel assignment in multi-radio wireless mesh networks," in Proceedings of the 25th IEEE International Conference on Computer Communications (INFOCOM '06), pp. 1-12, April 2006.

[9] R.-H. Jan, S.-Y. Huang, and C.-F. Wang, "An upper bound of the throughput for multi-radio wireless mesh networks," IEEE Communications Letters, vol. 14, no. 8, pp. 698-700, 2010.

[10] A. Capone, G. Carello, I. Filippini, S. Gualandi, and F. Malucelli, "Routing, scheduling and channel assignment in wireless mesh networks: optimization models and algorithms," Ad Hoc Networks, vol. 8, no. 6, pp. 545-563, 2010.

[11] E. Alotaibi, V. Ramamurthi, M. Batayneh, and B. Mukherjee, "Interference-aware routing for multi-hop wireless mesh networks," Computer Communications, vol. 33, no. 16, pp. 1961-1971, 2010.

[12] V. C. M. Borges, D. Pereira, M. Curado, and E. Monteiro, "Routing metric for interference and channel diversity in multi-radio wireless mesh networks," in Ad-Hoc, Mobile and Wireless Networks, vol. 5793 of Lecture Notes in Computer Science, pp. 55-68, Springer, Berlin, Germany, 2009.

[13] S. Roy, D. Koutsonikolas, S. Das, and Y. C. Hu, "High-throughput multicast routing metrics in wireless mesh networks," Ad Hoc Networks, vol. 6, no. 6, pp. 878-899, 2008.

[14] P M. Ruiz and A. F. Gomez-Skarmeta, "Approximating optimal multicast trees in wireless multihop networks," in Proceedings of the 10th IEEE Symposium on Computers and Communications (ISCC '05), pp. 686-691, June 2005.

[15] H. L. Nguyen and U. T. Nguyen, "Bandwidth efficient multicast routing in multi-channel multi-radio wireless mesh networks," in Proceedings of the International Conference on Ultra Modern Telecommunications and Workshops (ICUMT '09), pp. 1-8, October 2009.

[16] G. Zeng, B. Wang, Y. Ding, L. Xiao, and M. Mutka, "Efficient multicast algorithms for multichannel wireless mesh networks," IEEE Transactions on Parallel and Distributed Systems, vol. 21, no. 1, pp. 86-99, 2010.

[17] H. S. Chiu, K. L. Yeung, and K.-S. Lui, "Maximizing broadcast load in multi-channel Multi-interface wireless mesh networks," in Proceedings of the IEEE Global Telecommunications Conference (GLOBECOM '08), pp. 533-537, December 2008.

[18] F. Li, Y. Fang, F. Hu, and X. Liu, "Load-aware multicast routing metrics in multi-radio multi-channel wireless mesh networks," Computer Networks, vol. 55, no. 9, pp. 2150-2167, 2011.

[19] P A. K. Acharya and E. M. Belding, "MARS: link-layer rate selection for multicast transmissions in wireless mesh networks," Ad Hoc Networks, vol. 9, no. 1, pp. 48-60, 2011.

[20] A. Avokh and G. Mirjalily, "Interference-aware multicast and broadcast routing in wireless mesh networks using both rate and channel diversity," Computers & Electrical Engineering, 2013.

[21] T. Kim, Y. Yang, J. C. Hou, and S. V. Krishnamurthy, "Resource allocation for QoS support in wireless mesh networks," IEEE Transactions on Wireless Communications, vol. 12, no. 5, pp. 2046-2054, 2013.

[22] W. Kocay and D. Kreher, Graphs, Algorithms and Optimization: Discrete Mathematics and Its Applications, Chapman & Hall/CRC, Boca Raton, Fla, USA, 2005.

Avid Avokh, (1) Ghasem Mirjalily, (1) Jamshid Abouei, (1) and Shahrokh Valaee (2)

(1) Faculty of Electrical and Computer Engineering, Yazd University, Yazd 8915818411, Iran

(2) Department of Electrical and Computer Engineering, University of Toronto, Toronto, ON, Canada M5S3G4

Correspondence should be addressed to Avid Avokh; aavokh@stu.yazd.ac.ir

Received 29 August 2013; Accepted 23 September 2013

Academic Editors: C.-L. Chang, K. Dejhan, J. Garcia-Reinoso, and C. Pan

Table 1: Performance comparison for different number of channels.

Number of channels  Algorithm   [bar.NT]   [bar.U]   [bar.[X.sub.LS]]

                    IRBT        20.002     0.0961    0.9428
K = 1               IRMT        15.9444    0.0912    0.77
                    MCM-JCRS    18.1       0.0787    0.7239
                    SPT-JCRS    23.95      0.0703    0.7717
                    IRBT        19.7273    0.1998    0.9722
K = 2               IRMT        15.9967    0.1888    0.7993
                    MCM-JCRS    17.8833    0.1578    0.7205
                    SPT-JCRS    23.3780    0.1411    0.7628
                    IRBT        20.0016    0.2970    0.9719
K = 3               IRMT        16.2761    0.2769    0.7911
                    MCM-JCRS    18.225     0.2481    0.7644
                    SPT-JCRS    23.4697    0.2093    0.7561
                    IRBT        20.2207    0.3702    0.9144
K = 4               IRMT        18.6563    0.3086    0.7244
                    MCM-JCRS    18.966     0.2483    0.589
                    SPT-JCRS    24.1418    0.2455    0.6761
                    IRBT        21.5448    0.3909    0.8040
K = 5               IRMT        20.6932    0.3043    0.6105
                    MCM-JCRS    21.7823    0.2225    0.4608
                    SPT-JCRS    26.238     0.2155    0.4987
                    IRBT        23.9454    0.3929    0.7182
K = 6               IRMT        23.6876    0.2862    0.5197
                    MCM-JCRS    24.2579    0.2088    0.3854
                    SPT-JCRS    27.2301    0.2133    0.4204

Number of channels  [[tau].sub.sim](Mbps)   [[tau].sub.theory](Mbps)

                    2.2667                  2.2655
K = 1               2.32                    2.321
                    1.92                    1.9214
                    1.5467                  1.5448
                    4.7333                  4.7317
K = 2               4.8                     4.7986
                    3.8667                  3.8669
                    3.1333                  3.1325
                    7                       6.9988
K = 3               7                       6.9984
                    6.04                    6.0418
                    4.64                    4.6392
                    8.6909                  8.6918
K = 4               7.4545                  7.4531
                    5.9636                  5.9631
                    5.3818                  5.3816
                    8.96                    8.9613
K = 5               7.08                    7.0815
                    5.08                    5.0791
                    4.56                    4.56
                    8.64                    8.6388
K = 6               6.32                    6.3212
                    4.56                    4.5603
                    4.44                    4.4389
COPYRIGHT 2013 Hindawi Limited
No portion of this article can be reproduced without the express written permission from the copyright holder.
Copyright 2013 Gale, Cengage Learning. All rights reserved.

Article Details
Printer friendly Cite/link Email Feedback
Title Annotation:Research Article
Author:Avokh, Avid; Mirjalily, Ghasem; Abouei, Jamshid; Valaee, Shahrokh
Publication:The Scientific World Journal
Article Type:Report
Date:Jan 1, 2013
Words:6438
Previous Article:Memory-based multiagent coevolution modeling for robust moving object tracking.
Next Article:Large scale near-duplicate celebrity web images retrieval using visual and textual features.
Topics:

Terms of use | Privacy policy | Copyright © 2020 Farlex, Inc. | Feedback | For webmasters