Wireless Sensor Network, 2010, 2, 504-511
doi:10.4236/wsn.2010.27062 Published Online July 2010 (http://www.SciRP.org/journal/wsn)
Copyright © 2010 SciRes. WSN
Packet Compression Ratio Dependent Spanning Tree for
Changjin Suh, Jisoo Shin
Department of Computing, Soongsil University, Seoul, Korea
E-mail: cjsuh@ssu.ac.kr, jsshin@netwarking.com
Received April 12, 2010; revised May 4, 2010; accepted May 6, 2010
A convergecast is a popular routing in sensor networks. It periodically forwards collected data at every sen-
sor node along a configured routing path to the outside of a sensor network via the base station (BS). To ex-
tend the lifetime of energy-limited sensor networks, many previous researches proposed schemes for data
compression. However, few researches investigated the relation between packet compression ratio and span-
ning trees. We propose packet Compression ratio dependent Spanning Tree (CST) which can provide effective
routing paths in terms of the tree length for all ranges of compression ratio f. CST is equivalent to the Short-
est Path spanning Tree (SPT) which is optimum in the case of no-compression (f = 0) and is equivalent to
the Minimum Spanning Tree (MST) in the case of full-compression (f = 1). CST outperforms SPT and MST
for any range of f (0 < f < 1). Through simulation we show CST provides shorter paths than MST and SPT in
terms of the tree length by 34.1% and 7.8% respectively. We confirm CST is very useful in convergecasts.
Keywords: Packet Compression, Convergecast, CST, Spanning Tree, Sensor Network
1. Introduction
A sensor network is a distributed wireless network to
monitor various conditions of a remote area through an
autonomously configured routing path [1-4]. This paper
studies packet compression-dependent convergecasts. A
convergecast is a type of communication in the reverse
direction of a broadcast in which all collected packets are
forwarded to a single control node called a base station
(BS) [2,5]. To perform convergecast effectively, each
node forwards its packets to its neighbor once and only
once. If we trace these packet routes, we can build up a
spanning tree. A convergecast is very popular in sensor
networks [3,4]. It is common in sensor networks that
intermediate nodes try to reduce packet size during forw-
arding. This is called packet compression. Most previous
researches focused on no-compression or full-compre-
ssion cases for simplicity.
The compression ratio f is represented by the relatively
decreased packet lengths over all added packet lengths to
a unit length at each sensor node [2,6,7]. At no-com-
pression (f = 0), a node relays all collected packets with-
out reducing them. At full-compression (f = 1), a node
generates an x-bit packet after merging many received
x-bit packets and an x-bit packet generated at the node.
The Shortest Path spanning Trees (SPTs) and the Min-
imum Spanning Trees (MSTs) are useful for converge-
casts to save energy because transmission energy typi-
cally proportional to the square of distance. SPT mini-
mizes the length of paths from the root to all nodes, and
MST minimizes the sum of lengths of a set of links
which are used to connect all nodes. In terms of packet
compression, SPT and MST are optimum in total trans-
mission energy for a convergecast in no-compression and
full-compression cases respectively.
There are only a few previous researches about packet
compression-related spanning trees. Upadhyayula et al.
[7] tried to find a spanning tree that minimizes energy
and ‘time’ for a convergecast. Time indicates the number
of time slots required for a convergecast in a wireless
TDMA environment. To achieve less time, the paper
explains how to configure spanning trees and suggests an
algorithm for building them. The proposed algorithm
tends to prefer balanced trees.
Luo et al. proposed Minimum Fusion Steiner Tree
(MFST) [8] and Binary Fusion Steiner Tree (BFST) [9].
Both assume that sensor nodes must perform complex
calculations spending energy for packet compression.
They tried to minimize the sum of transmission energy
and packet compression energy. In MFST, packet com-
pression occurs at every intermediate node. In reality,
Copyright © 2010 SciRes. WSN
packet compression is not always beneficial to energy
saving if a compression ratio is low or the energy for
packet compression is large. BFST proposes a feasibility
test of packet compression. If a node passes the test, it
compresses packets and transmits the reduced packet. If
it fails, it sends packets without packet compression.
These researches focused on the packet compression side,
leaving transmission oversimplified. Spanning trees were
not their main interest. They assumed all transmissions
spend a unit of energy regardless of transmission dis-
tance. We could not find any packet compression related
paper that investigates the interaction between spanning
trees and packet compression ratio.
We propose three ideas in this paper. The first one is a
packet compression-related metric in defining the tree
lengths. Second, we propose a one-time compression
model that does not allow infinitely repeated packet
compression. The third idea is a packet Compression
ratio dependent Spanning Tree (CST) which builds a
spanning tree using the one-time compression model.
This new type of tree bridges the gap between SPT and
MST. CST can be briefly described as a mixture of f
times MST and (1 f ) times SPT. CST is equivalent to
SPT at no-compression and MST at full-compression.
This paper consists of the following sections. Section
2 defines a new distance that includes SPT, MST and
CST, and merges them into a unified tree and defines our
problem. Section 3 describes how to build CST. In Sec-
tion 4, we give simulation results and compare CST with
SPT and MST in terms of tree length. In Section 5, we
reach the conclusions.
2. Definition of Distance and Our Problem
This section defines distance rules and our problem using
the defined terminologies. Subsection 2.1 introduces three
metrics that define distances including our proposed met-
ric d(·) which is a function of the compression ratio f. If
we use d(·), no-compression (f = 0) and full-compression
(f = 1) network problems are automatically solved be-
cause they are incidences of the generic f-compression
network problem (10  f). Subsection 2.2 defines this
paper’s main problem, a unified CST problem using d(·)
which covers SPT, MST and CST problems.
2.1. Definition of Distance
We first define several terms. We represent the link from
a node i to a node j by l(i, j) and the link cost by C(i, j).
The kth ancestor node of a node q is defined as pk(q).
p1(q) is the parent node of q, and p0(q) is q itself. The
root node is BS for a convergecast and is represented by
R. For convenience we assume all ancestor nodes of R
are also R, providing:
,)( RRpk
,....2,1,0k (1)
The distance of a node q is defined as the shortest path
from q to R along the configured spanning tree. We use
three metrics (distance rules) to define distance: 1) nor-
mal distance δ(·), 2) constant compression distance λ(·),
and 3) our one-time compression distance d(·). Later
definitions commonly assume q is the kth (k = 1, 2,)
descendent node from R.
δ(·) defined in (2) simply adds costs of all active links
to R without considering packet compression. Active
links are the set of links that constitutes the routing path.
We define the constant compression distance as λ(·)
which is the most general compression model. Upa-
dhyayula et al. [7] use λ(·). This rule assumes packets are
compressed at a constant ratio f in all intermediate nodes.
We formulate λ(·) as
The last distance d(·) we propose is defined as
In d(q), packets are compressed with the compression
ratio f only once at the parent node along the path to R.
Figure 1 shows the sum of packet lengths transmitted at
each link l(i, j). A node q generates an mq-byte packet
and forwards it to R along the spanning tree. Although
this paper assumes the lengths of the generated packets
are identical, we use mq for clear understanding. Note all
packet lengths can be represented by the linear equation
of f : (aij· f +bij). This property is utilized to calculate the
best estimate compression ratio f from statistics in the
We can use any defined metric in defining the tree
length L(TS) of a spanning tree TS. This paper chooses
only d(·) because d(·) includes δ(·) and λ(·). L(TS) in (5) is
defined as the total distance from every node q to the
Figure 1. An example of one-time packet compression d(·).
The length of transmitted packet is written on each wireless
Copyright © 2010 SciRes. WSN
root node R in TS. The notation }|{ S
Tqq in this paper
denotes summation is done for all values of the index
variable q in TS.
SqdTL (5)
Minimizing L(TS) at no-compression is equivalent to
finding SPT, and minimizing L(TS) at full-compression is
equivalent to finding MST.
2.2. Formulation of Our Problem
2.2.1. Assumption of Sensor Network and
In a sensor network, all locations of sensor nodes are
known. All nodes periodically generate a fixed-length
packet which is convergecast to the root node R. During
convergecast, packet compression occurs, and we have
enough statistics about packet compression.
2.2.2. Definition of Problem
Assuming Subsection 2.2.1, we want to find the spanning
tree TS that minimizes total forwarding energy for a con-
vergecast. To numerically define the problem, our goal is
to find the TS that has minimum tree length using defini-
tions in (4) and (5).
2.3. Analysis of Our Metric d(·)
The metric metrics d(·) and λ(·) are nonlinear. If we use a
nonlinear operator, the link cost C(i, j) contributes dif-
ferently to the tree length. This influences the preferred
type of spanning trees. If we apply d(·), nodes close to R
prefer short links, and nodes distant from R choose
straight paths to R. If we use λ(·), nodes prefer short links
and do not mind choosing very long-hop paths.
The nonlinear operator d(·) is very difficult to handle.
We found a strange characteristic about d(·). Under d(·),
a node can be more distant from R than its descendant.
We also found that there is no greedy solution, and are
strongly convinced that there is no polynomial optimum
solution. Therefore, we decided to rely on heuristics.
Figure 2 can be used to explain why there is no gre-
edy solution. Figure 2(a) describes a given four-node
network. There are four usable wireless links in Figure
2(a), and their link costs are written by them. The node R
is the root node of the spanning tree. Figures 2(b) and
2(c) illustrate two spanning trees. Figure 2(b) shows the
spanning tree solved by a greedy solution. In Figures
2(b) and 2(c), node distance is recorded in each node
The greedy solution chooses a link that minimally in-
creases the tree length if the link addition still keeps the
sub-tree connected. The sub-tree grows with the addition
of selected links. The greedy method firstly chooses
l(R,A). The selected links, especially l(R,A), are never
removed from the spanning tree. If we add three node
distances, the length of the greedy spanning tree Tb be-
comes 196. In contrast, the length of the minimum tree
Tc in Figure 2(c) is 189.4. L(Tc) is shorter by 6.6 than
L(Tb). Figure 2 shows the optimum tree does not always
include greedy selection.
We choose one-time compression d(·) instead of con-
tinuous compression λ(·) for two reasons. Firstly, d(·) is
very simple. Because of simplicity, we can not only cal-
culate the best estimate compression ratio f
ˆ from sta-
tistics easily, but also obtain the core operation expressed
in (7) with )1(
-complexity. Secondly, the λ(·) model
only covers partial ways of compression. λ(·) cannot de-
scribe a typical nonzero compression. Compression ratio
generally decreases as compression repeats. Nonzero
length is common after infinite compression. λ(·) cannot
cover this type of compression.
3. Packet Compression Ratio Dependent
Spanning Tree (CST)
In this section we define CST in two steps and explain its
operation. Step A calculates the best estimate f
ˆ of f
using statistics. Step B establishes a spanning tree with
calculated f
ˆ. Step B has two sub-steps. Step B.1 gen-
erates an initial spanning tree and Step B.2 describes
how to transform to a shorter one.
3.1. Step A: Calculation of the Best Estimate f
of f
To deduce the best estimate f
ˆ, we need statistical data
about the average packet length for every active link in a
spanning tree. As our major target is to find out the op-
timal spanning trees with obtained f
ˆ, we leave this part
to the Appendix.
(a) (b) (c)
Figure 2. Evidence that shows CST solution cannot be
greedy. (a) A given network. f=0.8 ; (b) A tree Tb by greedy
method, L(Tb)=196 ; (c) A tree Tc by optimum method,
Copyright © 2010 SciRes. WSN
3.2. Step B: Tree Establishment
This step finds the local shortest spanning tree with f
obtained in Step A. We heuristically generate a CST in
two sub-steps. An initial tree is built up in a top-down
process (from R to leaf nodes) in Step B.1, and is recon-
figured in a bottom-up process (from leaf nodes to R) to
a shorter one in Step B.2.
3.2.1. Step B.1: Initial Tree Setup
Step B.1 defines how to establish an initial tree. An ini-
tial tree is built by a combined algorithm of Dijkstra’s
SPT [10] and Prim’s MST [11]. These two famous algo-
rithms are very alike in definition. They are both greedy
and satisfy the greedy properties mentioned in Section
2.3. Dijkstra chooses a link that connects a node whose
distance to R is minimum, and Prim picks up the link
whose link cost is minimum. Because both protocols al-
ways maintain the working sub-tree as connected, merg-
ing two algorithms is straightforward.
Our algorithm uses the Dijkstra’s SPT algorithm until
it generates an nS-node sub-tree including R. Then we
use the Prim’s MST algorithm until a complete n-node
spanning tree is made. nS is calculated from (6). In (6),
x represents the integer closest to x and not smaller
than x. We fix W in (6) as 8 based on simulation with
various n-node sensor networks and f values.
nfn W
S)1( ,8
W .10 f (6)
We can make two comments on the initial tree. First,
W has a very large value 8. This makes nS very close to n
in (6) for most values of f. This means the initial tree is
very similar to SPT. Second, we use the SPT algorithm
in establishing a spanning tree near R. It is because the
node, having many descendants, prefers SPT in selecting
its parent node.
We explain the reason as follows. Suppose a node m is
looking for a better parent node. m’s current parent node
is p1(m), and there is a candidate mi in Figure 3. m de-
cides its parent node as the one that produces less tree
length. Assume m’s uplink l(m, p
1(m)) and d(mi) are
short, and l(m,mi) and d(p1(m)) are long. For m, the link
cost of its first hop contributes 100% to the tree length,
and the link costs of later hops are added as a ratio of
(f1). However, for m’s descendants, the costs of all
up-links above m are reflected fairly with a ratio of
(f1). If m is a leaf node, it prefers p1(m) because the
first hop to R is more important than later hops. If m has
many descendants, m has to consider them too. For the
sake of its descendants, m chooses mi as a parent node
sacrificing itself.
3.2.2. Step B.2: Spanning Tree Establishment
Step B.2 reduces tree length from the initial tree estab-
lished according to Step B.1. We are going to explain the
core operation of the algorithm that decides m’s best up-
link as shown in Figure 3. The node m is called a ‘des-
ignate node.’ Throughout the operation, a designate node
m prepares: 1) 10 closest nodes representing mi
i), 2) d(m), and 3) the number of m’s descen-
dent nodes denoted by h(m). A list Q is maintained that
sorts all nodes in reverse order of d(·).
Figure 3(a) is the current spanning tree TO, and Fig-
ure 3(b) is a candidate of a new spanning tree Tmi for one
of 10 mi’s. p1(m) and m’s descendants are excluded from
mi. For TO and all candidate spanning trees Tmi, we cal-
culate L(TO) and L(Tmi) and choose a tree with the least
tree length. If the chosen parent node is different from
p1(m), we reconfigure the spanning tree according to
Figure 3(b) and update influenced variables.
The Tree improvement Lmi defined by (L(Tmi) L(TO))
indicates relatively improved tree length with a new
parent node mi. Positive Lmi means the new tree is better.
If we apply our metric d(·), Lmi becomes (7). If we re-
place d(·) with δ(·), (7) changes to (12). Note (12) has
-complexity because it only includes known terms
including O
So far we have explained how to improve the tree for a
designate node. We will now give comments on how to
assign designate nodes. A designate node m is chosen
from Q by the reverse order of d(m). After performing all
jobs mentioned above, the algorithm updated the queue
Q to choose the next designate node mn as the one whose
d(mn) is the smallest but larger than dm which is d(m)
before reconfiguration. We call a cycle every related
operation during which Q is totally scanned once for
choosing designate nodes. Cycles repeat until no more
improvement is possible. We observed through simula-
tion that calculation usually finishes at the second or the
third cycle. In this way, we achieve the locally best CST.
The CST algorithm for a cycle is summarized below.
1) Prepare mi, d(m), h(m) for every m and establish a
queue Q in reverse order of d(·). Let dm = .
2) Check whether m' exists whose d(m') is the largest
but less than dm.
(a) (b)
Figure 3. Spanning tree before and after reconfiguration. (a)
Tree TO before reconfiguration; (b) Tree Tmi after recon-
Copyright © 2010 SciRes. WSN
(If m' does not exist,) the current cycle is completed.
(If m' exists,) assign m' as a new designate node m and
update dm to the value of dm'.
3) For every allowed mi, calculate Lmi using (12).
Check whether a positive Lmi exists.
(If a positive Lmi exists,)
a) m’s new parent node is assigned by mj which gener-
ates the largest positive Lmj among mi.
b) Reconfigure the tree as drawn in Figure 3(b).
c) Update d(·) and h(·) at the nodes p1(m), mj , m and
all of m’s descendants.
d) Re-sort the queue Q in reverse order of d(·).
4) Go back to 2.
Now we define Lmi as a )1(
-complexity expression.
Reconfiguration in Figure 3 changes node distance for
node m and m’s descendants only. To visualize the dep-
endency between a spanning tree and distance, the used
tree is specified after d(·) or δ(·). m’s descendant nodes
vary in distance after reconfiguration by mi
mf |)()1((
)|)()1( O
. If we denote m’s descendent node set
by p_(m), the above discussion is mathematically expr-
essed as (7).
  (7)
The complex nonlinear operator d(·) in (7) can be re-
placed by δ(m) using (8) and (9).
),,(|)()1(|)( iTTmmCfmfmd mimi
)).(,(|)()1(|)( 1mpmCfmfmd OO TT 
Because Q maintains d(m) in the tree TO, we remove
using Figure 3(b).
).,(|)(|)( iTiT mmCmm Omi 
Replacing d(m) in (7) with δ(m) using (8) and (9), and
removing mi
using (10), Lmi is expressed in terms
of δ(·) in (11). This is finally transformed to (12) to de-
note Lmi with d(·) using (9).
Timi O
hmdm dm
Cmp mfCmp m
fCmm fCmm
Cmp m
 
 
 
We hope CST be better than or equal to MST and SPT
for any f (10
f). To do so, CST at least has to sat-
isfy the next two properties. As two proofs are very
similar, we only prove Property 1.
Property 1 If f is 1, CST is equivalent to MST.
If f is 1, the CST algorithm assigns MST as the initial
tree at Step A. MST is optimum at f =1. As the initial tree
is already optimum, finding a positive Lmi for any desig-
nate node m is impossible. This leads to no reconfigura-
tion at Step B.2.
Property 2 If f is 0, CST is equivalent to SPT.
4. Simulation and Analysis
We investigated the tree lengths of CST, SPT and MST
for various fs according to (4) and (5). We have 25-node,
100-node and 400-node sensor networks with nodes lo-
cated randomly in a unit-length square sensor field. We
also select the root node randomly. We prepare 100
kinds of sensor networks for each condition and deduce
the average tree length to draw curves. We basically use
the link cost C(i, j) as a square of distance from i to j, and
we consider the case of the fourth power of distance ad-
ditionally because the transmission loss model is propor-
tional to l2l4 with the wireless transmission distance l.
Figure 4 shows five CSTs with varying f from 0 to 1
in a 35-node sensor network with fixed root node R at the
center top position denoted by big dots in the sensor field.
CSTs in Figures 4(a) and 4(e) are equivalent to SPT and
MST respectively. We can observe that paths along SPT
have a tendency to be straight toward R in Figure 4(a),
and SPT links are longer than MST links in Figure 4(e).
When f increases from 0 to 0.75, we notice only a few
changes. Most changes occur in the range of 175.0
Figures 5 to 8 draw the tree lengths using (5) for the
entire range of f (10
f). Figures 5 to 7 indicate the
tree lengths of SPT, MST and CST when the numbers of
nodes are 25, 100 and 400 respectively. All curves in
these figures decrease monotonously with increasing f
because the tree length is short with a high f value due to
(4). CST is always the shortest for all fs, and SPT and
MST curves cross each other at f value of a little more
than 0.9. The difference in tree lengths between SPT and
MST cases are large at a large sensor network and a
sparse sensor network.
We additionally examined the case of the fourth power
of distance instead of square distance assigned to the link
cost C(i, j) in Figure 8. As tree length in Figure 8 drops
sharply as f increases, we use the log scale in the y-axis.
Except when using log or nonlog scales, Figures 5 to 8
are similar in curve pattern.
Table 1 shows tree lengths and their averages for SPT
and MST relative to CST for various fs at 20% intervals.
‘Relative’ means the results are obtained after being di-
vided by CST length for the same condition. A special f
Copyright © 2010 SciRes. WSN
(a) (b) (c) (d) (e)
Figure 4. Changes in CSTs with varying f. (a) 0%; (b) 25%; (c) 50%; (d)75%; (e)100%.
Figure 5. Tree lengths of MST, SPT and CST with varying f
in 25-node sensor networks.
Figure 6. Tree lengths of MST, SPT and CST with varying f
in 100-node sensor networks.
Figure 7. Tree lengths of MST, SPT and CST with varying f
in 400-node sensor networks.
Figure 8. Tree lengths of MST, SPT and CST with varying f
in 100-node sensor networks. (C(i, j) is re-defined as fourth
power of normal transmission distance.)
Table 1. Relative tree length of CST, SPT and MST in 100-node sensor networks.
f (%)
Routing tree 0 20 40 60 80 93 100 Average
CST 100.0 100.0 100.0 100.0 100.0 100.0 100.0 100.0
SPT 100.0 100.1 100.5 101.5 104.2 110.3 140.7 107.8
MST 148.0 146.0 143.9 138.4 128.5 111.4 100.0 134.1
MSPT* 100.0 100.1 100.5 101.5 104.2 110.3 100.0 102.4
* MSPT is the tree from SPT and MST which produces the shorter tree length.
Copyright © 2010 SciRes. WSN
value of 93% is added at which the SPT curve and MST
curve coincide. Table 1 introduces MSPT in the last row.
MSTP is defined as the shorter tree from MST and SPT
for each given condition.
The far right column in Table 1 shows averages of the
relative tree lengths on a line except for the value at f =
93%. The average MSPTs include this value specially
because MSPT has a peak value at f = 93%. According to
Table 1, CST is 34.1% and 7.8% shorter than MST and
SPT respectively in terms of tree length. CST still out-
performs MSPT by 2.4%.
5. Conclusions
In convergecast sensor networks, many routing schemes
have proposed packet compression to save energy. The
Shortest Path spanning Tree (SPT) and the Minimum
Spanning Tree (MST) are only popularly used because
they are optimal at no-compression and full-compression
respectively. We proposed two important concepts. One
is a simple one-time compression model. The other is a
new routing method called packet Compression ratio
dependent Spanning Tree (CST).
CST is superior to SPT and MST for three reasons.
Firstly, CST provides us the best estimate f
ˆ of com-
pression ratio f using collected statistics. Secondly, we
can calculate CST easily using a one-time compression
model. Thirdly, CST outperforms CST, MST and SPT at
all considered sensor network environments and is opti-
mum at no-compression and full-compression. Simula-
tion shows CST outperforms MST and SPT by 34.1%
and 7.8% respectively in averaging over many compres-
sion ratio fs. These observations confirm that CST is
very useful in convergecast sensor networks.
6. References
[1] J. N. Al-Karaki and A. E. Kamal, “Routing Techniques in
Wireless Sensor Networks: A Survey,” IEEE Wireless
Communications, Vol. 11, No. 6, December 2004, pp.
[2] J. N. Al-Karaki, R. Ul-Mustafa and A. E. Kamal, “Data
Aggregation in Wireless Sensor Networks—Exact and
Approximate Algorithms,” Proceedings of IEEE Work-
shop on High Performance Switching and Routing
(HPSR), Phoenix, April 2004, pp. 18-21.
[3] I. Demirkol, C. Ersoy and F. Alagoz, “MAC Protocols for
Wireless Sensor Networks: A Survey,” IEEE Communi-
cation Magazine, Vol. 44, No. 4, April 2006, pp. 115-121.
[4] R. Vidhyapriya and P. T. Vanathi, “Conserving Energy in
Wireless Sensor Networks,” IEEE Potentials, Vol. 26, No.
5, 2007, pp. 37-42.
[5] C.-K. Liang, Y.-J. Huang and J.-D. Lin, “An Energy Ef-
ficient Routing Scheme in Wireless Sensor Networks,”
22nd International Conference on Advanced Information
Networking and Applications (AINAW), Okinawa, March
2008, pp. 916-921.
[6] L. K. Lawrence, “Sensor and Data Fusion Concept and
Applications,” 2nd Edition, SPIE Optical Engineering
Press, Bellingham, 1999.
[7] S. Upadhyayula and S. K. S. Gupta, “Spanning Tree
based Algorithms for Low Latency and Energy Efficient
Data Aggregation Enhanced Convergecast (DAC) in
Wireless Sensor Networks,” Ad Hoc Networks, Vol. 5,
No. 5, July 2007, pp. 626-648.
[8] H. Luo, J. Luo, Y. Liu and S. K. Das, “Adaptive Data
Fusion for Energy Efficient Routing in Wireless Sensor
Networks,” IEEE Transactions on Mobile Computing,
Vol. 55, No. 10, October 2006, pp. 1286-1299.
[9] H. Luo, J. Luo, Y. Liu and S. K. Das, “Routing Corre-
lated Data with Fusion Cost in Wireless Sensor Net-
works,” IEEE Transactions on Mobile Computing, Vol. 5,
No. 11, November 2006, pp. 1620-1632.
[10] H. C. Thomas, E. L. Charles, L. R. Ronald and S. Clif-
ford, “Introduction to Algorithms,” 2nd Edition, MIT
press, Cambridge, 2001.
[11] R. C. Prim, “Shortest Connection Networks and some
Generalizations,” Bell System Technical Journal, Vol. 36,
1957, pp. 1389-1401.
Copyright © 2010 SciRes. WSN
Appendix: Step A—Calculation of the Best
Estimate f
ˆ of Compression Ratio f
This step demonstrates how to calculate the best estimate
ˆ of compression ratio f with a given spanning tree TS
from collected statistics. We call the quadratic modeling
error ME by adding the square of link estimate error
)),(( jilLE of our one-time compression model through-
out all links in TS shown in (13). We can find the only
ˆ that minimizes )( fM E in (14).
EE jilLfM (13)
(fMfMfM EEE  (14)
The link estimate error )),(( jilLE is defined in (15).
To perform convergecast, every node forwards packets
along TS, compressing the received packets with the
compression ratio f. To calculate the best estimate f
we use statistics to provide the average message length
Eij on a link l(i, j) in TS. If we apply our one-time com-
pression model, we can build up the one-time compres-
sion model length Wij for all active links l(i, j) according
to the procedure mentioned in Subsection 2.1 and Figure
1. Utilizing the property that Wij is a linear equation of f,
we can obtain every aij and bij for every active links l(i, j)
in (16).
|,|)),(( ijijE WEjilL
ijijij bfaW
ijij ba , are constants. (16)
Combining the four definitions (13) to (16), we get
(17). Equation (17) turns to a simple quadratic equation
of f in (18) for the constants
, and
are constants. (18)
The quadratic equation in (18) has the minimum value
at the origin. Because a parabolic and its axis cross at the
origin, the axis of the parabolic guarantees the minimum
modeling error )( fM E. The axis corresponds to
All Eij, aij, and bij are available, thus we can get f