# The Actual Maximum Throughput of Mobile Ad Hoc Networks with Reed-Solomon Coding

Authors: Yuanyuan Fan; Bin Yang; Xiaomei Yu
Journal: Mathematical Problems in Engineering
 (2015)

---

## Abstract

Maximum throughput serves as a fundamental metric for evaluating the performance of mobile ad hoc networks. However, the actual maximum throughput still remains significantly unknown in such networks. This paper studies the actual maximum throughput of mobile ad hoc networks under a general routing scheme with reed-solomon coding, where a source node first encodes a group ofg packets into w (w≥g) code blocks, and then these code blocks are transmitted to distinct relay nodes, which forward them to destination node. The original g packets can be decoded once the destination node receives any g code blocks. To explore the actual maximum throughput, we first establish two Markov chain models to capture the fastest packet sending and receiving processes at source and destination nodes under the considered routing scheme. Based on the Markov chain models, we then derive a closed-form expression for the maximum throughput in such networks. Finally, extensive simulations and theoretical results are presented to validate the accuracy of our theoretical maximum throughput analysis in mobile ad hoc networks and to illustrate how network parameters influence the maximum throughput performance.


---

## Body

## 1. Introduction

Mobile ad hoc networks represent a class of self-configurable wireless networks, where mobile nodes can communicate with each other freely through peer-to-peer wireless links without infrastructure support [1, 2]. Since such networks can be rapidly deployed, easily managed, and extended, they have many critical applications such as space or underwater communication, disaster relief, battlefield communication, and traffic offloading in cellular-based vehicular network. To guarantee Quality of Service (QoS) in these applications, it is of great importance to study the maximum throughput (i.e., the maximum packet delivery rate that each node in the networks can support) performance of mobile ad hoc networks.There have been several studies on the maximum throughput of mobile ad hoc networks in the literature. However, most of efforts focused on the study of asymptotic maximum throughput. For example, in a seminal work [3], Grossglauser and Tse showed that node mobility can significantly improve the maximum throughput and proved that it achieves Θ(1) under i.i.d mobility model (In this paper, we use the following asymptotic notations: (i) f(n)=O(g(n)) means that there exist a positive constant c and an integer N such that f(n)≤cg(n) for n>N; (ii) f(n)=Θ(g(n)) means that f(n)=Ogn and g(n)=O(f(n))). In addition, the maximum throughput of Θ(1) was later proved to be achievable under the Brownian mobility model [4] and the uniform mobility model [5]. The asymptotic trade-off between the maximum throughput and delay performance has also been studied. Neely and Modiano [6] showed that under i.i.d. mobility model, the asymptotic trade-off between delay and maximum throughput is not less than On, where n represents the number of nodes in the network. Toumpis and Goldsmith [7] also studied the asymptotic trade-off between them under i.i.d. mobility model. Sharma et al. [8] proposed a unified framework to explore the asymptotic trade-off under different mobility models. Recently, coding techniques have been incorporated into the studies. Ying et al. [9] proved that, by employing rate-less codes (e.g., Raptor codes), the asymptotic trade-off between maximum throughput and delay is improved under the proposed joint coding-scheduling algorithm. However, the maximum throughput of a constant O(1) is not achievable in [9]. More recently, Kong et al. [10] showed that, by employing reed-solomon coding, the maximum throughput can achieve a constant O(1) under two-hop relay routing in mobile ad hoc networks.Notice that all the aforementioned work on the maximum throughput of mobile ad hoc networks focused on the asymptotic results, which could not indicate the actual achievable maximum throughput of such networks. In practice, the actual maximum throughput is significantly important for network designers. Some researchers have made efforts to explore the actual maximum throughput of mobile ad hoc networks and obtained some initial results. Neely et al. [6, 11] derived closed-form expressions for the maximum throughput under independent and identically distributed mobility model and Markovian mobility model, respectively. Recently, Liu et al. [12] studied the actual maximum throughput under two-hop relay routing with packet replication technique, where each packet can be replicated to multiple relay nodes.In this paper, we study the actual maximum throughput of mobile ad hoc networks under two-hop relay routing with reed-solomon coding. Under this routing scheme, source node first encodes a group ofg packets into w (w≥g) code blocks, which will be transmitted to distinct relay nodes, and then its destination node receives these code blocks from either the relay nodes or the source node. The original g packets can be decoded once the destination node receives any g code blocks of the group. Notice that the work in [10] is closest to ours. However, the fundamental difference between them is that the work in [10] studies the asymptotic maximum throughput, while our work explores the actual maximum throughput. As a first step, this paper explores the actual maximum throughput by employing the reed-solomon coding.The main contributions of this paper are summarized as follows:(i)
We first establish two Markov chain models to capture the fastest packet sending and receiving processes at source and destination nodes under the routing scheme in the considered mobile ad hoc network.(ii)
Based on these two Markov chain models, we then derive a closed-form expression for the maximum throughput in such network.(iii)
Finally, extensive simulations are presented to validate the accuracy of theoretical maximum throughput analysis and numerical results are also presented to illustrate how network parameters influence the maximum throughput performance.This paper is organized as follows. We introduce system models and performance metric in Section2. Section 3 presents MAC protocol and routing scheme. Based on the routing scheme, we first establish two absorbing Markov chain models to depict the fastest packet sending and receiving processes at source and destination nodes and then derive the closed-form expression for the maximum throughput in Section 4. Section 5 provides numerical results to validate the accuracy of theoretical maximum throughput analysis and to illustrate the impact of network parameters on the maximum throughput performance. We conclude this paper in Section 6.


## 2. System Models and Performance Metric

In this section we introduce the system models and the definition of maximum throughput adopted in this paper.


### 2.1. System Models

#### 2.1.1. Network Model

We consider a mobile ad hoc network composed ofn nodes moving on a unit square region, opposite edges of which touch each other so as to avoid border effects. As shown in Figure 1, similar to previous work [6, 11–14], the network region is uniformly partitioned into m×m cells.Figure 1
Network model and MAC protocol.


#### 2.1.2. Mobility Model

The node movements in the network follow the independent and identically distributed (i.i.d.) mobility model widely adopted in [6, 11–14], where time is divided into slots of equal duration and at the beginning of each time slot, each node moves into a cell selected from the m2 cells with equal probability and remains in it for the entire time slot.


#### 2.1.3. Communication Model

We adopt a commonly usedprotocol model [13, 14] to avoid interference among simultaneous data transmissions. According to theprotocol model, each node (e.g., S1 in Figure 1) employs a fixed transmission range covering the cell it resides in and its eight neighbor cells. Let d(i,j) denote the Euclidean distance between node i and node j, and then node j can successfully receive data from node i if and only if the following condition holds: d(k,j)≥(1+Δ)d(i,j) for each other node k (k≠i) simultaneously sending, where Δ is a positive integer.


#### 2.1.4. Traffic Model

Similar to [15], we consider a permutation traffic model where each node is source of one traffic flow and destination of another traffic flow. Thus, there exist n traffic flows in the network. Each node can also serve as a potential relay to forward data for other n-2 traffic flows. We assume that, for the traffic flow originated at each node, it has an arrival rate of λ (packets/slot) at the beginning of each time slot and that one code block is transmitted at each successful data transmission.


### 2.2. Performance Metric

#### 2.2.1. Maximum Throughput

A traffic arrival rateλ (packets/slot) is called feasible or achievable under our routing scheme in the considered network, if the queue length of each node under the arrival rate does not grow to infinity as the time tends to infinity. The maximum throughput is then defined as the maximum feasible arrival rate λ.


## 2.1. System Models

### 2.1.1. Network Model

We consider a mobile ad hoc network composed ofn nodes moving on a unit square region, opposite edges of which touch each other so as to avoid border effects. As shown in Figure 1, similar to previous work [6, 11–14], the network region is uniformly partitioned into m×m cells.Figure 1
Network model and MAC protocol.


### 2.1.2. Mobility Model

The node movements in the network follow the independent and identically distributed (i.i.d.) mobility model widely adopted in [6, 11–14], where time is divided into slots of equal duration and at the beginning of each time slot, each node moves into a cell selected from the m2 cells with equal probability and remains in it for the entire time slot.


### 2.1.3. Communication Model

We adopt a commonly usedprotocol model [13, 14] to avoid interference among simultaneous data transmissions. According to theprotocol model, each node (e.g., S1 in Figure 1) employs a fixed transmission range covering the cell it resides in and its eight neighbor cells. Let d(i,j) denote the Euclidean distance between node i and node j, and then node j can successfully receive data from node i if and only if the following condition holds: d(k,j)≥(1+Δ)d(i,j) for each other node k (k≠i) simultaneously sending, where Δ is a positive integer.


### 2.1.4. Traffic Model

Similar to [15], we consider a permutation traffic model where each node is source of one traffic flow and destination of another traffic flow. Thus, there exist n traffic flows in the network. Each node can also serve as a potential relay to forward data for other n-2 traffic flows. We assume that, for the traffic flow originated at each node, it has an arrival rate of λ (packets/slot) at the beginning of each time slot and that one code block is transmitted at each successful data transmission.


## 2.1.1. Network Model

We consider a mobile ad hoc network composed ofn nodes moving on a unit square region, opposite edges of which touch each other so as to avoid border effects. As shown in Figure 1, similar to previous work [6, 11–14], the network region is uniformly partitioned into m×m cells.Figure 1
Network model and MAC protocol.


## 2.1.2. Mobility Model

The node movements in the network follow the independent and identically distributed (i.i.d.) mobility model widely adopted in [6, 11–14], where time is divided into slots of equal duration and at the beginning of each time slot, each node moves into a cell selected from the m2 cells with equal probability and remains in it for the entire time slot.


## 2.1.3. Communication Model

We adopt a commonly usedprotocol model [13, 14] to avoid interference among simultaneous data transmissions. According to theprotocol model, each node (e.g., S1 in Figure 1) employs a fixed transmission range covering the cell it resides in and its eight neighbor cells. Let d(i,j) denote the Euclidean distance between node i and node j, and then node j can successfully receive data from node i if and only if the following condition holds: d(k,j)≥(1+Δ)d(i,j) for each other node k (k≠i) simultaneously sending, where Δ is a positive integer.


## 2.1.4. Traffic Model

Similar to [15], we consider a permutation traffic model where each node is source of one traffic flow and destination of another traffic flow. Thus, there exist n traffic flows in the network. Each node can also serve as a potential relay to forward data for other n-2 traffic flows. We assume that, for the traffic flow originated at each node, it has an arrival rate of λ (packets/slot) at the beginning of each time slot and that one code block is transmitted at each successful data transmission.


## 2.2. Performance Metric

### 2.2.1. Maximum Throughput

A traffic arrival rateλ (packets/slot) is called feasible or achievable under our routing scheme in the considered network, if the queue length of each node under the arrival rate does not grow to infinity as the time tends to infinity. The maximum throughput is then defined as the maximum feasible arrival rate λ.


## 2.2.1. Maximum Throughput

A traffic arrival rateλ (packets/slot) is called feasible or achievable under our routing scheme in the considered network, if the queue length of each node under the arrival rate does not grow to infinity as the time tends to infinity. The maximum throughput is then defined as the maximum feasible arrival rate λ.


## 3. MAC Protocol and Routing Scheme with Reed-Solomon Coding

In this section, we first introduce MAC protocol and then present a general routing scheme with reed-solomon coding.


### 3.1. MAC Protocol

To ensure as many simultaneous data transmissions as possible over a shared channel without interfering with each other, we adopt an equivalent-class based MAC protocol [13, 16] for transmission scheduling. An equivalent-class is defined as the set of cells (e.g., as shown in Figure 1, all cells marked by dark gray color are located in the same equivalent-class), where a cell is separated from another cell at a distance of integer multiple of α cells in the horizontal and vertical directions, respectively. Thus, there are α2 distinct equivalent-classes covering all cells in the network. Notice that each equivalent-class will alternately become an active one at each α2 time slot, and each cell (also called active cell) in the active equivalent-class allows at most one node in it to execute data transmission at the time slot.The parameterα should be determined appropriately as follows. As shown in Figure 1, the maximum transmission distance r between a transmitter S1 and its possible receiver R1 is 22/m. For a transmission between them to be successful, the distance between R1 and another possible closest simultaneously sending node S2, that is, (α-2)/m, should meet the following condition according to theprotocol model [13, 14]: (α-2)/m≥(1+Δ)r. Since α≤m, we have α=min⁡{1+Δ22+2,m}, where · is the ceiling function.


### 3.2.  Routing Scheme with Reed-Solomon Coding

We consider a general two-hop relay routing with reed-solomon coding, where a group ofg packets at source node are encoded into w (w≥g) code blocks using reed-solomon coding [10], and then each code block is sent to either relay node or destination node. According to reed-solomon coding, the original g packets can be decoded once destination node receives g code blocks of the group from these relay nodes or source node. For the convenience of analysis, each relay node can only carry at most a code block of each group at the same time slot.Without loss of generality, we study a specific traffic flow and denote its source and destination byS and D, respectively. Each packet group at source S is assigned a unique group number SN(g), and destination D also assigns each packet group it is currently requesting a unique group number RN(g). For the traffic model, we notice that each node also acts as a relay for other n-2 traffic flows; thus each node maintains n-1 queues at its buffer, where one input queue stores packet groups locally generated by itself and waiting to be transmitted, and other n-2 relay queues store coded blocks from source nodes of other n-2 traffic flows (one queue per traffic flow).We now introduce the two-hop relay routing with reed-solomon coding. WhenS gets a transmission opportunity at current time slot according to the MAC protocol, it conducts the following operations.Step 1 (source-to-destination).
For the case whereD is in the transmission range of S, S initiates a handshake with D to check which group number RN(g)D is requesting. If SN(g)=RN(g), S sends a code block of current group from its input queue to D directly; else if SN(g)<RN(g), S sends a code block from its input queue with group number SN(g)=SN(g)+1 to D directly; else S stays idle at this time slot. When D has received g code blocks of a group, it decodes the original g packets of the group using reed-solomon coding technique and sets RN(g)=RN(g)+1.Step 2.
For another case whereD is not in the transmission range of S, if there does not exist another node in its transmission range, S stays idle at this time slot. Otherwise, S randomly selects a node, say R, and then performs the following operations with the same probability.(i)
Source-to-Relay: If R has been carrying a code block of current group that S is sending, S stays idle at this time slot. Otherwise, S sends a code block of the group from its input queue to R.(ii)
Relay-to-Destination: S (serving as a relay node) initiates a handshake with R to check which group number RN(g)R is requesting. If S is carrying a code block of the group, it sends a code block of the group from its corresponding relay queue to R. Otherwise, S stays idle at this time slot. When R has received g code blocks of the group, it decodes the original g packets of the group and sets RN(g)=RN(g)+1.It is notable that, under the routing scheme, the destination nodeD begins to receive code blocks of the next group i+1 only after g code blocks of the previous group i have been received.


## 3.1. MAC Protocol

To ensure as many simultaneous data transmissions as possible over a shared channel without interfering with each other, we adopt an equivalent-class based MAC protocol [13, 16] for transmission scheduling. An equivalent-class is defined as the set of cells (e.g., as shown in Figure 1, all cells marked by dark gray color are located in the same equivalent-class), where a cell is separated from another cell at a distance of integer multiple of α cells in the horizontal and vertical directions, respectively. Thus, there are α2 distinct equivalent-classes covering all cells in the network. Notice that each equivalent-class will alternately become an active one at each α2 time slot, and each cell (also called active cell) in the active equivalent-class allows at most one node in it to execute data transmission at the time slot.The parameterα should be determined appropriately as follows. As shown in Figure 1, the maximum transmission distance r between a transmitter S1 and its possible receiver R1 is 22/m. For a transmission between them to be successful, the distance between R1 and another possible closest simultaneously sending node S2, that is, (α-2)/m, should meet the following condition according to theprotocol model [13, 14]: (α-2)/m≥(1+Δ)r. Since α≤m, we have α=min⁡{1+Δ22+2,m}, where · is the ceiling function.


## 3.2.  Routing Scheme with Reed-Solomon Coding

We consider a general two-hop relay routing with reed-solomon coding, where a group ofg packets at source node are encoded into w (w≥g) code blocks using reed-solomon coding [10], and then each code block is sent to either relay node or destination node. According to reed-solomon coding, the original g packets can be decoded once destination node receives g code blocks of the group from these relay nodes or source node. For the convenience of analysis, each relay node can only carry at most a code block of each group at the same time slot.Without loss of generality, we study a specific traffic flow and denote its source and destination byS and D, respectively. Each packet group at source S is assigned a unique group number SN(g), and destination D also assigns each packet group it is currently requesting a unique group number RN(g). For the traffic model, we notice that each node also acts as a relay for other n-2 traffic flows; thus each node maintains n-1 queues at its buffer, where one input queue stores packet groups locally generated by itself and waiting to be transmitted, and other n-2 relay queues store coded blocks from source nodes of other n-2 traffic flows (one queue per traffic flow).We now introduce the two-hop relay routing with reed-solomon coding. WhenS gets a transmission opportunity at current time slot according to the MAC protocol, it conducts the following operations.Step 1 (source-to-destination).
For the case whereD is in the transmission range of S, S initiates a handshake with D to check which group number RN(g)D is requesting. If SN(g)=RN(g), S sends a code block of current group from its input queue to D directly; else if SN(g)<RN(g), S sends a code block from its input queue with group number SN(g)=SN(g)+1 to D directly; else S stays idle at this time slot. When D has received g code blocks of a group, it decodes the original g packets of the group using reed-solomon coding technique and sets RN(g)=RN(g)+1.Step 2.
For another case whereD is not in the transmission range of S, if there does not exist another node in its transmission range, S stays idle at this time slot. Otherwise, S randomly selects a node, say R, and then performs the following operations with the same probability.(i)
Source-to-Relay: If R has been carrying a code block of current group that S is sending, S stays idle at this time slot. Otherwise, S sends a code block of the group from its input queue to R.(ii)
Relay-to-Destination: S (serving as a relay node) initiates a handshake with R to check which group number RN(g)R is requesting. If S is carrying a code block of the group, it sends a code block of the group from its corresponding relay queue to R. Otherwise, S stays idle at this time slot. When R has received g code blocks of the group, it decodes the original g packets of the group and sets RN(g)=RN(g)+1.It is notable that, under the routing scheme, the destination nodeD begins to receive code blocks of the next group i+1 only after g code blocks of the previous group i have been received.


## 4. Markov Chain Models and Maximum Throughput

In this section, we first establish two Markov chain models to depict the fastest packet sending and receiving processes at source and destination nodes and provide some basic results. Based on them we then derive a closed-form expression for the maximum throughput.


### 4.1. Markov Chain Models

For the specific traffic flow and a given packet group, under our routing scheme, the two independent processes, that is, the fastest packet sending process at sourceS and the fastest packet receiving process at destination D, are modeled as two discrete-time absorbing Markov chains as shown in Figures 2(a) and 2(b), respectively. The fastest packet sending process corresponds to the process from the beginning (that S starts to send the first code block of the group and at the same time slot, D also starts to request for the group) to the end (that S finishes sending code blocks of the group), while the fastest packet receiving process corresponds to the process from the beginning (that D starts to request the group after S has already sent out all ω code blocks of the group) to the end (that D has received g code blocks of the group).Figure 2
Two absorbing Markov chains. For each state, the transition back to itself is not plotted for simplicity.
(a)
Absorbing Markov chain for the fastest packet sending process at sourceS
(b)
Absorbing Markov chain for the fastest packet receiving process at destinationDAs shown in Figure2(b), any transient state j denotes that S has sent out all ω code blocks of the group, while D has already received any j  (0≤j<g) code blocks of them; the absorbing state AD denotes that D has already received g code blocks of the group. In each time slot, only RD case (i.e., relay-to-destination transmission) will happen.As shown in Figure2(a), any transient state (i,j) denotes that S is sending the ith (1≤i≤ω) code block, while D has already received j  (0≤j<g,j≤i) code blocks of the group; the absorbing state set AS=a0,a1,…,ag denotes that S finishes the fastest packet sending process for the group. For a general absorbing state at  (0≤t≤g), it indicates that D has already received t code blocks of the group when S finishes the fastest packet sending process.Suppose that, for the Markov chain shown in Figure2(a), the transient state is (i,j) in current time slot; then only one of the following four transmission cases will happen in the next time slot:(i)
SR case: S transmits the ith code block to a relay node that does not carry any code block of the group. Under this case, the state (i,j) may transit to one of the states (i+1,j) when i<ω and aj when i=ω.(ii)
RD case: a relay node transmits a coded block to D. Under this case, the state (i,j) may transit to the state (i,j+1).(iii)
SR + RD case: both the source-to-relay and relay-to-destination cases happen concurrently. Under the case, the state (i,j) may transit to one of the states (i+1,j+1) when i<ω and aj+1 when i=ω.(iv)
SD case: S transmits a coded block directly to D. Under this case, the state (i,j) may transit to one of the states (i+1,j+1) when i<ω and aj+1 when i=ω.


### 4.2. Some Basic Results

Lemma 1.
For the considered traffic flow and a given time slot, letp1 be the probability that S performs a source-to-destination transmission and p2 be the probability that S performs a source-to-destination transmission or a relay-to-destination transmission. Then one has(1)p1=1α29n-m2nn-1-1-1m2n-18n+1-m2nn-1,p2=1α2m2-9n-11-1-1m2n-1-1-9m2n-1.Lemma 2.
For the considered traffic flow and a given packet group, in some time slot, suppose that the source nodeS is sending code blocks of the group, and there are β1 relay nodes each carrying a code block of the group and β2 relay nodes each carrying no code block of the group. In the next time slot, we denote by Pr(β1) the probability that D receives a coded block, denote by Pd(β2) the probability that S successfully transmits a code block to one of these β2 relay nodes, and denote by Ps(β1,β2) the probability that both the source-to-relay and relay-to-destination transmissions are performed concurrently. Then we have(2)Prβ1=p1+β12n-2p2,Pdβ2=β22n-2p2,Psβ1,β2=β1μ2m2-α24m2α4∑k=0n-5n-5kψk·∑t=0n-k-4n-k-4tψt1-18m2n-k-t-4,where(3)ψθ=99/m2θ+1-88/m2θ+1θ+1θ+2.The derivations of these probabilities in Lemmas1 and 2 are similar to those in [17], and please refer to [17] for details.For the Markov chain in Figure2(a), there are in total g rows of transient states, and the jth row has Lj transient states (0≤j≤g-1), where Lj is determined as(4)Lj=ω-j.Consider the lth transient state of the jth row in Figure 2(a), 0≤j≤g-1 and 1≤l≤Lj, we have(5)β1=l-1,β2=n-l-1,where β1 represents the number of relay nodes each carrying a code block of the group and β2 represents the number of relay nodes each carrying no code block of the group.It is notable that, for thelth transient state of the jth row in Figure 2(a), the transmission cases (SR, RD, SR + RD, SD and Self-loop) will happen with probability Pd(β2)-Ps(β1,β2), Pr(β1)-p1-Ps(β1,β2), Ps(β1,β2), p1, and 1-Pd(β2)-Pr(β1)+Ps(β1,β2), respectively.


### 4.3. Maximum Throughput

Letμ(g,ω) denote the maximum throughput under our routing scheme in the considered mobile ad hoc network. Based on these two Markov chain models, we derive a closed-form expression for the maximum throughput in Theorem 3. Before introducing Theorem 3, we first use VS to denote the long-term average packet sending rate at source S and use VD to denote the long-term average packet receiving rate at destination D, where(6)VS=limt→∞the  number  of  sent  packets  atSt,VD=limt→∞the  number  of  received  packets  atDt.Theorem 3.
For the considered mobile ad hoc network, the network can stably support any packet arrival rateλ≤μ(g,ω) under the routing scheme; then we have(7)μg,ω=min⁡ge1·N·e2,g∑i=0g-11/ω-i/2n-2p2,where N represents the fundamental matrix of the Markov chain in Figure 2(a), e1=(1,0,…,0), and e2=(1,1,…,1)T.Proof.
For the considered traffic flow, if the network is stable (i.e., the queue length at each node does not grow to infinity as the time tends to infinity) under the packet arrival rateλ, then we have(8)λ=VS=VD.
This is because, in a stable network, the long-term average rate of the input traffic is equal to that of the output one.
We usetS to denote the fastest packet sending time and use tD to denote the fastest packet receiving time. Thus, tS is the time it takes for the Markov chain in Figure 2(a) to become absorbed starting from the initial state (1,0), and tD is the time it takes for the Markov chain in Figure 2(b) to get absorbed starting from the initial state 0. E{tS} and E{tD} represent their corresponding expected values. Then we have(9)VS≤gEtS,VD≤gEtD.
Based on (8) and (9), we have(10)λ≤min⁡gEtS,gEtD.
Sinceμ(g,ω) is defined as the maximum λ that the network can stably support under our routing scheme, we have(11)μg,ω=min⁡gEtS,gEtD.
To determineμ(g,ω), we need to derive E{tS} and E{tD}. We first derive E{tS}. Let γ denote the total number of transient states in Figure 2(a). We index the γ transient states as 0,1,2,…,γ-1 in a left-to-right and top-to-down fashion.
Based on Markov chain theory, we know thatij-entry of the fundamental matrix N of the Markov chain in Figure 2(a) represents the expected number of times the chain is in the jth transient state until absorption, given that it starts from the ith transient state; thus we have(12)EtS=e1·N·e2,where e1=(1,0,…,0), e2=(1,1,…,1)T, and(13)N=I-Q-1.Here, I is a γ-by-γ identity matrix, and the ij-entry qi,j of matrix Q=(qi,j)γ×γ denotes the transition probability from the ith transient state to the jth transient state.
We now deriveE{tD}. We first index the g+1 states of the Markov chain in Figure 2(b) as 0,1,2,…,g in a left-to-right fashion and then use Xi to denote the time the Markov chain in Figure 2(b) takes to arrive at the absorbing state AD starting from the ith state (0≤i≤g). The corresponding expected value of Xi is denoted by E{Xi}. Since E{tD}=E{X0}, we need to determine E{X0}. Based on the definition of Xi, we have(14)EXi=∑j=0gqi,j′1+EXj=1+∑j=0gqi,j′EXj,where qi,j′ represents the transition probability from the ith state to the jth state in Figure 2(b).
We can see from Figure2(b) that the ith transient state can only transit to either the (i+1)th state or itself in the next time slot, so we have qi,j′=0 if j≠i+1 or j≠i. Since qi,i+1′=1-qi,i′ and E{Xg}=0, by iterating (14), we have(15)EX0=∑i=0g-11qi,i+1′.
We notice that if the Markov chain of Figure2(b) arrives at the ith transient state in current time slot, then there are in total ω-i relay nodes each carrying a code block of the group. In the next time slot, if D receives a code block from one of the ω-i relay nodes, then the Markov chain will arrive at the (i+1)th state. Since these ω-i events are mutually exclusive and the probability that D receives a code block from a relay node is p2/2(n-2), qi,i+1′ follows by summing up the probabilities of these ω-i events.
By substitutingqi,i+1′ into (15), we have(16)EX0=∑i=0g-11ω-i/2n-2p2.Since E{X0}=E{tD} and the transition matrix Q can be easily determined based on those basic results in Section 4.2, E{tD} can be derived.
This finishes the proof of Theorem3.


## 4.1. Markov Chain Models

For the specific traffic flow and a given packet group, under our routing scheme, the two independent processes, that is, the fastest packet sending process at sourceS and the fastest packet receiving process at destination D, are modeled as two discrete-time absorbing Markov chains as shown in Figures 2(a) and 2(b), respectively. The fastest packet sending process corresponds to the process from the beginning (that S starts to send the first code block of the group and at the same time slot, D also starts to request for the group) to the end (that S finishes sending code blocks of the group), while the fastest packet receiving process corresponds to the process from the beginning (that D starts to request the group after S has already sent out all ω code blocks of the group) to the end (that D has received g code blocks of the group).Figure 2
Two absorbing Markov chains. For each state, the transition back to itself is not plotted for simplicity.
(a)
Absorbing Markov chain for the fastest packet sending process at sourceS
(b)
Absorbing Markov chain for the fastest packet receiving process at destinationDAs shown in Figure2(b), any transient state j denotes that S has sent out all ω code blocks of the group, while D has already received any j  (0≤j<g) code blocks of them; the absorbing state AD denotes that D has already received g code blocks of the group. In each time slot, only RD case (i.e., relay-to-destination transmission) will happen.As shown in Figure2(a), any transient state (i,j) denotes that S is sending the ith (1≤i≤ω) code block, while D has already received j  (0≤j<g,j≤i) code blocks of the group; the absorbing state set AS=a0,a1,…,ag denotes that S finishes the fastest packet sending process for the group. For a general absorbing state at  (0≤t≤g), it indicates that D has already received t code blocks of the group when S finishes the fastest packet sending process.Suppose that, for the Markov chain shown in Figure2(a), the transient state is (i,j) in current time slot; then only one of the following four transmission cases will happen in the next time slot:(i)
SR case: S transmits the ith code block to a relay node that does not carry any code block of the group. Under this case, the state (i,j) may transit to one of the states (i+1,j) when i<ω and aj when i=ω.(ii)
RD case: a relay node transmits a coded block to D. Under this case, the state (i,j) may transit to the state (i,j+1).(iii)
SR + RD case: both the source-to-relay and relay-to-destination cases happen concurrently. Under the case, the state (i,j) may transit to one of the states (i+1,j+1) when i<ω and aj+1 when i=ω.(iv)
SD case: S transmits a coded block directly to D. Under this case, the state (i,j) may transit to one of the states (i+1,j+1) when i<ω and aj+1 when i=ω.


## 4.2. Some Basic Results

Lemma 1.
For the considered traffic flow and a given time slot, letp1 be the probability that S performs a source-to-destination transmission and p2 be the probability that S performs a source-to-destination transmission or a relay-to-destination transmission. Then one has(1)p1=1α29n-m2nn-1-1-1m2n-18n+1-m2nn-1,p2=1α2m2-9n-11-1-1m2n-1-1-9m2n-1.Lemma 2.
For the considered traffic flow and a given packet group, in some time slot, suppose that the source nodeS is sending code blocks of the group, and there are β1 relay nodes each carrying a code block of the group and β2 relay nodes each carrying no code block of the group. In the next time slot, we denote by Pr(β1) the probability that D receives a coded block, denote by Pd(β2) the probability that S successfully transmits a code block to one of these β2 relay nodes, and denote by Ps(β1,β2) the probability that both the source-to-relay and relay-to-destination transmissions are performed concurrently. Then we have(2)Prβ1=p1+β12n-2p2,Pdβ2=β22n-2p2,Psβ1,β2=β1μ2m2-α24m2α4∑k=0n-5n-5kψk·∑t=0n-k-4n-k-4tψt1-18m2n-k-t-4,where(3)ψθ=99/m2θ+1-88/m2θ+1θ+1θ+2.The derivations of these probabilities in Lemmas1 and 2 are similar to those in [17], and please refer to [17] for details.For the Markov chain in Figure2(a), there are in total g rows of transient states, and the jth row has Lj transient states (0≤j≤g-1), where Lj is determined as(4)Lj=ω-j.Consider the lth transient state of the jth row in Figure 2(a), 0≤j≤g-1 and 1≤l≤Lj, we have(5)β1=l-1,β2=n-l-1,where β1 represents the number of relay nodes each carrying a code block of the group and β2 represents the number of relay nodes each carrying no code block of the group.It is notable that, for thelth transient state of the jth row in Figure 2(a), the transmission cases (SR, RD, SR + RD, SD and Self-loop) will happen with probability Pd(β2)-Ps(β1,β2), Pr(β1)-p1-Ps(β1,β2), Ps(β1,β2), p1, and 1-Pd(β2)-Pr(β1)+Ps(β1,β2), respectively.


## 4.3. Maximum Throughput

Letμ(g,ω) denote the maximum throughput under our routing scheme in the considered mobile ad hoc network. Based on these two Markov chain models, we derive a closed-form expression for the maximum throughput in Theorem 3. Before introducing Theorem 3, we first use VS to denote the long-term average packet sending rate at source S and use VD to denote the long-term average packet receiving rate at destination D, where(6)VS=limt→∞the  number  of  sent  packets  atSt,VD=limt→∞the  number  of  received  packets  atDt.Theorem 3.
For the considered mobile ad hoc network, the network can stably support any packet arrival rateλ≤μ(g,ω) under the routing scheme; then we have(7)μg,ω=min⁡ge1·N·e2,g∑i=0g-11/ω-i/2n-2p2,where N represents the fundamental matrix of the Markov chain in Figure 2(a), e1=(1,0,…,0), and e2=(1,1,…,1)T.Proof.
For the considered traffic flow, if the network is stable (i.e., the queue length at each node does not grow to infinity as the time tends to infinity) under the packet arrival rateλ, then we have(8)λ=VS=VD.
This is because, in a stable network, the long-term average rate of the input traffic is equal to that of the output one.
We usetS to denote the fastest packet sending time and use tD to denote the fastest packet receiving time. Thus, tS is the time it takes for the Markov chain in Figure 2(a) to become absorbed starting from the initial state (1,0), and tD is the time it takes for the Markov chain in Figure 2(b) to get absorbed starting from the initial state 0. E{tS} and E{tD} represent their corresponding expected values. Then we have(9)VS≤gEtS,VD≤gEtD.
Based on (8) and (9), we have(10)λ≤min⁡gEtS,gEtD.
Sinceμ(g,ω) is defined as the maximum λ that the network can stably support under our routing scheme, we have(11)μg,ω=min⁡gEtS,gEtD.
To determineμ(g,ω), we need to derive E{tS} and E{tD}. We first derive E{tS}. Let γ denote the total number of transient states in Figure 2(a). We index the γ transient states as 0,1,2,…,γ-1 in a left-to-right and top-to-down fashion.
Based on Markov chain theory, we know thatij-entry of the fundamental matrix N of the Markov chain in Figure 2(a) represents the expected number of times the chain is in the jth transient state until absorption, given that it starts from the ith transient state; thus we have(12)EtS=e1·N·e2,where e1=(1,0,…,0), e2=(1,1,…,1)T, and(13)N=I-Q-1.Here, I is a γ-by-γ identity matrix, and the ij-entry qi,j of matrix Q=(qi,j)γ×γ denotes the transition probability from the ith transient state to the jth transient state.
We now deriveE{tD}. We first index the g+1 states of the Markov chain in Figure 2(b) as 0,1,2,…,g in a left-to-right fashion and then use Xi to denote the time the Markov chain in Figure 2(b) takes to arrive at the absorbing state AD starting from the ith state (0≤i≤g). The corresponding expected value of Xi is denoted by E{Xi}. Since E{tD}=E{X0}, we need to determine E{X0}. Based on the definition of Xi, we have(14)EXi=∑j=0gqi,j′1+EXj=1+∑j=0gqi,j′EXj,where qi,j′ represents the transition probability from the ith state to the jth state in Figure 2(b).
We can see from Figure2(b) that the ith transient state can only transit to either the (i+1)th state or itself in the next time slot, so we have qi,j′=0 if j≠i+1 or j≠i. Since qi,i+1′=1-qi,i′ and E{Xg}=0, by iterating (14), we have(15)EX0=∑i=0g-11qi,i+1′.
We notice that if the Markov chain of Figure2(b) arrives at the ith transient state in current time slot, then there are in total ω-i relay nodes each carrying a code block of the group. In the next time slot, if D receives a code block from one of the ω-i relay nodes, then the Markov chain will arrive at the (i+1)th state. Since these ω-i events are mutually exclusive and the probability that D receives a code block from a relay node is p2/2(n-2), qi,i+1′ follows by summing up the probabilities of these ω-i events.
By substitutingqi,i+1′ into (15), we have(16)EX0=∑i=0g-11ω-i/2n-2p2.Since E{X0}=E{tD} and the transition matrix Q can be easily determined based on those basic results in Section 4.2, E{tD} can be derived.
This finishes the proof of Theorem3.


## 5. Numerical Results

In this section, we first provide simulation results to validate the accuracy of the theoretical model for the maximum throughput and then apply the theoretical model to explore the maximum throughput performance of mobile ad hoc networks.


### 5.1. Simulation Setting

To validate the accuracy of theoretical maximum throughput, a simulator was designed to simulate the packet delivery process under the considered routing scheme. The guard factorΔ is set to 1 here and hence the MAC protocol is defined with α=min⁡8,m. In addition to the i.i.d. mobility model, we also implemented the following two popular mobility models.Random Walk Model [17]. At the beginning of each time slot, each node either moves to one of its eight neighbor cells or stays inside its current cell with an equal probability of 1/9.Random Waypoint Model [18]. At the beginning of each time slot, each node selects two values, dx and dy, uniformly from [1/m,3/m]. The node then moves a horizontal distance of dx and a vertical distance of dy.


### 5.2. Model Validation

Extensive simulations were performed to validate the accuracy of theoretical model for maximum throughput. We presented the simulation results here under two network scenarios ((n=100, m=8, g=3, and ω=7) and (n=200, m=16, g=4, and ω=9)). Given that the system load ρ=λ/μ(g,ω) varies from 0.1 to 1.4, the simulation results and theoretical ones were summarized in Figure 3. We can see from Figure 3 that, for the two network scenarios there under i.i.d. mobility model, the throughput linearly increases as ρ increases from 0.1 to 1 and then approaches the maximum throughput of 1.12×10-3 and 5.34×10-4 in Figures 3(a) and 3(b), respectively, as ρ further increases beyond 1, which means that the maximum throughput results determined according to Theorem 3 agree so well with the simulation ones.Figure 3
Throughput versus system loadρ.
(a)
The throughput for network scenario (n=100, m=8, g=3, and ω=7)
(b)
The throughput for network scenario (n=200, m=16, g=4, and ω=9)Another interesting observation from Figures3(a) and 3(b) is that, for the two network scenarios there, the networks under the random walk model and random waypoint model have very similar throughput as that under the i.i.d. mobility model. This shows that our theoretical model, though derived for the maximum throughput under the i.i.d. mobility model, can also capture the maximum throughput under those two mobility models.


### 5.3. Performance Analysis

Based on our theoretical model for maximum throughput, we first explore the impact of number of code blocksw on the maximum throughput. We summarize in Figure 4 how the maximum throughput μ(g,ω) varies with w in a network with n=300, m=16, and g=3,4,5. It is observed from Figure 4 that, as w increases, μ(g,ω) first increases and then remains unchanged. This is because, for a group of w code blocks at S, when w is relatively small (i.e., all w code blocks can be sent out before D has received g code blocks), increasing w could increase the number of relay nodes carrying the code blocks and hence improve the maximum throughput; however, when w further increases, all w code blocks cannot be sent out before D receives g code blocks and hence increasing w could not improve the maximum throughput. Furthermore, we can see from Figure 4 that, for each given w, the bigger the number of original packets g in a group, the smaller the maximum throughput (i.e., the slower D receives g code blocks of the group).Figure 4
μ
(
g
,
ω
) versus ω.To understand the impact of number of original packetsg on the maximum throughput, we summarize in Figure 5 how μ(g,ω) varies with g in a network with n=200, ω=40, and m=8,16,24. As observed from Figure 5, μ(g,ω) decreases as g increases. It can be explained as follows: for given ω, as g increases, the time that destination D takes to receive g code blocks becomes longer, which decreases the maximum throughput.Figure 5
μ
(
g
,
ω
) versus g.Finally, we explore the impact of number of nodesn on the maximum throughput μ(g,ω). Figure 6 shows how μ(g,ω) varies with n, given that m=16, g=3, and ω=5,8,11. It can be seen from Figure 6 that, for each setting of ω there, as n increases, the maximum throughput μ(g,ω) first increases and then decreases. Therefore, we can determine a most suitable number of nodes to maximize the maximum throughput μ(g,ω). The reasons for such phenomenon are twofold. On one hand, when the network is relatively sparse, increasing n could increase packet transmission opportunity and thus improve the maximum throughput. On the other hand, when n continues to increase, the network becomes relatively crowded and the issues of interference and medium contention among nodes start to have a significant negative impact on the network performance, which leads to the decrease of maximum throughput.Figure 6
μ
(
g
,
ω
) versus n.


## 5.1. Simulation Setting

To validate the accuracy of theoretical maximum throughput, a simulator was designed to simulate the packet delivery process under the considered routing scheme. The guard factorΔ is set to 1 here and hence the MAC protocol is defined with α=min⁡8,m. In addition to the i.i.d. mobility model, we also implemented the following two popular mobility models.Random Walk Model [17]. At the beginning of each time slot, each node either moves to one of its eight neighbor cells or stays inside its current cell with an equal probability of 1/9.Random Waypoint Model [18]. At the beginning of each time slot, each node selects two values, dx and dy, uniformly from [1/m,3/m]. The node then moves a horizontal distance of dx and a vertical distance of dy.


## 5.2. Model Validation

Extensive simulations were performed to validate the accuracy of theoretical model for maximum throughput. We presented the simulation results here under two network scenarios ((n=100, m=8, g=3, and ω=7) and (n=200, m=16, g=4, and ω=9)). Given that the system load ρ=λ/μ(g,ω) varies from 0.1 to 1.4, the simulation results and theoretical ones were summarized in Figure 3. We can see from Figure 3 that, for the two network scenarios there under i.i.d. mobility model, the throughput linearly increases as ρ increases from 0.1 to 1 and then approaches the maximum throughput of 1.12×10-3 and 5.34×10-4 in Figures 3(a) and 3(b), respectively, as ρ further increases beyond 1, which means that the maximum throughput results determined according to Theorem 3 agree so well with the simulation ones.Figure 3
Throughput versus system loadρ.
(a)
The throughput for network scenario (n=100, m=8, g=3, and ω=7)
(b)
The throughput for network scenario (n=200, m=16, g=4, and ω=9)Another interesting observation from Figures3(a) and 3(b) is that, for the two network scenarios there, the networks under the random walk model and random waypoint model have very similar throughput as that under the i.i.d. mobility model. This shows that our theoretical model, though derived for the maximum throughput under the i.i.d. mobility model, can also capture the maximum throughput under those two mobility models.


## 5.3. Performance Analysis

Based on our theoretical model for maximum throughput, we first explore the impact of number of code blocksw on the maximum throughput. We summarize in Figure 4 how the maximum throughput μ(g,ω) varies with w in a network with n=300, m=16, and g=3,4,5. It is observed from Figure 4 that, as w increases, μ(g,ω) first increases and then remains unchanged. This is because, for a group of w code blocks at S, when w is relatively small (i.e., all w code blocks can be sent out before D has received g code blocks), increasing w could increase the number of relay nodes carrying the code blocks and hence improve the maximum throughput; however, when w further increases, all w code blocks cannot be sent out before D receives g code blocks and hence increasing w could not improve the maximum throughput. Furthermore, we can see from Figure 4 that, for each given w, the bigger the number of original packets g in a group, the smaller the maximum throughput (i.e., the slower D receives g code blocks of the group).Figure 4
μ
(
g
,
ω
) versus ω.To understand the impact of number of original packetsg on the maximum throughput, we summarize in Figure 5 how μ(g,ω) varies with g in a network with n=200, ω=40, and m=8,16,24. As observed from Figure 5, μ(g,ω) decreases as g increases. It can be explained as follows: for given ω, as g increases, the time that destination D takes to receive g code blocks becomes longer, which decreases the maximum throughput.Figure 5
μ
(
g
,
ω
) versus g.Finally, we explore the impact of number of nodesn on the maximum throughput μ(g,ω). Figure 6 shows how μ(g,ω) varies with n, given that m=16, g=3, and ω=5,8,11. It can be seen from Figure 6 that, for each setting of ω there, as n increases, the maximum throughput μ(g,ω) first increases and then decreases. Therefore, we can determine a most suitable number of nodes to maximize the maximum throughput μ(g,ω). The reasons for such phenomenon are twofold. On one hand, when the network is relatively sparse, increasing n could increase packet transmission opportunity and thus improve the maximum throughput. On the other hand, when n continues to increase, the network becomes relatively crowded and the issues of interference and medium contention among nodes start to have a significant negative impact on the network performance, which leads to the decrease of maximum throughput.Figure 6
μ
(
g
,
ω
) versus n.


## 6. Conclusion

This paper studied the actual maximum throughput performance in mobile ad hoc network under a general routing scheme with reed-solomon coding. The closed-form expression of maximum throughput was derived with the help of the two Markov chain models, which were established to depict the fastest packet sending and receiving processes at source and destination nodes under the routing scheme. Extensive simulations show that our theoretical model can accurately predict the maximum throughput performance in the considered networks. Our findings are that reed-solomon coding technique could increase the maximum throughput of mobile ad hoc networks through sending limited number of code blocks, and also for each considered network, there exists an optimal network size to maximize the maximum throughput of such network.



---

*Source: 361256-2015-08-23.xml*