2022年低功耗无线传感器网络双层数据分发协议算法 .pdf

《2022年低功耗无线传感器网络双层数据分发协议算法 .pdf》由会员分享，可在线阅读，更多相关《2022年低功耗无线传感器网络双层数据分发协议算法 .pdf（6页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、http:/-1-低功耗无线传感器网络双层数据分发协议算法1钱铖,张陆勇,周正北京邮电大学无线网络实验室，泛网无线通信教育部重点实验室，北京（100876）E-mail：摘要：本文研究了无线传感器网络中针对移动汇聚节点提出的TTDD（Two-Tier Data Dissemination）路由算法。为了解决WSN 中能耗这一核心问题，对原有的TTDD 算法进行了改进和优化：依据首次查询中的源节点一次性建立虚拟网格；源节点和汇聚节点sink节点间寻找近似直线的路由来转发数据；通过设定虚拟网格边长，决定转发节点密度，且在转发节点的选择中引入竞争机制来延长平均网络寿命。仿真表明，新算法有效的提高了网

2、络的节点利用率，延长了网络生命周期。关键词：无限传感器网络，TTDD，功耗。1.引言凭借着微电子技术、计算技术和无线通信等技术的进步，低功耗多功能传感器得以快速发展，使其在微小体积内能够集成信息采集、数据处理和无线通信等多种功能。无线传感器网络1（wireless sensor network，WSN）是通过在特定的观测区域内部署大量的微型廉价传感器节点，以无线通信协议方式形成一个自组织网络，从而进行数据的搜集和传输，为用户提供有用信息。它在医疗、商业、军事领域都有着广泛的应用，被专家认为是未来四大高技术产业之一。然而，无线传感器节点多采用电池供电，能量有限且更换电池不便这些客观因素，这就使得

3、无线传感器网络路由设计是围绕着低功耗这一核心问题而展开的，如何延长传感器网络的生命周期也就成为了算法设计的重要目标。在大规模的无线传感器网络中,汇聚节点（sink）的位置信息不停的改变,以便于网络节点及时更新数据发送的方向。但是sink的移动性也给传感器网络带来了挑战，频繁的更新消息会增大网络负担,消耗过多能量,并且会造成通信冲突。TTDD 2算法为那些具有多个移动sink的网络提供了一种高效的具有可扩展性的方法，它充分利用了网络中传感器节点位置信息已知的特点，在具有移动sink的网络中表现出了良好的性能。2.TTDD 算法模型分析2.1 TTDD 概述在TTDD 算法中，数据的查询和传播是依

4、靠虚拟的方格来完成的。以源节点为交点做一条水平直线和一条垂直直线，并且分别以为间距做上述两条直线的平行线，以此把平面分成一个个的方格3（cell），源节点本身即为方格的一个顶点。设源节点的坐标为()yxLs,=，则方格其他的顶点坐标为()jipyxL,=，其中?=+=+=,2,1,0,;,jijyyixxji。由概率论可知，对于在观察区域内随机分布的传感器网络节点来说，每一个cell顶点附近都有一个距离它最近的网络节点，这个节点称之为分发节点。由各个分发节点构成的结构也是一个近似的方格网结构，同时这一结构1本课题得到国家自然科学基金项目(60432040,60772021),教育部博士点基金项

5、目(20060013008),韩国仁荷大学 IT研究中心项目(INHA UWB-ITRC)的资助。名师资料总结-精品资料欢迎下载-名师精心整理-第 1 页，共 6 页 -http:/-2-也保证了分发节点在网络内部分布的尽可能均匀。一些方格结构的基本信息也存储在分发节点中，如离它最近得方格顶点pL及上级分发节点的位置信息、数据声明消息等。当sink需要数据的时候，就在一个cell范围内洪泛查询消息，并找到最近的分发节点，称为 sink的“立即分发点”。随后在 cell级别的分发节点中传播查询信息。源节点收集到数据后，主动构建上述虚拟方格，找到到达sink的路径，开始发送信息。建立了方格之后，s

6、ink的查询消息就可以通过两个层次到达源节点。较低的层是指在一个小方格(cell)之内的通信，较高的层次是由方格的顶点组成的传输层。这就是TTDD 算法路由的建立过程。因此可以说，TTDD 算法的信息是沿着cell的边长传送的。如图1所示。图1 TTDD算法原理图图2 C-TTDD算法原理图2.2 TTDD 模型假设TTDD 的模型基于以下假设4:1.大量的具有相同属性的传感器节点分布在一个很大的区域内，传感器节点之间进行短距离的无线通信。远距离的通信是通过中间节点进行多跳实现的；2.每个传感器节点清楚自己的位置信息。但是sink可能不知道自己的位置信息；3.当有事件出现时，周围的传感器节点会

7、收集并处理信息，然后由其中的一个作为源节点发送数据；4.用户通过网络查询需要的信息。可能网络中同时有多个sink在移动收集信息；5.假设传感器节点已经清楚自己的任务。2.3 TTDD 算法的缺点基于以上的算法模型，分析一下TTDD 算法的主要缺点：首先，由于 TTDD 算法中所传送的数据是沿着分发节点组成的cell边长进行的，而cell虚拟方格结构走的是90度角的折线路径，因此TTDD 中的路径长度是最优路径长度的2倍，加大了传输开销。其次，传统的 TTDD 算法中每个源节点传输数据前，都要建立新的虚拟方格，存在着较大的建立方格开销。第三，在寻找每个cell顶点的分发节点时，传统TTDD 采用

8、了寻找距离顶点最近的一个传感器节点作为分发节点的办法，这样很容易使临近节点的能量耗尽，从而缩短网络的生命周期。立即分发点分发节点 1 源节点分发节点 2 分发节点 3 汇聚节点源节点汇聚节点TTDD 路由C-TTDD 路由名师资料总结-精品资料欢迎下载-名师精心整理-第 2 页，共 6 页 -http:/-3-3.改进的 C-TTDD路由算法3.1 C-TTDD 算法原理针对上文提出的TTDD 算法的不足，本着对节约能耗这一核心问题的处理，本文提出了一种新的算法：C-TTDD，算法思想如下：对于 TTDD 路径长度是最优路径的2倍这一问题，已有一些改进的方法，如A-TTDD5，在源节点和 si

9、nk的立即分发点之间建立一条直线，用直线经过的顶点的分发节点传输数据，这种方法虽然初步解决了传输路径上的能量损耗问题，但是由于没有考虑到分发节点的有效利用问题，会造成离顶点越近的传感器节点死亡越快的情况，从而缩短网络的生命周期。如图 2给出了 C-TTDD 算法的原理图，也是采用“对角线”路由建立方法，来解决TTDD 算法中路径长度问题；由于传感器节点的位置静止及位置信息已知，C-TTDD 算法在处理建立方格方面，采用了依据第一次查询时的源节点建立虚拟方格，之后的查询及数据传输不必从新建立方格，而是沿用已有虚拟方格的方法，即“一次建格，多次使用”的思想，从而大大节约了网络节点建立方格结构以及洪

10、泛建格信息的开销。并且，这种做法也有利于其他传感器节点的动态加入。在顶点分发节点的选取上，使用了竞争机制，建立以 cell顶点为中心、边长同 cell边长的正方格，取此方格范围内的剩余能量最大的传感器节点作为此顶点的分发节点（即在图2中虚线框包围的区域内选取此cell顶点的分发节点，其他路由经过的顶点类似），这样做在理论上可以保证所有传感器的最大利用率，从而进一步延长网络的使用寿命。3.2 C-TTDD 算法开销分析假设观测区域为E，区域内有 N个节点，区域的每条边上平均分布N个节点；sink 更新了 m次位置信息，每两次更新期间接收到了md个数据包，每个数据包大小为l；cell边长为，每个

11、cell中有ENn2=个节点，由于节点在概率上均匀分布，因此在cell的每条边上平均有n个节点。因此，在改进的C-TTDD 算法中，1.从源节点到 sink传输查询消息的开销是lNcnl?+，其中nl是sink节点洪泛开销67；2.从源节点到汇聚节点sink传输md个数据包的传输开销是mdNc?，其中 c为加权系数20c?，Nc?代表了传输路径上平均节点数目，同比TTDD 减少了2倍的能量损耗；3.更新查询任务开销为Nl，与TTDD 相比节省了构建虚拟方格的开销lN。因此，总的来说，与 TTDD 算法相比，C-TTDD 在能耗开销方面理论上降低了一倍。名师资料总结-精品资料欢迎下载-名师精心整

12、理-第 3 页，共 6 页 -http:/-4-3.3 算法仿真仿真条件假设如下：在300*300m 的观察范围内随机分布200个节点，每个传感器节点的初始能量为J1，bitnJEelec/50=为接收机电路和发射机电路处理1比特数据的功耗，2/100mbitpJmp=表示发射放大器向单位面积发射1比特数据的功耗。图3 分发节点的竞争图4 TTDD路由和 C-TTDD 路由名师资料总结-精品资料欢迎下载-名师精心整理-第 4 页，共 6 页 -http:/-5-图3为使用 C-TTDD 算法模拟的，在随机选择源节点传输100轮后，各 cell顶点的分发节点选取结果。其中绿点为汇聚节点sink，

13、黑点为虚拟的cell顶点，红点即为在以各自黑点为中心的正方形竞争区域内选出的剩余能量最大的传感器节点，即此轮的分发节点（m50=）。在相同的源节点和sink节点、相同的情况下，TTDD 和C-TTDD 的路径建立如图4所示，其中实线为改进后的C-TTDD 路由，虚线为沿虚拟方格边框传输数据的TTDD 路由。不管是在 TTDD 还是在 C-TTDD 中，cell的边长都是一个极其重要的参数，因为在算法中每个 cell顶点仅有一个分发节点，所以直接关系到了两个分发节点之间的平均距离，直接影响着网络的能耗和生命周期等性能。通过仿真找出TTDD 和C-TTDD 下各自的最佳cell边长。如表 1所示，

14、在各自虚拟方格边长条件下，C-TTDD 算法比 TTDD 算法生命周期提高了一倍左右并且在=50时打到最大值。表1 与网络生命周期关系边长 30 40 50 60 70 80 90 TTDD 182 180 179 185 190 175 183 C-TTDD 385 410 425 398 395 402 392 4.结论本文针对无线传感器网络典型处理移动sink的TTDD 算法，提出了改进的C-TTDD 算法：一是采用对角线组建网络路由，来处理最短路径问题；引入竞争机制，选择每个cell顶点附近采用能量剩余最大的节点作为转发节点；并一次性组建虚拟方格。通过对等参数的仿真，找到了网络的最优组

15、建方法，相比原有TTDD 算法在网络生命周期上提高了一倍以上。应该说，本文的算法仍然存在着很大继续改良的余地。比如在转发节点的竞争过程中，可以综合考虑减少传输距离节省的能耗和比较节点剩余能量消耗这两个方面，把原有TTDD的沿边路由方法和改进的对角线路由选择算法结合起来，寻找能耗更低的路由方法等。这些问题还有待在今后的研究工作中进一步加以深入讨论。参考文献1 孙利民，李建民，陈渝，朱红松，无线传感器网络，清华大学出版社，20052 F.Ye,H.Luo,J.Cheng,S.Lu,and L.Zhang,“A Two-tier Data Dissemination Model for Large-

16、scale Wireless Sensor Networks,”in Proc.Of the 8th Annual International Conf.on Mobile computing and networking.Atlanta,Georgia,USA:ACM Press,September 2002 3 Haiyun Luo,Fan Ye,Jerry Cheng,Songwu Lu,Lixia Zhang,“TTDD:A Twotier Data Dissemination Model for Largescale Wireless Sensor Networks”,UCLA Co

17、mputer Science Department Los Angeles4 应必娣,陈惠芳,赵问道,仇佩亮，“低能耗无线传感器网络路由算法”，传感技术学报2007年第五期5 杨明帅，“无线传感器网络路由算法研究”第四章，浙江大学6 C.Intanagonwiwat,R.Govindan and D.Estrin,Directed diffusion:A scalable and robust communication paradigm for sensor networks,in:Proceedings of ACM International Conference on Mobile C

18、omputing and Networking 7 D.Braginsky and D.Estrin,Rumor routing algorithm for sensor networks,in:Proceedings of Workshop on Sensor Networks and Applications(WSNA)名师资料总结-精品资料欢迎下载-名师精心整理-第 5 页，共 6 页 -http:/-6-Energy Controlled Two-Tier Data Dissemination in Wireless Sensor Network Qian Cheng，Zhang Lu

19、yong，Zhou Zheng Key Lab of Universal Wireless Communications，MOE Wireless Network Lab，Beijing University of Posts and Telecommunications，BUPT，Beijing（100876）Abstract This paper studies the TTDD routing algorithm in the wireless sensor network.In order to solve the energy limitation problem,we optimi

20、ze the algorithm in three aspects:build up the virtual network grids by the 1st source node;find out a line routing path between the source node and the sink node for data transfer;adopt a competition mechanism to select the dissemination node.The result shows that the new E-TTDD algorithm proposed in this paper has lower energy consumptions and a better utilization of nodes.Keywords：wireless sensor network，TTDD，energy consumption.作者简介：钱铖，男，硕士研究生，研究方向为无线传感器网络；张陆勇，男，副教授，硕士生导师，研究方向为无线传感器网络，信号处理等；周正，男，教授，博士生导师，研究方向为无线通信、信号处理等。名师资料总结-精品资料欢迎下载-名师精心整理-第 6 页，共 6 页 -