无线传感器网络中基于树的负载平衡算法研究

《无线传感器网络中基于树的负载平衡算法研究》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、无线传感器网络中基于树的负载平衡算法研究重庆大学硕士学位论文(学术学位)学生姓名：祝幸福指导教师：郭松涛教授专业：计算机应用技术学科门类：工学重庆大学计算机学院二O一四年四月ResearchonLoadingBalanceAlgorithmBasedonTreeinWirelessSensorNetworksAThesisSubmittedtoChongqingUniversityInPartialFulfillmentoftheRequirementfortheMaster’sDegreeofEngineeringByZhuXingfuSupervi

2、sedbyProf.GuoSongtaoSpecialty:ComputerApplicationTechnologyCollegeofComputerScienceofChongqingUniversity,Chongqing,ChinaApril2014重庆大学硕士学位论文摘要中文摘要随着微机电系统、片上系统、通信技术和低能耗嵌入式技术的快速发展，无线传感器网络（WSN）应运而生，已经成为计算机科学与技术的一个新兴领域。它有十分广阔的使用前景，目前已经应用到农业、军事、医疗、商业、环境等系统的各个方面。由于传感器节点自身携带能量低、不可充能、无人值守

3、等特点，极大程度限制了无线传感器网络的工作时间。在不知道节点具体位置的情况下如何建立一个高效连通的网络是目前面临的一个重要问题。本文针对WSN中的数据收集问题，以最大化网络生命周期为目的，在分析了大量网络协议的基础上，对不同类型的数据收集进行研究，建立不同的模型，提出了两种不同算法，并通过仿真实验验证算法性能。本文具体做了以下两方面工作：①针对精确数据收集，在不知道节点位置信息的情况下，提出一个网络负载平衡算法（LBAPDG）。它以最大化网络生命周期为目标，用多项式启发算法求解了一个需要构造最优生成树的NP完全问题。该算法首先通过Sink节点构造一棵具有最多孩

4、子的生成树，在这棵树的基础上，采用宏观的广度优先搜索不断转移瓶颈节点的子孙到其它负载较轻的节点上，网络负载依次从第一层节点开始逐层向下进行平衡，底层节点进行转移时不能影响高层的负载平衡，只能在某一子树内部进行转移。该算法以层为单位平衡网络的负载。②针对相关数据收集不能用LBAPDG算法解决的问题，提出了一个LBACDG算法。它以最大化网络生命周期为目标，根据稠密网络特点利用接收发送功率之间的相互关系，简化了网络模型。该算法通过贪心策略建立一棵初始就网络负载相对均衡的生成树，通过递归不断将负载较重节点的子孙转移到负载较轻的节点上，直至最后网络负载相对平衡。不同于

5、LBAPDG算法，节点转移算法采用深度优先搜索，不但可以转移节点，还可以直接转移子树。建树期间的贪心策略，可以减少节点转移期间的递归深度和次数，降低算法的复杂性。关键词：无线传感器网络，负载均衡，网络生命周期，精确数据收集，相关数据收集I重庆大学硕士学位论文英文摘要ABSTRACTWiththedevelopmentofsensortechnology,wirelesscommunicationtechnologyanddistributedinformationprocessingtechnology,wirelesssensornetwork(WSN)d

6、evelopsrapidlyandbecomesanemergingsubjectofcomputerscience.Ithasaverybroadprospect,andhasbeenappliedtothemilitary,commercial,health,environmentandotherfields.Inthispaper,wefocusontheproblemofdatacollection.Ourgoalistomaximizethenetworklifetime.Onthebaseofanalyzingalargenumberofnetwo

7、rkprotocols,westudydifferentdatacollections,builddifferentmodelsandpresenttwoalgorithms.Finally,wechecktheperformanceofthealgorithmthroughtheexperiments.Thispapercontainstwopartsmainly:①Foraccuratedatacollection,weproposeanalgorithm(LBAPDG)ofnetworkloadingbalanceinthecaseofunknowing

8、thegeographicalposi