论文-示例

无线传感器网络动态重传算法张三1袁二1于四2(1.东莞理工学院，东莞523808;2.中国科学院深圳先进技术研究院，深圳518055)摘要：无线传感器网络路由协议通过点到点的重传来提高数据传输的可靠性，其重传机制没有考虑不同业务数据的可靠性需求差异，统一设定一个静态的最大重传次数。本文提出了一种动态重传算法，为每种业务分别根据其可靠性需求动态设定最大重传次数。对于较低可靠性需求的业务，相比于传统重传机制减少了重传次数。仿真表明动态重传算法能有效降低网络能耗。关键词：无线传感器网络、路由协议、重传算法AdynamicretransmissionalgorithmforwirelesssensornetworksZHANGSan1,YUANEr1,YUSi2(1Engineering&TechnologyInstitute,DongguanUniversityofTechnology,Dongguan523808,China;2ShenzhenInstitutesofAdvancedTechnology,ChineseAcademyofSciences,Shenzhen518055,China)Abstract:Routingprotocolsforwirelesssensornetworksincreasethetransmissionreliabilitythroughpoint-to-pointpacketretransmissionmechanism.Themechanismdoesn’ttakeintoaccountdifferencesofreliabilityrequirementsofdifferenttypesoftasks,andthenetworksetsastaticmaximumnumberofretransmissions.Thispaperpresentsadynamicretransmissionalgorithm.Itsetsthemaximumnumberofretransmissionsforeachtaskaccordingtoitsreliabilityrequirement.Forlowerreliabilityrequirementtask,comparingtothetraditionalretransmissionmechanism,thedynamicmechanismreducesthenumberofretransmissions.Simulationresultsshowthatthedynamicalgorithmcaneffectivelyreducenetworkenergyconsumption.Keywords:Wirelesssensornetworks,routingprotocol,retransmissionalgorithm无线传感器网络数据收集路由协议[1-3]包括两部分功能：组网与数据转发。组网是将传感器节点组织成一定的拓扑结构，使得网络中的每个节点都有通往基站的路径。数据转发主要包括获取下一跳地址、缓存队列管理、数据重传等。在数据转发过程中，路由协议要为数据获取下一跳地址信息，并提供一定的可靠性服务。用户的可靠性需求是一个统计量。这种可靠性是针对某种业务的采样数据集合而不是针对单个数据包。比如对周期性上报数据的可靠性需求为90%，那么是指在一段时间内，其数据传输统计的可靠性在90%上下波动都是可以接受的。可靠性与低能耗是相互矛盾的，高可靠性往往需要高能耗，无线传感器网络能量极度受限，所以在能耗与可靠性之间需要达到某种折中。目前有多种方法用来实现数据传输的可靠性。在Internet中，TCP是一种面向连接的传输层协议[4]，通过端到端的重传来确保数据的可靠性。但在无线传感器网络中，这种方法能耗太大。拥塞控制与多路径路由也可以用来提高数据的可靠性，这两种方法都已有相关的研究成果[5-8]。现有的无线传感器网络路由协议通过点到点的重传机制来提高数据传输的可靠性，设定一个最大的静态重传次数，例如MintRoute[3]及CTP[4]在节点编程时设定最大重传次数，我们称这种机制为静态重传。该机制没有考虑不同业务数据的可靠性需求的差异。例如，在环境监测应用中[9-10]，用户对报警数据需要非常高的可靠性，对于周期性上报的数据可以接受一个较低的可靠性。静态重传通过提高最大重传次数来满足小概率报警数据的可靠性，但对于周期性上报数据提供了高于用户需求的可靠性，浪费了大量能量。本文提出了一种动态重传算法，为每种业务分别动态设定满足其可靠性需求的最大重传次数。对于较低可靠性需求的业务，相对于静态重传机制减少了重传次数，从而降低网络能耗。在TinyOS[11]系统中的CTP[2]路由协议中实现了该动态重传算法，仿真验证了该算法的性能。1简单算法动态重传算法通过逐跳的重传机制来建立数据传输的端到端的可靠性服务，这其中重传次数的设定是一个关键的因素，不够的重传次数会造成数据丢失，过多的重传次数会造成能量浪费。动态重传算法根据业务设定的可靠性需求来确定每个数据包在每跳的最优重传次数，该算法需要以下信息：1）跳数：在路由建立过程中可以确定每个节点的跳数，节点的跳数为父节点的跳数加1，基站节点的跳数为0。2）节点到下一跳的链路质量：在建立路由时通过交换信标（Beacon）包[4]可以较准确地获得下一跳节点的链路质量信息。3）数据的可靠性需求：把可靠性需求当作一种配置参数下发给每个节点。文中用到的变量说明：R：数据的可靠性需求；k：节点k产生的数据，k是传感器网络中任意节点；H：从源节点k到基站的跳数；hi：节点i到基站的跳数；ri：节点i到下一跳节点i+1的链路可靠性，可以表示为数据包的接收率，即一个数据包从节点i传给节点i+1被成功接收的概率；ei：源节点k产生的数据分配在第i跳的可靠性为（1-ei）,那么与可靠性对应的我们称此为丢包率，即第i跳的丢包率为ei；N(k,i)：源节点k产生的数据包经过中间节点i时需要的最大重传次数；E(k,i)：源节点k产生的数据包经过中间节点i时期望的传输次数；Tk：源节点k产生的数据包传输到基站总的期望传输次数；端到端的可靠性需求为R（0R1），那么从源节点k到基站允许的丢包率为1-R，k到基站一共需要H跳，让丢包率ei均匀地分布在每一跳上。注意ei是人为设定的期望值，当链路质量下降时，通过重传减少丢包率，但不是无限制的重传，设定最大重传次数的上限与静态重传相等，所以动态重传算法在最坏的情况下与静态重传性能一致。如图1所示，每一跳所承担的丢包率为e，第i跳的可靠性为（1-e），总的可靠性为R，所以有：ReH1....................................................................（1）Soure2iBSr1r2ri-1rirh......eeeee图1丢包率均匀分布考虑数据包在节点i的传输，ri为节点i到下一跳节点i+1的链路可靠性（0ri1）。该跳的一次传输的丢包率为1-ri，如果1-rie，则不需要重传就可以满足该跳承担的可靠性。如果1-rie则要求节点i发送多个拷贝以确保满足对于源节点k的数据包所分配的可靠性，最大的重传次数可以表示为N(k,i)：erikNi,1………………………………………..（2）结合公式（1）和（2），可以求得最大重传次数：iHirRreikN1log1log1loglog,1………….……………….（3）节点i将数据包发送给节点i+1，可能会出现三种情况：一是数据包在节点i+1得不到正确接收，该数据包丢失；二是数据包被i+1正确接收，但i+1发给节点i的ACK包丢失；三是数据包被i+1正确接收，且i也收到i+1对该数据的ACK包。当i接收到ACK包时，节点i立即停止重传，在其它两种情况下i继续重传持至达到最大重传次数。如图2所示为i到i+1的双向链路质量，那么i发出的数据包能成功收到ACK的概率为ri*qi，双向链路的丢包率表示为li=(1-ri*qi)。ii+1riqi图2双向链路质量源节点k的数据包在节点i至少需要1次传输，如果要重传jth次当且仅当前面j-1次传输都没有收到ACK，所以节点i对于源节点k的数据的期望传输次数可以表示为：1,1,21,11,ikNiikNjjiilikNljlikE……………………..（4）数据包从源节点到达基站，总的期望的传输次数为Tk：111,1HikiTEkie……………………………….（5）2改进算法传感器节点采集的数据需要在基站汇聚，这是多对一的通信。基站附近节点的负载比远离基站节点的负载要大得多，因此它们的能量消耗过快，会导致整个网络因为基站附近的节点死亡而无法连通。上节所述的基于丢包率均匀分布的重传机制让每跳都提供相同的可靠性，将会导致基站附近节点能耗过大。如图3所示，节点A与B的数据传输负担是节点D、G、F与H的四倍，如果丢包率均匀分布，将会导致叶子节点的负载太少，而基站附近的节点能量消耗过快。为了缓解基站附近节点负载过大的问题，我们让丢包率ei的分布从源节点到基站每跳递增。让源节点承担最高的可靠性，让最后一跳承担最低的可靠性，整条路径的可靠性达到用户要求为R。如图4所示，源节点1产生的数据经过多跳传递给基站，数据包的丢包率递增，第一跳的丢包率为Δe，第i跳的丢包率为i2Δe。有如下表达式：Reeieii10,2……………….....………………（6）HiRei121……………………….……………..（7）BBSADCHFGE1hop2hop3hop图3多对一的数据流示意图B12iBSr1r2ri-1rirh......e1=Δee2=4ΔeAei-1ei=i2Δeeh=h2Δe图4丢包率从源节点到基站依次递增由式（7）可以求得Δe有多个解，其中只有一个解符合要求。式（7）随着H的增大，求解Δe难度也增大。而这个算法要在无线传感器节点上运行，其计算复杂度太大，所以我们式（8）来替代多项式（7）进行近似计算。HiRei121……………………………………（8）12116HHHRe………………………..………..（9）命题1：当R→1，等式（7）中的Δe略大于式（8）中的e。证明：式（7）和式（8）联合可得：HiHiiiee1111…………………………………（10）根据著名的Weierstrass’s不等式[12]，当0xi1,i=1,2,…,n,n≥2，下面的不等式是成立的。1111nniiiixx………………………..………………………….（11）所以由（10）与（11）联合可以推断出'11HHiiiiee，即2'211HHiieiei，所以有Δee。另外式（7）可以分解为：iihiieCeCeCe221111……………………（12）其中C1，C2，Ci为系数，当R→1，有e→0，当i2时，有iieC→0，所以有ReeCeHiihii111111………………………..（13）所以iiee，命题1成立。我们用Mathematical分析e与e之间的关系。让可靠性取值为：0.6、0.7、0.8、0.9、0.98，源节点到基站的跳数从3到20之间取值，分别用公式（7）和（8）来计算e与e。如图5所示为e与e之间的关系，e略少于e，随着跳数和可靠性的增加，e与e之间误差越来越少。当可靠性为0.6，跳数为3，e与e之间误差为0.01。当可靠性为0.98，e与e之间大致相等。00.020.040.060.