南京航空航天大学 博士学位论文 无线传感器网络自组织演化模型及其关键技术研究 姓名：姜楠 申请学位级别：博士 专业：计算机应用技术 指导教师：丁秋林 20081101 南京航空航天大学博士学位论文 I 摘摘 要要 无线传感器网络作为新兴的信息获取技术，融合了嵌入式计算、无线通信、 微机电、传感器等多学科技术，是目前信息科学领域的研究热点之一。研究大规 模的密集部署的无线传感器网络的演化机制以及构建相应的自组织演化模型， 可 以真实再现其拓扑特征，有利于网络整体性能的分析和评估以及网络协议的设 计。目前，无线传感器网络的自组织演化模型还处于探索阶段，发展还不成熟。 研究人员一方面研究更加真实的演化模型， 另一方面研究某种模型的实际应用和 工作效率。 在分析复杂网络理论的原理和概念的基础上，根据真实的网络演化行为，形 成新的无线传感器网络自组织演化模型， 以期进一步深化无线传感器网络的拓扑 建模和路由等关键技术的研究。本文的主要研究工作如下： (1) 研究了无线传感器网络的小世界演化模型，提出了基于小世界理论的无 线传感器网络广播算法和选播路由算法 研究了无线传感器网络中的 AH-WS 小世界演化模型以及 Two-Radius 小世 界演化模型，借助于小世界网络高集聚系数和低平均路径长度的特征，将 Two-Radius 小世界演化概念分别引入到无线传感器网络的数据广播和汇聚选播 路由算法当中，同时利用了蚁群算法的启发式搜索，分别提出了一种基于小世界 演化模型的无线传感器网络的单 Sink 节点数据广播算法（SWPBA）和一种小世 界演化模型的无线传感器网络的多 Sink 节点选播路由算法（SWPAR） ，并分别 给出了两种算法的实现。 SWPBA 算法同已有的广播算法相比， 在单次广播能耗、 单次广播等待时间和网络生存时间三种性能指标均有一定程度的提高。而 SWPAR 算法同已有的选播算法相比，可以有效解决目前选播当中所存在的能量 空洞、最热路径以及 Sink 节点瓶颈问题。 (2) 提出了一种无线传感器网络节点随机部署演化模型 如何对无线传感器网络的节点进行有效的部署是其应用必须要解决的问题 之一。在连续介质演化模型以及组合演化模型的基础上，提出了一种节点的度分 布服从幂律指数的节点随机部署演化模型， 并且对该模型利用连续介质理论进行 解析得到度分布指数在 2 到 3 之间； 同时设计了无线传感器网络拓扑生成器对该 模型进行了仿真验证。 (3) 提出了一种无线传感器网络局域世界演化模型 无线传感器网络自组织演化模型及其关键技术研究 II 在经典 L-C 局域世界演化模型与 S-R 演化模型的基础上提出了一种无线传 感器网络局域世界演化模型。 该演化模型考虑了无线传感器网络中的四种演化行 为：节点的增加，节点的失效，节点之间发起新的连接以及链路失效，同时将四 种演化行为扩展到模型的动力学过程中， 使用连续介质理论分析了节点的度分布 特征，得出了该模型的度服从指数3=的幂律分布；并通过仿真验证了该模型 的有效性以及该模型对于节点的随机故障以及失效具有较高鲁棒性。 (4) 提出了一种无线传感器网络分簇演化模型 分簇现象在大规模的传感器网络广为存在。 已有的分簇模型均假设节点到达 时间服从均匀分布以及没有考虑节点的失效机制。基于 Poisson 增长模型，提出 了一种无线传感器网络分簇演化模型， 该演化模型考虑了四种分簇过程的动力学 行为：簇首的建立，普通节点与簇首的优先链接，普通节点的失效以及普通节点 的迁移四种情况，通过理论解析得到了簇容量及其指数分布情况，通过仿真实验 验证了理论分析的正确性。 关键词：关键词：无线传感器网络，演化模型，小世界网络，广播与选播，无标度网 络，分簇 南京航空航天大学博士学位论文 III ABSTRACT As an emerging information access technology, Wireless Sensor Networks (WSNs) is currently one of the hot spots in the research field of information science. It converges embedded computing, wireless communications, sensors and other multi-disciplinary technology. Research on evolving mechanisms and building corresponding self-organizing evolution model of wireless sensor networks, which are large scale and intensive deployment, can reproduce its true features of topology, which is conducive to the overall analysis and assessment of network performance, as well as design of network protocols. Currently, research on evolution model of wireless sensor networks is still in the exploratory stage, and its development is not yet ripe. On the one hand, more and more researchers devote their enthusiastic energy to explore and characterize the evolution model; on the other hand, the researches dedicate the practical application and the work efficiency of the evolution model. Based on the analysis of complex network theory and the dynamics of actual networks, new self-organizing evolution models and corresponding applications of wireless sensor network are designed. The main contributions of this dissertation are summerized as follows： (1) Based on research of the small-world evolution model, the broadcasting algorithm and the anycast routing algorithm of WSNs are proposed. Broadcasting and Anycast Routing are important operations and been widely used in wireless sensor networks. These networks are power constrained as nodes operate with limited battery power. Wireless sensor networks are spatial graphs that having much more clustered and much high path length characteristics. We investigate the small-world evolution model in WSNs.After considering energy efficient broadcasting and anycast routing in such networks, combined the two-radius evolution model and the heuristic search of ant algorithm, Small-World Power-aware Broadcasting Algorithm (SWPBA) with single-sink and Small-World Power-aware Anycast Rouing algorithm (SWPAR) with multi-sinks are proposed. Given different densities of network, simulation results show that SWPBA significantly improves life of networks, also reduces waiting time and power consumption, and SWPAR can effectively resolve the problems of energy holes, hottest path and sink bottlenecks. 无线传感器网络自组织演化模型及其关键技术研究 IV (2) A stochastic placement evolution model of WSNs by is proposed Power-Law topology has been proved to be an effective technique to improve fault tolerance. A power-law evolution model of wireless sensor networks by stochastic placement is proposed. In dynamic evolving process of WSNs, there are four types of events as follows: adding new nodes, nodes failure, adding new links and links failure. The dynamics of nodes and links are integrated into the evolving model consequently. By using continuum theory, the theoretical computing and simulated results show that the degree distribution of this model follows a power law. The scale-free properties revealed in this model display a tempting application foreground. (3) A local-world evolution nodel of WSNs is proposed Making use of the mechanisms of link compensation and local-world preferential attachment, a local-world evolution nodel of WSNs is proposed, which is based on the classic S-R mo