湖南大学 硕士学位论文 无线传感器网络中高效广播与数据聚集算法的设计与实现 姓名：高利 申请学位级别：硕士 专业：计算机应用技术 指导教师：李仁发 20070319 硕士学位论文 III 摘 要 广播与数据聚集在无线传感器网络中有着广泛的应用。广播是将信息从网络 中的某个节点分发到网络中所有节点的过程，数据聚集是每个节点将采集的信息 集中到网络中的某个中心节点的过程。由于传感节点的计算能力、存储容量、能 量受限等特点使得传统无线技术不能直接应用在无线传感器网络中，因此设计简 单高效的广播与数据聚集算法显得至关重要。 本文首先介绍了无线传感器网络的一些基本概念、原理以及应用发展情况， 然后对无线传感器网络广播与数据聚集算法的研究成果及其所面临的问题进行了 探讨。在深入研究蚁群算法和现有广播与数据聚集算法的基础上，针对目前广播 算法存在的约束考虑较为单一、没有考虑与能量的约束融合、仅局限于单纯的启 发式算法等缺陷提出了基于蚁群系统的广播算法。基于蚁群系统的广播算法利用 无线传感器网络的广播问题与旅行商(TSP)问题间的相似性， 将无线传感器网络模 型描述为一个加权图，采用蚁群系统的群体智能和正反馈机制，从满足给定约束 条件，优化能耗平衡度量的角度找出传感器网络拓扑中满足最小能耗并且可靠的 广播路径。通过仿真工具 OMNET+进行仿真实验，将新算法同以往算法进行了 性能比较，结果表明新算法在能量有效性、网络生命周期和延迟方面具有明显的 优势。 由于蚁群算法在解决组合优化问题方面显示出强大的优势，本文用它设计了 一种无线传感器网络中提供选播服务的数据聚集算法。在很多无线传感器网络的 应用中，常常忽视了相关数据聚集的一个重要的尺度融合代价，该代价和传输 代价一样也极大地影响了路由的确定。该算法将融合代价作为相关数据的选播路 由优化的另一个尺度，利用蚁群系统的正反馈性，在最小化总能耗的条件下，实 现了相关数据的融合，极大地提高了路由的性能。分别讨论了网络连通性、sink （基站）个数，相关系数和融合代价不同时，由该算法得到的总能耗，OMNET+ 仿真验证了它的有效性。该算法对于处理矢量数据或安全要求较高的传感网络具 有重要的意义。 关键词：无线传感器网络；广播与数据聚集；高效；蚁群系统；融合代价 无线传感器网络中高效广播与数据聚集算法的设计与实现 IV Abstract Many sensors applications need to use the broadcasting and data gathering. Broadcasting is to dispense the information from some node to other nodes in the networks. Data gathering is to collect all other nodes information to some central node. Sensor nodes computing ability, storage capability and energy is limited. which makes it impossible to apply traditional wireless technology in wireless sensor network directly. So it is crucial to design simple and effect broadcasting and data gathering algorithms. At first, some basic concept, principle and development of wireless sensor network are reviewed in this thesis. Afterwards, the relevant research results and the problems of broadcasting and data gathering in wireless sensor network are studied deeply. On the basis of studying ant colony algorithm and existing broadcasting and data gathering algorithms, the broadcasting algorithms based on ant colony system are presented in order to solve some problems of existing broadcasting algorithm, such as restrictive condition is single, energys restriction is not been considered or some simple heuristic algorithms are used. The broadcasting algorithms based on ant group system make use of the comparability of the broadcasting in wireless sensor network and TSP, describe wireless sensor network model as a map with power, and adopt ant systems capacity and plus feedback mechanism, and according to the given restrictive condition, to find out the credible broadcasting path, which satisfy the minimal energy. Simulation is operated with OMNET+. And the simulation results show that, the presented algorithm is simpler and more practical in energy validity, lifecycle of network and delay than traditional algorithm. Because of the advantages of ant system in resolving combination and optimizing problems, a data gathering algorithm based on ant algorithm is proposed. Fusion cost-an important characteristic of data gathering is often been neglected in some applications of wireless sensor network. It is the same with transmission cost to route. Different from existing schemes, the algorithm not only optimizes over the data transmission cost, but also incorporates the cost for data fusion. It makes use of ant group systems plus feedback character, achieves correlative datas gathering in the condition of minimizing total energy. Through extensive simulation results, it is shown that this algorithm has excellent performance behavior and provides a 硕士学位论文 V near-optimal solution when the connectedness of network, the number of sink, correlative coefficient and fusion cost are different, which is significant for emerging sensor network with vectorial data and/or security requirements. Key words: Wireless sensor network；Broadcasting and data gathering；Efficient； Ant colony system；Fusion cost 无线传感器网络中高效广播与数据聚集算法的设计与实现 VI 插图索引 图 1.1 无线传感器网络通信体系结构图 .2 图 1.2 无线传感器网络节点的结构图 .2 图 2.1 扩散法.7 图 2.2 算法的链构造过程 .9 图 4.1 多 sink 下的数据聚集示例图 .25 图 5.1 简单和复杂模块.30 图 5.2 OMNET+的 gate 与 Connection .31 图 5.3 网络模块构成图.32 图 5.4 节点模块结构.33 图 5.5 40 个节点的随机分布图.35 图 5.6 不同