Wireless Sensor Network, 2010, 2, 718-723
doi:110.4236/wsn.2010.29087 Published Online September 2010 (http://www.SciRP.org/journal/wsn)
Opportunistic Routing for Time-Variety and Load-Balance
over Wireless Sensor Networks
Nan Ding, Guozhen Tan, Wei Zhang
Department of Computer Science, Dalian University of Technology, Dalian, Liaoning, China
Received June 28, 2010; revised August 2, 2010; accepted September 4, 2010
Abstract
To aware the topology of wireless sensor networks (WSN) with time-variety, and load-balance the resource
of communication and energy, an opportunistic routing protocol for WSN based on Opportunistic Routing
Entropy and ant colony optimization, called ACO-TDOP, is proposed. At first, based on the second law of
thermo-dynamics, we introduce the concept of Opportunistic Routing Entropy which is a parameter repre-
senting the transmission state of each node by taking into account the power left and the distance to the sink
node. Then, it is proved that the problem of route thinking about Opportunistic Routing Entropy is shown to
be NP-hard. So the protocol, ACO-TDOP, is proposed. At last, numerical results confirm that the
ACO-TDOP is energy conservative and throughput gainful compared with other two existing routing protocols,
and show that it is efficacious to analyze and uncover fundamental of message transmission with Opportunistic
Routing in wireless network using the second law of thermodynamics.
Keywords: Wireless Sensor Network, Load-balance, Time-variety, Opportunistic Routing Entropy
1. Introduction
MULTI-HOP wireless networks, the same as mobile Ad
hoc networks and wireless mesh networks, is considered
to be convenient and cost-effective solutions in many
important areas, such as traffic monitoring, environ-
mental monitoring, and military security. Due to effects
of multi-path fading, signal interfering and path losses,
the link of WSN is time-varying. Besides, the power and
working state of each node is time-varying, too. So the
key challenge of multi-hop wireless networks protocol is
ensuring that the “best” receiver of each packet forwards
it.
At present, most of the traditional multi-hop routing
protocols in WSN typically adopt routing schemes and
techniques similar to those in wired networks [1]. The
protocols, such as DSR, OLSR, AODV and LEACH,
have proposed to update the network routing periodically
in order to adapt to the change of network, but messages
are still transmitted through static routing. These meth-
ods can partly solve the problem of energy consumption
balance; however they cannot solve the dynamic changes
of the link which is caused by the time-variety of the
network [2].
The opportunistic routing which is proposed in recent
years is a new dynamic routing based on multi-hop. It
proposes a transmission method based on the opportunistic,
that is, next relay is selected dynamically for each packet
and each hop. Through a large number of experiments
[3-6,7], they have verified the rationality and practicality
of the opportunistic routing compared with traditional
route in the network traffic process. To ensure the reli-
ability and validity of the dynamic transmission network,
the key of opportunistic routing algorithm is how to
select the next hop node. Currently, there are two re-
searching aspects on opportunistic routing:
One aspect is to establish best routing for wireless
network [8,9]. This aspect primarily builds the shortest
path or near the approximate shortest path to improve the
network throughput performance. Kai Zeng et al. [10] set
up an optimization model for the throughput of the op-
portunistic routing through a combination of graph theory
and network flow theory.
The other aspect is on the balance of energy consump-
tion in opportunistic routing [11-13]. Lakshmi V. et al.
[14] proposes two opportunistic transmission strategies
referring to energy, one of which is to eliminate the
nodes whose residual energy is less than threshold during
establishing the transmission path dynamically, and the

N. DING ET AL.
719
other is that the network nodes are divided into concentric
ring-type structure while the receive node as the center.
With the latter strategy, when the message is sent to the
ring whose nodes are close to the sink node, it will con-
sider the residual energy to make the distribution of en-
ergy consumption reasonable.
According to the studies above, the network transmis-
sion throughput rate and the energy balance are the key
factors of dynamic establishment of opportunistic routing,
and they are interactional and interdependent. For exam-
ple, in order to achieve maximum network throughput
rate and minimum delay, it is necessary to establish the
shortest path, while the shortest path will lead to unbalanced
energy consumption of the network. On the contrary, in
order to balance the energy consumption within the net-
work, packet transmission will avoid some node which is
on the shortest path but has little energy left, which will
increase the number of hops of packet transmission, in-
creasing the time delay and reducing the network
throughput rate. To coordinate these two factors, some
scholars have proposed to use the opportunistic routing
which is mainly to use heuristic algorithms, such as ant
colony algorithm, to get the transmission path selection
strategy [12,15]. But at present, we lack the optimization
model and analysis methods of transmission routing
based on time-varying characteristic, which is necessary
for improving the performance of opportunistic routing,
and the theory related with static networks is unable in
the time-varying networks [16].
To solve the problem, this paper gives the data transfer
rule that refers to the residual energy of the node and the
shortest path of the network, based on the second law of
thermodynamic.
2. Problem Formulation
Taking into account the shortest path and energy balance
with the time-varying characteristics of the network, we
propose Opportunistic Routing Entropy which provides a
theoretical basis for using opportunistic routing to create
dynamic data transmission path. And we prove that it is a
np-hard problem to get the best path which is time-
varying and opportunistic.
2.1. Network Model and Assumptions
This article assumes that nodes in the network are dis-
tributed randomly in a rectangular area, and there prop-
erties as follows: 1)Within the network, the unique sink
node is deployed in the center of the area, the rest of sen-
sor nodes will not move any more after deploying, and
the location information of each node is unknown. 2)
The identity of each node is unique. 3) The status of each
node is equal, with the same computing and communica-
tion capabilities, as well as initial energy.
Combining the properties above, the network model is
defined as follows:
Definition 1 Network communication diagram.
The communication graph of an N-node wireless sen-
sor network is an undirected graph, G(V,E). V is the set
of communication node, and V= Ssink∪Ssensor, where Ssink
is the sink node and Ssensor is the set of sensor nodes.
Each sensor node has a fixed communication range, R.
dij is the distance between node i and node j. E is the set
of edges and E = eij(i,jV) , dij ≤ R.
Definition 2 Communication distance.
In graph G, the communication distance is D(o, s)
which value is the hop count between node o and node s.
Definition 3 Set of neighbor node.
The set of neighbor node is N(u), and N(u) = ni(niV,
euni E), which includes the nodes which could commu-
nicate directly with node u.
Theorem 1 In WSN, the shortest path problem based
on time-varying and the opportunistic method for trans-
mission is shown to be NP-hard.
Proof. With the opportunistic method, the nodes of
WSN could choose the best link to repeat the messages
considering the condition of current network. Even
though the same node sends two messages in succession,
it may take different paths for transmission these two
messages, if conditions of the network transmission link
changed, for example interference etc. And the latter
message may arrive earlier than former.
So the WSN transmission link working in the oppor-
tunity method is NO-FIFO, when thinking about the
time-varying characteristics of communication links.
Ariel Orda et al has proved that in the time-varying net-
work, if the communication link is NO-FIFO, its com-
plexity of the shortest path problem is NP-hard. There-
fore, in Opportunistic Routing, the shortest path problem
based on time-varying is shown to be NP-hard [16].
2.2. Opportunistic Routing Entropy and
Programming
The second law of thermodynamicshe (also called en-
tropy law) developed by Rudolf Clausius, is the essential
theory of thermodynamic. Entropy indicates that the sys-
tem develop to the internal stable state without external
interference. The greater the entropy is, the more stable
the system is.
Because nodes of WSN require the separate power
supply as well as independent operation on normal con-
ditions, its data packet transmission is in a relatively in-
dependent system. Nodes will consume their energy
during the data packet transmission process. In order to

N. DING ET AL.
720
balance the energy consumption of each node to extend
the network lifetime, we should choose the node with
more residual energy, less energy consumption and
shorter number of hops from the sink node as the next
hop. Therefore, according the second law of thermody-
namicshe and the data packet transmission process in the
time-varying network model, we have defined the Op-
portunistic Routing Entropy and established the optimi-
zation model.
Definition 4 Opportunistic Routing Entropy.
Opportunistic Routing Entropy, Sop, is the measure of
transmission state of each node in WSN. Referred to as
Shannon entropy, Sop cannot decrease too. It is given by
(1). The more Sop, the less energy left and the more hops
to sink node.
()
() ()
op
u
u
op
h
wt
SEt ut， (1)
In (1), hu is the hop count between nodes u and the
sink node, wu(t) is the weight that node o communicates
with node u which is in neighbor node set N(o) of node o
at moment t. Eop(t) is residual energy, which can be cal-
culated by A/D converter in real time.
During data transmitting, it will choose the node with
small Opportunistic Routing Entropy as data forwarding
node, and the Opportunistic Routing Entropy of this
forwarding node will be progressively larger. Sop is on
behalf of the probability of each node to be selected as
next hop during data transmission. Smaller Sop is, more
probability the node will be selected as next hop.
Therefore, during forwarding the data, it will choose
the neighbor node with small Sop as the next hop node.
u
u
min .(,)()
..
() ()
()
()
0
(), ()0
() 0
1()0
0
(), 0
() ()
u
u
l
l
u
op
op l
uu
h
Sut wt
st
Et Et
Eu Eu
wt
wt
h
wt
Et
EtEt Et
h
 

  


 

 



(2)
Referring to Theorem 1, it is shown to be NP-hard to
get the shortest path of our model, so the problem of
route thinking about Opportunistic Routing Entropy is
also shown to be NP-hard.
According to computational complexity theory, any
np-hard problem do not exist completed algorithm within
polynomial-time unless P = NP [17]. At present, there
are two solutions to such problems, one is completed
algorithm which can get the optimal solution but with
high time complexity, and the other is to use heuristic
algorithms which can only get the approximate optimal
solution but within polynomial-time. As a result, we
propose a heuristic algorithm based on ant colony opti-
mization for the model which we establish.
3. ACO-TDOP Based on Ant Colony
Optimization
Ant colony optimization (ACO) takes inspiration from
the foraging behavior of some ant species. Routing algo-
rithms based on ACO algorithm have achieved good
results in the network, especially in wireless sensor net-
works.
3.1. Probabilistic Decision Rule of ACO Based
on Sop
When the source node o wants to send data, it will select
the next hop node by following the random-proportional
rule (see Equation(3)). It is a function thinking about the
Sop and the amount of pheromone trail present on the
connections between the nodes. So, it could choose the
node with maximum value of P(j, t) as the repeat node.

(,)
(,)
P, ,
(, )
()
(, )
op
iN op
jt
Sjt
jtj N
it
Sit







（3）
where:
P(j, t): the probability that the ant in the data packet
move to node j at moment t.
τ(j, t): the pheromone level of node j at moment t.
Sop(j, t): the selection entropy of node j at moment t.
N : the set of neighbors of the current node.
β: a parameter which determines the relative influence
of heuristic values Sop(j, t) (β > 0).
3.2. Pheromone Updating Rule
When received the data packets from node u, node j will
update its Pheromone τ(j, t). Introducing of the residual
rate ρ(t) (Eqs.(6)), we have improved the existing calcu-
lation model of pheromone.
Pheromone τ(j, t) based on residual rate:




, (),-1 jtt jt



 (4)






u
1h ht



  (5)
()
()=op
init
E
t
t
E

(6)

N. DING ET AL.
721
where ρ(t) is the pheromone accumulated parameter,
which indicates the proportion of pheromone remaining
at moment t. When the node has little residual energy, its
residual rate ρ(t) is small and its evaporation of phero-
mone is faster relatively. Einit represents of the initial
energy of the node, and the initial energy of each node is
fixed and equal in our model. hu is the hop count be-
tween nodes u and the sink node.
In Equation (4), τ(j, t) is the pheromone level of cur-
rent node at moment t, and τ(j, t-1) is the pheromone
level of current node at moment t-1. ∆τ is the new added
pheromone, and in Equation (5),if the value of (hi - hj) is
greater than zero, then it can conclude that node j is
closer to the sink node than node i. Hence, the algorithm
will reward the path from node i to node j by depositing
more pheromones. If the value of (hi - hj) is equal to zero,
then it means that both nodes i and j have the same hop
count to the sink node. As a result, the algorithm will
deposit the amount of pheromone τ(j, t) on the path. If
the value is less than zero, the algorithm will not deposit
pheromone on this path.
3.3. ACO-TDOP Algorithm
Combining Opportunistic Routing Entropy with ant col-
ony algorithm, we propose a new routing algorithm,
ACO-TDOP, and Figure 1 presents its Working state
diagram.
The main process is as follows:
1) Initial state: Starting from the state, S0, initialize
the system variable, and the sink node will flood the ini-
tialization packet to all the nodes in the network firstly.
After the node receives this packet, it will compute the
hop count to the sink node.
Figure 1. State machine of ACO-TDOP.
2) Ant waiting and information gathering: After
initialization, the source node will enter the state S1 to
wait to send ants. When the source node wants to send
ants, it will send a request packet to each neighbor node,
and wait for feedback messages from neighbors, that
process is the state S2. During the waiting time T_collect,
we will calculate the selection probability P(j, t) of each
neighbor on the basis of feedback message, which in-
clude Opportunistic Routing Entropy Sop and pheromone
τ(j, t). After the waiting time T_collect, the node will
enter to state S3.
3) Next hop node selection: We will select the node
whose P(j, t) is largest among the neighbors in N as the
next hop to send the ant.
4) Pheromone update: This is the state S4, and there
are two kinds of mode which can be converted to this
state. One mode is to update the Pheromone immediately
after sending a message over, the other is that the
pheromone will be evaporated when the node is idle for a
period of time such as T_wait. If the residual energy of
the node is less than the threshold ε, then the node will
be die and close its communication so as not to transmit
any information.
4. Simulation Results
4.1. Simulation Environment
This experiment simulation environment is NS-2. For
these simulation experiments, we assumed that there are
300 sensor nodes distributed randomly in a 300×300
square region. All nodes have the same transmission
range. There is a single sink node located at coordinates
(150, 150) of the wireless sensor networks, which re-
ceives the data of all source nodes for all the simulations.
The parameters of simulations are listed in Table 1.
Simulation is mainly on two aspects, one of which is
to compare the ACO-TDOP protocol with other routing
protocols including traditional Ant Colony algrithm and
EEABR on the performance, and the other is to get a
dynamic path with ACO-TDOP protocol by tracking a
packet from the source node to sink node.
4.2. Comparison with Other Protocols
For the Simulation, we will compare ACO-TDOP algo-
rithm with other two algorithms. The first is the routing
algorithm based on traditional ant colony algorithm
which is used to solve the approximate shortest route in
[7] and [13], and the second is EEABR routing algorithm
which is proposed in [11]. EEABR is also based on ant
colony but refer to the energy in the route, which means

N. DING ET AL.
722
that if there is more energy in one path, the density of
pheromone in this path will increases more and the path
will have more chance to be selected.
In the same simulation environment and net topology
scale, we have done experiment for 100 times to com-
pare the network lifetime of ACO, EEABR and ACO-
TDOP algorithm. Network lifetime can be defined as the
time elapsed until the first node (or the last node) in the
network depletes its energy (dies). From Figure 2, we
can see that ACO has shortest lifetime than others, and
EEABR is shorter than ACO-TDOP. Because ACO-
TDOP considers the left energy of each node in the path.
In order to analyze the residual energy distribution of
nodes at the end of WSN, we also have done test more
than 100 times. As a result shown as Figure 3, EEABR
and ACO-TDOP algorithm has a more balanced energy
consumption of the network, and there are more than
80% of the nodes whose residual energy is less than 35%
of the initial value.
Figure 4 shows the comparison of the throughput rate
after 100 tests. We can see that the throughput rate of
BACO, EEABR and ACO-TDOP are quite similar to
Table 1. Parameters of simulations.
Parameters value
Simulated area 300×300
Number of sensor nodes 300
Initial energy 50J
Sink node location (150,150)
Transmission range 25m
Transmitter energy consumption 50×10-8J/bit
Computing energy consumption 50×10-8J/bit
Circuit energy consumption 50×10-8J/bit
Figure 2. Lifetime of the networks.
Figure 3. Distribution of Average Energy.
Figure 4. Distribution of throughput gains.
each other. As the test carry on, the BACO has a rela-
tively stable throughput rate owing to without taking into
account of energy consumption, while the throughput
rate of EEBAR and ACO-TDOP is less than BACO for
considering the residual energy of nodes. However, the
throughput of EEBAR and ACO-TDOP is more than
BACO, that is to say they make full use of the residual
energy of the network, so they are better than BACO.
4.3. Path Tracking
In order to verify that ACO-TDOP routing algorithm can
dynamically adjust the transmission path, we have re-
corded several dynamic paths between source node s and
the sink node, as shown in Figure 5. We can see that the
length of the path is only 10 hops at first, as the consump-
tion of energy, the length of the path can reach to 16 hops.
Y-Total Hop Count or Message Transmission in the Network
X Number of messages
X Ratio of Energy Left (%)
Y Occupation Ration (%)
N
etwork Lifetime(time Units)
ACO EEABR ACO-TDOP
57289
89713
97863

N. DING ET AL.
723
Figure 5. Path formation to sink node from the first run to
network lifetime.
5. Conclusions
Based on the analysis of available opportunistic routing
protocols, this paper analyzes and describes the message
transmission process in the time-varying network model
referring to the second law of thermodynamics, and pro-
poses the Opportunistic Routing Entropy to replace the
original entropy so as to indicate the network transmis-
sion status of each node. Further, combining Opportunistic
Routing Entropy and Ant Colony Optimization, this pa-
per raises an opportunistic routing protocol, ACO-TDOP,
for time-varying network model considering the load
balancing of the network resources. So the message is
ensured that the “best” receiver of each packet forwards
it. At last, numerical results confirm that the ACO-TDOP
is energy conservative and throughput gainful compared
with other two existing routing protocols, ACO and the
EEBAR opportunistic routing protocol.
6. Acknowledgments
This paper was supported in part by the National Basic
Research Program under No. 2005CB321904.
5. References
[1] D. Tse and S. Hanly, “Multi-Access Fading Channels:
Polymatroid Structure, Optimal Resource Allocation and
Throughput Capacities,” IEEE Transactions on Informa-
tion Theory, Vol. 44, No. 7, 1998, pp.2796-2815.
[2] J. Lian, K. Naik and G. Agnew, “Data Capacity Improve-
ment of Wireless Sensor Networks Using Non-Uniform
Sensor Distribution,” Journal of Distributed Sensor Net-
works, Vol. 2, 2006, pp.121-145.
[3] S. Biswas and R. Morris, “ExOR: Opportunistic Multi-
Hop Routing for Wireless Networks,” Proceeding of
ACM SIGCOMM 05, ACM Press, Pennsylvania, pp. 133-
143, 2005.
[4] H. F. Hu and Z. Yang, “Collaborative Opportunistic
Routing in Wireless Sensor Networks,” Journal on
Communications, Vol. 30, No. 8, 2009, pp.116-123.
[5] C. Luk, W. Lau and O. Yue, “An Analysis of Opportunis-
tic Routing in Wireless Mesh Network,” Proceeding of
IEEE International Conference on Communications, Bei-
jing, 2008, pp. 2877- 2883.
[6] S. Flody, V. Jacobson, et al. “A Reliable Multicast
Framework for Light-Weight Sessions and Application
Level Framing,” IEEE/ACM Transactions on Networking,
Vol. 5, No. 6, 1997, pp.784-803.
[7] K. Zeng, W. J. Lou, et al. “Capacity of Opportunistic
Routing in Multi-Rate and Multi-Hop Wireless Net-
works,” IEEE transactions on wireless communication,
Vol. 7, No. 12, 2008, pp. 5118-5128.
[8] Y. Zhang, D. Lukas, et al. “Improvements on Ant Routing
for Sensor Networks,” Lecture Notes in Computer Sci-
ence, 2004, pp.154-165.
[9] K. Zeng, W. J. Lou, et al. “On End-to-end Throughput of
Opportunistic Routing in Multi-Rate and Multi-Hop
Wireless Networks,” Proceedings of the IEEE INFOCOM,
Phoenix, 2008, pp. 1490-1498.
[10] J. N. Laneman and G. Wornell “Energy-Efficient Antenna
Sharing and Relaying for Wireless Networks,” Proceed-
ing of IEEE Wireless Communications and Networking.
Chicago, 2000, pp.7-12.
[11] T. Camilo, C. Carreto, et al. “An Energy-Efficient Ant-
Based Routing Algorithm for Wireless Sensor Net-
works,” Ant Colony Optimization and Swarm Intelligence,
2006, pp. 49-59.
[12] J. Li and P. Mohapatra “Analytical Modeling and Mitiga-
tion Techniques for the Energy Hole Problems in Sensor
Networks,” Pervasive and Mobile Computing, Vol. 3,
2007, pp.233-254.
[13] V. Lakshmi, Thanayankizil, Aravind Kailas, et al. “Two
Energy-Saving Schemes for Cooperative Transmission
with Opportunistic Large Arrays,” Proceedings of Global
Telecommunications Conference, Washington, DC, 2007,
pp.1038-1042.
[14] S. Okdem and D. Karaboga. “Routing in Wireless Sensor
Networks Using Ant Colony Optimization,” Proceedings
of Adaptive Hardware and Systems, Istanbul, 2006, pp.
401-404.
[15] M. Dorigo and V. Maniezzo Etal, “The Ant System:
Optimization by a Colony of Cooperating Agents,” IEEE
Transaction on Systems, Man, and Cybernetics - Part B,
Vol.26, No. 1, 1996, pp. 1-13.
[16] A. Orda and R. Rom, “Shortest-Path and Minimum-Delay
Algorithms in Networks with Time-Dependent Edge-
Length,” Vol. 37, No. 3, 1990, pp. 607-625.
[17] M. R. Garey and D. S. Johnson, “Computers and Intrac-
tability: a Guide to the Theory of NP Completeness,”
Whfreemanand Company, New York, 1979.
X Time Units
(
/100 Time Units
)
Hop Count to Sink Node