# Application of anM/D/1 Queuing Model to WiMAX-Based  Wireless Mesh Networks: Grid Topology Case Study

Authors: Vahid Sattari Naeini; Naser Movahhedinia
Journal: ISRN Applied Mathematics
 (2012)

---

## Abstract

Wireless mesh networking is an effective approach to reach high performance in the last mile of broadband Internet access. The mesh structure is the basic step toward providing cost-effective, dynamic, and high-bandwidth wireless connection. In this paper, WiMAX-like wireless mesh network is considered, emphasizing the grid arrangement which is the general topology described in the literature. To evaluate the performance of the conventional and proposed scheduling algorithms, each link is modeled using anM/D/1 queue and a virtual node concept is introduced to describe comparable performance metrics for the system. Performance measures of the system in addition to the simulation results are assessed in terms of the network length and the arrival rates.


---

## Body

## 1. Introduction

Wireless mesh network (WMN) is a cost-effective multihop network, usually comprising some subscriber stations (SS) and one base station (BS). The multihop feature of WMN can increase its range of accessibility, in addition to reliability due to dynamic self-organizing and self-configuring features. Each SS can communicate with other SSs in its transmission range and the BS that connects the mesh network to the backbone. While some SSs only relay traffic flows of other SSs, some others carry their underlying subnetwork traffic flows as well.IEEE 802.16d has a potential to replace its tenacious rivals [1]. Its optional mesh mode transmits and routes various traffic streams among SSs directly in a distributed manner. Moreover, in its centralized mode, traffic stream routes to the network backbone through the BS. Since most of the traffic streams are between SSs and wired backbone network, the centralized mode is the most important [2–4] and we evaluate the system in this mode.In this paper, we consider an IEEE 802.16-like WMN and analyze the performance of a grid topology, which is generally used in WMNs. We introduce a queuing model to evaluate the average delay and also investigate some other issues influencing the delay constraint such as scheduling algorithm and position of the BS.The paper is organized as follows. In Section2, a brief survey of the previous research in this area is presented. In Section 3, the topologies used for introducing the model are described. Section 4 elaborates the IEEE 802.16d mesh mode with respect to its central scheduling procedure. The analytical model is presented in the Section 5. In Section 6, the VN solution is proposed and verified with two simple examples. Impact of the scheduling algorithm is also considered in this section. Performance evaluation of the proposed model and simulation results are discussed in Sections 7 and 8, respectively. Finally, the paper is concluded in Section 9.


## 2. Related Works

A comprehensive survey of WMNs has been presented in [5]. Performance analysis of WMN has been considered in a few recent papers. Reference [4] analyzes a WMN by combining M/M/C/∞, M/M/N(s)/K(s), and M/M/1/∞ queuing models. The network throughput, average packet delay, and packet loss are evaluated using the model. Performance modeling and analysis of integrated WLANs and mesh networks are considered in [2]. The analytical model utilizes the Poisson arrival and service rates at each mobile station. The average queuing delay in multichannel multi-interface WMNs is minimized in [6] based on an M/M/C/∞ queue.None of these models are suitable for IEEE 802.16 mesh network in which the frame duration is fixed. So, the main contribution of the paper is finding a suitable queuing model that can be considered in WiMAX-based WMN.Time division multiple access (TDMA) scheduling in central mesh mode of IEEE 802.16 has been considered in [7]. The authors of [8] have represented a survey on scheduling in WiMAX mesh mode. Since the basic scheduling algorithm of IEEE 802.16 has two drawbacks (stated below), some works have been carried out, challenging the basic algorithm. In [9], the Bellman-Ford scheduling algorithm shows worthy results on the return path delay, which is also bandwidth optimal. An interference-aware research framework introduced in [10] uses a blocking metric to improve spectral utilization. Scheduling problem in WiMAX mesh network is formulated and solved in [11] as a binary linear programming problem. The authors of [12] introduce the uniform slot allocation and uplink and downlink slot allocation algorithms to achieve higher spatial reuse and network throughput both in uplink and downlink paths.


## 3. Assumed Topologies

We consider a general form of mesh networks (Figure1), gird topology, which consists of some SSs and one BS. The length of the network (Y) is assumed to be the square root of the number of nodes (Y2=N).Figure 1
General grid topology used for WMNs.Each one of the nodes has a potential to be the BS; however, two more interesting geographical points will be elaborated in this paper. First, assuming the length of the grid to be an odd number, the BS is considered to be placed at the center of the grid (Figure2). The main advantage of this topology is its minimized hop count to other nodes. In the second topology (Figure 3), the BS is placed at one of the four corners of the grid. This topology is suitable for special situations such as earthquake-stricken or flood-prone areas, where the BS is placed at the margin of the area and SSs are distributed inside the area. However, with this topology the average hop count to the BS is maximized. We call the former topology BS centered (BSCe) and the later one BS cornered (BSCo).Figure 2
BS-centered scenario.Figure 3
BS-cornered scenario.


## 4. IEEE 802.16d Mesh Mode

Each SS is interconnected with other SSs in its transmission area. This structure forms a graph including some nodes (V) and some links (E). Each time an SS joins the network, it should experience an entry process. This process includes coarse synchronization establishment with the network. From all the potential sponsor nodes that the new node may connect to, it selects a sponsor node having the best signal quality metrics. After joining the network, the new node requests its data rate (service rate) from the BS through other SSs in the path to the BS. The BS collects all bandwidth requests from all SSs and assigns link bandwidths in a fixed frame length. The frame length is fixed at Tf; since each time its length is changed, the network should be set up again and this imposes some extra overheads to the network. As each node transmits in both uplink and downlink directions, node scheduling is replaced with link scheduling. Since this paper considers only uplink traffic analysis, node and link scheduling are equivalent and interchangeable throughout the paper.If total duration of bandwidth assignment procedure exceeds the frame length, link durations are fairly scaled down to be fit in the frame length. Scaling down the link durations means that some of the traffic needs to be queued for transmission in the next frames.A routing algorithm multicasts the end-to-end bandwidth granted to each mesh node by forming a spanning tree in the network. As stated in [13], this spanning tree can be constructed after a new node joins the network. We form one spanning tree for each of the two scenarios shown in Figures 4 and 5. Each tree has some leaf nodes and some middle nodes. Leaf nodes only generate traffic flows; however, middle nodes not only relay packets generated by leaf nodes but also may transmit their own traffic streams.Figure 4
BS-centered spanning tree.Figure 5
BS-cornered spanning tree.In the basic IEEE 802.16d scheduling algorithm, the transmission order of each link (in this paper, node) in the frame is computed during the breadth-first traversal of the routing algorithm. The link transmission times are sequential based on their ranking obtained from the previous stage. Once a transmission ends, the next transmission is started so there is no overlapping or gap between the two consecutive transmissions. This means that the IEEE 802.16 scheduling algorithm does not benefit the spatial reuse mechanism that allows simultaneous transmissions of nonconflicting links.Link durations are expressed in terms of minislots so that each minislot consists of some OFDM symbols. The maximum number of data minislots in a frame is limited to 256 [7]. Each OFDM symbol carries a number of bits (b), which is dependent to the modulation. Therefore, the number of bits transmitted in an OFDM symbol belongs to the {96,192,288,384,576,768,864}, where 96 is the number of bits carried in a symbol with the BPSK-1/2 modulation and 864 is the number of bits carried in a symbol with 64QAM-3/4 [7]. The total bandwidth occupied by the carriers is considered to be fixed at 20 MHz, so the duration of OFDM symbol will be Ts=12.5μs. Assuming that each minislot consists of o OFDM symbols and each transmission has an overhead of ν OFDM symbols, then, for the requested bandwidth of rj by node j, in terms of bits per second, the number of requested minislots is given by(4.1)dj=(rjTf/bj+νo).Sincedj may be scaled down due to inadequate space in the frame, the number of granted minislots will be(4.2)d̂j=(rjTf/bj+νo)×(1-ϕ),where0≤ϕ<1 is the scaling factor. As spatial reuse may be used in the scheduling algorithm, ∑jd̂j is greater or equal to 256; however, in this paper spatial reuse is neglected for simplicity; so, ∑jd̂j=256. Moreover, we exclude the overhead ν from analysis (ν=0). We assume that ϕ=0; so d̂j=dj.Granted link durations are fixed unless the bandwidth request of one or more nodes changes. Under such circumstances, the requested bandwidth propagates through the network and the BS recalculates the bandwidth granted to all the nodes again. This condition imposes some extra overheads to the system, which should be avoided [9]. We assume that the link durations or node service rates have been fixed for a long time.


## 5. Analysis

### 5.1. Mean Hop Count

Letℋ be a random variable denoting node hop counts to the BS. Probability distribution of node hop counts to the BS can be obtained by means of its probability generation function (PGF):(5.1)GH(z)=∑hiphizhi,wherehi=i is the ith hop count and phi denotes the probability of number of nodes in the ith hop count. The mean hop count to the BS is defined as(5.2)H̅=GH′|z=1.
The expected number of hops to the BS in the BSCe scenario (H̅BSCe) is computed as follows:(5.3)H̅BSCe=4Y2-1(∑i=1⌊Y/2⌋i2+∑i=⌈Y/2⌉,j=⌊Y/2⌋i=Y-1,j=1i×j)=4Y2-1(Y3-Y24+Y3-Y12).With some simple algebra,H̅BSCe can be simplified as(5.4)H̅BSCe=Y2.
By using (5.2) to calculate the expected number of hops to the BS in the BSCo scenario (H̅BSCo), we have(5.5)H̅BSCo=1Y2-1(∑i=1,j=2i=Y-1,j=Yi×j+∑i=Y,j=Y-1i=2(Y-1),j=1i×j)=1Y2-1(Y3-Y3+2Y3-3Y2+Y3).Again,H̅BSCo can be simplified as(5.6)H̅BSCo=Y2Y+1.Observation 1.
The ratio of the expected number of hops to the BS in the BSCo scenario to the expected number of hops to the BS in the BSCe scenario, for large number of nodes in the system, is 2.Proof.
From (5.4) and (5.6), it is clearly observed that
(5.7)lim⁡Y→∞⁡H̅BSCoH̅BSCe=lim⁡Y→∞⁡2YY+1=2.


### 5.2. Mean Service Rate

We assume that the service rate of each node follows a constant distribution with parameterS. This assumption is equivalent to what is stated in the IEEE 802.16d central mesh mode described in previous sections.The service process of the outgoing link of a node can be found by adding up its own service rate and the incoming service rates of that node:(5.8)Shij=S+∑kShi+1k,k∈INLNK(j),whereShij indicates the service rate of the jth link located at the ith hop count. INLNK indicates the set of all incoming links to node j.The mean service rate of links is obtained by the following relation:(5.9)S̅=∑i∑jShijN-1.This parameter, for the BSCe and the BSCo topologies, is obtained by the following relations, respectively:(5.10)S̅BSCe(Y)=4SY∑i=1⌊Y/2⌋iY2-1=Y2S,S̅BSCo(Y)=SY+S∑i=1Y-2(Y-i-1)(2i+1)+(1/6)S(Y(Y-1)(4Y+1)-6)Y2-1=Y2Y+1S.Observation 2.
It can be seen from (5.4), (5.6), and (5.10) that:
(5.11)S̅=H̅S.


### 5.3. Mean Arrival Rate

The arrival rate of each node is assumed to follow a Poisson distribution with parameterλ. With the spanning trees of Figures 4 and 5, a queuing network is constructed. The arrival rate of the last hop link (farthest link related to the BS) is λ. Since each link carries not only its own traffic flows but also its subtree traffic flows, the links closer to the BS get more arrival and service rates. Based on the Burke theorem, this arrival rate passes through the next link (because of stability conditions), and, next link, with respect to its own node, has a Poisson arrival rate of 2λ. The following relation is obtained for a general topology:(5.12)λhij=λ+∑kλhi+1k,k∈INLNK(j),whereλhij indicates the arrival rate of the jth link located at the ith hop count. The mean arrival rate of the links is obtained by the following relation:(5.13)λ̅=∑i∑jλhijN-1.The mean arrival rate for the BSCe and the BSCo topologies is obtained as follows, respectively:(5.14)λ̅BSCe(Y)=Y2λ,λ̅BSCo(Y)=Y2Y+1λ.Observation 3.
It can be seen from (5.4), (5.6), and (5.14) that
(5.15)λ̅=H̅λ.


### 5.4. Queuing Model

From the previous sections, it is concluded that the queuing model for the system follows anM/D/1 model for each link. The arrival process follows the Poisson model with parameter λi and the service model is assumed to be constant and equal to Si for the link i, respectively. The queuing metrics for this model are summarized as follows [14]:(5.16)wqi=12Si(ρi1-ρi),wi=12Si(2-ρi1-ρi),Lqi=ρi22(1-ρi),
where wqi is the queuing delay of the link i, wi is the sojourn time of the link i, and Lqi represents the queue length of the link i with ρi=λi/Si<1.


## 5.1. Mean Hop Count

Letℋ be a random variable denoting node hop counts to the BS. Probability distribution of node hop counts to the BS can be obtained by means of its probability generation function (PGF):(5.1)GH(z)=∑hiphizhi,wherehi=i is the ith hop count and phi denotes the probability of number of nodes in the ith hop count. The mean hop count to the BS is defined as(5.2)H̅=GH′|z=1.
The expected number of hops to the BS in the BSCe scenario (H̅BSCe) is computed as follows:(5.3)H̅BSCe=4Y2-1(∑i=1⌊Y/2⌋i2+∑i=⌈Y/2⌉,j=⌊Y/2⌋i=Y-1,j=1i×j)=4Y2-1(Y3-Y24+Y3-Y12).With some simple algebra,H̅BSCe can be simplified as(5.4)H̅BSCe=Y2.
By using (5.2) to calculate the expected number of hops to the BS in the BSCo scenario (H̅BSCo), we have(5.5)H̅BSCo=1Y2-1(∑i=1,j=2i=Y-1,j=Yi×j+∑i=Y,j=Y-1i=2(Y-1),j=1i×j)=1Y2-1(Y3-Y3+2Y3-3Y2+Y3).Again,H̅BSCo can be simplified as(5.6)H̅BSCo=Y2Y+1.Observation 1.
The ratio of the expected number of hops to the BS in the BSCo scenario to the expected number of hops to the BS in the BSCe scenario, for large number of nodes in the system, is 2.Proof.
From (5.4) and (5.6), it is clearly observed that
(5.7)lim⁡Y→∞⁡H̅BSCoH̅BSCe=lim⁡Y→∞⁡2YY+1=2.


## 5.2. Mean Service Rate

We assume that the service rate of each node follows a constant distribution with parameterS. This assumption is equivalent to what is stated in the IEEE 802.16d central mesh mode described in previous sections.The service process of the outgoing link of a node can be found by adding up its own service rate and the incoming service rates of that node:(5.8)Shij=S+∑kShi+1k,k∈INLNK(j),whereShij indicates the service rate of the jth link located at the ith hop count. INLNK indicates the set of all incoming links to node j.The mean service rate of links is obtained by the following relation:(5.9)S̅=∑i∑jShijN-1.This parameter, for the BSCe and the BSCo topologies, is obtained by the following relations, respectively:(5.10)S̅BSCe(Y)=4SY∑i=1⌊Y/2⌋iY2-1=Y2S,S̅BSCo(Y)=SY+S∑i=1Y-2(Y-i-1)(2i+1)+(1/6)S(Y(Y-1)(4Y+1)-6)Y2-1=Y2Y+1S.Observation 2.
It can be seen from (5.4), (5.6), and (5.10) that:
(5.11)S̅=H̅S.


## 5.3. Mean Arrival Rate

The arrival rate of each node is assumed to follow a Poisson distribution with parameterλ. With the spanning trees of Figures 4 and 5, a queuing network is constructed. The arrival rate of the last hop link (farthest link related to the BS) is λ. Since each link carries not only its own traffic flows but also its subtree traffic flows, the links closer to the BS get more arrival and service rates. Based on the Burke theorem, this arrival rate passes through the next link (because of stability conditions), and, next link, with respect to its own node, has a Poisson arrival rate of 2λ. The following relation is obtained for a general topology:(5.12)λhij=λ+∑kλhi+1k,k∈INLNK(j),whereλhij indicates the arrival rate of the jth link located at the ith hop count. The mean arrival rate of the links is obtained by the following relation:(5.13)λ̅=∑i∑jλhijN-1.The mean arrival rate for the BSCe and the BSCo topologies is obtained as follows, respectively:(5.14)λ̅BSCe(Y)=Y2λ,λ̅BSCo(Y)=Y2Y+1λ.Observation 3.
It can be seen from (5.4), (5.6), and (5.14) that
(5.15)λ̅=H̅λ.


## 5.4. Queuing Model

From the previous sections, it is concluded that the queuing model for the system follows anM/D/1 model for each link. The arrival process follows the Poisson model with parameter λi and the service model is assumed to be constant and equal to Si for the link i, respectively. The queuing metrics for this model are summarized as follows [14]:(5.16)wqi=12Si(ρi1-ρi),wi=12Si(2-ρi1-ρi),Lqi=ρi22(1-ρi),
where wqi is the queuing delay of the link i, wi is the sojourn time of the link i, and Lqi represents the queue length of the link i with ρi=λi/Si<1.


## 6. Virtual Node Concept

In this section, we take advantages of a virtual node (VN) to describe the overall properties of the mesh network, including(i) the average hop counts to the BS,(ii) their arrival and service rates.ThisVN could be a candidate node replacing all the nodes other than the BS and is located at H̅ hop count from the BS (Figure 6). The arrival and service rates of its connected link are λ̅ and S̅, respectively, both defined by Observation2 and Observation3. The stability condition for this model isFigure 6
TheVN solution.(6.1)ρ̅=λ̅S̅<1.The aggregate service rate of all links should be smaller than the maximum service rate of a frame of length 256 minislots. The service rate of a frame can be obtained by(6.2)FRMSR=256×o×bTf.Since there areY2-1 links in a frame, it can be concluded that(6.3)S̅(Y2-1)≤FRMSR.With some algebra, the following relations can be derived to obtainS̅ for the BSCe and the BSCo topologies, respectively:(6.4)SBSCe≤2×256×o×bY(Y2-1)Tf,SBSCo≤256×o×bY2(Y-1)Tf.Assuming the total bandwidth usage of the frame, the less than or equal sign is turned to equal sign. So(6.5)SBSCe=2×256×o×bY(Y2-1)Tf,(6.6)SBSCo=256×o×bY2(Y-1)Tf.Since, for the stability conditions,λ should be less than S, we have(6.7)λBSCe<2×256×o×bY(Y2-1)Tf,(6.8)λBSCo<256×o×bY2(Y-1)Tf.
Each node should be granted at least one minislot per frame; hence:(6.9)S×Tfb×o≥1.
From (6.6), (6.7), and (6.9) it can be concluded that(6.10)1<YBSCe<9,1<YBSCo<7.The average end-to-end waiting time, delivering traffic streams of all the nodes to the BS, is obtained by(6.11)w̅e2e=H̅w̅,which is turned to(6.12)w̅e2e=12s(2-ρ̅1-ρ̅).
Calculating w̅e2e, based on the VN data units, turns (6.12) to(6.13)w̅e2e=12s(2-ρ̅1-ρ̅)o×b×256H̅(Y2-1).
In which S is obtained by (6.5), or (6.6) and H̅ is calculated by (5.4) or (5.6), respectively. It is worth noting that in this case ρ̅=ρ.


### 6.1. Examples

In this section, two simple examples are used to validate and illustrate the above mentionedVN model.


#### 6.1.1. Simple Linear Topology

Figure7 shows the linear topology used for our experience. Each node is fed with the Poisson arrival rate with parameter λ. The arrival and service rates of each link are illustrated on that link. Each link is assumed to have an infinite buffer size.Figure 7
Simple linear topology.Mean end-to-end delay in this topology is calculated as follows:(6.14)we2e=w1+(w2+w1)+(w3+w2+w1)3=w1+23w2+13w3.The subscripti in wi indicates the ith SS. Since ρ=λ/μ,(6.15)w3=12S(2-ρ1-ρ),w2=14S(2-ρ1-ρ),w1=16S(2-ρ1-ρ).The actual mean end-to-end delay in this topology is obtained by(6.16)we2eAc=12S(2-ρ1-ρ).From theVN solution described in this section, we have(6.17)H̅=2,λ̅=2λ,S̅=2S.Then,we2e in the VN model is calculated as(6.18)we2eVN=12S(2-ρ1-ρ),which is equal towe2eAc.


#### 6.1.2. Simple Tree Topology

In simple tree topology of Figure8, the waiting times in the system are obtained by the following relations:(6.19)w1=16S(2-ρ1-ρ),w2=w3=12S(2-ρ1-ρ),Figure 8
Simple tree topology.which results in(6.20)we2eAc=w1+w2+w33=12S(2-ρ1-ρ).From theVN model, we have(6.21)H̅=53,λ̅=53λ,S̅=53S.Then, we2e in the VN model is calculated as(6.22)we2eVN=53(12×(5/3)S×2-ρ1-ρ),which is equal towe2eAc.


### 6.2. Impact of Scheduling Algorithm (Scheduling Delay)

Observation 4.
The maximum number of required frames, in which the BS can process all the nodes, is the height of the spanning tree.Proof.
In a spanning tree the node with maximum number of hops to the root (one of the leaf nodes as an example) has the worst condition to reach the root. This situation gets worse if the transmission order of links is conversely from root to that leaf. In the worst condition, the scheduling algorithm does not exploit the spatial reuse mechanism. So each link of the path to the root, on which the leaf node is scheduled, should be scheduled in a separate frame.The analytical model described in the previous section is based on the fact that the transmission order of the links is recursively from leaf nodes to the BS. For example in Figure8, links 2 and 3 start the transmission; then, transmission of link 1 will be commenced.Each link should be scheduled in a frame such that all the links take some amount of bandwidth in each frame. The transmission order of each link in the frame has a direct influence on delay consideration. For example, suppose that the transmission order of links in the linear topology of Figure7 follows e3⇝e2⇝e1. Since each link should be scheduled in each frame, all the links deliver their traffic in one frame (Scheduling Algorithm 1 (SA1)). This situation is the best in terms of the total delay for delivering the traffic streams to the BS and has been analyzed in the previous sections. On the other hand, suppose the transmission order follows e1⇝e2⇝e3 (Scheduling Algorithm 2 (SA2)) meaning that e1 delivers its data to the BS in the first frame, e2 delivers its data in the second frame, and e3 delivers its data in the third frame. Therefore, the average delay in terms of the number of frames is 2. This situation, on the other hand, is the worst in delivering traffic streams to the BS. All the other situations lie between these two scenarios.We estimate scheduling delay in terms of the frame lengthTf in the VN solution. As stated in the previous sections, H̅ can be obtained by (5.4) or (5.6). This number of hops (in this case, links) can be scheduled in maximum H̅ frames, based on Observation4. In the best case (by using SA1) all of them can be scheduled in one frame; on the other hand, in the worst case (by using SA2) all of them can be scheduled in H̅ frame. It is worthy to note that we defined this metric comparing various scenarios; however, the accurate analysis of delay in this case is out of the scope of this paper and in left for another work in this area.PGF ofℱ, a random variable denoting the number of required frames to deliver all the packets of nodes to the BS, is defined as(6.23)GF(z)=∑fipfizfi,wherefi=i>1 denotes the number of required frames and pfi is the probability of fi frames required to deliver all the packets to the BS. So, the mean number of required frames is defined as(6.24)F̅=GF′|z=1.Equation (6.13), with respect to (6.5) and (6.6) and with some simple algebra, can be rewritten as follows:(6.25)w̅e2eSA1=Tf2(2-ρ̅SA11-ρ̅SA1).Separating queuing and service delay results in(6.26)w̅e2eSA1=Tf2(ρ̅SA11-ρ̅SA1)+Tf.The first term in the right-hand side of (6.26) is queuing delay and the second term is serving delay of each unit of data in the VN solution. This equation implies that end-to-end delay in both topologies of Figures 4 and 5 is equal; since their arrival and service rates are different based on (6.5) and (6.6); however, this is only true in the case of SA1 deployment. Providing such a relation in the case of SA2 deployment is out of the scope of this paper; however, it is possible to estimate this metric as well.The serving delay in (6.26) can be expressed as scheduling delay. With respect to the VN solution and Observation4, it can be concluded that, in the case of SA2, the scheduling delay is turned to H̅Tf. So(6.27)w̅e2eSA2=H̅Tf2(ρ̅SA21-ρ̅SA2)+H̅Tf.Findingρ̅SA2 is out of the scope of this paper; however, we can put a maximum bound on λ̅SA2 for the stability condition as well.Sinceρ̅SA2 must be less than 1 and the serving delay is equal to H̅Tf, we have(6.28)λ̅SA2<o×b×256H̅2Tf(Y2-1).


## 6.1. Examples

In this section, two simple examples are used to validate and illustrate the above mentionedVN model.


### 6.1.1. Simple Linear Topology

Figure7 shows the linear topology used for our experience. Each node is fed with the Poisson arrival rate with parameter λ. The arrival and service rates of each link are illustrated on that link. Each link is assumed to have an infinite buffer size.Figure 7
Simple linear topology.Mean end-to-end delay in this topology is calculated as follows:(6.14)we2e=w1+(w2+w1)+(w3+w2+w1)3=w1+23w2+13w3.The subscripti in wi indicates the ith SS. Since ρ=λ/μ,(6.15)w3=12S(2-ρ1-ρ),w2=14S(2-ρ1-ρ),w1=16S(2-ρ1-ρ).The actual mean end-to-end delay in this topology is obtained by(6.16)we2eAc=12S(2-ρ1-ρ).From theVN solution described in this section, we have(6.17)H̅=2,λ̅=2λ,S̅=2S.Then,we2e in the VN model is calculated as(6.18)we2eVN=12S(2-ρ1-ρ),which is equal towe2eAc.


### 6.1.2. Simple Tree Topology

In simple tree topology of Figure8, the waiting times in the system are obtained by the following relations:(6.19)w1=16S(2-ρ1-ρ),w2=w3=12S(2-ρ1-ρ),Figure 8
Simple tree topology.which results in(6.20)we2eAc=w1+w2+w33=12S(2-ρ1-ρ).From theVN model, we have(6.21)H̅=53,λ̅=53λ,S̅=53S.Then, we2e in the VN model is calculated as(6.22)we2eVN=53(12×(5/3)S×2-ρ1-ρ),which is equal towe2eAc.


## 6.1.1. Simple Linear Topology

Figure7 shows the linear topology used for our experience. Each node is fed with the Poisson arrival rate with parameter λ. The arrival and service rates of each link are illustrated on that link. Each link is assumed to have an infinite buffer size.Figure 7
Simple linear topology.Mean end-to-end delay in this topology is calculated as follows:(6.14)we2e=w1+(w2+w1)+(w3+w2+w1)3=w1+23w2+13w3.The subscripti in wi indicates the ith SS. Since ρ=λ/μ,(6.15)w3=12S(2-ρ1-ρ),w2=14S(2-ρ1-ρ),w1=16S(2-ρ1-ρ).The actual mean end-to-end delay in this topology is obtained by(6.16)we2eAc=12S(2-ρ1-ρ).From theVN solution described in this section, we have(6.17)H̅=2,λ̅=2λ,S̅=2S.Then,we2e in the VN model is calculated as(6.18)we2eVN=12S(2-ρ1-ρ),which is equal towe2eAc.


## 6.1.2. Simple Tree Topology

In simple tree topology of Figure8, the waiting times in the system are obtained by the following relations:(6.19)w1=16S(2-ρ1-ρ),w2=w3=12S(2-ρ1-ρ),Figure 8
Simple tree topology.which results in(6.20)we2eAc=w1+w2+w33=12S(2-ρ1-ρ).From theVN model, we have(6.21)H̅=53,λ̅=53λ,S̅=53S.Then, we2e in the VN model is calculated as(6.22)we2eVN=53(12×(5/3)S×2-ρ1-ρ),which is equal towe2eAc.


## 6.2. Impact of Scheduling Algorithm (Scheduling Delay)

Observation 4.
The maximum number of required frames, in which the BS can process all the nodes, is the height of the spanning tree.Proof.
In a spanning tree the node with maximum number of hops to the root (one of the leaf nodes as an example) has the worst condition to reach the root. This situation gets worse if the transmission order of links is conversely from root to that leaf. In the worst condition, the scheduling algorithm does not exploit the spatial reuse mechanism. So each link of the path to the root, on which the leaf node is scheduled, should be scheduled in a separate frame.The analytical model described in the previous section is based on the fact that the transmission order of the links is recursively from leaf nodes to the BS. For example in Figure8, links 2 and 3 start the transmission; then, transmission of link 1 will be commenced.Each link should be scheduled in a frame such that all the links take some amount of bandwidth in each frame. The transmission order of each link in the frame has a direct influence on delay consideration. For example, suppose that the transmission order of links in the linear topology of Figure7 follows e3⇝e2⇝e1. Since each link should be scheduled in each frame, all the links deliver their traffic in one frame (Scheduling Algorithm 1 (SA1)). This situation is the best in terms of the total delay for delivering the traffic streams to the BS and has been analyzed in the previous sections. On the other hand, suppose the transmission order follows e1⇝e2⇝e3 (Scheduling Algorithm 2 (SA2)) meaning that e1 delivers its data to the BS in the first frame, e2 delivers its data in the second frame, and e3 delivers its data in the third frame. Therefore, the average delay in terms of the number of frames is 2. This situation, on the other hand, is the worst in delivering traffic streams to the BS. All the other situations lie between these two scenarios.We estimate scheduling delay in terms of the frame lengthTf in the VN solution. As stated in the previous sections, H̅ can be obtained by (5.4) or (5.6). This number of hops (in this case, links) can be scheduled in maximum H̅ frames, based on Observation4. In the best case (by using SA1) all of them can be scheduled in one frame; on the other hand, in the worst case (by using SA2) all of them can be scheduled in H̅ frame. It is worthy to note that we defined this metric comparing various scenarios; however, the accurate analysis of delay in this case is out of the scope of this paper and in left for another work in this area.PGF ofℱ, a random variable denoting the number of required frames to deliver all the packets of nodes to the BS, is defined as(6.23)GF(z)=∑fipfizfi,wherefi=i>1 denotes the number of required frames and pfi is the probability of fi frames required to deliver all the packets to the BS. So, the mean number of required frames is defined as(6.24)F̅=GF′|z=1.Equation (6.13), with respect to (6.5) and (6.6) and with some simple algebra, can be rewritten as follows:(6.25)w̅e2eSA1=Tf2(2-ρ̅SA11-ρ̅SA1).Separating queuing and service delay results in(6.26)w̅e2eSA1=Tf2(ρ̅SA11-ρ̅SA1)+Tf.The first term in the right-hand side of (6.26) is queuing delay and the second term is serving delay of each unit of data in the VN solution. This equation implies that end-to-end delay in both topologies of Figures 4 and 5 is equal; since their arrival and service rates are different based on (6.5) and (6.6); however, this is only true in the case of SA1 deployment. Providing such a relation in the case of SA2 deployment is out of the scope of this paper; however, it is possible to estimate this metric as well.The serving delay in (6.26) can be expressed as scheduling delay. With respect to the VN solution and Observation4, it can be concluded that, in the case of SA2, the scheduling delay is turned to H̅Tf. So(6.27)w̅e2eSA2=H̅Tf2(ρ̅SA21-ρ̅SA2)+H̅Tf.Findingρ̅SA2 is out of the scope of this paper; however, we can put a maximum bound on λ̅SA2 for the stability condition as well.Sinceρ̅SA2 must be less than 1 and the serving delay is equal to H̅Tf, we have(6.28)λ̅SA2<o×b×256H̅2Tf(Y2-1).


## 7. Performance Evaluation

The system described in the previous sections has two essential delay constraints: queuing delay (DQ) and scheduling delay (DS). The mean end-to-end delay of the system is given by(7.1)D̅e2e=D̅se2e+D̅Qe2e.To evaluate the performance of the system, the two scheduling algorithms, SA1 and SA2, which are the best and the worst cases, respectively, have been deployed to the analysis.pfi is computed in these two cases by the following relations:(7.2)pfi(SA1)={1i=1,0i≠1,pfi(SA2)={1i=H̅,0i≠H̅.


### 7.1. Delay Analysis

Deploying SA1 and SA2 scheduling algorithms results in the following relations obtaining the end-to-end delay:(7.3)De2e(SA1)=Tf+Tf2(ρ̅SA11-ρ̅SA1),De2e(SA2)=H̅Tf+H̅Tf2(ρ̅SA21-ρ̅SA2).Observation 5.
Assuming the same work load in the cases SA1 and SA2, it can be concluded that(7.4)De2e(SA2)=H̅De2e(SA1).We set the parameterso, b, and Tf to 3, {96,864}, and 10 ms, respectively. At first, we compare queuing and scheduling delay constraints. Figure 9 shows this comparison for the case of SA1. It can be seen that for ρ less than 2/3 the scheduling delay is dominant. When the amount of work load passes 2/3, the queuing delay will be the main factor and for work loads close to 1 the scheduling delay can be neglected.Figure 9
Queuing and scheduling delay comparison using SA1 scheduling algorithm.Figure10 compares the scheduling and queuing delay constraints for the case SA2 while the BSCe topology is exploited. In this case the queuing delay is dominant for ρs greater than 2/3, too.Figure 10
Queuing and scheduling delay comparison using SA2 scheduling algorithm for the BSCe topology.Figures11 and 12 illustrate the end-to-end delay for the case SA2 with possible Ys.Figure 11
End-to-end delay comparison using SA2 scheduling algorithm for the BSCe topology.Figure 12
End-to-end delay comparison using SA2 scheduling algorithm for the BSCo topology.Next, we compare end-to-end delay of the two topologies, the BSCe and the BSCo, in the cases of SA1 and SA2. Figure13 compares end-to-end delay for the four scenarios.Figure 13
End-to-end delay comparison for the four scenarios.The main results derived from Figure13 are summarized as follows.(i)
In the case of SA2, delay of the BSCe topology forρ=0.9 is greater than that of the BSCo topology for ρ=0.8.(ii)
In the case of SA2, delay of the BSCe topology forρ=0.95 is greater than that of the BSCo topology for ρ=0.9.(iii)
In the case of SA2, delay of the BSCo topology and that of the BSCe topology forρ=0.95, and ρ=0.95, respectively, are such that they are not suitable for real-time applications (maximum delay bound for real-time applications is about 150 ms).(iv)
The BSCe topology with SA2 deployment andρ=0.9 is suitable for real-time applications; however, the BSCo topology with SA2 deployment and ρ=0.9 is suitable for real-time applications for the network lengths of less than 4.(v)
Delay bound for the two topologies andρ=0.95 is greater than that for the BSCe topology with SA2 scheduling algorithm and ρ=0.8.


### 7.2. Throughput Evaluation

Since each individual node is granted256/((Y2-1)H̅) minislots, the throughput of the system is calculated according to the following relation, in the case of SA1, by means of the VN concept: (7.5)θSA1=256×o×b×ρSA1H̅Tf.
In the case of SA2 deployment, the system throughput is computed as follows:(7.6)θSA2=SSA2ρSA2(Y2-1).As previously stated,S̅SA2 is equal to S̅SA1/H̅; so:(7.7)θSA2=256×o×b×ρSA2H̅2Tf.Observation 6.
Assuming the same work load in the two cases SA1 and SA2, it can be concluded that(7.8)θSA1=H̅θSA2.Figure14 illustrates the throughput comparison of the four scenarios regarding three values of ρs for each scenario. The main results derived from the figure are summarized as follows. (i)
As it can be indicated from Figure13, the delay bounds for the two topologies in the case of SA1 are equivalent; however, the throughput of the BSCo topology is less than that of the BSCe topology in the case of SA2. This degradation is because of lower data rates of the BSCo topology.(ii)
The throughput of the SA2 scheduling algorithm is greater than the throughput of the SA1 scheduling algorithm for small network lengths; however, this measure is lower as the length of the network grows. Since the network length for the BSCe topology could not be set to 2, this situation occurs.Figure 14
Throughput of the system comparison for the four scenarios.As the throughput is dependent on the modulation used, Figure15 shows this dependency for b={96,864} for the BSCe topology in the case of SA1. It can be indicated from the figure that the maximum throughput reaches 39.8131 when b=864 and Y=3; this measure is 1.8959 when b=96 and Y=7.Figure 15
Throughput of the system comparison using SA1 scheduling algorithm for the BSCe topology.


## 7.1. Delay Analysis

Deploying SA1 and SA2 scheduling algorithms results in the following relations obtaining the end-to-end delay:(7.3)De2e(SA1)=Tf+Tf2(ρ̅SA11-ρ̅SA1),De2e(SA2)=H̅Tf+H̅Tf2(ρ̅SA21-ρ̅SA2).Observation 5.
Assuming the same work load in the cases SA1 and SA2, it can be concluded that(7.4)De2e(SA2)=H̅De2e(SA1).We set the parameterso, b, and Tf to 3, {96,864}, and 10 ms, respectively. At first, we compare queuing and scheduling delay constraints. Figure 9 shows this comparison for the case of SA1. It can be seen that for ρ less than 2/3 the scheduling delay is dominant. When the amount of work load passes 2/3, the queuing delay will be the main factor and for work loads close to 1 the scheduling delay can be neglected.Figure 9
Queuing and scheduling delay comparison using SA1 scheduling algorithm.Figure10 compares the scheduling and queuing delay constraints for the case SA2 while the BSCe topology is exploited. In this case the queuing delay is dominant for ρs greater than 2/3, too.Figure 10
Queuing and scheduling delay comparison using SA2 scheduling algorithm for the BSCe topology.Figures11 and 12 illustrate the end-to-end delay for the case SA2 with possible Ys.Figure 11
End-to-end delay comparison using SA2 scheduling algorithm for the BSCe topology.Figure 12
End-to-end delay comparison using SA2 scheduling algorithm for the BSCo topology.Next, we compare end-to-end delay of the two topologies, the BSCe and the BSCo, in the cases of SA1 and SA2. Figure13 compares end-to-end delay for the four scenarios.Figure 13
End-to-end delay comparison for the four scenarios.The main results derived from Figure13 are summarized as follows.(i)
In the case of SA2, delay of the BSCe topology forρ=0.9 is greater than that of the BSCo topology for ρ=0.8.(ii)
In the case of SA2, delay of the BSCe topology forρ=0.95 is greater than that of the BSCo topology for ρ=0.9.(iii)
In the case of SA2, delay of the BSCo topology and that of the BSCe topology forρ=0.95, and ρ=0.95, respectively, are such that they are not suitable for real-time applications (maximum delay bound for real-time applications is about 150 ms).(iv)
The BSCe topology with SA2 deployment andρ=0.9 is suitable for real-time applications; however, the BSCo topology with SA2 deployment and ρ=0.9 is suitable for real-time applications for the network lengths of less than 4.(v)
Delay bound for the two topologies andρ=0.95 is greater than that for the BSCe topology with SA2 scheduling algorithm and ρ=0.8.


## 7.2. Throughput Evaluation

Since each individual node is granted256/((Y2-1)H̅) minislots, the throughput of the system is calculated according to the following relation, in the case of SA1, by means of the VN concept: (7.5)θSA1=256×o×b×ρSA1H̅Tf.
In the case of SA2 deployment, the system throughput is computed as follows:(7.6)θSA2=SSA2ρSA2(Y2-1).As previously stated,S̅SA2 is equal to S̅SA1/H̅; so:(7.7)θSA2=256×o×b×ρSA2H̅2Tf.Observation 6.
Assuming the same work load in the two cases SA1 and SA2, it can be concluded that(7.8)θSA1=H̅θSA2.Figure14 illustrates the throughput comparison of the four scenarios regarding three values of ρs for each scenario. The main results derived from the figure are summarized as follows. (i)
As it can be indicated from Figure13, the delay bounds for the two topologies in the case of SA1 are equivalent; however, the throughput of the BSCo topology is less than that of the BSCe topology in the case of SA2. This degradation is because of lower data rates of the BSCo topology.(ii)
The throughput of the SA2 scheduling algorithm is greater than the throughput of the SA1 scheduling algorithm for small network lengths; however, this measure is lower as the length of the network grows. Since the network length for the BSCe topology could not be set to 2, this situation occurs.Figure 14
Throughput of the system comparison for the four scenarios.As the throughput is dependent on the modulation used, Figure15 shows this dependency for b={96,864} for the BSCe topology in the case of SA1. It can be indicated from the figure that the maximum throughput reaches 39.8131 when b=864 and Y=3; this measure is 1.8959 when b=96 and Y=7.Figure 15
Throughput of the system comparison using SA1 scheduling algorithm for the BSCe topology.


## 8. Simulation Results

We have developed a simulation scenario in the NS-2 simulation environment. It is assumed that all links exploit the BPSK-1/2 modulation (b=96) and each minislot contains 3 OFDM symbols. So, minislot size has been fixed at 96×3 bits. The buffer size of each node has been set so large such that no packet loss is occurred. Transmission and interference ranges of each node are equal with respect to the modulation used.For each network length we ran the simulation about 50 times and set the average as the simulation result. We took two scenarios for the simulation. The work load of the system in these two scenarios has been set to 0.9. In the first scenario, the BSCe topology along with SA1 scheduling algorithm withb=96 has been considered. In the second scenario, the BSCo topology along with SA2 scheduling algorithm with b=96 has been considered. In both cases, the analytical model has been illustrated along with the simulation result to verify the analytical model.Figure16 illustrates end-to-end delay calculated through simulations for various lengths of the network. As it can be indicated from the figure, the simulation and analytical results follow the same curve in the two cases; however, for the case of simulation because of some extra overheads, the end-to-end delay is more than that of analytical results. As network length grows up, the overhead gets bigger and the simulation results get a little far from the analytical approach. As a result, it can be seen that the analytical model can predict the system delay as well.Figure 16
End-to-end delay comparison of the analytical and simulation approaches (b=96, o=3, Tf=10ms, and ρ=0.9).Figure17 shows the throughput calculated through simulations for various lengths of the network. As it can be seen in this figure, the throughput degradation is completely evident in the case of simulation results. A simple indication is that, as each minislot carries some overhead, the aggregated minislots flown in the network are smaller than those of the analytical model. Again, the analytical results follow the same curves as simulation results and it can be concluded that the analytical approach predicts the throughput of the system as well.Figure 17
Throughput comparison of analytical and simulation approaches (b=96, o=3, Tf=10ms, and ρ=0.9).


## 9. Conclusions

The main contribution of this paper was devoted to introducing a model for estimating the performance measures of WiMAX-like WMNs. Exploiting the benefits of thevirtual node solution and introducing two types of scheduling algorithms, delay and throughput metrics of the two topologies were obtained. The analytical study shows that the throughput of the system is highly dependent on the position of the BS and the length of the network. Although the analytical approach was restricted by some simplifying assumptions, its verification with simulation results confirms that this approach estimates the system parameters well.



---

*Source: 340306-2012-03-21.xml*