1、毕业设计开题报告 测控技术与仪器 位置固定节点的无线传感网络广播算法研究 1 选题的背景、意义 无线传感器网络 (Wireless Sensor Networks， wSN)是集信息采集、信息传输、信息处理于一体的综合智能信息系统，是目前倍受国际关注、涉及多学科交叉知识、各项技术高度集合的前沿热点研究领域之一，它综合了微机电系统(Micro Electron Mechanical System， MEMS)、传感器技术、嵌入式计算技术、现代网络及无线通信技术、分布式信息处理技术等。作为一种新兴测控网络技术，它能够通 过各类集成化的传感器自主实现数据采集、融合和传输，并以自主多跳的网络方式传送给
2、用户终端，从而实现物理世界、计算机世界和人类社会三元世界的连通。无线传感器网络能够应用在军事国防、工农业控制、城市管理、环境监测、生物医疗、抢险救灾、防恐反恐、危险区域远程控制等诸多领域，具有非常广泛的应用前景， 由于无线传感器网络中节点数目庞大，使得其在组网和通信时要采用广播方式，以加快信息传播的范围和速度，从而可以节省电力。 广播是无线传感器网络最基础的通信方式之一，它的目的是将信息从网络中源节点发送给网络中其余的每一个节点。广 播可以实现网络的控制、时间同步、路由建立与维护资源分配与管理等。 广播在无线传感器网络中具有极为广泛的应用如节点向全网通告重要数据， sink 点向全网周期性查询
3、数据等简单泛洪 (flooding)可以实现广播这种方式虽然简单但极为耗能，而通常无线传感器网络节点电池容量有限且一般不可充电或更换，并且数据传输极为耗费能量所以简单泛洪并不适合无线传感器网络广播。无线传感器网络节点位置相对固定，但是节点数量巨大，密集高，冗余转播加剧了网络的拥塞、信道的竞争和数据冲突，从而降低网络的性能，增加节点的能量消耗，缩短 网络的寿命，因而设计优化无线传感器网络的广播算法有着现实意义。 2 相关研究的最新成果及动态 在国内外相关文献中相继出现了许多各具特点的无线传感器网络广播算法，但总的说来还有很多需要深入研究的问题。 (1)文献 3-4对泛洪广播方法进行了改进，提出了
4、基于概率、基于计数、基于距离等的广播策略。这些策略减少了冗余分组转播的数量，但是信道的竞争、数据冲突仍然较大，广播延迟较长，此外，还可能会丢弃一些非冗余的广播分组，无法保证广播分组的可达性。 在基于概率的算法中，节点在接收到数据包后以概率户转发数据包，以概率 l p丢弃数据包在基于计数的算法中，节点只有在接收到的数据包副本率小于设定的门限值时才转发数据包在基于位置的算法中，节点根据自身位置以及在一段时间内侦听到的其它发送节点的位置信息决定是否转发数据包这些算法虽然简单，但是减少的冗余节点数有限，性能改善并不明显 (2)基于连通支配集的路由算法的关键在于构造连通支配集，较小的支配集不但有利于构造
5、更优的路由，并且非支配节点在没有监测任务时，可进入休眠状态，从而极大的节约能量。据此提出了一种基于极大独立集构造最小连通支配集的算法 MISB：首先基于图的局部拓扑信息， 并利用贪心算法，使具有极大度的节点为独立点，构造出一个极大独立集；然后利用独立点作为锚点，利用分治的思想使用图的局部拓扑信息来连通极大独立集，从而构造出连通支配集。 MISB算法能够得到较小的连通支配集，应用于无线传感器网络路由，能够大大节省宝贵的网络资源。 (3)在节点发送功率可调节并同时保证所有节点都接收到广播的数据包的约束条件下，据此在 RBOP算法的基础上提出了一种高效节能的最小化能量广播算法ERBOP。 ERBOP
6、算法的设计过程及仿真结果表明， ERBOP的性能明显优于 RBOP。 ERBOP算法可节约无线传 感器网络的能量资源，能较好的适用于无线传感器网络的广播。 (4)从减少转发节点以节约能量、平衡通信量以平均消耗网络节点能量出发，提出了一种基于聚簇的能量感知广播算法 CBEA。仿真实验表明， CBEA算法有效减少了冗余转发节点从而节约了网络能量，平衡了网络通信量从而平均消耗了网络节点能量，因此大大延长了网络生存时间。 cBEA算法是一种性能优越的广播算法，能够较好的适用于无线传感器网络的广播。 （ 5）提出了 MPR方法。 MPR利用 2一 hop邻节点信息最小化转发节点集基于连通支配集的广播算法
7、 【 10-12】 是 目前研究得较多的一类广播算法，该类算法大多也是利用 2-hop邻节点信息计算连通支配集，只有支配节点才参与转发数据包这些利用 2-hop邻节点信息的广播算法虽然具有较好的性能，但需要更多的通信开销以获取和维护 2一 hop的邻节点信息，不适应拓扑变化 （ 6） 提出了一种仅利用 l-hop邻节点信息的边缘转发算法 EFB在 EFB算法中， 节点首先将其传输范围划分为 6个大小相等的扇形区域 图 l表示了节点 A的传输范围划分情况节点 A的 6个区域记为， Ap1， Ap2， ， Ap6，并记 表示两个相邻节点的区域相交情况 当 节点 B从邻节点 A接收到数据包后，确定自
8、身处于节点 A的哪个扇形区域中 EFB算法具有较好的性能，且只利用 1-hop邻节点信息通信开销较小 图 2中，不失一般性，假设节点 B处于节点 A的 Ap1区域节点 B不充当转发节点的条件是，在 Ap1区域与节点 B的各个区域相交的区域中，距离节点以最远的 3个边缘区域 Ap11， Ap12与 Ap16。中每个区域都存在其它节点，并且 Ap12中节点的传输范围覆盖了区域 a， Ap16，中节点传输范围覆盖了区域 6区域 a、 b表示了被节点 B的传输范围覆盖而没有被节点 A的传输范围覆盖的区域 EFB算法具有较好的性能，且只利用 1-hop邻节点信息通信开销较小 但我们发现 EFB算法仍存在
9、一些不足之处，在广播过程中还有冗余转发节点存在，影响了算法的性能 3 课题的研究内容及拟采取的研究方法（技术路线）、研究难点及预期达到的目标 （ 1）研究内容： 为进一步减少冗余转发节点，本文提出了一种利用 l-hop邻节点信息的基于传输范围覆盖的广播算法 TRCB在 TRCB算法中，由发送节点决定其 l hop邻节点是否参与转发，如果该节点被转发节点以及参与转发的 1一 hop邻节点覆盖。将不参与转发 （ 2）研究方法 ： 采用 Matlab作为仿真软件，在设定的区域内随机产生节点的二维坐标，并且当节点间的距离小于传输半径时节点相邻，每个节点都存储了其邻节点的坐标信息。然后利用本文算法进行仿
10、真 。 （ 3）研究难点 ： a. 节点 U 是否被集合 S 覆盖的问题。 b.计算节点 U 的转发节点集。 c. 计算节点 U0是否被集合 5 覆盖。 (4)预期达到目标： TRCB的转发率均远小于 EFB算法，性能远优于同样是利用 1一 hop邻节点信息的边缘转发算法 EFB 4 研究工作详细进度和安排 2010 年 10 月 15 日 12 月 15 日 阅读相关的资料； 2010 年 12 月 16 日 2011 年 01 月 10 日完成文献综述、外文翻译的撰写 ； 2011 年 01 月 10 日 02 月 25 日 完成 开题报告 ； 2011 年 02 月 26 日 04 月
11、08 日 完成系统框架设计 和 系统各模块功能设计 ； 2011 年 04 月 09 日 05 月 10 日 撰写论文，完成论文初稿 ； 2011 年 05 月 11 日 05 月 25 日 完成论文修改稿，准备答 。 5 参考文献 1崔莉鞠海玲苗勇。等无线传感器网络研究进展 J计算 机研究与发展 ,2005,42(1):163-174 2唐勇，周明天 ,张欣无线传感器网络路由协议研究进展 J软件学报，2006,17(3):410-421 3 CorsonM S,Macker J P,Cirincione G H.Internet-based mobile Ad Hoc networkingJ
12、.IEEE Internet Computing,1999,3(4):63-70. 4 Ni S Y,Tseng Y C,Chen Y S,et al.The broadcast storm problem in a mobile Ad Hoc networkC. Proc MOBICOM,1999:151-162. 5Cai Y， Hua K， PhiIlips A Leveraging 1-hop neighborhood knowIedge for efficient nooding in wireless ad hoc networksC Proc of the 24th IEEE I
13、nt l Performance Computing and Communications Conf ,Arizona,USA,2005,347-354 6Sasson Y,Cavin D， schiper A Probabilistic broadcast for fooding in wireless mobile ad hoc networksC Proc of the IEEE Wireless Communications and Networking Conf (WCNC 03)， New Orleans， Louisiana,USA，20031124 1130 7Tseng Y
14、Ni S， Shih E Adaptive approaches to relieving broadcast storms in a wireless multihop mobile ad hoc networkJ IEEE Transactions on Computers， 2003， 52(5):545-557 8Williams B,Mehta D， Camp T， et a1 Predictive modeIs to rebroadcast in mobile ad hoc networksJ IEEE Transactions on Mobile Computing，2004，
15、3(3)： 295 303 9Laouiti A,Qayyum A,Viennot L MuItipoint relaying;an efficient technique for flooding in mobile wireless networksC.Proc of the 35th Annual Hawaii Int l Conf.on System Sciences.Hawaii,USA,2002,298-307. 10Stojmbnovic I,seddigh M,Zunic J Dominating sets and neighbor elilIlination based br
16、oadcasting algorithms in wireIess networksJ IEEE Transactions on Parallel and Distributed Systems 2002， 13(1):114 25 11Wu J， Li H On calculating connected dominatillg set for efficient routing in ad hoc wireless networksC Proc of the 3rd Int I Workshop on Discrete Algofithms and Methods for Mobile Computing and Communications， USA 1999,7-14 12Wan P， Alzoubi K,Frieder O Distributed construction of connected dominating set in wireless ad hoc networksc Proc of IEEE Infocom,USA，2002 1597-1604 13 卢先领 .无冲突的无线传感器网络广播算法 .计算机工程与设计， 2008.
