# Mathematical Modeling and Analysis Methodology for Opportunistic Routing in Wireless Multihop Networks

Authors: Wang Dongyang; Wu Muqing; Lv Bo; Liao Wenxing
Journal: Mathematical Problems in Engineering
 (2015)

---

## Abstract

Modeling the forwarding feature and analyzing the performance theoretically for opportunistic routing in wireless multihop network are of great challenge. To address this issue, a generalized geometric distribution (GGD) is firstly proposed. Based on the GGD, the forwarding probability between any two forwarding candidates could be calculated and it can be proved that the successful delivery rate after several transmissions of forwarding candidates is irrelevant to the priority rule. Then, a discrete-time queuing model is proposed to analyze mean end-to-end delay (MED) of a regular opportunistic routing with the knowledge of the forwarding probability. By deriving the steady-state joint generating function of the queue length distribution, MED for directly connected networks and some special cases of nondirectly connected networks could be ultimately determined. Besides, an approximation approach is proposed to assess MED for the general cases in the nondirectly connected networks. By comparing with a large number of simulation results, the rationality of the analysis is validated. Both the analysis and simulation results show that MED varies with the number of forwarding candidates, especially when it comes to connected networks; MED increases more rapidly than that in nondirectly connected networks with the increase of the number of forwarding candidates.


---

## Body

## 1. Introduction

Recently, opportunistic routing (OR) for wireless multihop networks has drawn much attention due to its robustness in practical dynamic environments with frequent transmission failures. Traditional routing protocols, that is, dynamic source routing (DSR) [1], just rely on a (preselected) single fixed path to deliver packets from a source to a destination; therefore, the performance is easily affected by the wireless link. While in OR a packet can be received independently with a certain successful probability from each forwarding candidate, the OR mainly exploits the inherent broadcast nature of wireless transmission to mitigate the impact of poor wireless links. This feature could guarantee the robustness of the transmission. As a result, OR can cope well with the unreliable and varying link quality that is typical of wireless networks [2].In OR, each forwarding candidate is labeled with a priority which is set according to a certain metric, that is, the distance to the destination. Once a forwarding candidate receives a packet, it would store the packet in the local buffer and then start a timer. If this forwarding candidate receives an acknowledgement from any node with a higher priority before timer elapses, it means that the packet has been forwarded by other nodes. The forwarding candidate will drop this packet from the buffer. Otherwise, the node transmits the packet when the timer elapses [2]. The buffering time, also called the queueing delay, which represents the duration from the time when one packet arrives at the node to the time when this packet is ready to be transmitted, is the major component of mean end-to-end delay (MED).Besides the robustness against communication failures, time efficiency is also of primary importance in wireless multihop networks due to the applications of real-time nature, that is, disaster relief, military operation [3]. It is known that the MED is the most popular criterion for time efficiency. Moreover, the MED is inversely proportional to the average throughput, and the total average throughput can also be obtained by the derivation of MED [4]. For this reason, we strive to find appropriate methodology and model to study the generative mechanism and characterization of the MED in this paper.Modeling the forwarding feature and analyzing the MED theoretically for OR in wireless multihop network are a great challenge. There are several reasons: distributed architecture, varying wireless environment, dynamic topology, and so on. To deal with these issues, we firstly introduce a regular OR, which avoids the interchannel interference by setting different orders of access channel. Then we analyze the queueing delay of OR by dividing the network topology into two categories as shown in Figure1. One of the network topologies is directly connected network in which all the nodes are in the communication range of each other. Another network topology is nondirectly connected network in which not all the nodes could communicate with each other directly. This analysis may be the cornerstone of modeling the MED for OR strategies and could allow us to have a comprehensive understanding about queueing delay features. The main contributions of this paper are summarized as follows.(1)
A new mathematical distribution called generalized geometric distribution (GGD) is proposed to model the forwarding feature of OR in wireless multihop networks.
(2)
A new methodology for analyzing the OR’s MED is proposed. With the knowledge of priority rule and delivery probability, the forwarding probability could be calculated based on GGD. Afterwards, the generating function of the queue length distribution could be derived. According to the property of the multivariate generating function, closed form expressions of MED are derived. These analysis results could be applied to arbitrary directly connected networks and some special nondirectly connected networks.
(3)
An approximate analysis is also developed for the general cases in the nondirectly connected networks. Meanwhile, a large number of simulation studies have been performed. We have observed that analysis results coincide with the experimental data very well.Figure 1
Examples for directly and nondirectly connected networks.The organization of this paper is as follows. The next section summarizes related works. The system model is described in Section3. Section 4 introduces the GGD and some basic definitions. Based on the system model and basic definitions, we analyze the MED for different kinds of networks in Section 5. In Section 6, numerical results and experimental data are presented and discussed. In the last section, we discuss future research directions and conclude the paper.


## 2. Related Works

Since the milestone piece of work in this area was proposed in [5], OR has aroused much concern. A wide range of literature has been proposed recently, that is, [6–16]. References [6–10] emphasized particularly on researching opportunistic algorithms and protocols. In the following part, we only discuss some of the main theoretical achievements.Reference [11] proposed a very general analytical model to describe OR and then derived a closed form expression about the average number of transmissions for successfully delivering a packet to the destination. In [12], the expected transmission count (ETX) of different candidate selection algorithms were profoundly evaluated based on a very useful discrete-time Markov chain. Similarly, a mathematical model was proposed to compute the total number of transmissions of the whole network in [13]. It showed that the main reason behind retransmissions is that forwarder with lower priority is unable to hear the transmission from its neighbor with higher priority. Reference [14] formulated the end-to-end throughput bound as a linear programming problem. Then a heuristic algorithm was proposed to find a feasible scheduling of opportunistic forwarding priorities to achieve the maximum capacity. Considering the link-level interference among the nodes, a closed form expression of maximum achievable throughput was provided for directly connected multihop wireless networks in [15]. Reference [16] mainly focused on calculating the end-to-end energy consumption of each potentially available route for both traditional routing and opportunistic routing. In summary, [11–13] focused on the number of transmissions for successfully delivering a packet to the destination. References [14, 15] provided insights into the system throughput. Reference [16] studied the energy efficiency. These theoretical studies differ from our works.The works which are most related to ours are [4, 17]. Reference [17] was the first paper which analyzed MED by deriving the steady-state joint generating function of the queue length distribution. However, the analysis was limited to the tandem queueing network. Reference [4] analytically derived saturation throughput and MED for an interference aware opportunistic relay selection protocol. Unfortunately, it is only applicable to two- or three-hop networks. Here, our work well modeled the broadcast characteristic of wireless communication in OR and the analysis methodology for OR could be applied in a very general multihop network.


## 3. System Model

We consider that a network consists ofN
+
1 nodes. Node 0 is assumed as the destination and other nodes could transmit fixed-length packets to node 0. The behaviors of all the nodes in the data forwarding are coordinated by an OR protocol. The system operates in the time slotted and synchronized fashion. The time is divided into slots of size corresponding to the transmission time of a packet. A packet arriving during a slot cannot be forwarded before the beginning of the next slot. Each node is regarded as a first come first serve (FCFS) server.The main principles of the forward protocol analyzed in this paper are summarized as follows.(P1)
Forwarding candidates are coordinated based on a priority rule. In this paper, the priorities are set in accordance with the distance to the destination. The shorter the distance to the destination, the higher the priority that would be set for the forwarding candidate. In Figure1, the priorities of the forwarding candidates from node N to node 1 increase in turn. In the viewpoint of implementation, each node could obtain the global knowledge about the priority easily by the forward candidates discovery process as elaborated in [9].
(P2)
Since the nodes share a common radio channel, to avoid the collision, channel access is controlled in accordance with the preassigned priorities. More specifically, a node is allowed to transmit in a given slot only if the nodes with higher priority within its communication range have empty queues.
(P3)
After the upstream node broadcasts a packet, each node within its communication range may hear the packet. To avoid the duplicate transmission, the packet is received and further forwarded by only one node. Current node would drop the packet which would be received by other node with higher priority. That is, a given packet should be received only once by one of the forwarding candidates according to its corresponding priority order from high to low.(P2) and (P3) could be easily implemented when designing a practical OR protocol. Take nondirectly connected network as a general example. Assume that the communication range is two hops for each node in, which means node 3 may only be influenced by nodes{
5,4
,
2,1
}. When receiving a packet from node 4 or node 5, node 3 would not transmit the packet until node 2 and node 1 finish their transmission. What is noteworthy is that node 1 or node 2 may also receive the same packet from node 5 or node 4. If node 3 receives this packet from node 1 and node 2 during its waiting time, it would drop this packet because the packet has been forwarded by nodes with higher priority.In light of the property for multivariate generating function, the steady-state average queue length at nodei is(1)
L
¯
i
=
∂
G
Z
∂
z
i
z
1
=
⋯
=
z
N
=
1
,where G
(
Z
) is the steady-state joint generating function of the queue length distribution and its common definition is (2)
G
Z
=
lim
t
→
+
∞
E
∏
i
=
1
N
‍
z
i
L
i
t
,where we use the notation Z
=
(
z
1
,
z
2
,
…
,
z
N
) and let L
i
(
t
) denote the number of packets at node i at time t. Here, we assume that the Markov chain {
L
i
(
t
)
}
i
=
1
N is ergodic; namely, G
(
0
)
>
0. The normalization condition is G
(
1
,
…
,
1
)
=
1.Letr
i denote the arrival rate of packets at node i. The MED in the system is obtained by applying Little’s law to the whole system and it is given by(3)
D
=
∑
i
=
1
N
‍
L
¯
i
∑
i
=
1
N
‍
r
i
.For convenience, we employ the following notations:(4)
G
j
Z
=
G
z
N
,
…
,
z
j
+
1
,
z
j
,
0
,
…
,
0
,
G
j
1
Z
=
G
z
N
,
…
,
z
j
+
1
,
1,0
,
…
,
0
,where 1
≤
j
≤
N
+
1 and G
N
+
1
(
Z
)
=
G
(
0
,
…
,
0
)
=
G
(
0
).


## 4. Basic Definitions

In this section, the GGD is presented. Based on the GGD, the forwarding probability of OR is calculated. Finally, some other basic definitions for the analysis are presented.


### 4.1. Generalized Geometric Distribution

Definition 1.
Assumed thatN events denoted as {
X
1
,
X
2
,
…
,
X
N
} are mutual independence. The corresponding probability for each event is {
x
1
,
x
2
,
…
,
x
N
}, respectively. Let Y
i
=
⋂
k
=
1
i
-
1
X
¯
k
∩
X
i; namely, the events {
X
1
,
X
2
,
…
,
X
i
-
1
} do not happen but X
i happens. The probability distribution of the events {
Y
1
,
Y
2
,
…
,
Y
N
} is defined as a GGD.Lety
i denote the probability of event Y
i; we have (5)
y
i
=
∏
k
=
1
i
-
1
‍
x
¯
k
x
i
,where x
¯
=
(
1
-
x
) and it could be proved that(6)
0
≤
y
i
≤
1
,
lim
N
→
+
∞
∑
i
=
1
N
‍
y
i
=
1
.The traditional geometric distribution is a specific case of GGD with x
1
=
x
2
=
⋯
=
p and y
i
=
p
¯
i
-
1
p.Theorem 2.
For the events{
X
~
1
,
X
~
2
,
…
,
X
~
N
}, which are obtained through rearranging the events {
X
1
,
X
2
,
…
,
X
N
} according to another metric, one has (7)
∑
i
=
1
N
‍
y
i
=
∑
i
=
1
N
‍
y
~
i
,where {
y
~
1
,
y
~
2
,
…
,
y
~
N
} is the corresponding probability for the reordered events.Proof.
Let us change the order of any adjacent events in a given events set{
X
1
,
…
,
X
i
,
X
i
+
1
,
…
,
X
N
}. We get new events denoted as {
X
1
,
…
,
X
i
+
1
,
X
i
,
…
,
X
N
} with corresponding probability {
…
,
y
~
i
,
y
~
i
+
1
,
…
}. We get(8)
y
i
+
y
i
+
1
=
∏
k
=
1
i
-
1
‍
x
¯
k
x
i
+
x
¯
i
x
i
+
1
=
∏
k
=
1
i
-
1
‍
x
¯
k
x
i
+
1
+
x
¯
i
+
1
x
i
=
y
~
i
+
y
~
i
+
1
.Equation (8) means (7) still exists when changing the order of any adjacent events. Since any reordered events set could be obtained by changing the order of adjacent events in the original events set for several times, Theorem 2 is proved.GGD can be widely used to reveal the radio characteristics of wireless transmission. Specifically,X
i could be the event of the ith transmission between any two nodes and Y
i could be the event that these two nodes have transmitted for i times before being successful. Applying to OR, X
i could be the event that the ith forwarding candidate forwards the packet successfully. If it failed, the (
i
+
1
)th forwarding candidate would forward the packet and so forth. x
i is the delivery ratio decided by the underline propagation model and y
i is the actual forwarding probability.As shown in Figure2, x
i is the delivery ratio from node i to node 0. If the priorities are decided by the distance to the node 0, we have {
x
1
,
x
2
,
x
3
,
x
4
,
x
5
}
=
{
80
%
,
90
%
,
60
%
,
70
%
,
50
%
} and {
y
1
,
y
2
,
y
3
,
y
4
,
y
5
}
=
{
80
%
,
18
%
,
1.2
%
,
0.56
%
,
0.12
%
}. If the priorities are decided by another metric such as the ETX, the higher the delivery to the destination, the higher the priority that would be set for the forwarding candidate. We have {
x
~
1
,
x
~
2
,
x
~
3
,
x
~
4
,
x
~
5
}
=
{
90
%
,
80
%
,
70
%
,
60
%
,
50
%
} and {
y
~
1
,
y
~
2
,
y
~
3
,
y
~
4
,
y
~
5
}
=
{
90
%
,
8
%
,
1.4
%
,
0.36
%
,
0.12
%
}. This result is consistent with (7), which means that the sum of ratio of successful transmission is irrelevant to the order of the transmissions. Because the priorities which control the order of access channel have little impact on the performance of OR in accordance with Theorem 2, the analysis for the involved OR in this paper could be promoted to several other ORs with different priority rules.Figure 2
An example for GGD.


### 4.2. Other Basic Definitions

LetA
i
(
t
) be the number of packets generated at node i in the interval (
t
,
t
+
1
] and its steady-state joint generating function of the input process is expressed as(9)
F
Z
=
lim
t
→
∞
E
∏
i
=
1
N
‍
z
i
A
i
t
.On the basis of the property for multivariate generating function, we have(10)
r
i
=
∂
F
Z
∂
z
i
z
1
=
⋯
=
z
N
=
1
.LetS
i
(
t
) be the number of packets sent out by node i at the beginning of the slot t. Based on (P2), we get(11)
S
i
t
=
I
L
i
t
∏
m
=
i
-
h
i
i
-
1
1
-
I
L
m
t
,where I
(
x
) is a indicator function denoted as(12)
I
x
=
1
,
x
>
0
,
0
,
x
=
0
.And h
i is the number of nodes with higher priorities within node i’s communication range. When h
i
=
1, this network becomes a N-node tandem system where the packets are forwarded hop-by-hop. Generally, the number of forwarding candidates are more than two nodes in OR (h
i
≥
2).The explanation for (11) is that node i could transmit a packet when its own buffer is not empty while the buffers of its neighbors with higher priorities (i
-
h
i
≤
m
≤
i
-
1) are empty.Letp
j
,
i denote the delivery rate from node j to node i. Based on Definition 1, the forwarding probability of a packet that is transmitted from node j to node i is calculated as follows:(13)
p
j
i
=
p
j
,
i
,
i
=
j
-
h
j
,
p
j
,
i
∏
k
=
j
-
h
j
i
-
1
‍
1
-
p
j
,
k
,
j
-
h
j
<
i
≤
j
-
1
,
1
-
∑
i
=
0
j
-
1
‍
p
j
i
,
i
=
j
,
0
,
i
>
j
.The interpretation for (13) is that, for a packet transmitted by the upstream node j, node i is forbidden to receive it unless nodes i
-
1
,
i
-
2
,
…
,
j
-
h
j have not received it successfully.LetR
j
i
(
t
) be a binary-valued variable that takes value 1 if a packet is successfully transmitted from node j to node i during the interval (
t
,
t
+
1
]. R
i
i
(
t
) denotes the fact that the packet is not transmitted successfully to any other nodes during the interval and would be retransmitted in the next slot. The state space of {
R
j
i
(
t
)
}
i
=
0
j is {
1,0
,
…
,
0
,
0,1
,
…
,
0
,
…
,
(
0,0
,
…
,
1
)
} and the corresponding probabilities are p
j
0
,
p
j
1
,
…
,
p
j
j, respectively. For convenience, let us define z
0
≡
1. Thus, for j
=
1,2
,
…
,
N, the steady-state joint generating function of R
j
i
(
t
) is(14)
P
j
=
lim
t
→
+
∞
E
∏
i
=
0
j
‍
z
i
R
j
i
t
=
∑
i
=
0
j
‍
p
j
i
z
i
=
∑
i
=
j
-
h
j
j
‍
p
j
i
z
i
.Using the definitions of A
i
(
t
)
,
S
i
(
t
)
,
R
j
i
(
t
) and L
i
(
t
), it is easy to see that for i
=
1,2
,
…
,
N and t
=
0,1
,
2
,
…
(15)
L
i
t
+
1
=
L
i
t
+
A
i
t
+
∑
j
=
i
i
+
h
i
‍
R
j
i
t
-
S
i
t
.The third term of (15) represents the number of packets received from the neighbor nodes of node i.


## 4.1. Generalized Geometric Distribution

Definition 1.
Assumed thatN events denoted as {
X
1
,
X
2
,
…
,
X
N
} are mutual independence. The corresponding probability for each event is {
x
1
,
x
2
,
…
,
x
N
}, respectively. Let Y
i
=
⋂
k
=
1
i
-
1
X
¯
k
∩
X
i; namely, the events {
X
1
,
X
2
,
…
,
X
i
-
1
} do not happen but X
i happens. The probability distribution of the events {
Y
1
,
Y
2
,
…
,
Y
N
} is defined as a GGD.Lety
i denote the probability of event Y
i; we have (5)
y
i
=
∏
k
=
1
i
-
1
‍
x
¯
k
x
i
,where x
¯
=
(
1
-
x
) and it could be proved that(6)
0
≤
y
i
≤
1
,
lim
N
→
+
∞
∑
i
=
1
N
‍
y
i
=
1
.The traditional geometric distribution is a specific case of GGD with x
1
=
x
2
=
⋯
=
p and y
i
=
p
¯
i
-
1
p.Theorem 2.
For the events{
X
~
1
,
X
~
2
,
…
,
X
~
N
}, which are obtained through rearranging the events {
X
1
,
X
2
,
…
,
X
N
} according to another metric, one has (7)
∑
i
=
1
N
‍
y
i
=
∑
i
=
1
N
‍
y
~
i
,where {
y
~
1
,
y
~
2
,
…
,
y
~
N
} is the corresponding probability for the reordered events.Proof.
Let us change the order of any adjacent events in a given events set{
X
1
,
…
,
X
i
,
X
i
+
1
,
…
,
X
N
}. We get new events denoted as {
X
1
,
…
,
X
i
+
1
,
X
i
,
…
,
X
N
} with corresponding probability {
…
,
y
~
i
,
y
~
i
+
1
,
…
}. We get(8)
y
i
+
y
i
+
1
=
∏
k
=
1
i
-
1
‍
x
¯
k
x
i
+
x
¯
i
x
i
+
1
=
∏
k
=
1
i
-
1
‍
x
¯
k
x
i
+
1
+
x
¯
i
+
1
x
i
=
y
~
i
+
y
~
i
+
1
.Equation (8) means (7) still exists when changing the order of any adjacent events. Since any reordered events set could be obtained by changing the order of adjacent events in the original events set for several times, Theorem 2 is proved.GGD can be widely used to reveal the radio characteristics of wireless transmission. Specifically,X
i could be the event of the ith transmission between any two nodes and Y
i could be the event that these two nodes have transmitted for i times before being successful. Applying to OR, X
i could be the event that the ith forwarding candidate forwards the packet successfully. If it failed, the (
i
+
1
)th forwarding candidate would forward the packet and so forth. x
i is the delivery ratio decided by the underline propagation model and y
i is the actual forwarding probability.As shown in Figure2, x
i is the delivery ratio from node i to node 0. If the priorities are decided by the distance to the node 0, we have {
x
1
,
x
2
,
x
3
,
x
4
,
x
5
}
=
{
80
%
,
90
%
,
60
%
,
70
%
,
50
%
} and {
y
1
,
y
2
,
y
3
,
y
4
,
y
5
}
=
{
80
%
,
18
%
,
1.2
%
,
0.56
%
,
0.12
%
}. If the priorities are decided by another metric such as the ETX, the higher the delivery to the destination, the higher the priority that would be set for the forwarding candidate. We have {
x
~
1
,
x
~
2
,
x
~
3
,
x
~
4
,
x
~
5
}
=
{
90
%
,
80
%
,
70
%
,
60
%
,
50
%
} and {
y
~
1
,
y
~
2
,
y
~
3
,
y
~
4
,
y
~
5
}
=
{
90
%
,
8
%
,
1.4
%
,
0.36
%
,
0.12
%
}. This result is consistent with (7), which means that the sum of ratio of successful transmission is irrelevant to the order of the transmissions. Because the priorities which control the order of access channel have little impact on the performance of OR in accordance with Theorem 2, the analysis for the involved OR in this paper could be promoted to several other ORs with different priority rules.Figure 2
An example for GGD.


## 4.2. Other Basic Definitions

LetA
i
(
t
) be the number of packets generated at node i in the interval (
t
,
t
+
1
] and its steady-state joint generating function of the input process is expressed as(9)
F
Z
=
lim
t
→
∞
E
∏
i
=
1
N
‍
z
i
A
i
t
.On the basis of the property for multivariate generating function, we have(10)
r
i
=
∂
F
Z
∂
z
i
z
1
=
⋯
=
z
N
=
1
.LetS
i
(
t
) be the number of packets sent out by node i at the beginning of the slot t. Based on (P2), we get(11)
S
i
t
=
I
L
i
t
∏
m
=
i
-
h
i
i
-
1
1
-
I
L
m
t
,where I
(
x
) is a indicator function denoted as(12)
I
x
=
1
,
x
>
0
,
0
,
x
=
0
.And h
i is the number of nodes with higher priorities within node i’s communication range. When h
i
=
1, this network becomes a N-node tandem system where the packets are forwarded hop-by-hop. Generally, the number of forwarding candidates are more than two nodes in OR (h
i
≥
2).The explanation for (11) is that node i could transmit a packet when its own buffer is not empty while the buffers of its neighbors with higher priorities (i
-
h
i
≤
m
≤
i
-
1) are empty.Letp
j
,
i denote the delivery rate from node j to node i. Based on Definition 1, the forwarding probability of a packet that is transmitted from node j to node i is calculated as follows:(13)
p
j
i
=
p
j
,
i
,
i
=
j
-
h
j
,
p
j
,
i
∏
k
=
j
-
h
j
i
-
1
‍
1
-
p
j
,
k
,
j
-
h
j
<
i
≤
j
-
1
,
1
-
∑
i
=
0
j
-
1
‍
p
j
i
,
i
=
j
,
0
,
i
>
j
.The interpretation for (13) is that, for a packet transmitted by the upstream node j, node i is forbidden to receive it unless nodes i
-
1
,
i
-
2
,
…
,
j
-
h
j have not received it successfully.LetR
j
i
(
t
) be a binary-valued variable that takes value 1 if a packet is successfully transmitted from node j to node i during the interval (
t
,
t
+
1
]. R
i
i
(
t
) denotes the fact that the packet is not transmitted successfully to any other nodes during the interval and would be retransmitted in the next slot. The state space of {
R
j
i
(
t
)
}
i
=
0
j is {
1,0
,
…
,
0
,
0,1
,
…
,
0
,
…
,
(
0,0
,
…
,
1
)
} and the corresponding probabilities are p
j
0
,
p
j
1
,
…
,
p
j
j, respectively. For convenience, let us define z
0
≡
1. Thus, for j
=
1,2
,
…
,
N, the steady-state joint generating function of R
j
i
(
t
) is(14)
P
j
=
lim
t
→
+
∞
E
∏
i
=
0
j
‍
z
i
R
j
i
t
=
∑
i
=
0
j
‍
p
j
i
z
i
=
∑
i
=
j
-
h
j
j
‍
p
j
i
z
i
.Using the definitions of A
i
(
t
)
,
S
i
(
t
)
,
R
j
i
(
t
) and L
i
(
t
), it is easy to see that for i
=
1,2
,
…
,
N and t
=
0,1
,
2
,
…
(15)
L
i
t
+
1
=
L
i
t
+
A
i
t
+
∑
j
=
i
i
+
h
i
‍
R
j
i
t
-
S
i
t
.The third term of (15) represents the number of packets received from the neighbor nodes of node i.


## 5. Analysis

IfG
(
Z
) is determined, MED could be calculated from (3) and (1). In this section we first focus on G
(
Z
) for directly connected networks. Then we analyze that in nondirectly connected networks.


### 5.1. Directly Connected Networks

Based on (2), (4)–(15), and using a standard technique proved in Appendix A, we obtain(16)
G
Z
=
F
Z
∑
j
=
1
N
‍
G
j
Z
-
G
j
+
1
Z
z
j
-
1
P
j
+
G
0
.The term G
j
(
Z
)
-
G
j
+
1
(
Z
) represents the event that the buffer of node j is not empty while the buffers of nodes j
-
1
,
j
-
2
,
…
,
1 are empty and in such a case a packet is transmitted from node j to one of the forwarding candidates or retransmitted by node j as shown in the term P
j.In general, delivery probabilities between any nodes and the generating processes of the packets are known; namely,F
(
Z
) and P
j (calculated based on Definition 1) in (16) are known. Thus, in the following part, we would derive G
(
Z
) through determining G
(
0
) and N
-
1 boundary terms G
j
(
Z
) (2
≤
j
≤
N).


#### 5.1.1. Determination of the ConstantG
(
0
)

Fori
=
1,2
,
…
,
N, by substituting z
k
=
1
(
1
≤
k
≤
N
,
k
≠
i
), let z
i approach 1 in (16); then using the normalization condition G
(
1
,
…
,
1
)
=
1, we obtain N linear equations with the N constants G
j
(
1
)
=
G
j
(
Z
)
z
j
=
1
,
…
,
z
N
=
1.Fori
=
1, we get (17)
G
2
1
p
2
1
+
1
-
p
1
1
-
G
0
p
N
1
+
∑
j
=
3
N
‍
G
j
1
p
j
1
-
p
j
-
1
1
+
p
1
1
+
r
1
-
1
=
0
.For2
≤
i
≤
N
-
1, we get(18)
G
i
1
p
i
i
-
1
+
G
i
+
1
1
p
i
+
1
i
-
p
i
i
+
1
-
G
0
p
N
i
+
∑
j
=
i
+
2
N
‍
G
j
1
p
j
i
-
p
j
-
1
i
+
r
i
=
0
.Fori
=
N, we get(19)
G
N
1
-
G
0
p
N
N
-
1
+
r
N
=
0
.Solving these N equations, we obtain(20)
G
0
=
1
-
∑
i
=
1
N
‍
λ
i
,where λ
i
=
r
i
+
∑
k
=
i
N
p
k
i
λ
k.


#### 5.1.2. Determination of theN
-
1 Boundary Terms G
j
(
Z
)

Note thatG
(
Z
)
=
G
1
(
Z
), G
N
+
1
(
Z
)
=
G
(
0
). For convenience, by the definition of z
N
+
1
-
1
P
N
+
1
≡
1, (16) can be changed to (21)
G
Z
F
Z
z
1
-
1
P
1
-
1
+
F
Z
∑
j
=
2
N
+
1
‍
G
j
Z
z
j
-
1
P
j
-
z
j
-
1
-
1
P
j
-
1
=
0
.Here we first solve the boundary term G
N
(
Z
). Applying Rouche’s theorem, we can prove that, for given z
N with z
N
<
1, the equations shown in (22) have a unique solution over z
1
,
z
2
,
…
,
z
N
-
1 in the unit circles z
1
<
1
,
z
2
<
1
,
…
,
z
N
-
1
<
1. Let z
^
1
=
f
1
(
z
N
)
,
z
^
2
=
f
2
(
z
N
)
,
…
,
z
^
N
-
1
=
f
N
-
1
(
z
N
) denote the unique solution. Consider(22)
F
Z
z
k
-
1
P
k
=
1
,
k
=
1,2
,
…
,
N
-
1
.By substituting (22) and the solution in (21), we obtain(23)
G
N
Z
N
-
1
=
G
0
1
-
z
N
-
1
P
N
z
N
-
1
-
1
P
N
-
1
-
z
N
-
1
P
N
z
1
=
z
^
1
,
…
,
z
N
-
1
=
z
^
N
-
1
,where Z
N
-
1
=
(
z
^
1
,
…
,
z
^
N
-
1
,
z
N
). Since G
(
0
) has already been obtained in (20), we obtain G
N
(
Z
) as shown in (23).Similarly, we discussG
m
(
Z
) for 2
≤
m
≤
N
-
1. For given z
i, m
≤
i
≤
N with z
i
<
1; solving the m
-
1 equations F
(
Z
)
z
k
-
1
P
k
=
1 for 1
≤
k
≤
m
-
1 over z
1
,
z
2
,
…
,
z
m
-
1, we get the unique solution denoted as z
^
1
=
g
1
(
z
m
,
…
,
z
N
)
,
z
^
2
=
g
2
(
z
m
,
…
,
z
N
)
,
…
,
z
^
m
-
1
=
g
m
-
1
(
z
m
,
…
,
z
N
) in the unit circles z
1
<
1
,
z
2
<
1
,
…
,
z
m
-
1
<
1.By substitutingF
(
Z
)
z
k
-
1
P
k
=
1 and the solution in (21), we have (24)
G
m
Z
m
-
1
=
∑
j
=
m
+
1
N
+
1
‍
G
j
Z
z
j
-
1
P
j
-
z
j
-
1
-
1
P
j
-
1
z
m
-
1
-
1
P
m
-
1
-
z
m
-
1
P
m
z
1
=
z
^
1
,
…
,
z
m
-
1
=
z
^
m
-
1
,where Z
m
-
1
=
(
z
^
1
,
…
,
z
^
m
-
1
,
z
m
,
…
,
z
N
).SinceG
N
(
Z
N
-
1
) has already been obtained in (23), we can get G
N
-
1
(
Z
N
-
2
) for m
=
N
-
1 in (24). In the same way, by backward recursive substitution of G
k
(
Z
) for k
=
N
,
N
-
1
,
…
,
m
+
1 in (24), we could obtain G
m
(
Z
m
-
1
).Given all the boundary terms, the joint generating functionG
(
Z
) is uniquely determined. Recalling the derivation, it is observed that G
(
Z
) is mainly determined by the priority rule and delivery probability.


### 5.2. Nondirectly Connected Networks

In this kind of networks, the analysis becomes quite complex because nodei and node i
+
h
i may succeed in their transmissions simultaneously. To simplify the analysis, we assume that it is a linear network, the packets are only generated at node N, and all the nodes have the same communication range denoted as h hops.In the following part, we first study MED for the caseN
=
h
+
2 shown in Figure 3. Then, we propose an approximate analysis for MED in the general scene with N
>
h
+
2. The motivation for considering such a special case is threefold. Firstly, for the cases N
≤
h
+
1, nodes N
,
N
-
1
,
…
,
2,1, which are already analyzed in Section 5.1, are in the communication range of each other. Secondly, it is the simplest nondirectly connected networks in which channel could be reused (node N and node 1 may succeed in their transmissions simultaneously if the other nodes are silent). Thirdly, it will serve us as a crucial building stone in developing our approximate analysis of general nondirectly connected networks.Figure 3
Approximate analysis in nondirectly connected networks.


#### 5.2.1. Special Networks withN
=
h
+
2

Theorem 3.
ForN
=
h
+
2, the steady-state joint generating function of the queue length distribution is(25)
G
Z
=
F
Z
∑
j
=
1
N
-
1
‍
G
j
1
Z
-
G
j
+
1
Z
P
j
+
G
0
hhhhhhhhhh
+
G
N
Z
-
G
0
z
N
-
1
P
N
hhhhhhhhhh
+
G
z
N
,
0
,
…
,
0,1
-
G
N
Z
-
G
1
1
0
+
G
0


hhhhhhhhhhh
·
z
N
-
1
P
N
P
1
-
P
1
∑
j
=
1
N
-
1
‍
G
j
1
Z
-
G
j
+
1
Z
P
j
+
G
0
.Proof.
We obtainG
(
Z
) based on Appendix A as follows:(26)
G
Z
=
F
Z
∑
j
=
1
N
‍
G
j
Z
-
G
j
+
1
Z
z
j
-
1
P
j
+
G
0
hhhhhhhh
+
G
z
N
,
0
,
…
,
0,1
-
G
N
Z
hhhhhhhhhhhh
-
G
0
,
…
,
0
,
z
1
+
G
0
hhhhhhhh
·
z
N
-
1
P
N
-
1
z
1
-
1
P
1
∑
j
=
1
N
‍
G
j
Z
-
G
j
+
1
Z
z
j
-
1
P
j
+
G
0
.Compared with (16), an additional event is considered in (26). It is that the buffers of node N and node 1 are not empty while the buffers of other nodes are empty. In such case node N and node 1 transmit simultaneously.
Since nodeN is the sole source, it is easy to see that only node N could have more than one packet at a time instant. Other nodes can have at most one packet at a time. Considering (2), for j
=
1,2
,
…
,
N
-
1, we can define G
(
Z
)
=
f
z
j
+
g where f
,
g are two polynomials consisting of z
1
,
…
,
z
j
-
1
,
z
j
+
1
,
…
,
z
N
-
1
,
z
N
1
,
z
N
2
,
…
,
z
N
+
∞. By setting z
j
=
0,1 in G
(
Z
)
=
f
z
j
+
g, two equations could be established over f and g. By solving the equations, we have(27)
G
Z
=
G
Z
z
j
=
0
+
G
Z
z
j
=
1
-
G
Z
z
j
=
0
z
j
.
Through substitutingz
i
=
0 for i
=
1
,
…
,
j
-
1 in (27), we get(28)
G
j
Z
-
G
j
+
1
Z
=
G
j
1
Z
-
G
j
+
1
Z
z
j
.By substituting (28) into (26), we obtain (25). The proof of theorem is completed.According to (1), by taking a partial derivative of (27) with respect to z
j, we have(29)
L
¯
j
=
1
-
G
Z
z
j
=
0
,
z
i
=
1
(
N
≥
i
≥
1
,
i
≠
j
)
.Considering (29), the average queue length is determined by G
(
1,0
,
1
,
…
,
1
), G
1,1
,
0,1
,
…
,
1
,
…
,
G
(
1
,
…
,
1,0
) which could be obtained by setting z
N
=
1 in G
(
z
N
,
0,1
,
…
,
1
), G
z
N
,
1,0
,
1
,
…
,
1
,
…
,
G
(
z
N
,
1
,
…
,
1,0
). To solve these terms, we would establish equations in two steps.Firstly, to simplify (25), we assume that G
1
1
(
0
)
=
α
G
(
0
). α is a constant which is calculated as follows.By substitutingz
1
=
z
2
,
…
,
z
N
=
0 into (25), we get(30)
G
0
1
F
0
-
1
+
∑
j
=
1
h
‍
p
j
0
=
∑
j
=
1
h
‍
G
j
1
0
p
j
0
.Let G
j
1
(
0
)
≈
G
1
1
(
0
) for 2
≤
j
≤
N. We get(31)
α
=
1
F
0
∑
j
=
1
h
‍
p
j
0
-
1
∑
j
=
1
h
‍
p
j
0
+
1
.This approximation is reasonable. The explanation is that, forF
(
0
) close to 1, G
j
1
(
0
) (G
j
1
(
0
)
=
P
{
L
j
(
t
)
=
1
,
L
i
(
t
)
=
0
} for i
≠
j) is close to G
(
0
) (G
(
0
)
=
P
{
L
1
t
=
L
2
t
=
⋯
=
L
N
(
t
)
=
0
}). The accuracy of the approximation is demonstrated with simulation in Section 6. Thus (25) is simplified to(32)
1
F
Z
G
Z
-
∑
j
=
1
N
-
1
‍
P
j
G
j
1
Z
+
∑
j
=
2
N
-
1
‍
P
j
-
1
G
j
Z
+
P
1
1
-
z
N
-
1
P
N
G
z
N
,
0
,
…
,
0,1
+
z
N
-
1
P
N
P
1
-
1
-
P
1
+
P
N
-
1
G
N
Z
=
1
+
α
-
1
P
1
1
-
z
N
-
1
P
N
G
0
.Secondly, by setting (
z
N
-
1
,
…
,
z
1
)
=
(
{
0,1
}
,
…
,
{
0,1
}
) in (32), we obtain A
M
×
M
X
M
×
1
=
G
(
0
)
B
M
×
1 which shown as follows:(33)
X
=
G
z
N
,
0
,
…
,
0
G
z
N
,
0
,
…
,
1
⋯
G
z
N
,
1
,
…
,
1
,
B
=
B
z
N
,
0
,
…
,
0
B
z
N
,
0
,
…
,
1
⋯
B
z
N
,
1
,
…
,
1
,where M
=
2
N
-
1, A is the coefficient matrix of the linear equations, and B
(
z
N
,
…
,
z
1
)
=
(
1
+
(
α
-
1
)
P
1
)
(
1
-
z
N
-
1
P
N
). Obviously, if G
(
0
) is determined, we could solve the linear equations.Based on Cramer’s rule, letA
=
A
1
,
…
,
A
M and we obtain(34)
G
z
N
,
1
,
…
,
1
=
G
0
A
1
,
…
,
A
M
-
1
,
B
A
.Note that the determinant ofA denoted as A is a function of z
N. It can be proved that A
=
0 for z
N
=
1. Thus, based on (34), G
(
1
,
…
,
1
)
=
1, and l’Hopital’s rule, we obtain(35)
G
0
=
lim
z
N
→
1
⁡
A
A
1
,
…
,
A
M
-
1
,
B
=
∂
A
/
∂
z
N
∂
A
1
,
…
,
A
M
-
1
,
B
/
∂
z
N
z
N
=
1
.After G
(
0
) is obtained, we solve the equations as follows:(36)
G
z
N
,
1
,
…
,
0
,
…
,
1
=
G
0
A
1
,
…
,
B
,
…
,
A
M
A
,
G
z
N
,
1
,
…
,
1
=
G
0
A
1
,
…
,
A
M
-
1
,
B
A
.Based on l’Hopital’s rule, we get (37)
G
1,1
,
…
,
0
,
…
,
1
=
G
0
A
1
,
…
,
B
,
…
,
A
M
/
∂
z
N
∂
A
/
∂
z
N
z
N
=
1
,
∂
G
z
N
,
1
,
…
,
1
∂
z
N
z
N
=
1
=
G
0
∂
A
1
,
…
,
A
M
-
1
,
B
/
A
∂
z
N
z
N
=
1
.By substituting (29) and (36) into (1), the MED is obtained.


#### 5.2.2. General Networks withN
>
h
+
2

As mentioned above, it is very difficult to calculate the MED in the scene withN
>
h
+
2 since many nodes may succeed in their transmissions simultaneously. To circumvent this difficulty, we propose here an approximate analysis method.The rationale behind the proposed approximation is that for approximating the behavior of a node, it might suffice to consider the behavior of a substitute node which has a similar communication environment like that of the analyzed node. The behavior of a node in the general scene (N
>
h
+
2) can be approximated as the behavior of substitute node in the special scene (N
=
h
+
2) in Figure 2. If nodes N
-
h
-
2
,
N
-
h
-
3
,
…
,
0 are approximated as a destination node, nodes N, N
-
1
,
…
,
N
-
h
-
1 in the general case have the similar behaviors of the substitute nodes h
+
2, h
+
1
,
…
,
1 in the special case. Assume that the corresponding transmission probabilities P
j between the substitute nodes in the special scene is the same as that in the general scene; we get(38)
t
N
g
=
t
h
+
2
s
,
t
N
-
1
g
=
t
h
+
1
s
,
…
,
t
N
-
h
-
1
s
=
t
1
s
,where t
j
g, t
j
s denote queueing delay of node j in the general scene and special scene, respectively.Similarly, the upstream nodesN
,
…
,
N
-
h
-
1 could be approximated as a source node and the downstream nodes N
-
2
h
-
3
,
…
,
0 could be approximated as a destination node. Then, by substituting the corresponding transmission probabilities, we get(39)
t
N
-
h
-
2
g
=
t
h
+
1
s
,
t
N
-
h
-
3
g
=
t
h
s
,
…
,
t
N
-
2
h
-
3
g
=
t
1
s
.Thus, the queueing delay of each node in general scene could be obtained by using our approach iteratively.


## 5.1. Directly Connected Networks

Based on (2), (4)–(15), and using a standard technique proved in Appendix A, we obtain(16)
G
Z
=
F
Z
∑
j
=
1
N
‍
G
j
Z
-
G
j
+
1
Z
z
j
-
1
P
j
+
G
0
.The term G
j
(
Z
)
-
G
j
+
1
(
Z
) represents the event that the buffer of node j is not empty while the buffers of nodes j
-
1
,
j
-
2
,
…
,
1 are empty and in such a case a packet is transmitted from node j to one of the forwarding candidates or retransmitted by node j as shown in the term P
j.In general, delivery probabilities between any nodes and the generating processes of the packets are known; namely,F
(
Z
) and P
j (calculated based on Definition 1) in (16) are known. Thus, in the following part, we would derive G
(
Z
) through determining G
(
0
) and N
-
1 boundary terms G
j
(
Z
) (2
≤
j
≤
N).


### 5.1.1. Determination of the ConstantG
(
0
)

Fori
=
1,2
,
…
,
N, by substituting z
k
=
1
(
1
≤
k
≤
N
,
k
≠
i
), let z
i approach 1 in (16); then using the normalization condition G
(
1
,
…
,
1
)
=
1, we obtain N linear equations with the N constants G
j
(
1
)
=
G
j
(
Z
)
z
j
=
1
,
…
,
z
N
=
1.Fori
=
1, we get (17)
G
2
1
p
2
1
+
1
-
p
1
1
-
G
0
p
N
1
+
∑
j
=
3
N
‍
G
j
1
p
j
1
-
p
j
-
1
1
+
p
1
1
+
r
1
-
1
=
0
.For2
≤
i
≤
N
-
1, we get(18)
G
i
1
p
i
i
-
1
+
G
i
+
1
1
p
i
+
1
i
-
p
i
i
+
1
-
G
0
p
N
i
+
∑
j
=
i
+
2
N
‍
G
j
1
p
j
i
-
p
j
-
1
i
+
r
i
=
0
.Fori
=
N, we get(19)
G
N
1
-
G
0
p
N
N
-
1
+
r
N
=
0
.Solving these N equations, we obtain(20)
G
0
=
1
-
∑
i
=
1
N
‍
λ
i
,where λ
i
=
r
i
+
∑
k
=
i
N
p
k
i
λ
k.


### 5.1.2. Determination of theN
-
1 Boundary Terms G
j
(
Z
)

Note thatG
(
Z
)
=
G
1
(
Z
), G
N
+
1
(
Z
)
=
G
(
0
). For convenience, by the definition of z
N
+
1
-
1
P
N
+
1
≡
1, (16) can be changed to (21)
G
Z
F
Z
z
1
-
1
P
1
-
1
+
F
Z
∑
j
=
2
N
+
1
‍
G
j
Z
z
j
-
1
P
j
-
z
j
-
1
-
1
P
j
-
1
=
0
.Here we first solve the boundary term G
N
(
Z
). Applying Rouche’s theorem, we can prove that, for given z
N with z
N
<
1, the equations shown in (22) have a unique solution over z
1
,
z
2
,
…
,
z
N
-
1 in the unit circles z
1
<
1
,
z
2
<
1
,
…
,
z
N
-
1
<
1. Let z
^
1
=
f
1
(
z
N
)
,
z
^
2
=
f
2
(
z
N
)
,
…
,
z
^
N
-
1
=
f
N
-
1
(
z
N
) denote the unique solution. Consider(22)
F
Z
z
k
-
1
P
k
=
1
,
k
=
1,2
,
…
,
N
-
1
.By substituting (22) and the solution in (21), we obtain(23)
G
N
Z
N
-
1
=
G
0
1
-
z
N
-
1
P
N
z
N
-
1
-
1
P
N
-
1
-
z
N
-
1
P
N
z
1
=
z
^
1
,
…
,
z
N
-
1
=
z
^
N
-
1
,where Z
N
-
1
=
(
z
^
1
,
…
,
z
^
N
-
1
,
z
N
). Since G
(
0
) has already been obtained in (20), we obtain G
N
(
Z
) as shown in (23).Similarly, we discussG
m
(
Z
) for 2
≤
m
≤
N
-
1. For given z
i, m
≤
i
≤
N with z
i
<
1; solving the m
-
1 equations F
(
Z
)
z
k
-
1
P
k
=
1 for 1
≤
k
≤
m
-
1 over z
1
,
z
2
,
…
,
z
m
-
1, we get the unique solution denoted as z
^
1
=
g
1
(
z
m
,
…
,
z
N
)
,
z
^
2
=
g
2
(
z
m
,
…
,
z
N
)
,
…
,
z
^
m
-
1
=
g
m
-
1
(
z
m
,
…
,
z
N
) in the unit circles z
1
<
1
,
z
2
<
1
,
…
,
z
m
-
1
<
1.By substitutingF
(
Z
)
z
k
-
1
P
k
=
1 and the solution in (21), we have (24)
G
m
Z
m
-
1
=
∑
j
=
m
+
1
N
+
1
‍
G
j
Z
z
j
-
1
P
j
-
z
j
-
1
-
1
P
j
-
1
z
m
-
1
-
1
P
m
-
1
-
z
m
-
1
P
m
z
1
=
z
^
1
,
…
,
z
m
-
1
=
z
^
m
-
1
,where Z
m
-
1
=
(
z
^
1
,
…
,
z
^
m
-
1
,
z
m
,
…
,
z
N
).SinceG
N
(
Z
N
-
1
) has already been obtained in (23), we can get G
N
-
1
(
Z
N
-
2
) for m
=
N
-
1 in (24). In the same way, by backward recursive substitution of G
k
(
Z
) for k
=
N
,
N
-
1
,
…
,
m
+
1 in (24), we could obtain G
m
(
Z
m
-
1
).Given all the boundary terms, the joint generating functionG
(
Z
) is uniquely determined. Recalling the derivation, it is observed that G
(
Z
) is mainly determined by the priority rule and delivery probability.


## 5.1.1. Determination of the ConstantG
(
0
)

Fori
=
1,2
,
…
,
N, by substituting z
k
=
1
(
1
≤
k
≤
N
,
k
≠
i
), let z
i approach 1 in (16); then using the normalization condition G
(
1
,
…
,
1
)
=
1, we obtain N linear equations with the N constants G
j
(
1
)
=
G
j
(
Z
)
z
j
=
1
,
…
,
z
N
=
1.Fori
=
1, we get (17)
G
2
1
p
2
1
+
1
-
p
1
1
-
G
0
p
N
1
+
∑
j
=
3
N
‍
G
j
1
p
j
1
-
p
j
-
1
1
+
p
1
1
+
r
1
-
1
=
0
.For2
≤
i
≤
N
-
1, we get(18)
G
i
1
p
i
i
-
1
+
G
i
+
1
1
p
i
+
1
i
-
p
i
i
+
1
-
G
0
p
N
i
+
∑
j
=
i
+
2
N
‍
G
j
1
p
j
i
-
p
j
-
1
i
+
r
i
=
0
.Fori
=
N, we get(19)
G
N
1
-
G
0
p
N
N
-
1
+
r
N
=
0
.Solving these N equations, we obtain(20)
G
0
=
1
-
∑
i
=
1
N
‍
λ
i
,where λ
i
=
r
i
+
∑
k
=
i
N
p
k
i
λ
k.


## 5.1.2. Determination of theN
-
1 Boundary Terms G
j
(
Z
)

Note thatG
(
Z
)
=
G
1
(
Z
), G
N
+
1
(
Z
)
=
G
(
0
). For convenience, by the definition of z
N
+
1
-
1
P
N
+
1
≡
1, (16) can be changed to (21)
G
Z
F
Z
z
1
-
1
P
1
-
1
+
F
Z
∑
j
=
2
N
+
1
‍
G
j
Z
z
j
-
1
P
j
-
z
j
-
1
-
1
P
j
-
1
=
0
.Here we first solve the boundary term G
N
(
Z
). Applying Rouche’s theorem, we can prove that, for given z
N with z
N
<
1, the equations shown in (22) have a unique solution over z
1
,
z
2
,
…
,
z
N
-
1 in the unit circles z
1
<
1
,
z
2
<
1
,
…
,
z
N
-
1
<
1. Let z
^
1
=
f
1
(
z
N
)
,
z
^
2
=
f
2
(
z
N
)
,
…
,
z
^
N
-
1
=
f
N
-
1
(
z
N
) denote the unique solution. Consider(22)
F
Z
z
k
-
1
P
k
=
1
,
k
=
1,2
,
…
,
N
-
1
.By substituting (22) and the solution in (21), we obtain(23)
G
N
Z
N
-
1
=
G
0
1
-
z
N
-
1
P
N
z
N
-
1
-
1
P
N
-
1
-
z
N
-
1
P
N
z
1
=
z
^
1
,
…
,
z
N
-
1
=
z
^
N
-
1
,where Z
N
-
1
=
(
z
^
1
,
…
,
z
^
N
-
1
,
z
N
). Since G
(
0
) has already been obtained in (20), we obtain G
N
(
Z
) as shown in (23).Similarly, we discussG
m
(
Z
) for 2
≤
m
≤
N
-
1. For given z
i, m
≤
i
≤
N with z
i
<
1; solving the m
-
1 equations F
(
Z
)
z
k
-
1
P
k
=
1 for 1
≤
k
≤
m
-
1 over z
1
,
z
2
,
…
,
z
m
-
1, we get the unique solution denoted as z
^
1
=
g
1
(
z
m
,
…
,
z
N
)
,
z
^
2
=
g
2
(
z
m
,
…
,
z
N
)
,
…
,
z
^
m
-
1
=
g
m
-
1
(
z
m
,
…
,
z
N
) in the unit circles z
1
<
1
,
z
2
<
1
,
…
,
z
m
-
1
<
1.By substitutingF
(
Z
)
z
k
-
1
P
k
=
1 and the solution in (21), we have (24)
G
m
Z
m
-
1
=
∑
j
=
m
+
1
N
+
1
‍
G
j
Z
z
j
-
1
P
j
-
z
j
-
1
-
1
P
j
-
1
z
m
-
1
-
1
P
m
-
1
-
z
m
-
1
P
m
z
1
=
z
^
1
,
…
,
z
m
-
1
=
z
^
m
-
1
,where Z
m
-
1
=
(
z
^
1
,
…
,
z
^
m
-
1
,
z
m
,
…
,
z
N
).SinceG
N
(
Z
N
-
1
) has already been obtained in (23), we can get G
N
-
1
(
Z
N
-
2
) for m
=
N
-
1 in (24). In the same way, by backward recursive substitution of G
k
(
Z
) for k
=
N
,
N
-
1
,
…
,
m
+
1 in (24), we could obtain G
m
(
Z
m
-
1
).Given all the boundary terms, the joint generating functionG
(
Z
) is uniquely determined. Recalling the derivation, it is observed that G
(
Z
) is mainly determined by the priority rule and delivery probability.


## 5.2. Nondirectly Connected Networks

In this kind of networks, the analysis becomes quite complex because nodei and node i
+
h
i may succeed in their transmissions simultaneously. To simplify the analysis, we assume that it is a linear network, the packets are only generated at node N, and all the nodes have the same communication range denoted as h hops.In the following part, we first study MED for the caseN
=
h
+
2 shown in Figure 3. Then, we propose an approximate analysis for MED in the general scene with N
>
h
+
2. The motivation for considering such a special case is threefold. Firstly, for the cases N
≤
h
+
1, nodes N
,
N
-
1
,
…
,
2,1, which are already analyzed in Section 5.1, are in the communication range of each other. Secondly, it is the simplest nondirectly connected networks in which channel could be reused (node N and node 1 may succeed in their transmissions simultaneously if the other nodes are silent). Thirdly, it will serve us as a crucial building stone in developing our approximate analysis of general nondirectly connected networks.Figure 3
Approximate analysis in nondirectly connected networks.


### 5.2.1. Special Networks withN
=
h
+
2

Theorem 3.
ForN
=
h
+
2, the steady-state joint generating function of the queue length distribution is(25)
G
Z
=
F
Z
∑
j
=
1
N
-
1
‍
G
j
1
Z
-
G
j
+
1
Z
P
j
+
G
0
hhhhhhhhhh
+
G
N
Z
-
G
0
z
N
-
1
P
N
hhhhhhhhhh
+
G
z
N
,
0
,
…
,
0,1
-
G
N
Z
-
G
1
1
0
+
G
0


hhhhhhhhhhh
·
z
N
-
1
P
N
P
1
-
P
1
∑
j
=
1
N
-
1
‍
G
j
1
Z
-
G
j
+
1
Z
P
j
+
G
0
.Proof.
We obtainG
(
Z
) based on Appendix A as follows:(26)
G
Z
=
F
Z
∑
j
=
1
N
‍
G
j
Z
-
G
j
+
1
Z
z
j
-
1
P
j
+
G
0
hhhhhhhh
+
G
z
N
,
0
,
…
,
0,1
-
G
N
Z
hhhhhhhhhhhh
-
G
0
,
…
,
0
,
z
1
+
G
0
hhhhhhhh
·
z
N
-
1
P
N
-
1
z
1
-
1
P
1
∑
j
=
1
N
‍
G
j
Z
-
G
j
+
1
Z
z
j
-
1
P
j
+
G
0
.Compared with (16), an additional event is considered in (26). It is that the buffers of node N and node 1 are not empty while the buffers of other nodes are empty. In such case node N and node 1 transmit simultaneously.
Since nodeN is the sole source, it is easy to see that only node N could have more than one packet at a time instant. Other nodes can have at most one packet at a time. Considering (2), for j
=
1,2
,
…
,
N
-
1, we can define G
(
Z
)
=
f
z
j
+
g where f
,
g are two polynomials consisting of z
1
,
…
,
z
j
-
1
,
z
j
+
1
,
…
,
z
N
-
1
,
z
N
1
,
z
N
2
,
…
,
z
N
+
∞. By setting z
j
=
0,1 in G
(
Z
)
=
f
z
j
+
g, two equations could be established over f and g. By solving the equations, we have(27)
G
Z
=
G
Z
z
j
=
0
+
G
Z
z
j
=
1
-
G
Z
z
j
=
0
z
j
.
Through substitutingz
i
=
0 for i
=
1
,
…
,
j
-
1 in (27), we get(28)
G
j
Z
-
G
j
+
1
Z
=
G
j
1
Z
-
G
j
+
1
Z
z
j
.By substituting (28) into (26), we obtain (25). The proof of theorem is completed.According to (1), by taking a partial derivative of (27) with respect to z
j, we have(29)
L
¯
j
=
1
-
G
Z
z
j
=
0
,
z
i
=
1
(
N
≥
i
≥
1
,
i
≠
j
)
.Considering (29), the average queue length is determined by G
(
1,0
,
1
,
…
,
1
), G
1,1
,
0,1
,
…
,
1
,
…
,
G
(
1
,
…
,
1,0
) which could be obtained by setting z
N
=
1 in G
(
z
N
,
0,1
,
…
,
1
), G
z
N
,
1,0
,
1
,
…
,
1
,
…
,
G
(
z
N
,
1
,
…
,
1,0
). To solve these terms, we would establish equations in two steps.Firstly, to simplify (25), we assume that G
1
1
(
0
)
=
α
G
(
0
). α is a constant which is calculated as follows.By substitutingz
1
=
z
2
,
…
,
z
N
=
0 into (25), we get(30)
G
0
1
F
0
-
1
+
∑
j
=
1
h
‍
p
j
0
=
∑
j
=
1
h
‍
G
j
1
0
p
j
0
.Let G
j
1
(
0
)
≈
G
1
1
(
0
) for 2
≤
j
≤
N. We get(31)
α
=
1
F
0
∑
j
=
1
h
‍
p
j
0
-
1
∑
j
=
1
h
‍
p
j
0
+
1
.This approximation is reasonable. The explanation is that, forF
(
0
) close to 1, G
j
1
(
0
) (G
j
1
(
0
)
=
P
{
L
j
(
t
)
=
1
,
L
i
(
t
)
=
0
} for i
≠
j) is close to G
(
0
) (G
(
0
)
=
P
{
L
1
t
=
L
2
t
=
⋯
=
L
N
(
t
)
=
0
}). The accuracy of the approximation is demonstrated with simulation in Section 6. Thus (25) is simplified to(32)
1
F
Z
G
Z
-
∑
j
=
1
N
-
1
‍
P
j
G
j
1
Z
+
∑
j
=
2
N
-
1
‍
P
j
-
1
G
j
Z
+
P
1
1
-
z
N
-
1
P
N
G
z
N
,
0
,
…
,
0,1
+
z
N
-
1
P
N
P
1
-
1
-
P
1
+
P
N
-
1
G
N
Z
=
1
+
α
-
1
P
1
1
-
z
N
-
1
P
N
G
0
.Secondly, by setting (
z
N
-
1
,
…
,
z
1
)
=
(
{
0,1
}
,
…
,
{
0,1
}
) in (32), we obtain A
M
×
M
X
M
×
1
=
G
(
0
)
B
M
×
1 which shown as follows:(33)
X
=
G
z
N
,
0
,
…
,
0
G
z
N
,
0
,
…
,
1
⋯
G
z
N
,
1
,
…
,
1
,
B
=
B
z
N
,
0
,
…
,
0
B
z
N
,
0
,
…
,
1
⋯
B
z
N
,
1
,
…
,
1
,where M
=
2
N
-
1, A is the coefficient matrix of the linear equations, and B
(
z
N
,
…
,
z
1
)
=
(
1
+
(
α
-
1
)
P
1
)
(
1
-
z
N
-
1
P
N
). Obviously, if G
(
0
) is determined, we could solve the linear equations.Based on Cramer’s rule, letA
=
A
1
,
…
,
A
M and we obtain(34)
G
z
N
,
1
,
…
,
1
=
G
0
A
1
,
…
,
A
M
-
1
,
B
A
.Note that the determinant ofA denoted as A is a function of z
N. It can be proved that A
=
0 for z
N
=
1. Thus, based on (34), G
(
1
,
…
,
1
)
=
1, and l’Hopital’s rule, we obtain(35)
G
0
=
lim
z
N
→
1
⁡
A
A
1
,
…
,
A
M
-
1
,
B
=
∂
A
/
∂
z
N
∂
A
1
,
…
,
A
M
-
1
,
B
/
∂
z
N
z
N
=
1
.After G
(
0
) is obtained, we solve the equations as follows:(36)
G
z
N
,
1
,
…
,
0
,
…
,
1
=
G
0
A
1
,
…
,
B
,
…
,
A
M
A
,
G
z
N
,
1
,
…
,
1
=
G
0
A
1
,
…
,
A
M
-
1
,
B
A
.Based on l’Hopital’s rule, we get (37)
G
1,1
,
…
,
0
,
…
,
1
=
G
0
A
1
,
…
,
B
,
…
,
A
M
/
∂
z
N
∂
A
/
∂
z
N
z
N
=
1
,
∂
G
z
N
,
1
,
…
,
1
∂
z
N
z
N
=
1
=
G
0
∂
A
1
,
…
,
A
M
-
1
,
B
/
A
∂
z
N
z
N
=
1
.By substituting (29) and (36) into (1), the MED is obtained.


### 5.2.2. General Networks withN
>
h
+
2

As mentioned above, it is very difficult to calculate the MED in the scene withN
>
h
+
2 since many nodes may succeed in their transmissions simultaneously. To circumvent this difficulty, we propose here an approximate analysis method.The rationale behind the proposed approximation is that for approximating the behavior of a node, it might suffice to consider the behavior of a substitute node which has a similar communication environment like that of the analyzed node. The behavior of a node in the general scene (N
>
h
+
2) can be approximated as the behavior of substitute node in the special scene (N
=
h
+
2) in Figure 2. If nodes N
-
h
-
2
,
N
-
h
-
3
,
…
,
0 are approximated as a destination node, nodes N, N
-
1
,
…
,
N
-
h
-
1 in the general case have the similar behaviors of the substitute nodes h
+
2, h
+
1
,
…
,
1 in the special case. Assume that the corresponding transmission probabilities P
j between the substitute nodes in the special scene is the same as that in the general scene; we get(38)
t
N
g
=
t
h
+
2
s
,
t
N
-
1
g
=
t
h
+
1
s
,
…
,
t
N
-
h
-
1
s
=
t
1
s
,where t
j
g, t
j
s denote queueing delay of node j in the general scene and special scene, respectively.Similarly, the upstream nodesN
,
…
,
N
-
h
-
1 could be approximated as a source node and the downstream nodes N
-
2
h
-
3
,
…
,
0 could be approximated as a destination node. Then, by substituting the corresponding transmission probabilities, we get(39)
t
N
-
h
-
2
g
=
t
h
+
1
s
,
t
N
-
h
-
3
g
=
t
h
s
,
…
,
t
N
-
2
h
-
3
g
=
t
1
s
.Thus, the queueing delay of each node in general scene could be obtained by using our approach iteratively.


## 5.2.1. Special Networks withN
=
h
+
2

Theorem 3.
ForN
=
h
+
2, the steady-state joint generating function of the queue length distribution is(25)
G
Z
=
F
Z
∑
j
=
1
N
-
1
‍
G
j
1
Z
-
G
j
+
1
Z
P
j
+
G
0
hhhhhhhhhh
+
G
N
Z
-
G
0
z
N
-
1
P
N
hhhhhhhhhh
+
G
z
N
,
0
,
…
,
0,1
-
G
N
Z
-
G
1
1
0
+
G
0


hhhhhhhhhhh
·
z
N
-
1
P
N
P
1
-
P
1
∑
j
=
1
N
-
1
‍
G
j
1
Z
-
G
j
+
1
Z
P
j
+
G
0
.Proof.
We obtainG
(
Z
) based on Appendix A as follows:(26)
G
Z
=
F
Z
∑
j
=
1
N
‍
G
j
Z
-
G
j
+
1
Z
z
j
-
1
P
j
+
G
0
hhhhhhhh
+
G
z
N
,
0
,
…
,
0,1
-
G
N
Z
hhhhhhhhhhhh
-
G
0
,
…
,
0
,
z
1
+
G
0
hhhhhhhh
·
z
N
-
1
P
N
-
1
z
1
-
1
P
1
∑
j
=
1
N
‍
G
j
Z
-
G
j
+
1
Z
z
j
-
1
P
j
+
G
0
.Compared with (16), an additional event is considered in (26). It is that the buffers of node N and node 1 are not empty while the buffers of other nodes are empty. In such case node N and node 1 transmit simultaneously.
Since nodeN is the sole source, it is easy to see that only node N could have more than one packet at a time instant. Other nodes can have at most one packet at a time. Considering (2), for j
=
1,2
,
…
,
N
-
1, we can define G
(
Z
)
=
f
z
j
+
g where f
,
g are two polynomials consisting of z
1
,
…
,
z
j
-
1
,
z
j
+
1
,
…
,
z
N
-
1
,
z
N
1
,
z
N
2
,
…
,
z
N
+
∞. By setting z
j
=
0,1 in G
(
Z
)
=
f
z
j
+
g, two equations could be established over f and g. By solving the equations, we have(27)
G
Z
=
G
Z
z
j
=
0
+
G
Z
z
j
=
1
-
G
Z
z
j
=
0
z
j
.
Through substitutingz
i
=
0 for i
=
1
,
…
,
j
-
1 in (27), we get(28)
G
j
Z
-
G
j
+
1
Z
=
G
j
1
Z
-
G
j
+
1
Z
z
j
.By substituting (28) into (26), we obtain (25). The proof of theorem is completed.According to (1), by taking a partial derivative of (27) with respect to z
j, we have(29)
L
¯
j
=
1
-
G
Z
z
j
=
0
,
z
i
=
1
(
N
≥
i
≥
1
,
i
≠
j
)
.Considering (29), the average queue length is determined by G
(
1,0
,
1
,
…
,
1
), G
1,1
,
0,1
,
…
,
1
,
…
,
G
(
1
,
…
,
1,0
) which could be obtained by setting z
N
=
1 in G
(
z
N
,
0,1
,
…
,
1
), G
z
N
,
1,0
,
1
,
…
,
1
,
…
,
G
(
z
N
,
1
,
…
,
1,0
). To solve these terms, we would establish equations in two steps.Firstly, to simplify (25), we assume that G
1
1
(
0
)
=
α
G
(
0
). α is a constant which is calculated as follows.By substitutingz
1
=
z
2
,
…
,
z
N
=
0 into (25), we get(30)
G
0
1
F
0
-
1
+
∑
j
=
1
h
‍
p
j
0
=
∑
j
=
1
h
‍
G
j
1
0
p
j
0
.Let G
j
1
(
0
)
≈
G
1
1
(
0
) for 2
≤
j
≤
N. We get(31)
α
=
1
F
0
∑
j
=
1
h
‍
p
j
0
-
1
∑
j
=
1
h
‍
p
j
0
+
1
.This approximation is reasonable. The explanation is that, forF
(
0
) close to 1, G
j
1
(
0
) (G
j
1
(
0
)
=
P
{
L
j
(
t
)
=
1
,
L
i
(
t
)
=
0
} for i
≠
j) is close to G
(
0
) (G
(
0
)
=
P
{
L
1
t
=
L
2
t
=
⋯
=
L
N
(
t
)
=
0
}). The accuracy of the approximation is demonstrated with simulation in Section 6. Thus (25) is simplified to(32)
1
F
Z
G
Z
-
∑
j
=
1
N
-
1
‍
P
j
G
j
1
Z
+
∑
j
=
2
N
-
1
‍
P
j
-
1
G
j
Z
+
P
1
1
-
z
N
-
1
P
N
G
z
N
,
0
,
…
,
0,1
+
z
N
-
1
P
N
P
1
-
1
-
P
1
+
P
N
-
1
G
N
Z
=
1
+
α
-
1
P
1
1
-
z
N
-
1
P
N
G
0
.Secondly, by setting (
z
N
-
1
,
…
,
z
1
)
=
(
{
0,1
}
,
…
,
{
0,1
}
) in (32), we obtain A
M
×
M
X
M
×
1
=
G
(
0
)
B
M
×
1 which shown as follows:(33)
X
=
G
z
N
,
0
,
…
,
0
G
z
N
,
0
,
…
,
1
⋯
G
z
N
,
1
,
…
,
1
,
B
=
B
z
N
,
0
,
…
,
0
B
z
N
,
0
,
…
,
1
⋯
B
z
N
,
1
,
…
,
1
,where M
=
2
N
-
1, A is the coefficient matrix of the linear equations, and B
(
z
N
,
…
,
z
1
)
=
(
1
+
(
α
-
1
)
P
1
)
(
1
-
z
N
-
1
P
N
). Obviously, if G
(
0
) is determined, we could solve the linear equations.Based on Cramer’s rule, letA
=
A
1
,
…
,
A
M and we obtain(34)
G
z
N
,
1
,
…
,
1
=
G
0
A
1
,
…
,
A
M
-
1
,
B
A
.Note that the determinant ofA denoted as A is a function of z
N. It can be proved that A
=
0 for z
N
=
1. Thus, based on (34), G
(
1
,
…
,
1
)
=
1, and l’Hopital’s rule, we obtain(35)
G
0
=
lim
z
N
→
1
⁡
A
A
1
,
…
,
A
M
-
1
,
B
=
∂
A
/
∂
z
N
∂
A
1
,
…
,
A
M
-
1
,
B
/
∂
z
N
z
N
=
1
.After G
(
0
) is obtained, we solve the equations as follows:(36)
G
z
N
,
1
,
…
,
0
,
…
,
1
=
G
0
A
1
,
…
,
B
,
…
,
A
M
A
,
G
z
N
,
1
,
…
,
1
=
G
0
A
1
,
…
,
A
M
-
1
,
B
A
.Based on l’Hopital’s rule, we get (37)
G
1,1
,
…
,
0
,
…
,
1
=
G
0
A
1
,
…
,
B
,
…
,
A
M
/
∂
z
N
∂
A
/
∂
z
N
z
N
=
1
,
∂
G
z
N
,
1
,
…
,
1
∂
z
N
z
N
=
1
=
G
0
∂
A
1
,
…
,
A
M
-
1
,
B
/
A
∂
z
N
z
N
=
1
.By substituting (29) and (36) into (1), the MED is obtained.


## 5.2.2. General Networks withN
>
h
+
2

As mentioned above, it is very difficult to calculate the MED in the scene withN
>
h
+
2 since many nodes may succeed in their transmissions simultaneously. To circumvent this difficulty, we propose here an approximate analysis method.The rationale behind the proposed approximation is that for approximating the behavior of a node, it might suffice to consider the behavior of a substitute node which has a similar communication environment like that of the analyzed node. The behavior of a node in the general scene (N
>
h
+
2) can be approximated as the behavior of substitute node in the special scene (N
=
h
+
2) in Figure 2. If nodes N
-
h
-
2
,
N
-
h
-
3
,
…
,
0 are approximated as a destination node, nodes N, N
-
1
,
…
,
N
-
h
-
1 in the general case have the similar behaviors of the substitute nodes h
+
2, h
+
1
,
…
,
1 in the special case. Assume that the corresponding transmission probabilities P
j between the substitute nodes in the special scene is the same as that in the general scene; we get(38)
t
N
g
=
t
h
+
2
s
,
t
N
-
1
g
=
t
h
+
1
s
,
…
,
t
N
-
h
-
1
s
=
t
1
s
,where t
j
g, t
j
s denote queueing delay of node j in the general scene and special scene, respectively.Similarly, the upstream nodesN
,
…
,
N
-
h
-
1 could be approximated as a source node and the downstream nodes N
-
2
h
-
3
,
…
,
0 could be approximated as a destination node. Then, by substituting the corresponding transmission probabilities, we get(39)
t
N
-
h
-
2
g
=
t
h
+
1
s
,
t
N
-
h
-
3
g
=
t
h
s
,
…
,
t
N
-
2
h
-
3
g
=
t
1
s
.Thus, the queueing delay of each node in general scene could be obtained by using our approach iteratively.


## 6. Results and Discussion

We validate the correctness of the theoretical derivation and approximation approach by comparing numerical results with simulation using MATLAB in this section. Beside the MED, an extra performance metric called saturation throughput is studied in our simulation. It is defined as the minimum value of arriving rate for which the MED becomes infinite.N
+
1 nodes (including the destination) with infinite buffers are used. Node N is the source node where node 0 is the destination node. The external arriving process is the Bernoulli process with parameter r
N. When considering directly connected networks, all the nodes are randomly distributed in a circular area. The diameter is 100 m to ensure that all the nodes in the network are directly connected to each other. When considering nondirectly connected networks, nodes are preassigned in a line. The distance between two adjacent nodes is the same and is set to 30 m. Consider (40)
p
x
=
1
2
erfc
⁡
2
2
1
σ
dB
10
log
⁡
R
X
T
h
r
e
s
h
L
4
π
2
x
β
P
t
G
t
G
r
λ
2
.Delivery probability based on the shadow propagation model in (40) is assumed. In the equation, p
(
x
) denotes the delivery probability for distance x, P
t is the transmission power, G
t and G
r are the transmission and reception antenna gain, respectively, λ is the signal wavelength (c
/
f, with the speed of light, c
=
3
×
1
0
8 m/s), β is the path loss exponent, and L is the system loss. Packets are correctly delivered if the received power is greater than or equal to R
X
T
h
r
e
s
h. The delivery probability with varying distance is depicted in Figure 4. The corresponding simulation parameters are listed in Table 1. We implement the OR described in Section 3. The MED for experimental data is the average time of packets transmitted from the source node to the destination node. After each simulation, we record N, h
i, and the delivery probability among the nodes and then feed them into the mathematical model to obtain numerical results. Each data sample in the following figures is averaged over 100 runs.Table 1
Parameters settings.
Description
Values
Simulation time
1
0
6 slots
P
t
0.28183815 W
R
X
T
h
r
e
s
h
3.652
×
1
0
-
10 W
G
t
,
G
r
,
L
1, 1, 1
f
,
β
,
σ
dB
2.4 GHz, 3, 6 dBFigure 4
Delivery probability versus distance.The MED for directly connected networks with two, three, and four nodes versus different arriving rates is plotted in Figure5. We obtain the following observations.Figure 5
Directly connected networks (N
=
2,3
,
4).Firstly, theoretical calculation has high accuracy agreement with the computer simulation.Secondly, under little traffic (r
N
≤
0.24), MED is all small. The MED in the four-node network is about one slot higher than that in three-node network and two slots higher than that in two-node network. Since network congestion does not exist under the little traffic, MED is mainly caused by the transmission time between nodes. The more the nodes in the network, the higher the MED.Thirdly, as the arriving rate increases, MED becomes large. When the traffic is heavy, the MED rises sharply. In OR, a low priority node is not allowed to access to channel until all the packets buffered in the nodes of higher priorities are transmitted successfully. Thus, network congestion is the main reason for the sharp rise of the MED.Finally, the saturation throughput for the two-, three-, and four-node networks is 0.72, 0.47, and 0.36, respectively. Obviously, more forwarding candidates introduce more coordination time overhead. On the other hand, in order to supply the spatial diversity and improve the transmission reliability, enough forwarding candidates are required in OR. Therefore, it is very important to discover a suitable forwarding list when designing the OR.In Figures6–10, the MED versus the arriving rate for nondirectly connected networks with varying number of nodes is plotted. The results in Figure 6 show that the theoretical analysis for the case N
=
h
+
2 is in good agreement with experiment data. Saturation throughput in the network with N
=
4 is about 0.45. More notably, saturation throughput does not significantly change with the increasing number of nodes. The reason is that under heavy traffic, the MEDs are mainly caused by the network congestion at the source node. However, in nondirectly connected networks, the source node is only directly affected by nearby nodes. Thus, adding the nodes at the end of the linear network would not change the behavior of the source node.Figure 6
Nondirectly connected networks (h
=
2
,
N
=
4).Figure 7
Nondirectly connected networks (h
=
2
,
N
=
5).Figure 8
Nondirectly connected networks (h
=
2
,
N
=
6).Figure 9
Nondirectly connected networks (h
=
2
,
N
=
7).Figure 10
Nondirectly connected networks (h
=
2
,
N
=
8).Note that the approximate value coincides closely with the experimental data shown in Figures7–10. In particular, when r
N
≤
0.40, mean absolute error between approximate value and experimental results is controlled within 1.78916 slots regardless of the increasing number of nodes (varying from 5 to 8). These results verify the rationality of the approximate method.Obviously, when the arriving rate becomes larger than 0.45 packet/slot, all the MEDs in Figures7–10 rise sharply. In addition, we would like to point out that the differences become wider when the arriving rate becomes greater than the saturation throughput. A possible explanation for this is that when network congestion happens, the behavior of a node cannot be approximated as that in a special case with network congestion. In such case, we are unable to determine the exact value of the MED but get a general trend.


## 7. Conclusion

This paper investigates the MED of a regular OR under different scenes. We first propose a new mathematical distribution which has many more exciting applications than the traditional geometric distribution. Then, we develop the MED calculation methodology for any directly connected network and some special cases of nondirectly connected network. We also propose an approximate analysis method for the general cases so that this analytical framework can be applied to more general scenario. By applying the MED calculation into actual networks, the relationship between the MED and the number of forwarding candidates is revealed. In directly connected networks, MED is quite sensitive to the number of forwarding candidates, while, in nondirectly connected network, this phenomenon is not apparent.This MED calculation methodology can be applied to an arbitrary OR with the knowledge of the priority rule and delivery rates between the nodes. In this case, the relationship between the MED and related parameters can be indicated clearly and specifically, which provides guideline for the OR design evaluation or OR optimization.Currently, our approach for nondirectly connected networks is limited to linear networks and our future work would extend to two- or three-dimensional network.



---

*Source: 521861-2015-03-08.xml*