# P-bRS: A Physarum-Based Routing Scheme for Wireless Sensor Networks

Authors: Mingchuan Zhang; Wangyang Wei; Ruijuan Zheng; Qingtao Wu
Journal: The Scientific World Journal
 (2014)

---

## Abstract

Routing in wireless sensor networks (WSNs) is an extremely challenging issue due to the features of WSNs. Inspired by the large and single-celled amoeboid organism,slime mold Physarum polycephalum, we establish a novel selecting next hop model (SNH). Based on this model, we present a novel Physarum-based routing scheme (P-bRS) for WSNs to balance routing efficiency and energy equilibrium. In P-bRS, a sensor node can choose the proper next hop by using SNH which comprehensively considers the distance, energy residue, and location of the next hop. The simulation results show how P-bRS can achieve the effective trade-off between routing efficiency and energy equilibrium compared to two famous algorithms.


---

## Body

## 1. Introduction

Wireless sensor networks (WSNs) are a class of wireless ad hoc networks which consist of a set of sensor nodes and aim at several applications, such as industrial sensing and control and environment monitoring [1]. Each sensor node is a low-cost, short range wireless transceiver typically equipped with a low-computation processor and a battery operated power supply. Under many cases, sensors need to work without battery replacement for several years. Thus, there are two questions needing to be considered. One is how to achieve the energy balance of sensor nodes to avoid the emergence of energy hole which commonly occurs around the S
i
n
k, since the data traffic follows a many-to-one communication pattern and nodes nearer the S
i
n
k have to take heavier traffic load. The other is how to obtain high routing efficiency under multihop transmission circumstance, since WSNs can contain hundreds of such low-cost sensor nodes. Therefore, designing such networks should primarily focus on both routing efficiency and energy equilibrium in terms of trade-off.Location-aware routing protocols seem to possess high routing efficiency. However, there are two extremes in location-aware routing, the greedy strategy and the robust strategy. Greedy strategies may suffer failures to route packets to destination, while robust strategies need very high flooding rates to ensure reliability and rapid delivery of data. Thus, many location-aware routing protocols are mostly to propose methods to overcome the mentioned drawbacks. GPSR [2] is a famous greedy routing protocol, which makes greedy forwarding decisions using only information about a router's immediate neighbors. Sivrikaya et al. [3] propose randomized routing based on Markov chains to balance the load and routing performance. Kuhn et al. [4] utilize face (or perimeter) routing to go around voids in the topology. Bai et al. [5] present a routing algorithm which routes the connections in a manner that link failure does not shut down the entire stream but allows a continuing flow for a significant portion of the traffic along multiple paths to address the issues of reliability and energy efficiency. Trajcevski et al. [6] present heuristic approaches to relieve some of the routing load of the boundary nodes of energy holes in location-aware WSNs. Wang and Syue [7] propose a relay selection protocol based on geographical information, in which multihop transmission is realized by concatenation of single cluster-to-cluster hops.The energy-aware routing attracts more attention of researcher than location-aware routing for the significance of energy. For maximizing the network lifetime, Rao and Fapojuwo [8] present a battery-aware distributed clustering and routing protocol which incorporates the state of the battery’s remaining charge and health parameters in computing the charge utility metric at each cluster formation round. Trajcevski et al. [9] construct a data aggregation tree that minimizes the total energy cost of data transmission. By allowing the battery to rest for certain duration, without being subjected to heavy loads, Chau et al. [10] consider that a portion of the lost charge can be recovered due to the battery's recovery effect and present a battery model. A battery-aware power allocation model was studied in [11] for a single-hop transmission scheme to balance the network energy consumption based on the nonlinear battery parameters proposed in [12].In recent years, bio-inspired technology has been concerned by researchers [13–15]. We draw the inspiration from the slime mold Physarum polycephalum which is a large and single-celled amoeboid organism. Nakagaki et al. [16] validate physarum which is apparently able to solve shortest path problems by constructing a maze. Tero et al. [17] use physarum forms of a network with comparable efficiency, fault tolerance, and cost to those of Tokyo rail system. Tero et al. [18] propose a mathematical model for the behavior of physarum and argue extensively that the model is perfect. We migrate the physarum foraging model to wireless networks to develop physarum-based routing algorithms through dimensionless analogy analysis [19, 20].Based on our prior works [19–23], this paper focuses on how to choose the proper next hops to transmit data to the S
i
n
k in thinking of both routing efficiency and energy equilibrium, which is partially same to GEAR [24], other than only depending on the remaining energy [25]. The rest of this paper is organized as follows. Section 2 formulates the bio-inspired model. Section 3 proposes the P-bRS routing scheme. Section 4 evaluates our P-bRS by simulations. Finally, the conclusion is presented.


## 2. System Models

### 2.1. Typical WSNs Scenario

This paper considers large multihop WSNs which consist ofn static sensor nodes and a mobile S
i
n
k node, and the sensor nodes are distributed uniformly in a two-dimensional space. We assume that (1) all sensor nodes are aware of their locations, which may be achieved through GPS receivers or other methods; (2) each sensor node is aware of its energy residue; and (3) the S
i
n
k node moves along a certain orbit in the field and broadcasts periodically its current positions.In WSNs, each nodei has a fixed circular transmission range r which determines the set of sensors in which each node can communicate with node i in one hop. We abstract such WSNs using a graph G
=
(
V
,
E
), where each node v
∈
V represents a sensor and each edge e
∈
E represents the existence of one-hop wireless link between two sensors. An example of WSNs' topology is shown in Figure 1.Figure 1
An example of WSNs’ topology.The transmission range ofs is drawn as a dashed circle whose radius is r and center is s. We call the angle θ to be the angle of deviation, which represents a measurement of the next hop deviating from the S
i
n
k
d. The Euclidean distance of any two nodes and the angle θ can be calculated following (1) and (2), respectively. Consider
(1)
L
i
j
=
(
x
i
-
x
j
)
2
+
(
y
i
-
y
j
)
2
,
(2)
θ
=
arccos
L
s
c
2
+
L
s
d
2
-
L
c
d
2
2
×
L
s
c
×
L
s
d
,
where (
x
i
,
y
i
) and (
x
j
,
y
j
) are the coordinates of nodes i and j, respectively.If the nodes needs to transmit data to the S
i
n
k
d, it will select its next hop in the dashed circle. However, the nodes in semicircle far from the S
i
n
k are apparently inappropriate to be chosen as the next hop. Usually, we choose the next hop in the semicircle nearer to the S
i
n
k. Obviously, the smaller the angle θ is, the closer the next hop is to the S
i
n
k. Therefore, we are apt to choose the node whose θ is smaller as the next hop. In order to simplify discussion, we define the N
s, N
s
F, and N
s
N as the sets of neighbors (the nodes in the dash circle in Figure 1), far neighbors (the nodes in the left dash circle in Figure 1), and near neighbors (the nodes in the right dash circle in Figure 1), of node s, respectively, where N
s, N
s
F, and N
s
N satisfy N
s
=
N
s
F
∪
N
s
N and N
s
L
∩
N
s
R
=
∅.In addition, acquiring energy residues of neighbors is important for choosing next hop to balance the energy of sensor's nodes. We think of the basic theory of wireless transmission combing with Figure1. If node s transmits a group of data to c, all of the nodes in N
s would receive the wireless radio and check the packet header. The node c matches the field D
e
s
t
i
n
a
t
i
o
n and receives the packet. Other nodes mismatch the field D
e
s
t
i
n
a
t
i
o
n, then ignore the packet, and go on sleeping.In order to acquire the energy residue of neighbors, we add a new fieldE
n
e
r
g
y
_
R
e
s
i
d
u
e to the packet header. When node s transmits a group of data to c, all of the nodes in N
s extract the fields of S
o
u
r
c
e and E
n
e
r
g
y
_
R
e
s
i
d
u
e from the packet header and save E
n
e
r
g
y
_
R
e
s
i
d
u
e in local memory according to field S
o
u
r
c
e. Then, the node c matches the field D
e
s
t
i
n
a
t
i
o
n and receives the packet. Other nodes mismatch the D
e
s
t
i
n
a
t
i
o
n, then ignore the packet, and go on sleeping. Since each node needs to listen in real time to every packet and try to match its field D
e
s
t
i
n
a
t
i
o
n, only adding an operation of saving E
n
e
r
g
y
_
R
e
s
i
d
u
e would not add a considerable effect on energy consumption. Therefore, we neglect the cost of acquiring energy residue of neighbors.When theS
i
n
k moves along the certain orbit, it broadcasts periodically its current positions, as shown in Figure 2. Thus, the sensor nodes can achieve the current position of the S
i
n
k in real time. When a sensor node needs to send data to the S
i
n
k, it can calculate the θ following by the mode in Figure 1.Figure 2
The orbit of theS
i
n
k node.


### 2.2. Selecting Next Hop Model Based on Physarum

In this section, we draw a selecting next hop model (SNH) based on physarum foraging mechanism. From paper [18], the flux through each plasmodial tube is as follows:
(3)
Q
i
j
=
π
r
i
j
4
(
P
i
-
P
j
)
8
η
L
i
j
=
D
i
j
(
P
i
-
P
j
)
L
i
j
=
D
i
j
Δ
P
i
j
L
i
j
,
where Δ
P
i
j
=
P
i
-
P
j is the difference of pressures, η is the viscosity of the fluid, and D
i
j
=
π
r
i
j
4
/
8
η is a measure of the conductivity of the tube.Physarum forages for distributed food sources through adapting the adaptive behavior of the plasmodium. Consider(4)
d
d
t
D
i
j
=
φ
(
|
Q
i
j
|
)
-
δ
D
i
j
,
where δ is a decay rate of the tube and φ
(
·
) is a monotonically increasing continuous function satisfying φ
(
0
)
=
0. Since (3) and (4) come from fluid dynamics and cannot be directly used in WSNs, we should discuss how to migrate (3) and (4) to WSNs.Firstly, we discuss the replacement of physical quantities in (3). Because the D
i
j is an inherent characteristic of the tube, we replace the D
i
j by an inherent physical quantity of wireless link-link quality Φ
i
j. Since the meaning of L
i
j is the same as that in fluid dynamics, its meaning remains in our model. The replacement of Δ
P
i
j is rather complex. If flux (e.g., fluid or data packet) wishes migrate from source to destination passing by two other nodes, the fluid tends to flow through the node with lower pressure in fluid dynamics, while data packet should be relayed by the node with higher energy residue and lower angle of deviation. Therefore, we replace the P
j of node j by k
·
ER
j
+
(
1
-
k
)
cos
θ
j
i
d, so does P
i of node i. Since P
i is the base pressure, we replace Δ
P
i
j by P
j through omitting P
i. Using (3), we have
(5)
Q
i
j
=
D
i
j
·
Δ
P
L
i
j
=
Φ
i
j
[
k
·
ER
j
+
(
1
-
k
)
cos
θ
j
i
d
]
L
i
j
,
where Q
i
j is the virtual flux of communication through the wireless link i
j; Φ
i
j is the link quality; ER
j is the energy residue of node j; L
i
j is the Euclidean distance of nodes i and j; θ
j
i
d is the angle of deviation and its range is [
-
π
/
2
,
π
/
2
]; k is a proportional coefficient which is used to adjust the weight of ER
j and cos
θ
j
i
d.Because of the same characteristic of each node, we suppose that theΦ
i
j of each link is the same and ignore it to simplify discussion. Thus, we have
(6)
Q
i
j
=
D
i
j
·
Δ
P
L
i
j
=
k
·
ER
j
+
(
1
-
k
)
cos
θ
j
i
d
L
i
j
.Secondly, we analyze the adaptive behavior of plasmodium referring to Figure3(b), where two food sources are connected by two tubes. Because Δ
P
i
j
1
=
Δ
P
i
j
2 and L
i
j
1
>
L
i
j
2, the flux Q
i
j
2 will be greater than Q
i
j
1 from (3). Note that L
i
j
1 and L
i
j
2 are kept constant throughout the adaptation process in contrast to D
i
j. Therefore, the adaptive behavior of plasmodium is fulfilled by the evolution of D
i
j
(
t
). In WSNs, node i chooses the next hop form candidates as shown in Figure 3(a). Because (
1
)  L
i
j
1 and L
i
j
2 are kept constant, and (
2
)  Δ
P
i
j
1 and Δ
P
i
j
2 are different and time-varying, we can achieve the adaptation by the evolution of Δ
P
i
j
(
t
). Supposing that φ
(
Q
)
=
Q
μ, we have
(7)
d
d
t
Δ
P
i
j
=
φ
(
|
Q
|
)
-
δ
Δ
P
i
j
=
(
Φ
i
j
Δ
P
i
j
L
i
j
)
μ
-
δ
Δ
P
i
j
,
where δ is a decay rate of Δ
P
i
j and μ is a constant satisfying μ
>
0. We call (7) SNH and use it to determine the next hop in our P-bRS; namely, we choose the node with the largest d
Δ
P
i
j
/
d
t as the next hop.(a) If there are two candidates for next hop, the node who has the greaterk
×
ER
+
(
1
-
k
)
cos
θ will be picked as the next hop. (b) If two food sources are connected by two tubes, the longer tube L
i
j
1 will vanish with time going by.
(a)
(b)


## 2.1. Typical WSNs Scenario

This paper considers large multihop WSNs which consist ofn static sensor nodes and a mobile S
i
n
k node, and the sensor nodes are distributed uniformly in a two-dimensional space. We assume that (1) all sensor nodes are aware of their locations, which may be achieved through GPS receivers or other methods; (2) each sensor node is aware of its energy residue; and (3) the S
i
n
k node moves along a certain orbit in the field and broadcasts periodically its current positions.In WSNs, each nodei has a fixed circular transmission range r which determines the set of sensors in which each node can communicate with node i in one hop. We abstract such WSNs using a graph G
=
(
V
,
E
), where each node v
∈
V represents a sensor and each edge e
∈
E represents the existence of one-hop wireless link between two sensors. An example of WSNs' topology is shown in Figure 1.Figure 1
An example of WSNs’ topology.The transmission range ofs is drawn as a dashed circle whose radius is r and center is s. We call the angle θ to be the angle of deviation, which represents a measurement of the next hop deviating from the S
i
n
k
d. The Euclidean distance of any two nodes and the angle θ can be calculated following (1) and (2), respectively. Consider
(1)
L
i
j
=
(
x
i
-
x
j
)
2
+
(
y
i
-
y
j
)
2
,
(2)
θ
=
arccos
L
s
c
2
+
L
s
d
2
-
L
c
d
2
2
×
L
s
c
×
L
s
d
,
where (
x
i
,
y
i
) and (
x
j
,
y
j
) are the coordinates of nodes i and j, respectively.If the nodes needs to transmit data to the S
i
n
k
d, it will select its next hop in the dashed circle. However, the nodes in semicircle far from the S
i
n
k are apparently inappropriate to be chosen as the next hop. Usually, we choose the next hop in the semicircle nearer to the S
i
n
k. Obviously, the smaller the angle θ is, the closer the next hop is to the S
i
n
k. Therefore, we are apt to choose the node whose θ is smaller as the next hop. In order to simplify discussion, we define the N
s, N
s
F, and N
s
N as the sets of neighbors (the nodes in the dash circle in Figure 1), far neighbors (the nodes in the left dash circle in Figure 1), and near neighbors (the nodes in the right dash circle in Figure 1), of node s, respectively, where N
s, N
s
F, and N
s
N satisfy N
s
=
N
s
F
∪
N
s
N and N
s
L
∩
N
s
R
=
∅.In addition, acquiring energy residues of neighbors is important for choosing next hop to balance the energy of sensor's nodes. We think of the basic theory of wireless transmission combing with Figure1. If node s transmits a group of data to c, all of the nodes in N
s would receive the wireless radio and check the packet header. The node c matches the field D
e
s
t
i
n
a
t
i
o
n and receives the packet. Other nodes mismatch the field D
e
s
t
i
n
a
t
i
o
n, then ignore the packet, and go on sleeping.In order to acquire the energy residue of neighbors, we add a new fieldE
n
e
r
g
y
_
R
e
s
i
d
u
e to the packet header. When node s transmits a group of data to c, all of the nodes in N
s extract the fields of S
o
u
r
c
e and E
n
e
r
g
y
_
R
e
s
i
d
u
e from the packet header and save E
n
e
r
g
y
_
R
e
s
i
d
u
e in local memory according to field S
o
u
r
c
e. Then, the node c matches the field D
e
s
t
i
n
a
t
i
o
n and receives the packet. Other nodes mismatch the D
e
s
t
i
n
a
t
i
o
n, then ignore the packet, and go on sleeping. Since each node needs to listen in real time to every packet and try to match its field D
e
s
t
i
n
a
t
i
o
n, only adding an operation of saving E
n
e
r
g
y
_
R
e
s
i
d
u
e would not add a considerable effect on energy consumption. Therefore, we neglect the cost of acquiring energy residue of neighbors.When theS
i
n
k moves along the certain orbit, it broadcasts periodically its current positions, as shown in Figure 2. Thus, the sensor nodes can achieve the current position of the S
i
n
k in real time. When a sensor node needs to send data to the S
i
n
k, it can calculate the θ following by the mode in Figure 1.Figure 2
The orbit of theS
i
n
k node.


## 2.2. Selecting Next Hop Model Based on Physarum

In this section, we draw a selecting next hop model (SNH) based on physarum foraging mechanism. From paper [18], the flux through each plasmodial tube is as follows:
(3)
Q
i
j
=
π
r
i
j
4
(
P
i
-
P
j
)
8
η
L
i
j
=
D
i
j
(
P
i
-
P
j
)
L
i
j
=
D
i
j
Δ
P
i
j
L
i
j
,
where Δ
P
i
j
=
P
i
-
P
j is the difference of pressures, η is the viscosity of the fluid, and D
i
j
=
π
r
i
j
4
/
8
η is a measure of the conductivity of the tube.Physarum forages for distributed food sources through adapting the adaptive behavior of the plasmodium. Consider(4)
d
d
t
D
i
j
=
φ
(
|
Q
i
j
|
)
-
δ
D
i
j
,
where δ is a decay rate of the tube and φ
(
·
) is a monotonically increasing continuous function satisfying φ
(
0
)
=
0. Since (3) and (4) come from fluid dynamics and cannot be directly used in WSNs, we should discuss how to migrate (3) and (4) to WSNs.Firstly, we discuss the replacement of physical quantities in (3). Because the D
i
j is an inherent characteristic of the tube, we replace the D
i
j by an inherent physical quantity of wireless link-link quality Φ
i
j. Since the meaning of L
i
j is the same as that in fluid dynamics, its meaning remains in our model. The replacement of Δ
P
i
j is rather complex. If flux (e.g., fluid or data packet) wishes migrate from source to destination passing by two other nodes, the fluid tends to flow through the node with lower pressure in fluid dynamics, while data packet should be relayed by the node with higher energy residue and lower angle of deviation. Therefore, we replace the P
j of node j by k
·
ER
j
+
(
1
-
k
)
cos
θ
j
i
d, so does P
i of node i. Since P
i is the base pressure, we replace Δ
P
i
j by P
j through omitting P
i. Using (3), we have
(5)
Q
i
j
=
D
i
j
·
Δ
P
L
i
j
=
Φ
i
j
[
k
·
ER
j
+
(
1
-
k
)
cos
θ
j
i
d
]
L
i
j
,
where Q
i
j is the virtual flux of communication through the wireless link i
j; Φ
i
j is the link quality; ER
j is the energy residue of node j; L
i
j is the Euclidean distance of nodes i and j; θ
j
i
d is the angle of deviation and its range is [
-
π
/
2
,
π
/
2
]; k is a proportional coefficient which is used to adjust the weight of ER
j and cos
θ
j
i
d.Because of the same characteristic of each node, we suppose that theΦ
i
j of each link is the same and ignore it to simplify discussion. Thus, we have
(6)
Q
i
j
=
D
i
j
·
Δ
P
L
i
j
=
k
·
ER
j
+
(
1
-
k
)
cos
θ
j
i
d
L
i
j
.Secondly, we analyze the adaptive behavior of plasmodium referring to Figure3(b), where two food sources are connected by two tubes. Because Δ
P
i
j
1
=
Δ
P
i
j
2 and L
i
j
1
>
L
i
j
2, the flux Q
i
j
2 will be greater than Q
i
j
1 from (3). Note that L
i
j
1 and L
i
j
2 are kept constant throughout the adaptation process in contrast to D
i
j. Therefore, the adaptive behavior of plasmodium is fulfilled by the evolution of D
i
j
(
t
). In WSNs, node i chooses the next hop form candidates as shown in Figure 3(a). Because (
1
)  L
i
j
1 and L
i
j
2 are kept constant, and (
2
)  Δ
P
i
j
1 and Δ
P
i
j
2 are different and time-varying, we can achieve the adaptation by the evolution of Δ
P
i
j
(
t
). Supposing that φ
(
Q
)
=
Q
μ, we have
(7)
d
d
t
Δ
P
i
j
=
φ
(
|
Q
|
)
-
δ
Δ
P
i
j
=
(
Φ
i
j
Δ
P
i
j
L
i
j
)
μ
-
δ
Δ
P
i
j
,
where δ is a decay rate of Δ
P
i
j and μ is a constant satisfying μ
>
0. We call (7) SNH and use it to determine the next hop in our P-bRS; namely, we choose the node with the largest d
Δ
P
i
j
/
d
t as the next hop.(a) If there are two candidates for next hop, the node who has the greaterk
×
ER
+
(
1
-
k
)
cos
θ will be picked as the next hop. (b) If two food sources are connected by two tubes, the longer tube L
i
j
1 will vanish with time going by.
(a)
(b)


## 3. P-bRS Routing Scheme

### 3.1. Data Structure in P-bRS

In this section, we introduce the data which should be conserved in each node. Each nodei needs to conserve the following information: L
i
j
(
j
∈
N
i
), θ
j
i
d
(
j
∈
N
i
R
), ER
i
j
(
j
∈
N
i
), ER
i
i, and β
i
p
j
(
j
∈
N
i
L
), where node p is the previous hop of node i, ER
i
i represents the ER
i stored in node i, and ER
i
j represents the ER
j stored in node i. As our WSNs are location-aware, the L
i
j, θ
j
i
d, and θ
i
p
j are easily acquired following (1) and (2). Note that the nodes in our WSNs are fixed, and we only need to calculate the L
i
j once at WSNs deployment time. For the difference between E
R
j and cos
θ
j
i
d, we normalize ER
j to ER
^
j. Therefore, we obtain
(8)
Q
i
j
=
k
×
ER
^
j
+
(
1
-
k
)
cos
θ
j
i
d
L
i
j
,
(9)
d
d
t
Δ
P
i
j
=
(
k
×
ER
^
j
+
(
1
-
k
)
cos
θ
j
i
d
L
i
j
)
μ
-
δ
[
k
×
ER
^
j
+
(
1
-
k
)
cos
θ
j
i
d
]
.


### 3.2.  Routing Scheme Algorithm

If nodes needs to send data to the S
i
n
k
d, it searches for a routing in the following method.Step 1.
Receive the positioning information of theS
i
n
k node, and then calculate each θ
j
i
d and β
i
p
j.Step 2.
Divide each nodej
∈
N
s into j
∈
N
s
F or j
∈
N
s
N based on the positioning information of the S
i
n
k node.Step 3.
Calculate eachd
Δ
P
s
j
/
d
t
(
j
∈
N
s
N
) following from (9), where θ
j
s
d, ER
^
s
j, and L
^
s
j are acquired by node s beforehand.Step 4.
Each nodej
∈
N
s
N is saved into a temporary array variable T
e
m
p in descending order by d
Δ
P
s
j
/
d
t.Step 5.
The first node inT
e
m
p is picked as the next hop of the routing.Step 6.
If the next hopa of node s satisfies N
a
N
=
∅, namely, there is an energy hole in WSNs, the node a will not send A
C
K to s. Then, the node s will trigger a specific processing routine.Step 7.
If|
T
e
m
p
[
0
]
→
θ
j
s
d
-
T
e
m
p
[
1
]
→
θ
j
s
d
|
≥
π
/
2, node s will choose the node T
e
m
p
[
1
] as the next hop. Then, the regular processing routine is going on.Step 8.
Otherwise, eachd
Δ
P
/
d
t
(
j
∈
N
s
F
) is calculated following (10) and the nodes are saved into the T
e
m
p in ascending order by d
Δ
P
/
d
t. Then, the first node in T
e
m
p is chosen as the next hop of the routing and the regular processing routine is going on. Consider
(10)
d
d
t
Δ
P
i
j
=
(
k
×
ER
^
j
+
(
1
-
k
)
β
a
s
j
L
i
j
)
μ
-
δ
[
k
×
ER
^
j
+
(
1
-
k
)
β
a
s
j
]
,
where β
a
s
j is the angle of line s
a and line s
j. Equation (10) indicates that it tends to choose a node which sharply deviates from the node a as the next hop to avoid entering the energy hole again.Step 9.
The process is repeated, like a rolling wheel, until theS
i
n
k
d is found.


### 3.3.  Algorithm Analysis

In this section, we analyze the feasibility of SNH by mathematical theoretical analysis. We study cases in which two nodes connected to the same node compete to be the next hop, as shown in Figure3(a).There are four nodesi, j
1, j
2, and S
i
n
k
d. For simplicity, we hereafter replace L
i
j
1, L
i
j
2, Q
i
j
1, Q
i
j
2, Δ
P
i
j
1, and Δ
P
i
j
2 by L
1, L
2, Q
1, Q
2, Δ
P
1, and Δ
P
2, respectively. In multipath routing, the virtual fluxes along each path are calculated as follows:
(11)
Q
1
=
Δ
P
1
/
L
1
Δ
P
1
/
L
1
+
Δ
P
2
/
L
2
,
Q
2
=
Δ
P
2
/
L
2
Δ
P
1
/
L
1
+
Δ
P
2
/
L
2
.SinceQ
1 and Q
2 are nonnegative, adaptation equation (7) becomes
(12)
d
d
t
(
Δ
P
1
)
=
φ
(
Q
1
)
-
δ
·
Δ
P
1
,
d
d
t
(
Δ
P
2
)
=
φ
(
Q
2
)
-
δ
·
Δ
P
2
.Settingφ
(
Q
)
=
Q
μ, (
d
/
d
t
)
(
Δ
P
1
)
=
0, and (
d
/
d
t
)
(
Δ
P
2
)
=
0, we have
(13)
(
Δ
P
1
/
L
1
Δ
P
1
/
L
1
+
Δ
P
2
/
L
2
)
μ
=
δ
·
Δ
P
1
,
(
Δ
P
2
/
L
2
Δ
P
1
/
L
1
+
Δ
P
2
/
L
2
)
μ
=
δ
·
Δ
P
2
.From (13), we obtain
(14)
Δ
P
2
=
(
δ
-
1
/
μ
(
Δ
P
1
)
1
-
1
/
μ
-
Δ
P
1
)
L
2
L
1
.From (13) and (14), we obtain
(15)
Δ
P
1
=
1
δ
[
1
(
1
+
(
L
1
/
L
2
)
1
/
1
-
μ
)
]
μ
.Similarly,(16)
Δ
P
2
=
1
δ
[
1
(
1
+
(
L
2
/
L
1
)
1
/
1
-
μ
)
]
μ
.Namely, equilibrium point is given by(
Δ
P
1
,
Δ
P
2
). We perform the simulation by setting the parameters μ
=
0.8, δ
=
0.3, L
1
=
10, and L
2
=
12 following from (13), and the visualization of the solutions is shown in Figure 4, where point E is the equilibrium point of two curves. Therefore, the routing of WSNs will reach equilibrium with our SNH, which is very important to a routing strategy.Figure 4
Asymptotic behavior of the solution inμ
=
0.8, δ
=
0.3, L
1
=
10, and L
2
=
12: two curves which come from (13) intersect in a point E, which is the sole equilibrium point.


## 3.1. Data Structure in P-bRS

In this section, we introduce the data which should be conserved in each node. Each nodei needs to conserve the following information: L
i
j
(
j
∈
N
i
), θ
j
i
d
(
j
∈
N
i
R
), ER
i
j
(
j
∈
N
i
), ER
i
i, and β
i
p
j
(
j
∈
N
i
L
), where node p is the previous hop of node i, ER
i
i represents the ER
i stored in node i, and ER
i
j represents the ER
j stored in node i. As our WSNs are location-aware, the L
i
j, θ
j
i
d, and θ
i
p
j are easily acquired following (1) and (2). Note that the nodes in our WSNs are fixed, and we only need to calculate the L
i
j once at WSNs deployment time. For the difference between E
R
j and cos
θ
j
i
d, we normalize ER
j to ER
^
j. Therefore, we obtain
(8)
Q
i
j
=
k
×
ER
^
j
+
(
1
-
k
)
cos
θ
j
i
d
L
i
j
,
(9)
d
d
t
Δ
P
i
j
=
(
k
×
ER
^
j
+
(
1
-
k
)
cos
θ
j
i
d
L
i
j
)
μ
-
δ
[
k
×
ER
^
j
+
(
1
-
k
)
cos
θ
j
i
d
]
.


## 3.2.  Routing Scheme Algorithm

If nodes needs to send data to the S
i
n
k
d, it searches for a routing in the following method.Step 1.
Receive the positioning information of theS
i
n
k node, and then calculate each θ
j
i
d and β
i
p
j.Step 2.
Divide each nodej
∈
N
s into j
∈
N
s
F or j
∈
N
s
N based on the positioning information of the S
i
n
k node.Step 3.
Calculate eachd
Δ
P
s
j
/
d
t
(
j
∈
N
s
N
) following from (9), where θ
j
s
d, ER
^
s
j, and L
^
s
j are acquired by node s beforehand.Step 4.
Each nodej
∈
N
s
N is saved into a temporary array variable T
e
m
p in descending order by d
Δ
P
s
j
/
d
t.Step 5.
The first node inT
e
m
p is picked as the next hop of the routing.Step 6.
If the next hopa of node s satisfies N
a
N
=
∅, namely, there is an energy hole in WSNs, the node a will not send A
C
K to s. Then, the node s will trigger a specific processing routine.Step 7.
If|
T
e
m
p
[
0
]
→
θ
j
s
d
-
T
e
m
p
[
1
]
→
θ
j
s
d
|
≥
π
/
2, node s will choose the node T
e
m
p
[
1
] as the next hop. Then, the regular processing routine is going on.Step 8.
Otherwise, eachd
Δ
P
/
d
t
(
j
∈
N
s
F
) is calculated following (10) and the nodes are saved into the T
e
m
p in ascending order by d
Δ
P
/
d
t. Then, the first node in T
e
m
p is chosen as the next hop of the routing and the regular processing routine is going on. Consider
(10)
d
d
t
Δ
P
i
j
=
(
k
×
ER
^
j
+
(
1
-
k
)
β
a
s
j
L
i
j
)
μ
-
δ
[
k
×
ER
^
j
+
(
1
-
k
)
β
a
s
j
]
,
where β
a
s
j is the angle of line s
a and line s
j. Equation (10) indicates that it tends to choose a node which sharply deviates from the node a as the next hop to avoid entering the energy hole again.Step 9.
The process is repeated, like a rolling wheel, until theS
i
n
k
d is found.


## 3.3.  Algorithm Analysis

In this section, we analyze the feasibility of SNH by mathematical theoretical analysis. We study cases in which two nodes connected to the same node compete to be the next hop, as shown in Figure3(a).There are four nodesi, j
1, j
2, and S
i
n
k
d. For simplicity, we hereafter replace L
i
j
1, L
i
j
2, Q
i
j
1, Q
i
j
2, Δ
P
i
j
1, and Δ
P
i
j
2 by L
1, L
2, Q
1, Q
2, Δ
P
1, and Δ
P
2, respectively. In multipath routing, the virtual fluxes along each path are calculated as follows:
(11)
Q
1
=
Δ
P
1
/
L
1
Δ
P
1
/
L
1
+
Δ
P
2
/
L
2
,
Q
2
=
Δ
P
2
/
L
2
Δ
P
1
/
L
1
+
Δ
P
2
/
L
2
.SinceQ
1 and Q
2 are nonnegative, adaptation equation (7) becomes
(12)
d
d
t
(
Δ
P
1
)
=
φ
(
Q
1
)
-
δ
·
Δ
P
1
,
d
d
t
(
Δ
P
2
)
=
φ
(
Q
2
)
-
δ
·
Δ
P
2
.Settingφ
(
Q
)
=
Q
μ, (
d
/
d
t
)
(
Δ
P
1
)
=
0, and (
d
/
d
t
)
(
Δ
P
2
)
=
0, we have
(13)
(
Δ
P
1
/
L
1
Δ
P
1
/
L
1
+
Δ
P
2
/
L
2
)
μ
=
δ
·
Δ
P
1
,
(
Δ
P
2
/
L
2
Δ
P
1
/
L
1
+
Δ
P
2
/
L
2
)
μ
=
δ
·
Δ
P
2
.From (13), we obtain
(14)
Δ
P
2
=
(
δ
-
1
/
μ
(
Δ
P
1
)
1
-
1
/
μ
-
Δ
P
1
)
L
2
L
1
.From (13) and (14), we obtain
(15)
Δ
P
1
=
1
δ
[
1
(
1
+
(
L
1
/
L
2
)
1
/
1
-
μ
)
]
μ
.Similarly,(16)
Δ
P
2
=
1
δ
[
1
(
1
+
(
L
2
/
L
1
)
1
/
1
-
μ
)
]
μ
.Namely, equilibrium point is given by(
Δ
P
1
,
Δ
P
2
). We perform the simulation by setting the parameters μ
=
0.8, δ
=
0.3, L
1
=
10, and L
2
=
12 following from (13), and the visualization of the solutions is shown in Figure 4, where point E is the equilibrium point of two curves. Therefore, the routing of WSNs will reach equilibrium with our SNH, which is very important to a routing strategy.Figure 4
Asymptotic behavior of the solution inμ
=
0.8, δ
=
0.3, L
1
=
10, and L
2
=
12: two curves which come from (13) intersect in a point E, which is the sole equilibrium point.


## 4. Simulation Results

We design a simulation platform using C++ to validate P-bRS. In the simulation, 400 sensors are relatively regularly deployed in the field of 200 m × 200 m, and theS
i
n
k node is deployed the right of the field, as shown in Figure 5. The sensing radius of each sensor is 30 m, the original energy of each node is 100, and the energy of the S
i
n
k node is inexhaustible. We suppose that the energy consumption of one transmission is 1, if the transmission distance is 20 m. Therefore, the energy consumption of one transmission of two nodes i and j is (
L
i
j
/
20
).Figure 5
Sensors distribution.In order to validate the energy equilibrium, we only choose the nodes in the center or peripheral simulation field (enclosed by red dashed circle or two red dashed rectangles in Figure5) to transmit data to the S
i
n
k. If a chosen node transmits a group of data to the S
i
n
k, the P-bRS is used to choose next hops until the S
i
n
k is found, which is called a r
o
u
n
d. This iterative process will halt after n rounds until WSNs break down. We run GPSR, GEAR (k
=
0.5
,
0.9, where we use k to replace α which is used in [24] to bring into correspondence with P-BRS) and P-bRS (k
=
0.5
,
0.9) 10 times, respectively, to acquire their average value and compare them. If the distance between the nodes and the S
i
n
k is less than 30 m, we set the nodes to directly transmit data to the S
i
n
k to quicken convergence of P-bRS, and the energy consumption is set to 1.


### 4.1. Energy Equilibrium of P-bRS

Figure6 illustrates the lifetime of WSNs. In GPSR, the first dead node emerges in round of 406, and the WSNs break down in round of 1857. In GEAR (k
=
0.5), the first dead node emerges in round of 1955, and the WSNs break down in round of 3042. In P-bRS (k
=
0.5), the first dead node emerges in round of 2284, and the WSNs break down in round of 3351. In GEAR (k
=
0.9), the first dead node emerges in round of 3462, and the WSNs break down in round of 4043. In P-bRS (k
=
0.9), the first dead node emerges in round of 3524, and the WSNs break down in round of 4108. Therefore, the lifetime of GEAR (k
=
0.5) is 63.8% longer than that of GPSR; the lifetime of P-bRS (k
=
0.5) is 10.2% longer than that of GEAR (k
=
0.5); and the lifetime of P-bRS (k
=
0.9) is 1.6% longer than that of GEAR (k
=
0.9). From Figure 6, we can differ that (
1
) whether considering energy residue of next hops or not will impact on the lifetime of WSNs greatly; (
2
) in energy balanced WSNs, the time period is very short from emerging dead nodes to networks breaking down, because all nodes reach exhausted status of energy in same time period.Figure 6
Lifetime of network.Figure7 illustrates the dead nodes distributions of GEAR (k
=
0.5) and P-bRS (k
=
0.5) in the rounds of 2750. The results show that P-bRS (k
=
0.5) has much less dead nodes than GEAR (k
=
0.5). We can also differ that the dead nodes of both algorithms are converged on a specific field but not spread around the entire range of WSNs, which is useful in deploying such WSNs to prolong the lifetime through rationally deploying the specific field.Distribution of dead sensor nodes.
(a)
P-bRS,k
=
0.5, round
=
2750
(b)
GEAR,k
=
0.5, round
=
2750


### 4.2.  Efficiency of P-bRS

Figure8 illustrates the number of hops that the different algorithms need in different rounds of transmission. By calculating, the average hops of GPSR, GEAR (k
=
0.5), P-bRS (k
=
0.5), GEAR (k
=
0.9), and P-bRS (k
=
0.9), are 9.7, 12.2, 11.1, 14.8, and 13.3, respectively.Figure 8
Needing hops of transmission of each round.In the case ofk
=
0.5, the average hop of P-bRS is 14.4% more than that of GPSR, and the hop of GEAR is 25.8% more than that of GPSR. Combing with Figure 8, the increment of average hops of 14.4% will lead to the increment of lifetime of more than 70% from GPSR to P-bRS, while the increment of average hops of 25.8% will only lead to the increment of lifetime of more than 60% from GPSR to GEAR. Therefore, the P-bRS is more efficient in balance of routing efficiency and energy equilibrium than GEAR.In the case ofk
=
0.9, the average hop of P-bRS is 37.1% more than that of GPSR, and the hop of GEAR is 52.6% more than that of GPSR. Combing with Figure 6, the increment of 14.4% of average hops will lead to the increment of about 70% of lifetime from GPSR to P-bRS (k
=
0.5), while the increment of 19.8% of average hops will only cause the increment of 22.6% of lifetime from P-bRS (k
=
0.5) to P-bRS (k
=
0.9). That is to say, the larger k is, the smaller the increment of k impacts on lifetime of WSNs. Therefore, it is improper to set a larger k, so does GEAR.


## 4.1. Energy Equilibrium of P-bRS

Figure6 illustrates the lifetime of WSNs. In GPSR, the first dead node emerges in round of 406, and the WSNs break down in round of 1857. In GEAR (k
=
0.5), the first dead node emerges in round of 1955, and the WSNs break down in round of 3042. In P-bRS (k
=
0.5), the first dead node emerges in round of 2284, and the WSNs break down in round of 3351. In GEAR (k
=
0.9), the first dead node emerges in round of 3462, and the WSNs break down in round of 4043. In P-bRS (k
=
0.9), the first dead node emerges in round of 3524, and the WSNs break down in round of 4108. Therefore, the lifetime of GEAR (k
=
0.5) is 63.8% longer than that of GPSR; the lifetime of P-bRS (k
=
0.5) is 10.2% longer than that of GEAR (k
=
0.5); and the lifetime of P-bRS (k
=
0.9) is 1.6% longer than that of GEAR (k
=
0.9). From Figure 6, we can differ that (
1
) whether considering energy residue of next hops or not will impact on the lifetime of WSNs greatly; (
2
) in energy balanced WSNs, the time period is very short from emerging dead nodes to networks breaking down, because all nodes reach exhausted status of energy in same time period.Figure 6
Lifetime of network.Figure7 illustrates the dead nodes distributions of GEAR (k
=
0.5) and P-bRS (k
=
0.5) in the rounds of 2750. The results show that P-bRS (k
=
0.5) has much less dead nodes than GEAR (k
=
0.5). We can also differ that the dead nodes of both algorithms are converged on a specific field but not spread around the entire range of WSNs, which is useful in deploying such WSNs to prolong the lifetime through rationally deploying the specific field.Distribution of dead sensor nodes.
(a)
P-bRS,k
=
0.5, round
=
2750
(b)
GEAR,k
=
0.5, round
=
2750


## 4.2.  Efficiency of P-bRS

Figure8 illustrates the number of hops that the different algorithms need in different rounds of transmission. By calculating, the average hops of GPSR, GEAR (k
=
0.5), P-bRS (k
=
0.5), GEAR (k
=
0.9), and P-bRS (k
=
0.9), are 9.7, 12.2, 11.1, 14.8, and 13.3, respectively.Figure 8
Needing hops of transmission of each round.In the case ofk
=
0.5, the average hop of P-bRS is 14.4% more than that of GPSR, and the hop of GEAR is 25.8% more than that of GPSR. Combing with Figure 8, the increment of average hops of 14.4% will lead to the increment of lifetime of more than 70% from GPSR to P-bRS, while the increment of average hops of 25.8% will only lead to the increment of lifetime of more than 60% from GPSR to GEAR. Therefore, the P-bRS is more efficient in balance of routing efficiency and energy equilibrium than GEAR.In the case ofk
=
0.9, the average hop of P-bRS is 37.1% more than that of GPSR, and the hop of GEAR is 52.6% more than that of GPSR. Combing with Figure 6, the increment of 14.4% of average hops will lead to the increment of about 70% of lifetime from GPSR to P-bRS (k
=
0.5), while the increment of 19.8% of average hops will only cause the increment of 22.6% of lifetime from P-bRS (k
=
0.5) to P-bRS (k
=
0.9). That is to say, the larger k is, the smaller the increment of k impacts on lifetime of WSNs. Therefore, it is improper to set a larger k, so does GEAR.


## 5. Conclusion

The physarum forages for patchily distributed food sources through accommodating its body to form networks with comparable efficiency, fault tolerance, and cost. We draw inspiration from the physarum model and improve it to suit the routing choice for WSNs. The P-bRS algorithm can deal with the trade-off between routing efficiency and energy equilibrium in WSNs, which greatly reduces the processing delay and saves the energy of sensors. Based on the simulation results, we discuss the P-bRS's performance. In future work, we consider introducing actual mobility model of nodes into P-bRS to make it fit in with mobile WSNs. Moreover, we consider the model may also provide a useful help to develop the routing protocols in other networks, which will be our future focus.



---

*Source: 531032-2014-02-05.xml*