3TECHNICAL PRELIMINARIES
In this section, we introduce the preliminary knowledge
related to our work, and provide a motivating example to
illustrate the importance of exploiting spectrum spatial
reusability for routing in multi-hop wireless networks.
3.1 System Model
We consider a static multi-hop wireless network with a set
of N nodes. For clarity, we assume that the nodes use the
same transmission rate, and do not employ any power
control scheme in this work.
1
Let p
ij
be the link delivery probability from node i to
node j, i.e., if a packet is transmitted from node i to node j,
then with probability p
ij
the packet can be decoded. That is
to say, to deliver a packet from node i to node j, node i is
expected to do
z
i
¼
1
p
ij
p
ji
; (1)
times of transmissions, when MAC-layer acknowledgment
is required. We note that in practice, the probability of p
ij
is
related to packet size of data packet or MAC-layer ACK.
This is commonly considered in the single path routing as
expected transmission count metric (ETX) [6]. Let T
data
and
T
ack
denote the transmission time of a data packet and an
acknowledgment, respectively. Then, the expected time to
deliver a packet from node i to node j is
t
ij
¼ z
i
T
data
þ z
i
p
ij
T
ack
¼
T
data
p
ij
p
ji
þ
T
ack
p
ji
:
(2)
In the case of anypath routing (e.g., [4], [13]), the hyper-
link from a sender to a set of forwarders and the end-to-end
acknowledgment are usually used instead of previous
deterministic link and MAC-layer ACK, respectively. Let
F
i
N be the forwarding set of node i. Then, to deliver a
packet from node i to at least one of the nodes in its for-
warding set F
i
, the expected number of transmissions
needed to be done by node i is
z
iF
i
¼
1
1
Q
j2F
i
ð1 p
ij
Þ
: (3)
This cost metric is called the expected number of anypath
transmissions (EATX) [4], [32]. Since the packets are nor-
mally sent in batches and only an end-to-end ACK is
needed for a whole batch in anypath routing, the cost of
ACK is very small compared with the total size of the pack-
ets in the batch and can normally be ignored [4]. Therefore,
the expected time to deliver a packet from node i to at least
one of the nodes in its forwarding set F
i
is
t
iF
i
¼ z
iF
i
T
data
¼
T
data
1
Q
j2F
i
ð1 p
ij
Þ
:
(4)
Since wireless signal fades in the process of propaga-
tion, two wireless (hyper-)links can work simultaneously,
if they are spatially far away en ough from each other. We
define non-interfering set I, in which any pair of (hyper-)
links a re out of the interference range of each other, i.e.,
the (hyper-)links in the same non-interfering set can work
at the same time.
3.2 Improper Usage of ETX/EATX
Although ETX/EATX has been widely incorporated into
many single-path/anypath routing protocols, it is still not
properly used, especially in multi-hop wireless networks.
There are two reasons:
1) ETX/EATX is designed to capture the quality of a
single-hop wireless link/hyperlink. It does not natu-
rally indicate the transmission capability of an end-
to-end (any)path.
2) ETX/EATX-based routing protocols tend to choose
the route that minimizes the sum of the ETXs/
EATXs of the links/hyperlinks involved. Since the
wireless communication media has the property of
spatial reusability, minimizing the total number of
transmissions to deliver a packet from a source node
to a destination node does not necessarily maximize
the end-to-end throughput.
Here, we use a toy example as shown in Fig. 1 to illus-
trate the importance of considering spatial reusability of the
communication media in single-path routing in wireless
networks. In the example, we have four intermediate nodes
fA; B; C; Dg between source node Src and destination node
Dst. The dashed circle centered at each of the nodes indi-
cates the interference range of the node; and the ETX cost is
marked beside each of the wireless links.
There are two paths from node Src to node Dst:
Path I : Src B C D Dst;
Path II : Src A B C D Dst:
The ETX cost of path I and path II is 3:3 þ 1:7 þ 1:9 þ
2:0 ¼ 8:9 and 2:4 þ 1:7 þ 1:7 þ 1:9 þ 2:0 ¼ 9:7, respectively.
Since path I has a smaller ETX cost, it is normally selected
by traditional ETX-based routing protocols, and is expected
to have better performance. However, our simulation
results show that path II achieves an average end-to-end
throughput of 753 Kbps, which is 10.2 percent higher than
683 Kbps achieved by path I, when the transmission rate is
Fig. 1. Importance of spatial reusability.
1. However, our approach can be extended to adapt to multiple
transmission rates, as long as the conflict graph of links can be calcu-
lated. We leave it to our future work.
246 IEEE TRANSACTIONS ON COMPUTERS, VOL. 65, NO. 1, JANUARY 2016