# Dynamic Retransmission Limit Scheme in MAC Layer for Routing in Multihop Ad hoc Networks

Authors: Ralph El-Khoury; Rachid El-Azouzi
Journal: Journal of Computer Systems, Networks, and Communications
 (2008)

---

## Abstract

We consider a wireless ad hoc network with random
access channel. We present a model that takes into
account topology, routing, random access in MAC
layer, and forwarding probability. In this paper, we focus on drawing benefit from the interaction of the MAC (governed by IEEE 802.11 or slotted Aloha)
and routing by defining a new cross-layer scheme
for routing based on the limit number of retransmission.
By adjusting dynamically and judiciously
this parameter in a saturated network, we have
realized that both stability of forwarding queues and
average throughput are significantly improved in
linear networks with symmetric traffic: a gain of 100% can be reached. While in asymmetric topology
network with asymmetric traffic, we achieve a better
average delay (resp., throughput) for each connection
without changing the average throughput (resp.,
delay). In addition, we show the efficiency of our
new scheme in case of multimedia applications with
delay constraint. A detailed performance study is
presented using analytical and simulation evaluation.


---

## Body

## 1. Introduction

A multihop wireless ad hoc network is a
collection of nodes that communicate with each other without any established
infrastructure or centralized control. Each of these nodes is a wireless
transceiver that transmits and receives at a
single-frequency band which is common to all the
nodes. These nodes can communicate with each other, however,  they are limited
by their transmitting and receiving capabilities. Therefore, they cannot
directly reach all of the nodes in the network as most of the nodes are outside
of direct range. In such a scenario, one of the possibilities for the
information transmission between two nodes that are not in position to have a
direct communication is to use other nodes in the network. To be precise, the
source node transmits its information to one of the nodes which is within
transmission range of the source node. In order to overcome this, the network
operates in a multihop fashion. Nodes route traffic for each other. Therefore,
in a connected ad hoc network, a packet can travel from any source to its
destination either directly, or through some set of intermediate packet
forwarding nodes.In recent years, an increased effort was consecrated
to cross-layer design, of ad hoc networks, where information is exchanged
between different layers. In wireless context where channel conditions and
network connectivity impose serious challenges, new cross-layer approaches are
needed to optimize performances. In fact, the knowledge of channel condition in
the physical layer may help on choosing the adequate number of retransmission
in the MAC layer which also depends on the application requirement and the
transport layer utilized. On the one hand, it is also profitable for routing
protocols to know the link state of lower layers to choose the best route
possible in terms of available bandwidth, stability of links, energy
consumptions, and so on. On the other hand, giving route information to the MAC
layer can be efficient to control packet retransmissions, as we will see in
this paper. In this case, we can achieve better QoS in terms of
end-to-end delay and throughput. Moreover, by using
cross-layer approaches, we can avoid network partitioning due to both link
degradation (and thus link breakage) and rapid energy expiration. Various
cross-layering approaches are analyzed in [1–3].To study the network performances with the interaction
of various parameters from different layers, we consider in this paper the
framework of random access mechanism for the wireless channel where the nodes
having packets to transmit in their buffers attempt transmissions by delaying
the transmission by a random amount of time. This mechanism acts as a way to
avoid collisions of transmissions of nearby nodes in the case where nodes cannot sense the channel while transmitting (hence, are not aware of other ongoing
transmissions). We assume that time is slotted into fixed length time frames.
In any slot, a node having a packet to be transmitted to one of its neighboring
nodes decides with some fixed (possibly node-dependent)
probability in favor of a transmission attempt. If there is no other
transmission by the other nodes whose transmission can interfere with the node
under consideration, the transmission is successful. We assume throughout that
there is some mechanism that notifies the sender of success or failure of its
transmissions. For example, the sources get the feedback on whether there was
zero, one, or more transmissions (collision) during the time slot.At any instant in time, a node may have two kinds of
packets to be transmitted as follows.(1)
Packets generated by the node itself. This can be sensed data if we consider a
sensor network.(2)
Packets from other neighboring nodes that need to beforwarded. In this paper,
we consider two separate queues for these two types and do a weighted fair
queueing (WFQ) for these two queues. This type of configuration allows us to
include in the model the cooperation level which represents the fraction of the
traffic forwarded by a node in ad hoc network.In [4, 5],
working with the above-mentioned system model, we have already studied the
impact of routing, channel access rates and weights of the weighted fair
queueing on throughput, stability, and fairness properties of the network. We
obtained important insights into various tradeoffs that can be achieved by
varying certain network parameters. The throughput maximization of the multihop
wireless networks has been extensively studied in [6–8]. However, it is shown that
the high throughput in the ad hoc network is achieved at the cost of a high
amount of delay. This problem has drawn our attention to the relation between
the delay characteristic and the throughput.In this paper, we use a cross layer optimization
between MAC and network layer for routing. For a given path between a source
and a destination, each intermediate node computes a new limit number of
retransmission based on a specific algorithm. This parameter can be adjusted
easily by each node. Using this new routing, we achieve a better average delay
(resp., throughput) for each connection without changing the average throughput
(resp., delay). In extreme cases, areset technique is introduced to
optimize performances. In addition, we show the efficiency of our scheme in
case of multimedia applications with delay constraint.Related Work
In most recent literature, the tradeoffs between
throughput and delay have been investigate as a key measure of the network
performance. Several studies have first focused on wireless network stability
and finding the maximum achievable throughput. Stability problem was considerably studied for the Aloha [11, 12] and scheduling [9, 10] protocols. Tassiulas and Ephremides [9] obtain a scheduling policy
for the nodes that maximizes the stability region. Their approach inherently
avoids collisions which allows to maximize the
throughput. Radunovic and Le Boudec [13] suggest that considering the total throughput as a
performance objective may not be a good objective. Moreover, most of the
related studied did not consider the problem of forwarding and each flow is
treated similarly (except for Radunovic and Le Boudec [13], Huang and Bensaou
[14], or Tassiulas and
Sarkar [15]). Our setting
is different from the mentioned ones in the following: the number of retransmission
is finite, and therefore in our setting, the output and the input rates need
not be the same.
In recent years, there has been a considerable effort
on trying to increase the performance of wireless ad hoc networks since Gupta
and Kumar [7] showed
that the capacity of a fixed wireless network decreases as the number of nodes
increases. Grossglauser and Tse [6] presented a two-phase packet forwarding technique for
mobile ad hoc networks, utilizing the multiuser diversity, in which a source
node transmits a packet to the destination when this destination becomes the
closet neighbors of the relay. This scheme was shown to increase the capacity
of the MANET, such that it remains constant as the number of users in the MANET
increases. However, the delay experienced by packet under this strategy was
shown to be large and it can be even infinite for a fixed number of nodes in
the system. Since both capacity as well as delay are important from an application
point of view, many works have recently been
studied to understand the delay-capacity relationship in ad hoc networks. In
[1], the authors
considered wireless network consisting of static sender-destination pairs and
mobile relays, and proposed a geographic routing scheme that achieves near
optimal capacity. They showed that under this scheme, the near optimal capacity
is achieved with the low delay. Many papers have studied the tradeoff between
throughput and delay. In [16, 17], the authors achieve a high throughput and low delay
in ad hoc networks. El Gamal et al. [18] analyze the optimal delay-throughput scaling for
different wireless network topologies. In the static random network with n nodes, they obtain an optimal tradeoff between
throughput and delay. Neely et al. [19] consider the delay-throughput tradeoff only for
mobile ad hoc networks.
The problem of optimizing the tradeoff throughput
delay can have a direct impact on the QoS of multimedia applications. The
previous mentioned literatures have mainly worked on analytical models.
Moreover, many papers have proposed some heuristics and new methods to improve
the quality of real-time streaming media over wireless networks. Since the
wireless links cause a lot of challenges due to the variation of channel
conditions, authors in [20–22] have treated this problem by proposing some
algorithms to adapt video streaming to the wireless channel in a WLAN. Their
ideas are based on protecting high-priority packets
and on considering the variation of channel conditions. Authors in [20] propose a selective packet
algorithm that runs in the base-station to determine which of the delayed packets
to deliver. Packets that have missed their play-out time are removed from the
base-station buffer without being transmitted. In [21], authors developed a
cross-layer algorithm motivated by the advantage of adapting the retry limit.
They observed that this latter can be optimized in such a way that the overall
packet losses from link errors and buffer overflow are minimized. In addition,
high priority packets are protected by giving them higher retry limit. In
[22], a retransmission
deadline is assigned to each packet by the application layer. Therefore, the
MAC layer can decide when to drop the packet by adapting the retry limit
parameter in the IEEE 802.11. It is important in such mechanism to find the
good optimization for the existing tradeoff between the delay incurred by
increasing the retry limit to protect some packets and the packet loss due to a
late arrival.
In multihop networks case, the QoS problem is more
complicated as it includes additional factors like multihop transmissions,
variation of the channel conditions, link breakage, congestion. Papers in
[23–26] have studied the problem of
real-time video over ad hoc networks. Authors in [23] believed that multipath
transport is a promising technique for this
problem. In [24], a
cross-layer approach (including APP/NETWORK/MAC layers) based on adaptive rate control for video streaming is proposed.
Source nodes must estimate the minimum effective transmission rate of a given
path to decide on their rate. The end-to-end QoS was improved, but the challenge
is to find the good balance between performance gains and design complexity as
mentioned in [25]. In
[26], it is shown how
the multihop paths and link failure can influence the performances, and therein
authors suggest a mechanism to adapt the application layer to network topology
change.Contribution
In comparison to previous works, the following distinguishes our paper.
(i)
We use a multilayer model that can track the
retransmission effects on the performances. Then, in symmetric networks, it is
possible to prove the efficiency of any methods that control the retransmission
limit.(ii)
Encouraged by previous studies done in WLAN on
the retransmission limit, we remarked that an optimization of this latter
through a given path in multihop networks can increase the available bandwidth.
It is a kind of congestion control that can be applied to multimedia streams.(iii)
The distributed cross-layer scheme that we
propose besides of its novelty and efficiency is characterized by its
simplicity. It does not need external information to the node itself, but a
local decision can be taken with the help of routing information from the
network layer and load estimation if needed.The rest of the paper is organized as follows. In
Section2, we describe the network model. Then in Section 3, we present our new
cross-layer dynamic scheme for routing. A detailed evaluation of performance is
performed in Section 4 to show the efficiency of our new scheme. In Section 5,
we study the performances in the case of delay-sensitive connections. Finally,
we give a conclusion in Section 6.


## 2. Network Model

### 2.1. Assumptions and Definitions

We model the ad hoc wireless network as a set ofN nodes deployed arbitrarily in a given area. We
assume the following.(i)
A single channel. Nodes use the same
frequency for transmitting with an omnidirectional
antenna. A node j receives successfully a packet from a node i if and only if there is no interference at the
node j due to another transmission on the same
channel, that is, if there is no transmission from any node of the set N(j)∪j,
where N(j) is the set of neighbors of node j.
We assume that all the nodes in N(j) has j as a neighbor. Note also that a node cannot
receive and transmit at the same time.(ii)
Two types of queues. Two queues are
associated with each node. The first one is the forwarded queue, noted by Fi (proper to the node i), which carries all the packets originated
from a given source and destined to a given destination. The second is Qi which carries the proper packets of the node i (in this case i≡s,
where s designates a source node). We assume that each
node has an infinite capacity of storage for the two queues. When Fi has a packet to be sent, the node chooses to
send it from Fi with a probability fi.
In other terms, it chooses to send from Qi with probability 1−fi.
When one of these queues is empty, then we choose to send a packet from the
nonempty one with a probability 1.(iii)
Saturated network. Each node has always
packets to be sent from queue Qi,
whereas Fi can be empty. Consequently, the network is
considered saturated, and thus it depends on the channel access mechanism. This
assumption is suitable to determine the limit operation of the network.
Besides, analytical results become feasible.


### 2.2. Network Layer

Network layer
handles the two queuesQi and Fi using the WFQ scheme, as described previously.
Also, this layer maintains routing algorithms. So, each node acts as a router,
it permits to relay packets originated from a source s to a destination d.
It must carry a routing information which permits sending of packets to a
destination via a neighbor. In this paper, we assume that nodes form a static
network where routes between any source s and destination d are invariant in the saturated network case.
Proactive routing protocols as optimized link state routing (OLSR) construct
and maintain a routing table that carries routes to all nodes on the network.
This kind of protocols corresponds well with our model. Note that the set of
nodes between a node s and d is designated by Rs,d.


### 2.3. MAC Layer

We assume a channel access mechanism only based on a
probability to access the network, that is, when a nodei has a packet to transmit from the queue Qi or Fi,
it accesses the channel with a probability Pi.
For example, in IEEE 802.11 distributed coordination function (DCF), the
attempt probability is given by [27] (1)P=2(1−2Pc)(1−2Pc)(CWmin+1)+PcCWmin(1−(2Pc)m), where Pc is the conditional collision probability given
that a transmission attempt is made, and m=log2(CWmax/CWmin) is the maximum of back-off stage. CWmax and CWmin designate the maximum and the minimum
contention windows, respectively. The scheduler of
transmission overall the network depends on Pi.
We assume that each node is notified about the success or failure of its
transmitted packets. A packet is failure only when there is an interference on
the intended receiver, in other terms, when a collision occurs on the receiver.
We have considered previously infinite buffer size, therefore, there is no
packet loss due to overflow at the queues. The only source of packet loss is
due to collisions. For a reliable communication, we allow a limit number of
successive transmissions for a packet, after that it will be dropped
definitively. Considering infinite forwarding buffer (yet neglecting the losses
due to overflow) does not really affect our results because we are considering
stability issue. In fact, this latter gives a practical indication on the
congestion occurring on the network.


### 2.4. Layer Representation of the Model

The model of
Figure1 is a layer representation of our model for each node. Attempting to
access the channel begins by choosing the queue from which a packet must be
selected. And then, this packet is moved from the corresponding queue from the
network layer to the MAC layer where it will be transmitted and retransmitted,
if needed, until its success or drop. In this manner, when a packet is in the
MAC layer, it is itself attempted successively until it is removed from the
node.Figure 1
Network layer and
MAC layer of nodei.


### 2.5. Main Notations

We summarize the parameters and notations used in this
paper for a general network topology.(1) MAC layer notations are as follows.(a)
Pi is the probability of transmission on the
channel of the node i.(b)
Pi,s,d is the probability that a transmission from
node i on the path from s to d is successful.(c)
Ki,s,d is the maximum number of transmissions allowed
to a packet sent from the node i on the path from s to d.
After Ki,s,d failures, the packet is dropped.(d)
Li,s,d is the expected number of attempts till
successful or a drop from node i on the path from s to d.(2) Network layer notations are as follows.(a)
fi is the probability to send a packet from the
queue Fi when it carries a packet.(b)
Rs,d is the set of intermediate nodes in a path
between a node s and a node d.s and d are not in this set.(c)
Ri,s,d is the set of nodes Rs,i∪i in the path s,d.(d)
ji,s,d designates a neighbor node of i that comes after i in the set Rs,d toward the destination on the path from s to d.
It is the next hop node of the node i.(e)
πi is the probability that the queue Fi has at least one packet to be forwarded after
a departure of a packet. It is the load of the forwarding queue Fi.yi:=1−πifi gives an indication about load or stability of
queue Fi.
Interesting results about the stability of forwarding queues were presented in
our previous works [4, 5].(f)
πi,s,d is the probability that the queue Fi has a packet at the first position ready to be
forwarded to the path Rs,d after a departure of a packet. It represents
the intensity of traffic for a given path Rs,d.(g)
Pi,d is the probability that the node i chooses the path Ri,d (whose destination is d) for sending packets from Qi.
Normally, this parameter can be assigned to the node
i-transport layer decision.


## 2.1. Assumptions and Definitions

We model the ad hoc wireless network as a set ofN nodes deployed arbitrarily in a given area. We
assume the following.(i)
A single channel. Nodes use the same
frequency for transmitting with an omnidirectional
antenna. A node j receives successfully a packet from a node i if and only if there is no interference at the
node j due to another transmission on the same
channel, that is, if there is no transmission from any node of the set N(j)∪j,
where N(j) is the set of neighbors of node j.
We assume that all the nodes in N(j) has j as a neighbor. Note also that a node cannot
receive and transmit at the same time.(ii)
Two types of queues. Two queues are
associated with each node. The first one is the forwarded queue, noted by Fi (proper to the node i), which carries all the packets originated
from a given source and destined to a given destination. The second is Qi which carries the proper packets of the node i (in this case i≡s,
where s designates a source node). We assume that each
node has an infinite capacity of storage for the two queues. When Fi has a packet to be sent, the node chooses to
send it from Fi with a probability fi.
In other terms, it chooses to send from Qi with probability 1−fi.
When one of these queues is empty, then we choose to send a packet from the
nonempty one with a probability 1.(iii)
Saturated network. Each node has always
packets to be sent from queue Qi,
whereas Fi can be empty. Consequently, the network is
considered saturated, and thus it depends on the channel access mechanism. This
assumption is suitable to determine the limit operation of the network.
Besides, analytical results become feasible.


## 2.2. Network Layer

Network layer
handles the two queuesQi and Fi using the WFQ scheme, as described previously.
Also, this layer maintains routing algorithms. So, each node acts as a router,
it permits to relay packets originated from a source s to a destination d.
It must carry a routing information which permits sending of packets to a
destination via a neighbor. In this paper, we assume that nodes form a static
network where routes between any source s and destination d are invariant in the saturated network case.
Proactive routing protocols as optimized link state routing (OLSR) construct
and maintain a routing table that carries routes to all nodes on the network.
This kind of protocols corresponds well with our model. Note that the set of
nodes between a node s and d is designated by Rs,d.


## 2.3. MAC Layer

We assume a channel access mechanism only based on a
probability to access the network, that is, when a nodei has a packet to transmit from the queue Qi or Fi,
it accesses the channel with a probability Pi.
For example, in IEEE 802.11 distributed coordination function (DCF), the
attempt probability is given by [27] (1)P=2(1−2Pc)(1−2Pc)(CWmin+1)+PcCWmin(1−(2Pc)m), where Pc is the conditional collision probability given
that a transmission attempt is made, and m=log2(CWmax/CWmin) is the maximum of back-off stage. CWmax and CWmin designate the maximum and the minimum
contention windows, respectively. The scheduler of
transmission overall the network depends on Pi.
We assume that each node is notified about the success or failure of its
transmitted packets. A packet is failure only when there is an interference on
the intended receiver, in other terms, when a collision occurs on the receiver.
We have considered previously infinite buffer size, therefore, there is no
packet loss due to overflow at the queues. The only source of packet loss is
due to collisions. For a reliable communication, we allow a limit number of
successive transmissions for a packet, after that it will be dropped
definitively. Considering infinite forwarding buffer (yet neglecting the losses
due to overflow) does not really affect our results because we are considering
stability issue. In fact, this latter gives a practical indication on the
congestion occurring on the network.


## 2.4. Layer Representation of the Model

The model of
Figure1 is a layer representation of our model for each node. Attempting to
access the channel begins by choosing the queue from which a packet must be
selected. And then, this packet is moved from the corresponding queue from the
network layer to the MAC layer where it will be transmitted and retransmitted,
if needed, until its success or drop. In this manner, when a packet is in the
MAC layer, it is itself attempted successively until it is removed from the
node.Figure 1
Network layer and
MAC layer of nodei.


## 2.5. Main Notations

We summarize the parameters and notations used in this
paper for a general network topology.(1) MAC layer notations are as follows.(a)
Pi is the probability of transmission on the
channel of the node i.(b)
Pi,s,d is the probability that a transmission from
node i on the path from s to d is successful.(c)
Ki,s,d is the maximum number of transmissions allowed
to a packet sent from the node i on the path from s to d.
After Ki,s,d failures, the packet is dropped.(d)
Li,s,d is the expected number of attempts till
successful or a drop from node i on the path from s to d.(2) Network layer notations are as follows.(a)
fi is the probability to send a packet from the
queue Fi when it carries a packet.(b)
Rs,d is the set of intermediate nodes in a path
between a node s and a node d.s and d are not in this set.(c)
Ri,s,d is the set of nodes Rs,i∪i in the path s,d.(d)
ji,s,d designates a neighbor node of i that comes after i in the set Rs,d toward the destination on the path from s to d.
It is the next hop node of the node i.(e)
πi is the probability that the queue Fi has at least one packet to be forwarded after
a departure of a packet. It is the load of the forwarding queue Fi.yi:=1−πifi gives an indication about load or stability of
queue Fi.
Interesting results about the stability of forwarding queues were presented in
our previous works [4, 5].(f)
πi,s,d is the probability that the queue Fi has a packet at the first position ready to be
forwarded to the path Rs,d after a departure of a packet. It represents
the intensity of traffic for a given path Rs,d.(g)
Pi,d is the probability that the node i chooses the path Ri,d (whose destination is d) for sending packets from Qi.
Normally, this parameter can be assigned to the node
i-transport layer decision.


## 3. A New Dynamic Scheme for the Maximum Number of Transmissions in Routing

The maximum
number of the transmissionsKi,s,d of each node i on a path Rs,d appears to be an important parameter  (in
[4, 5])  that can be adjusted easily
by each node. When all nodes have the same static value K,
it is sufficient to increase K so that throughput is considerably ameliorated
but the load is not. A tradeoff stability throughput is clearly
noticed. Is it possible to benefit from a dynamic
value of Ki,s,d to optimize this tradeoff?In this section, we propose a new dynamicKi,s,d scheme based on a table-driven routing where
routes are already known. It is a cross-layer scheme where each node needs the
information about the route to determine the corresponding Ki,s,d which is a MAC layer parameter. Each node in a
path Rs,d must be introduced
with the following:(1)
the length of the path in number of
hops; and(2)
its position in the path in terms of the
number of hops that separates it from the source. These two
pieces of information can be provided from the
routing protocol. If they are available, our scheme
computes the corresponding Ki,s,d.
The following is a description of the scheme.Consider that each node has a default value of the
maximum number of transmissions set toK.
Each node i in the set Rs,d∪{s} computes the corresponding Ki,s,d in such a manner that this latter is higher
than or equal to the previous Kj,s,d,
where j is the previous node of i in the path Rs,d∪{s},
that is, i=jj,s,d.
Furthermore, the average values of Ki,s,d (for i∈Rs,d∪{s}) must be set to K,
that is, (1/|Rs,d∪{s}|)∑i∈Rs,d∪{s}Ki,s,d=K.
Also, the values of Ki,s,d (for i∈Rs,d∪{s}) are determined based on the position of the
node i in the path Rs,d,
that is, it is based on the number of hops that
separates it from the source or the destination. We add to this scheme a reset
technique when the average queue size or the load of Fi exceeds some threshold. In fact, when the
average queue value in dynamic case becomes not profitable in comparison to the
static case, we reset the value of Ki,s,d to K,
or to a lower value. In the following section, we will specify a detailed and
practical method for choosing Ki,s,d.Under this scheme, we aim to give more chance of
success to packets that had come near to their destination. It rather means
that we need to avoid as much as possible loosing packets near their destination
so that waste of bandwidth throughout a path becomes lower. In other terms, we
expect to reduce the number of wasted slots in each connection.Normally, the way of choosing goodKi,s,d should depend on many parameters, not only on
the number of hops of each connection but also on the transmission
probabilities and the number of neighbors. Taking aware of many parameters at
the same time is a complex issue. In this paper, we focus mainly on varying Ki,s,d function of the number of hops. The following
evaluation of performance section may clarify the interest of using dynamic Ki,s,d.


## 4. Performance Evaluation: Numerical Results and Simulations

In this
section, we evaluate the performance of the dynamic scheme for a symmetric
linear and an asymmetric network. We specify and detail our dynamic scheme for
choosingKi,s,d in terms of the hop number. Then an analysis
of the numerical and simulation results are given. All numerical results have
been validated with our discrete time simulator that is presented in paper
[5].


### 4.1. Symmetric Linear Network Case

#### 4.1.1. Description of the Network

Our purpose by
studying the linear network case is to understand the advantage of the new
dynamic scheme so that we can understand the efficiency of the method on the
asymmetric case. Also, the linear symmetric network is simple to study
[4]. The
characteristics of this network are as follows: (1) equal number of neighbors,
that is, ni=2 for all nodes; (2) Pi=P;
(3) infinite number of nodes; (4) equal forwarding probability, that is, fi=f;
(5) Ps,d,
depends on the connection hop number of h,
thus Ps,d=P(h);
(6) there is only one path between two different nodes, that is, one way to
reach any destination from any source. The consequence of these hypothesis is
that the stability is the same for all nodes, that is, yi=y.
When we take a uniform probability to choose a given path of length h,
then P(h)=1/2B,
where B represents the maximum number of hops to reach
the farthest destination.


#### 4.1.2. Main Expressions for Performance Evaluation

We will mainly
study the stability-throughput issue with the new scheme. In addition, the
probability of success and the average number of transmissions bring additional
material to understand what is happening in the network. Later, in the
asymmetric network section, the end-to-end delay gives more information about
stability of connections; while in the symmetric linear network, the stability
of a node is equivalent for all nodes, thus the variation of a node stability
informs about delay variation.General expressions for performance evaluation in
general networks were already derived in our paper [5], but in the linear symmetric
case, these expressions can be derived from [4]. Here, we include the fact that the limit number of
transmissions is the function of the number of hops. Let T:=1−Pi,s,d be the collision probability, Pi,s,d=(1−P)2,
and K(i,h) represents the value of Ki,s,d in K(i,h) notation, i represents the position of the node on the
path Rs,d.
For example, Ks,s,d=K(1,h), Kjs,s,d,s,d=K(2,h),
and so on. Let L(i,h) be the average number of transmissions (i.e., Li,s,d) of the node i on the path of length h.
Thus, L(i,h)=(1−TK(i,h))/(1−T).
For all paths, the average number of transmissions L(i,h) becomes (2)L=2(1−y)B2−B∑j=1B∑h=j+1BL(j,h)+2y∑h=1BP(h)L(1,h), where (B2−B) is the number of connections that traverse a
node. Note that L depends only on y and B for a given P.
It means that L for the dynamic case is different from the
static one.Now, to determiney,
we can write the balance rate equation of the forwarding queue. Then, the
arrival rate to the forwarding queue of a given node is equal to the departure
rate from it. The arrival rate from all sources of the network to a given node
can be written as (3)a=2y∑j=1B∑h=j+1BP(h)PL∏k=1j(1−TK(k,h)). This latter is formed by two
main parts: the first one is the traffic intensity of source nodes (of new
packets) and the second one is the end-to-end probability of success. The
departure rate is (4)d=(1−y)PL. This latter also is formed by
two parts: the first one is the intensity of forwarding packets (1−y) and the second is the rate of removing a
packet from the node by successful transmission or a drop after K transmissions. Therefore, the stability region
can be written as (5)y=11+2∑j=1B∑h=j+1BP(h)∏k=1j(1−TK(k,h)). The throughput on the path of
length h can be written as (6)thp(h)=yP(h)PL∏k=1h(1−TK(k,h)). The average throughput for all h is (7)thp¯=yPB⋅L⋅∑h=1BP(h)∏k=1h(1−TK(k,h)). The probability of success
between a couple of nodes on a path of length h is Psucc(h)=∏k=1h(1−TK(k,h)).
The average probability of success for all h is Psucc¯=(1/B)∑h=1BPsucc(h).


#### 4.1.3. A Practical Description of a Dynamic Method

We use a simple method that gives a dynamic value ofK(i,h) depending on the length of a connection h,
on the position of the node i on the path Rs,d,
and on K′ the step of how
much we increase K on a given node i.
Each node i initializes K(i,h) to K.This method maintains an averageK of all K(i,h) (for i∈Rs,d∪{s}) values of each connection. For example, this
average K can be the default value of the maximum number
of transmissions in a network of static K.
Also, in this manner it will be easy to compare the static K case performance and the dynamic one.Practically, for each packet transmission, a nodei must know its K(i,h) on a given path (or connection) of length h.
In fact, it must determine the length h of the path from the routing, then its related position to the source. Supposing that K and K′ are known, node i can calculate easily its corresponding K(i,h) while maintaining an average K in the path. Then, it informs the MAC layer
about this K(i,h) new value.As an exterior observer point of
view, theK(i,h) values are attributed as follows: the middle
node has the value K (when h is even, we attribute K to the two middle
nodes), and on its both sides, K is decreased in the direction of the source
and increased in the direction of the destination by a value of K′ for each hop. On one side, whenever it is
impossible to decrease K,
the value of K(i,h) maintains its last value. On the other side, K(i,h) must maintain also the last value in a certain
level so that we maintain an average of K.For example, whenh=10,K=8, and K′=2,
the set values of K(i,h)
is attributed to
the set of nodes in Rs,d∪{s} starting from the source and ending with the
node before the destination, that is, {2,2,4,6,8,8,10,12,14,14}.
In this case, we have K(4,10)=6,K(5,10)=8,
and so forth. We could also use another method to attribute values of K(i,h).
The key idea of the dynamic scheme is to attribute the values of K(i,h) in an increasing manner starting from the
source of a connection till the destination. For that, a simple algorithm can
be turned on each node to determine its corresponding dynamic K to a given route Rs,d.


#### 4.1.4. Analysis of the Numerical Results

We draw some
numerical results of the above formulas using the previous parametersB=10 and K=8 for the two cases K′=0 and K′=2.
The maximum hop number B=10 allows about 2*10 possible connections for each node. The
forwarding probability is set to f=0⋅8.
The numerical results concern the average number of transmissions and stability
for each node, then the end-to-end throughput and probability of success. We
are also interested in evaluating the behavior of these, for each transmission
probability, that is, when the channel suffer from
low-to-high contention. All these performance metrics are shown from Figures 2 to 5. The main
remarkable thing is that the stability and the throughput are considerably
ameliorated with the dynamic scheme (K′≠0) compared to the static K case (K′=0).Figure 2
Average number
of transmissionL for different K′.This remarkable amelioration is mainly due to the
following facts.(1)
The dynamic scheme privileges the forwarded
packets that come near the destination. It is better to encourage these packets
to reach their destination, otherwise, the network will suffer more wasted bandwidth.(2)
The flow of packets from each source is limited on
the first hops of each connection. If the network cannot support transporting
more packets on a connection, it is better to limit the flow of new entering
packets in the network. This is a load moderating issue.As a consequence, Figure2 shows that the average
number of attempts in the dynamic scheme (L(K′≠0)) is always lower than the number of attempts
in the static case, that is, L(K′≠0)≤L(K′=0).
(Let X(K′≠0) and X(K′=0) be two symbols, where X represents one of the parameters in the set {K,L,y,thp¯,Psucc¯} for the two dynamic and static K case,
resp.) It means that a packet needs less average number of retransmissions at each node
throughout a path Rs,d to be delivered on the destination, in the
dynamic case. Therefore, the service rate of the forwarding packets will be
faster. As shown in Figure 3, it has permitted a low load, and more new packets
have entered the network, indicating a higher region of stability. For that, y(K′≠0)≥y(K′=0).Figure 3
Stability region
for the linear case with static and dynamicK.We distinguish two states of the network for two
contention degrees when we use the dynamic scheme. These are shown on Figure4
where for a given P0 (P0≃0.55 in this example), the probability of success
for K′≠0 comes near the one for K′=0.
Therefore, we distinguish the following.Figure 4
Average
Probability of success for the linear case with static and dynamicK.Figure 5
Average
throughput for the linear case with static and dynamicK.(i) Thesevere state for a low-moderate contention: P≤P0 and Psucc¯(K′≠0)<Psucc¯(K′=0).
In this state, the nodes with K(K′≠0)<K have the aptitude to drop a lot of packets in
the first nodes (near the source) on a path Rs,d,
in such a manner that a less number of successful packets arrives to the
destination compared to the static K case. When dropping a lot of packets in the
network, the load of each node diminishes, thus y(K′≠0)≥y(K′=0).
Since the impact of the load in this state is higher than the end-to-end
probability of success, the average throughput in the network becomes larger,
that is, thp¯(K′≠0)≥thp¯(K′≠0),
see Figure 5. In low contention, we do not really need to limit a lot the
retransmission of packets since they have a higher chance to reach the
destination in the static K case. The load control appears to be more
efficient than controlling the success of packets to get a good throughput. In
fact, giving more chance of success to packets approaching the destination is
not the main reason of amelioration in low-channel contention case. Instead,
decreasing the limit number of retransmissions of source packets is more
important as it has the impact on the load of forwarding queues.(ii) Themoderate state for a moderate-high contention: P≥P0 and Psucc¯(K′≠0)≃Psucc¯(K′=0).
In this state, dropping packets with K(K′≠0)<K is more efficient than the severe state,
in such a manner that even the end-to-end probability of success comes closer
to the static case. In high contention, a packet that has traveled through many
nodes in the static K case is more susceptible to drop. When
dropping such packet, we loose all retransmission slots from the source until
its drop. Therefore, increasing K behind the middle node on a path Rs,d helps conserving the packets from drop and
minimizes the number of loosed slots. In this way, the throughput and the load
are ameliorated as shown in Figures 5 and 3, respectively. This also can be
verified with Figure 2, where L(K′≠0)≤L(K′=0).These two states can merge to one state for some
values ofK,K′, or B.
However, the dynamic scheme maintains its advantage compared to the static K case.


#### 4.1.5. Impact ofB,K, and K′

We study the impact ofB,K, and K′ on the performance of the network. We proceed
by comparing the static and the dynamic case. We show on the following figures the gain ratio while using the
dynamic case in terms of these last parameters. The gain ratio of the
static-dynamic K for the average throughput and the stability
region, presented in Figures 7 to 10, is defined as (X(K′≠0)−X(K′=0))/X(K′=0),
where X is the average of thp¯ or y for all P.
From these figures, the gain ratio of the average throughput and the stability
region evolve in a similar way when varying B,K,
or K′.
Remark that the average throughput is mainly affected by the load variation of
each node from (7).(1)Impact ofB. Let ΔL be the difference between the average number
of transmissions for K′=0 and K′≠0,
that is, ΔL=L(K′=0)−L(K′≠0).ΔL is an increasing function with B as shown in Figure 6 which verifies the
increasing gain ratio of the Figure 7. The dynamic scheme has a good
performance in large multihop networks.Figure 6
ΔL versus B for different K,
for K′=2 and P=0.5.Figure 7
Gain ratio of
dynamic case compared to the static one versusB (linear network).(2)Impact ofK. When K tends toward large values, the two dynamic and
static cases tend to each other, that is, we tend to zero gain ratio. So, each
packet will be retransmitted until achieving a
success. It does neutralize our dynamic scheme. Also, the impact of K depends on K′ as we see in Figures 8 and 9. For some K near the value of K′ or multiple of it, we have picks of gain ratio
that decrease with K.
For K=5,
we have the maximum possible gain in these two figures. It is a question of how
we use K′ according to K so that the dynamic scheme operates in an
optimal point. In fact, for some values of K and K′,
the source nodes (and the nearest nodes to the source) may be affected
by
very low dynamic K or not (according to the scheme calculation of
dynamic K). This is why we can see picks of gain or not
in Figures 8 and 9. For a fixed K′ and P,
we plot the quantity ΔL as a function of K in Figure 6. We observe that for small B,ΔL decreases with K,
so in Figure 8, the gain ratio is also decreasing. Remark that Figure 8 (as
Figures 7, 9, and 10) presents the gain ratio for all P,
whereas Figure 6 is presented for a fixed P=0.5.
Therefore, for P=0.5 and large B,
our scheme obtains high performance with higher K.
For that, the impact of B is considerable compared to K.Figure 8
Gain ratio of
dynamic case compared to the static one versusK for K′=2 (linear network).Figure 9
Gain ratio of
dynamic case compared to the static one versusK for K′=4 (linear network).Figure 10
Gain ratio of
dynamic case compared to the static one versusK′ (linear network).(3)Impact ofK′. The dynamic scheme is defined for K′≤K.
From Figure 10, choosing K′=7 for K=8 causes severe drops at the beginning of a path
since K(K′≠0)=1 for K(K′≠0)<K.
Even though the gain ratio is clearly large. The difference between K′=2 and K′=4 in Figure 10 is explained by Figure 2 where L(K′=2)<L(K′=4).


### 4.2. Asymmetric Network Case

Consider an asymmetric static wireless network with 11
nodes as shown in Figure11. We choose the following parameters: fi≡f=0.8 and Pi in a manner of enabling stability, for all i.
Let P2=P3=P7=P8=0.3,P4=P10=0.4,P5=0.5 be the fixed transmission probabilities for
nodes 2, 3, 4, 5, 7, 8, and 10 while Pi≡P for all other i.
Many nodes need to have a fix transmission probabilities so to get stable
queues for all nodes. The default maximum number of transmissions is K.
In the static case, Ki,s,d≡K,
while in dynamic case, Ki,s,d is chosen using the dynamic scheme presented
previously (Sections
3 and 4.1). We implement this dynamic scheme in our
discrete time simulator, so we can evaluate performance and validate numerical
results with simulations.Figure 11
Ad hoc wireless
network.


#### 4.2.1. A First Numerical and Simulation Study

Leta,b,c,d, and e be the five connections established on the
network of Figure 11, as indicated in the same figure. We compare from Figures
12 to 16 the dynamic (K=4 and K′=1) and the static (K=4 and K′=0) cases. Note that yj=1 for j∈{1,6,9,11},
since these nodes do not forward packets. Firstly, the forwarding source nodes
(3, 4, and 8) of the connections a, b,
and d have affected small dynamic K for their new packets (packets from Q): K3,3,6=K4,4,11=K8,8,2=3 and higher dynamic K for their forwarding packets: K3,8,2=K4,3,2=K8,11,6=5 and K4,6,7=4 (see Table 1 for K′=1 and Table 2 for K′=2). Note that “Conn." means
“connection." In fact, there are two advantages on giving smaller K for new packets. The first one is that it
gives more priority to the forwarding queue. Therefore, we observe less load,
then more aptitude to send new packets. The second one is that it can optimize
the load on the nodes belonging to the source connection, in a saturated
network case. In fact, it can make severe drops of
new packets (due to small K) that can diminish the flow of packets in a
connection and maintain necessary packets. Figure 12 supports our comment: the
stability region or the aptitude of sending new packets is considerably
ameliorated in nodes 3, 4,
and 8.
In addition, the throughput of connection d has beneficed from the increase of y8 of its source node 8, while the two others a and b have maintained their throughput
approximatively unchanged.Table 1
Values of the
dynamic maximum number of transmissions forK′=1 and K=4.
Nodes23456781011Conn.a003405000Conn.b435000000Conn.c000000543Conn.d050400300Conn.e004530000Table 2
Values of the
dynamic maximum number of transmissions forK′=2 and K=4.
Nodes23456781011Conn.a002406000Conn.b426000000Conn.c000000642Conn.d060400200Conn.e004620000Figure 12
Stability regionyi of the dynamic (K′=1) and static (K′=0) cases for K=4 (nodes 3, 4, and 8 of the asymmetric network
of Figure 11).Secondly, as the nodes6 and 11 do not forward packets in our example, then y6=y11=1.
These two nodes are the source of connections e and c,
respectively. From Figure 14, the throughput of these two connections are
clearly higher in the dynamic scheme and do not depend on any forwarding queue
loads in these connections. However, the packets sent from nodes 6 and 11 are
limited by the fact that K6,6,7=K11,11,6=3,
but there are privileged at nodes 5 and 8 with K5,6,7=K8,11,6=5.
Each drop at these latter nodes is more expensive than the drop at the source
nodes (as explained previously). For that, the throughput of these connections
(see Figure 14) was only affected by the end-to-end success of packets in an
interval of time without the impact of y6 and y11 which are the source
aptitudes of sending new packets. Note that nodes 2, 5, 7, and 10
have not really changed their region stability with the dynamic scheme in this
example (see Figure 13).Figure 13
Stability regionyi of the dynamic (K′=1) and static (K′=0) cases for K=4 (nodes 2, 5, 7, and 10 of the asymmetric
network of Figure 11).Figure 14
Throughput of the dynamic
(K′=1) and static (K′=0) cases for K=4 (asymmetric network of Figure 11).Thirdly, the end-to-end delay of a
connection gives a global vision on the stability of nodes that forms this
connection. Precisely, it is mainly affected by the waiting time on the
forwarding intermediate queues. In Figure15, the high delay of connection c clearly reflects the high and moderate charges
of nodes 10 and 8 shown in Figures 13 and 12, respectively. In
Figure 16, connection a has maintained the same delay in the dynamic
as in the static case. This was a consequence of the y5 and y7 unchanging (not so changed) in these two
cases. Delay of connections b, c,
and e have been ameliorated in the dynamic case due
to the forwarding aptitude of source nodes 4 and 8 that belong to these connections.Figure 15
Delay of the
dynamic (K′=1) and static (K′=0) cases for K=4 (connections b and c of the asymmetric network of Figure 11).Figure 16
Delay of the
dynamic (K′=1) and static (K′=0) cases for K=4 (connections a, d,
and e of the asymmetric network of Figure 11).What about the gain percentages of our scheme compared
to the static one? On one hand, we can observe from the presented Figures14,
15, and 16 for
K′=1
that the gain varies in function of the
probability of transmission. Therefore, for a P=0.4,
the throughput amelioration reaches 20% for connection d and is around 9% for connections c and e.
The delay for this same P is around 15% for connection b and around 11% for connections c and e.
On the other hand, Figures 17 and 18 can show a gain up to 50% for the throughput and up to 30% for the delay, for K′=2.
In the following paragraph, we will discuss some issues from these figures.Figure 17
Throughput of the
dynamic (K′=2) and static (K′=0) cases for K=4 (asymmetric network of Figure 11).Figure 18
Delay of the dynamic (K′=2) and static (K′=0) cases for K=4 (asymmetric network of Figure 11).


#### 4.2.2. Discussion

Here, we start
our discussion on the observations of previous figures of the asymmetric
network. In summary, the dynamic scheme has better performances when some of
the source nodes collaborate by forwarding packets and when these kinds of
sources are well distributed in the network. In fact, there are two properties
that help a connection to get a good performance:(1)
a connection must include within its
intermediate nodes a source node of another connection;(2)
the source node of a connection must not forward
packets.The first one
ameliorates the delay and the second one the throughput. These two properties
are jointly found in connectionsc and e.
Furthermore, the good performance (of throughput and delay) of connection c and e confirms this conclusion. In fact, nodes 11 and 6 are two nodes that do not forward packets (see
network of Figure 11) and in addition they are sources of the connections c and e,
respectively. Therefore, the traffic intensity from these two nodes to their
corresponding connections is maximal since no forwarding packets are to be
transmitted. This is why we can expect a good throughput. Furthermore, the set
of intermediate nodes of connections c and e contains a source node of other connections:
node 8 for connection c and node 4 for connection e.
These latter source nodes experience less delay due to the fact that they have
been affected lower limit number of retransmissions. Consequently, the
end-to-end delay of connections c and e would be lower.When one of these two properties is not found, then
threesituations are presented: a connection of the dynamic scheme(1)
maintains unchanged one performance
criterion (throughput or delay) and ameliorates the
other one;(2)
deteriorates one performance criterion and
ameliorates the other one;(3)
maintains unchanged the performance. These three situations are with comparison to the static case. An example of the first and the second
situation is the connections a, b,
and d in Figures 17 and 18 depending on the
transmission probability. In the second situation, the new scheme does not
overcome the existing tradeoff throughput delay for a given connection, but it
enables a benefit to other connections, and thus the aggregate performance of
the network is ameliorated. To overcome this tradeoff of some given connections
of this second situation, we have introduced to the new dynamic scheme
the capability to reset the dynamic value of K,
that is, to reallocate the default value K instead of the dynamic value only on the case
where K(K′≠0)>K(K′=0).
We study this option of reallocating K in the next section and we call it the reset
technique.


#### 4.2.3. A Second Simulation Study with the Reset Technique

Here, we consider only three connectionsa, b,
and f,
where f is formed by the successive nodes 9-10-7-3 with node 9 as a source and node 3 as a destination. a and b are the same as previously
mentioned. Connection b causes node 4 to forward. The default value of K is maintained to 4. But, we choose K′=3.
In this manner, the value of K(K′=3) for node 7 is set to 7 for the two connections a and f.
Therefore, the stability of node 7 becomes critical and is penalized when the
contention on the channel increases: many retransmissions of each single packet
causes more additional waiting time on the forwarding queue. So the choice of
high K(K′=3) on this node is not really judicious for
itself as shown in Figure 19: y7(K′=3)<y7(K′=0),
nor for the connection delays as shown in Figure 21. However, a considerable
amelioration on the throughput is clearly observed in Figure 20.Figure 19
Stability regionyi of the dynamic (K′=3) and static (K′=0) cases for K=4 (asymmetric network of Figure 11).Figure 20
Throughput of the
dynamic (K′=3) and static (K′=0) cases for K=4 (asymmetric network of Figure 11).Figure 21
Delay of the
dynamic (K′=3) and static (K′=0) cases for K=4 (asymmetric network of Figure 11).These observations correspond to the secondsituation described previously. Each node suffering from a degradation of stability
appeals the reset technique. In fact, each node uses the following three
steps to test and apply if needed, the reset technique as follows.(1)
If the average queue size exceeds a given
threshold, then go to the second step, else do nothing. The average waiting
time in the queue can be another criteria to decide whether to use thereset
technique or not. It is directly related to the queue size. Also, the
estimation of y(K′=0) and the measurement of y(K′≠0) can also be used for the decision.(2)
Choose judiciously a connection (according to
its data type and if it is not yet chosen) between those traversing it.(3)
Apply the reset ofK(K′≠0) to the default value K,
that is, set K(K′≠0)≡K for the connection chosen in step 2.In our example, thereset technique is applied
to the node 7 of the connection f.
Figures 22, 23, and 24 show that node 7 and connection f restore their performances as in the static
case. The remarkable thing is that even the connection a has seen its delay ameliorated due to the load
reduction on the node 7 forwarding queue while the throughput of a was not really affected in this example.
Hence, after applying the reset technique to node 7, connections a and f are now classified in the first and the third situations,
respectively, where at least one performance criterion is ameliorated or no
deterioration is observed.Figure 22
Stability
regionyi of the dynamic (K′=3) and static (K′=0) cases for K=4 with a reset of the K value of node 7 (asymmetric network of Figure 11).Figure 23
Throughput
of the dynamic (K′=3) and static (K′=0) cases for K=4 with a reset of K(K′=3) on node 7 of connection f (asymmetric network of Figure 11).Figure 24
Delay of
the dynamic (K′=3) and static (K′=0) cases for K=4 with a reset of K(K′=3) on node 7 of connection f (asymmetric network of Figure 11).


## 4.1. Symmetric Linear Network Case

### 4.1.1. Description of the Network

Our purpose by
studying the linear network case is to understand the advantage of the new
dynamic scheme so that we can understand the efficiency of the method on the
asymmetric case. Also, the linear symmetric network is simple to study
[4]. The
characteristics of this network are as follows: (1) equal number of neighbors,
that is, ni=2 for all nodes; (2) Pi=P;
(3) infinite number of nodes; (4) equal forwarding probability, that is, fi=f;
(5) Ps,d,
depends on the connection hop number of h,
thus Ps,d=P(h);
(6) there is only one path between two different nodes, that is, one way to
reach any destination from any source. The consequence of these hypothesis is
that the stability is the same for all nodes, that is, yi=y.
When we take a uniform probability to choose a given path of length h,
then P(h)=1/2B,
where B represents the maximum number of hops to reach
the farthest destination.


### 4.1.2. Main Expressions for Performance Evaluation

We will mainly
study the stability-throughput issue with the new scheme. In addition, the
probability of success and the average number of transmissions bring additional
material to understand what is happening in the network. Later, in the
asymmetric network section, the end-to-end delay gives more information about
stability of connections; while in the symmetric linear network, the stability
of a node is equivalent for all nodes, thus the variation of a node stability
informs about delay variation.General expressions for performance evaluation in
general networks were already derived in our paper [5], but in the linear symmetric
case, these expressions can be derived from [4]. Here, we include the fact that the limit number of
transmissions is the function of the number of hops. Let T:=1−Pi,s,d be the collision probability, Pi,s,d=(1−P)2,
and K(i,h) represents the value of Ki,s,d in K(i,h) notation, i represents the position of the node on the
path Rs,d.
For example, Ks,s,d=K(1,h), Kjs,s,d,s,d=K(2,h),
and so on. Let L(i,h) be the average number of transmissions (i.e., Li,s,d) of the node i on the path of length h.
Thus, L(i,h)=(1−TK(i,h))/(1−T).
For all paths, the average number of transmissions L(i,h) becomes (2)L=2(1−y)B2−B∑j=1B∑h=j+1BL(j,h)+2y∑h=1BP(h)L(1,h), where (B2−B) is the number of connections that traverse a
node. Note that L depends only on y and B for a given P.
It means that L for the dynamic case is different from the
static one.Now, to determiney,
we can write the balance rate equation of the forwarding queue. Then, the
arrival rate to the forwarding queue of a given node is equal to the departure
rate from it. The arrival rate from all sources of the network to a given node
can be written as (3)a=2y∑j=1B∑h=j+1BP(h)PL∏k=1j(1−TK(k,h)). This latter is formed by two
main parts: the first one is the traffic intensity of source nodes (of new
packets) and the second one is the end-to-end probability of success. The
departure rate is (4)d=(1−y)PL. This latter also is formed by
two parts: the first one is the intensity of forwarding packets (1−y) and the second is the rate of removing a
packet from the node by successful transmission or a drop after K transmissions. Therefore, the stability region
can be written as (5)y=11+2∑j=1B∑h=j+1BP(h)∏k=1j(1−TK(k,h)). The throughput on the path of
length h can be written as (6)thp(h)=yP(h)PL∏k=1h(1−TK(k,h)). The average throughput for all h is (7)thp¯=yPB⋅L⋅∑h=1BP(h)∏k=1h(1−TK(k,h)). The probability of success
between a couple of nodes on a path of length h is Psucc(h)=∏k=1h(1−TK(k,h)).
The average probability of success for all h is Psucc¯=(1/B)∑h=1BPsucc(h).


### 4.1.3. A Practical Description of a Dynamic Method

We use a simple method that gives a dynamic value ofK(i,h) depending on the length of a connection h,
on the position of the node i on the path Rs,d,
and on K′ the step of how
much we increase K on a given node i.
Each node i initializes K(i,h) to K.This method maintains an averageK of all K(i,h) (for i∈Rs,d∪{s}) values of each connection. For example, this
average K can be the default value of the maximum number
of transmissions in a network of static K.
Also, in this manner it will be easy to compare the static K case performance and the dynamic one.Practically, for each packet transmission, a nodei must know its K(i,h) on a given path (or connection) of length h.
In fact, it must determine the length h of the path from the routing, then its related position to the source. Supposing that K and K′ are known, node i can calculate easily its corresponding K(i,h) while maintaining an average K in the path. Then, it informs the MAC layer
about this K(i,h) new value.As an exterior observer point of
view, theK(i,h) values are attributed as follows: the middle
node has the value K (when h is even, we attribute K to the two middle
nodes), and on its both sides, K is decreased in the direction of the source
and increased in the direction of the destination by a value of K′ for each hop. On one side, whenever it is
impossible to decrease K,
the value of K(i,h) maintains its last value. On the other side, K(i,h) must maintain also the last value in a certain
level so that we maintain an average of K.For example, whenh=10,K=8, and K′=2,
the set values of K(i,h)
is attributed to
the set of nodes in Rs,d∪{s} starting from the source and ending with the
node before the destination, that is, {2,2,4,6,8,8,10,12,14,14}.
In this case, we have K(4,10)=6,K(5,10)=8,
and so forth. We could also use another method to attribute values of K(i,h).
The key idea of the dynamic scheme is to attribute the values of K(i,h) in an increasing manner starting from the
source of a connection till the destination. For that, a simple algorithm can
be turned on each node to determine its corresponding dynamic K to a given route Rs,d.


### 4.1.4. Analysis of the Numerical Results

We draw some
numerical results of the above formulas using the previous parametersB=10 and K=8 for the two cases K′=0 and K′=2.
The maximum hop number B=10 allows about 2*10 possible connections for each node. The
forwarding probability is set to f=0⋅8.
The numerical results concern the average number of transmissions and stability
for each node, then the end-to-end throughput and probability of success. We
are also interested in evaluating the behavior of these, for each transmission
probability, that is, when the channel suffer from
low-to-high contention. All these performance metrics are shown from Figures 2 to 5. The main
remarkable thing is that the stability and the throughput are considerably
ameliorated with the dynamic scheme (K′≠0) compared to the static K case (K′=0).Figure 2
Average number
of transmissionL for different K′.This remarkable amelioration is mainly due to the
following facts.(1)
The dynamic scheme privileges the forwarded
packets that come near the destination. It is better to encourage these packets
to reach their destination, otherwise, the network will suffer more wasted bandwidth.(2)
The flow of packets from each source is limited on
the first hops of each connection. If the network cannot support transporting
more packets on a connection, it is better to limit the flow of new entering
packets in the network. This is a load moderating issue.As a consequence, Figure2 shows that the average
number of attempts in the dynamic scheme (L(K′≠0)) is always lower than the number of attempts
in the static case, that is, L(K′≠0)≤L(K′=0).
(Let X(K′≠0) and X(K′=0) be two symbols, where X represents one of the parameters in the set {K,L,y,thp¯,Psucc¯} for the two dynamic and static K case,
resp.) It means that a packet needs less average number of retransmissions at each node
throughout a path Rs,d to be delivered on the destination, in the
dynamic case. Therefore, the service rate of the forwarding packets will be
faster. As shown in Figure 3, it has permitted a low load, and more new packets
have entered the network, indicating a higher region of stability. For that, y(K′≠0)≥y(K′=0).Figure 3
Stability region
for the linear case with static and dynamicK.We distinguish two states of the network for two
contention degrees when we use the dynamic scheme. These are shown on Figure4
where for a given P0 (P0≃0.55 in this example), the probability of success
for K′≠0 comes near the one for K′=0.
Therefore, we distinguish the following.Figure 4
Average
Probability of success for the linear case with static and dynamicK.Figure 5
Average
throughput for the linear case with static and dynamicK.(i) Thesevere state for a low-moderate contention: P≤P0 and Psucc¯(K′≠0)<Psucc¯(K′=0).
In this state, the nodes with K(K′≠0)<K have the aptitude to drop a lot of packets in
the first nodes (near the source) on a path Rs,d,
in such a manner that a less number of successful packets arrives to the
destination compared to the static K case. When dropping a lot of packets in the
network, the load of each node diminishes, thus y(K′≠0)≥y(K′=0).
Since the impact of the load in this state is higher than the end-to-end
probability of success, the average throughput in the network becomes larger,
that is, thp¯(K′≠0)≥thp¯(K′≠0),
see Figure 5. In low contention, we do not really need to limit a lot the
retransmission of packets since they have a higher chance to reach the
destination in the static K case. The load control appears to be more
efficient than controlling the success of packets to get a good throughput. In
fact, giving more chance of success to packets approaching the destination is
not the main reason of amelioration in low-channel contention case. Instead,
decreasing the limit number of retransmissions of source packets is more
important as it has the impact on the load of forwarding queues.(ii) Themoderate state for a moderate-high contention: P≥P0 and Psucc¯(K′≠0)≃Psucc¯(K′=0).
In this state, dropping packets with K(K′≠0)<K is more efficient than the severe state,
in such a manner that even the end-to-end probability of success comes closer
to the static case. In high contention, a packet that has traveled through many
nodes in the static K case is more susceptible to drop. When
dropping such packet, we loose all retransmission slots from the source until
its drop. Therefore, increasing K behind the middle node on a path Rs,d helps conserving the packets from drop and
minimizes the number of loosed slots. In this way, the throughput and the load
are ameliorated as shown in Figures 5 and 3, respectively. This also can be
verified with Figure 2, where L(K′≠0)≤L(K′=0).These two states can merge to one state for some
values ofK,K′, or B.
However, the dynamic scheme maintains its advantage compared to the static K case.


### 4.1.5. Impact ofB,K, and K′

We study the impact ofB,K, and K′ on the performance of the network. We proceed
by comparing the static and the dynamic case. We show on the following figures the gain ratio while using the
dynamic case in terms of these last parameters. The gain ratio of the
static-dynamic K for the average throughput and the stability
region, presented in Figures 7 to 10, is defined as (X(K′≠0)−X(K′=0))/X(K′=0),
where X is the average of thp¯ or y for all P.
From these figures, the gain ratio of the average throughput and the stability
region evolve in a similar way when varying B,K,
or K′.
Remark that the average throughput is mainly affected by the load variation of
each node from (7).(1)Impact ofB. Let ΔL be the difference between the average number
of transmissions for K′=0 and K′≠0,
that is, ΔL=L(K′=0)−L(K′≠0).ΔL is an increasing function with B as shown in Figure 6 which verifies the
increasing gain ratio of the Figure 7. The dynamic scheme has a good
performance in large multihop networks.Figure 6
ΔL versus B for different K,
for K′=2 and P=0.5.Figure 7
Gain ratio of
dynamic case compared to the static one versusB (linear network).(2)Impact ofK. When K tends toward large values, the two dynamic and
static cases tend to each other, that is, we tend to zero gain ratio. So, each
packet will be retransmitted until achieving a
success. It does neutralize our dynamic scheme. Also, the impact of K depends on K′ as we see in Figures 8 and 9. For some K near the value of K′ or multiple of it, we have picks of gain ratio
that decrease with K.
For K=5,
we have the maximum possible gain in these two figures. It is a question of how
we use K′ according to K so that the dynamic scheme operates in an
optimal point. In fact, for some values of K and K′,
the source nodes (and the nearest nodes to the source) may be affected
by
very low dynamic K or not (according to the scheme calculation of
dynamic K). This is why we can see picks of gain or not
in Figures 8 and 9. For a fixed K′ and P,
we plot the quantity ΔL as a function of K in Figure 6. We observe that for small B,ΔL decreases with K,
so in Figure 8, the gain ratio is also decreasing. Remark that Figure 8 (as
Figures 7, 9, and 10) presents the gain ratio for all P,
whereas Figure 6 is presented for a fixed P=0.5.
Therefore, for P=0.5 and large B,
our scheme obtains high performance with higher K.
For that, the impact of B is considerable compared to K.Figure 8
Gain ratio of
dynamic case compared to the static one versusK for K′=2 (linear network).Figure 9
Gain ratio of
dynamic case compared to the static one versusK for K′=4 (linear network).Figure 10
Gain ratio of
dynamic case compared to the static one versusK′ (linear network).(3)Impact ofK′. The dynamic scheme is defined for K′≤K.
From Figure 10, choosing K′=7 for K=8 causes severe drops at the beginning of a path
since K(K′≠0)=1 for K(K′≠0)<K.
Even though the gain ratio is clearly large. The difference between K′=2 and K′=4 in Figure 10 is explained by Figure 2 where L(K′=2)<L(K′=4).


## 4.1.1. Description of the Network

Our purpose by
studying the linear network case is to understand the advantage of the new
dynamic scheme so that we can understand the efficiency of the method on the
asymmetric case. Also, the linear symmetric network is simple to study
[4]. The
characteristics of this network are as follows: (1) equal number of neighbors,
that is, ni=2 for all nodes; (2) Pi=P;
(3) infinite number of nodes; (4) equal forwarding probability, that is, fi=f;
(5) Ps,d,
depends on the connection hop number of h,
thus Ps,d=P(h);
(6) there is only one path between two different nodes, that is, one way to
reach any destination from any source. The consequence of these hypothesis is
that the stability is the same for all nodes, that is, yi=y.
When we take a uniform probability to choose a given path of length h,
then P(h)=1/2B,
where B represents the maximum number of hops to reach
the farthest destination.


## 4.1.2. Main Expressions for Performance Evaluation

We will mainly
study the stability-throughput issue with the new scheme. In addition, the
probability of success and the average number of transmissions bring additional
material to understand what is happening in the network. Later, in the
asymmetric network section, the end-to-end delay gives more information about
stability of connections; while in the symmetric linear network, the stability
of a node is equivalent for all nodes, thus the variation of a node stability
informs about delay variation.General expressions for performance evaluation in
general networks were already derived in our paper [5], but in the linear symmetric
case, these expressions can be derived from [4]. Here, we include the fact that the limit number of
transmissions is the function of the number of hops. Let T:=1−Pi,s,d be the collision probability, Pi,s,d=(1−P)2,
and K(i,h) represents the value of Ki,s,d in K(i,h) notation, i represents the position of the node on the
path Rs,d.
For example, Ks,s,d=K(1,h), Kjs,s,d,s,d=K(2,h),
and so on. Let L(i,h) be the average number of transmissions (i.e., Li,s,d) of the node i on the path of length h.
Thus, L(i,h)=(1−TK(i,h))/(1−T).
For all paths, the average number of transmissions L(i,h) becomes (2)L=2(1−y)B2−B∑j=1B∑h=j+1BL(j,h)+2y∑h=1BP(h)L(1,h), where (B2−B) is the number of connections that traverse a
node. Note that L depends only on y and B for a given P.
It means that L for the dynamic case is different from the
static one.Now, to determiney,
we can write the balance rate equation of the forwarding queue. Then, the
arrival rate to the forwarding queue of a given node is equal to the departure
rate from it. The arrival rate from all sources of the network to a given node
can be written as (3)a=2y∑j=1B∑h=j+1BP(h)PL∏k=1j(1−TK(k,h)). This latter is formed by two
main parts: the first one is the traffic intensity of source nodes (of new
packets) and the second one is the end-to-end probability of success. The
departure rate is (4)d=(1−y)PL. This latter also is formed by
two parts: the first one is the intensity of forwarding packets (1−y) and the second is the rate of removing a
packet from the node by successful transmission or a drop after K transmissions. Therefore, the stability region
can be written as (5)y=11+2∑j=1B∑h=j+1BP(h)∏k=1j(1−TK(k,h)). The throughput on the path of
length h can be written as (6)thp(h)=yP(h)PL∏k=1h(1−TK(k,h)). The average throughput for all h is (7)thp¯=yPB⋅L⋅∑h=1BP(h)∏k=1h(1−TK(k,h)). The probability of success
between a couple of nodes on a path of length h is Psucc(h)=∏k=1h(1−TK(k,h)).
The average probability of success for all h is Psucc¯=(1/B)∑h=1BPsucc(h).


## 4.1.3. A Practical Description of a Dynamic Method

We use a simple method that gives a dynamic value ofK(i,h) depending on the length of a connection h,
on the position of the node i on the path Rs,d,
and on K′ the step of how
much we increase K on a given node i.
Each node i initializes K(i,h) to K.This method maintains an averageK of all K(i,h) (for i∈Rs,d∪{s}) values of each connection. For example, this
average K can be the default value of the maximum number
of transmissions in a network of static K.
Also, in this manner it will be easy to compare the static K case performance and the dynamic one.Practically, for each packet transmission, a nodei must know its K(i,h) on a given path (or connection) of length h.
In fact, it must determine the length h of the path from the routing, then its related position to the source. Supposing that K and K′ are known, node i can calculate easily its corresponding K(i,h) while maintaining an average K in the path. Then, it informs the MAC layer
about this K(i,h) new value.As an exterior observer point of
view, theK(i,h) values are attributed as follows: the middle
node has the value K (when h is even, we attribute K to the two middle
nodes), and on its both sides, K is decreased in the direction of the source
and increased in the direction of the destination by a value of K′ for each hop. On one side, whenever it is
impossible to decrease K,
the value of K(i,h) maintains its last value. On the other side, K(i,h) must maintain also the last value in a certain
level so that we maintain an average of K.For example, whenh=10,K=8, and K′=2,
the set values of K(i,h)
is attributed to
the set of nodes in Rs,d∪{s} starting from the source and ending with the
node before the destination, that is, {2,2,4,6,8,8,10,12,14,14}.
In this case, we have K(4,10)=6,K(5,10)=8,
and so forth. We could also use another method to attribute values of K(i,h).
The key idea of the dynamic scheme is to attribute the values of K(i,h) in an increasing manner starting from the
source of a connection till the destination. For that, a simple algorithm can
be turned on each node to determine its corresponding dynamic K to a given route Rs,d.


## 4.1.4. Analysis of the Numerical Results

We draw some
numerical results of the above formulas using the previous parametersB=10 and K=8 for the two cases K′=0 and K′=2.
The maximum hop number B=10 allows about 2*10 possible connections for each node. The
forwarding probability is set to f=0⋅8.
The numerical results concern the average number of transmissions and stability
for each node, then the end-to-end throughput and probability of success. We
are also interested in evaluating the behavior of these, for each transmission
probability, that is, when the channel suffer from
low-to-high contention. All these performance metrics are shown from Figures 2 to 5. The main
remarkable thing is that the stability and the throughput are considerably
ameliorated with the dynamic scheme (K′≠0) compared to the static K case (K′=0).Figure 2
Average number
of transmissionL for different K′.This remarkable amelioration is mainly due to the
following facts.(1)
The dynamic scheme privileges the forwarded
packets that come near the destination. It is better to encourage these packets
to reach their destination, otherwise, the network will suffer more wasted bandwidth.(2)
The flow of packets from each source is limited on
the first hops of each connection. If the network cannot support transporting
more packets on a connection, it is better to limit the flow of new entering
packets in the network. This is a load moderating issue.As a consequence, Figure2 shows that the average
number of attempts in the dynamic scheme (L(K′≠0)) is always lower than the number of attempts
in the static case, that is, L(K′≠0)≤L(K′=0).
(Let X(K′≠0) and X(K′=0) be two symbols, where X represents one of the parameters in the set {K,L,y,thp¯,Psucc¯} for the two dynamic and static K case,
resp.) It means that a packet needs less average number of retransmissions at each node
throughout a path Rs,d to be delivered on the destination, in the
dynamic case. Therefore, the service rate of the forwarding packets will be
faster. As shown in Figure 3, it has permitted a low load, and more new packets
have entered the network, indicating a higher region of stability. For that, y(K′≠0)≥y(K′=0).Figure 3
Stability region
for the linear case with static and dynamicK.We distinguish two states of the network for two
contention degrees when we use the dynamic scheme. These are shown on Figure4
where for a given P0 (P0≃0.55 in this example), the probability of success
for K′≠0 comes near the one for K′=0.
Therefore, we distinguish the following.Figure 4
Average
Probability of success for the linear case with static and dynamicK.Figure 5
Average
throughput for the linear case with static and dynamicK.(i) Thesevere state for a low-moderate contention: P≤P0 and Psucc¯(K′≠0)<Psucc¯(K′=0).
In this state, the nodes with K(K′≠0)<K have the aptitude to drop a lot of packets in
the first nodes (near the source) on a path Rs,d,
in such a manner that a less number of successful packets arrives to the
destination compared to the static K case. When dropping a lot of packets in the
network, the load of each node diminishes, thus y(K′≠0)≥y(K′=0).
Since the impact of the load in this state is higher than the end-to-end
probability of success, the average throughput in the network becomes larger,
that is, thp¯(K′≠0)≥thp¯(K′≠0),
see Figure 5. In low contention, we do not really need to limit a lot the
retransmission of packets since they have a higher chance to reach the
destination in the static K case. The load control appears to be more
efficient than controlling the success of packets to get a good throughput. In
fact, giving more chance of success to packets approaching the destination is
not the main reason of amelioration in low-channel contention case. Instead,
decreasing the limit number of retransmissions of source packets is more
important as it has the impact on the load of forwarding queues.(ii) Themoderate state for a moderate-high contention: P≥P0 and Psucc¯(K′≠0)≃Psucc¯(K′=0).
In this state, dropping packets with K(K′≠0)<K is more efficient than the severe state,
in such a manner that even the end-to-end probability of success comes closer
to the static case. In high contention, a packet that has traveled through many
nodes in the static K case is more susceptible to drop. When
dropping such packet, we loose all retransmission slots from the source until
its drop. Therefore, increasing K behind the middle node on a path Rs,d helps conserving the packets from drop and
minimizes the number of loosed slots. In this way, the throughput and the load
are ameliorated as shown in Figures 5 and 3, respectively. This also can be
verified with Figure 2, where L(K′≠0)≤L(K′=0).These two states can merge to one state for some
values ofK,K′, or B.
However, the dynamic scheme maintains its advantage compared to the static K case.


## 4.1.5. Impact ofB,K, and K′

We study the impact ofB,K, and K′ on the performance of the network. We proceed
by comparing the static and the dynamic case. We show on the following figures the gain ratio while using the
dynamic case in terms of these last parameters. The gain ratio of the
static-dynamic K for the average throughput and the stability
region, presented in Figures 7 to 10, is defined as (X(K′≠0)−X(K′=0))/X(K′=0),
where X is the average of thp¯ or y for all P.
From these figures, the gain ratio of the average throughput and the stability
region evolve in a similar way when varying B,K,
or K′.
Remark that the average throughput is mainly affected by the load variation of
each node from (7).(1)Impact ofB. Let ΔL be the difference between the average number
of transmissions for K′=0 and K′≠0,
that is, ΔL=L(K′=0)−L(K′≠0).ΔL is an increasing function with B as shown in Figure 6 which verifies the
increasing gain ratio of the Figure 7. The dynamic scheme has a good
performance in large multihop networks.Figure 6
ΔL versus B for different K,
for K′=2 and P=0.5.Figure 7
Gain ratio of
dynamic case compared to the static one versusB (linear network).(2)Impact ofK. When K tends toward large values, the two dynamic and
static cases tend to each other, that is, we tend to zero gain ratio. So, each
packet will be retransmitted until achieving a
success. It does neutralize our dynamic scheme. Also, the impact of K depends on K′ as we see in Figures 8 and 9. For some K near the value of K′ or multiple of it, we have picks of gain ratio
that decrease with K.
For K=5,
we have the maximum possible gain in these two figures. It is a question of how
we use K′ according to K so that the dynamic scheme operates in an
optimal point. In fact, for some values of K and K′,
the source nodes (and the nearest nodes to the source) may be affected
by
very low dynamic K or not (according to the scheme calculation of
dynamic K). This is why we can see picks of gain or not
in Figures 8 and 9. For a fixed K′ and P,
we plot the quantity ΔL as a function of K in Figure 6. We observe that for small B,ΔL decreases with K,
so in Figure 8, the gain ratio is also decreasing. Remark that Figure 8 (as
Figures 7, 9, and 10) presents the gain ratio for all P,
whereas Figure 6 is presented for a fixed P=0.5.
Therefore, for P=0.5 and large B,
our scheme obtains high performance with higher K.
For that, the impact of B is considerable compared to K.Figure 8
Gain ratio of
dynamic case compared to the static one versusK for K′=2 (linear network).Figure 9
Gain ratio of
dynamic case compared to the static one versusK for K′=4 (linear network).Figure 10
Gain ratio of
dynamic case compared to the static one versusK′ (linear network).(3)Impact ofK′. The dynamic scheme is defined for K′≤K.
From Figure 10, choosing K′=7 for K=8 causes severe drops at the beginning of a path
since K(K′≠0)=1 for K(K′≠0)<K.
Even though the gain ratio is clearly large. The difference between K′=2 and K′=4 in Figure 10 is explained by Figure 2 where L(K′=2)<L(K′=4).


## 4.2. Asymmetric Network Case

Consider an asymmetric static wireless network with 11
nodes as shown in Figure11. We choose the following parameters: fi≡f=0.8 and Pi in a manner of enabling stability, for all i.
Let P2=P3=P7=P8=0.3,P4=P10=0.4,P5=0.5 be the fixed transmission probabilities for
nodes 2, 3, 4, 5, 7, 8, and 10 while Pi≡P for all other i.
Many nodes need to have a fix transmission probabilities so to get stable
queues for all nodes. The default maximum number of transmissions is K.
In the static case, Ki,s,d≡K,
while in dynamic case, Ki,s,d is chosen using the dynamic scheme presented
previously (Sections
3 and 4.1). We implement this dynamic scheme in our
discrete time simulator, so we can evaluate performance and validate numerical
results with simulations.Figure 11
Ad hoc wireless
network.


### 4.2.1. A First Numerical and Simulation Study

Leta,b,c,d, and e be the five connections established on the
network of Figure 11, as indicated in the same figure. We compare from Figures
12 to 16 the dynamic (K=4 and K′=1) and the static (K=4 and K′=0) cases. Note that yj=1 for j∈{1,6,9,11},
since these nodes do not forward packets. Firstly, the forwarding source nodes
(3, 4, and 8) of the connections a, b,
and d have affected small dynamic K for their new packets (packets from Q): K3,3,6=K4,4,11=K8,8,2=3 and higher dynamic K for their forwarding packets: K3,8,2=K4,3,2=K8,11,6=5 and K4,6,7=4 (see Table 1 for K′=1 and Table 2 for K′=2). Note that “Conn." means
“connection." In fact, there are two advantages on giving smaller K for new packets. The first one is that it
gives more priority to the forwarding queue. Therefore, we observe less load,
then more aptitude to send new packets. The second one is that it can optimize
the load on the nodes belonging to the source connection, in a saturated
network case. In fact, it can make severe drops of
new packets (due to small K) that can diminish the flow of packets in a
connection and maintain necessary packets. Figure 12 supports our comment: the
stability region or the aptitude of sending new packets is considerably
ameliorated in nodes 3, 4,
and 8.
In addition, the throughput of connection d has beneficed from the increase of y8 of its source node 8, while the two others a and b have maintained their throughput
approximatively unchanged.Table 1
Values of the
dynamic maximum number of transmissions forK′=1 and K=4.
Nodes23456781011Conn.a003405000Conn.b435000000Conn.c000000543Conn.d050400300Conn.e004530000Table 2
Values of the
dynamic maximum number of transmissions forK′=2 and K=4.
Nodes23456781011Conn.a002406000Conn.b426000000Conn.c000000642Conn.d060400200Conn.e004620000Figure 12
Stability regionyi of the dynamic (K′=1) and static (K′=0) cases for K=4 (nodes 3, 4, and 8 of the asymmetric network
of Figure 11).Secondly, as the nodes6 and 11 do not forward packets in our example, then y6=y11=1.
These two nodes are the source of connections e and c,
respectively. From Figure 14, the throughput of these two connections are
clearly higher in the dynamic scheme and do not depend on any forwarding queue
loads in these connections. However, the packets sent from nodes 6 and 11 are
limited by the fact that K6,6,7=K11,11,6=3,
but there are privileged at nodes 5 and 8 with K5,6,7=K8,11,6=5.
Each drop at these latter nodes is more expensive than the drop at the source
nodes (as explained previously). For that, the throughput of these connections
(see Figure 14) was only affected by the end-to-end success of packets in an
interval of time without the impact of y6 and y11 which are the source
aptitudes of sending new packets. Note that nodes 2, 5, 7, and 10
have not really changed their region stability with the dynamic scheme in this
example (see Figure 13).Figure 13
Stability regionyi of the dynamic (K′=1) and static (K′=0) cases for K=4 (nodes 2, 5, 7, and 10 of the asymmetric
network of Figure 11).Figure 14
Throughput of the dynamic
(K′=1) and static (K′=0) cases for K=4 (asymmetric network of Figure 11).Thirdly, the end-to-end delay of a
connection gives a global vision on the stability of nodes that forms this
connection. Precisely, it is mainly affected by the waiting time on the
forwarding intermediate queues. In Figure15, the high delay of connection c clearly reflects the high and moderate charges
of nodes 10 and 8 shown in Figures 13 and 12, respectively. In
Figure 16, connection a has maintained the same delay in the dynamic
as in the static case. This was a consequence of the y5 and y7 unchanging (not so changed) in these two
cases. Delay of connections b, c,
and e have been ameliorated in the dynamic case due
to the forwarding aptitude of source nodes 4 and 8 that belong to these connections.Figure 15
Delay of the
dynamic (K′=1) and static (K′=0) cases for K=4 (connections b and c of the asymmetric network of Figure 11).Figure 16
Delay of the
dynamic (K′=1) and static (K′=0) cases for K=4 (connections a, d,
and e of the asymmetric network of Figure 11).What about the gain percentages of our scheme compared
to the static one? On one hand, we can observe from the presented Figures14,
15, and 16 for
K′=1
that the gain varies in function of the
probability of transmission. Therefore, for a P=0.4,
the throughput amelioration reaches 20% for connection d and is around 9% for connections c and e.
The delay for this same P is around 15% for connection b and around 11% for connections c and e.
On the other hand, Figures 17 and 18 can show a gain up to 50% for the throughput and up to 30% for the delay, for K′=2.
In the following paragraph, we will discuss some issues from these figures.Figure 17
Throughput of the
dynamic (K′=2) and static (K′=0) cases for K=4 (asymmetric network of Figure 11).Figure 18
Delay of the dynamic (K′=2) and static (K′=0) cases for K=4 (asymmetric network of Figure 11).


### 4.2.2. Discussion

Here, we start
our discussion on the observations of previous figures of the asymmetric
network. In summary, the dynamic scheme has better performances when some of
the source nodes collaborate by forwarding packets and when these kinds of
sources are well distributed in the network. In fact, there are two properties
that help a connection to get a good performance:(1)
a connection must include within its
intermediate nodes a source node of another connection;(2)
the source node of a connection must not forward
packets.The first one
ameliorates the delay and the second one the throughput. These two properties
are jointly found in connectionsc and e.
Furthermore, the good performance (of throughput and delay) of connection c and e confirms this conclusion. In fact, nodes 11 and 6 are two nodes that do not forward packets (see
network of Figure 11) and in addition they are sources of the connections c and e,
respectively. Therefore, the traffic intensity from these two nodes to their
corresponding connections is maximal since no forwarding packets are to be
transmitted. This is why we can expect a good throughput. Furthermore, the set
of intermediate nodes of connections c and e contains a source node of other connections:
node 8 for connection c and node 4 for connection e.
These latter source nodes experience less delay due to the fact that they have
been affected lower limit number of retransmissions. Consequently, the
end-to-end delay of connections c and e would be lower.When one of these two properties is not found, then
threesituations are presented: a connection of the dynamic scheme(1)
maintains unchanged one performance
criterion (throughput or delay) and ameliorates the
other one;(2)
deteriorates one performance criterion and
ameliorates the other one;(3)
maintains unchanged the performance. These three situations are with comparison to the static case. An example of the first and the second
situation is the connections a, b,
and d in Figures 17 and 18 depending on the
transmission probability. In the second situation, the new scheme does not
overcome the existing tradeoff throughput delay for a given connection, but it
enables a benefit to other connections, and thus the aggregate performance of
the network is ameliorated. To overcome this tradeoff of some given connections
of this second situation, we have introduced to the new dynamic scheme
the capability to reset the dynamic value of K,
that is, to reallocate the default value K instead of the dynamic value only on the case
where K(K′≠0)>K(K′=0).
We study this option of reallocating K in the next section and we call it the reset
technique.


### 4.2.3. A Second Simulation Study with the Reset Technique

Here, we consider only three connectionsa, b,
and f,
where f is formed by the successive nodes 9-10-7-3 with node 9 as a source and node 3 as a destination. a and b are the same as previously
mentioned. Connection b causes node 4 to forward. The default value of K is maintained to 4. But, we choose K′=3.
In this manner, the value of K(K′=3) for node 7 is set to 7 for the two connections a and f.
Therefore, the stability of node 7 becomes critical and is penalized when the
contention on the channel increases: many retransmissions of each single packet
causes more additional waiting time on the forwarding queue. So the choice of
high K(K′=3) on this node is not really judicious for
itself as shown in Figure 19: y7(K′=3)<y7(K′=0),
nor for the connection delays as shown in Figure 21. However, a considerable
amelioration on the throughput is clearly observed in Figure 20.Figure 19
Stability regionyi of the dynamic (K′=3) and static (K′=0) cases for K=4 (asymmetric network of Figure 11).Figure 20
Throughput of the
dynamic (K′=3) and static (K′=0) cases for K=4 (asymmetric network of Figure 11).Figure 21
Delay of the
dynamic (K′=3) and static (K′=0) cases for K=4 (asymmetric network of Figure 11).These observations correspond to the secondsituation described previously. Each node suffering from a degradation of stability
appeals the reset technique. In fact, each node uses the following three
steps to test and apply if needed, the reset technique as follows.(1)
If the average queue size exceeds a given
threshold, then go to the second step, else do nothing. The average waiting
time in the queue can be another criteria to decide whether to use thereset
technique or not. It is directly related to the queue size. Also, the
estimation of y(K′=0) and the measurement of y(K′≠0) can also be used for the decision.(2)
Choose judiciously a connection (according to
its data type and if it is not yet chosen) between those traversing it.(3)
Apply the reset ofK(K′≠0) to the default value K,
that is, set K(K′≠0)≡K for the connection chosen in step 2.In our example, thereset technique is applied
to the node 7 of the connection f.
Figures 22, 23, and 24 show that node 7 and connection f restore their performances as in the static
case. The remarkable thing is that even the connection a has seen its delay ameliorated due to the load
reduction on the node 7 forwarding queue while the throughput of a was not really affected in this example.
Hence, after applying the reset technique to node 7, connections a and f are now classified in the first and the third situations,
respectively, where at least one performance criterion is ameliorated or no
deterioration is observed.Figure 22
Stability
regionyi of the dynamic (K′=3) and static (K′=0) cases for K=4 with a reset of the K value of node 7 (asymmetric network of Figure 11).Figure 23
Throughput
of the dynamic (K′=3) and static (K′=0) cases for K=4 with a reset of K(K′=3) on node 7 of connection f (asymmetric network of Figure 11).Figure 24
Delay of
the dynamic (K′=3) and static (K′=0) cases for K=4 with a reset of K(K′=3) on node 7 of connection f (asymmetric network of Figure 11).


## 4.2.1. A First Numerical and Simulation Study

Leta,b,c,d, and e be the five connections established on the
network of Figure 11, as indicated in the same figure. We compare from Figures
12 to 16 the dynamic (K=4 and K′=1) and the static (K=4 and K′=0) cases. Note that yj=1 for j∈{1,6,9,11},
since these nodes do not forward packets. Firstly, the forwarding source nodes
(3, 4, and 8) of the connections a, b,
and d have affected small dynamic K for their new packets (packets from Q): K3,3,6=K4,4,11=K8,8,2=3 and higher dynamic K for their forwarding packets: K3,8,2=K4,3,2=K8,11,6=5 and K4,6,7=4 (see Table 1 for K′=1 and Table 2 for K′=2). Note that “Conn." means
“connection." In fact, there are two advantages on giving smaller K for new packets. The first one is that it
gives more priority to the forwarding queue. Therefore, we observe less load,
then more aptitude to send new packets. The second one is that it can optimize
the load on the nodes belonging to the source connection, in a saturated
network case. In fact, it can make severe drops of
new packets (due to small K) that can diminish the flow of packets in a
connection and maintain necessary packets. Figure 12 supports our comment: the
stability region or the aptitude of sending new packets is considerably
ameliorated in nodes 3, 4,
and 8.
In addition, the throughput of connection d has beneficed from the increase of y8 of its source node 8, while the two others a and b have maintained their throughput
approximatively unchanged.Table 1
Values of the
dynamic maximum number of transmissions forK′=1 and K=4.
Nodes23456781011Conn.a003405000Conn.b435000000Conn.c000000543Conn.d050400300Conn.e004530000Table 2
Values of the
dynamic maximum number of transmissions forK′=2 and K=4.
Nodes23456781011Conn.a002406000Conn.b426000000Conn.c000000642Conn.d060400200Conn.e004620000Figure 12
Stability regionyi of the dynamic (K′=1) and static (K′=0) cases for K=4 (nodes 3, 4, and 8 of the asymmetric network
of Figure 11).Secondly, as the nodes6 and 11 do not forward packets in our example, then y6=y11=1.
These two nodes are the source of connections e and c,
respectively. From Figure 14, the throughput of these two connections are
clearly higher in the dynamic scheme and do not depend on any forwarding queue
loads in these connections. However, the packets sent from nodes 6 and 11 are
limited by the fact that K6,6,7=K11,11,6=3,
but there are privileged at nodes 5 and 8 with K5,6,7=K8,11,6=5.
Each drop at these latter nodes is more expensive than the drop at the source
nodes (as explained previously). For that, the throughput of these connections
(see Figure 14) was only affected by the end-to-end success of packets in an
interval of time without the impact of y6 and y11 which are the source
aptitudes of sending new packets. Note that nodes 2, 5, 7, and 10
have not really changed their region stability with the dynamic scheme in this
example (see Figure 13).Figure 13
Stability regionyi of the dynamic (K′=1) and static (K′=0) cases for K=4 (nodes 2, 5, 7, and 10 of the asymmetric
network of Figure 11).Figure 14
Throughput of the dynamic
(K′=1) and static (K′=0) cases for K=4 (asymmetric network of Figure 11).Thirdly, the end-to-end delay of a
connection gives a global vision on the stability of nodes that forms this
connection. Precisely, it is mainly affected by the waiting time on the
forwarding intermediate queues. In Figure15, the high delay of connection c clearly reflects the high and moderate charges
of nodes 10 and 8 shown in Figures 13 and 12, respectively. In
Figure 16, connection a has maintained the same delay in the dynamic
as in the static case. This was a consequence of the y5 and y7 unchanging (not so changed) in these two
cases. Delay of connections b, c,
and e have been ameliorated in the dynamic case due
to the forwarding aptitude of source nodes 4 and 8 that belong to these connections.Figure 15
Delay of the
dynamic (K′=1) and static (K′=0) cases for K=4 (connections b and c of the asymmetric network of Figure 11).Figure 16
Delay of the
dynamic (K′=1) and static (K′=0) cases for K=4 (connections a, d,
and e of the asymmetric network of Figure 11).What about the gain percentages of our scheme compared
to the static one? On one hand, we can observe from the presented Figures14,
15, and 16 for
K′=1
that the gain varies in function of the
probability of transmission. Therefore, for a P=0.4,
the throughput amelioration reaches 20% for connection d and is around 9% for connections c and e.
The delay for this same P is around 15% for connection b and around 11% for connections c and e.
On the other hand, Figures 17 and 18 can show a gain up to 50% for the throughput and up to 30% for the delay, for K′=2.
In the following paragraph, we will discuss some issues from these figures.Figure 17
Throughput of the
dynamic (K′=2) and static (K′=0) cases for K=4 (asymmetric network of Figure 11).Figure 18
Delay of the dynamic (K′=2) and static (K′=0) cases for K=4 (asymmetric network of Figure 11).


## 4.2.2. Discussion

Here, we start
our discussion on the observations of previous figures of the asymmetric
network. In summary, the dynamic scheme has better performances when some of
the source nodes collaborate by forwarding packets and when these kinds of
sources are well distributed in the network. In fact, there are two properties
that help a connection to get a good performance:(1)
a connection must include within its
intermediate nodes a source node of another connection;(2)
the source node of a connection must not forward
packets.The first one
ameliorates the delay and the second one the throughput. These two properties
are jointly found in connectionsc and e.
Furthermore, the good performance (of throughput and delay) of connection c and e confirms this conclusion. In fact, nodes 11 and 6 are two nodes that do not forward packets (see
network of Figure 11) and in addition they are sources of the connections c and e,
respectively. Therefore, the traffic intensity from these two nodes to their
corresponding connections is maximal since no forwarding packets are to be
transmitted. This is why we can expect a good throughput. Furthermore, the set
of intermediate nodes of connections c and e contains a source node of other connections:
node 8 for connection c and node 4 for connection e.
These latter source nodes experience less delay due to the fact that they have
been affected lower limit number of retransmissions. Consequently, the
end-to-end delay of connections c and e would be lower.When one of these two properties is not found, then
threesituations are presented: a connection of the dynamic scheme(1)
maintains unchanged one performance
criterion (throughput or delay) and ameliorates the
other one;(2)
deteriorates one performance criterion and
ameliorates the other one;(3)
maintains unchanged the performance. These three situations are with comparison to the static case. An example of the first and the second
situation is the connections a, b,
and d in Figures 17 and 18 depending on the
transmission probability. In the second situation, the new scheme does not
overcome the existing tradeoff throughput delay for a given connection, but it
enables a benefit to other connections, and thus the aggregate performance of
the network is ameliorated. To overcome this tradeoff of some given connections
of this second situation, we have introduced to the new dynamic scheme
the capability to reset the dynamic value of K,
that is, to reallocate the default value K instead of the dynamic value only on the case
where K(K′≠0)>K(K′=0).
We study this option of reallocating K in the next section and we call it the reset
technique.


## 4.2.3. A Second Simulation Study with the Reset Technique

Here, we consider only three connectionsa, b,
and f,
where f is formed by the successive nodes 9-10-7-3 with node 9 as a source and node 3 as a destination. a and b are the same as previously
mentioned. Connection b causes node 4 to forward. The default value of K is maintained to 4. But, we choose K′=3.
In this manner, the value of K(K′=3) for node 7 is set to 7 for the two connections a and f.
Therefore, the stability of node 7 becomes critical and is penalized when the
contention on the channel increases: many retransmissions of each single packet
causes more additional waiting time on the forwarding queue. So the choice of
high K(K′=3) on this node is not really judicious for
itself as shown in Figure 19: y7(K′=3)<y7(K′=0),
nor for the connection delays as shown in Figure 21. However, a considerable
amelioration on the throughput is clearly observed in Figure 20.Figure 19
Stability regionyi of the dynamic (K′=3) and static (K′=0) cases for K=4 (asymmetric network of Figure 11).Figure 20
Throughput of the
dynamic (K′=3) and static (K′=0) cases for K=4 (asymmetric network of Figure 11).Figure 21
Delay of the
dynamic (K′=3) and static (K′=0) cases for K=4 (asymmetric network of Figure 11).These observations correspond to the secondsituation described previously. Each node suffering from a degradation of stability
appeals the reset technique. In fact, each node uses the following three
steps to test and apply if needed, the reset technique as follows.(1)
If the average queue size exceeds a given
threshold, then go to the second step, else do nothing. The average waiting
time in the queue can be another criteria to decide whether to use thereset
technique or not. It is directly related to the queue size. Also, the
estimation of y(K′=0) and the measurement of y(K′≠0) can also be used for the decision.(2)
Choose judiciously a connection (according to
its data type and if it is not yet chosen) between those traversing it.(3)
Apply the reset ofK(K′≠0) to the default value K,
that is, set K(K′≠0)≡K for the connection chosen in step 2.In our example, thereset technique is applied
to the node 7 of the connection f.
Figures 22, 23, and 24 show that node 7 and connection f restore their performances as in the static
case. The remarkable thing is that even the connection a has seen its delay ameliorated due to the load
reduction on the node 7 forwarding queue while the throughput of a was not really affected in this example.
Hence, after applying the reset technique to node 7, connections a and f are now classified in the first and the third situations,
respectively, where at least one performance criterion is ameliorated or no
deterioration is observed.Figure 22
Stability
regionyi of the dynamic (K′=3) and static (K′=0) cases for K=4 with a reset of the K value of node 7 (asymmetric network of Figure 11).Figure 23
Throughput
of the dynamic (K′=3) and static (K′=0) cases for K=4 with a reset of K(K′=3) on node 7 of connection f (asymmetric network of Figure 11).Figure 24
Delay of
the dynamic (K′=3) and static (K′=0) cases for K=4 with a reset of K(K′=3) on node 7 of connection f (asymmetric network of Figure 11).


## 5. Playout Delay Control in VOIP

After we have
seen in general the performances of the scheme, here we study the performances
for multimedia applications with delay constraint. Delay, jitter, and packet
loss are the main factors impacting audio quality in interactive multimedia
applications. In ad hoc network, the audio packets transmitted from a source to
a destination can encounter variable delay while crossing the intermediate
nodes. In order to play the receiver stream, an application must buffer the
packets and play them out after a certain deadline to get again a periodic
stream at the application level. Packets arriving after their corresponding
deadline are considered lost and are not played out. For that, we need to fix a
delay limit needed for some type of application.LetTs,d be the maximum delay limit for a connection
between s and d allowed for each packet in this connection.
The instantaneous delay of each packet must not exceed Ts,d,
if so, the destination node must drop this packet. For large Ts,d,
we get less packet dropped and the end-to-end delay may be greater. Then
clearly we see the tradeoff generated by setting the value of Ts,d.
The end-to-end effective throughput thpes,d of a given connection Rs,d can be written as (8)thpes,d=thps,d⋅P(delay≤Ts,d), where thps,d is the end-to-end throughput without the
constraint on the delay, and P(delay>Ts,d) is the probability to drop a packet when its
delay exceeds Ts,d.From Figure25 to 28, we simulate two scenarios where
in the first one we consider that the delay limit for all connections is T=65 and in the second one T=100.
The effective throughput shown form these figures is considerably ameliorated
in the dynamic scheme, specially for T=65,
for all connections. While for high-delay limit T=100,
the performance differences are less for connections a and c.
It is now clear that it is better to drop packets in intermediate nodes instead
of dropping them in the destination due to delay constraint. This is why we
have an addition amelioration from Figures 25 and 26. An extension of our
scheme can take into consideration the priority of real-time packets. In fact,
a high-priority packet can get a minimum limit number of retransmission, not less
than the default K.
Furthermore, it is also interesting to see that K′ can also be adjusted according to the delay
constraint Ts,d of a given connection.Figure 25
The effective
throughput of the dynamic (K′=2) and the static (K′=0) cases for K=4 and T=65 (connections a, b,
and c of the asymmetric network of Figure 11).Figure 26
The effective
throughput of the dynamic (K′=2) and the static (K′=0) cases for K=4 and T=65 (connections d and e of the asymmetric network of Figure 11).Figure 27
The effective
throughput of the dynamic (K′=2) and the static (K′=0) cases for K=4 and T=100 (connections a, b,
and c of the asymmetric network of Figure 11).Figure 28
The effective throughput
of the dynamic (K′=2) and the static (K′=0) cases for K=4 and T=100 (connections d and e of the asymmetric network of Figure 11).


## 6. Conclusion

In this paper,
we have presented a new cross-layer scheme using the limit number of
retransmission parameter in a saturated ad hoc network, so a dynamic routing
can be achieved. The advantage of this scheme consists
of the following.(1)
It is a simple distributed cross-layer scheme that
can be implemented easily on each node.(2)
It does not need external information about
neighboring or other things, but the decision of setting the limit number of
retransmission can be taken locally at each node with the help of routing
information from the network layer.(3)
The limit number of retransmission has a direct
impact on the end-to-end throughput and delay in the saturated network case.(4)
It mainly controls packets flow by allocating
priority to some of them using route information. It is thus efficient in
congestion situations.(5)
An advanced configuration of the scheme is
possible by also adjusting the step parameterK′.The performance evaluation study using analytical and
simulation tools has shown that in the case of symmetric linear networks the
scheme significantly improves the stability and the throughput for all
transmission probabilities. We have also studied the impact of several parameters
such as the maximum length of connections and seen that we take benefit from
large connections. On the other hand, asymmetric networks performances are
directly related to the topology and the neighboring distribution. However, we
have identified two properties that a connection must have to get both the
throughput and the delay ameliorated. If one of these is not presented, then
connection performance can be classified on one of 3situations where we
can benefit or leave unchanged the performances. A reset technique was
integrated to the scheme so to optimize performances. In addition, for
multimedia applications with delay constraint, we can achieve higher effective
throughput as observed in the simulation results.Moreover, it will be interesting to apply our results
in this paper to study its exact behavior using the IEEE 802.11 DCF operation.
In fact, an extension of our model presented in this paper is sufficient to
study analytically the problem, and some simulations can track the real
functioning of the network. It is always possible to enhance the scheme
according to the applications need or according to the complexity that we
allow. It can be also integrated with other schemes. A content-based dynamic
retransmission can be one of the directions to enhance the scheme for video
streaming over wireless. In fact, based on the priority of multimedia packet,
we can adjust the retransmission limit locally in each node. Therefore, we get
a cross-layer-based APP/NETWORK/MAC layers. Improving the QoS of multimedia
traffic in multihop ad hoc networks is a real issue, specially, if we need to
work on with analytical multilayer model. This is an open issue since high
interactions and correlations may exist between different layers in the same
node and different nodes in the same network.



---

*Source: 414073-2008-05-25.xml*