第 27卷 第 l2期
2010年 12月
计 算 机 应 用 研 究
Application Research of Compute ̄
V01.27 No.12
DeC. 201O
无尺 度 网络的数据 包传 输元胞 自动机模 型研 究 术
唐 红 ,廖荣南 ,胡 容
(重庆邮 电大学 网络与计 算研 究中心 ,重庆 400065)
摘 要:为 了更真 实地模拟 网络行为,提 出了一种基 于无尺 度 网络 的数 据包传输 元胞 自动机模 型 ,模型 中通过
增加缓存队列大小和提 高中心节点的处理速度来减少丢 包数 ,提 高网络性能。仿真结果表 明,在元胞 交互规则
的作用下 ,数据 包发送速率,缓存队列大小和丢包数在时间序列上都具有 自相似特性 ,自相似程度呈现 负相 关;
它们在时间序列上是长程相关的,在功率谱图中都具有幂律分布特性 ,在高频段呈现 出白噪声特性。
关键词 :无尺度 网络 ;元胞 自动机 ;丢 包数 ;自相似性 ;功 率谱 ;幂律特 性
中图分类号 :TP393.01 文献标 志码 :A 文章编 号 :1001—3695(2010)12—4686-04
doi:10.3969/j.issn.1001—3695.2010.12.084
Cellular automata model for packet transmission on scale—free network
TANG Hong,H AO Rong—nan,HU Rong
(Network& Computation Research Center,Chongqing University ofPosts&Telecommunications,Chongqing 400065,China)
Abstract:To simulate the network behavior more close to the reality,this paper brought a cellular automata model for packet
transmission under a kind of scale—free network.In this model,according to increase the size of buffer queue or promoting the
processing speed of the center node could reduce the discard packets and promote the network performance.The simulation re-
suhs show that there is the self-similarity property in the rate of packet,the size of buffer queue and the number of packet loss,
and the degree of its self-similarity presents negative correlation.They are long—range correlation on the time series,and their
high- ̄equency section presents white noise property in the power spectrum .at the same time there is the power-law property in
power spectrum . 。
Key words:scale-free network;cellular automata;packet loss;self-similarity;power spectrum;power·law
互联 网是一个 由大量路由器节点 以及这些节点 之间众多
的通信链路构成的无尺度网络 。大量研究表明,互联 网流量具
有自相似性,其拓扑结 构服从幂律 分布等复杂行 为特征 。 ,
对互联 网运行维护和管理控制 带来严 峻挑 战。研究这些 复杂
行为特征与互联 网内部运行机制 的关系对 于深 入理解 因特网
运行规律 ,更好地进行 网络及用 户管理 ,设计 高效的新 网络协
议 和新业务有着重要的理论和实践指导意义。
元胞 自动机是定义在一个具有离散 、有 限状态 的由元胞组
成的空 间上 ,按照一定局部规则在离散时间维上演化 的动力学
系统 。元胞在微 观层 面通过简单规 则进行交互 ,表 现 出宏
观上的一种突现行为。元胞 自动机模型最初主要用于生物,交
通 和地理信息系统等方面的动力学研究 。近年来 ,元胞 自动机
模 型也被应用到网络行 为 的研究 ,并且 因其结构简单 ,容易在
计算机上实现 ,能突现 出宏观上 的一些复 杂行为 ,已成为 网络
复杂行为的重要研究方法 j。袁坚等人 通过分 析一种计算
机 网络元胞 自动机模 型 ,对网络内部节点 的整体行为进行了探
讨,发现各 网络节点的吞吐量和缓冲区排队长度在空间和时间
上均呈现幂律分 布 ,网络节点的整体行为表现出 自组织临界现
象。刘锋等人” 提 出了描述计 算机互联 网络数据包 传输 的简
单元胞 自动机模 型 ,研究发现系统存在 自由流和拥塞 流两种相
态 。在 自由流状态 ,数据包排 队长度和传输时间均服从幂律分
布 ;在拥 塞状态 ,路 由节点数据 包排 队长度呈 现 白噪声 特性 。
雷霆等人 提出了一种 网络流 量的一维 元胞 自动机 模型 ,该
模型较好地描述了 网络从 自由流到拥 塞流的相变行为。Tang
Hong等人 利用一维元胞 自动机模 型对数据包传输过程进行
模拟 ,研究发现节点缓存服从 幂律分布 ,数据包 流量具有 自相
似性等突现行为。Xu Zan—xin等人 训利用元胞 自动机模型研
究 了域间路 由系统的行 为,研究 发现当大量节点存在于网络 中
时,将产生不期望的宏 观路 由行 为。贺正求等人 提出了一
种 自组织 的二维元 胞 自动机 网络模型 ,并研究 了网络中的临界
特征和长相关特性 。Yuan Jian等人 提 出了一种 基于 二维
元胞 自动机的网络模型 ,并对网络的整体动态特性进行了较为
深入 的研究。张文涛等人 利用二维元胞自动机模型对无线
传感 网络的拓扑控制过 程进行模拟 ,研究表 明 ,在 不同的局部
演化规则的作 用下 ,该系统呈现 出复杂的时空演化现象 。
为了能更 真实地研究互联 网中数据包传输的复杂行为 ,考
虑到互联网是无尺度网络这一特性 ,本文提 出了一种基于无尺
度 网络的数据包传输元胞 自动机模型。
1 无 尺度 网络的构 造
近年来众 多研 究者在 复杂 网络方面 发现 Internet、WWW、
收稿 日期 :2010-06-22;修回日期:2010-08-06 基金项目:国家自然科学基金资助项 目(60873079);重庆 市 自然科 学基金计 划重点项
目(CSTC 2009BA2089)
作者简介 :唐红(1957-),女 ,江西南昌人 ,教授 ,博导,CCF高级会员 ,主要研究方向为网络 流量与测量,网络行为学研 究(tan曲0ng@cqupt.edu.
cn);廖荣南(1986-),男,硕士研究生,主要研 究方向为网络行为学;胡容(1984.),女 ,硕士研究生,主要研究方向为网络行为学.