Department of Computer Science, University of Victoria,
Victoria, Canada
e-mail: wkui@cs.uvic.ca
Keywords Wireless mesh networks  Anycast 
Unicast  Multicast  Coding
1 Introduction
Recently, wireless mesh networks (WMNs) have emerged as
a promising technology to provide the broadband network
services. Compared with infrastructure-based networks,
WMNs have advantages such as easy deployment, flexible
network architecture, self-configuration, and many more.
With the increase in both wireless channel bandwidth and the
computational capability of wireless devices, WMNs now
can be used to support delay-sensitive applications such as
video streaming or interactive gaming. Such delay-sensitive
applications require that the data content should be propagated
to the destination node(s) in a timely fashion.
The wireless devices in WMNs, however, are usually
powered by batteries, and as such energy consumption
becomes a critical issue, particularly when low-end devices
such as sensors or smartphones are used as mesh nodes. As
a common practice to save energy, sleep scheduling (i.e.,
let the devices go to sleep whenever they become idle) has
been broadly used, for example, in wireless sensor networks
[1, 2] and DigiMesh [3] or ZigBee [4] based WMNs.
While sleep scheduling can save energy, it may incur extra
delay because a node along an end-to-end path may need to
wait for its next hop to wake up before it can transmit. Such
a waiting delay could be intolerable for delay-sensitive
applications. In addition, wireless channel is usually
unreliable, and packet retransmission to improve reliability
can have a negative impact on the end-to-end delay guarantee.
To sum up, reducing end-to-end delay and guaranteeing
reliable data delivery are two contradicting core
challenges in WMNs.
123
1274 Wireless Netw (2011) 17:1273–1285
To reduce the end-to-end delay, an interesting method is
to transmit packets with anycast [5]. Instead of having one
designated next hop under the traditional packet forwarding
schemes, each intermediate node maintains multiple
next hops in its forwarding set. The sending node only
needs to wait for any one of the next hops to wake up
before it can transmit the packet. The end-to-end delay is
thus reduced for the waiting delay at each hop. Nevertheless,
existing anycast schemes assume reliable radio
channels and ignore packet losses [5].
To deal with the unreliable channels, packet retransmissions
based on the feedback from the receiving nodes
are usually adopted. In delay-sensitive applications such as

multimedia streaming, however, in-time packet delivery is

much more important since late packets may be useless.
We hence should care more about the end-to-end delay as
long as the data content can be correctly delivered with a
high probability. Due to this reason, TCP-like end-to-end
feedback control for reliable per packet delivery is generally
avoided for delay-sensitive applications. Following the
similar spirit, per-hop retransmission due to channel errors
may be also undesirable.
By allowing multiple next hop nodes to receive packets,
anycast opens the good opportunities for reducing endto-end
delay and in the meantime achieves a high packet
delivery ratio. Anycast alone, however, lacks a control
knob that can be used to tune the balance between the endto-end
delay and the reliability. We are thus motivated to
design a good mechanism to enhance reliability while the
end-to-end delay is effectively controlled.
In this paper, to reduce the end-to-end delay and
improve the reliability, we propose using coded anycast
packet forwarding (CAPF) scheme in unreliable WMNs for
unicast and multicast. To be specific, instead of designating
one determined next hop at each step, any active node in a
forwarding set can be the candidate to propagate the
packet. A sending node can forward the packet once any
one of the next hops in its forwarding set wakes up. In
addition, with coding, the destination node can decode the
native packets once it receives a certain number of coded
packets propagated from the source node.
Recently, coding, e.g., source coding and network coding
[6], has received extensive research attention in the
networking area, and it has been shown that coding can
improve network reliability by reducing the number of
packet retransmissions in wireless lossy networks [7–9].
Our work differs from the previous literature in that previous
work is mainly focused on the traditional packet
forwarding scheme, i.e., a given single path for unicast or a
given multicast tree for multicast [9]. In contrast, with
anycast packet forwarding scheme, the next hop for each
step is not designated but is determined by the stochastic
sleep scheduling. Thus, the derivation of the delay and the
123
reliability with coded anycast schemes needs to be reconsidered.
The previous literature on anycast [5] has tried to

minimize the delay in low duty-cycle wireless network.

این مطلب را هم بخوانید :

However, the existing work assumes packets are not coded
and wireless channels are reliable [5]. While network
coding based opportunistic routing [10, 14] is similar to our
work, the underlying routing structure in [10, 14] is different
and does not take advantages of anycast. To the best
of our knowledge, no previous work has considered the
coded anycast packet forwarding schemes for unicast as
well as multicast to better trade off the end-to-end delay
and the reliability.
The main contributions of our work are summarized as
follows.
(1) We study the coded anycast packet forwarding
scheme from the aspects of both end-to-end delay
and reliability in unreliable WMNs.
(2) We theoretically derive the end-to-end delay and the
reliability for the unicast communication with our
coded anycast packet forwarding scheme. The simulation
results confirm the advantages of coded anycast
packet forwarding method compared to other packet