On the Deployment of Wireless Data Back-haul Networks

On the Deployment of Wireless Data Back-haul Networks Xin Liu and Prasant Mohapatra Department of Computer Science University of California, Davis, CA 95616 Abstract— We study the deployment of data back-haul nodes for wireless networks with energy constraints. We address the
following problem: given the required lifetime of a sensor
network, the energy constraint of back-haul nodes, and the
area to be covered, what is the minimum number of nodes
needed to construct such a back-haul network and what is
the corresponding deployment scheme? Finding an efficient
deployment scheme involves location management, routing, and
power management. We focus on linear networks and formulate a
deployment optimization problem. We then propose and analyze
a greedy deployment scheme that achieves close to optimal
performance. We reveal the closed-form relationship among
different design parameters, namely, the number of sensor nodes,
the desired lifetime, and the coverage distance. We also study
the effect of miscellaneous power consumptions and non-uniform
data density, and consider extensions to planar networks. Index Terms— Deployment, Sensor Networks, Lifetime. I. I NTRODUCTION We study the deployment of data back-haul nodes for wireless networks with energy constraints. An application
scenarios is in wireless sensor networks. For many sensor-
network applications, the desired lifetime of the network is on
the order of a few years. It may be infeasible or expensive
to change batteries in sensor nodes once a wireless sensor
network is deployed. Thus, it is critical and challenging to
deploy sensor nodes effectively to form long-lived sensor
networks under energy constraints. Hierarchical structure has been considered as a necessity for large wireless systems. An example is shown in Figure 1.
The bigger gray nodes represent more capable and expensive
nodes in the higher hierarchy that are responsible for data
processing and back hauling. The smaller dark nodes rep-
resent sensing nodes that collect information on interested
events and report to nearby gray nodes for processing and
communication. Consider a real-world example. Crossbow
Technology Inc. supplies both smaller and less expensive mote
series and more sophisticated and expensive Gateways series.
We can consider the mote series as sensing nodes and the
Gateways series as data back-hauling nodes in the Figure.
In a remote area, both sensing nodes and data back-haul
nodes can be energy constrained, which limit the lifetime
of a sensor network. In this study, we focus on data back-
haul nodes that consume more energy for communications
and are mission-critical. Because these nodes are important
and usually expensive, strategic deployment of these nodes
is justified. In this paper, we study the deployment of these Fig. 1. A Hierarchical Linear Network nodes to satisfy the desired lifetime requirement. The degrees
of freedom for such a design are multi-fold. They involve
topology management, power management, and routing. We focus on a many-to-one sensor network. In a many- to-one network, data from all nodes is directed to a sink-
node/fusion-center. Many-to-one communication is typical in
sensor networks used for monitoring/surveillance purposes.
Unlike a distributed peer-to-peer wireless networks, the traffic
load is highly asymmetric in a many-to-one network, i.e.,
nodes closer to the sink node have heavier relay load, as illus-
trated in Figure 1. Thus, the traffic load and the corresponding
power consumption are location-dependent. The lifetime of a
network can be limited by nodes with heavy traffic load or
power consumptions. This problem is adequately captured in
this work. We use data density to model the amount of data generated in a sensor network and assume that the data density is uniform
unless otherwise stated. Given the energy constraint and data
density, our objective is to answer the following question: What is the minimum number of data back-haul
nodes we need to construct a sensor network and
how these data back-haul nodes should be placed
such that the network can satisfy the predetermined
life-time and coverage requirement? An alternative question is: given the number of data back-haul
nodes, and the desired life time of the sensor network, how
large an area can this sensor network cover and how? Yet
another objective is: given the number of nodes and the area
to be covered, what is the maximum lifetime of the network
and what is the deployment scheme to achieve it? In this paper, our primary focus is on linear sensor net- works, in which the data back-haul nodes are deployed in a
linear topology. Such a topology can be used in a narrow
and long sensor network, as shown in Figure 1. This is
justified by real world examples. For instance, the sensor
network deployed on Great Duck Island is in a narrow-and- 2 long shape (about 50 nodes long and 5 nodes wide) [1]. Other
applications include sensor networks for border surveillance,
highway traffic monitoring, safeguarding railway tracks, oil
and natural gas pipeline protection, and structural monitoring
and surveillance of bridges and long hallways. In addition, we
have also provided heuristics for analyzing planar networks
using the analysis of the basic linear topology. We assume the deployment of data back-haul nodes is care- fully planned and controlled instead of randomly performed.
First, in most current sensor network deployments, sensor
nodes are manually deployed instead of randomly thrown
into the field of interest. Furthermore, because data back-
haul nodes are mission-critical, expensive, and in a relatively
small number, careful planning and deployment is justified.
Our numerical results show that the lifetime of a randomly
deployed network is an order of magnitude lower than that of
a carefully deployed one. The paper is organized as follows. We discuss related work in Section II. In Section III, we elaborate the problem and
introduce a deployment optimization problem. In Section IV,
we propose and analyze a greedy deployment scheme. We
show that the performance of the greedy scheme is close to
optimal. The closed-form analysis of the greedy scheme allows
us to understand the relationship among the design parameters.
We study the effects miscellaneous power consumptions and
non-uniform data density, and consider extensions to planar
networks in Section V. The paper is concluded in Section VI. II. R ELATED W ORK In this section we briefly discuss the related work on the capacity and lifetime of wireless adhoc/sensor networks.
Bhardwaj et al have provided upper bounds on the lifetime of
sensor networks [2], [3] where sensor node locations are given.
In [4], the authors propose a transmission range distribution
optimization scheme to maximize the network lifetime given
fixed node locations. In comparison, our work is to address
the deployment issue of sensor networks. Energy conservation
and lifetime extension is investigated in [5] using cell-based
techniques [6]. In comparison, our work focuses on many-to-
one networks, which is significantly different from random
distributed peer-to-peer networks. In [7], the authors study
the problem of placing the sink-node to maximize the life-
time of the network in a two-tiered wireless sensor network.
Furthermore, the placement and power management of ad-
ditional relay nodes are also considered in [8]. The joint
design problem is formulated as a mixed-integer nonlinear
programming problem and heuristic algorithms are proposed.
Our work is different in the sense that we assume only one
fixed sink node. In addition, the relay nodes do not have their
own traffic load in [8], which also differs from our scenario. The most closely related work is by Ganesan et al [9], where our work differs in terms of the data collection model.
The problem is not solved for the general model in [9],
and the optimal scheme presented in [9] assumes that each
node has the same amount of data regardless of its coverage
distance. In comparison, we assume uniform data density
across the network, and thus a node that covers a larger distance has more data. In our model, more complexity is
involved because the data volume at each node is a function
of its distance from its neighboring node. In other words, the
total amount of data relayed to the fusion center is linearly
proportional to the total number of nodes in [9], while it is
proportional to the total distance that the network covers in our
work. Thus, their results do not yield our results. We justify
our assumption using the following example of a borderline
surveillance network. Assume that events happen uniformly
and randomly in the surveillance area. Then it is reasonable
to assume that the total number of events reported to the fusion
center is proportional to the length of the borderline instead
of the number of nodes deployed. In other words, a node that
covers a larger area/distance observes more events and thus
generates more data. This phenomena is particularly evident
when we consider the higher layers in a hierarchical network. Maximum lifetime routing in sensor and ad hoc networks have been studied extensively in the literature, see e.g., [10],
[11], [12], [13], [14]. Most of proposed schemes assume given
node locations (potentially mobile in ad hoc networks), which
is different from the deployment requirement. On the other
hand, for a given deployment, the proposed schemes can be
used so that the lifetime of the deployment can be numerically
evaluated, and thus beneficial to obtain good 2D deployments. Our preliminary work is presented in [15], [16]. We extend the previous work by including studies on miscellaneous
power consumptions and non-uniform data density, as well
as heuristics on planar networks in this paper. III. P ROBLEM D ESCRIPTION It is well-known that in a many-to-one communication network, the sink node is usually the capacity bottleneck.
It is also noticed that the sink node can be the energy
bottleneck. We elaborate the problem in the context of a
linear network. Assume that the sink node is at the end of
the network. Data back-haul nodes closer to the sink node
will have much higher relay load. When evenly spaced, nodes
close to the sink consume more power and die quickly, which
causes the wireless sensor network to be disconnected. In this
case, nodes closer to the sink node limit the lifetime of a
sensor network. There are different approaches to alleviate the
problem, including allocating more energy to nodes closer to
the sink node, placing more nodes, and placing nodes closer
in heavy load areas. Another possibility is to perform load
balancing, i.e., a node with lower traffic load can send data
over longer hops to release the burden of other nodes. We
consider all these possibilities in the paper. Our objective is
to deploy data back-haul nodes in an optimal way such that
the network can cover as large an area as possible given the
number of nodes available and the desired lifetime of the
network. A. System Model In this paper, we assume a perfect medium access control as in [4], [9]. Due to low energy supplies and low duty-
cycles of wireless sensor networks, many research efforts have 3 suggested (localized) TDM-type of access schemes, which is
in accord with our assumption. We use the following communication model in the paper. Let d be the distance between the sender and the receiver, and P be the transmission power. Then the data rate R is proportional to the received signal strength; i.e., R = P/βd γ , where γ is the distance loss factor, 2 ≤ γ ≤ 5, and β is a constant, which can be considered as the signal strength
requirement. This model is widely used in the literature, e.g.,
[17], [18]. We are interested in the case where d is relatively large (e.g., at least on the order of tens of meters). We assume
that background noise is at a constant level, and therefore the
received signal strength infers signal to noise ratio (SNR).
Thus, the energy consumption to convey one unit of data over
distance d is P × 1 R = βd γ . (1) Note that we only consider the transmission power here. Other
power consumptions, such as receiving power and miscella-
neous power at the transmitter, are considered in Section V-A. In practice, due to shadowing and fading phenomena in the transmission environment, the received signal strength is
often random. However, without precise information about
the territory and considering the long-term average, it is
reasonable to assume a direct relationship between distance
and per bit energy consumption [19]. Thus, we use Eq. (1) as
a the model to understand the deployment issue in wireless
sensor networks. The ideal bit-energy model in Eq. (1) can also be extended to a more practical power-goodput model. Basically, we ex-
plore the fact that goodput increases as SINR increases. First,
with the advances in DSP and sensor developments, newer ver-
sions of sensors, especially more expensive and sophisticated
ones, have the capability to adjust data rates based on channel
conditions. In addition, for a given modulation/coding rate,
where SINR is higher, the BER (bit error rate) is lower, and
thus the probability of failure is smaller, which implies higher
goodput and thus lower energy consumption. All results in this
paper can be directly applied to systems with power-goodput
model where per-bit energy consumption is a polynomial
function of distance. Such a model can take into account less-
than-ideal hardware realization and capture a less aggressive
correlation between energy and distance. We should note that the communication model does not impose a constraint on the transmission range. Instead, it is
possible for two far-away nodes to communicate with each
other at the cost of high transmission power. Thus, the model
is general. On the other hand, imposing an additional range
constraint will not change the problem significantly because
communications over a long link is penalized in teams of
power consumption. Furthermore, the proposed greedy algo-
rithm does not rely on the assumption of unlimited com-
munication range, yet yields close-to-optimal performance.
Thus, the impact of allowing large communication range is
negligible. We assume that each unit coverage distance generates c unit of data per unit time. An example where this assumption d i n 1 i i+1 d 0 Fig. 2. A Linear Network holds is a surveillance sensor network where incidents happen
uniformly along the surveillance line (e.g., a border line). B. Problem Formulations Let E be the initial energy of each node and T be the desired lifetime of the sensor network. We are interested in the case of
a relatively large T . Let d i be the distance between the ith the (i+1)th nodes, i = 1, , n−1, and d 0 be the area covered by node 1, as shown in Figure 2. We assume that the node i will collect all the data between nodes (i−1) and i, which is d i−1 c per time unit. Therefore, d i−1 is the coverage distance of node i. Node n is the sink node. We have d i ≤ D for all i, where D is the predefined maximum distance between two nodes.
In the case of a hierarchical network, D limits the distance between a sensor node to its neighboring data back-haul node
(i.e., the cluster head) in the higher hierarchy. We first introduce Problem IDEAL. In this problem, we assume that energy can be allocated arbitrarily among nodes.
In other words, we only have a total energy constraint. Given
(n − 1) nodes, the total initial energy is (n − 1)E. (Note that
node n is the sink node.) This is an idealized case, and its result serves as a benchmark of the system. When energy can
be allocated arbitrarily among nodes, the network dies only
when there is absolutely no energy left in any nodes. Thus,
the definition of the lifetime of such a network is very general.
We will show later that the performance of the proposed
scheme under more realistic assumption is close to that in
the benchmark case, and thus the effect of arbitrary power
allocation is limited. When energy can be allocated arbitrarily among nodes, routing in a linear network is greatly simplified. A necessary
condition for optimality is that node i should relay all data to node i + 1, its nearest neighbor toward the destination because (a + b) γ > a γ + b γ , where a, b > 0 and γ > 1. In other words, it consumes more energy to transmit data over longer hops
than over multiple shorter hops. This holds when energy can
be arbitrarily allocated among nodes. The objective of Problem IDEAL is to find a deployment scheme to cover the maximum distance given the number
of data back-haul nodes and the lifetime requirement. The
problem is formulated as maxmize d n−1 i=0 d i (2) subject to β n−2 i=0 cd i n−1 k=i+1 d γ
k ≤ (n − 1)E T (3) 0 ≤ d i ≤ D, i = 0, , n − 1. (4) In Eq. (2), cd i is the amount of data collected by node (i + 1) in one time unit and it is relayed to node (i + 2), ..., and node 4 (n − 1), to node n. Furthermore, (n − 1)E is the total initial
energy and T is the required life time, and thus (n − 1)E/T is the maximum amount of energy consumed per time unit by
all nodes. Therefore, Eq. (3) is the energy constraint. Eq. (4)
is the maximum distance constraint. We note that it can take
several hops for a packet (bit) to be forwarded to the sink,
and thus the energy consumption could happen at different
time periods. The problem formulation assumes steady state.
This is reasonable in a long-lived sensor network, where the
time period to forward a packet, on the order of seconds, is
much smaller than the life-time of the network, on the order
of months or longer. Problem IDEAL serves as a benchmark
because of its arbitrary energy allocation assumption and the
corresponding definition of lifetime. A similar problem can be
formulated to introduce individual energy constraints on each
node. We refer interested readers to [16] for details. We note that Problem IDEAL is not a convex optimization problem because the domain is not a convex set. However,
because the number of variables is relatively small, we use the
fconmin function in matlab to obtain the solution numerically.
Next, we present a heuristic deployment scheme that achieves
close-to-optimal performance and enables analysis. IV. G REEDY D EPLOYMENT S CHEME Problem IDEAL serves as a benchmark because of its arbitrary energy allocation assumption and the corresponding
definition of lifetime. However, such a heterogeneous energy
allocation may be inconvenient and impractical in production
and deployment. In this section, we present a greedy de-
ployment scheme where each node has an individual (usually
homogeneous) energy constraint. The intuition of the greedy
scheme is as follows: a node relays data for all nodes that are
further away from the sink. It tries to push its data as far away
as possible given the lifetime and energy constraints, which
determines the distance to its nearest neighbor toward the sink. To elaborate, the total traffic load of node i is c i−1
j=0 d i . Let x i be the pushing distance; i.e., the maximum distance that node i can push this amount of data given the energy and lifetime constraints. We have β(c i−1
j=0 d j )x γ
i = E
T . The algorithm is greedy in the sense a node tries to push its data
as far away as possible under the constraints. Furthermore,
node i does not directly send data to node j, where j ≥ i + 2, because it consumes more energy. Because of the maximum
distance constraint, we have d i = min{D, x i }, where d i is the distance between nodes i and i + 1. Therefore, the greedy algorithm can be stated as: 



 d 0 = D d i = min D, E βT c P i−1
j=0 d j 1 γ , i = 1, , n − 1. (5) In the greedy algorithm, d i can be calculated iteratively. We note that d i is monotonically decreasing — a node with heavier relay load is compensated through a smaller transmission
distance. The greedy algorithm can be easily adopted to more
general cases. For example, if each node has heterogeneous
initial power constraints, E i , we can replace E by E i in 0 10 20 30 40 50 0.4 0.5 0.6 0.7 0.8 0.9 1 node index d i opt., D n =27.4395 greedy, D n =27.4392 Fig. 3. Compare the locations of data back-haul nodes in the greedy scheme
with the numerical solution of Problem IDEAL. Eq. (5). If data density is non-uniform, we can replace
c i−1
j=0 d j by the aggregated load from distance 0 to i−1
j=0 d j . A. Numerical Comparison We compare the performance of the greedy scheme with that of Problem IDEAL. Figure 3 compares the numerical solution
of Problem IDEAL and the performance of the greedy one.
Problem IDEAL serves as a benchmark because of its arbitrary
energy allocation assumption and the corresponding general
definition of life time. Define a constant C = E/(cβT ). When D ≥ C (1/(γ+1)) , we have x i ≤ D for all i. This is the case where the required lifetime is long and/or the initial
energy in each data back-haul node is low, which is of our
primary interest. In the numerical result, C = 1, D = 1, and n = 50. We set γ = 4 for all numerical results in this paper unless otherwise specified. In Figure 3, the x-axis is
the index of nodes and the y-axis is d i , which is the distance between two consecutive nodes. In the legend, D n is the total coverage distance given n nodes. We notice that the difference in performance of the greedy algorithm with the optimal one
is very small. Figure 4 compares the energy allocation of the
two schemes. In the greedy scheme, all nodes consume the
same amount of energy by definition in Eq. (5). In the optimal
solution of Problem IDEAL, we notice that the leftmost nodes
have slightly higher energy allocations, which infers to the
slightly larger d i in Figure 3. Figure 5 compares the coverage length of the greedy al- gorithm with the optimal solution of the Problem IDEAL
where D = 1 and C = 0.01, 1, 10, respectively. (Note that smaller values of C are of more interests since they correspond to long network lifetime.) It includes both cases
where D ≥ C (1/(γ+1)) and D < C (1/(γ+1)) . The x-axis is the number of nodes and y-axis is the total distance covered. For
each fixed C, we can see that the performance of the greedy algorithm is almost indistinguishable from that of the optimal
scheme with arbitrary energy allocations. Figure 6 shows the
results for γ = 2. In summary, the advantage of allowing arbitrary energy allocation is negligible; the greedy algorithm where each node
has the same initial energy performs very well. Its coverage 5 10 20 30 40 0 0.5 1 1.5 node index energy opt.
greedy Fig. 4. Compare the power allocation among data back-haul nodes in the greedy scheme with the numerical solution of Problem IDEAL. 0 10 20 30 40 50 0 10 20 30 40 50 Number of nodes Total distance ← C=0.01 ← C=1 ← C=10 greedy
optimal Fig. 5. Compare the coverage distance of the greedy scheme with the numerical solution of Problem IDEAL when γ = 4. 5 10 15 20 25 30 35 40 5 10 15 20 25 30 Number of nodes Total distance ← C=0.01 ← C=1 ← C=10 greedy
optimal Fig. 6. Compare the coverage distance of the greedy scheme with the numerical solution of Problem IDEAL when γ = 2. distance is almost equal to that of the optimal deployment.
Thus, it justifies the greedy deployment of homogeneous data
back-haul nodes. B. Performance Analysis Because the greedy scheme achieves close to optimal per- formance, its closed-form analysis can provide insight into the
design of wireless data back-haul networks, which is one of the
reasons to introduce the greedy algorithm. In this section, we
obtain a closed-form approximation for the greedy algorithm.
Let D i = i−1
k=0 d k , i.e., D i is the total length covered by nodes 0 to (i − 1), which can be calculated iteratively using Eq. (5). We claim a closed-form approximation of D i as follows: D i ≈ C 1 γ+1 γ + 1 γ i γ γ+1 , i = 1, , n, (6) To justify our claim, we only need to show that the above
equation satisfies Eq. (5) iteratively. Assume Eq. (6) hold for
k = 0, 1, , i − 1. By Eq. (5), we have d k = E cβT i−1
j=0 d j 1 γ = C D k 1 γ ≈ C 1 γ+1 γ (γ + 1)k 1 γ+1 , k = 1, , i − 1. (7) In the above equation, the first equality holds by definition
(Eq. (5)) and the second by Eq. (6). Then, D i = i−1 k=1 d k + d 0 ≈ i 1 C 1 γ+1 γ (γ + 1)x 1 γ+1 dx + d 0 ≈ C 1 γ+1 γ + 1 γ i γ γ+1 (8) Thus, Eq. (6) is an approximation of the total distance covered
by i nodes in the greedy algorithm. In Eq. (8), approximations occur when we replace a summation with an integral, and
when the impact of d 0 (i.e., the boundary effect) is ignored. The approximation is very close, especially for relatively large
n (e.g., n ≥ 5). We compare the numerical result to a network
up to 10000 nodes, for 0.01 ≤ C ≤ 10, and observe that the maximum discrepancy between the approximation and the
actual value is smaller than 0.2% for all n, where 5 ≤ n ≤ 10000. When n is reasonably large, the approximation of
summation by integral is relatively small. This closed-form approximation in Eq. (6) reveals the relationship among the design parameters, n, the number of data back-haul nodes needed, T , the life time of the data back-haul network, L, the total distance that the network can covered ( L = D n when there are n data back-haul nodes). We have L γ+1 = E T cβ γ + 1 γ n γ . (9) Having any two design parameters fixed, we can obtain the
third. For example, given T , n ∝ L γ+1 γ , which indicates a super-linear increase in the number of node required with 6 respect to the coverage distance. Given L, n ∝ T 1 γ is sub- linear. In addition, the marginal effect of adding one more
node is sub-linear. Suppose that γ = 4 and all other parameters are fixed. To double the lifetime of a sensor network, we only
need 19% more data back-haul nodes. To double the length of the sensor network, we need 138% more nodes. Finally, we compare the greedy scheme with the uniform deployment scheme. In the uniform deployment scheme, nodes
are evenly placed along the line. Assume the routing decision
is to relay data to the nearest node toward the sink node.
Because node n − 1 is the closest to the sink node and has the most heavy relay load, it exhausts its energy first. Thus,
its lifetime limits the lifetime of the network. Our analysis
show that given n, E and T , the greedy scheme can cover ((γ + 1)/γ) γ/(γ+1) larger in distance than that of the uniform deployment [16]. For example, the coverage distance of our
greedy scheme is 24% and 19% longer than the uniform one when γ = 3 and γ = 4, respectively. Alternatively, the lifetime of the greedy deployment is (1 + 1/γ) γ times of that of the uniform deployment, which is 237% and 244% when γ = 3 and γ = 4, respectively. V. D ISCUSSIONS A. Miscellaneous Power Consumptions In a wireless device, power consumption is multi-facet. It consumes energy to keep the circuit awake, to receive and
process signals, etc. Such power consumption is usually not
negligible in practice. For instance, the power consumption
for reception is usually of the same order as that for transmis-
sion. In this section, we consider such miscellaneous power
consumptions and their impact on deployment. To conserve energy in a wireless device, the device should be put into sleep mode when no transmission/reception occurs.
We assume that the energy consumption in the sleep mode is
negligible. We assume perfect synchronization, and thus the
transmitter and the receiver are awake only when transmission
occurs. We also assume that data back-haul nodes do not
perform sensing or the power consumption of infrequent
sensing/event-driven sensing is negligible. Let P a be the amount of additional power consumed by the transmitter in order to keep the circuit “awake”, P t be the transmission power, i.e., the power emitted by the antenna,
and P max be the maximum transmission power allowed by the power amplifier, where 0 ≤ P t ≤ P max . Thus, P t + P a is the total power consumed by the transmitter. Let P r be the total power consumed by the receiver, including the power
consumed by a circuit, to receive signals, and to perform
signal processing. Given the transmission power P t and the SNR requirement β, if the distance between the transmitter and the receiver is d, then the achievable data transmission rate R is R = P t /(βd γ ). The total energy consumption by the transmitter to send one bit over distance d is E t = 1 R (P t + P a ) = βd γ P t (P t + P a ) ≥ βd γ P max + P a P max ∆ = E ∗ t , (10) where the inequality holds when P t ≤ P max , and E ∗ t is the minimum amount of energy consumed to transmit a bit. The
energy consumption by the receiver for the bit is E r = 1 R (P r ) = βd γ P t (P r ) ≥ βd γ P r P max , ∆ = E ∗ r . (11) Again, the last inequality holds when P t ≤ P max , and E ∗ r is the minimum amount of energy consumed to receive one bit.
Thus, it saves energy to transmit with the maximum power
at the highest data rate instead of lower power at lower data
rate because this mode takes the smallest amount of time and
thus reduces the miscellaneous power consumption at both the
transmitter and the receiver. This accords to current research
findings [20]. We assume from now on that transmitting at the
maximum power is the transmission mode used. The challenge
remains to determine the deployment and routing strategy. Let us consider the tradeoff between long and short hops. Without loss of generality (WLOG), we compare a long hop
of distance l d versus two short hops with distances s 1 and s 2 , where l d = s 1 + s 2 . Assume all nodes transmit at P max as discussed earlier. The total energy consumption to move 1 bit
using the long hop of distance l d is E long = 1 R (P max + P a + P r ) = βl γ
d P max + P a + P r P max . Using two short hops, the energy consumption per bit is E short = β(d 1 ) γ P max + P a + P r P max +β(d 2 ) γ P max + P a + P r P max . For γ > 1, we have (l d ) γ = (s 1 + s 2 ) γ ≥ s γ
1 + s γ
2 , and thus E long ≥ E short . The intuition is that the total awake time for two short hops is shorter than that of a long hop when γ > 1 and the rate is proportional to the received SNR. Note that
the important factor is that the (maximum) rate decays super-
linearly with respect to distance, i.e., γ > 1. Thus, the time to transmit and receive one bit grows super-linearly over distance
and so does the total power consumption. In a linear network,
long hops can always be broken into two or more shorter hops
iteratively, and thus short hops are preferred under the above
stated assumption. Compared to the case where we only take the transmission power into account, we notice that the energy consumption
to transmit and receive one bit is scaled by a constant factor
(P max + P a + P r )/P max . We define ρ = P max P max + P a + P r as the energy coefficient. In other words, ρ is the ratio of the energy that is used for signal transmission to the total
energy consumption. A node consumes 1/ρ times of energy to handle one bit compared to the transmission-power only
case. Because a node (except the sink node) receives and
transmits the same amount of data, this is equivalent to scaling
the original energy by a factor of ρ. Note we make the assumption that a data back-haul node receives data from sensors in the lower hierarchy and does not
perform sensing itself. Furthermore, we assume that a node
consumes the same amount of energy to receive one unit of
data from a neighboring data back-haul node and from sensors 7 in the lower hierarchy. This assumption may not always be true
because a sensor node in the lower hierarchy may have smaller
transmission power and consumes longer time to transmit one
bit to data back-haul nodes. However, for nodes with a large
relay load, the difference is small. The larger the value of i, the better the approximation. The difference is more significant
for nodes far away from the sink node. In summary, the effect of miscellaneous power consumption can be well modeled by a scaling factor ρ. It may seem counterintuitive that smaller hops are desirable even when
miscellaneous power consumptions are taken into account.
The reason is that when nodes are closer, the reliable data
rate is higher, the aggregated time for transmission/reception
is shorter, the miscellaneous power consumption is lower, and
thus the total energy consumption is lower. B. Non-uniform Data Density In sensor network applications, data density may vary over locations. For instance, different portions of a road may
experience different volumes of traffic and intersections are
in general busier. To model this phenomena, let c(x) be the density at location x, where x ≥ 0. The sink node is located at the rightmost location. The greedy algorithm can be extended
to the case with non-uniform data densities along the coverage
area as follows: d i = min D, x i : βl(i)x γ
i = E T , (12) where l(i) is the load for node i to forward; i.e., l(i) = P i−1
j=0 d j 0 c(x)dx. In words, in the greedy algorithm, node i tries to push its load l(i) as far as possible within the constraint D, which reflects the same intuition as in Eq. (5). Next, we show numerical results in the case of non-uniform data density. We consider a linear network of length 10000(m). The data density along the linear network is not uniform, as
shown in Figures 7 and 8, respectively. In both figures, the x-
axis represents location and y-axis shows the variation in data
density. Figure 7 represents a linear network with location-
varying data density, e.g., a border line with different volumes
of traffic. Figure 8 represents a network with bursty data traffic,
e.g., a highway with exits. We assume that the data density
profile does not change over time and can be estimated when
the sensor network is deployed. When the lifetime of the
network is relatively long, short-term variation (e.g., rush-hour
vs. mid-night) is smoothed. In addition, to evaluate the impact
of estimation errors of data density on the network lifetime,
a zero-mean Gaussian estimation error is added to the actual
data density profile to create a noisy estimate, as shown by
the lower plot in each figure. The standard deviation of the
Gaussian-distributed error is 20 % of the actual value of the load, which we consider as moderate estimation errors. We compare the performance of the greedy scheme with perfect knowledge of the data density profile, the greedy
scheme using noisy estimate, uniform deployment, and ran-
dom deployment. We first use the greedy algorithm in Eq. (12)
to calculate the number of data back-haul nodes needed to
monitor the linear network, denoted as n. The greedy algo- rithm is then used based on the noisy estimated data density 0 2000 4000 6000 8000 10000 0 2 4 6 Location (x) Density 0 2000 4000 6000 8000 10000 0 2 4 6 8 Location (x) Estimate Fig. 7. Nonuniform data density profile. 0 2000 4000 6000 8000 10000 0 5 10 15 Location (x) Density 0 2000 4000 6000 8000 10000 0 5 10 15 20 Location (x) Estimate Fig. 8. Bursty data density profile. (the lower plot in each profile). In the uniform deployment,
n nodes are evenly distributed along the linear network. In
the random deployment, n nodes are randomly and uniformly distributed along the line. In all deployments, each node
forwards data to its nearest neighbor toward the sink node,
which is at the end of the linear network. The network is
considered dead when the first node runs out of energy. Figure 9 compares the greedy deployments with and with- out estimation errors on the data density. The x-axis is the
node index, and y-axis represents the distance between two
consecutive nodes. The two curves of the greedy deployment
with and without estimation errors (noted as “greedy” and
“w. error” in the legend) are almost indistinguishable. To
achieve the desired lifetime, the greedy deployment requires
243 nodes with perfect density information. In the presence of
estimation errors, 244 nodes are required and the deployment
achieves 99 % of the desired lifetime. The preliminary result shows that independent estimation errors have little impact on
the performance of the greedy deployment. This is due to the
fact that the aggregated load at each node is more important
than the density at a location. Because estimation errors are
independent, the aggregated estimation error at a particular
location is small compared to the total aggregated load, due
to the central limit theorem, for moderate or large values of 8 0 50 100 150 200 250 300 20 30 40 50 60 70 80 90 100 Node index Distance greedy
w. error
unif Fig. 9. Compare the deployment of the greedy algorithm with and without estimation errors. i. Therefore, the impact of independent estimation errors is
small. On the other hand, if estimation errors are correlated,
say a large portion of the network is under-estimated, the
impact will be larger. The impact of such correlated errors
needs to be further investigated. As a reference, we plot the curve of a greedy deployment where the data density is uniform with the same average
density (average over the whole linear network), which is
noted as “unif” in the legend. This deployment requires 256
nodes to achieve the desired lifetime. The difference between
the uniform and non-uniform density cases is most significant
when a low data density exists and thus the distance between
two consecutive users are larger (e.g., nodes 20-50). In the uniform deployment, n (n = 243) nodes are evenly spaced in the linear network. The lifetime of the uniform
deployment is 34% of the desired lifetime. This is in ac- cordance with the result presented in Section IV. In the
random deployment, we run 100,000 independent realizations,
where in each realization, n (n = 243) nodes are randomly and uniformly deployed. The average lifetime of the random
deployment is less than 1% of the desired lifetime. This is due to the randomness in the deployment of nodes; i.e, there exists
consecutive nodes with a large gap with a high probability.
The larger the network, the worse the lifetime of the random
network in comparison. This justifies strategic deployment of
nodes and is in accord with theoretical results on the coverage
and connectivity properties of randomly deployed networks
(e.g., [21]). We also note that nodes closer to the sink are
more likely to fail due to their heavier loads. Bursty data density is also considered, as shown in Figure 8. Similar comparison is shown in Figure 10. In this case,
the estimation error costs the greedy algorithm no additional
node and 2 % decrease in the desired lifetime. The uniform deployment achieves 47 % percent of the desired lifetime and the random deployment achieves less than 1 %. While we consider the estimation error on data density above, another type of error occurs on deployment due to
inaccurate geographic measurements or physical constraints.
We expect the greedy deployment scheme to be robust against
small independent deployment errors. Let d i be the desired 0 100 200 300 400 20 30 40 50 60 70 80 90 100 Node index Distance greedy
w. error
unif Fig. 10. Compare the deployment of the greedy algorithm with and without estimation errors. deployment and d ′
i be the actual deployment with errors. The lifetime of the actual deployment is η times of the desired one, where η = min i d γ
i i
k=0 d k (d ′
i ) γ i
k=0 d ′
k . However, as n increases, the performance deteriorates because it is bounded by the worst-case scenario. We hope to study the
issue further in the future. C. Planar Networks The deployment in planar networks presents great chal- lenges, mainly due to the large search space of decision
variables. For instance, even with the assumption of arbitrary
power allocation, we cannot reduce the search space of routing
possibilities much due to possible triangular routes. With x data back-haul nodes, we have 2x + x 2 continuous variables to optimize. In addition, the coverage area of each data back-
haul node needs to be determined so that the total transmission
power is minimized while it is guaranteed that all sensors in
the lower hierarchy can be connected to at least one back-haul
node. In the following, we present two heuristics for the planar
deployment. Consider a square area where the sink is located at the right upper corner. A square-shaped deployment is shown in
Figure 11. There are n 2 nodes and node (n, n) is the sink. The deployment is symmetric: d i is the distance between nodes (i, j) and (i + 1, j), and the distance between (j, i) and (j, i+1). Each node collects data of the left-lower rectangular.
Assume only total energy constraint is considered. When
γ ≥ 2, to send data from (i, j) to (i + 1, j + 1), it is more
efficient to send to node (i, j + 1) and then to (i + 1, j + 1) because d 2 i + d 2 j γ ≥ (d γ
i + d γ
j ). In this case, routing is simple — a packet is routed either a
right or upper neighbor until it reaches the sink. Formally, the 9 0 1 2 3 4 0 0.5 1 1.5 2 2.5 3 3.5 4 4.5 sink (k,j) d k d j d 0 d 1 d 2 d 0 d 1 d 2 Fig. 11. Square-shape 2D deployment with total energy constraints. problem is formulated as maxmize d n−1 i=0 d i (13) subject to n−1 i=0 n−1 j=0 cd i d j β 
 n−1 k=i+1 d γ
k + n−1 k=j+1 d γ
k 
 ≤ (n 2 − 1)E T (14) 0 ≤ d i ≤ D, i = 0, , n − 1. (15) Eq. (14) is the total energy constraint, where cd i d j is the vol- ume of data collected by node (i+1, j+1) and β( n−1
k=i+1 d γ
k + n−1
k=j+1 d γ
k ) is the energy to relay one bit to the sink from this node. Note that Eq. (13) is not a general 2D deployment
problem because we limit the degree of freedom in allocating
nodes. An alternative is the strip deployment, shown in Figure 12. The whole area is divided into a number of strips, where the
result in the linear network can be applied in each strip. In
the figure, the greedy algorithm is used, shown as circles. At
the right edge, a dense linear network is deployed vertically
to pull data to the sink node, shown by the hexagon nodes.
The strip deployment is similar to the proposed in [9], where
linear approaches are extended to planar networks by dividing
a planar network as strips or pieces of pies. We compare the performance of the two schemes. For a fixed n, we solve Eq. (13) numerically to determine the maximum coverage given n 2 nodes. The perimeter of the area is denoted by L. We then run the greedy algorithm to determine how many nodes are needed to cover the same
area. The number of horizontal rows in the strip deployment
is determined by m r = ⌈L/D⌉ because the maximum width of a strip is D. The width of each strip is w r = L/m r . The load for the ith node in the strip is cw r i−1
k=0 d k . Eq. (5) can then be used to determine the distance d i . The vertical line at the right edge is determined with data density cw r L per strip. In Figure 13, we show the perimeter of the coverage area as 0 1 2 3 4 0 0.5 1 1.5 2 2.5 3 3.5 4 4.5 sink Fig. 12. Deployment of data back-haul nodes in the strip mode. 4 6 8 10 12 14 2 4 6 8 10 12 14 n Perimeter (L) ← C=0.01 ← C=1 ← C=10 Fig. 13. Coverage area with given number of nodes in the square-shape deployment. The x-axis is n, where n ∗ n is the total number of nodes. a function of n under different values of C. In Figure 14, we compare the number of nodes needed to cover the same area
by the two schemes. In the figure, the x-axis represents the
square deployment where n 2 is the number of nodes needed, the y-axis represents the strip deployment where n 2 strip is the total number of nodes needed. The dashed line is the diagonal.
The square deployment is better if the curve is above the
diagonal line (e.g., C = 10), and the strip one is better if the curve is below the line (e.g., C = 0.01). We note that square deployment is preferred when C is large, and strip one preferred when C is small. Small C implies small energy budget per bit (e.g., long T or high c). In this case, it is more efficient to aggregate the data to a few heavy duty nodes
with short transmission distances, as the dense vertical line in
the strip mode. This implies that some kind of heavy-duty
backbone may be desirable in optimal 2D deployments. In general, deployment of large planar sensor network is of great challenge and requires further study. We hope that
the strip and square deployments can shred lights on general
2D deployments. Other potential solutions include deploying
multiple sink nodes, exploiting mobile sinks, and decreasing
data dimension (e.g., the maximum temperature instead of 10 5 10 15 20 4 6 8 10 12 14 16 18 20 n n strip ← C=0.01 ← C=1 ← C=10 Fig. 14. Compare the number of nodes needed in the square-shape deployment and strip deployment. The x-axis is n strip , where n 2 strip is the total number of nodes. temperature of all nodes). VI. C ONCLUSION In this paper, we study the deployment issue for data back- hauling in wireless sensor networks. Determination of an
optimal deployment scheme involves location management,
routing, and power management. We formulate a general de-
ployment optimization problem in a linear network and obtain
numerical solutions. We then propose a greedy algorithm
that performs close to optimal compared to the benchmark
case. The closed-form analysis of the performance of the
greedy algorithm revealed the relationship among the design
parameters, i.e., the required lifetime, the number of data
back-haul nodes, and the length of a linear network to be
covered. We expect such relationship holds in the case of
optimal deployments because the greedy scheme depicts close-
to-optimal performance. We study the effect of miscellaneous power consumptions, including circuit power consumption and receiving power
consumption. We also study the cases of non-uniform data
density and bursty data pattern. The greedy algorithm can
be easily adapted to both cases with significant better per-
formance compared to that of homogeneous and random
deployment schemes. We present two heuristic extensions to
planar networks. Future study include planar networks, and the
impacts of realistic data aggregation models and deployment
errors. R EFERENCES [1] R. SZewczyk, A. Mainwaring, J. Anderson, and D. Culler, “An analysis of a large scale habit monitoring application,” in ACM Sensys, Baltimore,
MD, 2004, ACM. [2] M. Bhardwaj and A. P. Chandrakasan, “Bounding the lifetime of sensor networks via optimal role assignments,” in IEEE INFOCOM, 2002,
vol. 3. [3] M. Bhardwaj, T. Garnett, and A. P. Chandrakasan, “Upper bounds on the lifetime of sensor networks,” in IEEE International Conference on
Communications, 2001, vol. 3. [4] M. Perillo, Z. Cheng, and W. Heinzelman, “On the problem of unbalanced load distribution in wireless sensor networks,” in IEEE Globecom 2004, Dallas, TX, Nov. 2004, IEEE. [5] D. Blough and P. Santi, “Investigating upper bounds on network lifetime extension for cell-based energy conservation techniques in stationary ad
hoc networks,” 2002. [6] F. Ye, H. Luo, J. Cheng, S. Lu, and L. Zhang, “A two-tier data dissemination model for large-scale wireless sensor networks,” in ACM
MOBICOM 2002, 2002. [7] J. Pan, Y. T. Hou, L. Cai, Y. Shi, and S. X. Shen, “Topology control for wireless video surveillance networks,” in Proceedings of ACM Mobicom
2003. 2003, ACM. [8] Y. T. Hou, Y. Shi, H. Sherali, and S. Midkiff, “On energy provisioning and relay node placement for wireless sensor networks,” IEEE TRANS-
ACTIONS ON WIRELESS COMMUNICATIONS, vol. 4, no. 5, 2005. [9] D. Ganesan, R. Cristescu, and B. Beferull-Lozano, “Power-efficient sensor placement and transmission structure for data gathering under
distortion constraints,” in IPSN 2004, 2004. [10] Jae-Hwan Chang and Leandros Tassiulas, “Maximum lifetime routing in wireless sensor networks,” IEEE/ACM Trans. Netw., vol. 12, no. 4,
pp. 609–619, 2004. [11] Honghai Zhang and Jennifer C. Hou, “On the upper bound of α-lifetime for large sensor networks,” ACM Trans. Sen. Netw., vol. 1, no. 2, pp.
272–300, 2005. [12] A. Sankar and Zhen Liu, “Maximum lifetime routing in wireless ad-hoc networks,” in INFOCOM 2004, 2004. [13] C.-K. Toh, “Maximum battery life routing to support ubiquitous mobile computingin wireless ad hoc networks,” IEEE Communications
Magazine, vol. 39, no. 6, pp. 138–147, 2001. [14] Cunqing Hua and Tak-Shing Yum, “Optimal routing for maximizing lifetime of wireless sensor networks,” in INFOCOm 2005 (poster). [15] P. Cheng, C. N. Chuah, and X. Liu, “Energy-aware node placement in wireless sensor networks,” in IEEE Globecom, 2004. [16] X. Liu and P. Mohapatra, “On the deployment of wireless sensor nodes,” in Third International Workshop on Measurement, Modelling, and Per-
formance Analysis of Wireless Sensor Networks, in conjunction with Mo-
biQuitous 2005,. 2005, ACM, www.cs.ucdavis.edu/∼liu/research.html. [17] Rene L. Cruz and Arvind V. Santhanam, “Optimal routing, link scheduling and power control in multi-hop wireless networks,” in IEEE
INFOCOM, 2003. [18] J.-Y. Le Boudec, R. Merz, B. Radunovic, and J. Widmer, “DCCMAC: a decentralized mac protocol for 802.15.4a-like UWB mobile ad-hoc
networks based on dynamic channel coding,” in IEEE Broadnets, 2004. [19] Shiann-Tsong Sheu, Jenhui Chen, Hsueh-Wen Tseng, and Hsien-Ta Chiang, “A safe multiple access-rates transmission (smart) scheme for ieee 802.11 wireless networks,” in AINA ’03: Proceedings of the
17th International Conference on Advanced Information Networking
and Applications, Washington, DC, USA, 2003, p. 172, IEEE Computer
Society. [20] T. van Dam and K. Langendoen, “An adaptive energy-efficient MAC protocol for wireless sensor networks,” in Proceedings of the First International Conference on Embedded Networked Sensor Systems.
2003, ACM. [21] T. K. Philips, S. S. Panwar, and A. N. Tantawi, “Connectivity properties of a packet radio network model,” IEEE Transactions on Information
Theory, vol. 35, no. 5, pp. 1044 –1047, 1989.

Comments