无线传感器网络综合了传感器技术、嵌入式计算技术、现代网络及无线通信技术、分布式信息处理技术等,能够通过各类集成化的微型传感器相互协作,实时监测、感知和采集各种环境或监测对象的信息,通过嵌入式系统对信息进行处理,并通过随机自组织无线通信网络以多跳中继方式将所感知信息传送到用户终端,从而真正实现"无处不在的计算".无线传感器网络可广泛用于军事、国家安全、环境科学、交通管理、反恐维和、灾害预测、智能城市建设等领域.其巨大的科学意义和应用价值,已经引起了学术界、工业界和军事部门的极大关注,成为当前热门的研究领域.美国《技术评论》把无线传感器网络列为未来十项新兴技术之首.《IEEE Spectrum》预计无线传感器网络的发展和广泛应用,将对人们的社会生活和产业变革带来极大的影响和产生巨大的推动.《国家中长期科学和技术发展规划纲要》和《国家"十一五"科学技术发展规划》将"传感器网络与智能信息处理"提升到信息产业发展的一个重点领域与优先主题,并把它列为具有前瞻性、先导性和探索性的重大前沿技术. 无线传感器网络因为不依赖于固定的基础设施,所以网络节点要求具有自组织的能力.一个节点进入工作区域之后,它只能依赖于MAC层和物理层所能提供的有限机制获得周围一跳(one-hop)邻居的信息,对全网的拓扑结构将一无所知.这时候需要有一个算法将这些分散的节点有效地组织起来,协调一致来完成某一个特定的任务,这一类的算法就叫做自组织算法.它为整个系统的运行构建拓扑基础,在此之上,各种路由协议、传输层协议以及应用程序才能正常运作,可以说,自组织算法是整个无线传感器网络的"基石". 自组织算法是与网络的拓扑构建与控制联系在一起的.一般来说,无线传感器网络的组织拓扑分为平面结构和层次结构,相应的,自组织的算法也分为基于平面结构的算法和基于层次结构的算法.层次结构与平面结构相比,在网络管理、系统扩展性、降低系统开销,提高网络吞吐能力以及QoS支持等各方面都存在明显的优势,所以随着应用的增加,大规模的无线传感器网络逐渐呈现出层次化的趋势,基于层次型结构的自组织算法是目前研究的重点.层次型结构的自组织算法一般包括分簇(clustering)方法与连通支配集 (Connected Dominating Sets) 方法.分簇方法是指在网络规划初期通过分布式算法将网络划分成簇头节点与普通节点.连通支配集的方法是利用图论中连通支配集的理论在传感器网络中构建类似于因特网的虚拟骨干网(Virtual Backbone),整个网络被划分成骨干节点集和普通节点集.在这两种方法中,簇头和骨干节点完成拓扑管理、路由构建与维护以及资源分配等功能. 论文的第三部分研究了无线传感器网络的分布式分簇算法.首先证明了经典IEACH算法的不确定性将会导致某些节点过快耗尽电池能量而缩短网络生存期.在此基础之上,提出了一种基于退避策略的负载均衡的分簇算法,通过自适应地调整每个节点的退避等待时间从而保证拥有较多电池能量的节点有更大的机会成为簇头,并引入信道竞争机制来保证簇头的均匀分布,仿真实验表明,该算法有效延长了系统生命,提高了网络的能耗效率.接下来作者进一步扩展了以上分簇算法的研究工作,提出了一种两参数的分布式分簇算法,该算法能够通过参数的设置确保簇头的均匀分布,从而避免了借助下层信道竞争机制来完成这一目的,降低了算法的实现复杂性.簇头分布均匀将会大大降低普通节点成为"被动型簇头"的可能,减少节点与基站进行远程通信的次数,节约有限的系统能量. 论文的第四部分研究了无线传感器网络异构分簇模型.近来提出的基于异构分簇模型的无线传感器网络,是指网络中存在多种不同能力的节点,能力强的节点自动成为簇头,这种网络避免了复杂的簇头选举过程并有效降低了普通节点的硬件复杂性和成本.但是,固定簇头的方法会削弱系统的负载均衡以及鲁棒性.为了解决这个问题,本文提出了一种基于自适应退避策略的簇头调度方案,该方案通过适当增加冗余度实现传感节点的k履盖,增强了网络的鲁棒性.同时,依赖于地理信息和剩余电池能量信息,簇头节点通过自主周期性睡眠来保证系统负载的均衡分配,延长网络生存期. 在论文的第五部分,研究了基于连通支配集(CDS)的虚拟骨干网形成算法.CDS的构造算法要尽可能地减少参与路由计算的节点数量,即生成最小连通支配集(MCDS).本文提出了一种分布式的CDS形成算法,通过去除虚拟骨干网中所有的三角形回路,有效减少了骨上海交通大学博士学位论文:无线传感器网络臼组织算法关键技术的研究干网中节点的数目.同时,该算法具有线性的时间和消息复杂性以及较低的实现复杂性.理论分析和仿真结果都显示本文的算法优于经典算法. 本论文的第六部分,研究了与数据融合相关的移动代理路由选择问题.在分簇结构的传感器网络中,簇中的传感器节点并不直接发送原始数据,而是由簇头发送移动代理到各个节点收集有用的数据,实现数据的融合.为了获取簇中节点的数据,在每一个数据融合周期内,簇头需要事先计算好移动代理的路由,即选择一条路线,在保证有用数据被采集到的前提下,使数据融合过程所消耗的能量最少从而最大化网络生存期.考虑到传感器节点覆盖范围有限以及相邻节点测量数据强相关性的特点,本文将多跳网络环境下的移动代理路由问题建模成为了一个顶点加权的游客问题,并且证明了这是一个NP完全问题.在此基础之上,提出了一种降低能耗的近似算法.仿真结果表明,该算法具有更高的能耗效率. 在最后部分,总结了全文,展望了未来的研究方向.