基于位置的无线传感器网络可靠性区分服务机制.doc

第2期曾勇等：基于位置的无线传感器网络可靠性区分服务机制77基于位置的无线传感器网络可靠性区分服务机制曾勇1, 马建峰1,2(1. 西安电子科技大学 计算机学院, 陕西 西安710071；2.计算机网络与信息安全教育部重点实验室, 陕西 西安 710071)摘 要：如何根据不同任务的不同可靠性需求来提供相应的服务是无线传感器网络所面临的最重要问题之一。结合基于位置的路由机制，给出衡量可靠性的量化度量模型，该模型无需全局网络拓扑信息。通过引入虚拟参考点，将数据的转发限制在特定区域从而减少无关传感器节点的能耗。分析了该区域与可靠性的函数关系，得到了可靠性随着参考点与源节点距离的增长而平方级增长的结论。在此基础上给出区分可靠性的服务机制。实验结果表明所提机制有效。关键词：无线传感器网络；可靠性；服务区分；基于定位的路由机制中图分类号：TP302.8 文献标识码：A 文章编号：1000-436X(2008)02-0071-08Location based reliability differentiation service for WSNZENG Yong1, MA Jian-feng1,2(1.School of Computer Science & Technology, Xidian University, Xian 710071, China; 2. Key Laboratory of Computer Networks & Information Security, Ministry of Education, Xian 710071, China)Abstract: How to design reliability differentiated service for missions with different reliability requirements becomes one of hot topics in wireless sensor networks. Combined with location-based routing mechanism, a quantified model without full network topology was proposed to evaluated reliability. By introducing a virtual reference point, the data transfer was limited in a specified area. The reliability function of the area was given. A detailed analysis shows that the function increases quadratically with the distance between the source node and the reference node. Based on the above conclusion, a reliability differentiated service mechanism was proposed. Simulation results show the efficiency of proposed mechanism.Key words: wireless sensor network; reliability; service differentiated; location-based routing mechanism1 引言收稿日期：2007-03-30；修回日期：2007-10-08基金项目：国家自然科学基金资助项目（90204012，60633020，60503012）；陕西省自然科学基础研究计划资助项目（2007F37）；国家高技术研究发展计划（“863”计划）基金资助项目（2007AA01Z429，2007AA01Z405）Foundation Items: The National Natural Science Foundation of China (90204012, 60633020, 60503012); The Natural Science Basic Research Plan in Shanxi Province of China (2007F37); The National High Technology Research and Development Program of China (863 Program)(2007AA01Z429, 2007AA01Z405)随着传感器技术、嵌入式计算以及低功耗无线通信等技术的飞速发展，无线传感器网络（WSN, wireless sensor networks）在军事国防、环境检测、抢险救灾等领域的应用得到了广泛的关注1,2。WSN资源有限以及应用高度相关的特点使得研究人员开始广泛关注其路由协议的设计。已有的大多WSN路由协议均基于端到端的路由建立、维护和存储技术，并且需要根据全网络的拓扑变化对路由动态维护3。然而，由于传感器节点失效率较高，拓扑变换也相对比较频繁，因此这些路由策略往往时延较高，且可靠性较低，所以这些策略并不适合于WSN，特别是对突发事件有较高可靠性与及时性要求的业务。此外，在很多应用场景中，传感器节点必须知道自身的地理位置，否则其采集到的突发事件数据缺乏应用价值，例如在抢险救灾中，只有得到发生危险的地理位置后，抢救人员才能有针对性地进行抢救。因此，WSN中需要借助全球定位系统（GPS, global positional systems）对节点定位4。由于WSN中，传感器节点数目巨大且能量有限，而GPS造价和能耗均较高，因此不适宜在每个节点均装备GPS。目前的解决方法主要依靠分布式的GPS位置定位与分发技术来有效地获得节点位置信息5,6。基于位置的路由协议（LBR, location-based routing protocol）恰恰避免了在节点中建立、维护和存储路由表，无需全局网络拓扑信息，仅仅依赖直接相邻节点进行路由选择，因而具有传输时延小，可靠性相对较高的优点。因此，研究人员正在努力研究适合无线传感器网络的LBR协议3,59。然而，不同的任务有不同的可靠性需求，其对网络的资源要求也是不同的，LBR并不能自适应地提供保障可靠性需求的相应服务10,11，因此如何在无线传感器网络中提供区分可靠性的服务机制成为研究热点之一1012，该研究最重要的目的是避免对具有不同可靠性的业务提供统一服务所导致的资源浪费。现有工作要么需要全局网络拓扑信息，要么局限于定性描述，统一的定量分析还不多见。本文分析与总结了当前较为重要的LBR与区分可靠性服务的协议，指出了其核心路由机制、特点和优缺点。给出了基于定位的区分可靠性服务机制。通过引入一个虚拟参考点，将数据中继限制在某个特定的区域内，传感器节点只需要简单的计算就可以判断是否需要接收与转发传感数据，从而大大降低了传感器节点的能量消耗；通过建立数学分析模型，给出了该可靠性与虚拟参考点的函数关系，得到了可靠性与虚拟参考点距源节点距离的平方成正比的结论；实验仿真表明，理论分析与实验结果相符，在全网络能量消耗与能耗负载均衡方面，本文工作优于已有方案。2 相关工作简介本小节给出WSN中几个最经典的协议，指出其核心机制的优缺点。GPSR协议7是最经典的LBR协议之一。该协议基于贪心算法，各节点产生或收到数据后，计算所有相邻节点与目的节点的欧氏距离，然后选择向最短欧式距离的节点转发数据。TBF 协议8可以认为是GPSR协议的一种改进，不同之处在于TBF事先指定了一条连续的传输轨道，然后将此信息包含在数据报头中，收到报文的节点利用贪心算法根据轨道参数以及其相邻节点的位置，计算出最接近轨道的邻节点，并作为下一跳节点。这两个协议都可能遇到传输空洞问题，即贪心算法所计算出的传输区域（传输空洞）可能均无法到达目的节点，此时可以按照右手法则沿空洞周围传输来解决此问题3, 8。然而，这2个协议均忽略了不同的任务对可靠性的不同需求。实际应用中，根据任务的需要，传感器节点采集到的数据往往具有不同的可靠性与及时性要求，例如在森林温度监控应用中，温度的急剧变化情况必须及时并且高度可靠地传输到控制中心，而相对平缓的温度变化则可以容忍一定程度的传输时延与失败。然而，这两个协议对具有不同可靠性需求的任务所提供的服务却是相同的，这样导致的结果是：低可靠性需求的任务依然占用高可靠性需求的资源，会不可避免地带来资源浪费。SPEED协议9的路由机制和GPSR类似，不同之处在于，SPEED是第一个区分了时延性需求的LBR协议。它提供了拥塞控制和软实时保证机制，同时和前两个协议类似，都无需全局网络拓扑。AFS10和ReInform11首次明确区分了不同可靠性需求，指出可以通过调节路径冗余度使之适应不同可靠性需求。但是，这两个协议需要全局或半全局网络拓扑信息来调节路径冗余度和计算最优路径，并且它们的工作主要集中在定性描述，其研究方法主要依靠举例说明，不具备一般性。MMSPEED12综合考虑了如何同时满足区分不同时延性和可靠性需求，重点讨论了网络层与MAC层在同时支持区分性服务时，对通信范围、能量效率的要求。同时，该文还给出了基于概率统计来估计端到端的传输可靠性方法，该方法无需全局网络拓扑，仅仅需要直接邻节点的信息。但是，该文的方法没有考虑传感器节点的能量消耗问题，一次数据的发送需要全网络的传感器节点参与，因此会带来很多无谓的能量消耗。3 网络模型和问题陈述3.1 网络模型根据上述对LBR协议的分析，总结出此类WSN的性质如下。首先，所有传感器节点随机部署在一个二维的区域M内，并且：1) 在以某个节点为圆心，以r为半径的感知范围内的所有其他传感器节点均能直接接收到其发送的消息，在感知范围外则不能；2) 相对于节点感知范围而言，M的半径R足够大（rx，化简可得b/(2)。此时C4的面积Sa等于扇形EOFP的面积S1与EPFG所围面积S2之和，由上下对称性可知，Sa=2(S1+S2)(4)对扇形EPO，令弧OE上任意一点坐标为M(，)，则可取面积积分变元为0.5x2d， ，/2，所以S1 =(5)对于EPG，易知其面积等于EHG的面积S3加上直角三角形EPH的面积S4，而S3又等于扇形EOG的面积S5减去直角三角形EOH的面积S6，即S2=S5S6+S4，而对S5同理可取面积积分变元为0.5(2xb)2d，0，得S5=，又不难求得S6和S4分别为和，因此S2 =+(6)将式(5)、式(6)代入式(4)并化简得到S0 = x2 + (2x2-4bx+b2) arccos (2xb)/2x +(7)图2 极坐标系下虚拟参考点的位置b) P在线段(H，G)上，如图2(b)所示，此时(2xb)cos/4，xb，圆C1和圆C3所围区域C4的面积S为S = x2 + (2x24bx+b2) arccos (2xb)/2x+，xb(11)类似的，当b/2xb，圆C1和圆C3所围区域C4的面积S为S = x2 + (b22x2) arccos (b/2x) ，b/2x 0，因此C4的面积S是关于自变量x的单调递增函数。至此，得到定理1。定理1 给定源节点S与目的节点D，令参考点P与源节点S的距离为x，则区域C4的面积S由式(11)和式(12)给出，S是x的单调递增函数。推论2 S与x2成正比。证明 对式(11)和式(12)不难求得= ，= 。这2个极限均为大于0的常数，因此，S与x2是同阶无穷小，可简记作S=O(x2)。换言之，随x的增长S的增长是x2级的，因此结论得证。4.3 进一步分析本小节给出数据传输的可靠性与x的关系。已有文献研究WSN数据无状态路由传输（性质6）的可靠性，其中最有影响的是文献12。该文献量化地给出了如何根据直接邻节点的信息估计数据传输成功的概率，其方法如下。每个节点i保存并更新与直接相邻节点j之间最新的丢包率ei, j，记从源节点i经直接邻节点j中继并成功发送到目的节点d的可达概率为Tj, 则有=(13)其中，表示对节点j到d距离与节点i到j距离的比值取整，该数值用于在缺乏全局网络拓扑的情况下，通过邻节点j的信息来估计从源节点i到目的节点d的跳数，而该跳数用于估计从节点j到目的节点d的可达概率。令源节点i的所有直接邻节点集合为J，记从源节点i经直接邻节点集合J中继并成功发送到目的节点d的总可达概率为TJ，则有=(14)而式(14)则被用于评估WSN端到端数据传输的可靠性。该式建立在如下假设之上：1)节点j和其后继节点之间的丢包率与源节点i和j之间的丢包率具有相似性；2)节点j和其后继节点之间的距离与源节点i和j之间的距离具有相似性。显然，对于WSN来说，该假设是合理的。文献12的路由选择过程中，则通过式(13)和式(14)计算可达概率，并选择高于给定可靠性需求的路由，最终的路由可能是单径，也可能是多径。虽然文献12的路由算法能有效地根据任务的可靠性需求来选择前向转发路径，但是，该文的路由算法本质上是一种flooding（泛洪）路由机制，而flooding机制本身存在信息内爆与重叠问题3，因此文献12的工作会不可避免地导致无关传感器节点参与路由，从而带来无谓的能量消耗。基于此，本文对其进行了改进，将数据的中继限制在可行区域C4之中，从而大大减少了无关传感器节点的参与以减少无谓能耗。式(14)建立在全网络传感器节点均参与数据中继的基础之上，而在我们的机制中则限制在区域C4内，因此需要新的计算公式。在不具备全网络拓扑的条件下，由统计学知识可知，两者的比值等于C4的面积与全网络面积的比值，则可达概率计算如下=(15)然而，考虑到传感器节点能量和计算能力均有限，而求必须要计算相对复杂一些的式(11)和式(12)，因此需要化简。根据推论2易得，随x的增长，的增长依然是x2级的，特别地，由于R一般都较大(Rr10m)，因此有，xb或者，xb。这样，源节点在选取参考点坐标过程中，只需要计算简单的(x/R)2即可。令某业务期望达到的可靠性为Preq，则Preq，结合式(15)与上述分析，参考点距离源节点的距离x至少应该满足(16)式(16)说明参考点P在源节点S与目的节点D连线的延长线上时，相对P在S与D的连线上的情况更加容易满足业务期望达到的可靠性，因此在实际选择参考点的时候，应该尽可能地选择大一些的x。一旦选定x，则容易算出直角坐标系下，虚拟参考点P(Px, Py)的坐标， Px=Sx+x(Sx-Dx)/|SD|， Py=Sy+x (Sy-Dy)/|SD|。4.4 区分可靠性服务机制1) S根据公式(16)计算适合此次传输需求的x，将(Px，Py)与Preq附加在数据报头中发送；2) 其他传感器节点A根据式(1)判断是否需要接收与转发数据；3) 参与转发的节点i计算式(14)，选择不低于Preq的路由前向转发数据。5 性能分析与相关工作比较5.1 相关工作比较GPSR7 和TBF 8主要关注如何合理地采用贪心算法来确保数据的成功传输，指出了在网络连通性不被破坏的情况下，一定能够发现可达路由，但是它们均未给出计算可靠性的方法，因此不能满足不同任务的不同可靠性需求，所有业务都采用同样的策略，因此容易导致节点的无谓能量消耗。本文给出了根据邻节点的信息估计可靠性的计算公式，从而能够区分不同任务可靠性需求，降低节点的无谓能量消耗。AFS10和ReInform11能够调节路径冗余度，使之适应不同可靠性需求。但是，这两个协议给出的仅仅是路径冗余度与可靠性的定性描述，缺乏进一步的量化分析，此外它们均需要知道本结点到基站或者汇聚节点的跳数距离。本文的工作不仅有量化的计算公式，而且可以通过局部拓扑信息来估计跳数距离。MMSPEED12给出了仅仅依靠直接邻节点的信息来量化可靠性的方法，并综合考虑了时延性和可靠性。然而，该方法在传输数据时，所有传感器节点都有可能参与数据中继，因此容易带来不必要的能量消耗。本文通过引入虚拟参考点，将数据的中继限制在特定区域，并建立了该区域与可靠性的函数关系，通过调节虚拟参考点的位置来适应业务的不同可靠性需求，因此能有效地减少无关节点的能耗。本文针对WSN的具体情形，通过引入虚拟参考点，将数据的中继限制在特定的区域内，其他传感器节点至多需要4次欧氏距离的计算就可以判断出是否需要参与中继，从而减少了无关传感器节点的无谓能量消耗，参与的节点只需要接收和转发数据，额外的通信开销包括该数据期望的可靠性需求与参考点P的坐标。表1总结了上述比较。5.2 性能评价采用Glomosim作为模拟实验平台对所提机制进行了分析，并对以下指标进行了评价。首先给出了协议的有效性分析，然后与相关协议进行了比较。模拟实验使用和ReInform相同的能量模型与参数设置，详细的参数不再赘述，请参见文献11。模拟实验环境检测区域半径为50m，节点感知半径为5m。图3给出了本文的方法在不同节点部署密度下的有效性分析。其中横轴表示某业务期望的可靠性，纵轴表示该业务在对应的需求下实际获得的可靠性。从图中可以看出，本方法可以有效地满足业务的不同可靠性需求。表1相关工作比较相关工作研究方法拓扑需求可靠性定义可靠性区分源节点计算开销其他节点计算开销参与节点额外通信开销GPSR仿真局部无不能与所有邻节点的欧氏距离与所有邻节点的欧氏距离无TBF仿真局部无不能计算指定轨道曲线所有邻节点与指定曲线的欧氏距离所有邻节点与指定曲线的欧氏距离一条指定曲线AFS仿真全局举例能建立全局拓扑计算并维护路由维护路由信息期望的可靠性指定路由ReInform仿真+理论推导半全局定性+定量能与所有邻节点的丢包率计算式(14)分配路径数同源节点期望的可靠性路径数MMSPEED仿真+理论推导局部定量能与所有邻节点的丢包率计算式(14)同源节点期望的可靠性本文工作仿真+理论推导局部定量能与所有邻节点的丢包率计算式(14)与式(16)仅满足式(1)的节点同源节点，不需计算式(16)期望的可靠性一个参考点坐标图3 期望的可靠性与获得的可靠性图4是不同协议在相同的网络拓扑，相同的目的节点与源节点以及相同的随机业务流下，得到的节点能耗情况的比较结果，其中横轴表示时间，纵轴表示在对应时间下所有节点剩余的总能量之和。根据表1，我们只需要和基于无状态的路由协议进行比较，包括TBF以及仅区分可靠性的MMSPEED。图4是不同协议节点能耗情况的比较。其中X轴是时间，Y轴是所有节点剩余总能量。结果表明，我们的机制优于TBF和MMSPEED。注意到TBF和MMSPEED在最初相差不是太多，甚至TBF还要优秀一些，这是因为最初TBF只需要局部的计算，而中期MMSPEED由于区分了可靠性，因此减少了能耗，同时TBF指定传输曲线的开销居高不下导致能耗增加，后期由于网络连通性变差，节点故障频繁，TBF需要多次运行右手法则来解决空洞问题，所以性能变得不稳定。MMSPEED与我们的方案相比，由于增加了无关节点的传输，因此性能稍弱。图4的结果和表1的理论分析结果相符。图4 网络剩余总能量与时间的关系6 结束语分析并指出了已有基于位置的无线传感器网络路由协议的优缺点；通过引入虚拟参考点，在保证可达性的前提下，将数据中继限制在相对较小的区域内，减少了无关传感器节点的能量消耗；给出了该区域与虚拟参考点的函数关系，并给出了可靠性量化度量模型，从而建立了可靠性与该区域的函数关系，得到了可靠性与虚拟参考点距源节点距离的平方成正比的结论，并据此提出了区分可靠性的服务机制；实验仿真表明，理论分析与实验结果相符，网络能量消耗优于已有方案。参考文献：1AKYILDIZ I F, SU W, SANKARASUBRAMANIAM Y, CAYIRCI E. A survey on sensor networksJ. IEEE Communications Magazine, 2002,40(8):102-114.2ESTRIN D. Next century challenges: scalable coordination in sensor networksA.Proc of MobiCOM99C. Seattle,USA,1999. 263-270.3马祖长,孙怡宁,梅涛.无线传感器网络综述J.通信学报,2004, 25(4):114-122.MA Z C, SUN Y N, MEI T. Survey on wireless sensors networkJ. Journal on Communications, 2004,25(4):114-122.4HOFMANN WELLENHOF B, LICHTENEGGER H, COLLINS J. Global Positioning System: Theory and PracticeM. Springer Verlag, 1997.5BULUSU N, HEIDEMANN J, ESTRIN D. GPS-less low cost outdoor localization for very small devicesJ. IEEE Personal Communications Magazine, 2000, 7(5): 2834.6HIGHTTOWER J, BORIELLO G. Location systems for ubiquitous computingJ. IEEE Computer, 2001, 34(8): 57-66.7KARP B, KUNG H. GPSR: greedy perimeter stateless routing for wireless networksA. Proc of the 6th Annual Intl Conf. on Mobile Computing and NetworkingC. Boston, 2000. 243-2