基于元胞自动机的无线传感网络整体行为研究.pdfVIP

第 57卷 第 11期 2008年 11月 物 理 学 报 Vo1．57，N0．11，November，2008 1000．3290／2008／57(11)／6896—05 ACTA PHYSICA SINICA ⑥2008Chin．Phys．Soe． 基于元胞 自动机的无线传感网络整体行为研究* 张文铸 袁 坚 俞 哲 徐赞新 山秀明 (清华大学电子工程系 ，北京 100084) (2008年 1月2日收到 ；2008年 5月 12日收到修改稿) 探讨 自组织通信 网络中局部行为与系统整体行为的关联 ，对于相关系统的设计和控制具有重要应用价值 ．利 用二维元胞 自动机模型对无线传感网络的拓扑控制过程进行模拟，可以分析节点间局部交互作用规则对网络整 体行为的影响．研究表明，在不同的局部演化规则作用下，该系统呈现出复杂的时空演化现象，发现系统整体行 为空间中存在振荡、衰减 、稳定等基本模式，并且该模型可 以反映系统内不 同全局 目标之间的折中关系，为进一步 研究无线传感网络整体行为的控制问题提供一种新 的途径 ． 关键词：自组织，元胞 自动机，通信网络，无线传感网络 PACC：0547，0565 表现出的突现行为实际上又是难以预测的．因此研 1．引 言 究 自组织通信系统的内在复杂性 ，对于解决大规模 通信网络系统的设计分析、操作控制、安全监测等问 互联网与无线对等通信 网络 的出现和广泛应 题有着重要的应用价值 ． 用，表明分布式 自组织结构已经成为通信系统的一 本文着重研究无线传感 网络的拓扑控制问题 ． 个重要发展方向．分布式的 自组织网络具有一些突 无线传感网络是一种典型的自组织通信网络，它由 出的特点：系统对动态环境的 自适应性、对单点故障 大量分布式的微小节点(传感器)构成，每个节点只 的鲁棒性 ，以及包容大量节点的可扩展性等等 ，这 能够与周围临近的节点进行通信 ，并依靠局部信息 是近年来 自组织通信网络快速发展的主要原因…． 做出行为决策 ．拓扑控制问题突出体现了无线传感 然而，在 自组织通信网络技术应用的同时，对 网络的这种 自组织特征 ：各个网络节点根据其邻居 于相应的设计和控制问题的理解还存在不足 ．一般 节点的工作／休眠状态来控制 自身状态的转换，在 而言，自组织是系统为形成和维护 自身空间上、时 尽量减少系统能量消耗的前提下，保证整个网络拓 间上或功能上的结构，在没有外部或集中控制的条 扑的连通性和覆盖性 ． 件下，节点层次所进行 的动态 自适应过程 ．随着系 本文用二维元胞 自动机模型对无线传感网络的 统规模增长，自组织通信网络的复杂程度越来越 拓扑控制过程进行模拟 ．元胞 自动机作为状态离散 高 ，一些关键问题逐渐 凸显 ．例如，在互联 网中路 系统，能够以简单的规则揭示复杂的全局特性 ，因 由更新过程中出现的同步现象 ，BGP路由协议出 而成为研究 自组织系统时空演化规律的重要工具 ． 现的全局路 由不稳定性 ，以及在无线 Ad—Hoc网 Wolfram等人详细分析研究了一维元胞 自动机的演 络节点的数量和位置引起 的相变现象 等等 ．一方 化行为，并在大量计算机仿真的基础上，将一维元 面 ，人们希望通过控制节点层次相对简单 的局部行 胞 自动 机 的演 化 行 为 归 纳 为 四类 ：平 稳 型 为，实现宏观层次的整体特性，如拓扑连通性、系 (homo