1 An FEC-bad Reliable Data Transport Protocol for Underwater Sensor Networks
Peng Xie and Jun-Hong Cui
xp@engr.uconn.edu,jcui@c.uconn.edu
Computer Science and Engineering Department
University of Connecticut,Storrs,CT06269-2155
Abstract—In this paper,we investigate the reliable data transport problem in underwater nsor networks.Underwa-ter nsor networks are significantly different from terrestrial nsor networks in two aspects:acoustic channels are ud for communication and most nsor nodes are mobile due to water current.The distinctions feature underwater nsor networks with low bandwidth capacity,large propagation delay,high error probability,half-duplex channels,and highly dynamic topology, which po many new challenges for reliable data transport in underwater nsor networks.In this paper,we propo a protocol,called gmented data reliable transport(SDRT),to achieve reliable data transfer in underwater nsor networks. SDRT is esntially a hybrid approach of ARQ and FEC. It adopts efficient erasure codes(so-called SVT codes in this paper),transferring encoded packets block by block
and hop by hop.Compared with other existing reliable data transport approaches for underwater networks,SDRT can reduce the total number of transmitted packets,improve channel utilization, and simplify protocol management.In addition,we develop a mathematic model to estimate the expected number of packets actually needed.Bad on this model,we can t the block size appropriately for SDRT,as helps to address the node mobility issue.We conduct simulations to evaluate our model and SDRT. The results show that our model can cloly predict the number of packets actually needed,and SDRT is energy efficient and can achieve high channel utilization.
I.I NTRODUCTION
Underwater nsor networks have received growing interests [19],[13],[1],[8],[6]recently.Compared with traditional techniques(such as remote nsing)ud in aquatic appli-cations,underwater nsor networks empower us to moni-tor/detect phenomena more accurately and timely in extended areas.
As in terrestrial nsor networks,for mission critical ap-plications,reliable data transport is demanded in underwater nsor networks.To design a good reliable data transport protocol,a natural concern is the energy efficiency issue since,similar to terrestrial nsor nodes,underwater nsor nodes are also usually powered by batteries.In harsh aquatic environments,it is even more difficult to recharge
or replace batteries.Besides energy consumption,there are veral other important issues to consider due to the significant distinctions between underwater nsor networks and terrestrial nsor networks,which we describe as follows.
First,acoustic channels are ud for underwater com-munication.In underwater environments,radio does not *This work is supported in part by the NSF CAREER Grant No.0644190.work well due to extremely limited propagation distance,
thus acoustic channels are employed.The propagation speed
of acoustic signals in water is about1.5×103m/s,five orders of magnitude lower than the radio propagation speed
(3×108m/s).Moreover,underwater acoustic channels are affected by many factors such as path loss,noi,multi-path, and Doppler spread.All the cau high error probability in acoustic channels.Further,due to mechanical limitations (sound is a mechanical wave),acoustic modems typically operate in half-duplex,and the transition between nding and receiving modes is very slow,usually taking tens of milliconds[7].
Second,underwater nsor nodes are passively mobile.
Empirical obrvation suggests that water current move at
the speed of3-6kilometers per hour in a typical underwater
condition[2].In an underwater nsor network,majority of the
nsor nodes(except somefixed nodes equipped on surface-
level buoys)are mobile due to water currents1.This kind
of node mobility results in highly network topology dynamics.
In summary,underwater nsor networks have the following unique characteristics:large propagation delay,low bandwidth capacity,half-duplex channels,high error probability,and high topology dynamics.All the features po many challenges for reliable data transport in underwater nsor networks.
A.Design Challenges
The new characteristics discusd above make many com-mon wisdoms in reliable data transport undesirable for under-water nsor networks.
亲子游戏活动1)End-to-End approach does not work well for underwater nsor networks:Broadly speaking,there are two types of approaches for reliable data transport,namely,end-to-end and hop-by-hop.Some recent studies[18],[9],[15]show that the end-to-end approach is infeasible for nsor networks.This conclusion still holds in underwater nsor networks,and is additionally justified by the high channel error probability and the low propagation speed of acoustic signals:(1)The high channel error probability makes the probability of successfully transferring data from end to end almost approaching to 1In this paper,we mainly discuss“mobile”underwater nsor networks, where nsors are notfixed and can passivelyfloat with water currents.This feature is common in a wide range of aquatic applications,such as estuary monitoring and submarine detection[6].However,our propod approach can be easily adapted to stationary underwater nsor networks.荷花钻石
0,as results in too many retransmissions for a successful packet delivery;(2)The low propagation speed of acoustic signals(1500m/s)will cau very large end-to-end delay, which introduces difficulty for the two ends to manage data transmission timely.
2)Half-Duplex acoustic channels limit the choice of com-plex ARQ protocols:Many reliable data transfer protocols u ARQ(Automatic Repeat Request),in which the receiver needs to nd acknowledgement(ACK)to the nder,requesting for retransmission if packets are lost.The simplest
ARQ protocol is the Stop-and-Wait protocol.In this protocol,after the nder nds one packet,it waits for ACK from the receiver.Only when a positive ACK is received,it starts to nd a new packet. It is well-known that the channel utilization of this simple protocol is very low,especially when the signal propagation delay is large.Pipelined ARQ protocols,such as Go-Back-N and Selective Repeat,can significantly improve channel utilization.However,half-duplex acoustic channels limit the choice of the complex ARQ protocols which require full-duplex operation.
3)Too many feedback from receivers are not desirable: In the literature,there are veral improved versions of Stop-and-Wait protocols,which are designed to increa channel utilization[11],[17].In such protocols with many ACKs,if ACKs are lost,not only bandwidth resource is wasted for ACK transmission,but also some successfully received packets will be retransmitted by the nder,causing more energy con-sumption.Additionally,in a denly deployed nsor network, multiple nsor nodes in the transmission range of the nder can overhear the transmission of the same packets.In this scenario,if one receiver requests for retransmission of lost packets,other receivers have to consume energy in overhearing the duplicate packets.
4)Pure Feedback-Free protocols are not energy efficient: Some reliable data transport protocols resort to Forward-Error-Correcting(FEC)to overcome the problems caud by many ACKs.In an FEC
approach,packets are encoded at the nder,and then transmitted continuously to the receiver. At the receiver side,lost packets are ignored,and original data packets can be reconstructed after enough number of encoded packets are successfully received.The management of feedback-free protocols using FEC is relatively simple(com-pared with ARQ protocols,which usually involve complex timeout and synchronization management)in that encoding and decoding are the only additional overhead introduced to the nder and receiver respectively.However,FEC esntially exploits redundancy for reliability.In other words,additional energy is wasted to achieve reliable data transport.In nsor networks,due to energy constraints,pure FEC protocols may not be a good choice.
5)Very large bulk data transmission is not suitable in mobile underwater nsor networks:In our target underwater nsor network scenario,most nodes are mobile.Therefore, there is no long-lastingfixed ,the com-munication time between any pair of nder and receiver is limited.Moreover,the bandwidth of communication channels is relatively low,and the propagation delay is extremely high. All the factors restrict the nder from nding very large bulk data at one time.
B.SDRT Overview and Contributions
Summarizing the above discussions,we aim to design a reliable data transport protocol for underwater nsor net-works,with the goals of high energy efficiency,high channel utilization and simple protocol management.In this paper, we propo a protocol,called Segmented Data Reliable Transport(SDRT),which is esntially a hybrid approach exploring both FEC and ARQ.SDRT assumes that receivers can detect corrupted packets.When a packet is completely lost or unrecoverable from corruption,this packet is treated as “lost”.In this paper,we are interested in reconstructing lost packets,not error-correction within packets.
In SDRT,a data source nodefirst groups data packets into blocks.Then the data packets are delivered from the source to the destination,block by block and hop-by-hop2.An intermediate node encodes each data block using an efficient erasure coding scheme(SDRT adopts a simple variant of Tornado codes[10],referred to as SVT codes,which will be discusd in Section II)and pumps encoded packets into the channel.After a receiver receives the encoded packets, it decodes and reconstructs the original block.After the reconstruction is done,the receiver encodes the block again and relays the block to the nodes in next hop.For each relay of a data block,the nder keeps pumping encoded packets until receiving a positive ACK from its next hop.
Our contributions can be summarized are follows:•SDRT can well satisfy the harsh requirements in u
nder-water nsor networks:efficient SVT codes enable SDRT to significantly improve channel utilization and relieve both nders and receivers of handling many ACKs;more important,SDRT reduces the number of packets to nd, thus saving energy.
•SDRT also helps to address the dynamic network topol-ogy problem caud by nsor node passive mobility.
By tting an appropriate block size,SDRT controls the transmission time of each block,thus,looning the requirements for the routing protocol to lect next hop.
The central issue for tting block size is to estimate the number of packets actually needed to recover the original data packets.We develop a mathematical model,which can help to t the block size appropriately.
交通事故赔偿协议
•We conduct simulations to evaluate our model and SDRT.
The results show that our model can cloly estimate the expected number of needed packets,and SDRT is energy efficient,and can achieve high channel utilization.
The rest of this paper is organized as follows.Wefirst give a brief review of SVT codes in Section II.T
hen we prent the SDRT protocol in Section III.After that,we describe the mathematical model of estimating the expected number of needed packets and the block size in Section IV-A, followed by the performance evaluation in Section V.Finally, 2In this paper,we design SDRT protocol using the hop-by-hop approach. However,it does not mean that there is no need to achieve end-to-end reliability.In fact,in the ca of network disconnection or congestion,some mechanism should be incorporated to provide end-to-end feedback,achieving the ultimate end-to-end reliability.
吃药用英语怎么说we discuss veral minal proposals for reliable data transport
in nsor networks in Section VI,and conclude our paper in
Section VII.
II.S IMPLE V ARIANT OF T ORNADO(SVT)C ODES Since SVT codes are simplified Tornado codes,we willfirst
introduce Tornado codes in the following.
Tornado codes[10]are one type of erasure codes,which
typically encode a t of original n messages into a t of
N encoded messages,where N≥n.In order to reconstruct the n original messages,the receiver has to receive a certain
number(larger than n)of encoded messages.The stretch
factor,defined as N
n ,is ud to measure the redundancy of
erasure codes.In Tornado codes,encoding and decoding only involve XOR operations,and thus are usually faster than other coding methods,such as Reed-Solomon codes,which require computation-intensivefield operations[14].Before describing the encoding and decoding algorithms of Tornado codes,we give some definitions.We call the original n messages as data packets,all the other messages are called check packets.In this paper,we u“packet”to refer to a data packet or a check packet.XOR operation is denoted as⊕.If we we u P1and P2to reprent two packets of the same size,then P1⊕P2is the result of bitwi-XOR’ing packets P1and P2. Encoding:The encoding algorithm in Tornado codes is equiv-
alent to constructing a multi-level bipartite graph where the nodes in each level are only randomly co
nnected to the nodes in adjacent levels.In the graph,the nodes in the leftmost level denote original data packets,and the nodes in each other level are the XORs of all their neighbors(nodes)in the left adjacent level.The randomly ordered packets including both data packets and check packets constitute thefinal encoded packets.An example of three-level Tornado codes is shown in Fig.1.In thisfigure,d1,d2,...,d5denote the original data packets.c1=d1⊕d2⊕d3,c2=d1⊕d3⊕d5,c3=d2⊕d4are the nodes in the cond level,and b1=c1⊕c2and b2=c1⊕c3 constitute the third level.
d1
d2
d3
d4
d5
01
Fig.1.An example of Tornado codes.
For a multiple-level bipartite graph,any two adjacent levels are connected by edges and constitute a subgraph,denoted as G k,which specifies the way to generate the check packets.As shown in Fig.1,G0and G1are two subgraphs.In a subgraph, an edge is an edge of degree i on the left(right)if it is adjacent to a node of degree i on the right(left).For example,in subgraph G0,edges adjacent to node d1are edge of degree 2on the left since node d1is a node with degree2on the right.A subgraph is determined by two edge-degree vectors,namely,left degree vectorλ=(λ1,λ2,···,λM)and right degree vectorρ=(ρ1,ρ2,···,ρM),whereλi is the fraction of edges with the degree i on the left andρi the fraction of edges with the degree of i on the right.Thus for subgraph G0,λ=(28,68)andρ=(0,28,68).Given the two vectors, we can generate the subgraph by a method suggested in[10]. Decoding:The encoding process of Tornado codes is to construct a graph from left to right,while the decoding process of Tornado codes is to reconstruct the graph from the right level to the left level.In a subgraph G k,if most of the nodes are known,then we have a higher chance to recursively reconstruct the unknown nodes until all the nodes in the left level(which is the right level for the subgraph G k−1)are recovered.Following this way,we can recover all the nodes till the leftmost level are reconstructed.The reconstruction process within each subgraph is one step of the decoding process.In each decoding step,for a node on the right side,if all but one of its neighbors are known,then this lost packet can be recovered by XORing all the related packets.For example, in Fig.
1,suppo packet d1is lost,we can reconstruct d1by d2⊕d3⊕c1.For a subgraph G k,its decoding subgraph consists of the nodes on the left side that are lost and not decoded yet,all nodes on the right side(already recovered in subgraph G k+1)and all the edges between them.One decoding step is equivalent tofinding a node of degree1on the right side in the decoding subgraph,and removing this node,its left neighbor nodes and all edges adjacent to its neighbors from this decoding subgraph.This procedure is repeated until all the lost packets are reconstructed or no more node of degree 1on the right side.
SVT Codes:Tornado codes are preferred in many network applications in that they can be easily and fast encoded and decoded[5],[4],[3].However,the degree ud in the original design of Tornado codes,which is derived from differential equations and relatively large,is not suitable for our scenarios. Since the number of packets in each block is very small,it is hard tofind the optimal degree vectors required by the original Tornado codes.Moreover,a large degree results in more packet header overhead.Thus,we adopt a simple variant of Tornado codes(referred to as SVT codes in this paper)for SDRT. SVT codes are esntially two-layer Tornado codes,with the first two elements of the left degree vectorλfixed ,λ1=λ2=0).The rationale behind this choice of degree distribution is following:in[10],it is proved that,to make the decoding of Tornado codes efficient,the left degrees of nodes are at least3,that is,λ1=λ2=0.
III.SDRT P ROTOCOL D ESIGN
A.Network Setting
Our target nsor network is relatively den,with nodes working in low-power transmission range(less than100m). The available data rate in such a network is expected to be around10kbps In the network,majority of the nodes are mobile,except some surface gateway nodes which are attached to buoys.A data source node generates data packets and relays to its neighbor nsor nodes.Through multiple routing hops, the data packetsfinally reach surface gateways,which then transfer data to the onshore commend center via radio.
B.Protocol Description
The key idea of the gmented data reliable transport (SDRT)protocol is to transfer encoded packets(using SVT codes),block by block and hop-by-hop.In order to reconstruct the original data packets,the receiver has to receive sufficient encoded packets.Becau the node mobility in underwater environment results in short communication time between any pair of nder and receiver,the transmission time for the encoded packets is limited.Thus SDRT has to guarantee that the receiver can receive enough encoded packets in such a limited time interval.By tting the block
size ,the number of original data packets in each block)appropriately, SDRT can control the transmission time and allow the receiver to be able to receive enough packets in order to reconstruct original block even in node motion.
In SDRT,a data sourcefirst groups data packets into blocks of size n.Then the source encodes the blocks of packets, and nds the encoded blocks into the network.The data packets are forwarded from the source to the destination block by block,and each block is forwarded hop-by-hop.In each hop-by-hop relay,the nderfirst estimates the number of packets it needs to nd for the receiver to reconstruct the original packets(using the model prented in Section IV). We call this number as“nding window”.Within the nding window,the nder pumps the encoded packets to the network fast.When the window is reached,the nder slows down pack transmission,waiting for a positive feedback from the receiver3.After receiving encoded packets,the receiver tries to reconstruct the original data packets.If the reconstruction is successful,it nds back a positive feedback.Upon the reception of a feedback,the nder stops nding packets, while the receiver encodes the original data packets again and relays them to the next hop.
The operations performed on the nder and the receiver are described in the following.
SDRT Sender:
1)Estimates the nding window.
2)Encodes a block using SVT codes.
3)Pumps encoded packets fast(in a random order)within
the nding window.
4)Sends encodes packets slowly outside the nding win-
dow until receiving a positive feedback from the receiver. SDRT Receiver:
1)Keeps receiving packets until it can reconstruct the
original data packets,and nds a positive feedback to the nder4.
2)Encodes the reconstructed packets again and relay them
to the next hop.
From the above description,we can e that SDRT reduces the burden of the nder and the receive
r by requiring only one feedback per block.The nder has no additional re-sponsibilities except encoding and injecting packets,and the receiver only needs to nd one feedback after reconstructing the original packets.
3The slow nding rate outside the nding window allows the nder to switch to receiving to listen for the feedback from the receiver.
4In real implementation,the feedback can be nt veral times to make sure that the nder can successfully receive a feedback.C.Discussions
1)Performance Improvement:In SDRT,a nder keeps nding randomly ordered encoded packets into the network
until receiving a positive feedback for each block.On the one
hand,this improves the channel utilization since the nder
does not need to wait for the feedback from the receiver before
transmitting subquent packets.On the other hand,as will be
shown in Section V,SDRT actually reduces the number of
packets transmitted,therefore,saves more energy.
2)Multiple Receivers:In underwater nsor networks,it is common that there are multiple nodes in the transmission
range of a nder.All the nodes can overhear the trans-
mission of the same packets and they are potentially capable
of relaying the block to the next hop.As pointed in[9],
sometimes it is necessary for the routing protocol to provide
alternative paths to overcome link failures.Our SDRT protocol
can be smoothly integrated with the routing protocols that
support alternative paths to improve the network robustness.
Our theoretical analysis and simulation results will show that
SDRT performs even better in the multiple-receiver ca. 3)Sensor Node Mobility:In underwater nsor networks, the dynamic network topology issue is a major concern of
routing protocols.SDRT contributes to address this problem
by tting an appropriate block size such that the next hop has
sufficient time to reconstruct the whole block even in motion.笔记本电脑摄像头
The block size n is determined by many factors such as the
implementation of SVT codes,the mobile speed of nodes,
the available bandwidth,the sound propagation speed and the
distance between the nder and the receiver.We will prent
an approach to estimate the block size,n,in ction IV-C.
IV.A NALYSIS
In this ction,we prent a model to estimate the expected
number of needed packets,and discuss how to calculate the
block size for SDRT.
A.Modelling SVT Codes
We have the following assumptions for the SVT codes we
u.First,we assume packet loss are independent.Second,
we assume that the nder only needs to nd at most three
rounds of encoded packets to guarantee that the receiver
successfully recovers the original data packets.This can be
achieved by lecting appropriate left degree vector and right
degree vector.Our model can be easily extended to SVT codes
with more than three rounds.
We u a bipartite graph with two levels to reprent SVT
codes.Let G={V,E}be the bipartite graph,where E is the
t of edges and V is the t of nodes in the graph.V=D∪C
and D∩C=φ,where D is the t of data packets and C
is the t of check packets.The edges randomly connect the
nodes in D and the nodes in C.For each node v∈C,we
define a box,b v={u|u=v,or uv∈E}.Thus,for each node v∈C,there is a corresponding box,which is the t of this node and its neighbors.There are totally|C|boxes in graph
G.If the left degree of node v∈C is i,we say the degree of
b v is i and the capacity of b ,the number of nodes in this box)is i+1.We call the t of all the boxes with the same degree a cluster.The cluster with degree i is denoted as B i.
For a nder-receiver pair,the receiving process at the
receiver side is equivalent tofilling packets into|C|boxes.
When a check packet is delivered successfully,it is equivalent
to putting one packet into one box.If a data packet of
degree j is received,it is equivalent to put j packets into孑孓是什么意思
j different boxes.For clarity,we refer the packets generated by a data packet or a check packet to as replicas.The replicas
generated by the same data packet are called sibling replicas.
For simplicity,we assume that sibling replicas are independent
of each other.This assumption is reasonable to some extent
since sibling replicas are independently and randomly put into
different boxes.When a box of capacity k isfilled with k−1
or k packets,we consider this box ,all the packets in
this box can be recovered.Using SVT codes,one full box can
potentially cau other boxes full.
We still uλandρto specify the edge-degree vectors,
<,λ={λ1,λ2,...,λM}is the left degree vector andρ= {ρ1,ρ2,...,ρM}is the right degree vector.We u p to denote the(packet)erasure probability,n to denote the number of original data packets or block size,and1+βto denote the stretch factor.It is easy to get|D|=n,|C|=nβ,and N= |C|+|D|=(1+β)n.
B.Estimating Expected Number of Needed Packets
In this subction,wefirst examine the single receiver ca and prent a model to estimate the expected number of packets actually needed by the receiver to reconstruct the original data packets,then we extend the model for the ca of multiple receivers.
1)Single Receiver:Let f(x)be the probability that the receiver reconstructs the original data packets given that x packets has been nt out before.Let d(1|x)be the probability that a successfully delivered packet is a duplicate one given that x packets has been nt out(by the nder)before,and r(1|x)be the probability that the receiver can reconstruct the original data packets when a non-duplic
ate packet is successfully delivered given that x packets has been nt out before.Then,we have
f(x+1)=pf(x)+(1−p)(d(1|x)f(x)
+(1−d(1|x))r(1|x))
f(0)=0
(1)
Due to space limit,we will not include the procedures of evaluating r(1|x)and d(1|x)in this paper.Interested readers can refer to our technical report[20].
Now we can evaluate the probability that a receiver recovers the original data packets when the nder nds out exactly x encoded packets.Let P(x)denote this probability,and it is computed as
P(x)=f(x)−f(x−1)(2)
Then,the average number of packets a nder needs to nd can be evaluated as
E1=Σ∞i=0i×P(i)(3)
2)Multiple Receivers:Now we consider the ca with R receivers,where R≥2.When the nder nds one packet, we assume that this packet is transmitted to R receivers independently.
For one receiver,we can u random variable X to denote the number of successfully received packets given that k packets have been nt out by the nder.We can reprent X as X=
j
X j,where random variable X j has value1if a packet is successfully delivered,and0otherwi.Further,we have notations P r(X j=1)=1−p and P r(X j=0)=p. Then,X has a binomial distribution,with expected value as µ=k(1−p)and standard deviation asδ=
k×(1−p)×p. For the multiple-receiver ca,R receivers are equivalent to R trails of X with the same binomial distribution.If any one receiver can reconstruct the original data packets and thus nd a positive feedback,the nder then stops nding packets.In other words,we need tofind the expected maximum value among the R trials.We evaluate the expected maximum value of the R trials by the Chebyshev’s Inequality[12].The expected number of packets needed in the ca of R receivers, E R,can be evaluated as follows:
E R=
(
√
Rp+4pE1−
√
Rp)2
4p.(4) From Equation4,we can easily prove that E R≤E1.This means,in SDRT,the nder actually nds fewer packets when there are more than one receivers.
C.Calculating Block Size
As stated earlier,in order to address the node mobility issue in underwater nsor networks,SDRT has to properly t the block size,n.Block size is determined by many factors, such as the stretch factor,the mobile speed of the nodes,the bandwidth of communication channels and the propagation speed of sound.We u1+βto denote the stretch factor(same as before),bw to denote the bandwidth of communication channels,L to denote the packet size,V to be the propagation speed of acoustic si
gnals and i be the number of receivers (i=1or R).Further,we denote the possible minimum time interval for the communication between a nder and a receiver (supported by routing protocols)as T r.Then the block size, n,must satisfy the following inequity:
E i×L
bw
穿上衣服用英语怎么说<T r(5) Note that n is one parameter in computing E i.Due to the complicated procedure of estimating E i,we can only resort to numerical methods to compute n.It should be further noted that the block size estimation is conducted off-line,before the underwater nsor network deployment.Thus,the complexity of block size estimation will not burden nor nodes.
An Example:If we have n=1000,β=0.6,bw=50kbps, V=1500m/s,the erasure probability p=0.5,the packet size L=40bytes,the left degree vectorλ={0,0,0,1}
and the right degree vectorρ={0,0,0,0,1
8
,
0,78},we can estimate the average number of needed packets,which is4185 bad on Equation3,for the ca of single receiver.Then according to Inequity5,the transmission time is less than26.2
conds.In other words,a block size of1000requires that the minimum time interval for the communication between a nder and a receiver is at least26.2conds.This means that the receiver should stay in the transmission range of the nder for at least26.2conds.If the node transmission range is100m,then roughly speaking,the whole block of data can be successfully transmitted from the nder to the receiver, considering the node moving speed is less than3m/s.
V.P ERFORMANCE E VALUATION
In this ction,we evaluate the performance of SDRT by simulations.We have also conducted experiments to evaluate the accuracy of the packet estimation model propod in Section IV.Due to space limit,we will not show the results for model evaluation in this paper.Interested readers can refer to our technical report[20].
A.Performance Metrics
We define the following metrics for SDRT.
1)Goodput:This metric is define as
θ=
#of original data packets
Time to sucessfuly nd all packets
.(6)
Goodputθis a measure of channel utilization:the higher the goodput,the better the utilization,and vi versa.
2)Sending Inefficiency:This metric is defined as
α=每天跑步好吗
#of packets nt
#of original data packets
.(7)
We u nding inefficiencyαto measure energy effi-ciency.The smaller the inefficiency,the fewer packets are nt;thus,less energy is consumed.
B.Results and Analysis
1)Channel Utilization::First,we compare the goodput of SDRT with a naive ARQ approach and an accumulative ARQ approach,in the ca of single receiver.The naive ARQ approach is similar to the basic Stop-and-Wait protocol,and the accumulative ARQ approach is esntially the same as the S&W-2approach[11].
In this t of simulations,wefix the packet size as40bytes and the bandwidth as10kbps.The distance between the nder and the receiver is t to60m and90m.The SVT codes have non-uniform degree distribution:λ=(0,0,0,1)
andρ=(0,0,0,0,1
8,0,78).The simulations are run for100
trials,and thefinal results are plotted in Fig.2.
From Fig.2,we can obrve that the goodput of SDRT is two orders of magnitude higher than that of the naive ARQ and the accumulative ARQ,as indicates that the channel utilization is significantly improved in SDRT.If we compare the naive ARQ and the accumulative ARQ,the latter slightly improves the goodput.This can be explained as follows:(1)In the accumulative ARQ,the nder reduces time on waiting ACKs by nding packets and ACKs in burst;(2)The accumulative ARQ reduces redundant packet retransmissions(caud by lost ACKs in the naive ARQ)by using accumulative ACKs.This is consistent with the conclusion drawn in[16].
G
o
o
d
p
u
t
(
k
b
p
s
)
Erasure Probability
Fig.2.Goodput vs.the erasure probability for single receiver,where-d60 means the ca of60m,and-d90means the ca of90m.
Another obrvation from Fig.2is that the distance between the nder and the receiver has almost zero effect on the goodput of SDRT(thus in thefigure,only one curve is shown). This is due to the fact that SDRT only needs a very limited number of ACKs.However,distance plays a non-negligible role in both the naive ARQ and the accumulative ARQ.This tells us that SDRT is more robust to network density.
2)Energy Efficiency:In this subction,we compare the nding inefficiency of four protocols:data caroul,SDRT, naive ARQ,and accumulative ARQ.The naive ARQ and accumulative ARQ protocols are the same as discusd in the last subction.The data caroul protocol is esntially a brute-force data transmission approach:no packet encod-ing/decoding,and no ACKs either.The nder simply keeps nding data packets in a random order until the receiver receives the data packets successfully.
In this t of simulations,the number of data packets is t to1000.For SDRT,the block size is1000,a
nd the stretch factor is1.,there are1000data packets and600 check packets in each block.We u the SVT codes with the left degree vector(0,0,0,1)and the right degree vector (0,0,0,0,18,0,78).Further,wefix the network size(with20 hops),and vary the erasure probabilities from0.1to0.5.We conduct simulations in both single-receiver and three-receiver scenarios.The results are shown in Fig.3.
From Fig.3,a general trend we can get is that when the erasure probability increas,the nding inefficiency is lifted, i.e.,the energy efficiency is reduced.This is pretty intuitive: the poorer the channels,the more energy is needed to achieve reliability.Comparing the four protocols,SDRT has the least nding inefficiency,therefore,fewest packets are nt;thus the energy efficiency is the best,in all cas.In addition, SDRT and the data caroul protocol perform better in the ca of three-receiver than in the ca of single-receiver,as is consistent with the analysis in Section IV.However,this conclusion does not hold for the naive ARQ and accumulative ARQ,where the nder needs to nd more packets when there are three receivers.This is mainly due to the following two reasons:(1)Multiple receivers nd more ACKs for the retransmission;(2)Lost ACKs cau the nder to nd duplicate packets.Thus,it is reasonably to predict that both the naive ARQ and accumulative ARQ perform wor when
