Unidirectional Link-Aware DTN-based Sensor
Network in Building Monitoring Scenario
Manussanun Buranachokphaisan, Hideya Ochiai, Hiroshi Esaki
Graduate School of Information Science and Technology, The University of Tokyo, Japan
Email: {kaew, jo2lxq, hiroshi}@hongo.wide.ad.jp
Abstract—The performance of wireless sensor network inbuilding monitoring system (BMS) is often deteriorated byintermittently-connected and unidirectional links occurring inbuilding environment. With DTN-based approach, Potentialbased Entropy Adaptive Routing (PEAR) protocol can achieve
high reliability and scalability over intermittently-connected meshnetwork in the building scenario. However, the result of highdelivery latency caused by ignoring the presence of unidirectional links may not be acceptable in BMS. In this paper, wepropose Unidirectional Link-Aware Next-hop Selection (ULANS),
the technique of detecting unidirectional links and the new nexthop selection scheme for PEAR. The real-world experimental
result shows that ULANS can avoid choosing unidirectional links
as the next-hop and improve delivery latency of PEAR.
Keywords—Unidirectional link, PEAR, DTN, Latency, WSN

I.

I NTRODUCTION

Building monitoring system (BMS) gains much interest
from many sectors these days. In BMS, large scale sensor
network is deployed in the building to gather power consumption and building’s environmental data. Wireless sensor
network (WSN) has been proposed to used in BMS due to theease of deployment and low maintenance cost. However, WSN
always suffers from dynamic environment in the building.
Intermittently-connected links also occur in such environment, even though all nodes are static deployment. Therefore,delay/disruption tolerant network’s (DTN) approach, which
always achieves high delivery ratio, plays an important rolein BMS.
DTN takes hop-by-hop reliable message transfer to attainhigher delivery ratio. Hop-by-hop reliability requires bidirectional communication to confirm message delivery. However, unidirectional links frequently occur in wireless ad-hoc
network [1]–[4]. The unidirectional link arises between twoconnected nodes when only one of two nodes can directly send
messages to the other. It may be caused by transmitter/receiver
heterogeneity, power control of sensor node, interference orhidden terminal. This may reduce the performance of WSN
regarding delivery latency.
Potential-based Entropy Adaptive Routing (PEAR) protocol [5], one of DTN-based routing protocol, has achieved 100%of delivery ratio over 10 hops in the 50 node-scale wirelessmesh network [6]. Although the result showed PEAR’s reliability and scalability, large delivery latency may not be acceptable
in BMS [7]. After examining the behavior of PEAR, we foundthat the unidirectional link is one of the cause of high latency.
PEAR assumes that all wireless links are bidirectional andchooses only the shortest path in the message delivery.

To avoid the unidirectional links in DTN-based routing
protocol, we propose Unidirectional Link Aware Next-hopSelection (ULANS), the simple technique of detecting theunidirectional links and the new next-hop selection scheme
for DTN-based routing protocol. In this paper, we focus on
PEAR as DTN-based routing scheme to study the effect of theunidirectional links and the improvement with our proposed
ULANS in building monitoring scenario. The experimental
evaluation shows that ULANS can alleviate this problem andimprove PEAR’s routing performance.
The rest of the paper is organized as follows. In Section II,
we briefly explain the concept of PEAR. Section III presents
our proposed method. Section IV shows the experiment andevaluation of the proposed method compared to the originalPEAR. We give a discussion in Section V. Finally, Section VI
concludes this paper.
II.

P OTENTIAL - BASED E NTROPY A DAPTIVE ROUTINGPEAR inherits potential-based routing protocol (PBR) andhop-by-hop store-and-forward mechanism from DTN. In PBR,
each node has a positive scalar value indicating the distancefrom the destination called potential. The higher potential
implies the further distance from the destination. Each nodebroadcasts advertise messages (ADV) periodically in order toupdate its potential with neighbor nodes and selects the lowestpotential neighbor as the next-hop.
PEAR defines next-hop selection scheme as follows,𝑑𝐹𝑚𝑎𝑥(𝑛) =max {𝑉 𝑑 (𝑛) − 𝑉 𝑑 (𝑚)}𝑚∈𝑛𝑏𝑟(𝑛)(1)𝑑(𝑛) = 𝑉 𝑑 (𝑛) − 𝑉 𝑑 (𝑘)} (2)𝑁 𝐻 𝑑 (𝑛) ={𝑘∣𝑘 ∈ 𝑛𝑏𝑟(𝑛), 𝐹𝑚𝑎𝑥

where 𝑛𝑏𝑟(𝑛) denotes the set of neighbor nodes of node 𝑛,𝑉 𝑑 (𝑛) represents the potential of node 𝑛 for the destination
𝑑𝑑, 𝐹𝑚𝑎𝑥(𝑛) keeps the maximum difference between node 𝑛’s
potential and its neighbors’ potential and 𝑁 𝐻 𝑑 (𝑛) is the nexthop of node 𝑛 toward the destination 𝑑.
In store-and-forward mechanism, the messages are copiedand stored in the intermediate nodes. Before forwarding themessages, nodes have an investigation to check whether theirnext-hops already have the messages. Firstly, the sender requests message information by sending all message ID stored
in the buffer to the next-hop. Then, the next-hop replies
the state of each message, i.e. already-received, not-received
or delivered, with a response message. Finally, the sendersends only not-received messages to the next-hop and deletesdelivered messages from the buffer. Fig. 1a illustrates theinvestigation when node 𝐵 is the next-hop of node 𝐴.

Fig. 3.
(a) Bidirectional link(b) Unidirectional link

Fig. 1. The investigation when the link between 𝐴 and 𝐵 is (a) bidirectionaland (b) unidirectional.

Owing to the investigation, nodes send the messages onlywhen the investigation succeeds, i.e. when nodes receive theresponse from their next-hops. Thus, the bidirectional link
is required in PEAR. However, PEAR is interested only thelowest-potential neighbor without being aware of the unidirectional links. The unidirectional links may interrupt theinvestigation (Fig. 1b). Consequently, the messages are delayed
at the intermediate nodes resulting in high delivery latency.
III.

U NIDIRECTIONAL L INK AWARE N EXT- HOPS ELECTION

In this section, we describe how Unidirectional LinkAware Next-hop Selection (ULANS) works. We first give thedefinition of unidirectional link using in this paper. Then,we explain the method of detecting the unidirectional links.
Finally, we present the new next-hop selection scheme forPEAR.
A. Unidirectional link
To classify the links at each node 𝑛, the link pointing
outward from 𝑛 is defined as forward link and the link directing
to 𝑛 is called reverse link. The definition is illustrated in theFig. 2.
We define that any link becomes unavailable when the linkcannot deliver any messages within a period of time called
Connectivity Time (𝑇𝐶 ). Supposing that node 𝑛 is connectedwith node 𝑘 ∈ 𝑛𝑏𝑟(𝑛), when we consider at node 𝑛, there
should be both forward link to 𝑘 and reverse link from 𝑘 ifthe link is bidirectional. The link between 𝑛 and 𝑘 becomes
unidirectional when the forward link to 𝑘 is available but thereverse link from 𝑘 is unavailable or vice versa. The exampleof the unidirectional link is shown in Fig. 3.
Here, 𝑇𝐶 is the important factor to decide whether the link
is unidirectional. Due to the fluctuation of wireless link, themessages could be lost, even though the link quality is good.
𝑇𝐶 filters out ordinary message loss and confirms that the link
is unidirectional.

Fig. 2.

The definition of links at node 𝑛.

Example of the unidirectional link between 𝐴 and 𝐵.

B. Unidirectional Link Detection
To detect the unidirectional links, the neighbor table at eachnode must consist of (1) Reverse Link Lifetime and (2) Link
status for every neighbor. Reverse Link Lifetime (𝑅𝐿𝐿) isnon-negative integer showing the time-to-live of the reverse
link. Once 𝑅𝐿𝐿 is set to non-zero value, 𝑅𝐿𝐿 decreases
every second. Link status (𝐿) indicates whether the link isbidirectional. 𝐿 is either available (‘𝐴’) or unavailable (‘𝑈 ’);
𝐿 is set to ‘𝐴’ only when both reverse link and forward link
are available and set to ‘𝑈 ’ if the reverse link or the forward
link is unavailable.
ULANS exploits the feature of PBR to detect the unidirectional links between nodes by observing the receipt of ADV
at each node. Since each node broadcasts ADV periodically,
nodes learn that the reverse links are unavailable when nodes
do not receive ADV within 𝑇𝐶 . Whenever nodes receive ADVfrom neighbors, nodes set 𝑅𝐿𝐿 to 𝑇𝐶 . Therefore, non-zero
𝑅𝐿𝐿 indicates that the reverse link is available. Note that𝑇𝐶 must be more than ADV broadcast interval to detect theunidirectional links.
However, nodes cannot identify the presence of forward
link by themselves. Thus, nodes embedded a neighbor list
containing neighbor ID with non-zero 𝑅𝐿𝐿 in ADV to inform
other nodes. When nodes find themselves in the neighbor list,
nodes perceive that the forward links are available as well.
Then, nodes set 𝐿 to ‘𝐴’. On the other hand, nodes realizethat the links are unidirectional and set 𝐿 to ‘𝑈 ’ when theirIDs are not in the neighbor list.
ADV reception and link information from neighbor nodes
confirm the existence of reverse link and forward link respectively. Nodes know whether the forward links are available
only when the reverse links exist. That is enough for DTNbased routing protocol because as long as the reverse links are
lost, nodes cannot update neighbors’ information or succeed
the investigation. Therefore, forward link’s information isunnecessary unless the reverse links are available.

C. New scheme for the next-hop selection
As we mentioned before, PEAR’s next-hop selection
scheme chooses only the lowest-potential node to be the nexthop without being aware of the existence of the unidirectional
links. In order to avoid this problem, ULANS modifies andproposes new scheme for the next-hop selection as shown in
Eq. 3 and Eq. 4.

(a)
(a)

(b)

Fig. 4. (a) Deployment configuration, (b) topology and connectivity of theexperimented network.

𝐹 𝑑 (𝑛) =max

{𝑉 𝑑 (𝑛) − 𝑉 𝑑 (𝑚)}𝑚∈𝑛𝑏𝑟(𝑛),𝐿𝑛𝑚 =‘𝐴’𝑑(b)Fig. 5. (a) Unidirectional links existed in the network when 𝑇𝐶 was 80
seconds. The thicker line indicates that the link became unidirectional more
frequently. (b) Unidirectional link selection ratio of each node when 𝑇𝐶 was
80 seconds.

(3)

𝑁 𝐻𝑈𝑑 𝐿𝐴𝑁 𝑆 (𝑛) ={𝑘∣𝑘 ∈ 𝑛𝑏𝑟(𝑛), 𝐹 (𝑛) = 𝑉 𝑑 (𝑛) − 𝑉 𝑑 (𝑘)}(4)where 𝐿𝑛𝑚 is the link status between node 𝑛 and node 𝑚.
ULANS adds one more condition to address the unidirectional
links in the previous next-hop selection scheme. When nodes
compare the potential with their neighbors, nodes consider
only neighbors with the bidirectional links. As a result,
ULANS forces nodes to choose only the lowest-potential
neighbor with the bidirectional link as the next-hop.
IV.

(a) PEAR(b) ULANS(80)Fig. 6. Delivery paths of (a) PEAR and (b) ULANS(80). Dashed line indicatesthe unidirectional link between a pair of nodes.

E XPERIMENTAL E VALUATION

We studied the effect of unidirectional links in PEAR andevaluated ULANS on the testbed experiment. First of all, wedescribe our experiment setup, then present our study on theunidirectional links. Finally, the experiment results are shownand analyzed.
A. Experiment SetupThe experiment was carried out with 15 UTMesh nodes[8] on 10th floor of Eng. Bldg 2 in the University of Tokyo.
UTMesh nodes were operating with Armadillo-220, Linuxembedded computer with Wi-Fi (IEEE802.11) module. All
nodes were powered by batteries and operated at the sametransmit and receive power level. We set ADV broadcast, nexthop selection and system update interval to 10 seconds. To
mock-up building monitoring system scenario, every node wasconfigured to send 22- or 23-byte messages (depends on nodeID) to node 1 every 30 seconds. Apart from the original PEAR,
PEAR with ULANS was run with 3 different 𝑇𝐶 , i.e. 40, 60,
80 seconds. We denote the experiment of PEAR with ULANS
as ULANS(𝑇𝐶 ). Each experiment took 1 hour. Fig. 4 shows
the deployment, topology and connectivity of this experiment.
B. Effect of the unidirectional links in PEAR
We picked PEAR and ULANS(80) to observe the effectof the unidirectional links in this experiment. Fig.5a shows
the presence of unidirectional links when 𝑇𝐶 was 80 seconds.
From our observation, most links became unidirectional during
the experiment, though all nodes operated at the same power

level. However, their occurrence was dynamic. The links became unidirectional temporarily and turned back to be bidirectional back and forth. Some links became unidirectional only
for a short time, while some links turned into unidirectional
in a long period. Links between nodes located far from eachother often became unidirectional.
We also observed how PEAR selected the next-hop by
examining Unidirectional Link Selection Ratio (UDLSR) andmain delivery paths. UDLSR is the ratio of the number of times
that nodes select next-hops with the unidirectional links to thenumber of times next-hop selection process is executed. Fig.
5b shows UDLSR of PEAR when 𝑇𝐶 was 80 seconds. We cansee that node 8, 9 and 10 gave high UDLSR corresponding tothe main delivery paths of PEAR shown in Fig. 6a. Those
nodes often chose next-hops with the unidirectional links.
After applying ULANS (Fig.6b), those nodes avoided theunidirectional links and chose next-hops with better links.
C. Experiment Result
We evaluated the improvement of PEAR with ULANS byobserving Investigation Success Ratio (ISR), delivery latency
and hop count. Overall performance of experiments is presented in Table. I.
1) Investigation Success Ratio (ISR): Considering that theunidirectional links affect the investigation, the success of theinvestigation is examined. We define Investigation Success
Ratio (ISR) as the ratio of the number of response messages

TABLE I.

OVERALL PERFORMANCE .

Experiment

ISR(%)

Delivery Latency (s)
Avg
99%
Max

PEAR
ULANS(40)ULANS(60)ULANS(80)

56.22
66.03
63.08
63.12

25.70
35.40
20.32
20.87

205.22228.60136.85135.56

Hop count

401.60382.54297.00201.68

1.78
2.33
2.09
2.21

received to the number of request messages sent between eachpair of nodes. ISR of the network was improved by 7-10%
after applying ULANS to PEAR. In other words, avoiding theunidirectional links enhanced chances of sending the messages
to the next-hop.
2) Delivery latency: Delivery latency is the amount of timethat the message travels from the source to the destination.
Fig. 7 shows the distribution of delivery latency in box
plot. ULANS decreased maximum delivery latency, however,
ULANS did not always decrease average delivery latency
since ULANS(40) resulted higher value than the originalPEAR. ULANS(60) and ULANS(80) outperformed PEAR by
reducing average delivery latency by 20%. Maximum delivery
latency was decreased by 26% in ULANS(60) and 50% inULANS(80). Moreover, 99% of the messages were delivered
33% faster in ULANS(60) and ULANS(80).

enough for ULANS to decide whether ADV loss is caused
by unidirectional links or just normal packet loss. Nodes
may change next-hops unnecessarily leading to higher hopcounts and, consequently, higher average delivery latency as
in ULANS(40). On the other hand, large 𝑇𝐶 may lead to slow
detection. Seeing that different 𝑇𝐶 gives different performance,
𝑇𝐶 must be set appropriately.
We raised the problem of unidirectional links in DTNbased approach in this paper. However, there are other factors
causing high delivery latency since ISR was still low even withULANS. In our future works, we attempt to improve delivery
latency by considering link quality or applying retransmission
scheme to PEAR.
VI.

C ONCLUSION

In this paper, we studied the effect of unidirectional links inDTN-based routing protocol. Unidirectional links often arise
in wireless network, though all nodes are static. DTN-based
approach achieved reliability and scalability in intermittentlyconnected wireless network, however, unawareness of unidirectional link sometimes causes high delivery latency.
We proposed Unidirectional Link Aware Next-hop Selection (ULANS) for PEAR. ULANS detects the unidirectional
links by exploiting the feature of PEAR and avoids theunidirectional links with the new next-hop selection scheme.
ULANS was evaluated with the testbed experiment in building
monitoring scenario. The experimental evaluation confirmedthat ULANS can avoid the unidirectional links and improve
the performance of PEAR.
R EFERENCES

Fig. 7.

Box plot showing the distribution of delivery latency.

3) Hop count: Hop count is the number of hops that messages travel from the source to the destination. While PEAR
chose the farthest nodes, which were likely to connect with theunidirectional links, as the next-hop, ULANS avoided those
nodes and selected closer nodes resulting in more hop counts.
The messages delivering with more hop counts possibly gavehigher delivery latency. This is why average delivery latency
was not always improved in ULANS.
V.

D ISCUSSION

In accordance with the experiment results, the unidirectional links led to high delivery latency in PEAR. ULANS
enhanced successful investigation and, as a result, decreased
delivery latency. ULANS also collected data faster in comparison with PEAR. However, the increment of hop count could
degrade the performance concerning delivery latency.
As we mentioned in Section. III-A, 𝑇𝐶 is the significant
parameter to filter out the unidirectional links. 𝑇𝐶 must be set
corresponding to ADV broadcast interval. Too small 𝑇𝐶 is not[1] M. K. Marina and S. R. Das, “Routing performance in the presence of
unidirectional links in multihop wireless networks,” in Proceedings ofthe 3rd ACM International Symposium on Mobile Ad Hoc Networking&Amp; Computing, ser. MobiHoc ’02. New York, NY, USA: ACM,2002, pp. 12–23.
[2] J. Zhao and R. Govindan, “Understanding packet delivery performance indense wireless sensor networks,” in Proceedings of the 1st International
Conference on Embedded Networked Sensor Systems, ser. SenSys ’03.
New York, NY, USA: ACM, 2003, pp. 1–13.
[3] J. G. Jetcheva and D. B. Johnson, “Routing characteristics of ad hoc
networks with unidirectional links,” Ad Hoc Netw., vol. 4, no. 3, pp.
303–325, May 2006.
[4] L. Sang, A. Arora, and H. Zhang, “On exploiting asymmetric wirelesslinks via one-way estimation,” in Proceedings of the 8th ACM International Symposium on Mobile Ad Hoc Networking and Computing, ser.
MobiHoc ’07. New York, NY, USA: ACM, 2007, pp. 11–21.
[5] H. Ochiai and H. Esaki, “Mobility entropy and message routing incommunity-structured delay tolerant networks,” in Proceedings of the
4th Asian Conference on Internet Engineering, ser. AINTEC ’08. NewYork, NY, USA: ACM, 2008, pp. 93–102.
[6] H. Ochiai, M. Nakayama, and H. Esaki, “Hop-by-hop reliable, parallel
message propagation for intermittently-connected mesh networks,” inProceedings of the 2011 IEEE International Symposium on a Worldof Wireless, Mobile and Multimedia Networks, ser. WOWMOM ’11.
Washington, DC, USA: IEEE Computer Society, 2011, pp. 1–9.
[7] N. Saputro, K. Akkaya, and S. Uludag, “A survey of routing protocols
for smart grid communications,” Computer Networks, vol. 56, no. 11,pp. 2742–2771, 2012.
[8] H. Ochiai, K. Matsuo, S. Matsuura, and H. Esaki, “A case study ofutmesh: Design and impact of real world experiments with wi-fi andbluetooth devices,” in Applications and the Internet (SAINT), 2011
IEEE/IPSJ 11th International Symposium on, July 2011, pp. 433–438.