IEICE TRANS. COMMUN., VOL.Exx–??, NO.xx XXXX 200x
1
LETTER
Interference-aware Energy-efficient Geographical Routing
for IEEE 802.15.4a Networks
Junseok KIM
†∗
, Nonmember and Younggoo KWON
†∗
, Member
SUMMARY The IEEE 802.15.4a standard enables geo-
graphical routing in ZigBee networks but previous geographical
routing algorithms can suffer high packet loss due to the interfer-
ence effects. This letter proposes an interference-aware energy-
efficient geographical routing algorithm for the IEEE 802.15.4a
networks. The proposed algorithm estimates the energy cost by
considering the interference effects and forwards a packet to the
neighbor with the lowest energy cost to advance. Experimental
results show that the proposed algorithm outperforms the pre-
vious algorithms in terms of the delivery ratio and the energy
consumption.
key words: Interference, Geographical routing, 802.15.4a
1. Introduction
IEEE 802.15.4/ZigBee is a standard for the low-
rate wireless personal area networks [1]. The ZigBee de-
fines the network layer on the top of the medium access
control layer (MAC) and the physical layer (PHY) of
the IEEE 802.15.4. In ZigBee networks, the power con-
servation is very important because nodes are usually
operated on limited batteries. A well designed rout-
ing protocol can reduce the energy consumption and
increase the communication bandwidth. The ZigBee
standard defines two routing protocols: the ad-hoc on-
demand distance vector routing protocol (AODV) and
the hierarchical routing protocol (HRP). The AODV
floods the route request (RREQ) message over the net-
work to find the destination, and thus it causes a large
message overhead. In the HRP, a packet is forwarded
to the coordinator (the root node in a tree topology)
and the coordinator forwards the packet to the desti-
nation. HRP incurs much less message overhead than
AODV, but it establishes long routes.
The IEEE 802.15.4a is an amendment to the IEEE
802.15.4 and it defines two additional PHYs based on
the ultra wide band (UWB) and the chirp spread spec-
trum (CSS) to support high accuracy localization [2]. If
the location information is available, the geographical
routing protocol is more efficient than AODV or HRP.
Most geographical routing protocols use the greedy for-
warding and the face recovery [5] [10]. The greedy for-
warding transmits a packet to the neighbor geographi-
cally closest to the destination. When there is no neigh-
bor closer to the destination, the face recovery routes
Manuscript received May 05, 2009.
†
The authors are with Konkuk University, 1 Hwayang-
dong, Gwangjin-gu, Seoul, 143-701, Korea.
∗
E-mail: jskim1, ygkwon@konkuk.ac.kr
the packet around the perimeter of faces of the com-
munication graph. ZigBee applications are usually de-
ployed in buildings. The greedy forwarding can per-
form poorly because it tries to forward packets through
obstacles. Many algorithms have been proposed to im-
prove the greedy forwarding [4] [6] [7]. In [4], a node es-
timates the minimum transmit power based on the log-
distance path loss model and forwards a packet to the
neighbor with the lowest energy/distance value. How-
ever, estimating the minimum transmit power based
on the distance can incur high packet loss, because the
signal strength is heavily affected by obstacles. In [6]
[7], a node estimates the packet reception ratio (PRR)
for each neighbor and forwards a packet to the neigh-
bor with the highest PRR× distance value. The PRR
based algorithms cannot adapt to the environmental
changes dynamically because it has to send or overhear
several packets to estimate the PRR. The link quality
fluctuates wildly due to the interference of other wire-
less products and therefore the previous algorithms can
suffer significant performance degradation.
In this letter, we propose an interference aware en-
ergy efficient geographical routing algorithm (IEG) for
IEEE 802.15.4a networks. In the proposed algorithm,
each node estimates the energy cost by considering the
interference effects and forwards a packet to the neigh-
bor which requires the lowest energy cost to advance to
the destination. Since the energy cost depends on the
interference power level, the proposed algorithm routes
a packet around the interference region. We evaluate
the performance of the proposed algorithm by using the
simulator and the testbed. Experimental results show
that the proposed algorithm outperforms the greedy al-
gorithm and the PRR×distance algorithm in terms of
the energy consumption and the delivery ratio.
2. Overview of IEEE 802.15.4a
The IEEE 802.15.4a standard presents the sym-
metric double sided two way ranging (SDS-TWR) al-
gorithm. In the TWR, two nodes exchange a packet
and an acknowledgment (ACK) as shown in Fig. 1. If
the sender transmits the packet at the time t
start
and
receives the ACK at the time t
stop
, the distance d is
estimated as follows:
d = λ × (t
stop
− t
start
− t
ta
) /2(1)